zkVM 1,074 words

The Journey Toward Aleo’s Universal ZKVM

How Aleo moved from a circuit-per-program model toward a universal zkVM.

0. Background

Aleo is a Layer-1 blockchain focused on enabling privacy-preserving, scalable decentralized applications using zero-knowledge proofs (ZKP). Since 2019, Aleo has been building a customized ZKVM solution with a unique programming language, Leo, powered by the Aleo Virtual Machine (AVM). Its consensus leverages Proof-of-Work to promote decentralization. In its early testnet, Aleo combined POW with zero-knowledge proofs to construct a puzzle for miners. In its mainnet, it encourages acceleration of trace generation for Leo instructions.

Recently, Aleo published a proposal titled ARC-0043: Extending the Puzzle to a Full SNARK. This proposal aims to have miners generate useful SNARK proofs while reducing the burden on validators to verify the puzzle.

Let’s dive into more detail.

1. Architecture of Aleo

As shown in the picture below, there are two types of provers in the solution:

  1. AVM prover. It uses the Varuna proving system, based on AHP R1CS and univariate sumcheck protocol (the “Third Party Prover” part in the left side of the picture).
  2. POW prover. It uses a POW mechanism to incentivize provers to compute a puzzle (the “ Prover” part in the right side of the picture).
Figure 1. Aleo core architecture, from link: https://developer.aleo.org/concepts/network/overview/core_architecture/

These two provers are currently distinct.

  • The AVM prover is used on the user side to generate a zkSNARK proof, ensuring user and application privacy.
  • The POW prover in the existing mainnet stage doesn’t generate a useful SNARK or zkSNARK proof. Instead, it performs computations involving circuit generation for a set of instructions and some Merkle tree hash computations. As a form of POW, randomness is included to have miners demonstrate proof of work.

2. History of Aleo’s POW prover

Here’s a picture illustrating how Aleo has incentivized provers throughout its history.

Figure 2. Aleo incentive program, from link: https://aleo.org/post/community-road-to-mainnet/

At each stage, Aleo has been constructing various algorithmic challenges for POW provers to accelerate, including KZG (Testnet 3) and synthesis (Current Mainnet) operations. Aleo also hosts multiple rounds of ZPrize to reward the community for accelerating ZK proving.

As described in the ARC-0043 proposal, it’s time for POW provers to generate a full SNARK.

3. The journey toward universal ZKVM

In the ARC-0043 proposal, Aleo plans to use POW provers to generate SNARK proofs, which are then verified by validators. This approach could eliminate the performance bottleneck in validator verification, as SNARK verification is considerably faster.

If this becomes reality, the community’s POW provers will have the capacity to generate useful SNARK proofs. Note that these don’t necessarily have to be zkSNARK proofs, but SNARK proofs. This development could make Aleo the first project to leverage both major uses of zero-knowledge proofs: privacy preservation (via AVM prover) and computation scaling (via POW prover).

What’s next? Universal AVM prover.

As mentioned by Aleo in a previous article, “Aleo’s innovative approach allows users to outsource proof generation to third-party proving services equipped with advanced computational resources” It would be advantageous if POW prover machines could run the AVM prover, helping users generate ZK proofs or outsource the proving work. This means the AVM prover and the POW prover can be unified at the machine level, creating a universal AVM prover. This development would provide Aleo’s application side or user side with low-cost, high-performance ZKP proving, further advancing the Aleo project and realizing the vision to “build cryptographically secure dApps at scale”.

Get Computation Frontier’s stories in your inbox

Join Medium for free to get updates from this writer.Subscribe

Further potential? Universal ZKVM prover.

As Aleo potentially gains a dominant position with thousands of miners generating AVM ZK proofs at lightning-fast speeds, could it evolve to support various ZKVM proof generations? This evolution could lead to a universal ZKVM prover — not just for Aleo itself, but for other ZKP projects as well. Such a prover could encompass both privacy preservation and computation scaling use cases.

It will be challenging for Aleo to upgrade its algorithms to support different instruction sets and backends. Additionally, continuation technology and proof recursion technology may need to be added. However, if successful, Aleo will create immense value for the mass adoption of zero-knowledge proof technology.

First, by supporting various frontends — not just Leo — the developers’ user experience will improve significantly.

Second, a universal ZKVM prover can benefit the entire ZKP community by providing common ZKP computational power for all ZKP projects.

Moreover, developing an ASIC ZKP machine is costly. A universal ZKVM prover can save substantial development expenses.

At the hardware level, we can consider designing a system compatible with various ZKVM protocols. Alternatively, the hardware could support or be upgraded with minimal changes to accommodate new ZKVMs. It’s worth noting that not only Aleo but other ZKVM projects also have the potential to build such universal platforms.

Regardless, the first step will be to realize ARC-0043. Now, let’s delve into more details about AVM.

4. Introduction to Aleo’s Varuna-based AVM

The zkSNARK proof system in Aleo is Varuna, primarily based on AHP (Algebraic Holographic Proofs) and PCS (Polynomial Commitment Scheme), as shown in the following diagram:

Figure 3. Varuna architecture.

The time-consuming parts are mainly NTT, MSM, and Synthesis, which have already achieved good hardware acceleration (such as ASIC, GPU, etc.). The purpose of Aleo ARC-0043 is to transform the Puzzle in the diagram into a SNARK system, significantly reducing the validation time for validators and thereby increasing block generation speed.

To turn the Puzzle into a SNARK, it’s estimated that the POW Prover would need to perform both synthesis operations and SNARK proof generation. Therefore, the Puzzle prover would need to:

  1. Support more Aleo instruction types;
  2. Implement AHP and PCS to generate SNARK proofs;
  3. Implement modules such as NTT and MSM, simplified from algorithms in the AVM prover.

5. Comparisons of ZKVMs

Aleo’s AVM was introduced several years ago and has now reached mainnet. Since then, other new ZKVMs have emerged. Let’s compare Varuna with some other ZKVMs:

Table 1. Comparison of some ZKVMs.

Through this comparison, we can see that Aleo’s Varuna has reached production and mainnet, though it doesn’t use a more general ISA and hasn’t yet supported recursion technology.

It’s possible that Aleo will continue to upgrade to further promote the mass adoption of zero-knowledge proof technology.

6. Summary

We’ve analyzed the history of Aleo provers and its latest ARC-0043, and compared Aleo’s Varuna-based AVM with other ZKVMs. We observe that Aleo is on track to become a platform with abundant, high-performance, and decentralized ZKP provers.