GKR Protocol

The protocol is best presented in terms of the (arithmetic) circuit evaluation problem. In this problem, $V$ and $P$ first agree on a log-space uniform arithmetic circuit $C$ of fan-in 2 over a finite field $F$, and the goal is to compute the value of the output gate(s) of $C$. A log-space uniform circuit $C$ is one that possesses a succinct implicit description, in the sense that there is a logarithmic-space algorithm that takes as input the label of a gate $a$ of $C$, and is capable of determining all relevant information about that gate. That is, the algorithm can output the labels of all of $a$’s neighbors, and is capable of determining if $a$ is an addition gate or a multiplication gate.

Notation

Suppose we are given a layered arithmetic circuit $C$ of size $S$, depth $d$, and fan-in two ($C$ may have more than one output gate). Number the layers from $0$ to $d$, with $0$ being the output layer and $d$ being the input layer. Let $S_i$ denote the number of gates at layer $i$ of the circuit $C$. Assume $S_i$ is a power of $2$ and let $S_i$ = $2^{k_i}$. The GKR protocol makes use of several functions, each of which encodes certain information about the circuit:

• Let $W_i: \{0, 1\}^{k_i} → F$ denote the function that takes as input a binary gate label, and outputs the corresponding gate’s value at layer $i$.

• Let $add_i: \{0, 1\}^{k_i + 2k_{i+1}} → \{0,1\}$ denote the function that takes as input three gate labels $(a, b, c)$ and return 1 if and only if $b$ and $c$ are the first and second in-neighbour of gate $a$ and gate $a$ is an addition gate.

• Let $mult_i: \{0, 1\}^{k_i + 2k_{i+1}} → \{0,1\}$ denote the function that takes as input three gate labels $(a, b, c)$ and return 1 if and only if $b$ and $c$ are the first and second in-neighbour of gate $a$ and gate $a$ is a multiplication gate.

• Let $\widetilde{W_i}$, $\widetilde{add_i}$ and $\widetilde{mult_i}$ denote the multilinear extensions of $W_i$, $add_i$ and $mult_i$.

Illustration

$W_0(0) = 15$, $W_1(0) = 12$, $W_1(1) = 3$, $W_2(0, 0) = 3$, $W_2(0, 1) = 4$, $W_2(1, 0) = 1$, $W_2(1, 1) = 2$

$add_0(0, 0, 1) = 1$ and equals to 0 for all other inputs

$mult_0$ is 0 for all the inputs

$add_1(1, 1, 0, 1, 1) = 1$, for all the other inputs the output is zero

$mult_1(0, 0, 0, 0, 1) = 1$, for all the other inputs the output is zero

Important lemma

$\widetilde{W_i}(z) = \sum_{b,c \in \{0,1\}^{k_{i+1}}}\widetilde{add_i}(z, b,c)(\widetilde{W_{i+1}}(b)+\widetilde{W_{i+1}}(c)) + \widetilde{mult_i}(z, b,c)(\widetilde{W_{i+1}}(b)·\widetilde{W_{i+1}}(c))$

Protocol

1. Let $C$ be a layered arithmetic circuit of depth $d$ and fan-in two on input $x ∈ F^n$. Throughout, $k_i$ denotes $\log_2(S_i)$ where $S_i$ is the number of gates at layer $i$ of $C$.

2. At the start of the protocol, $P$ sends a function $D: \{0, 1\}^{k_0} → F$ claimed to equal $W_0$ (the function mapping output gate labels to output values).

3. $V$ picks a random $r_0 ∈ F^{k_0}$ and lets $m_0 = \widetilde{D}(r_0)$. The remainder of the protocol is devoted to confirming that $m_0 = \widetilde{W_0}(r_0)$.

4. For $i = 0, 1,...,d-1:$

   1. Define the $(2k_{i+1})\text{-variate}$ polynomial $f_{r_i}^{(i)}(b,c) = \widetilde{add_i}(r_i, b, c)(\widetilde{W_{i+1}}(b) + \widetilde{W_{i+1}}(c)) + \widetilde{mult_i}(r_i, b, c)(\widetilde{W_{i+1}}(b) · \widetilde{W_{i+1}}(c))$.

   2. $P$ claims that $\sum_{b,c \in \{0,1\}^{k_{i+1}}}f_{r_i}^{(i)}(b,c) = m_i$

   3. So that $V$ may check this claim, $P$ and $V$ apply the sum-check protocol to $f_{r_i}^{(i)}$, up until $V\text{'s}$ final check in that protocol, when $V$ must evaluate $f_{r_i}^{(i)}$ at a randomly chosen point $(b^{*}, c^{*}) \in F^{k_{i+1}}×F^{k_{i+1}}$. See Remark (a).

   4. Let $l$ be the unique line satisfying $l(0) = b^∗$ and $l(1) = c^∗$. $P$ sends a univariate polynomial $q$ of degree at most $k_{i+1}$ to $V$, claimed to equal $\widetilde{W_{i+1}}$ restricted to $l$.

   5. $V$ now performs the final check in the sum-check protocol, using $q(0)$ and $q(1)$ in place of $\widetilde{W_{i+1}}(b^{*})$ and $\widetilde{W_{i+1}}(c^{*})$. See Remark (b).

   6. $V$ chooses $r^* \in F$ at random and sets $r_{i+1} = l(r^*)$ and $m_{i+1} = q(r_{i+1})$.

5. $V$ checks directly that $m_d = \widetilde{W_d}(r_d)$. Note that $\widetilde{W_d}$ is simply $\tilde{x}$, the multilinear extension of the input $x$ when $x$ is interpreted as the evaluation table of function mapping $\{0, 1\}^{\log n} → F$.

Remark a. Note that $V$ does not actually know the polynomial $f_{r_i}^{(i)}$, because $V$ does not know the polynomial $\widetilde{W_{i+1}}$ that appears in the definition of $f_{r_i}^{(i)}$. However, the sum-check protocol does not require $V$ to know anything about the polynomial to which it is being applied, until the very final check in the protocol.

Remark b. We assume here that for each layer $i$ of $C$, $V$ can evaluate the multilinear extensions $\widetilde{add_i}$ and $\widetilde{mult_i}$ at the point $(r_i, b^∗, c^∗)$ in polylogarithmic time. Hence, given $\widetilde{W_{i+1}}(b^{*})$ and $\widetilde{W_{i+1}}(c^{*})$, $V$ can quickly evaluate $f_{r_i}^{(i)}(b^{*}, c^{*})$ and thereby perform its final check in the sum-check protocol applied to $f_{r_i}^{(i)}$.

Properties

• perfect completeness

• soundness error: $O(d \log S / |F|)$

Costs

Let $n$ be a number of inputs.

Communication	Rounds	V time	P time
$O(d \log S)$	$O(d \log S)$	$O(n + d \log S)$	$poly(S)$

Note (a): It is now known how to achieve prover runtime of $O(S)$ for arbitrary layered arithmetic circuits $C$ [XZZ+19].