SEASON 2 MODULE 3
An Update on Lookups w/ Ariel Gabizon
In this module, Nicolas Mohnblatt and Ariel Gabizon start by giving an overview of the lookup landscape, going over the three main approaches that have been used in lookup protocols. They then dive deep into one of those approaches, the log-derivative approach (or its clearer name, fractional sums).
What you’ll learn:
- 00:00 – Introduction and lookup landscape
- 06:35 – Log-derivative approach: Basic lemma
- 14:10 – The logup protocol
- 20:42 – The Aurora lemma
- 28:41 – The cq protocol: KZG additivity and sparse polynomials
- 34:18 – Which polynomials in the logup protocol are sparse
- 45:33 – cq = cached quotients
- 51:42 – Drawback of cq and decomposable tables
- 56:49 – How big are the values to commit to in logup
- 1:00:27 – Logup GKR
Below is an accompanying reading list:
- Module Six: Lookup Tables for Performance Optimisation w/ Mary Maller, ZK Whiteboard Sessions S1, ZK Hack, 2022.
- The halo2 book, by Zcash.
- plookup: A simplified polynomial protocol for lookup tables, by Ariel Gabizon and Zachary J. Williamson, 2020.
- Spartan: Efficient and general-purpose zkSNARKs without trusted setup, by Srinath Setty (Microsoft Research, 2019).
- Unlocking the lookup singularity with Lasso, by Srinath Setty, Justin Thaler and Riad Wahby, 2023.
- Bulletproofs++: Next Generation Confidential Transactions via Reciprocal Set Membership Arguments, by Liam Eagen, Sanket Kanjalkar, Tim Ruffing and Jonas Nick (Blockstream, 2022).
- Multivariate lookups based on logarithmic derivatives, by Ulrich Haböck, 2022.
- cq: Cached quotients for fast lookups, by Liam Eagen, Dario Fiore and Ariel Gabizon, 2022.
- Delegating Computation: Interactive Proofs for Muggles, by Shafi Goldwasser, Yael Tauman Kalai, Guy N. Rothblum, 2008
- Improving logarithmic derivative lookups using GKR, by Shahar Papini and Ulrich Haböck, 2023.
- ProtoStar: Generic Efficient Accumulation/Folding for Special Sound Protocols, by Benedikt Bünz, Espresso SysBinyi Chen (Espresso Systems, 2023).
- Baloo: Nearly Optimal Lookup Arguments, by Arantxa Zapico, Ariel Gabizon, Dmitry Khovratovich, Mary Maller, and Carla Ràfols, 2022.
- FLI: Folding Lookup Instances, by Albert Garreta and Ignacio Manzur (Nethermind Research, 2024).
- Aurora: Transparent Succinct Arguments for R1CS, by Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward, 2019.
- TaSSLE: Lasso for the commitment-phobic, by Daniel Dore (Lita Foundation, 2024).
ZK Whiteboard Sessions is an educational series on all things zero knowledge. Presented by ZK Hack.
Get notified on the latest module’s release by signing up below: