Awesome
zkPairing
<!-- START doctoc generated TOC please keep comment here to allow auto update --> <!-- DON'T EDIT THIS SECTION, INSTEAD RE-RUN doctoc TO UPDATE -->- Project overview
- Setup
- Building keys and witness generation files
- Benchmarks
- Testing
- Demo
- Acknowledgments
Project overview
This repository provides proof-of-concept implementations of elliptic curve pairings (in particular, the optimal Ate pairing and Tate pairing) for the BLS12-381 curve in circom. These implementations are for demonstration purposes only. These circuits are not audited, and this is not intended to be used as a library for production-grade applications.
Circuits can be found in the circuits
directory. The scripts
directory contains various utility scripts (most importantly, a script for building a zkSNARK to verify BLS signatures). test
contains some unit tests for the circuits, mostly for witness generation.
Setup
First, install yarn and circom.
- run
yarn install
in the root directory to install the dependencies (snarkjs
andcircomlib
) inyarn.lock
. - You'll need
circom
version>= 2.0.3
. - If you want to build the
optimalate
,subgroupcheckG1
,subgroupcheckG2
circuits, you'll need to download a Powers of Tau file with2^24
constraints and copy it into the circuits subdirectory of the project, with the namepot24_final.ptau
. We do not provide such a file in this repo due to its large size. You can download and copy Powers of Tau files from the Hermez trusted setup from this repository. - If you want to build the
verify
andtatepairing
circuits, you'll need a Powers of Tau file that can support at least2^25
constraints (place it in the same directory as above with the same naming convention).
Building keys and witness generation files
We provide the following circuits as examples:
verify
: Prove that a BLS signature verification ran properly on a provided public key, signature, and message. The circuit verifies that the public key and signature are valid.optimalate
: Prove that the optimal Ate pairing is correctly computed on two elements in appropriate subgroups.tatepairing
: Prove that the Tate pairing is correctly computed on two elements in appropriate subgroups.subgroupcheckG1
: Prove that a public key is valid, i.e., lies in the subgroupG1
of the curve.subgroupcheckG2
: Prove that a signature is valid, i.e., lies in the subgroupG2
of the curve.maptoG2
: Given twoF_{p^2}
elements, prove that their mapping to the twisted curve and cofactor clearing toG2
is correctly computed according to the Internet Draft.
Run yarn build:verify
, yarn build:optimalate
, yarn build:tatepairing
, etc. at the top level to compile each respective circuit and keys. See documentation for input format.
Note that verify
and tatepairing
are very large circuits so they require special hardware and setup to run: see Best Practices for Large Circuits.
Benchmarks
All benchmarks were run on a 32-core 3.1GHz, 256G RAM machine with 1TB hard drive (AWS r5.8xlarge instance). Constraints refer to non-linear constraints.
verify | optimalate | tatepairing | maptoG2 | subgroupcheckG1 | subgroupcheckG2 | |
---|---|---|---|---|---|---|
Constraints | 19.2M | 11.4M | 24.7M | 2M | 789K | 819K |
Circuit compilation | 3.2h | 1.9h | 4.2h | 23m | 7.6m | 8.5m |
Witness generation C++ compilation | 2h | 1.1h | 2.3h | 9.3m | 4.2m | 3.8m |
Witness generation | 2.6m | 1m | 2.5m | 33s | 23s | 13s |
Trusted setup phase 2 key generation | 58m | 32m | 1.6h | 4.5m | 1.7m | 1.9m |
Trusted setup phase 2 contribution | 25m | 13.6m | 29m | 2.9m | 54s | 55s |
Proving key size | 12G | 6.5G | 15G | 1.2G | 421M | 445M |
Proving key verification | 1.5h | 43m | 2.5h | 6.2m | 2m | 2.3m |
Proving time (rapidsnark) | 2m | 52s | 2.1m | 6s | 3s | 3s |
Proof verification time | 1s | 1s | 2s | 1s | 1s | 1s |
Testing
See the /test
directory for examples of tests. The circuits to be tested should be written in the /test/circuits
folder, while the test execution code should be written in regular JavaScript files under /test
. A short description of each test can be passed in as the first parameter of the describe()
function, and yarn --grep name
will run all tests whose description contains name
as a substring.
Documentation
See documentation for documentation of all circuits.
Demo
See here for a demo of BLS signature verification inside a zk-SNARK. The frontend code for the demo can be found here, and the server code can be found here.
Acknowledgments
This project was built during 0xPARC's ZK-ID Working Group.
We use a circom bigint library from circom-ECDSA and implement many of the same optimizations for elliptic curve operations as they do. This library uses an optimization for big integer multiplication from xJsnark.