ZK-CSPR: Scaling Casper (V0.1)
This design document describes the implementation of a zero-knowledge rollup system intended to increase the throughput of native Casper transactions. It aims to scale the network by submitting proofs of computation for batches of transactions processed externally.
“Transaction” refers to either a “Deposit”, “Transfer” or “Withdrawal”.
Transactions and Deposits
Deposits are events recorded on the Casper blockchain, while Transfers and Withdrawals must be routed through the external rollup service.
To submit a Transfer or Withdrawal to the rollup system, the user will send a POST request to its REST API. A deposit smart contract records events that are queried by the rollup service and inserted into the rollup service’s database with a “processed=false” flag. Newly recorded transactions are also initially flagged as “processed=false.”
Managing Balances
Balances are calculated from transactions stored in the rollup service’s database at runtime. This approach may be reconsidered in future releases. One possibility is to add an additional table that stores balances. If a transaction is deemed invalid, it will be rejected before making its way into the rollup service’s database. Additional security is provided by the rollup circuit, which will be described later in this document.
Transaction Batching
For every Era (a period defined by n seconds), all transactions flagged as “processed=false” are retrieved from the rollup service’s database and included in a “Batch”. The Batch is a struct that implements a “Hashable” trait.
Delta Merkle Tree
The Delta Merkle Tree, a type of Merkle Tree represented by a snapshot of the leaves affected by an insert operation, used in this rollup implementation, was inspired by Tornado Cash’s Merkle Tree and has been modified to include functionality for verifying Merkle paths. The Delta Merkle Tree has a fixed size and is initialized with a set of empty leaves. For every leaf inserted into the Merkle Tree, a new tree snapshot with a unique root is created.
Delta Merkle Tree is not a widely recognized term, but I personally like it since it describes the nature of this particular tree very well.
The implementation used for prototyping is open source and can be viewed here:
Withdrawals
Withdrawals are implemented in the Deposit Smart Contract, but the focus of version 0.1 is on Deposits and Transfers. In the future, a Withdrawal will be submitted to the REST API of the rollup service through a POST request. The rollup service will sign the transaction and submit a signed deploy to the Casper Blockchain. This aspect of the implementation is centralized, and native Casper withdrawals are currently not being considered due to increased synchronization complexity.
Risc0 circuit
Due to the Risc0 zero-knowledge virtual machine’s support for native Rust code, it presents an attractive option for prototyping zero-knowledge applications and services. Version 0.1 of the native Transaction Rollup service will implement the rollup circuit as a Risc0 guest program. Read more about Risc0 here.
The Risc0 circuit takes as public input the previous state of the Merkle Tree, which is retrieved from the Casper blockchain’s verifier smart contract. For every unique Batch of Transactions, a leaf H(Batch) is inserted into the Merkle Tree. Alongside the insertion, all signatures for all transfers in the set of transactions are verified, implying that the proof of computation generated will attest to their integrity.
The public output of the rollup circuit will be the resulting Merkle Tree snapshot from the insertion of the leaf. The updated tree snapshot, along with the Risc0 zero-knowledge proof, is submitted to the verifier smart contract. Once the Deploy has been successfully processed, the database entries for the transactions in the current batch will be updated from “processed=false” to “processed=true”.
Thanks to the native Rust support of Risc0, the circuit is rather succinct. The complexity lies mainly in the on-chain proof verification and Merkle tree operations:
The above code is still in the works and later the journal will include not just the resulting tree snapshot, but also the input snapshot which acts as a public input to the circuit in a broader sense.
Verifier Contract
The verifier smart contract is deployed on the Casper network and initializes the fixed-size Merkle Tree. In addition to verifying proofs generated by the Risc0 prover, it is responsible for storing all snapshots of the Delta Merkle Tree to enable client-side Merkle proof verification. A client must verify the integrity of all insertions in the Merkle Tree to trust a rollup service’s data availability API.
The data availability API is not yet part of version 0.1, but all requirements needed to build an API on top of this version have been implemented. For each Batch, the Client will query the snapshot at the given height/index h-1 and verify that inserting H(Batch) as a leaf in the tree will result in the root at index h.
The Client will calculate Balances from Transactions included in Batches that can be verified using the Merkle proof function.
Data Availability
Since Casper does not intend to operate a coin mixer, the data availability API (DA) of the rollup service will always store all transactions and, therefore, will not provide the same level of privacy as mixers like Tornado Cash.
The DA of this rollup service will enable reporting and transaction screening, as clients can query the full transaction history and verify Merkle paths for each batch of transactions, respectively.
Thoughts on Transaction Sequencing
Decentralized transaction sequencing requires an additional consensus layer. This practice is not common on other blockchains, and a code review of the frontier project “Espresso-Sequencer” has concluded that implementing a decentralized sequencing mechanism for the first iteration of a Casper rollup system is excessive. Therefore, the design described in this proposal is centralized, but all transaction data is verifiable.
Rollup version 0.1, as described in this document, launches a single rollup node that consists of a REST API and a synchronization service. As long as nodes establish consensus over sequencing, either by querying a centralized data source or through more complex implementations, a distributed solution built on top of version 0.1 is achievable.
V0.1 Limitations
Designing an efficient and production-ready zero-knowledge rollup is a complex undertaking that involves many different layers. One key component of such a system is the Merkle Tree or Trie used to represent the internal state. The prototype described in this design document is only capable of increasing the throughput of native Casper transactions and is to be extended with a more complex Merkle Trie to evolve into a comprehensive rollup capable of handling WebAssembly executions, thereby implementing the Casper Blockchain’s internal Trie.
Risc0 offers an outstanding developer experience and short write-time; however, it does not necessarily meet the requirements in terms of efficiency and performance. The heavy virtual machine that emulates a processor architecture comes at the cost of speed, potentially impacting the consensus mechanisms and validator workload balancing of the Casper Blockchain network.
Alternatives such as lighter VMs and proving systems like circom or noir offer performance improvements at the cost of write-time and developer experience. It is essential to continuously explore the landscape of proving systems and VMs to develop and maintain cutting-edge, production-ready scaling solutions.
V0.1 at the time of writing
Most components of this implementation are close to being complete. Everything from deposit events, transfer submission, batching, and proving is nearly ready for publication. Once the proof generation and basic REST API have been finalized, a verifier smart contract will be written, targeting a feature version 2.0 build of the Casper Node. Although the codebase is not fully open source at the moment, it is likely to be made available soon. Once public, a link to the repository will be added to this document.
