Adding Support for the Pairing-Equipped Elliptic Curve BLS12–381 to Tezos

Published in

METASTATE

8 min readMar 20, 2020

In case you missed it, here’s the link of Part 1: Enhancing Baking Accounts.

The purpose of this series is to share details with the Tezos community on one of the features that are being explored by our team: adding support for the pairing-equipped elliptic curve BLS12–381 to Tezos.

Due to the complexity of this field, this article is structured as follows: First, we provide background on zero-knowledge proofs of knowledge (zkPoK) schemes, with particular focus on one of the variants: SNARKs, with examples of technologies that have deployed them in mainnets or test networks. Second, we recapitulate on the current state of zkPoKs and elliptic curve cryptography (ECC) on Tezos. Third, we navigate through the background and motivations behind the focus on the specific BLS12–381 pairing-equipped EC curve. Finally, we describe some of the known features or use cases that the addition of this curve could enable on Tezos.

Background on Zero-Knowledge Proofs of Knowledge (zkPoK) Schemes

Zero-knowledge proofs of knowledge schemes (zkPoK) are a cryptographic primitive that enables one party, the prover, to prove to another party, the verifier, that they know of a value X which satisfies some predicate, without revealing any information about X itself. In addition, these cryptographic primitives enable faster verification of X fulfilling a property, than computing the property:

For illustration: computing a square root is expensive, but checking that a given number is a square root of another number is computationally cheap and fast.

Due to the properties of these methods, zkPoK schemes have increasingly attracted the interest of many researchers and engineers in the public decentralised ledger space. Although there are many variants and types of zkPoKs, in this article we focus on succinct (short proofs) non-interactive arguments (a party with sufficient computing power could forge false proofs) of knowledge (described above): SNARKs.

SNARKs have had particular prominence due to their capability to not only bring or increase privacy guarantees, but also their potential applicability to solve other hard problems in the realm of public decentralised networks, such as Layer 1, through recursive SNARKs, and Layer 2 scalability through ZK-Rollups.

Even though research publications and prototypes are abundant, examples of networks that have deployed SNARKs on mainnet or test networks are scarce:

ZCash, a cryptocurrency protocol, leverages zk-SNARKs (a zero-knowledge variant of SNARKs) to enable shielded transactions, where users can prove ownership / spending of funds without producing a transaction graph, which can be constructed by data points, such as public keys or accounts, amounts, timestamps, etc — this way, providing stronger anonymity and privacy guarantees than solely pseudonymous cryptocurrency protocols, such as Bitcoin.
Ethereum, a smart contract platform, supports opcodes that allow developers to write smart contracts that can verify SNARK proofs, as long as they utilise the supported curve alt-bn128 or any pairing-equipped elliptic curve.
Coda Protocol (in test network phase) is a cryptocurrency protocol that leverages recursive SNARKs to reduce the storage requirements of the ledger, making data verification more accessible for a larger set of clients (not only full nodes but also light clients), such as browsers or mobile devices.

Apart from SNARKs, these are other types of zkPoK schemes that have been deployed to a certain capacity:

StarkDEX Alpha, currently on Ethereum’s Ropsten Test Network (see e.g. Proof #5040, a Layer 2 scalability solution for Decentralised Exchanges on Ethereum, leverages zero-knowledge scalable transparent (verifier messages are public coins and no requirement of trusted setup) arguments of knowledge (STARKs) to verify on-chain transaction batches that were processed off-chain, thereby lowering the on-chain computational requirements of the DEX use cases.

*These are the networks, in either public test network phase or in mainnet that deploy these technologies, which at the time of writing I’m aware of. If you know of any other ones, feel free to leave a comment with the name and links to the source (e.g. source code).

The State of Zero-Knowledge Proofs of Knowledge on Tezos

At the time of writing, it is theoretically possible to implement a pairing-equipped elliptic curve (like BLS12-381) on a Tezos smart contract. Nonetheless, it is practically unfeasible within the current smart contract constraints (gas limits), as it would require the implementation of a non-trivial number of arithmetic operations.

The Tezos protocol 006 or mainnet does not support any pairing-equipped elliptic curve that could enable zk-SNARKs nor any zkPoK. More specifically, Tezos does not support the necessary components in the base protocol to enable on-chain verifiers for zkPoK schemes. However, there are many teams and individual contributors in the ecosystem who are actively researching and developing on the topic, such as Nomadic Labs (see Sapling integration in Tezos — Tech Preview) or our team.

The State of Elliptic Curve Cryptography on Tezos

Pairing-equipped elliptic curves are a crucial component in existing and emerging zk-SNARK protocols.

Currently, the Tezos protocol supports three elliptic-curves: Curve25519, secp256k1, and P-256. The usage of ECC in Tezos is pervasive. For instance, elliptic-curve cryptography is used in the process of key or implicit accounts generation (tz1, tz2, tz3 respectively); in algorithms that allow users to produce signatures with their respective keys (bakers, users, etc), or in the process of verifying that a message (e.g. a transaction) has been signed with the valid key, carried out by the Michelson opcode CHECK_SIGNATURE.

All the use cases above are part of the digital signature schemes currently supported by the protocol, such as Ed25519 (EdDSA with Curve25519).

However, mature implementations of zk-SNARK protocols, such as ZCash’s Sprout and Sapling, rely on pairing-equipped curves, such as bn128 and BLS12–381 respectively, which are currently not supported on Tezos.

Adding Support for the pairing-equipped elliptic curve BLS12–381 to Tezos

Background on curve BLS12–381

BLS12–381 is a pairing-equipped elliptic curve. Concretely, it is an instantiation of the Barreto Lynn Scott curve family, which was developed by the Electric Coin Company (R&D team developing the ZCash protocol) that provides better performance and security than its predecessor bn128 (see Reducing Shielded Proving Time in Sapling).

At the time of writing, although there are many open-source implementations of the curve, the most broadly adopted implementation is the one by the Electric Coin Company in Rust (see librustzcash/bls12_381, which is the one that the ZCash mainnet relies on).

Other pairing-friendly curves on our team’s radar are: BLS12–377 by cLabs, which is part of the Celo protocol’s digital signature scheme architecture (not in production yet); MNT4/6, which is a requirement of Coda protocol’s distinct design due to cyclic recursion; formerly known as bn128 (also named BN254), although being deprecated in favour of BLS12–381 due to better security and performance. A variant of bn128, alt-bn128, is supported by networks such as Ethereum and trusted-setup initiatives such as AZTEC team’s (not in production yet).

Why Support the Pairing-Equipped BLS12–381 Curve on Tezos?

As mentioned above, SNARKs and generally zkPoK schemes have shown non-trivial potential to solve some of the hardest problems in the realm of permissionless, censorship-resistant and decentralised networks. Thus, our high level goal is to make sure that Tezos gradually supports the building blocks or basic components required to enable not only existing SNARKs, STARKs, and recently published schemes, such as SHARKs, (see our Founder Christopher Goes’ talk on zkPoK variants at TQ Tezos Global Summit), but also upcoming improved and novel zkPoK designs and constructions that are yet to spawn.

Although adding the support for curve BLS12–381 does not enable per se any zkPoK schemes on Tezos, it would enable the deployment of zkPoK verifiers on-chain on Tezos, which are essential components of any existing and emerging zkPoKs. In addition, our team is working on example zkPoK verifier smart contracts that leverage the corresponding Michelson opcodes that the support for curve BLS12–381 enables.

This would pave the way for the protocol to more easily enable novel zkPoKs in the future, should the community decide to adopt any features on the Tezos protocol that relies on SNARKs or other zkPoK variants.

What Could the BLS12–381 Support Potentially Enable?

Broadly speaking, adding support for the pairing-equipped curve BLS12–381 on the Tezos base layer protocol enables the ability to develop and deploy verifier smart contracts on-chain. These verifier smart contracts will be able to interact with other components of zkPoK schemes that rely on this particular curve. Examples include, but are not limited to the following:

Sapling’s spend circuit and output circuit, which are the circuits (another essential component of zkPoK schemes) that compose ZCash’s upgrade Sapling. Noteworthily, these circuits were designed explicitly over the BLS12–381 curve.
Modifications of the existing circuits that rely on BLS12–381, for instance modifications of the existing Sapling circuits.
Layer 2 scaling solutions, such as ZK Rollups (see for example Matter Labs blog posts on ZK Rollups), currently being explored by existing teams in the Tezos ecosystem.

Summary & Final Remarks

In this Meanwhile at Cryptium Labs article we explore one of the features that our team is exploring: adding support for the pairing-equipped elliptic curve BLS12–381 to Tezos.

First, in order to provide broader context to the Tezos community, we shared a background on zero-knowledge proofs of knowledge (zkPoK) schemes, with particular focus on one of the variants: SNARKs, with examples of technologies that leverage them in live or test networks. Second, we recapitulated the current state of zkPoKs and elliptic curve cryptography on Tezos, which does not currently support any pairing-equipped elliptic curves at the base layer. Third, we navigated through the motivations and background on the specific BLS12–381 pairing-equipped elliptic curve choice. Finally, we described some of the known applications that this curve could enable on Tezos.

In order to facilitate more community involvement in the protocol development process, we would like to use this article and the Meanwhile series as research synthesis and discussion reference, in addition to opening this topic for discussion on multiple platforms. To discuss the topic of adding support for the pairing-equipped elliptic curve BLS12–381 to Tezos, you are encouraged to participate on Tezos Agora (this topic).

More Resources

Current implementation (Gitlab issue and MR) of adding support for BLS12–381 on Tezos (WIP) in collaboration with Nomadic Labs.
For more details on the implementation, see what’s under the hood through these repositories: rustc-bls12–381 & ocaml-bls12–381 by Nomadic Labs.
Cryptium Labs’ Research Blog for the upcoming Demystification of zkPoK protocols series and technical deep dives.
Our Team’s official website: Metastate.ch for more information on current projects and organisation.

Acknowledgements

On behalf of our team, I would like to thank the Electric Coin Company, for not only pioneering in the field of ZKPs applied to decentralised ledgers, but also for the vast contributions made so far through research publications and open-source libraries. I would also like to thank the Nomadic Labs team and my team members for the time spent in reviewing and providing constructive feedback on this article.

For feedback or questions, please do not hesitate to contact us : team@metastate.dev