Indexed Merkle Trees - Lasse/Aztec Labs

Transcript

uh hello everyone uh today we have a glasses and who will be talking about index America trees and welcome everyone and welcome and the floor is yours thank you so um from from Aztec and we talked about index not the trees for this session um sort of presentation agenda will be as this we're surely going over what is Aztec and why do we even have interest in these trees then go over our Legacy nullifier setup how index trees make sense for us and

some of the intuition of why or how they work and then is essentially we end up with with profit by having a smaller circuits at the end so we can surely for for Aztec for those that don't know we are working on building a layer 2 that's having private smart contracts as it is means that we also end up having a lot of private state that we need to deal with and notify as an important part of this as we'll see shortly and so we need some way to efficiently prove that all of the data is up to date um and yeah we need to do it very efficiently because a lot of the stuff

needs to happen on user devices so it cannot just happen on a huge server somewhere and we've been always trying to find some ways to do and improved more efficiently sometimes is by having your proof systems where the cryptography has just gotten better but this type of change here from the indexed military is more of a engineering fix or feature than actually finding a new cryptographic primitive um so a key takeaway from this is also that you can contribute to like making the proofs more efficient even if you don't necessarily get all the thick photography if you can just figure out hey what if you do this on a

specific part of the setup or the stack so we've been looking briefly at the two trees model um and why it exists this is very relevant for why we're having these trees at all so if we are taking like a full experiment and saying our roll-up state has a state tree where for every slot um we have some value and it has shot through this route um if sag make a transaction he he has a transaction it updates some value industry it could be a balance update it could be whatever so here inserts a value we now have it in this roll-up

block state tree um time flies by all of the rest of the state have been more of the state have been filled out so there's a lot of State values at different slots um eventually SEC figures out that hey he want to use some of the fonts that he deposited in somewhere or change some value if he's doing this transfer on the same like Star slot you can see that as this value was like 300 before so it's 600 now um he's updating the value and we can now see that hey someone changed this value even if all of these values

are encrypted if it's happening on the same storage slot you can just see that hey something change and if we're dealing with something like a a transfer someone will like there will be changes to places the guy that are sending funds and the guy that are receiving funds so we can start making profiles if if this is something we can do and having just one roll up state tree so yeah this was just what I mentioned if data encrypt it if you can if it's deterministic what the slots are you you can still figure out some information about the recipients and the guys that are using the system so the fix is essentially a bit of spoiler introducing these two trees

so what if we we have our state tree but what if we whenever we're doing an update to a specific slot we never write to that slot again um so just like simply don't update slots to address like to have this actually be possible for us we introduce a second tree so we have one tree that is for data so you're storing commitments to data and you have a separate tree that is for like indicating that this data have been consumed or nullified it's often called like a nullifier tree um so yeah terminology we have commitments in one trees a commitment tree a

commitment is some like could be a hash of some data that you're putting into this Trace only the hash is there and if you know all the contents you can spend that that number that commitment and when you're spending it or consuming the data you emit like a nullifier such that if someone tries to spend the same data later on uh this this nullify will already exist so you will catch it as a like a double spend um so if we're growing this out we'll have these two trees we're on the left we have this state tree and on the right we have a knowledge fire tree so when sag is like updating his value

he will just like insert a new value and to this uh the state tree and nullify the old one and the nullifier doesn't have a clear link to what it was nullifying that is like visible from from the outside um so from the outside you would just see okay some data was spent and some new data had been inserted but you don't know uh really doing anything more than that um yeah we insert value in a new slot and we create evaluated nullifier tree just to indicate this has been been consumed um something that's very important for this part to actually work is that you can like deterministically generate the

nullifiers from some of the original state um to say that we have a case where this isn't we just use nullifiers as like a random piece of data like fully random then you don't know like if if I'm trying to spend the uh the same data again I could just pick a different nullifier and then I can perform double spins um so you need some way to deterministically compute it it automate this is that as part of the original state when you're inserting these like data blobs um into the commitment tree you have some Secret in there that you are using to compute the nullifier so if you try to use it again you will hit the same

nullifier um so that was just having these two trees one is for nullifiers if it what was that question or oh let's just continue um so we were having these two trees one of them being our data tree and one of them being our like nullifier tree where okay this is just to keep track of what have been been spent um so in this case we have to the tree that has as many leave the general fire tree will have be a sparse Michael tree which has as many leaves as possible

values um so let's say this is our spot fire tree when we start out everything is set to to be null so there's nothing and then no data have been nullified in this case um yeah we can have like eight elements and if you want to check that a specific nullifier is in a set you just try to like go down essentially the tree to the specific index like the index is the value of the nullifier in this case um so if you want to see that there's nothing in there you go down to see a null if you expect it to be something it could be like a Boolean just devalue itself or hey a

flag that this thing was already spent um yeah this allows us to prove it there is also a null at that point in time so if I can go like all the way down we can also go up and go from like the uh the nullify that we want to prove is not get spent and compute to root uh so this is like a local path membership or military membership if we want to show that like that the value 2 is not in the nullifier tree we can start at like index two in this case and then we just okay then start like doing normal path

or mobile membership proofs from here so we do a couple of hashes if we're getting to the same route as like the current route okay we're good there's no value in there and so we're not overwriting something that was already there um everything is nice so what is the issue with this the main issue is that for this tree was super tiny we had a tree of size like three the air depth which means that they could only contain two to the power of the depth elements and when this was like all the possible values this means that for some small trees you could have like a couple of transfers and then you don't

have any more in there and if you're having these values you want them to spend like a large domain just says that it's harder to uh that yeah you have more space to be in there or you can have more empty like more random um so when we're dealing with this in like a real world scenario so for people that don't know Aztec had this product that was called at the connect which allowed you to do private transfers and so on and in that setup we were using this fast Market Streets and to make it like practically work we needed to have a tree of Dev 254.

um which means that we need to do a lot of hashing to do these membership checks um so for yeah every time we wanted to check that hey you're not double spending inside something you would first do the membership check from that hey the value is null at the moment and then you would insert it and compute the new route so you end up doing 508 hashes for every insertion so this becomes an issue when you start doing Roll-Ups of larger badges so we in our case we could it was not fully if a thousand were around 900 transactions in a Bash but every batch could compute produce

like multiple Northern fires notifiers when you have these 500 hashes per nullifier it quickly adds up being like a thousand houses per transaction and a million hashes for for the entire roller overall this just means that the roll up circuit itself has a shitload of of constraints and you need a very powerful machine to actually compute it so um what can we do about this because this is our main bottleneck at the moment and when we're moving to have a smart contract instead it will only get even worse as nowadays more state to deal with

um so we needed to figure out how to do something better and the initial idea is just how could we get away with doing list hacking and can we do it so that we can still perform these non-inclusion proofs to make sure that you don't double spend anything and there's a pretty simple idea that we would have liked to have figured out ourselves but it's also okay to to get some help and so there's was this idea from from David that hey what if you um and he's saying this that he I have this new idea for a Mercury what if you store a linked list of of the leaves

and such that they can be like ordered numerical numerically so you can more easily perform these non-membership checks um so we go over this idea and this is what we have called index murgatories as you just keeping track of the indexes uh but you could also think of it like a successor um success on Military so the key idea is what if we use a linked list as all of our nodes and then we prove that something is not in this list so if we have a linked list of um sorted nodes and then you'll have like node one is pointing to node two which is like it's

successor or the next highest value so the highest the smallest higher value essentially and when you have this like link it means that if Node 1 is pointing to node two you know that there's nothing in between them so if you start having uh having actual values on these say we have one and ten then we know that okay there's nothing in between so two to nine they don't exist in this this tree at all um with this idea hand so daddy is taking also from from this paper and but with this like idea at hand we can start designing a more uh interesting tree

that is a bit more complex to use than this Mastery but give us gives us some nice properties so the idea is that for air all of the leaves in this index medical tree will keep the value a and essentially a pointer to the successor and then we can just append these as an appendicularly Mercury so it will since you'll be used as a list you just insert um insert into next available spot and then you need to go go back and update uh previous leaves um but we if you have this at hand okay

um so the initial State both Central look like this but you have your tree but instead of having just this hey these indexes and all the values are null we now have um like free values for for every node you have the value itself and then they point us to to the next to it to its successor um things someone needs to mute or okay so this is the initial State and while all of them these are marked as zero the first zero zero zero is like a special

class here and I said oh both the minimum and the maximum value so if we want to insert into this tree as if we if we want to insert 30 for this case we insert it into the next spot so this will be index set one and then we need to update the um it's like predecessor and the predecessor in this case would be the first value so it will now be pointing I don't know if you can see my mouse but if you can see my mouse you can see that hey uh index 0 is now on have value 0 is pointing to index one with value 30 as it's a 6000 and 30 is pointing to zero

zero as its successor if you're pointing to zero zero as your successor it just means that you are the last largest value so you're simply pointing them pointing to the beginning um so this is how people can do like one insertion if you're inserting again afterwards as they've been setting 10. so when we are inserting 10 we first need to do this check that hey 10 is not already in there which we would be doing by jumping to uh going down the tree here showing that we have this node intercept that has value 0 and the next value is value 30.

okay 10 is between 0 and 30. so we know it doesn't exist in the set already we can do this like erase check essentially and then we just inserted an update um update the predecessor tool to 0.2 to 10 now so you can see I the first value is now pointing to 10 and 10 is pointing to whatever uh what's the success of um its own predecessor that might be a bit hard to figure out the word again so essentially when you're inserting you will take the the values from um the node you are inserted right after

and use them as your new successor so what you are pointing to so if we're jumping over them like as this linked list we'll start at zero we can see that okay we should jump to index two so that's 10 and from there we jump to index ones that's 30. so we have 0 10 and 30 in this set um then we can keep on doing these insertions where we again just same flow uh does it mean that every update kind of Max and modify to nodes of the tree and so we

essentially yeah you will have that every update does this but you can also do a batch in searching insertion that will show yeah I think should actually be in in just a second um we can go over how you can do some of these patching session as essentially to do this in sessions you need to know the full data of the uh your predecessor so in the old one you just need to kind of come with hey this is my Notifier nullifier now you need to know some more information about hey this is my nullify here was some of the earlier stuff um and I'm not interested so that you need a bit more access to information

but the stuff that the circuit needs to do to perform the inclusion uh can be can be easier and to do this or maybe let's say computational um so when you're doing the inclusion proof of Note 10 in this case uh we essentially do it just as before like a mogul membership um all the way up to the root okay no 10 is in there and we know that way 10 is also pointing to 20 so there's nothing in between as yeah this was just

refresher from earlier if you had one in ten there was nothing in between so when we have 10 pointing to 20 we could insert any value or any value between 10 and 20 do not exist in the set already and all we need to do to do to membership is just okay the smallest of these nodes so One path of the three and the values of this um of this node um so if we do and always something should be 11 to 90.

so the idea is if we wanted to insert like dude inclusion uh prove non-inclusion of 15. from this case we have our current value was 10. so we need like 10 should be less than the value we're trying to to prove it's not there and the next values will be larger than and 15 is more than 10. it's less than 20 we're all good in this case we could insert it and yeah we're doing this through uh two range checks then um to prove this inclusion and the mobile path uh

it's a nice thing by having this case where we can just append new notes is that we can change the size of the tree so um instead of having this like spasm murgatory but we had a size 240 yeah 54 we can have the same size as our like commitment tree so all of the data can only be nullified once so we can make the nullify tree the same size as the this data three of the commitment tree which in in our case was 32.

so in this case to do the inclusions uh during inclusions we can just need to lose like 32 hashes up and two range checks then you have done the non-inclusion uh that's a lot easier than doing like 200 uh 54 like hashes but we also have a bit more nice ideas around this with uh because you're not doing like random insertions anymore we'll be doing like structures insertions uh you can essentially compound multiples and insert a subtree at once so this means that you could do a batch insertion insertion

um and when you're doing dispatch searching you have some of these hashes that you needed to do normally and now you essentially amortizing them over all of your batch and so you can get away with doing like a way less how she's overall if you have dispatch insertions and so if we try to insert a patch yeah so we are going from the tree we had before and then we're saying we want to prepare a sub tree and insert a 35 50 60 and 50.

and so insulating this soft remark with a degree Square um initially we'll need to point to uh like all of update what was already in the tree so these like it's sometimes called like a low nodes or the predecessor um so in this case when we're inserting 35 our low node would be the note 30 the marketable screen so we need to update that value or update its successor to B4 now so the index in is 35 value and we need to set the values of our 35 node to be zero

and zero as 30 was the largest value we had before so we are doing some updates here on the existing tree and some only in our subtree after this we can insert 50 50 is larger than 35. so we need to update stuff that are already in our like pending insertions and for 60 same same stuff again we update uh values that we have inside our uh our bedroom sessions and then when we're getting to 15 we're doing the to check all the way oh

we're doing this like updating the the note with value 10. and so throughout this process we had to update some of the values in the tree existing tree and change values in our like pending subtree but when we have been going through all of these uh this process and updating the pointers also in in our pending tree we can essentially just insert the whole sub-true at once um so we save a lot of hashing as you don't need to Hash all the way up for every every node now you're just doing once for that entire subtree and so if the light to the subtree the

more savings you're getting from here um yes this was essentially how you like insert uh doing dispatching sessions um so I hope that helped a bit on the question from earlier uh in in Rico did it held on on your question yeah yeah it does thank you okay and so I think this is actually like the plant ending of this um mobile drawing out so the the main thing that we are winning from here is saying okay what if we could introduce some structure to how we do like

nullified trees while still Computing still having the same um some of these uh while still having the same properties to hey we can do uh non-inclusion checks and hopefully do this pretty easily and cheaply yes the main thing was introducing some more structure and how we can do these checks um essentially yeah because if you have the more structure we had the the more information we could like deal with outside of our circuits so finding these like predecessors we can do that all all of that stuff we can deal with outside the circuit um but then have that the circuit itself

need to compute less information um yeah I think this was essentially what we had had planned for this we have a like a Jupiter notebook with some examples that people can play around with I will add it to probably add it to the slides and and then when they get published we can play around with it with adapter one um is there any questions related to this or something that was like super unclear from how I described it um I have a question if I can maybe just ask here and like this voice thanks for

the presentation by the way it was very nice um so maybe you could share where that information is stored like who's accessing who has access to what information and I mean the root and the leads uh yeah yeah okay so in um when you're dealing with these cases so the um the commitments and the nullifiers are all broadcasted on chain in at least in our case which means that any node that is have access to L1 State could essentially rebuild these trees as I say you're you're running a node when you see this commitments coming in

you just like add them it's append only so you just add them into the tree when you see the nullifiers come in you uh like also add them into the tree but you need to do this like small uh updates to the state as well and then you can compute the state locally and see that hey you're getting the same thing the idea is that this circuit and sure make sure that if you're doing updates the same way this is the result that you set it up with but you can perform the checks locally as well um because it makes sense so basically everything is in plain text right uh essentially the the nullifiers are yeah essential in plain text yeah as it

did notifies it just seems like random random garbage that you're spinning out you just need to make sure that if you try to nullify the same um same commitment it will always produce the same nullifier and take for commitments you will just see like the commitment itself not the data in it so the data in it will be held by like the user that owns that data or is what you can so if I like have some funds in the system everyone can see the commitments but they don't know whose commitment this is and I have the data that is like inside those commitments so when I want to spend it I just

prove that hey I know the data that is part of these commitments here to nullify us and they are not already like have not been spent before and then yeah are broadcasted so basically as a user what I want to make um I want to spend something that hasn't been spent before I would ask assuming that I don't keep the state of the tree like all the leaves myself I would ask uh some node for the that on the leads that are needed to reconstruct the vertical path and so you would yeah you do that for your

um like your your commitment data so you would probably hold that data yourself um so when you're doing commitment uh inclusion proofs they don't need to happen with the current state the nullifies the solar ensuring that hey this thing haven't been before so you can do inclusion proofs for your commitments on like uh Old State which means you could when you are receiving the funds you could just store the the path and put it say it's on your hard disk so you have the information right at hand and in our case we have that you are doing the inclusion proofs for your commitments

and then you have just have the values for the nullifiers and then uh there will be this the idea is that we have a Federated um improving Network which will essentially be okay let's see the nullifiers and they will then be able to find their they have default state so they can just order for the notify tree so they can find the predecessors and perform the insertions and thanks uh it doesn't it have more computers yeah it adds some more performance requirements on the Note side because you need to know where uh these prior like uh notes were so in in this past Michael tree uh world you

only need Supply no the nullifiers that you are inserting and so you have like 32 bytes of information per per note that have been inserted um and our case you need to know also yeah the next value so you have a bit more information per node um so you add you have some more stuff there but you have a lot less hashing to do uh when you're doing updates of the trees and since we're doing like uh snack friendly hiking it can it can quickly add up if you certainly need to do like fact off 10 attaching um on the second question how does how

does the search happen for finding the new nullifiers for a non-membership uh brute force and so essentially you um yeah you could do Brute Forces probably one of the the easiest way to do it um elsewhere it is essentially a because it's a linked list you can essentially do like a any of it it's almost like a sorted linked list that you can have so you can just do any any like a binary search uh if if you want to do that [Music]

um um yeah because like you know all of the the leaves so you can just find a research your way through it um hope that helps a bit may I ask if there's an implementation of this variant of um yeah yeah we have an implementation like where's it easy is to send links as the they are available for people just to add them at the end of the slides how do we do a linear search intersect finding uh so you don't need to do the search inside the um

inside the circuit you can do the search on the Node and then this for the circuit you just say hey here is the loan no node and prove that this is actually low node so you're doing all the like the the complex stuff or as much as possible doing that outside and then you just say hey here's what should be the the answer and prove that it's it's the answer and but we have yeah we have an implementation of I'll find a link to it uh otherwise it could probably be a bit hard to find but

in our crypto library for riddenberg there should be a um an implementation of it and there's also some implementations of some of the other ones um or the standard one cool um maybe explain again why the requirements for the depth of 254 is not needed anymore and now you're using 32 oh yeah okay and so in the 200 you essentially needed to cover the entire like space that you notifies could land in um so if you're doing nullifiers through

hashing you would often do it to like say Peterson you're doing you end up with just a field element and if you want to do it uh just that it's very easy for you to do a in a membership you can use the like the value of the nullifier as the index itself because then you know exactly where to look up the value but then you need your your tree needs to be large enough to contain all of the possible values so that's why you had this like large tree and we can live with this smaller tree and because we can do like this append only and then we're just saying okay the node will find till like a leaf you

need outside of the circuit and then you just prove uh that if you were inserting like 15 for example earlier that we had this node that has value 10 the next one is 20. um got it so so we only needed as many like our another file set practically uh so this set of possible nullifiers is the field size so that's like two to 254 but the set of like possible nullifiers is smaller as you could only have one nullifier for every like commitment that have been inserted so you will never actually fill out the entire

um the entire thing and the range cost should be in equivalent yeah so the range cost in this case you could say that as long as they range past we had two rain checks so as long as they achieve more than 100 hashes uh then it's cheaper in general and then if you start doing the badging then it became comes even cheaper okay um but yeah I'll add some of the links to the code at the end of the the slides um before they go up

any questions here at the end or okay no more questions Okay so thank you that's it for the great presentation thank you so much and and thank you everyone for attending and yeah so see you next time okay thank you bye