Implementing Schnorr's Protocol in Rust

Introduction

In the Discrete Log Problem (DLP), we’re given a group (say, Z_p* for some large prime p), a generator g which produces a cyclic subgroup of large prime order q, and an element h of that subgroup. Our goal is to find an element x of Z_q such that g^x = h mod p; finding such an x is known to be quite hard, an assumption which multiple cryptosystems, such as Diffie-Hellman, rely on.

Say I’ve solved some hard DLP — that is, I claim I know x such that g^x = h mod p for some public h — and you’re interested in buying x from me. Before sending me the money, you’d want to verify that I’m not cheating you, and that x indeed solves the given DLP. However, if I’d just send you x, you might be able to verify the DLP, but you’d have no reason to pay me as you already possess x!

In this post, we’ll see a way to solve this problem using Schnorr’s identification protocol, originally presented by Claus Schnorr in a seminal paper from 1989. This protocol is a simple example of a Zero Knowledge Proof, which allows us to prove that x indeed satisfies the DLP relation, without revealing anything about x.

The first version of the protocol, which we’ll implement from scratch in Rust, is interactive, and requires the prover and verifier to be able to exchange messages with each other. After implementing this, we’ll see how we can use the Fiat-Shamir heuristic to create a non-interactive proof. This proof will be appended at the end of this post, and you’ll be able to use the code to verify it offline!

The Algorithm

Σ-Protocols

The protocol we’ll implement is an instance of a more general object called a Σ-Protocol. Given a public relation R, which defines which (instance, solution) pairs are “valid” (for example, the relation for DLP contains all (h, x) \in ⟨g⟩ \times Z_q for which g^x = h mod p; we will henceforth call x the witness), the Σ-Protocol lets the prover prove to the verifier that they possess some x for which (h, x) \in R for a public instance h, using 3 messages: (u, c, z). The prover first sends u, to which the verifier responds with a challenge c, and the prover replies with z.

A Σ-Protocol is required to satisfy three properties:

1. Perfect Completeness: if the prover follows the protocol correctly, then the verifier accepts the proof with probability 1.
2. Special Soundness: there is a polynomial-time algorithm that, given two transcripts (u, c1, z1) and (u, c2, z2) with c1 != c2, outputs a witness x such that (h, x) \in R. That is, if the prover answers more than one challenge after sending their first message, then they must know a witness. This is compared to only answering one challenge, under which it is only guaranteed with high probability that the prover knows a witness.
3. Zero Knowledge: the verifier cannot learn anything about the witness x from the transcript. Formally, we define this by saying that there exists a randomized polynomial-time simulator that, given the instance h, outputs a transcript (u, c, z) such that the distribution of those transcripts is indistinguishable from the distribution of the honest verifier interacting with the honest prover. Intuitively, if we can generate transcripts that look identical to real ones with no knowledge of x, then the transcripts from the Σ-Protocol do not reveal anything about x.

Schnorr’s Σ-Protocol for DLP

Now, let’s see how a Σ-Protocol for DLP looks like. First, the prover generates a random nonce r, chosen uniformly at random from Z_q*. Later, this nonce will serve us to bind the witness x – that is, send something related to x which allows the verifier to verify the proof but without revealing x itself. After choosing r, we compute u = g^r mod p — this is called a commitment to r — and send u to the verifier. Then, the verifier picks a challenge c at random from Z_q*, and sends it to the prover.

On the prover side, we then compute z = r + x * c (the binding for x), and send it to the verifier. Observe that:

g^z = g^r * g^(x * c) = u * (g^x)^c

If g^x = h as the prover claims, then the above is equal to u * h^c, which is composed only of public values. Therefore, to verify, we can simply test whether g^z = u * h^c! This achieves perfect completeness, but what about the other properties?

For special soundness, given two transcripts, we have:

z1 = r + x * c1
z2 = r + x * c2

Subtracting z2 from z1, we get:

z1 - z2 = x * (c1 - c2)

Because c1 != c2, then c1 - c2 != 0, and so it must have a modular inverse y such that (c1 - c2) * y = 1. We get y * (z1 - z2) = x, producing a witness for the DLP in polynomial time.

Finally, for zero knowledge, to produce a simulator that creates transcripts indistinguishable from real ones, if we pick c and z uniformly at random from Z_q*, and choose u = g^z * (h^c)^{-1}, then we get the desired distribution, as c is random in both cases, and (u, z) are chosen at random under the constraint that u * h^c = g^z.

Implementation

First, we define a structure for the prover:

pub struct Prover {
    /// We claim we know a solution to some DLP in our group:
    /// g^x = h mod p
    x: BigUint,
    /// Our random nonce r
    r: BigUint,
}

When initializing the prover, we randomly sample the nonce r:

/// Create new prover given the DLP solution; also generate a random nonce
pub fn new(x: BigUint) -> Prover {
	let mut rng = rand::thread_rng();
	let r = rng.gen_biguint_below(&GROUP_Q);

	Prover {
		x,
		r,
	}
}

Then, we create a method for committing to the nonce. For the group parameters, I used the 2048-bit group from RFC 5114:

/// Commit to our nonce: g^r mod p
pub fn commit(&self) -> BigUint {
	GROUP_G.modpow(&self.r, &GROUP_P)
}

On the verifier side, we generate the challenge:

pub struct Verifier {
    /// The prover claims they know x with g^x = h mod p
    h: BigUint,
    /// We'll randomly generate this challenge and send it over to the prover
    c: BigUint,
}

/// Generate a verifier w/a randomly-picked challenge
pub fn new(h: BigUint) -> Verifier {
	let mut rng = rand::thread_rng();
	let c = rng.gen_biguint_below(&GROUP_Q);
	
	Verifier {
		h,
		c,
	}
}

Back on the prover side, we respond to the challenge with this function:

/// Respond to the challenge c we got from the verifier
pub fn respond(&self, c: BigUint) -> BigUint {
	(&self.r + &self.x * c) % &*GROUP_Q
}

And given this response the verifier verifies as follows:

/// After the prover has responded to our challenge, we verify the response
pub fn verify(&self, u: BigUint, z: BigUint) -> bool {
	// We have g^z = g^(r + xc) = (g^r) * (g^x)^c = u * (g^x)^c
	// If the prover's statement is true, then g^x = h,
	// and the above is equal to u * h^c.
	// if not, then w.h.p. we'll get some other value.
	GROUP_G.modpow(&z, &GROUP_P) == (u * self.h.modpow(&self.c, &GROUP_P)) % &*GROUP_P
}

The implementation is pretty straightforward, but the protocol we implemented requires interaction between prover and verifier, which isn’t always possible (e.g., if the prover just posted the proof onto a blockchain and wants to enable a verifier to verify the proof offline). Next, we’ll see how to exploit properties of hash functions in order to do this.

Going Non-Interactive

The Fiat-Shamir Heuristic

In the interactive version, the only reason we needed the verifier was to create a random challenge. On paper, it might seem like this is necessary: if we’d relay this responsibility to the prover, they might be able to cheat and select challenges that benefit them, claiming the challenges were picked at random with the verifier having no way to ascertain whether this is true.

However, if we remember that cryptographic hash functions act as random oracles, ideally returning a random digest given some input, we can think of a clever way to create a non-interactive proof: just hash the random commitment u and use that as the challenge c! Because u changes with every random nonce r, the challenge c is also random. Moreover, u is public, so the verifier can check that the challenge was indeed created by hashing u. Other than that, everything will be identical, and now we don’t need any interaction.

However, the above offer has a critical bug: because we don’t hash h, the prover can forge h’s such that their proofs are always valid! More precisely, we can run the following attack:

1. Pick some value for the commitment u.
2. Compute the challenge c = H(u).
3. Select a random z.
4. Compute h = ((g^z) / u)^{1 / c}.

On the verifier side, we have:

H(u) = c -> correct
u * (h^c) = u * (g^z / u) = g^z -> correct

Thus, the proof verifies even though the prover doesn’t actually know a witness x. Therefore, when using the above transform, called the Fiat-Shamir Heuristic, it’s important to always use all the public parameters when constructing the challenge. In our setting, that means u, h, g, q, and p.

The Implementation

Now, we’ll have only a single Proof structure:

/// A proof that g^x = h mod p
#[derive(Serialize, Deserialize)]
pub struct Proof {
    h: BigUint,
    /// Commitment u to a random nonce
    u: BigUint,
    /// The challenge c which we create by hashing the public params
    c: BigUint,
    /// "Response" z
    z: BigUint,    
}

Generating a new proof is very similar to before, except we construct the challenge on the prover side using the Fiat-Shamir heuristic:

// Generate a ZKP that g^x = h mod p
pub fn new(x: BigUint, h: BigUint) -> Proof {
	let mut rng = rand::thread_rng();
	// Generate our nonce r
	let r = rng.gen_biguint_below(&GROUP_Q);
	// And commit to it
	let u = GROUP_G.modpow(&r, &GROUP_P);
	// Now generate our challenge using a random oracle (SHA256)
	// We need to make sure to pass in all public params: h, u, g, and q
	// This is what makes the proof non-interactive: we don't rely on the verifier for a challenge
	let buf: Vec<u8> = [h.to_bytes_le(), u.to_bytes_le(), GROUP_G.to_bytes_le(), GROUP_Q.to_bytes_le(), GROUP_P.to_bytes_le()].into_iter().flatten().collect();
	let c = BigUint::from_bytes_le(&Sha256::digest(buf)) % &*GROUP_Q;
	// Finally construct our response to the challenge, as in the interactive version
	let z = (r + x * &c) % &*GROUP_Q;

	Proof {
		h,
		u,
		c,
		z,
	}
}

Finally, the verifier side is identical, except we also verify that the challenge was created appropriately:

// Verify the proof - identical to the interactive version
pub fn verify(&self) -> bool {
	// We need to verify whether the challenge was produced correctly
	let buf: Vec<u8> = [self.h.to_bytes_le(), self.u.to_bytes_le(), GROUP_G.to_bytes_le(), GROUP_Q.to_bytes_le(), GROUP_P.to_bytes_le()].into_iter().flatten().collect();
	let expected_c = BigUint::from_bytes_le(&Sha256::digest(buf)) % &*GROUP_Q;
	if expected_c != self.c {
		false
	} else {
		// We have g^z = g^(r + xc) = (g^r) * (g^x)^c = u * (g^x)^c
		// If the prover's statement is true, then g^x = h,
		// and the above is equal to u * h^c.
		// if not, then w.h.p. we'll get some other value.
		GROUP_G.modpow(&self.z, &GROUP_P) == (&self.u * self.h.modpow(&self.c, &GROUP_P)) % &*GROUP_P
	}
}

That’s it! Indeed, with the below test, we verify that an honest proof verifies:

#[test]
fn test_proof_works() {
	// This is our DLP solution
	let x = BigUint::from(1337u32);
	let h = GROUP_G.modpow(&x, &GROUP_P);
	// Construct a proof
	let proof = proof::Proof::new(x, h);
	// Hopefully it should verify
	assert!(proof.verify())
}

Conclusion

In this post, we implemented Schnorr’s protocol in Rust as a simple example of a ZK proof. We began by seeing why the protocol is an instance of a Σ-Protocol, and then created an implementation of the interactive protocol in Rust. Then, we learned about the Fiat-Shamir heuristic, and how it can be leveraged to implement the protocol completely non-interactively. Of course, the code we implemented in this post is only for educational purposes, and should not be used in production systems. In future posts, I hope to implement more ZK primitives, and learn more about this field. Thanks for reading!

Finally, as mentioned in the intro, I’ll include the proof that I know of a witness x to some DLP here, and you’re welcome to use the code to verify it :)

Proof { h: 4875025991740592185682531125340732238465525645620221363399560622959064989424060779966260588857583282316744840812202671223102259238981027116683705969153347751011944616742267263657154210143472537220587923077251044902178310722308545021339902729921552519760899968186166953366166459033246903901566724875781159809693509539150177858937620832245519676602162785560612786727474258339576453401490333184451700605891819602349707559967137330028962473375274585066355985894026963682277609396290924953031809639635347737691258137371122423596951344897217195796604877697369472794707319283101562011828178875572687038835460972624582901915,
 u: 12088062557911634980185241927548870278057617270180515422694460075519926629814318475870371545725301064122455137844171138202003099234090120035570162451050758605902431164126799397827392862731245596318864829840620428434385315628746706275849808531186458382337225523137160196065463858644267111966688663639646583150137638978161322861448732067363057334831608287914111161910568506621185962915166449483229168607324362427005281128908222587738052049520886874511858987157250562958807816394330493526770142417828423406162609721326848872779818635893579994473067508716079961548921819384848271418940961761651664693172409146093761868321, 
 c: 6240272790876391784190897177114003616981132970890002757855385758925180657806,
 z: 44805023717921012453048585882565276103057435991112469684095838626167100611376 }

References

Schnorr, C.P. (1990). Efficient Identification and Signatures for Smart Cards. In: Brassard, G. (eds) Advances in Cryptology — CRYPTO’ 89 Proceedings. CRYPTO 1989. Lecture Notes in Computer Science, vol 435. Springer, New York, NY. https://doi.org/10.1007/0-387-34805-0_22

Justin Thaler, Proofs, Arguments, and Zero-Knowledge, Now Publishers, 2022.

https://www.zkdocs.com/docs/zkdocs/protocol-primitives/fiat-shamir/

Fiat, A., Shamir, A. (1987). How To Prove Yourself: Practical Solutions to Identification and Signature Problems. In: Odlyzko, A.M. (eds) Advances in Cryptology — CRYPTO’ 86. CRYPTO 1986. Lecture Notes in Computer Science, vol 263. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47721-7_12