this project has been going for a little
bit less than a year and it started as a
little curiosity but then it sort of
meandered into all sorts of rabbit holes
and currently it's been supported by
three different organizations it's a
theorem Foundation and form of grants
and also buy in fewer buy-in contracts
with me an interchange foundation as
well you probably know about interchange
foundation by a cosmos product so let's
start so I'm going to skip all the
slides that I had before because you've
probably seen them so we start right
from the meet about what is the
difference between the gas and turbid
gas and so on the slide you could see on
the left hand side you could see like
the in the cerium the this the state of
accounts and the contracts and their
storage is modeled as the Petruchio tree
which is essentially a radix tree of
radix 16 with some refinements to be
able to get rid of some some waste of
waste of space and when you're more do
it like that and you want to persist it
and then database the persistence you
looks like on the right hand side which
is the key of the so it basically the
whole structure every node in its
patricia tree is split and is one record
in a database and for that record the
key is the the hash of the civilization
of this node and the value is the
serialization itself what it allows us
to do is let's pretend that we we do not
have that pink node in the top like the
diamond pink node and instead we we
simply have a hash which is which you
could see that there's a little dark and
dark rectangle so what we could do is
that we could take that hash and then
use it as the key in the database and
look up the serialization of that pink
node and reconstruct it and then plug it
into the tree so that's how basically
pretty much all the clients do that as
far as I know and so the the problem
that so that was when I first saw it
actually I I was a bit surprised because
for me it wasn't it wouldn't be how I
would do it and that's why I actually
started on this process because whenever
I see something which doesn't look like
I expected this is where you so I didn't
expect to see that but probably it was
very natural for other people so the
main problem here that I saw is that
let's say that when you when you were
only have a root and nothing else in the
memory and then you want to fetch that
let's say element v5 which is the purple
diamond in that on the bottom right you
actually have to do one two three
lookups to the database and the reason
for that is because in order to retrieve
the diamonds you have to first retrieve
the element before that because it
contains its hash so an end so vice
versa so you have to do three sequential
lookups to the database you cannot
paralyze them because you there's a data
dependency there so that gave me the
idea of not doing that so basically that
you see in the red matters depth should
not matter it means that how can we do
that without doing three lookups or five
lookups so seven would lookups or
whatever I think at the moment an
average will be eight or nine lookups if
you don't go through from the root so
what I try to do is that okay let's just
put them in a database as I would expect
it to be like you've got the key which
is the which is the actual key of the
value that you want to store and the
value is the actual value that you want
to store and if it's a history
historical value then we can we're gonna
append some kind of block number encoded
in some way to the key just for
simplicity and the the main problem here
is that how we're going to compute the
oracle hash of that and i think
initially when the first clients had
been produced the assumption was that oh
that's going to be super expensive to
actually have this flat representation
and then should build a whole tree and
then everybody decided to go okay let's
do the list blue Patricia tree in a
database but then I said well why not
good to try and then I try that and
actually turned out that you can do
things much well in a lot of cases much
faster if you simply rebuilt the the
hash tree on the on the fly and you use
some caching and stuff like this so the
way it looks like in imagine that we
need to
[Music]
to get the to this pink diamond now with
the pink then we just we just simply
fetch it but actually let's meet let's
say that we want to compute the hash of
that the oval that our thing so in this
case we do a range query which will
fetch us all the keys and valleys which
starts with 1 which is the actually
might be maybe the pictures might be
wrong but anyway so you probably get the
idea so we get the range of keys and
valleys and then we apply our merkel
ization to them and we get the hash the
it only kind of works for this for the
current state and if you want to compute
the miracle hashes of the current state
but for historical state it's it's a
kind of a lot of work because you don't
usually store the historical state in
your cache but it works reasonably well
for for the RPC queries that are tested
so let's go so so as I mentioned that in
fewer has been supporting this project
for for some time and one of the things
we did is that instead of me only
running the surrogates on my machines or
some cloud machines they try to run it
out of the source code and this is what
happened and I was kind of pleasantly
surprised because I must have been
running it on a really bad machines
before so now I usually got two weeks to
sync it but this was actually synced in
about six and a half days yeah six and a
half days and the this - the pretty
recent block and the it's archive node
actually so it has a full unrolled
history and it only was what two hundred
two hundred fifty something gigabytes
which was cool because it probably six
times less than you would normally get
and just as an interesting thing that
the memory profile so the what you can
see here is that the yellow oscillating
bit is that it's obviously go it has a
garbage collection and that's why it's
oscillating so much that it's basically
allocated heap which goes into 13 gig
maximum and you can see the spike about
the the spam attacks where it was a big
load and the green bit is there is a
number of nodes so what Troopergate does
actually one of the things it does
differently as well is that you
limit number of nodes at use of the of
the tree you can store in a cache and
that might allow you so my hope was that
you can use it to calibrate the the heap
space but you know I think it might
still be considered constantly
increasing so now what I so now look at
the these graph so what you can see this
is the recent well quite recent maybe
one month old graph and this is where
the they actually the cost of storage
comes from most of it is now blog bodies
which is the essentially this is all the
blocks combined for like six million
books and then the the second biggest
structure is the code block this is like
a gray one block number two changed keys
this is the structure which is a
specific to through bagasse and it
allows it to to know which accounts and
which storage indices changed at which
block and why do we need this is because
it allows us to do to rewind the state
quickly so in a situation where let's
say that we've been like sinking to the
main chain and then we suddenly see
rework of like four blocks so what the
to Poquette does it actually it looks at
this mapping and figures out which keys
changed in this four blocks then picks
up the values which were before these
four blocks and then unwinds the the
tree in the hash and then computes a new
hash and then reapply is the the state
on a on a fork on and out of work and so
what you do not see here is is the
receipts you can have them there they
would take about six 70 to 80 gigabytes
of all receipts from the beginning and I
will show you later why would one you
want to do that but the interesting bit
to note is that lots of people are
confused about the size of the state in
the theorem and in the reason why
they're confused is because different
clients toward the state differently
like like for example go is theorem
current state representation goes here
probably like 80 gigabytes 92 bytes in
through bagasse is probably going to be
about 12 gigabytes I don't know how it's
going to be in parity but it's a
different client store differently and
sometimes people confuse the current
state with the like total historical
state with the prune historical state
that's why
is but what you can see from this
picture on the very top you can see
accounts which is 3.89 gigabytes this is
the account without any storage items is
just simply balances nonces hashes of
the of the of the storage roots and the
code hashes and the whole no it's not
the whole history is the current
accounts so the history of accounts you
can see on the left on a yellow bit so
forty four gigabytes then the storage of
the contracts the current the current
state is what ten gigabytes you can see
it somewhere down the middle
the purple my violet bit and then you
can see the history of its it's about 20
or 60 gigabytes so you can see that the
current state is still kind of about
twelve gigabytes probably now so this is
the this is where I'm gonna say about
receipts because I haven't tested all
old entire entire set of our pcs and
again this numbers are very rough I
didn't do scientific studies on this but
this is what I just saw there after very
quick running
I run the both archive gas and turbo gas
on the same machine and obviously there
would be lots of noise but I could see
through this noise that generally the
things are going faster except for the
receipts and the reason that for that is
because I chose to prune the receipts
from the database and instead I just
recompute them so when somebody asks me
for receipt I just go to the state where
that was at that block and after that
transaction just really execute the
transaction produce receipts return them
it turns out to be slower actually this
might be not ten times may be a bit more
slower but somebody tell me that maybe
you just need to be a flag because some
people the only thing they do is
actually query receipts so for those
people they might be able to might want
to pay 70 gigs for for speed of that RPC
so now the other thing I didn't quite
recently interpret guess is they I have
prepared it for the pruning but I
haven't implemented pruning yet so but I
made sure that the pruning can be done
pretty faithfully and so the idea here
is that instead of so what you could see
in this diagram so every bubble every
little circle is actually a record in a
database and so the the arrows like this
thick arrows they
they represent that the each to each of
these circles is basically a
representation of the state for that
period of time so let's say that the
green circle on the right is the current
state it means that the current state
has been for that like if you look at
the top one for the last let's say seven
blocks or eight blocks I don't see it
exactly this was the current state and
it hasn't been changed for seven or
eight blocks right and before that there
was this yellow bit which was since we
know and and so on so the red bit is
where something gets deleted
for example the account gets deleted
then I mark it as a red we put it as a
record as well and also that you could
see that the blank blue one this is
where something just first been created
and there was nothing in bits before so
now what we can do is that what I could
reverse diffs instead of forward ifs and
what it allows you to do is this so if
you basically chop off the the left bit
then you can just keep running your your
note because you still have everything
everything is still consistent so you
can still query the state at any point
that you have a history for if you if
you try to do it with the forward this
that would be difficult because you
would have to when you chop the chop
this up you would have to rebuild the
current state at the point of the chop
because everything is Israel is relative
to the to the previous um some sort of
previous snapshot so as I said I haven't
implemented yet but it's trivial now
light clients I mean here I'm actually
mean light server and at the moment is
not implemented and the reason for that
is because I simply don't store any
hashes in a database and I kind of do
but not much only in Oconee for the
current state so what the light clients
actually need you could see on a lot
right hand side all the ticks that the
last two protocol needs all this support
all these things and the ones that my
accountant currently cannot provide is
these the ones which I pointed with a
red arrows which is no data and proofs
all right so no data will be very
difficult in any way because it's
specific to it turns out to be specific
to the way that current clients store
the state and would be
very difficult for me to implement that
because it's actually you cannot come up
with any hash in history or in the
current state which I have no idea where
which block it is from and you're
supposed to give me I supposed to give
you the the note for that and I don't
have idea where to look for it in my
database because my database is
structured by the blocks the get proof
is more is easier for me because it at
least it tells me at which block and in
which account you look for so I can
actually find it so it's easier to
implement that and maybe I know that the
light clients can ask for proofs not for
the current state but but for for some
delayed state but it could be done but
and the and then there's another problem
which I encountered recently I call it
creates a revival problem and it's also
actually this is also to inform people
about something which is coming up in
the Constantinople it is not in the main
idea by the way don't get scared it's
the sir great show up code essentially
is introduced to allow efficient
counterfactual instantiation and in the
way it does it is that if you look at
the formula of the address computation
it it includes address which is
basically the creator of this contract
salt which could be chosen at at will
and then in it code which is something
which will be executed to generate the
actual deployed code so that means that
you you you can in theory and in
practice recreate the contract after
they've been self destructed so in this
diagram the big circles is the contract
and the small circles is the storage
items of the contract and you can see
that how contract was created and
storage has been modified blah blah blah
and then we go to the point where he got
self destructed and you got all these
red things and then later on in like
three blocks later it's been recreated
using crate to with the same code or
with a different code but with the same
init code and then after that you
supposed to so it's assumed that now at
this point then the the storage is
cleared and balance is cleared so this
is completely empty contract and now you
can start again so the problem for super
guest is that because it doesn't store
the state as a tree but rather in this
relational way it has to either insert
all these red bubbles into into the
database which could be in millions
potentially
at the point of self-destruction or it
has to apply much more more in nuanced
way when you actually fetch the contract
item so the alternative would be to like
whenever anybody asked me for the
contract storage I would have to also
check whether the contract has been self
destructed in the past and when there
was the last time so it's more searching
I can implement it but it's kind of a
bit hustle now so this is this is highly
experimental this is a this is something
that I came up with when I was thinking
about all these problems that with the
light clients and with the with the
create two and at the same time I was I
was working with the ether main team and
they basically we did some tests with
the load-in even transaction at either
mint and it turns out to be a bit slow
so I said we need to be we need to get
faster with that and so the idea is to
actually create a specialized database
that would allow these few desirable
things and I will explain why they are
they might be good it's still very
experimental so it's it could also it
turned out to be a different way so
although I did some proof of concept on
this I will tell you roughly what the
results were so let's get into them the
details of that so as you know again as
I told you before as well the the
theorem currently uses petruchio tree
for miracle ization but also it's it's
it's before inserting every anything in
the pituitary it also applies the hash
function to the key so the keys are not
just inserted as they are and this is
because in beckon mm whenever 15 I think
when when there was a security audit of
a serum something pointed out by Andrew
Miller that you could actually create a
very very long branches in that tree
but attacker could do that and I'm
basically introduced some some bad
things
so as the mitigation it has been
suggested to hush all the keys before
inserting them into the patricia tree
and the idea is that it would kind of
balance them out there is a it still
doesn't completely solve the problem but
we're not going to touch it right now
so for the serum 2.0 for example there's
also
of sparse miracle tree which is
essentially also radix tree but with a
different radix instead of radix 16 they
use radix 2 and but the idea is very
similar and for the same exact reason
the keys will have to be hashed and the
reason I don't like the hash keys is
firstly because I believe that the the
problem pointed out insecurity or it has
not been completely resolved and it will
keep persisting if we stick with a
sparse Merkle trees and also you also
have to keep pre images so to be able to
each rate through the state and the
perimeters are not really heavy at the
moment but in I just chopped a bit out
of the diagram it's but 15 gigs so what
have been experimenting with and of
course it's it's been it's been a it's
been inspired by the by the fact that
that that either mint uses the AVL trees
looking at the balance in trees and the
main objection to balance in trees was
that the order of insertion and deletion
actually matters and I've been looking
at not only AVL trees but also the well
weight balance tree is actually really
little known about them but these are
the structures which are really good for
functional languages for some reason so
actually what the idea is that ok let's
try to encode the structure of the
industries of string a bit so this is
actually you're probably going to look
at the slides later but so this is to
demonstrate you that you can encode the
any any binary tree in fact into the
string of bits with the cost of at most
2 bits per item and then decode them
with a very simple state machine as I
provide here so the coding allows you to
either rebuild the whole tree or
actually compute Merkel cash efficiently
and then what you do next is that you
have this huge tree which is balanced
and you would nor close it according to
this huge tree and then in order to
efficiently store it and database you
split in two pages of the fixed size and
this is kind of the schematics of how
you would do it then after you do that
you encode them in the pages and this is
the structure of the page I'm using and
proof of concept it's called like
different elements in that and what is
interesting here is the page pointer so
there's two elements stored in a pages
that the the values you can see that FP
there and is
circle with the arrows are the pointers
and so then after that you can actually
add the history so so the main so let's
let's talk about this so first of all in
order to explain Morrison in a short
sentence is that the main idea is that
you use the same structure for the
database index as us the structure that
you use for miracle ization so it's the
same so that means that whenever you
actually commit something into database
it doesn't move anymore because it's an
exactly the same point in exactly the
place where it's supposed to be
according to the to the index of the
database which means that write
amplification equals the basically write
amplification does not happen and so the
database just grows it doesn't keep
three writing things on it if it's just
simply adds thing which is has some nice
properties so at the moment with my
proof of concept which I've been running
I was comparing with Troopergate which
is also quite already high bar so the
right hand so the the right efficiency
has been about seven times better than
in turbo gas so it means that it
actually has said seven times less IO
unfortunately the space efficiency has
decreased compared to too big if it's
about four times less space efficient in
the current numbers but I have a some
some I know some ways how you can
improve that access efficiency are only
superficially tested that so and so well
this to put it in a perspective is that
people usually talk about the trade-off
of three things and database is update
efficiency space efficiency and access
efficiency and you can see that you
really want to be inside this triangle
on that plane but you don't you never
really know whether you're above that
triangle which means that you're you
don't actually have an efficient rate of
optimal trade-off or you're in a
triangle so what I'm trying to do is
that I put it that none up to my systems
are already above actually above the
triangle so they're not really
exercising trade-offs at all so they're
inefficient in any way in any possible
way but what I'm trying to do now is
that trying to hopefully I am inside the
triangle already and trying
navigating between them so I'm gonna if
it's any time I'm gonna take any
questions any time for questions or yes
yep there's some time for questions yeah
I sorry I rushed so just that I
understand it this 200 gigabytes or 200
plus 70 for the receipts that's actually
an archive not right yes sir Connaught
nice
yeah and it can it can fetch you any
data for the entire history through any
RPC queries can you talk more about this
range request Oh range request it's it's
it's it's basically so range of quest is
quite simple because essentially you
were in most of these key value stores
what you can do you can open a course or
at a certain you can you can seek to the
certain key for example in this case
will be one with the sum 0 0 0 0
whatever the first key is to start with
1 and then you just use that iterator to
iterate through them until you see 2 in
the first position
that's it range query it's not like a
square but it's still possible
efficiently Alexa can you talk a little
bit more about your experiment with you
Thurman and why oh yes I forgot about
that sorry so the ether main experiment
is interesting for me because at the
moment when I only try to optimize the
surrogate and there is a Patricia tree
which already I said that I don't like
it very much but and it's it's encoded
in a yellow paper but what I want to
kind of look behind beyond the yellow
paper maybe because because it's cool
because because I want to search for
different structures maybe because
they're going to be used in East Point 2
to point or because a you know we might
be able to be able to create something
more efficient in either maned and then
we could just transplant the same so
they cerium it's probably good for
experimentation I also quite like
working with the either main team so
there
so yeah it's that's the reason is there
any like performance difference when
you're doing verses intermittent or very
early stages and the whole reason why I
started to do this Morris thing is
because the first performance tests were
not satisfactory to me so I wanted that
to be faster we probably have time for
one more question
yeah first of all I just wanted to ask
do you realize how amazing you are
oh thanks how you come from one point
three terabytes to 250 gigabytes with
the same it feels like the same
performance but a very significant
decrease in the size well there it comes
from two things first of all I don't
store any hashes and the hashes are
probably one of the biggest contributor
to the to the space in in existing
clients and secondly the the tree
structure when you were model the
history of tree structure it repeats a
lot of the elements on closer to the
root when you create a new version so
that repetition also that it also
contributes to the might to the Moores
being less space efficient because it's
also tree based so and that's basically
two reasons and if you remove these two
things that becomes a super
space-efficient all right well thank you
very much
alexei thank you for coming great
[Applause]
you