SNARKs are rapidly becoming more important in the context of bitcoin and its adoption. The bitcoin blockchain stands as the most resilient and accessible global settlement layer for the internet. But despite this significant value proposition, bitcoin's functionality is limited by the simplistic nature of its scripting language, Script.
The ability to verify off-chain arbitrary computations—such as those executed on "Layer 2" solutions—without actually performing them on-chain, presents a unique opportunity to securely enhance the privacy, expressivity, and scalability of bitcoin. SNARKs, which are also often simply referred to as zero-knowledge proofs, provide a powerful means to achieve this.
In this blog, we will explore the evolution and importance of SNARKs, tracing some of the key technological advancements made in the last few decades.
Introduction to Interactive Proofs
In mathematics and logic, proofs are essential for establishing the truth of theorems and propositions based on axioms (i.e. self-evident truths) and previously established statements. A classic example of this method is Euclid’s proof that there are infinitely many prime numbers. To demonstrate this, Euclid began with the assumption that there is a finite list of all prime numbers. By multiplying all the primes in this list together and adding one to the total, he created a new number. This number couldn’t be divided evenly by any prime in the list—each division would leave a remainder of one. Therefore, this new number must either be prime itself or have prime factors that are not included in the original list. In either scenario, it reveals the existence of additional prime numbers beyond those initially considered, which leads to the conclusion that there must be infinitely many primes.
This logical progression from axioms, such as any integer greater than one is either a prime itself or can be factored into primes, to conclusion is central to mathematical proofs. It is a powerful illustration of how significant discoveries can be made by starting from basic principles and applying rigorous logical reasoning.
Now consider a scenario similar to a game show where you know the answer to a hidden riddle but can't reveal it directly. The host (the verifier) asks you (the prover) questions to try and figure out if you know the answer (the secret). You strategically answer these questions to provide "evidence" of the knowledge without ever giving away the secret itself. Unlike the one-way nature of Euclid’s axiomatic proof, this method introduces the concept of back-and-forth dialogues between the prover and the verifier. This interactive interpretation of proof led to the development of what is known in the literature as an interactive proof (IP).
Why Interact in the First Place?
The concept of interactive proof might be more familiar than we realize. Much like how we intuitively engage in back-and-forth exchanges to clarify misunderstandings or build consensus with friends and family, similar interactions can prove complex mathematical statements between machines.
Consider tackling problems within the NP complexity class, such as the canonical Boolean satisfiability problem (SAT) that asks whether a given Boolean formula (e.g. \(x\) AND NOT \(y\)) can be satisfied by some assignment of its variables (e.g: \(x\) = True, \(y\) = False). While finding an efficient algorithm to solve SAT still remains challenging, verifying a proposed solution (also known as “witness”, \(|w|\)) is straightforward and computationally easy. But then we ask ourselves: if verifying NP problems is already easy, why bother with interactive proofs at all? Why not simply send the witness?
Interactive proofs add two significant improvements in this context.
First, they offer a means to reduce the communication complexity below the cost of sending the witness. Rather than transmitting the entire solution (which can be very large for large computation), a prover can engage in a dialogue with the verifier, responding to specific challenges. This interaction allows the prover to demonstrate the correctness of the solution while transmitting significantly less data than the full \(|w|\).
Second, interactivity allows the prover to convince the verifier of the solution's correctness without disclosing the solution itself. This foundational concept, where a verifier is convinced of a statement's truth through interactions without the solution being revealed, was pioneered by Goldwasser, Micali, and Rackoff in 1985 [SMR85].
Lund, Fortnow, Karloff, and Nisan further underscored the power of interactive proofs beyond NP statements. They showed that an unbounded prover can convince a polynomial-time verifier that a Boolean formula is unsatisfiable [LFKN92]. This result is significant because it implies that, under the interactive proof model, certain coNP problems (like UNSAT) can be verified with an efficient verifier, a feat not achievable under the static proof model without the strong assumption that \(\text{coNP} = \text{NP}\).
Building on the work of Lund et al., Shamir showed that the class of problems verifiable in polynomial time through interactive proofs aligns exactly with PSPACE [Sha92]. This class includes decision problems solvable in polynomial space, enveloping a broad spectrum of classes including P, NP, coNP, and beyond. The implication is profound: a vast array of problems, extending well beyond the confines of NP, are amenable to proof via interactive dialogues.
From Interactive Proof to Succinct Non-Interactive Argument of Knowledge (SNARK)
Goldwasser et al.'s research laid the theoretical foundation for interactive proof systems and zero-knowledge proofs. In their seminal paper, they proposed that every interactive proof system must satisfy two key properties:
- Completeness
- If the prover is honest, it will eventually convince the verifier. Any true statements will have a convincing (highly probable) proof.
- Soundness
- The prover can only convince the verifier if the statement is true. False statements will not have a convincing proof. A proof system is statistically sound if soundness holds for any unbounded (infinite computational resource) prover. A proof system is computationally sound if soundness holds for only a computationally bounded prover.
Statistically sound interactive proof systems are unlikely to have communication improvements beyond the size of witness \(|w|\) [BCC+14]. However, Kilian in 1992 showed that we can do much better if we relax the notion of soundness from statistical soundness to computational soundness. He showed that for computationally sound proof system (argument system), it is possible to generate a succinct argument that is poly-logarithmic in the size of the statement (\(|x|\)) and the witness (\(|w|\)) [Kil92]. Kilian achieved this by leveraging the notion of Probabilistically Checkable Proofs (PCPs), a highly influential idea in computational complexity. Soon a landmark result followed in the form of the PCP theorem, which stated that every decision problem in NP has a proof that can be verified with a high degree of confidence by looking at only a constant number of bits from the proof, chosen at random. New York Times even wrote an article on it: “New Short Cut Found For Long Math Proofs”.
The idea that a proof can be probabilistically verified by examining only a small part of it, paved the way for the construction of succinct arguments.
While interactive proofs inherently rely on back-and-forth communication between the prover and the verifier, practical applications necessitate minimizing these interactions due to their computational cost and impracticality in real-world scenarios. Addressing this challenge, Blum et al. in 1988 laid the groundwork for reducing such interactions by introducing the concept of "common random string" [BFM88]. In this framework, both the prover and the verifier operate using the same sequence of random coin tosses, effectively pre-establishing a shared basis for proof generation and verification. This concept was later generalized into the "common reference string (CRS),” "structured reference string (SRS),” and “universal reference string (URS)." These models consolidate all interactions into a pre-processing step, enabling the prover to subsequently generate proofs and the verifier to check these proofs using the agreed-upon CRS, SRS, or URS.
Building upon the work of Shamir, Micali applied the Fiat-Shamir heuristic to transform Kilian’s interactive argument into a non-interactive one within the random oracle model [Mic94]. Random oracle is a theoretical black box that provides a truly random response to every unique query. Formalized by Bellare and Rogaway in 1993, random oracle model simulates idealized collision resistant hash functions [BR93]. The construction was later further refined by replacing random oracles with extractable collision-resistant hash functions to provide a stronger notion of knowledge soundness [BCCT12], [BCC+14]. Knowledge soundness asserts that if a verifier accepts the proof as valid, not only is the statement true, but the prover must also possess explicit knowledge of the witness.
Knowledge soundness provides a deeper layer of security by linking the truth of a statement to the possession of concrete, extractable knowledge.
While a PCP verifier only needs to check a tiny portion of the proof, the proof itself can be quite large. This is because PCPs embed redundancies to allow for probabilistic verification. The shortest PCPs known today are still quite lengthy (growing quasilinearly with the input size) [BS08] and finding a linear size PCP still remains an open challenge for researchers [ACY23]. This limitation led to the development of Interactive Oracle Proofs (IOPs). IOPs are essentially Interactive Proofs, where the verifier has a PCP-like (oracle) access to prover’s messages. Even though IOPs do not improve the soundness of PCPs, they allow us to construct compact proofs that are highly desirable for practical applications.
Advancements such as these—reducing proof sizes, minimizing verification computations, eliminating interactive steps, and integrating knowledge soundness—have collectively contributed to the development of what is now known as SNARK, or Succinct Non-Interactive ARgument of Knowledge.
Constructing a SNARK
To generate a SNARK for an NP statement, we must first convert it into a “form” suitable for proof generation. Typically, this involves encoding the computation as a series of polynomial equations that encapsulate the underlying logic. By ensuring these equations hold true, we can guarantee the integrity of the entire computation. Polynomials are therefore one of the core-ingredients of SNARKs.
To get a better intuition for why polynomials are so crucial, consider a dataset \(d_1 = [0,1,2,3,4,5,6,7,8,9]\). If we choose to represent this dataset as a polynomial, we can use the index of each element as the x-value and the element itself as the y-value. From this, we can derive a polynomial that perfectly fits the data, which in this case is a simple expression.
\(P(x) = x\)
However, altering just one element of the dataset—for example, changing \(d_1\) to \(d_2=[0,1,2,3,4,5,6,7,8,10]\)—can radically transform the polynomial.
\(\displaylines{P(x)=2.756×10^{−6}x^{9}−9.921×10^{−5}x^{8}+1.505×10^{−3}x^{7}\\−1.250×10^{−2}x^{6}+6.186×10^{−2}x^{5}−1.854×10^{−1}x^{4}\\+3.255×10^{−1}x^{3}−3.020×10^{−1}x^{2}+1.111x}\)
This highlights a crucial property: a polynomial's shape uniquely identifies the data it represents. Fundamental Theorem of Algebra states that a polynomial of degree \(d\) can have at most \(d\) roots. This means any two polynomials of degree \(d\) can intersect at no more than \(d\) points unless they are the same polynomial. From a cryptographic perspective, this indicates that a prover could potentially deceive a verifier by claiming to know a polynomial of degree \(d\) if the verifier only checks the polynomial at those \(d\) specific points—no more. However, the domain of \(x\) (all possible values of \(x\)) is typically very large. For instance, if \(x = 10^{50}\), then the probability that a prover could successfully cheat in a single round of verification is merely
\(d/10^{50}\)
Given that \(d\) is usually much smaller than \(10^{50}\), this probability becomes exceedingly small, making the deceit highly unlikely. This illustrates the effectiveness of using polynomials in SNARKs where security hinges on the improbability of successfully guessing a polynomial without genuine knowledge of it. This naturally leads to the question: How do we derive polynomials from a computation?
One way to generate these polynomials is by writing the computation as an arithmetic circuit. Arithmetic circuit is a computational model that consists of inputs, outputs, and a set of computational gates connected by wires. These gates perform basic arithmetic operations such as addition and multiplication over a finite field. The circuit is then compiled into an algebraic representation called a Quadratic Arithmetic Program (QAP), which converts the circuit's operations into a set of polynomial equations. The transformation of computation into a QAP makes it possible to use the QAP Satisfiability problem, an NP-complete problem, as a foundation for generating proofs. This conversion leverages the power of NP-completeness, a property that allows any problem in the NP class to be reduced to this format. As a result, SNARKs can be constructed for a vast array of computations.
The development of SNARKs has been fueled by two fundamental limitations of present-day blockchains: privacy and scalability. SNARKs achieve privacy by shielding the inputs of the computation (Zero Knowledge SNARKs) and scalability by generating a succinctly verifiable proof of computation. Pinocchio [PHGR13] marked the first practical implementation of zk-SNARKs and was originally used by Zcash to implement its shielded transaction protocol. In 2016, Jens Groth enhanced this protocol, leading to the development of what is now known as Groth16. Since then, the landscape has seen a rapid proliferation of diverse SNARK implementations. Although we are still in the early stages of this technology, the advancements made over the past decade set a promising precedent. Looking ahead, we can expect the next few years to bring innovative developments that will further enhance the capabilities of SNARKs.
Reference:
[ACY23] Gal Arnon and Alessandro Chiesa and Eylon Yogev. “IOPs with Inverse Polynomial Soundness Error”. In: Cryptology ePrint Archive, Report 2023/1062 (2023).
[BCC+14] Nir Bitansky, Ran Canetti, Alessandro Chiesa, Shafi Goldwasser, Huijia Lin, Aviad Rubinstein,and Eran Tromer. The hunting of the SNARK. Cryptology ePrint Archive, Report 2014/580,2014. http://eprint.iacr.org/2014/580.
[BCCT12] Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. From extractable collisionresistance to succinct non-interactive arguments of knowledge, and back again. In ShafiGoldwasser, editor, ITCS 2012, pages 326–349. ACM, January 2012.
[BFM88] Manuel Blum, Paul Feldman, and Silvio Micali. "Non-interactive Zero-Knowledge and Its Applications." In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (STOC '88). Association for Computing Machinery, New York, NY, USA, 1988, pp. 103–112. DOI: https://doi.org/10.1145/62212.62222.
[BR93] Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designingefficient protocols. In V. Ashby, editor, ACM CCS 93, pages 62–73. ACM Press, November 1993.[BS08] Eli Ben-Sasson and Madhu Sudan. “Short PCPs with Polylog Query Complexity”. In: SIAM Journal on Computing 38.2 (2008). Preliminary version appeared in STOC ’05., pp. 551–607.
[Kil92] Joe Kilian. "A Note on Efficient Zero-Knowledge Proofs and Arguments (Extended Abstract)." In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing (STOC '92). Association for Computing Machinery, New York, NY, USA, 1992, pp. 723–732. DOI: https://doi.org/10.1145/129712.129782.
[Mic94] Silvio Micali. Computationally Sound Proofs (extended abstracts). In 35th FOCS, pages 436–453. IEEE ComputerSociety Press, November 1994.
[PHGR13] Bryan Parno, Jon Howell, Craig Gentry, and Mariana Raykova. "Pinocchio: Nearly Practical Verifiable Computation." In: Cryptology ePrint Archive, Report 2013/279 (2013).
[Sha92] Adi Shamir. "IP = PSPACE." In: Journal of the ACM 39, 4 (October 1992), pp. 869–877. DOI: https://doi.org/10.1145/146585.146609.
[SMR85] Shafi Goldwasser, Silvio Micali, and Charles Rackoff. "The Knowledge Complexity of Interactive Proof-systems." In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing (STOC '85). Association for Computing Machinery, New York, NY, USA, 1985, pp. 291–304. DOI: https://doi.org/10.1145/22145.22178.
