Fiat-Shamir Transformation: The Grandfather of Zero-Knowledge Proofs

Zero-knowledge (ZK) proofs are gaining popularity, and exciting new applications for this technology are emerging, particularly in the blockchain space. As the name suggests, a zero-knowledge proof system allows a prover to prove that they possess specific information without revealing that information!

For example, say you want to spend some money without revealing the exact amount - you can use ZK proofs to prove to the verifier that you possess enough money to spend without revealing how much total you have or spent.

Sounds like magic, right?

Wait till you hear what Fiat-Shamir Transformation does!

Sigma (Σ) Protocols

ZK Proofs are made secure by a property called ‘soundness’. It means that a malicious prover (who doesn’t actually know the underlying information) can never succeed in convincing the verifier with a forged proof of knowledge.

In the early days, soundness was made possible in ZK proofs via an interactive protocol that works like this:

• First, the prover sends an initial encrypted message to the verifier - this is called the commitment message

• Then, the verifier replies with a truly random message - this is called the challenge message

• Finally, the prover sends back a proof (response message) that directly depends on the challenge message, which the verifier accepts as valid or invalid

Such interactive protocols are called Sigma Protocols. Let’s look at an example to understand this better-

Alice knows a secret color and wants to convince Bob of her knowledge without revealing the secret color.

Say Alice’s secret color is Red🔴

She finds out the complementary color of red, and this gives her cyan 🔵

• First, Alice sends over cyan to Bob. (Assume Bob has no way to figure out complementary colors) - This is the commitment message

• Then, Bob sends her a challenge color - say, yellow 🟡

• Alice mixes her private color red with Bob's challenge color yellow and sends the resulting orange (response message) back to Bob-Red 🔴 + Yellow 🟡 = Orange 🟠

• Bob mixes orange with cyan, to get his original yellow back:🟠 + 🔵 = ( 🔴 + 🟡 ) + 🔵 This is the same as( 🔴 + 🔵 ) + 🟡 Since, red and cyan are complementary, this leaves us:⚪ + 🟡 = 🟡

Thus, Bob can be convinced that Alice is using the right secret key without ever knowing her original red color. If Alice was using any other color than her original, mixing orange with cyan would not have returned yellow.

This interaction between the verifier and the prover is what defines a Sigma protocol. And it works pretty well,

Except..

Except this method cannot scale. Imagine if Bob was a bank and had to use this protocol to get income proofs from the borrowers - he would have to do this 3-step interaction with every customer separately!

Thus, to scale, we need non-interactive ZK Proofs. And this is where the Fiat-Shamir Transformation comes in.

Fiat-Shamir Transformation

The Fiat-Shamir Transformation is a technique that converts an interactive proof system into a non-interactive proof system. In other words, it allows a prover to prove their knowledge of a secret to a verifier without any interaction between them.

“Wait what!?”

You heard that right!

Fiat Shamir achieves this magic by using something called a ‘hash’ function.

In Fiat-Shamir, 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 a response message as proof. The verifier either accepts or rejects this in a non-interactive process.

Mathematically, this is done by using Modular Arithmetic

Let’s look at a simple example to understand it:

The prover wants to prove to the verifier that they know the secret value X such that:

for some generator g.

Given Y, it’s extremely tough to find out X

The protocol works as follows:

• The prover generates a random value A, and computes B = gᴬ 

• Then the prover generates C randomly with a hash function. C = hash(B)

• The prover sends Z = A + CX to the verifier as its proof

• The verifier verifies the proof by checking that gᶻ = BYᶜ

And in this way, Fiat-Shamir transforms an interactive protocol into a non-interactive protocol. And it can be made stronger by making the hash completely random, C is taken as a hash of 2 or 3 different numbers. The power of the grandfather of ZK proofs is that it makes them practical by turning them non-interactive.