I’ve been asked to write a specification of a proposal to scale MASP-on-EVM. But since I’ll be on vacation for the next week, I thought it would make more sense to write about what I have been researching to scale MASP-on-EVM.
The current MASP-on-EVM architecture embeds the new Merkle root that the contract should have inside transactions themselves. This is done because Merkle root computations using the Pedersen hash are expensive to do on chain. However this means that if multiple transactions are constructed and submitted simultaneously by different users without prior coordination, only one transaction will be accepted. We can introduce relayers/sequencers, but this introduces the challenge of quickly sequencing, proving root updates, and submitting transactions whilst preventing the batch from being invalidated by events occurring on-chain. These challenges can be addressed, but I suspect that the solutions may introduce complexity.
Therefore my major interest has been investigating ways to remove the new Merkle tree root from transactions. I propose two possible approaches: split-batching and Poseidon hashing.
Approach 1: Split Batching
The split batching approach is implemented in https://github.com/heliaxdev/split-batcher/tree/master . The basic idea is to separate user transaction validation and execution from Merkle tree updates. (This technique is written about here: An Incomplete Guide to Rollups .) In our context, this would mean:
- Clients produce ordinary MASP transactions and submit them to the smart contract
- The smart contract validates the transaction (ZK proofs, nullifier, signatures) and immediately effects ERC20 transfers if necessary. However, notes are added to a (ordered) queue instead of being placed directly in the Merkle tree
- Periodically provers download the note queue from the smart contract, compute the Merkle root that arises from placing those notes into the Merkle tree, and submit the new root along with a proof that it was done correctly
- The smart contract validates the append proof, updates the Merkel root accordingly, and empties the queue (by just updating an offset)
In this approach, many users can successfully submit their transactions simultaneously. No race conditions occur for users because their transactions immediately go to chain instead of being batched somewhere off-chain. This technique is not optimistic: once a transaction passes validation, it is executed and cannot be reverted.
Provers, on the other hand, may or may not have race conditions depending on who we choose to allow to send append proofs to the smart contract. Allowing everyone to submit append proofs works and is called total anarchy: it’s perfectly decentralized but results in many wasted proofs. The opposite approach is centralization where only one Ethereum address is allowed to submit Append proofs. See a discussion at: An Incomplete Guide to Rollups .
This work was also an attempt to explore alternative architectures to the Plasma architecture, which is what has been used in previous projects.
Approach 2: Poseidon Hashing
The main reason why we do not compute new Merkle roots on chain is due to prohibitive gas costs. My theoretical computations suggest that single Pedersen hash uses about 350k gas. The pedersen-solidity-benchmark suggest similar numbers. Therefore I investigated whether we can replace the Pedersen hash in the MASP circuit with a hash function that’s both gas friendly and ZK friendly.
A Poseidon-based spend circuit is implemented in Murisi/poseidon 0.6.0 by murisi · Pull Request #1 · anoma/sapling-crypto · GitHub . Some implementation details:
- The MASP circuits are written using the Bellman library in Rust. Therefore to minimize integration costs, a Poseidon hash implementation written Bellman/Rust was sought
- Amongst the libraries reviewed, the Neptune implementation at GitHub - lurk-lab/neptune: Rust Poseidon implementation (contact: @porcuquine) · GitHub seemed most suitable. It is audited and uses Bellpepper (a fork of Bellman).
- The main challenge in integration was writing adapters to make certain Bellpepper types work with Bellman. Once this one, the Pedersen hash call in the Spend circuit was simply replaced with a Poseidon hash call
- The most significant surprise in carrying out this work was that the number of constraints in the spend circuit significantly went down: the Pedersen-based Spend circuit uses 98777 constraints while the Poseidon-based Spend circuit uses 63129 constraints.
Benchmarks that measure the gas used to insert leaves into Poseidon-based Merkle trees can be found at: Gas and circuit constraint benchmarks of binary and quinary incremental Merkle trees using the Poseidon hash function - zk-s[nt]arks - Ethereum Research . According to the report 770k gas is used to insert a leaf into a tree of depth 20, and 1.2m gas for depth 30. Note that we can modify the Merkle tree height assumed by the Spend circuit if we so desire. Also note that inserting 2 or 3 leaves does not cost much more than for 1 leaf.
Additionally, Poseidon hashes can complement other approaches for scaling MASP-on-EVM. This is due to the fact that lower constraint counts lead to lower proving times. So, loosely speaking, 5x less constraints could the possibility 5x larger batches without an increase in proving time.
Summary
Two proposals have been presented for scaling MASP-on-EVM. One is on-chain and the other is off-chain, though techniques from both can be combined. Both these approaches do not require relayers/sequencers and therefore may be easier to build and audit (especially when the masp_primitives and masp_proofs crates are extensively reused) and are likely more decentralized and permissionless.