Prerequisite:

- multilinear polynomials
- low degree extension

## Multilinear extensions

A multivariate polynomial $g$ is multilinear if the degree of the polynomial in each variable is at most one.

let $f:{0,1}_{v}→F$ be any function mapping the v-dimensional hypercube to $F$, then multilinear extension of $f$ is $g$, a $v$-variate polynomial that agrees with $f$ on all $x∈{0,1}_{v}$.

Why multilinear extensions?

Allows to represent domain of length 2^v into v variable multilinear polynomial, which is way less than univariate polynomials where $v−1$ variable polynomial is needed to represent length $v$ domain.

Using SZ lemma, verifier gains power over prover as if two functions $f,f_{′}$ differ at even one point in ${0,1}_{v}$, then their extension $g,g_{′}$ disagree almost everywhere, precisely agree at most $∣F∣d $.

Prove that a function $f:{0,1}_{v}→F$ has a unique multilinear extension $f $ over $F$. a

### Lagrange interpolation

$f (x_{1},x_{2},…,x_{v})=w∈{0,1}_{v}∑ f(w)⋅eq (x_{1},…,x_{v}) $where for any $w=(w_{1},…,w_{v})$, $eq _{w}(x)$ is called equality polynomial,

$eq (x_{1},…,x_{v})=i=1∏v (x_{i}w_{i}+(1−x_{i})(1−w_{i}))$## Sumcheck protocol

To Prove: $∑_{i=0}f=c$

More precisely, sumcheck protocol is used to prove a v-variate polynomial defined over a Finite field $F$.

$H:=b_{1}∈{0,1}∑ b_{2}∈{0,1}∑ ⋯b_{v}∈{0,1}∑ g(b_{1},…,b_{v}) $Let’s see how the protocol behaves:

- $P→V:C$ claiming $C$ to equal to $H$
- round 1: $P$ sends a univariate polynomial: $g_{1}(X_{1})=∑_{x_{2},…,x_{v}∈{0,1}_{v−1}}g(X_{1},x_{2},…,x_{v})$
- $V$ checks that $C_{1}=g_{1}(0)+g_{1}(1)$, and $g_{1}(g)≤g(X_{1})$
- $r∈F←V$, and sends to $P$
- round i:
- $P→V:g_{j}(X_{j})=∑_{x_{j+1},…,x_{v}∈{0,1}_{v−i}}g(r_{1},…,r_{i−1},X_{j},x_{j+1},…,x_{v})∀i∈[2,v−1]$
- $V$ checks $g_{j}(0)+g_{j}(1)=g_{j−1}(r_{j−1})$ and sends $r_{j}∈F$ to $P$

- last round: $P→V:g_{v}(X_{v})=g(r_{1},…,r_{v−1},X_{v})$
- $V$ checks $g_{v}(0)+g_{v}(1)=g_{v−1}(r_{v−1})$, and $g(g_{v})≤deg(X_{v}∈g)$
- checks with oracle query access to $g$ that $g(r_{1},…,r_{v})=g_{v}(r_{v})$

Efficiency:

- $P$: for each round i: $O(1+g_{i}(g))⋅2_{v−j}$ terms are sent

### Univariate sumcheck

Introduced in Aurora Paper, univariate sumcheck proves relation for a univariate polynomial $f(x)$ of degree $d$ and subset $H⊆F$:

$a∈H∑ f(a)=0$Properties of protocol:

- rounds: $O(gd)$
- proof complexity: $O(d)$
- query complexity: $O(gd)$
- prover operations: $O(dg∣H∣)$
- verifier operations: $O(gd+g_{2}∣H∣)$

Uses theorem stated by Byott and Chapman BC99 that $∑_{a∈H}f(a)=0$ iff $f$ has degree less than $∣H∣−1$. Prove this using FRI protocol by BBHR18b which has proof complexity $O(gd)$ and proof length $O(d)$. For case when degree $d>∣H∣−1$: we observe that we can split any polynomial $f$ into two polynomials $g$ and $h$ such that $f(x)≡g(x)+∏_{α∈H}(x−α)⋅h(x)$ with $deg(g)<∣H∣$ and $deg(h)<d−∣H∣$; in particular, $f$ and $g$ agree on $H$, and thus so do their sums on $H$.

$f^ a∈H∑ f^ (a) ≡g^ +Z_{H}⋅h^≡a∈H∑ (g^ (a)+Z_{H}⋅h^(a))=βa∈H∑ a_{∣H∣−1} $- https://hackmd.io/@kIJ38IbETaGkxGkcxhrNVg/HycoeJUJh?utm_source=preview-mode&utm_medium=rec

## GKR

$P$ and $V$ agrees to a circuit. $P$ proves $V$, the output of the circuit.

Taken from jolt repo:

GKR is a SNARK protocol for binary trees of multiplication / addition gates. The standard form allows combinations of both using a wiring predicate $V~_{i}$, and two additional MLEs $add~_{i}$ and $mult~_{i}$.

$V_{i}(j)$ evaluates to the value of he circuit at the $i$-th layer in the $j$-th gate. For example $V~_{1}(0)$ corresponds to the output gate.

$add_{i}(j)$ evaluates to 1 if the $j$-th gate of the $i$-th layer is an addition gate.

$mult_{i}(j)$ evaluates to 1 if the $j$-th gate of the $i$-th layer is a multiplication gate.

The sumcheck protocol is applied to the following:

$V~_{i}(z)=(p,ω_{1},ω_{2})∈{0,1}_{s+2s}∑ f_{i,z}(p,ω_{1},ω_{2}),$where

$f_{i}(z,p,ω_{1},ω_{2})=β_{s_{i}}(z,p)⋅add~_{i}(p,ω_{1},ω_{2})(V~_{i+1}(ω_{1})+V~_{i+1}(ω_{2}))+mult~_{i}(p,ω_{1},ω_{2})V~_{i+1}(ω_{1})⋅V~_{i+1}(ω_{2})$ $β_{s_{i}}(z,p)=j=1∏s_{i} ((1−z_{j})(1−p_{j})+z_{j}p_{j}).$Lasso and Jolt implement the Thaler13 version of GKR which is optimized for the far simpler case of a binary tree of multiplication gates. This simplifies each sumcheck to:

$V~_{i}(z)=p∈{0,1}_{s}∑ g_{z}(p),$where

$g_{z}(p)=β_{s_{i}}(z,p)⋅V~_{i+1}(p,0)⋅V~_{i+1}(p,1)$GKR is utilized in memory-checking for the multi-set permutation check.

## Resources

- recmo’s post about sumcheck
- JThaler’s: unreasonable power of sumcheck
- JThaler’s sumcheck notes
- JThaler’s: Proofs, Args, and ZK, Chapter 3, 4
- JThaler’s small sumcheck
- erhant’s notes on Lecture 4 of ZKP MOOC
- NUS CS6230: The power of IPs
- Berkeley’s CS294: Introduction to IP & Sumcheck
- risencrypto’s sumcheck
- zk sumcheck
- sumcheck arguments and their application
- CPerez’s post about sumcheck
- CPerez’s ideas about GKR