ZK12: From IVCs to RCGs - Ariel Gabizon

Transcript

[Music] so I I I always uh get a haircut that convey zero knowledge about where my bald spots are before I talk about zero knowledge so uh okay so let me give you a a small outline of the talk uh uh first I I'll start with some simplified details about the Aztec uh smart contract system uh this will lead us to define a notion called uh repeated computation

with global State that's um then we'll go over how to deal with global State uh using uh log derivative methods uh and I'll end by highlighting a theoretical issue I want theoreticians to look into [Music] so so Aztec is about uh private smart contracts so like ethereum uh contract has functions uh but since everything is snark ified every uh function say A and B have some verification key uh that Ma

matches the function function and uh what can functions do well one important thing they can do uh for this talk is that they can call each other a function can call a function in the same contract or a different contract so let's spend a few minutes thinking about how what is what does it mean for like snark circuits to call each other um so for example let's say we have we

have this execution um we're calling a with args a somewhere in the middle of this execution it's calling B with args b and we want to make a proof of such an execution um so the the basic idea is uh A's public input will contain the verification key of B and the arguments of b um and one you may be wondering what why why is this an issue at all to prove

such an execution like don't we have such stuff and we we sort of do like what's a little different in the Aztec scenario is that the functions are already individually snark ified so a has vka B has vkb and we're expected to use those keys uh okay so so here's what what what uh this could look like so we we'll construct a proof for a uh called the proof Pi a where the public input now contains the arguments to a but also the

verification key of B and the arguments to be and now we'll construct a proof for B where uh the the public input is is just the arguments to be and we'll have a verifier check uh check the proof for a with uh key vka and public input XA we'll have the verifier also check proof pi b for uh with verification key vkb and public input xB

and since this V will enforce we'll use the same args B and vkb for checking a and checking B this corresponds intuitively to a calling B that's the basic idea okay um but now we we want to massage this to a more uniform

form uh so we want to think of these different steps as iterations of the same function so we'll have this function f where the inputs of f are the current VK uh the current public input which again is consists of the the current AR arguments of the current function the next verification key and the next arguments and by the way this is sort of an arbitrary choice for Simplicity that like the current function is calling at most one other function um it might be even more natural to think of it as calling

several in the code it's four the maximum uh so and also uh another argument of f is the current proof Pi uh and the current stack of functions to to be called and now what is what does f check um so it checks that the element at the top of the stack is the current V K and the current args and it'll pop it off the stack uh it'll check

that uh the proof Pi with public input X and the current VK accepts and it'll push to the stack the to the top of the stack the the next function the next VK and the next args um another sort of simplification here for presentation is so here it looks in in step two that Pi is like a full snark proof and we're verifying a a snark proof in the actual protocol

uh we're uh the step two is just uh what's called folding um a proof of correctness uh or really just folding the the witness so like if you want to make it closer to what's actually going on Pi is you you can think of it as just a as really as a witness as the actual original witness um yeah but for Simplicity you can also just think of pi as a proof all right so so this is just this this F is like a way to when we have a

sequence of calls just a way to think of those SE and in each call is right for a totally different function potentially uh right because different contracts have different functions uh but this F is like a way of thinking of of this you know process of one function calling another calling another is just iterations of the same capital F but we we so far we forgot to deal with global state in in addition to

functions uh a contract in Aztec will have notes representing its state for example the notes N1 and N2 and in in addition to calling other functions a function while it's executing can add read or delete notes of its contract so to enable these uh Global State

operation we'll add to the public key uh public inputs so so far we had the the current arguments the arguments and the VK of the function you you're you're going to call next maybe will also add um to the public input the note operations you're do you're doing so for example the here like the call to a and and these operations they will have timestamps so for example here uh the call to a is reading note n at time stamp 8 and the call to be is reading uh is reading is sorry is creating or

adding note n at time stamp 3 and and now the problem to deal with is so when we're verifying the the proof to a we see this note operation um read note n at Tim stamp 8 but while we're verifying this proof we can't be sure that in some future IVC iteration will'll indeed see the note and created and moreover created with an earlier

timestamp right we don't want to read notes that haven't been created and we also don't want to read notes at an earlier timestamp then when they were created so at a higher level uh the the order of proving here is different than the order of execution since like I said before the functions have already been individually snark ified right in execution we we start with a go into B finish B go back to a finish a but since the function are individually already

snark ified we have to prove it in a different order we have to do all the proof for a and then all the proof for B so in execution the note n was created before it was read but in proving we're only get to going to get to that creation of the note n later in the proving process so to conveniently deal with this

setting uh we Define the notion of rcg repeated computation with global state uh at a high level or even a less than high level rcg is very similar to incrementally verifiable computation IVC which you've probably heard of a a lot uh but there's two there's two differences so the the the first difference is that in our R CG we know the end point the computation ends before uh proving

starts so if in the original IVC paper Paul Valiant is talking about a computation humanity is going to be doing for Generations uh here we're assuming the computation has ended uh before the proving is started um so then well you could say okay so then is it like IVC at all if it's already ended so what's the what's the why is it even similar so the the desirable property in IVC is what people uh they call complexity preserving uh sometimes that the the pro

memory even if the computation has many steps the the prover memory depends on the memory of uh of that the one step for example one execution of this function capital F we had below so in rcg we we still want to sort of have have that property but we we relax it so we say uh the Prov memory uh should mainly depend on the memory for for one iteration but it's also allowed to depend on the size of the the global state so let let me walk you through a a

simplified version of the the actual definition uh so we're going to have uh to Define an rcg relation we're going to have a transition predicate and a final predicate and now we're we're going to say these uh transition and final predicate they Define the the relation of pairs X W uh where X so what is X x contains the the final proof the final State sort of Z final and the number of iterations

N and W contains uh three vectors z w and sorry and S uh where intuitively Z is going to be the different states we we go through uh W is going to be the the witnesses that get us through those States and the s's are the the ch chunks of the global State we use in each uh each iteration so we so we say that uh W xw is in the relation if well we end ZN is Z final so we end in the desired uh

final State um for each I the transition holds so F of zi minus1 wi Z SI is is valid is accept uh and the the final predicate uh if we if we insert into it the the all the s's from all the iterations it's it outputs accept uh right so this third thing is like where we have this additional ability that we wouldn't have in IVC we can we are allowed to test some final

predicate of little we think of them as relatively little chunks from from all the erations um and again the the point is you could just say okay just build a snark for this relation what why do you call it rcg uh just build a big circuit and the the again the point the IVC like kind of point is is uh we we say a snork is space efficient uh if the prover requires SP space uh I'm not formally defined here the size of f but requires space which

is roughly the size of one step plus the size of the the global State that's the memory that we allow the prover to use so like I said this is a s simplified definition I I I will raise one little hole in this simplified definition and maybe it's occurred to some people here maybe we want to hide the number of iterations when we do the ZK snark so in the actual relation this n is not part of of the instance X what's part of the instance X is some bound C on n and n is part of the

witness yeah uh okay so uh to to illustrate this point uh so let's see how we use uh you know an example of an sort of rcg uh to deal with these uh these memory operations um so uh we're going to add to the to the ad operations we're going to add uh the number of times

uh by the way if you don't have like deja vu is because I prepared these slides according to previous talks of of yens so uh so we we're going to add to the ad operations the number of times a note and a note was read so that's this this num read uh field we're we're going to add to the uh to the read operations uh and we we have the Tim stamp where the note was read we're going to add to the read operations uh the the

timestamp uh where where the note that's being read was added so that that's this at and now what what are we going to check so uh in the transition function we're going to check for each read that a is smaller than T that the alleged time of creation of the note was smaller than the time we're we're reading it and and now we're going to sort of use the fact that we're allowed uh were allowed more more memory in in

the size of the global state so the prover is going to store all the node operations from across the the iterations and it's going to Hash them to get some challenge beta um and so now right so our goal is to our goal is to check that every time you have a read um you're reading a note that was create really added and also added at an

earlier Tim stamp so so this check at smaller than t uh sort of checks that if this note is legit that that the the time St of addition is is is smaller as needed but but right it could be that when I have this read n it could be that there actually does not a I'm not going to have an operation ad like n a I'm it's just so so we need to check that all the alleged creations of of notes really happened and that's going to be done by this this fractional sum so right we're going to check that the sum of the reads

of this expression think of the node as just a value in the field uh we're going to have this sum over the the reads of 1 / n + beta * a the alleged time of creation of the notes and we're going to compare that to we're going to sum now overall add operations from from all iterations and we're going to compare that to to now for each read we we put in the numerator the the alleged number of times the note was read and we divide that by n plus beta * t plus the time stamp of the ad um and and you can you can see that if some attempt to cheat was made like a

there's a read operation for a note that doesn't exist then with very high probability over beta this the sum won't won't be equal five okay uh okay so that's that's some details from the uh construction and I want to end by highlighting a theoretical issue that I think need

needs could benefit from scrutiny uh so in this paper to to make our proofs uh e easier or easy or at least easier uh we use what I call uh the recursive algebraic group model that was implicitly introduced in this in this paper analyzing Nova uh by lean SE I hope I'm saying that right and let me explain to you what this recursive algebraic model is so let's let's talk about the original AGM what was the idea there the idea there is that if I have I have some structured reference string of

elements of the group uh then when an adversary outputs some a in the group uh they must also explain how they got to this a by the SRS elements so they must output but also a vector of of scalers C such that this a is equal to some C ivi okay but now let's say we are these group elements we're representing them as pairs of field elements so fix some representation function of G by by pairs of field

elements and now suppose that you know know the algebraic adversary outputed this Vector C and it just so happens that for some two adjacent indices in this Vector of scalers C CI CI + 1 is a valid representation of some group element B so you could ask if if you uh you could ask well shouldn't the algebraic adversary now also give us a uh explained to us how he got to be using the SRS and some would say no no you you

shouldn't do that but the recursive algebraic group model says yes you should definitely make the adversary's life a bit harder and your analysis a bit easier and yes you should you should demand uh an explanation how how to also make B uh from uh the SRS elements so so the theis of algebraic adversary now must also output C Prime such that b is uh Su C Prime C Prime I VI and then you ask well what if C Prime there's some two indices that are a valid does does he have to do it again yes that's where why

why there's recursive in the name so the recursive algebraic adversary must keep outputting these vectors of scalers C until he his output vectors with no nothing there no to adjacent elements there are um right it's a sanity check you could say won't he always by accident there' be some C plus one like this and it'll be an infinite Loop well it shouldn't be because right if if f and g are of similar size say in the elliptic curve case it it shouldn't happen by accident that you know so but so this is the question I want theoreticians to look at because I I I really like writing proofs with this thing uh for IVC uh so I want people to look into is

this legit and yeah so that's sort of a shout out for that yeah so thanks for listening thank [Applause] you thank you very much Ariel we have a bit of time for questions if you have any one over there oh hi arel great talk um in the recursive uh AGM uh sorry uh algebraic group model um is it necessary that CI and CI +1 they are consecutive like it could be any like any two yeah that's a great

question the it is a little ad hoc to look at all adjacent pairs the reason why you can't look at all sub sets is there's an exponential number of them and then you will be in a situation where oh just by chance some something is a representation and the the adversary will be an infinite Loop any other questions all right so let's thank our speaker again [Applause]