pedersen-libsnark

zkSNARK for a Pedersen commitment

Ian Goldberg (iang@uwaterloo.ca), August 2019

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.

The algorithm is a pretty naive square-and-multiply; there are surely better ones. This circuit ends up with 3045 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 three generators of this curve, which must not have a known DL representation among them. They are G(0,11977228949870389393715360594190192321220966033310912010610740966317727761886), H(1,21803877843449984883423225223478944275188924769286999517937427649571474907279), and C(2,4950745124018817972378217179409499695353526031437053848725554590521829916331).

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.

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

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.