zkPairing: zkSNARKs for Elliptic Curve Pairings (Part 1) ​

Jonathan W., Vincent H., and Yi Sun

We present circom-pairing, a proof-of-concept implementation of zkSNARK circuits for elliptic curve pairings in Circom.

Introduction ​

Pairing-based cryptography (PBC) builds upon elliptic curve cryptography using the existence of a mathematical object known as an elliptic curve pairing. While pairings are relatively complicated to define, they underlie many of the cryptographic objects core to modern developments in zero-knowledge cryptography: BLS digital signatures, KZG polynomial commitments, and zkSNARKs.

Due to this key role in the ZK ecosystem, implementing pairings within zkSNARKs dramatically expands the scope of addressable cryptographic constructions and adds the ability of reflection to SNARKs. In particular, we envision applications to ZK Identity, blockchain scaling, and programmability for SNARKs. This last "unlock" may enable a future where anyone can freely compose and combine different SNARKs on the fly.

Because pairings involve many intricate elliptic curve operations, implementing them within a zkSNARK poses many challenges. First, for elliptic curve arithmetic over a non-native field, we must use big integer and ECC optimizations from zk-ECDSA, but adapted to our curve and the fact that pairings for BLS12-381 involve operating over a field extension. Second, Miller's algorithm for computing pairings admits many optimizations in the standard compute model, and we port these over to the zkSNARK setting. Finally, because of the complexity of the pairing computation, even the final optimized circuit may be quite large, meaning some infrastructure best practices are necessary to adapt the Circom tool stack for this purpose.

In this series of posts, we present a proof-of-concept Circom implementation of the optimal Ate pairing on the BLS12-381 curve and an example application to BLS signature verification. We then outline other potential applications like recursive SNARK and polynomial commitment verification, which our methods should easily generalize to.

circom-pairing ​

We implemented the circom-pairing repository, which provides unaudited ZK circuits for the following operations on the BLS12-381 curve:

• Tate pairing: tatepairing The Tate pairing is one of the simplest elliptic curve pairings. It satisfies the bilinearity properties, making it suitable for use in cryptography, and serves as a good sanity check that our elliptic curve computations and algorithms are implemented correctly.
• optimal Ate pairing: optimalate The optimal Ate pairing is the pairing most commonly used in practice. The computation is similar to that of the Tate pairing (using Miller's algorithm, which we'll talk about in a future post); however, there are fewer steps involved while the arithmetic at each step is more complicated, the net result being a shorter total computation.
• BLS signature verification (short pubkey): verify BLS signature verification allows one to check the validity of a BLS signature. Given a signature $s$, a generator $G$, a public key $xG$, and a hashed message $\mathsf{hash}$, the verify circuit converts $\mathsf{hash}$ into an elliptic curve point $H(m)$ using the maptoG2 circuit below and then verifies that $s$ is indeed the signature generated by the given public key and message. BLS signature verification involves evaluating two optimal Ate pairings to check that $e(s,G)=e(H(m),xG)$, where $e$ denotes the optimal Ate pairing.
• hash to curve: maptoG2 BLS signature verification operates by computing pairings of points on an elliptic curve. The message being signed must first be hashed into a numerical value. This hashed value is then converted into a point on an elliptic curve; the hash to curve circuit performs this conversion.

More detailed documentation of our circuits is available here. These circuits are not audited, and this is not intended to be used as a library for production-grade applications.

Demo ​

To illustrate our circuits, we implemented a demo at zkpairing.xyz which allows a user to generate the proof of the validity of any BLS signature (in a particular input format). If the user doesn't have a specific BLS signature they want to verify, they can specify any block number on the Ethereum Beacon Chain and the demo will parse the block data into the appropriate format and generate a proof that verifies the validator signature of that block. For each proof, we provide all of the data -- in three small files -- for anyone to use to verify the proof on their own computer!

Benchmarks ​

All benchmarks were run on a 32-core 3.1GHz, 256G RAM machine with 1T hard drive and 400G swap (AWS r5.8xlarge instance).

Running large circuits ​

Note that verify and tatepairing are very large circuits so they require special hardware and setup to run. In particular, one must use C++ for witness generation, rapidsnark for proving, and a patched version of Node.js without garbage collection for key generation. All this must be done on machines with large amounts of memory; our setup workflow is detailed in the Best Practices for Large Circuits document.

What can we do with zkPairing? ​

Because pairings are a core ingredient in many cryptographic protocols, zkSNARKs for pairing computations allow us to put the following higher-level primitives inside a SNARK:

• BLS signature verification: The Boneh-Lynn-Shacham (BLS) digital signature is a signature scheme based on elliptic curve pairings. It is currently used in blockchains such as Ethereum 2.0, ZCash, and Dfinity due to the ability to efficiently compute aggregate and threshold signatures using BLS. Verifying a BLS signature involves a pairing check that two elliptic curve pairings are equal and is thus directly enabled by zkPairing. This unlocks potential scaling applications like signature aggregation for light clients and bridges.
• Recursive SNARK verification: Because Groth16 proof verification only involves pairing checks, SNARK-ing pairings enables SNARK-ing the entire verification algorithm, called recursive verification. This allows us to build a zkSNARK of a zkSNARK of a ... ad infinitum, enabling developers to compose different SNARK proofs instead of building a single large SNARK and greatly increasing the complexity of possible SNARKs. We are adapting our circuits to recursive Groth16 verification on BN254 and hope to release a proof-of-concept in the near future.
• KZG polynomial commitment verification: The KZG polynomial commitment underlies PlonK, one of the new generation of zkSNARKs with universal trusted setup. Because verifying a KZG commitment involves a single pairing check, zkSNARK-ing pairings enables us to verify anything built on top of KZG commitments in a SNARK, including PlonK verification itself!

Look out soon for Part 2 discussing techniques going into our implementation of zkPairing!

Acknowledgments ​

This project was built during 0xPARC's ZK Identity Working Group with the support of the ZKxZK Gitcoin grant.

We were inspired by and share many techniques with circom-ecdsa, particularly for optimization of big integer and elliptic curve arithmetic. For instance, we use an optimization for big integer multiplication from xJsnark.

We also benefited greatly from the incredible generosity and openness of Jordi Baylina the original creator Circom and snarkjs. He taught us a great deal about the circom/snarkJS toolstack and shared many insights on how to effectively build large ZK circuits.