Batched Pedersen Equality Proofs

Table of Contents

Sometime last year I came across a result that I found interesting demonstrating a variant of Schnorr’s identity protocol adapted to the case where a prover wishes to show knowledge of \(d\) discrete log identities. In addition to being a noteworthy protocol in of itself, I played around with it a bit and found a related variant which allows one to prove knowledge of multiple Pedersen commitments. I haven’t seen this written up anywhere so it seemed worth writing a short post on it.

We’ll be covering protocols that demonstrate:

Note that I have not yet proven soundness of the last protocol, although it seems intuitively secure. Caveat emptor.

Schnorr’s Identity Protocol

In 1989 Claus Schnorr invented the Schnorr identity protocol, which is the basis for Schnorr signatures. It is designed to prove knowledge of a secret key. The protocol’s security reduces down to the hardness of discrete log in the chosen group.

In the following description, we assume a group \(G\) with generator \(g\) of order \(q\). The prover will take in as a private input some \(w \in F_q\) such that \(y = g^{-w}\), where \(y\) is known to both the prover and verifier.

1. The prover picks randomly some \(r \in F_q\) and sends the group element \(x = g^r\) to the verifier
2. The verifier picks a random challenge \(e \in F_q\) and sends it to the prover
3. The prover computes scalar \(s = r + w \cdot e\) and sends it to the verifier
4. The verifier checks that \(x = g^s \cdot y^e\) and accepts iff true

It is easy to see upon expanding out the verification equation that \(g^sy^e = g^rg^{we}g^{-we} = g^r = x\). Multiple soundness proofs are available in the literature and will be glossed over here.

Schnorr Batched Identity Protocol

In 2004 a team of researchers including Rosario Gennaro discovered a generalization of Schnorr’s identity protocol which allows one to prove simultaneously \(d\) discrete log instances \(y_1,...,y_d\) with respect to the same base \(g\). They reduce the soundness of their scheme down to a stronger variant of the discrete logarithm assumption. Note that the word “batched” here does not refer to verifying multiple proofs at once, but to proving multiple discrete log values in the same proof.

As above, we assume a group \(G\) with generator \(g\) of order \(q\). The prover takes in as private input some \(w_1,...,w_d\) such that for all \(1 \leq i \leq d\), \(y_i = g^{-w_i}\). Note that \(\prod_i\) is implicitly taken over all \(1 \leq i \leq d\).

1. The prover picks some random \(r \in Z_q\) and sends \(x = g^r\) to the verifier
2. The verifier picks a random challenge \(e \in Z_q\) and sends it to the prover.
3. The prover computes \(s = r + \Sigma_i w_i \cdot e^i\) and sends it to the verifier.
4. The verifier checks that \(x = g^s \cdot \prod_i y_i^{e^i}\) and accepts iff true

As above, we can see completeness by expanding out the verification equation as \(g^s \prod_i y_i^{e_i} = g^rg^{\Sigma_i w_i e^i}g^{\Sigma_i -w_i e^i} = g^r = x\).

Essentially, the protocol is identical to the original, where we deal with the sum of multiple discrete log values \(w_i\) by expanding the random challenge \(e\) out into multiple values \(e\), \(e^2\), \(e^3\),… to separate out each \(w_i\) in the summation. This allows us to “reuse” the computations involving \(r\) and \(s\) to save computation asymptotically as \(d\) grows.

In terms of computation, if we are operating in an elliptic curve group, invoking the original Schnorr identification protocol \(N\) times requires \(N\) scalar multiplications for the prover, and \(2N\) for the verifier. The batched variant above requires \(1\) scalar multiplication for the prover, and \(1 + N\) for the verifier, an improvement for \(d \geq 3\).

A proof of soundness can be found in the aforementioned authors’ paper, linked at the end of the post.

Schnorr’s Protocol Adapted for Pedersen Commitments

A Pedersen commitment is a commitment scheme of the form \(c = g^mh^\rho\). Here \(c\) is the full commitment, \(m\) is the committed-to message, \(\rho\) is a uniformly random value, and \(g,h\) are generators of some group \(G\) of order \(q\). It provides information theoretic hiding and is computationally binding under the discrete logarithm assumption.

We can create a variant of the Schnorr identification protocol to prove knowledge of a message \(x\) hidden in a Pedersen commitment as follows. Here the prover will take as secret inputs a message \(m\) and randomness \(r\), both in \(F_q\). Both the prover and verifier will have access to generators \(g,h\) and the commitment \(c\). The prover’s goal is to convince the verifier it knows \(m,\rho\) such that \(c = g^m h^\rho\).

1. The prover picks randomly some \(r_m, r_\rho \in F_q\) and sends the group element \(x = g^{r_m}h^{r_\rho}\) to the verifier
2. The verifier picks a random challenge \(e \in F_q\) and sends it to the prover
3. The prover computes scalars \(s_m = r_m - x \cdot e\) and \(s_\rho = r_\rho - \rho \cdot e\) and sends them to the verifier
4. The verifier checks that \(x = g^{s_m} \cdot h^{s_\rho} \cdot c^e\) and accepts iff true

As usual, completeness can be proven by expanding out the verification equation: \(g^{s_m}h^{s_\rho}c^e = g^{r_m}g^{-xe}h^{r_\rho}h^{-\rho e}g^{xe}h^{\rho e} = g^{r_m}h^{r_\rho} = x\). Note that flipping the addition operations to subtraction in step 3 was an arbitrary choice, as instead we could have made the commitment over \(-m\) and used addition as in the above discrete log protocols.

For knowledge soundness, an extractor can be constructed which runs a prover with randomness \(e\) to get back \(s_m, s_\rho\), then rewinds the prover and calls it with randomness \(e' \not= e\) to get back \(s_m', s_\rho'\). Computing \((s_m - s_m')/(e-e')\) will yield \(m\), and likewise for \(\rho\).

Conceptually, this protocol is really a special case of a more generalized scheme, which can easily be derived from the description above, which modifies the original Schnorr protocol to prove knowledge of \(n\) discrete log values in a product of \(n\) generators, as \(g_1^{x_1}g_2^{x_2}...g_n^{x_n}\). In other words, it proves knowledge of the discrete log values used in a size \(n\) fixed-base multi-exponentiation. In this case the prover in step 3 computes \(n\) values in the same manner as the current protocol does for \(s_m\) and \(s_\rho\), and sends them to the verifier. The protocol proving knowledge of a Pedersen commitment described here is the case where \(n=2\).

Schnorr’s Protocol Adapted for Batched Pedersen Commitments

Here we demonstrate a protocol which proves knowledge of \(d\) Pedersen commitments over the same basees \(g,h\). In this context the prover takes in as secret input the messages \(m_1,...,m_d\) and randomness values \(\rho_1,...,\rho_d\) of \(d\) Pedersen commitments \(c_1,...,c_d\). Both the prover and verifier have access to the full commitments, in addition to the generators \(g,h\) over the same group \(G\).

1. The prover picks randomly some \(r_m, r_\rho \in F_q\) and sends the group element \(x = g^{r_m}h^{r_\rho}\) to the verifier
2. The verifier picks a random challenge \(e \in F_q\) and sends it to the prover
3. The prover computes scalars \(s_m = r_m - \Sigma_i m_i e^i\) and \(s_\rho = r_\rho - \Sigma_i \rho_i e^i\) and sends them to the verifier
4. The verifier checks that \(x = g^{s_m} \cdot h^{s_\rho} \cdot \prod_i c_i^{e^i}\) and accepts iff true

Completeness follows from expanding out the verification equation as \(g^{s_m}h^{s_\rho}\Sigma_i c^{e^i} = g^{r_m}g^{-\Sigma_i m_i e^i}h^{r_\rho}h^{-\Sigma_i r_i e^i} \prod_i g^{m_i e^i} h^{\rho_i e^i} = g^{r_m}h^{\rho_m} = x\).

If we are working in an elliptic curve group, the protocol for a single Pedersen commitment executed \(N\) times requires \(2N\) scalar multiplications for the prover and \(3N\) for the verifier. The batching version of the protocol for \(N\) Pedersen commitments requires a constant \(2\) scalar multiplications for the prover and \(2 + N\) scalar multiplications for the verifier. This implies the protocol is useful when the number of commitments is only \(2 \geq d\).

A proof of soundness is left as an exercise to the reader.

As with the previous protocol proving knowledge of only one Pedersen commitment, the generalization proving knowldge of \(d\) distinct products of multi-exponentiations each with the same \(n\) generators is easy to derive.

Citations

Author: Michael Straka

Created: 2025-02-03 Mon 09:48