# Notes for KZG Blob Reads

## Goal
Prove batch multi-opens of KZG blobs described in [EIP-4844](https://eips.ethereum.org/EIPS/eip-4844).

## Motivation
[Data availability](https://ethereum.org/en/developers/docs/data-availability/) is a critical aspect to Ethereum's rollup-centric roadmap. Current production systems for storing rollup transactions make compromises in cost (when stored in [calldata](https://medium.com/ethereum-optimism/the-road-to-sub-dollar-transactions-part-2-compression-edition-6bb2890e3e92#:~:text=Calldata%20Overview,store%20Optimism%20transactions%20in%20calldata.)) or in trust (when stored [off-chain](https://celestia.org/)).

[Danksharding](https://ethereum.org/en/roadmap/danksharding/), along with the intermediate upgrade of proto-danksharding, presents a promising solution. It is an approach for storing aribitrary blobs of data cheaply on the main Ethereum network. How? Rather than storing blobs directly in the calldata at the execution layer, proto-danksharding has raw data stored temporarily at the consensus layer, with only the commitments stored at the execution layer.

These blob commitments are KZG vector commitments. To make use of them in the EVM, contracts must check the validity of batches of KZG openings. Given the [lack of a BLS precompile](https://eips.ethereum.org/EIPS/eip-2537) on top of an already compute intensive procedure, this is only feasible on-chain when done within a SNARK.

## Deliverables
1. Blob read circuit built on top of `halo2-scaffold`
2. A `KZGChip` that supports opens and multi-opens
3. Module for BLS12-381 that includes field and group operations, along with the pairing

## Circuit Design
### Constants
1. Pairing over BLS12-381 ($e: G_1 \times G_2 \to G_T$)
2. Generators ($H_1 \in G_1$, $H_2 \in G_2$)
3. Lagrange basis $L$ from trusted setup ($\{\lambda_i = \prod^{n - 1}_{j = 0, j \neq i} \frac{\tau - k}{i - j}\}$, where $n = 4096$)
4. Group element $[\tau]_2$ from trusted setup
5. Batch size ($k$)

### Inputs
1. Blob commitment $\bar p = [p(\tau)]_1$ to polynomial $p$ where $p(i) = b_i$ purportedly holds for all $i \in [0, n - 1)$, where $b_i$ is the $ith$ element in the blob
2. Batch $B = [(k_0, b_{k_0}), (k_1, b_{k_1}), ..., (k_l, b_{k_l})]$
3. Multi-open proof, commitment $\bar q = [q(\tau)]_1$ to polynomial $q(x) = \frac{p(x) - r(x)}{\prod_{k \in B} (x - k)}$

### Logic
1. Compute $r(x)$ to interpolate the points in $B$. This must be done the same way the client does it outside of the circuit. Use this to compute $[r(\tau)]_1$
2. Perform the pairing check $e([p(\tau) - r(\tau)]_1, H_2) = e([q(\tau)]_1, [\prod_{k \in B} (\tau - k)]_2)$

## Client Design
### Constants
1. Lagrange basis $L$ from trusted setup ($\{\lambda_i = \prod^{n - 1}_{j = 0, j \neq i} \frac{\tau - j}{i - j}\}$, where $n = 4096$)
2. Generators ($H_1 \in G_1$, $H_2 \in G_2$)

### Inputs
1. A blob vector of BLS12-381 field elements, size $n = 4096$
2. Indices $K = [k_0, k_1, ..., k_l]$ to make the multi-open proof for

### Logic
1. Interpolate polynomial $p(x)$ and compute $\bar p$ using $L$
2. Interpolate polynomial $r(x)$
3. Compute the quotient polynomial $q(x)$ and $\bar q$ using $L$

## Implementation Details
### BLS12-381 Group Operations & Pairing
We will use the `bn254` and `bigint` modules in `halo2-ecc` to implement arithmetic & pairings for BLS12-381. Perhaps we will implement a more generic `curve` module and refactor BN254 and BLS12-381 to be instantiations of it. Need to look into pairing math though to see if this is sensible.

### Client Implementation
There's a [geth branch](https://github.com/mdehoog/go-ethereum/blob/e864dddbe003833592e6b90317c86213007316b0/core/types/data_blob.go#L263) that has blob commitment implemented. There is, however, a lot of overhead and clunk with using this as our client. Spinning up our own would be faster, allowing us to focus on circuit writing. Leaning toward the custom client approach.

### Blob Data Interpolation
The official EIP spec uses roots of unity $[w_0, w_1, ..., w_{n-1}]$ instead of $[0, 1, ..., n-1]$ to index the blob elements. Likely so FFT can be used instead of lagrange interpolation. Haven't confirmed yet, but will loop back and edit the above design once we do.

### Batch Size
We'll set the parameter $l$ based on the max number of blob elements needed to store an L2 transaction. Can be quite large since the only computation that scales with $l$ in the circuit is the lagrange interpolation, which is $O(n^2)$ but doesn't have a large constant factor.

### Computational Feasibility
The amount of non-native arithmetic required here is worrisome. Will start with benchmarking the fundamental operations we require to get an estimate of runtime for the full circuit.

## Authors
Pun, Lyron, Jonathan, Yi