Zero-Knowledge Proofs from Information-Theoretic Proof Systems - Part II

The pioneering work of Arora et al. on classical PCPs presented a relatively simple PCP for NP based on the Hadamard code. Viewed as a classical PCP, this so-called “Hadamard PCP” is very inefficient, having exponential proof size. However, when applied to short statements, it was still efficient enough to serve as the simpler of two main building blocks in the proof of the PCP Theorem. The construction and analysis were somewhat complicated by the need to rely on linearity testing, a nontrivial test of proximity to the Hadamard code. In the LPCP model described above, where even a malicious prover is bound to a linear function of the verifier’s queries, this extra complication can be avoided. To present the Hadamard-based LPCP, it is convenient to write the NP-relation $R(x,w)$, restricted to a fixed statement length, as an arithmetic circuit over a finite field $\mathbb{F}$, whose gates perform field additions and multiplications. Concretely, the prover wants to convince the verifier that there is a witness $w\in\mathbb{F}^m$ such that $C(x,w)=0$, where $C$ is a publicly known arithmetic circuit and $x\in\mathbb{F}^n$ is the public statement.

The first step is to convert $C$ and $x$ to a system of $s$ quadratic equations of the form $Q_i(Y)=0$, where each $Q_i$ is a multivariate polynomial of degree (at most) 2 in $s$ variables $Y_1,\ldots,Y_s$. This should be done so that there is $w\in\mathbb{F}^m$ such that $C(x,w)=0$ if and only if there is $y\in\mathbb{F}^s$ such that $Q_i(y)=0$ for all $i$. The natural way of doing it is by assigning a variable $Y_j$ to each gate of $C$, where $Y_1,\ldots,Y_n$ correspond to the input gates and $Y_s$ to the output gate. We can now express the question “does there exist $w$ such that $C(x,w)=0$?” as the existence of $y\in\mathbb{F}^s$ that satisfies $Q_i(Y)=0$ for the following polynomials:

• for each input gate $i= 1,\ldots,n$, let $Q_i = Y_i-x_i$ (where $x_i$ is a fixed field element taken from the public statement $x$)
• for each multiplication gate of the form “gate $i$ equals gate $j$ times gate $k$,” let $Q_i = Y_i-Y_jY_k$
• for each addition gate of the form “gate $i$ equals gate $j$ plus gate $k$,” let $Q_i = Y_i-(Y_j+Y_k)$
• for the output gate, let $Q_s = Y_s$

It is not hard to see that $Q_i(y)=0$ for all $1\le i\le s$ if and only if $y$ contains the values of all $s$ gates of $C$ on some input $(x,w)$ such that $C(x,w)=0$. (If $C$ is an arithmetic extension of a Boolean circuit, one can add the additional polynomials $Q’_i=Y_i(1-Y_i)$ for $n+1\le i\le n+m$ to ensure that all $w$ values are from $\{0,1\}$.)

The Hadamard LPCP for proving the satisfiability of $Q_i(Y)$ now proceeds as follows. The LPCP prover, on input $(x,w)$, first computes the values $y\in\mathbb{F}^s$ of all $s$ gates of $C$ on input $(x,w)$. It then computes the tensor product $\hat y=(y \otimes y)$, where $\hat y:[s]\times[s]\to \mathbb{F}$ is defined by $\hat y_{j,k}=y_jy_k$. The proof can now be defined as $\pi=(y, \hat y)$, where $\hat y$ is parsed as a vector in $\mathbb{F}^{s^2}$. Note that, assuming $\pi$ is well-formed, every degree-2 polynomial in $y$ can be obtained by the verifier by making a single linear query to $\pi$.

The verifier’s queries achieve two goals: (1) check consistency of the two parts of $\pi$ with the tensoring relation; (2) check satisfiability of all $Q_i$ relations assuming (1). Goal (1) is realized by comparing two different ways of computing the square of a random linear combination $\Sigma_{j=1}^s r_jy_j$ of the entries of $y$: first directly, and second by taking a suitable linear combination (with coefficients of the form $r_jr_k$) of $\hat y$. Using tensor notation, the verifier makes two linear queries: (1) $\langle \pi, q_1\rangle =\langle y,r\rangle$, for a uniformly random $r\in\mathbb{F}^s$, and (2) $\langle \pi, q_2\rangle=\langle \hat y, r\otimes r\rangle$. The verifier checks that the two inner products, $a_1$ and $a_2$ respectively, satisfy $a_2=a_1^2$. It follows from the Schwartz-Zippel Lemma that if $\hat y\neq y\otimes y$ then the latter check fails except with at most $2/|\mathbb{F}|$ probability. Finally, the verifier makes a third query that checks all equations $Q_i(y)=0$ simultaneously via a random linear combination: (3) $\sum_{i=1}^s r_i\cdot Q_i(y)=0$. Note that (3) can be written as
\begin{equation}
\langle \pi, q_3\rangle=\sum_{i=1}^n r_ix_i
\end{equation}
for a linear query $q_3\in\mathbb{F}^{s+s^2}$ defined by the $r_i$’s. Assuming that indeed $\hat y=y\otimes y$, if there is $i$ such that $Q_i(y)\neq 0$ then this check fails except with $1/|\mathbb{F}|$ probability. Overall, we have an LPCP over $\mathbb{F}$ with 3 queries, proof size $|\pi|=O(s^2)$ (where $s$ is the size of the verification circuit), and soundness error $O(1/|\mathbb{F}|)$. It is easy to convert this LPCP into a zk-LPCP, namely an LPCP in which the view of an honest verifier can be simulated given $x$. This can be achieved by augmenting $R$ so that $w$ has an additional dummy entry $w_0$. The prover picks $w_0$ at random, which makes $a_1=\langle \pi,q_1\rangle$ random and all 3 answers jointly simulatable.

Fast verification and reusable soundness. Before discussing cryptographic compilers and more efficient LPCPs, it is instructive to highlight two extra features of the simple Hadamard LPCP that will be useful in the following. While these features are simpler to discuss in the cleaner context of information-theoretic proof systems, they will be inherited by the SNARGs obtained from them via cryptographic compilers.

The first feature is fast verification given input-independent preprocessing. Whereas the cost of generating the queries $q_i$ grows with the size of the verification circuit $C$, the verifier can generate the queries before the input $x$ is known and only keep $r_1,\ldots,r_n$ for later use. Once $x$ is known, the verifier can compute $\alpha=\sum_{i=1}^n r_i x_i$, using only $O(n)$ arithmetic operations. Finally, once the LPCP answers $a_1,a_2,a_3$ are available, the verifier can decide whether to accept by checking that $a_2=a_1^2$ and $a_3=\alpha$, which only takes $O(1)$ field operations. This fast verification feature is particularly useful when the same queries are reused for proving multiple statements. We discuss this setting next.

A second useful feature of the Hadamard LPCP is a strong form of soundness that holds even when the same queries are reused for verifying multiple proofs: for any $x$ and proof $\pi^*$, the prover can predict based on $x,\pi^*$ alone whether the verifier will accept, except with $O(1/|\mathbb{F}|)$ error probability (over the verifier’s unknown random queries). This means that when $\mathbb{F}$ is sufficiently big (say, $|\mathbb{F}|\ge 2^{80}$), learning whether the verifier accepted $\pi^*$ reveals only a negligible amount of information about the queries $q_j$. The latter strong soundness property is useful for making the SRS in LPCP-based SNARGs reusable even when the prover can learn whether the verifier accepted each instance. This is contrasted with classical (zk-)PCPs, which are inherently susceptible to a “selective failure” attack in which a malicious prover can gradually learn the secret set of queries when it is reused for multiple proofs. This can be done by slightly perturbing honestly generated proofs and learning whether the verifier accepted each perturbed proof instance.

Cryptographic compilers for LPCP: First generation. Before discussing more efficient alternatives to the Hadamard LPCP, we turn to discuss suitable cryptographic compilers. Unlike cryptographic compilers for classical PCPs and IOPs, which only rely on “symmetric” (private-key) cryptography, here the compilers accommodate the richer type of queries by employing homomorphic cryptographic computations that require “asymmetric” (public-key) cryptography. At a high level, by extending PCP to LPCP, we obtain better efficiency and simplicity for the information-theoretic proof system, at the cost of slower and more structured cryptography.

The first generation of such compilers relied on the existence of a linearly homomorphic encryption scheme (sometimes referred to as additively homomorphic encryption). Such an encryption scheme over a field (or ring) enables efficient computation of linear functions with publicly known coefficients on encrypted field elements without knowing the secret decryption key. Instances of linearly homomorphic encryption can be based on a variety of standard cryptographic assumptions, including ones related to the intractability of discrete logarithm, factoring, or lattice problems. The compiler uses such an encryption scheme to implement a special kind of interactive commitment scheme, which allows the prover to succinctly commit to a vector $\pi$ in a way that allows the prover to subsequently open inner products of the form $\langle \pi,q\rangle$ with a small amount of prover-to-verifier communication. This “commitment with linear opening” primitive can be seen a simple instance of a more general notion of functional commitment.

The enhanced commitment primitive gives rise to a natural cryptographic compiler in which the prover commits to the LPCP proof $\pi$ and the verifier challenges the prover to open the the inner products $\langle \pi,q_i\rangle$ corresponding to the linear queries $q_i$. While this compiler can be based on a variety of standard cryptographic assumptions, it has several disadvantages. First, it only gives rise to interactive protocols in which the verifier has secret coins, and thus cannot be made non-interactive via the Fiat-Shamir heuristic. Second, succinctness is only in one direction: small prover-to-verifier communication, but high communication, comparable to the size of $\pi$, from the verifier to the prover. (The latter can be partially mitigated via communication balancing and recursion.) Finally, an additional price one pays for only relying on standard cryptographic assumptions is that a malicious prover can potentially commit to a nonlinear function $\pi^*$ of the queries. This requires an additional information-theoretic compiler that uses linearity testing to protect against such a stronger malicious prover, which takes an additional toll on efficiency. Despite these limitations, refinements of the above approach were efficient enough to serve as the basis for Pepper and Ginger, two of the first implementations of proof systems with fast verification. See this article by Walfish and Blumberg for a survey of this early line of work.

Cryptographic compilers for LPCP: Second generation. The next generation of cryptographic compilers eliminate most of the disadvantages of the first generation at the cost of an expensive (but reusable) trusted setup, stronger and “not efficiently falsifiable” cryptographic assumptions, and (in the case of public verification) stronger forms of public-key cryptography. These compilers can yield zk-SNARKs with very short proofs (roughly 1000 bits, or even less in some settings). They were first implicitly used in the pioneering work of Groth, with subsequent improvements by Lipmaa. An explicit treatment of such compilers was first given in a joint work with Bitansky, Chiesa, Ostrovsky, and Paneth, and (in a more restricted form) in the work of Gennaro, Gentry, Parno, and Raykova that will be further discussed in the context of LPCP constructions.

Let us start by considering the following natural attempt for compiling an LPCP into a designated verifier SNARG with a reusable structured reference string (SRS). The verifier generates LPCP queries $q_1,\ldots,q_d$ (e.g., $d=3$ in the case of the Hadamard LPCP), and lets the SRS $\sigma$ include a linearly homomorphic encryption of (each entry of) the verifier’s queries, denoted by $\sigma = (E(q_1),\ldots,E(q_d))$. The verifier keeps the secret key $k_V$ that can be used for decryption. Now, given an input $(x,w)$ and $\sigma$, the prover computes an LPCP proof vector $\pi$, and uses the linear homomorphism of $E$ to compute a short SNARG proof $\hat\pi$ consisting of the $d$ ciphertexts $\hat\pi=(E(\langle \pi,q_1\rangle),\ldots,E(\langle \pi,q_d\rangle))$ that it sends as a SNARG proof to the verifier. The verifier uses the secret key $k_V$ to decrypt the LPCP answers $a_1=\langle \pi,q_1\rangle,\ldots,a_d=\langle \pi,q_d\rangle$, and applies the LPCP decision predicate to decide whether to accept or reject.

The above attempt to implement LPCP under the hood of homomorphic encryption clearly satisfies the completeness requirement. Moreover, it is tempting to believe that since the encryption hides the queries, the proof $\pi$ must be independent of the queries and thus soundness holds as well. However, this simplistic soundness argument is flawed for two reasons.

First, while a standard linearly homomorphic encryption scheme $E$ supports computing linear functions on encrypted inputs, it provides no guarantee that only linear functions can be computed. In fact, linearly homomorphic encryption can be fully homomorphic, in which case soundness completely breaks down. The solution to this problem is essentially to “assume it away” by relying on an encryption scheme $E$ that is conjectured to support only linear computations on encrypted inputs. (Alternatively, this can be extended to affine computations that include a constant term.) This strong notion of “linear-only encryption” will be discussed in more detail below.

A second problem is that there is nothing in the above solution that prevents a malicious prover from using a different proof vector $\pi^*_i$ for each encrypted query $E(q_i)$. This is beyond the capability of a malicious prover in the LPCP model and may thus violate soundness. A solution to this problem is to have the verifier add to the LPCP an additional query which is a random linear combination of of the original queries, namely $q_{d+1}=\rho_1q_1+\ldots+\rho_d q_d$, and check that the answer to this query satisfies $a_{d+1}=\rho_1a_1+\ldots+\rho_da_d$. This can be viewed as a simple information-theoretic compiler from LPCP to a 1-round linear interactive proof (LIP), a stronger information-theoretic proof system that can be viewed as restricting a standard interactive proof by allowing provers (both honest and malicious) to only compute linear functions of the verifier’s messages.

To sum up: the modified compiler proceeds in two steps. First, an information-theoretic compiler is applied to convert the LPCP into a LIP. If the LPCP has proof size $m$ and $d$ queries, the LIP resulting from the simple compiler described above has verifier message consisting of $(d+1)\cdot m$ field elements and prover message consisting of $d+1$ field elements. Then, linear-only encryption is used to compile the LIP into a designated-verifier SNARG with SRS that consists of $(d+1)\cdot m$ ciphertexts and proof that consists of $d+1$ ciphertexts. This transformation respects all of the additional features of LPCPs we discussed in the context of the Hadamard LPCP: zero knowledge, fast verification, and reusable soundness. The latter means that the SRS of the resulting SNARG can be safely reused for multiple proofs. Finally, when the LPCP is also a “proof of knowledge” (which is the case for all natural constructions), and when the linear-only encryption is “extractable” (a plausible assumption for concrete instantiations), the resulting (zk)-SNARG is also a proof of knowledge, namely it is a (zk)-SNARK.

There is still one remaining issue: The above approach seems inherently restricted to the {\em designated verifier} setting, since only the verifier is able to decrypt the encrypted LIP answers. While this is good enough for some applications, many current applications of SNARGs require public verification. The solution, first (implicitly) used in the work of Groth, is to rely once again on a special property of the LPCP which is respected by the transformation to LIP. Suppose that the LIP verifier’s decision predicate is quadratic in the following sense: to decide whether to accept, the verifier tests equalities of the form $p_x({\bf u}, {\bf a})=0$, where $p_x$ is a degree-2 polynomial determined by the input statement $x$, the vector ${\bf u}$ contains state information determined by the LIP query, and the vector ${\bf a}$ contains the LIP answers. Indeed, this is the case for the Hadamard-based LIP. Then, public verification can be achieved by using an encryption scheme that allows such quadratic tests to be performed on an encrypted input without knowing the decryption key. Fortunately, this kind of functionality is supported by pairing-based cryptography. If the SRS $\sigma$ includes a “pairing-friendly encryption” of the LIP query along with the state information ${\bf u}$, which can be implemented using bilinear groups, the prover on input $(x,w)$ can compute an encryption of the LIP answers $\bf a$, and then {\em everyone} can check that the encrypted $\bf u,a$ satisfy the quadratic relation defined by $x$.

On “linear-only” type assumptions. Recall that a linear-only encryption is an encryption scheme that only enables computing linear functions on encrypted inputs. This requirement is closely related to a more general notion of targeted malleability. There are several variations of linear-only encryption that are tailored to the type of verification (public vs. designated) and the security requirements (whether the input is adaptively chosen and whether the “proof of knowledge” property is required). Moreover, in some cases it is useful to relax “linear-only encryption,” which guarantees indistinguishability of any pair of messages, to “linear-only one-way encoding,” which only requires security for certain distributions of messages, and may impose additional security requirements. While linear-only security is a very strong assumption that requires care in formalizing, it seems reasonable to conjecture that most standard public-key encryption schemes satisfy it. This includes variants of the encryption schemes of Goldwasser and Micali, ElGamal, Paillier, and Regev. The latter can be used as a basis for concretely efficient and plausibly post-quantum lattice-based designated-verifier SNARGs. It is an interesting open question to construct practical publicly verifiable SNARGs with post-quantum security and a similar level of succinctness, under any assumptions. The closest contenders are IOP-based SNARGs, whose concrete proof length is significantly bigger.

Finally, the type of linear-only assumption required for aforementioned publicly verifiable SNARGs is even more involved; however, when instantiated with pairing-friendly groups, it can be proved to hold unconditionally in suitable generic models, which provides further heuristic evidence for security.

I would like to conclude this discussion by arguing that even if the current formulations of the linear-only assumptions turn out not to hold for their proposed instantiations, there is still a wide safety margin. Indeed, to violate the soundness of an LPCP-based SNARG one would need to maul ciphertexts in a very specialized way that corresponds to the verification predicate of the LPCP. This takes much more than merely refuting current formulations of linear-only security, and would likely imply unexpected structural properties of existing encryption schemes that have other major consequences. Studying the security of different flavors of linear-only assumptions as well as their relations with other forms of targeted malleability and with extractability assumptions is an interesting direction for further research.

More efficient LPCPs. Recall that in the simple Hadamard LPCP, the proof length $m$ grows quadratically with the size of circuit verifying $R(x,w)$. This implies a similar quadratic overhead for the SRS size and prover complexity of the corresponding SNARGs. The quadratic overhead was eliminated in the influential work of Gennaro, Gentry, Parno, and Raykova (GGPR). Using an abstract computation model called Quadratic Arithmetic Program, they obtained an LPCP for NP in which the proof length is linear in the verification circuit size and the prover’s running time in this LPCP is quasilinear in the circuit size, and moreover it has the same number of queries, verification degree, and other useful features of the Hadamard LPCP discussed above. At a high level, the improvement stems from replacing the tensoring in the Hadamard LPCP by polynomial multiplication. See tutorials by Tromer and Buterin for simplified explanations. The GGPR construction was followed by many refinements and implementations, including Zaatar, Pinocchio, Geppetto, and libsnark, and served as a basis for the Zcash cryptocurrency. A zk-SNARK based on an optimized variant of GGPR, due to Groth, improves the proof size to only 3 group elements ($\approx 1000$ bits in the best concrete instantiations). Despite evidence for optimality in restricted settings, it is open whether one can get a better level of succinctness with a reasonable running time.

A route for better succinctness was given by Bitansky et al., who presented an information-theoretic compiler that converts any classical PCP with $d$ queries and $2^{-\Omega(d)}$ soundness error into a single-query LPCP/LIP with similar soundness error over a field of size $2^{O(d)}$. Combined with known constructions of classical PCPs and candidates for linear-only encryption schemes, this gives rise to designated-verifier SNARGs in which the proof consists of a single ciphertext, or two elements in a pairing-free group ($\approx 500$ bits in concrete instantiations) if one settles for inverse-polynomial soundness. However, this approach leaves much to be desired. Other than being only applicable in the designated verifier setting (due to the high verification degree), it does not offer fully reusable soundness and is currently impractical since it relies on classical PCPs with low query complexity. Partial progress on the practical efficiency front was obtained in this recent work by relying on the Hadamard-based LPCP instead of classical PCPs.

Bypassing the LPCP-based approach, interactive arguments and SNARGs with optimal succinctness ($d\ge 1$ bits of prover-to-verifier communication with $\approx 2^{-d}$ soundness error) can be based on strong cryptographic primitives such as obfuscation or even witness encryption. In fact, succinct proof systems may be a promising route towards the construction of witness encryption schemes. However, current candidate constructions of these high-end primitives are not yet efficient enough for practical purposes. Future developments in the area of cryptographic obfuscation may change this state of affairs.

On the prover computation front, it is open whether there is an LPCP with constant (or even sublinear) query complexity in which the prover’s computation is linear (rather than quasilinear) in the verification circuit size. For the zero-knowledge variant of LPCP, this question is meaningful even without any restriction on the number of queries. It turns out that existing constant-query LPCPs such as the Hadamard-based LPCP described above can be converted into a zk-LPCP (implying a similar zk-LIP) that answers the latter question affirmatively in the arithmetic setting. Concretely, if $R(x,w)$ is computed by an arithmetic circuit over $\mathbb{F}$ of size $s$, the zk-LPCP prover can be implemented by an arithmetic circuit of size $O(s)$, where the number of queries is $O(s)$ and the soundness error is $O(1/|\mathbb{F}|)$. This in turn implies (non-succinct) NIZK for arithmetic circuits with constant computational overhead using a correlated randomness setup, where the latter can be efficiently realized under arithmetic variants of the Learning Parity with Noise assumption. This approach can have attractive concrete efficiency features over fast networks or for small verification circuits. It was recently optimized to yield practical zero-knowledge proof systems with fast and memory-efficient provers.

Up to this point we discussed two orthogonal relaxations of the classical PCP model: adding interaction and using linear queries instead of point queries. The linear IOP (LIOP) model combines these two relaxations in a natural way. As in the IOP model, the prover generates a sequence of proof vectors $\pi_i\in\mathbb{F}^{m_i}$ in multiple rounds, where each $\pi_i$ is a response to a random challenge $r_i$. In the end of this interaction, the verifier can make linear queries to each $\pi_i$, as in the LPCP model. (The LIOP model is closely related to an earlier Interactive Linear Commitment model; see discussion below.)

The GKR protocol. The “doubly efficient” interactive proof protocol of Goldwasser, Kalai, and Rothblum (GKR), which builds on the classical sum-check protocol of Lund, Fortnow, Karloff and Nisan, can be cast as an LIOP for NP with the following features. If $R(x,w)$ is computed by a layered arithmetic circuit of size $s$ and depth $d$ over $\mathbb{F}$ with $m$ inputs, then there are $\approx d$ rounds in which the proofs $\pi_i$ are vectors over $\mathbb{F}$ of size $\approx \log s$ each, and a single round in which the proof vector of size $\approx m$. (We use $\approx$ to hide multiplicative factors that are at most polylogarithmic in $s$.) The verifier makes a constant number of linear queries to each proof and applies a decision predicate of degree 2. The soundness error is $\approx d/|\mathbb{F}|$. Furthermore, the verifier’s running time can be made $\approx d+m$ if the circuit has a succinct description of an appropriate kind. Concretely, the circuit should be log-space uniform in the sense that relevant local information about a gate can be computed in logarithmic space given the gate label. The latter uniformity feature was crucial in the original context of the GKR protocol, namely fast verification of shallow polynomial-size deterministic circuits, with no witness $w$. However, in the context of proof systems for NP (with or without zero knowledge), an LIOP as above is meaningful even for general verification circuits that do not have a succinct description. (Using statement-independent preprocessing, one can still achieve fast online verification even in the non-uniform case.) See this blog post by Thaler for an exposition of the sum-check protocol and a simplified variant of the GKR protocol based on matrix powering. A more sophisticated related protocol due to Reingold, Rothblum and Rothblum (RRR), which applies to space-bounded computations, can also be cast as a (constant-round) LIOP for NP. See this high-level overview by Goldreich.

The GKR protocol can be optimized to have good concrete efficiency, and as such had a big impact not only on theory-oriented research but also on applied research in the area of verifiable computation. The first step in this direction was taken by Cormode, Mitzenmacher, and Thaler, with several subsequent refinements and improvements: see here, here, and here. In particular, for layered arithmetic circuits of depth $d\ll s$ and witness length $m\ll s$ over large fields, Libra (building on earlier zero-knowledge sum-check techniques) obtained a zero-knowledge variant and additionally obtained constant computational overhead on the prover side in the arithmetic setting.

This can be compared to the simpler constant-overhead zk-LPCP for NP discussed above, which applies to arbitrary verification circuits (of arbitrary structure, depth, and witness length) but offers no form of succinctness.

In the context of efficiently verifying deterministic low-depth computations, variants of the GKR protocol can be used “out of the box” as interactive proofs, without a cryptographic compiler. This was proposed as a practical approach to verifiable programmable hardware. Alternatively, one can use the Fiat-Shamir heuristic for making such protocols non-interactive.

In the context of zero-knowledge proofs for NP, the GKR paper showed how to leverage efficient verification towards “witness-succinct” zero-knowledge proofs for relations $R(x,w)$ with low-depth circuits, namely proofs in which the communication is comparable to the witness length rather than the circuit size. Their transformation from an interactive proof with fast verification to a zero-knowledge proof with low communication relies on a classical cryptographic compiler that makes a non-black-box use of a one-way function. It was only much later, sparked by the growing practical interest in succinct proof systems, that the GKR protocol was used to obtain proof systems that break the witness size barrier and have competitive concrete efficiency features for NP-relations.

Cryptographic compilers and Polynomial IOP. Can we compile an LIOP for NP into a proof system whose communication complexity is comparable to the query complexity of the LIOP? Before answering this question, let us discuss the motivation. For now, consider the GKR-based LIOP. Assume we are in a “GKR-friendly” scenario where $R(x,w)$ is implemented by a layered arithmetic circuit over a large field $\mathbb{F}$, where $d,m\ll s$. Compared to both IOP-based and LPCP-based succinct proof systems, we can hope to get better prover computation (linear vs.\ quasilinear). Compared to IOP-based systems, we can hope to further gain a concrete efficiency advantage by exploiting the “algebraic” nature of the LIOP, which makes the soundness error vanish when $\mathbb{F}$ grows while the other parameters are fixed. Compared to LPCP-based systems, we can hope to further gain the advantage of being transparent (i.e., not requiring a trusted setup), or at the very least use an SRS whose size is comparable to $m$ rather than $s$. The latter is based on the fact that the total proof length in the GKR-based LIOP is comparable to $m$, as opposed to $s$ in LPCPs.

A straightforward compiler that makes a non-black-box use of symmetric cryptography is to have the prover succinctly commit to each proof string using a hash function, and emulate linear queries by using (say, IOP-based) SNARK to prove the consistency of the answers with the commitment. (This approach is non-black-box with respect to the underlying hash function since the NP-statement being argued depends on this hash function.) Note that in the GKR-based LIOP, the short proofs can be sent in the clear, and the expensive non-black-box approach only applies to the longer proof (of size $\approx m$). This approach can support two of the three potential advantages discussed above: it is transparent, and can have a linear-time prover when $d,m\ll s$. However, if we use a generic IOP, we cannot hope to gain a succinctness advantage over IOP. Moreover, the non-black-box use of the hash function would lead to a big concrete computational overhead unless the ratio $s/m$ is huge.

The key to better cryptographic compilers is the following additional feature of the GKR-based LIOP: Each of the proof vectors $\pi_i$ can be viewed as defining the coefficients of a polynomial in a small number of variables, where each linear query to $\pi_i$ evaluates the polynomial at a single point. More concretely, the long proof vector in the GKR-based LIOP defines a multilinear polynomial in $\log m$ variables that encodes $(x,w)$.

This can be captured by a more refined notion of LIOP in which a proof is interpreted as the coefficient vector of a polynomial of bounded degree, typically in a small (at most logarithmic) number of variables, and a query is interpreted as an evaluation point. This refinement of LIOP, referred to as polynomial IOP (PIOP), is motivated by possibility of cryptographic compilers that take advantage of the extra structure. (Another name for a closely related model is Algebraic Holographic Proof.) Cryptographic compilers for PIOP rely on efficient realizations of polynomial commitment, a functional commitment scheme that allows the prover to commit to a polynomial in a way that supports an efficient proof of evaluation on a given point.

The first systems that combined the GKR protocol with polynomial commitments were Hyrax and (zk)-vSQL. Hyrax used a transparent implementation of polynomial commitment based on discrete logarithm at the cost of proof size $\approx d+\sqrt{m}$. The vSQL system could eliminate the $\sqrt{m}$ additive term by using a variant of a widely used polynomial commitment scheme due to Kate, Zaverucha, and Goldberg that relies on a pairing-friendly group and requires a trusted setup. The subsequent Libra system combined a similar polynomial commitment with an improved zero-knowledge variant of the GKR-based PIOP. Virgo is a variant of Libra that uses an efficient transparent polynomial commitment based only on symmetric cryptography, combining an IOP based on the FRI protocol with a GKR-based LIOP with $m=O(\log s)$. A similar kind of polynomial commitment was proposed in RedShift. Finally, Bünz, Fisch, and Szepieniec presented a transparent polynomial commitment scheme with much better succinctness using groups of an unknown order. This comes at the cost of high concrete prover complexity and no post-quantum security.

Fully succinct PIOPs. Back from cryptographic compilers to information-theoretic proof systems, the GKR-based PIOP has the disadvantage of having query complexity that grows with the circuit depth. (While the circuit depth of $R$ can be generically reduced by adding intermediate computation values to the witness, this would make the GKR protocol inefficient.)

A variety of recent proof systems can be cast as being based on PIOPs that have constant or logarithmic round complexity and query complexity. This includes STARK, Sonic, Plonk, Marlin, Supersonic, and Spartan (building on Clover, a multi-prover variant of GKR). See Section 5 in the paper of Bünz et al. for a unified overview of these proof system in the language of PIOPs, along with an information-theoretic compiler transforming any “algebraic” LIOP to PIOP. While the resulting proof systems are typically less succinct than the LPCP-based ones described above (either by constant or logarithmic factors), they have weaker setup requirements. Concretely, they are either completely transparent, have a shorter SRS, or have additional desirable features such as a universal and updatable SRS.

Ideal Linear Commitment. Polynomial IOP can be viewed as a refinement of Linear IOP, which provides an additional algebraic structure that can be exploited by cryptographic compilers. A different kind of refinement was considered by Bootle, Cerulli, Ghadafi, Groth, Hajiabadi and Jakobsen under the name ideal linear commitment (ILC) model. A proof in the ILC model can be viewed as an LIOP where each proof vector $\pi_i$ is parsed as a matrix $\Pi\in\mathbb{F}^{n_i\times m_i}$, and each query to $\pi_i$ is specified by a vector $q\in\mathbb{F}^{m_i}$, returning the matrix-vector product $\Pi q$. (Alternatively, an ILC can be viewed as a standard LIOP if the underlying field is replaced by a vector space.) Bootle et al. show how to use a collision-resistant hash function to compile an ILC proof system into a public-coin argument in the plain model in which the communication complexity is roughly $\sum_i (n_i+m_i)$. Instantiated with linear-time encodable error-correcting codes and with linear-time computable hash functions, the compiler respects the asymptotic computational complexity of the underlying ILC proof. They also show a construction of constant-overhead “square-root succinct” zk-ILC for the satisfiability of arithmetic circuits. Concretely, for an NP-relation $R(x,w)$ computed by an arithmetic circuit over $\mathbb{F}$ of size $s$, the communication is $\approx \sqrt{s}$, the round complexity is $O(\log\log s)$, and both parties can be implemented a RAM program whose running time is dominated by $O(s)$ field operations, where the soundness error is negligible in $\log|\mathbb{F}|$. Combining this ILC with a linear-time instantiation of the cryptographic compiler yields (under plausible cryptographic assumptions) a square-root succinct zero-knowledge argument for arithmetic circuit satisfiability with constant computational overhead.

This is the third approach we have seen for obtaining a zero-knowledge proof system with constant computational overhead. It has better asymptotic succinctness than the simple LPCP-based approach. It is incomparable to the GKR-based approach: its succinctness is typically worse (unless the circuit is relatively deep), but it achieves constant overhead for arbitrary circuits and witness length. Unlike the other two approaches, the hidden multiplicative constants of the ILC-based system seem quite large, and it is open whether it can be optimized to have competitive concrete efficiency features. Note that all three approaches for zero knowledge with constant computational overhead can only achieve negligible soundness error for arithmetic computations over fields of super-polynomial size. In the parallel RAM model, an approach for amortizing away the (parallel) prover computational overhead, at the cost of a minor increase in the number of processors, was proposed in this recent work. However, when considering the standard metric of Boolean circuit size or (sequential) running time on a RAM machine, constant-overhead zero knowledge is still wide open, and there are no candidate constructions under any cryptographic assumption.

All proof systems considered so far assume that the verifier has full access to the input statement $x$. But there are situations in which this is not the case. For instance, the input can be partitioned between two or more parties (e.g., banks or hospitals), or secret-shared using a linear secret-sharing scheme. In these distributed settings, it is still possible to efficiently make a linear query to the input by locally applying a linear query to each part of the input. Linear queries to the input are also possible when the input is hidden using a linearly-homomorphic encryption or commitment scheme.

The above settings naturally call for a stronger variant of the LPCP and LIOP models in which linear queries apply jointly to an input $x\in \mathbb{F}^n$ and a proof $\pi\in\mathbb{F}^m$, where the verifier has no direct access to the input except via such queries. Information-theoretic proof systems of this kind were studied in a recent joint work with Boneh, Boyle, Corrigan-Gibbs, and Gilboa under the name fully linear proof systems, but are implicit in many previous works. In the zero-knowledge version, the simulator does not get access to the input $x$, capturing the requirement that the verifier learn nothing about $x$ and $w$ except for the fact that $x\in L$ (compared to only hiding $w$ in the usual definition). The limited access to the input makes fully linear proof system with low query complexity meaningful even for polynomial-time languages, and even if P $=$ NP. This is akin to proofs of proximity, except that the latter only give the weaker guarantee that the input is close to being in $L$, and is also closely related to holographic proofs in which the verifier can query a suitable encoding of the input.

Fully linear proof systems are motivated by the goal of efficient distributed zero-knowledge proofs, namely ones in which the input statement $x$ is known to the prover but is distributed between two or more verifiers. (This should not be confused with other kinds of distributed zero-knowledge proofs, such as this one.) Indeed, by having the prover secret-share each proof vector, a fully linear proof system can be compiled into a distributed zero-knowledge proof in which the communication complexity is dominated by the total length of the proofs and the answers to the linear queries. This is contrasted with previous cryptographic compilers in which the proof length did not influence communication, since proofs could be “compressed” by hashing or homomorphic encryption. Moreover, the compilers for distributed zero knowledge can be information-theoretic, and do not take advantage of the additional structure offered by polynomial IOPs or the low algebraic degree of the verifier’s decision predicate.

Given the above, a natural goal is to design fully linear PCPs and IOPs (abbreviated as FLPCPs and FLIOPs) in which the proof length and query complexity are both sublinear in the input length. This goal is well-motivated even for simple languages $L\subseteq \mathbb{F}^n$. To give two concrete examples, consider the the inner-product language $L_1$ consisting of concatenations of pairs of vectors in $\mathbb{F}^{n/2}$ whose inner product is 0, or the language of binary vectors $L_2=\{0,1\}^n$. It turns out that the concrete LPCP and LIOP discussed above can be made fully linear with the same number of queries. However, whereas the proof length of the Hadamard LPCP and the LPCP of GGPR is at least linear in $n$, the GKR protocol yields an FLIOP whose total proof and answer length is comparable to the circuit depth, or $O(\log^2n)$ for the above examples, with a similar number of rounds. Similarly, the RRR protocol implies constant-round sublinear FLIOPs for low-space computations.

For languages that are recognized by low-degree polynomials, as in the above examples, there are simpler and more efficient fully linear proof systems. For instance, there is a (non-interactive) zk-FLPCP for proving that $x$ satisfies a single degree-2 equation (as in $L_1$ above) with a proof of size $O(\sqrt{n})$ and a similar number of queries, which can be shown to be optimal. This protocol is a zero-knowledge variant of a communication complexity upper bound of Aaronson and Wigderson. For languages recognized by systems of constant-degree equations (including both of the above examples), the proof size and query complexity can be reduced to $O(\log n)$ at the cost of settling for zk-FLIOP with $O(\log n)$ rounds of interaction. These constructions start with a generalization of a GGPR-style zk-LPCP that takes advantage of repeated structures, and then improve its efficiency via balancing and recursion.

As already mentioned, fully linear proof systems are motivated by the goal of distributed zero-knowledge proofs. Such proofs were implicitly used for verifiable private data aggregation in the Prio system and also for verifiable function secret sharing. In the context of efficient interactive proofs (without zero knowledge) for distributed graph problems, fully linear IOPs were implicitly used in the work of Naor, Parter, and Yogev to improve on previous results along this line.

A distributed GMW-style compiler. I would like to conclude this section by revisiting a powerful and beautiful application of zero-knowledge proofs: enforcing honest behavior in general cryptographic protocols. A paper of Goldreich, Micali, and Wigderson established the feasibility of general secure computation protocols via the following two-step approach: (1) design a protocol that offers security against honest-but-curious parties, who send messages as prescribed by the protocol but try to obtain additional information from messages they receive; (2) apply a general compiler based on zero-knowledge proofs to enforce an honest behavior. The compiler, commonly referred to as the GMW compiler, requires parties to prove that they “stick to the protocol,” namely send out the correct messages given messages they already received. Zero knowledge is necessary here because the correctness of messages is an NP-statement involving the secret input and randomness that cannot be revealed.

A limitation of the GMW compiler is that it only applies to protocols over a public broadcast channel, since otherwise the NP-statement (which includes the messages) is not fully known to the verifiers. Distributed zero-knowledge proofs allow for GMW-style compilers that apply to protocols over secure point-to-point channels. Such channels are necessary for secure computation protocols with information-theoretic security in the honest majority setting. Alternatively, protocols in this setting can use symmetric cryptography for better concrete efficiency. It turns out that in natural protocols of this type, it suffices to prove in zero knowledge distributed statements that can be verified by degree-2 polynomials. In particular, one can apply the efficient zk-FLIOP discussed above to protect such protocols against malicious parties with sublinear additive communication cost over the best “baseline” protocols that have security against honest-but-curious parties. See here, here, and here for applications of distributed zero-knowledge proofs to efficient honest-majority secure computation.

We discussed a modular approach for constructing zero-knowledge or succinct proof systems by combining an idealized information-theoretic proof system, such as the different kinds of PCPs and IOPs discussed above, with a cryptographic compiler. Information-theoretic proof systems can be crudely divided into four categories depending on whether interaction and linear queries are allowed. Linear queries help simplify proof systems and make them more succinct, but their cryptographic compilers typically result in strong setup requirements, heavy use of “public-key” cryptography, and no post-quantum security. Allowing interaction contributes to simplicity and lower prover complexity, typically at the cost of suboptimal succinctness. We demonstrated that a large portion of the work on efficient proof systems can be cast in this modular framework.

Are PCPs necessary? Rothblum and Vadhan gave evidence in this direction, showing that computationally sound proof systems which make a “black-box” use of certain cryptographic primitives imply PCPs with related efficiency. But regardless of the extent to which such a converse direction holds, there are other potential approaches to the design of efficient proof systems that do not naturally fit into the current taxonomy. We list below some of the approaches to efficient proof systems we did not cover in this survey.

Zero knowledge from garbling. Jawurek, Kerschbaum, and Orlandi showed how to build concretely efficient zero-knowledge proofs from Yao’s garbled circuit construction. In fact, relaxed forms of garbling schemes (known as privacy-free or partial garbling, which are closely related to conditional disclosure of secrets) suffice for this purpose. While this approach has several limitations, recent advances in garbling techniques make it competitive for some use cases. More applications may be found in the future.

Discrete-log based proof systems. We did not cover many proof systems from the literature that are based on discrete-log type assumptions. This includes a wide array of well-known protocols, originating from classical ones due to Schnorr, Guillou-Quisquater, and Cramer-Damgård, via the pairing-based NIZK protocols of Groth-Ostrovsky-Sahai and Groth-Sahai, to popular recent zk-SNARKs such as Bulletproofs. See here and here for progress on a unified treatment of such protocols and here for a recent lattice-based analogue. It remains to be seen if these protocols can be naturally cast as applying a general compiler to a suitable kind of PCP.

Multi-prover proof systems. The pioneering work of Ben-Or, Goldwasser, Kilian, and Wigderson showed that information-theoretic zero-knowledge proofs are possible in a model where there are two or more potentially malicious but non-colluding provers. This work has led to a systematic study of the power of multi-prover proof systems and PCPs, which culminated in the PCP theorem and gave rise to other influential results such as the parallel repetition theorem. Multi-prover proof systems are closely related to the kinds of information-theoretic proof systems discussed in this survey. In particular, practical proof systems in this model were later cast as polynomial IOPs. A 2-prover zero-knowledge proof protocol in which one of the provers is stateless can be viewed as an interactive zk-PCP in which the proof oracle $\pi$ is succinctly represented by a circuit. This model gives rise to information-theoretic zero-knowledge proofs for NP using untrusted tamper-proof hardware (with efficient provers), or even for NEXP (with inefficient provers). An alternative multi-prover model is one both soundness and completeness hold as long as at least one prover is honest. Canetti, Riva, and Rothblum showed that this type of “refereed” proof systems enable lightweight verification of computations using collision-resistant hash functions without any kind of nontrivial PCP machinery.

Proof composition. It is sometimes useful to apply one proof system for “proving the knowledge of a proof” in another. This can be used to enhance efficiency via bootstrapping, as in Valiant’s notion of incrementally verifiable computation or its extension to proof-carrying data. It can also be used for “best-of-both-worlds” combinations of different proof systems, say one with a fast prover but only partial succinctness and one with a slower prover but better succinctness. The overhead of proof composition can be reduced via new instances of cryptographic hash functions that optimize relevant complexity measures. A different kind of proof composition makes a black-box use of succinct commitments as a common interface between different proof systems. It is likely that in the future we will see more hybrid proof systems that combine the advantages of the different approaches presented here.

To conclude, we discussed many different techniques for constructing zero-knowledge and succinct proof systems. These give rise to an enormous design space in which different instances often have incomparable features. The modular approach we survey here can help navigate this space in a systematic way, helping identify efficiency bottlenecks and opportunities for further improvement.

I would like to thank Daniel Benarroch and Yau Benor for inviting this blog post and waiting patiently for its arrival, Daniel for a lot of help along the way, Oded Goldreich for his encouragement to write a different but related survey, and Ron Rothblum for many helpful discussions and comments.