## Setup

Recall from our previous note that the [Specialized Sum-Check protocol](https://hackmd.io/@plafer/SyrEonFr0#The-Specialized-Sum-Check-protocol) allows to prove a statement of the form

$$
\sum_{(x_0, \cdots, x_v) \in \{0, 1\}^{v+1}} g(f_0(x_0, \cdots, x_v), \cdots, f_m(x_0, \cdots, x_v)) = C,
$$

where $f_0, \cdots, f_m$ are multi-linear polynomials defined over some field $\mathbb{F}$, $g$ is any multivariate polynomial $\mathbb{F}^{v+1} \rightarrow \mathbb{F}$, and $C$ is some arbitrary value. During each round of the protocol, the prover is asked to build the following univariate polynomial:

$$
s_i(X_0) = \sum_{(x_{i+1}, \cdots, x_v) \in \{0, 1\}^{v-i}} g(f_0(r_0, \cdots, r_{i-1}, X_0, x_{i+1}, x_v), \cdots, f_m(r_0, \cdots, r_{i-1}, X_0, x_{i+1}, x_v)),
$$

where $r_0, \cdots, r_{i-1}$ are random variables from the previous rounds.

In this note, we will discuss how to efficiently compute that polynomial $s_i$.

## Preliminaries

Polynomials can either be stored in coefficient form, or evaluation form. For example, given a simple polynomial $f(x) = ax + b$, we could store $f$ as

- coefficient form: $[a, b]$
- evaluation form: $[f(0), f(1)]$

In general, for a polynomial of degree $d$, we need to store $d+1$ distinct evaluations. [Barycentric evaluation](https://people.maths.ox.ac.uk/trefethen/barycentric.pdf) is an algorithm that can be used to evaluate a polynomial stored in evaluation form.

We will be storing $s_i$ using evaluation form. Specifically, we will limit $s_i$ to be at most degree $d$, and store $s_i$ as $[s_i(0), s_i(1), ..., s_i(d)]$.

Also, the multi-linear $f_0, \cdots, f_m$ will have the evaluations of $r_0, \cdots, r_{i-1}$ already *bound*. That is, we will actually be working with some similar $f'_j$, defined as $f'_j(x_i, \cdots, x_v) = f_j(r_0, \cdots, r_{i-1}, x_i, \cdots, x_v)$. Therefore, the sum-check round univariate polynomial $s_i$ will actually be built as:

$$
s_i(X_0) = \sum_{(x_{i+1}, \cdots, x_v) \in \{0, 1\}^{v-i}} g(f'_0(X_0, x_{i+1}, x_v), \cdots, f'_m(X_0, x_{i+1}, x_v),),
$$

## Key multi-linear polynomial identity

Our algorithm will make use of a very useful identity of affine functions.

Let's begin with a simple univariate affine function: $h(x) = ax + b$. The identity is:

$$
h(x) = (1 - x) h(0) + x h(1)
$$

This is relatively easy to show:

$$
\begin{align*}
(1 - x) h(0) + x h(1) &= (1 - x) b + x (a + b) \\
&= b - bx + ax + bx \\
&= b + ax \\
&= h(x)
\end{align*}
$$

Note that multi-linear polynomials are *affine* in each of their variables. For example, take a 2-variate multi-linear function $h_2(x_0, x_1) = ax_0x_1 + bx_0 + cx_1 + d$. We will show that it is affine in $x_0$:

$$
\begin{align*}
h_2(X_0, x_1) &= aX_0x_1 + bX_0 + cx_1 + d \\
&= (ax_1 + b)X_0 + (cx_1 + d)
\end{align*}
$$

We used a capitalized $X_0$ to accentutate the fact that we're treating $x_1$ as constant. Since $(ax_1 + b)$ and $(cx_1 + d)$ are constants, then $h_2$ is affine in $X_0$. The same argument can be used to show that $h_2$ is affine in $x_1$ as well. And this is not limited to only 2 variables - it is true for any arbitrary number of variables.

Hence, our identity for multi-linear polynomials becomes:

$$
h(x_0, x_1, \cdots, x_v) = (1 - x_0) \times h(0, x_1, \cdots, x_v) + x_0 \times h(1, x_1, \cdots, x_v)
$$

### Use of the key identity in the algorithm

In the algorithm described below, we will need to evaluate $s_i$ at successive points: $s_i(0), s_i(1), \cdots, s_i(d)$. Ultimately, this will translate into evaluating each multilinear $f'_j$ similarly: $f'_j(0, x_{i+1}, \cdots, x_v), f'_j(1, x_{i+1}, \cdots, x_v), \cdots, f'_j(d, x_{i+1}, \cdots, x_v)$, for all $(x_{i+1}, \cdots, x_v) \in \{0, 1\}^{v-i}$.

For each instantiation of $(x_{i+1}, \cdots, x_v)$, instead of naively evaluating $f'_j$ some $d+1$ times, we will only evaluate it twice: $f'_j(0, x_{i+1}, \cdots, x_v)$ and $f'_j(1, x_{i+1}, \cdots, x_v)$. Then, we use the identity to get all the other evaluations:

- $f'_j(2, x_{i+1}, \cdots, x_v) = -1 \times f'_j(0, x_{i+1}, \cdots, x_v) + 2 \times f'_j(1, x_{i+1}, \cdots, x_v)$
- $f'_j(3, x_{i+1}, \cdots, x_v) = -2 \times f'_j(0, x_{i+1}, \cdots, x_v) + 3 \times f'_j(1, x_{i+1}, \cdots, x_v)$
- $\cdots$
- $f'_j(d, x_{i+1}, \cdots, x_v) = -(d+1) \times f'_j(0, x_{i+1}, \cdots, x_v) + d \times f'_j(1, x_{i+1}, \cdots, x_v)$

## The algorithm

> To simplify the notation, in this algorithm we will make use of vector addition and scalar mutliplication. That is, if $v_1 = [a, b, c]$ and $v_2 = [d, e, f]$, then $v_1 + v_2 = [a+d, b+e, c+f]$, and $42 *v_1 = [42 * a, 42* b, 42 * c]$.

The goal of the algorithm is to compute $s_i(X_0)$, which concretely, means computing $s_i(0), s_i(1), \cdots, s_i(d)$, since $s_i$ is stored in evaluation form as previously discussed.

- let $s_{acc} = [0, \cdots, 0]$ be an array of $d+1$ variables initialized to $0$ that will ultimately hold the evaluations of $s_i$ at $0, 1, \cdots, d$.
- The "acc" stands for "accumulator", as for each round of the coming loop, we will "accumulate" the results in this array.
- Only by the end of the loop will $s_{acc}$ contain the evaluations $s_i(0), \cdots, s_i(d)$.
- For each $(x_{i+1}, \cdots, x_v) \in \{0, 1\}^{v-i}$
- Let $evals_0 = [ f'_0(0, x_{i+1}, \cdots, x_v), \cdots, f'_m(0, x_{i+1}, \cdots, x_v) ]$
- Let $evals_1 = [ f'_0(1, x_{i+1}, \cdots, x_v), \cdots, f'_m(1, x_{i+1}, \cdots, x_v) ]$
- Update $s_{acc}$
- $s_{acc}[0] \mathrel{+}= g(evals_0)$
- $s_{acc}[1] \mathrel{+}= g(evals_1)$
- $s_{acc}[2] \mathrel{+}= g(2 * evals_1 - evals_0)$
- $s_{acc}[3] \mathrel{+}= g(3 * evals_1 - 2 * evals_0)$
- $\cdots$
- $s_{acc}[d] \mathrel{+}= g(d * evals_1 - (d-1) * evals_0)$
- Return $s_{acc}$