pedersen-libsnark

zkSNARK for a Pedersen commitment

Ian Goldberg (iang@uwaterloo.ca), updated March 2020

I spent a day learning how to use libsnark, and thought an interesting first project would be to create a zkSNARK for knowledge of a preimage for a Pedersen commitment. I spent another day reimplementing it with a better scalar multiplication algorithm. A few months later, I did a little more work on the algorithm, further reducing the cost of scalar multiplication (with a constant base point) to 3 constraints per bit, and implementing new features like scalar multiplication of non-constant points.

This circuit ends up with 1531 constraints for a Pedersen commitment over a 254-bit elliptic curve.

It uses libsnark's BN128 implementation, which has an order (not modulus) of r=21888242871839275222246405745257275088548364400416034343698204186575808495617. Then using Sage, the findcurve script in this repo searches for an elliptic curve with modulus r, and with both prime order and whose twist has prime order. (You do not need to run the findcurve script yourself.) The resulting curve (over F_r) is E: y^2 = x^3 - 3*x + b, where b=7950939520449436327800262930799465135910802758673292356620796789196167463969. The order of this curve is the prime 21888242871839275222246405745257275088760161411100494528458776273921456643749.

The code uses four generators of this curve, which must not have a known DL representation among them. They are G(0,11977228949870389393715360594190192321220966033310912010610740966317727761886), H(1,21803877843449984883423225223478944275188924769286999517937427649571474907279), C(2,4950745124018817972378217179409499695353526031437053848725554590521829916331), and A(4,1929778687269876629657252589535788315400602403700102541701561325064015752665).

If you switch to a different underlying curve for the zkSNARKs than BN128, you will need to find a new E and new generators, and change the precomputed values in ecgadget.hpp to match. (Update 30 March 2020: MNT4 and MNT6 are now also supported.)

The code produces a zkSNARK for the statment "I know values a and b such that a*G + b*H equals the given Pedersen commitment P."

Also supported: scalar multiplication by a constant point (768 constraints), scalar multiplication by a public point (3048 constraints with a private precomputation table, or 1530 with a public one, but the public version is considerably slower to verify).

As an application of the latter, the included verifenc program provides a zkSNARK for verified ElGamal encryption of a private key (corresponding to a given public key) to a given receiver's public key. As an application of scalar multiplication by constant points, the included ratchetcommit program provides a zkSNARK for commitments of private values, where those private values are the output of a two-hash ratchet.

Building:

• Clone the repo
• git submodule update --init --recursive
• Ensure you have the build dependencies for libsnark installed.
• cd libsnark
• mkdir build && cd build && cmake -DCURVE=BN128 ..
• make
• cd ../..
• make

Thanks to Christian Lundkvist and Sam Mayo for the very helpful libsnark tutorial.