# Clookup - Composite Function based Lookup Argument

- Speakers: [Wanseob Lim](https://streameth.org/speakers/wanseob-lim)
- Channel: [Devcon 7 SEA](https://streameth.org/devcon_7_sea)
- Date: 2024-11-15
- Duration: 15:16
- Watch: https://streameth.org/watch/6737434e74749a4b8959c027

## Description

Presenting Clookup, a novel lookup protocol that enhances efficiency in verifiable computations. By using a composite function approach and multivariate polynomials within the sumcheck protocol, Clookup achieves optimal time complexity \(O(m(m+n))\) when processing \(2^m\) witness elements against a \(2^n\) table. This method eliminates the need to compute coefficient forms of composite functions.

## About the speakers

### Wanseob Lim

Wanseob Lim is an applied cryptography researcher and cypherpunk dedicated to sharing knowledge and promoting opensource initiatives to enhance resistance and resilience.


## Transcript

Hello everyone, thank you so much for coming to my talk. Today I'm gonna have a talk about the C lookup, the lookup argument based on composite function. Actually, this is the first time ever that we are presenting our work. So my name is Wansup Lim, and researcher at PSC. This is a joint work with my colleagues. So I did this work with Suwon and Dohoon together. And the summary is that given that we have a n size of table and a witness with size of m, then if the witness size is much larger than the table size, we can accomplish a O of log squared m time complexity to the lookup argument. I'm going to explain more about how we achieved this. First of all, I would love to introduce where we got the inspirations. The first one was about the GKR, because we noticed that GKR is a very, a one unique version of composite function. And the second was about Hyperplunk's PIOP2, the permutation argument PIOP2. It is also using kind of a composite function. It was very inspiring for me to think about the log of argument using that. And so using that, we are using some composite function, just like in GKRs, each layers. Actually, in our case, we are using only one layer, and we are achieving the O of log squared time complexity. So first, let's discuss about the objective, and let's understand the current situation. We have two sets. First one is about witness, and the second is about the element of the given table. And our goal is to prove that for every element in W is also an element of a table. In other words, we are verifying that each witness element is contained within the table. And this implies that the set of witness, w, is a subset of the table, t. Okay. And before we go deep dive into the lookup argument, C lookup argument protocol, I would love to introduce the main use case, the interesting use case if you have the lookup argument. So what if we define each witness W as an encoding of function along with its input and output result. And let T be a predefined computations. Then we can formally verify that f equals to y always holds true provided that the witness is a subset of the predefined computations. This means we can ensure that each computed value corresponds to a valid function and input and produces the correct output as specified in our predefined table of computations. And it becomes a cornerstone for formally verified computations. So we can implement some like zkpm, which is also called the lookup singularity, which is also the Jolt and Lasso's approach. So I'm going to introduce our approach, the C-lookup approach. So first, we are going to define a relation, Cilicup, as the set of all tuples of public instance X and witness W, where the public instance X is a tuple of oracles of functions f, t, and sigma, and the witness is a tuple of functions f, t, and sigma, and the witness is a function of two is a tuple of functions t, f, t, and sigma. To be precise, f is a function that maps all the witnesses defined on a domain x, f with range y, f, And t is a function that maps table elements defined on the domain xt with range yt. And if there exists a domain transformation function sigma that maps elements from xf to xt, also which satisfies that f of x equals to t of sigma of x for all the x in the domain xf. Then the range of f is a subset of the range of t. And we say that the tuple of public instance and witness is in the C lookup relation. Okay. First, I'm going to show you the knife approach version. We'll consider a polynomial F and t and sigma over a finite field, and we're going to use univariate polynomial approach. Then we're going to map the witness and elements using the corresponding root of unity. And the relation that f of x always equals to t of sigma of x for all the roots of unity holds true if and only if there exists a quotient polynomial q such that f of x minus t of sigma of x equals to z of x times q of x for the vanishing polynomial z. Actually, here exists a caveat that the degree explodes. The degree explodes if we have the univariate polynomial, if we compute the composite function. times degree of the sigma. So which means like n times m. But if we use multivariate polynomial approach, it changes a lot. We will define the domain on the vector space. For the witness, we're going to define its domain as Boolean hypercube over a log m dimensional space. And for the table, we're going to define the domain over the log n dimensional space. And then defining the domain transformation function sigma as a tuple of all the domain transformation functions, then the relation that the f of x always t of sigma of x holds true if and only if there exists a auxiliary polynomial H which satisfies some zero-check PIOP protocol. Precisely here the R and R' and gamma are the randomly chosen vector from the verifier, and the auxiliary polynomial gives us the relation that there exists mapping correctly and the domain transformation is actually bound to the 0 and 1 correctly. As a result, we could achieve the log squared of m against the witness size or log of the table size and complexity, time complexity. If we think about the protocol, let's go through the protocol quickly. So let's assume we have a witness, witness F, witness vector F, and the table vector T, 2, 3, 5, 7, 11, 5, blah, blah, blah. And the first step is preparation. So we're going to compute the table polynomial. But for an efficient parallelization, we're going to use the coefficient form. But it doesn't, actually it does not a big thing because it's a pre-processing period. And then we interpolate the witness. So just say for your easier understanding, I just express this in a coefficient form. And then we also need to find the domain transformation functions. This is just a mapping between the witness domain to the table domain. So if we express that in a coefficient form, actually we are using only the evaluation form. And then we use public coin protocol to run sum check only once by patching everything together. So we choose, the verifier chooses the R, R' and gamma. And in this case, let's say we chose 31, 37 for R, and 5 and 7 for R', and 9 and 11, 13 for the gamma. Rerun sum check. The first round will look like this and you can see here the intermediate univariate polynomial is not a linear function. It has some degrees and we run the following rounds following round and as a result we need to check the resulting random evaluation from this sum check equals to the thing that we can query from the Oracle which was the one of the public instance X. So we query the evaluations through the oracles and we check this they are hold the relation holds true by checking this condition and consistency. One important thing is that the main advantage of this approach is that it is very easy to decompose into smaller tables. So we have a T polynomial here, and we can decompose it into two smaller pieces, T1 and T2. In T1, it's just a T of 0, x2, x3. And T2 is actually T of 1, x2, x3. We can decompose a table very easily. We can decompose more smaller pieces. Also, we can utilize this composite function approach with a sum. We can tweak a little bit. If we tweak this a little bit, then we can also compute the two intersections, I mean size of two, intersection of two given sets. And actually the result for the computational results also shows the same result. One of the key theses we had here is that if we use the composite function using multivariate setup, then the cost becomes too logarithmic. And if we maximize the parallelization, we thought that, okay, here's the composite function cost, and in univariate function, it was really high because the degree was exploding, but in multivariate setup, we can actually logarithmically change that. And the result is actually like, okay, it depends on the number of rounds times the composite function cost, evaluation of the composite function cost. And once again, composite function is a very, very generalized version of a GKR-ish approach. And to demonstrate our thesis, actually we implemented the CUDA-based sum check protocol first in this repository. So it was a highly parallelizing all the evaluations, polynomial evaluations using GPU. And then we utilize this CUDA sum check to see the results in this silicon repository. We just use KTJs just for easier implementation, but definitely you can change this commitment scheme to others. And successfully we could see our result approach shows the logarithmic increase compared to the classical approach. Actually the implementation and benchmark data is still being fleshed out. So but we are pretty optimistic for about the result that it's showing the sublinear result, not only against the witness side, but also against the table side. Conclusion. This approach is very simple to understand, to other local argument approach. And it supports table decomposition gracefully and also it achieves sublinear proving time. My talk was a little bit longer than compared to the given time so I cannot have some enough Q&A time. I'm gonna be out there so thank you so much coming to my talk. Thank you very much, Mansoor, for your wonderful presentation and teaching us about CLOOKUP. Thank you. And we're going to start at 3.50 with the last question.