Overview
Proof of Proof is a universal verifiable computing framework that works for all programming languages, virtual machines, and instruction set architectures (ISA), and is compatible with any zero-knowledge (ZK) backends and zero-knowledge virtual machines (zkVMs).
Verifiable computing and zkVMs
Verifiable computing is the technology that allows a computing party to produce verifiable computing results, which usually consist of the original result together with a certificate that shows that the result is indeed correct.
There's a verification algorithm that anyone can use to verify a certificate. If the verification is successful, then it is convinced, either absolutely or with very high probability, that the results are also correct.
Verifiable computing is critical for securely outsourcing and delegating complex computational tasks to untrusted, remote computing services. It significantly reduces the size of the trust base of a computational task from a more powerful computing party to a more computationally economic verification party.
zkVMs are a typical approach to verifiable computing systems. To use a zkVM to produce verifiable results of computational task, you will need to implement a zkVM system in a higher-level programming language (such as Rust), which will then be compiled into a lower-level representation (such as RISC-V).
The zkVM's ZK circuit process the execution traces of the zkVM to generate the final verifiable certificates known as zero-knowledge proofs (ZKPs).
However, the zkVM approach has the following three limitations:
It relies on a long and complicated compilation chain from the higher-level languages to ZK circuits that causes significant performance overhead.
It only works on programs written in a handful of higher-level programming language(s) from which a compilation chain does exist to the lower-level representation supported by the ZK circuits of the zkVM.
It has a large trust base that consists of the long compilation chain from high-level languages to ZK circuits as well as the implementation of the ZK circuits themselves.
Proof of Proof
Proof of Proof is an innovative framework to verifiable computing that complements the zkVM approach by addressing the above-mentioned limitations using the formal semantics of programming languages.
It provides a clean separation of concerns across three core pillars:
Proof of Proof starts with three pieces of information: a programming language, a program written in that language, and an input for the program. Together, these define the computational task that needs to be verified.
Then, it does the following three steps in sequence:
Run the program using formal semantics
Proof of Proof uses the K framework to execute the program with the input. It relies directly on the formal semantics of the programming language to get the result of the computation.
Generate a mathematical proof
During execution, K produces logs called a "math proof hint." This hint is used to generate a full mathematical proof showing that the program was executed correctly. The proof is based entirely on the language’s formal semantics and can be checked by a simple program called a math proof checker.
Produce a ZK proof as a verifiable certificate
The act of checking the math proof is then turned into a zero-knowledge (ZK) proof. This ZK proof acts as the final verifiable certificate and can be generated by any zkVM, or by the Pi Squared Block Checker. Like earlier steps, this process also uses the language’s formal semantics.
Therefore, Proof of Proof is a universal framework for verifiable computing because it is based directly on the formal semantics of programming languages. As a result of that, Proof of Proof has the following advantages:
Proof of Proof works for all programming languages, virtual machines, or instruction set architectures, by taking their formal semantics as direct input and avoiding the long and complicated compilation chain from higher-level languages to lower-level representations.
Proof of Proof postpones the expensive ZK process by generating math proofs first, which keeps the nice mathematical abstractions and structures of the original computing tasks that would have been lost in compilation, and thus enables new and significant semantics and mathematics-level optimizations.
Proof of Proof yields a much smaller trust base that mainly consists of the math proof checker(s) and the various formal semantics of programming languages, virtual machines, and instruction set architectures.
Why we call it “Proof of Proof”
Proof of Proof gets its name from how it works: (ZK) proof of (math) proof.
Last updated
Was this helpful?
