Tree Types

Transcript

all right everybody um welcome to my presentation on trees so um in the blockchain space I hope most of you are pretty familiar with Merkle trees in general and their constructions and their variants but in this talk we're just kind of gonna run over a couple like we're gonna go over a panda only Merkle trees sparse knuckle trees index Marco trees the trees that did exist in aspect connect and what they were for and then we're going to go over the trees well very briefly the trees that are in Aztec 3 and what we use them for and why they're important so first of all just a rough overview of what a Merkle tree is

the great thing about a Merkle tree is that it's you can think of it it's just the data structure that allows you to store arbitrary data but then allows you to make proofs against data that exists within your data structure so in this example it's just ripped from Google it's the one that I think everyone's really seen if I have data L1 data L2 data L3 and data L4 we have to Hash them together all the way up to the root and then I can provide a proof that L1 exists in the tree by providing a hash of L1 and then providing providing a path that brings me to the root the idea being is that your hashes are some kind of random or Google they're

sufficiently random so the idea is that it would be impossible for you to provide a hash path that would get to the hash at the root of the truth if you didn't actually know what data was in the tree um so that's kind of the assumption that underlies Merkle trees is just the assumption that underlies all hash functions in general so a key data structure within I suppose all private state applications is the idea of an append only Market tree and the reason that we have an opendo numerical tree is if you look at ethereum state

where everything's kind of stored in these things are called Patrician Merkle trees but we can kind of think of them in the same sense if I have a piece of data here and I want to change it if I were to update the data in this index I kind of leak to everyone that oh there's this piece of data here that I'm changing and it was also changed in a transaction ages ago and let's say somebody can then link these two interactions together and that's kind of what you don't want so the idea for stay inside um applications which have private state is that we just have a Merkle tree that we only append to so a piece of data gets added during a transaction that's just like this one here at the end and the rest of

the tree just remains completely unchanged so that's what these two colors are for so we have the immutable part of the tree on the left and then whenever we insert this Leaf here we basically add a new node here we add update this node and we update this node but everything else to the last days um unchanged so as I said earlier a great property of Merkle trees is that we can do a membership proof so I can prove to you that a piece of data exists in the tree and I don't have to run through every single node in the tree to go check where it is you can just provide me something that's known as a hash pad so

what's also great is in this hash path if you can think of it as if I want to get to this route I take the hash of this value and this value that will bring me to this value and then hash this value in this value brings me to this value and then hash this value and this value it brings me to the root I can calculate these two um as I'm going so whenever you're providing the proof you only have to provide these hard side notes because I can actually derive the data in between so to as I've just said to do a membership proof and then take these values hash them together and attach these two values together I hatch these two values together and then I end up with my root there we are happy days

so how do I do a non-membership proof and we'll go over shortly why these why we want these non-membership proofs um or just right now the idea being if in these private State trees if I want to spend the note that exists within the tree I then have a nullifier tree which we use to delete that piece of data so the way we delete a piece of data is by deterministically linking something in the nullifier tree in the data tree so if I go all the way back oops progress to want to delete this piece of information here

I would want to create a leaf in the nullifier tree which is derived from this to make sure I can't spend it twice I first have to check that the nullifier doesn't exist so go back to the section where I was in yeah so how do I check that this doesn't exist an independently train it's really difficult so the idea is well you can do it but it's just extremely wasteful I basically need to check every single node in the tree to check that it isn't isn't the data enter a new data structure called a

sparse Michael tree and the idea of a sparse Michael tree is we instead of adding leaves into the next available index we add leaves into the node at which at the Key of the index that they represent so for example if I was to insert the value 4 into my tree I would put it at index 4 instead of putting it at the very beginning at the beginning everything is set to null or zero or whatever whatever you choose so in this case you can see that index zero if I was to Hash zero with

some imaginary hash function I'll end up with this value 42 or if I have a hash two like at 96 but every key that's empty so one doesn't exist in this tree so at this node we store now three doesn't exist Industries with this node restoring all four doesn't exist six doesn't exist and you can probably see how we can prove something doesn't exist basically by proving that the node had a particular intra index is actually null and doesn't have some known hash value added so I want to prove that null isn't one isn't in there I prove that null is at the is at the index one and then I do my conclusion proof that I was doing already and if I get to the

root I can be confident that the value one doesn't exist so in private state applications if I was to have a let's say an ethereum where all values are 256 bits for to represent 256 values and as far from our culture I'm going to need 256 levels so you can see in this tree I can only represent a possible of eight values which can be represented with um four bits so I have three levels and then the root at the top and for if we were to represent the 32

by words so something is 2 to 56 bits I would need 256 levels and you can kind of see already that if I was to try and do a normal membership proof for something this 256 levels deep I'm having to do 256 hashes and that's a lot especially to do inside a circuit and especially in the case where if I want to do a null membership proof I first have to well if I want to insert something in the tree I have to do a non-membership proof to prove that it doesn't exist already and then update the route after that I've inserted the value that means that I'm having to do actually 512 hashes um which is an extraordinary amount to be doing well on ethereum or inside a

circuit or anywhere it's incredibly expensive so this is where a new data structure comes in and it's called the index Merkle tree so an index Markle tree is an extension of a dependently Markle tree that allows for efficient non-membership checks so I'll get into how it does that very shortly but it allows for us the the key Advantage is that it allows for us to shrink the size of the tree we no longer need to represent every key at the index that it represents so I don't have to store the value 2 to the 128 at index 2 to the 128 in my tree I can just

add it like it's an append only tree but still be able to perform a non-membership check and the way it does it is very simple we extend the tree such that it stores the value the next value so the next largest value in the tree so this is really a pointer and then the index of the next value in the tree so we can think of it that well we'll go through an example very shortly but if everything has been inserted correctly the number anything between value and next value will not exist in the tree because if I have the value 10 here and the next value here is 20 and

then I know that all of the values between 10 and 20 so 11 through 19 don't actually exist within the tree and the way I provide a non-membership check is just by proving that the node that has 10 here and 20 years this is in the tree and we'll get to this shortly it's quite hard to think about without it being visualized so let's say I have an empty tree here as you can see each Leaf now consists of three data points so we have the value itself and then two pointers so this is the initial state if I was to insert 30 I basically put 30 into the tree in the next available index I then lit update my

it's What's called the low pointer node to point to 30 so the next value is 30 and the next index is one so now you can kind of see that if I have a node that looks like this where I have zero as the value and 30 is the next value I can be pretty certain that any if I can provide a membership proof for this I can be certain that the value is 0 through 29 do not exist within the tree and this kind of carries on as you insert values so vinester 10. as you can see 10 just goes into the next available slot I then have so I will then point oh this hasn't been updated yet it's a mistake so what would happen is I point the next value at this one which should be 10.

and then this one here points of 30. so you can see that the pointer from the first leaf changed to be the one on the second leaf a lot of virus to insert oh wait this is all wrong Bruno yes I read this from an article that Michael grin and I've just realized that this should be 10 everywhere almost 20.

that's okay um we should be able to let me just cut this real quick so with index yeah that's true we have this new data structure that gets stored at every leaf and every leaf is a hash of everything in this data structure so you basically will um concatenate value next and next next value together and then hash them together to get your lease value but I'll tell you what value next to next and next value I sure are so and we have let's say the value 10 have a value and it's index zero well the next one let's say and the next value is 20 and it said index one we can then be certain that in between 10 and 20 nothing actually exists because if let's say 15 was in

the tree then the next value would actually be 15. and so you can be certain that from value to the next value that there will be nothing in there so if I can provide a membership proof for let's say the example I gave which was 10 0 and 20 what 10 120 I can be sure that I could use that as the non-membership proof for values in length 11 through 19. and quite hard to to understand just by me saying it so I'm going to give a demonstration of doing some insertions here so this is what the initial tree will look like as you can see every single leaf will have a lot more data stored in it so we'll

have all these pointers and the value itself so I'm going to insert first the value of 30 into the tree so we have this special leaf that'll always exist at the start which will have value zero and the reason for that um and talk about right now is you always have to have the lowest value and your possible set of numbers existing in the trade so in our case it'll be a set of field elements or whatever you need it to be like let's say a set of real numbers where zero is meant to be the bottom bonds of the group and then at the very top you will always have something that's pointing to that um thing that's the lowest and if the last value is pointing to the thing

that's the lowest then you can be certain that it is actually the largest number in the group so you can kind of think that you're kind of you're inserting into this series of pointers that is actually a ring and the group will always be closed um that's the intuition behind having um zero zero at the end here and having and zero at the start but anyway when we insert 30 you can see that we've updated the pointers in the value immediately or the lower below it which is zero to points of 30. so if I as I just said if I can provide a membership proof of something that has the value zero and the next value of 30. I can be sure that from the values 1 through 29 don't exist in the tree so if I was to insert the

value 10 like I am not I first would provide a non-membership roof for this Leaf I can be then be certain the 10 doesn't exist in the trade and whenever we want to go insert 10 I update the pointers and the value below so now I've inserted into the index 2 the value 10 and I've updated this value to show that and the next immediate value with immediately higher value from 10 is 30 so it points to 30. so now using this Leaf I could provide a non-membership for 20 should do here and then if I insert 20 I want to update to this the lower node to point to 20 and then 20 itself will point at what this was previously pointing out which was 30.

so that's that's the intuition for inserting into the tree um so let's talk about doing an inclusion proof there precisely as they used to be but you need to know the film no data this time you can't just have the value and just hash the value in and prove that it exists in the tree you actually have to Hash the entire note itself so you have the hash value next index with next value and then use perform normal inclusion proof that we saw before so we have this pair but then hashes up to this parent that's up to this parent that hashes up to our known are known roots so non-membership proofs I've just talked about them but this is the main optimization

recall from earlier um well I've already spoiled this but if a tree is well formed we can be certain that nothing exists within value and next value um if they were then when we would have updated the pointers and you can kind of see that in this case they're like I can't provide a proof for 30 doesn't exist because there's no nodes here which have a range that 30 would exist in non-inclusive of course [Music] so let's quickly do an example non-membership for the value 35.

so first I want to search for the value that's immediately below 35 and in that case it will be this node here 30 40 50 30 and 4 and 50. I prove the inclusion of this node by providing a hash path for it and then hopefully my circuit will accept it and then once I've proven that this note exists I can basically just check is value itself less than the value I'm trying to figure non-membership for 35 yes then this is true if I am trying to prove that 50 is greater than 35 which is here which is true and then Grant has a check and then I basically as I've just said through the inclusion

of this leaf that is enough for me to be certain that 35 doesn't exist within the tree so yeah just highlighting again this is this is the comparison that you're doing so this is what I've just also talked about already I've jumped again and if I want to insert 35 I just do the normal membership check and then add 35 and then as you can see that all together this was only two Merkel membership proof as was the case with previous insertions um and that's only going to be 64 hashes if you're in a 32d3 instead of 256 and that is the main optimization that we

have but there is another and is that we can actually do batch insurgents so as this is independently tree we know what indexes we're going to be inserting multiple values into if you had a sparse membership tree and you had a range of nullifiers which were all very they're random and they're different from each other you can't insert them you can't insert them efficiently or in batches like by inserting an entire subtree because they're at random different points in the tree and you can't really do the batch insertion if the values that you're trying to insert don't live within the same symmetry but in this case because you know that

there are all going to be in series you can so for example I'm just going to show what a back insertion would look like so let's say we have the state that our tree was in previously and we're going to try and sort of 30 50 16 15 35 even so I'm going to prepare our Production Services sub trade here um I've kind of blocked it off here to kind of show that we have we're not going to insert it just yet but this is kind of the pending something that we're going to be inserting first I'm going to update the low node for 35. to so 30 is going to point to 35 because it's the immediate low nullifier or low node I then I'm going to

update 50s low note um this exists within our pending insertion subtree so it's pretty cheap to do and then do the same for 16. and then do the same for 15 so that would update the leaf over here and then I can just build to the subtree and then insert this subtree all at once so instead of having to update the root every time I insert one of these I just updated the root every time I answer a pointer it's over here and then I can just insert this whole subtree at once so it's amazing for circuit performance because we're doing a lot less hashing but there is a trade-off and it's that

there has to be a node that can provide all of these um well where all of these low nullifiers are and let's say you're inserting a random value into the tree realistically if in the naive case you would have to do an exhaustive search of ultra enormous to find the nodes that you're trying to insert um for the low nullifier note for the node you're trying to insert which isn't great but you can just store some kind of lookup table that links um or sort your the nodes in some other data structure that the node will take um care of to basically increase this performance you're not doing a linear search of everything um okay so that's an overview of all the

trees that we'll be using in an Aztec we're going to talk about the trees that were in asset connect so as I said earlier we have in classic private State um applications we have a couple of append only trees that we always add new data to True new data to and then we have another fire trade to basically spend our notes and delete them so this is a visualization of what all the trees and asset connect look like so we have a data tree that then has a data roostering that it commits to and I'll talk about why why you need this we then have a nullifier tree

and then the D5 tree which stored all the interactions and anytime a defy interaction was spent you add something to the mill fire trade every time and you can see that they're all here with the Define notes in the clean notes and then every time um like the user interaction or transfer was done and spent you also add them to the middle of archery so what is this data root string the idea is you need it to combat race conditions so in our private State applications users are creating proofs on their device it's not all being done by the sequencer at one point in time like would happen in theory when you're ordering a block the block Builder would would know the insertions to be doing

inside ethereum's Markle tree um and it would know what state to prove against whenever your users are doing these proofs themselves the root of the data tree whenever they create their proof may be different to the root of the data tree whenever the sequencer comes to bundle their transaction so with every block this route will change if you produce your proof against one block that's in the past the sequencer is still able to accept your transaction if it's able to find the route at the time you major proof inside the roots tree so it's just a way that allows the sequencer to accept

transactions that were created against steel roots and whenever it's private data you don't have to worry about multiple people spending those notes because only one person can and if a transaction came in before from the same person it spends up now it would exist in the nullifier tree and be rejected but you can be certain that the route the leaf did exist at some point in time using this model so for anything that can be consumed by any can be consumed by the user on their device you're going to have to have this routine to keep track of previous words so I'll say three or just that second on has

a lot more trees as you can see we're doing a lot more complex things there isn't just contract there isn't just default interactions and transfers there's this concept of storing contracts on chain and L1 messages and public data and all that kind of stuff so this is guava trees in Aztec look like there's a lot more of them but all of them kind of serve a very similar purpose to the ones that existed within asset connects and they're they're very similar so we have the private data tree that existed and as they connect on the root string we then have the L1 to L2 messages so we can support arbitrary

message passing we have our nullifier trees we now have this new one which is a public data tree which is a sparse Michael tree and it's basically just to to model a title state so it doesn't have the same problem that we have for private state where we need to keep track of a nullifier trade update values in the public state tree everyone can see it we don't care that people can link transactions together in this case because the user is deciding to make it public um so we can just do updates in place in this tree and then we have the contractory basically tells us that um the contract that you've created a proof for does actually exist and that it has certain functions and we'll dive into

that slightly in a second so here we are the contractually this is a model taken from zexi um another way to basically prove that the contract you're interacting with does exist and that the function that you're using does exist without revealing the function you use what function you are interacting with so this this looks very complicated but conceptually it's not too not too tricky to wrap the head around so on a lot of contracts and that's like three well ATEC is just a group of functions and that is kind of shown over here we have

a tree of functions that are valid for a certain contract so we have the function selector the data about it we have the verification key for that so that's what allows us to to verify the smart proofs that the user creates and there will be a series of these that make up this kind of function tree inside a contract we then have a contract address and a portal is linked on L1 to kind of get hashed together to give us our contract leaf and then we just have the tree of contracts so this looks very complicated but it's really just a contract has set functions and an address rationals together to give us at least in a contractory and then we have lots of different contracts all have this inside of them

and that's what goes into our contractory so another challenge that we got to combat is the size of our nullifier trees so they can get pretty big especially as your protocol goes on your especially since every single interaction that you're doing ends up creating nullifiers who say you're spending messages or consuming State and you're going to start adding adding things to nullified tree so every transaction really is going to just be creating data for nodes to take care of and there's been very interesting

research done by well the polygon Biden team and some of Alex work on our own stated expiring that it goes into an idea of splitting up nullifier trees into these things called epochs and as I've just said consuming data from my pandem new trade ends up adding to another fire Chase so it's going to get pretty big and here's just an example of zcash and it's recent blockchain size and a lot of this has been caused by somebody able to cheaply create nullifiers and so it's really something you've got to prepare for to meet to try and combat the size of your nullifier tree getting too big for node operators because

and you're also going to have some economics and the pricing of creation of these nullifiers is too expensive to do some kind of DDOS attack but it is definitely something to take care of or even think very carefully about um and then we have asset connects it it had a massive ever-growing State size um that well was becoming an engineering problem as well and asset connect has been Sunset recently so as I've just said we want to limit the state of our the growth or null of archery and the way we do that is by having these things called printable epochs and the idea of a printable Epoch is that the node itself doesn't actually need to

store the nullifier tree it can group them all up store the route at some point in time and then the users themselves will be responsible for proving that some nullifier doesn't exist within x amount of epochs so every single piece of data that's created in assec will have the null the appbox that it's created as hashed inside of it so then if you want to spend that note or consume it you will basically have to provide a non-membership proof between epocket was created and the epoch that is in well that you're in now um so here's just kind of something to

give you a quick intuition because it's signs very fancy realistically it's not too fancy so let's say we have a nullifier Trader we've just gone over the industry and we have some kind of epoch tree as time goes on stuff will get added to the nullifier tree and then whenever we progress in Epoch we've taken off our tree at a certain point in time and we added in to this basically previous Epoch tree the node well this basically compresses this entire nullifier tree to just be a single hash in this epoxy tree so the node can then store this hash store this route delete this and then it'll be up to some other provider to

Index this or up to the users to store their own inbox or store that block of the um the leads that they would like to consume and then as you can see as time goes on runoff archery fills up with the battle Park you store that in the epoxy and alphar tree goes back to me smaller so yeah as I just said I'll create a notes have to be tied to an Epoch in order to prove non-membership in the current Epoch you will basically have to prove my membership in all the epochs that have come since and this does support very quite quite expensive but hopefully via some clever recursion and maybe folding schemes or something like that we can get the cost of doing all

these proofs down for the user and it won't be too bad and we can strike some more compromise between what's reasonable for a node and what's reasonable for a user um so there are some as I said some availability issues with this and these are all kind of open questions and infrastructure that we will probably have to create and nodes will not store the passwords it will destroy the roots so a user will have to know this information or another third party will need to provide that for them or another type of maybe some type of archive node in a way and this is very similar to what um a stateless ethereum would look like in general and it might be

something that people will have to deal with um or come to term not so they deal with but it may be the new normal as time goes on to basically limit State growth and there are ways that you can request all of these previous paths um maybe you could do some kind of omr stuff where the server is providing you this information doesn't know what is giving you and this is very very interesting areas of research private data information retrieval um another is like slight issue is that each note is tied to nullifier tree and well each note is tied to a network so

you can slightly it slightly reduces the size of your anonymity sets um a way to get around this is allow you to to claim membership in a range of epochs and maybe delete this but if you're not if your Xbox is sufficiently large this isn't something really to worry about but it is something to be wary of and um thanks for watching that's uh hopefully everything you need to know about trees um yeah thank you