Implementing A Zero Knowledge Proof Of Knowledge From The Schnorr Protocol: Σ Protocols And Fiat Shamir

2020-04-27 · Leonardo Benicio

Summary

A comprehensive technical exploration of implementing a zero knowledge proof of knowledge from the schnorr protocol: σ protocols and fiat shamir, covering key concepts, practical implementations, and real-world applications.

Contents

The Art of Proving Without Revealing: Implementing Zero‑Knowledge Proofs from the Schnorr Protocol

Imagine you’re standing at the entrance of a cave with two branching tunnels that meet at a secret door inside. I walk in, choose a path at random, and you lose sight of me. A moment later, I emerge from the other tunnel. I do this not once, but twenty times, each time you choose which tunnel I should come out of. After seeing me succeed every single time, you become convinced that I must know the magic words that open the door. Yet you have learned nothing about those words—not a syllable, not a hint. That’s the essence of a zero‑knowledge proof: a way to convince someone that you possess a piece of secret information without revealing any information about that secret itself.

This metaphor, invented by Jean‑Jacques Quisquater and used in the landmark 1989 paper “How to Explain Zero‑Knowledge Protocols to Your Children,” is more than a charming puzzle. It captures the spirit of one of the most powerful tools in modern cryptography. Zero‑knowledge proofs—once a theoretical curiosity in the 1980s—have become the backbone of privacy‑preserving systems, from anonymous cryptocurrencies like Zcash to secure authentication protocols and scalable blockchain roll‑ups. They allow us to say, “I know the password, but I won’t type it,” or “I processed your transaction correctly, but you don’t get to see my data.” The ability to prove something without revealing why it’s true is not just a neat trick; it’s a paradigm shift in how we think about trust, security, and transparency.

Among the simplest and most elegant of zero‑knowledge constructions is the Schnorr protocol. Proposed by Claus‑Peter Schnorr in his 1989 patent, this protocol lets a prover demonstrate knowledge of a discrete logarithm—the secret exponent in a public key—without ever revealing that exponent. It’s a textbook example of what cryptographers call a Σ‑protocol (Sigma‑protocol), named after the Greek letter Σ (sigma) that resembles the three‑message flow of the protocol. In this article, we’ll walk through the Schnorr protocol from the ground up, implementing it step by step, proving its security, and exploring how it has evolved into practical systems used by millions of people every day.

1. Why Zero‑Knowledge? The Privacy Imperative

Before diving into the math, let’s consider why zero‑knowledge proofs matter. In the traditional world, proving something often means surrendering your secret. Think about logging into a website: you type your password, which is sent (ideally salted and hashed) to the server. The server compares it with its stored hash. But what if the server is compromised? Or what if a man‑in‑the‑middle intercepts your password in transit? Even with TLS, the plaintext password is momentarily exposed at the server. We accept this risk because we have few alternatives—but the alternative exists in the form of zero‑knowledge password proofs.

Zero‑knowledge proofs (ZKPs) allow a prover to convince a verifier that a statement is true without leaking any information beyond the truth of the statement itself. The statement in Schnorr’s protocol is: “I know a secret (x) such that (y = g^x) (mod (p))”, where (g) is a generator of a cyclic group and (p) is a large prime. This is called a proof of knowledge of a discrete logarithm. It’s not enough to prove that such an (x) exists—the verifier already knows it does, because (y) is public. The prover must show that she actually knows (x), not merely that the statement is true. This distinction is central to many cryptographic applications.

The Three Properties of Zero‑Knowledge

A zero‑knowledge proof must satisfy three properties:

Completeness – If the prover is honest (knows the secret), the verifier will accept the proof with overwhelming probability.
Soundness – If the prover is dishonest (does not know the secret), the verifier will reject the proof with overwhelming probability (except for a negligible chance of cheating).
Zero‑knowledge – The verifier learns nothing about the secret itself. More formally, there exists a simulator that can produce an indistinguishable transcript of the protocol without knowing the secret.

These properties are formally defined using probabilistic algorithms and negligible probabilities. For the Schnorr protocol, we’ll prove each one.

The Discrete Logarithm Problem

The security of the Schnorr protocol rests on the hardness of the discrete logarithm problem (DLP). Given a cyclic group (\mathbb{G}) of order (q) with generator (g), and an element (y = g^x), it is computationally infeasible to find (x) (for suitably large groups, e.g., 256‑bit subgroups of elliptic curves). This is the foundation of many cryptographic systems, including Diffie‑Hellman key exchange and the ElGamal encryption scheme. DLP is believed to be hard even against quantum computers, though Shor’s algorithm breaks it, but that’s a topic for another day.

2. The Schnorr Protocol: A Three‑Move Dance

The Schnorr protocol is an interactive proof between a prover (P) and a verifier (V). It consists of three messages: a commitment, a challenge, and a response. This is why it’s called a Σ‑protocol: the shape of the three messages (and the Greek letter Σ) resembles the flow.

Setup:

Prover and verifier agree on a cyclic group (\mathbb{G}) of prime order (q) with generator (g).
Prover has a secret key (x \in \mathbb{Z}_q) (the discrete logarithm) and a public key (y = g^x).
The goal: Prove knowledge of (x) without revealing it.

Protocol steps:

Commitment (P → V):
Prover picks a random nonce (k \in \mathbb{Z}_q) (called the blinding factor), computes (t = g^k), and sends (t) to the verifier.
Challenge (V → P):
Verifier picks a random challenge (c \in \mathbb{Z}_q) and sends (c) to the prover.
Response (P → V):
Prover computes (s = k + c \cdot x \mod q) and sends (s) to the verifier.

Verification:
Verifier checks that (g^s = t \cdot y^c) (mod (q)). If the equation holds, the proof is accepted.

Let’s verify correctness:
(g^s = g^{k + c x} = g^k \cdot (g^x)^c = t \cdot y^c). QED.

Why the Name “Commitment”?

The term “commitment” is borrowed from commitment schemes. In the first message, the prover “commits” to a random value (k) by sending (t = g^k). She cannot change (k) later because (t) is fixed. However, the verifier cannot extract any information about (k) from (t) because (g) is a group generator and DLP is hard—(t) looks uniformly random. This ensures that the prover’s response is bound to her initial choice.

Visualizing the Protocol

Imagine a simple numeric example (just for illustration, numbers are small and insecure). Let’s use a toy group: (q = 7), generator (g = 3) (mod 7). Actually, we need a cyclic group, e.g., prime field with generator 3. But modulo 7, 3 has order 6, not prime. So let’s pick (q = 5) (prime), (g = 2) mod 7? That won’t work. Better: use a subgroup. For simplicity, let’s just work in the multiplicative group modulo a prime (p = 23) with (q = 11) (order of generator (g=2)). Actually, 2 is a generator of (\mathbb{Z}_{23}^) of order 22, not prime. Let’s pick (g=4) (order 11). (p=23), (g=4), order (q=11). Secret (x=3), so (y=4^3=64 \mod 23 = 64-46=18). Prover picks (k=5), (t=4^5=1024 \mod 23). 2344=1012, remainder 12. So (t=12). Verifier picks (c=7) (mod 11). Prover computes (s=5+73=5+21=26 \mod 11 = 4). Verifier checks (g^s=4^4=256 \mod 23). 2311=253, remainder 3. (t y^c = 12 * 18^7 \mod 23). Compute (18^2=324 \mod 23=2314=322, rem 2). (18^4 = 2^2=4). (18^7 = 18^4 _ 18^2 _ 18 = 4218=144 \mod 23=236=138, rem 6). So (t y^c = 12 * 6 = 72 \mod 23 = 3). Matches. Good.

In practice, groups are much larger (e.g., 256‑bit prime order curves like secp256k1, or 2048‑bit prime groups). The protocol is extremely efficient: only a few exponentiations.

3. Proving Security: Completeness, Soundness, Zero‑Knowledge

3.1 Completeness

If the prover knows (x) and follows the protocol, the verification equation holds by construction. The probability that an honest prover fails is zero (assuming correct arithmetic). In practice, it’s negligible due to possible bugs or network errors, but the protocol itself is perfectly complete.

3.2 Soundness: The Knowledge Extractor

Soundness ensures that a cheating prover cannot convince the verifier except with negligible probability. For Σ‑protocols, we need a stronger notion: proof of knowledge. There must exist an extractor algorithm that, given two valid transcripts ((t, c, s)) and ((t, c’, s’)) with the same commitment (t) but different challenges (c \ne c’), can compute the secret (x).

Why two transcripts? Because the cheating prover might guess a challenge in advance and cheat. Let’s see how.

Suppose a malicious prover wants to convince the verifier without knowing (x). She can pick a random challenge (c) first, and then compute (t) such that she can later produce a valid response. For example, she picks a random (s), then computes (t = g^s \cdot y^{-c}). This is a valid transcript for that specific (c). But she cannot answer any other challenge because the commitment (t) is fixed before seeing the challenge. If she guesses (c) correctly, she succeeds. Over a large challenge space (e.g., (q \approx 2^{256})), the probability of guessing correctly is negligible.

Now, if the prover could answer two different challenges (c) and (c’) for the same commitment (t), then we can extract the secret. Let (s = k + c x) and (s’ = k + c’ x) (where (k) is the discrete log of (t)). Then (s - s’ = (c - c’) x \mod q), so (x = (s - s’) \cdot (c - c’)^{-1} \mod q). This extraction works because we assume discrete logs exist. Therefore, a cheating prover who can answer two challenges is essentially the honest prover who knows (x). Soundness error is at most (1/q) (chance of guessing the challenge). This is called special soundness – the property of Σ‑protocols.

3.3 Honest‑Verifier Zero‑Knowledge

Zero‑knowledge requires that the verifier learns nothing beyond the statement. For Σ‑protocols, we achieve honest‑verifier zero‑knowledge (HVZK): if the verifier follows the protocol honestly, she gains no information. But what if the verifier is malicious—say, she picks a challenge non‑randomly? In that case, the protocol may leak information. However, HVZK is sufficient for many applications, especially when combined with the Fiat‑Shamir transform to make it non‑interactive and publicly verifiable (as we’ll discuss).

To prove HVZK, we construct a simulator that, without knowing (x), produces a transcript ((t, c, s)) that is indistinguishable from a real transcript. The simulator does the following:

Pick random (s \in \mathbb{Z}_q) and random (c \in \mathbb{Z}_q).
Compute (t = g^s \cdot y^{-c}).

Then ((t, c, s)) has the same distribution as a real proof: in a real proof, (t) is uniformly random because (k) is uniform, and given (t), the challenge (c) is uniform independent, and (s = k + c x) is uniformly distributed over (\mathbb{Z}_q) because (k) is uniform. In the simulated transcript, (s) and (c) are chosen uniformly, and (t) is derived. Since (g) is a generator, the mapping ((c,s) \mapsto t) is bijective given (y). The real distribution is ((t,c,s)) where (t) uniform, (c) uniform, (s) uniform (because (k) uniform). The simulator distribution is ((c,s)) uniform, (t) derived. These are identical distributions. Hence, the transcript reveals nothing about (x).

This is a simple but powerful insight: the verifier could generate a valid transcript herself without any help from the prover! That’s why it’s called zero‑knowledge: any interaction can be simulated.

4. Implementing the Schnorr Protocol in Python

Let’s bring the theory to life with a concrete implementation. We’ll use the cryptography library for elliptic curves (or a simple multiplicative group). For clarity, we’ll implement it in pure Python with a small prime order group (not secure, just for demonstration). Then we’ll show a version using the secp256k1 elliptic curve via the ecdsa library.

4.1 Toy Implementation (Multiplicative Group)

We’ll generate a safe prime (p) such that (p = 2q+1) and use the subgroup of quadratic residues of order (q). This is common practice.

import random

# Toy parameters (insecure, for illustration)
# q is a prime, p = 2q + 1, g is a generator of the subgroup of order q
Q = 11  # prime order
P = 23  # safe prime
G = 4   # generator of subgroup of order 11 (since 4^11 = 1 mod 23)

def mod_sqrt(a, p):
    # not needed for this protocol
    pass

def generate_keypair():
    x = random.randrange(1, Q)  # secret key
    y = pow(G, x, P)           # public key
    return (x, y)

def prove(x, y, c=None):
    """
    Prover: given secret x, public y, optional challenge c (if not provided, verifier chooses).
    Returns commitment t, challenge c, response s.
    """
    k = random.randrange(1, Q)
    t = pow(G, k, P)
    if c is None:
        # Simulated interactive: verifier would provide c
        # Here we get challenge as argument for flexibility
        pass
    s = (k + c * x) % Q
    return (t, c, s)

def verify(y, t, c, s):
    lhs = pow(G, s, P)
    rhs = (t * pow(y, c, P)) % P
    return lhs == rhs

But note: in interactive protocol, the verifier chooses (c) after seeing (t). So we need to simulate the round trip. For a complete interactive demo, we can run two parties. Let’s code a full interactive simulation:

import random

def interactive_proof():
    # Setup
    Q = 11
    P = 23
    G = 4
    x = 3  # secret key
    y = pow(G, x, P)  # public

    # Prover generates commitment
    k = random.randrange(1, Q)
    t = pow(G, k, P)
    print(f"Prover sends commitment t = {t}")

    # Verifier generates challenge
    c = random.randrange(1, Q)
    print(f"Verifier sends challenge c = {c}")

    # Prover computes response
    s = (k + c * x) % Q
    print(f"Prover sends response s = {s}")

    # Verifier checks
    lhs = pow(G, s, P)
    rhs = (t * pow(y, c, P)) % P
    if lhs == rhs:
        print("Proof accepted!")
    else:
        print("Proof rejected!")

4.2 Real‑World: Elliptic Curve Schnorr (using secp256k1)

In practice, Schnorr is often implemented on elliptic curves for efficiency and smaller key sizes. The Bitcoin ecosystem has adopted Schnorr signatures (via BIP‑340) which are based on the same discrete logarithm proof. Let’s implement a proof of knowledge of a discrete log on the secp256k1 curve using Python’s ecdsa library (or cryptography). We’ll use the secp256k1 curve with generator (G) and order (n).

First install ecdsa:

pip install ecdsa

Implementation:

from ecdsa import SECP256k1, ellipticcurve
from ecdsa.ellipticcurve import PointJacobi
import random

# Curve parameters
curve = SECP256k1.curve
G = SECP256k1.generator
n = SECP256k1.order  # order of the group

# Generate keypair
sk = random.randrange(1, n)
pk = sk * G  # public key is a point

# Prover
k = random.randrange(1, n)
T = k * G   # commitment point

# Verifier challenge (random scalar)
c = random.randrange(1, n)

# Prover response
s = (k + c * sk) % n

# Verification
left = s * G
right = T + c * pk   # point addition
print(left == right)  # True

Note: In elliptic curve notation, the verification equation is (sG = T + cP) where (P) is the public key. This is equivalent to the multiplicative group version.

This implementation is trivial once you have the curve operations. The Schnorr protocol is essentially the same whether you’re in a multiplicative group or an elliptic curve group. The underlying algebraic structure is identical.

5. From Interactive to Non‑Interactive: The Fiat‑Shamir Transform

Interactive proofs are great, but real‑world applications often need non‑interactive proofs that can be stored and verified independently. For example, a blockchain transaction should not require a second party to be online to issue a challenge. The Fiat‑Shamir heuristic (or transform) converts any interactive Σ‑protocol into a non‑interactive one by replacing the verifier’s random challenge with a hash of the commitment and, optionally, additional data. This yields a digital signature if the statement includes a message.

The idea: Instead of the verifier sending a random (c), the prover computes (c = H(t, m)) where (H) is a cryptographic hash function (e.g., SHA‑256) and (m) is the message to be signed. The prover then publishes ((t, s)) (or ((c, s))) and the verifier checks that (c = H(t, m)) and (g^s = t y^c). This is exactly how Schnorr signatures work—the original Schnorr signature scheme (patented) uses this transform.

Security of Fiat‑Shamir

In the random oracle model, where (H) is modeled as a random function, the non‑interactive proof is sound (proof of knowledge) and zero‑knowledge. The intuition: an adversary who can forge a proof must either break the discrete log or find a hash collision. The Fiat‑Shamir transform is widely used, but beware: it is not provably secure in the standard model, only in the random oracle model. Nevertheless, it is considered safe for practical purposes.

Implementation of a Schnorr Signature

Let’s implement a simple Schnorr signature on secp256k1:

import hashlib
import random
from ecdsa import SECP256k1, ellipticcurve
from ecdsa.ellipticcurve import PointJacobi

curve = SECP256k1.curve
G = SECP256k1.generator
n = SECP256k1.order

# Key generation
sk = random.randrange(1, n)
pk = sk * G

# Signing a message
message = b"Hello, ZKP!"
k = random.randrange(1, n)
R = k * G  # commitment point
# hash (Rx || message) to get challenge
hash_input = str(R.x()).encode() + message
c = int(hashlib.sha256(hash_input).hexdigest(), 16) % n
s = (k + c * sk) % n
signature = (c, s)

# Verification
# Recompute R' = sG - cP
R_prime = s * G - c * pk
hash_input_prime = str(R_prime.x()).encode() + message
c_prime = int(hashlib.sha256(hash_input_prime).hexdigest(), 16) % n
if c_prime == c:
    print("Signature valid")
else:
    print("Signature invalid")

This is a textbook Schnorr signature (though real implementations like BIP‑340 use a slightly different encoding for efficiency). Notice that we don’t need the full point (R) in the signature; we just need (c) and (s), and the verifier recomputes (R).

The Fiat‑Shamir transform is a cornerstone of modern cryptography, enabling decentralized protocols where no interactive challenge is possible.

6. Advanced Properties and Extensions

6.1 Proof of Knowledge of Multiple Secrets

The Schnorr protocol can be extended to prove knowledge of multiple discrete logs simultaneously. For instance, prove knowledge of (x_1, x_2) such that (y = g^{x_1} h^{x_2}). This is useful in anonymous credentials and attribute‑based systems. The protocol becomes: prover commits with (t = g^{k_1} h^{k_2}), challenge (c), response (s_1 = k_1 + c x_1), (s_2 = k_2 + c x_2). Verification: (g^{s_1} h^{s_2} = t y^c).

6.2 OR Proofs (Disjunctive Proofs)

A striking extension allows proving knowledge of one of several secrets without revealing which one. For example, “I know either (x) such that (y_1 = g^x) or (x’) such that (y_2 = g^{x’}).” This can be done using a technique where the prover simulates one part and honestly proves the other. The verifier cannot tell which branch is real. OR proofs are crucial for ring signatures and anonymous authentication.

6.3 Batch Verification

If you have many Schnorr proofs (e.g., thousands of signatures), you can verify them more efficiently by combining them using random linear combinations. This reduces the number of exponentiations.

7. Real‑World Applications

7.1 Cryptocurrencies: Schnorr Signatures on Bitcoin

In 2021, Bitcoin adopted Schnorr signatures through the Taproot upgrade (BIP‑340). This replaced the older ECDSA signatures with Schnorr, which are more efficient, enable signature aggregation (multiple signers produce a single signature for a multi‑signature transaction), and improve privacy. The core of a Schnorr signature is exactly the non‑interactive Schnorr protocol applied to a transaction message.

7.2 Anonymous Credentials and Identity

Microsoft’s U‑Prove and IBM’s Idemix use zero‑knowledge proofs to let users prove attributes (e.g., age > 18) without revealing their identity. They often rely on discrete‑log‑based proofs like Schnorr.

7.3 Blockchain Privacy: Zcash and Bulletproofs

Zcash uses zk‑SNARKs (Groth16) for its shielded transactions, but earlier versions of confidential transactions used Schnorr‑like range proofs. Bulletproofs, a recent efficient zero‑knowledge argument, uses internal commitments that are essentially Schnorr proofs in a different group.

7.4 Password Authentication: OPAQUE and SRP

The Secure Remote Password (SRP) protocol is a zero‑knowledge password authentication scheme that subtly uses the discrete log knowledge assumption. More recently, the OPAQUE protocol combines a password with an oblivious pseudo‑random function and zero‑knowledge proofs to resist offline dictionary attacks.

8. Comparison with Other Zero‑Knowledge Constructions

8.1 Schnorr vs. zk‑SNARKs

zk‑SNARKs (e.g., Groth16, PLONK) are extremely compact (a few hundred bytes) and fast to verify, but they require a trusted setup and are computationally heavy to prove. Schnorr proofs are simpler, don’t need a trusted setup, and the prover cost is linear in the number of statements. They are less efficient for complex statements (e.g., “I know a preimage of a hash”) but perfect for linear statements.

8.2 Schnorr vs. Bulletproofs

Bulletproofs are a type of range proof that proves a value lies in a interval without revealing it. They are built on inner‑product arguments and are more expressive than Schnorr. However, they are larger and sometimes slower. For simple discrete‑log knowledge, Schnorr is the canonical construction.

8.3 Schnorr vs. Guillou‑Quisquater

Another Σ‑protocol is the Guillou‑Quisquater (GQ) protocol for RSA‑based statements. It proves knowledge of an RSA signature without revealing the signature. Schnorr works only in prime‑order groups, while GQ works in RSA groups, which may have different trust assumptions.

9. Limitations and Pitfalls

Trusted Verifier? The basic Schnorr protocol is only honest‑verifier zero‑knowledge. If the verifier chooses a non‑random challenge (e.g., (c=0)), she could extract the secret (since then (s = k) and she learns (t = g^k), which reveals (k)). In practice, this is mitigated by using Fiat‑Shamir or by having the verifier commit to the challenge beforehand.
Randomness Quality: The prover must use high‑quality randomness for the nonce (k). If (k) is reused or biased, the secret can be recovered. This famously broke the Sony PlayStation 3 ECDSA implementation in 2010.
Quantum Vulnerability: The discrete‑log problem is vulnerable to Shor’s algorithm on a quantum computer. Schnorr signatures would become insecure. Post‑quantum zero‑knowledge proofs exist (e.g., based on lattices, isogenies, or hash functions) but are more complex.
Proof Size: Interactive Schnorr proofs are very short (two scalars), but non‑interactive ones include a hash and the signature. For many applications, that’s acceptable. However, if you need to prove thousands of statements, the proof size grows linearly.

10. Conclusion: The Beauty of Simplicity

The Schnorr protocol is a masterpiece of cryptographic design. Its elegance lies in its minimalism: a three‑message exchange, a few modular exponentiations, and a verification equation that emerges naturally from the algebra of cyclic groups. Yet from this simple seed grows a vast tree of applications—digital signatures, anonymous credentials, confidential transactions, and beyond.

Implementing the Schnorr protocol from scratch is an excellent way to build intuition for zero‑knowledge proofs. You start with the cave metaphor, then a concrete mathematical construction, then a real implementation, and finally a non‑interactive signature. The journey from “magic words in a cave” to “verifiable computation without trust” is short but profound.

As we look toward a future of decentralized systems and privacy‑preserving technologies, the ability to prove without revealing will only grow in importance. Whether you are building the next anonymous audit system, a blockchain roll‑up, or a password‑less login, the Schnorr protocol and its descendants will be your trusted companions.