Partnered With:

a16z: Lasso+Jolt, a promising new prospect for rapid commitments.

a16z crypto

Read this article in 20 Minutes

Original Title: "Boosting Lasso+Jolt through faster commitments – with far-reaching consequences"

Original Author: Justin Thaler

Translated by: Luccy, BlockBeats

Editor's Note:

a16z Crypto has released two SNARK-related technologies: Lasso and Jolt. They address three key issues: performance, developer experience, and auditability.

Lasso is a new lookup parameter that significantly improves prover costs; Jolt (Just One Lookup Table) is a framework designed specifically for Ethereum Virtual Machine-compatible Rollups, a novel way of building SNARK VMs using Lasso. Lasso and Jolt can significantly speed up scaling and building applications in Web3, and together represent a new SNARK design approach that can improve the performance of widely deployed toolchains by an order of magnitude or more.

Related Reading: "a16z Launches New Zero-Knowledge Proof Tools Lasso and Jolt: Improving SNARK Performance and Developer Experience"

Justin Thaler, a research partner at a16z and associate professor of computer science at Georgetown University, delves into the latest developments in SNARK technology, emphasizing the need to change various components of existing deployments, including multiple key technologies, to obtain SNARKs with high-performance provers. Justin suggests using sum-check-based polynomial IOPs and combining faster provers, larger proofs schemes such as Ligero/Brakedown, and recursion to achieve more efficient SNARK systems. In addition, he emphasizes the urgent need for simpler, more developer-friendly SNARK systems to improve auditability and security.

Earlier this year, we launched Lasso and Jolt, which not only have more powerful performance, but also easier-to-build and audit SNARKs.

Lasso is a new type of lookup parameter with significantly faster provers. Jolt is based on Lasso and provides a fundamentally new design paradigm for designing so-called zkVMs - SNARKs, allowing provers to prove that a computer program (specified in the assembly language of a specific virtual machine) runs correctly.

Lasso and Jolt both rely on a technology tool called the sum-check protocol, which minimizes the amount of data that the prover must commit to (as well as the "size" of each data piece). The cost of committing data is a key bottleneck for SNARK prover performance.

Today, Ben Diamond and Jim Posen from Ulvetanna (referred to as D&P below) have released a game-changing paper. D&P's main contribution is modifying the Ligero/Brakedown commitment scheme, allowing verifiers to pay for each commitment value "bit by bit". I will explain how they achieved this and why, when combined with Lasso, it leads to a significant improvement in SNARK performance. D&P refer to their implementation as Binius.

These developments not only improve performance, but also indicate that we have been misconceiving key aspects of SNARK design. For example, Jolt has shown that when we manually design "SNARK-friendly" VMs, we are actually customizing them for the artificial constraints of today's popular SNARKs. D&P also shows that SNARK-friendly hashes are the same. At the end of this article, I will also explain in detail what changes need to be made to SNARK design, both in terms of how we think about it and what we build.

Through Lasso to Achieve Better Circuit-SAT SNARK

Jolt can be seen as an application of Lasso to VM execution, which includes a simple fetch-decode-execute loop of repeatedly executing the VM. However, Lasso itself has a wider range of applicability.

The first step of D&P is to use Lasso to provide better SNARK for circuit satisfiability (more precisely, the supported "circuits" are Plonkish constraint systems). This can be seen as applying Lasso to (potential) non-uniform computation (unlike VM execution, which is essentially uniform because the VM repeatedly executes the same fetch, decode, and execute loop). This application leverages the fact that Lasso is actually more powerful than finding parameters: it is a parameter for general sparse linear relationships, used to establish the relationship M⋅t = a, where M is a sparse matrix (i.e., most of its entries are zero), and t and a are (possibly submitted) vectors.

Like Jolt, this application of Lasso has an important feature where almost all values that the prover needs to make cryptographic commitments to are small, meaning they are between 0 and 2b, where b is a relatively small number (we refer to b as the bit complexity of each commitment value). For example, in Jolt, b ≤ 25 for most commitment values.

In another article, Srinath Setty and I proposed an alternative to SNARK called Plonkish generalization. We believe that this alternative approach is conceptually simpler, but may not be as easy to integrate with D&P's subsequent contributions.

These new Plonkish constraint systems based on Lasso, called SNARK, will make it easier to integrate Lasso foundational technology into existing tools (such as Halo2), many of which specifically support Plonkish.

更快速的小值多项式承诺方案

"More efficient small-domain polynomial commitment scheme"

Firstly, as I explained in my previous article, most SNARKs consist of two components: a so-called polynomial IOP and a cryptographic primitive called polynomial commitment scheme. The critical bottleneck for the prover is often the polynomial commitment scheme.

Currently, there are two widely used polynomial commitment schemes. One is based on elliptic curve cryptography, with the most popular examples being KZG commitment and Bulletproofs/IPA. The other is based on hashing, with the currently most popular example being FRI.

For commitment schemes based on curves and hashes, smaller values are faster than larger values. However, in terms of the cost for the prover, it is a step function with respect to the value size: as the value grows, the cost remains relatively constant, with occasional significant jumps.

In the case of curve-based commitments, this is due to Pippenger's algorithm, which roughly allows the prover to commit to values of 1 to 20 bits using a single group operation, to values of 20 to 40 bits using two group operations, and to values of 40 to 60 bits using three group operations, and so on. (Here, 20 is a substitute for the logarithm of the commitment vector length, which is typically between 20 and 30, and the aforementioned commitment cost is amortized.) For hash-based commitment schemes, many projects today work on extension fields with a smaller base field. If all committed values reside in the base field, the commitment calculation is faster, and the current common base field size is between 31 and 64 bits.

However, the current commitment schemes have limited benefits for small values. In the case of curve-based schemes, committing to a 2-bit value (i.e. a value from {1, 2, 3, 4}) is not faster than committing to a 20-bit value (i.e. a number between 0 and 2^20≈1 million): both require roughly one group operation using Pippenger's algorithm. The popular hash-based schemes today also treat all basic domain elements similarly.

D&P combines two techniques to make the step function of Ligero/Brakedown's hash-based polynomial commitment scheme smoother, allowing provers to "pay" roughly in bits for each commitment value. They achieve this by combining two techniques. First, they work in the GF[2^128] field, which has a characteristic of two (this is very different from today's popular SNARKs, whose characteristic is at least 2^31). They construct this field as a tower, meaning that GF[2^128] is constructed as an extension of GF[2^64], which is constructed as an extension of GF[2^32], and so on. Second, they use techniques related to code concatenation to ensure that the cost of committing to a 1-bit value is really about twice as cheap as committing to a 2-bit value, the cost of committing to a 2-bit value is about twice as cheap as committing to a 4-bit value, and so on. (For an overview of these techniques, see my more detailed technical companion FAQ.)

This effect could be enormous. In D&P's SNARK for Keccak, all commitment values are individual bits, and their improvement has reduced the time to commit to these single-bit values by an order of magnitude. For example, in Jolt, one-third to two-thirds of commitment values are just a single bit.

Dramatically Improved Hash SNARKs

The first two contributions in the application of circuits to the satisfiability of binary features have resulted in a faster SNARK, potentially faster by one or even two orders of magnitude compared to previous work.

Then, D&P applied this SNARK to implement hash functions Keccak (and another called Grøstl), producing SNARKs for these hash functions that are much faster than anything before. Once fully optimized, I expect their SNARKs to be able to prove over 5,000 Keccak-f permutations per second in single-threaded scenarios (using an AWS c7i.16xlarge instance with an Intel Sapphire Rapids 8488C processor in benchmark tests), with ample parallelism available. This means that 20-25 MiB of data can be hashed in approximately 30 seconds of single-threaded processing.

Impact

SNARKs, which are better suited for hashing, are inherently powerful because SNARKs are applied to many cryptographic statements (such as knowledge of Merkle authentication paths) that ultimately boil down to hashing. In fact, this is the key bottleneck for Type-1 zkEVMs and recursive hashing-based SNARKs.

Therefore, although Lasso improves the SNARKs of hashes, it also benefits Jolt: better SNARKs of hashes allow Lasso and Jolt to be combined with (recursive versions of) polynomial commitment schemes based on Ligero/Brakedown hashes. These schemes are very fast for provers, but require verifiers to perform a considerable number of hash operations (square root of the size of the committed polynomial). This makes it difficult to use Ligero/Brakedown recursively applied SNARKs, as provers struggle to prove that they correctly executed the verifier's hash operations. This difficulty should disappear with the use of faster hash SNARKs.

Specifically, for circuits with billions of gates, Ligero/Brakedown proves sizes in the MB range, and verifier V mainly performs field operations (cheap for recursion) and hash operations. Considering that SNARKs can hash 20 MB of data in 30 seconds of single-threaded processing time (and have sufficient parallelism), the prover should need less than 10 seconds of single-threaded processing time to apply recursion to the proof system.

In addition, when using recursion, optimizing the proof size of Ligero/Brakedown is not reasonable, and the runtime of the recursive prover should be optimized instead. Since hash operations are more expensive than field operations, Ligero/Brakedown should be configured to perform fewer hash operations for the verifier V, even if this means larger proofs and more field operations. This will speed up the recursive proof beyond the estimated 10 seconds mentioned earlier.

Overall, combining Lasso and Jolt with D&P's commitment scheme (recursively applied) will further improve the performance of Lasso and Jolt. This is because Keccak and Grøstl are faster than SNARK-friendly hash functions popular today, and regardless of which hash function is used, Ligero/Brakedown's proof speed is faster than FRI.

Re-examining the Perspective of SNARK-friendly Hash

The situation here is that the sum-check protocol requires the prover to perform additional field operations (which are fast) to reduce the number of cryptographic operations used by the prover in the commitment scheme (which are slow). This is a win for the prover's time. In contrast, highly interactive commitment schemes require the prover to perform additional cryptographic operations (relative to the minimal interactive scheme) not to reduce the prover's work, but to reduce the verifier's costs, such as proof size and verifier work. It is better to use recursion instead of interaction to shift these verifier costs to the prover, and the prover's time will only increase slightly (now we have SNARKs that are fast enough for hashing).

Recursive solutions have solved the problem of high verification costs.

Impact of Cryptographic Academic Articles on the SNARK Ecosystem

Polynomial IOPs (Interactive Proofs): They should be based on overall checks to minimize the amount of data that the prover needs to submit.

Polynomial commitment scheme: We should combine faster provers and larger proof systems, such as Ligero/Brakedown, with recursion. Ligero/Brakedown have the same security properties as FRI. They are transparent and may be secure in the post-quantum era, based solely on hash functions, etc.

The fields they involve: Due to various technical reasons, the popular SNARKs today usually require domains with relatively large characteristics (deployments typically use domains with at least 2^31 characteristics). SNARKs based on the universal setup protocol do not have this limitation, and D&P demonstrates how to use domains with very small characteristics, such as GF[2^128], to achieve significant performance improvements.

Fortunately, the same development that led to these changes also made SNARKs simpler and easier to construct, although there is still room for further improvement. In particular, Jolt eliminates the need for manually designing instruction sets for zkVM or manually optimizing circuits to implement these instruction sets, as it replaces these circuits with a simple specification of evaluation tables for each primitive instruction. This modular and generic architecture makes it easier to replace domains and polynomial commitment schemes, achieve recursion, and generally reduce the surface area of errors and the amount of code that needs to be maintained and audited.

This simplicity is not only crucial for usability and development speed, but also helps address an important security issue. SNARK-based systems consist of tens of thousands of lines of code and require an understanding of multiple custom constraint systems or DSLs, which will never be auditable enough to ensure the security of billions of dollars in value.

I hope this article can convince more projects to invest in developing SNARKs that comply with this design pattern.