Multi-linear extension
Justin Thaler’s descritpion of sum-check protocol
Following the definition from Justin Thaler (you can find why the multilinear extension of a indexed table is unique)
Let \(\mathbb{F}\) be any finite field, and let \( f : \{0,1\}^v \rightarrow \mathbb{F} \) be any function mapping the \( v \)-dimensional Boolean hypercube to \(\mathbb{F}\). A \( v \)-variate polynomial \( g \) over \(\mathbb{F}\) is said to be an extension of \( f \) if \( g \) agrees with \( f \) at all Boolean-valued inputs, i.e., \( g(x) = f(x) \) for all \( x \in \{0,1\}^v \).
an example:
| x | y | f |
| 0 | 0 | \(f(0,0)\) |
| 0 | 1 | \(f(0,1)\) |
| 1 | 0 | \(f(1,0)\) |
| 1 | 1 | \(f(1,1)\) |
The multi-linear extension of \(f\) can be expressed as:
$$\tilde f=f(0,0)(1-x)(1-y)+f(0,1)(1-x)y+f(1,0)x(1-y)+f(1,1)xy$$
check this post about the common transforms used in multi-variate polynomials
Turn a function in binary field to its multilinear extension.
let \(\mathcal{G}\) be a function in binary field:
$$\mathcal{G}(x), x \in \{0,1\}^m$$
its multi-linear extension can be presented as:
$$\mathcal{G}(r_1,…,r_m)=\sum\limits_{x\in\{0,1\}^m}\mathcal{G}(x)\prod\limits^{m}_{i=1}\underbrace{(r_i\cdot x_i + (1-r_i)(1-x_i))}_{x_i=0 \rightarrow 1-r_i, x=1 \rightarrow r_i }$$
Or another equivalent expression:
$$\mathcal{G}(r_1,…,r_m)=\sum\limits_{x\in\{0,1\}^m}\mathcal{G}(x)eq(x,r)$$
emphasize:
\(r_i \in \mathbb{F}\)
\(x \in \{0,1\}^m\)
\(x_i \) is 0 or 1
Notes
sum-check protocol deals with binary inputs. but the polynomial \(g\) has inputs of field elements. \(g\) can be a multi-linear extension of an indexed table, or itself just directly a function defined on fields. the difference is the degree of the sumcheck: if \(g\) is not a multi-linear extension of an indexed table, it might has higher degree on variables, then each round, the prover sends a higher degree polynomial to the verifier.
as specified in Justin’s note
In every layer of GKR, a sum-check is used, which means all the inputs need to be binary.
The multi linear extension is for \(P(x_1,…,x_n)\), not for the sum.
The protocol
Input:
– A multilinear polynomial \( g(x_1, x_2, \ldots, x_n) \) of degree at most 1 in each variable over a finite field \(\mathbb{F}\) (this degree requirement is only for the case the polynomial is a multi-linear extension of a indexed table).
– A value \( S \in \mathbb{F} \) that is claimed to be the sum of \( g \) over all possible binary inputs, i.e., \( S = \sum_{x_1 \in \{0,1\}} \sum_{x_2 \in \{0,1\}} \cdots \sum_{x_n \in \{0,1\}} g(x_1, x_2, \ldots, x_n) \).
Protocol:
Initialize:
Let \( i = 1 \).
Prover’s Claim:
The Prover claims that \[ S = \sum_{x_1 \in \{0,1\}} \sum_{x_2 \in \{0,1\}} \cdots \sum_{x_n \in \{0,1\}} g(x_1, x_2, \ldots, x_n). \]
While \( i \leq n \):
Prover computes the univariate polynomial \[ h_i(z) = \sum_{x_{i+1} \in \{0,1\}} \cdots \sum_{x_n \in \{0,1\}} g(r_1, \ldots, r_{i-1}, z, x_{i+1}, \ldots, x_n) \] and sends \( h_i(z) \) to the Verifier.
– Verifier: Checks that \[ h_i(0) + h_i(1) = h_{i-1}(r_{i-1}), \] where \( h_0 = S \) and \( r_{i-1} \) is the value chosen by the Verifier in the previous round. If the check fails, the Verifier rejects and terminates.
– Verifier: Picks a random \( r_i \in \mathbb{F} \) and sends \( r_i \) to the Prover.
– Prover: Sets \( g(r_1, \ldots, r_{i-1}, r_i, x_{i+1}, \ldots, x_n) \) as the new polynomial and continues to the next iteration.
– Increment \( i \).
Final Check: After \( n \) rounds, the Prover sends the value \( g(r_1, r_2, \ldots, r_n) \) to the Verifier.
– Verifier: Evaluates \( g(r_1, r_2, \ldots, r_n) \) directly and checks if it matches the value sent by the Prover.
– If the values match, the Verifier accepts.
– Otherwise, the Verifier rejects.
Notes
The above sum-check protocol directly start with a multilinear polynomial over finite field \(\mathbb{F}\). While many other description will start with a polynomial defined over binary hypercube, i.e., \(x_n\in\{0,1\}\), the multilinear extension of the polynomial will have notation as \(\tilde g(x_1, x_2, \ldots, x_n).\)
In every round, the polynomial sent by the prover to the verifier is a one degree polynomial \(h(z)=\alpha+\beta z\), \(\alpha\) and \(\beta\) are coefficients.
Given an example of 3 variants linear polynomial \(f(x,y,z)\), it has a universal representation as
$$g(X,Y,Z)=a_0+a_xX+a_yY+a_zZ+a_{xy}XY+a_{xz}XZ+a_{yz}YZ+a_{xyz}XYZ$$
Then in the first round, the polynomial sent by prover to the verifier is:
\(h(t)=g(t,0,0)+g(t,0,1)+g(t,1,0)+g(t,1,1)=(4a_x+2a_{xz}+2a_{xy}+a_{xyz})t+4a_0+2a_y+2a_z+a_{yz}\)
i.e.,
$$\alpha=4a_x+2a_{xz}+2a_{xy}+a_{xyz}$$
$$\beta=4a_0+2a_y+2a_z+a_{yz}$$
Cost:
in total, it is n rounds, n represent the size of binary hypercube, n binary bits.
if \(g\) is a multi-linear extension of a indexed table , the size of the table is \(2^n\)
the cost is logarithmic to the size of the table, each round, a hash, a communication between prover and verifier, the size of the communication is linear to the degree of the variable. \(deg(x_i)+1\)
note how the size of the field would effect the cost of the communication. if smaller field is used, and extension field has degree \(q\), then each round, the communication cost is \(q \cdot \mathsf{deg}(x_i)\)
At the end of the sumcheck, verifier needs to compute \(g(r_0,r_1,…,)\)
A PCP, multi-variate polynomial commitment scheme can be used to verify the evaluation of \(g(r_0,r_1,…,)\)