GKR

GKR is a SNARK protocol for small-depth circuits of multiplication and addition gates. The standard form allows combinations of both. The protocol involves three MLEs: ${\tilde{V}}_i$ is the MLE of a function capturing the values of the gates at layer $i$, and ${\widetilde{\text{add}}}_i$ and ${\widetilde{\text{mult}}}_i$ are MLEs of functions capturing the circuit's wires.

Specifically, ${\tilde{V}}_i(j)$ evaluates to the value of the circuit at the $i$-th layer in the $j$-th gate. For example ${\tilde{V}}_1(0)$ corresponds to the output gate.

${\widetilde{\text{add}}}_i(j,a,b)$ evaluates to 1 if the $j$-th gate of the $i$-th layer is an addition gate whose inputs are the $a$'th and $b$'th gates at the preceding layer.

${\widetilde{\text{mult}}}_i(j,a,b)$ evaluates to 1 if the $j$-th gate of the $i$-th layer is a multiplication gate whose inputs are the $a$'th and $b$'th gates at the preceding layer.

The sumcheck protocol is applied to the following: $${\tilde{V}}_i(z)=\sum _{(p,{\omega }_1,{\omega }_2)\in \{0,1{\}}^{s_i+2s_{i+1}}}{f}_{i,z}(p,{\omega }_1,{\omega }_2),$$

where

$$f_i(z,p,{\omega }_1,{\omega }_2)={\widetilde{\text{eq}}}_{s_i}(z,p)\cdot ({\widetilde{\text{add}}}_i(p,{\omega }_1,{\omega }_2)({\tilde{V}}_{i+1}({\omega }_1)+{\tilde{V}}_{i+1}({\omega }_2))+{\widetilde{\text{mult}}}_i(p,{\omega }_1,{\omega }_2){\tilde{V}}_{i+1}({\omega }_1)\cdot {\tilde{V}}_{i+1}({\omega }_2))$$ $${\widetilde{\text{eq}}}_{s_i}(z,p)=\prod _{j=1}^{s_i}((1-z_j)(1-p_j)+z_j{p}_j).$$

(See the eq-polynomial page for details.)

Lasso and Jolt currently use the variant of GKR described in Thaler13, which is optimized for the far simpler case of a binary tree of multiplication gates. This simplifies each sumcheck to: $${\tilde{V}}_i(z)=\sum _{p\in \{0,1{\}}^{s_i}}{g}_z^{(i)}(p),$$

where

$$g_z^{(i)}(p)={\widetilde{\text{eq}}}_{s_i}(z,p)\cdot {\tilde{V}}_{i+1}(p,0)\cdot {\tilde{V}}_{i+1}(p,1)$$ GKR is utilized in memory-checking for the multi-set permutation check.