Navigating Eth2 with Simple Serialize

Transcript

hello everyone my name is caiman Nava I'll be talking about navigating eath to with simple serialize so just before we get into everything I just want to introduce myself I'm a technical lead on the lodestar project this is a project by chain safe we're writing an ease to client and we're writing it in typescript if you see those two pictures of me those are my avatars so maybe you've interacted online so this is kind of the overview we're gonna go over it's gonna be kind of fast I have a lot of slides and I really want to get through

it all but first what like before we get into like the details of this symbol serialize we're gonna say like figure out why it even exists in the first place and then we're gonna dig into how it's used in eath to kind of go over the different aspects of it we're gonna look at it in practice so like different implementation techniques and then finally get into some benchmarks and then if there's any time then we'll go into questions so why is SC in the theorem - we I mean in aetherium interests in general we have a lot of data that we're trying to mark allies and the reason that we were analyzed

this data is that we can make proofs succinct proofs about it in in in e2 we have an even more of a need for these proofs to be small than eighth one so we have like stateless clients by default we're gonna have a lot like light clients kind of as a first-class citizen and so some of the techniques we used in each one don't quite work in e to the another thing e to state is very different than the eath one state so we have a lot of data structures in eath to that we're kind of getting consensus on we have this entire machinery that's

handling the proof of stake system and all of that is gonna be Merkel eyes denieth to we'll look at some of that so some differences some things that are different between each two and one with respect to how our merkel izing data so one thing one big thing is in each one we're using hex Airy trees crys eath - we're using binary trees and the reason is the proofs are significantly smaller another thing to keep to note if you're coming from the eath one world the lot of all this data that we're america lysing it's not we're

not dealing with sparse trees these were full ish Merkle trees and the data that we're dealing with is much more richly typed and it's much more heterogeneous than just like the three or four different things that were merkel icing an eighth one so here's kind of just a it's a big list I'm not really only looking at not really gonna go into it but the idea here is that like there's a lot of different structures this is just the beacon state in the East - there's a lot of different like substructures different things that were merkel izing and so we need like a consistent way to be thinking about this landscape and so we need to this consistent standard

formalizing data is ssz so about sse you can kind of think of it as the type system for e2 at least from the consensus layer we have these different types that we get we have an unsigned integer a boolean vector a list container and a root we'll go into a little bit of detail on all of these but really important thing to kind of keep in mind as we're going through this and I'll be highlighting it with some diagrams these SSE these objects these values they all have an unambiguous merkel eyes representation and so you can think about all of these types are all these data all these values as if

they were trees and so going back and forth between the tree representation and kind of the datatype representation is will be very valuable from an implementation perspective when we get into that later so real quickly unsigned integer we have int you it from you and 8 all the way to unit 256 these were just kind of like unsigned integers as you know them in e2 we have valid air balances we have time stamps we have block numbers or slots and those are all represented as unsigned integers so if

we were gonna kind of represent this as a tree this would be a treat with one node that's very uninteresting kind of tree and we could kind of see realize that data each node in the tree is 32 bytes so kind of the red section is where the actual data is and the rest is padded with zeros boolean it's a boolean as you know it true or false in East two we use boolean mostly 4-bit lists and so we can tell like if someone in a committee did something or didn't do something if they sign or they didn't sign and again if you think about this it's like a Merkle tree it's just a

single node and most of its padded zeros but you use one bite so here's where things start to get a little more interesting the vector type that we defines how much home jeans collection so there's just one type for all the elements and it's fixed length so part the length is part of the the data type so some examples in ease to validate or public keys signatures so any kind of or most of the byte arrays that we deal with our fixed length those are most of the vectors that we deal with so the way that we

represent this is an entry we basically just put all the all the elements as leaves in the tree and if the length of the tree is not a power of 2 then we pad it with 0 chunks and if the underlying element if more than one of the underlying element can fit into a single 32 byte chunk then we compress as many of those things into that one trunk as we can so let's say we have a vector of bytes unsigned unsigned in 8 we can put we can put as many of those we can pack

it with them pack as many as we can into one chunk so that we're not just wasting a bunch of space in each chunk there's a really notable the really notable time that we're doing this in these two is four we four is four vectors of boolean's or lists of billions so like committee committee bit lists we tightly pack the boolean zazz single bits so we can get 256 boolean's in a single chunk oh and if the element is actually bigger than 32 bytes than we mark first we

Merkel eyes that element and then we put that the root into each each leaf so here's an example where we have a public key a public key in e - is a 42 bite our 42 late 42 byte array so the way that we would represent this in a miracle tree is so 42 48 can be fit into two 32 byte chunks the first chunk would be fully filled and then the second chunk is like half filled and then the rest is padded we can imagine if we had an even longer vector then we would just

keep on adding chunks and then merkel eyes as needed in this case this is just a tree of like depth one there's only two elements a list is our way of doing variable length collections so there are like vectors and that they're homogeneous collection so all the elements have the same type but they're variable length and the one gotcha that we have is that there's a Mac a fixed maximum length for these for these types so the fixed that this limit is part of the data type and so needs to some

examples of this is different transaction types in the beacon blocks those are all lists Committees of validators because the committee size can grow and shrink depending on the total validator set that's also a list and the validator registry itself is also a list again liking the vector we put all of the elements as we set all the elements as leaves when we're merkel izing but the difference here is that we add one additional level at the top and we the reason that we do this is so that we can have an extra node to say what the actual length is so well you may be

thinking so like what it's like how do you know what the actual depth of this tree is or how do you know how many Matt how many elements there are well this is the reason that we have a max length in the written that reason is that we can have a fixed depth of our tree moving on let's see containers we have a container so that we can have it's a so that we can have a way of putting together a bunch of types or a bunch of elements together that have different different types so it's heterogeneous every element has its own type you can kind of think of this like

a key value store where we have the keys and the value is kind of predetermined in their types and eath too so we have like validator records where we keep track of the different data we need for each validator blocks state most data structures he needs to are are these containers so again it's it's very very similar to vectors every element is a leaf in the tree so here's an example of a checkpoint which is the data type in eath - this is a pretty simple tree

there's two there's two different elements EPOC in a root both of those each one would be a leaf the first one since since it's a you in 64 we're only going to be using 1/4 of the forces of this leaf here the rest is padded and then the bytes 32 is using the entire the entire trunk or the entire leaf so where things get more interesting kind of think what thinking about things from a Merkel eyes perspective is when you have when you have containers where some of the values in the container are

containers themselves or are bigger bigger trees themselves so this is kind of the structure you get in ease to when you have bigger when you get to these bigger structures so like the beacon State is like a tree of trees of trees of trees with many smaller sub trees below it yeah and a root I'm give calling this a separate type it's actually just a bite 32 type with some special semantics around it we treat this as a bite 32 but it has the special

kind of ability that we can also imagine that the root is the root of another tree and for that we need to know the type of that of that sub tree so like for our example of a checkpoint earlier the the root sub element is actually the root of a beacon block and it's not just a byte 32 so if we were to like imagine this this tree of this checkpoint again actually the root you can think of the root as containing the the whole beacon

block and why this is cool so like from like one checkpoint you can kind of imagine expanding the data to a higher beacon block within a beacon block beating blocks have roots you can expand that data maybe to a beacon state and like somehow you know navigate all the way to a shard State and when you're thinking about like what this would look like practically speaking you're you could be building like a Merkel proof that could be taking you all the way from like this checkpoint and it would be could provide you one witness that takes you all the way down so you could in within like one request request either some historical state or some shard state that's like that's you would

think would really be far away so like in practice let's kind of see how it's used these are kind of the common operations that you do on it so there's things that you would expect from like standard data types just like getting and studying elements iterating over things seeing if something is equal to something else or greater than or less than these are all kind of standard and then you have your like blockchain specific things that you can do with it and so that's serialization Merkle ization and then like dealing with all like the merkel proofs so so you've actually got like three different ways

of of like looking at this the same data looking at data and you can actually you can have at least three different implementations of of that data so like there's the structural way which is where you imagine like a collection as maybe like a Python dict or a JavaScript object there's the tree representation where you can imagine you could actually work off of a tree directly and then there's a serialized representation where you can deal with just just a byte array but all three of those things kind of are could be potentially dealing with the same object abstractly or the same you could be

thinking of them as the same object there's differently TripIt trade-offs to storing the data in these different ways and this it's really interesting to look at these ways be looking at these three different ways because they have different trade-offs in practice and so when we get to the benchmarks we will very briefly like look at like what the benefits are of using a tree what the benefits are of using like the structural approach and oftentimes like you kind of have to use a hybrid so like we're building this e to client and we're kind of using a combination of all three in different cases where it makes sense so there's like structural

approach we you can represent these objects as like native data types in whatever language you're you're working in and it's great because languages are usually designed to like get out of away and so when you access different pieces of data it's fast it's convenient because it's built into whatever language you're using the cons are that like when you actually go to Merkel eyes this data you have to serialize the data and then you have to like do a lot of hashing so in our experience preview before we were like even kind of thought about anything any of like anything more advanced we had this naive implementation where we would like

Merkel eyes an entire beacon state just an empty vegan state with it would take us 15 seconds to do - just to hash it and we were dealing with 12 second block times it just doesn't work so like the con the cons are big when you're when you're wanting to merkel eyes data a lot kind of the on the other side very kind of very different trade-offs great kind of on the other side of the trade-offs actually you have the tree implementation and the well there's probably there's there's probably several different ways of implementing a merkel there's many different ways of

implementing a miracle tree or merkel eyes data the approach that we went with is capturing the tree as a persistent data structure which and so storing each of the nodes and the hashes of the nodes lit as a linked data structure rather than storing them in an array or something like that we have we have separate nodes with pointers to each of the children and whenever we do an update to a leaf we can kind of cache all of the pieces of the tree that don't change so whenever large parts of the tree you

don't change we can reuse that subtree yeah we can reuse the subtree it's reuse that all all that memory and so this is really great for hashing because once you've hashed something you already have the hash there you just kind of like look at the node you look at the position in the tree that you want to get that root it's very fast to like clone a data structure because since we're kind of dealing with things immutably all you have to do is like make a new pointer to the to the root of the tree and its really great for for sharing data so like in e24 for instance we can store

our beacon state as a Merkel tree and when only a small amount of the validators chain or when only a small amount of the validators change or only a small piece of state changes we can reuse like a vast amount of the of the tree and we can storm many states where it's reusing maybe 50 80 percent of the actual underlying memory the Khans so you're now you're when you're dealing with a tree it's no longer just the same as dealing with like a languages native types and so it's much less convenient and if you're doing this naively the data retrieval requires actually navigating the tree so you know as we

saw in the previous slides the data is all stored in the roots and you usually would have a kind of point of a pointer at the at the root of the tree so you have to navigate down all the way and then if you want to actually like get this unsigned int or get this booming and you have to deserialize the data at that point and then very briefly you've serialized so you're dealing with serialized data you can imagine this is like just dealing with just the the just a byte array that has all the data in it this is great because all the data that we get over the network is serialized in

byte arrays and so maybe you only want to check one small piece of a very large data structure that's sterilized you wouldn't need to like first deserialize it turn it into a tree or whatever you would just only deserialize just the tiny piece of it that you're needing to check and it's really compact you don't need this whole linked data structure that takes up a lot of memory a lot more memory the cons are that you have to navigate this byte array it's against not it's convenient and then you have to deserialize any primitives that you're dealing with so let's I've got one slide on benchmarks it's really like benchmarks smart early benchmarks it's relative and so really I was just wanting to like

highlight some like three big categories or two two categories and and some practical results so we look we were we can look at iteration and this is something that like really favors a native datatype a native piece of data so iterating through an array like a languages native array is going to be very very very fast whereas iterating through a tree is going to be significantly slower because we need to navigate down from the root of a tree all the way to the leaves and depending on how you do it either start at the root again and then navigate down or kind of pop your way along along the

tree and so what we found by looking at our benchmarks is that structural data is like 2,000 times faster roughly then then like a tree based implementation other thing we look at is hash tree root so getting the root of the tree and we look at this looked at getting a root of a ten thousand and thousand large validator set and we found that like you'd expect the tree implementation is significantly faster the reason being a lot of times you have you've cashed intermediate nodes and you'd have to do like significantly less

hashing if you're doing repeated hashing and so we do we do a lot of iteration and we do a lot of hash tree routing and ease to getting the the root of the tree Neath two and kind of you think about like one really high level thing that we're doing is the state transition so we ran some benchmarks against the state transition and just our beacon state as a tree or has a structural piece of data or as a byte array and we found that the tree backing is roughly 10 to 100 times faster so it turns out that our bottleneck was

actually getting the the root of the tree and more so than like iterating over a large validator set and that's it any questions yes thank you thank you that was great very informative but one question which I may have misunderstood when you said 2,000 times faster was it two times a two thousand times faster than previous

solution or between the state tree ants realized or like didn't walk oh sorry it's the structural is a tree backing is two thousand times faster than a structural implementation did you ever compare the byte array like serialized form no sorry these are just comparing the tree versus structural all right I think you for a hash favorite you'd expect the tree would still be roughly that fast for iteration it'd probably be a little closer between structural and serialized um did you sorry for the last question if I can they did you try the actual serialized form like some kind of by Terrenas and so on did you test it not not with the

state transition but just for a duration and hash for you yes but I I think we've been mainly just like focused on on serial sorry structural and hash tree root great thank you thank you so much yeah thank you we go through the last talk [Applause] [Applause]