A Road Map for Lookup Tables
summary
Road map presents concrete tradeoffs: Caulk and Caulk+ turn static preprocessed tables into lookup arguments at the cost of a temporary table-dependent step and a quadratic verifier cost that Caulk+ reduces; Baloo and Baloo/CQ make lookups linear in group time and target on-the-fly (dynamic) tables for VMs; CQ uses logarithmic derivatives and heavy preprocessing to work over roots of unity and remove table dependence; zero knowledge adds overhead, dynamic tables cannot asymptotically beat linear work, and maintainable (efficiently updatable) static tables remain an open, partially solved engineering problem.
AI-written summary · about
chapters (13)
- 0:00Lookup tables intro
- 1:26Static vs dynamic tables
- 3:14Hiding vs public relations
- 6:03Lookup prover properties
- 8:31Early lookup constructions
- 11:46Caulk and Caulk+ improvements
- 15:20Balloon and CQ for dynamics
- 17:25Prover efficiency questions
- 18:30Zero knowledge for dynamics
- 19:36Maintainable membership proofs
- 21:00ZK-EVM dynamic tables
- 22:47Linear combos on the fly
- 23:32Audience questions and discussion
related talks
25m“A Semi Compile/Run-time Map with (Nearly) Zero Overhead Lookup”
22mCircuit Optimization using Arithmetic Table Lookups
15mFABLE: Batched Evaluation on Confidential Lookup Tables in 2PC
18mA Simple and Efficient Implementation of Strong Call by Need by an Abstract Ma…
39mA Reusable Machine-Calculus for Automated Resource Analyses
29mVerified and Efficient Matching of Regular Expressions with Lookaround
20mUnleashing the Power of Learning: An Enhanced Learning-Based Approach for Dynamic Binary Translation
26mGenerating Compilers for Qubit Mapping and Routing