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
| Word | What it means |
|---|---|
| Interactive | needing messages back and forth |
| Non-interactive | one message that anybody can check |
| Fiat-Shamir | replacing the challenge with a hash |
| Transcript | everything sent during a proof |
| Forgery | a 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
docker exec jupyter python3 steps/fiatshamir.pyShown 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 Schnorr | Fiat-Shamir Schnorr | |
|---|---|---|
| Who picks c | The verifier, at random | A hash of y, t and the message |
| Messages | Three, back and forth | One, t and s together |
| Who can check | Only the verifier who chose c | Anybody, at any time |
| What it convinces | One verifier | Everybody who checks |
The cells students fill in are left blank in this preview.
Try it: forge against a weak hash
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
docker exec jupyter grep -n def zk.pyShown here, not run. Press Start lab to type it into your own lab’s terminal.