performance:
Prover is \(\mathcal{O}(C)\)
Verifier is \(\mathcal{O}(d\log C)\) for d-depth log-space uniform circuit.
note: in sumcheck/GKR context, the size of the circuit usually is described as \(2^l\), namely, the inputs of the circuit is \(2^l\), for a linear prover in this setting, has complexity \(\mathcal{O}(2^l)\), a logarithmic verifier has \(\mathcal{O}(l)\) complexity
Building Blocks
sumcheck protocol
performance:
Verifier time is \(O(dl)\): \(l\) is the total variable number, \(d\) is the variable-degree. (note the total variable number \(l\) means there are \(2^l\) inputs in the circuit)
Prover time depends on the degree and the sparsity of \(f\)
Proof size: \(O(dl)\), as there will be in totoal \(l\) rounds, each round a polynomial of degree \(d\) will be sent, and it is determined by \(d+1\) points
GKR protocol
Layer numbering
some time the order of the layer is confusing in the paper and code, just to make it clear, in the paper it specifies:
page 9:
Verifier’s work
what the complexity of the verifier? what computation the verifier needs to make, in these computations, which part is computed locally without the need to rely on the prover, and which part needs to be computed depended on prover’s responses?
Verifier’s computation:
for each layer, following the equation below, the verifer needs to compute the multilinear extension of \(f_i(x,y)\), to do this, the verifier needs
- the outputs of this layer, for layer 0 it becomes the output of the circuit, for other layers, the outputs are claimed in the last round of sumcheck protocol of the previous circuit layer. With the outputs of the layer, its multilinear extension can be computed directly.
- The multilinear extension \(\widetilde{add}_{i+1}(u,v)\) and \(\widetilde{mult}_{i+1}(u,v)\) (they only depend on the wiring pattern of the circuit, but not on the values.) The verifier needs these polynomials in the last round of the sumcheck protocol.
- \(V_{i+1}(u)\) and \(V_{i+1}(v)\) , for the last round of the sumcheck protocol.
\(\tilde{V}_i(g) = \sum\limits_{x,y \in \{0,1\}^{s_{i+1}}} f_i(x,y)\)
\(= \sum\limits_{x,y \in \{0,1\}^{s_{i+1}}} \left( \widetilde{add}_{i+1}(g,x,y)(\tilde{V}_{i+1}(x) + \tilde{V}_{i+1}(y))\right.\)
\(\left. + \tilde{mult}_{i+1}(g,x,y)(\tilde{V}_{i+1}(x)\tilde{V}_{i+1}(y)) \right)\)
Some confusing part of this equation:
- the polynomial has input \(g\), why in the multilinear extension representation, there are only two variables \(x, y\) without \(g\)?
explanation:
- the multilinear extension of \(f_i(x,y)\) is not\(\tilde{V}_i\), recall the closed form expression:
$$\tilde{f}(x_1,\ldots, x_l)=\sum\limits_{b_i\in\{0,1\}}f(b_1,\ldots, b_l)\prod\limits^{l}_{i=1}(x_i\cdot b_i + (1-x_i)(1-b_i))$$
it’s not the same.
- the below polynomial is a function of variable \(g\)
\(\tilde{V}_i(g) = \sum\limits_{x,y \in \{0,1\}^{s_{i+1}}} f_i(x,y)\)
\(= \sum\limits_{x,y \in \{0,1\}^{s_{i+1}}} \left( \tilde{a}dd_{i+1}(g,x,y)(\tilde{V}{i+1}(x) + \tilde{V}{i+1}(y))\right.\)
\(\left. + \tilde{m}ult_{i+1}(g,x,y)(\tilde{V}{i+1}(x)\tilde{V}{i+1}(y)) \right)\)
which means, the verifier’s challenge is for \(g\), has nothing to do with \(x,y\)
for each layer’s sumcheck, prover will firstly claim the output of layer,
To make things clear, \(\tilde{V}(g)\) and \(\tilde{add}_{i+1}(g,x,y)\) may look confusing, because for each layer, there will be multiple gate outputs, indexed by \(g\), but these multiple values are all “encoded” into the polynomial \(\tilde{V}(g)\), so when talking about sumcheck, it is all about this single polynomial, but why there are two polynomials from the next layer? is because the gate set to have two inputs, they will be represented by two variates. they are the same polynomial, but evaluated in different points.
There are two ways to combine the two claims into one:
Condensing to one claim
random linear combination
Upon receiving the two claim \(\tilde{V_i}(u)\) and \(V_i(v)\), the verifier selects challenge \(\alpha_i , \beta_i\)
Linear GKR
Complexity of Sumcheck
In GKR, every round of the sumcheck protocol, the prover get a new multivariate polynomial:
\(f(r_1, …,r_{i-1},b_i,b_{i+1},…,b_l)\) for round \(i\), this polynomial needs \(2^{l-i+1}\) entries to store (as it is \(l-i+1\) variables multilinear variable polynomial)
look into the detail of the computation:
Algorithm 1: evaluations of the Function on hypercube.
Evaluate the function from the bookkeeping table:
Recall the Closed-form expression for multilinear extension of a polynomial on hypercube:
$$\tilde{f}(x_1,\ldots, x_l)=\sum\limits_{b_i\in\{0,1\}}f(b_1,\ldots, b_l)\prod\limits^{l}_{i=1}(x_i\cdot b_i + (1-x_i)(1-b_i))$$
We can re-write this equation into
\(\tilde{f}(x_1,\ldots, x_l)=\sum\limits_{b_i\in\{0,1\}}f(0,b_2,\ldots, b_l)(1-x_1)\prod\limits^{l}_{i=2}(x_i\cdot b_i + (1-x_i)(1-b_i))\)
\(+\sum\limits_{b_i\in\{0,1\}}f(1,b_2,\ldots, b_l)\cdot x_1\cdot\prod\limits^{l}_{i=2}(x_i\cdot b_i + (1-x_i)(1-b_i))\)
plug in \(x_1=r_1\) we can get
\(\tilde{f}(r_1,x_2\ldots, x_l)=\)
\(\sum\limits_{b_i\in\{0,1\}}f(0,b_2,\ldots, b_l)(1-r_1)\prod\limits^{l}_{i=2}(x_i\cdot b_i + (1-x_i)(1-b_i))\)
\(+\sum\limits_{b_i\in\{0,1\}}f(1,b_2,\ldots, b_l)\cdot r_1\cdot\prod\limits^{l}_{i=2}(x_i\cdot b_i + (1-x_i)(1-b_i))\)
\(=\sum\limits_{b_i\in\{0,1\}}\left( f(0,b_2,\ldots, b_l)(1-r_1)+f(1,b_2,\ldots, b_l)\cdot r_1 \right)\prod\limits^{l}_{i=2}(x_i\cdot b_i + (1-x_i)(1-b_i))\)
which essentially means, the Multilinear extension of polynomial \(\left( f(0,b_2,\ldots, b_l)(1-r_1)+f(1,b_2,b_l)\cdot r_1\right)\)
The bookkeeping table
Recall that in each round of the sumcheck protocol, the prover sends a univariate polynomail:
$$f_i(x_i)\stackrel{def}{=}\sum\limits_{b_{i+1},…,b_l\in \{0,1\}}f(r_1,…,r_{i-1},x_i,b_{i+1},…,b_l)$$
and prover needs to provides \(f_i(r_i), f_i(0), f_i(1), f_i(2)\) (why \(f_i(2)\)?)
To compute these value, we need to have
for \(f_i(0)\) :
let me take an example of \(l=3\)
bookkeeping matrix \(\mathbf{A}\):
\(\begin{bmatrix}i=0 & \tilde{f}(b_1,b_2,b_3) & b_1,b_2,b_3 \in \{0,1\} \\ & f(0,0,0) & f(0,0,1) & f(0,1,0) & f(0,1,1) & f(1,0,0) & f(1,0,1 ) & f(1,1,0) & f(1,1,1) \\ i=1 & \tilde{f}(r_1,b_2,b_3) & b_2,b_3 \in \{0,1\}\end{bmatrix}\)
now in round \(i=1\), the prover want to compute \(f_1(x_1)\stackrel{def}{=}\sum\limits_{b_{2},b_3\in \{0,1\}}f(r_1,b_2,b_3)\), we need all the values of \(f(r_1, b_2,b_3), b_2,b_3\in \{0,1\}\)
observe that
\(\left( f(0,b_2,b_3)(1-r_1)+f(1,b_2,b_3)\cdot r_1 \right)=f(r_1,b_2,b_3)\)
which means the values we want can be computed from the record in matrix \(\mathbf{A}\) of the last round
\(\begin{bmatrix}i=0 & \tilde{f}(b_1,b_2,b_3) & b_1,b_2,b_3 \in \{0,1\} \\ & f(0,0,0) & f(0,0,1) & f(0,1,0) & f(0,1,1) & f(1,0,0) & f(1,0,1 ) & f(1,1,0) & f(1,1,1) \\ i=1 & \tilde{f}(r_1,b_2,b_3) & b_2,b_3 \in \{0,1\}\\ & \left( \begin{aligned}&f(0,0,0)(1-r_1)\\&+f(1,0,0)r_1\end{aligned} \right)& \left( \begin{aligned}&f(0,0,1)(1-r_1)\\&+f(1,0,1)r_1\end{aligned} \right)& \left( \begin{aligned}&f(0,1,0)(1-r_1)\\&+f(1,1,0)r_1\end{aligned} \right)& \left( \begin{aligned}&f(0,1,1)(1-r_1)\\&+f(1,1,1)r_1\end{aligned} \right)\end{bmatrix}\)
now when the prover want s to compute the point on the polynomial of each round, he sum up all the values in one row. This is described in algorithm 2
Algorithm 3 is just two instance of algorithm 2 and compute their product in each round.
this polynomial can be computed from
\(\tilde{f}(r_1,…,r_i, x_)\)
The prover will use a bookkeeping table \(\mathbf{A}\) to record this polynomial of each round, namely, record the evaluations of the polynomial on hypercube.
bookkeeping matrix (a) is initialised by all the evaluations of f on hypercube.
ots, b_l)\cdot r_1 \right)\) on hypercube is \(\tilde{f}(r_1,x_2\ldots, x_l)\)
Linear-time sumcheck for products of multilinear functions
Observe the equation of the polynomial in each layer:
the class of functions can be conclude as:
\(\sum\limits_{x,y\in \{0,1\}^l}f_1(g,x,y)f_2(x)f_3(y)=\sum\limits_{x\in{0,1}^l}f_2(x)\sum\limits_{y\in \{0,1\}^l}f_1(g,x,y)f_3(y)=\sum\limits_{x\in \{0,1\}^l}f_2(x)h_g(x)\)
which is related to (let’s only consider the multiplication gate for now)
\(\left(\alpha_i \tilde{m}ult_{i+1}(u,x,y) + \beta_i \tilde{m}ult_{i+1}(v,x,y)\right) \left(\tilde{V}{i+1}(x) \tilde{V}{i+1}(y)\right))\)
precisely (I will add multilinear extension mark to these functions, as otherwise, it can be confusing in the next steps):
\(\tilde{f_1}\) is equivalent to \(\tilde{V}_{i+1}(y)\)
\(\tilde{f_2}\) is equivalent to \(\tilde{V}_{i+1}(x)\)
\(\tilde{h_g}\) is equivalent to \(\left(\alpha_i \tilde{m}ult_{i+1}(u,x,y) + \beta_i \tilde{m}ult_{i+1}(v,x,y)\right) \tilde{V}_{i+1}(y)\)
note: even though \(f_1\) has three variable, but as the function consists of gates, variables are bounded by the number of the inputs, thus it’s evaluations on hypercube is a sparse array with \(\mathcal{O}(2^{2l})\) non zero elements.
Initializing the bookkeeping table
Analyzing:
\(\sum\limits_{x,y\in \{0,1\}^l}f_1(g,x,y)f_2(x)f_3(y)=\sum\limits_{x\in{0,1}^l}f_2(x)\sum\limits_{y\in \{0,1\}^l}f_1(g,x,y)f_3(y)=\sum\limits_{x\in \{0,1\}^l}f_2(x)h_g(x)\)
- \(h_g(x)\) still has the variable \(g\), and the above summation is a uni-variate function of \(g\)
- \(g\) in this context will be the challenge from the verifier. in hypercube context, it is in index of the gate in this layer.
firstly, let’s try to make \(h_g\) that has \(\mathcal{O}(2^{3l})\) into \(\mathcal{O}(2^{2l})\)
as \(f_1(g,x,y)\) has complexity of \(\mathcal{O}(2^l)\), to utilized this fact, we can just consider the set that make \(f_1\) non zero. \(x\) is the last variable to be summed, so we consider \((g,y)\), however, \(g\) is a challenge from verifier, we cannot limit it to a specific set. but we can still use close form expression, to make \(f(g,x,y)\) to be \(f(z,x,y)\) where \(z\) is only limited in the set, and then use \(I(g,z)\) to “select” \(g\)
Let \(\mathcal{N}_x\) be the set of \(\{z,y\}\in \{0,1\}^{2l}\) such that \(f_1(z,x,y)\) is non-zero.
\(h_g(x) = \sum_{(z,y) \in \mathcal{N}_x} I(g,z) \cdot f_1(z,x,y) \cdot f_3(y),\)
where \(I(g,z) = \prod\limits_{i=1}^{l} \left((1-g_i)(1-z_i) + g_i z_i\right).\)
Concrete example:
Prover received the challenge \(g\) from the verifier let’s say \(g=0101\)
\(\begin{bmatrix}\mathbf{G}[0]=1 \\ i=1 & b=0& b=1\\& \mathbf{G}[0,0]=(1-g_1) & \mathbf{G}[0,1]=g_1 \\i=2 & b=00& b= 01 & b=10 & b=11\\& \mathbf{G}[0,0,0]=(1-g_1)(1-g_2) & \mathbf{G}[0,1,0]=g_1(1-g_2) \\ & \mathbf{G}[0,0,1]=(1-g_1)g_2& \mathbf{G}[0,1,1]=g_1g_2 \end{bmatrix}\)
About the benefits of GKR
When people talking about GKR can avoid the commitments to the intermediate values. How exactly this is achieved?
Because the prover only commits to the inputs of the circuit. But there is some cost as well. In the layers inside the circuit, for example, if a layer has \(2^l\) inputs, prover doesn’t need to commit to these values, but prover needs to send a polynomial for each variable as for the sumcheck protocol, that is \(l\) polynomial, with degree let’s see \(d\), then totally \((d+1)l\) coefficients needs to be sent.