SNARGs Book Study Group - Week #4 with Giacomo Fenzi

Transcript

until now we've been like looking at a lot of different things you've seen like definition of the random Oracle model you've seen like the initial like f first for the sigma protocol then for interactive proofs and in general like what we've seen like in this in this course was like how you can take information theoretical tools and then combine use them to get to two arguments and 1 arguments and currently what we have seen was like especially was like how to compile interactive proofs into to arguments so turns out that constructing good and non-trivial interactive proofs

is like our problem because there are some fundamental limit to what we can do like basically in some sense like things like JKR and the RR protocol are the best like kind of tool that we know for this kind of job and while they are very nice they by themselves they don't give you enough what the what we're going to do next in the next few weeks we're going to move toward like more exotic and maybe uh less intuitive like model of computations namely those of probabilistically checkable proofs and interactive Oracle proofs and we're going to be showing how to use those to construct arguments the recipe itself will be very similar to what we've seen before so

we're going to be like starting with taking one of these protocol an interactive proof or a PCP and then we're going to be compiling it to get to an argument using the random Oracle what's really differs is that now the kind of interactive tool that we have will not we will not it will not be enough to just use thehm it's like a new tool that we will see there are Oracle models in which like basically the approver will send oracles to these messages and so we need to have more like cryptography and more Tools in order to compile them to to interactive arguments so in this particular lecture I'm going to start

introducing some of the tools that we're going to be using later on so the main tool we're going to be using are going to be Merle TR and this lecture we going to be start by first talking about commitment schemes and then we're going to use them to build Merle trees and then we're going to revisit a bit of the security property that Merle tree gives in the random Oracle model and this will be helpful later on for like when we going to be using them in constructing for example helan and BCS transformation but in particular they also will be useful wherever you're using mer tra because they give you like really they they pin down what kind of security properties you can you can uh expect from these constructions so I'm going to connect

from my iPad so you're going to lose me for a moment but I'll arrive so just bear with me a second hello hello can you hear me yes okay amazing and let me also share my screen okay you can also see my

screen yes okay amazing then then let's do this uh okay so we're gonna be doing things in two steps so this chapter is relatively light compared to the other ones because we're just not going to be talking about anything but commitments so could you maybe turn the try turning the laptop the other direction the landscape Direction uh yes you that's a very good point better thanks yep way better thanks okay perfect and also when I'm in on the laptop I cannot see

the I cannot see the what's it called the chat and things exactly so if anybody has question in the chat just somebody please read I'll keep an eye yep I keep an eye on it thanks thank you okay so we're going to be like talking about commitments so to pick a value in a certain sense this we want to replicate the same kind of like functionality that an envelope gives to

us so if you have an envelope which you're going to see some amazing drawing skills over here this is an envelope incredible I can put stuff into it then I can close the envelope and later on I can reopen it and get the value out this this physically in the real world this has got two properties one of them is what we will refer to as binding which is I cannot change the content of the envelope what it means when I put

something inside the envelope I cannot tamper with it with what it inside the second notion is hiding which means means uh the envelope hies what's inside so when I have a Clos envelope I cannot tell what it is committed into these are the two properties that an envelope gives us and we would like to mimic them with a commitment scheme and a commitment scheme iner is a very basic

notion in cryptography was one of the very first thing they were like studied and in our particular case we're going to do like commitment schemes based on the pure random Oracle model because in this in this book we just want to care about the random Oracle model so this we'll see how to achieve this kind of functionality with something which we call the the basic commitment which you can imagine as the simplest possible form of commitment that that you could choose and then later on we'll see how to upgrade it to something stronger called uh Vector commitments uh we'll see a bit better

what the definition of this is but now the kind of like intuition that you should have is that like I can now commit to a vector say I have some Vector in some alphabet I can commit to it and later on I can prove let's say the position at I is like zero for example so I can prove a single index over year so I don't have to reveal the entire thing and we're going to see that the way you can construct Vector commitment in the random Oracle is via this classical construction which is called Merle in fact the basic commitment will

already introduce a lot of the property that we will later on want to care about the mer it will be a very nice and natural warm up to Merkle trees which is what actually we will really need later on okay questions about this overall strategy okay then I can go straight into it all right I said before the a non-interactive commitment is it enables a party to commit to some message while obtaining these two

properties of binding and uh and an ID so what do we want to do first we want so just to get some notation M will be the message that we want to commit and CM will be the commitment so the the first thing that we want to name is some kind of like completeness property so we want that once I put the message in the commitment I'm later able to open it up so opening is the act of revealing what's in the commitment second we will have uh

binding it is like the that it should be hard to to open the commitment to a different message finally we want to we want to have iding which means that the commitment should not reveal any information about what message is been put inside this is just telling us what we want to achieve and now we're going to introduce the notation for

it so we're going to be like considering like a tuple of algorithms which is this the commit and the check algorithm and it will be extremely simple we're going to be using the random Oracle in the easiest way possible so the entire description of the commit scheme is just the following to line so when I get a message M to commit it what I do I will sample some salt I'll explain why this is needed later and then I just my commitment is just obtained by applying the random

Oracle to the message and the Sal so just to reash this so what I'm doing is I have as input a message I sample some salt I'll use it in blues just to say what what's related to the to the hiding property and then we the commitment is just obtain by obtaining the by applying the random Oracle to the message and F pair now what do we do to then verif that something has been committed to the opening algorithm is just the prover

will reveal what the the committer not the prover in this case will reveal what the the Sal is so it will just reveal oh sorry and then the verif the the person who's checking a commitment you will query the random Oracle to check that in fact the commitment is the obtain by applying the random Oracle to the message and the result so this is really simple as a scheme you're just really sampling a bit of Randomness you're quering the random Oracle once and to verify you're also quering the random Oracle one and here's another diagram of what

we're doing so we're taking the message and Thea we're asking the random Oracle and we get in the commitment and this this very simple Construction in fact it can be shown to satisfy very strong properties so the first one I said before we will show that it is binding and it is hiding so once you put a commitment in you're not able to change it to a different once you put a message in you're not able to produce an opening for a disting message and uh it is hiding in the sense that the commitment does not reveal any

information to what message has been committed to further uh he also satisfies one stronger property which is that of extractability this will be very helpful for later on when we want to do like knowledge sounds ARS but for now think of it as a strengthening of binding okay questions on the scheme okay let me move towards what we mean to buying a big effort of like theoretical cryptography is like actually finding

the right way to to formally Define what are intuitive Notions so this case we need to talk about how to formalize the the fact that ver cannot find two distinct messages that open the same commitment so the intuitive reasoning of why this scheme is binding is that it comes from really the fact that it is hard to find Collision in the random Oracle so suppose that we had a collision so suppose that we had we have two pairs which have the same commitment the means that there are

like some M and pi and M Prime Pi Prime which end up mapping to the same commitment CM with M different from M Prime so what is implies is exactly the fact that F of M to is equal to F of M Prime to and which is which is exactly a collision in in

F so if you're able to find an opening for two two openings for the same commitment you have directly found a collision in F the since f is a random Oracle this cannot happen as we've seen in the first in the very first lecture that I gave a few weeks ago one of the main properties of random Oracle is that they are like they actually do not have collisions the at least an adversary

which makes a few number of queries will not be able to find collisions so this intuitive explanation formalize the intuition that this schem is binding so let me just State what uh State what exactly The Binding experiment looks like so we have a theorem here so The Binding experiment is the following so first as in every like game in the in the random Oracle model we start by sampling the random Oracle then that

versary then you the that versary with access to the random Oracle tries to find five things you try to find a commitment and two pairs of message and salt and to me pairs of messages and thought the adversary wins this game if the following things are satisfied first the two messages are distinct second both both

um both messages Sol pair end up like verifying correctly and what the f says is that like the probability that this happen the is bounded by this by this term here which is roughly the complexity of finding a collision in less than T queries not the compet sorry the probability so what what is stat say

look consider the following experiment first I sample aroundand the Oracle then a outputs a commitment cm and two pairs m0 t0 and M1 T1 a WIS is m0 is different than M1 and the commitment checks just to expand the verification this is just like that F at m0 t0 is equal to CM and F at M1 T1 is equal to CM so this

is the game like I'm just um explaining it like uh in detail because later on we're going to be moving to the vector commitment case you will be good to have this kind of idea of a commitment experiment very much in mind so okay so just to recap we've shown so this here this LMA shows that the commitment scheme is binding and I don't want to go into proof as always the proofs is something that you should check on your own time time I think they're very informative and this one in particularly is quite nice and not particularly hard but what the proof show is that the probability of for of an adversary of breaking The Binding

property of the commitment scheme of this basic commitment scheme is roughly related to the probability of finding a collision in the random Oracle this bound is in fact tight because as I sketch beforeand if I'm able to find a collision in the random Oracle then I'm automatically able to find a collision in the a collision in the commitment scheme okay H questions on The Binding game so this is The Binding

property and we're going to one other thing that I want to note is that if you look at look at this what is error term looks it depends on only two things so one of them is the of course the query budget of the adversary and then it depends on the digest size of the random orle the thing that it does not depend on is the size of the salt intuitively this is because the salt has to do with the hiding property we'll see this will be very important for the hiding property while the while for the for binding it really doesn't matter particularly

much and in fact if you're like interested later on to compile arguments which only have subance and you don't care about the knowledge for example then you can forgo the Sals entirely and this can have some non-trivial improve and improve sizing for example okay yes you could also so the kind of binding we saw today is a binding which is computational in the sense that an adversary which makes enough query to the random Oracle will be in fact able to to BL to to break the

binding property in fact one can even like so commitments they can they often can be also statistically binding and in particular this is another case of a commitment can be statistically binding so if if the Dig size of the random Mor is large enough turns out that not only finding conditions is hard but in fact with high probability the dorle will be an injective function so actually finding Collision will actually be impossible with high probability but in particular it doesn't matter how many query an adversary does with ey probability you will not be able

to break the binding property we are not particularly interested in this case because we will want our like commitment to be compressing and when the commitment is compressing by definition the the random orle will not be injected because you're mapping from like a larger space to a smaller space so there will be Collision the only thing that we want is that these collisions are hard to find so in this case we settle for just this computational binding okay so let's talk about a little bit of a stronger notion of of that the basic commitment satisfies and that is that of extractability

you might remember the there are two different notion of soundness first narcs one notion of soundness which is the one notion is that of normal soundness which is roughly saying that an adversary cannot make the verifier accept on a false statement a stronger notion the one can aim to achieve is that of knowledge soundness which roughly say that if a verifier is able to if aover is able to convince the verifier of any statement then there's existant extractor which is able to extract the witness to that statement and this is a strengthening which is very much needed for a lot of

application like for example PCD record Pro composition it's very important in practice binding in a certain sense relates to the soundness notion of the the the argument that we will be like constructing later on while extractability will be something that we will need to instead get knowledge soundness so what does it mean in this setting a Comm scheme is distractable if if whenever an adversary is able to Output a commitment that he can

open then this implies that the this implies that the adversary actually knew the opening at the commitment time so in the book they studi this for both one commitment and for multiple commitment but we're going to be looking just at the single commitment for Simplicity I'm going to talk a bit about what the security experiment is and now the security experiment is a bit more comp complicated we we'll actually have two phases so maybe let me get some space and then I'll write what experiment looks like can I paper okay so what does the security experiment looks like so we will

have it will be very similar to to to what we have in other things so we will have that first we start by sampling random Oracle as always then what will happen is that the so this is the first stage then we will let the adversary run with the random Oracle and after run the adversary will will output some commitment CM okay so what will um will yes so we will let Trace be the

list of queries and answers made by a to the random Oracle so this will be a list of like pair of the form like Z1 y1 Z two Y2 and so on up to say Z T1 and Z yt2 T1 sorry okay we're going to give to we're goingon to give um this list to an algorithm which is going to be called CMS

trct CMS trct will be given as input both the commitment CM so this commitment over here and this list of traces and this will output like some new message M actually should let's call it m star because I like stars okay then the adversary has another goal so the adversary will run again it run again and we assume that this can be they can keep state so the adversary will run again and now

he will try to to Output some opening so in this case this will be like just a pair in which case that adversary win the adversary wins if m is distinct from the message extracted and the actually F of M to is equal to the commitment so intuitively a wins it if it is able

to to create a commitment that then the adversary like that then the structor out exract a message from but then it is able to is it able to Output an opening to a different message okay questions on this game okay so maybe let's go back to the book so again let's remember just to notation

we have as before we have the the sampl of the random Oracle then we have the first phase in which the adversary outputs a commitment then the structor outputs in fact we do a likely stronger property in this case the adversary exract message and assault from this commitment in this trace and then the another go the check satisfies and the distracted pair is different from the actual pair opened by dver one of the interesting thing is why

is it actually required us to have two phases why did we actually need the adversary to be able to to do the second phasing which is start to Output which remember we didn't have in The Binding game the reason is that the adversary might be able to like one one thing adversary might do is just like select a random string and just without clearing random Oracle and just just output that then the structure has no way of actually figuring out what is the value inside but it doesn't really matter because ADV version in that case has no really has only a very small probability of actually being able to open the the message to anything because it doesn't know what is a preimage of this

commitment and you would have to work very hard to find it so in this case in this this game kind of encompasses all of this kind of thing the structor in fact is very simple the structor it's h described right here just what he ends up doing is just searching the trace for query answer space which has the commitment as the answer and if he doesn't find anything like that he just gives up so it is in fact like you can show that that the commitment scheme satisfies the strong property and in fact what may be surprising is that it satisfies it with exactly the same bound as in The Binding

case so compared to binding extractability has exactly the same bound so while it it is a stronger property you don't actually need to pay anything more than that the random Oracle and the comment scheme already give you all of this properties for free okay questions on this Okay cool so I wanted to talk about this because it's important for for uh the PCP setting uh you can generalize this to multiple commitments uh you get a slightly worse error but it's not too bad like the dominating term is still

that of finding collisions in most in most instant settings and I'm just going to like very quickly talk about binding and about iding sorry so this is where we need the sols so the souls in the basic commitment are needed for The Binding property of the scheme so in particular in the iding game we're comparing to distribution so we have again a game in which the the the adversary so hiding in computer science

is always done via a simulator so this is an algorithm which this is an algorithm which will try to simulate a valid commitment so we will have two games one in one of them the adversary Cho the message and then gets a commitment to that message in the second casee the adversary is still out with the message but now the commitment is given by a simulator so the simulator just simulates the commitment without actually seeing the message and we say that the commitment is hiding if the

distance of the two distributions are closing statistical distance I don't want to talk too much about what this means but that basically means that not ver can distinguish the do distributions and turns out that you can that there is a Bound for this can I do it bigger yes I can do bigger there's a you can show that the the commit scheme satisfy the strong property and in fact is stfy both computational and statistical

I we present both because the computational bound is a bit tighter so the hiding is related to the size of the salt if you use computational binding you're able to use a smaller size of the salt compared to what you would have to do in the case of the statistical binding okay question on this before we move on Merle trees okay cool let me move to meracle trees now now so we've seen before that we have the the basic commitment schemes give you a commitment scheme by us in

the name and now we want to see in fact for like the the kind of protocol that we will be later seeing for Suess a commitment scheme is not enough what we'll actually be needing is a vector commitment scheme intuitively is because the future protocol that we're going to be seeing require they have oracles that imagine them as very long strings and then the verifier will be able to like query like just bits of these oracles so maybe see like The Fifth Element maybe the 26th element and so on so we want like the prover to be able to reveal bits of the string like parts of this long Oracle string but not anything

more the meral Tre is exactly something made for this and we Define is as a tup of free algorith so we will have a commitment an opening and a check recall that like in the in the normal commitment scheme the we only have 12 dreams in the miracle scheme we have three of them just because the opening will be non-trivial I think we have a diagram in next slide so I'll go to it but intuitively the flow will be that like the we will have some kind of like string then we commit

to into a root we'll see why it is called a root later on and then later on like say it also gives you some other information then there will be an open algorithm that allows you to open one particular thing so this will give me some kind of proof and then the the check will take the the root the indexes that are going to be querying that the values of let's call the string M for example M at the indexes and the proof to check the opening so will be so first we will commit and then we'll be able to open at

some location so let's see how this is done in practice this is just some notation for binary trees but this is do we have a better one I think they have a better one some okay so here will be how we will be doing the the commitment so in the mle threee what you end up having so in this case you have a message M which is of eight element I say there are bits for Simplicity but this can be anything so what you end up doing is you apply the basic commitment recurs so you first you apply it at the what is called the

the Le layer and then once you have uh you have that you apply it again so there's like Leaf commitments and this is call it the the inner nodes so what I'm doing at each step I'm applying the random Oracle to the results of the previous step and I'm merging them together for example yeah so this is the the the way in which a is done okay so we've why does this give us some benefit because the alternative imagine that now

you had this Vector m one other thing that we could have done to do a commitment will be just to do to as it all together with some salt this is just applying the basic commitment by the previous chapter we know is mining it's hiding it's got good properties why do we have to do other things and put a miracle to structure on if you're using at the basic commitment the kind of issue that you can not really you cannot really reveal a part of M while the merel tree will be able to help us with that so suppose that for example we're trying to like we were trying to reveal this no here so we're trying to

reveal this not here one natural strategy you might see is to end up like revealing What's called the Copa so for example I can reveal this value here I can reveal this value here and this value here if I reveal these values what I can end up doing I can just check okay look if I Ash so first I Ash these things and I get this value here when I Ash these two values I get this value now when I Ash these two values I get this value and now I can just check whether the value that I obtain by ashing these two values is equivalent to the root

so what I've done basically by just sending instead of sending the entire the entire values I'm sending just one value for each layer of the tree so the opening complexity is uh log l where L is the number of of element in the sorry in the Merkle tree that I've committed to okay question on the Merc tree construction I think this is used in a lot of other places you might have seen it like

uh in a in a bunch of other uh constructions but I think it's very good to have it here as well okay okay let's go and see what like the what the morle tree gives you so first of all how expensive is to commit it you at then what you end up doing in total is exactly two to queries to the ROM to the random Oracle so this is a linear amount of

queries in the number of element you're committing to for the verifier checking is also quite nice because checking actually only requires you to do one tw for each level of the tree so this is quite nice as well yes so they also have very nice properties you can practically you might also consider using other Rarities but in reality the B three case it's a very sweet Sports in term of trade-off because the using higher arties you can have

like lesser levels in the tree but then each opening needs to reveal actually more layers so in fact the binary case is basically optimal in terms of if you want to for example minimize the proof size if you want to do fewer call around the Oracle maybe your Rush function you're using is very expensive then you might want to consider it but often the binary case is the optimal one let's talk about the property that the Merkle tree end up satisfying first of all you have exactly the same property as in the as in the commitment scheme that is that of

binding only now binding is slightly different because now what we are asking so we are not interesting in we're also interested in binding of the entire scheme but we are interestedly mostly in binding of the parts are being open so now in my game what I will have I have the adversary is first output some root and then this will be like a root of some Merle tree then it's trying to find two different subset I and I prime where they disagree on some kind of overlap if it is able to find something

and they where the path still verify back to the root so if it is able to find some path which verify back to the root but on which like the values disagree on some point this is it wins the game so just let's see what this looks like in formally so the prover again now receive to the random Oracle and outputs a root and then he outputs two pair of openings so the pairs the triples opening sorry the triples contain both the answers the indexes and some authentification path and um the

prover the adversary wins if the like the triple that the outputs verify successfully with respect to like the with respect to the root and further there's some disagreement in the in the answers so there are some parts in which look the answers are some parts in this opening which the two answers do are not consistent with each other as in like the as like in the what's it called as in the commit scheme

turns out the is very much related to to the to the possibility of finding a collision in the in the random Oracle so in particular like roughly you get you end up getting something like t^ squ over two Sigma which is the probability of finding a collision in the random Oracle so this is roughly of course this is with some small condition on the dep of the tree which is the usually satisfied in practice Okay cool so we don't have much time so I'll say another few words on the the other property of the miracle

tree so as as as in the case of the commitment scheme Merle Tre also satisfies tractability which is defined in a very similar way so again you will have this kind of game which the struct the adversary first tries to Output some root then the stractor tries to extract the message committed to this route and then the adversary the adversary tries to produce an opening and the adversary wins if the if the message tracted disagree with the answers at the opening and the the miracle ification path

suceed the pro of this is very hard I had to go through it myself at one point and it was not very hard but it's quite verbose let's say but at the end what you end up concluding is that you actually also get an error which is roughly related to probability of finding collisions in the random Oracle so Merle trees satisfy this very strong notion of extractability and in fact it safy a stronger still notion in which the in which you are extracting multiple commitments which we do not have in the book but we have in our one of our recent papers but roughly here the cas which show actually

concern with um the case where the Merkle tree is used multiple times and you have to get struck from multiple commitment which might even have some shared like query to the random Oracle and the mle Tre is also satisfied is very strong property okay questions on the struction part okay cool then let me see what the

situation is in binding yes so there's okay there's some extensions but important Merle trees also are strong enough that they do not that they add the the message exactly the same notion as in the in the I beg your pardon in the Bic commitment and it intuitively makes sense look we have this mer trees are made of basic commitments if the basic commitment is hiding putting things

together should not reveal something formalizing this is a bit more complicated but you also see that both that you the message and also the authentification path do also do not reveal anything but but the part which are being open so overall this shows you that that the miracle commitment the the mirle commitment satisfies both Bing and iding property so let me see if I have anything that I want to cover in this no I think I think I'm done on this so I think we have five minutes left um I'm happy to take question otherwise I can like talk a bit more about other part of

the book which talk about Miracle commitments and practical optimization that can be interesting I would vote that you do a recap instead of covering more material okay cool let me then go at the very start we had done that the first time as well I completely forgot okay so what have we seen in this lecture so in this lecture we've seen like some of the building blocks it will be required to actually get a subed argument from new tools called pcps and iops these tools are commitment steams H we in this lecture we saw both like the basic commitment scheme from the random Oracle and then the Merle three

commitment which is a generalization of that which enables you to get a stronger functionality namely that of vector commitments so these roughly are like commitment but they're able to they enable you to suly reveal only a part of the message that you're committed to the we've recap was were like the Notions that we're interested to in a commitment scheme one of them is of course completeness while the others uh are binding extractability and hiding we've recapped how to construct these very natural like schemes in the random Oracle model so natural that in fact these are basically the only known commitments in the random in the pure

Rand oral model without any other assumptions in fact it is an open problem to figure out whether there are like like better improvements on these very simple techniques or give a lower bound if not but anyways I digress so we show that this natural construction they are both iding binding they have extractability properties and in the later lecture we will see how these end up playing a role in constructing some of the state-of-the-art sub arguments in particular for example all the stateof thee Art n using for example lre test such as fries war end up relying very heavily on the the Merle

commitment scheme so a nice understanding of it's properties will go a long way towards deploying secure and fast and scalable argument of scale so I think this is all that I have um um next in the next session which will be on the 14th of January D will be taking some time to talk over the the Kilian transformation which will be one of the first time we will actually be using these Miracle commitments in practice lovely thanks okay good then

have a good Christmas holiday