[Music]
hi
everyone so today we're going to talk
about how to build provs uh this is a
joint talk with my colleague aam and um
yeah um the main purpose of the talk is
to see how we can use list polinomial
commitments and we're going to create
something based um on Lio and breakdown
which are two pre just
works uh so just a quick word about us
uh we're both cryptography researchers
uh at consensus uh and we're working in
the linear pro
team and since you here you probably
have been hearing all this time how to
make proofs how to make proofs we want
to make proofs um and this talk this
intermediate cryptography talk is about
how to actually uh do that
mathematically and how to construct a
system so we're going to dig into some
details some mathematical details but
we're going to do that hopefully in a
way that carries information across to
you so just some motivation um at the
high level we're interested in how we
can move from a evm state to another one
uh there is the eternum virtual machine
State transition um that basically
explains how that happens and what
happens in the layer two rollups is that
that this state transition is being
arithmetization happened
properly
and why this is useful is that not all
nodes will have to perform the St
transition themselves they can just
verify the proof and since verification
um will be by design a very cheap
operation uh the overall system is going
to um to be quite
efficient and as I already um um as I
already um prepared you uh we're going
to look into how to construct such a
proof
system there will be two parts in our
talk the first part will be uh the
polinomial commitment scheme um which we
call Vortex and the second part will be
how to use this pomal commitment scheme
some other Machinery in order to um
reason about the evm
execution so let's deep into
cryptography uh with polinomial
commitments um so basically like these
two parts um are the main building
blocks of how to build a
snar so po polinomial commitments uh
first you're going to have just a setup
algorithm and um at a very high level
it's just going to give you some public
parameters so public
parameters
and if you want to commit you're going
to use these public parameters you're
going to use some polinomial you want to
commit to a polinomial this polinomial
will have some bounded degree K and
you're going to out output some
commitment
C and then we want to reason about this
polinomial about this commitment that we
just made and basically we're going to
look at a protocol that's interactive
between a prover and a verifier they
both have access to the polinomial to
the parameters to the commitment and in
the case of the prover also uh yeah also
the polinomial the verifier doesn't know
the polinomial only knows the commitment
and the prover basically attempts to
prove that P of X is indeed equal to
Y and this happens over multiple
interaction
rounds
um very high level the security
condition that we want to achieve is
that the approver should not be able to
convince the verifier in the case that
he committed to something to some
polomia that actually does not evaluate
to to the claimed
why and we want to do this efficiently
we want to amortize our costs so
basically we're going to do something
called batch polinomial commitments in
instead of committing to only one
polinomial we're going to commit to n of
them uh we're going to have we're going
to claim n evaluation n evaluations and
basically the proof is going to be a
badged proof a combined proof that all
of these polinomial evaluate
properly and also the verifier now knows
the evaluation um the claimed
evaluations and let's look into the math
that we use in order to build such a
thing um these are called the read
Solomon code code and without getting
into the nitty-gritty um we're going to
use a finite field fee F uh if you don't
know what a final field is just imagine
uh uh integers modulos some prime p and
we are going to take some subset of n
elements A1 to a n from this final field
then encoding a polinomial so this is
about the codes ining a polinomial we
just be evaluated the polinomial at this
end
points and in order for you to actually
in order for this encoding to actually
Express information about the
polinomial um you want that the degree
of p is actually smaller or equal than n
uh in order to be actually be able to
express it uniquely and in fact you want
to have this n is going to be much
higher you want to have redundant
information about the polinomial in
order to error
correct um and now let's look at the uh
what we uh where we took the the
starting point where we took inspiration
for our work uh which is the Li
breakdown protocol um these are two
separate schemes but um uh they have a
very common structure so in this
previous work the setup algorithm would
give you a hash function as the public
parameters and then in order to commit
to n polinomial what you're going to do
is that you're going to you're going to
first compute the encodings the r Solon
encodings of the N
pooms each row now corresponds to an
encoding you're going to construct this
Matrix and you're going to apply a hash
function on each column in order to get
H1 then you apply the hash function on
the second column to get H2 and so
on and this is going to be your
commitment your commitment is this
hashes of The Columns of the encodings
uh of your
polinomial so that's how you commit and
I put this here in case you forget it uh
now we also interested in how do we open
how do we actually prove to the verifier
that uh our claimed devaluations are
correct and in a secure way so basically
the verifier is going to send the coin
beta to the prover the prover is going
to compute this looks like a complicated
equation but actually it's not it's just
you have each row and each row gets
multiplied with the power of beta so
it's a linear combination of the rows
with this beta that comes from the
verifier this is a vector U send it to
the verifier the verifier now picks an
index that it wants to check it's only
going to be able to check one send it
back and the prover replies to the
column of that specific index in this
case this is the first
one the verifier does two checks it
checks that indeed when it applies the
hash function to the opened column to
the one that we just revealed it is
equal to the one in the commitment and
it checks that indeed if you compute the
linear combination of the betas with the
revaled columns then you're going to get
the I coordinate of U in this protocol
is going to ensure that all the rows are
indeed code
words but we want more than this we want
to actually make a proof about the
claimed evaluations of the polinomial
not just show that the rows are code
words and what we notice um in this work
is that if we interpolate this Vector
that is sent by the prover to obtain
some polinomial and then we also check
that this polinomial evated that X is
equal to the linear combinations of the
Y's if we do this additional check
you can actually ensure we can prove
that the polinomial is evaluate
properly
and um this proof can be very simple if
you are in the unique decoding regime
which I'm just going to talk about next
um the point is that if you want op if
you want optimal parameters the proof
becomes very complicated and I'm going
to give you just a flavor of why that is
um so basically when you're talking
about codes you you can consider two
cases
there is the unique decoding which in
this case is exemplified by this radius
this is the target Vector that we want
to decode and this is a radius around it
and as you can see if you set it to this
length then there is only one code
word however you can also consider
relaxing this op this U this parameter
to be able to include multiple points
that are candidates for your
decoding and the proof for our
polinomial commitment schem becomes much
more complicated if you want the optimal
parameters if you want to have something
that's efficient in
practice so as I said the small one is
the UN coding regime there's only one
candidate and the yellow one is the
least one multiple
candidates um so the security guarantee
in the that we show in the listed coding
regime is that there will exist
polinomial polinomial a small degree
that evaluate correctly and this
commitments will have only a small
amount of coordinates that are different
from the target commitments that we are
decoding um and if you want more details
for the proof of security you can check
out our reprint uh and there's also
thanks a lot I'm going to now now we're
going to move to the second part of the
talk where we're looking at how can we
use this pomal commitment to um in
conjunction with other things to reason
about the evm and I'm handing over over
to my colleague
aam thank you
B uh so
uh let's go to the second part uh how uh
and here we are focusing what is
happening on Layer Two linear and how we
generate proof from evm execution via
such polinomial
commitment uh there are a lot of Step
until we can generate proof the first
step in this journey is arithmetization
and arithmetization for us is
mathematical modeling of evm by columns
and constraint between columns for
example if you want to prove that a
transaction had a valid signature first
you hash the signature so you have to
prove that the hash was correct so if I
want to here to show that hash of is y I
start with column X and column X is a
kind of a describing your input EX for
example you can consider the bite of the
X which are splitted in the cells of
these
columns then which uh with each steps of
the uh computation that is happening in
the hash uh this column you would have a
new column with new values in the cell
and so on until that you would arrive to
column Y which is your
output and there is constraint between
this column to say that uh how the
computation of the hash is going on so
by this arithmetization here you we get
bunch of columns and constraint between
columns uh there are different uh
constraint uh for example it's just uh
example here there are more uh Lop
constraints or Lop query we Alo can
say which says uh column o is included
in column B uh or local constraint that
says okay if you have two columns then
uh the first row of these two columns
are
equal Global concern which are very
important for us and uh they are more
about cells uh the relation over the
cells of or the same column or even
between several columns uh I'm putting
an example here for Fibonacci sequence
for uh for this Fibonacci Sequence we
know that for each cell is in fact
addition of two previous cell so you
write the constraint like
this for this uh and we call this one
Trace uh trace of execution or
fibon okay if you want to verify this
Con constraint as a verifier definitely
you don't want to do it uh like this
because it's too many effort especially
Global constraint because they are over
the cells and you have to check a lot of
uh relation between columns and cells so
and that's where uh uh polinomial
commitment comes to
rescue we write each column as a
polinomial uh we interpret the column as
a
polinomial for example you can say that
okay the values in the columns you can
see them as the coefficient of a
polinomial and by this the constraint
would be translated as a relation
between pols and from here you can apply
polinomial Comm commitment I want you I
remind you that polinomial commitment
can do two task for you which are very
simple but very important one task was
it can commit and by a short commitment
and you can use the commitment uh to
open to request the evaluation of the
polinomial uh another interesting uh
property of the polinomial is that why
we are interested in polinomial and why
we are going from columns to polinomial
is thanks to this LMA Schwarz Zer LMA
and it says that if you have a relation
for a polinomial between polinomial
commitments you don't need to check the
relation for each ex you just take a
random point from the domain and if the
relation over the random Point Alpha
satisfied then you know that it was
satisfied for every ex this would
simplify everything and that's why we
are interested in polinomial because by
this verifier uh task is very easy it
just needs to take a random point and
then verify the polinomial and
constraint over this random
Point uh so by this so we can get now
uh pols a bunch of polinomial and
constraints we are very close to get the
proof but we are not still there and the
reason is that these constraint are not
the constraint that uh I
want uh the constraint that we are
interested in are Global constraint why
Global constraint because uh thanks to
this Schwarz Zer Lemo uh you can verify
them easily uh Global constraint are
between cells so you don't need to check
them between cells you use short zielo
over global con straint and you just
check in a random point so we are
interested to kind of reduce this
constraint every constraint that you
have for example Lup queries permutation
queries and a lot of queries that may
happen in during arithmetization we want
to replace them with global constraint
because from there we have we can have a
simple verification uh via short Z
LMO to do this to go uh to get global
constraint we need uh
piop but what is
piop piop stands for polinomial
interactive Oracle
proof uh it's a idealize ideal modeling
of a protocol between PR and
verifier
uh you have a SE party between prover
and verifier uh this uh handsome guy uh
that we call it
Oracle Oracle is honest and can answer
any question so prover and verifier
start their interactions and they use
this uh Oracle to help them to reduce
their constraint uh to Global
coning and uh there is a
theorem that says that polinomial
commitment in such
construction uh resemble to an oracle
because Oracle does not exist uh
such guy does not exist unfortunately so
we have to replace it with something
real and there is a theorem that says
that polinomial commitment is a good
candidate and you can replace it with
this guy to help you to reduce your
polinomial to constraint to normal to
Global and now we are fine so we use
piop we reduce everything to the global
constraint and we can use a polinomial
commitment for this but we cannot use
our Vortex and the reason is that our
Vortex is not a standard polinomial
commitment that and the theorem is not
true uh it's not a good candidate for
Oracle uh why it's not good candidate
it's because of this uh property least
property uh why it makes problem why it
cannot work with
piop and the reason is that in piop you
have rounds of interactions between
prover and verifier and uh in fact due
to this Leist property polinomial has a
lot of choices in different rounds and
he can do kind of mix match attack
between different rounds and different
polinomial from the
list uh but we have a trick for this we
uh can prevent uh in in fact we use a
trick to force uh which we call it Comet
separately and open colal ly and by this
uh I don't go to the details theoretical
details but by this trick we are uh we
are able to force the prover in fact to
open uh all the uh polinomial
commitments at the same position over
the D skill let's say uh so for the
first round maybe he has choices but for
the other rounds he doesn't have choice
and he has to stick to the First
Choice uh so this would solve the
problem of list but still Vortex is not
good one more step and why it's not a
good it's now because this nice property
I I call it nice because it's batching
but batching uh uh it's not an uh
General batching uh as you see in Vortex
the batching is just batching of all the
pols over the same
point uh and in the real application
poop applications when you applied your
piop in fact you are in the general case
that you have many polinomial many uh
points so this kind of batching even
though it's nice but it's more fantasy
and it's not applicable
here uh but we also find another
theoretical trick to solve this
problem still I would not go to the
theory just uh uh the general view is
that we come back uh to the step that we
designed our poop uh and we kind of
modify it to be able to use batching
over the same point and the way that we
modify it uh is just uh first they uh
convert uh can speak freely and at the
end we apply uh a kind of reduction via
Oracle over the same point and from here
now Vortex is applicable we can replace
our Vortex with Oracle and we are done
finally we have our first
proof and here is just an example of the
parameters if you are interested thank
you very
much thank you very much uh I love the
dynamic between the two of you
explaining the different SES it was cool
uh we have some questions and uh also
some that I had sorry I also introduced
you wrong I said you're from the prover
team of consensus and then I was like
consensus doesn't do proves so from the
Linea team and I guess that became clear
immediately but yeah so one of the first
questions was uh is this the vortex that
line
uses uh yes uh this is the first proof
uh that's why I mentioned that finally
we have our first proof this is the
first proof that we generate after there
are a lot of more layers that will come
to aggregate the this initial proofs and
uh finally a final proof to be
compatible with uh ethereum uh but this
is yes this is the first proof that we
generate in
lineal and the classic uh any benchmarks
how fast is it Benchmark was uh because
uh as I said this is the first proof so
we have uh several kind of recursion and
uh our estimation is that uh you need uh
for 100 bits of security you need
15 millions of constraint uh inside of
for the verifier of Vortex inside of
plun and uh comparing to breakdown and
liero that are in unique decoding uh
this is four times fast the not faster
but the size of the proof is four times
smaller nice so I think this uh question
comes up or well this might answer the
next question in part at least so what
are the advantag ant ages disadvantages
of Vortex compared to other polinomial
commitment schemes so in terms of pro
time proof size you mentioned with proof
size already
but uh yes I mentioned about proof size
that uh is a uh faster than breakdown
smaller than breakdown four times due to
due to the least uh commitment property
and regarding the Prov time uh uh
um both are
uh good I mean it's as good as buron but
it's also I can compare it with a fry
for example because uh Vortex it's very
important property that it doesn't need
thrusted setup it's like fry and uh
comparing to fry the prover is
faster yeah good so a last question uh
is batching over the same point does it
impact the security uh that's why we
went all through this uh uh modifying
poop and modifying distri of uh
commit separately open
collectively all of this was for the SEC
uh proof of security so the paper in
fact analy the security that okay it's
not a standard commitment so how can we
use it uh
securely nice I see maybe one more
question came in as we have two minutes
left for questions maybe we can can uh
scroll and see I actually left my uh
phone
okay never mind what question would you
love to
hear pick your own
question H what field do you
use uh uh in fact the only property that
we need is because you uh uh we use fft
so the only property that we need is to
add city which means that the order of a
uh if your field uh is uh Q uh the prime
that we are using Q minus y should be a
big factor of uh two to uh so if you
have this property it's enough for us
after uh because we also have used uh
it's a a ltis for the hash for hashing
of the columns uh so we may for
optimization can we have uh more choices
in distance but already this the
this fact that we just need to add the
city is it would give us a big Choice
nice good and thank you to whoever
upvoted the question so we could read it
collaboration at its finest so let's
thank the speakers once again um thank
you and yeah catch them if you want to
know about L's Prov thank you very much
bye uh