We have been exploring the use of bivariate polynomial commitment schemes to enable chunk sampling in Nomos DA v2. By representing data in two dimensions using a bivariate polynomial, we can produce a single commitment instead of multiple commitments, reducing the total number of commitments compared to the current design. For instance, in the current setup we need 32 commitments for 1 MB of data; the bivariate approach would significantly reduce this, especially in scenarios without chunk sampling.
To compare, we also evaluated expressing data in one dimension using univariate polynomials combined with multi-proof and multi-opening mechanisms to understand the performance trade-offs. This helped us assess how the system would behave if we later switched to bivariate polynomials.
In parallel, we decided to revisit the FK20 method, particularly its multi-opening proof generation mechanism, to better understand how FK20 could be applied both to univariate and bivariate polynomials. This includes a deeper review of FK20’s multi-proof generation process in the first phase.
A bivariate polynomial is a function
$F(X,Y)=\sum_{i=0}^{d_X}\sum_{j=0}^{d_Y}a_{i,j}X^iY^j$
with bounded degree in each variable $(d_X,d_Y)$. In a data-availability setting, we often treat a rectangular matrix of data as evaluations of $F$ on a grid of points $(x_i,y_j)$.
Prover constructs witnesses $Q_X,Q_Y$ satisfying:
$F(X,Y)-v=(X-x_0)Q_X(X,Y)+(Y-y_0)Q_Y(X,Y).$
Send proofs of $Q_X,Q_Y$ (or use a random-line reduction to a univariate opening).