The problem BLS PIL solves

An elliptic curve pairing is a bilinear function that takes in 2 elliptic curve points and outputs a scalar. Pairings are important cryptographic primitives and used in verifying zkSNARK proofs and also verifying BLS signatures. zkSNARK proofs are used for privacy (for example in Tornado Cash) and scaling (zkEVM). BLS signatures are used by Eth2 PoS validators and in other blockchains. We implemented pairing for the BLS12-381 curve in PIL, which is a new language that allows users to generate STARK proofs. By having BLS12-381 pairing in a STARK, we can verify BLS signatures within a STARK, which is useful for succinctly verifying BLS signatures on-chain. With succinct verification of BLS signatures on-chain, important applications like trust-minimized bridging is opened up. Furthermore implementation of pairing in a STARK opens up verifying a zkSNARK in a STARK recursively.

In general, our reference implementation is open-source and available to the community. We hope that this primitive serves useful for future users of PIL or others wanting to implement pairing in a STARK.

Challenges we ran into

One big challenge we had was doing out of field arithmetic in the STARK (BLS12-381 has 381 bits whereas the field used in the STARK is 64 bits). Another challenge was implementing the complex math operations used in pairing, as the pairing function is extremely complex. We were able to overcome these hurdles by careful step by step debugging of our code and architecting the sytem to be modular, so that each individual component was easily testable.