Home Explore Help
Sign In
iang
/
pedersen-libsnark
1
0
Fork 0
Files Issues 0 Pull Requests 0 Wiki

zkSNARKs for knowledge of preimage of a Pedersen commitment using libsnark

Tree: 17ffb8e98d
Branches Tags
pedersen-lib...
ZIP TAR.GZ
Ian Goldberg 17ffb8e98d Implement the 2-bit window optimization for scalarmults of constant points 4 years ago
libsnark @ 477c9dfd07 cb8642b8df Add libsnark as a submodule 4 years ago
sage 7ea1a3d913 Initial commit of pedersen-libsnark code 4 years ago
.gitmodules cb8642b8df Add libsnark as a submodule 4 years ago
Makefile 629d2245ec Scalar multiples of variable points (with new varscalarmul test program) 4 years ago
README.md 77aad9361e Improved algorithm for scalar multiplication 4 years ago
ecgadget.hpp 17ffb8e98d Implement the 2-bit window optimization for scalarmults of constant points 4 years ago
libsnark_headers.hpp 12c989ed60 Use precompiled headers for libsnark 4 years ago
pedersen.cpp a145003c92 Add versions of the scalarmul gadget that don't take an accumulator 4 years ago
pedersen.hpp 12c989ed60 Use precompiled headers for libsnark 4 years ago
scalarmul.cpp a145003c92 Add versions of the scalarmul gadget that don't take an accumulator 4 years ago
scalarmul.hpp 12c989ed60 Use precompiled headers for libsnark 4 years ago
varscalarmul.cpp 881144454e Allow Ptables to be public or private 4 years ago

README.md

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. I spent another day reimplementing it with a better scalar multiplication algorithm.

The algorithm is still a pretty naive square-and-multiply; there are surely better ones. This circuit ends up with 2045 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.