Optimistic Rollup Design in Ergo
Summary on the bottom
Upgrading scalability while maintaining functionality
Layer 2 Scaling solutions have long been touted as a solution to scalability problems, allowing for transactions to take place off-chain or to be "rolled-up" into a single larger transaction. This means that individual transactions will take less computation power, and the same safety guarantees of the Layer 1 network apply.
This post concerns Optimistic Rollups, a Layer 2 Solution which has two main points:
- Optimistic - Assumes all transactions are valid by default, and they need to be proven wrong
- Rollup - Batches together multiple transactions (refered to here as subTx) into a single, larger one (refered to here as mainTx)
An Optimistic Rollup in Ergo
Designing an Optimistic Rollup in Ergo has vast differences than an Optimistic Rollup in Ethereum, for better and worse. The environment is completely different, from the structure of tokens, with Ergo having native tokens, to the structure of transactions and data itself due to the eUtxo model vs the Account-based model, and the scripting language of ErgoScript vs Ethereum's Solidity.
Modifying and applying the structure of an Optimistic Rollup is not harder due to these changes, however. Key to the application of a rollup on Ergo, and any Layer 2 scaling solution on Ergo in general, is the AvlTree.
What is an AvlTree?
An AvlTree is a Binary Tree, able to efficiently hold a large number of Keys + Values. This type is also natively implemented in ErgoScript, allowing all ErgoScript contracts to utilize AvlTrees. In AvlTrees, getting values require having a Key + Proof of the action, calculated off-chain. Because the proof of an action is calculated off-chain, any actions interacting with an AvlTree on-chain can be optimized greatly, looking up only necessary values within a single transaction. Data storage within an AvlTree is also highly efficient, as not all of the data within an AvlTree needs to be accessed for any transaction.
The root hash of an AvlTree, its Digest, is an Array of 33 Bytes which holds the data for ALL data within the AvlTree. Through this digest, an AvlTree which holds hundreds of thousands of Bytes of data can be stored with only 33 Bytes.
Looking up values within an AvlTree is also highly effecient: the size of a proof grows logarithmically with the number of Keys within an AvlTree. For example, looking up a value from an AvlTree with around 1 million values takes a Proof of ~775-800 + the size of the Value's Bytes.
How would an Optimistic Rollup be stored?
An Optimistic Rollup in Ergo would be represented by a Box, holding two AvlTrees necesarry for the Layer 2 network:
- A main state AvlTree, listing all pseudoBoxes on the network
- - Stores a list of pseudoBoxes (fake Boxes because they're on Layer 2), which are represented by the digest of an AvlTree with the pseudoBox's contents
- A unconfirmed transaction AvlTree, listing the past 5000 (subject to change) rollup transaction digests (the mainTx)
- - Each mainTx can further be broken up into many subTxs (also an AvlTree Digest), an individual transaction submitted by any user
- - SubTxs provide the past state before the subTx, the state after the subTx, and all of the pseudoBoxes used as an input and output
Fraud Proofs in Ergo
Key to the usage of Optimistic Rollups are Fraud Proofs, essentially the proof that a given transaction is invalid. Because Optimistic Rollups default that any given transaction is valid, it is required that other users govern the rollup ecosystem, and prevent any invalid transactions from surviving the 5000 transactions to become accepted in the permanent state. Because verifying that an entire transaction is valid, whether through ZK SNARKs or ZK STARKs, is troublesome on Ergo (and I don't know much in that area), I have been working on a Fraud Proof that requires full knowledge, and goes through each step in full.
Isn't this very computationally expensive?
In short, both yes and no. Because a fraud proof only requires that a subTx or mainTx is proven wrong instead of right, a Fraud Proof is naturally much smaller than a Validation Proof. It's easier to show that a single rule was broken than that 100 rules were followed. However, without applying ZK SNARKs/STARKs, the size and computation necessary for a proof is larger than possible, and in fact regularly is much more than can be done in a single transaction, due to computation limits and the 95kb data limit. While submitting a fraud proof for an average subTx, with up to ~50 pseudoBoxes and somewhat simple scripts can be done in a single transaction, that is not good enough. To be a true Layer 2 Network, it has to be capable of supporting DeFi, large-scale payments, and all aspects which are available on Ergo's Layer 1.Multi-stage Fraud Proofs
While only ~50 pseudoBoxes can be (in)validated if all aspects are handled within a single transaction, that does not need to be the case. One key aspect of Ergo, both a limitation and a blessing, is its use of Multi-stage Contracts. In short, ErgoScript as a scripting language is not Turing complete. Lacking basic programming functions as setting variables within the script, infinite loops, and other useful items, ErgoScript seems very limited from a first view. However, by creating Multi-Stage Contracts, ErgoTree scripts are able to achieve Turing completeness across multiple transactions while increasing the scalability of transactions which do not require multiple stages.Multi-stage Contracts are smart contracts which, as the name implies, have multiple stages. By utilizing a required token(s) as a proof the multi-stage contract is being followed, ensuring that the token is only accessed with a valid starting condition, Multi-Stage contracts can prevent malicious actors from arbitrarily creating a starting point with their own data. Because ErgoTree scripts are limited, Box registers can act as variables, loops can occur by looping through the stage itself, and can span across as many or as few transactions as necessary. Multiple stages of a single contract can also be fulfilled within a single transaction, so Multi-stage Contracts do not negatively-affect scalability.
By splitting up a Fraud Proof throughout multiple stages, a Fraud Proof can get as large or as small as possible, and is not limited by a single transaction if necessary. A Fraud Proof for a subTx with ~50 pseudoBoxes can still be done within a single transaction, and a Fraud Proof for a subTx with ~100,000 pseudoBoxes can take one transaction or up to 850 transactions across 1-5 blocks, depending on where the fraud occured.
Note:
A currently planned maximum pseudoBoxes per subTx will be 100k pseudoBoxes, although 1 mil+ is possible. However, as Fraud Proofs become less efficient as the number of pseudoBoxes (and subTxs within a mainTx) increases, a limit is beneficial, not to mention strain on submitters to ensure every mainTx with 1 mil+ subTxs, and 1mil+ pseudoBoxes per subTx, that they're submitting is valid.In addition, requiring more complex Fraud Proofs will either congest the main network due to requiring more mainnet transactions in a short period of time, or slow down the Layer 2 network as it waits for the fraud proof to be submitted and the state rolled back, and so strong incentives are required to prevent incorrect Txs, especially extremely complex incorrect Txs, are submitted.
Conclusion
By utilizing the data storage capabilities of AvlTrees and the nearly unlimited power of Multi-stage Contracts, an Optimistic Rollup on the Ergo Network is viable if not inevitable way to provide scalability to Ergo. If this topic interests you, I am currently working on bringing this design into reality, although I lack the time and skills to do it all myself. As such, anyone with experience in or willing to learn Blockchain Tech (for the Layer 2), ZK SNARK/STARK cryptography, ErgoScript, Frontend dev work, Graphic design work, or anything they think might help is more than welcome. I also would like to form a dedicated team if possible, as I think my design and initial implementations are ready to go further.
Please contact me on Discord at Quwin#6226, or send me a message here!
