Reckle Trees - Charalampos Papamanthou

Transcript

hello everyone today we have babis who will be talking about record trees so you can ask questions at the end of the presentation so H feel free to start when when you want okay thank you Vivian uh I'm very happy to be here thank you for the invitation today I'm going to talk about research that we have been doing at l Grant where I'm spending my sabatica from yel University as a chief scientist the talk is about recal trees so recal is a combination of recursive arguments and merel trees so this is a combination of these two words and um if

you have interest in any of or both of these two cryptographic Primitives I hope you will be able to learn something from my talk today just some things about recal trees um so this paper will appear at CCS 2024 it's a a cryptography conference uh in Salt Lake City at Utah in November and also it serves as the main component of the ukl technology that was recently launched at l Grant which is uh a hyper parallel ZK coprocessor right so let's get right into it um okay so what is a Merle

trade so I'm hoping most of you here are familiar with this foundational data structure in blockchains it is used to compress State um in of the blockchain um with the ethereum mer Patricia try for example so etherum merel Patricia Tri is a type of Merkel tree so since recel tree trees are based on Merkel trees I would like to make sure everyone is on the same page so I like to present what a Merkel tree is and take it from there okay so Merle tree is a way to compress an array of data say from a z to a15 here into a succinct

cryptographically Collision resistant digest and the way to do that is to build a binary tree on top of this array of data and then then start hierarchically Computing a house of every relaf in pairs so you compute the house of a z and A1 the has of A2 and A3 and then you continue and you apply this computation in the same way recursively up until you reach the root of the tree and this uh C digest is what represents the array of data from a0 to a15 in a collision in resistant manner meaning

that it is very hard to find a different array of data that is going to have the same cryptographically uh Collision uh the same digest SE okay why Merle trees are interesting one of the main applications of Merle Tre is this notion of a membersy proof so Merle trees will allow you to prove that a specific Leaf of a mirle of uh a specific element of the array that has been accumulated with a mirle tree is present in this data structure by just having access to the digest of the Merle tree so how you do that so say for example you want to prove that

A5 is part of this digest that you computed before you don't have to give the rest of the elements and recompute the digest instead what you can do is you can provide a logarithmically sized membership Pro that consists specifically of the green elements in the screen so A4 C lrr and so on um once you have this logarithmic sized proof so to say you can try to use A5 and this proof to recompute the digest C that we saw in the previous screen right so how you do that you kind of recreate this hassing procedure where you compute the H of A4 and A5 then the

output you has it with what was the right child this right sibling of this proof and so on and so forth until you read the root once what you're Computing equals to the digest that you were initially given then you can be assured that A5 is part of the Merkle tree that was computed and resulted into this digy now what we're really interested in this line of work is the notion of datability of proofs okay so imagine you have this membership proof which consists here on of this green hes how can you update this proof when

an element in the array changes so let's see here an example so say for example let's consider array element a12 okay so now imagine that you want to update the membership proof for array element a five when a12 changes so let's take a12 and add some Delta to it okay as you see you can easily identify the elements of A5 membership proof that will be affected due to this change in particular the elements of A5 membership Pro that will be affected from this

change is only going to be this right has labeled CR okay so in logarithmic time you can actually recompute the has the path from a12 to the root and you can actually compute how this CR is getting affected right so you can recompute this so so basically the only house of A5 membership prove that it's being affected due to a12 changing is is the CR you can update it in this way and in logarithmic time you can update the membership proof of a file okay so this this is good so let's so what I want you to remember from the

slide is that in logarithmic time if I give you members a mirle membership proof you can update it if any other element of the Merle tree changes okay so let's look at a more complicated proof that is called arrange proof arrange proof is a single proof that can be used to prove a range of elements so consider the range from A3 through A8 okay so how we can prove that these elements are part of the digest C so the way it works is you can give the boundary proofs so two boundary membership proofs in this case it is the

boundary membership proof for A2 which is this membership proof and it is is the also the other boundary membership proof for A9 which is this proof here okay so given this two proofs you can recompute the digest by using the elements in the range and this boundary membership proofs so you can run the hassin scheme and you can compute C so if this proof verifies that means that indeed a through A3 through A8 are part of the Merle tree represented by this digest C okay so again now this talk is going to be about updates so how can we

update the range proof once an element of the tree changes okay so say you have A2 again you add Delta to A2 you can easily identify which elements of the range proof are going to be affected and you can do the same thing you did before for the membership roou okay right so in logarithmic time you can update the range proof as well so now we're going to move from simple membership proof and range proofs which have structure to something that is more unstructured which what we call a Bots proof which is relevant for a blockchain applications so Bots proof is a single

proof to open k arbitrary elements simultaneously so the not in a range they can be arbitrary elements in the Merle tree that creates complications so of course you can provide a Bots proof by providing individual membership proofs of every element in the bats but this is going to be a large buts proof If you have K elements you want to prove Logan size the membership proof it's K * Logan we don't want to do that we want to have a bat proof that that is independent of the size of the elements that are included in the bot

proof and the contribution of this work is to provide a Bots proof that can also be updated efficiently you see the same algorithms that apply in range proof and membership proof for updates completely break down when you try to update succinct Bots proofs so this is going to be the focus of this talk how to compute a BS proof in a Merle tree that is succinct but is also efficiently updatable okay so what is recal trees is a b proof using recursive snarks and Merle trees it can be updated in

logarithmic time and an extension of our B framework that I'm going to present can also be used to verify m redu style computation on Dynamic data for example I want to verify the number of elements in a merel tree that are greater than five so we extend this idea and we propose this recal plus trees and with this Rec trust trees we can support very interesting applications our Dynamic aggregate BLS key and dynamic digest translations that I'm going to talk about u in this uh in this talk later okay so let's delve into the technical

details of our bot proof but to begin with to understand the problem let's look into how an inefficient BGE proof works like I said if you want if you have a batch of elements A2 A4 A5 and a15 an in efficient badge proof can be just provide the individual membership proofs of all the elements so if you take the union of the membership gr of all these elements these are the hes that you have to provide right but unfortunately this you know as you see um is not in it's inefficient because you have to provide uh all the all these

casses right now how would you verify this inefficient Bots proof so I want an algorithm that is going to take all this hes and it's going to verify whether the claim claimed buts is part of the Merle tree so the input to this algorithm is a digest of the Merle tree a claimed subset of the Merle leaves the height of the Merle tree and some auxiliary witness okay so the output is yes if s is indeed a subset of some Merle tree of L levels whose digest is C and no otherwise now the verification algorithm

takes this we as input right which is an auxiliary witness so in the standard approach this we like in the previous appr that that I show to you this we is just Merle membership proofs right so in our approach we're going to put forth a modification of this algorithm that that is appropriate for our setting where the Merle the we contains not only Merle Merle membership proofs but this notion of a node subset okay so let's see so the standard approach will just the verification algorith the standard approach will just take us input all these meral membership

proofs and we'll just recompute all these hes until it reaches the root of the Merle tree but in our approach what we going to do okay so this approach right so to make clearly the standard approach has the problem of inefficiency so the only way that we know of to turn the standard approach of verifying a budge proof into an efficient B proof is to snark the verification algorithm that is to to to compute a proof for the computation of the verifier needs to do the witness in this proof is going to be that all the meracle membersy proofs but the final output due to the suance of

the snark the final proof due to the suance of the snark is going to be a very very small bprw now this satisfies the notion of a small BS proof uh but one of the problems with this is that whenever something changes in the tree and you need to update this bch proof this will have to be a computed from scratch okay so this is not good right so this this requires linear time in the size of the B right also the B size needs to be static so that to avoid having a different circuit for different sizes of of bues okay so so what I'm saying here

is there is a way to have a sucin buts proof by just snarking the verification algorithm of the standard approach this gives you suine buts proof it's really bad for updates and you have to stick to a static B size okay so we are we in this in this paper we we we're solving the last two problems so how we do it remember our witness now is going to be not only the miracle membership proofs but also this of a node subset so assume s is the set of elements in the bat the node subset of a node V with respect to S is naturally defined as the

subset of s in the sub rooted at V so the node subset of the root with respect to S is the subset itself s because the root includes all the elements of any subset of the tree okay so I'll give you an example here so say for example uh our BS is A2 A4 A5 and a15 right so we're going to compute the node subset of every node of the Merkle tree with respect to this blue elements so clearly CLR is A2 CLR L is A4 A5 and you can do uh you know you

can easily follow the unions and you can reach the root where the not subset of the root is all the elements so now like I said I'm I'm I'm ex extending the witness of the verification Al to also contain this miracal subset this node subset why because I want to express the verification algorithm of the buds as a recursive algorithm right so the way now I can verify that that that the the the Bots proof is not only I'm going to check that I'm going to start from the route and I'm going to say look I claim that A2 A4 A5 and a15 are subsets of a Merkle tree that is

represented by the digest C okay so what I need to check now is that c is the has of Cl and CR and also that the um the the not subset of the root is the union of the node subsets of the left C and the no subset of the right side and then I'm continuing doing the same or basically I'm saying uh right so I need to check that CL is the H of Cl and cl R and the not subset of Cl is the union of the not subset of CLL and the not subset of CLR so I'm continuing like this this

is how the verification algorithm works now and at at some point I'm reaching you know the last level and the important thing so I'm doing all the same computation for levels but when I'm reaching the leaves what I have to check is that the leaf it's the same as the not subset A2 right so this would make sure that I'm not giving random elements for the subset right so I'm giving elements that are actually parts that are leaves of the Merle tree okay right so again I haven't talked anything I haven't told you anything about snack so far I just presented a different way to run a verification algorithm on a Merle

tree given membership groups and this uh and this not substance okay so now we take this idea and we use recar snarks to compute this SP proofs right and let's see how it's going to work so the public input of our snark is CSL which means that s is some subset of a Merle tree of L levels that is represented by the digest C now the witness for this public statement is CL SL LL and pl and CR Sr LR and PR meaning that you know PL is a

proof saying that SL is a subset of a Merle tree represented by CL of L levels and so is for the right okay so the computation of the snark circuit that we have built does exactly that so it checks the levels it checks the that c is the has of Cl and CR this is the Merle tree it checks the union of the sets and then it says you know if you are at level one and SL is not equal to empty set which means that this you're at the leaf that is part of your bats then you need to check that SL is CL in other words that you're not giving random elements part of the BTS

but you also you actually giving some elements that is part of the Merle tree and you're doing the same here and if L is greater than one and SL not equal to zero then you you call you verify the statement on the left and then you verify the statement on the right right and then you through so this is basically the basic circuit that will produce a succinct BS proof uh for a Merle tree of digest uh C okay so let's go see now how we Implement that okay so we we going to start from the bottom and we're going to start Computing these proofs for the

first level once these are computed Computing a proof for the for second level then for the third level and finally I'm Computing the proof P at the at the root level now one interesting thing about this is as I have shown here this proofs can be computed naturally in parallel in a distributed fashion so at the first level you can go ahead and in a distributed fashion you know assign the the left one little subre to one worker one little sub to another worker all of these workers can run in parallel once they complete they push their proofs to the next level that is being

used all these proofs are being used to compute the the proofs in parallel the next level and then the next level so in theory we can compute this Parts proof in logarithmic time assuming we have a lot of parallels right and this is something that we're we're doing a lot in our uh distribut architecture of like gr okay one other thing to notice which is one of the main main points of this work is now that we have produced a bat proof that is exin so P at the root is exin but also is updatable Right which we didn't know how to do before so for example now if you go and uh change A5

to A5 plus Delta not everything needs to be recomputed for example the right sub tree doesn't need to be recomputed at all what you need to do is just update the proofs the recursive snark proofs PL RL plr PL and then recompute finally the proof at the root Pi okay so all the right sub three is not touched due to this the computation to update this BGE proof is logarithmic so not only this is a highly parallel computation it's also updatable

okay so now some optimizations we do um we using set accumul instead of node subsets right we want to have fixed size circuits so we cannot afford having actual sets uh going into the circuit so we represent the sets as set accumulation and in particular we have come up with a specific hbas set accumulation for efficiency which we call canonical hassing okay so how do we take now this idea and we push it forward for more complicated types of computation so we're going to show how we can support map reduce computation

with reel plus trees so what happens is we um right so we we still have a Merle tree but say for example we want to prove a statement of the type this is the output of a mapu computation on a Merle tree whose digest is C so what we can do is we can extend the circuits the recar circuits that we have with some logic that is representing the map and the reduced computation that will come alongside the hassing that proves membership in the tree and we have map again executing at the base level and then you have reduce

executing at the intermediate levels right and then we can have this this proof that this is the output of the map reduce computation of a fixed map reduce computation now we will'll saw two um applications of this map produce uh framework one is this notion of aggregated BLS public keys so say you have the public keys of end validators that are stored in a smart contract and the goal is to calculate the aggregate public of a subset of validators s right and the upset Tes can change across blocks and this is useful in emerging rear hold

systems now the public statement that we want to prove is that APK is the aggregated BLS public key of T public keys that belong to some merel tree of n public Keys whose roote Merkel digest is C so you have a Merle Tree on top of all the public keys and you want to prove that if I give you a BLS public key this represents a subset of this some subset of this public ke sub the lives in particular a t size subset okay and of course as signers and notes are coming in and out you want to be able to keep this proof updated right

so how would you update this proof without having to recompute say for example one node leaves and you want to prove but now this is an aggregated public key of T minus one public key so how can you ially update this Pro without having to recup it from scratch so this is something that Rec plus trees can do the idea is again you you H the trees so you have the SM tree of public keys and then you you basically have a map computation that picks a certain subset and the reduced computation what it does is just multiplying um you know the the the children the children public is and adding their counters right so here

counter stays the same because we haven't include G to the sk3 in the subset and you continue like this you output a proof again counter stays the same because there's there's nothing else in this left sub tree you have a proof here and then finally you have the proof that gsk2 sk4 sk5 is theu keys of is the AL of three public keys that are part of the Merle 3 that represented by this digest C okay and of course all the properties we talked about B proofs hold here the proof is succinct it's highly par can be computed in parallel time very fast and it can it it is easily

updatable okay another application that that that we we we investigated is this notion of digest translation so imagine you have n values in a vector and we have a miracle digest that can be computed with expensive has function for snar 56 and a miracle digest that is computed with H2 a posidon has which is cheaper so you want to have a proof that H1 and H2 are hes of the same set of elements but with different H functions right why you want to have that typically you know ethereum mer Patricia tries do not use use the posidon H

function which is good for snarks so if you try to run something on the Hing scheme of mpts it is quite expensive so sometimes might be useful to have a mapping of data structures from ketak or Shad 56 to Poseidon so that you can execute queries faster on the posidon has uh data has data okay so but you need this proof of consisten right so you need to make sure that you're Computing the on the same data that is represented by some other house right so uh again this this this is can be done with with with with this notion of

of map reduce and is easily updatable and computed in a highly power fashion so again the the the public statement we're proving is that merel digest CN and C2 computer using has function H1 and H2 respectively corresponds to the same n values all right so right so here it's it's it's it's it's similar to adjust the B prooof actually to this application because what you need to do is instead of computing just a single H now you Computing two hes and you end up in the end in the route with two houses okay great okay so I'm going to show you some preliminary evaluation uh so we did this implementation with plony 2 and we

chose plony 2 because this is one of the fastest recursive snark proof systems that exist that are open source right now H so the distribution of reckle trees led to three from 3x to 270x faster than just standard uh record Tre so have like building a distributor architecture for doing this proof computations uh some concrete numbers the proof size is 112 kilobytes the B proof size and I'm going to give you some numbers now for um n is the size of the miracle tree and S is the size of the butts we're trying to prove so aggregation

time is 123 seconds for these numbers this is a little bit better than hyper proofs and just grow 16 Merle trade just a standard approach for for computing a Bots proof um so verification is this very very fast is 18.2 milliseconds this is a up to 1,000x Improvement right and the update of a single proof is 16 seconds approximately a little less than a second per level we spend so this is uh from 11 to 15x compared to just you know recomputing the whole bu proof from scratch using approaches like hyperproof

or or Merle Okay so some some um results about reel plus trees um so one of the things that we observed in this digest translation and um and BLS aggregation baselines we trying to implement them with with with a monolithic circuit we will quickly run out of memory I mean we've had many memory issues so so for digest translation for number of leaves to to the 21 we have ketak and Poseidon we have an estimation of being 200x faster and the updates are two uh 12x faster uh right the reason I'm doing

estimation here is we can run our stuff but we can't run the other stuff so we we we had to estimate and um for BLS key agregation um the updates were around six times uh better um and we were a little faster for large butt sizes so I mean the aggregation there was a little bit slower but uh what what we what ends up happening is as as you increase the size you run off memory in the other approaches and we become a little better but of course you you have the benefit of being able to update this which is the main the main thing here right that that you're able to update

this proof for BL segregation um right so okay yeah I think that's it um everything is open source record Tre is open source we you can go and download the code and uh the paper is also out right and uh yeah super excited about this work thank you very much oh thank you thank you for the great presentation so I will let people talk so feel free to ask question H everyone can ask

question can write in the chat or can unmute themselves and ask questions yeah is there any question not for now but yeah let's wait a bit thank you so much yeah interesting thanks than okay yeah if if there are not

questions yeah we can wrap it up and yeah [Music] there yeah there there is a question can you read it or do you want me to read yes do you see Rec having applications to generating updatable snarks Yes actually in the mer in the rec paper we we give an informal definition of what we believe should be called updatable snark and uh we have some initial ideas of how to take this technology and use the fundamental Primitives to build a snark that is updatable in the general sense I mean so

whenever you change a little bit a small part of the witness you can update the proof for the public statement without having to run the pro from scratch so actually this is something that we'll be working in the summer yeah hey I I don't think I can hear you

yeah thank thank you very much for the great presentation so people are saying thank you and do you have any plans to dat to plony free yes uh this is part of current investigation that we're doing right now as to what is the bestass proof system to move forward so Pony 3 is part of our considerations right but we haven't made a decision yet but there definitely this is something that we're we're considering what's what's going to be the next I mean there's like lots of workout there from folding BL 3 I mean so so we're we're looking into many

things they right right yes actually with do have at like grants we have uh investigated that we we we they can be implemented with with folding schemes there are some challenges uh the data structure storing the proofs might be larger but in principle nothing prevents us for doing that so this is also part of our current investigation great yeah I think there are more

questions no great yeah thank you so much and thank you everyone for attending and thank you babies for the great presentation for accepting the invitation and yeah have a great day thanks thanks a lot thank you thank you bye bye thank you bye