# 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$.