$\newcommand{\F}{\mathbb{F}}$
$\newcommand{\mle}[1]{\widetilde{#1}}$
$\newcommand{\inn}{\text{in}}$
$\newcommand{\add}{\text{add}}$
$\newcommand{\mult}{\text{mult}}$
$\newcommand{\poly}{\text{poly}}$

# GKR Protocol (Underground ZKP Reading Group)
We follow Justin Thaler's book [*Proofs, Arguments, and Zero-Knowledge*](https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.html).

## Overview
The GKR protocol is an interactive proof (IP) protocol for arithmetic circuit evaluation. For circuits with structure, it can result in linear time provers and sublinear time verifiers.
## Mathematical Background
- Let the number of gates in an arithmetic circuit be called its size $S$. Any arithmetic circuit can be converted to a layered circuit (wires only connect gates in adjacent layers) with an at most $d$ factor blowup in size, where $d$ is the depth of the circuit.
- Any function $f: \{0, 1\}^v \rightarrow \F$ mapping points on the boolean hypercube to a finite field $\F$ has a unique $v$-variate multilinear extension $\mle{f}$.
- Let $g$ be a $v$-variate polynomial defined over a finite field $\F$. The sum-check protocol is an interactive proof (IP) protocol for the sum of $g$ over the boolean hypercube.
- A key fact about the sum-check protocol we use is that the verifier $V$ does not need to know $g$. It simply needs to evaluate $g$ at a random point in the final round of the protocol.

### Reducing Two Polynomial Evaluations to One
Suppose a verifier has to evaluate a multilinear polynomial $\mle{f}: \F^v \rightarrow \F$ at two points $b$ and $c$, to check whether they equal the prover's claimed values. Let $l: \F \rightarrow \F^v$ be the line defined by $l(0) = b$ and $l(1) = c$.

Consider the restriction of $\mle{f}$ to the line $l$, $\mle{f} \circ l: \F \rightarrow \F$. The prover sends the verifier its claimed value $q$ for this univariate polynomial. The prover picks a random $r \in \F$ and computes $\mle{f}(l(r))$ and checks if it is equal to $q(r)$. If so, the verifier is convinced $q$ truly equals $\mle{f} \circ l$ and in turn uses $q(0)$ and $q(1)$ for $\mle{f}(b)$ and $\mle{f}(c)$, respectively.

## GKR Protocol
Prover $P$ and verifier $V$ agree on a layered arithmetic circuit $C$ of fan-in 2 over a finite field $\F$. Prover wants to convince the verifier that it knows the outputs of $C$, when evaulated at some input $x$.

Suppose $C$ has depth $d$ and size $S$. We number the layers from $0$ to $d$ with $d$ referring to input layer and $0$ referring to output layer.

Let $S_i$ be the number of gates at layer $i$. For simplicity of exposition, we assume $S_i$ is a power of 2, so $S_i = 2^{k_i}$. Number the gates in layer $i$ from $0$ to $S_i - 1$. We define the following functions for each layer $i$:
- $W_i: \{0, 1\}^{k_i} \rightarrow \F$ takes in a gate label (as a binary string) and outputs the corresponding gates value. $\mle{W_i}$ denotes the multilinear extension of $W_i$.
- Wiring predicate functions:
- $\inn_{1,i}, \inn_{2,i}: \{0, 1\}^{k_i} \rightarrow \{0,1\}^{k_{i+1}}$ denote the functions that take in a gate $a$ at layer $i$ and outputs its first and second in-neighbors, $b$ and $c$ in layer $i+1$.
- $\add_i, \mult_i: \{0,1\}^{k_i + 2k_{i+1}} \rightarrow \{0, 1\}$ take in three gate labels $(a, b, c)$ and returns $1$ iff $(b,c) = (\inn_{1,i}(a), \inn_{2,i}(a))$ and gate $a$ is an addition (respectively, multiplication) gate. Let $\mle{\add_i}$ and $\mle{\mult_i}$ denote the multilinear extensions of $\add_i, \mult_i$.

The GKR protocol proceeds as follows. The prover $P$ sends the verifier $V$ a function $D: \{0, 1\}^{k_0} \rightarrow \F$ which encode the claimed output values of the circuit $C$. Suppose $V$ knows $\mle{W_0}$. Then, it can verify that $\mle{D} = \mle{W_0}$ by checking that they agree at a random point $r_0 \in \F^{k_0}$. However, $V$ cannot evaulate $\mle{W_0}(r_0)$ without further interaction with $P$.

As a result, the GKR protocol proceeds in $d$ iterations. In each iteration $i$, the prover reduces a claim about $\mle{W_i}(r_i)$ to a claim about $\mle{W_{i+1}}(r_{i+1})$. At the end, the verifier must check a claim about the input layer $d$, for which it no longer needs the provers help.

To make this reduction, we utilize this expression:
$$ \mle{W_i}(z) = \sum_{b,c \in \{0,1\}^{k_{i+1}}} \mle{\add_i}(z,b,c)(\mle{W_{i+1}}(b) + \mle{W_{i+1}}(c)) + \mle{\mult_i}(z,b,c)(\mle{W_{i+1}}(b) \cdot \mle{W_{i+1}}(c)) $$

The validity of this expression results from the fact that a function over the boolean hypercube has a unique multilinear extension.:

To check a prover's claim about the value of $\mle{W_i}(r_i)$, the sum-check protocol is applied to the polynomial:

$$f_{r_i}(b,c) = \mle{\add_i}(r_i,b,c)(\mle{W_{i+1}}(b) + \mle{W_{i+1}}(c)) + \mle{\mult_i}(r_i,b,c)(\mle{W_{i+1}}(b) \cdot \mle{W_{i+1}}(c))$$

However, there is an issue: the verifier does not know the polynomial $\mle{W_{i+1}}$ and so it does not the polynomial it is applying the sum-check protocol to! This is acceptable until the final rounds of sum-check where the verifier has to evaulate $f_{r_i}$ at a random point $(r_b, r_c)$, where $r_b, r_c \in \F^{k_{i+1}}$.

Evaluating $f_{r_i}(r_b, r_c)$ requires evaulating:
- $\mle{\add_i}(r_i, r_b, r_c)$ and $\mle{\mult_i}(r_i,r_b,r_c)$. The time complexity of this depends on whether the circuit $C$ has any structure. For instance, in the original GKR paper it is assumed that $C$ is logspace-uniform. Thaler's book also discusses data-parallel circuits, with repeated strucuter. We do not discuss this matter further but assume the time for this evaulation is $\poly(k_i, k_{i+1})$.
- $\mle{W_{i+1}}(r_b)$ and $\mle{W_{i+1}}(r_c)$. As discussed in the mathematical background, we can reduce this to evaluating $\mle{W_{i+1}}$ at a single point $r_{i+1}$.

## Sum-Check Protocol

Let $g$ be a $v$-variate polynomial over a finite field $\F$. The sum-check protocol allows a prover $P$ to convince a verifier $V$ about the value of the following sum:

$$ \sum_{(x_1,...,x_v) \in \{0,1\}^v} g(x_1,...,x_v)$$

Suppose the $P$ claims the above sum is $H$. The protocol proceeds in $v$ rounds, as follows. In round $i$, $P$ sends $V$ the polynomial $g_1(X_1)$ claimed to equal the following polynomial:
$$s_1(X_1) = \sum_{(x_2,..,x_v) \in \{0,1\}^{v-1}} g(X_1, x_2,...,x_v)$$

To check if $V$'s claim abouit $H$ is correct the prover needs to verify:
1. $H = g_1(0) + g_1(1)$
2. $s_1 = g_1$.

The first is easy, the second is difficult because $s_1$ is a sum over $2^{v-1}$ evaluations of $g$. So instead, $V$ reduces to checking that $s_1(r_1) = g_1(r_1)$ at a random point $r_1 \in \F$ and that $g_1$'s degree is as expected. Obviously, this reduction incurs some soundness error. $V$ sends its claimed value of $g_1(r_1)$. But now checking that this equals $s_1(r_1)$ is the same as applying sum-check to the $(v-1)$-variate polynomial $g(r_1, x_2,...,x_v)$.

From here it is relatively clear to see that this problem will be reduced to sum-check over a $(v-2)$-variate polynomial, and so on until $V$ is left to compute $g$ at the random point $(r_1,...,r_v) \in \F^v$.

## Rough Cost Accounting and Soundness Error

### Verifier $V$'s Runtime
$V$'s runtime is $O(n + d \log S + t + S_0)$, where $t$ is the time needed to evaluate $\mle{\add_i}$ and $\mle{\mult_i}$ at a random point for each layer $i$. $n$ is the input size and is the time needed to compute $\mle{W_d}(r_d)$. $S_0$ is the time needed to read the vector of claimed outputs and evaluate its multilinar extension. The $d \log S$ term is for checking the $P$'s messages over each of sum-check sub-routines.

### Prover $P$'s Runtime (Unsophisticated Method)
A naive analysis yields a runtime for $P$ of $O(S^3)$. The analysis is as follows. $P$ has to run sum check for the $f_{r_i}$ polynomials. These polynomials are $v$-variate, where $v = 2k_{i+1}$. At round $$ of the sum-check protocol, we have to send the description of a univariate polynomial. This description can be evaluated by evaluating $f_{r_i}$ at $3 * 2^{v-j}$ points. Evaluating $f_{r_i}$ requires $O(S_i + S_{i+1})$ time. So overall round $i$ of GKR is $O(2^v(S_i + S_{i+1}))$ time. Summing this over the $d$ layers yields $O(S^3)$.

### Soundness Error
The soundness error comes from the sum-check protocol and the reducing two evaluations to one evaluation sub-routine. In each of these cases, the error comes from different univariate polynomials being equal at a random point. Union bounding over these error yields a soundness error of $O(d \log S / |\F|)$.