Skip to main content
Cryptography

Return to Answer

Bounty Ended with 50 reputation awarded by user93353
the extension is not multilinear, as it is a product of multilinear extensions
Source Link
Hilder Vitor Lima Pereira
Hilder Vitor Lima Pereira
  • 7.4k
  • 1
  • 25
  • 43

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 multilinearlow-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).

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 multilinear 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}$.

(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).

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

Source Link
Hilder Vitor Lima Pereira
Hilder Vitor Lima Pereira
  • 7.4k
  • 1
  • 25
  • 43

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 multilinear 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}$.

(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).