An Introduction to Verifiable Computation

# An Introduction to Verifiable Computation ### *[Part 1] What is verifiable computation?* ### *[Part 2] Why should you care about verifiable computation?* ### *[Part 3] What is a SNARK?* ### *[Part 4] Conceptual building blocks for SNARKs* ### *[Part 5] Building verifiable applications* --- *This is intended as introductory material, and aims for accessibility and conceptual intuition over precision and rigor.* *For a more precise approach, we recommend [Proofs, Arguments, and Zero-Knowledge] and the [SNARGs Book]. For something in between, we recommend the [ZK Whiteboard Sessions] and the [ZK MOOC].* [Part 1]: #Part-1-What-is-Verifiable-Computation [Part 2]: #Part-2-Why-should-you-care-about-verifiable-computation7 [Part 3]: #Part-3-What-is-a-SNARK12 [Part 4]: #Part-4-Conceptual-Building-Blocks-for-SNARKs [Part 5]: #Part-5-Building-verifiable-applications19 --- ## Part 1. What is Verifiable Computation? Verifiable computation refers to the ability to **offload some computational task to a third party, while maintaining verifiability of the results.** In some sense, all computation is verifiable: anyone can simply re-run the original computation to check the results. But recent advances in computer science have shown that it’s possible to verify a computation using less resources than it took to run the original computation. This is called **succinct** verifiable computation. A pivotal moment for succinct verifiable computation came in 1992, with the proof of the [PCP Theorem](https://en.wikipedia.org/wiki/PCP_theorem). The PCP Theorem shows that any proof can be rewritten in such a way that can be checked without reading the entire proof. At first glance, it’s rather hard to believe that succinct verifiable computation is possible. How could one possibly verify the correctness of a computation without re-doing the computation? And indeed, there is a caveat. Succinct verifiable computation will always have some margin of error — some possibility that a faulty computation will pass verification. Fortunately, we can tune down this margin of error to be negligible. In 1992, this was a theoretical result that couldn’t really be applied in practice. But over the course of the next couple decades, the techniques for succinct verifiable computation have become more and more efficient. In 2013, the first application of succinct verifiable computation was deployed in the real world ([ZCash](https://z.cash/)). At that stage, building applications that leverage this technology was extremely difficult. Building verifiable applications was something that was accessible to cryptographers who were willing to write assembly code. Today, tools like the [RISC Zero zkVM](https://risczero.com) have made it possible for regular software developers to build verifiable applications and deploy them on the blockchain of their choice. The tooling has matured to the point that you can build and deploy an end-to-end prototype in a weekend, using your own laptop. And when you’re ready to go to production, you can outsource the computation to [Bonsai](https://bonsai.xyz), the proving service for RISC Zero’s zkVM. And as icing on the cake, there’s a ready-to-use verifier, already deployed on a number of leading blockchains. To sum up: the era of verifiable computation has arrived. It’s fast, affordable, and the software development experience is ergonomic. After 2+ years since our initial 0.1 release, [zkVM 1.0] has arrived, complete with end-to-end tooling for building and deploying verifiable applications. You’re probably thinking — OK, but why should I care? Keep reading to find out. ## Part 2: Why should you care about verifiable computation? ### Delegating computation makes the world go 'round. In traditional web applications, most of the computational work is delegated to Amazon Web Services. In hardware, computation gets delegated to GPUs, FPGAs, and ASICs. For blockchains and blockchain applications, verifiable computation is a pre-requisite for delegating computation. When talking about delegating computation in any of these contexts, we can say that we offload work from the main **processor** to a **coprocessor**. ### The Coprocessor Model for Blockchains Let’s dig in a bit deeper to the idea of coprocessors for blockchains. Recall that a blockchain [is a computer][ethereum], and a smart contract [is a computer program][smart-contract]. Generally, a blockchain is a very slow, very expensive computer, which imposes severe limits in what's possible using smart contracts. Enter: Verifiable computation. ### Coprocessors for Blockchain Applications Verifiable computation offers a mechanism for offloading computation from the blockchain to another computation environment, which simultaneouosly reduces costs and increases capabilities for blockchain applications. In an on-chain game, the complex game logic can be moved off-chain. In an identity application, the signature verification can be moved off-chain. The list goes on. The list above highlights the basic idea of a coprocessor in the context of blockchain applications: an application developer delegates their app logic to some verifiable, off-chain computational environment, in order to scale their application without impacting their on-chain footprint. This not only enables applications to scale, it *fundamentally changes what's possible on-chain*. Previously, on-chain applications were subject to limits on data sizes and computational intensity. Delegating computation enables blockchain applications to trascend these limitations entirely. ### Coprocessors for Blockchains (aka Rollups/Validiums) Beyond the benefits at the application level, the same techniques can be used to offload the computational work *of the blockchain itself*. Read about "[ZK rollups]" or "[validiums]" to learn more. <iframe width="560" height="315" src="https://www.youtube.com/embed/Cl2L2dklLbk?si=FTYwfr7ip1NILo74" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe> ## Part 3: What is a SNARK? In practical applications of verifiable computation, **SNARKs** are generally the tool-of-choice: *Succinct, Non-interactive ARguments of knowledge*. Let’s unpack some of the terminology, and then discuss some of the engineering tradeoffs in designing SNARK protocols. We’ve already [touched on][Part 1] the term **succinct** — this refers to the property that verification is more efficient than the original computation. **Non-interactive** means that the “Prover” and the “Verifier” don’t need to interact in real time. One party can generate a SNARK that “proves” the output of some computation, and another party can verify that SNARK, with no direct communication required, aside for sharing the SNARK itself. Argument of knowledge roughly translates to “proof of computation. For more precise definitions, check out [Proofs, Arguments, and Zero-Knowledge] or the [SNARGs Book]. So, we can summarize: 1. The Prover runs the computation — and does some extra work to create a SNARK. 2. The Prover sends the SNARK to the Verifier (or posts the SNARK somewhere public). 3. The Verifier checks the validity of the SNARK. And amazingly, the Verifier can check the validity of the SNARK in milliseconds — *regardless of the complexity of the original computation!* ### Tradeoffs in SNARK design When designing SNARK protocols, there are a number of competing costs that one aims to minimize: - Prover complexity: the work required to generate a SNARK - Verifier complexity: the work required to verify a SNARK - Size: the size of the SNARK In the context of blockchain applications, the Verifier is a smart contract living on-chain, which means that we need the SNARK to be small and the verification algorithm to be lightweight. The Prover is the computationally intense component here. Depending on the application, the Prover might be running on a mobile device, a laptop, a supercomputer, or a hardware cluster. Systems like RISC Zero, ZK Sync, and Polygon zkEVM rely on a multi-layer proof system in order to get the best of all worlds. At RISC Zero, most layers of the proof system utilize a hash-based SNARK, which offers fast proving, and a SNARK size of roughly 200 kB. The last step uses an elliptic-curve-based SNARK, which is slower but offers a SNARK size on the order of 100 bytes. These tiny SNARKs are small enough to post & verify on-chain, enabling blockchain applications to utilize SNARKs as a replacement for expensive on-chain computation. ## Part 4: Conceptual Building Blocks for SNARKs In this part, we present a framework for building SNARKs, in terms of four components: - An arithmetization scheme, - An interactive oracle protocol, and - A polynomial commitment scheme. > *Note that you can utilize verifiable computation in your applications without understanding anything in this section. If you're more interested in building than theory, you can skip to [Part 5].* ### Arithmetization Arithmetization is the process of translating a statement like, “A known algorithm was run for 10000 steps, and the final output was 0” into a more formal language that’s conducive to SNARK protocols. The “[language]” is defined in terms of instances and witnesses. Given some computation, the **witness** is an encoding of the execution trace — i.e., a complete record of the state of the machine at each step of the computation. And the **instance** is an encoding of the rules that define the correctness of the computation. So, checking that the witness satisfies the the constraints is logically equivalent to checking the correctness of the computation. Circling back to the statement we started with… > A known algorithm was run for 10000 steps, and the final output was 0. Once we choose an arithmetization scheme, we can translate the computational algorithm, the number of steps, and the asserted output into an *instance*. And if the Prover has actually run the algorithm as asserted, they will have a *witness* that satisfies the instance. Common arithmetization schemes include R1CS, Plonkish, and AIR. Now, the Prover need a technique to prove that the witness satisfies the instance. Enter: Interactive Oracle Proofs.   ### Interactive Oracle Proofs [Interactive oracle proofs] (IOP) are a technique for proving that a witness satisfies an instance. In a (polynomial) IOP protocol, a Prover and Verifier exchange a number of messages, where each message from the Prover is in the form of a “polynomial oracle” (which the Verify can "query") and each message from the Verifier is drawn from a “random oracle.” As the names suggest, polynomial oracles and random oracles are idealized abstractions. In real SNARK constructions, polynomial commitment schemes are used in place of polynomial oracles and hash functions are used in place of random oracles. IOPs are useful because they provide a clean mathematical framework for analyzing properties like completeness, soundness, and zero-knowledge, which we’ll discuss later on. ### Polynomial Commitment Schemes As mentioned in the previous section, Interactive Oracle Proofs include two tools that don't exist in the real world: random oracles and polynomial oracles. To bring the math to the real world, we replace the random oracle with a cryptographic hash function, and we replace the polynomial oracle with a [polynomial commitment scheme]. <iframe width="560" height="315" src="https://www.youtube.com/embed/pTAj9QFGrog?si=sXthOvi_UB21wkXY" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe> ### A Recipe for Building SNARKs So, now we can give a high-level view for how we build SNARKs in the [random oracle model]. 1. We start with an assertion about a computation. 1. We *[arithmetize](#Arithmetization)* that assertion, translating it into an assertion that some *witness* satisfies the *instance*. 1. We choose an [IOP protocol](#Interactive-Oracle-Proofs) to prove that the witness does in fact satisfy the instance. 1. We replace the random oracle in the IOP with a concrete hash function in order to construct a non-interactive oracle proof (see [Fiat-Shamir Heuristic]). 1. We replace the polynomial oracle in the IOP with a [polynomial commitment scheme](#Polynomial-Commitment-Schemes) in order to construct a SNARK (see BCS Transformation). ## Part 5: Building verifiable applications Fortunately, tooling for verifiable computing has evolved to a point where developers don't need to work directly with concepts like arithmetization or IOPs. Today, developers can write applications in a high-level language like Rust, and then generate SNARKs by running their applications inside a "zkVM" (zero-knowledge virtual machine). To get started, check out the [RISC Zero developer docs] or head straight to the [Foundry Template]. <iframe width="560" height="315" src="https://www.youtube.com/embed/Z4JNXiIs-E0?si=eJi5Ylx2wnNSWvGC" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe> ## Questions or Suggestions? Find me in the [RISC Zero Discord]. [ethereum]: https://www.abra.com/resources/worlds-computer/ [Foundry Template]: https://github.com/risc0/risc0-foundry-template [Interactive Oracle Proofs]: https://nmohnblatt.github.io/zk-jargon-decoder/definitions/polynomial_interactive_oracle_proof.html [language]: https://nmohnblatt.github.io/zk-jargon-decoder/intro_to_zk/what_is_proving.html [smart-contract]: https://ethereum.org/en/smart-contracts/ [Fiat-Shamir Heuristic]: https://blog.trailofbits.com/2021/02/19/serving-up-zero-knowledge-proofs/ [polynomial commitment scheme]: https://nmohnblatt.github.io/zk-jargon-decoder/definitions/polynomial_commitment.html [Proofs, Arguments, and Zero-Knowledge]: https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf [random oracle model]: https://nmohnblatt.github.io/zk-jargon-decoder/definitions/random_oracle.html [RISC Zero developer docs]: https://dev.risczero.com [RISC Zero Discord]: https://discord.gg/risczero [SNARGs Book]: https://snargs-book.org [validiums]: https://ethereum.org/en/developers/docs/scaling/validium/ [zkVM 1.0]: https://www.risczero.com/blog/hello-zkvm-1-0 [ZK rollups]: https://ethereum.org/en/developers/docs/scaling/zk-rollups/ [ZK Whiteboard sessions]: https://zkhack.dev/whiteboard/ [ZK MOOC]: https://zk-learning.org/