# Sumcheck protocol and another protocol based on Sumcheck.
This is my note about sumcheck protocol and another protocol based on sumcheck.

## I. Sumcheck protocol (LFKN92)
### 1.1 What is the problem sumcheck protocol solve?

Fix a finite filed $F$ and a subset $H \subseteq F$. The 2 party prover $P$ and verifier $V$ and $m$-variable polynomial $f: F^{m} \rightarrow F$ have degree $\leq d$ and ($d \lt\lt |F|$).

Prover want to convince verifier:

$$
\sum_{z_1 \in H, z_2 \in H,..z_n \in H}^{} g(z_1,z_2,...,z_n) = s \ (*)
$$

with constant $s \in F$. Verifier $V$ have limit computation power. Prover $P$ have unbound computation power.

We denote protocol by $(P(f), V^f(s))$

### 1.2 Protocol
How we prover can prove $(*)$ it to verifier? They use very clever protocol call sumcheck protocol. Protocol work follow schema below:

1. Prover $P$ send function $f_1(x) = g(x, z_2,...,z_n)$ to verifier $V$
2. Verifier $V$ check $\sum_{v \in H} f_1(v) = s$.
3. Verifier $V$ sample a random number $r1$ on $F$ and send it to prover $P$.
4. Prover $P$ repleace $x_1$ with number $r_1$ and free $z_2$ by variable $x$ we function $f_2(x) = g(r_1, x, z_3,...,z_n)$.
5. Repeat step 1 to 4 with the new $s = f_i(r_i)$.
6. And the last round when $i = n$ we check $f(r_1,r_2..., r_n) = f_n(r_n)$.

The protocol success if any check this mean $(*)$ is true, vice versa $(*)$ is not true.

### 1.3 Complexity

Let $deg(f)$ denote degree of polynomial $f$.

Because prover have unbound compution power, so we don't create about it in this case.
For verifier we have runtime complexity = $O_V(\sum_{i=1}^{n}deg(f_i))$ and 1 evaluate $g$.
And communicate complexity = $O(\sum_{i}^n deg(f_i))$.

### 1.4 Completeness and Soundness
* **Completeness**: if $\sum_{z_1 \in H, z_2 \in H,..z_n \in H}^{} g(z_1,z_2,...,z_n) = s$ then
$$
Pr[(P(f), V^f(s)) = 1] = 1
$$

* **Soundness**: if $\sum_{z_1 \in H, z_2 \in H,..z_n \in H}^{} g(z_1,z_2,...,z_n) \neq s$ then
$$
Pr[(P(f), V^f(s)) = 1] \leq \frac{dn}{|F|}
$$

**Proof**:

## II. GKR protocol (GKR15)

### 1.1 Problem

Let circuit C be a $d$ depth layer citcuit composed by 2 fan-in gate: addition and multiplication. Layer $d$ is input and layer 0 is output.

Example, the circuit below is have $d = 3$:


We also have 2 party prover and verifier and prover wants to prove to the verifier the that their computation on C is valid.

For easy to compute we assume the size of each layer is equal each other and echo $n$.
### 1.2 Protocol

We index the circuit by binary representation for each layer from left to right.

We assume:
- $V_i(p): \{0, 1\}^n \rightarrow F$ is function compute value at gate $p$ from 2 gates at lower layer.
- $mul(p, u, v)$ return 1 if u, v is in gates p and p is multiplication gate, 0 if not.
- $add(p, u, v)$ return 1 if u, v is in gates of p and p is addition gate, 0 if not.
- $\beta(p, q)$ equal 1 if $p = q$ and equal 0 if $p \neq q$.
We can easy to see:

$$
V_i(p) = \sum_{q, u, v \in \{0, 1\}^{log_2n}}\beta(p, q) * (V_{i+1}(u) + V_{i+ 1}(v)) * add(p, u, v) + V_{i+1}(u) * V_{i+1}(v) * mul(p, u, v)
$$

Let call $f_i(p, u, v) = (V_{i+1}(u) + V_{i+1}(v)) * add(p, u, v) + V_{i+1}(u) * V_{i+1}(v) * mul(p, u, v)$

So we have:

$$
V_i(p) = \sum_{u, v, q \in \{0, 1\}^{log_2n}} \beta(p, q)* f(p, u, v) \space \space(**)
$$

Note u,v, p, q is binary representation

We want to verify the computation on $V_i$ is true for each gate. But verifier don't want to eval $(**)$ because this is heavy computation.

Wait... we can use sumcheck protocol to verify the correctness of this computation. However the last verify of sumcheck protocol(check step 6) is compute $\beta(p, r_3) * f(p, r_1, r_2)$ which $r_1, r_2, r_3$ is random number choose by verifier. Verifier need to evaluate $V_{i+1}(r_1)$ and $V_{i+1}(r_2)$. This computation actually recompute the circuit, this mean verifier can't do that. Instead of prover will send $s_1, s_2$ is result of $V_{i +1}(r_1)$ and $V_{i+1}(r_2)$. We will do sumcheck again on the layer i + 1 over $V_{i +1}(r_1) = s_1$ and $V_{i+1}(r_2) = s_2$.

Everything look good right now, but we have a new problem. After we do sumcheck for one layer the number of fomula we do sumcheck will be double. Example: The first layer do 1 sumcheck, the second layer will do 2 sum check, the third layer will do 4 sumcheck, ... The n-th layer will do $2^n$ sumcheck. We want to improve the complexity. Let find the way to **reduce 2 sumcheck to 1 sumcheck**.

Let fixed $t_1, t_2$ we have function $\gamma: F \rightarrow F^m$ be a unique line such that $\gamma(t_1) = r_1$ and $\gamma(t_2) = r_2$. Example we can fix $t_1 = 0, t_2 = 1$, then $\gamma(t) = (1 - t) *r_1 + t * r_2$.

Call $f = V_i \circ \gamma$, Prover send $f$ to verifier. Verifier will will check $f(t_1) = s_1$ and $f(t_2) = s_2$. If sumcheck pass, verifier will sample a random number $t$ and sent it to prover. We continue protocol with proof $p = \gamma(t), s = f(t)$ on the next layer.

### 1.3 Complexity

### 1.4 Completeness and Soundness

## Improvements

### Gir++ protocol