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

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))$

The above is the equation on which the Sum-Check Protocol will be run on each layer $i$ from $i = 0$ to $d-1$.

Consider an example Circuit from the book

enter image description here

Let's consider the Sum-Check Protocol for the middle layer - there are 4 gates. Each of these 4 gates can be the $z$ in the equation for that layer.

So who chooses which of the 4 gates is used for that layer? Is it the Prover or the Verifier?

I don't think it matters - we use the Sum-Check protocol to verify whether the polynomial has been constructed correctly by the Prover for that layer - the verifier uses the probabilistic Schwartz–Zippel lemma to verify the polynomial & any gate should do? But I am just curious & also I am trying to check whether my assumption that it doesn't matter is correct?


$P$ sends $g_1$ to $V$. $V$ then computes $g_1(0) + g_0(1)$ - what does he then check if this addition is equal to? Which gate's output does he check if it's equal to?


1 Answer 1


Actually nobody "chooses a gate $z$". What the protocol does is to define a multilinear polynomial extension $\tilde{f}$ of $$ f(a, b) = 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)) $$ then noticing that the multilinear polynomial extension of $W_i(z)$ is $\tilde{W}_i(z) = \sum_{a, b \in \{0,1\}^{k_i}} \tilde{f}(a,b)$, GKR protocol uses the sumcheck sum protocol to verify that $\tilde{W}_i$ is correct.

For this, the client proceeds by picking random field elements $r_i$'s, sending them to the server, receiving one-variable polynomials, etc. But none of those $r_i$'s correspond to a gate.

You can think that by verifying $\tilde{W}_i$ you are verifying if all the gates of the $i$-th layer are correct (instead of verifying one single gate).

  • $\begingroup$ While running the sum-check, the prover has to first send the summation value to the verifier, right? Now for evaluating the summation on the Right Hand Side which is the same as the value of $W(z)$, doesn't he have to fix a $z$ first? For e.g. in my circuit diagram, if he picks the 1st gate in the output layer (Gate 0 of layer 0), then the value which P sends to V would be 4. If he pickets Gate 1 of layer 0, then he would send the value 2. How would he do that without picking a gate? $\endgroup$
    – user93353
    Apr 15 at 13:55
  • $\begingroup$ No... The protocol starts with P sending to V a function D such that D(i) = W_0(i) for each gate i of the layer zero (output layer). So V can obtain the output by evaluating D (in your example, we could have D(0) = 4 and D(1) = 2, then V would never receive "4", but the function D that allows V to obtain 4). Now, V has to check if D is indeed W_0. For this, the client samples a random $r_0$ and proceeds with the protocol to check that $D(r_0) = W_0(r_0)$. So, the client doesn't have to pick any gate. $\endgroup$ Apr 15 at 16:35
  • $\begingroup$ No... $g_1(0)$ and $g_1(1)$ are not gate values! Remember that $g_1(X)$ is a polynomial corresponding to adding up $f(a, b)$ for all the values of the bits representing variables $a, b$, except for the first bit. So $g_1(X)$ doesn't represent the any output gate. $\endgroup$ Apr 16 at 11:48
  • $\begingroup$ V should check that $g_1(0) + g_1(1) = D(r_0)$, where $D$ is the function V received in the very beginning and $r_0$ is the random field element V sampled before starting the sumcheck protocol (the $r_0$ I described in my first comment here). Thus, as I said, V (or P) never chooses a specific gate. $\endgroup$ Apr 16 at 17:19

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.