As a first approach, we can follow the Semi-AVID paper where commitment to source data is a hash of column commitments: $C = Hash(c_0…c_d)$. This brings the following drawback: we need to send all source column commitments to the verifier.

This may to some extent be mitigated if we use the fact that pieces have commitments within them, but this way we have to carefully align columns with pieces.

A way to commit to KZG commitments as a two-tier commitment is described in **Proofs for Inner Pairing Products and Applications** (sec 6.1)

Data Layout

For the data arranged in a $l\times m$ grid (as in many existing schemes), it is common to represent each column (or row) as a polynomial $f_j(Y)$ for $j$ in $0 … m-1$.

Any such grid, being two-dimensional, can also be seen as evaluations or coefficients of a bivariate polynomial $f(X,Y)$. Then the values in a single column are obtained by fixing a value of $x$, and in a row by fixing a value of $y$. For example, $f(0,Y)$ evaluates to the first column and $f(X,0)$ evaluates to the first row. This approach is explicitly taken by Ethereum.

We imply that each $(x,y)$ cell of the grid is the KZG-instantiation compatible field element, i.e. 254 bits for BLS12-381 based KZG.

Commitment

For the data arranged in a $l\times m$ grid, we treat each column vector as represented by a polynomial

$$ f(j,Y) = f_j(Y) = \sum_{i=0}^{l-1}a_{i,j}Y^i \tag{1} $$

for $j$ in $0 … m-1$.

First, the prover computes a KZG commitment to every column (the y-polynomials $f_j$) and obtains $l$ column (inner) commitments $\overrightarrow{C} = \{C_0…C_l\}$.

Second, the prover computes a pairing commitment to the KZG commitments:

$$ T=\overrightarrow{C}\ast \overrightarrow{v}=\prod_{j=0}^{m-1}e(C_j,v_j)\tag{2} $$

We will call $T$ the outer commitment. Above, $\overrightarrow{v}$ is a subset of public parameters (aka structured reference string, SRS), available to both prover and verifier. We explain the contents of $\overrightarrow{v}$ in the Setup section below.

In the paper, the described commitment protocol outputs only the outer commitment. However, in the implementation the commit() outputs both the outer commitment and all the y-polynomial commitments. We also observe that the two tiers are practically independent at this stage and we may abstract away the second tier into a separate primitive, i.e. outer_commit(column_commitments, public_parameters) → T

Proving