lineval protocol

We present a protocol for sparse lineval. Based on Marlin/Fractal using Justin Drake's version of sumcheck.

Let \(H\) be a multiplicative subgroup of size \(n\). Let \(L_1,\ldots,L_n\in \mathbb{F}_{<n}[X]\) be a lagrange base of \(H\).
Here a verifier has a commitment to a polynomial \(f=\sum_{i\in H} f_i\cdot L_i(X)\) and wishes to compute the polynomial \(M\cdot f\) defined as follows. \(M\cdot f\) is the polynomial of degree \(<n\) with \((M\cdot f)(i) = \sum_{j\in H} M_{i,j}f_j\) for each \(i\in H\).

This suffices for an r1cs snark:
In R1CS the instance is defined by three matrices \(M_A,M_B,M_C\). Ignoring public inputs for simplicity, \(\mathscr{P}\) wishes to show knowledge of a vector \(f\in\mathbb{F}^n\) with
\((M_A\cdot f)\circ (M_B\cdot f) = (M_C\cdot f)\)
where \(\circ\) denotes coordinate-wise multiplication of vectors.
Thus, \(P\) can commit to the corresponding \(f=\sum_{j\in H}f_jL_j\), commit to the quotient polynomial \(T\triangleq (M_A f\cdot M_B f- M_C f)/Z_H\), and \(V\) can use the lineval protocol to check the equation at a random \(z\).

Terminology

We use the \(H\)-ranged polynomials protocols from PLONK.
Which means we describe protocols by \(P\) sending polynomial commitments (or the polynomial themselves to an ideal party) and \(V\) checking in the end if certain identites hold between the polynomials on \(H\).

The sumcheck subprotocol

An important component in lineval is a subprotocol for computing the value \(\sum_{i\in H}f_i\) given \(com(f)\) (or oracle access to \(f\) via other means).
Marlin/Fractal use a protocol from Aurora for this, we instead use a suggestion of Justin Drake (with a further optimization of Dan Boneh and Ben Fisch).

Note that we can always reduce to the case of proving \(\sum_{i\in H}f_i =0\) , by subtracting \(c/|H|\) from \(f\), \(c\) being the original claimed sum.

Suppose \(g\) is a generator of \(H\). The prover will commit to the poly \(Z\in \mathbb{F}_{<n}[X]\) with \(Z(1)=0\),
and \(Z(g^i)=\sum_{j<i}f(g^j)\).
The verifier will check that the following equation holds on \(H\).

• \(Z(X)+f(X) - Z(g\cdot X)=0\)

preprocessing:

Let \[A(X,Y) \triangleq \sum_{i,j\in H} M_{i,j}L_i(X)L_j(Y)\]

The verifier precomputes polynomials to aid it in computing \(A\) taking advantage of the sparsity of \(M\).
We assume for simplicity the number \(k\) of non-zeroes entries in \(M\) is equal to \(n\) (otherwise the protocol requires an additional multiplicative subgroup of size \(k\)).

Now let \(col,row,val\) be polys of deg \(<n\) such that the \(i\)'th non-zero entry of \(M\) is at location \((row(i),col(i))\) and has value \(val(i)\).
Thus we have
\[A(X,Y)= \sum_{i\in H} L_{row(i)}(X)L_{col(i)}(Y) val(i)\]

We precompute commitments to \(row,col,val\).

evaluating \(M\cdot f\)

Suppose now we wish to evaluate \((Mf)(x)\) for some \(x\in \mathbb{F}\).

We have
\[ (Mf)(x) = \sum_{i\in H} L_i(x)\cdot \left(\sum_{j\in H}M_{i,j}f_j\right)\]
reordering the sum we get
\[= \sum_{j\in H}f_j \cdot \left(\sum_{i\in H}M_{i,j}L_i(x)\right)= \sum_{j\in H}f(j)A(x,j)\]

Define \(A_x(X)\triangleq A(x,X)\)
Hence, it suffices to run the sumcheck subprotocol
on the polynomial \(f\cdot A_x\).
The subprotocol will require oracle access to \(A_x\)

Hence to reduce to sumcheck, it suffices to show how to compute \(A_x(y)\) for given \(y\in \mathbb{F}\).

computing \(A_x\)

We have \[A_x(y)= \sum_{i\in H} L_{row(i)}(x)L_{col(i)}(y) val(i)\]
Using \(L_i(X)= c_i Z_H(X)/(X-i)\) we can transform this to
\[=\sum_{i\in H}\frac{Z_H(x)}{x-row(i)}\frac{Z_H(y)}{y-col(i)}val(i)\]
(Note that we can modify dfn of \(val\) to "swallow" the constants c_i so the above equation is really accurate)

This is a sum of a rational function instead of polynomial, so we need to massage it a bit.
\(P\) sends a commitment to the polynomial \(g\in \mathbb{F}_{<n}[X]\) with
\[g(i)=\frac{Z_H(x)}{x-row(i)}\frac{Z_H(y)}{y-col(i)}val(i)\]
for each \(i\in H\).

We check \(g\)'s correctness by checking on \(H\) the identity
\[ g(X)\cdot (x-row(X))(y-col(X))-Z_H(x)Z_H(y)val(X)=0\]

Knowing that \(g\) is correct, we can run the sumcheck subprotocol on \(g\) to verify the value of \(A_x(y)=A(x,y)\) which was the last missing piece in the first sumcheck, and concludes the evaluation of \(Mf\) at \(x\).