[Libra] is a protocol integrating GKR sumcheck protocol for IOP and modified multilinear KZG (zkVPD in the paper).

Chap3: GKR Protocol with Linear Prover Time

The core of the chapter is to develop a linear time $O(2^\ell)$ prover for the sumcheck protocol used in GKR protocol.

Recall in the standard sumcheck protocol of the polynomial $g\in\mathbb{F}_2[X]$ requires the prover to compute

for the only multilinear extension $f\in\mathbb{F}_q[X]$ in the $i$ -th round, which takes a time of $O(2^\ell dT_f)$ . $d$ is for sending a function $s_i(X_i)$ which has degree less than $\deg f=d$ requires to set at most $d$ evaluations of $X_i$ on different points. Then the prover sends the $d$ values to the verifier.

GKR protocol

The goal of GKR protocol is to prove for public $C:\mathbb{F}^n\mapsto\mathbb{F}^k$ and $x$ , the prover knows the output $C(x)$ . The GKR protocol acts like an IOP in SNARK systems.

Assume the arithmetic circuit $C$ is of a layered structure, with depth $d$ and $S_i$ gates on the $i$ -th layer, $s_i=\log S_i$ and $S_0=k$ , $S_d=n$ . The circuit graph has the output gate on the ontly gate of the $0$ -th layer. The functions $\mathsf{add}_i,\mathsf{mul}_i:\{0,1\}^{2s_i+s_{i-1}}\mapsto\{0,1\}$ are encodings of the wiring in between each layer, e.g. if the sum of the output of $a$ -th gate and $b$ -th gate on the $i$ -th layer is the $c$ -th gate on the $(i-1)$ -th layer, then $\mathsf{add}_i(a,b,c)=1$ . Thus we define the output function $V_i:\{0,1\}^{s_i}\mapsto\mathbb{F}$ that takes $b$ as binary string, and output the value. We have

for every $z\in\{0,1\}^{s_{i}}$ iff the circuit value is legal. Below we assume that all functions are linearized to $\mathbb{F}$ .

The verifying goal is $V_0(z)=…$ for all $z\in\{0,1\}^{k}$ . Thus the verifier randomly pick $g$ and after that runs a sumcheck protocol to verify

In the last round of sumcheck protocol, the verifier gets $f_0(u_1,v_1)$ from the prover where $u,v\in\mathbb{F}$ are challenges from the verifier. To verify the $f_0(u,v)$ , the verifier needs to know $V_1(u_1)$ and $V_1(v_1)$ , so the prover sends $V_1(u_1)$ and $V_1(v_1)$ and tries to convince the verifier these are correct. The verifier first checks if $f_0(u_1,v_1)=\left(\mathsf{add}_0(g,x,y)(V_1(x)+V_1(y))+\mathsf{mul}_0(g,x,y)V_1(x)V_1(y)\right)$ . Then the verifier checks that the values are correctly calculated. If we run two sumchecks, the proof size and time will be exponential in $d$ .

So we use interpolation to combine two claims; in the original GKR protocol, the interpolation is on the domain, i.e. let $\gamma:\mathbb{F}\mapsto\mathbb{F}^{s_0}$ be a line where $\gamma(0)=u_1,\gamma(1)=v_1$ and $h(x)=V_1(\gamma(x))$ ; then prove $h(r)=V_1(\gamma(r))$ for a random point on the line.

The Libra uses combination in the range (as [1] has proposed) and considers a random combination $\alpha_1V_1(u_1)+\beta_1V_1(v_1)$ and the next sumcheck is run to verify

The procedure goes on and on for $d-1$ rounds. In the final round, the verifier gets $V_d(u_d)$ and $V_d(v_d)$ . Only then does the verifier access the oracle $\mathsf{Oracle}_{V_d}$ to see if the two values are correct.

$O(2^\ell)$ provers for the sumcheck protocol

In the last section we directly used the sumcheck protocol on a function that is a sum of multiplication of multilinear functions. Here we use $\ell$ to denote the numbers of variables of the polynomial $V$ ’s. If we use the original sumcheck protocol, the prover time will be $O(2^{2\ell})$ for the $\mathsf{add}$ polynomial has $2\ell$ variables.

If we consider that the result polynomial is sparse(in domain, i.e. on many points it evaluates to zero), the sumcheck prover will be much faster rather then $O(2^{2\ell})$ . The paper mentioned a $O(\ell 2^\ell)$ approach and a $O(2^\ell)$ approach. We can verify that the function

is indeed a sparse function for there are at most $2^{s_i}$ tuples $(z,x,y)$ that makes $\mathsf{add}_i$ and $\mathsf{mul}_i$ evaluate to $1$ . So in this section we assume that $f$ is non-zero only on at most $2^\ell$ points in $\{0,1\}^{3\ell}$ .

Consider the protocol is run on a multilinear polynomial $f$ . The former approach uses a list to store values; at the $i$ -th round it stores $f(r_1,\dots,r_{i-1},b_{i},\dots,b_n)$ for all $b_i,\dots,b_n$ with $r_1,\dots,r_{i-1}$ are picked by the verifier. The idea utilizes the property that

This method uses time $O(2^{2\ell}T_f+2^{2\ell-1}+2^{2\ell-2}+\dots+2^1+1)$ which is still quadratic. Since $f$ is sparse, the list takes down only $O(2^\ell)$ of all the values; but the halving does not hold, thus the overall time is $O(2^{2\ell}T_f+\ell2^{\ell-1}+2^\ell)$ . Here comes the core of this chapter.

Here comes the main algorithm. We want to sumcheck the function $f(x,y)=f_1(g,x,y)f_2(x)f_3(y)$ where there are at most $O(2^\ell)$ non-zero positions and $f_2,f_3:\mathbb{F}^\ell\mapsto\mathbb{F}$ , $f_1:\mathbb{F}^{3\ell}\mapsto\mathbb{F}$ , all multilinear. The idea is

and we run two sumcheck protocols shown in $\mathsf{SumCheckProduct}$ below.

These two algorithms are the same as the former described ones, with time $O(2^\ell)$ . But to run them we need bookkeeping tables for $f_1(g,x,y)f_2(x)f_3(y)$ .

where

To sum all up,

Remarks.

• This algorithm 3 requires $f(u)g(u)$ in the last round of interaction. So after step 2 in algorithm 6, the verifier needs to varify the value of $\sum_y f_1(g,u,y)f_3(y)f_2(u)$ .

• The procedure $\mathsf{Precompute}(g)$ is for constructing a bookkeeping table for the function $I_g(z):=\prod_{i=1}^\ell [(1-g_i)(1-z_i)+g_iz_i]$ which evaluates to $1$ if and only if $g=z$ . So $h_g(x)=\sum_{y,z} I_g(z)f_1(z,x,y)f_3(y)$ and by the sparse condition, the sum has $O(2^\ell)$ terms.

• Similarly, $f_1(g,u,y)=\sum_{z,x}I_g(z)I_u(x)f_1(z,x,y)$ and the sum has also $O(2^\ell)$ terms. This is shown in algorithm 5.

• All the algorithms run in $O(2^\ell)$ time.

Zero-Knowledge

zkVPD is the analogy of commitment schemes with zk properties.

References

[1] Chiesa, A., Forbes, M.A., Spooner, N.: A Zero Knowledge Sumcheck and its Applications. CoRR abs/1704.02086 (2017), http://arxiv.org/abs/1704.02086