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}\to \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^{\prime }$, defined as

$f_j^{\prime }(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^{\prime }(X_0,x_{i+1},x_v),\cdots ,f_m^{\prime }(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)+xh(1)$$

This is relatively easy to show:

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

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)=a{x}_0{x}_1+b{x}_0+c{x}_1+d$. We will show that it is affine in

$x_0$:

$$\begin{array}{rl}{h}_2(X_0,x_1)& =a{X}_0{x}_1+b{X}_0+c{x}_1+d\\ & =(a{x}_1+b)X_0+(c{x}_1+d)\end{array}$$

We used a capitalized

$X_0$ to accentutate the fact that we're treating

$x_1$ as constant. Since

$(a{x}_1+b)$ and

$(c{x}_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^{\prime }$ similarly:

$f_j^{\prime }(0,x_{i+1},\cdots ,x_v),f_j^{\prime }(1,x_{i+1},\cdots ,x_v),\cdots ,f_j^{\prime }(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^{\prime }$ some

$d+1$ times, we will only evaluate it twice:

$f_j^{\prime }(0,x_{i+1},\cdots ,x_v)$ and

$f_j^{\prime }(1,x_{i+1},\cdots ,x_v)$. Then, we use the identity to get all the other evaluations:

• $f_j^{\prime }(2,x_{i+1},\cdots ,x_v)=-1\times f_j^{\prime }(0,x_{i+1},\cdots ,x_v)+2\times f_j^{\prime }(1,x_{i+1},\cdots ,x_v)$
• $f_j^{\prime }(3,x_{i+1},\cdots ,x_v)=-2\times f_j^{\prime }(0,x_{i+1},\cdots ,x_v)+3\times f_j^{\prime }(1,x_{i+1},\cdots ,x_v)$
• $\cdots$
• $f_j^{\prime }(d,x_{i+1},\cdots ,x_v)=-(d+1)\times f_j^{\prime }(0,x_{i+1},\cdots ,x_v)+d\times f_j^{\prime }(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\ast v_1=[42\ast a,42\ast b,42\ast 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
    $eval{s}_0=[f_0^{\prime }(0,x_{i+1},\cdots ,x_v),\cdots ,f_m^{\prime }(0,x_{i+1},\cdots ,x_v)]$
  • Let
    $eval{s}_1=[f_0^{\prime }(1,x_{i+1},\cdots ,x_v),\cdots ,f_m^{\prime }(1,x_{i+1},\cdots ,x_v)]$
  • Update
    $s_{acc}$
    • $s_{acc}[0]+=g(eval{s}_0)$
    • $s_{acc}[1]+=g(eval{s}_1)$
    • $s_{acc}[2]+=g(2\ast eval{s}_1-eval{s}_0)$
    • $s_{acc}[3]+=g(3\ast eval{s}_1-2\ast eval{s}_0)$
    • $\cdots$
    • $s_{acc}[d]+=g(d\ast eval{s}_1-(d-1)\ast eval{s}_0)$
• Return
  $s_{acc}$