Batched Pedersen Equality Proofs

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.

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

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\le i\le d$, $y_i=g^{-w_i}$. Note that $\prod _i$ is implicitly taken over all $1\le i\le d$.

As above, we can see completeness by expanding out the verification equation as $g^s\prod _i{y}_i^{e_i}=g^r{g}^{{\mathrm{\Sigma }}_i{w}_i{e}^i}{g}^{{\mathrm{\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\ge 3$.

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

A Pedersen commitment is a commitment scheme of the form $c=g^m{h}^{\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 }$.

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^{\prime }\ne e$ to get back $s_m^{\prime },s_{\rho }^{\prime }$. Computing $(s_m-s_m^{\prime })/(e-e^{\prime })$ 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$.

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$.

Completeness follows from expanding out the verification equation as $g^{s_m}{h}^{s_{\rho }}{\mathrm{\Sigma }}_i{c}^{e^i}=g^{r_m}{g}^{-{\mathrm{\Sigma }}_i{m}_i{e}^i}{h}^{r_{\rho }}{h}^{-{\mathrm{\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\ge 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.