# Aztec Grant Application - BLS12-381 Curve Library

## Project

### KZG Proof Verification Library (EIP-4844 compliant)

Verifying data contained within an Ethereum blob requires verifying a KZG proof that the polynomial committed to by the blob opens to a given value(s) at a given point(s).

The delivery of this project is two Noir libraries. One for efficient pairing checks for the BLS12-381 curve and another that uses this library to perform KZG multi-proof verification. This unlocks the ability to perform verifiable computations over Ethereum blob data within Aztec as well as any other applications that require verification of KZG commitments. The library will be delivered at a standard that is ready to proceed to an external audit including complete test coverage.

The public interface of the BLS12-381 pairing library will be the function and associated types to compute

fn pairing(p: G1, q: G2) -> Fp12;

Recent research by Geometry Research and Alpen Labs[^1] has shown a number of different strategies that can be deployed to improve the efficiency of proving/verifying pairing checks and these will be considered for implementation as part of this engagement where possible.

The KZG library will have a similarly simple interface to allow consumers to verify proofs of N-point openings

verify<N>(
    srs: SRS,
    commitment: G1,
    proof: G1
    zs: [Fp; N],
    ys: [Fp; N]
) -> bool

It will additionally export functions to decode values from their binary representation as defined in the [specification](https://github.com/ethereum/consensus-specs/blob/dev/specs/deneb/polynomial-commitments.md).

### Prior Work

We are aware of existing Noir implementations of:

- [BLS12-381 pairings](https://github.com/onurinanc/noir-bls-signature/tree/main)

These will be used as reference and the authors credited where appropriate however to streamline auditing the implementation we ship will not depend on any code outside of the Noir standard library.

### Testing

Existing Ethereum standardized test suites for KZG can be used to ensure compliance and reduce testing workload.

See [test specifications](https://github.com/ethereum/consensus-spec-tests/tree/master/tests/general/deneb/kzg) and test [example test consumer](https://github.com/ethereum/c-kzg-4844/blob/main/src/test_c_kzg_4844.c).

Similarly standard test vectors can be used for testing the pairing checks.

### Milestones

#### 1. Efficient Implementation of pairings for BLS12-381 (2 engineers, 1 weeks)

- [ ] Implement BLS12-381 pairings in Noir based on existing implementations where possible
- [ ] Implement Miller loop line precomputation strategy of [^1] and quantify improvement
- [ ] Comprehensive tests against standard BLS12-381 test vectors

#### 2. KZG Multi-proof Verification (2 engineers, 0.5 weeks)

- [ ] Implement KZG multi-proof verification using above BLS pairing check library
- [ ] Write test harness to test against Ethereum EIP-4844 specification

## Proposed Funding Amount

Milestone 1 - $28k USD
Milestone 2 - $14k USD

Total - $42k USD

## About the team

### [ChainSafe R&D](https://solutions.chainsafe.io/)

ChainSafe R&D is a consulting team within ChainSafe with specialized skills in cryptography and systems design. Founded in 2020 we have successfully delivered projects for dozens of notable clients including:

- Ethereum Foundation
- Mina
- ZCash
- Protocol Labs
- Gnosis

We have experience developing production ready ZK implementations of cryptographic primitives. Notably a Halo2 implementation of BLS12-381 pairings which has been audited and is used in the Sygma cross-chain protocol.

- [Implementation](https://github.com/axiom-crypto/halo2-lib/pull/175)
- [Audit repot](https://f8t2x8b2.rocketcdn.me/wp-content/uploads/2024/06/VAR_ChainSafe-2.pdf)

### Team

[Willem Olding](https://github.com/willemolding/)
- PhD in Engineering (signal processing)
- Rust developer with 6 years professional experience
- Previously lead developer for Mina-rs

[Sebastian Lindner](https://www.linkedin.com/in/sebastian-lindner-594363110/)
- PhD in Computer Science (cryptography and number theory)
- Prior researcher in the field of hyper-elliptic curves including low-level optimized implementations

## Additional support requests

- A shared chat for any Noir related questions would be appreciated

## Additional Details

[^1]: https://eprint.iacr.org/2024/640.pdf