VERI-ZEXE: Decentralized Private Computation with Universal Setup

By: Alex Xiong

TL;DR: As part of our effort in exploring private smart contract solutions, we developed a decentralized private computation (DPC) system, VERI-ZEXE, that supports universal setup. VERI-ZEXE improves the state-of-the-art [1] by ~9.0x on transaction generation and ~2.6x on memory usage, and will be used in future versions of CAPE to enable arbitrary user-defined asset policies while maintaining configurable asset privacy.

See ePrint paper here and GitHub here.

ZEXE: background and limitations

Smart contract systems such as Ethereum and Solana are great breeding grounds for web3 innovations. However, they suffer from lack of privacy or scalability, and sometimes both. To ensure public verifiability, all program states and state transitions are public and transparent, sacrificing privacy, and all transactions or computation are re-executed by all (full) nodes, affecting scalability.

In 2019, Bowe et al. proposed a scheme called decentralized private computation (DPC) that allows users to execute arbitrary computation off-chain and submit a transaction attesting to the correctness of this computation using zero-knowledge proofs [2]. They implemented a system named ZEXE (zk-execution) that instantiates the DPC scheme to tackle both pain points above. Roughly, ZEXE is a “programmable Zcash”, generalizing from a single-application system to a smart contract system while preserving the privacy guarantees.

Some noteworthy features of ZEXE are:

• Data & function privacy: ZEXE hides all program states as well as inputs/outputs to function calls (data privacy) and, importantly, which functions/programs are invoked in each transaction (function privacy). Even with numerous follow-up alternative approaches to private smart contracts, ZEXE remains the only concrete construction that achieves function privacy (see related work section in the paper).
• Programmability: With ZEXE, users can attach arbitrary policies/predicates to a record (similar to the idea of Bitcoin Script) which specify the transition rules for relevant program states. Bowe et al. have shown how to program user-defined assets, DEXes, and regulation-compliant stablecoins under the ZEXE model.
• Succinct verification: On-chain validators don’t need to re-execute the computation. Instead, they verify the short transaction validity proofs, which takes constant time regardless of how expensive the off-chain computation is.

The existing implementations (SnarkVM testnet 1 and SnarkVM testnet 2) deliver on the features described above but have drawbacks that limit their practicality and leave much room for improvement:[3]:

• Circuit-specific setup: ZEXE (SnarkVM testnet1) use non-universal SNARKs like GM17 and Groth16 for certifying the correctness of smart contract executions, leading to a trusted setup for each application/program, which is highly impractical.
• Performance: ZEXE with universal SNARK (SnarkVM testnet2) suffers a significant performance deterioration due to the higher complexity of the universal SNARK verification logic and the fact that ZEXE requires producing a SNARK proof for a statement that encodes the SNARK verification logic.

VERI-ZEXE: universal setup without performance loss

VERI-ZEXE addresses the two foregoing challenges, while preserving all features and properties of the original ZEXE, by introducing many optimizations on reducing the circuit complexity of the universal SNARK verifier gadget. We refer readers to the VERI-ZEXE paper for detailed descriptions of these techniques; in this post we only showcase and interpret our benchmark results.

Firstly, we compare ourselves against the state-of-the-art ZEXE implementations, among which the most important metrics include the transaction generation time (i.e. Execute algorithm), the memory usage, and transaction validity proof size. As shown below, our performance is on-par with the original non-universal ZEXE. Compared to the best universal ZEXE implementation, we attain a ~9.0x improvement on transaction generation and a ~2.6x improvement on memory usage.

Comparison of three DPC implementations for 2-input-2-output transaction, run on AMD EPYC 7R13 at 2.65 GHz with 64 cores and 128 GB of RAM.

Secondly, we provide a more elaborate comparison against SnarkVM testnet2. As shown below, our outer circuit (used during depth-2 proof composition) size is much smaller, and thus prover time is an order of magnitude faster, which leads to much faster proof generation across all transaction dimensions:

Finally, to illustrate our innovation in TurboPlonk and UltraPlonk constraint system design, and our optimization techniques, we provide a breakdown of constraint cost for cryptographic building blocks used in VERI-ZEXE. We shared these highlights on gadget complexity when we introduced our Jellyfish library earlier this year.

Number of PLONK constraints for major cryptographic building blocks and algebraic operations. These numbers are specific to the TurboPlonk design.

VERI-ZEXE + CAPE: customizable asset policy

While ZEXE is not a silver bullet as a private smart contract design (due to more problems mentioned in [3]), it is a great solution for applications with minimal shared states among users that would enjoy high parallelism and low transaction-dependency under the UTXO model. The CAPE product is a great example of how this might look to users.

Currently our CAPE protocol only supports a predefined set of asset policies (e.g., enabling minting, anonymous transfers, freezing keys, designated viewing policies etc.), but not dynamic, user-defined asset policies. Imagine you want to create a new “concert token” that has a total supply of 1000 units and can only be minted if a specific asset was paid to a designated address. This new minting policy associated with our new concert token goes beyond what the current CAPE product can enforce. It’s a common requirement and desirable feature for asset issuers to be able to design customized, more complicated policies for their future assets. VERI-ZEXE will make such programmability possible.

“VERI-ZEXE can serve as a substrate for private smart contracts. Compared to prior work, it supports a universal setup and a ~9x speed up on transaction generation as well as ~2.6x saving on memory usage, pushing applications like private stablecoins with arbitrary, customizable asset policies within the realm of practicality,” says Alex Xiong, first author.

Binyi Chen, Chief Cryptographer for Espresso Systems added: “The techniques underlying VERI-ZEXE are not limited to enabling privacy, but also help with scalability. For example, the same techniques can be used to optimize the performance of so-called zk-zk-rollup, where rollup is applied to zero-knowledge (private) transaction formats such as CAP or Zcash.”

We will release more about our designs for advancing CAPE in future posts, and are extremely excited about what these groundbreaking innovations will bring to Espresso. Stay tuned!

Footnotes

[1]: SnarkVM by Aleo has many iterations: their testnet1 version is a reasonably faithful realization of ZEXE described by the S&P19 paper which requires application-specific trusted setups; early version of testnet2 swaps the proof system used to generate proofs for birth/death predicates from GM17 to Marlin, making the system “universal”; later version of testnet2 and future testnet versions shift away from the original DPC model, by simplifying the model but restricting its programmability (e.g. disallowing inter-program call). The new, simplified yet restricted DPC model since testnet3 is outside the scope of this blog and our code is measuring against testnet1 and earlier version of testnet2. We’ve made extra modifications to their code to make fair comparison during benchmark, see more details in Section 4.2 of the paper.

[2]: The general flow of computing off-chain and verifying computation integrity proof on-chain may sound similar to zk-rollup. Users in ZEXE generate the transaction validity proof and send transactions directly on chain whereas users in zk-Rollup send transaction to rollup validators who will then generate the zk proof to be sent on chain. Technically ZEXE doesn’t care how the off-chain computation is done, either by a single user, or a multi-user MPC protocol, or in a rollup-server fashion, therefore we deem the two approaches complementary.

[3]: There are many other challenges with ZEXE including concurrency issue (when multiple users trying to transition a shared state to a new state simultaneously), atomic composability capability (achieving Flashloan-like application in ZEXE would require a technique we call “in-bundle accumulation” which slightly modify record nano-kernel (RNK) of ZEXE), difficulty of predicate programming in UTXO model (existing solution such as Chialisp). We will try to introduce our approaches to some of these problems in future blog posts.