Startseite Erkunden Hilfe
Anmelden
iang
/
pedersen-libsnark
1
0
Fork 0
Dateien Issues 0 Pull-Requests 0 Wiki

zkSNARKs for knowledge of preimage of a Pedersen commitment using libsnark

Struktur: 2dce3ad890
Branches Tags
pedersen-lib...
ZIP TAR.GZ
Ian Goldberg 2dce3ad890 Remove accidentally duplicated code vor 5 Jahren
libsnark @ 477c9dfd07 cb8642b8df Add libsnark as a submodule vor 5 Jahren
sage 7ea1a3d913 Initial commit of pedersen-libsnark code vor 5 Jahren
.gitmodules cb8642b8df Add libsnark as a submodule vor 5 Jahren
Makefile e251c51f13 Add an example application of verifiable encryption vor 5 Jahren
README.md 95d946225b Update README vor 5 Jahren
ecgadget.hpp 088df43cd7 Choose a better generator A that is more clearly nothing-up-my-sleeve vor 5 Jahren
libsnark_headers.hpp 12c989ed60 Use precompiled headers for libsnark vor 5 Jahren
pedersen.cpp a145003c92 Add versions of the scalarmul gadget that don't take an accumulator vor 5 Jahren
pedersen.hpp 12c989ed60 Use precompiled headers for libsnark vor 5 Jahren
scalarmul.cpp a145003c92 Add versions of the scalarmul gadget that don't take an accumulator vor 5 Jahren
scalarmul.hpp 12c989ed60 Use precompiled headers for libsnark vor 5 Jahren
varscalarmul.cpp 12129895ac Improve the CLI for varscalarmul vor 5 Jahren
verifenc.cpp 2dce3ad890 Remove accidentally duplicated code vor 5 Jahren

README.md

zkSNARK for a Pedersen commitment

Ian Goldberg (iang@uwaterloo.ca), updated November 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. 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.

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

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.