SE SNARK verifier gadget

scipr-lab / libsnark

C++ library for zkSNARKs

Other

1.81k stars 572 forks source link

SE SNARK verifier gadget #127

Open imeckler opened 5 years ago

imeckler commented 5 years ago

This PR implements a gadget for verifying Groth--Maller 17 SNARKs (r1cs_se_ppzksnark). To do so, it does the following:

Changes the r1cs_se_ppzksnark verification key to contain e(G_alpha, H_beta)
Adds a simple gadget for checking the equality of a vector of field elements
Makes a few modifications to field extension gadgets
Adds a G2 curve addition gadget
Changes the weierstrass miller loop gadget to handle negative loop lengths correctly
Adds a few simple pairing gadgets
Adds a verifier gadget for the GM17 SNARK

I've made each commit fairly self contained (and with decent descriptions in the commit messages). I know these are a lot of changes, so if you all would prefer they be split up between a few PRs, happy to do so.

There is also a change here that requires modifying libff slightly. How do you all coordinate updates between the repos?

imeckler commented 5 years ago

Oh also - thank you to @akattis for figuring out the negative loop length issue and @bekahoxoo for reviewing.

howardwu commented 5 years ago

Note that these changes include modifications to the current implementation of se_ppzksnark. These changes will affect the reported performance benchmarks as provided in the ppzksnark README: https://github.com/scipr-lab/libsnark/tree/master/libsnark/zk_proof_systems/ppzksnark

imeckler commented 5 years ago

@howardwu I don't think any of the changes I made will affect performance in any meaningful way. The primary difference is that the key generator now has to do one pairing to precompute G_alpha_H_beta (this is a few milliseconds).

imeckler commented 5 years ago

Ah - it does affect the verification key size I suppose. Although if you prefer we can make the serializer not write down G_alpha_H_beta and recompute it when we deserialize

howardwu commented 5 years ago

I believe the current approach is fine (@popoffka and @madars, feel free to chime in), we'll just need to have the table in the ppzksnark README updated to reflect the change.

howardwu commented 5 years ago

There is also a change here that requires modifying libff slightly. How do you all coordinate updates between the repos?

In this case, coordinated updates are made by first introducing the necessary (non-breaking) change in libff, followed by bumping the dependency versions in libfqfft and libsnark, and lastly by merging in the new functionality in libsnark.

HarryR commented 5 years ago

Any update on this?