Home

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 --> <!-- END doctoc generated TOC please keep comment here to allow auto update -->

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.

Building keys and witness generation files

We provide the following circuits as examples:

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.

verifyoptimalatetatepairingmaptoG2subgroupcheckG1subgroupcheckG2
Constraints19.2M11.4M24.7M2M789K819K
Circuit compilation3.2h1.9h4.2h23m7.6m8.5m
Witness generation C++ compilation2h1.1h2.3h9.3m4.2m3.8m
Witness generation2.6m1m2.5m33s23s13s
Trusted setup phase 2 key generation58m32m1.6h4.5m1.7m1.9m
Trusted setup phase 2 contribution25m13.6m29m2.9m54s55s
Proving key size12G6.5G15G1.2G421M445M
Proving key verification1.5h43m2.5h6.2m2m2.3m
Proving time (rapidsnark)2m52s2.1m6s3s3s
Proof verification time1s1s2s1s1s1s

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.