In this two-part extended blog post I will discuss a modular approach to the design of efficient zero-knowledge proof systems that aims at maximizing the separation between the “information-theoretic” and the “cryptographic” ingredients. While this approach is already practiced, it could arguably be applied more often and more systematically. The post is loosely based on recent talks I gave, including one at the 2nd ZKProof Workshop. Shorter expositions of this kind can be found in Section 2 of the ZKProof Community Reference document, Section 2 of the BBCGI19 paper and Section 5 of the BunzFS20 paper.
Motivation
The growing number of competing proposals for practical zero-knowledge and/or succinct proof systems makes it easy to get confused about how these different systems compare to each other. One reason such comparisons are difficult is the multitude of application scenarios, implementation details, efficiency desiderata, cryptographic assumptions, and trust models. To make things worse, such systems are typically offered as a “package deal” that makes it difficult to apply a mix-and-match approach for finding the best combination of the underlying ideas in the context of a given application.
This calls for a modular approach that allows for an easier navigation in the huge design space. A higher level of modularity and abstraction is useful for capturing technical ideas in a way that makes them more broadly applicable, beyond the setting in which they were originally introduced. This can help us avoid reinvention of the same ideas in related contexts.
Guide to readers. The current post will survey a specific modular approach, which covers many of the techniques that underlie modern proof systems. It does not intend to fully cover the current state of the art, which is a rapidly moving target. Instead, it mainly aims to suggest common principles and clean abstractions that can apply to a wide variety of proof systems, including ones that are not mainstream today but may become more popular in the future. This post is meant for readers with diverse backgrounds. Those who already have a good familiarity with the theory of zero-knowledge proofs may be better off skipping the next background section. Then, in this first part of the post, I will discuss the simplest kind of information-theoretic zero-knowledge proof systems, how to use cryptography to compile such systems into zero-knowledge proof protocols, and how to construct such systems from protocols for secure multiparty computation. Relaxed kinds of information-theoretic proof systems that lead to better succinctness will be discussed in the forthcoming second part of this post.
Background
To make the post relatively self-contained, I would like to give some background on the kinds of zero-knowledge proof systems we will be interested in. I will also give a high-level overview of theoretical research in this area that provides the foundations, as well as a useful toolbox, for the recent practice-oriented research.
Definition
The goal of a zero-knowledge proof is specified by an NP-relation $R(x,w)$, where $x$ is referred to as a statement (or sometimes an input) and $w$ as a witness. A zero-knowledge proof for $R$ is a protocol that specifies the rules for an interaction between a prover and a verifier, both of which run in polynomial time and can toss coins. The prover and the verifier share a statement $x$ as common input, and the prover additionally knows a witness $w$ such that $(x,w)\in R$. One can think of $w$ as a “classical proof” that the statement $x$ is in the language $L=\{ x\,:\, \exists w \, (x,w)\in R\}$. However, instead of simply sending $w$ to the verifier, the prover would like to convince the verifier that $x\in L$ without revealing information about $w$. A zero-knowledge proof protocol for $R$ should satisfy the following, loosely stated, requirements:
- Completeness: If $(x,w)\in R$, then in the end of the interaction the verifier always accepts.
- Soundness: If $x\not\in L$ (namely, there is no $w$ such that $(x,w)\in R$), then the verifier rejects except for a small probability, called the soundness error. This holds even when the prover is malicious and can deviate arbitrarily from the protocol.
- Zero knowledge: The view of a verifier interacting with the honest prover on input $(x,w)\in R$ can be efficiently simulated based on $x$ alone. By default, this is required to hold for any efficient malicious verifier. An honest-verifier zero-knowledge proof is one where this is only required to hold for the honest verifier.
This informal definition leaves some details unspecified, such as the allowable running times of a malicious prover and the quality of the simulation. It also ignores composition-related issues. See Chapter 4 of Goldreich’s textbook for a more rigorous treatment.
Variants
There are several important variations and extra features that will play a role in the following.
Proofs vs. arguments. The original notion of zero-knowledge proofs requires soundness to hold against computationally unbounded malicious provers. However, it is often useful to consider proof systems whose soundness is restricted to hold only against efficient (e.g., polynomial-time) provers. Such computationally sound proof systems are often referred to as arguments. Here I will typically ignore this distinction and use the term “proof” even in the case of computational soundness.
Proofs of knowledge. The soundness requirement is often replaced by a stronger proof of knowledge requirement, which captures the intuitive property that any prover who can convince the verifier of the truth of a statement $x$ (with better probability than the soundness error) must “know” a valid witness $w$ such that $R(x,w)$ holds. Here we will mainly focus on the simpler soundness requirement, though the concrete proof systems discussed below will in fact be proofs of knowledge.
Non-interactive proofs. A particularly appealing type of proof system is a non-interactive zero-knowledge (NIZK) proof, in which the protocol involves a single message from the prover to the verifier. This message may depend on a common reference string (CRS) that can either be uniformly random (URS) or structured (SRS). Here a long CRS can be generated together with a short verification key to speed up verification, and the zero-knowledge simulator is allowed to generate the reference string together with the simulated proof. Whereas there are simple (but unproven) heuristics for generating a URS without a trusted setup and without compromising security, there are no similar heuristics for generating an SRS. Instead, the SRS is typically generated using a large-scale secure multiparty computation protocol, a process sometimes referred to as an “MPC ceremony.”
A powerful technique for converting interactive proof systems into non-interactive ones is the Fiat-Shamir transform. This technique applies to the class of public-coin protocols, where the verifier’s role is restricted to generating and sending random messages, and essentially amounts to having the prover generate each verifier’s message by applying a hash function to the protocol’s transcript up to this message. While the security of the transformation can be proved in the random oracle model, which models the hash function as a perfectly random function, when instantiated with real hash functions the security becomes heuristic. An advantage of such non-interactive proof systems is that they are transparent in the sense that they avoid the need for a trusted setup by only requiring a URS, which can be eliminated in practice. See “state of the art” below for further discussion.
Designated-verifier proofs. The NIZK protocols discussed above have the appealing feature of being publicly verifiable, as the verifier has no secret state. An alternative setting is that of a designated-verifier NIZK, in which the CRS is a public key that corresponds to a secret verification key owned by the designated verifier, and can typically be securely generated by the verifier alone. Proofs generated using this public key can only be verified by the designated verifier. An even more liberal setting is that of NIZK with a correlated randomness setup (sometimes referred to as preprocessing NIZK). In this setting, a designated verifier and a designated prover share a pair $(k_P,k_V)$ of correlated secret keys. Proofs can be generated using $k_P$ and verified using $k_V$.
Succinct proofs. A final and very important goal in the design of proof systems is optimizing their efficiency. Here the main focus is on two efficiency measures that are typically (but not always) correlated: communication and verifier’s computation. Optimizing these measures is meaningful even for proof systems without the zero knowledge property. The baseline is the simple “classical” proof system in which the prover sends $w$ to the verifier, who checks that $R(x,w)$ indeed holds. This may be unsatisfactory in terms of both communication complexity and verifier’s running time. A succinct proof system is one that has better communication complexity. The term “succinct” is typically also associated with fast verification, requiring that the verifier’s running time be smaller than the time required for computing $R$, possibly given preprocessing that may depend on $R$ but not on the statement $x$. Here we will use this term to refer only to low communication complexity by default. The term succinct non-interactive argument, commonly abbreviated as SNARG, refers to a non-interactive, computationally sound proof system that satisfies the succinctness requirement. A zk-SNARG additionally satisfies zero knowledge, and a (zk-)SNARK additionally has the proof of knowledge property. As most succinct proof systems can be modified to realize the extra zero knowledge requirement with little extra cost, we will assume by default that all proof systems are zero knowledge even when we do not say it explicitly. However, most of this post is relevant also to succinct proof systems without zero knowledge. Finally, while we will mostly ignore here the proof of knowledge property, it is satisfied by almost all known proof systems, sometimes under stronger assumptions, and is important for many applications.
State of the art
What do we know about the existence of zero-knowledge proofs for general NP-relations? Let me briefly summarize where we stand from a crude “feasibility” standpoint. More refined efficiency issues will be discussed later. Shortly after the introduction of zero-knowledge proofs by Goldwasser, Micali, and Rackoff in the mid-1980s, the first general construction was given by Goldreich, Micali, and Wigderson (see also Chapter 4 of Goldreich’s texbook). This construction, which will be described below, can use any cryptographic commitment scheme, which in turn can be based on one-way functions. On the other hand, Ostrovsky and Wigderson showed that a weak flavor of one-way functions is also necessary for non-trivial zero-knowledge. This means that a (very mild) cryptographic assumption is necessary and sufficient for the existence of general zero-knowledge proofs.
In the non-interactive setting, all current protocols require much stronger cryptographic assumptions. Originating from the work of Blum, Feldman, and Micali that introduced NIZK proofs, there has been a large body of work on diversifying these assumptions. This is an active area of research with some exciting recent results: see here, and here, and here. At this point in time, NIZK proofs for NP can be based on most of the standard cryptographic assumptions that are known to imply public-key encryption. Notable exceptions are assumptions related to the discrete logarithm problem.
The above state of the art is good, since it gives us a high degree of confidence that general NIZK protocols do exist. But it also leaves a gap between the current “provable” constructions and ones that rely on instantiating the Fiat-Shamir transform. It is commonly believed that this heuristic is good enough for practical proof systems and hash functions that were not designed to defeat it. This holds even with hash functions that are not known to imply public-key cryptography. However, we do not have good evidence in this direction, and there are negative results that rule out a generic approach for instantiating a random oracle with a concrete hash function, even in the specific context of the Fiat-Shamir transform (when applied to arguments rather than proofs). See this and this recent works for a survey of this direction. Understanding the minimal cryptographic assumptions that suffice for NIZK is an intriguing question that will surely generate a lot of interesting future research.
For succinct proof systems, the state of provable constructions is considerably worse. Things are not too bad in the interactive setting, where collision-resistant hash functions suffice for obtaining succinct proof systems for NP. (This is considered a standard and mild cryptographic assumption, albeit stronger than one-way functions that suffice for non-succinct zero-knowledge proofs.) In the non-interactive setting, all known constructions are either cast in idealized models (such as the random oracle model or the generic group model) or alternatively are based on strong “extractability” assumptions such as knowledge-of-exponent assumptions. The latter seem hard to validate and are in some cases likely to be false. The algebraic group model is a weaker version of the generic group model that can potentially be instantiated and may serve as a cleaner substitute to concrete extractability assumptions.
Can SNARGs be based on standard cryptographic assumptions? Gentry and Wichs gave negative evidence that effectively serves as a barrier. They showed that, in some well-defined sense, “standard” assumptions and proof techniques cannot imply SNARGs with adaptive soundness, namely soundness that holds even when the statement can depend on the CRS. The goal of basing different flavors of SNARGs on standard cryptographic assumptions remains an important challenge in the theory of cryptography. Progress on this question is likely to require new techniques that have benefits beyond the goal of provable security. See here, here, here, and here for a very partial sample of results along this line.
Factoring out cryptography
This post is about separating the “cryptographic” part of a proof system from the “information-theoretic” part. Before switching to a more abstract level, let me put this in the context of practical zero-knowledge proof systems. Such systems are often divided into two parts: (1) a “front-end” compiler converting a specification of an NP-relation $R$ (e.g., using a C program) into a “zero-knowledge friendly” representation $\hat R$ (such as an arithmetic circuit or a rank-1 constraint system — R1CS); (2) a “back-end” compiler converting $\hat R$ to a zero-knowledge proof protocol for $R$. The two components are related in that the zero-knowledge friendly representation is tailored to the back-end compiler.
Here we will not consider front-end compilers. Instead, we are interested in further breaking the back-end compiler into two parts: (2a) converting $\hat R$ into a (zero-knowledge) information-theoretic proof system for $R$, and (2b) using a cryptographic compiler for converting the information-theoretic proof system into a usable zero-knowledge proof protocol for $R$. Let me explain what each part means.
Information-theoretic proof system. Such a proof system, sometimes referred to as a probabilistically checkable proof (PCP), is information-theoretic in the sense that it provides soundness and zero knowledge guarantees even when the prover and the verifier are computationally unbounded. To make this possible, the proof system can make idealized assumptions that are difficult to enforce via direct interaction. For instance, it may allow the prover to generate a long proof vector and then only grant the verifier restricted access to this vector, where the access pattern is independent of the proof. Enforcing this restricted access via direct interaction is outside the scope of an information-theoretic proof system. (The classical notion of interactive proofs does not make any idealized assumptions; however such proofs are much weaker than the information-theoretic proof systems considered in this work.) The idealized assumptions typically make information-theoretic proof systems useless as standalone objects. On the other hand, they allow us to construct them unconditionally, without relying on cryptographic assumptions. We will discuss several kinds of information-theoretic proof systems with incomparable features. The different kinds of proof systems vary in the restrictions they impose on the verifier’s access to the proof and the amount of interaction. We will also discuss information-theoretic compilers that convert one type of information-theoretic proof system into another.
Cryptographic compiler. The cryptographic compiler removes the idealized assumptions that underly the information-theoretic proof system by transforming it into a protocol that involves direct interaction between the prover and the verifier. This is done by using cryptographic primitives, such as a collision-resistant hash function, or alternatively idealized primitives that replace them, such as a random oracle or a generic bilinear group. Both types of primitives may come with some (possibly heuristic) concrete instantiation, such as a concrete hash function or pairing-friendly elliptic curve. Unlike the underlying information-theoretic proof system, the protocol obtained by the cryptographic compiler is only secure with respect to a computationally bounded prover and/or verifier. This security will typically be based on a cryptographic assumption. A possible exception is when using idealized primitives. In this case, security can be unconditional, but it is still computational in the sense that it bounds the number of queries (or “oracle calls”) made to the primitive. The cryptographic compiler may also provide extra desirable properties, such as eliminating interaction, shrinking the size of some of the messages, or even adding a zero knowledge feature to an information-theoretic proof system that doesn’t have it.
Advantages of the separation. Separating information-theoretic proof systems from cryptographic compilers can serve multiple purposes. It makes protocol design conceptually simpler by breaking it into two modular parts, where each part can be analyzed, optimized, and implemented separately. This facilitates a systematic exploration of the design space in search of the best solution for the task at hand. It enables useful mixing and matching of different instantiations of the two components. For instance, the same information-theoretic proof system can be paired with different cryptographic compilers to give useful tradeoffs between efficiency, security, and setup assumptions. This makes it easier to port technical insights and optimization ideas between different types of proof systems. Finally, information-theoretic proof systems serve as cleaner objects of study than their computationally secure counterparts. In particular, they are better targets for lower bound efforts, which can lead to new insights that often result in better upper bounds.
Example: Zero-knowledge proof for Graph 3-Coloring
Example: Zero-knowledge proof for Graph 3-Coloring
To illustrate the above modular approach, let’s revisit the first construction of a zero-knowledge proof system for NP.
The 3-coloring problem. The proof system is described for the specific 3-coloring relation $R_{\sf 3COL}$, where the statement is an undirected graph $G=(V,E)$, the witness is a mapping $c:V\to\{1,2,3\}$ specifying a coloring of each node by one of three colors, and $R$ tests whether the coloring is valid. Concretely, $(G,c)\in R_{\sf 3COL}$ if $c(u)\neq c(v)$ whenever $(u,v)\in E$. The relation $R_{\sf 3COL}$ corresponds to the NP-complete problem of deciding whether a graph $G$ is 3-colorable. This implies that a zero-knowledge proof for any NP-relation $R$ can be obtained from a zero-knowledge proof for $R_{\sf 3COL}$ by having the prover and the verifier locally apply a polynomial-time reduction to convert their inputs for $R$ into inputs for $R_{\sf 3COL}$.
The protocol. The zero-knowledge proof for $R_{\sf 3COL}$ proceeds as follows.
- The prover, on input $(G,c)$, picks a random permutation $\phi:\{1,2,3\}\to\{1,2,3\}$ defining a random shuffle of the colors, and lets $c'(v)=\phi(c(v))$ be the shuffled coloring.
- The prover and the verifier engage in $|V|$ instances of a cryptographic commitment protocol, in which the prover commits to the shuffled color $c'(v)$ of each node $v$. Such a commitment protocol is a digital analogue of a locked box: it hides the committed value from a computationally bounded verifier (even a malicious one) and it binds the prover to at most one value $c^*(v)$ that can be later opened and accepted by the verifier. (A malicious prover can choose the $|V|$ values $c^*(v)$ arbitrarily.) A 2-message commitment protocol can be based on any one-way function, and a non-interactive one on any injective one-way function.
- The verifier picks a uniformly random edge $(u,v)\in E$ and sends $(u,v)$ as a challenge to the prover.
- The prover opens the commitments to $c'(u)$ and $c'(v)$.
- The verifier accepts $G$ if the prover successfully opens the two commitments and they contain different values in $\{1,2,3\}$.
Analysis. The above protocol satisfies the completeness property, since if the coloring $c$ is valid then so is its permuted version $c’$, and so an honest prover will always successfully open two distinct colors in $c’$. It intuitively satisfies the zero knowledge requirement because the only colors not hidden by the commitments are the opened colors $(c'(u),c'(v))$, which can be simulated by choosing two distinct but otherwise random colors. Note that this holds even for a malicious verifier, who can choose $u$ and $v$ arbitrarily, assuming that the prover checks that the pair $(u,v)$ sent by the verifier is indeed a valid edge; this check is necessary, since otherwise the verifier can learn whether the two (disconnected) nodes $u$ and $v$ have the same color in $c$. The simulation is easy to formalize if commitments are implemented by a physical locked box, but is considerably more subtle when using a computationally hiding cryptographic commitment scheme.
Finally, soundness can be argued as follows. if $G$ does not admit a valid coloring, then no matter which colors $c^*$ are committed to by a malicious prover, there is at least one edge $(u,v)\in E$ that will satisfy $c^*(u)=c^*(v)$. It follows that the verifier will reject the proof with at least $1/|E|$ probability. This poor level of soundness can be amplified, while preserving zero knowledge, by running the protocol many times independently. Concretely, with $k\cdot |E|$ repetitions, the probability of the prover getting lucky in all instances drops to roughly $e^{-k}$ for $e\approx 2.7$.
An abstraction? The above protocol, while simple and elegant, leaves much to be desired in terms of efficiency. There are two sources of overhead. The first is a Cook-Levin reduction from a “useful” NP-relation $R$ (say, the satisfiability of a Boolean or arithmetic circuit) to $R_{\sf 3COL}$. The second is the overhead of amplifying soundness, which grows linearly with $|E|$. Even in terms of simplicity, while the analysis of the protocol is quite straightforward when using ideal commitments, this is not the case when using their cryptographic implementation. Should this analysis be redone from scratch for a similar protocol based on a different NP-complete problem, say graph Hamiltonicity? Abstraction can be helpful towards addressing both issues.
Zero-knowledge PCPs and their cryptographic compilers
Zero-knowledge PCPs and their cryptographic compilers
The combinatorial core of the above protocol can be abstracted by a simple kind of information-theoretic proof system that I will refer to as a zero-knowledge probabilistically checkable proof (zk-PCP). (Here I am using this term to refer to a specific, arguably the simplest, flavor; other flavors of zk-PCP will be discussed later.) In a zk-PCP for an NP-relation $R$, the prover computes a probabilistic polynomial time mapping from a statement-witness pair $(x,w)$ to a proof string $\pi\in\Sigma^m$. In the above example, $\pi$ is a string of length $m=|V|$ over $\Sigma=\{1,2,3\}$ comprised of the values $c'(v)$ for $v\in V$, where the randomness is over the permutation $\phi$ used to convert $c$ into $c’$. The verifier decides whether to accept or reject by querying a randomly chosen subset of the symbols of $\pi$. More concretely, the verifier’s algorithm is specified by a randomized mapping from an instance $x$ to a subset $Q\subset[m]$ of queried symbols, and a decision predicate $D(x,Q,\pi_Q)$ deciding whether to accept or reject based on the contents of the queried symbols. In the above example, $Q$ is uniformly distributed over sets of size 2 corresponding to edges in $E$, and $D$ accepts if the two queried symbols are distinct. We assume that one can efficiently recognize whether a set $Q$ can be generated by an honest verifier on a given input $x$.
The completeness, soundness, and zero knowledge properties of a zk-PCP are defined as expected, where the zero-knowledge simulator is required by default to perfectly sample the view $(Q,\pi_Q)$ of an honest verifier given $x$ alone. The basic version of the zk-PCP for $R_{\sf 3COL}$ has a high soundness error of $1-1/|E|$. Soundness can be amplified, while respecting zero knowledge, by concatenating independently generated proofs $\pi^{(i)}$ and querying them independently. Note that making multiple queries to the same $\pi$ would compromise zero knowledge.
The need for a cryptographic compiler. The above notion of zk-PCP is information-theoretic in the sense that both soundness and (honest-verifier) zero knowledge hold with respect to computationally unbounded parties. The reason it cannot be directly used as a zero-knowledge proof protocol, without additional cryptographic machinery, is that it is not clear how to only allow the verifier a restricted access to $\pi$, which is necessary for zero knowledge, without allowing a malicious prover to violate the independence assumption between $\pi$ and $Q$ on which soundness relies. Put differently, if $Q$ is sent to the prover first, then a malicious prover can violate soundness, and if $\pi$ is sent to the verifier in its entirety, then zero knowledge is compromised even when the verifier is honest. The role of a cryptographic compiler is to convert an arbitrary zk-PCP (possibly with some syntactic restrictions) into a zero-knowledge proof protocol.
Cryptographic compilers for zk-PCP
Cryptographic compilers for zk-PCP
The cryptographic compiler implicit in the above protocol for $R_{\sf 3COL}$ relies on a cryptographic commitment scheme and proceeds as follows. Given $(x,w)$, the prover uses the zk-PCP prover to generate a proof $\pi\in\Sigma^m$ and uses the underlying commitment scheme to independently commits to each of the $m$ symbols. The verifier uses the zk-PCP verifier to pick a subset $Q$ of the symbols, which it sends as a challenge to the prover. The prover opens the symbols $\pi_Q$ after checking that $Q$ is valid (in the sense that it can be generated by an honest verifier). The verifier uses the decision predicate $D$ of the zk-PCP to decide whether to accept.
Using standard cryptographic assumptions. While simple and natural, the analysis of the above compiler when using a standard computationally-hiding commitment scheme is more subtle than it may seem. In particular, efficient simulation requires that the distribution of $Q$ have polynomial-size support. This indeed applies to the basic version of the zk-PCP for $R_{\sf 3COL}$, but not to the one with amplified soundness. As a result, the compiler yields a (constant-round) zero-knowledge protocol with poor soundness, which can be amplified via sequential repetition. An alternative cryptographic compiler, which avoids the polynomial-size support restriction by using a statistically-hiding commitment scheme (and an even more subtle analysis), is implicit in the work on constant-round zero-knowledge proofs for NP. Both of the above compilers yield zero-knowledge proof protocols in which the communication complexity is bigger than that of communicating $\pi$; ideally, we would like to make it comparable to only communicating $\pi_Q$. As we will see, this can make a big difference.
When instantiated with statistically-binding (and computationally-hiding) commitments, the above compilers yield statistically-sound proofs rather than computationally-sound arguments. In this case, their high communication cost seems inherent, as there is a strong complexity-theoretic evidence (see here and here) that the prover-to-verifier communication in proof systems for hard NP-relations cannot be much smaller than the witness size. On the other hand, a different cryptographic compiler can use any collision resistant hash function to obtain a zero-knowledge argument whose communication complexity is close to just the size of $\pi_Q$, which for some zk-PCPs (that will be discussed in the second part of this post) can be much smaller than the witness size. The first compiler of this kind, implicit in the work of Kilian, can obtain a similar zero-knowledge argument from any PCP, namely zk-PCP without the zero knowledge requirement. However, in contrast to compilers based on zk-PCP, Kilian’s compiler uses the underlying cryptographic primitive in a non-black-box way, which makes it inefficient in practice.
Practical NIZK compiler in the random oracle model. All of the previous black-box compilers can be analyzed unconditionally if the underlying “symmetric” cryptographic primitive is abstracted as a random oracle. But one can actually go further and make these interactive public-coin protocols non-interactive via the Fiat-Shamir transform. Combining the two steps, we get concretely efficient compilers from any zk-PCP to NIZK in the random oracle model. The latter is then heuristically instantiated with a practical hash function based on, say, SHA-256 or AES. See the background part for more discussion of this methodology. Interestingly, even in the random oracle model, the NIZK does not entirely dominate the interactive protocol on which it is based, since removing interaction can come at a price. For instance, consider an interactive protocol with soundness error of $2^{-30}$, which is often reasonable in practice. In the NIZK obtained via the Fiat-Shamir transform, the prover can convince the verifier of a false statement with certainty by generating roughly $2^{30}$ random transcripts until finding one that would lead the verifier to accept. This type of attack effectively means that the non-interactive variant should rely on a zk-PCP with a considerably smaller soundness error, which increases the concrete communication and computation costs (though fortunately by a small factor).
NIZK from standard cryptographic assumptions. As mentioned in the background part, a recent line of work shows how to instantiate the random oracle in NIZK proofs obtained via the Fiat-Shamir transform under standard cryptographic assumptions. These works rely on a special type of correlation-intractable hash functions together with a special kind of $\Sigma$-protocols, namely 3-message honest-verifier (computational) zero-knowledge proof systems that satisfy some additional properties. The latter in turn implicitly rely on a special kind of zk-PCP that can be instantiated with Blum’s graph Hamiltonicity protocol but remains to be more systematically explored. In contrast to these recent NIZK protocols, the classical approach for basing NIZK for NP on standard cryptographic assumptions uses a very different kind of information-theoretic proof systems referred to as zero-knowledge proofs in the hidden bits model. Known proofs of this type are more involved and less efficient than their zk-PCP counterparts. However, the cryptographic compiler from the hidden bits model to NIZK can rely on the intractability of factoring or, more generally, a (suitable kind of) trapdoor permutation. An interesting question is whether one can obtain a similar cryptographic compiler from zk-PCP.
Back to zk-PCP. The usefulness of zk-PCPs makes them an independently interesting object of study. The original notion from the literature, due to Kilian, Petrank, and Tardos, is stronger than the one defined above in that it requires zero knowledge to hold even against a malicious verifier who can make a bounded number of queries $t$. Here the prover is given $t$ as an additional input, and the proof size can grow polynomially with $t$. The main challenge is to make the number of queries of the honest verifier smaller than $t$, say growing at most polylogarithmically with $t$ and the statement length. Interestingly, in all known constructions the verifier needs to make two rounds of adaptive queries to the proof $\pi$, in contrast to the single round of queries in the honest-verifier case. Whether this limitation can be removed is open; see here and here for progress in this direction. Apart from the theoretical interest in this stronger notion of malicious-verifier zk-PCP, it has also found cryptographic applications. However, for most applications of zk-PCPs, including all of the cryptographic compilers mentioned above, our default honest-verifier notion suffices. From here on, we will only consider zk-PCPs with an honest verifier.
Information-theoretic compilers: zk-PCP from MPC
Information-theoretic compilers: zk-PCP from MPC
A general paradigm for constructing zk-PCPs, originating from a joint work with Kushilevitz, Ostrovsky, and Sahai, is via protocols for secure multiparty computation (MPC). This paradigm, commonly referred to as “MPC in the head,” gives a variety of information-theoretic compilers from (different kinds of) MPC protocols to (different kinds of) zk-PCPs.
An MPC protocol allows $n$ parties to compute a given functionality $f$, mapping $n$ local inputs to $n$ local outputs, while hiding (in a sense that will be specified later) all information about the inputs except the outputs.
The simplest instance of an information-theoretic compiler from MPC protocol to zk-PCP proceeds as follows. Given an NP-relation $R(x,w)$, define an $n$-party MPC functionality $f(x;w_1,\ldots,w_n)=R(x,w_1\oplus w_2\oplus\ldots\oplus w_n)$, where the input of each party $P_i$ consists of the public statement $x$ and a secret input $w_i$, and where $R(x,w)=1$ if $(x,w)\in R$ and $R(x,w)=0$ otherwise. Intuitively, $w_i$ can be thought of as a share of $w$. The output of $f$ should be delivered to all parties.
The zk-PCP can be based on any MPC protocol $\Pi_f$ for $f$, over secure point-to-point channels, that offers security against two “semi-honest” parties. The latter is a weak security requirement asserting that if all parties follow the protocol, then each pair of parties cannot learn more information from messages they receive than what follows from their inputs and the output. That is, the joint view of any pair of parties can be simulated given their inputs and outputs of $f$ alone, independently of the inputs of the other parties. Simple protocols of this kind exist unconditionally for $n\ge 5$ parties: see here, here, and here.
Given a protocol $\Pi_f$ as above, the zk-PCP prover, on input $(x,w)$, generates a proof $\pi$ as follows. First, it randomly splits $w$ into $n$ additive shares $w_i$. Concretely, $w_1,\ldots,w_{n-1}$ are picked uniformly at random, and $w_n$ is computed as $w_n=w\oplus w_1\oplus w_2\oplus\ldots\oplus w_{n-1}$. Next, the prover runs “in its head” a virtual execution of $\Pi_f$ on the common input $x$ and the secret inputs $(w_1,\ldots,w_n)$. This involves picking a secret random input $r_i$ for each $P_i$, and computing the messages sent from each party to each other party round by round, until all parties terminate with an output. Without loss of generality, each message sent by $P_i$ as well as the output of $P_i$ are fully determined by $w_i, r_i$, and the messages received by $P_i$ in previous rounds.
Finally, the prover lets $\pi=(V_1,\ldots, V_n)$, where $V_i$ is the entire view of $P_i$ in the virtual execution of $\Pi_f$. We can assume $V_i$ consists of $w_i,r_i$ and all messages received by $P_i$. The zk-PCP verifier queries a pair of random symbols $V_i,V_j$ and checks that: (1) the two views are consistent in the sense that the incoming messages in each view coincide with the outgoing messages implicit in the other view; (2) the outputs of $P_i$ and $P_j$ implicit in the views are both 1. The verifier accepts if both conditions hold and otherwise rejects.
The above zk-PCP construction is quite easy to analyze:
- Completeness follows from the definition of $f$ and the (perfect) correctness of $\Pi_f$.
- Zero knowledge follows from the fact that the pair of witness shares $w_i,w_j$ reveal no information about $w$ and by the security of $\Pi_f$; more formally, to simulate the symbols in positions $Q=\{i,j\}$, the zk-PCP simulator picks the inputs $w_i,w_j$ at random and then invokes the MPC simulator to simulate the views $V_i,V_j$ given the inputs $w_i,w_j$ and the output $f=1$. (Note that we could in fact use a leaner version of $f$ in which only the first 3 parties hold witness shares.)
- Finally, to analyze the soundness error, suppose $x$ is such that there is no $w$ for which $R(x,w)=1$. We have the following two cases. (1) The views $V_i$ correspond to some valid execution of $\Pi_f$ on inputs $(w^*_1,\ldots,w^*_n)$; in this case, the output in all views must be $R(x,w^*_1\oplus\ldots\oplus w^*_n)=0$ and the verifier will always reject. (2) The views are not consistent with any valid execution of $\Pi_f$; in this case, there must be a pair of inconsistent views, which the verifier will open and reject with $1/{n\choose 2}$ probability. Note that unlike the previous $R_{\sf 3COL}$ example, the verifier rejects a false statement with constant probability when $n$ is constant. This soundness error can be reduced to $2^{-k}$ via $O(k)$ repetitions.
The above construction can be modified and extended in many useful ways. For instance, MPC with security against one (semi-honest) party can be used by letting $\pi$ include the $n$ views along with the ${n \choose 2}$ transcripts between pairs of parties, and letting the verifier check consistency between a random view and a random transcript involving this view. The point-to-point channels can be replaced by oblivious transfer channels or even by more general channels, which in turn can be used for applying MPC protocols with fewer parties and better efficiency. The perfect correctness of the MPC protocol can be relaxed at the expense of making the zk-PCP interactive. (We will discuss the interactive model in more depth below.) The MPC model can be augmented to take advantage of input-independent preprocessing. Finally, one can use MPC protocols with a large number of parties while simultaneously achieving negligible soundness error by using MPC protocols with security against malicious (as opposed to semi-honest) parties. This will be further discussed below.
Applications. MPC-based zk-PCPs have several attractive features. Their simplicity typically makes the concrete computational overhead on the prover side smaller than in competing approaches. While the communication and verifier computation are asymptotically dominated by the alternative proof systems I will describe next, MPC-based constructions are still competitive for small problem sizes, or alternatively in settings where the prover’s computation cost is the main bottleneck. Optimized zero-knowledge proof systems of this kind include ZKBoo as well as this and this improved variants. Interestingly, the latter serve as the basis for practical post-quantum digital signature schemes such as Picnic.
In all of the above proof systems, the satisfiability of a Boolean or arithmetic circuit $C$ is proved with communication complexity that scales linearly with the number of gates $|C|$ (excluding parity or addition gates). When using information-theoretic MPC protocols, this linear communication barrier may seem inherent, but it turns out that it is not. The Ligero system gets around the circuit size barrier by using information-theoretic MPC protocols (with security against a constant fraction of malicious parties) in which the total communication complexity is comparable to $|C|$, but where the per-party communication is comparable to $\sqrt{|C|}$. In the corresponding (interactive) zk-PCP, the proof $\pi$ consists of (roughly) $\sqrt{|C|}$ symbols of length $\sqrt{|C|}$ each, and the number of symbols queried by the verifier is $O(k)$ for soundness error $2^{-k}$. Using the cryptographic compilers discussed above, this can be compiled into lightweight zero-knowledge arguments in which the communication complexity grows linearly with $\sqrt{|C|}$.
More broadly, information-theoretic compilers from MPC protocols to zk-PCPs can be used to port the big array of techniques found in the literature on efficient MPC to the domain of zero-knowledge proofs. For instance, MPC protocols based on algebraic geometric codes can be converted into (statistically sound) zero-knowledge proof protocols for Boolean circuit satisfiability in which the ratio between the communication complexity and the circuit size is constant, while the soundness error is negligible in the circuit size. Similarly, one can exploit MPC protocols that make a black-box use of general rings or other algebraic structures, MPC protocols for linear algebra problems, and many more. One should keep in mind, however, that MPC protocols are designed for a distributed setting in which no single entity has full information. This is contrasted with the setting of proof systems, where the full information is available to the prover, and explains why MPC-based zk-PCPs cannot reach the asymptotic level of succinctness we will consider in the second part of this blog post.
The computational overhead of zk-PCP
The computational overhead of zk-PCP
An intriguing open question about the efficiency of zero-knowledge proof systems is whether their computational overhead, namely the asymptotic ratio between the computation performed by the parties in the protocol and computing $R$ in the clear, can be made constant, namely independent of the level of security. The same question is open for zk-PCPs. In fact, under suitable cryptographic assumptions, the cryptographic compilers discussed above would be able to transform a zk-PCP with constant computational overhead into zero-knowledge proof protocols with the same property.
What do we know about the computational overhead of zk-PCPs? To make the question concrete, consider an NP-relation $R$ computed by a family of Boolean circuits $C_n$ of size $s=s(n)$, where $C_n(x,w)$ computes $R$ on statements $x$ of length $n$. Suppose the required soundness error is $2^{-k}$ for $k=k(n)$ (to ignore lower order additive terms, assume that $s\gg k$, say $s>k^2$). Let $s’=s'(n)$ denote the size of a Boolean circuit implementing the prover, mapping $(x,w)$ and secret randomness to a proof $\pi$. (We ignore here the verifier’s complexity, since in known constructions it is smaller than the prover’s complexity.) How small can $s’$ be? In zk-PCPs obtained from simple MPC protocols with a constant number of parties, we have $s’=O(ks)$. This can be improved to $s’=\mathrm{polylog}(k)\cdot s$ by using MPC protocols with security against a constant fraction of malicious parties. Whether this can be further improved to $s’=O(s)$ is an open question whose resolution is likely to require new technical insights. This question is open not only for zk-PCPs but also for any other kind of (computational or information-theoretic) zero-knowledge proof system from the literature. Jumping ahead, we will see that an arithmetic version of the question, where Boolean circuits are replaced by arithmetic circuits over a field $\mathbb{F}$ of size $2^{\Omega(k)}$, can be answered affirmatively by using more liberal variants of zk-PCP.
To conclude, in the first part of this blog post we discussed the advantages of decomposing a zero-knowledge proof into an information-theoretic proof system and a cryptographic compiler. We considered a simple kind of information-theoretic proof system called “zero-knowledge PCP” and matching cryptographic compilers. These give rise to theoretical feasibility results, as well as practical zero-knowledge proofs that are either non-succinct or “semi-succinct.” In the second part, we will discuss different routes to full succinctness.
Related Posts
September 29, 2021
Darlin: Proof-carrying data based on Marlin
In this blog post, we describe Darlin,…