Pedersen commitment equality proof

This is a zero-knowledge proof that two distinct curve points C1 and C2 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:

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

• 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

2. The proof sent to the verifier contains C3, C4, z1, z2, and z3. The verifier checks:
   1. C3 + c * C1= z1 G + z2H
   2. 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 C1,…,Cn that all commit to the same integer value m, using distinct blinding factors r1,…,rn. 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 (C1, Ci). 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:

1. Output a Chaum-Pedersen proof for the first pair C1 and C2
2. Compute k = H(C1,…,Cn) and ai = H(k, i) mod p
3. Compute Di = ai(Ci – C1) and zi = ai(ri – r1) for each i = 3 to n
4. Compute D = D3 + … + Dn  and z = z3 + … + zn
5. 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)