Security of Fiat-Shamir transformation by Michal Zajac | Devcon SEA

I'd like to introduce our speaker today. His name is Mihail. He's flown all the way from Poland about a 17-hour trip. So, why don't you give a round of applause to Mihail? [Applause] [Music] Does it work?

Okay, perfect. Yeah. Hello. Thanks for inviting me talking today. So, my talk is about the security of Fiat-Shamir transformation.

So, basically the security of the transformation that allows you to use all these SNARKs, STARKs on chain as non-interactive proof instead of having them like as a communication between prover and verifier. Okay. So, before we dive in, let's talk very briefly about zero-knowledge proofs. So, in in zero-knowledge proofs, we usually have these these two parties, prover and verifier. The the prover wants to convince the verifier about veracity of some some particular statement.

Formally, we we want to say that particular statement belongs to some predefined language, but we don't need to to go into such details now. So, prover has like two two inputs. One is the statement that it wants to to prove, and another is witness. So, so for example, um like when when you have uh um the statement could be like a circuit C executed on some input A evaluates to B, and witness could be like all the the values from from the circuit from very bottom to the top, and from right it should end with with B. Um So, in zero-knowledge proofs, we don't give the the verifier the the full knowledge of the circuit.

We only give the the statement the statement of the prover. This also comes from the fact that usually we can write statements in a much shorter way than than witnesses. So, from zero-knowledge proofs, we require basically three properties. The first one is completeness. So, we want to say that if both prover and verifier are honest, then prover will be able to to convince the the the verifier about the veracity of the statement.

Another, which I claim is like probably the most important one is soundness. So, so here we want to say that if the prover is is malicious and the statement is incorrect, then the probability that the verifier will accept such such statement is is negligible. Um the different flavor of soundness is knowledge soundness, and this is what we usually use. And this is like a stronger notion of soundness. So, here if if verifier accepts the proof, then we know that the prover knows the witness.

And finally, we have zero knowledge that we we really don't use in blockchain applications, at least for now. So, so here we we say that protocol is zero knowledge if if the verifier learns nothing about about the witness from from the from this communication with the with the prover. Okay. So, like let's talk about how SNARKs are built. So, sorry for for for this like very theoretical slide.

There will be few of them here. Um So, STARKs and SNARKs start as uh uh interactive proof between like this prover and verifier. So, we design our SNARKs as protocols where the prover sends some some polynomials to to to to like some imaginary party called called oracles. These polynomials, um for example, represent like very big computation. So, so these polynomials are are huge.

Um When these polynomials are sent, the verifier also replies with some some challenges um that also provides some information to the prover how these polynomials should be built. Eventually, the the verifier asks this oracle that got all these polynomials to evaluate these polynomials for them. So, it picks some evaluation point and gets the gets the evaluations. So, finally, that the proof is like the set of all these polynomials sent by by the prover along with all challenges that the verifier sent, evaluation point, and evaluation at the of the polynomials at evaluation point. So, there are a few problems with this approach, namely well, like all is like this imaginary party that really doesn't exist in real life.

And like since these polynomials represent all these computation, they are huge. So, we don't want that. So, we need to to make like a next step. So, for next step, we use something called polynomial commitments, which basically allowed the the prover to send like a short digest that represents the polynomial instead the whole polynomial. And importantly, the verifier can also can can also evaluate this this polynomial by sending like the evaluation point to the prover such that this evaluation can be verified.

So, so now we can replace our oracle just by using the polynomial commitments. Um and that also makes our proof um much shorter, right? Because instead of full polynomials, we send this this very short digest. So, now the communication looks like we have a prover that sends some polynomial commitments, and verifier that replies with with these random challenges, eventually replies with some evaluation point, and gets evaluation of the polynomials along with proofs that the evaluations have been computed correctly. So, now like okay, this is still not great because we we have this interaction between the prover and the verifier.

So, what we do is we introduce a random oracle. So, random oracle is like another imaginary entity that is is is a random function that on on input provides some some random answer. So, now this this function is used to to compute all the challenges that the verifier would compute itself. So, now the nice thing is that the prover doesn't need to uh to talk constantly with the verifier because it will send something called like partial transcript. So, it it computes this polynomial commitments, send them to to to the random oracle, gets a reply, includes the reply in the further computation, computes new polynomials, new polynomial commitments, sends them back and forth.

The random oracle back and forth. Finally, it is able to to produce like a single proof for that can be presented to the verifier. And similarly, the the verifier itself has access to this random oracle, so can produce the can produce the challenges on on its own. So, so now like the the proof is like all these polynomial commitments that that the prover sent they are like included in this proof along with with the challenges from from the random oracle, evaluations of the polynomials, and proofs for for the evaluation correctness. Yeah.

So, so the problem with random oracle is that well, it doesn't exist. So, what we usually do is like we say, "Okay, instead of random oracle, let's use hash function." So, now the question is like how secure is is such such protocol? So, now we are going to the core. Um So, the the thing with um the thing with using hash functions and like random oracle as well is that we change a bit the game that we are playing with the with the prover.

So, like the verifier now is in a bit different situation uh than it was before. Why is that? Because when we have like an interaction between the prover and verifier in the interactive proof, and the verifier realizes that that the prover is like incorrect, like tries to to to to claim something something in something wrong, or like some of the answers of the of the prover don't make sense, then it can always interrupt the the communication. So, we can think that the communication goes as long as prover makes a mistake, this malicious prover. However, um in the case when we have like a Fiat-Shamir transformation, the situation for malicious prover is much better.

Because now the prover, since it computes the uh it computes the challenges that verifier sends on its own, he can uh predict like, I mean, by doing computation, he can see whether he can answer these challenges or not. And if he uh sees like a challenge that he cannot answer, he can just rewind the computation, right? To the very beginning, uh try to send like a different polynomials, and can try locally compute a proof that that would fit it. Uh so so here we have uh a notion of of a lucky set. So, basically we can say that some of the challenges that um that the verifier sends may be particularly good for a malicious malicious prover.

Mm. So, maybe for uh for for for those who are uh interested in in math, um I can add that we usually want to have some polynomials to be equal each other. So, I I had an example like a few slides back. Let me go here. Here we have this m1x * m2x = m3x, okay?

Uh as I mentioned like these polynomials are huge, we don't want to sell send them. On the other hand, we can verify the statement by evaluating the polynomial at random point. Why is that? Because like the probability that the um uh that this this later later equation holds when the first line doesn't is like really negligible. Uh and it depends on the degree of the polynomial and the the the size of of the field.

Mm. Let me get back here. Yeah. And and here we have a also like similar situation, right? If the the malicious prover is lucky, and it uh comes to to a challenge z, this evaluation challenge z, such that, well, even though these polynomials are not equal each other, uh but they are equal on on z, then um then yeah, that's that's a very good situation for the prover.

Uh and with a non-interactive proofs, the the the the the prover can just like try multiple times. Right? If we have like a interactive proof, then um when well, when if I would talk with a verifier that constantly gives me like a some bad answers, I would just interrupt connection. Okay. So, how how to compare the the security uh of of interactive and non-interactive proofs.

So, now um we need to to say, okay, so uh our starting point is like saying, what's the probability that an interactive protocol would be broken? And this is uh say some probability some probability alpha, okay? Uh then uh we we check like the probability that one of the answers from from the random oracle, from the hash function, will be uh from from this lucky set where where the prover can provide uh a good proof for for a false statement. Uh finally, we need to include the computational power of the of the malicious prover, right? Because if the prover is like more powerful, then it can include like much more uh they can do like much more trials.

Mm. Not going into the formulas, uh but let me let me only say that that the the security of uh the the security loss of Fiat-Shamir transformation is roughly like this eta * q. So so the the probability uh that the adversary gets a challenge from a lucky set uh times times the the the power of the of the adversary. Okay, so how how does it affect security? So, let's assume that our starting point for the interactive protocol is like uh 2 to the minus 100, right?

So so we calculated that uh an adversary in the interactive protocol who wants to to to break the protocol has probability 2 to the minus 100 um of of doing so. Um and like what what what is the realistic q? It's it depends on the adversary, right? But if you want to be uh relatively uh pessimistic, um I would say, okay, let's see like what's the computational power of we have like right now, like uh here I looked at uh Bitcoin network, but it's like it's a bit outdated data, but like uh you know, like the computational power of world like uh grows like immensely because of all the uh of this AI-related things, uh also like Bitcoin at $100,000 as well. Uh so so the this computational power is like pretty pretty pretty amazing.

And the result we have is that we have like roughly like 2 to the 85 hashes per day. That's how much we can compute. What does it mean? It means that um it means that the the the probability that this network breaks uh the uh breaks the security is is no longer like the 2 to the minus 100 is 2 to the minus 15. So, um if it's like big or or small, I would say it's like the probability is relatively big.

Especially that the compute grows, and you don't want to to change the parameters of the proof system all the time. Okay. So, one thing that is um often used in the modern SNARKs are small fields. So, in small fields, uh the challenges from the verifier come from like very small uh set that also makes uh the uh that also makes the the the the prover uh much more capable of of guessing the guessing the challenge or um being lucky in in having like a good challenge. And there are basically two ways of dealing with this problem.

So, first of all, what um uh I I I hope all protocols are doing is that they don't pull the challenges from from these small fields, but use some field extensions. But now I would like to talk about uh parallel repetition, because this is also like technique that uh works very nicely in interactive proofs, but is totally insecure in terms of non-interactive proofs. So, parallel repetition basically says, okay, I am as a prover will uh so the prover and verifier run two verification protocols in parallel. So, there are like two copies of the prover, two copies of the verifier. For the prover to accept the proof, both uh both executions need to be correct.

Both executions needs to be acceptable. And when we have interactive proof systems, that gives us like super nice property, because like the the probability uh here like denoted by epsilon 2, that that the verifier breaks both uh both executions is like, yeah, epsilon squared. So so it's like we had like, I don't know, 2 to the minus 32, another 2 to the minus 32, it's 2 to the minus 64. But for Fiat-Shamir transformation, this this parallel repetition uh doesn't work at all. So so the thing is that uh yeah, I don't have time to to go into details, unfortunately.

So, um but we I'm very happy to talk about this uh later. Um so so the the the main point is that the the adversary can can partially solve like one transcript, and partially solve like another transcript. So, the more uh parallel repetitions we have, then the worse this security loss it becomes. Mm. Okay.

So, and there's more about Fiat-Shamir transformation. So, uh it's easy to implement it incorrectly, so that many attacks shows that. Uh so there's like was a big uh big problem with uh uh with Plonk uh because like some some some teams didn't implement that the final final hashing that was discovered by trail of bits. And also yeah, like it's it's very important like when we have like a Fiat Shamir not to deviate from protocol description. So like the the message I want to say in this talk is that yeah, we need to use Fiat Shamir transformation.

But we need to be aware that it comes with some security losses and there's a cost that that we need to pay. So we cannot be too uh too aggressive on our param security parameters that we pick and we need to pick them wisely. Thank you, Mihai. Thank you so much. You can never be too careful.

You can never be too sure. Um everyone round of applause for Mihai, please. That was a lot, sir. Thank you very much. So uh we have a couple minutes for questions now.

Uh I'm going to point your attention to the screen here, this QR code. So if you have questions for Mihai, uh just scan the QR code. It'll uh open up the Meerkat app and you can start uh plugging your questions in there. Um the questions will appear on my mobile and uh I will probably just read the questions to Mihai if that's okay with you. And uh he'll feel happy to answer it.

Yeah. Oh, I see. I see. Okay. Okay.

Go for it. Uh so why parallel repetition for fails? Um So the thing is that when you we have like multiple copies of the protocol uh parallel repetition says that we need to be successful in each of them, right? When we have Fiat Shamir transformation and we have this lucky set um so let let let me uh repeat what what lucky set is. Like lucky set is like the um it's a set of challenges such that if the verifier gets a challenge for from that particular set then uh the the verifier is like off the hook.

So he can compute the rest of the proof such that it will be um it will be accepted by the prover. So the problem with that is that the the the prover can in parallel repetition can like focus on the first transcript try to get into the lucky set, okay, which it will come with some probability because like as as we assume that the uh fields are small, the field the space of challenges is small. And then like say save the state, okay? So the the prover knows that in the in the first track it was successful. Then he can focus on other on other tracks on other uh executions and do the same trick.

So like um So so the thing is that uh when the the prover is say successful in the first execution, he doesn't need to prove he doesn't need to care about this execution anymore. He can go to the other um and um and this uh this when when we analyze the the probability of the adversary successful in turns out that the the the security is like much much worse when compared to this epsilon squared. I'm happy to like discuss in more details later. Which concrete property should a concrete hash function satisfy? Um So the thing is that uh as cryptographers define hash function you know like we need this this um this the collision resistance.

This is basically the the property. However, we know that there are hash functions that have this property of collision resistance but uh but are insecure when we try to instantiate like hash function with that. So so the the thing is that um and there is analysis, but all these hash functions that are insecure for Fiat Shamir are like some um not natural examples. They are not like SHA or Keccak or something. They are like uh hash functions that uh were designed to be like insecure for Fiat Shamir.

I don't recall correctly like what's the property uh of of the hash function that it need to have to to be um useful for Fiat Shamir transformation, um but if you take a any reasonable uh hash function, it should be good. Uh verifier challenge selection on small fields pulling from extensions. Yes. So uh so so if think like uh I don't know, Mersenne prime field, it has like roughly like 2 to the 32 elements. So this is like a very small field.

Um so instead of of using this as a challenge you you take a challenge being a polynomial the of uh of degree one um over like this say F squared like where the F is the um with where F is this this this Mersenne prime, right? So so you don't take uh you don't take like a single element, but you take like a pair of elements or a triples of of elements. One more question. Yeah, uh one more. Uh I think I answered all.

I probably not. Um Uh sorry, maybe there's something like in below, but I don't see it. Uh ah, sigma protocol. Um Okay, I I will need some time to process it, I think. Coming challenge for You have a maybe a minute.

Okay, so so sorry, let let me take this offline. Um maybe like I will be able to quickly answer the quantum security. Fiat like quantum security and Fiat Shamir transformation is are orthogonal problems. Uh