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