We introduce the GKR protocol, explaining how it recursively verifies the correctness of layered circuit computation through the multivariate Sumcheck protocol. It elaborates on the circuit’s layered relationships, constraint construction, and verification procedures, demonstrating the efficiency and scalability of GKR in zero-knowledge proofs.
In Zero-Knowledge Proofs (ZKP), the GKR protocol (Goldwasser–Kalai–Rothblum protocol) is an efficient interactive proof system used to verify the correctness of arithmetic circuit computations. It recursively verifies the relationship between the outputs and inputs of layered circuits using the Multivariate Sumcheck Protocol, achieving correctness proofs for arbitrary multi-layer circuits while maintaining logarithmic communication complexity and sub-linear verification complexity.
Consider an arithmetic circuit:
$$C : F^{S_n} \rightarrow F$$
The circuit consists of n layers, from input layer n to output layer 0, and the layers are connected through directed edges:
We define the following notation:
\[ add^{(i)}(p, u, v) = \{1, \text{ if } p = u + v \text{ and } p \text{ is an addition gate } 0, \text{ otherwise} \]
\[ mult^{(i)}(p, u, v) = \{1, \text{ if } p = u \times v \text{ and } p \text{ is a multiplication gate } 0, \text{ otherwise} \]
To perform algebraic verification over the field F, we apply multilinear extensions (MLE) to these Boolean functions:
\[ \widetilde{add}^{(i)}, \widetilde{mult}^{(i)} : F^{s_{i} + 2s_{i+1}} \to F \]
They match the Boolean functions on 0,1 while being computable as polynomials over F.
The core task of the GKR protocol is to verify whether the outputs of each layer are consistent with the inputs of the lower layer. Let $\widetilde{w}_{i}: F^{s_{i}} \to F$ denote the multilinear extension of the output values of layer $i$, then for any $p \in G_{i}$, the following must hold:
\[ \widetilde{w}^*_i(p) = \sum_{u, v \in \{0, 1\}^{s_{i+1}}} \left[ \widetilde{add}^{(i)}(p, u, v) (\widetilde{w}^*_{i+1}(u) + \widetilde{w}^*_{i+1}(v)) + \widetilde{mult}^{(i)}(p, u, v) (\widetilde{w}^*_{i+1}(u) \cdot \widetilde{w}^*_{i+1}(v)) \right] \]
This expresses that each gate’s output equals the combination of the addition or multiplication of its input gates.
The core task of the GKR protocol is to verify whether the outputs of each layer are consistent with the inputs of the lower layer. Let $\widetilde{w}_{i}: F^{s_{i}} \to F$ denote the multilinear extension of the output values of layer $i$, then for any $p \in G_{i}$, the following must hold:
\[ \widetilde{w}^*_i(Z) = \sum_{u, v \in \{0, 1\}^{s_{i+1}}} g^{(i)}(Z, u, v) \]
where
\[ g^{(i)}(Z, u, v) = \widetilde{add}^{(i)}(Z, u, v) (\widetilde{w}^*_{i+1}(u) + \widetilde{w}^*_{i+1}(v)) + \widetilde{mult}^{(i)}(Z, u, v) (\widetilde{w}^*_{i+1}(u) \cdot \widetilde{w}^*_{i+1}(v)) \]
This identity is a multivariate polynomial identity with variables $(u, v) \in F^{2s_{i+1}}$. The Prover and Verifier can verify this sum using the Multivariate Sumcheck Protocol.
Define the full variable set $X = (u, v) \in F^{2s_{i+1}}$. We aim to verify:
\[ \sum_{X \in \{0, 1\}^{2s_{i+1}}} g^{(i)}(Z, X) = \widetilde{w}_i(Z) \]
The Sumcheck protocol allows the Prover to sequentially submit polynomials $G_1, G_2, \dots, G_{2s_{i+1}}$, each representing partial sums with respect to remaining variables.The Verifier sends random challenges $r_j$ each round, updating the target partial evaluation until, in the last round, only a single-point check of $g^{(i)}(Z, r)$ remains.
After Sumcheck concludes, the Verifier obtains point evaluations to be checked:
\[ \widetilde{w}^*_{i+1}(u), \widetilde{w}^*_{i+1}(v) \]
These two values become the inputs for the next recursive verification step. The Verifier again selects a random challenge $Z' \in F^{s_{i'}}$ , forming the new identity:
\[ \widetilde{w}^*_{i+1}(Z') = \sum_{x, y \in \{0, 1\}^{s_{i+2}}} g^{(i+1)}(Z', x, y) \]
The Sumcheck process is repeated.
When recursion reaches the bottom layer (input layer $n$), $\widetilde{w}_n(x)$ corresponds to the circuit input values, which are public or directly verifiable:
\[ \widetilde{w}_n(x) = Input(x) \]
The Verifier can check this identity directly, completing the entire verification process.
The GKR protocol recursively verifies inter-layer consistency using the multivariate Sumcheck, achieving efficient algebraic verification of arithmetic circuits. Its core features include:
This design makes the GKR protocol a fundamental algebraic component of modern zero-knowledge proof systems (such as Spartan, Halo, Nova, Lasso, Sumcheck-based zkVMs), widely applied in efficient circuit verification, scalable proof systems, and recursive proof constructions.
Subscribe to the ZKM Blog to stay updated with the latest research by ZKM.
We introduce the GKR protocol, explaining how it recursively verifies the correctness of layered circuit computation through the multivariate Sumcheck protocol. It elaborates on the circuit’s layered relationships, constraint construction, and verification procedures, demonstrating the efficiency and scalability of GKR in zero-knowledge proofs.
In Zero-Knowledge Proofs (ZKP), the GKR protocol (Goldwasser–Kalai–Rothblum protocol) is an efficient interactive proof system used to verify the correctness of arithmetic circuit computations. It recursively verifies the relationship between the outputs and inputs of layered circuits using the Multivariate Sumcheck Protocol, achieving correctness proofs for arbitrary multi-layer circuits while maintaining logarithmic communication complexity and sub-linear verification complexity.
Consider an arithmetic circuit:
$$C : F^{S_n} \rightarrow F$$
The circuit consists of n layers, from input layer n to output layer 0, and the layers are connected through directed edges:
We define the following notation:
\[ add^{(i)}(p, u, v) = \{1, \text{ if } p = u + v \text{ and } p \text{ is an addition gate } 0, \text{ otherwise} \]
\[ mult^{(i)}(p, u, v) = \{1, \text{ if } p = u \times v \text{ and } p \text{ is a multiplication gate } 0, \text{ otherwise} \]
To perform algebraic verification over the field F, we apply multilinear extensions (MLE) to these Boolean functions:
\[ \widetilde{add}^{(i)}, \widetilde{mult}^{(i)} : F^{s_{i} + 2s_{i+1}} \to F \]
They match the Boolean functions on 0,1 while being computable as polynomials over F.
The core task of the GKR protocol is to verify whether the outputs of each layer are consistent with the inputs of the lower layer. Let $\widetilde{w}_{i}: F^{s_{i}} \to F$ denote the multilinear extension of the output values of layer $i$, then for any $p \in G_{i}$, the following must hold:
\[ \widetilde{w}^*_i(p) = \sum_{u, v \in \{0, 1\}^{s_{i+1}}} \left[ \widetilde{add}^{(i)}(p, u, v) (\widetilde{w}^*_{i+1}(u) + \widetilde{w}^*_{i+1}(v)) + \widetilde{mult}^{(i)}(p, u, v) (\widetilde{w}^*_{i+1}(u) \cdot \widetilde{w}^*_{i+1}(v)) \right] \]
This expresses that each gate’s output equals the combination of the addition or multiplication of its input gates.
The core task of the GKR protocol is to verify whether the outputs of each layer are consistent with the inputs of the lower layer. Let $\widetilde{w}_{i}: F^{s_{i}} \to F$ denote the multilinear extension of the output values of layer $i$, then for any $p \in G_{i}$, the following must hold:
\[ \widetilde{w}^*_i(Z) = \sum_{u, v \in \{0, 1\}^{s_{i+1}}} g^{(i)}(Z, u, v) \]
where
\[ g^{(i)}(Z, u, v) = \widetilde{add}^{(i)}(Z, u, v) (\widetilde{w}^*_{i+1}(u) + \widetilde{w}^*_{i+1}(v)) + \widetilde{mult}^{(i)}(Z, u, v) (\widetilde{w}^*_{i+1}(u) \cdot \widetilde{w}^*_{i+1}(v)) \]
This identity is a multivariate polynomial identity with variables $(u, v) \in F^{2s_{i+1}}$. The Prover and Verifier can verify this sum using the Multivariate Sumcheck Protocol.
Define the full variable set $X = (u, v) \in F^{2s_{i+1}}$. We aim to verify:
\[ \sum_{X \in \{0, 1\}^{2s_{i+1}}} g^{(i)}(Z, X) = \widetilde{w}_i(Z) \]
The Sumcheck protocol allows the Prover to sequentially submit polynomials $G_1, G_2, \dots, G_{2s_{i+1}}$, each representing partial sums with respect to remaining variables.The Verifier sends random challenges $r_j$ each round, updating the target partial evaluation until, in the last round, only a single-point check of $g^{(i)}(Z, r)$ remains.
After Sumcheck concludes, the Verifier obtains point evaluations to be checked:
\[ \widetilde{w}^*_{i+1}(u), \widetilde{w}^*_{i+1}(v) \]
These two values become the inputs for the next recursive verification step. The Verifier again selects a random challenge $Z' \in F^{s_{i'}}$ , forming the new identity:
\[ \widetilde{w}^*_{i+1}(Z') = \sum_{x, y \in \{0, 1\}^{s_{i+2}}} g^{(i+1)}(Z', x, y) \]
The Sumcheck process is repeated.
When recursion reaches the bottom layer (input layer $n$), $\widetilde{w}_n(x)$ corresponds to the circuit input values, which are public or directly verifiable:
\[ \widetilde{w}_n(x) = Input(x) \]
The Verifier can check this identity directly, completing the entire verification process.
The GKR protocol recursively verifies inter-layer consistency using the multivariate Sumcheck, achieving efficient algebraic verification of arithmetic circuits. Its core features include:
This design makes the GKR protocol a fundamental algebraic component of modern zero-knowledge proof systems (such as Spartan, Halo, Nova, Lasso, Sumcheck-based zkVMs), widely applied in efficient circuit verification, scalable proof systems, and recursive proof constructions.
Subscribe to the ZKM Blog to stay updated with the latest research by ZKM.
