[ANN] bls12-381.3.0.0

Ecosystem
, , ,
1

Hello,

It is my pleasure to announce the release of the cryptographic library bls12-381.3.0.0 (keep reading for more details about the library content and engineering problems we faced and solved).
The changelog from 2.0.1 can be found here.
The release is available in the public opam-repository. You can install it using

opam install bls12-381.3.0.0

Repository: Danny Willems / ocaml-bls12-381 · GitLab
Release: 3.0.0 · Tags · Danny Willems / ocaml-bls12-381 · GitLab
License: MIT
Documentation: index (bls12-381.index)
Nomadic Labs website: https://nomadic-labs.com

This is also the first public announcement of a bls12-381 release. And, for this reason, I would like to describe the history of the library and the different challenges we faced as it may interest OCaml engineers, and also describe the content of bls12-381.
Disclaimer: For non-cryptographers, the cryptographic-related content may be too technical. Still, the following sections may be of interest for the OCaml engineers:

What is bls12-381?

bls12-381 provides a fast OCaml implementation of the pairing-friendly elliptic curve BLS12-381 and some cryptographic primitives built over it. The elliptic curve BLS12-381 has become a reference if not standard in recent years. Many blockchain protocols are relying on for aggregated signatures and zero-knowledge proofs: Tezos, Zcash and Ethereum 2.0.

BLS12-381, an instantiation of the BLS (Barreto-Lynn-Scott) curve family, was designed by Sean Bowe in early 2017 as the foundation for an upgrade to the Zcash protocol. It is both pairing-friendly (making it efficient for digital signatures) and effective for constructing ZK-SNARKs.

Library overview

This library contains fast implementations of:

  • operations over the scalar field, including (i)FFT.
  • operations over the groups G1 and G2, including EC-FFT, Hash to Elliptic Curves and the pippenger algorithm for fast multi scalar exponentiation.
  • operations over the target group of the pairing (GT).
  • pairing from G1 x G2 to GT
  • BLS signatures described in this specification. Both instantiations, i.e. the one minimizing the public key size and the one minimizing the signature size, are provided.
  • an instantiation of Poseidon providing a security of 128 bits. See the documentation for more information on the chosen parameters.
  • an instantiation of Rescue providing a security of 128 bits. See the documentation for more information on the chosen parameters.

The early development: Rust bindings and packaging

The development of the library started in early 2020 with the goal to integrate opcodes in Michelson in Tezos to give smart contract developers access to algebraic operations on the elliptic curves, the underlying scalar field and compute pairings. It has been successfully added to Tezos in the Edo protocol early 2021. It permits the deployment of projects like zkchannels and proof systems verifiers like Groth16 or PLONK can be implemented on-chain.

The first version of the library is a binding to the Rust crate pairing and exposed the scalar field, the elliptic curves and the pairing.
In 2020, OCaml bindings to Rust code were not completely new, but there was not a lot of examples and successfull deployments in production. At Nomadic Labs, we started discussing about how to deploy and package Rust bindings and asked the community. The current solution used in Tezos is to package the Rust library-specific code and vendor all the Rust dependencies like any other OCaml packages. While installing the OPAM package, the Rust code will be compiled using rustc and will produce a (static) library, which will be linked to the final binary. On the OPAM side, it results in a simple dependency.

OCaml/Rust interoperability in the browser

Since 2020, there is an increasing effort at Nomadic Labs to compile the Tezos client to JavaScript using js_of_ocaml. Therefore, there was a need to make interoperable Rust and OCaml in the browser/NodeJS for bls12-381, and there was no previous known work.

The road we took was compiling Rust to web-assembly (wasm) and call it from OCaml using js_of_ocaml. Some (unfinished) tutorials have been written from these experiments and a new version of bls12-381, 0.4.0, has been published, supporting compilation to JS. More details on the process should be added to the tutorials given above, in particular how to deal with pointers. In a nutshell, while calling a Rust symbol from OCaml, the OCaml value is copied into the wasm memory, used by the Rust code. The output is written in the wasm memory and copied back to the JavaScript memory. It is not the most efficient implementation, but performance wasn’t the priority that time, especially for the JavaScript backend as it was experimental.

To a more efficient implementation

BLS12-381 starting being a standard, high performance and secure implementation of the curves and primitives built above it were required. blst is one of them. It is written in C and assembly.
Blst, in addition to the curves and field arithmetic, implements the recently drafted Hashing to Elliptic Curves and BLS signatures standards, used for instance in Tezos for the transactional rollups.

bls12-381 moved to blst and has been released in bls12-381.1.0.0. This version uses ctypes to bind the C API given by blst. However, it has been decided to get rid of ctypes because we observed an overhead up to 25% of CPU time on the operations of the scalar field, mostly spent on allocations of Cstruct and additional information kept in a type Ctypes.t.

Removing ctypes gave opportunities to write more low-level optimisations. One of them is saving the C value directly in a custom block, giving a 40% improvement The overhead was due to the allocation of a pointer while allocating a custom block, adding also the overhead of a finalizer, which is the behavior when using Ctypes.ptr. As described here, this solution cannot always be applied, but the library is a good example of the overhead we can get rid of.

OCaml/C interoperability in the browser

As the library moved to a different backend in C, the previous JavaScript backend using Rust has been dropped. bls12-381.3.0.0 brings it back.

The idea is similar to the Rust based implementation. The C code is compiled to web-assembly using emscripten, exporting the symbols the library requires for the stubs. Most of the work is done in a primitive called wasm_call in the codebase. When calling a stubs, the parameters are copied into the wasm memory and we copy back the result in the JavaScript memory when the call finished, freeing the wasm memory at the same time. Allocation and free rely on the primitives malloc and free given by emscripten.

Primitives built over BLS12-381: Poseidon, Rescue and BLS signatures

The library does not restrict its content to the low-level primitives like the scalar field or the curves. Many cryptographic primitives built on top of the curve start to emerge and are on the road of standardisation. Therefore, centralising an (efficient) implementation in the project makes sense.

Algebraic hash functions

Poseidon and Rescue are algebraic hash functions. Algebraic means the construction of these primitives are based on operations over a (prime) field and does not operate on bits like standard primitives. This type of primitives is useful in SNARKs because programs are expressed in terms of constraints on multivariate polynomials on a (prime) field. Projects like Zcash in their upcoming Orchard upgrade and Dusk use Poseidon.

bls12-381 provides specific instances of Poseidon and Rescue design strategies. It also includes a novel optimisation on Poseidon, which decreases the CPU time of a permutation by 15% compared to our previous implementations. Our optimisation is not OCaml specific, it generically reduces the number of algebraic operations required to compute the Poseidon function. We believe other projects could benefit from this idea to achieve a similar speed-up.

Signature scheme

BLS (Boneh–Lynn–Shacham) signatures have been around for 20 years, but there haven’t been any concrete instance of it until recently. The main reason is because the BLS signature scheme require a hash function producing a point on an elliptic curve from an arbitrary-length input message, and there was no standard for the curve family BLS12-381 belongs to before the draft Hashing to Elliptic Curve.
BLS signatures are different from the more common ECDSA or Shnorr because of its aggregation properties. BLS signatures can be aggregated into a single short constant-size signature and can be verified without communication between the signers and there is no need for them to be online all together at the same time. In particular, this aggregation property is useful in blockchain applications like transactional rollups on Tezos.

Different instantiations of BLS signatures over BLS12-381 exist: one minimizing the size of the public keys at the expenses of having a longer signature size, or minimizing the size of the signature at the expenses of having longer public keys. This symmetry comes directly from the pairing-friendly property of BLS12-381.

bls12-381 provides both instantiations, leaving the choice to the library user. Also, the standardised hash functions on the curve are exposed to let the user using it for other applications.

Thanks for reading,
Happy hacking and coding.

4 Likes