Sumcheck

This module holds the implementation of the sumcheck protocol.

The implementation varies depending on the Flavor provided as a template parameter. The two main conditions that change the prove/verify functionality are

1. IsGrumpkinFlavor concept, which distinguishes whether coefficients are Grumpkin (ECCVMFlavor, ECCVMRecursiveFlavor) or BN254 scalars.
2. hasZK which determines whether the flavor is a ZK Flavor.

<tt>SumcheckProver</tt>

Non-ZK sumcheck

This is a fairly standard implementation of the sumcheck protocol utilizing a book-keeping table.

The protocol proves/verifies the correctness of a claim $\sum_{X\in\lbrace 0,1\rbrace^d}\tilde{F} = 0$, where $$\tilde{F}(X) = \textsf{pow}_{\beta}(X_0,\dots,X_{d-1}) F(P_1(X), \dots, P_N(X)) = 0$$

to prove that $F(P_1(X),\dots,P_N(X)) = 0$ on points on the hypercube. Couple things to note:

1. $P_i$'s are multilinear polynomials
2. for $\beta = (\beta_0,\dots, \beta_{d-1})$, $\textsf{pow}(\beta)(X)$ is a multilinear polynomial with evaluation $\Pi_{i\in [d]} \beta_i^{X_i}$ for any $X$ on the hypercube.

‍note: for all flavors other than MultilinearBatchingFlavor we set the vector $\beta$ to be $(\beta, \beta^2, \dots, \beta^{2^{d}})$. Hence, the evaluation at the $i^{th}$ hypercube edge (i.e. $bin(i)$), is $\beta^i$.

<tt>SumcheckProver::prove()</tt>

This is the typical sumcheck proving algorithm. At each round the prover computes a round univariate $$S^i(X_i) = \sum_{\ell\in \lbrace 0,1\rbrace^d}F(u_0,\dots,u_{i-1},X_i, \ell_{i+1},\dots,\ell_{d-1})$$

The important observation is that since $P_i$'s are multilinear polynomials, we have the following equality for $\ell \in \lbrace 0,1\rbrace^{d-k-1}$: $$\begin{align}P_i(u_0,\dots, u_{k-1}, u_k, \ell)=&\ &u_k\cdot P_i(u_0,\dots,u_{k-1},1,\ell) \+ &(1-u_k)\cdot P_i(u_0,\dots,u_{k-1},0,\ell)\end{align}$$

Hence, at round $i$ the prover will keep a book-keeping table of evaluations $P_j(u_0,\dots,u_{i-1},\ell)$ for $\ell$ on the hypercube. In the code these are referred to as partially_evaluated_polynomials. The next book-keeping table (for round $i+1$) which has half the size of the one from round $i$, is computed using the equation above.

At the last round the partially_evaluated_polynomials only holds the evaluation of the multilinear polynomials at challenge point $u_0,\dots,u_{d-1}$.

Hence, here is how the proving flow goes:

1. The prover computes the first round univariate $S^0$ by calling compute_univariate on the full polynomials.
2. The prover initializes the partially_evaluated_polynomials book-keeping table and performs the first partial evaluation using partially_evaluate_first_round. Note that, since GateSeperatorPolynomial ($\textsf{pow}_\beta$) is also a multilinear polynomial, we follow the same logic as other multivariates for it.

• for remaining $d-1$ rounds:
  1. The prover computes the round univariate $S^i$ by calling compute_univariate on partially_evaluated_polynomials.
  2. Prover sends the round univariate to the verifier via the transcript object.
  3. The prover updates its book-keeping table in-place using partially_evaluate_in_place.

1. After all the rounds, the prover computes the final evaluation multivariate_evaluations by calling the extract_claimed_evaluations. This method simply returns the last element left in the book-keeping table after all the rounds which corresponds to $P_i(u_0,\dots,u_{d-1})$.
2. The prover sends these evaluations to the verifier via the transcript object

ZK sumcheck

There are two new subtleties that are introduced when making the proving system zero-knowledge.

1. The sumcheck protocol should be modified so that the round univariates and evaluations don't leak information about the witness
2. The sumcheck protocol should accommodate for randomness added to the end of the witness polynomials.

Let us focus on bullet point 2 first. In order to hide the contribution of witness values in commitments/openings every witness column is appended with 4 random values.

‍technically we only need to add 3 random values to each column, but since we require shift of some polynomials we append columns with 4 random values so there are 3 random values at the end of the shifted polynomial

As these values are random, for the sumcheck relation to hold, these values should be canceled. This is where we introduce the concept of RowDisablingPolynomials.

<tt>RowDisablingPolynomials</tt>

Assuming a reverse lexicographic order on the points on the hypercube, we want a polynomial that is $0$ at the following 4 points and $1$ everywhere else.

• $2^{d}-1 = (1,1,1,\dots,1)$, with the lagrange polynomial $L_{2^d-1} = X_0X_1X_2\dots X_{d-1}$
• $2^{d}-2 = (0,1,1,\dots,1)$, with the lagrange polynomial $L_{2^d-2} = (1-X_0)X_1X_2\dots X_{d-1}$
• $2^{d}-3 = (1,0,1,\dots,1)$, with the lagrange polynomial $L_{2^d-3} = X_0(1-X_1)X_2\dots X_{d-1}$
• $2^{d}-4 = (0,0,1,\dots,1)$, with the lagrange polynomial $L_{2^d-4} = (1-X_0)(1-X_1)X_2\dots X_{d-1}$

Hence, the polynomial which is zero on these $4$ points and $1$ everywhere else on the hypercube is $$\begin{align}\textsf{RowDisablingPoly} =&1 - (L_{2^d-1} + L_{2^d-2}+ L_{2^d-3} +L_{2^d-4})\ =& 1- X_2X_3\dots X_{d-1} \end{align}$$

Given the definition, the updated sumcheck relation, is: $$\begin{align} \sum_{X\in \{0,1\}^d } F(X)\textsf{RowDisablingPoly}(X) = 0 \end{align}$$ This affects the sumcheck rounds in 2 ways:

1. The contribution of $\textsf{RowDisablingPoly}$ to the round univariates should be added.
2. The contribution of $\textsf{RowDisablingPoly}$ to the last round's multivariate eval should be added.

Bullet point 2 is quite easy to handle, as the evaluation of the sumcheck multivariate should just be multiplied by $1-u_2\dots u_{d-1}$.

Now let's tackle bullet point 1. Let us refer to the round univariate without taking into consideration the RowDisablingPoly as $S_{F,i}$ and the round univariate of the corrected poly $S'_{F,i}$.

Recalling the definition of the round univariates of sumcheck we have that: $$\begin{align} S'_{F,i} &= \sum_{\gamma_i\in\{0,1\}} (F\times (1-L))(u_0,\dots,u_{i-1},X,\gamma_{i+1},\dots,\gamma_{d-1}) \ &= S_F - \sum_{\gamma_i\in\{0,1\}} F\times L(u_0,\dots,u_{i-1},X,\gamma_{i+1},\dots,\gamma_{d-1}) \end{align}$$ For $i=0$, $\Pi$ is only non-zero when for all $i>1$ $\gamma_i =1$ this means: $$\begin{align} S'_{F,0} &= S_F - \sum_{\gamma_1\in\{0,1\}} F\times L(X,\gamma_{1},1,\dots,1) \ & = S_F - \sum_{\gamma_1\in\{0,1\}} F(X,\gamma_{1},1,\dots,1) \end{align}$$ for $i=1$, $$\begin{align} S'_{F,1} &= S_F - F\times L(u_0,X,,1,\dots,1)\ &= S_F - F(u_0,X,1,\dots,1) \end{align}$$

For $i>1$, $$\begin{align} S'_{F,i} &= S_F - F\times L(u_0,\dots,u_{i-1}X,1,\dots,1)\ &= S_F - \Pi_{j=2}^{i-1}u_j \times X\times F(u_0,\dots,u_{i-1}X,1,\dots,1) \end{align}$$

Computing round univariates:

One important detail is how the round univariates (and the row disabling polynomial contributions are implemented).

To compute the round univariate first we would need to compute the corresponding univariates $P_j\left(u_0,\ldots, u_{i-1}, X_{i} , \vec \ell \right)$, for all prover multilinear polynomials $P_j$, over all $\vec \ell$ on the boolean hypercube.

Note that, $P_j\left(u_0,\ldots, u_{i-1}, X_{i} , \vec \ell \right)$ is already computed for $X_i \in \lbrace 0,1\rbrace$ in PartiallyEvalutedPolynomials book keeping table. To be able to compute evaluations of this univariate on an arbitrary point $X_i$ we should extend the evaluation table to the max individual degree of the relations in each variable. This is referred to as MAX_PARTIAL_RELATION_LENGTH and is specified by the Flavor.

This extension is done via the extend_edges method. This method uses a barycentric evaluation type algorithm (with specific optimizations for univariates of low degrees).

Computing the final round univariate, from the evaluations of the individual multilinear polynomials is done via the batch_over_relations method, which as the name suggests batches the univariate contributions of each multilinear to obtain the final univariate.

The contribution of the RowDisablingPoly to the round univariate is done quite similarly using the equalities given in the previous section and can be found in the compute_offset_area_contribution method of SumcheckProverRound. The same method also applies the dual L factor to any relation tagged IS_OFFSET_ONLY (see IsOffsetOnlyRelation), which is how boundary constraints on the offset rows 0..3 are enforced.

Libra

Now that we have covered removing the contribution of masking randomness in the witness polynomials we move to describing zero-knowledge variant of the sumcheck IOP itself. The approach we take is from Libra.

The main idea is that for a sumcheck claim $\sum_{x\in\lbrace 0,1\rbrace^d} F(x) = 0$ we pick a multivariate polynomial $G(x_0,\dots,x_{d-1})$ and a random challenge $\rho$ and perform a sumcheck protocol for the claim $$\sum_{x\in\lbrace 0,1\rbrace^d} (F(x) + \rho G(x)) = \rho\cdot \sum_{x\in\lbrace 0,1\rbrace^d} G(x)$$

In the code, we refer to $\rho$ as libra_challenge and $\sum_{x\in\lbrace 0,1\rbrace^d} G(x)$ as libra_total_sum.

The main contribution of Libra is that $G$ can have a very specific structure of form: $$\begin{align} G(X_0,\dots,X_{d-1}) =& a_0 + g_0(X_0) + g_1(X_1) + \dots+ g_{d-1}(X_{d-1}) \end{align}$$ Where for all $i\in [d-1]$, $g_i$ is a univariate of degree $\ell$ with random coefficients. $\ell$ is computed as the maximum individual degree of each variable in $F$.

So to summarize the extra steps of the protocol,

• Prover generates $g_i$\'s and commits to $G$.
• Verifier sends the libra_challenge $\rho$ (done via Fiat-Shamir)
• Prover and verifier engage in the sumcheck protocol for $F+ \rho G$
• in the last round, the verifier asks for openings of both $F$ and $G$ to perform the final evaluation check

Now let us discuss the details of the prover algorithm to include the contributions from the Libra polynomial. Looking at the definition of the round univariate again, we have that the corrected round univariate (of polynomial $F + \rho G$), is: $$\begin{align} S'_{F,i} &= \sum_{\gamma_j\in\{0,1\}} F(u_0,\dots,u_{i-1},X,\gamma_{i+1},\dots,\gamma_{d-1}) \ &+\rho\cdot \sum_{\gamma_j\in\{0,1\}} H(u_0,\dots,u_{i-1},X,\gamma_{i+1},\dots,\gamma_{d-1}) \ &= S_{F,i} + \rho \cdot\sum_{\gamma_j\in\{0,1