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