zkSummit6: Pointproofs: Aggregating Proofs for Multiple Vector Commitments – Leo Reyzin – Algorand

Transcript

[Music] all right so um i'm going to talk about point proofs um which is a name we gave to aggregateable proofs for multiple vector commitments and i'll try to define all these terms as i go along uh this is um work that was done at algorand jointly uh with sergey gorbanov hotek we and jen feijiang i'm leo razon and people have since scattered to various other corners of the globe but i'm still a diagram so there we go um all right let's consider a scenario that's uh

hopefully comfortable for for most of us uh we have um alice who has a message m um and she hashes it and gives a short hash of the message to bob then we can view that as a commitment to this message in the sense that later um when alice wants to reveal the message she sends it to bob and he can just check that the hash of the message is equal to h and so alice did not change the message between the time when she first committed to it and the time when she revealed it and this uh sense of the term commitment is uh not hiding it's not designed to hide m because for example exhaustively searchable um you know somebody could exhaustive search for him

it's just designed to bind alice to m so it's binding but not hiding in the crypto terminology these are the kinds of commitments i'm going to be talking about so that's that's a simple one message commitment that we just saw now let's talk about vector commitments um they were formally introduced by catalano and fiori in 2013 although they existed before in various forms but the definition they're the ones to first sort of name them and the idea is that alice should now be able to commit to n values not just one with a single short commitment which we're going to call c and then she should be able to reveal just one element let's say the ith element

and a short proof that the ith element is correct and bob should be able to verify um against the initial commitment given the index i and the message mi and the proof and an important feature of the structure commitment as opposed to the single commitment we saw before using a hash function is that alice doesn't need to reveal everything right this uh considerably saves bandwidth because she just needs to she can just reveal one element of the vector uh leo i think we may have a question someone raised their hand here i'm not sure if they meant to but let me just see if i can pull them into the chat and uh and if they have a question i'll let them ask if it disappears in five seconds then we'll know it was

potentially a misfire but uh yeah sounds good uh and yeah just for a quick reminder for folks only only press your share audio video if you want to ask a question here and you can do that and that's no problem uh or you can or you can drop a drop the question in the chat uh great okay i think it must have been a mistake so leo why don't you go ahead and continue sounds good so there's a well-known solution to this problem of revealing just one element and that's merkle trees uh they are based on hatching just like the previous commitments but they put hashing in a tree um essentially a binary tree where the leaves are the messages am i and then you hash it in pairs all the way up to the root and the only problem from our point of

view is that the proof size is is fairly big the proof in this case for a miracle tree is going to be the authenticating path all the hash values on the way from the leaf to the root which is 32 log n bytes then what's log n well log n sort of is always somewhere between uh you know 10 and 40 in in real life um so we're looking at something like a kilobyte okay so now what we want to do is have vector commitments with short proofs and the way we can accomplish that um is by a technique of liberty and jung which i will share in a little bit once we get to the technical details it's based on pairings over elliptic

curves the proof size is just one elliptic curve point which is 48 bytes for the kinds of curves we need to use there and that is uh regardless of n so it doesn't grow with an unlike merkle trees and 48 bytes is much smaller than even the smallest merkle trees will give you the caveat is that you need public parameters which consist of three an elliptic curve points but once you have those public parameters they're fixed and sort of hardwired then the rest then the proofs are very short and what about if i want to have short proofs for several elements what if alice wants to reveal not just one element of her vector but let's say k elements so at k indices i1 through ik elements mi1 through mik

and one single proof for all of them so she wants to reveal a sub vector um so then bob would know the the subset right and for uh consensus of terminology i'm going to call the subset s that way i can have you know s s is my set of vectors m sub s is the sub vector and i want a single short proof pi sub s and i want bob to be able to verify all of that um and there is a way to do that and specifically sub-vector commitments of la malavalta from just a year ago also based on pairings over elliptic curves give us a proof size of one elliptic curve point again 48 bytes uh regardless of the size

of the original vector and regardless of the sub vector size however the the public parameters grow where they were linear in and in the liberty new vector commitment they're now n squared which is a bit of a problem right because in square elliptic curve points if your vectors are of length a thousand and that's like a million elliptical points in public parameters and that that's a bit big um okay so let me get to now our goals of the work that i'm presenting the goal number one is proof aggregation so let's proof aggregation um if alice commits to a bunch of elements i want her to be able to reveal a few elements with their individual proofs so

maybe she reveals element i1 with its proof and element i 2 and so on up to ik with their proofs they each have a proof but i want somebody to then be able to compute a single proof for this entire subset s si1 sik and aggregate these individual proofs into a single subset proof and then forward this on to bob and bob should be able to verify just like bob did in the originals in the in the previous slide sub vector commitments a single proof for this entire sub vectors and why might i want to do that because maybe alice is a distributed system she's revealing these proofs to different people at different times right she's maybe submitting

transactions to blockchain from different places uh it's not actually a single alice and then i want to be able to get to aggregate these in order to save on bandwidth somewhere so our first contribution is that we actually are able to do that based on pairings in the random oracle model our proof size is one elliptic curve point again 48 bytes uh regardless of nnk so unlike prior work we can not only have a proof for a sub vector but we can have um an aggregation of individual proofs into a single proof from a subvector by anybody and that that person doesn't have to know

the vector um and we have a short public parameter so we went back from the n squared of line molar voltage to just 3n elliptic curve points okay so that's our first goal um our second goal is uh more ambitious what we want to be able to do is imagine that we have a bunch of uh alice's alice one through alice l uh and each of them will commit to a vector of her own so m1 mn ml all the way right through ml um and now bob has a bunch of these commitments

and these various analysis will reveal some sub vectors and their proofs right so the first alice might reveal a sub vector one uh with its proof that itself the proof could have been computed in an aggregated way using the the sort of what i presented on the previous slide um and the second alice might reveal her own subset and so on and then what i want to be able to do is to again for anybody to aggregate these sub vectors into a single proof that can then be given to bob so bob is going to be given the subsets um and the elements of these indices which is sort of necessary that's the information he actually wants plus one single short proof and he

should be able to verify all of that so cross commitment proof aggregation has not been done before we actually define and achieve the first cross commitment proof aggregation where again the proof size is just 48 bytes which is one elliptic curve point uh regardless of l and n and subset sizes so regardless of how many analyses you have how long the vectors are and how long this upsets the reveal and our public parameters are going to stay at again 3n elliptic curve points uh we just wanted to stop you here quickly there's one question in the chat that uh aline i think

took a stab at answering but just just wanted a flag for you and the question is what is the cost of aggregation uh yeah go ahead aline thank you for uh for answering uh you answered correctly so the cost of aggregation and we're going to talk i'm going to show how it's done and talk about it in more detail but for each thing you're aggregating you are going to pay one elliptic curve exponentiation um or scalar multiplication depending on how you prefer your elliptic curves to be named um great all right so um good the assumptions crypto assumptions that we need are um the random oracle model and pairings uh

and specifically on the pairing side we need something called weak bilinear deformant exponent assumption um and the algebraic group model which sort of models the pairings as somewhat idealized primitives okay so now that i've told you what it is we've done you may ask how we do it and why we care let me do the how first and then come back to the y okay so the how i need to give you a bit of background on bilinear pairings and then that will hopefully help understand how we actually do it so here's how we're going to view by linear pairings we're going to think of

a group generated by some generator g where discrete log is hard we're going to call that a source group and because writing things in exponential notation is a pain and g is always going to be our generator instead of g to the x we'll write curly braces x in red so it's both red and curly braces just so you can see it in case color is not coming through or your color blend okay here's an important thing about exponentiation given n and x in curly braces we can compute n times x right that's just raising g to the x to the power n and also given x and y which are actually g of the x and g to the y right

we can compute x plus y that's just group multiplication so uh keep that in mind that given n in plane not in curly braces actual n and x as g to the x we can compute these things okay the second part of our setup is that we need a different group again of the same size it's called a target group it's going to be generated by something called gt a different generator in a different group and discrete log is also going to be hard in that group and in that group instead of using curly braces and red we're going to use square brackets in blue but the group by itself behaves the same way the same computations are possible given n and x you can get an x given x and y in blue brackets you can

compute x plus y and the third ingredient that connects these groups is a bilinear map that takes x and y in the source groups and gives their product in the target group so it sort of can compute stiffy helmet for you x times y right which is a magical thing that should be hard but it doesn't quite do that it moves things to a new group so this my leading map only works for two red elements to give you one cyan element and any kind of inverse is hard it's not they can go back and then move x y into the red curly braces and then do one more to get

x y z it doesn't work like that this is sort of a one and one time thing once you've moved from red to cyan you stay there uh for those who are a bit more familiar with this uh the connoisseurs of bilinear pairings we'll know that actually often two source groups that are slightly different uh but for simplicity we will stick with one source group here so there's one source group and one target group in reality they're actually a left source group in the right source group but that's not relevant for for the purposes of this talk okay so that's the background and now i'm going to tell you how commitments from libert and jung work there's something interesting about our work what we actually were able to do and

what we only realized after sort of doing the work and reinventing the commitments is take the commitments of liberte and jung and make them aggregateable um so libertarian commitments are from about 2010. i forgot to put the date on the slide um here's their trusted setup the trusted setup remember i told you it was going to be a linear number of elliptic curve points the trusted setup needs the following points it needs in the red group the curly braces group it needs a a squared a cubed a to the n all the way to a to the power 2n n is the length of our vector here so we need double the length of a vector but we do not need in fact we should not

have element a to the n plus one okay remember again these aren't curly braces so it's not like given a you can compute a squared this is g to the power a and g to the power a squared and g to the power a cubed and so on so a to the n plus one is not there a to the n plus one is only available in the target group in the blue brackets okay so let me cross it out just as a reminder that it is not there and nobody should know it and this setup has to be trusted if somebody screwed it up we're in trouble unfortunately it's a relatively easy actually quite easy npc multi-party computation that can give us the setup where you need a random a and basically you can have a multi-party computation where each party comes

and modifies the previous party's result by re-randomizing it with with its own random a and then the end you will end up with a product of all the a's so it's sort of a non-interactive multi-party computation anybody can come and modify the previous results and add their own randomness it's a bit like sort of collecting a randomness for for uniform random strings and you can prove that you actually modified it correctly without too much trouble using billionaire pairings so the setup is not too bad once you have this setup okay oh sorry this is an important thing that our assumption implies that a to the n plus one that missing element in the

source group is hard to find given everything else you you have it in the target group but you can't have it in the source group okay so once you have this setup you can ask all right how do we commit and the way we commit is we have again a vector of length n right we want to output a commitment c we're going to take to take the following result we're going to multiply a by and one remember one is being in the one is in the clear it's not in any group um so we can multiply on one a by one and then we can multiply a squared by m2 and a cubed by m3 and so on and then we

can add them all up because we know how to add red elements and that's going to be our commitment so one way to think of this commitment is that it's essentially a dot product of two vectors it's a dot product of the m vector and the a vector and the reason we're able to compute this uh this dot product um even though the a vector is in the exponent it's not actually known to us it's g to the a vector right it's because the m vector is known so the m vector is known and that's what enables us to compute the dot product and that's our commitment then how uh not actually our commitment that's the liberty and commitment how does one then prove um an element of this vector so to prove m1 here's the proof i'm going

to do um i'm going to this is a there's a deliberately crossed out element i'm going to imagine that i multiplied m one by a to the n plus one but of course i can't i don't have a to the n plus one nobody has it and then i'm going to multiply m two by a to the n plus two and three by eight to the n plus three the sort of the tail end of the red vector is going to get multiplied by the original vector except the m1 i'm proving that m1 has some value i don't actually need to include m1 in my proof i need to include all the other elements in my proof and the way i include them is by multiplying them by the tail end of this vector and this multiplication essentially places a 1 into the one

missing position so the way to view it um pictorially is that i again do the dot product of the m vector with now the tail of my public parameters except the missing element of the m-vector i did not use okay so that's how i'm going to come up with a proof form one what about a proof for m2 the proof for m2 is very similar um except i'm going to shift oh there's an error on the slide best fixed in real time because it's going to be very confusing voila okay there we go the way i improve m2 is i

shift the vector 1 to the left and now m2 is in the missing position right m2 is in the position where i don't have the public parameter a to the n plus 1 and i again do a dot product of the m vector with the a vector that piece of the a vector that i'm currently using so that's going to be the proof of m2 and the proof of m3 is going to be again a 1 shift of the m vector so the proof of m3 is a dot product of the m vector with a portion of the a vector which portion the portion that makes sure that the thing i'm proving is actually in the gap in the public

parameters okay so the proof for each element consists of a dot product of all the other elements with the um with a relevant portion of the public parameters vector okay so these are all the proofs eventually if you go all the way to the left right for proving the nth element it's going to be a dot product uh with a again the almost the left portion left most portion of the public parameters so proving and commuting look very similar and sort of previewing once we're going to start talking about the cost you can see that both proving and committing takes a linear number of elliptic curve operations in the length of the vector okay so generically if you prove want to

prove mi you put the ith element under the hole in the public parameters and then you dot product the rest okay so now given that this is the way you prove things how do you verify things what does the verifier have let's think about it carefully the verifier has the commitment which is an element in the source group uh the index and the value that is being proven and the proof okay so here are the things the verifier is going to do the verifier is going to first move the proof over to the target group which is where the bilinear pairing operation comes in um because remember the pairing operation as it as it

takes to write elements it'll multiply them together to give us a blue limit so we'll just multiply pi by 1 to give pi in the in the target group and then and this is the more interesting pairing operation we're going to multiply our commitment by a to the n plus 1 minus i if you think about what that does it'll shift the commitment to the right exactly to where the proof was it'll shift the commitment to make it so that the element we're proving the eighth element sits right under a to the n plus one right because um a to the n plus 1 minus i plus i is i is being the ith element is a to the n plus 1 that's the missing

piece okay and the verification equation then after i've done these two shifts is simply to check that the proof is equal to the shifted commitment okay the shifted commitment is just a shift of the dot product vector i places to the right but the proof does not have one thing what does the proof not have the proof doesn't have the eighth element multiplied by a to the a plus one so i'm going to subtract it how can i subtract it as a verifier i don't have a to the a plus one in the red i have it in the blue which is exactly what enables me to subtract it because having a to the n plus one and the blue is enough uh to be able to do operations in the target group

so that's the entire verification thing it's two pairings and um and then we have to do a comparison which is nothing okay so those are your sorry liberty and commitments um and went to invented about 10 years ago uh and actually quite simple right it's dot products to commit dot product to prove and to verify you shift things to the target group and you shift the commitment over to the right to look like the proof and then you may ask okay well why is this secure like it yeah it works but why is it secure here's security intuition imagine that i wanted to change my i wanted to lie about what am i

is okay if i want to lie about what am i is this equation needs to work how is this equation going to work okay what am i what are my choices as the adversary what can i mess with well i can't mess with c the commitment has been committed i can't mess with a to the n plus 1 minus i or a to the n plus one those are uh in the public parameters the only thing i can mess with is the proof in this equation right the pi i on the left okay well how can i mess with phi i i need to add the pi i is given to me in the red it's not given to me in the blue i need to give it to the verifier in the red if i'm the adversary i need to give the verifier a red pie i

because the verifier is going to move it over to the blue group so if i give the verifier a red pi i it better have an appropriate change to it so the verification equation is going to hold but what change the change has to be in the coordinate that corresponds to the missing a to the n plus one red element but i don't know that element it's missing in fact the assumption is that it's hard to compute so there's no way for me to change mi and add the appropriate multiple of a to the n plus one because i would have to know what i'm adding because i would uh you know i'd have the old pi and the new pi i prime so that's the intuition behind why this commitment is secure

obviously there's a whole proof behind it but the proof roughly follows the situation so now we come to our technique thanks for bearing with me for the background the technique for same commitment aggregation okay i want to aggregate let's just do two proofs i want i have a proof for pi i and i have a proof for pi j so i have a proof for the ith element the i the jth element i want to aggregate them what i'm going to do is choose random and randomize encodes because we'll have to think about how to choose them in a minute ti and tj and just do a linear combination of the two proofs with random coefficients t i pi i plus t i j and that's going to be the proof for the two elements i and

j and this generalizes in the most obvious way for three elements four elements and so on you're just going to choose random coefficients for each of the proofs and you're going to do a linear combination of the proofs with these random coefficients and the reason you can do that is again because we can multiply in the red group in the red group by black elements and then add things okay let me show you why this works so what sort of happens what is it that i'm doing i'm multiplying um pi i by ti let's just write the verification equation multiplied through by ti it's just like the original equation on the left the blue equation that you see except now it's um it's all multiplied by ti if the equation was false before it's still

going to be false unless ti is zero right so the verifier can totally multiply things by ti and not hurt security and if it was true before it's also going to be true before multiplying an equation by ti does no harm and no good multiplying the second equation by tj will be the same so if the equations were true before they're true now and essentially what happens is now i'm adding the two equations because i have t i pi into j by j here's a nice fact if you had two equations that you wanted to verify and you want to verify just one because you're lazy all you need to do is multiply equations by random numbers and then add them up if the original was true the result is still going to be true

if either of the original equations were false or if both were false then the new thing is false with overwhelming probability the only way the equation the equations were false the new thing becomes true is if you're very unlucky in your choice of t i and t j and things cancel out but if they're random that's not going to happen so if you think of the new verification equation it is pi aj on the left which is just a linear combination of pi and pi j and then the appropriate linear combination of the things on the right using distributive law there's nothing interesting going on here the verifier can still do this verification by just using the tis and tjs and appropriately modifying the

verification equation and again if you have more than two you do the same thing okay so to verify many proofs at once again let me summarize this in words we're going to take a random linear combination of the verification equations and if at least one equation fails then the combined one will fail also with high probability and then you may ask okay but where do these random tis ntjs come from there's an aggregator who aggregates there's a verifier who checks obviously we can't trust the aggregator to check that you know pick ti's and tj's because then the aggregator could pick ones that will make two false equations

into a true one by lucky cancellation so the technique is pretty standard actually the way we're going to choose random values that the verifier needs and the approver has to come up with is by the fiat schemer technique which is to hash the statement that is being proven if you hash the statement that's being proven then the prover has no chance of messing um with the randomness and the verifier can be assured that it was well chosen as long as the hash function behaves well like a random oracle so what do we need to hash in this case we need to hash the commitment the indices i and j and the messages mi and mj and if there's more of them then you hash the entire subset right and the indices that correspond to

that subset and so that's how you pick the coefficients that's the entire actually let me go back for a sec that is the entire idea behind same commitment aggregation the rest is working out the efficiency and making sure you can do this verification efficiently and um the cross commitment aggregation remember the second part of of the work which is we can aggregate the same way for many commitments uses the exact same idea it's random it's a random linear combination of proofs and of verification equations and i will not bore you with the details because the math gets more hairy there are now more commitments lying around but the actual technique is the same you take a random linear combination of

verification equations and you get the aggregated proofs and the nice thing is that we're aggregating you know 48 byte proofs but we're aggregating them into now a single 48 byte value no matter how many of them there are okay so that's the aggregation technique i want to focus on one other useful feature of liberty on commitments and that is their updatability um remember that's our commit equation and one truman gets committed by this dot product m one a plus m two a squared so on um imagine that m4 changes to m4 prime i want to update the commitment without recomputing

everything and turns out that's very easy right because if you think about what changes in this vector um the dot product c will change to c prime by just a small change i need to add uh m prime 4 a to the fourth and subtract m for a to the fourth so i can update the commitment with knowing just the old value and the new value i don't need to know all the other m values and that's going to be a useful feature in the next step that i described so remember this we can always update commitments by just knowing the old value and the new value they changed and actually the same for proofs proofs are just dot products and the same exact idea applies okay

so you can run update without knowing the other values okay so now that i've told you how we do cross commitment proof aggregation you may ask why do we care and so let me give you two applications one in a bit more detail than the other um of of why we do it okay so obviously you want to do it when you collect proofs from multiple sources and the first use case we explore in the paper is the imagine that you have smart contracts with large memory state so you have a smart contract owner and the smart contract maybe has many variables so memory is big and um the owner of the smart contract will commit to the entire current state of the memory initial state of the memory let's

say and this commitment will be known to the cryptocurrency validators who will not need to know the entire memory state of the smart contract right and it'll be one commitment per smart contract so what we're doing is we're replacing the large state of the contract with a small commitment to the state now a transaction which is a call to a smart contract may touch only a few variables in this large memory right maybe you're updating only a little bit okay so let's say that they're users who submit transactions and to many different smart contracts in each transaction that gets submitted we will submit the transaction and the variables that were touched only those that are

touched by this transaction and the proofs and then a block proposer will be able to perform the transactions because the variables that are touched by a smart contract call are known as part of the transaction and aggregate all the proofs together and then send all the transactions on all the variables touched and a single proof for all of it to the very to the validators who will verify and update every commitment because remember commitments are updatable as part of the transaction call they'll be able to see how to update the commitment which variables changed and so what we did in this example is we traded

memory state for bandwidth because now the validators don't need to have the memory state of every smart contract they need to know only what a particular transaction touched and they will be able to very verify and update every one of them but as as the trade-off they need to now find out what variables got touched fortunately they do not need to waste any space on proofs because a single aggregated proof of just 48 bytes will cover everything every smart contract and every variable touched so uh this approach makes sense yeah sorry leo yeah just uh there's a discussion that's kind of going on in the in the chat right now let me read it yeah go ahead and take a

look uh i was reading up the paper some months ago and as far as i know there's a limitation on the eye size um okay oh sorry allen is responding thinking allen there is an upper bound on the size of the vector being committed to indeed uh verification time grows with l indeed um so robert's question is verification this is not elvis it's not i this is l um right thank you robert for clarifying all right let me explain for those who are

not following the discussion um if you have many commitments then verification time will grow with the number of commitments indeed the size of the proof will not but the verification time will um and that's uh uh a drawback but note that everybody has to do work linear in the number of commitments currently active anyway because you're gonna have to run every smart contract that is being invoked so if l is the number of smart contracts that got run then uh every smart contract has to do something and yes you also need to validate the

commitment for every one of them by the way the cost of this verification is one pairing per smart contract or per commitment which is the same thing in this example but only for the ones that are touched with in this particular block so smart contracts that are uh that are dormant and not being invoked do not contribute to your cost at the moment okay robert's second question is whether we can use this for the whole blockchain state and not a single account and it seems it will not be practical for that imagine millions of accounts so again millions of accounts are not a problem it's the thousands of accounts that are in a particular block

that we need to think about because accounts that are not touched in a given block do not contribute to your verification time there are other barriers to using these vector commitments as is for the whole blockchain state because the vector length is where you run into trouble n is the size of your public parameters the size of your vector and the verification sorry and the constraint on generating proofs and there using a single vector of length one million is going to be a problem uh fortunately we have follow-up work that i'm actually going to talk about in about

two minutes that uh figures out how to use these for the whole blockchain state so robert hang on and i think i will answer your question to some extent and then maybe we'll follow up um i'll explain how we commit to the whole blockchain state um cool and we've got a few more questions i'll let how about maybe we'll let you get through your next segment so i think we've we've opened up uh the floodgates now that you started answering some questions so maybe uh why don't you i suggest this since we have 20 minutes left go through your next segment that you have prepared and then when we have time at the end we'll aggregate all the rest of the questions does that sound okay to you yes aggregate was a good pun nice job um so um uh let me just the other questions

are actually quick can we consider liberty young as a type of multi-trap door militaril i think in fact that's what it is but it's not particularly relevant for what we're doing with it but there's some work on that and then sanaz is asking uh do the validators have to know the public parameters of each smart contract so to answer another question there is one set of public parameters for everything in the entire world it's sort of oh in your code base nobody needs to generate it again um so it's one set of public parameters you can use many commitments for public parameters so it's just you know 1000 values for example that's not a big deal robert i'll i'm going to get back to your question and you can ask it again if i haven't answered it okay so actually let me talk about

the second way to use cross-commitment profession i talked about the smart contracts use case now let's think about stateless validation not just for smart contracts but maybe for the entire cryptocurrency state and since i'm getting close to time and this is an entire separate piece of work i'm going to refer you for a lot of details to a paper called aardvark um and i'll have a link at the end uh joint work with derrick clung jose gillard where we talk about how to apply vector commitments to account based cryptocurrencies but let me give you sort of the very high level view of what we do imagine that you have all the pairs of public keys and balances

everything in millions of accounts right and you want to commit to them all and put this commitment in the block header and the basic transaction is just think of a simple transaction it requires you to update balances for the public key of the sender and the public key of the receiver right and so again we can say that the users will submit the transactions the balances that are attached to per transaction the sender and the receiver and the proofs and the block proposal will aggregate all the transactions all the balances touched a single proof now so we save on the proofs it's just 148 by thing and the new commitment c prime which will go into the new block header and the verifiers should be able to verify update c and check if the result is c prime that's pretty straightforward here are the challenges that i'm not

going to discuss unless some questions come up but i don't have any slides planned for a lack of time we have what i've presented so far is a limited length vector like electro a vector of length 1000 or maybe 10 000 whatever public parameters allow you to do and this vector is an array right you can index into the ith element but what i want to do is actually have an associative dictionary i don't want an array i want to be able to go from a public key to a value that's an associative array right and vector commitments by themselves don't give that functionality the other challenge that happens with a large-scale deployment is that now you have asynchronous

transactions right because they come in out of order so the proof that i give for a transaction at the time i create it is stale it's out of date by the time the transaction gets processed potentially and so the validators cannot validate it with respect to the most recent c prime because c prime got updated now we know we can update proofs but that's expensive we don't want everybody to be updating every proof all the time so to handle asynchrony where the proofs go out of date and the validators need to update things in an asynchronous order and to convert from arrays to dictionaries we actually have a separate paper called artwork that handles these challenges

that essentially generates an associative array out of a set of small thousand length non-associative arrays by storing some extra tables storing next pointers in the array so you can know what's missing what's in the gap so you can know exactly which accounts are missing and by careful handling of these asynchronous processes that paper is on aprint and the link is 20 29.75 i can put it in the chat as well so that's all the detail i want to go into for now but i'll be happy to take more questions let me tell you a little bit about performance

of these things um and this performance numbers are i'm presenting performance numbers that are from a year ago we have not updated the benchmarks with the more efficient implementations of pairing so they should improve with better pairing libraries out there that have been produced since then a single commitment proof is essentially a single multi exponentiation so for vector length of 1000 that's a 1 000 long multi exponentiation that takes about 70 milliseconds a cross commitment aggregate is one multi-exponentiation that the size of this multi explanation exponentiation is as big as the number of commitments you're aggregating

and so that's very quick per commitment that's only 0.07 milliseconds so 70 microseconds per commitment so aggregation is fast and the verification cost the way to think about it is it's one elliptical exponentiation per message and one pairing operation per commitment um and so let's say this now you have to it's a linear combination of two things so you have to um be careful with your parameters let's say you have eight messages that you revealed per commitment as in the smart contract example maybe there are eight variables that got touched by a smart contract call then the cost is going to be 0.7 milliseconds per message and as i said these numbers can be

improved with better current implementation but that's the rough ballpark so you get an idea all right let me conclude and then uh get two more questions of the irony um what our paper does is it gives you the shortest proofs um in same commitment aggregation same computer aggregation existed before us but the proofs were considerably longer the first ever cross-commitment aggregation and the proofs are again very short 48 bytes we have a cryptocurrency smart contract application and there is an implementation available under on github under algorand point proofs um and i think that's it i'm happy to take more questions uh great um so yeah maybe

so yeah anyone who has questions feel free and raise your hand and uh uh or post in the chat and then i guess maybe leo if you want the conversation is sort of ongoing so maybe we can maybe if you can restate uh the benefit of this approach versus traditional approach for in a cryptocurrency setting oh it looks like alien wants to maybe a lien is going to stand up in a loose state and or ask the question but maybe i'll lean just for once uh i think uh alex thank you i think it's a good idea to let aline answer let me just uh say one thing robert was asking if you have 100 billion accounts then you need to recurse three times for aggregation of aggregations

um that is indeed one way to do things is to have a recur a tree essentially of vector commitments another way is to realize that um you can do quite well by just dividing things by a thousand and not recursing and so uh a set of uh a thousand uh a set of vectors that is one thousand times shorter than the number of accounts is actually pretty good already and you don't necessarily need to recurse any further or or if you feel like it you can put merkle trees on top and so on but once you've reduced things by a factor of a thousand you're doing pretty well already um but alien wanted to speak so i'm happy to let him all right let me uh bring aleene up here let's see if this works

perfect hi welcome welcome to our to our session thanks for thanks for the talk leo it was really great really really fantastic presentation uh thank you i i was wondering you know i just really wanted to follow up on an earlier chain of emails regarding the pre-computing goal proof sufficiently in this uh in this construction i was wondering if uh yeah yeah i was wondering if you've thought about whether that's possible at all or whether it's actually inherently difficult to do because of the ly structure and these dot products which have to be shifted um uh okay so asking a very good question

and i think there has been some work uh on i think it's in the context of a different set of vector commitments uh the bonnet boons and fish vector commitments where they are pre-computing all the proofs at once with some pretty clever fft like tricks but uh oh the kzg stuff or the um because bonnie boone's face is just accumulators okay so i probably will i'll probably screw up the answer right now in real time i remember seeing some work on pre-computing all of them but i don't remember the context and it wasn't the same thing as what we were

doing um my so the answer is i'm not sure a second answer may be a slightly better answer is that a lot of the techniques that i presented here are also applicable to what are known as polynomial commitments where you commit to p of x and then a reveal is evaluation of a polynomial on a given point and you can see that because right our exponents are essentially uh a polynomial a monomials a a squared and so on and so there's a pretty tight relationship between vector commitments and polynomial commitments and people have looked at efficient vector commitment uh precomputation of proof of polynomial commitments and some of the same techniques may well apply um but i have not yeah i'm not willing to sort of figure this out

in real time probably but it's a good question and we have so in an appendix of our paper actually show kind of the the polynomial commitment view of the same thing um right we translate some of the aggregations so i think the answer is then i wouldn't be surprised if something is possible but i have not looked at it myself yes probably yes i like the idea of of trying to apply the feist kovratovich technique for pre-computing polynomial proofs to this construction which can be regarded as polynomial that's interesting yeah okay cool yeah thanks so much and thanks again for the talk thanks thanks elena thank you for not making me uh ask all that repeat that from the chat so it's much more efficient for you

to just say all that i'm gonna i'm gonna send you off now but uh we'll and we'll get to a couple other questions here um great and uh so i guess maybe we'll take uh so we have time i think for three more questions we'll uh maybe we can we've got two in the chat here so leo maybe i'll let you read off of them if you see them or i can read them you tell me what you prefer okay oh no i can read them um uh so is aardvark going to build authenticated dictionaries on algorand as layer 1 or layer 2 smart assets and the answer is that we haven't yet announced how we're going to use authenticated dictionaries this is for now a research project a

paper and code there's no strategy announced yet for how we're going to release them um and then robert is asking do you see it impossible to extend the scheme for exclusion proof that a value does not exist in a commitment um so uh let me give two answers if we're just talking about vector commitments um as a pure primitive then there's no such thing as an exclusion proof because it's an array of a thousand elements arrays are initialized to something so there's always something there you can decide that it's something undefined but it is something there's no exclusion proof however if you're looking at a dictionary public key to balance let's say or

whatever then of course you want to have exclusion proofs you want to have a proof that something does not exist in your map and the answer is that yes we do provide exclusion proofs we provide them essentially in a dictionary application and artwork we provide them as exclusion proofs by essentially storing next pointers and showing that the correctness does not exist and then the technically interesting piece is how do you update these next pointers efficiently when things change so um i'm posting into the chat the links to the paper itself and to point proofs and i see that alex already posted i'll repeat it here

the link to artwork which is the system that builds on top um yeah and just maybe clarifying i think robert's follow-up question was compare you know so merkle trees you know you can show that something doesn't exist by showing two neighbors so i guess the is there an equivalent in this uh construction right so again these constructions are not in merkel trees you can show that something doesn't exist by showing two neighbors if you have alphabetized the merkle tree typically you don't alphabetize your array alphabetization is a good technique for static data structures it is a terrible technique for dynamic ones you don't want to do expensive insertions right what you do is you maintain a binary search tree or a try or something like that and you can build such things on top of

vector commitments indeed and you do that is exactly by showing two neighbors you basically show next pointers great um so with that i guess let's uh let's take one more question before we conclude does anyone else i guess we'll leave 10 seconds or 15 seconds here give some time for the lag but if anyone else has any final questions please either write them in the chat or raise your hand and uh and before we conclude here i have a question alex um what's happening during is is the break a break break or is there something happening in in on the stage or somewhere else oh we log out and we log in again you're stealing my thunder for the for the after you're my i will let you i

will let you do it on your own schedule but i think i think we might uh it looks like i don't i'm not sure if there's any other questions so to answer your question leo uh and for everyone's benefit here in the session we are there is an activity planned for the break uh we'll be meeting in gather dot town so for those of you stuck around to the end yesterday it's just kind of a virtual environment uh that where we can socialize and do different stuff we've got a lot of uh different activities that you can do in there there's actually uh there's a couple i think the top left corner of the map you can see the main stage talks replaying yesterday uh there's some chess boards poker tables and if you see a little sprite sitting by itself playing sudoku in the

corner rest assured that's me um but uh but yeah anyways i'll drop let me drop the link here in the chat now but this is where we're kind of going to be hanging out uh in between or yeah for the break and then oh perfect sean just dropped drop the link in there let me drop this one yep same way and then there's a password let me drop that in here too so you guys have it um and yeah so this is where we're gonna be during the break and then please don't go away that's the password i just posted there um in the chat please don't go away before the end of the day because we're going to be regat re uh you know kind of or meeting back up and gather

after the last talk and we have kind of a special surprise plan it'll be a new link but yeah stay tuned for that you definitely won't want to miss it so in the meantime uh i guess thank you very much leo for presenting this work i think we all learned a lot and there's a lot of interesting discussion here thank you to everyone in the session and special thanks to you aline for uh for helping me moderate and answering answering questions in the chat um but yeah thank you to everyone who attended and i hope to see you all uh in in the gather kind of space here thank you leo thanks alex and thanks everyone for coming and thanks celine