The lookup singularity - how zero-knowledge proofs can be made simpler and easier to review.
Occasionally, I like to envision the 'best' possible outcome and assess how close we are to it. Zero-knowledge proofs, as they stand today, are complex and difficult to review. The ideal outcome would be a simpler system that is easier to scrutinize and far more efficient than our current options. So, in which direction should we look for the 'best' possible ZKP solution? One promising avenue is lookup tables.
What exactly is a lookup table? A lookup table (or lookup arguments) is a pre-computed set of values that allows a prover to perform certain operations more efficiently. When a prover needs to use a value, they can simply look it up in the table and prove to the verifier that the value exists.
Let's consider a straightforward example. A prover and verifier want to determine whether an integer value is smaller than an arbitrarily chosen number, such as '32'. Accomplishing this using a constraint-only system is highly resource-intensive. The circuit would need to verify the binary representation of all input integers, ensuring that they do not exceed a specific bound. This results in numerous constraints and slower prover times.
Lookup tables can help us bypass this issue. A prover and verifier can begin with a pre-computed table of all 32 possible values. During the proof, they can simply ask if the value is in the table. If it is, then it must be an integer value under '32'. Lookup arguments have proven useful for a variety of non-ZKP-friendly operations, such as range checks and bitwise operations.
The 'lookup singularity' is an idea where all ZKP operations are done with simple and efficient lookup arguments — all circuits will be lookup circuits. We would not need high-degree gates, constraint reduction techniques or other ad-hoc performance improving techniques, if we had a hyper efficient lookup scheme. The singularity has yet to be realized due to limitations in our methods and the immense size of some tables that would be needed to cover 'all' possible operations. Let's shortly review the history and use of lookup arguments and how the research is bringing us closer to the 'ideal' outcome.
Where did the idea of a lookup argument come from?
Ancient India. Looking things up in a table has been known, to be faster than redoing computations by hand, for many years. Historically they were used to speed up the hand calculation of complex functions. One of the first examples is a sine table found in India but many other cultures found them similarly useful for fast and efficient maths.
Much later — modern computer scientists re-discovered the usefulness of lookup tables in their advanced computations. I/O operations were slow in early computers, leading people to manually create static lookup tables to expedite the operations. In the world of ZK, we are still in the very early stages of development when it comes to lookup arguments. But progress is quick.
"Plookup: A simplified polynomial protocol for lookup tables" (2020) is often cited as the most significant initial work for modern SNARK lookups. Plookup introduces an efficient and simplified method for incorporating lookup tables within SNARKs. This groundbreaking advancement greatly improved the efficiency and versatility of these proofs. Previous methods for incorporating lookup tables were complex and less efficient, making it challenging to employ them for various use cases. The plookup protocol streamlined the process by presenting a polynomial-based approach to represent and verify the use of lookup tables in a ZKP system. This innovative technique reduced the complexity of proofs and enhanced the overall performance of SNARKs and the ZKVMs based on them.
In spite of the advances based on Plookup there were still limitations such as added complexity and slower prover times. In 2022 we got Caulk and Caulk+. The key benefit of Caulk is its enhanced performance in prover time and its application in membership proofs and lookup arguments. It outperformed all existing alternatives by orders of magnitude in terms of prover time. Caulk+ further simplified the calculations used and reduced prover times.
At the end of 2022 some of the original authors of Plookup published a new paper Baloo: "the first protocol for lookup tables where the prover work is linear on the amount of lookups and independent of the size of the table." Baloo allows for quasi-linear prover runtime in the set to be opened, rather than the full table size. Separating the correlation between larger tables and slower prover times, makes it possible to do range checks and other computations that simply would be unfeasible with previous methods. This method is still limited because it requires a pre-processing phase which is quasi-linear in the table size.
What is the future of lookup arguments?
Researchers are creating schemes with even faster prover times while removing dependencies on pre-processing phases and table size. When all factors are independent of table size we can use large lookup tables for various tasks; i.e. large tables will no longer be the limiting factor for achieving the lookup singularity. We could take two floating point representations in our VM add them together and find the result in a table, allowing for speed and efficiency not seen in any ZKVM so far. Moreover, the use of lookup arguments will allow for 'front-end' logic that is much simpler to build, reason about, and scrutinize.
"cq: Cached quotients for fast lookups" (2023), is the most recent published work on the topic. Once again this work reduces prover and pre-processing runtimes. CQ also allows for homomorphic table commitments which is useful for vector lookups (unlike Flookup). From the recent line of work, we can say we are heading towards asymptotically optimal prover times! i.e. the most efficient theoretical prover time that can be achieved as the input size increases. When this is achieved contributions will be further techniques that reduce input size (for ZKWasm) and solid implementations and libraries of the schemes.
Many potential applications of ZK are limited by the need to do complex computations which require bit-decompositions and non-native arithmetic. The lookup singularity will allows us to more create more efficient ZK-virtual machine, to support floating point numbers for ZK-machine learning, and other ZK-apps of various sorts. I think it is a goal that needs more attention and I am excited for work being done right now on this subject. By familiarizing ourselves with the recent history, problems and solutions we can hope to actively contribute to the space with implementations, and further optimizations. In the very near term, ICME is building folding scheme tooling with application specific lookup arguments tied-in: for our advanced portable ZKWasm implementation. As always we appreciate your support via: following and sharing on social, signup to this mailing list, and reaching out if interested in what we are building 😊.