Security of Fiat-Shamir transformation

I'd like to introduce our speaker today. His name is Michal. He's flown all the way from Poland, about a 17-hour trip. So why don't you give a round of applause to Michal. How many pieces do you have?

There's five. Does it work? Okay, perfect. Hello, thanks for inviting me to talk 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 as a communication between prover and verifier. Okay, so before we dive in, let's talk very briefly about zero-knowledge proofs. So in zero-knowledge proofs, we usually have these two parties, prover and verifier. The prover wants to convince the verifier about veracity of some particular statement. Formally, we want to say that particular statement belongs to some predefined language, but we don't need to go into such details now.

So prover has two inputs. One is the statement that it wants to prove, and another is witness. So for example, when you have... The statement could be like a circuit C executed on some input A evaluates to B, and witness could be like all the values from this circuit from very bottom to the top, and, right, it should end with B. So in zero knowledge proofs we don't give the verifier that the full knowledge of the circuit we only give 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 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 convince the verifier about the veracity of the statement. Another which I claim is like probably the most important one is soundness.

So here we want to say that if the prover is malicious and the statement is incorrect, then the probability that the verifier will accept such statement is negligible. 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 verifier accepts the proof, then we know that the prover knows the witness. And finally we have zero knowledge that we really don't use in blockchain applications, at least for now.

So here we say that protocol is zero knowledge if the verifier learns nothing about the witness from this communication with the prover. Okay, so let's talk about how snarks are built. So sorry for this very theoretical slide. There will be few of them here. So, Starks and Snarks start as interactive proof between this prover and verifier.

So we design our Snarks as protocols where the prover sends some polynomials to some imaginary particle called oracles. These polynomials, for example, represent very big computations. So these polynomials are huge. When these polynomials are sent, the verifier also replies with some challenges that also provide some information to the prover how these polynomials should be built. Eventually, 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 evaluations. So finally, the proof is like the set of all these polynomials sent by the prover, along with all challenges that the verifier sent, evaluation point, and evaluation of the polynomials at the evaluation point. So there are a few problems with this approach. O is like this imaginary party that really doesn't exist in real life. And since these polynomials represent all this computation, they are huge.

So we don't want that. So we need to make a next step. So for next step, we use something called polynomial commitments, which basically allow the prover to send like a short digest that represents the polynomial instead the whole polynomial. And importantly, the verifier can also evaluate this polynomial by sending like the evaluation points to the prover such that this evaluation can be verified. So now we can replace our oracle just by using the polynomial commitments and that also makes our proof much shorter, right, Because instead of full polynomials, we send this very short digest.

So now the communication looks like we have a prover that sends some.