GKR -Part1: Arithmetization - Shuang's Crypto Notes

Take example circuit in figure 1, following the Arithmetization described in post, a step by step description of GKR arithmetication of a concrete example.

Notations representing index of gates

$q’\in \{0,1\}^{b_N}$: The index of one of the $N$ identical copies of the base circuit $C_0$ within $C$.

$q\in \{0,1\}^{b_G}$ is the gate index within the base circuit, different layer has different $b_G$

$i\in [d]=\{0,1,…,D\}$ the index of the layer within the base circuit

In the example, $N=2, b_N=1$.

$h’\in \{0,1\}^{b_N}$: The index of one of the $N$ identical copies of the base circuit $C_0$ within $C$. The same definition of $q’$, but we need to present the values transfer from layer $i+1$ to layer $i$, thus using a new notation for layer $i+1$.

$h_R,h_L \in \{0，1\}^{b_G}$, two gate indexs within the base circuit, the same as $q$ but in layer $i+1$

Notations representing functions

$add_i(q,h_L,h_R)=1$ $iff$ gate $q$ at layer $i$ takes both $h_L$ and $h_R$ as inputs from layer $i+1$ and is an addition gate.

$mul_i(q,h_L,h_R)=1$ $iff$ gate $q$ at layer $i$ takes both $h_L$ and $h_R$ as inputs from layer $i+1$ and is a multiplication gate.

$eq(a,b)$ returns $a==b$

Notations represent values that flow through the circuit

$V(q’,q)$: output value of gate $q’,q$ at layer $i$

function that captures the transaction from one layer to the next

$P_{q’,q,i}(h’,h_L,h_R)=eq(h’,q’) \cdot $

$$[add_i(q,h_L, h_R)\cdot (V_{i+1}(q’,h_L)+V_{i+1}(q’,h_R))+mul_i(q,h_L,h_R)\cdot V_{i+1}(q’,h_L)\cdot V_{i+1}(q’,h_R)]$$

Notes about $P_{q’,q,i}(h’,h_L,h_R)$:

– $eq(h’,q’)$ limits only the gate that has index $q’$ and on layer $i-1$ (limited by $V_{i+1}$) can be counted. Recall $q’$ is the index of one of $N$ identical base circuit $C_0$ with $C$.

– Give a layered circuit with many base circuit parallel. The fixed functions that can be pre-computed are $add_i(q,h_L, h_R),mul_i(q,h_L,h_R)$

Then we have:

$$V_i(q’,q)=\sum_{h’\in\{0,1\}^{b_N}}\sum_{h_L<h_R\in\{0,1\}^{b_G}}P_{q’,q,i}(h’,h_L,h_R)$$

The equation basically go through all the gate in layer $i+1$ (with all the copies of base circuit), the gates that actually contribute to the final result will be select by $eq(h’,q’),mul_i(q,h_L,h_R),add_i(q,h_L, h_R)$. They are like the selector polynomial in plonkish Arithmetization.

let’s see the example, and compute one $V_i(q’,q)$: