ZK Fundamentals: The Fiat-Shamir Transform

Today we explore interactive ZK proofs without interaction

This is the fourth article from our series exploring ZK fundamentals, zero knowledge proofs and related notions.

ZK Fundamental series:
📚 Part I: What is a proof?
📚 Part II: Interactive Proofs
📚 Part III: Zero-Knowledge
📚 Part IV: The Fiat-Shamir Transform
📚 Part V: Succinctness
📚 Part VI: Intermediate representations

In the previous articles of this series we formalized the notion of a proof and saw the power of interaction.

Interaction bundled with randomness provides a powerful new proof system and it was a delight to see how easy and natural some statements like for instance graph non-isomorphism can be proven in this new setup.

It seems reasonable and is conjectured that the class of problems having an interactive proof (this class was denoted by IP) is substantially larger than the ones having only an interactive proof.

Then, in an interactive setup, we introduced the notion of zero-knowledge, a concept that seems so counterintuitive and out of this world that one would think it should not be possible. We can engage in an interaction and prove a statement to someone without conveying anything but the statement’s validity.

In all of these interaction was a key component and the proof was only convincing to the interacting party. Remember the example of the prover claiming to be able to distinguish regular coffee from decaf coffee from Part II of this series? The prover with eyes closed is repeatedly handed either regular or decaf coffee at random by the verifier and has to make his best guess. If he can guess right at each instance, the verifier would be convinced that the prover can really distinguish the two. If he couldn’t, then at each guess he had only a 1/2 chance of guessing rightly and repeating several times, the probability of the prover being right in all of them would become microscopically small. But the proof will only be convincing to the interacting verifier who decides (maybe by flipping a coin) to hand regular/decaf coffee at each trial. It would for instance not be convincing for another party, who will just watch this interaction. After all, a colluding malicious prover and verifier could have just agreed on a sequence of regular/decaf coffees to be handed beforehand and could just be putting up an act.

In some applications such an interaction might not be possible or even not be desirable. Concurrency between the prover and verifier might be difficult to achieve.

Moreover, there might be several verifiers that we want to provide convincing proof for, who might be in different geographic locations, or the proofs might be requested at different times. So we would like to create proofs without interaction, that can just be posted and read by at any time by any verifier who wants to be convinced of the truth of the statement.

This is particularly important in decentralized systems like blockchains, with many distributed nodes each verifying a statement (e.g. validity of transactions) independently.

In short, interactive proofs only convince the interacting party, but we want to render the proof non-interactive and publicly verifiable. How to achieve this? Read on to find out.

Isn’t that just where we started?

You might be saying “Wait a moment! No interaction? Is this not our good old friend, the static proof, which we ditched for all this fancy interaction and now you want to just go back to it? Why didn’t we just stick with NP in the first place?”.

The short answer is “it’s complicated!”. Let’s explain in detail, one step at a time!

OMG so many acronyms: P, NP, BPP, MA, AM… ASL?

Without interaction and randomness we clearly fall back to NP. With a “non-interactive interactive proof”, i.e. if we allow the verifier to use randomness and accept false proofs with some probability, but have no interaction, most likely nothing is gained either. This class is known as Merlin-Arthur (MA) and is conjectured to be not any larger than NP.

Even more is true: if we want the zero-knowledge feature, little interaction does not help either. Oded Goldreich and Yair Oren (Definitions and Properties of Zero-Knowledge Proof Systems) have proven a series of impossibility results.

If there is only one message sent by the prover, in a zero-knowledge proof we land in the class BPP (bounded-error probabilistic polynomial time), which is contained in MA and is just P where we add the possibility of making an error with a bounded probability. The class of problems in BPP not known to be in P is decreasing steadily (most prominently PRIMES) and it is believed that BPP = P.

Furthermore, if we have a total of two messages interchanged (one from the verifier to the prover and one back), then under a somewhat more restricted notion of zero-knowledge (which however is more suitable for cryptographic applications), we still are in BPP. So for zero-knowledge proofs even some restricted interaction most likely does not help.

There are a plethora of results on the number of rounds of interaction (a.k.a. round complexity) required for a ZK proof for problems in various complexity classes, for various notions of zero-knowledge and under various assumptions (existence of one-way functions, collision-resistant hash functions).

Despite all the impossibility results not everything is lost (otherwise this would be a quite short article). As a first step let’s see how we can weaken the requirement of interaction or what to replace it by, rather than hoping to abolish it totally.

Common Random String

Blum-Feldman-Micali have shown that if the prover and verifier share a common random string, computational zero-knowledge is possible, without the need for interaction. In some sense this is a weakening of interaction, as through interaction they could agree on a common random string, but not the other way around.

Arthur-Merlin Proofs

Rather than cutting out interaction altogether (so only the prover communicates a message), we can put restrictions on what is communicated during the interaction by the verifier.

Remember the two instances of interactive proofs mentioned earlier of graph isomorphism (GI) and graph non-isomorphism (GNI).

For GI the prover wanted to convince the verifier that two given graphs G₀ and G₁are isomorphic. For this he choses a permutation of one of the graphs and the verifier flipps a coin and asking the prover to exhibit an isomorphism to G₀ or G₁ accordingly.

For GNI, the verifier randomly chooses one of G₀ or G₁ and challenges the prover to decide which one it was.

There is an important difference between these two: in the first one the verifier reveals all of his random choices (coin flips), in the second one something is computed from the random choice (a permutation of the according graph), which is shared with the prover, however the random choice is kept secret (finding the random choice constitutes exactly the challenge of the prover).

These are called public coin/private coin protocols accordingly. Though it seems like private coin protocols are more powerful, a surprising result of Goldwasser-Sipser shows in fact they are not: whatever you can prove interactively with private coins, you can also prove in a protocol relying only on public coins (possibly at the expense of increasing the number of rounds). So when we talk about interaction, all we need from the verifier is in fact to toss coins and send them as challenges to the prover. Let’s show the beautiful idea in the case of GNI. The rough idea is as follows: assume the graphs have n vertices each. Forgetting for a moment about automorphisms of graphs, we see that in case the graphs are not isomorphic there are 2 • n! graphs isomorphic to G₀ or to G₁, which however collapse to n! many graphs in case G₀ and G₁ are isomorphic.

So a random graph would have a higher chance of being isomorphic to one of the two in case they are not isomorphic. This gap in the probabilities can be exploited. The verifier can repeatedly choose random graphs and ask the prover to exhibit isomorphisms to either one of the graphs whenever this is the case. By computing the proportion the verifier can estimate the probability and decide which situation is more likely to be the case (remember that we allow the verifier to make some mistakes).

The Fiat-Shamir Transform

For a public coin protocol, the input of the verifier is only minimal (random messages) but crucial. The critical aspect is that they cannot be foreseen by the prover, no matter how powerful he is.

Only after the prover sends a message can he obtain the response. We cannot leave the task of choosing the random challenge to the prover, as he is untrusted. To create random challenges that are unpredictable and not available before the previous message has been sent by the prover, we imagine an abstract construct, called a random oracle.

A random oracle is a function taking inputs and providing outputs. We want the function to look like a randomly chosen function, without any apparent structure. It should be a function, i.e. it should provide the same output for the same input (so it is not just spitting out random output), but the output on given input should be unpredictable before the oracle has been queried with the given input.

Basically for each input that has not been queried before, the oracle should choose an output uniformly at random, remember the input output pair, and respond with the same output should it be queried with the same input. Given access to such a random oracle, we can substitute it for the random challenges provided by the verifier in a public coin interactive protocol.

When running an interactive protocol on input x, rather than waiting for the i-th challenge from the verifier, the prover feeds x and all previous messages to a random oracle and uses the output of the random oracle as random challenge. The outcome is random, and is unpredictable before the prover settles on the message to send to the verifier. One can show that if the initial interactive public coin proof is sound, one obtains a sound non-interactive proof. This was introduced in the paper “How to Prove Yourself: Practical Solutions to Identification and Signature Problems” and is called the Fiat-Shamir Transformation, named after its inventors.

A contradiction?

So through the Fiat-Shamir transform, or using a common random string à la Blum — Feldman — Micali, we can obtain non-interactive zero-knowledge proofs.

You might be wondering if these do not contradict the impossibility result of Goldreich-Oren. The answer is no. These are all part of different computational models.

Goldreich-Oren is a result in the standard model (also known as the plain model), where proofs are given based only on complexity assumption (the difficulty of certain operations like discrete logarithms, factorization etc.). Here we do not have the notion of a common reference string or a random oracle. Computational models where there are made available are known as the Common Reference String Model and the Random Oracle Model, respectively. And different things are possible in different computational models.

Random Oracles in Real Life

Unfortunately random oracles are not practically realizable. They are an abstraction of an idealized hash function. What is done in practice (known as the random oracle methodology) is to do all security proofs under the assumption that a random oracle does exist (in the random oracle model), and then replace the random oracles by your favorite hash function (queries to the oracle are given by hash function evaluations).

If the used hash function has good properties (collision resistance, preimage resistance, etc.) it is assumed that the resulting interactive scheme is secure in the standard model.

There is however no proof for its security, it is more like a heuristic. Hence one usually talks about the Fiat-Shamir heuristic: render a public coin proof non-interactive using a random oracle and provide a security proof in the random oracle model. Afterwards replace the random oracle by a hash function. Heuristically the resulting scheme should be secure.

This is a very fine line, and one has to be very careful when threading it. Let us just mention a result by Goldwasser and Tauman Kalai, that shows that there are interactive proofs, which become unsound no matter which hash function we use to replace the random oracle.

After seeing the importance of interaction, we have now seen how and at which price we can keep its benefits, while avoiding interaction itself. Until our next article you can now go ahead and create your most favorite proofs, all by yourself!

Want to learn more about this? Follow us:

Twitter | Lens Protocol | LinkedIn | Github | Request Audit