Multi-linear extension
Following the definition from Justin Thaler
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$$
Notes
sum-check protocol deals with binary inputs.
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}\).
– 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(x_1, \ldots, x_{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(x_1, \ldots, x_{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}$$