zkAcademy #7: Drawing Merkle Trees By Hand with Lagrange, presented by Union Build

Transcript

[Music] [Music] [Applause] hi uh I'm Shan shinas and uh I work on UPL cryptography like R laabs uh today I'm really excited to talk to you folks about uh a new work in progress which we call as Rec proofs uh uh it's a Merkle Tre based Vector commitment scheme with updatable batch

proofs um yeah so uh let's start from the scratch um um so a Merkle tree is a cryptographic primitive that lets you compute a Shar uh commitment to an ordered sequence of values say we have values from a0 to a15 uh to build a mercel tree what you would do is you would first uh take the adjacent pair of values say in this case a a z and A1 A2 and A3 and so on and you concate them and hash and you do and you do this recursively all the way to the top until you just have just one hash value which is called as the root of the Merkle tree or the Merle digest and uh this is a short commitment to the all the uh 16 values that are

there in the tree um Merkle trees are ubiquitous in cryptography and they have countless applications in blockchains and Beyond so um in addition to just proving uh just Computing the commitment to an audit sequence of values uh me uh you can also compute membership proof for an element that is there in the vector say uh you have an element AI in the vector uh you can compute U so to prove that AI is in in fact in the Spector you would give out a small proof in this case it's going to be logarithmic in the size of the vector uh those values are going to be A4 CL l r r CL L and CR so these values hash values that are highlighted in green and these

values act as a proof of membership for element A5 so when someone wants to verify this proof what they would do is they would just take um they would just take uh Ai and The Sibling hash values and recompute the path from A5 to the root so uh this way they could recompute the digest and as a verifier if I know this digest then I can accept this proof else I can uh reject this proof saying that hey I don't know this uh I don't think this value matches with what I know so um the primary focus of the stock is going to be about updatable batch proofs but in order to build up to that I'm going to show you how to do updates on indivual membership proofs and so that you get a feel for how later

U patch proofs are updated so uh say that arbitrary element changes this in this example say A2 changes by some value Delta all you have to do is to just recompute the uh the hash path from a12 to the root um and uh you just have to see where the proof of AI intersects with this hash path so in this example it's going to intersect at the node highlighted in green and along the path which is CR so all you have to just do is just update the CR and that would give you an updated proof for uh element Ai and the vector um jumping into range proofs uh a range proof is a special type of uh membership proof that proves that a

contigous set of elements are there in in the vector say that I want to prove uh that A3 to A8 is in fact in this Vector what I would do is I would uh naely give out a proof of uh A3 which is going to be the values here highlighted in green and I will also give out the um the membership proof of uh A8 which are also highlighted in green so using these login uh values you can recompute uh the entire parts from these leaves to the root to check if these values are in fact present so uh the verification procedure goes about like this you would recompute uh these blue blue uh nodes in the tree and you would do this all the

way until the top you end up with a commitment and if this commitment is known to me as a verifier then I would accept this range proof else I'll go ahead and reject this range proof uh just like uh following the theme for the rest of the talk uh you can also update range proofs uh so what you would do is say an arbitrary element like a12 changes in the vctor by Delta you would just like the individual membership proofs you would recompute the path from a12 to the root and the places where uh these hash values intersect with the proof batch uh sorry the range proof of um these set of values uh you just have to update those so in this particular example you just update the green nodes

that are along the path from A2 to the root so this would in turn give you the latest up toate Pro range proof um after incorporating the change of a12 so um switching cures little bit uh the um um batch proof is going to be the focus of the stock uh a batch proof is a special type of membership proof um however in membership proof you can uh in in an individual membership proof You just prove a membership of one element however in the batch proof you would prove uh membership of K arbitrary elements simultaneously uh a Nave example of a batch proof is going to be concatenating ke individual proofs U we have a key efficiency requirement that is required for a batch proof is that uh the

individual uh the the batch proof has to be much smaller than ke individual proofs a key difference between a batch proof and a range proof is uh batch proof is for any K arbitrary elements in the vector however range proofs are only for a consecutive set of elements in the vector um existing batch proof uh approaches are not efficiently updatable uh and in this work we propose a way to do it efficiently uh and uh we also talk about we also touch upon the idea of aggregation where when you are given multiple individual proofs you combine them into a single batch proof so uh the contributions in this book are so we propose a new batch proof uh

construction using recursive snarks uh we can update uh the batch proof and logarithmic time and reg generalize this idea to verify map redu style computation even when the underlying data changes uh say if you want to verify U say when you have a set of leaves commented using a Merc tree and you want to run some arbitrary predicate like say uh number of elements that are greater than um uh greater than F and you want to compute a proof of correct computation you can use uh the ideas from this work to uh to to perform something like this uh later in the stock I'll show you a couple of examples and applications of how we use this map Ru style computation to do uh Dynamic

BLS aggregation uh BLS key aggregation even when the data is changing and uh even uh in the context of something called as digest translation so um jumping into uh how things work here so uh let me start with an e version of a batch proof say uh I want to prove that A2 A4 A5 and a15 are in the batch so then of any way of doing it is going to be uh taking uh the membership proof of A2 taking the membership proof of A4 and A5 and taking the membership proof of a15 this way uh you have a batch proof of course it does not meet the efficiency requirement however I would be using U this uh as a

running example to illustrate how our scheme works so when you have all of uh these proofs together you can um any to verify a batch proof uh you broadly need certain set of inputs so first you would need the digest of the mle tree then we need to know the information about the claimed subset that that's in this Vector the height of the Merc tree and and some auxiliary witness I I'll get into details about what this auxiliary Witness is so U given uh the set of inputs we want to be able to uh the verification algorithm should be able to return uh true or false uh if it should return true if and only if uh s is

indeed a sub subset of some M trees of level else whose digest is C and it should return no otherwise so um there are uh in this talk I'm going to give you two ways to do it one is the standard approach which we know and love so all you have to to do is just give the individual membership merel proofs these things act act as an auxiliary witness and uh given the other set of inputs uh like the commitment and the set information about the set and so on you can use these values to verify if this is indeed uh if this is indeed a valid batch roof or not uh the second approach which I'm going to talk about in later in this uh uh this talk is we in addition to the membership roofs we

also use something called as node subset uh I'll precisely uh Define this later however we use another auxiliary information to verify uh membership batch proofs uh in the setting uh let me start uh by giving you an intuition of how uh standard uh way is doing it so uh you would take the membership roof of A2 you reconstruct the path from uh A2 to the root and check if this is in fact valid you do the same thing for the membership proof of AI you reconstruct the path from leave uh to the root and you do this again for a15 if all of these um all of these uh individual membership proofs verify then we do know

that this patch proof is in fact correct so uh obviously this does not need the efficiency requirement because all these proofs are concatenated together so have a large proof size so you can make them efficient by snacking the verification algorithm so uh This Way say if when you pick a a a proof system like R 16 you will end up with a really small uh snar proof that essentially will attest to the fact that uh a uh the values A2 A4 A5 and a15 are in fact in this Vector um however uh an approach like this would has drawbacks first is whenever there is a change at the vector you have to recompute uh the uh the uh the batch proof from scratch um regardless of

whether it's there in the bat or not and the another problem is there is an AI BR on the bat size so whenever you go out of pound there's a this hazle of creating uh new public parameters performing the setup again and so on uh especially if you use something like Crow 16 so um jumping into how uh we verify in our approach say uh s is the set of elements in the batch we Define something called as a node subset uh of for each element each node B in the Merkle tree uh this is defined with respect to the sub with uh to the set s so the way it goes is uh the node subset of uh um is essentially the subset of s

in the the in the subt tree rooted at V so um I'll show you uh illustrate this with an example but um an obvious example of a node subset of the root is the entire set s is in fact the node subset of the root and in addition to storing the meral hashes we also store uh these no node subset values uh in the internal nodes of the the Merkle tree so um say consider this example the set is going to be A2 to a15 so um and you can see that uh you can [Music] see excuse me uh this is an Amber I'm sorry yeah uh uh cons uh yeah getting

back into the uh the slides say that you have a sub subset s uh which is consist of values A2 A4 A5 and a 15 um the node subset of the root is exactly this whole set however the node subset of the right subtree is going to be uh is just a15 as you can see that uh a15 is the only element that is there in the this in this uh subt Tre rooted at CR which is also part of the set s similarly if you look at the left sub tree you can see that you don't have have a15 because a15 does not belong to the subtree and uh and A2 A4 and A5 are the are the only elements of of the set s that are in this subre we can recursively do this all the way uh to the bottom so that uh

you have um uh you can compute the U not subset of all the elements along the way so uh to verify uh uh in our uh the batch proof in our scheme so uh we would first prune out the nodes that are of interest to us so in this particular example uh um what we need is only the only the paths from the leaf to the root we only care about these set of uh uh parts and we can prun out the rest so um starting from the root we would first check if uh if the root can be computed by hashing the left and the right sub child and we'll also check if the node subset of the root is in fact the union

of the node subset of the left and the right uh and then the right tree uh we can do this All the Way recur all the way to the bottom we can do this recursively and check if uh if the the relationship between the root or the parent is consistent with uh the child that uh the the node has we can do this for uh all the way until to the bottommost level of the tree where what instead of uh checking if uh the consistency here what we would do is we would check if the node subset of A2 um of this specific node is in fact the value A2 so uh and we would just check the node subset is the same as the value and we can do this uh and this would

ensure uh the consistency of this these values so um putting this all together as a SoDo code so uh first we would need certain set of public inputs we're going to take in the we are going to take in uh we're going to take in the Merkle digest the set s and the height of the Merk tree so uh just like the way uh we made the standard approach efficient by using snarks we can we can make um our approach as well efficient by using recursive SAR and I'm going to show you how this s code works so the the witnesses that you need are uh to verify the statement uh verify the statement are you need two of uh two pairs one that will uh that is the meral hash of

the right sub tree the the set Sr and height of that tree and the pi uh pi r which proves that this uh this statement is in fact correct and you also need a corresponding value uh corresponding uh set of witnesses which are the Merle values of Cl the sets SL the height and the P which will attest that the left the left sub child is in fact uh is a valid statement um so the verification algorithm goes about like this first you would check if the the height of the uh right sub tree and the height of the left sub tree when you add by one do you get the height of the uh the root then you would hash uh you would

hash uh the right uh chart and the left child concate together and check if this is in fact the the value at this current node and you would do a union of the the node subsets of the right child and the left child and see if this is in fact the um this is in fact the node subset of this node uh the base case just like the way I showed you in the figure when when you at when you are at the bottom of the tree you all you have to check is the value that is present in the Merkle tree is the same as the node subset so that's just checking if these values are the same and in and in in the in the standard case what you would do is you would recursively verify if if each P L is in

fact valid and and you go down all the way to the bottom of the leaf until you end up at the base case and all of these checks work out you return true um to see this in a little bit more the context of a picture uh uh say that you have say that I want to prove uh batch membership of A2 A4 A5 and a15 um these are the moal values and these are the not subset Val values um so what we would do is first we would uh construct this notot proof which uh from the bottom which says that um the whatever is inside that sub tree is in fact correct so the P ll in this example is going to address to the fact that whatever is in this uh sub tree is correct and Pi L Pi lrl is going to

attest to the fact that all of this is correct and so on so using these proofs you would construct another layer of recursive proof which says that P is in fact uh a u a correct subtree all the values and the proofs are consistent and you do all the way until the top you would just end up with a recursive proof Pi so this Pi would in fact be uh is is is the batch proof in our setting this proves that A2 A4 A5 uh A5 and a15 are in fact uh the the Spector and uh and they are in fact correct so uh just like the way we are updating all other merul Tre based proofs you can update um you can you can update our batch proof uh in logarithmic time say that uh in this example if I

changes by some value Delta you would update the witness and you would just recompute the uh the snark proof that is there along this path and this would in turn just give you the most up to-date proof so that's it so um you just take logarithmic uh updates to uh logarithmic uh updates to compute the latest batch proof rather than recomputing everything from scratch so um the key some of the optimizations which we use are instead of using uh instead of using um a note subset we use set hashing and set accumulators and that helps us uh uh do this much more efficiently uh the snot uh we don't need to have we don't need

to carry the entire set around and uh there are numerous uh places to optimize first we can we can make we can ensure that U uh we have the appropriate snar friendly Primitives s friendly hash functions not friendly uh set hashing schemes then the appropriate um backend that supports the kind of recursion which we want ideas from folding and there are numerous plenty of uh uh optimization opportunities in this design space and we are exploring that uh another uh crucial optimization which we use we in fact make the circuits simple by breaking them into two circuits one circuit is for the leaf nodes and the other circuit uh is for the internal nodes all can do is uh you

can put these two circuits together uh the proofs from these circuits in such a way that they are sound rather than having one monolithic large circuit to do this so U we can uh generalize this idea of batch uh computation the way we do it uh to M to verify map R style computation so uh what you would do is say that when you have values from a0 to A7 and these are the merry values so we can uh have a map operation which enco which which essentially Maps the the leaf values a z into specific output and um and we can have a reduce operation which takes the results of map and uh computes an intermediate result uh at the end of the result at the end of the

reduce operation uh however in while doing this we also attach a proof uh so at each uh each node which says that uh the reduce operation uh which the user is trying to do was done correctly and in the the level above you can take the results from the previous um previous reduce operation and compute a new proof seeing that whatever a map and reduce operation that has happened in this subtree is in fact correct and you can do this all the way until the top where you can end up with the result of the reduced computation and at the same time a p proof which add to the fact that this uh this computation was done correctly so uh seeing this in a little bit more uh with more concrete example um you can do this for computing

aggregated BLS Keys say that you have a smart contract which consists of U and memory slots and each slot consists of u a BLS key the goal is to compute um aggregated public key of set of validators that have signed a specific message uh in this case and we also want to compute uh the number of such people uh number of such signers in this uh in this so that we can compute whether there sufficiently many people have signed it and so on and the key thing to note is between blocks then uh the person who has CH ass signed this message could uh could may not be available the next one so the set s could change across blocks and uh these uh this problem is uh um useful in

emerging applications where you want to prove some threshold of um users have signed some specific message so here is the exact public statement which you're approving uh so uh let APK be the uh aggregated public key uh of the BLS scheme which which consists of three public Keys uh at belong to some Merkle tree of n uh n public keys and and the Merkle doist of those end public Keys is in fact C so um to see this in a little bit more action say that you have the public Keys as the leaf uh you can compute the Merkle digest of this tree and say us um sk2 SK uh 4 and sk5 have signed a particular message uh at the

end of the map operation uh each consist of it the map the map results gives the count which is one one one person has signed and uh their uh and their public key so using this you can perform reduce operation uh and this example you can see that the end of rce operation here uh in this specific subtree there are two signers and um two signers and the product of those two public Keys uh is another value you can do this uh and you can attach this with with the PIP proof say which attest to the fact that everything was done correctly in the subtree and you can um do this All the Way to the Top by Computing the the reduce uh operation and also Computing the snar proof such

that you uh you can end up with the the computation which is uh in this case three uh um signers have signed this message and this is the product of the BLS keys and the small proof Pi in fact add us to the correctness of this computation so whenever something changes you you can recompute this uh uh in logarithmic time and this way you can update the proof uh using uh R proofs uh another example which you can uh consider is say that there are n values in the vector and say that you build a mul Tre based on using hash function like H1 um say it's like Sha Sha 256 and let that commitment be C1 and you build another Merle digest uh C2 um using a different hash function like posidon on

the same set of data you want to prove that these two uh commitments were computed using the same uh n values uh this in fact in fact this uh specific application is useful in uh rollups where uh it it might be expensive to verify a sh 256 inclusion proof however a POS based proof would be easier to verify uh you can simply give a proof a proof that says that um uh these two uh um commitments were computed using the same set of data so to see the um just uh the public statement a little bit more clarity uh say the you have M dig C1 and C2 computed using hash function H1 and H2 respectively uh we want to

prove that these were computed uh using the same n values in the same order so uh the map map operation so just like the way we first build uh just like the BLS example we're going to build the Merkle tree using um the mer Tre using the hash function H1 and um we can use the map map operator it's going to be just an Iden operator it's going to a z is going to be just B a z and so on and these values go through reduce where the reduce operation essentially takes the two Childs and uh two uh of the parent two Childs of the parent uh and concatenate them then hash them and you can do this All the Way to the Top while attaching a snar proof that says that

the sub tree was uh the computation the s l then correctly this way you would end up with a simp uh single snot proof at the top it says that C1 and C2 were computed using the same set of values a0 to A7 so uh we performed a preliminary evaluation of Rick proofs we implemented it using plank2 and we observed that um uh there is scope to uh distribute the the pro proof computation and we observe that you you can have 3.4x to 10x faster than standard version of Rec proofs uh our proof size are slightly large it's around 45 KB by it's just a single planky to proof U for Merle tree height of 29 and subset size of uh 2 ra to 14

we observe that our aggregation in fact is slower than Merkel snarks so by Merkel snarks I mean the standard approach which I mentioned using gra 16 uh this is the price which we pay for uh having updatable property however um our verification is around 40 milliseconds and uh and it's roughly 40x faster than Mel snarks but uh we can update uh uh uh batch proofs um in 35 seconds it's 43x faster than the standard Baseline approach and even uh it can be all the way up to 135 times faster when uh whenever you have to uh whenever you have to Recon uh perform the setup again to uh to update the bat size in the

Merle snars so uh here is the URL to find uh the link of the paper and yeah the thanks for listening wow that that was very insightful and I have so I have so much new information in my head that I'm not sure I'm not sure where to but but first off thank you so much for for your presentation uh and it opens my mind to the possibilities of of mathematics and uh how we can incorporate these these Concepts into everyday life

I think there's there's so many applications both in software and in mental computation that if we can adjust and adapt our our thought processes to include these these mechanisms I think we can all think like more efficiently and kind of incorporate this into into daily life so my my question because it's it was something that you brought up a couple of times that um and I've heard before but I'm not super familiar with so I heard you mentioned multiple times uh logarithmic time and how we can we can uh adapt these proofing mechanisms

and uh make them Faster by logarithmic time and then as you as you got further into the presentation uh towards the end you started to talk about the efficiency benefits of of time in milliseconds so could you you talk could you kind of explain the difference between the logarithmic time of these proofs and then the the computation time of running these proofs in practice sure sure sure so uh the by logarithmic time I was referring to the fact that this is the asymptotic complexity so this is the standard measure which we use in computer science it says that hey my workload is is proportional to the am amount of input

data I have so whether I'm doing linear work whether I'm doing logarithmic work that's the thing see when you have sorted values in the vector you can instead of if you want to find a specific value you can do binary search and it just take logarithmic number of steps to do that so uh and in the earlier part of first part of the talk uh I was just referring to the fact that uh in order to do updates in the standard approaches like gr 16 you would have to recompute the entire tree from scratch so that would incur a linear of work however by just putting them neatly structuring them in a tree like fashion you just have to Traverse the path uh from the uh the leaf to the root which is just the login number of uh hops

nodes along this path and that that's what I was referring to in in the when I when I said login updates so um yeah uh uh essentially the the Practical uh uh implication of this is it's going to take let's say that if you if you can do a single uh what do you call it um update from a a specific Leaf to the nde above takes some amount of time then a practical way to aisal way of seeing is like you have to do log in such steps to get the final uh final result you want yeah got it so it's log and steps uh almost operations right to go

from from the the state of the proof before the update to the state of the proof after the update will take a number of steps n and you can take the log n uh to measure the amount of computational time that it takes to update the proof yeah exactly yeah that's that's one yeah that's very nice way to put yeah okay um the other my other question is around the applications here like we've seen these in these proofs in practice you mentioned rollups is is a great example um and we're proving the state of balances across ethereum accounts um what are what are some of the other

exciting applications for this technology oh we are we had we are thinking about numerous applications like for example uh whenever there's an there's an update and you don't want to recompute things from scratch we are thinking about this application for example um let's say that you have some smart contract memory you have certain set of values you want to run saying that hey uh these values can change what is the specific balance I I want to pick the top I want to pick let's say uh uh certain set of people who who have certain amount of balance at this point in time um so that I can have another uh what do you call some some sort of uh reward function based on hey if we have

sufficient balance I'm going to give you some tokens you can participate in my system so that those are such uh ways to think about about uh one one such way to think about uh the applications of uh what I'm talking about there there are much more open problems and we are exploring them as we come along yeah awesome and and I am I'm also curious about the the inputs because we have um hashing functions with there there's so many types of um blockchain architectures nowadays so we have sha 256 hashing algorithm in Bitcoin um there there's so many there's so many

other architectural types depending on the the blockchain of your choice and I'm curious about interoperability between these rollups each of them are specialized for their own use case and from my understanding of of building these Merkel trees we can prove States across blockchains so I I'm curious about about proving states of blockchains with different architectures could we take inputs from one blockchain and then uh have that as the maybe the right side of a Merkel tree take a set of inputs from another blockchain Define those as the

left side of the Merkel tree and then and then we build a mer a Merkel uh tree up to the root of uh using leaves from two different blockchains yeah so uh um this is a a wide open problem I don't think I have a great solution to it yet so whenever there are uh systems that share very similar uh uh kind of tree architecture you can you can think about uh reusing many ideas from here but uh in terms of a specific example which you mentioned uh there are numerous other steps involved in doing it right so first when you take from The Source uh Source chain you're going to transform it into some

other train you need to prove that you have converted whatever data you have that was done that was transformed correctly that's one step and you have to do this for multiple Source chains and then you have to prove statements over this transform data structure so U there are cool interesting problems I don't have a one siiz fits-all solution however whenever uh whenever you see U whenever you see certain uh uh U systems sharing very similar uh tree structure and so on that's where you can find ways to uh um improve efficiency here yeah got it well this this is uh this is

ma just just really informational so thank you so much for for coming on um and really looking forward to exploring some more of these ideas uh did you have any questions for for our audience um for what you'd like them to consider yeah so uh um I spoke about free applications I'm very curious to see what audience have in their mind uh I'm just very curious to see what what kind of applications which they are thinking of which I'm not even able to Fathom it right now that's one touch uh Direction which I want to see what our audience have to say uh and um and and I'm just curious there are numerous design decisions that can be happening here um I'm I'm just wondering if um if

there are any anything which people have a particularly favorite Direction which they think it's useful there are there are so many things you can do you can change the branching Factor you can change the front and back end you can figure out different uh figure out different set of uh snar friendly Primitives uh I'm just curious to see if uh they have any set of uh decisions which is very useful in their application so that I'm I'm I'm just more aware of them yeah awesome yeah so everyone uh everyone who's listening feel free to uh drop your answers uh to to the question in the comments um we'll be going through and uh there's gon to be a little something special for uh the best answers to the question so uh again

thank you so much for presenting this has been been very educational and uh yeah great time thank you it was a pleasure to talk to you folks