Lasso, Jolt, and the Lookup Singularity, Part I with Justin Thaler | a16z crypto research talks

TL;DR

Lasso is a new family of lookup arguments designed to improve performance and scalability, while Jolt is a new SNARK front-end technique built on Lasso. Justin Thaler’s Part I talk explains why lookup arguments can reduce commitment overhead compared with bit decomposition and introduces how SNARK toolchains turn high-level programs into arithmetic circuits. Read on for the core concepts behind Lasso, Jolt, lookup arguments, and succinct proofs.

Transcript

uh very pleased to introduce Justin thaler of course one of our own research partner here at a16 zoo crypto I'm also a professor at Georgetown he's going to be giving two talks so today's going to be part one which will be more of the kind of high level overview and kind of why you should care and then tomorrow we'll have part two which is more abo... Read More

Key Insights

• 🧡 Lookup arguments offer a more efficient alternative to bit decomposition for range proofs, reducing the commitment overhead for provers.
• 👔 Existing lookup arguments have limitations tied to table size, requiring a commitment overhead that hinders scalability.
• 👶 Lasso is a new family of lookup arguments that improves performance and scalability by reducing the commitment overhead for provers.
• 🔶 Lasso allows for efficient range proofs with larger tables, addressing the limitations of traditional lookup arguments.
• 😒 The use of multi-exponentiations in polynomial commitment schemes can significantly enhance the efficiency of lookup arguments.
• 🫦 The trade-off between bit decomposition and lookup arguments depends on various factors, including the number of lookups and table size.
• 🫰 The development of indexed lookup arguments offers an alternative approach for more specific range checks, tying each value with a particular index in the table.

Questions & Answers

Q: What are Lasso, Jolt, and the lookup singularity in Justin Thaler’s Part I talk?

Lasso is a new family of lookup arguments, and Jolt is a new front-end technique that builds on Lasso. Part I provides a high-level overview of these proof-system ideas and explains why they matter, while Part II is intended to cover how they work under the hood.

Q: What is a SNARK?

A SNARK is a cryptographic protocol in which an untrusted prover claims to know a witness satisfying a property while giving the verifier a proof that is cheaper to check than the witness directly. The name stands for succinct non-interactive argument of knowledge: the proof is short, static, and cannot convincingly establish a false claim unless an underlying cryptographic system is broken.

Q: What does a prover demonstrate in a SNARK?

The prover demonstrates knowledge of a witness that satisfies a specified property. One example is knowing a value W whose SHA3 hash equals an agreed string Y, without simply providing W as the proof.

Q: What makes a SNARK proof succinct and work-saving?

Justin Thaler describes a proof as succinct when it is shorter than the witness itself, which would be the trivial proof. He uses “work-saving” to clarify that checking the proof is also faster than checking the witness directly.

Q: What does non-interactive mean in a SNARK?

Non-interactive means the proof is static rather than requiring repeated interaction between the prover and verifier. Because it is static, it can be posted to a blockchain.

Q: How does a SNARK front end process a computer program?

A developer first writes a witness-checking program in a high-level language such as Rust or C. The front end converts that program into an equivalent lower-level computational representation, typically an analog of an arithmetic circuit.

Q: Why do SNARK toolchains convert programs into arithmetic circuits?

Arithmetic circuits use very simple operations and represent computation at a lower level than the original program. Their simplicity makes it easier to design SNARKs that let a prover establish knowledge of a satisfying assignment to the circuit.

Q: How do lookup arguments compare with bit decomposition for range checks?

Lookup arguments can perform range checks with less commitment overhead than bit decomposition, which requires committing to many field elements. Existing lookup arguments remain limited by their dependence on table size, while Lasso is intended to support larger tables with improved performance and scalability.

Summary & Key Takeaways

• Look up arguments are a more efficient way to perform range checks compared to bit decomposition, which requires committing to many field elements. However, existing lookup arguments have limitations tied to table size.

• Lasso is a new family of lookup arguments that addresses these limitations by providing improved performance and scalability. It allows for efficient range proofs with larger tables, reducing the commitment overhead for provers.