# ProtoDankSharding with FRI Polynomial commitment

## Parameters

We view a 1 MB data blob as a $64 \times 64$ matrix, with entries between $0$ and $p$ for a prime $p \sim 2^{2 56}$.

- n: 64. Number of rows of the matrix.
- m: 64. Number of columns of the matrix.
- $\omega$: the $2n$-th root of unity.
- $\rho$: the $2m$-th root of unity.
- $\alpha$: 16. Expansion factor of FRI commitment.
- $p$. A $256$ bits prime satisfying $\rho \equiv 1 \bmod 4\rho n$.

## Data representation

A data is defined as
$$d := \begin{bmatrix}
d_{0,0},& \dots,& d_{0,m-1}\\
\vdots, &\ddots, &\vdots\\
d_{n-1,0},& \dots, &d_{n-1,m-1}\\
\end{bmatrix}$$
Denote by ${\vec r_i}$, $\vec c_j$ the $i$-th row and $j$-th column of $d$. Then, let ${\bf r}_i(x)$ be the polynomial such that $\texttt{NTT}({\bf r}_i(x)) = \vec r_i$; and ${\bf c}_i(x)$ be the polynomial such that $\texttt{NTT}({\bf c}_i(x)) = \vec c_i$. That is, $\vec r_{i, j} = {\bf r}_i(\rho^j)$ and $\vec c_{i, j} = {\bf c}_i(\omega^j)$.

For each $\vec r_i$, we can build a $2m$ dimensional extended vector, denoted by $\vec r_i' := \left<{\bf r}_i(\rho^0),\dots, {\bf r}_i(\rho^{2m-1}) \right>$. This gives a $n \times 2m$ dimensional matrix. Extending the same notation, we obtain ${\vec c}_i$ for $i \in [0,2n)$. We then extend ${\vec c}_i$ in a similar fashion, and obtain ${\vec c}_i':= \left<{\bf c}_i(\omega^0),\dots, {\bf c}_i(\omega^{2n-1}) \right>$.

At the current stage, we have a $2n\times 2m$ matrix
$$f := \begin{bmatrix}
f_{0,0},& \dots,& f_{0,2m-1}\\
\vdots, &\ddots, &\vdots\\
f_{2n-1,0},& \dots, &f_{2n-1,2m-1}\\
\end{bmatrix}$$
with the following property:
- for $i$-th row, any $m$ element allows for reconstructing ${\bf r}_i(x)$, and hence the original $\vec r_i$;
- for $i$-th column, any $n$ element allows for reconstructing ${\bf c}_i(x)$, and hence the original $\vec c_i$.

## EIP4844
For simplicity, we assume $m = n$.

In EIP4844, it is proposed to use KZG commitment over Bl12-381 to commit to $\vec r_i'$  and $\vec c_j'$. The commitment to each polynomial is a G1 element of $48$ bytes, generated via an $n$-dim MSM. The openings for all elements can be batch generated via $n\log^2 n$ group operations.

The major drawback of the system is that __it requires a trusted setup__. At the current stage Ethereum layer 1 does not require such an assumption.

## Proposed solution

We propose to use the FRI commitment scheme to commit $\vec r_i'$ and $\vec c_j'$. Our naive solution uses a prime field of 256 bits as well. It may be possible to use a better, smaller field, such as Goldilock field. We leave this to further work.

Each commitment will be a root of the merkle tree, and therefore $32$ bytes.

Suppose we want to commit to $r_i'$, we extend $r_i'$ again to $r_i''$ of degree $2\alpha n = 2048$ (we will need to perform $\texttt{NTT}$s over this domain). We have a soundness error of $1/\alpha = 2^{-4}$, therefore to achieve $2^{-128}$ soundness error we need to open 32 paths. Each path is of $\log(2\alpha n)+1 = 12$ nodes, and each node is of size $32$ bytes. Our concrete proof size is
$$32  \times 12 \times 32 = 12 \texttt{KB}$$

In terms of running time, we require $2\alpha n = 2048$ hashes per polynomial, or $2\alpha n^2m = 8M$ for the whole matrix (without any batching). Note that we do not require circuit friendly hashes, so we can use $\texttt{keccak}$. [Sha3-512 is  11 cycles on SkylakeX](https://keccak.team/sw_performance.html). So we expect $<30ms$ over a single CPU. Also that our design is perfectly parallelizable. So we may get $<3 ms$ for a consumer grade desktop.

### Batching