Detailed Explanation of a16z Crypto's Newly Launched Two SNARK Tools

Original Title: Approaching the 'lookup singularity': Introducing Lasso and Jolt
Compiled by: Qianwen, ChainCatcher

SNARK is a cryptographic protocol that allows anyone to prove to untrusted verifiers that they know a "witness" that satisfies certain properties. A prominent application of SNARK in Web3 is the proof from L2 rollups to L1 blockchains that they know the digital signatures authorizing a series of transactions, allowing those signatures themselves to not be stored and verified by L1, thus enhancing scalability.

Applications of SNARK outside of blockchain include: high-speed but untrusted hardware devices proving the validity of all outputs they generate, ensuring users can trust them. Individuals can prove in a zero-knowledge manner that a trusted authority has issued them a credential. For example, proving that they are old enough to access age-restricted content without revealing their date of birth. Anyone sending encrypted data over the network can prove to administrators that the data complies with network policies without disclosing further details.

While many SNARKs are low-cost for provers, SNARKs generally still incur about six orders of magnitude overhead in verification computations. The additional work that verifiers are forced to undertake is highly parallelizable, but the million-fold overhead severely limits the application of SNARKs.

More powerful SNARKs can speed up L2 and allow builders to unlock yet-to-be-realized applications. Therefore, we are introducing two related new technologies: Lasso is a new lookup parameter that significantly reduces prover costs; Jolt uses Lasso technology to provide a new framework for designing SNARKs for zkVM and other frontends. Together, they enhance the performance, developer experience, and auditability of SNARK design, facilitating the construction of web3.

Compared to the lookup parameters in the popular SNARK toolchain halo2, the preliminary implementation of Lasso has demonstrated a speed improvement of over 10 times. We expect that when the Lasso codebase is fully optimized, the speed will improve by about 40 times. Jolt includes more innovations based on Lasso, and we hope it can achieve speeds similar to or higher than existing zkVMs.

Lookup Parameters, Lasso, and Jolt

The SNARK frontend is a compiler that transforms computer programs into circuits, which are then ingested by the SNARK backend. A circuit is an extremely limited computational model where the primitive operations are merely addition and multiplication.

A key tool in modern SNARK design is the lookup argument, which is a protocol that allows untrusted provers to submit a large vector in an encrypted manner and then prove that each entry of that vector is contained in a predetermined table. Lookup arguments can effectively handle operations that cannot be naturally computed through a small number of additions and multiplications, thus helping to keep circuits small.

Barry from the Ethereum Foundation proposed a vision that if we could efficiently define circuits using only lookup arguments, it would lead to simpler tools and circuits, achieving the "lookup singularity," where we could "design circuits that only perform lookups," which would outperform polynomial constraints in almost every aspect.

This vision starkly contrasts with today's working methods, where developers deploy SNARKs by writing programs in domain-specific languages (compiling programs into polynomial constraints) or directly manually coding constraints. This toolchain consumes significant human and material resources, leading to a high probability of security-critical vulnerabilities. Even with complex tools and circuits, SNARKs remain slow, limiting their applications.

Lasso and Jolt address all three key issues: performance, developer experience, and auditability. I believe they will collectively realize the vision of the lookup singularity. Lasso and Jolt also prompt us to reflect on many common truths in SNARK design. After introducing some necessary background, this article will revisit some common views on SNARK performance and explain how to update these views based on innovations like Lasso and Jolt.

Background on SNARK Design: Why So Slow?

Most SNARK backends require verifiers to make encrypted commitments to the values of each gate in the circuit, using a method known as a polynomial commitment scheme. The prover then proves that the committed values correspond to the correct execution of the witness checking program.

I refer to the prover's work from the polynomial commitment scheme as commitment cost. SNARKs also incur additional prover costs that come from outside the polynomial commitment scheme. However, the commitment cost often becomes the bottleneck. This is also true for Lasso and Jolt. In SNARK design, if the commitment cost does not constitute the primary prover cost, it does not mean that the polynomial commitment scheme is low-cost; rather, it indicates that other costs are higher than they should be.

Intuitively, the purpose of commitment is to securely increase the succinctness of the proof system through cryptographic methods. When a prover commits to a large value vector, it is akin to the prover sending the entire vector to the verifier, just as a trivial proof system sends the entire witness to the verifier. The commitment scheme does not require the verifier to actually receive the entire witness to achieve this, which means that in SNARK design, the purpose of the commitment scheme is to control verifier costs.

However, these cryptographic methods are very costly for provers, especially compared to the information-theoretic methods used outside of the polynomial commitment scheme in SNARKs. Information-theoretic methods rely solely on finite field operations, and the speed of a single field operation is several orders of magnitude faster than the time required to commit to arbitrary field elements.

Depending on the polynomial commitment scheme used, computing commitments involves multi-scalar multiplication (also known as MSM), or FFT and Merkle hashing. Lasso and Jolt can use any polynomial commitment scheme, but incur additional costs when using MSM-based schemes, such as IPA/Bulletproofs, KZG/PST, Hyrax, Dory, or Zeromorph.

Why Lasso and Jolt Matter?

Lasso is a new lookup parameter method that requires fewer and smaller committed values from the prover compared to previous methods. Depending on the specific situation, this can increase speed by 20 times or more, with 2 to 4 times coming from fewer committed values, and another 10 times because in Lasso, all committed values are small. Unlike many previous lookup parameters, Lasso (and Jolt) also avoids FFT, as FFT requires significant space and can lead to bottlenecks in large instances.

Moreover, as long as the table is "structured" (in a precise technical sense), Lasso can even be applied to huge tables (e.g., of size up to 2^128). When the table size is too large, no one can explicitly instantiate it, but Lasso only incurs costs for the table elements it actually accesses. Another noteworthy point is that if the table is structured, then no party needs to make encrypted commitments to all values in the table.

Lasso leverages two different structural concepts: decomposability and LDE structure. Decomposability roughly means that a single lookup can be completed through a small number of lookups on a very small-scale table. This is a stricter requirement than LDE structure, but Lasso is highly efficient when applied to decomposable tables.

Jolt

Jolt (Just One Lookup Table) is a new frontend that utilizes the capability of Lasso to use giant lookup tables. Jolt targets virtual machine/CPU abstractions, also known as instruction set architectures (ISA). SNARKs that support this abstraction are referred to as zkVMs. For example, the RISC-V instruction set (including multiplication-extended instruction sets) supported by the RISC-Zero project. This is a popular open-source ISA developed by the computer architecture community without considering SNARK during development.

For each RISC-V instruction fi, the main idea of Jolt is to create a lookup table that contains the entire evaluation table for fi. Therefore, if fi receives two 32-bit inputs, the table will have 2^64 entries, where the (x,y)'th entry is fi(x,y). If we consider instructions for 64-bit rather than 32-bit data types, the size of the table for each instruction will be 2^128 instead of 2^64.

Essentially, the lookup table for each RISC-V instruction is decomposable and applicable to Lasso. A few instructions are handled by applying a short sequence of other instructions. For example, the handling of division instructions involves having the prover submit the quotient and remainder and checking if they are correctly provided through one multiplication and one addition.

The circuit running a T-step RISC-V CPU can be generated as follows. For each step in T steps, the circuit contains some simple logic to determine the original RISC-V instruction fi to be executed in that step and the inputs (x, y) for that instruction. Then, the circuit only needs to perform a single lookup to reveal the (x,y) entry in the relevant table to execute fi. More precisely, Jolt only considers one table, which is formed by concatenating the tables for each instruction, hence it is called "Just One Lookup Table."

Reexamining Common Truths in SNARK Design

Lasso and Jolt also disrupt several common truths in SNARK design.

1. Overlarge fields in SNARKs are a waste. Everyone should use FRI, Ligero, Brakedown, or their variants, as these techniques avoid elliptic curve techniques, which are typically suited for larger fields.

The size of the field here can be roughly understood as the size of the numbers appearing in SNARK proofs. Since the overhead of addition and multiplication of large numbers is significant, SNARKs over large fields lead to waste, meaning we should design protocols that never involve large numbers whenever possible. MSM-based commitments use elliptic curves, which are typically defined over large fields (approximately size 2^256), leading to poor performance.

I have previously discussed that whether it is reasonable to use small fields largely depends on the application. Lasso and Jolt demonstrate that even when using MSM-based commitment schemes, the prover's work is almost unaffected by the field size. This is because, for MSM-based commitments, the size of the committed values is more important than the size of the field they reside in.

Existing SNARKs require provers to submit many random field elements. For example, a prover named Plonk submits about 7 random field elements (along with additional non-random field elements) for each circuit gate. Even if all values appearing in the proven computation are small, these random field elements can be large.

In contrast, Lasso and Jolt only require provers to submit smaller values (the values submitted by Lasso provers are also fewer than those of previous lookup parameters). This significantly improves the performance of MSM-based schemes. At the very least, Lasso and Jolt should dispel the notion that the community should abandon MSM-based commitments when prover performance is crucial.

2. Simpler instruction sets lead to faster zkVMs.

As long as the evaluation table for each instruction is decomposable, the complexity of Jolt (for each instruction) only depends on the input size of the instruction. Jolt proves that even complex instructions are decomposable, especially all RISC-V instructions.

This contradicts the common belief that simpler virtual machines (zkVMs) necessarily lead to smaller circuits and consequently faster provers (for each step of the virtual machine). This perspective has guided the design of minimalist zkVMs (like Cairo VM).

In fact, for simpler virtual machines, Jolt reduces the prover's commitment costs more than previous SNARKs. For example, provers executing on the Cairo VM must submit 51 field elements for each step of the virtual machine. The SNARK deployed on Cairo VM currently operates over a field of 251 bits (63 bits is the hard lower limit for field size that SNARK can use). Jolt's verifiers submit about 60 field elements per step on the RISC-V CPU (defined as 64-bit data types). Considering the fewer submitted field elements, the cost for Jolt verifiers is roughly equivalent to submitting 6 random field elements of 256 bits.

3. Breaking large computations into smaller chunks does not incur performance loss.

Based on this perspective, current projects break large circuits into smaller chunks, proving each chunk separately and recursively aggregating the results through SNARK. These deployments use this method to alleviate the performance bottlenecks of most SNARKs. For instance, FRI-based SNARKs require nearly 100 GB of prover space even for small circuits. They also require FFT, which is a super-linear operation that can become a bottleneck if SNARK is applied to large circuits all at once.

The reality is that some SNARKs (like Lasso and Jolt) exhibit economies of scale (whereas currently deployed SNARKs do not). This means that the larger the statement being proven, the smaller the overhead for the prover relative to witness checking (the work required to evaluate the witness circuit without guaranteeing correctness). Technically, economies of scale arise from two aspects:

1) The Pippenger speedup for MSM of size n improves log(n) times over the original algorithm. The larger n is, the greater the improvement.

2) In lookup parameters like Lasso, the prover incurs a one-time cost that depends on the size of the lookup table but is independent of the number of lookup values. The one-time cost for the prover is amortized over all queries to the table. Larger data chunks mean more lookups, leading to better amortization.

Today, the mainstream approach to handling large circuits is to break them into as small chunks as possible. The primary limitation on the size of each chunk is that they cannot be too small, or else recursive aggregation of proofs will become a bottleneck for the prover.

Lasso and Jolt propose a fundamentally opposite approach. We should use SNARKs with economies of scale. Then, break large computations into as large parts as possible and recursively aggregate the results. The primary limiting factor on the size of each computation segment is the prover space, which increases as the computation segments grow larger.

4. High-degree constraints are a necessary condition for efficient SNARKs.

Jolt uses R1CS as an intermediate representation. In Jolt, using "high-degree" or "custom" constraints offers no benefits. In Jolt, most of the prover's costs are in the lookup parameter Lasso, rather than in the satisfiability of the proof constraint system (which takes lookup options for granted).

Jolt is general-purpose, so it does not lose generality. Therefore, developers focus on designing highly constrained (often manually customized) systems to extract higher performance from today's popular SNARKs, which is precisely the opposite of what Jolt represents.

Of course, in some cases, high-degree or custom constraints can still be beneficial. An important example is the Minroot VDF, where 5-degree constraints can reduce commitment costs by about 3 times.

5. Sparse polynomial commitment schemes are costly and should be avoided whenever possible.

The criticism mainly targets the recently launched system called CCS and the SNARKs supporting it: (Super-)Spartan and (Super-)Marlin. CCS is a concise summary of all constraint systems popular in today's practice.

This criticism is unfounded. In fact, the technical core of Lasso and Jolt is the sparse polynomial commitment scheme in Spartan, called Spark. Spark itself is a scheme that converts any (non-sparse) polynomial commitment scheme into one that supports sparse polynomials.

Lasso optimizes and extends Spark to ensure that provers only submit "small" values, but even without these optimizations, this criticism is unreasonable. In fact, the provers of Spartan commit fewer (random) field elements compared to SNARKs (like Plonk) that avoid sparse polynomial commitments.

Spartan's approach has additional performance advantages, especially for circuits with repetitive structures. For these circuits, adding gates does not increase the encryption workload for Spartan verifiers. This workload only increases with the number of variables in the given constraint system, not with the number of constraints. Moreover, unlike Plonk, Spartan verifiers do not need to commit to multiple different "copies" of the same variable.

Conclusion

We believe that Lasso and Jolt will significantly change the way SNARKs are designed, thereby improving performance and auditability. Subsequent articles in this series will delve deeper into how Lasso and Jolt work.