# Pedersen commitment equality proof

This is a zero-knowledge proof that two distinct curve points *C**1* and *C**2* are both Pedersen commitments to the same integer value *m*. The curve points are not equal because the blinding factors are different. This is implemented in the FRP cryptography library using a standard proof technique called a Chaum-Pedersen proof.

The contents of a Chaum-Pedersen proof are as follows:

- Public (verifier) inputs
*C**1**= mG + r**1**H and C**2**= mG + r**2**H* - Private (prover) inputs
*m*,*r*1 and*r*2 - Prover generates:
- Three new random values r3, r4, and r5
- The Pedersen commitment
*C**3*= r3G + r4H and C4 = r3G + r5H - A non-interactive “challenge” c = SHA256(C1, C2, C3, C4)

- Public (verifier) inputs

*Integer values mod p (the prime order of the elliptic curve group): z1 = c m + r3 and z2 = c r1 + r4 and z3 = c r2 + r5*

- The proof sent to the verifier contains C3, C4, z1, z2, and z3. The verifier checks:
- C3 + c * C1= z1 G + z2H
- C4 + c * C2 = z1G + z3H

Generating the proof requires 4 scalar multiplications on the elliptic curve (about 60 µs) and verifying this proof requires 6 scalar multiplications (about 90 µs). The size of the proof is two curve points and three scalars, or approximately 160 bytes.

There is also a version of this protocol for proving equality of more than two Pedersen commitments. The input is a list of curve points *C*1,…,*C*n that all commit to the same integer value *m*, using distinct blinding factors *r*1,…,*r*n. The simple way to implement this protocol is to reuse the Chaum-Pedersen proof and create *n* – 1 (pairwise) Pedersen equality proofs on each pair (*C*1, *C*i). However, a more efficient method uses a collision-resistant hash function *H* (e.g. SHA-256) and a 128-bit prime *p*, and operates as follows:

- Output a Chaum-Pedersen proof for the first pair
*C*1 and*C*2 - Compute
*k*=*H*(*C*1,…,*C*n) and*a*i =*H*(*k*,*i*) mod*p* - Compute
*D*i =*a*i(*C*i –*C*1) and*z*i =*a*i(*r*i –*r*1) for each*i*= 3 to*n* - Compute
*D*=*D*3 + … +*D*n and*z*=*z*3 + … +*z*n - Output a Chaum-Pedersen proof that
*D*is a Pedersen commitment to 0, using blinding factor*z*.

The total size of this proof is two Chaum-Pedersen proofs (just 320 bytes) and the cost of proof generation/verification for large *n* is approximately the cost of two Chaum-Pedersen proofs (60 / 90 µs) plus *n* additional 128-bit scalar multiplications (8 µs each).

Associated functions**:**

*pedersen_equality_prove*([uint64_t]*m,*[curve_point]*C1,*[uint256_t]*r1,*[curve_point]*C2,*[uint256_t]*r2*)

*pedersen_equality_verify*([string]*proof,*[curve_point]*C1,*[curve_point]*C2*)

*pedersen_equality_list_prove(*[uint64_t]*m,*[curve_point*]*point_list,*[uint256_t*]*blind_list*)

*pedersen_equality_list_verify*([string]*proof,*[curve_point*]*point_list*)