Easier to read with cream paper, a tint, more contrast or larger text? Choose your colours and text, once, for every page.

Free lesson

Fiat-Shamir: a proof anybody can check

After this lesson: I can compute a Fiat-Shamir challenge and verify a non-interactive proof.

60 min lesson2 commandsZero-knowledge proofs lab: commitments, Schnorr, Fiat-Shamir and Merkle proofs in Python

A proof that works without a conversation

The Fiat-Shamir transform turns an interactive proof into a non-interactive one: the prover makes the whole proof alone, and anybody can check it later. A hash plays the verifier.

This is how Schnorr becomes a signature, and how most zero-knowledge proofs are posted and checked today.

By the end of this lesson

Note

I can compute a Fiat-Shamir challenge and verify a non-interactive proof.

Key words

WordWhat it means
Interactiveneeding messages back and forth
Non-interactiveone message that anybody can check
Fiat-Shamirreplacing the challenge with a hash
Transcripteverything sent during a proof
Forgerya proof that passes without the secret

The cells students fill in are left blank in this preview.

A hash can pick the challenge

Interactive Schnorr needs a live verifier, which is awkward for a proof that many people check later.

Fiat-Shamir sets c to the hash of the public key, t and a message, cut down mod Q. The prover cannot choose c, because it depends on t, and a hash cannot be steered. So the prover still has to commit to t first. Anybody can work out the same c again.

Make and check a non-interactive proof

Command
docker exec jupyter python3 steps/fiatshamir.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

Read what the lab printed

The proof is two numbers, t = 718 and s = 501. The challenge, worked out from the hash, came to 14. The proof checks out as True.

The same two numbers with a different message check out as False, because the message is inside the hash and gives a different challenge. A Schnorr proof tied to a message is a signature on it.

Worked example: interactive and non-interactive

Interactive SchnorrFiat-Shamir Schnorr
Who picks cThe verifier, at randomA hash of y, t and the message
MessagesThree, back and forthOne, t and s together
Who can checkOnly the verifier who chose cAnybody, at any time
What it convincesOne verifierEverybody who checks

The cells students fill in are left blank in this preview.

Try it: forge against a weak hash

Code: python
import hashlib

P = 1019
Q = 509
G = 4
y = 227  # somebody's public key: we do not know their secret

def weak_challenge(message):
    # Wrong on purpose: t is left out of the hash.
    return int(hashlib.sha256(message.encode()).hexdigest(), 16) % Q

message = "Pat owes Kim 5"
c = weak_challenge(message)
s = 123
t = pow(G, s, P) * pow(pow(y, c, P), -1, P) % P
print("c =", c, "forged t =", t, "s =", s)
print("check passes:", pow(G, s, P) == t * pow(y, c, P) % P)
# Fix it: hash str(t) + message, so t must be chosen before c is known.

Hash everything the verifier would see

The code above left t out of the hash. So the forger worked out c first, picked any s, and made a t that fits, just as the simulator did. The check passed with no secret at all.

The rule is to hash every value the verifier would have seen before choosing: the group, the public key, t and the message. Real systems have shipped with this mistake, so it is worth checking by eye.

A common mistake

Warning

Many people think any hash makes Fiat-Shamir safe. It is only safe when the hash covers t and the statement. Leave t out, and a forger chooses the challenge first and fakes the proof, as the simulator does.

List the functions in zk.py

Command
docker exec jupyter grep -n def zk.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

About this lab and its source: Zero-knowledge proofs lab: commitments, Schnorr, Fiat-Shamir and Merkle proofs in Python

Teaching a class? Set this module for your students with a teacher guide, marked assignments and a lab for every student.