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)\):

Note: the output layer is layer 0

Your point of view caught my eye and was very interesting. Thanks. I have a question for you.

what question?

Your article helped me a lot, is there any more related content? Thanks!

https://www.shuangcrypto.com/2024/06/15/gkr-part-2-example/