https://a16zcrypto.com/posts/article/measuring-snark-performance-frontends-backends-and-the-future/
<aside> 💡 Can you explain what an intermediate representation in context of SNARKs?
The program ψ is then fed through a SNARK frontend that compiles it into a format that is more amenable to application of SNARK technology. This SNARK-friendly format is called an intermediate representation (IR).
How is this representation used in backend? Maybe give a concrete example of what this IR actually looks like?
</aside>
<aside> 💡 Please go into detail how a proof relates to the backend in terms of different PCSs and Information theoretic components (IOPs, etc)
</aside>
<aside> 💡
This article gives this statement: "“CPU emulator” projects such as RISC-V and Cairo produce a single circuit that can handle all programs in the associated assembly language. "
That means regardless of the opcodes, all programs will be compiled to the same circuit.
</aside>
<aside> 💡
Can you help explain this more:
The final component of frontend overhead comes from the fact that all SNARKs use circuits that operate over finite fields. The CPU on your laptop can multiply or add two integers with a single machine instruction. If a frontend outputs a circuit over a field of large enough characteristic, it can essentially simulate that multiplication or addition via the corresponding field operation. However, implementing the field operation on a real CPU will typically require many machine instructions (although some modern processors do have native support for certain fields).
What do they mean by real CPU? can you illustrate an example of a say a gate in the circuit that is run over a CPU?
</aside>
<aside> 💡 can you help explain this passage:
Some SNARK backends enable more flexible field choices than others. For example, if the backend makes use of a cryptographic group G, the circuit’s field has to match the number of elements in G, which can be limiting. In addition, not all fields support practical FFT algorithms.
Why is FFT algos important?
why would you want to convert coefficients to evaluations in polynomials or vice versa? Any concrete ecamples with real proof systems you can provide to enlighten this subject?
</aside>
<aside> 💡 can you explain this paragraph better:
Some projects have chosen to work over fields with particularly fast arithmetic. For example, Plonky2 and others use a field of characteristic 2^64 – 2^32 + 1 because arithmetic in this field can be implemented several times faster than in less structured fields. However, using such a small characteristic may lead to challenges in efficiently representing integer arithmetic via field operations. (For instance, multiplying a 32-bit unsigned integer by any number larger than 2^32 might yield a result greater than the field characteristic. Hence, the field choice naturally supports arithmetic only on 32-bit numbers.)
How can arithmetic be implemented faster? can you give an example? Also how can it lead to challenges for representing integer arithmetic via field operations? Can you give an example?
</aside>
<aside> 💡 can you explain this new section
"SNARKs for circuit-satisfiability are typically designed by combining an information-theoretically secure protocol called a “polynomial IOP” with a cryptographic protocol called a “polynomial commitment scheme.” In most cases, the concrete bottleneck for the prover is the polynomial commitment scheme. In particular, these SNARKs have the prover cryptographically commit to one or more polynomials whose degree is (at least) |C|, the number of gates in the circuit C. In turn, the concrete bottleneck within the polynomial commitment scheme will depend on the scheme used and the circuit size. But it will always be one of the following three operations: computing FFTs, exponentiations in a cryptographic group, or Merkle-hashing. Merkle-hashing is typically a bottleneck only if the circuit is small, so we will not discuss it further. "
why is committing a bottleneck, and why does # gates determine prover time? Please give a concrete example of a case. In a PCS, when does it have to consider computing FFTs, exponentiations in a group, and merkle hashing? Also, can you map out a table of PCSs and their circuit size, and the degree of how intense computing FFTs, exponentiations in a group, and merkle hashing.
</aside>
<aside> 💡 when you take exponentiations, will it always be to the coefficient of the polynomial, or can it be the evaluation? Where does FFT help exponentiations? If a scheme uses merkle hashing, at what result of the FFT will it require to move to merkle hashing? In other words, what will determine if the leaves will be evaluations or coefficients.
I am just confused with the relationship of FFTs and the decision for exponentations and merkle hashing
</aside>
<aside> 💡
"In polynomial commitments based on the hardness of the discrete logarithm problem in a cryptographic group G (KZG, Bulletproofs, Dory, and Hyrax-commit), the prover has to compute a Pedersen vector commitment to the coefficients of the polynomial. This involves a multi-exponentiation, of size equal to the polynomial’s degree. In SNARKs, this degree is typically the size |C| of the circuit C.
Done naively, a multi-exponentiation of size |C| requires about 1.5·|C|·log |G|≈ 400·|C| group operations, where |G| denotes the number of elements in the group G. However, there is an approach, called Pippenger’s algorithm, which can reduce this by a factor of roughly log |C|. For large circuits (say, |C| ≥ 225), this log |C| factor can concretely be 25 or more, that is, for big circuits, we expect that the Pedersen vector commitment may be computable with a little over 10·|C| group operations. Each group operation in turn tends to be (as a very rough ballpark) about 10x slower than a finite field operation. SNARKs using these polynomial commitments are as expensive for P as about 100·|C| field operations. "
What are multiexponentiations and why are they needed in this context?
</aside>