zk-SNARKs: A High-Level Primer
zk-SNARKs are powerful cryptographic tools that provide new ways to achieve data privacy and verification. But what is a zk-SNARK? This primer introduces zk-SNARKs and explains why they’re so important in the blockchain context.
Introduction
Major advances in cryptography are relatively rare. It typically takes many years of research and a little bit of luck to produce fundamentally new insights and develop new constructs. Even when new ideas come along, cryptographers are often reluctant to fully trust them until they’re battle tested in the field. Due to this rarity and difficulty, when new cryptographic tools are discovered, it can usher in an epochal change. The discovery of tools such as RSA cryptography and elliptic curve cryptography are examples of such major advances. More recently, the discovery of zk-SNARKs represents a similarly fundamental development in the field of cryptography. In addition, these powerful new tools are well suited for use with another important emerging technology — namely blockchain.
Blockchain technologies are transformative. Specifically, blockchain protocols permit new database structures that allow multiple entities to share a common record of “truth” in the form of a distributed ledger. These shared ledgers permit non-trusting entities (with write privileges) to nonetheless agree on the consistency of the database. Remarkably, this capacity for non-trusting entities to agree holds true even in the absence of a central authority. If the group of entities contains a malicious member, who intends to gain advantage by corrupting the shared database (for example, by initiating a transaction to spend funds they do not possess), the protocol ensures that the invalid modification is rejected. Hence, integrity of the database is maintained even if users do not trust each other. This powerful property is one of the reasons why blockchain technologies are so transformative — a blockchain does not require a central entity to police the ledger and ensure consistency of shared data. Instead, blockchains can be public and permissionless, allowing any individual or organisation to modify the ledger, while also ensuring that all users can trust the accuracy of the data. This advancement enables fundamentally new mechanisms of decentralized value-transfer, as manifest by blockchains such as Bitcoin and Ethereum.
In blockchains, as in life, nothing is free and the use of a distributed ledger comes with costs. Blockchains typically include a record of all transactions/modifications enacted by users, allowing users to verify the consistency of data. A less desirable by-product of this transparent record-keeping process is that user data may be readily extracted. For example, users of the Ethereum blockchain have accounts and may transfer value (Ether) between accounts. For any given transaction, the ledger maintains a record of the accounts involved and the amount of value transferred. Accounts are nominally private as they are defined by a seemingly random string of characters related to a user’s encryption key¹. Consequently, if you don’t know the account number for a particular user, you’re unable to identify their transaction history. However, if you’re able to discover the account number for an individual or entity, you can harvest the blockchain and uncover their transaction history. For example, if you send Ether to a friend’s account, they can immediately identify your account number, determine how much value is stored in your account and learn your transaction history — every transfer of value into or out of your account is now identifiable, including transactions between accounts you own.
This lack of privacy presents a major obstacle for the construction of decentralised financial systems and infrastructure. Individual users, organisations and governments who value privacy will not willingly use a shared ledger if it allows hostile entities to view their record of transactions. To make blockchains more user-friendly, for both individuals and organisations, it is therefore necessary to include greater privacy protections to safeguard user information.
A powerful cryptographic primitive capable of enhancing privacy on blockchains is known as a zero-knowledge, Succinct Non-interactive Argument of Knowledge, or zk-SNARK for short. This cryptographic tool was brought to the attention of the blockchain community when the Zcash² blockchain went live. The Zcash blockchain implements zk-SNARKs on a fork of the Bitcoin blockchain. Hence, in essence, the Zcash blockchain is a version of Bitcoin with greater privacy features. The privacy-enhancing features of zk-SNARKs, along with their succinctness, makes them of great interest to the blockchain community.
In what follows, a high-level introduction to zk-SNARKs is presented. The goal of this article is to provide a degree of familiarity with the basic ingredients of zk-SNARKS and to foster an intuitive understanding of this cryptographic tool. This post is aimed at anyone with a general interest in these tools, including beginners in this space, and is not intended as a technical introduction.
Proof versus Argument
zk-SNARKs leverage a concept known as an argument of knowledge. To understand how zk-SNARKs work, it’s therefore necessary to understand what is meant by an argument. You are likely familiar with the basic concept of a proof, which involves two parties, a prover and a verifier. The prover constructs a proof to demonstrate that some statement is valid. Familiar examples are found in mathematics, where a prover derives a formal mathematical proof of some statement. More generally, the notion of a proof can be captured by saying that the prover constructs a proof that a particular statement (denoted as φ) and some additional information, referred to as a witness and denoted by w, belong to a certain relation R, namely (φ, w) ∈ R. This sounds rather formal but all we really mean is that the combination of φ and w behave in the way the prover claims. To give a concrete example, we could take R to be a set of relations defined as polynomials that vanish at certain points. In this case, the statement φ is some polynomial (say φ = x² − 3x + 2) and the witness w is a solution to the equation φ = 0. We say that (φ,w) ∈ R if the polynomial x² −3x+2 vanishes at x = w, namely if w² −3w+2 = 0. Thus, the proof is valid if φ and w form a pair in the relation R.
A proof system has two important properties, known as completeness and soundness. Completeness refers to the ability of a prover to convince a verifier of a valid proof. A proof system is said to have perfect completeness if an honest prover can always construct a proof that will be accepted by a verifier. That is, for any statement φ that is part of the relation R, it is always possible to construct a valid proof using proof systems with perfect completeness. Soundness refers to the likelihood that a verifier will accept an invalid proof. If a proof system has perfect soundness a verifier will never accept an invalid proof. As an example, the methods used to construct and confirm mathematical proofs (such as the proof that the square-root of 2 cannot be express as a ratio of integers) have perfect completeness and perfect soundness. For a mathematical proof, a prover can always describe every step of the proof to a verifier and convince them of the validity of the proof — this corresponds to perfect completeness. Similarly, if the prover presents a proof that is invalid, the verifier may investigate all steps of the proof and uncover the flaws, thereby preventing the prover from convincing the verifier of an invalid proof (i.e. perfect soundness).
In practice it is not always necessary (or possible) to ensure that a verifier rejects all invalid proofs. In fact this requirement may impose an overhead on verifiers that renders some tasks either impractical or prohibitive. For example, many problems are computationally intensive to solve, yet all verifiers have bounded computational powers. This motivates the consideration of proof systems that relax the constraint of perfect soundness. More generally, one may consider proof systems that possess computational soundness, meaning a verifier is highly unlikely to accept an invalid proof. One can rigorously define what is meant by proof systems with computational soundness but the intuitive picture is straight forward. Instead of demanding absolute certainty that an accepted proof is valid, one requires statistical certainty that an accepted proof is valid.
A proof generated by a proof system that has perfect completeness and computational soundness is referred to as an argument — such systems generate arguments rather than proofs. The difference between a proof and an argument therefore reflects the difference between perfect soundness and computational soundness. Proof systems with computational soundness and proof systems with perfect soundness differ in their assumptions about the computational powers of the prover. A proof system with perfect soundness assumes a computationally unbounded prover and requires the verifier to reject all invalid proofs. If the verifier did not reject all invalid proofs, the computationally unbounded prover would be able to fool them. Conversely a proof system with computational soundness assumes a computationally bounded prover. Consequently the verifier need only protect themselves against invalid proofs that could be generated by a prover with bounded resources. The notion of computational soundness therefore appears very natural and simply means that a computationally bounded prover is unlikely to fool a verifier.
It may seem strange to allow a verifier to (potentially) accept invalid arguments. However, in practice this condition is necessary. Most cryptographic techniques can be broken if an attacker (referred to as an adversary) has access to sufficient resources. For example, with sufficient computational power, an adversary can factorise large primes and break RSA cryptography or, alternatively, take enough random guesses to break other cryptosystems. Accordingly, the verifier is often at the mercy of underlying cryptographic techniques and the verifier’s ability to confirm the validity of an argument is dependent on the strength of the tools used to generate the argument. Note that proof systems with computational soundness make probabilistic statements regarding the likelihood that a verifier accepts an invalid proof. Deterministic statements are not used for such systems as, typically, a computationally bounded adversary could randomly guess private information and generate a proof that is accepted. As an example, an adversary could randomly guess the prime factors needed to break an RSA encryption scheme. Proof systems with computational soundness ensure that the likelihood of making a successful random guess is negligibly small. For example, a computationally sound proof system may require that an adversary would take longer than the age of the universe to successfully guess the private information needed to generate a seemingly valid proof (on average, based on currently available computational resources). Although such assertions are not deterministic, they’re generally sufficient for practical applications.
Interactive versus Non-interactive
An interactive proof system involves a dialogue or communication between the prover and the verifier. The prover may first send some information to the verifier, with the goal of convincing the verifier of a statement such as “I know the solution to a particular problem”. Subsequently, the verifier sends a request for additional information back to the prover. The prover replies with the requested information, to which the verifier may request further information. After multiple iterations of this process the verifier eventually obtains enough information to assess the validity of the proof. At this point, the dialogue concludes and the verifier decides that the proof is either valid or invalid.
Non-interactive proof systems, on the other hand, do not involve such a dialogue. In a non-interactive proof system, the prover generates a proof and makes it available to the verifier. The verifier performs some operations on the proof and decides to either accept or reject the proof. There is no need for further communication as the verifier reaches their decision solely on the basis of operations performed on the initial proof.
Non-interactive proof systems are ideal for the blockchain setting. When a user generates a non-interactive proof of some statement and submits it to a blockchain, any individual can perform operations on the proof and decide whether they accept or reject the proof, without having to further communicate with the prover. Relative to interactive systems, non-interactive proofs can therefore provide efficiencies that may be necessary for systems handling financial transactions. For example, if user A claims to have enough funds to support a promised payment, it is clearly inefficient for user B, who is deciding whether to enter into a financial agreement with A, to engage in multiple back-and-forth communications to decide whether to trust A’s claim. If user B can instead perform a single operation and convince themselves of the accuracy of A’s claim, they may safely (and efficiently) enter into a financial agreement with A.
The preceding discussion allows us to define a non-interactive argument. Formally, a non- interactive argument refers to a non-interactive proof system possessing perfect completeness and computational soundness. Non-interactive arguments involve a prover, who generates an argument, and a verifier, who performs operations on the argument and decides to either accept or reject it. No further interactions are required for the verifier to reach their decision.
Succinctness and SNARGs
Succinctness of a proof system is a concept that is both easy to describe and difficult to define in a general sense. Intuitively, a succinct proof system involves the exchange of short messages and/or requires fast execution time(s). Succinct proof systems typically have a discrepancy between the complexity of the prover’s algorithm and the complexity of the verification algorithm. The algorithm for generating proofs can be rather involved and may require significant time and/or computational resources to execute. However, the outputted proof remains short (i.e. succinct) and, relative to the proving algorithm, the verification algorithm is fast. These features permit a discrepancy between the resources required to generate a proof and the resources required to verify a proof. A prover may require vast computational resources and/or time to generate a proof, yet verification can remain efficient. Succinct proof systems therefore allow computationally limited verifiers to verify the output of a computationally expensive calculation. This capacity has many applications. For example, a computationally limited verifier can outsource a complex calculation to the cloud and verify the returned result if it includes a succinct proof.
More formally, the definition of succinctness can vary among authors, depending on the proof system and the context. With respect to zk-SNARKs, succinctness usually relates to the length of the proof generated by the prover and the duration of the execution time for the verifier. In mathematical terms, a succinct proof system typically generates proofs with polynomial length in a quantity referred to as the security parameter (denoted as κ). For larger values of κ, the system is more secure, meaning that, e.g., the verifier is less likely to accept an invalid argument. A proof system is called succinct if (i) the proof has polynomial length in κ, denoted as poly(κ), and (ii) the time complexity of the verification process has polynomial length in both the size of the statement being proved and the security parameter (denoted as poly(κ + |φ|), where |φ| denotes the length of the statement). Although the precise details of these formal definitions can vary, the intuitive picture remains the same.
The information discussed so far is sufficient to introduce the concept of a succinct non- interactive argument (or SNARG, for short). A SNARG is a non-interactive proof system with perfect completeness and computational soundness, such that the proof (or argument) length is poly(κ), and verification involves time complexity poly(κ + |φ|).
Zero-knowledge and Arguments of Knowledge
SNARGs are not discussed as frequently as SNARKs in mainstream blockchain articles, though it’s helpful to understand the definition of a SNARG to fully appreciate the meaning of a SNARK. In basic terms, it’s straightforward to state the difference between a SNARG and a SNARK — SNARGs involve non-interactive arguments whereas SNARKs use non- interactive arguments of knowledge. Hence, unlike a SNARK, a SNARG is not an argument of knowledge. This means that SNARGs allow verifiers to convince themselves that a proof is valid but they do not allow verifiers to confirm the type of knowledge possessed by the prover (this point is explained in more detail below). Recall that, formally, a non-interactive argument system has perfect completeness and computational soundness. A non-interactive argument of knowledge has perfect completeness and computational knowledge soundness. Thus, to understand a SNARK we must first define computational knowledge soundness. However, before doing so, it’s helpful to first define the concept of zero-knowledge.
Zero-knowledge
As described earlier, the notion of a proof may be formalised by saying that a valid proof arises when the prover knows a witness w and a statement φ such that (φ,w) ∈ R, and further, the prover uses these to derive their proof. Sometimes a prover may not wish to reveal the information encoded by w to the verifier. For example, a prover may wish to prove that a valid transaction has occurred yet may not want to reveal the actual amount of value transferred. A proof system is said to be zero-knowledge if the proof does not reveal anything more than the fact that the claimed statement is true — i.e. the proof does not reveal any information about the witness w to the verifier.
Cryptographers formally define zero-knowledge by considering an adversary who is a malicious verifier. This adversary wants to extract any information they can about the witness w and thus attacks the prover’s proof in an effort to ascertain w. Formal definitions of zero-knowledge introduce an actor called a simulator, who uses certain trapdoor information to simulate a proof without actually knowing the witness w. If an adversary receives a valid proof (which is derived using w) and a simulated proof (derived without knowing w, but otherwise seemingly equivalent to a valid proof) and cannot distinguish between the two proofs, the proof system is said to have zero-knowledge. In such cases, the malicious adversary cannot learn anything more by attacking a proof generated using w than they can learn by attacking a proof that did not use w. Since the latter simulated proof does not contain any information about w, the adversary cannot possibly learn anything about w in either case and zero-knowledge is assured.
The existence of a simulator that generates proofs without knowing w may seem to contradict the whole purpose of a proof system. How can it be OK for an actor to generate a proof without knowing such critical information? However, when one looks into the technical details of such systems, this concept is not as strange as it first appears. In the case of Zcash, the proof system relies on information referred to as a common reference string. Constructing this common reference string automatically produces a trapdoor that would enable a malicious user to cheat the system. This trapdoor is the so-called toxic waste that had to be safely destroyed to ensure the security properties of Zcash. If anyone ever discovered the trapdoor, they would be able to generate proofs for invalid transactions and thereby create value from nothing. Security proofs for Zcash assume that the simulator has access to the trapdoor and can therefore generate seemingly valid proofs without knowing the witness w. In practice one would never want such a simulator to exist as it would undermine the entire system. Theoretically, however, such an actor can exist and plays an important role in rigorously defining security proofs for the system. These observations, made in the context of Zcash, hold more generally for many zero-knowledge constructs.
Arguments of Knowledge
In cases where the prover does not wish to reveal the witness w, the verifier may want to convince themselves not only that the prover’s argument is valid but also that the prover does indeed know the witness w. For example, if someone tells you they know how to solve a complicated equation and they know a solution, but refuse to share the solution with you, you won’t necessarily believe them unless they convince you they do in fact know the solution.
Arguments of knowledge are arguments that enable a verifier to confirm that the prover does indeed know the witness w. Recall that non-interactive arguments have perfect completeness and computational soundness, where computational soundness ensures that the verifier is highly unlikely to accept a proof if the corresponding statement φ is not part of the relation R (more formally, if the statement φ is not part of the language used to form the relation R). Non-interactive arguments of knowledge, on the other hand, possess perfect completeness and computational knowledge soundness. Computational knowledge soundness ensures that the verifier is unlikely to accept an invalid proof if both the statement φ and the associated witness w do not belong to the relation R, i.e. (φ, w) is not in the relation R. Note the difference here. Proof systems with computational soundness allow a verifier to convince themselves that the prover’s statement φ is true (with high probability). Proof systems with computational knowledge soundness have the additional property of allowing the verifier to convince themselves that the prover actually knows a valid witness w. Consequently computational knowledge soundness is a stronger property than computational soundness.
More formally, proof systems that generate arguments of knowledge allow the construction of an actor referred to as an extractor. Given access to the same information as an adversary who generates a proof, the extractor is able to “extract” the associated witness information w. That is, the extractor is capable of extracting the witness corresponding to the adversary’s proof. If the statement and extracted witness do not belong to the relation R, the verifier is very unlikely to accept the proof as valid. Thus, arguments of knowledge allow the verifier to ensure that the prover’s claim is correct and that the prover does indeed know the information necessary to make such a claim. An argument of knowledge is therefore stronger than an argument, and consequently a SNARK is stronger than a SNARG, because the latter only permits the verifier to assess the statement φ, whereas the former also allows the verifier to determine whether the prover has a valid witness w. Note that the verifier does not necessarily learn any other information about w. Computational knowledge soundness only assures that the verifier can assess whether or not the prover knows w. This property is compatible with (but does not assure) zero-knowledge.
zk-SNARKs
Putting this all together, we now have all the ingredients necessary to define a zk-SNARK. A zk-SNARK is a zero-knowledge proof system that generates succinct non-interactive arguments of knowledge. Being arguments of knowledge, zk-SNARK proof systems have perfect completeness and computational knowledge soundness. Therefore a prover can always convince a verifier of a valid proof and a verifier is highly unlikely to accept a proof if the prover does not know a valid witness. These non-interactive proofs do not require the exchange of any information beyond transmission of the proof by the prover — no further dialogue is required between prover and verifier. The verifier need only perform operations on the proof to decide whether to accept or reject it. Being succinct, the proofs are small in size and verification is relatively fast. Finally, the proofs are zero-knowledge, meaning a verifier does not learn anything about the witness w, even though they can convince themselves that the prover does indeed know the witness. Note that the zero-knowledge property must be added to the SNARK — in general, an argument of knowledge does not possess zero-knowledge and one must modify the SNARK to ensure the verifier can convince themselves that the prover knows a witness and yet learn nothing about the witness.
The ability to prove the validity of a statement without revealing sensitive information makes zk-SNARKs a powerful cryptographic tool. Furthermore, the properties of zk-SNARKs make them well-suited for the blockchain use case. Specifically, because zk-SNARKs are non-interactive, they reduce network traffic by minimising the dialogue required between prover and verifier. The succinctness property of zk-SNARKs reduces both the amount of data that must be stored on-chain and the resources required for verification. These properties are important as storing information on a blockchain such as Ethereum is expensive. Efficient verification algorithms are also essential for the implementation of proof systems using smart contracts on-chain. Moreover, efficient verification algorithms ensure that computationally limited users can participate in the blockchain, thereby democratising access to the system (i.e. the pool of participants is not limited to those with vast computational resources). As zk-SNARKs are arguments of knowledge, verifiers can convince themselves that the prover does indeed have access to the claimed information (such as the amount of funds in their account). Finally, the zero-knowledge property enhances user privacy and protects sensitive information, despite the otherwise open nature of blockchain protocols. Clearly zk-SNARKs are powerful tools that have much to offer blockchain ecosystems.
The utility of zk-SNARKs in the blockchain context was already demonstrated in the case of Bitcoin, with the Zcash fork up and running. Other projects such as Zeth³ aim to bring zk-SNARKs technology to Ethereum. Much more can be learnt about zk-SNARKs by delving into the technical details of how these constructs work. Nonetheless, before doing so, it helps to have an intuitive understanding of zk-SNARKs and why they’re useful in a blockchain context. Hopefully this article helped you develop this intuition. For introductory articles on the technical workings of zk-SNARKs see the Zcash blog⁴, the blog post by Vitalik⁵ or Christian Reitwiessner’s notes⁶ (which discuss implementations using Quadratic Span Programs⁷).
Any thoughts, comments or questions? Tweet us @Clearmatics
Kristian McDonald, Cryptography Researcher, Clearmatics
Acknowledgments
Thanks to Antoine Rondelet and Duncan Tebbs for feedback on this post.
References
[1] Technically, account numbers correspond to the last 160 bits of the hash of a user’s public key.
[2] Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. Zerocash: Decentralized anonymous payments from Bitcoin. In Proceedings of the 2014 IEEE Sympo-sium on Security and Privacy, SP ’14, 2014.
[3] Antoine Rondelet, and Michal Zajac. ZETH: On Integrating Zerocash on Ethereum. arXiv:1904.00905. Retrieved from: https://arxiv.org/abs/1904.00905
[4] https://z.cash/technology/zksnarks
[5] https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
[6] https://chriseth.github.io/notes/articles/zksnarks/zksnarks.pdf
[7] Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic span programs and succinct NIZKs without PCPs. In EUROCRYPT, volume 7881 of Lecture Notes in Computer Science, pages 626–645, 2013.
