[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