---
# System prepended metadata

title: GKR reading note
tags: ['#multi-variate', '#GKR']

---

# GKR reading note

[toc]

## 1. Intuition

### 1.1 zero check / testing
    
- [x] how to encode $N$ constraints in uni-variate zkp (pairing-based / hash-based)?
       
     - [x] a uni-variate polynomial $f(X) = \sum_{i=0}^{N-1} a_i * X^i$ of degree less than $N$ can be uniquely represented by its evaluation over set $T = \{w^i: 0 \leq i < N\}$
         - $\{ f(w^i): 0 \le i < N\}$
         - We can use Lagrange interpolation to convert between evaluation form and coefficient form.
     - for each $w^i$, we have $f(w^i) * g(w^i) = h(w^i)$; 
     - this is equivalent to $f(X)*g(X)-h(X) = 0$ for $X \in T$
     - this is equivalent to $(X - w^i)$ divides $f(X)*g(X) - h(X)$ for each i;
     - this is equivalent to $$Z_T(X) = \prod_{i=0}^{N-1} (X - w^i) = (X^N - 1)$$ divides $f(X)*g(X) - h(X)$;
     
     - this is equivalent to 
         > there exists a polynomial $q(X)$ s.t. $q(X)*Z_T(X) = f(X)*g(X) - h(X)$.

- [x] how to encode $N$ constraints in GKR?
    - we can encode $3N$ variables into 3 multilinear polynomials $f(\vec{X}), g(\vec{X}), h(\vec{X})$ via interpolation over the hypercube $B_n = \{0, 1\}^n$;
    - for each element $\vec{b} = (b_1, \ldots, b_n)$ in boolean hypercube, we have $$f(\vec{b}) * g(\vec{b}) - h(\vec{b}) = 0.$$
    - this is equivalent to $c(\vec{X}) = f(\vec{X})*g(\vec{X}) - h(\vec{X})$ evaluates to 0 over boolean hypercube. Note that $c(X)$ is **not** a multilinear polynomial. 
    - But MLE $\tilde{c}(\vec{X})$ of $c(\vec{X})$ **is** a multilinear polynomial.$$\tilde{c}(\vec{X}) = \sum_{b \in B^n} \textrm{eq}(\vec{\textbf{b}}, \vec{X})*[f(\vec{b})*g(\vec{b}) - h(\vec{b})].$$
    - the above $N$ constraints imply that $\tilde{c}(\vec{X})$ is zero polynomial: 
        
    - [x] By [Schwartz-Zippel lemma](https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma), we know that the probability that a non-zero multilinear polynomial $p(\vec{X})$ evaluates at a random point $\vec{\beta} \in F^n$ is no larger than $\frac{1}{|F|}$. This means that if a multilinear polynomial $p(\vec{X})$ evaluates to 0 at a random point, then we have $p(\vec{X}) = 0$ with high probability ($1-\frac{1}{|F|}$).
          
      Therefore we can use this zero testing technique:
      
      > sample a random challenge $\vec{\beta} \in F^n$ check if $\tilde{c}(\vec{\beta}) = 0$.

    - Therefore zero check of $\tilde{c}(X)$ is done via 
        
        $$\textrm{prover.sumcheck}(\textrm{poly} = eq(\vec{x}, \vec{\beta})*[f(\vec{x})*g(\vec{x}) - h(\vec{x})], \textrm{sum} = 0)$$
### 1.2 MLE

MLE of a multi-variate function $g: F^n \rightarrow F$.

- Background
      $$\textrm{eq}(x_1, \ldots, x_n, y_1, \ldots, y_n) = \prod_{i=1}^n [(x_i * y_i) + (1-x_i)*(1-y_i)]$$
      It's easy to see for any two elements $(\vec{X}, \vec{Y})$ from the boolean hypercube $B^n$: $\textrm{eq}(\vec{X}, \vec{Y}) = 1$ iff $\vec{X} = \vec{Y}$.
      
- Lagrange basis for $n$-variate multilinear polynomials
    
  - [x] how to uniquely recover a $n$-variate multilinear polynomial? 
    
    > Each $n$-variate multilinear polynomial is uniquely determined by its evaluations ($2^n$ elements) over boolean hypercube!
        
    $f(X_1, X_2, \ldots, X_{n-1}, X_n) = f_0(X_1, \ldots, X_{n-1}) + f_1(X_1, \ldots, X_{n-1}) * X_n$
    
    1. $f_0(x_1, \ldots, x_{n-1}) = f(x_1, \ldots, x_{n-1}, 0)$
    2. $f_1(x_1, \ldots, x_{n-1}) = f(x_1, \ldots, x_{n-1}, 1) - f(x_1, \ldots, x_{n-1}, 0)$.

    We can prove this using induction starting with the simple fact
    
     > a linear uni-variate polynomial can be uniquely recovered by **two** evaluations.
        
  - $L_{\vec{\textbf{b}}}(\vec{X}) = \textrm{eq}(\vec{\textbf{b}}, \vec{X}) = 1$ if $\vec{X} = \vec{\textbf{b}}$ and 0 if not.
      
  - MLE of $g$ (denoted by $\tilde{g}$) is a $n$-variate multilinear polynomial: $$\tilde{g}(\vec{X}) = \sum_{\vec{\textbf{b}} \in B^n} \textrm{eq}(\vec{\textbf{b}}, \vec{X})*g(\vec{\textbf{b}}).$$

### 1.3 Sumcheck


   $n$-variate polynomial $f(X) \in F[\vec{X}]: F^n \rightarrow F$, the scripts generated in sumcheck protocol are:
   - for each round i from 1 to n, 
       - P sends V:  $\big[f^i(0), f^i(1), f^i(2), \ldots, f^i(d) \big]$ where $$f^i(X) = \sum_{\vec{b} \in B_{n-i}} f(r_1, \ldots, r_{i-1}, X, \vec{b}).$$

       - In each round, the sumcheck prover needs to do summation over $2^{n-i}$ elements from hypercube $B_{n-i}$.
       
       - V sends P: challenge $r_i$;
  
    
## 2. textbook GKR for layered circuit

- textbook GKR: gkr08 paper, cmt12 paper 
    - the relation between values at layer $i$ and layer $i+1$ is that for each gate $g \in B_{s}$,
     $$
      \begin{eqnarray}
        \tilde{v}_i(g) &=& \sum_{b, c \in \{0, 1\}^s} \tilde{\textrm{add}}(g, b, c) * \big(\tilde{v}_{i+1}(b) + \tilde{v}_{i+1}(c)\big) + \\ & &\tilde{\textrm{mul}}(g, b, c) * \big(\tilde{v}_{i+1}(b) + \tilde{v}_{i+1}(c)\big).
    \end{eqnarray}
      $$
    Since both sides of the above equation are multilinear polynomials in $g$, we know that **this equation holds for any $z \in F^s$**.
     
     $$
      \begin{eqnarray}
        \tilde{v}_i(z) &=& \sum_{b, c \in \{0, 1\}^s} \tilde{\textrm{add}}(z, b, c) * \big(\tilde{v}_{i+1}(b) + \tilde{v}_{i+1}(c)\big) + \\ & &\tilde{\textrm{mul}}(z, b, c) * \big(\tilde{v}_{i+1}(b) + \tilde{v}_{i+1}(c)\big).
    \end{eqnarray}
      $$
      
    - MLE math: 
        1. $\tilde{\textrm{add}}(z, b, c) = \sum_g \textrm{eq}(g, z) \cdot \textrm{add}(g, b, c)$.
        2. closed form for $\tilde{\textrm{add}}(z, x, y)$:
             - For any $p \in \{0,1\}^{3s}$, we define $p_0 = p[0:s], p_1 = p[s:2s], p_2 = p[2s:3s]$;
            - For any $z, x, y \in F^s$, we have $$\tilde{\textrm{add}}(\vec{z}, \vec{x}, \vec{y}) = \sum_{p \in \{0, 1\}^{3s}: \textrm{add}(p) =1} eq(p_0, \vec{z}) \cdot eq(p_1, \vec{x}) \cdot eq(p_2, \vec{y}).$$


- [x] problem: the selector $\tilde{\textrm{add}}(\vec{z}, \vec{b}, \vec{c})$ has $2s$ variables. In round $j$ of sumcheck prover, an naive implementation will do $2^{2s-j}$ summation. how to reduce the time from $O(S^3)$ to $O(S \log S)$?

    - Check **appendix A** of [CMT12 paper](https://arxiv.org/abs/1105.2003). 
    - Let's define $\vec{p}_j = (p_{j+1}, \ldots, p_{3s})$;
    - Let $\vec{r}_j = (r_1, \ldots, r_{j-1}) \in F^{j-1}$ and $\vec{b} = (b_{j+1}, \ldots, b_{3s})$, then we have 
            $$
            \begin{eqnarray}
            \sum_{\vec{b} \in \{0,1\}^{2s-j}} \tilde{\textrm{add}}(\vec{z}, \vec{r}, X_j, \vec{b}) & = & \sum_{p \in \{0, 1\}^{3s}: \textrm{add}(p) =1} \sum_{\vec{b}} \chi_p(\vec{r}, X_j, \vec{b}) \\
            & = & \sum_{p \in \{0, 1\}^{3s}: \textrm{add}(p) =1} \chi_p(\vec{r}, X_j, \vec{p}_j)
            \end{eqnarray}
            $$
    
    - $\chi_p$ function has the nice form
        $$
        \chi_p(\vec{z}, \vec{r}_j, X_j, \vec{p}_j)= \textrm{eq}(X_{j}, p_{s+j}) \prod_{i=1}^s \textrm{eq}(p_i, z_i) \prod_{i=1}^{j-1} \textrm{eq}(p_{i+s}, r_i) 
        $$
        
        Therefore we can store `eq_rand[p]` for each $p$ and update it incrementally: `eq_rand[p] *= eq(p[s+j], r_j)`.
        
    - Therefore, the GKR prover runs in $O(2^s)$ time for each round.
        

- [ ] The correctness of $\tilde{v}_i(z)$ is reduced to the correctness of evaluations of $\tilde{v}_{i+1}(X)$ at points $\{ \omega_1, \omega_2 \}$. how to merge these two into one?


- [x] linear time GKR for layered circuit: [Libra19 paper](https://eprint.iacr.org/2019/317)

    - we can write the gkr layer reduction formula in another form by defining one helper multilinear polynomial $g_z(X)$: 
      
      - $g_z(X) = \sum_{c \in \{0,1\}^s} \tilde{\textrm{mul}}(z, X, c) * \tilde{v}_{i+1}(c)$;
    - textbook GKR relation can then be rewrote as 
          $$
          \begin{eqnarray}
          \tilde{v}_i(z) & = & \sum_{b, c} \tilde{\textrm{mul}}(z, b, c)*\tilde{v}_{i+1}(b) * \tilde{v}_{i+1}(c) \\ 
          & = & \sum_b \tilde{v}_{i+1}(b) * \sum_c \tilde{\textrm{mul}}(z, b, c) * \tilde{v}_{i+1}(c) \\
          & = & \sum_b \tilde{v}_{i+1}(b) * g_z(b)
          \end{eqnarray}
          $$
    - **Therefore we can replace the old $2s$-variate sumcheck with two new $s$-variate sumchecks**.
        - phase/step 1 sumcheck: 
            
            $$\tilde{v}_i(z) = \sum_b \tilde{v}_{i+1}(b) * g_z(b)$$ => $\tilde{v}_{i+1}(x)$ and $g_z(x)$ where $x \in F^s$;
            
        - phase/step 2 sumcheck:
            $$g_z(x) = \sum_{c \in \{0,1\}^s} \tilde{\textrm{mul}}(z, x, c) * \tilde{v}_{i+1}(c)$$ => $\tilde{\textrm{mul}}(z, x, y)$ and $\tilde{v}_{i+1}(y)$ where $y \in F^s$.
     
    - [x] how to get $g_z(X)$'s MLE repr?
        - Since $\tilde{\textrm{mul}}(z, b, c) = \sum_{a \in B_s} \textrm{eq}(z, a) \textrm{mul}(a, b, c)$, we have for each $b \in B_s$
            $$
            \begin{eqnarray}
            g_z(b) & = & \sum_c \tilde{\textrm{mul}}(z, b, c) * \tilde{v}_{i+1}(c) \\
            & = & \sum_{a, c \in B_s} \textrm{eq}(z, a) * \textrm{mul}(a, b, c) * \tilde{v}_{i+1}(c);
            \end{eqnarray}
            $$
        
        - Let $P_b = \{a: \exists c, \textrm{mul}(a, b, c) = 1\}$ be the subset of gates at layer $i$ that has gate $b$ at layer $i+1$ as left input. 
        
        - We can then do only $|P_b|$ summation:
            $$
            \begin{eqnarray}
            g_z(b) & = & \sum_{a, c \in P_b} \textrm{eq}(z, a) * \tilde{v}_{i+1}(c);
            \end{eqnarray}
            $$
        
        - For some random vector $z \in F^s$, we can compute $\textrm{eq}(z, b)$ for all elements of $B_s$ in $O(2^s)$ time. 
        - since $\sum_b |P_b| \le 2^s$, we have the desired property that getting $g_z(b)$ for all $b$ runs in $O(2^s)$ time.

    - [x] for each $c \in B_s$, how to compute $\tilde{\textrm{mul}}(z, x, c)$ efficiently?
    
       - $\tilde{\textrm{mul}}(z, x, c) = \sum_{a, b} \textrm{eq}(z, a) * \textrm{eq}(x, b) * \textrm{mul}(a, b, c)$.
       
       - Let $Q_c = \{ a: \exists c, \textrm{mul}(a, b, c) = 1\}$ be the subset of gates at layer $i$ that has gate $c$ at layer $i+1$ as right input.
       - `G_z[a] = eq(z, a)` is stored in $O(2^s)$ space and computed in $O(2^s)$ time.
       - Similarly, `G_x[a] = eq(x, a)` can also be stored in $O(2^s)$ space.
       - Therefore $\tilde{\textrm{mul}}(z, x, c) = \sum_{a, b \in Q_c} \textrm{eq}(z, a) * \textrm{eq}(x, b)$.
    
- [ ] how does libra work with data parallel circuit?

## 3. GKR for layered data parallel circuit

- $2^b$ is the number of instances; $s$ is the number of variables per layer in the inner circuit.

- The relation between layer $i$ and layer $i+1$ is 

    $$
    \begin{eqnarray}
    v_i(g_1, g_2) & = &  \sum_{b_1, c_1 \in B_s} \tilde{\textrm{mul}}(g_1, b_1, c_1) * \tilde{v}_{i+1}(b_1, g_2) * \tilde{v}_{i+1}(c_1, g_2) 
    \end{eqnarray}
    $$
    
   With MLE, we have 
   $$
    \begin{eqnarray}
    \tilde{v}_i(z_1, z_2) & = & \sum_{g_1 \in B_s, g_2 \in B_b} \textrm{eq}(z_1, g_1) * \textrm{eq}(z_2, g_2) \sum_{b_1, c_1} \tilde{\textrm{mul}}(g_1, b_1, c_1) * \tilde{v}_{i+1}(b_1, g_2) * \tilde{v}_{i+1}(c_1, g_2) 
    \end{eqnarray}
    $$

## 4. GKR for unlayered data parallel circuit (ceno GKR)



## QA


## Appendix A. useful docs (survey / paper / video)

- talk by Ariel Gabizon (★★★★★) {%youtube tSpvk3EGRSM %}

- a note on GKR by j.thaler (★★★★★) https://people.cs.georgetown.edu/jthaler/GKRNote.pdf