# GKR

$$ \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\ps#1{\delim\{{#1}\}} \gdef\F{\mathbb F} \gdef\set#1{\mathcal #1} \gdef\mat#1{\mathrm #1} \gdef\vec#1{\bm #1} \gdef\popcount{\mathrm{popcount}} \gdef\eq{\mathrm{eq}} \gdef\∀{\mathop{\huge ∀}\limits} \gdef\mul{\mathsf{mul}} \gdef\add{\mathsf{add}} \gdef\addc{\mathsf{add^C}} \gdef\bar#1{\overline{#1}} $$

Last year saw the publication of many interesting new proof systems that deviate from the pattern of doing plonkish-starkish arithmetization on top of a (univariate) polynomial commitment protocol. These new systems are broadly based on two mechanism: folding schemes and sumcheck+GKR. In this note I'll explore sumcheck and GKR.

GKR, introduced in 2008 respectively, is an relatively old protocol. I am not sure why it has thusfar received little attention from implementers, but I suspect it is because the proof sizes are not particularly small and the protocols are arguably more complicated. Proof size was the main metric to benchmark protocols on and here Groth16 is still king, with plonkish-starkish over KZG close behind. Now that it has become practical to recursively verify proofs this is less of a concern, a larger proof can be recursively verified in, say, a Groth16 proof and become small.

The main reason there is renewed interest in GKR protocols is prover complexity. Both Groth16 and plonkish arithmetization require the prover to do $O(n⋅\log n)$ work in the size of the computation. Through clever use of multivariate polynomials the GKR based methods can achieve $O(n)$ prover complexity.

## GKR

In GKR08 we have a $k$-layered circuit with the first layer being the input and each further layer computed from the previous one by adding or multiplying two values. For simplicity let's assume each layer has the same number of values $2^n$. We encode each layers values on a $\ps{0,1}^n$ hypercube, creating multi-linear extensions $w_i(\vec x)$ for each layer $i$. The inputs are encoded in $w_0(\vec x)$ and the output will be in $w_k(\vec x)$. The circuit is encoded using two indicator functions, they are MLEs with the following values on the hypercube $\ps{0,1}^{3⋅n}$:

$$ \begin{aligned} \mathrm{add}_i\p{\vec x, \vec y, \vec z} &= \begin{cases} 1 & w_{i+1}(\vec x) = w_i(\vec y) + w_i(\vec z)\\ 0 & \text{otherwise} \end{cases} \\ \mathrm{mul}_i\p{\vec x, \vec y, \vec z} &= \begin{cases} 1 & w_{i+1}(\vec x) = w_i(\vec y) ⋅ w_i(\vec z)\\ 0 & \text{otherwise} \end{cases} \\ \end{aligned} $$

Note that the order of $\vec y$, $\vec z$ is important to avoid double counting, there should be only one $1$ per output node, i.e. for each value of $\vec x$. With these circuit-encoding functions the values on the layers are related by

$$ w_{i+1}(\vec x) = \sum_{\vec y, \vec z ∈ \{0,1\}^n} \p{\hspace{.1em} \begin{aligned} &\phantom{+}\mathrm{add}_i\p{\vec x, \vec y, \vec z} ⋅ \p{w_i(\vec y) + w_i(\vec z)}\\ &+\mathrm{mul}_i\p{\vec x, \vec y, \vec z} ⋅ \p{w_i(\vec y) ⋅ w_i(\vec z)} \end{aligned} \hspace{.5em}} $$

By constuction this holds for $\vec x ∈ \ps{0,1}^n$. To see that it holds for all $\vec x ∈ \F^n$ observe that $\mathrm{add}_i$ and $\mathrm{mul}_i$ are MLEs in $\vec x$ and a linear combination of MLEs is also an MLE. Since MLEs are uniquely identified by their values on $\ps{0,1}^n$ they must be identical. Note that $\mathrm{add}_i$ and $\mathrm{mul}_i$ do not need to be multilinear in $\vec y, \vec z$. In GKR08 a slightly more complex expression is used that does not require multilinearity in $\vec x$ either. The above expression is due to T15.

**Prover**sends the output values $w_k(\vec x)$.**Verifier**sends random $\vec r_{\vec x} ∈ \F^n$ and computes $w_k(\vec r_{\vec x})$.- The
**prover**and**verifier**run sumcheck on the relation between $w_{k}(\vec r_{\vec x})$ and $w_{k-1}(\vec x)$ as above (using $f$ for the summand) $$ w_k(\vec r_{\vec x}) = \sum_{\vec y, \vec z ∈ \ps{0,1}^n} f(\vec r_{\vec x}, \vec y, \vec z) $$ this results in $\vec c ∈ \F$, random $\vec r_{\vec y}, \vec r_{\vec z} ∈ \F^n$ and a claim $c = f\p{\vec r_{\vec x}, \vec r_{\vec y}, \vec r_{\vec z}}$ **Prover**sends $w_{k-1}(\vec r_{\vec y})$ and $w_{k-1}(\vec r_{\vec z})$, to be proven in a moment.**Verifier**computes $\mathrm{add}_{k-1}\p{\vec r_{\vec x}, \vec r_{\vec y}, \vec r_{\vec z}}$ and $\mathrm{mul}_{k-1}\p{\vec r_{\vec x}, \vec r_{\vec y}, \vec r_{\vec z}}$ locally and checks $c = f\p{\vec r_{\vec x}, \vec r_{\vec y}, \vec r_{\vec z}}$.- The
**prover**and**verifier**reduce the two queries $w_{k-1}(\vec r_{\vec y})$ and $w_{k-1}(\vec r_{\vec z})$ to one query $w_{k-1}(\vec r_{\vec x}')$. - The
**prover**and**verifier**run repeat steps 3-6 for $k-1$ more times. - The
**prover**and**verifier**use further methods to checks $w_0(\vec r_{\vec x})$.

This reduces a claim on the output values $w_k(\vec x)$ to a claim on the input values $w_0(\vec r_{\vec x})$.

Note that it is assumed the verifier knows $\mathrm{add}_i$ and $\mathrm{mul}_i$ and it is economical for the verifier to evaluate it. Alternatively the prover can use a polynomial commitment scheme or other means to convey those values to the verifier.

This protocol can be straightforward generalized to support unequal sized layers $n_i$, leading to potential further reductions in proof size and compute cost.

TODO: Analysis, especially complexity and proof size. Especially efficient evaluation of $\mathrm{add}_i$, $\mathrm{mul}_i$.

Q: The choice of addition and multiplication gates is natural, but also arbitrary. What other gates can be supported? S23 presents a clever scheme using an exponentiation operator.

### Quickly evaluating $\add_i$ and $\mul_i$ in random $\vec r$

Observe that in a fully defined circuit each output node has either $\add$ or $\mul$ return $1$ for it. So together they have one-hot on each corner of the $\vec x$ hypercube. We can construct this basis in

$$ \p{2^{n+1} - 4}⋅\mul + n⋅\addc $$

operations.

$$ \mul_i(\vec r_x, \vec r_y, \vec r_z) = \sum_{\vec x ∈ \set M} \eq(\vec x, \vec r_x)⋅ \eq(\vec y(\vec x),\vec r_y)⋅ \eq(\vec z(\vec x),\vec r_z) $$

What remains is computing the various $\eq(\vec c_x, □)$ values. Here $\vec c_x$ encodes the connectivity and is sparse: only $2^n$ out of $2^{2⋅n}$ values are used. We can however again assume that each node is an input at least once. So all values appear. We get $$ 3⋅\p{2^{n+1} - 4}⋅\mul + 3⋅n⋅\addc $$

To compute the three lookup tables for the $\eq$'s. Then to combine them into $\add$ and $\mul$ we need a further $$ 2^{n + 1}⋅\mul $$

- Compute the hypercube basis for $\eq(\vec c, \vec r_x)$, $\eq(\vec c, \vec r_y)$ and $\eq(\vec c, \vec r_z)$ in $3⋅2^n$ space.
- Use two acumulators $\add$ and $\mul$. For each entry in

See XZZ+19.

## References

- GKR08 Shafi Goldwasser, Yael Tauman Kalai, Guy N. Rothblum (2008). Delegating Computation: Interactive Proofs for Muggles.
- CTY11 Graham Cormode, Justin Thaler, Ke Yi (2011). Verifying Computations with Streaming Interactive Proofs.
- CMT12 Graham Cormode, Michael Mitzenmacher, Justin Thaler (2012). Practical Verified Computation with Streaming Interactive Proofs.
- T13 Justin Thaler (2013). "Time-Optimal Interactive Proofs for Circuit Evaluation"
- T15 Justin Thaler (2015). "A Note on the GKR Protocol"
- CFS17 Alessandro Chiesa, Michael A. Forbes, Nicholas Spooner (2017). A Zero Knowledge Sumcheck and its Applications.
- XZZ+19: Tiancheng Xie et al. (2019). "Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation".
- T20a T20b: Justin Thaler (2020). "The Unreasonable Power of the Sum-Check Protocol"
- K22 Erich Kaltofen (2022). "The GKR Protocol Revisited"
- PH23 Shahar Papini, Ulrich Haböck (2023). "Improving logarithmic derivative lookups using GKR"
- S23 Lev Soukhanov (2023). "Power circuits: a new arithmetization for GKR-styled sumcheck"
- T23a Justin Thaler (2023). "Proofs, Arguments, and Zero-Knowledge". See also lecture notes and older lecture notes
- T23b Justin Thaler (2023). The sumcheck protocol over fields of small characteristic.
- G24 Ariel Gabizon (2024). zkWarsaw talk "The GKR method".

https://github.com/ingonyama-zk/papers/blob/main/sumcheck_201_chapter_1.pdf

https://eprint.iacr.org/2024/1046

- BDT24 Suyash Bagad, Yuval Domb, Justin Thaler (2024). The Sum-Check Protocol over Fields of Small Characteristic.