Ethereum Foundation DevCon 6 - Layer 2s Track, 15 Oct 2022

Previous Meeting Next Meeting

⏯

youtube image

►

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

Description

Visit the https://archive.devcon.org/ to gain access to the entire library of Devcon talks with the ease of filtering, playlists, personalized suggestions, decentralized access on Swarm, IPFS and more.
https://archive.devcon.org/archive/watch/6/using-a-hybrid-utxo-and-account-based-state-model-in-a-zk-rollup/

Many rollups choose to follow Ethereum’s account-based state model. We explore an alternative approach: a hybrid of a UTXO and an account-based model, specifically in a context of a ZK rollup. This approach offers a number of interesting properties including local transaction execution, support for privacy-preserving smart contracts, and reduced state bloat. In this talk we describe tradeoffs between different state models and cover the specific design choices we’ve made with Polygon Miden.

Speaker(s): Bobbin Threadbare
Skill level: Intermediate
Track: Layer 2s
Keywords: zk-rollup,utxo,privacy

Follow us: https://twitter.com/efdevcon, https://twitter.com/ethereum
Learn more about devcon: https://www.devcon.org/
Learn more about ethereum: https://ethereum.org/

Devcon is the Ethereum conference for developers, researchers, thinkers, and makers.
Devcon 6 was held in Bogotá, Colombia on Oct 11 - 14, 2022.
Devcon is organized and presented by the Ethereum Foundation, with the support of our sponsors. To find out more, please visit https://ethereum.foundation/

A

A

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.

A

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.

A

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.

A

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.

A

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?

A

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.

A

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?

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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

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.

A

We have two different types of two different modes of storing accounts in this database.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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?

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

A

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.

A

The blog producer will need to decide which of those transaction goes through, because um you know you can't.

A

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.

A

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.

A

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.

A

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.

A