2
$\begingroup$

I am reading about GKR protocol from Justin Thaler's book - Proofs, Arguments & Zero Knowledge

On Page 59,

In the first message, $P$ tells $V$ the (claimed) output(s) of the circuit. The protocol then works its way in iterations towards the input layer, with one iteration devoted to each layer.

I am a little confused about what exactly iteration means here. Does one iteration means one sum-check proof or can each iteration (corresponding to a layer) contain multiple sum-check proofs?

Page 61, Lemma 4.7

$W_i(z) = \sum_{b,c \in \lbrace 0,1 \rbrace^{k_{i+1}}} add_i (z,b,c)\cdot (W_{i+1}(b)+W_{i+1}(c)) + mult_i(z,b,c)\cdot (W_{i+1}(b)\cdot W_{i+1}(c))$

Consider this circuit from Page 65

enter image description here

For e.g. for the circuit above, in the first (topmost) layer, won't we have to run the sum-check protocol for both $W_0(0)=4$ & $W_0(1)=2$ separately? And in the next layer, we will need 4 sum-check protocol runs - $W_1(0,0)=1$, $W_1(0,1)=4$, $W_1(1,0)=2$ & $W_1(1,1)=1$. And so on?

I can think of making it just one sum-check per layer but that will work only if all the gates in that layer are addition gates.

If all the gates in a layer are addition gates, then we can change the sum-check equation to

$\sum_{z \in s} W_i(z) = \sum_{z \in \lbrace 0,1 \rbrace^{log(s)}} \sum_{b,c \in \lbrace 0,1 \rbrace^{k_{i+1}}} add_i (z,b,c)\cdot (W_{i+1}(b)+W_{i+1}(c)) + mult_i(z,b,c)\cdot (W_{i+1}(b)\cdot W_{i+1}(c))$

Where number of gates in that layer is $s$

But this will not work unless all gates in that layer are addition gates.

$\endgroup$
2
  • $\begingroup$ I surmise that each circuit layer requires one sum-check. The GKR protocol aims to compel the prover to demonstrate, via the sumcheck protocol, to the verifier that the computation of each layer is correct. This layer-by-layer proof approach can reduce the output of the circuit back to the input of the circuit. $\endgroup$
    – X.H. Yue
    Commented Feb 27 at 8:20
  • $\begingroup$ Sorry, I'm not able to recall exactly the technical details of the GRK protocol, because it's so old... $\endgroup$
    – X.H. Yue
    Commented Feb 28 at 1:59

1 Answer 1

2
+50
$\begingroup$

Short answer

The GKR protocol consists of one execution of the sum-check sum protocol per layer.

Long answer

Considering that a layer has $2^{k}$ gates, the function $W_i: \{0,1\}^k \rightarrow \mathbb{F}$, defined as

$$W_i(z) = \sum_{b,c \in \lbrace 0,1 \rbrace^{k}} add_i (z,b,c)\cdot (W_{i+1}(b)+W_{i+1}(c)) + mult_i(z,b,c)\cdot (W_{i+1}(b)\cdot W_{i+1}(c))$$

maps every gate $z$ of the $i$-th layer to its output value. You should verify and convince yourself about this before continuing the analysis (basically, for each gate $z$, there will be a single pair $(a, b)$, corresponding to the left and right input wires of $z$, thus, only one instance of $add(z, a, b)$ or of $mult(z, a, b)$ will be equal to 1 in the summations in $W$).

Now, what the GKR protocol does is to define a low-degree polynomial extension $\tilde{W}:\mathbb{F}^k \rightarrow \mathbb{F}$ of $W_i$ and it applies the sum-check sum protocol on $\tilde{W}$ running over the variables $a$ and $b$, not on $z$ (so there are not 3 summations as you wrote!).

In other words, for some function $f$, we can write $$\tilde{W}(z) = \sum_{a, b \in \{0, 1\}^k} f(z, a, b)$$ And when given a polynomial $G$ claimed to be equal to $\tilde{W}$, we can pick a random field element $r^\star$ and check if $G(r^\star) = \tilde{W}(r^\star)$. By the Schwartz-Zippel lemma, if this equality is true, then we can assume $G$ and $\tilde{W}$ are indeed equal. However the verifier can only compute $y = G(r^\star)$, but not $\tilde{W}(r^\star)$, since they don't know $\tilde{W}$ (only the prover does).

So, they both run the sum-check protocol (running on all the $2^{k+1}$ possible values for the pairs $(a, b)$) to verify that $$y = \sum_{a, b \in \{0, 1\}^k} f(r^\star, a, b)$$

Notice that if the sum-check sum protocol has a positive answer, we conclude that $y = \sum_{a, b \in \{0, 1\}^k} f(r^\star, a, b)$, thus, $G(r^\star) = \tilde{W}(r^\star)$, thus, $G = \tilde{W}$, thus, all gates of the $i$-th layer were evaluated correctly.

(There is a detail here: at the end of the protocol, the verifier cannot finish the sum-check sum protocol, since this requires evaluating $f(r^\star, a^\star, b^\star)$ for random $r^\star, a^\star, b^\star$. This check is then "shifted" to the next layer and the GKR protocol continues recursively).

$\endgroup$
3
  • $\begingroup$ Your question was about executing the sum-check protocol one or multiple times per layer. As I said in the answer, you just need one. It seems that she is talking about how you go from layer i to layer i+1 in the recursive step of GKR. If so, this is covered in Thaler's book and, basically, for the next layer you again just need the sum-check protocol one time because of the 2-to-1 trick. But she might also be talking about something else or about a specific application of the GKR protocol. I didn't have time to watch the full video. $\endgroup$ Commented Mar 1 at 14:44
  • $\begingroup$ @user93353 As I said, I didn't have time to check the video, so I don't know what she is talking about. When I heard "2-to-1 trick" I thought it was the technique to collapse the verification of $W(r')$ and $W(r'')$ into a single verification (and maybe it is). But anyway I've answered your question. If there is something you don't understand in my answer, I will be glad to clarify it. $\endgroup$ Commented Mar 1 at 19:56
  • $\begingroup$ Btw, consider this: sum-check protocol has verification cost > log|C| . If it was applied to every gate, GKR's verification cost would be |C| log |C|, which is heavier than running the circuit locally, so, it would be pointless. $\endgroup$ Commented Mar 1 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.