ZK10: A new Fiat-Shamir library for the masses - Michele Orrù

Transcript

foreign [Music] talking us about the library targets to facilitating the future transformation hello yeah thank you so much for the introduction and even before starting I would like to say that this work is actually not only mine but it has been the collaboration of a series of talks for over one year with the Dimitri from ethereum Foundation Trevor that was working with signal but also from Francois Nicola monblatt and JP Amazon so it's only the credit is not only mine for this we're going to be talking about

via Shamir um you it's a transformation it's a neuristic that allows us to take a public link protocol what does it mean for a protocol to be public coin it means that is interactive so there is a prover and the verifier they are talking to each other and the verifier is only sending random challenges and at the end is checking what we call a verification equation to make sure that everything is correct and we take this public coin protocol so again interactive with random challenges and we'll transform into a non-interactive argument through something that we call random Oracle and as long as you believe that the random Oracle exists and then you will end up with a with a valid non-interactive proof there are several advantages why you want in practice to use the fiesta

Mir transform mostly that it kills all communication so you have no latency and especially in blockchain applications you sometimes you don't even know who you're talking to um it gives you zero knowledge so adversarially um other set of verifiers I would be covered in this case and finally it will be publicly verifiable so there's a ton of advantages for using the fiesta mirror transform however is also a source of vulnerabilities and historically we've had tons of of works that have been Illustrated this we have now a rate I think of uh one paper every five years that rediscovers uh faults in modern systems and the the bottom line of this talk is maybe there is a Monumental model that allows us to avoid some of these bugs

some of these bugs historically just to give you an overview have been on the xenology part and some on the soundness part and you know if you if you start having problems on both then there there is a high risk that uh that it will cover like really important properties of your system um the one thing that breaks always zero knowledge is um has been happening for the PS3 when Sony was signing their games was that you have had approver they were sending two messages but we we you could we were able to produce two different challenges and if this happens actually you're able to recover the full witness and in the case of Sony they

were able to recover the secret key for signing games which was uh which was pretty bad um on the soundness part instead is more the bugs that are up and the most time is that the the way that we do the future transform does not provide enough context to the hash we do not hash enough elements and um the just uh like this has been discovered for Helios there has been this Frozen bleed attack more recently it was found on Swiss posts there has been a long history of softwares that just did not put enough elements in their fiesta mirror transform and this led to attacks um just to be clear the the thing that when you're doing a zero knowledge prove the thing that you want to put into your

hash um into your Fiesta mirror transform comprehends the statement so whatever public input you're putting whatever relation you're proving as well as the public parameters and when I talk about traffic parameters I mean the generators of the elliptic curves this was about found in Helios when they were able to prove under different generators the discrete log of an element they actually did not know the discrete log of and the curve identifier so these are more difficult to find in the wild but there is this uh invalid curve attacks where if you're able to select the curve for another person uh there are the formulas for scalar multiplication do not depend on all the parameters of the elliptic curve do not depend for instance on the inhomogeneous term so you want to make sure that it's there in case your adversary is able also to convince you

to use another elliptic curve and all these things are very much neglected in papers and uh you know just to give an example and to blame myself for this this is one of my papers and uh you know we just say we sample is a random challenge we never say whatever the verifier is really using and so the help of this talk is to maybe like guide you how do you go from there from the actual to the actual implementation um what we discovered over the years and what I think is the golden standard for like how to um use Fiesta Mir is to use a construction called a duplex sponge so it's a sponge function so it's going to behave um with a sequence of calls of absorbing and squeezing where we're going to feed

it with inputs and we're going to get challenges out and uh I think the right mental model to have that was actually introduced um by by Henry the valance in a previous Library called Merlin was to have a transcript context so you have an object that is carrying out the state of the hash function throughout the world protocol and then you're going to fit it with more data and you're going to get challenges from it and in fact for keeping this transaction context over over the last I would say 10 years there has been at least two big approaches one has been two um dynamically embed all the information you have to the transcript so um whenever you are sending a vector to the verifier you also know

um you have to embed also the length and everything is decided at runtime as soon as you absorb an element you have to specify how to separate the elements from each other and this is what is done in a library called Merlin that was uh used a very very much popular and now I think is a bit unmountained and um this is based on the straw protocol framework from Mike Hamburg that really tells you how you should embed public and private elements in the wire Etc and there is another way which is um static so in specifically in zero knowledge proof because you know very much the length of the elements that you're going to send throughout the protocol you can commit to them at the beginning and then um work work them out in the in during

the protocol you don't need to to specify separations because this is already done at the beginning and this is what I want to talk about with this new library that I've been developing called Nimo and it is based on the top of the save framework and um the basic idea behind the safe framework at least for what I was able to learn is that you want to commit to the entire message flow at the beginning so when you start the hash function you will put this bunch of elements that are encoding the message flow and I will explain in a second and after that it's only concatenation you just have to concaten ID element because you're already committed to the world protocol length to the world protocol flow at the

beginning you put the domain separator so the website where you are at and this is really important otherwise you're going to having you might end up having proofs that can be used across different protocols and that might be a problem you want to signal that you are going to absorb a new element so that's a you're going to write the length 32 bytes and then this element might be the generator you want to do the same for the public key this might be a short signature for instance um R is ratcheting I will go over that there in a second but then same you want to absorb another element you want to squeeze a challenge you want to observe a response you harsh all this you end up with a fixed size element and then you initialize a function and you just concatenate from there so what is the

advantage of committing to this world protocol at the beginning is um that we are able to support many more Rush functions whereas uh with things like Merlin or strobe you we were really bound to sponge functions um in this case where we're not bound to strobe which is a byte oriented interface we can for instance support algebraic hashing rather easily and all these parts about committing to the message flow is done outside of the circuit which is really advantageous because it gains you also a lot of uh um it removes a lot of Burden from the actual proof system where you would have to add inputs in the middle and another thing that I think is pretty sweet about this uh model it allows you

for static composition um when you have to commit at the beginning to how the protocol will look like there is less risk that in the middle of the protocol later you will invoke the wrong sub protocol or that you will decide a runtime as an implementer or I might use this part of the proof or this other the proof uh depending on an extra parameter so um you must know what they're about to prove before starting the wallproof protocol and I think overall this allows you to also have more control with operation that are not necessarily supported when you're doing um when you're using other Frameworks like strobe one of them that I really want that I think is important and that we add actually on the top of the save framework is ratcheting so

um whenever because you're keeping the state object throughout the protocol and this proof system I also take a long time um you might want to avoid storing any sensitive avoid recovery of private information even from there from this state and one way to do so is through ratcheting so invoke the permutation function you clear clear the rate and it's very difficult to go back to the previous state from there and this is useful for pre-processing because at this point you have the rate that is completely free and you can start a proof system from there but as well if you for instance before when we were absorbing also the the public key no information about the public key is going to be kept after a ratchet so the generator and the public key will be the statement ratchet no information about

what they were restored and then I can continue from there um interesting um yeah so um in order to um since this is also part of the GK proof standardization effort and we want to develop a spec that makes sense um I started developing a new library for it where that you can check out and I will put a link at the end of the talk um and I guess the one of the things that uh where we are maybe diverging from past works is that I think we need

to include a little bit extra batteries into this um for instance we went as far as also supporting previous as far as functions like Blake 2 or Chateau we have an entire support in Rust for libraries that just satisfy the digest uh trait so what does this mean is man it means that you can do fzmir with Chateau if that's a constraint that you need to care that you need to keep or Blake to which is what happens for instance in lo2 ETC and another thing that we want to start thinking is uh how do you serialize points and scalars because um well this is super important for Interval operability uh because we've seen that different people might encode points differently and right now I I

have something that is compatible at least between dialect and artworks I want to go as far as supporting also DK cryptos Library and um and it has less bugs um for instance it's um it might be really difficult for an implementer to know should you encode should you absorb a projective point or should you absorb on a fine point and it turns out that there are bugs depending on which one you choose or for instance whenever you are squeezing out an element from um an element modulo P this is going to be random modulo P by the guarantees of the sponge function but it's not clear that it will be still uniformly distributed if you take a certain number of bits of them it's not clear that it's uniformly distributed

modulo 2 to the end so all these things I think need to be handled by a library and that's what I'm trying to take care of and that's what we are developing at Nimoy and so um the library looks something like this it has this nice interface where you don't really have to count how many bytes occupy the scalar um you can make it aware of the group that you're using and then you will put all the elements on the i o pattern and uh this is what uh the answer will be we're using instead of space null separated bytes it's pretty much how much does it take to build an IO pattern that is valid and um keeping in mind this idea of also uh preventing bugs and having something

that is more interoperable we have also traits that might help the provers so whenever the prover wants to generate some Randomness we provide you with a secure random number generator that is also bound to the transcript of the proof so that that problem that we saw before of you get two different challenges for the same message from the prover that will never happen because also the transcript is also bound to the protocol transcript finally uh we have a byte oriented transcript so whenever the prover is absorbing an element it will be also kept into um a write interface and into into a vector of of bytes that at the end you can just output as the proof so serialization is all done by this environment and it

really corresponds to whatever approver has been sending throughout the protocol you don't have to worry about whether you included more elements or less and um and so just to show you how this is done uh this is National proof so you want to get a challenge you want to multiply you absorb it you want to get a challenge you compute the response you absorb it and then you just return the transcript out of it and this is already serialized and you know that whatever was done for squeezing the scalars is also what is uh what will end up on the other side for generating this transcript because it's handled by the same object and um just as a like an idea this is how like just to give you an idea this is how the verifier is done you will get the next

point from the transcript you will squeeze a new challenge and then check the verification equation so yeah I this is pretty much it I'm very happy to go into more details about this uh this is the GitHub repo I would really appreciate more eyes to look into this and also more help there are a bunch of easy issues that we can all take care of um if we work together so yeah uh thank you very much Miguel that was great uh we do have time for a few questions and answer so yeah please raise the hand if you have any

come on anyone that's okay so in case you are in like folding environments or stuff like that where you might need to hash points that are not in the native curve so you need basically raw bytes in order to fit into the transcript do you provide some kind of API also to do that um I started to think about this and it really depends on the different orders of the curve generally when you're absorbed when so yes I started to think about this um I'm working on like adding it to the library but uh I think we agreed on a way in which this can be done securely and we're just uh it really depends on the orders of the points and the hash

function so because if if the ash function is uh over elements that are bigger than the inputs then you can just absorb them naturally but if it's smaller then you need to make sure that you split them correctly but they also need to split in a way that is smart for a xenology proof to then treat so do you have any kind of insight on how this way of splitting looks like or um I think you just do modular Division and then you take the reminder but that seems the right way unless you're using a normal hash function over bytes in which case you probably want to split that true to the end and absorbing is not the problem I think the the big problem is uh is squeezing because when

you squeeze you have different distribution and in places like artworks or Nova when we squeeze elements and we would just want bytes um oftentimes we just need they just take 16 bytes but if you want more you will end up consuming up to modulus -1 and these last few bits are not uniformly random I'm not sure there is an actual attack on it but on the safe side it's better to to cut it a little bit beforehand and this really depends on the prime that you're using yes for the squeezing Parts I will give a link in my slides to be next that provides you exact rules how you kind of split and take modulus and so

any other question anyone yes for the um verify transcript would you be able to use nimu in solidity right now or is it only rust based it's only rust based right now but I'm I think that he has are settled now it would be yeah I don't know if there is any solidity developer that is curious about uh these and wants to write a framework on it or help me with that I would be really happy to to guide them through yeah oops thank you you said that you are

supporting uh more standards and all the hash functions that such as blig2 are you also supporting more recent ones such as position CQ animoi right so the framework is there um while I was testing I was able to do so um I think um the big the big gap that is there is there is that things like anemoy implementation I will just say is uh like there are very a lot of different parameters and it's unclear whether I should bring like all these a bunch of folders into the project or I should make a wrapper on it the way that we develop is just that is really that we need just a permutation function tell me the rate and the capacity and then everything is taken care of

um but this Library don't provide just simply the permutation function they often do a little bit more specifically for implementation of Poseidon in artworks uh what they have is the parameters are decided at runtime which I do not necessarily want um so you have a field and then like from the field like you need to decide something runtime whereas yeah I would like to have different a set of different parameters that uh that are decided uh before a compile time and so um despite artworks is very happy to bring all of these into their into the crypto Primitives part it seems that it requires also a little bit of a change into into Poseidon so I was able to do it with a little experiments is not right now in the library which by the

way is like cargo ad Nimo and then and then you have it and you can play it with it thank you any other question okay great well thank you again Miguel that was great Round of Applause please thank you thank you thanks