GKR Explained: From Cubes to Curves
Soundness via Sum-Check, Folding, and Multilinear Extensions

1. The Sum-Check Protocol
2. The Multilinear Extensions
3. The GKR Protocol

NOTE: This write-up accompanies a compact C++ implementation (~1k LOC) of GKR under dense-circuit MLEs:

1. The Sum-Check Protocol

1.1. Multivariate Polynomials

\(k\)-variate polynomial \(f(x_1,...,x_k)\) over a finite field \(\mathbb F_p\)

Variable degree \(d\): max degree of each variable
Multilinear polynomial: \(d = 1\)

E.g., \(f(x_1, x_2) = 5 + 4x_1 + 3x_2 + 2x_1x_2 \)

The size of a multilinear polynomial (# of coefficients/monomials): \(N = 2^k \) (Binary Tree)
Size of multivariate polynomial

E.g., \(f(x_1, x_2) = 1 + x_2 + {x_2}^2 + x_1 + {x_1}{x_2} + {x_1}{x_2}^2 + {x_1}^2{x_2} + {x_1}^2{x_2}^2\)

The size of a multivariate polynomial (# of coefficients/monomials): \(N = (d+1)^k \) (d-leaves Tree)

1.2. The Sum-check Problem

\[ S = \sum_{b_1,...,b_k \in \{0,1\}}{f(b_1,...,b_k)} \] Where \(f\) is a multivariate polynomial, \(S\) is the sum of boolean hypercube evaluations of \(f\)

E.g., \(f(x_1, x_2) = 5 + 4x_1 + 3x_2 + 2x_1x_2 \to f(0, 0) = 5, f(0, 1) = 8, f(1, 0) = 9, f(1, 1) = 14 \to S = 36\)

Number of evaluations in the sum: \(2^k\)
Time to compute each evaluation: \(T\)
Total time to compute the sum: \(2^k \times T\)

1.3. The Sum-check Protocol

The sum-check protocol is an interactive proof protocol to prove the correctness of a sum-check problem.

Initial: P send the Claimed \(S\)

\[ S = \sum_{b_1,...,b_k \in \{0,1\}}{f(b_1,...,b_k)} \]
First Round: P construct univariate polynomial \(f_1 \in \mathbb F\) to V
\[ f_1(x_1) = \sum_{b_2,...,b_k \in \{0,1\}}{f(x_1,b_2,...,b_k)} \]
- V checks if \(S = f_1(0) + f_1(1)\)
- V then picks a random value \(r_1 \in \mathbb F \) and sends to P
Now in the next round, P need to prove the reduced sum-check problem \(S_1\) with \(x_1\) being replaced by fixed \(r_1\): \[ S_1 = f_1(r_1) = \sum_{b_2,...,b_k \in \{0,1\}}{f(r_1,b_2,...,b_k)} \]

1.3.1. Second Round: P construct univariate polynomial \(f_2 \in \mathbb F\) to V

\[ f_2(x_2) = \sum_{b_3,...,b_k \in \{0,1\}}{f(r_1,x_2,b_3...,b_k)} \]

V checks if \(S_1 = f_2(0) + f_2(1)\)
V then picks a random value \(r_2 \in \mathbb F \) and sends to P

Now in the next round, P need to prove the further reduced sum-check problem \(S_2\) with \(x_1, x_2\) being replaced by fixed \(r_1, r_2\): \[ S_2 = f_2(r_2) = \sum_{b_3,...,b_k \in \{0,1\}}{f(r_1,r_2,b_3,...,b_k)} \]

1.3.2. i-th Round: P construct univariate polynomial \(f_i \in \mathbb F\) to V

\[ f_i(x_i) = \sum_{b_{i+1},...,b_k \in \{0,1\}}{f(r_1,...,r_{i-1},x_i,b_{i+1}...,b_k)} \]

V checks if \(S_{i-1} = f_i(0) + f_i(1)\)
V then picks a random value \(r_i \in \mathbb F \) and sends to P

Now in the next round, P need to prove the further reduced sum-check problem \(S_i\) with \((x_1,...,x_i)\) being replaced by fixed \((r_1,...,r_i)\): \[ S_i = f_i(r_i) = \sum_{b_{i+1},...,b_k \in \{0,1\}}{f(r_1,...,r_i,b_{i+1}...,b_k)} \]

1.3.3. The Last Round (round k): P construct univariate polynomial \(f_k \in \mathbb F\) to V

\[ f_k(x_k) = f(r_1,...,r_{k-1},x_k) \]

V checks if \(S_{k-1} = f_k(0) + f_k(1)\)
V then picks a random value \(r_k \in \mathbb F \) and performs the final check

\[ f_k(r_k) \stackrel{?}{=} f(r_1,...,r_k) \] This means V is now perform computation on its own to check that whether the evaluation of \(r_k\) on constructed \(f_k\) by P is equal to the evaluation of \((r_1,...,r_k)\) on the multivariate polynomial \(f\) in the sum-check problem.

The soundness comes from the final check, if \(f_k\) is incorrectly constructed by a dishonest P, then the probability that \(f_k(r_k) = f(r_1,...,r_k)\) is only \(\frac{d}{|\mathbb F |}\), where \(d\) is the total degree of polynomial \(f\) over finite field \(\mathbb F\), according to the DeMillo-Lipton-Schwartz-Zippel lemma, which is unconditionally secure without any crypto assumption.

2. The Multilinear Extensions

2.1. Multilinear Polynomial from Coefficients

For an n-variate multilinear polynomial, the classic "coefficients" view stores the \(2^n\) numbers \(c_b\) array. \[ g(x_1, \dots, x_n) = \sum_{b \in \{0,1\}^n} c_b \prod_{i=1}^n x_i^{b_i} \] Where \(b = (b_1,...,b_n)\) is an n-bit vector indexing the monomials of a multilinear polynomial (i.e., \((b_i \in \{0,1\})\) is the i-th bit of the vector \(b\)), and because each exponent is 0 or 1, every variable appears at most linearly in any term.

In cryptography, multilinear polynomials often operating in a large finite field, which cannot include real numbers. (Predictable, efficient to evaluate & manipulate and can apply random evaluation on Schwartz-Zippel Lemma).

2.2. Multilinear Extensions from Dense Values

In Arithmetic Circuits, which is a layered directed acyclic graph (DAG) where each gate computes an arithmetic operation (typically addition or multiplication) over a finite field, and where each gate in a layer depeneds only on gates from the previous layer). When we already know the circuits's wire-values on the boolean cube we can have the evaluation view of that circuit's multilinear polynomials. \[ (v_b \stackrel{\text{def}}{=} g(b_1,...,b_n))_{b \in \{0,1\}^n} \]

Unlike monomial coefficients, the circuit layers provide these values \((v_b)\) directly through evaluation. These values suffice to compute the multilinear extension (MLE) of \(g\), i.e., evaluating \(g(x)\) at any \(x \in \mathbb{F}^n\) using folding techniques.

2.3. Folding Technique

Because \(g\) is linear in each coordinate, to evaluate it at a random point \(r = (r_1, \dots, r_n) \in \mathbb{F}^n\), fix all but one variable, say \(x_1 = t\), and let \(h(t) = g(t, x_2, \dots, x_n)\). This \(h(t)\) is degree \( \leq 1\), so \(h(t) = a \cdot t + b\) for some \(a, b \in \mathbb{F}\).

As a degree-1 polynomial in \( t \), \( h(t) = a \cdot t + b \) for some \( a, b \in \mathbb{F} \). Evaluating at the Boolean points gives \( h(0) = b \) and \( h(1) = a + b \), so \( a = h(1) - h(0) \) and: \[h(t) = (1 - t) \cdot h(0) + t \cdot h(1).\]

So for \(g(t) \in \mathbb F\), we have: \[ g(t,x_2,...,x_n) = (1 - t) \cdot g(0,x_2,...,x_n) + t \cdot g(1,x_2,...,x_n) \]

Repeating this per variable shrinks the evaluation table: \( 2^n \to 2^{n-1} \to \dots \to 1 \), yielding \( g(r) \).

Because \(g\) is degree-1 in every coordinate, we can evaluate it by a sequence of 1-dimensional linear interpolations:

dimension   n:   size 2^n     -- fold along x1 -->
dimension n-1:   size 2^{n-1} -- fold along x2 -->
...
dimension   1:   size 2       -- fold along xn -->
dimension   0:   size 1       (the answer)

Cost: One addition and one multiplication per value per fold, totaling \( n \cdot 2^n \) operations—efficient as it only combines existing gate values.

2.4. Thaler'13: Linear-time Sum-Check via Folding Table

Here we introduce the linear-time sum-check prover of Thaler (2013), which maintains a folded slice of the Boolean cube across rounds to reduce total prover time from \(O(n \cdot 2^n)\) to \(O(2^n)\) – linear to the circuit size.

Recall in round \(k\), sum-check needs the univariate \[ p_k(x)\;=\;\sum_{\text{remaining } \{0,1\}^{\,n-k}}\! g\big(x_1=r_1,\dots,x_{k-1}=r_{k-1},\,x_k=x,\,\ldots,\,x_n\big). \] Because \(g\) is multilinear, \(\deg p_k\le 1\), so \(p_k(x)=c_0+c_1 x\).

By maintaining a working table \(T^{(k-1)}\) that stores the values of \(g\) after fixing \((x_1 = r_1, ..., x_{k-1} = r_{k-1})\), we can reuse computations in round \(k\): The \(k\)-th coordinate is the least-significant bit (LSB) of the index: for each \(i\), entries \(2i\) and \(2i+1\) share the same suffix \(x_{k+1},...,x_n\) with \(x_k\) = 0 and \(x_k\) = 1, respectively. Initially \(T^{(0)}\) is the dense cube \(\big(v_b\big)_{b\in\{0,1\}^n}\).

Build \(p_k(x) = c_0 + c_1x\) from \(T^{(k-1)}\): Here \(c_0 = p_k(0)\) and \(c_1 = p_k(1) - p_k(0)\). With the LSB indexing above,

\[ c_0 = \sum_{i}T^{(k-1)}[2i], \qquad c_1 = \sum_{i}(T^{(k-1)}[2i+1] - T^{(k-1)}[2i]) \]

Consume the new fix \(x_k = r_k\): After the verifier sends \(r_k\), fold along coordinate \(k\) to obtain \(T^{(k)}\) of half the length:

\[ T^{(k)}[i] = (1 - r_k)T^{(k-1)}[2i] + r_kT^{(k-1)}[2i+1] \]

Each round is a single linear scan of a shrinking table of sizes \(2^n,2^{n-1},\dots,1\). Hence total time \(O(2^n)\), with memory shrinking every round.

2.5. Concrete Example

Folding is just repeated affine interpolation, turning the vector \(v\) into a single weighted sum, for \(n = 3 \), let:

\begin{aligned} r := (r_1,r_2,r_3) \in \mathbb F^3, \\ v := (v_{000},v_{001},v_{010},v_{011},v_{100},v_{101},v_{110},v_{111}), \\ \end{aligned}

Step 1 (fold \(x_1\)) size 4:

\begin{aligned} g_{00} &= (1-r_1)\,v_{000} + r_1\,v_{100},\\ g_{01} &= (1-r_1)\,v_{001} + r_1\,v_{101},\\ g_{10} &= (1-r_1)\,v_{010} + r_1\,v_{110},\\ g_{11} &= (1-r_1)\,v_{011} + r_1\,v_{111},\\[6pt] \end{aligned}

Step 2 (fold \(x_2\)) size 2:

\begin{aligned} h_{0} &= (1-r_2)\,g_{00} + r_2\,g_{10},\\ h_{1} &= (1-r_2)\,g_{01} + r_2\,g_{11},\\[6pt] \end{aligned}

Step 3 (fold \(x_3\)) size 1:

\begin{aligned} g(r_1,r_2,r_3) &= (1-r_3)\,h_{0} + r_3\,h_{1}. \end{aligned}

2.6. Concrete Example Thaler'13

Let \(n=3\) and \(v=(v_{000},v_{001},v_{010},v_{011},v_{100},v_{101},v_{110},v_{111})\).

2.6.1. Round 1 (variable \(x_1\)).

Current table \(T=v\). Then \[ c_0 = \underbrace{v_{000}+v_{001}+v_{010}+v_{011}}_{\text{all with } x_1=0},\qquad c_1 = \underbrace{(v_{100}-v_{000})}_{\text{pair }(000,100)} + \underbrace{(v_{101}-v_{001})}_{\text{pair }(001,101)} + \underbrace{(v_{110}-v_{010})}_{\text{pair }(010,110)} + \underbrace{(v_{111}-v_{011})}_{\text{pair }(011,111)}. \] Send \(p_1(x_1)=c_0+c_1x_1\) and receive \(r_1\).

Fold \(x_1=r_1\):

Replace each pair by \((1-r_1)v_{0}+r_1 v_{1}\) to get \(T^{(1)}=(g_{00},g_{01},g_{10},g_{11})\)

2.6.2. Round 2 (variable \(x_2\)).

\[ c_0=g_{00}+g_{01},\qquad c_1=(g_{10}-g_{00})+(g_{11}-g_{01}). \] Send \(p_2(x_2)\), receive \(r_2\), fold to \(T^{(2)}=(h_0,h_1)\).

2.6.3. Round 3 (variable \(x_3\)).

\[ c_0=h_0,\qquad c_1=h_1-h_0. \] Send \(p_3(x_3)\), receive \(r_3\). The final fold gives \(g(r_1,r_2,r_3)\).

Each step is one linear pass over the current table; no recomputation.

3. The GKR Protocol

The GKR protocol is used to build a delegation of arbitrarily computations, which can be represented by (universal) circuits in cryptography, to achieve this, the authors of the paper try really hard to write the output of the circuit \(y\) as the sumcheck equation of the input \(x\).

3.1. Multilinear Indicator Polynomial

The multilinear extension is the unique polynomial: \[ g(x_1,\dots ,x_n) =\sum_{b\in\{0,1\}^n} v_b\; \prod_{i=1}^{n}(1-x_i)^{\,1-b_i}\,x_i^{\,b_i}. \] (In dense cases (e.g., gate-value arrays), \( v_b \) is nonzero for most \( b \); in sparse cases (e.g., circuit wirings), most \( v_b = 0 \), so the sum is efficiently over only nonzero terms.) Each boolean assignment \(v_{b}\) contributes with the weight \(\chi_b\):

\[ \chi_b(x_1,\dots ,x_n) =\prod_{i=1}^{n}(1-x_i)^{\,1-b_i}\,x_i^{\,b_i} \]

\(\chi_b\) is called Multilinear Indicator Polynomial for the vertex \(b\) (gate value at index \(b\)), a multivariate delta function: \( \chi_b(b') = 1 \) if \( b' = b \), else 0 on the hypercube. Summing these basis polynomials, scaled by gate values, extends the Boolean table to all of \( \mathbb{F}^n \). This Lagrange form is the "reverse" of folding: both recurse on the fact that fixing all but one coordinate makes the polynomial affine (degree-1). Folding collapses values to evaluate at a point; indicators build the polynomial from values.

3.2. Building GKR Circuit Wiring MLEs

In GKR protocol, the relationship between output layer \(w_o\) and input layer \(w_i\) with circuit wirings can be represented as:

\[ w_o(a, b, c) = \sum_{a,b,c \in \{0,1\}^{s_a + 2s_{bc}}} add(a, b, c) \cdot ({w_i}(b) + {w_i}(c)) + {mul}(a, b, c) \cdot {w_i}(b) \cdot {w_i}(c) \]

The wiring MLEs \( \tilde{add} \) and \( \tilde{mul} \) encode the circuit structure and are built iteratively using the Multilinear Indicator Polynomial.

The \(v_b\) can be any field elements (e.g., gate values, weights or predicates). But in GKR's dense wiring polynomials (\(\tilde{add}\) and \(\tilde{mul}\)), the value of \(v\) is typically \(0/1\) (1 if a gate connects output \( a \) to inputs \( b,c \); or a count if multiple).

In GKR protocol, for a layer \(i\) with:

Output address bits \(a \in \{0, 1\}^{s_a} \) (these index positions in layer \(i\)).
Input address bits \(b, c \in \{0, 1\}^{s_{bc}}\) (two fan-in wires from layer \(i-1\)).

As we mentioned before, the wiring predicates can be defined like this:

\(\text{add}_i(a, b, c)\): equals the number of ADD gates in layer \(i\) whose output index is \(a\) and whose inputs are \((b,c)\).
\(\text{mul}_i(a, b, c)\): same for MUL gates.

These are 0/1-valued functions on the Boolean cube \(\{0, 1\}^{s_a + 2s_{bc}}\), its multilinear extensions can be obtained with the usual MLE formula:

\[ \widetilde{add}(a, b, c) = \sum_{\text{ADD gates } g} \chi_{g.\text{out}}(a) \cdot \chi_{g.\text{left}}(b) \cdot \chi_{g.\text{right}}(c) \]

Note: This is the sparse form of the general MLE, summing over gates only where \( v_{(a,b,c)} = \) count \(> 0\), as connections are sparse on hypercube.

(analogous for \(\tilde{mul}\) ).

In the wiring MLEs (e.g.,\( \tilde{add} \) or \( \tilde{mul} \)), the indicator \( \chi_{g.out}(a) \) for output index \( o_{id} \) (binary string of length \( s_a \)) is:

\[ \chi_{g.out}(a) = \prod_{j=0}^{s_a-1} \begin{cases} a_j & \text{if } o_{id}[j] = 1, \\ 1 - a_j & \text{if } o_{id}[j] = 0. \end{cases} \]

From the circuit wiring view, for Boolean \(a\), this acts as a Kronecker delta \( \delta_{o_{id}, a} \): 1 if \( o_{id} = a \), else 0. It "switches on" only when indices match, encoding the circuit's structure by selecting exact gate connections in the MLE sum.

3.3. Local Sum Check Protocol in GKR Circuit Layer

Recall in Sum-check protocol, our goal is to prove:

\[ S = w_o(x) = \sum_{x_1,...,x_{s} \in \{0, 1\}} f(x_1,...,x_{s}) \]

For this, we've already built the Multilinear Extensions \(\tilde{f}\) for \(x \in \{\mathbb F \}^s \). (\(\tilde{w_i}(b), \tilde{w_i}(c)\) can be initialized from the gate values' array during the Prover circuit evaluation process) By leveraging the power of randomness in low-degree polynomial, we are able to prove the sum \(S\) interactively.

3.3.1. Fixes the Target Polynomial on \(r_a\)

The sum-check protocol run at each GKR layer must target a fixed low-degree polynomial before the interaction begins. For that, we need freeze the output address by sampling \(r_a \in \mathbb F\) up front that pins layer polynomial down and prevents the prover from adapting it mid-protocol.

\[ \tilde{w}_o(r_a) = \sum_{b,c \in \{0,1\}^{2s_{bc}}} \widetilde{add}(r_a, b, c) \cdot (\tilde{w_i}(b) + \tilde{w_i}(c)) + \widetilde{mul}(r_a, b, c) \cdot \tilde{w_i}(b) \cdot \tilde{w_i}(c) \]

Specializing the wiring MLEs at \(a = r_a\) converts them into functions of \((b,c)\) alone. Wirings can be represented by their dense value table \((\alpha^{add}, \alpha^{mul})\) over the Boolean cube, and then used to build dense MLEs:

\[ \boxed{% \begin{aligned} \alpha^{add}[b ∥ c] = \widetilde{\mathrm{add}}(r_a,b,c) &= \sum_{\text{ADD gates g}} \chi_{g.out}(r_a)\, \chi_{g.left}(b)\,\chi_{g.right}(c),\\[2mm] \end{aligned}} \]

and analogously \(\alpha^{mul}\). Here \(\chi_{g.out}(r_a)\) is the multilinear indicator for the output bits of gate \(g\), evaluated at the field point \(r_a\); on Boolean \(a\) it is a Kronecker delta, but at random \(r_a\) it is a weight in \(\mathbb F\). For a fixed Boolean \((b, c)\), the factors \(\chi_{g.left}(b), \chi_{g.right}(c)\) select exactly those gates whose input addresses equal \((b, c)\), so \(\alpha^{add}[b ∥ c]\) is the sum of \(\chi_{g.out}(r_a)\) over all such ADD gates (and similarly for MUL). We then instantiate the reduced wiring polynomials as MLEs from these tables.

3.3.2. Local Sum-check on \((b, c)\) after fixing \(a = r_a\).

Once we fix the output address \(a = r_a\), the wiring MLEs become functions of the input addresses only: \[ A(b,c) := \widetilde{\mathrm{add}}(r_a,b,c),\qquad M(b,c) := \widetilde{\mathrm{mul}}(r_a,b,c), \]

Both multilinear in \((b,c)\in\mathbb{F}^{2s}\). Let \(w(\cdot)\) be the MLE of the previous layer’s wire-values. The target function for sum-check is

\[ F(b,c) \;=\; A(b,c)\cdot\bigl(w(b)+w(c)\bigr)\;+\;M(b,c)\cdot w(b)\,w(c), \]

the claimed sum is

\[ H \;=\; \sum_{(b,c)\in\{0,1\}^{2s}} F(b,c). \]

In the \(k\)-th round the verifier fixes all but the current variable \(x\in\{b_j\}\cup\{c_j\}\) and asks the prover for the univariate polynomial \(p(x)\)

\[ p(x) \;=\; \sum_{\text{remaining }(b,c)} F(\cdot). \]

Because \(A,M\) are linear in each coordinate and \(w(b),w(c)\) are linear in the relevant coordinate, we have \(\deg p \le 2\):

\(M(b, c) \cdot w(b) \cdot w(c) \) is (linear) \(\cdot\) (constant or linear) \(\cdot\) (constant or linear), because \(w(b)\) and \(w(c)\) are never \(x\)-dependent at the same time:
- If \(x\in b\): \(\deg_x\big(A\cdot w(b)\big)\le 2\), \(\deg_x\big(A\cdot w(c)\big)\le 1\), \(\deg_x\big(M\cdot w(b)\cdot w(c)\big)\le 2\).
- If \(x\in c\): symmetric (swap \(b\) and \(c\)).
- \(\to\) \(M(b, c) \cdot w(b) \cdot w(c) \) is quadratic in \(x\).

Writing every linear factor as \((1-x)u_0 + x\,u_1\), the identity

\[ \bigl((1-x)a_0+x a_1\bigr)\bigl((1-x)w_0+x w_1\bigr) = a_0w_0 + (-2a_0w_0+a_1w_0+a_0w_1)x + (a_0w_0-a_1w_0-a_0w_1+a_1w_1)x^2, \]

shows that the contributions of \(A\cdot w(b)\), \(A\cdot w(c)\), and \(M\cdot w(b)\cdot w(c)\) to the coefficients \((c_0,c_1,c_2)\) of \(p(x)=c_0+c_1x+c_2x^2\) are simple sums of the four endpoint products \((a_0w_0, a_0w_1, a_1w_0, a_1w_1)\) (and linear terms when one factor is constant).

3.3.3. GKR Layer: Quadratic \(p(x)=c_0+c_1x+c_2x^2\) via the Same DP Idea

Here we again keep shrinking tables for the remaining cube in the current round:

\(T_A,T_M\) for \(A,M\): current dense tables for \(A\) and \(M\) after all consumed folds.
\(T_{w_b}\) for \(w(b)\) (when the next variable lies in \(b\)).
\(T_{w_c}\) for \(w(c)\) (when the next variable lies in \(c\)).

While the verifier fixes \(x (b, c)\) to \(r\), all affected tables are folded, same idea with Thaler'13: Linear-time Sum-Check via Folding Table.

Now suppose the next unfixed variable \(x\) is in \(b\). Write each linear factor as \((1-x)\,u_0 + x\,u_1\), which is a two-point Lagrange interpolation where: \[ u_0 := f(0)\ \text{(value with }x=0\text{)}, \qquad u_1 := f(1)\ \text{(value with }x=1\text{)}. \]

Only \(b\)-endpoints depend on \(x\); \(c\)-quantities are constants this round. Expanding shows contributions to \(p(x)=c_0+c_1x+c_2x^2\):

\begin{aligned} A\cdot w(b):\quad & c_0 \mathrel{+}= \sum A_0 w_0, c_1 \mathrel{+}= -2\sum A_0 w_0 + \sum A_1 w_0 + \sum A_0 w_1,\\ & c_2 \mathrel{+}= \sum A_0 w_0 - \sum A_1 w_0 - \sum A_0 w_1 + \sum A_1 w_1;\\ A\cdot w(c):\quad & c_0 \mathrel{+}= \sum A_0\,w(c), c_1 \mathrel{+}= -\sum A_0\,w(c) + \sum A_1\,w(c), c_2 \mathrel{+}= 0;\\ M\cdot w(b)w(c):\quad & c_0 \mathrel{+}= \sum M_0\,w_0\,w(c),\\ & c_1 \mathrel{+}= -2\sum M_0\,w_0\,w(c) + \sum M_1\,w_0\,w(c) + \sum M_0\,w_1\,w(c),\\ & c_2 \mathrel{+}= \sum M_0\,w_0\,w(c) - \sum M_1\,w_0\,w(c) - \sum M_0\,w_1\,w(c) + \sum M_1\,w_1\,w(c). \end{aligned}

All sums are over the remaining \((b,c)\) cube, with the current \(x\) fixed at \(0\) or \(1\).

3.4. Lagrange Interpolation

After running the \(2s\) round sum-check protocol on

\[ F(b,c)\;=\;A(b,c)\cdot\bigl(w(b)+w(c)\bigr)\;+\;M(b,c)\cdot w(b)\,w(c), \]

with the output address fixed to a random \(a=r_a\), the verifier finishes the sum-check with:

Concrete field points \(b^\star,c^\star\in\mathbb F^{s}\) determined by the \(2s\) fixed coordinates.
A scalar \(S^\star\in\mathbb{F}\) that should equal \(F(b^\star,c^\star)\) for an honest prover.
The ability to compute \(A(r_a,b^\star,c^\star)\) and \(M(r_a,b^\star,c^\star)\) directly from the circuit description.

The obstacle is that the verifier cannot (and will not) directly evaluate \(w(b^\star)\) and \(w(c^\star)\). The standard GKR trick is to reduce these two unknowns into one by walking along the line between \(b^\star\) and \(c^\star\).

3.4.1. Define the line and the univariate restriction

Let \[ u(t) \;=\; (1-t)\,b^\star + t\,c^\star \in \mathbb F^s, \qquad q(t) \;=\; w(u(t)). \]

Because \(w\) is multilinear in \(s\) coordinates and each coordinate of \(u(t)\) is affine in \(t\), the univariate q has degree \(\deg q \le s\). Note that:

\[ q(0)=w(b^\star) \qquad q(1)=w(c^\star) \]

3.4.2. Commit to a degree-\(\le s\) curve

The verifier chooses any \(s+1\) distinct nodes \(x_0,\dots,x_s\in\mathbb F\) (e.g., \(x_j=j\)) and asks the prover for the vector evaluations

\[ y_j \stackrel{?}{=} q(x_j)=w(u(x_j)), \qquad j=0,\dots,s. \]

These \(s+1\) values uniquely determine a degree-\(\le s\) polynomial.

3.4.3. Lagrange Polynomial

We want basis polynomials \(\ell_0(t),\dots,\ell_s(t)\) of degree \(\le s\) on distinct nodes \(x_0,\dots,x_s\in\mathbb{F}\) with the Kronecker-delta property \[ \ell_j(x_k) = \delta_{jk} = \begin{cases} 1, & \text{if } k=j, \\ 0, & \text{if } k\neq j, \end{cases} \qquad \text{for all } j,k\in\{0,\dots,s\}. \]

A polynomial vanishing at all nodes except \(x_j\) is \(\prod_{m\ne j}(t-x_m)\).

Normalize it to take value \(1\) at \(t=x_j\), we get the definition of Lagrange polynomial:

\[ \ell_j(t) \;=\; \prod_{\substack{m=0\\ m\ne j}}^{s} \frac{t-x_m}{x_j-x_m}. \]

From Wikipedia: Although named after Joseph-Louis Lagrange, who published it in 1795, the method was first discovered in 1779 by Edward Waring. It is also an easy consequence of a formula published in 1783 by Leonhard Euler.

Kronecker-delta vs. Lagrange polynomial (same idea, different domains).

Similarity "delta":

Polynomial evaluate to \(1\) at their own node and \(0\) at all others. enable reconstruction of a polynomial from its values at those nodes.

Different domain/degree:

Lagrange (1-D, arbitrary nodes): On a set \(\{x_0,\dots,x_s\}\) in one dimension, \(\{\ell_j\}\) reconstructs a univariate degree-\(\le s\) polynomial from \(s{+}1\) samples.

Kronecker/multilinear indicators (n-D Boolean grid): On the Boolean hypercube \(\{0,1\}^n\), \[ \chi_b(x_1,\dots,x_n) \;=\; \prod_{i=1}^{n}(1-x_i)^{1-b_i}\,x_i^{\,b_i}, \qquad b\in\{0,1\}^n, \] forms a basis for multivariate polynomials that are degree \(\le 1\) in each coordinate (multilinear). It reconstructs from \(2^n\) vertex values.

3.4.4. Lagrange Interpolation

The Lagrange interpolation is a method for constructing a unique polynomial that passes through a given set of data points with the lowest order.

and the verifier defines the committed univariate polynomial:

\[ \widehat q(t) \;=\; \sum_{j=0}^{s} y_j\,\ell_j(t). \]

This binds the prover to a single degree-\(\le s\) curve before the verifier reveals any fresh randomness.

3.5. GKR: Reduction Between Layers

Set \(A:=A(r_a,b^\star,c^\star)\) and \(M:=M(r_a,b^\star,c^\star)\), which the verifier can compute. The verifier checks

\[ \boxed{\; A\cdot\bigl(\widehat q(0)+\widehat q(1)\bigr)\;+\;M\cdot \widehat q(0)\,\widehat q(1) \;\stackrel{?}{=}\; S^\star. \;} \]

Passing this does not prove \(\widehat q(0)=w(b^\star)\) and \(\widehat q(1)=w(c^\star)\) individually; it only proves that the pair is consistent with the already verified \(S^\star\) under the circuit's wiring weights.

3.5.1. Compression two quries to one

Sample fresh \(t^\diamond\ \in \mathbb F\) uniformly and set

\[ \boxed{\; r^{(i-1)} := u(t^\diamond) = (1-t^\diamond)\,b^\star + t^\diamond c^\star, \qquad H^{(i-1)} := \widehat q(t^\diamond). \;} \] This yields a single scalar claim for the next (input) layer: "the previous layer’s MLE equals \(H^{(i-1)}\) at the point \(r^{(i-1)}\)."

3.5.2. Soundess of this reduction

If the prover deviates so that \(\widehat q(t)\neq q(t)=w(u(t))\), then the error \(\Delta(t):=\widehat q(t)-q(t)\) is a nonzero univariate with \(\deg\Delta\le s\).

By DeMillo-Lipton-Schwartz-Zippel lemma: \[ \Pr\big[\widehat q(t^\diamond)=q(t^\diamond)\big] \;\le\; \frac{s}{|\mathbb F|}. \] Hence, except with probability \(\le s/|\mathbb F|\), the next-layer claim \(H^{(i-1)}\) is false and will be caught as the protocol proceeds (certainly at the input check).

3.5.3. Reduction between layers: invariant, step, and base case

Invariant at layer \(i\):

Let \(w_i\) be the MLE of wire values at layer \(i\) (inputs are layer \(0\), outputs layer \(L\)). At the start of layer \(i\), the verifier holds a point \(r^{(i)}\in\mathbb F^{s_i}\) and a scalar \(H^{(i)}\in\mathbb F\) with the invariant \[ H^{(i)} \;=\; \widetilde{w_i}(r^{(i)}) \quad\text{(for an honest prover).} \]

One layer step \(i\) to \(i-1\):

First, pin the output address, set \(a:=r^{(i)}\) and define \[ F_i(b,c) \;=\; A_i(a,b,c)\cdot\bigl(w_{i-1}(b)+w_{i-1}(c)\bigr) \;+\; M_i(a,b,c)\cdot w_{i-1}(b)\,w_{i-1}(c). \] The wiring identity implies \[ H^{(i)} \;=\; \sum_{(b,c)\in\{0,1\}^{2s_{i-1}}} F_i(b,c). \]

Next, run local sum-check on \(F_i\). After \(2s_{i-1}\) rounds, obtain \(b^\star,c^\star\in\mathbb F^{s_{i-1}}\) and a value \(S^\star\) that should equal \(F_i(b^\star,c^\star)\).

Local identity check and compression

Compute \(A:=A_i(a,b^\star,c^\star)\) and \(M:=M_i(a,b^\star,c^\star)\) from the circuit.
Obtain \(s_{i-1}\!+\!1\) samples of \(q(t)=w_{i-1}\big((1-t)b^\star+tc^\star\big)\), form \(\widehat q\) via Lagrange, and verify \[ A\bigl(\widehat q(0)+\widehat q(1)\bigr)+M\,\widehat q(0)\widehat q(1) \stackrel{?}{=} S^\star. \]
Draw \(t^\diamond\!\leftarrow\!\mathbb F\) and set \[ r^{(i-1)} := (1-t^\diamond)b^\star+t^\diamond c^\star, \qquad H^{(i-1)} := \widehat q(t^\diamond). \]

If the prover cheated, the handoff is wrong with probability at least \(1 - s_{i-1}/|\mathbb F|\).

Base case (input layer):

At \(i=0\), the verifier knows the input table and thus \(\widetilde{w_0}\). It checks

\[ \boxed{\;\widetilde{w_0}(r^{(0)}) \stackrel{?}{=} H^{(0)}.\;} \] Acceptance implies that all reductions were consistent; otherwise the proof is rejected.

3.6. Summary of GKR Protocol

3.6.1. Initialization at outputs.

The prover provides (or commits to) the output table. The verifier samples \(r^{(L)}\!\leftarrow\!\mathbb F^{s_L}\) and computes the initial claim \[ H^{(L)} := \widetilde{w_L}(r^{(L)}). \]

3.6.2. Final input check.

Verify \(\widetilde{w_0}(r^{(0)})=H^{(0)}\). If any deviation occurs, either a sum-check equality fails immediately, or the line test injects a bad claim that is caught later (with per-layer soundness error at most \(s_{i-1}/|\mathbb F|\)). The overall soundness error is the sum of these negligible terms.

3.6.3. Iterate down the circuit.

For \(i \in \{L,\dots,1\}\), perform the layer step \(i\to i-1\) above to obtain \((r^{(i-1)},H^{(i-1)})\).

GKR Explained: From Cubes to Curves Soundness via Sum-Check, Folding, and Multilinear Extensions

Table of Contents