Research Spotlight | A Historical Perspective on Zero-Knowledge Proofs

Zero-knowledge proofs have been gaining popularity in recent years due to both their capabilities to scale existing blockchains and the increased demand for privacy. While it may seem like the zero-knowledge proof narrative has come out of nowhere, they have actually been around since the 1980s, but were largely an academic pursuit without much opportunity for practical applications. This is largely due to the nature of databases which have traditionally been centralized, rendering zero-knowledge proofs interesting but not that useful. Due to the rise of decentralized databases - in this case blockchains - the applications of zero-knowledge proofs as well as the need for them has skyrocketed.

In this post Zaira Pindado Tost, part of the Dusk Research Team, will give you an expert deep-dive into the history of zero-knowledge proofs, as well as introduction to how they actually work beyond the classic line of “proving something without revealing what it is”.

This is quite a technical article, so if you’re looking for more of an introduction to the concept of zero-knowledge proofs and what they are used for, rather than the math behind them, check out this article by Hein Dauven and this Twitter space, where founder Emanuele Francioni speaks about zero-knowledge proofs.

Zero-knowledge proofs are used in many practical scenarios, although for many years were mostly a theoretical tool. In the last two decades they have been improved, becoming orders of magnitude more efficient. In this article, we give an overview of the evolution of this tool.

A Zero-Knowledge (ZK) proof scheme is a cryptographic tool that allows one party, called the prover, to provide a convincing proof about the validity of some statement to another party, the verifier, without revealing any additional information. Intuitively, having such a proof that a claim holds is equivalent to having received from a trusted party the guarantee that this claim is true.

For many years, ZK proofs were mostly a theoretical tool , but in the last two decades they have been improved with new methods from pairing-based cryptography, exploiting properties of polynomials, hash functions, and many other techniques, becoming orders of magnitude more efficient. Some of them are even scalable and post-quantum secure. Nowadays, ZK proofs are used in practice in blockchain applications as a proof for correct computations of secret elements, or to allow anonymous payments, to name a few applications. They are also used for anonymous identification and for self-sovereign applications. In the following, we give an overview of the history of how this tool has evolved since its origin up to recent breakthroughs.

In 1985, Goldwaser, Micali and Rackoff introduced Zero-Knowledge (ZK) Proofs in their work The knowledge complexity of interactive proof-systems. They defined these proofs as follows; Given a certain type of computational problems, the prover’s goal is to convince the verifier that they know a solution to the problem. For example, the quadratic residuosity problem is a problem that cannot be solved in a reasonable amount of time. Given an element y, we say that y is a quadratic residue mod x, if there exists some z such that y=z^2 mod x. The first ZK proofs defined in that work were for proving that a public y is a quadratic residue, while keeping the square root (z) hidden for the verifier. Both parties exchange a series of messages until the verifier is convinced about the validity of the statement or the contrary, so they decide to accept or reject the proof. Even though the problem is not solvable in a reasonable amount of time, there is an efficient algorithm associated with the type of problems to recognize if a possible solution satisfies the relation defined by the problem.

The first ZK proofs were introduced as an interactive protocol between the prover and the verifier, where the verifier randomly samples elements to create challenges for the prover and expects convincing answers. For example, in the Schnorr protocol, the prover wants to convince the verifier that they know the discrete logarithm of an element y (knowledge of some x such that y=g^x  for some fixed public element g). This protocol is commonly used in practice. At Dusk Network we use a variant of the Schnorr protocol to prove knowledge of some discrete logarithm of two elements. This guarantees the ownership of the note of the user who is spending it.

In contrast, in non-interactive proofs, this exchange of messages is substituted by a single message from the prover to the verifier that constitutes the proof and can be checked off-line by the verifier. Being online during the construction of the proof is not very practical at scale or for a system that is live continuously, so a way to allow the prover to make their proof without the verifier having to be online and waiting is necessary. At Dusk Network, we work with Non-Interactive Zero-Knowledge (NIZK) proofs since they are more practical and more efficient. In order to use this non-interactive model, we need something that replaces the messages from the verifier, those challenges that in the interactive protocol they send to the prover. We use the CRS model introduced by Blum et al. in the work Non-interactive zero-knowledge and its applications. CRS stands for Common Reference String, and consists of a set of public parameters shared by the prover and the verifier, and generated by a third party. The challenge to the prover is codified inside this CRS, since the prover does not know the secret elements chosen by the third party to compute it. Moreover, each message from the prover to the verifier in the interactive version is hashed and used in the next steps in the construction of the proof. This is done to simulate the commitment of the prover in the interactive version, that is, the notion that they send a message and cannot change it afterwards.

The usability of NIZK proofs depends on the type of problems that they apply to and the efficiency associated with the proof system. Ideally, one would like to define proof systems that allow the prover to prove very general statements, for example Circuit Satisfiability. Circuits encode in a natural way many types of computation. Circuit Satisfiability is used to ensure correctness of these computations. It is a very powerful problem since any other problem that is not solvable in a reasonable amount of time can be converted in an efficient way to one of this kind. However, historically it was difficult to design efficient proofs for these powerful problems. For many years, the only known efficient constructions were for very specific problems, like identification schemes (Zero-knowledge proofs of identity) and shuffle arguments for electronic voting (Receipt-Free Mix-Type Voting Scheme - A practical solution to the implementation of a voting booth).

In the last two decades, this field experienced a big change with the development of pairing-based cryptography. A pairing or bilinear map is a bilinear operation that, along with two elliptic curves, forms a bilinear group. The bilinear structure is very suitable to develop efficient constructions of NIZK proofs with efficient public verification. Pairing-based NIZK proofs were introduced by Groth, Ostrovsky and Sahai in their work Perfect Non-Interactive Zero Knowledge for NP in 2006 where the authors constructed the first efficient NIZK argument for general statements in the CRS model. Although this work was much more efficient concretely than any other NIZK proof in the same model, a proof for Circuit Satisfiability requires linear communication in the circuit size, which is completely impractical for most interesting circuits.

The techniques introduced in Groth, Ostrovsky and Sahai were important to inspire the framework of Groth-Sahai proofs (Efficient Non-interactive Proof Systems for Bilinear Groups) in 2008, which defines proofs for specific problems. They presented proofs of satisfiability of several types of quadratic equations with pairings. For many equation types they remain the best alternative based on very weak assumptions in bilinear maps. This line of research culminated with the well-known zk-SNARKs constructions that we explain in the following.

In 2010, Groth (Short Pairing-Based Non-interactive Zero-Knowledge Arguments) presented the first constant-size NIZK argument for Circuit Satisfiability, combining techniques from previous pairing-based NIZK proofs and strategies from interactive proofs. Intuitively, since the proof is very small (constant, independent of the circuit size), it is not possible under standard assumptions to extract a valid witness. A non-standard assumption is needed to extract a witness linear in the circuit size in the security proof, as formalized by the result of Gentry-Wichs (Separating Succinct Non-Interactive Arguments From All Falsifiable Assumptions). Therefore, in Groth's work the security is proven under a knowledge of exponent assumption, which is very strong and non-desiderable for many cryptography community members. This technique started a line of research followed by Gennaro et al. (Quadratic Span Programs and Succinct NIZKs without PCPs) and other works that progressively decrease the size of the proof, all of them are based on very strong assumptions. These constructions are called zk-Succinct Non-Interactive Arguments of Knowledge (zk-SNARKs).

Another line of research that makes the proof very efficient in terms of communication under very weak falsifiable assumptions was introduced by Jutla and Roy in Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces with the Quasi-Adaptive NIZK (QA-NIZK) proofs. They are proven under weak assumptions which is very desiderable, but they are defined for some very specific types of problems. For example, for proving linear relations in a group. This is the drawback they have, but they are very efficient since they consist of just one group element.

In practice, we need a proof that fits the problems we want to prove that we have a solution for. The more flexible they are, the better. This is why we choose to work with zk-SNARKs even though their security is proven under very strong assumptions, because it is compensated by the very small proof and they allow us to work with general statements. A drawback of all NIZK proofs is the need of a trusted third party who creates the CRS. This CRS was dependent on the circuit in the first generation of SNARKs, so a new CRS had to be produced for each different circuit. This is very impractical, due to the large size of the CRS.

In the last two decades, a lot of effort has been made to decrease the trust in this third party. Moreover, a lot of new constructions have been presented in different lines of research. In the newest zk-SNARKs, the CRS is universal in the sense that it can be reused for any other circuit, or if the user does not trust it, they can update it. There is another part of the CRS that depends on the circuit and the user derives it from the universal CRS. An example of this is PLONK, the zk-SNARK used in Dusk Network for proving the correct computations in the circuits. In other constructions like STARKs or Bootle et al. (the work that Bulletproofs is based on) presented during these years there is no need for the CRS being created with any structure, just random elements. They use other types of assumptions, but they are still defined for the correctness of a circuit and also different problems. However, we prefer PLONK because it has constant size and constant verification. We have the same performance in general terms in the other pairing-based zk-SNARKs, which remain the best choice in terms of efficiency. STARKs and Bootle et al.-based constructions remain the best choices in terms of weaker assumptions and no need for a trusted third party to create a structured CRS.

More articles like this will come in the following weeks where we will talk more about the Common Reference String (CRS) of NIZK proofs, cryptographic assumptions and circuits.