zk-VM

How do you prove, succinctly and in zero knowledge, that a certain program was executed on a certain input and it had a certain result? This is a question that motivates zero knowledge virtual machines (zk-VMs). A zk-VM provides a program execution environment which allows for program executions to be verified succinctly and in zero knowledge. Succinct and zero-knowledge proofs combine both of these sometimes-desirable properties: succinctness and zero-knowledge. “Succinctness” means basically that the proofs are not too long. “Zero-knowledge” means basically that the proofs contain no useful information beyond the facts that they are proving. Succinct proofs are of interest for applications where someone (a person or a system) needs to know something without having all of the information required to verify that fact constructively (i.e., by directly checking the conditions for it to be true). This can happen because sometimes all of the information required for a constructive proof is too much to store or transmit in a cost-effective way. In these cases, indirect verification using a succinct proof may be preferable. Zero knowledge proofs are of interest for applications where someone (a person or a system) needs to prove something without revealing all of the information required to verify that fact constructively. This can happen because there are secrets in the world, such as cryptographic secrets used to secure cryptographic protocols. One of the sometimes-undesirable properties of succinct and zero-knowledge proofs of program execution is that there is sometimes a relatively steep cost of creating them. Highly computationally complex cryptography used in succinct and zero-knowledge proving protocols sometimes leads to a lack of scalability in systems built on them. Given increased interest in using systems built upon these protocols, there is a significant market opportunity in providing efficient, scalable production of succinct and zero knowledge proofs of program execution.

Lita aims to provide leading edge tooling and systems for succinct and zero knowledge proving. We aim to set the bar in terms of efficiency, speed, and verifiability of our work. Our strategy for doing this includes the following aspects.

• Choose and build a base proving system out of the research literature which optimizes for the time, space, and energy complexity of proving, while also keeping the proofs reasonably succinct.

• Use that base proving system to create proofs of program execution. This is a general enough application to encompass all of the applications of succinct and zero knowledge proofs.

• Create proofs of program execution using a zero knowledge virtual machine (zk-VM) which has a zk-friendly instruction set architecture (ISA). A zk-friendly ISA is one which is especially amenable to efficient zero knowledge proving of executions of programs compiled to run on that ISA. Usually a zk-friendly ISA is one which has been designed specifically for use in the creation of a zk-VM.

• Create a compiler toolchain which lets application developers compile popular source languages to the zk-friendly ISA.

• Create a hardware accelerated zk-VM prover using leading edge parallel computing technology.

• Deploy a proving service which allows users to outsource the computation of proofs to us and our partners.

• Build a web-based integrated development environment (IDE) which allows application developers to quickly and easily spin up projects which make use of proofs of execution of parts of their application code.

• Use formal verification to validate the correctness of key pieces of proving system logic, such as the verifier, the STARK constraint system, and the VM execution engine.