Original Title: "A technical FAQ on Lasso, Jolt, and recent advancements in SNARK design"

Original Author: Justin Thaler

Translated by: Luccy, BlockBeats

Editor's Note:

On November 20th, Ben Diamond and Jim Posen (D&P) of Ulvetanna released a paper that improved upon sum-check based polynomial IOPs and integrated them with sum-check based SNARKs (such as Lasso) along with faster provers and larger proof size commitment schemes Ligero/Brakedown. After a thorough analysis of the technology by Justin Thaler, a research partner at a16z, various researchers raised questions about the content of the article.

Related Reading: "a16z: Lasso+Jolt, a new prospect for fast commitment"

This FAQ consolidates 13 questions, answering various questions about Jolt Prover performance, D&P's choice of Keccak and Grøstl hash functions, and the security of hash-based commitment schemes. In addition, the answers cover the basic relationship between Lasso and Jolt, the performance advantages of using Reed-Solomon codes, the advantages of Ligero/Brakedown over FRI, and an explanation of D&P's commitment to GF[2] elements.

The discussion focuses on the implementation of the entire computation as a Boolean circuit, the benefits of work in characteristic two fields, and the technical and cost issues of combining SNARK proofs and D&P commitment schemes with elliptic-curve based SNARKs through recursive composition. Finally, the article raises the question of whether SNARKs using D&P's commitment scheme can be combined with folding schemes (such as Nova). In-depth research on these issues is expected to promote technological innovation and further improvement in this field.

Q1: How fast do you think the Jolt prover will be once it is re-implemented to use D&P's commitment, compared to native execution of RISC-V programs?

A: Here is a rough and speculative estimate. The Jolt prover is expected to commit about 800 bits of data per RISC-V CPU, using 32-bit data types and multiplication extensions. It is important to note two things: first, some RISC-V instructions are processed through multiple pseudo-instructions. For example, the division instruction verifies both the quotient and remainder provided by the prover through multiplication, addition, and inequality checks. Second, this estimate of the number may be slightly adjusted after parsing the lookup table decomposition of GF[2128].

Using the commitment scheme of D&P and assuming that recursion will not become a bottleneck, the main commitment costs in T steps of calculation are as follows.

First, apply additive FFT to the total of approximately 200T bytes of data. Specifically, Ligero/Brakedown provers perform O(√T) independent FFTs of size O(√T) (which involves less total work and can be better parallelized than performing a single FFT of length O(T)). Second, hash the approximately 200T bytes using standard hash functions such as Keccak or SHA2.

Based on experience, D&P found that FFT and hash are roughly equivalent in prover time.

Using Keccak hash, it is estimated that each byte requires about 70 RISC-V cycles. These operations are about 30,000 times slower than running an unproven RISC-V program. In other words, in order to prove that the Jolt prover has correctly run a RISC-V program Ψ, the prover itself (implemented in RISC-V) will need at least 20,000 more cycles than Ψ itself.

These cost commitments are "fast" enough to indicate that the bottleneck for the prover may lie in the limited field operations performed in the overall verification protocol, even when considering optimizations for small feature fields. Therefore, roughly estimating, I guess that the Jolt prover (implemented in RISC-V) will be about 50,000 times slower than just running a RISC-V program.

The whole calculation is a bit absurd: when Jolt is deployed, the prover itself is unlikely to be implemented by RISC-V. But this does give a rough idea of how to estimate the cost of zkVM prover.

Although a 50,000-fold slowdown may seem significant, it is 20 times faster than the optimistic estimate of 1 million-fold overhead I made about 18 months ago. The main reason for this improvement is that the commitment data unlocked by Lasso and Jolt is smaller (as well as the smaller size of each commitment value). The remaining reasons are attributed to better commitment schemes (such as improved use of fast hash functions and the ability to use commitment values on a small scale in hash-based SNARKs).

Q2: D&P provides fast SNARKs for Keccak and Grøstl. Why choose these hash functions? What other hash functions are suitable for these technologies?

BlockBeats Note: Grøstl is a cryptographic hash function.

A: Keccak/SHA3 is an obvious choice because it is a NIST standard, an Ethereum precompile, and a key bottleneck for Type-1 zkEVM. SHA3 is the official NIST standard, and Keccak is an Ethereum precompile. They are cost-agnostic when it comes to SNARK.

D&P considered Grøstl because it was expected to lead to faster provers while retaining many of the advantages of Keccak. In particular, Grøstl underwent strong cryptographic analysis despite ultimately not being selected, but because it made it to the final round of NIST's SHA-3 competition and uses AES S-box. Due to the AES acceleration instruction AES-NI, Grøstl even runs faster than Keccak on Intel chips.

The prover of D&P should be faster for Grøstl than for Keccak, because Grøstl is basically locally defined on GF[28], which means that the prover of D&P can commit to fewer field elements than Keccak. (For more information on how this benefits the prover, see Q9.) Overall, Grøstl should be more suitable for (recursive) SNARKs than Keccak, as it is faster on both the prover and the chip.

D&P's SNARKs are unrelated to Keccak and Grøstl. These technologies should be applicable to many other hash functions. For example, D&P believes that SHA2 should be as good as Keccak, but it has not been studied in detail yet.

Q3: I thought Lasso/Jolt was a commitment scheme for elliptic-curve cryptography?

A: No, Lasso and Jolt are not specifically designed for curve-based commitment schemes. However, their advantages are most evident when combined with curve-based commitments compared to previous work a few months ago. This is because when the prover has to commit to random field elements, curve-based commitments incur a particularly high cost. Therefore, the novel capabilities of Lasso/Jolt avoid this situation and have the most notable performance impact when these commitments are used.

In short, although no one has previously designed the use of SNARKs based on curve commitments to leverage promised small values, to some extent, hash-based commitments working on small fields have already utilized this.

However, even with hash-based commitments, Lasso and Jolt have improved on previous work in two ways. First, D&P showed that hash-based commitments can benefit more strongly from only committing to small-domain elements compared to previously known methods. For example, while today's commitment schemes have the same prover cost for committing to 1-bit values and 32-bit values, using D&P's scheme makes committing to 1-bit values almost 32 times cheaper. Second, Lasso and Jolt not only ensure that the prover commits only to small-domain elements, but also ensure that the prover commits to fewer domain elements than non-sum-check-based SNARKs. In fact, in Jolt, we carefully calculated the total bit complexity of all committed domain elements and confirmed that it is much smaller than the work done in existing zkVMs.

A few months ago, when Lasso/Jolt was released, another technical issue highlighted the curve-based commitment: the only hash-based commitment scheme with logarithmic polynomial proof size, FRI, is for univariate polynomials, while Lasso/Jolt uses multilinear polynomials. Several known transformations adjust FRI to be applicable to multilinear polynomials, but these transformations add what we consider to be unacceptable overhead in terms of prover time, proof size, or both. BaseFold now allows for "direct" multilinear commitments with logarithmic polynomial proof size, although the resulting proof speed is slower than Brakedown and the proof size is larger than FRI.

Unlike FRI, Ligero/Brakedown promises schemes that are directly applied to multilinear polynomials and have very fast provers. However, in the past, it was difficult to apply recursion to reduce the size of its proofs because verifiers performed a large number of hash operations, making recursion expensive. By providing faster SNARKs for hashing, D&P's work will greatly reduce the cost of this recursion.

Q4: Didn't you say that curve-based commitment schemes are faster than hash-based schemes (when committing to small values like Lasso/Jolt)? Isn't this contradictory to your endorsement of D&P's SNARKs?

A: First of all, as I mentioned earlier, there are some important SNARK use cases, and hash-based SNARKs are clearly not the optimal choice in terms of performance, as working on the base field of elliptic-curve groups makes more sense. When using these fields, curve-based commitments are faster. Any statement about elliptic-curve cryptographic systems (including knowledge about ECDSA digital signature authorized blockchain transactions) falls into this category.

Secondly, even in applications that use small feature domains, the performance comparison between hash-based schemes and curve-based schemes is complex. For example, it largely depends on how fast the hash function used in the hash-based scheme is. Today, many (but not all) projects use slower hash functions such as Poseidon to achieve recursion. With such hash functions, hash-based schemes are significantly slower than curve-based schemes when promising small values (such as Lasso/Jolt). Even with fast hash functions, it is not clear whether they are faster (as I mentioned earlier).

However, D&P accelerates hash-based commitments, making them more efficient when using a domain with a feature of 2, and allowing provers to better utilize the small scale of commitment values compared to existing hash-based schemes such as FRI. Therefore, my current expectation is that Ligero/Brakedown will be the way forward in the domain with a feature of 2, unless proven otherwise with local definitions on other finite fields.

Anyway, until today, it is widely believed that hash-based commitment schemes are faster than curve-based schemes mainly because popular SNARKs like Plonk require the prover to commit to random field elements rather than small field elements, and in this case, curve-based commitment schemes are very slow. Lasso and Jolt show that the prover does not need to commit to random field elements. In this case, the comparison is at least more detailed. Until today, curve-based schemes are actually faster, but with the improvement of D&P, the situation is reversed (except for cases defined locally on large fields).

Q5: Didn't you say that hash-based commitment schemes have lower security?

A: Hash-based commitment schemes like FRI or Ligero/Brakedown themselves are not insecure. However, projects generally prioritize performance over security, deploying FRI on configurations where known attacks are close to feasible and assuming that these known attacks on FRI are optimal.

One benefit of the Ligero/Brakedown commitment scheme is that the security of the main conjecture about FRI, which is not related to the security of the conjecture under neighboring parameters outside the Johnson boundary, is not relevant. Therefore, SNARK designers do not have an incentive to base security on this conjecture.

A: Yes.

Brakedown's polynomial commitment scheme encodes subvectors of the values to be committed using any necessary error-correcting code. Suppose the values to be committed are in GF[2], but we want the encoding itself to operate on a larger field, GF[2^16]. There are many technical reasons why we want to do this, and in fact it is necessary if we want to apply certain encodings to vectors of length up to 216.

In order to achieve this, we can simply use code concatenation, which involves dividing all GF[2] values into blocks of size 16 and "packing" each block of 16 GF[2] values into a single GF[2^16] field element. This will reduce the number of field elements to be committed by a factor of 16. Then, we can apply any error-correcting code that runs on the GF[2^16] field, which is called the "outer code". Each symbol of the resulting codeword can then be "unpacked" into sixteen GF[2] elements and encoded using the "inner code" defined on GF[2].

This simple method, which uses the concatenated code application Brakedown, has achieved many benefits of D&P work. However, D&P uses a different approach, resulting in faster prover speed (at the cost of slightly larger proofs). For example, D&P's actual method avoids the cost of applying inner codes to each unpacking symbol of external codewords.

Q9: Since the commitment scheme of D&P makes the values in {0,1} very cheap to commit, why not let the prover only commit to the bit decomposition of all values appearing in the computation? In other words, why not use boolean circuits to implement the entire computation and let SNARK assign a "complete" field element to each input bit and gate in the circuit?

A: In their SNARK for Keccak, D&P indeed makes the prover commit to values in {0,1}, but this may not always be a good idea in general.

Indeed, the commitment time of D&P is roughly proportional to the sum of the bit complexities of all commitment values, regardless of how many field elements these values are distributed over (which is why committing to only one bit value in Keccak's SNARK is a reasonable idea).

However, this does not mean that all costs are unrelated to the number of committed field elements. In particular, the size of the commitment scheme's evaluation proof is proportional to the square root of the number of committed field elements.

D&P uses a protocol based on sum-checks to pack many one-bit values into a single field element after these values have been committed, in order to reduce the cost of committing many one-bit values. This allows them to avoid paying too much for sum-check proofs for many committed values in terms of time, while still being able to enjoy their benefits (especially once the commitment has been bit-decomposed, certain operations such as bitwise AND do not incur any additional commitment cost when proven by sum-checks).

Q10: What are the specific advantages of D&P using features with a binary field?

D&P extensively utilizes tower constructions. In the context of fields with characteristic two, this refers to constructing GF[22] as a quadratic extension of GF[2], then constructing GF[24] as a quadratic extension of GF[4], then constructing GF[28] as a quadratic extension of GF[24], and so on. In particular, for fields with characteristic two, highly efficient tower constructions are known to exist.

Calculate the sum of the polynomial g with multiple variables in the summation of x belonging to 0,1^n in the sum-check protocol. The size of the Boolean hypercube {0, 1}n (and its sub-cubes) is a power of 2, so the subfields and sub-cubes align well. D&P takes advantage of this to make it easy to pack many small field elements into a single element of a larger extended field.

D&P currently uses Reed-Solomon encoding in the Ligero/Brakedown polynomial commitment scheme. Efficient Reed-Solomon encoding requires additive FFT, which is very effective in fields of characteristic two but not so much in other fields. However, using other encodings can completely avoid the need for FFT.

Features of binary fields are well-handled in actual hardware. Real-world computers are based on data types that are powers of 2 in size. You can perfectly fit the largest amount of information in registers, cache lines, etc. without padding. Intel even built in primitive instructions for performing very fast arithmetic in GF[28] in its chips (Galois Field New Instructions [GFNI]). This can be used to achieve very fast GF[2k] arithmetic even for k > 8 when using tower constructions.

Q11: Does recursively combining SNARK proofs with themselves using D&P's commitment scheme remove the limitation of SNARK proofs becoming small?

A: Yes, the "recursive threshold" promised by Ligero/Brakedown's SNARK is relatively high. The recursive threshold refers to the size of the proof, that is, by recursively applying the Brakedown/Ligero-based SNARK to the verifier, no shorter proof can be generated. I expect the recursive threshold to be on the order of several MB.

If you want to obtain smaller proofs, I believe it can be achieved by combining with other smaller proofs of SNARK, please refer to Q12 for details. If this assumption is ultimately proven to be incorrect, it should not be regarded as Binius' failure, but as a criticism of the scalability of popular SNARKs today. If they cannot prove that several MB of data has been hashed in a reasonable time, how can we say that they are scalable?

Regardless, there are other important reasons for fast recursive composition besides reducing proof size. Most importantly, it is a key tool for controlling proof space requirements. Since (non-recursive) SNARKs take up a lot of space for the prover, people break up large computations into small chunks, prove each chunk separately, and use recursive proofs to "link" these chunks together. D&P's fast SNARK for standard hash functions (such as Keccak) enables this recursive proof to be done quickly, even if the proof size is somewhat large.

Q12: Suppose you want to combine D&P's commitment scheme with elliptic-curve-based SNARKs (such as Plonk or Groth16) to reduce the cost for validators to publish proofs on the chain before verification. Doesn't this require proving "non-local" field arithmetic? Because D&P's verifier operates on GF[2^128], while curve-based SNARKs use large prime-order fields.

A: Yes, this is a potential challenge, but I believe we can find a solution.

One possibility is to first combine with SNARK that uses hash-based polynomial commitment schemes, which have shorter proofs (possibly FRI, converted to multilinear polynomial commitment schemes, or BaseFold), and then combine with curve-based SNARK. Note that FRI can be run locally on fields of characteristic two, and in fact, this case was considered in the original FRI paper. The current popular SNARKs' restrictions on using these fields come from the use of non-sum-check-based polynomial IOPs, which is different from FRI itself.

This does not eliminate the problem of non-local field arithmetic, but it can alleviate it to a large extent, because for sufficiently large polynomials, the total operations performed by the FRI verifier are relatively small, especially compared to the field operations performed by the Ligero/Brakedown verifier.

Q13: Can the SNARK using D&P's commitment scheme be combined with folding schemes such as Nova?

A: This will encounter the same problem as Q12, which is that the folding scheme uses elliptic-curve, typically defined over a large prime-order field, while the D&P commitment scheme uses fields of size 2 to the power of n.

I expect to make significant progress in folding schemes, and they will play an important role in future SNARK designs. However, it may be the case that they do not integrate well with hash-based SNARKs on very small characteristic fields.

Currently, it is recommended to use elliptic-curve based commitment and folding schemes (such as Nova) when dealing with statements defined locally on large fields or in situations critical to the prover space. These folding schemes are far superior to other SNARKs in terms of prover space, as they can break down large computations into much smaller parts than other SNARKs. In other cases, hash-based schemes should be used, especially when dealing with small characteristic fields.

Similarly, further development of folding schemes in the future may lead to them surpassing hash-based schemes. In fact, Nova has already been faster than the current generation of hash-based SNARKs in some benchmark tests (although there are many claims that current hash-based SNARKs are faster than curve-based ones).

"Original article link"

Welcome to join the official BlockBeats community:

Telegram Subscription Group: https://t.me/theblockbeats

Telegram Discussion Group: https://t.me/BlockBeats_App

Official Twitter Account: https://twitter.com/BlockBeatsAsia