Using a Hybrid UTXO and Account-based State Model in a ZK Rollup by Bobbin Threadbare

foreign [Music] so in my talk today I'm going to be talking for the first time about um how we've designed a polygon Milan roll up and specifically how we use this hybrid utx or an account based model to achieve some interesting properties so just to set the context at first the goal that we have in mind is we want to build a scalable decentralized roll-up with privacy enabling architecture and what I mean by that is that our immediate goal is to achieve scaling but we want to design the role up in such a way that when we want to turn on privacy it will not require a complete architecture overhaul it should be very easy to achieve that um and I'm sure a lot of you here are already familiar with this but just to set a context of what is a decentralized roll up we have users we have rollup operators um and we have ethereum L1 and in this model users and transactions to The Operators operators aggregate those transactions into blocks and then they submit kind of the state Delta in a context of a ZK roll up with a ZK proof to A3 ml1 and then um uh what we get and this is not specific to a decentralized roll-up this is a true for any roll-up we inherit security from ethereum um what is specific for a decentralized rollup is that a roll-up is has its own L2 chain and it's um its own consensus mechanism because the operators need to agree on the state of the of the chain and then we want to have these operators to be the set of operators to be permissionless meaning anybody can join and leave the set as they please um now compared to a centralized roll-up where we have only one operator a decentralized rollup has a number of challenges and the most important ones are um you know you need to have a separate consensus mechanism um you need you also have this execution bloat problem and I'll explain what it is in a couple of seconds and then you have a state load problem so in this uh talk in this talk I'm going to talk about specifically execution bloat and state load and so let's get into it so what is execution bloat an execution load basically means that the network needs to execute all the transactions and more specifically a block producer needs to execute on the transactions in the block but also everybody else in the network needs to re-execute the transactions to make sure that block is valid and you know that leads to a lot of free executing the same code over and over again what is State load I'm sure a lot of you are familiar with that this is basically means that state size grows with time the more accounts there are the more tokens accounts hold and all of that you know the state size increases and the reason why we can't do much with about that is that nodes or operators need to be able need to hold the full state to be able to validate the blocks and nodes need the full state to be able to produce new blocks now why are these things bad like I said there are challenges so why exactly are they challenges so the first thing is um if you have state load and execution bloat you need powerful machines to like let's say we have thousands and transactions per second you need a powerful powerful machine to process that if you have a large you know terabyte size State you need a large machine to hold that in memory and that leads to essentialization and if you don't have good solutions to this problem you might as well just build a centralized roll up uh the other one because everyone sees everything and everybody needs to re-execute transactions and have the full State there is inherently less privacy in this uh in the setup and last one is especially specific to State load this is not sustainable if the state grows you can you know scale the role up only as fast as the hardware scales you can you can go uh like a Hardware in a single machine or something like that um so what do we want to achieve what is the ideal solution to this so the first thing we want to minimize execution bloat and that means we want to execute transaction only once and also we want to make sure that it doesn't have to be executed by the same party so it's not the same block producer that needs to execute all transactions we want to have distinct actors in a network that can execute transactions we also want to minimize the state load and that means we don't want to enforce the condition where you need to know the full state to validate blocks and we also don't want to enforce the condition where you need to know the full state to produce new blocks zkps can give us you know these two upper properties if you have the KPS you can you know produce a proof of execution for example and you don't need to re-execute the same transaction over and over again but to achieve the other two properties you need something else zkp is alone are not enough you need what I call a concurrent State model and before I get into the concurrent State model let's talk about like the popular approaches to what that you know the popular state models right now so we usually have an account based State and a utxo based date and if we look at pros and cons of each let's say for account based date um you know it's great for expressive smart contracts this is what we love about ethereum we can write very cool applications you have a lot of freedom and they all interact with each other very well uh it's not great for concurrent execution it is possible to achieve but it is not very easy and you know has a lot of issues and it is also bad anonymity because if you want to if you have accounts and you know which account participation which transaction it's very difficult to hide kind of this transaction graph so to say utxo base model is kind of opposite of that it's great for concurrent execution because in a utxo model transactions are logically separate from each other it's actually a very good tool for anonymity like if you want to achieve an image you almost have to use a utxo model it's not the only thing that you have to use but it is one of the kind of basic building blocks but it is not great for expressive smart contracts you can kind of get smart contracts in utxo model but it's not easy and you know the more expressive they are the more it starts to look like an account based model so what we want to do is combine the nice properties of each of this into a single model and I call this like basically account based model each Excel based model and combine that with EK proofs and we'll get something that I call is the actor based model with concurrent of chain State and I'll get into what all of those terms mean in the course of this presentation so first thing that I want to explain of how this works is how do transactions work in this model and what is an actual model specifically and how we think of transactions in that model so just to take a step back and explain what is an actual model it's a concept from distributed uh kind of systems where you have actors which are kind of state machines with inboxes and actors communicate by sending messages to each other and the important property is that the messages are asynchronous so an actor can produce a message and then a different doctor can consume this message at a later point in time the way we apply this active model to a blockchain is that in our context in context of Maiden actors are accounts an account holds a state and exposes an interface and interface is just a collection of methods which you know every of those methods is a mighty NVM program and might and VM is a you know fully to recomplete sck VM um so you can think about it as very you know expressive functions that you can write uh for the account interface accounts communicate with each other by sending nodes to each other and nodes can carry assets and the node also has this pen script which needs to be executed to be able to consume a node and one important property is that in this model is actually takes two transactions to move assets from one account to another so in a traditional kind of ethereum model for example you usually have just one transaction that moves assets from one account to another in this model you have to have two uh transactions because the first transactions create a node and the second transactions consume a node now let's talk about transactions have been in a bit more detail so what is the transaction in the context of Maiden a transaction always involves only one account the transaction does not enroll more account and you know as a in the course of a different section the state of the account gets updated um transaction can consume zero more nodes and a transaction can produce zero more nodes so in the previous example for example there was a one transaction that produced One node and one transaction that consumed one node and we can have also transactions that produce and consume nodes in the same transactions um now the execution graph of how like let's say nodes get consumed um kind of to explain how this whole process works is let's say we have a transaction that wants to consume two nodes in a context of one account so the way it would start is like we have this product and epilogue that do some bookkeeping to make sure that like let's say sum of inputs is equal to sum of outputs uh and nothing kind of no new assets get created in the process of transaction but then we go into this execution stage where the first thing that happens is we call execute we execute a script of the node of the first node in this transaction and then this uh execute script can call any number of methods on the account interface so you know in this case let's say there is a receive method that receives assets on the account so a node can pass assets to their account through this receive method and one important thing is that account uh methods are the only ones that have access to account State and node cannot modify the state of their account directly it needs to call a method on the account interface to modify an account and then the account interface methods can create other nodes that's how you can for example create new nodes in the process of a transaction and then you know if we have another node we do the same thing sequentially execute the second node in the context of the same account and that node can again call the same or different method on the account to have different effects and so forth now in our context the because we can kind of execute and nodes only touch a single account what we do is we execute a transaction and immediately produce a proof for it so in our case we use the Stark proving system so might and VM is a stark based VM so whenever a transaction is executed we immediately produce a proof of execution and because again I mentioned the transactions are logically distinct they only touch each account separately we can produce many transaction proofs in parallel so we actually produce all the all the transaction groups in parallel and then what we do is once we have a bunch of these transaction proofs we recursively aggregate them into the into batches and this batches then recursively get aggregated into block proofs and then these blog proofs get further aggregated into like Epoch proofs and that's what gets submitted to ethereum now it's important to know that all of this recursive aggregation can also be done in parallel so as I mentioned all transactions have been can be proved in parallel but also all batches can be proved in parallel the only thing that doesn't get proof to parallel is the final kind of tip of this block proof and then there is another interesting property is that we can prove transactions locally and I'll get into that in a second of what exactly it means um but then the segregation steps need to be done by the network for example a block producer or a block producer can delegate this kind of aggregation to someone else some other actors now let's talk a little bit more about what this concept of local versus Network execution so in a traditional kind of uh model okay when we execute a transaction we have you know a step that prepares some inputs for the transaction signs the transaction and so forth then we execute it um then in the context of SDK system we generate a proof for this transaction and finally we get this transaction proof that you know according to the previous slide gets aggregated into batches and it finally end UPS in the block now in a network model the block producer so that the user prepares the transaction sends it to the um you know the network and then a block producer would execute this transaction generator proof and then you know aggregate this proof as I described on the previous slide in a local context the user can actually do all of this so the user can both prepare the transaction execute it and generate a transaction proof and then what gets sent to the network is actually just the transactional proof itself and then the block producer doesn't actually need to execute the transaction and doesn't need to generate the proof for it it just the block producer just needs to aggregate it but it was other transactions for which it has generated the proofs um one important thing to note is how do we handle shared State because you know it works what I described works very nice when you have like transactions which go and don't touch multiple accounts or like when you have nodes that go to different accounts and so forth but let's say we have something like a uni swap situation where we want we have several accounts that want to send nodes in exchange let's say assets for some other assets uh using uni swap account so in the way we would do it is that first we would have you know each account generates its own transaction to create a node that targets a uni swap account um this would be two separate kind of logically separate transactions then the block producer will generate a third transaction that would consume the first two nodes in a single transaction and also as a result of this consumption of this node that would generate other two nodes that would kind of Target back create like the exchange tokens back to their original accounts and then we would um and then we would have the you know additional transactions that uh the accounts the users of accounts one and two would execute to consume kind of this nodes back into the uh back into the their respective accounts so basically in this model we still have this ability to interact with a contract or account with a shared State just in this case the transaction that interacts with the account of the shared State needs to be a network transactions it's not a locally executed transaction must be executed by the network or the block producer because the block producer needs to sequence the nodes according to whatever logic they want to do and then execute all of the nodes against the same account now just to kind of summarize this you know pros and cons of local versus Network execution so if we want to have a shared State kind of an account with share State we cannot use local transactions but we can use Network transactions now if we use a local transaction we can have privacy because nobody actually on a network needs to execute those transactions um we cannot have privacy with network transactions because obviously somebody needs to execute them now generating proofs is a fairly computationally intensive process so the client Hardware requirements might be high for local transactions but on the flip side because you generated the proof locally there is much less work than a Blog producer needs to do they don't need to generate the proof for the transaction they don't need to execute the transaction so the fees for such transactions for local transactions would be lower than for the ones that are requested for the network to execute now the next thing I want to talk about is what kind of a state model do we need to support this type of transaction model and this is where the uatxon account based model kind of comes together so um My Little roll up state is actually described by three databases usually you have a single database you have usually an account database or you know in each Excel context you have a kind of ATX or database but in our context actually three separate databases there is an account database there is a nodes database and there is a nullifier database and I'll explain why you know why all of them are needed and then in our case updates to all of this three database so like when you have a Blog a block contains information that updates all of the three databases and you know takes the state of the network from you know stay tuned to extend n plus one um account database account database holds all of the you know current states of their accounts and we use the sparse Merkle tree to kind of uh as a data structure that holds this information uh and the sparse Michael tree Maps account IDs to account hashes but we have one kind of twist to this we have two different types of two different modes of storing accounts in this database the first one is on chainstate which is basically the same as what you would get was ethereum where for each hash the nodes store also all the associated data for the accounts such as like storage code you know nons and so forth but there is also an option to do just an off-chain state where what the node store adjusts the hash of the account and uh the the user himself or herself is responsible for storing the actual state of the account so network not Network don't do not store the actual account State let's go to the nodes database next the nodes database stores all nodes that have been ever created and for this we use a miracle mountain range which is a append only accumulator and a leaf in this miracle mountain range is basically just a set of nodes that were created in a specific block and one of the reasons we chose this uh there are a number of reasons why we chose the miracle mountain region it's very convenient for a number of purposes but one of this is that um you can extend or add new nodes to this accumulator without actually knowing most of the previous nodes so you can discard the big part of the uh of the nodes database and still be able to add new nodes to it without problem the other property that is very important is EK context because we need to prove the inclusion of um you need we need to prove that we're spending a node that has been you know has been created at some point in the past is that the witness kind of inclusion witness does not become stale so you know if you have a mortal path it actually just needs to be extended from time to time very infrequently but it doesn't become stale and that means that the hdk proof that you generate does not become absolute very quickly this is a very important SDK context uh and then lastly we have the nullify database and the reason why we need this nullifier database is that um you know we have the account database which stores states of accounts we have the nodes database that stores all the all the nodes ever created but we do not remove nodes from the uh nodes database because we want to have this nice property of append only accumulator therefore we need another data structure that will tell us which nodes have been consumed so the notify database is something that keeps track of nodes that have been consumed and for this we also use a sparse Merkel tree where we basically map a node hash to either zero one zero indicates that the node hasn't been consumed one indicator the nodes has been consumed so whenever we generate a proof for a block the the proof must include that you know this node existed in a accounts database and it did not exist in the nullifier database um we actually have a slightly more sophisticated data structure where there are multiple epochs and you know those are time periods and for each airport you have a separate nullifier tree uh and then um you know nodes are expected to keep the last two epochs but can discard the nullifiers for the prior epochs now uh we have two uh we have this different databases and there are very different growth drivers for each of these databases so An accounts database grows primarily with the state of with a number of Public Accounts um or the accounts that have on chain State because if you you know it does grow within a total number of accounts but if you only have to store a single hash for an account that you know that's almost negligible like you can store a billion accounts and it's going to be only 64 gigabytes uh and also we can dynamically kind of prune this we can you know for accounts for example that haven't been used in a while we can just remove all the data and store the hash for that account or nodes can choose to do that if they wish to uh the notes database grows with the number of unconsumed nodes so as soon as the node is consumed it can be safely discarded you don't need to store it anymore so unconsumed nodes is what drives the um the size of the database but also you can have this pruning where you can you can remove some of the notes and just keep the hash then finally we have the nullifier database and this one is a different one because you can't easily prune nullifiers to be able to create new blocks you actually need to keep all the notifiers and the nullifier database depends on the throughput so like the more transactions per second you have the more nullifiers you need to keep in for a given Epoch we can make Epoch smaller but you know there are some downsides to that so overall you know if we look at kind of like what sizes of these databases could be that nullifier database is going to be by far the ones that drive the size of the overall State it's going to be larger than the nodes or accounts databases combined now I have a few slides to wrap up the talk to say well well what did we achieve first we have this concept of different models of execution so the network execution and local execution and we have this concept of on-chain data and off-chain data and the combination of this gives us you know different nice properties so for example if we have on-chain data and network execution this is a typical you know public transactions something that happens on ethereum right now we can also have stateless transactions if we have off-chain data but Network execution where um you know the network doesn't store the state of the accounts for example but the user needs to provide the state of the account with every transaction so the network can execute the transaction and the next thing we can do if the data is off chain and local execution is happening we can have private transactions where the network is not aware not only of what code was executed necessarily but also is not aware of the data that is in the account and we can also hide the transaction graph using utxos um it's I'm not going to get into that right now but it's a bit slightly more complicated but we can do that as well and then finally for completeness there is this uh you know local execution and on chain data I personally don't know which use cases that would cover but maybe people will come up with something how did we address execution load with those models so first we achieved no re-execution so all transactions are executed only once uh second we have concurrent processing where transactions can be processed in parallel uh on Independent machines and you can almost scale this thing horizontally by adding more and more machines to generate proofs and finally we have this local execution where transactions can be executed by the users that are involved in those transactions and the nice property here is the more locally proven transactions you have the less burden computation loaded in the network has to encounter because let's say 90 of transactions are something that has proven locally there is very little work that the block producer needs to do to uh to they don't need to execute them they don't need to prove them they just aggregate them into blocks and then regarding State load we have kind of this Dynamic pruning where we can collapse accounts and nodes into their hashes um we can have very light verifying notes if you only want to verify State Transitions and you don't want to create new blocks you actually don't need to maintain the nullifier database at all and in that case as I mentioned the nullify database is the biggest part of the state so you can actually discard the biggest part of the state and we have this nice thing where because the nullifier database dominates this overall State size the oral State size really depends on GPS so the higher the GPS the higher the nullifier the bigger the state but it doesn't vary with the number of accounts for example as much or number of nodes in the system and last thing that I want to leave you with is that this is what we're trying to achieve where the more privacy there is in a network the more scalable it is the more scalable it is the more private it is and this is our goal with the maiden roll-up thank you so how would the network result when two accounts try to spend the same utxo like in a text or something like that so um if two accounts are trying to spend the same utx oh that's a conflict you can't spend the same ejx or twice um so I think the problem um so it's not really a problem in that case like if you are trying to spend like if you if you have utxo and I have utxo and we submit transactions for whatever reason that both of us can consume the blog producer will need to decide which of those transaction goes through because um you know you can't you can't execute both of those transactions simultaneously because there will be you know one of them will produce a nullifier that the second transaction will not succeed because the nullifier for this utxo has already been created so like in the union swap example you can send so like you can send a note that says I want to swap token a for token B right at this price and somebody else can do the same thing and those are two different requests but then the block producer will aggregate those requests sequence them in a single transaction and execute them and there will be no conflict on that because the the state of the uni swap contract gets updated sequentially after each uh consume node so you're not consuming the same utxo you're applying the different nodes to the same account but yes that cannot be done locally that needs to be done by a block producer um it's an optimization uh the idea is that if you want to have an um if like let's say um your node was created in a prior Epoch and the nullifier was created then you you will need to provide the path that proves that it was it hasn't been consumed yourself the node the nodes are not responsible for that so the notes are meant to be like a short-lived object so they are not meant to stay in a state for a long time and if for whatever reason you decided to keep the state there for uh quite long that's your responsibility to be able to provide this proof to uh the network it's not Network's responsibility to keep it for more than let's say six months or so thank you