Lasso in a Nutshell with Justin Thaler | a16z crypto

TL;DR

New lookup argument called Lasso allows faster prover commitment by committing to fewer and smaller field elements, supporting large tables and utilizing multivariate polynomials.

Transcript

all right so just a like a one slide recap of yesterday um so I'll look up arguments uh let's approver commit to a vector of value and then prove that all entries of that Vector reside in some predetermined table um so lasso is a new family of lookup arguments uh high level I think the prover is about an order magnitude faster than prior works and ... Read More

Key Insights

• 💨 Lasso lookup arguments offer faster prover commitment by committing to fewer and smaller field elements.
• 😒 The use of multivariate polynomials in Lasso improves performance and enables support for larger tables.
• 😘 Jolt, a ZK VM technique built on Lasso, provides lower commitment costs for provers by proving the correct execution of instructions through table lookups.
• 😘 Lasso enables the handling of decomposable tables with lower overhead compared to prior lookup arguments.
• 👪 The Lasso family of lookup arguments introduces a unique feature by supporting gigantic tables with some structure.
• 👻 Commitment schemes for small values in Lasso allow for faster cryptographic computations during prover commitments.
• ❓ Prior lookup arguments cannot achieve the same results as the generalized Lasso strategy, which exploits weaker structural properties using univariate polynomials.

Questions & Answers

Q: How does Lasso improve prover speed compared to prior lookup arguments?

Lasso improves prover speed by committing to fewer field elements and using small value commitments, resulting in faster cryptographic computations for commitment schemes.

Q: Can Lasso handle large tables?

Yes, Lasso can support gigantic tables as long as they have some structure, allowing for efficient lookup operations without the need for the prover to commit to the table.

Q: What is the main idea behind Jolt?

Jolt is a ZK VM technique that leverages the Lasso lookup argument. It proves correct execution of primitive instructions by performing a lookup in a large table, containing the entire evaluation table of the instruction.

Q: What is the advantage of using multivariate polynomials in Lasso?

Multivariate polynomials in Lasso allow for more efficient handling of tables, including the ability to support weaker structural properties and achieve better performance compared to using univariate polynomials.

Summary & Key Takeaways

• Lasso is a faster lookup argument that proves all entries of a vector reside in a predetermined table, with faster prover commitments due to fewer and smaller field elements.

• Lasso supports gigantic tables with some structure, eliminating the need for the prover to commit to the table in many cases.

• Jolt is a new ZK VM technique built on Lasso, providing lower commitment costs for the prover by proving correct execution of primitive instructions through a lookup into a large table.