By Jim Miller, Senior Cryptography Analyst

Zero-knowledge (ZK) proofs are gaining popularity, and exciting new applications for this technology are emerging, particularly in the blockchain space. So we’d like to shine a spotlight on an interesting source of implementation bugs that we’ve seen—the Fiat Shamir transformation.

A ZK proof can be either interactive, where the prover and verifier communicate via challenges in a multi-step process, or non-interactive, where a prover computes a proof once and sends it to the verifier. The non-interactive ZK proof is preferred over the multi-step interactive process, but most ZK schemes are interactive by default.

Enter the Fiat-Shamir transformation. It transforms interactive ZK proofs into non-interactive ones. Easier said than done. This can be a tricky implementation and has led to several bugs, including one discovered in a Swiss voting system.

Here, we will use a tennis analogy to walk you through what this transformation is, and then we’ll show some examples of how it goes wrong in practice.

ZK Crash Course

Zero-knowledge proofs allow you (the prover) to prove to another party (the verifier) that you know some secret value without having to reveal the value itself. This concept can be applied in a variety of ways. For example, you give the verifier some value y, and you can prove that you possess an input value x such that y = sha256(x), without having to reveal x.

Or, as we’ve seen in the blockchain space, you want to spend some money without revealing how much you are spending, and ZK proofs can prove to the verifier that you possess enough money to spend without revealing how much you have or spent.

Now let’s talk about what security looks like for ZK proofs. They have a security notion known as soundness, which has a formal and well-defined technical definition. Simply put, a ZK proof is sound if a malicious prover can’t create fake proofs that appear to be valid. In other words, the verifier can’t be tricked with a bad proof.

Tennis analogy

Let’s visualize ZK proofs and the Fiat-Shamir transformation with a tennis analogy. The prover and verifier are tennis players standing opposite sides of the net. The prover is trying to prove to the verifier that they are good at tennis. (“Good” is used here in a very basic sense and specific to this example.)

(1) The prover hits the ball to the verifier, and (2) the verifier sends a random return back to the prover—random speed, location, amount of spin, etc.—and (3) the prover must return the ball to a targeted spot on the court. If the prover hits the target, the verifier classifies them as a good tennis player. If they do not hit the mark, they are classified as a bad tennis player.

In ZK terms, being classified as “good at tennis” corresponds to the verifier accepting the ZK proof as valid. Being classified as “bad at tennis” corresponds to the verifier rejecting the proof as invalid.

Now assume that this tennis game is a sound ZK scheme. Recalling our definition earlier, this means that a bad tennis player cannot convince the verifier they are good. If the prover is actually bad, they are unable to hit the tennis ball into the target. However, and this is important, this game is sound only if the verifier sends the tennis ball back in a truly random way.

Imagine the prover realizes that the verifier sends the tennis ball to the same spot and same location every time. Maybe the verifier is bad at tennis but only practiced hitting the ball from that exact location every time.

Even though they cannot hit the target from any location, they can hit the target from that exact spot and trick the verifier. Therefore, bad randomness can break the soundness of this scheme as well as real ZK schemes.

Back to ZK

This tennis analogy is a common challenge/response protocol seen in various areas of cryptography. In the ZK space, these are sigma protocols having three steps:

1. The prover first sends an initial message, the commitment message. (The prover first hits the ball to the verifier in our tennis analogy.)
2. The verifier replies with a truly random message, the challenge message. (The verifier returns the tennis ball to a random spot with random speed and spin.)
3. The prover sends a message that directly depends on the challenge message, the “response” message, and the verifier then accepts this as valid or invalid. (The prover moves to hit the return of the verifier and attempts to hit the target.)

It turns out that many ZK schemes take the form of one of these sigma protocols, which unfortunately makes them interactive. Luckily, the Fiat-Shamir transformation can transform these sigma protocols into non-interactive protocols.

First, I’ll explain the transformation using our tennis example. Sometimes players practice by hitting the tennis ball off of a wall to simulate another player’s returns. This is like the Fiat-Shamir transformation. Instead of relying on the verifier sending a return, we replace the verifier with a wall that returns the ball for us. And for this scheme to be sound, this return has to be completely random. Therefore (stretch your imagination here), we need a special wall that returns the ball with a completely random ball speed, placement, and spin. Then, the prover sends the ball back as before, and if they hit the target, they are a good player.

So how do we find such a wall for ZK proofs in practice? We use a hash function. Instead of sending their initial message to the verifier and waiting for a random response, the prover inputs their message into a hash function and uses the output as its challenge message. Using this challenge, the prover executes step 3 and sends the verifier’s response message as its proof. The verifier either accepts or rejects this in a non-interactive process.

Security of Fiat-Shamir implementations

Is this secure? Yes, mostly. First of all, we have to assume that our hash function returns completely random outputs. This is known as modeling the hash function as a random oracle and is somewhat of a controversial topic, but it has been used in various applications.

The other crucial and more subtle aspect is determining what input the hash function should receive. Using our tennis example, let’s say we’re using a wall to return the tennis ball, but for some reason, the wall’s internal random generation is only dependent on the speed and spin, but not on the location. This means that the prover will get the same challenge (i.e., the ball will be returned to the same spot on the court) from different locations, as long as the speed and spin are identical. These challenges are no longer truly random, allowing the prover to break the scheme’s soundness.

In the theoretical world, this is referred to as the weak and strong Fiat-Shamir transformations. Essentially, a small difference in inputs into the hash function can have very subtle but severe consequences to the protocol’s security. The theoretical details are a bit out of scope for this blog post, but if you are curious, you can read more about them here.

Going wrong in practice

Let’s look at a very simple sigma protocol example—the Schnorr protocol. In the Schnorr protocol, the prover proves to the verifier that they know the value X such that Y = g^X, for some group generator g. For those of you familiar with cryptography, you’ll know this is the common private/public key structure for things like ECC, El Gamal, etc. Therefore, this allows the prover to prove that they hold the secret key, X, corresponding to their public key, Y. The protocol works as follows:

• The prover generates a random value A, and sends B = g^A to the verifier
• The verifier replies with a random challenge value C
• The prover sends Z = A + CX to the verifier as its proof
• The verifier verifies the proof by checking that g^Z = BY^C

After doing some arithmetic, you can see that the verification check works, and this protocol is secure because the discrete log problem is assumed to be hard.

Since this is a sigma protocol, we can make this non-interactive with our new favorite transformation, Fiat-Shamir:

• The prover generates a random value A, computes B = g^A
• The prover generates C randomly with a hash function
• The prover sends Z = A + CX to the verifier as its proof
• The verifier verifies the proof by checking that g^Z = BY^C

But how exactly should the prover generate this random value, C? In the interactive protocol, the prover sends B to the verifier, so it might make sense to compute C = Hash(B). This is actually what theorists define to be the weak Fiat-Shamir transformation. As you might suspect, this has some subtle consequences. In particular, by using this computation, it’s actually possible for an adversary to provide a valid proof for some public key even if they don’t know the secret key:

• Let PK’ be some public key that we don’t know the secret key for
• Set B = PK’, C = Hash(B)
• Pick a random Z
• Set PK = (g^Z / PK’)^1/C

After some more arithmetic, you can see that Z will verify as a valid proof for PK. But since we don’t know the secret key for PK’, we don’t know the secret key for PK either! This is a forged proof. Depending on the exact application, this could be very problematic because it allows you to create fake proofs for keys related to another party’s public key, PK’.

This problem is avoided by adjusting how you compute C. By setting C = Hash(B, PK) or C = Hash(B, PK, g) will avoid these issues entirely. These are defined to be the strong Fiat-Shamir transformation.

A very similar issue was discovered in a Swiss voting system. In this system, one of the design goals is to allow for verifiable election results. To do this, a ZK scheme produces a decryption proof, which proves that an encrypted vote decrypts to the correct result. However, when implementing this scheme, only part of the prover’s input was given to the hash function (i.e., the strong Fiat-Shamir transformation was not used), and the prover was able to create false proofs. In this case, this meant that valid votes could be altered in such a way to make them not be counted, which has obvious implications for an election using such a scheme.

Conclusion

In summary, the Fiat-Shamir transformation converts an interactive ZK proof into a non-interactive one by computing a hash function on the prover’s inputs. In practice, this can lead to very subtle but dangerous bugs. When in doubt, use the strong Fiat-Shamir transformation and make sure every piece of the prover’s input is placed inside of the hash function!