# Clookup - Composite Function based Lookup Argument by Wanseob Lim | Devcon SEA

- Speakers: [Wanseob Lim](https://streameth.org/speakers/wanseob-lim)
- Channel: [Devcon](https://streameth.org/devcon)
- Date: 2025-10-07
- Duration: 15:16
- Watch: https://streameth.org/watch/yt-WR2ztiLgizA
- YouTube: https://www.youtube.com/watch?v=WR2ztiLgizA

## 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.

Speaker(s): Wanseob Lim
Skill level: Expert
Track: Applied Cryptography
Keywords: Cryptography, ZKP

Follow us: https://twitter.com/efdevcon, https://twitter.com/ethereum, https://warpcast.com/devcon
Learn more about devcon: https://www.devcon.org/
Learn more about ethereum: https://ethereum.org/ 

Visit the https://archive.devcon.org/ to gain access to the entire library of Devcon talks with the ease of filtering, playlists, personalized suggestions, decentralized access on Swarm, IPFS and more.

Devcon is the Ethereum conference for developers, researchers, thinkers, and makers. 
Devcon SEA was held in Bangkok, Thailand on Nov 12 - Nov 15, 2024.
Devcon is organized and presented by the Ethereum Foundation. To find out more, please visit https://ethereum.foundation/

## Transcript

[Music] uh hello everyone uh thank you so much for coming to my talk um today I'm going to uh have a talk about the SE lookup the lookup argument based on uh composite function um actually this is the first time uh that first time ever that we are presenting our work uh uh so my name is Li and researcher at PSC this is a joint work with my colleagues so I did this work with suan and dhun together and the summary is that uh given that we have a uh n size of table and a witness with size of M then if uh the this size is much larger than the table size we can accomplish a o of log squ M time complexity to the look of argument uh I'm going to explain more about uh how we achieve this uh first of all I would love to introduce uh where we got The Inspirations the first one was about the gkr because uh we notice that gkr is a very a one unique um version of composite function and the second was about hyper plong poop2 the permutation argument poop2 uh it is also using kind of a composite function it was very inspiring for me to uh think about the local argument using that uh and so using that we are using some compettive function just like in gk's each layers actually in our case we are using only one layer and we are achieving the O of uh log squared and time complexity uh so first let's discuss about the objective and let's understand the current situation that we have two sets uh first one is about witness and the second is about the elements of the given table and our goal is is to prove that for every element in uh W is also an element of a table in other words uh we are verifying that each witness element is contained uh within the table and this implies that the set of witness W is a subset of the table t uh okay and before we go uh deep dive into the lookup argument C lookup argument protocol I would love to introduce the main uh use case the interesting use case uh if you have the look of argument so what if you 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 ofx equals to Y always holds true uh provided that the witness is a subset of the predefined computations um 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 uh corstone for formally verifiable computation so we can Implement some like ZK PM which is also called The Look of Singularity which is also the uh jolt and lour uh approach um so I'm going to uh introduce our approach the silic approach so first we're going to define the relation silic up uh as the set of all all Ts of public instance X and the witness W where the public instance X is a tuple of Oracles of functions ft and sigma and the witness is a function of two is a tle functions T ft and sigma um to be precisely f is a function that maps all the witnesses defined on the domain XF uh with range YF and T is a function that Maps table element defined on a domain XT with range YT then if there exists a domain transformation function Sigma uh that maps elements from XF to XT also which satisfies that f ofx 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 uh public inance and witness is in the C lookup relation okay uh first I'm going to show you the knife approach version we'll consider a polom f and T and sigma over a finite field and we're going to use univariate polinomial approach uh then we're going to map the witness and element using the corresponding root of unity and the relation that F ofx always equals to T of Sigma of X for all the roots of unity holds true if and only if there EX is a quo polinomial Q such that F ofx minus t of Sigma of x = to Z of x * Q of X for the vanishing polinomial Z actually here exists a caveat that um the degree explodes the degree explores if we have the univ polinomial and if if we compute the composite function the degree of the the whole system uh becomes a degree of T times degree of the uh Sigma so which means like n * m but if we use multivari polinomial approach it changes a lot we will Define the domain uh on the vector space uh for the witness we're going to uh Define its domain as bullan hyper Cube uh over a log M dimensional space and for the table we're going to define the domain uh over the log n uh dimensional uh space and then uh defining the domain transformation function Sigma uh as a tuple of all the domain transformation functions then the relation that the F ofx always T of Sigma of X holds true if and only if there exist auxiliary polinomial H uh which satisfies some zero check Pol zero check uh Pro piop protocol precisely here the r and RP Prime and GMA are the randomly chosen uh Vector from the verifier and the auxiliary polinomial gives you the Rel gives us the relation that the there exist mapping correctly and the domain transformation is actually bound to uh the zero and one correctly as a result uh we could achieve the log squar of M against the witness size or uh log of the table size and complexity time complexity if we think about the protocol uh let's go through the protocol quickly so let's assume we have a witness witness f with with this Vector F and the table Vector T 2 3 5 7 11 5 like blah blah blah and the first step is preparation so we're going to compute the table polom but for a efficient uh some parallelization we're going to use the coefficient form but it doesn't actually actually does not a big uh thing because it's a pre-processing period and then we interpolate the with so just say for your uh easier uh understanding I just expressed this in a coefficient form and then we also need to find the domain transformation functions this is just a mapping between the uh table domain witness domain to the table domain so if we express that in the coefficient form actually we are using only the evaluation form and then uh we use public coin protocol to uh run some check only once uh by patching every everything together so we we choose uh the verifier choose chooses the r RP Prime and Gamma and in this case let's say we chose 31 37 for R and 5 and 7 for RP Prime and 9 and 11 13 for the comma run some check the first R will look like this and you can see here here uh the intermediate univ polinomial is not a linear function it has some degrees um and we run the following round and as a result uh we need to check the resulting eval random evaluation from this Su check equals to the thing uh that we can query from the Oracle uh which was the one of the public instance X so we carry the evaluations through the oracles and we check this uh they are hold they the relation holds true by checking this condition and consistency one important thing is that the uh main advantage of this approach is that it is very easy to decompose into smaller tables so we have a t polinomial here and we can uh decompos it into two smaller pieces T1 and T2 in T1 is just say t of 0 comma X2 comma X3 and T2 is actually T of 1 comma X2 comma X3 so we can decompose a table very easily we can uh de composite more smaller pieces also we can utilize this uh composite function approach with a a some we can tweak a little bit uh if if we tweak this a little bit then we can also compute the two intersection I mean size of two intersection of two given set and actually the result for the computational results also uh shows the same result uh one of the key thesis we had here is that if we uh use the composite function using multivariate uh setup then the Cod becomes to uh logarithmic and if we maximize the parallelization uh we thought that okay here's the composite function cost and in Univar function it was the really high because the degree was exploding but in a multivariate setup we can actually log Lo logarithmically change that and the result is actually like okay it depends on the number of rounds Times uh the composite function cost evaluation of the composite function cost and once again composite function is a very very generalized version of a gkr is approach um and to demonstrate our thesis actually we implemented the ca based Su protocol first in this repository so it was a highly paralyzing all the evaluations polinomial evaluations using GPU and then we utilize this CA Su check to see the results in this uh ccal cical repository we just use just for easier implementation but definitely you can change this commitment scheme to others uh and successfully we could see our result approach shows the logarithmic increase compared to the classical approach actually the implementation and Benchmark data is is still being fleshed out so uh but we are pretty optimistic for about the result that it's showing the sub linear uh result not only against the witness side but also against the table side uh the conclusion this approach is a very simple to understand uh comparing to other look of argument approach and it supports table decomposition gracefully and also it achieves sublinear proving time uh my toe was a little bit longer than uh compared to the given time so I I cannot have some enough Q&A time I'm going to be out there so thank you so much uh coming to my talk thank you very much man for your wonderful presentation and teaching us about C lookup thank you and uh we're going to start at 350 with the