zkStudyClub: Alin Tomescu on authenticated dictionaries and cross-incremental proof (dis)aggregation

Transcript

good cool and all right recording great well welcome everybody welcome to the zk study club uh today we have aleene tomescu who's going to be presenting his work on authenticated dictionaries and cross-incremental proof aggregation and disaggregation i think i got that right um this for this organization i want to say thanks to alex for helping put this together uh alex maybe just put your hand up say hi real quick alex face to the new name on telegram yes so alex uh alex is actually going to be working a little bit more with me to do the zk study club hopefully we get to do this more regularly

i'm very excited to have him helping out and you're going to be working uh i guess you'll be fielding some of the questions on this edition um one thing before we start i just want to remind everybody that the zk summit is happening on november 23rd and 24th so put that in your calendar i will be sharing more info soon but i just want to make sure everyone here knows about it uh yeah cool okay so i think we should kick it off all right so i guess i'll take over from here thanks thanks anna for having me again uh i feel quite honored this is like almost like a peer review for my e-prince you know i just discussed them in the zika study club

and i get all this great feedback so i really appreciate it um so today i want to tell you all about our new work on authenticated dictionaries with the notion of cross-incremental proof disaggregation and aggregation and this is joint work with my mit lab mates yusha and zac newman well i should say xmit lab mates but we've continued to work together and let's get started so the motivation for the work is to figure out a way to do more efficient stateless validation and also other applications so specifically we want uh more powerful authenticated dictionaries for authenticating validation state which takes hundreds of gigabytes in

cryptocurrencies like ethereum and in feed scalability and decentralization and you could say well just use a vertical tree but previous authenticated data structures from merkle trees or other techniques are not actually sufficiently updatable aggregateable or sufficiently efficient for this task and there is some previous work that shows vector commitments actually suffice to authenticate the validation state but because vector commitments are much smaller the they limit the smart contract memory and as a second application we want to build transparency logs so some of you might be familiar with this project called certificate transparency that actually secures the web every time you go and visit any hd

https website so these transparency logs are really just append only authenticated dictionaries that map each website's domain name to the the list of their public keys over time so that websites can audit their public keys and so sort of previous work either builds these things from merkle trees which requires extra trust assumptions to keep the logs append only or there's some other previous work that uses rsa and bilinear accumulators but has kind of super high overheads and i should know because this is my work and i implemented this stuff and super slow and finally i think we want authenticated dictionaries for their own sake i think non-merkle authenticated dictionaries are interesting and are more powerful

and that sort of motivates finishes the motivation for this work and so our contributions are this new notion of cross-incremental proof disaggregation for authenticated data structures so the idea is that i have a bunch of different authenticated dictionaries d1 through d n and i have a proof with respect to each digest di and now i would like to be able to aggregate these proofs with respect to these different digests into a single succinct proof and this is a notion that was originally introduced by point proofs by gorbanov and here we generalize it so you could do it incrementally in the sense that after you've done this cross aggregation once with respect to a bunch of different digests if you get some other proofs with

respect to some other digest then you can sort of incrementally aggregate those into the previous cross-aggregated proof and not only that you can take a cross-aggregated proof and disaggregate it into its components so if that doesn't make sense please feel free to ask questions now uh and in general by the way i would love to to get questions live so feel free to interrupt it would be great to have a back and forth um and another contribution is we actually construct an updatable authenticated dictionary that supports this notion and can be used for stateless validation and we also give a new append only authenticated dictionary that's more efficient and i want to say more versatile than previous work

and can be used for transparency logs and in this process we also give some new techniques to compute non-membership witnesses all of the witnesses across different but related rsa accumulators and we also give techniques for aggregating such witnesses and finally we give a faster algorithm for extracting witnesses in bonnetol's proof of knowledge of co-prime roots or pokci protocol which is what which is which lies at the core of our cross-incremental proof disaggregation um okay so let me sort of uh paint a picture of how uh what what what capabilities previous authenticated dictionaries have and what we bring to the table and so

kind of ignore these footnotes here because i didn't know how to animate beamer properly to make them appear at the right time but they'll make sense in a second so we have the popular merkle trees uh merkel trees do not support any type of proof aggregation not even if i have a bunch of proofs with respect to a single digest i cannot aggregate them at least not efficiently in principle i can do it if i use snarks for example um they they have a notion of security this is the the binding notion of security that is strong in the sense that if i have an adversary that outputs an adversary cannot output a digest that says different things about a keys value so it cannot say that this key has value

vk and vk prime that are not equal so that's called strong binding and the adversary is allowed to output this digest adversarially that's where the strength comes from it's a very strong adversary and miracle trees are updatable in the sense that if i have an individual proof that's where this i stands for by the way can people see my cursor if i if i move the cursor yeah okay because i'm going to be doing that a lot so so miracle proofs are updatable but in order to update a miracle proof let's say for position i after position j changed i need an update hint i need some auxiliary information to do this update so if i want to update the proof for i well i actually need the proof for j2 if j changed in order to update i so this is what we call

an update hint and a scheme is called update hint free if it doesn't require any such information and you can just do the update directly merkle trees are not like that and if you organize the merkle tree proper properly you can get non-membership proofs so imagine a prefix merkle tree uh or a binary search tree that's mercalized and so on and unfortunately if you organize the merkle tree for non-membership proofs you lose the ability to prove append only and this is actually an open problem to support both things efficiently in a miracle tree you can also organize the merkle tree to support append only proofs but then you lose non-membership proofs so i i suspect you cannot do this efficiently in merkel trees but i don't have a proof that you cannot so it'd be really cool

as future work to come up with that and finally in a miracle tree it's very easy to compute all miracle proofs fast because you just mercalize your data you get the tree and you have all proofs so i hope so sort of these columns make sense as to what i'm describing here and then i'm going to go through some other schemes including ours there's some really cool work from eurocrypt 13 by papaman ii on building streaming authenticated data structures from lattice-based hash functions and this is basically just like a merkle tree but it's a little bit cooler in the sense that you can also update the digests not just the proofs and it's update hint free you don't need any information to do these updates any auxiliary information you have a proof

for i j changed you can just update the proof or i you can just update the digest whereas in merkle tree if you want to update the digest you you need the update hint and actually i should have had a d here in in update ability from a culture the digest is also updatable in the microchip but you need the proofs for the things that changed uh it's a slight error and finally also by papaman two at all there are authenticated hash tables these only are secure under weak binding which means if you have a correctly produced digest not adversarially produced digest the adversary cannot equivocate about the value of a key but the assumption here is that the digest was produced correctly and these weak binding authenticator structures

are actually all you need in the stateless validation setting because in that setting the digest is always produced after appending a bunch of blocks to the blockchain and these these um appends are verified by the miner and the authenticated data structured digest is produced correctly after those appends um and unfortunately so is this is this the difference between um a collision property where you the adversary is is trying to produce two data structures and uh kind of a a second pre-image property where they're trying to produce another structure that matches the same the same house i actually i actually really love that

question i've never thought about it in that way before i will say that strong binding usually implies collision resistance i remember working this out for myself earlier on i don't know if weak binding does doing i'd have to think about that for a second maybe we can discuss at the end that would be that would be interesting to figure out okay uh yeah um okay so uh authenticated hash tables are not updatable unfortunately in the sense that you cannot update the digest you cannot update the proofs efficiently uh and in that sense there's no sense in talking about update hints they do support non-membership proofs they don't support a pendulum proofs and they can be pre-computed fast

there's a really cool work by bonnet boons and fish on building key value commitments again another name for authenticated data structure and i think this was the first construction that actually supported one hop proof aggregation which means i have a bunch of proofs with respect to a single digest i can aggregate this into a single proof and that's all i can do i cannot take some other aggregated proof and continue the aggregation incrementally i can just do it one hop and they are also updatable given update hints consisting of the proofs for the changed positions they support non-membership they don't support append only and you can pre-compute all proofs fast and bonnet will also give a faster version of their first construction which is only secure under weak binding and can be used for stateless validation

and has the same features of as the first one but saves like an order of lambda work concretely where lambda is a security parameter can you just clarify what what fast means in the last column good good good so uh i have i i want to compute n proofs and i want to do it faster than n squared so i usually want quasi-linear and log k-n-time okay thanks um there then there's the authenticated append on the authenticated dictionary work uh which doesn't support proof aggregation has strong binding is not updatable supports non-membership and append only proofs at the same time and as far as

as we know this is the first construction that supports this so both proofs are logarithmic size diffuse rsa accumulators and it supports a way to pre-compute operates fast but the construction is the amortized and and is very inefficient um is it uh specifically rsi or is it any group of online auto it's i think well to the extent that you could build rsa accumulators over groups of unknown order it's any any group of unknown order but there was some recent troubling eprint on breaking class groups which i haven't really spent the time to understand it was one specific property um that some protocols relied on

i can't remember which one the low order assumption the low order right but i i couldn't understand if there was a way to check if a hidden order group actually was if a class group actually was susceptible to that attack or if you could trap if you could trap door a class group so you couldn't tell if it's acceptable yeah i think i think it was mainly about constructing trap door yeah well then that kind of kills pokey proofs for a bunch of accumulators in those groups um okay then there's some work by loom at all on building again authenticated dictionaries from vector commitments as a building block and they use the point proof vector commitment

and they support the aggregation of proofs but it's only one hop they're secure under weak binding and this is kind of inherent to their construction as far as i can tell they cannot be made strong binding and and they do support updating digests and and individual proofs as long as you have some update hints which are static actually they don't consist of proofs for the changed positions they're just consist of some static information associated with each position and they have non-membership no append only and actually no way to pre-compute proofs fast as far as i can tell uh maybe there's a way to do that but i couldn't trivially build such a way finally concurrent with our work there's this really cool paper by shashank agrawal in srini raga

ragumaran on also building authenticated dictionaries from vector commitments from catalan and fiori vector commitments which is what we use as as well so they support one hub proof aggregation they are secure under weak binding however i suspect this is not inherent they could actually get a security proof for strong binding too they support updating digests and individual proofs and they don't need update hints so this is really really cool that they don't need update ends and unfortunately they do not explore building non-membership proofs again i don't think this is inherent i think their construction could be changed to support that they don't support append only proofs perhaps that could be done too i haven't investigated and they don't have a way

to prove all everything fast again i don't know if that could be supported and finally we have our first construction which is an updatable authenticated dictionary which supports the stronger notion of aggregation of cross aggregation that can be repeated incrementally and can be disaggregated back into its components our construction is inherently weak binding secure which means it's only usable for stateless validation in applications like that but it's highly updatable in the sense that you can update aggregated proofs you can update digest you can update individual proofs and you can also update cross-aggregated proofs and it's update it's not update hint free in the sense that you need some auxiliary information to do these updates so it'd be really nice

to sort of integrate the changes from kvac into our construction and get update hint freeness but unfortunately i think that would break a lot of the for other properties we have then we also support non-membership proofs however these non-membership groups can only be one hop aggregated fortunately in the status validation setting i don't think there's actually a big use case for non-membership proofs that remains to be seen and we support append only proofs and computing all proofs fast and finally we take this uad and we add strong binding to it and as a result of adding strong binding we kind of lose the cross incrementality we only get one hop aggregation

we still maintain some update ability of aggregated proofs in the sense that we can update aggregated proofs as long as an existing key in the dictionary has changed but if i add a new key or remove a key from the dictionary i cannot update cross-aggregated proofs i'll maybe touch upon why that's the case towards the end of the talk and once again we need we need some auxiliary info to do these updates and we support non-membership append only and efficient proof pre-computation okay so i really wanted to spend a lot of time on on contextualizing the work because i think that's this is a part of the presentation that you know uh it's easier to understand than the math that's going to come up and i also want to say that i made an effort to reduce the math and my collaborators helped me yesterday to get rid of a lot

of it so i hope the presentation is not too um mathematical uh so that makes sense i missed what i missed what adix meant yes good so adix is is just what the update ability of the construction is so the big a stands for aggregatable proofs are updatable the d stands for digests are available i stands for individual proofs are updatable x stands for cross aggregated proofs are updatable does that make sense yes thank you okay great okay so the rest of the talk will kind of be background on the building block of our

construction which is the beautiful vector commitment by catalano in fiore and then i'll present how we build our uad our updatable authenticated dictionary and then i'll touch upon what we do for our aad without going into too many details and then i'll conclude and i obviously advise you to read the paper for more details here i'm just trying to give a lot of intuition and explain some some things that don't really actually we don't actually explain the paper so i hope this will nicely complement that okay so let's begin with the cf vector commitment scheme uh originally uh by catalan and fiore and extended by lion malavolta and campanelli at all and here i'm really describing cf after these extensions so keep that in

mind this is not the original cf it's kind of the extended one [Music] so assume i have a vector v with elements v1 through vn and while you assume that i'm going to pour some coffee and its digest which i denote by digestive v or its commitment is just two things the first thing is an rsa accumulator over all of the positions j in the vector and how do i build that accumulator i take each position j i hash it to a prime e j and i do the product of all prime and the exponent of this generator g of a hidden order group by the way everything in the stock is hidden order groups

rsa groups or class groups if they're still usable and the second part of the digest is the slam the component and what this lambda component is it's really a multi-exponentiation of the rsa witness for for position j raised to the value at that index right so s to the one over ej is an rsa membership witness for for position j with respect to the accumulator s if you guys recall that if not you can just look at it as as s to the one over e j it is useful to realize that this is an rsa accumulator and this is just the membership witness with respect to the rsa and that's kind of it it's just these two group elements and if you want to update this digest after delta after position j

changed by delta j you must have this auxiliary information called an update key consisting of this non-membership witness for j and the way you do the update is very easy you just take this lambda and you sort of change vj by adding in this s to the one over e j raised to the delta j which will change v j here in the exponent um uh and a few critical observations the values v i have to be l bit numbers and the primes e i have to be l plus one bit numbers and as far as i can tell this is really strict they have to be strictly greater than l plus one bits for security to hold if they're not then you cannot really

prove security as far as i can tell um so and so uh delta j is the new value minus the old values all right yes yes yes yes thank you thank you for clarifying uh and one thing you might wonder is well when i come commits to this vector it's easy to compute s in linear time but what about delta because i have all of these different roots of s i have an e j through the s and i need this root for all of the possible different j and it turns out i can compute all of these roots of j using a classic algorithm originally proposed by sander at all and recently renamed by bonnet boons and fish to root factor which i think is a really good

name and root factor basically takes the generator g and all of these things in the exponent of g e 1 through e n and gives you all of the roots of s e 1 e 2 e n and so notice that g to all of this is s and root factor gives you g to all of this but one thing in it and it gives you that for all of these one things and uh this is it's this is a really cool algorithm that's very useful for for the cf scheme so companies leverage it a lot to speed up their construction and we also leverage it in our paper a lot so if this doesn't make sense now would be a good time to ask a question about it and finally like i said before s is an

rsa accumulator and s to the one over e j is just a membership witness with respect to that accumulator okay how do you prove things in in cfvc so suppose i actually want to prove that a bunch of positions i in a big set capital i have values v sub i so i'm generalizing notion of a proof i'm going directly to the so called sub vector proofs rather than going through individual proofs and actually this is uh this is kind of what's the beauty about catalan of your vcs is that you can look at a proof of pi i for i as just the digest of v without positions i in it so i'm denoting this by v minus vi i'm kind of defining my own notation

here and if you try and commit to this vector without positions i in it how would you go about it well you would compute the rsa accumulator over all positions in n except i right so i'm going through all positions from one terrain accept the positions in i and this is really like the uh accumulator s raised to one over e i where s is the accumulator over all positions in n right does everyone agree [Music] the animation never works out as i want

it uh right so so so i have this uh rsa accumulator for this half vector now and then i also have to compute its lambda component and it's lambda component remember has to be a membership witness with respect to the rsa accumulator of the vectors positions raised to the value at that position and that's exactly what i have here i have a witness for for each j with respect to s i raised to its v j and i do a multi x and that's by definition the digest of v without positions i in it and that's actually a proof for the sub vector and the way you verify it is well you take this s i you you you um you sort of add back

the the positions in i to this lambda i and you check that you get back the original digest i'm actually not going to go through the verification here but you can see our paper for that but the idea is that you you can verify it in linear time where linear in the number of positions in the i sub vector um and really the reason i'm explaining things this way is because i want to make you realize that a proof is really just like a digest and because the digest is updatable the proof is updatable too just like just like we can update a digest after something in the vector changes we can update a proof too okay and to give you an example if j changed by delta j

then all i take is i take lambda i and i raise it and i multiply it by by this guy raised to delta j where this guy is the membership witness for j with respect to s i and that kind of tweaks the vj in here right um and one observation i want to make is the question is like if i'm doing this update where do i get the sting from this uh membership witness for j with respect to si because if i'm doing the update i have a psi but i don't have an ej through to that side however i can ask the the person who's giving me this update to also include this s to the one over e j with the update and if i have additional this s1 to the ej i can actually compute a root an ej

through the vesi which is really an e i times e j through s using a so called shamir trick and what a shamir trick does is it takes an e i through it and an e j through it and it outputs an e i times e j through it and i won't go into details about how it works you can see our paper for that you can see campanelli's paper uh it uses the extended euclidean algorithm it's a very useful trick in this line of work um so yeah so that's sub vector proofs uh the other cool thing about these vectors as shown by company at all is that you can actually extend them with new positions so i can add a new position n plus one with value v n plus 1 to a vector v with n

positions and the way i can do that well it's very easy to update the accumulator part of the digest all i take is the previous accumulator and i exponentiate it by this en plus 1 associated with position n plus one and now i have an accumulator over all positions from one to n plus one right does that make sense and for the lambda part of the component so um sorry to interrupt interrupts is there a limit is there a limit on the range of the um values um in the dictionary yes yes it says so i as i mentioned in the initial slide uh the values have to be l bit numbers l bit numbers and the primes have to be greater than l plus one bit numbers

i see okay for for security to hold yeah and right so for the lambda part of the the digest well lambda needs to have a witness for for the position n plus one raised to the value at position n plus one and that's what this guy is but then i also need to update the previous witnesses in the old lambda to be with respect to this s plus one the this s prime by multiplying by exponentiating with this e n plus 1 and this might not be intuitive so i'm just going to actually going to expand this equation to see why this holds so uh if we expand this lambda remember it's just the product overall positions in from one to n of witness with respect to s

which is the old digest erase the vj and now i'm raising all of this to the new en plus one and now i can actually do two things the first thing i'm going to do is i'm going to rewrite s as s prime to the 1 over e n plus 1 which i can do that's by definition what s is and then i'm going to move this e n plus 1 inside this this bracket here and i know that s to the en plus one is s prime so i get an s prime in here and now if you look very carefully i can actually just merge in this guy into the product and i get the product overall j from n from 110 plus one of s prime so membership witness with respect to the s prime for position j raised to v j and

that's why i can add new positions to the vector and i can actually repeat this you know so if i want to add several new positions i can do this sequentially i can take this new updated digest and add an n plus two position to it by just doing the same thing okay and this is something i'm not sure that we explained this in the paper i think we touch upon it briefly but it's actually quite useful in the next slide and in the rest of our construction so next i want to tell you about how cfvcs disaggregate proofs again we're still in the background section we haven't gotten the meat of the talk so suppose i have a subvector proof for i and i want to build a sub vector proof for k where k is a

subset of i right so how can i do that this is called this aggregation i have a proof for a lot of things and i want to get a proof for less of those things well first let's define this delta as the things that are in i but are not in k and notice that really what i'm trying to do is go from a digest of v without i in it to v without k in right by definition that's what a proof or i is and that's what a proofer k is and we we can just notice uh intuitively that v if i add v delta to v without i in it well what i actually get is i get v without i in it and i can expand the deltas to by definition delta is i without k in it

and now these v i's cancel out so actually what i get is v without k in it so really all i need to do to get a sub vector proof for k where k is a subset of i is just add back the things that are in delta to the proof for i and i know how to add back things to a digest i just told you here how i can add new things to a digest right so that's exactly what i'm going to do for each i in delta i will sequentially add it to s i and lambda i and get sk and lambda k and this will take me l times size of delta group operations as shown in the previous slide so in an earlier version of the talk this was way more complicated

but i think this is actually the simplest way to do aggregation and the nice thing about this is that you actually get a faster disaggregation protocol than the one proposed in cfg plus 20 as far as i can tell unless i'm making some horrible mistake here i did figure out this late at night so it's possible that it's completely wrong so please let me know if you find about but it looks right to me and an implication of this is that you can actually compute all proofs in uh n log n time rather than n log squared and time which is what the original cfg paper proposed via this aggregation now how do you compute all proofs via disaggregation this is not intuitive but the idea well it's actually intuitive never mind take a proof for the full vector imagine you have a proof for the full

vector disaggregate it into a proof for the left half and a proof for the right half then disaggregate it into a proof for the left left and left right right left and right right continue all the way down until you get the individual proofs at the bottom right so this is a really beautiful algorithm by company at all so this aggregation is actually quite a useful trick for computing proofs efficiently and yeah like i said before they claim l n log squared n but i think if you do this aggregation in this faster way you can get a faster algorithm um okay so we're almost done here another thing that cfo vc support is incremental aggregation which means i can take a prefer i in for j and obtain a proof for the

union but then if i get another set k i can also continue this aggregation incrementally and get approved for the union of i j and k i'm just going to show you how how to do the the proof for i and j here and i'm going to assume they don't intersect because if they do it's easy to disaggregate one of the proofs so that they don't intersect so if i have a proof for one two and another for two three i can disaggregate the proof for one two into a proof for one so now i only need to aggregate the proof for one and the proof for two three right so i don't need to worry about intersection and again the idea here is that i'm going from a digestive v without i and a digestive v without j to a digest without both i and j

in it right and the first thing to notice here is that i can easily compute the accumulator part of the of the proof by again using a chamier trick so so the accumulator part of the proof will be an e i e j through of s that's what the digestive v without inj will look like and this i can again do via trick i have an either i have a ej through it they're both in the pi and pi j proofs and i can get this e-i-e-j through it and yeah and the other part is computing the the lambda of of pi iuj and this lambda is kind of a mouthful so you have to do a product over all positions n without i union j

in it rsa witness with respect to s i u j raised to the value at that position and you can kind of rewrite this like you can pull out of the exponent from siuj in here and write this as s and this will actually help you figure out how to compute the lambda iuj basically you tweak the lambda i into into something that looks like this and you take tweak the lambda j into something that looks like this and then you do a chamier trick to take this uh this root now i'm not going to come explain this in details because i think it's too complicated and we don't really use it in the rest of the talk i do have it in the appendix if you want to discuss it at the end of the talk and really this just takes two root factors in a chamier trick

and that's what i'm going to say and i'm also going to say that it takes quasi-linear time to aggregate assuming i is greater than j so that kind of uh covers the background so i hope you know you you you can gain a glimpse of how beautiful this construction is and let me show you how you actually turn this into an authenticated dictionary so suppose i have a dictionary d i can basically treat it as a sparse vector i can treat the keys as indices in a vector and the digest of this dictionary will have the s and the lambda part as before the s as before is just an accumulator over all the keys where i hash each key

to its prime e k and the lambda part as before is rsa witness for k with respect to s raise to v k product over all of these so nothing changes here the only thing that changes i'm treating keys as indices in fact this is so obvious like i i'm so pissed i didn't realize this later earlier you know like i've been looking at this scheme for quite a while and it's a very simple observation and similar to catalan of your vcs because we haven't changed much the digest remains updatable and i know i can add new things to the digest as i showed you before so i can easily add new keys to the dictionary but i haven't shown you how to handle

removing keys from the dictionary so we'll we'll do that the proof for a bunch of keys k remains the digest of the dictionary without those keys in it just like a proofer sub vector was the digest of the vector without those indices in it and the proof remains updatable except i have to handle removing keys from the dictionary once again so how do i update a proof after a key was removed from the dictionary and the proofs remain incrementally disaggregateable and i want to say this is actually a concurrent idea with the ar-20 the the e-print that elegantly removes update keys by shashank agrawal so i really encourage you to read their

paper they have a really beautiful way of removing these update keys but what we do is we go in a slightly different direction we add this new notion of cross-incremental aggregation which i'm going to explain next and we add support for non-membership groups and we add strong binding to the dictionary so this so far is weak binding and we add append only proofs and let's just first i'm going to kind of treat all of these in order how do i update the digest after uh adding or removing a key well you know as previously shown if i add kvk if i want to add kdk to the dictionary and get an updated digest d prime i can

basically uh i can basically use the trick for adding new positions to the vector so i'm not going to go over that because i can add new positions to the vector i can add new keys to the dictionary the more interesting cases how do i remove things from the dictionary so suppose i'm removing a key k hat with value v k hat from the dictionary the thing to notice here is that the updated digest is the digest of d without dk hat in it but by definition this is actually the lookup proof for pi k hat with respect to the digest t so remember look up proof for an individual key it's just the digest of the dictionary without that key in it but that's also the the updated digest of the dictionary after removing that key right so to update a proof so to update the

digest after removing one key i just set the digest to be the proof for the removed key so i need this as auxiliary information and again if you read the ar-20e print you don't need this which is really cool but in our construction you do now what about multiple removals suppose i'm removing a bunch of keys in a capital k hat now i have a bunch of lookup proofs for each individual for each individual key in the set or maybe i have an aggregated lookup proof for all of these keys in the set well again the thing to notice is that the updated digest is just the dictionary d without all of these keys k hat in it but that's by definition the aggregated lookup proof pi k hat with respect to the old digest right

so if i get individual proofs for all of these things in k i can aggregate them into this 5k hat and i set the die just to be that right so so that covers that covers updating the digest after removals after additions and we know that we can update the digest after changing keys just like we could update the vector commitment before what about updating proofs so again a proof for for k is just a digest of d without the keys k in it and i know that uh after i add a key i can update this proof in the same fashion as updating the digest in the vector after adding new positions so again we're not going to go over that question is how do i update and i also

know that i can update a proof after changing keys in the dictionary just like i could update the vector so again the question remains how do i update this proof pi k to a pi k prime after removing the key k hat v k hat from the dictionary and importantly so this new proof pi k hat has to verify with respect to this new dictionary d prime that doesn't have this key in it so d prime is d without that key in it and the thing to notice here is that oh you know by definition pi k prime is the digest d prime without the keys k in it right the the the without the keys k in it right that's that's by

definition what a proof of k is and i can rewrite this so i can expand d prime i know d prime is d without d k hat so i put this here and d prime k stays the same but then i notice that d prime k is actually the same as d k and now what i notice is that well this updated proof pi k hat is just the digest d without k hat and without k in it which by definition is the aggregated proof for k and k hat right so if i want to update a proof i just after removing a k-hat i just aggregate that proof with k-hat that's the intuition here

and that kind of covers proof updates so we talked updating digest updating proofs and remember these proofs are aggregated right so there's they're proofs for a bunch of different keys uh let's move on to the more interesting part which is the cross-incremental proof desegregation so again i have a bunch of different dictionaries di m of them and i'm going to change notation a little bit i can no longer use s and lambda because of these i subscripts so digest of di will be a i and ci where ai is the isa accumulator overall keys in the dictionary and ci is the lambda part which is rsa witness with respect to a i for k raised to the value at k now a proof for a bunch of keys cap

ki with respect to its digest di i have a bunch of these proofs so i have m different proofs each with respect to a different di will be this you know eki through it of the rsa accumulator ai by definition so i'm going to call this wi again i'm changing notation so previously this would have been s and this would have been s sub sub k but now because i have a bunch of different proofs i'm using this new notation but all that i want to say is that you know the this this is just an eki through of the rsa accumulator in the digest because that's basically an rsa accumulator over all keys in di except the keys ki and then there's the lambda i part of the digest

which i'm rewriting slightly differently here so the rsa witness for k with respect to wi is a i raised to 1 over a k raised to 1 over e k i because a i raised to 1 over e k i is wi and if you take an e k worth of that you get a witness for k with respect to wi this is a bit of a luck the process so all i'm saying is that the witness is this race to this and i'm raising all of it to vk right so you can move this guy inside here and that's the witness with respect to wi so again this is just a proof for ki and i'm going to play with this a little bit i'm going to rewrite it as

you know i'm going to take this difference here and i'm going to write it as a fraction so here i have the product over all keys in the dictionary and here i have the product over the keys in ki and right so far so good and this this guy stays the same here and then i noticed that well this thing at the top is actually just ci by definition right so just look here this is just ci and this guy i'm gonna leave it unchanged except i'm changing the notation from dki to ki which is basically the same and i'm gonna baptize this guy as alpha i and that's that's that and what i want to point out here is that a proof for

ki consists of an eki through of something and an ekit root of something else and in general all of these different proofs for these different kis will be an eki fruit of something and bonnet at all gave a protocol for aggregating such co-prime roots so if i have a bunch of of roots of of of coprime roots eki with respect to different things i can actually aggregate them very simply by doing a product over them similarly here i have a bunch of eki roots of these ai's and i can also aggregate them by doing a product but there's a caveat the scope prime-ness is the caveat so i can only do this aggregation if the

ekis are co-prime but it turns out they're not go prime let me tell you why so again they have to be co-prime for the segregation to work so the gcd of eki and ekj has to be one for all i different than j but this is not true because i could have the same key k within different ki and kj and that means that ek divides this eki and ek divides this ekg and their gcd will be at least divisible by ek or or greater than that so these things are not actually co-prime so that's kind of a bummer you know how do we aggregate this if they're not go prime and we kind of hack our way around this what we say is we require a different hash function h i

for each dictionary d i so this eki will hash k with h i rather than h so k i will have h i of k and k j will have h j of k therefore you won't have the same prime dividing both of them right so this way h i of k is different than h j of k and their gcd remains one because if you have keys in common they'll hash different primes but of course this is kind of a limitation do the different hash functions need to hash to destroy sets of primes well i think the only property you need is

given a key k h i of k should be different than h j of k this jointness would totally give you that i'm not sure that you need to be fully disjoint like you could have the hi of k1 be sum prime e and h i actually no no you're right no you can't have that either yes this is good good so they need to be disjoint okay yes yes how do you just use like pre-image resistance here right if we if it's hard to find a pre-image we're not going to be able to find something which or any great sort of cross-collision resistance so they don't have to be disjoint this has to be hard to find a solution yeah i'm not sure that's correct because

the the gcd will not be equal to one ah so these are not primes the the e sub k i are not prime they're products of primes they contain primes right right but is the h i of k prime because if so then all you need is some sort of cross collision resistance yes the h i is prime okay yes the output of the h i is r prime yeah so you need cross collision resistance which you can easily get if you consider like you take h and you prefix i into h as input because h is collision resistant which is h i and h j should be cross-collision

resistant um ah right but but they don't need to be provably distract they just need to you just need to have a hash with a large enough five points up okay uh but again i want to say this is this is kind of a limitation because we require the dictionaries that we do the cross aggregation for to use different public parameters so each di has to have its own hash function i that the prime representatives are computed with and this is not ideal ideally we would like to aggregate truths across dictionaries with the same public parameters and we leave that as future work can you not just

um remove the keys that are going to collide first from the same way that you did earlier with when you yeah well but you can't because you want to prove you want to prove that those keys are in ki i want to prove that case both in ki and k is both in kj you know i need to make that statement about the key k being uh yeah i guess yeah okay i can't really desegregate my way out of this okay so for the verification um i'm going to define this is how bonnet all shows how to verify such a such a pokcr aggregated uh proof so i have this e star which is the product over all of these eki so

remember that eki's in turn are product over a bunch of primes for each key and ki and i'm going to define this e-star in this way and to verify that i want to verify that each wi is an eki root of a i and i want to do this for all double uis but i've aggregated them within w so how can i do this well bonnet at all show that it's sufficient to check this equality holds and i won't explain why this works but intuitively you can sort of mask out the e here the e star here and notice that this really checks that w was computed correctly from the wise but it's not as simple as that because if you check it in this way which you can do very fast via this algorithm that that boneet all

introduced called multi-root x if you check it in this way then you can actually extract all of the wi's from w so it gives you a really strong property so i can actually recover the wise from w if this holds and one of our contributions is that we give a faster algorithm for this extraction that saves a factor of order n by log and work and we actually need to extract these these w's after doing the certification because we need the w i's uh to apply a few root factors to it so we can reconstruct the alpha i's against which were defined in this way against which we verify the lambda i's that are aggregated within lambda so remember the lambda

lambda i is an eki of alpha i and to verify all of the aggregated lambda i's i do the same type of verification where i compute this rand the right hand side using multi root x again i'm not going to give details about this but this is in the bonnet paper and we also explained it in our paper again and you know i i don't have a good way to explain this yet beyond the fact that if you understand how you can extract all of the w i's if this holds then you should see how this equation actually checks that each wi is equal to the eki root of a i so uh you can see our paper for that you can also see the preliminaries of our paper

i do want to say that if you read bonus paper there is some typo in in their algorithm for extracting the the wis from w so so please be mindful of that at least in the eprint i believe there's a typo i don't know who the crypto paper is so in our paper there's no typo as far as i can tell uh that that might be clear okay so we can verify the cross aggregated proof and if b is the max size of a ki then the verification can be done in sort of quasi-linear time in the number of cross-activated proof and in the size of each aggregated proof so this basically comes this is the time to do the extraction of the w

i's this part and this log b part is the time to do the root factors which i didn't go into details about um and you can see more details about this in our paper i'm not going to bore you with the math uh a really cool concept sorry what was b again oh b is the max size of a k i so remember i have a bunch of k i i'm sorry aggregating all yeah so we're almost running out of time uh one quick thing and i'm actually done so one one quick thing i want to say is that because i can extract the individual aggregated proofs from the cross-aggregated proof uh this actually means that i can disaggregate cross-activated proofs

which is kind of neat but it also means i can update them because i can disaggregate them first then update the original aggregate proofs and then re-aggregate them and perhaps there's a way to do this faster than that but at least in principle i can update cross-aggregated proofs and that concludes the uad part of the presentation and real quickly i want to go about other things that we add for applications beyond stateless validation so i mentioned strong binding for our aad construction and the idea for providing strong binding is that you have to make the security proof work out and if you try really hard to make the security proof work out you all of a sudden realize that if in addition to this sk lambda k part of the proof you also

include a non-membership witness 4k with respect to sk which is actually just yet another rsa accumulator that totally makes the uh the security proof pass um because you can use this to do some gcds and get a strong rsa break so i don't have a lot of intuition to give here beyond read the security proof and see how this helps but because i've added this rsa non-membership witness to a proof i now downgrade to one hop aggregation because rsa non-membership witnesses as far as we know are not incrementally cross-aggregateable because pokey proofs are not incrementally aggregateable they kind of are aggregatable but they're not

linear they're not constant size after you aggregate them you have some integers left over we also have non-membership proofs and this is easy to see because if i want to prove that a key is not in the in the dictionary d would die just as lambda all i have to show is that key is not this in the key k is not in this rsa accumulator s right and i can do that using an rsa non-membership witness with respect to s um finally append only proofs suppose i have a null digest for for dictionary d and the new digest for d prime well the one thing i have to observe is that the s prime in the new digest is actually s raised to some integer u and the lambda prime in the new digest

is lambda raised to that same u times s raised to some integer z and it turns out that if i show this holds i can prove append only security holds i can prove nothing has been removed from the dictionary only new keys have been added and we formalize this in the paper and we prove security in the appendix and that's when you say when you say new keys have been added that means no existing keys have been changed yes exactly yeah only new keys have been added yes got it yes okay so i'm ready to conclude now so it seems to me that these cfvcs

just keep on giving so they're really beautiful construction uh we showed how to get cross incremental aggregation for for dictionaries with different parameters it'd be really nice to to do it for addictions with the same parameters we showed how to get authenticated dictionaries with strong key binding for applications like transparency logs and for that we also need these append only proofs and we showed how to add non-membership proofs to our authenticated dictionary and again i want to encourage you to read the eprint by shashank agrawal and srini raghuraman for how to remove update keys i think they have a really beautiful idea there and really the open question is what else can we do with these vcs they seem to be really powerful really cool so

that's how i'm going to end this talk and i thank you for your time and attention and if you want to discuss more i'll be here thank you yeah so we have and we have uh 30 minutes left to discuss the paper and for anyone who wants to to ask any questions so with that um please anyone feel free and step in also i've muted all of you so you would need to unmute yourself if you want to ask anything okay i guess a lot of people are

thinking so i guess i guess one question is about concrete efficiency good um so suppose we're using rsa um that means i guess that well well it's it has to be an rsa for which we don't know the um factors right that's correct so we need a trusted setup right okay but it's it's a simpler setup than a qsdh let's say setup where right you have this huge crs um so i i i can't remember what the um what the um npc based setups for rsa

um groups look like does the modulus have to be larger than it normally would be no okay okay are there any constraints sorry go ahead i think there's a thing where you can do an unstructured setup just take a random number it just has to be absolutely huge oh yeah yeah yeah that's yeah in principle yes but in practice no okay okay so let's say that we're using i don't know 3096-bit rsa so so let's look at the um the costs of the particular algorithms so i guess one thing you're going to be

interested in is how long does it take to compute all proofs uh how big are the proofs so proofs are two group elements uh whether they're individual lookup proofs or aggregated lookup proofs or cross-aggregated lookup proofs just two group elements uh the time to verify for example one thing that will be of concern is this time to verify you know it's it's conceivable that you cannot do faster than b times n because you have d times m keys that you need to go through to verify the proof right but this l factor is inherent from the the l bit size of the primes this log squared m factor would be nice to get rid of this log b factor would be nice to get rid of but in principle you shouldn't be able to do faster than order bm

uh to verify across aggregated proof to verify an individual proof uh for b keys sorry uh aggregated proof of b keys i think it's just order lb time uh i could be wrong do you need to do root factors too maybe maybe it might be older lb log b time actually because you might need to do a root factor uh but no no is that true no you could you just add back the keys no no you should be able to do it in order lb time i take that back because you can just add back the keys to the proof and make sure you get the original digest by adding back the keys to the proof because the proof is just digest without keys you add the keys back to the proof you get the original digest and you can

add the keys in order lb time so so by a um a g question mark ops that's uh multiplication in the rsa group yes yes good yeah i didn't want to say exponentiations because you know this seems more precise but you could shave off this this l factor which is tends to be 256 bits anyway it's like a security primary and you could change this to exponentiations so then you have order bm hidden order group of size exponentiations of size l huh that seems as though it could be quite practical yes uh i don't think it's i you know obviously pairing-based stuff will always be faster

[Music] but it's not out of the realm of of possibility uh the more concerning stuff i think is the size of the proofs but when you consider cross-aggregation like imagine a stateless cryptocurrency they have a bunch of smart contracts you're proving things about the reads and the memory of the smart contracts so you're proving let's say you know thousands and thousands of reads and now you're cross-aggregating all of this proof into 6 000 bits right let's say that's pretty nice you know you have to send the keys anyway and the values of those keys and the proof overhead is really small now the time to verify is gonna you know must be super fast but who knows i don't know maybe you can just use a

snark and um arrange for the the arithmetic to be fast in the snark and then the proving will be expensive but the verification won't be right right um yeah i i also want to say that you know this cross-aggregation requirement for each di to use different public parameters is actually not a problem in the smart contract setting as far as i can tell because each smart contract can easily use its own hash function hi to compute its authenticated dictionary but for other applications it might be

oh i see so so basically if system has lots of independent things um that don't interact very much with each other then it's going to be easy to do this segregation okay anish i think i i think anish uh you had a question as well would you like to would you like to ask oh no i was just about to ask given there was all this question about uh you know size of primes i was wondering if there was any smooth risk requirement because you are doing a lot of gcds and things like that so you know security margin could be much lesser if you have some sort of

smoothness requirement sorry i didn't quite hear what you said there uh i said if you are doing a lot of gcds especially in rsa they might have i was wondering if there was any smoothers requirement so number of factors in that sense what the size would be the largest one in that sense number of factors in what in the size of the largest factor in that sense there's a smoothness so when you do factoring data so you're talking about the isa modulus and if there's yes yes yeah that's this one yeah absolutely seo so actually there's like a great uh there's a great stack exchange question right now uh about the security requirements of of on n for rsa accumulators i think it's

still unanswered uh um okay but yeah all i can say is all i can say is you know i'm not a crypt analyst so all i can do is prove this is secure as long as strong rsa holds in the group now what does it need for strong isa to hold in the group uh i don't know that's you know obviously you need to pick n randomly as a product of two primes yeah you probably need to operate within a subgroup of quadratic residues uh but uh beyond that i'm not sure what to say so i think other people are best better suited to answer that question than i am i just posted the link to that in the

chat oh okay thank you right question yeah yes yes so criteria for public modules of rsa accumulator [Music] so that's in some sense what you're asking anish because if you think about the cf scheme it it's it heavily relies upon rsa accumulators so it definitely needs uh security for our securities to hold might need some other things well you know it seems to hold it seems to just need strong rsa um and in fact you can even get rid of stronger sa and reduce to rsa um okay for weak binding i i think um yeah so sorry i don't have a better answer to your question

no no no sorry i was just thinking out loud because you're using a bunch of gcds and what that does in terms of security has significant implications for the size of your factors in that sense and also when you are talking about speeding it up so depending on the smoothness you you can have some uh some speed as possible so that's kind of when it went to my head when you guys started thinking about what the size and how fast you could run okay thank you are we always taking gcds of products of large primes uh we're taking i mean we need certain gcds to hold between these products of large crimes for example here gcd is one between these prime

representative products we're also taking gcds when we're doing some year tricks like for example when i aggregate a proof like here i have to do a shmear trick to aggregate the rca accumulators i think that comes up well it's much earlier in the talk or else the gcds turn out disaggregation we don't need to do gcds i think it's when aggregating and when yeah just when aggregating so what are the requirements on the hash function a the hash just has to return h yes has to

output l plus one bit numbers has to be collision resistant uh now i think collision resistance but is actually needed just for correctness not for security i see okay so it doesn't have to be a random oracle it just has to produce distinct primes yeah i want to say so um so for example in pokcr we need collision resistant for for correctness if if we don't have a collision resistance here we cannot aggregate right um in the security proof uh i never need to assume

that the primes are different i need to assume things about gcds um yeah i should revisit that more carefully uh my my impression is that the collision resistance is needed just for correctness uh and not for security could be wrong um yeah okay thanks following up on that question so you mentioned that um you know the requirement to have a different hash function as public parameters for each dictionary is one potential limitation in an area that this could be extended um what other areas uh are are promising

future directions do you think for this line of research um let's go can we go let me see if i can go to to the um i can't easily navigate this damn thing it's so big uh i i wanted to go to the table i had that problem with my talk how can i let me okay i think i start screen sharing i'm going to preview this differently with the page numbers [Music] come on tech studio work with me uh okay and now we can start screen sharing again

tech studio that's uh there you are sure uh let's go to page and so to answer that question i i just wanted to look at this table so you know i think what one one important direction is to get rid of these updatings so for example the the kvac construction by ar-20 is arguably a better fit for stateless validation because they don't need update hints which can be kind of problematic now i haven't given it too much thought as to how problematic they are uh but this is a big plus on the other hand they don't have cross incremental

proof aggregation so when you think about different smart contracts you can't really cross aggregate the proofs so so that's kind of a bummer and will result in a bigger proof size so i would say you know we want something that's cross incremental uh and update hint free that would be really cool to get also uh as touched upon daera it would be nice to have something more concretely efficient like from bilinear pairings for example now incremental aggregation from bilinear pairings doesn't really work out that i think that's an open problem so this partial fraction decomposition that is used to aggregate proofs in bilinear things as far as i can tell can't be

incrementally applied because the polynomials don't work out anymore but in principle you know so a sub-vector proof in in a in a casey gvc is just a polynomial commitment and you're going from a polynomial commitment of some degree to a polynomial commitment of a smaller degree so that in principle should be possible you're not going from big from small to bigger which might break some assumptions so when i've looked at um by linear accumulators that they've all seemed to have um uh reference strings that are the uh linear in the

maximum number of elements yes is that the case okay yes and that that has kind of put me off um thinking about how to use them because i in the protocols i'm interested in that that's a showstopper yes well actually so for example for bilinear accumulators and vector commitments both have linear size parameters but for the stateless setting those linear parameters are only problematic during the setup in the sense that you have to do this large setup but once you do it in the protocol you never have to deal with their linearity in the protocol each user for example only stores their constant size update key the miners only store constant size things there's the proof serving nodes

which compute the proofs which need the linear public parameters so i guess that's slightly there's an asterisk there there are some entities that deal with them but they're not as problematic as one might think uh but yes i agree with you they are a pain in the butt yeah yeah so yeah so i think you know alex answer your question the first thing that i think of is can we cross incremental and update him freeness for the aad you know updating the aed proofs uh might be useful for the certificate transparency setting where each server web server has their proof with respect to the log and as new things get added to the log they need to update that

proof and update hints might be annoying in that setting too yeah so i think even cross-incremental aggregation for aeds might be useful well uh because you might imagine a world where you have a bunch of transparency locks you might have a certificate transparency log you might have a software transparency log you might have a i know machine learning data transparency log and you might have programs that talk full of these things and and cross-aggregating proofs across these logs might be important so even even here can we get strong

binding and cross incrementality that would be nice does that have to reduce do you have to i guess then solve the underlying problem of the hash because if you introduce the hash function then you need to like is that limiting you from going to strong binding versus weak binding or is that is that an unrelated problem no the the hash function is unrelated to the weak and strong binding for aads if we could get cross incrementality even across dictionaries with different parameters that would be okay too because the logs could conceivably have different public parameters it wouldn't be that big of a problem and it's not like you need to rerun the trusted setup the public parameters only

differ in the hash function not in the modulus and so that would be okay but yeah i think it's quite open you know it's uh if you look at the stable there's only one two three four five six authenticated dictionaries from non-merkle assumptions that i could find in the literature uh so there's not a lot of work on this um you clearly get more power from from algebraic constructions what else can you do we need to find out cool thanks thailand uh i mean

uh how um anyone else have any more questions uh about the paper or any related kind of topics and i'd say if not then i think we could probably wrap up unless unless you want to say anything else uh no nothing beyond thank you for your time attention questions and feel free to reach out if you want to collaborate on why i say things or bilingual things or yeah thanks for coming thanks so much for doing the study club and thanks to everybody for joining

and thank you again anna for having me and alex for organizing totally i think you both need to stop your recordings when you have a chance all right