Setup

Recall from our previous note that 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 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}\)