Hyperproofs: Maintainable and Aggregatable Vector Commitment

Transcript

[Music] foreign [Music] presenting our Vector commitment called hyper proofs uh it's the first Vector commitment that is both aggregatable and maintainable so uh this is a joint work with Alexander trepanoi bobis Papa mantu Alan Thomas q and eupanksang we worked on this project uh when I was a PhD student at University of Maryland since then I have graduated and moved on to LaGrange labs and some of my collaborators have moved on to other places as well we love

our Merkel tree but um there are times when you want to use something else so uh this talk is about when they are used when an alternative is useful and and what properties do we have from that so uh here is a quick primer a vector commitment is a short commitment to an audit sequence of values it lets a brewer computer small proof of opening for an element in the vector and any verifier can track if this proof is indeed correct uh by running the verify function um the key security property which we want from a vector commitment is called position binding say the proverb has committed to uh

some value M at position I then the prover should not be able to come up with a different uh value M Prime approved for for M Prime uh that is accepted by the verifier under the same commitment C a good example of vector commitment is Merkel tree and Vector commitments are useful in verifiable storage stateless blockchains snacks and many applications continue to emerge so um existing Vector commitment landscape can be categorized into two broad categories in the first category we have schemes that are aggregatable meaning uh if you have an individual proof you can combine them into a single chart proof uh that's called as

aggregation and on the other hand you have uh Vector commitment schemes that are maintainable so what I mean by that is whenever there's an update in the vector we can update all grooves in sublinear time uh the aggregatable vector commitment proof schemes have constant size proof however they are hard to maintain on the other hand a maintainable vector commitments are of course they're easy to maintain but you cannot efficiently aggregate them so a good example of a maintainable vector commitment is a Merkel tree say that position one changes from value safe from 5 to 10 then all the values all the way to the digest keeps changing however

let's say I have a proof of uh inclusion proof or some value at position seven I just have to update my proof wherein it it intersects with the intersects with the proof of one so uh that's what I mean by maintainability and you should be able to do this in sublinear time um yeah the quick way to do uh aggregation in something like a maintainable scheme like Merkel tree is to snark however snacks uh in this context are not appropriate tools um for example uh it could take anywhere between uh 10 to 19 million constraints based on the choice of your hash

function and it could take anywhere between 20 to 83 minutes for a single threaded code and yeah we do have more numbers on this how uh the long story short snarks may not be the right tool to aggregate or something like a Merkel tree so up so the question which we asked in this book is can we build and if can we build a vector commitment scheme that is both are efficiently aggregatable and maintainable so uh why do we care about these two properties first uh the only other alternative we have is to be using uh snarks and they may not be the right tools it could be it's inefficient uh how and and the other key reason why we want to use uh our Vector commitment

scheme with these two properties are in the context of stateless blockchains where we need uh maintainability and efficient aggregation uh here is a quick summary of our results so our record commitment scheme is the first one to efficiently do aggregation and mainta and can maintain proofs uh since then there are other works that also have these two properties simultaneously together our aggregation is 10x to 41x faster and our we can a single update um with in say that there's a single update in the system um we can update all proofs in our 2.8 or 2.6 milliseconds and uh our our proof sizes are small it's it's login it's

around 1.44 KB bytes and yeah how would all of this comes with a cost our aggregated proof size is slightly large it's around 52 KB bytes and we also need a linear size trusted parameters where linear is in the size of the vector so a quick heads up this has slight technical details uh even if you skip them uh you should be able to follow the rest of the talk so this is going to be the broad overview of the rest of the talk first I'm going to tell you how we come into a vector uh how do I compute a proof of opening and then um how do we maintain troops in hyper proofs we also have

schemes to aggregate proofs and other cool properties however uh I'm Gonna Leave You uh I'm going to ask you to look up the paper so that you have better context so the fundamental building block which we use in our scheme is a polynomial commitment so I'm sure here's a quick one slider uh one slide and I'm sure most of you know how it works however let's say that your approval has a polynomial function f and the Brewer wants to commit to it and compute the short commitment later the Brewer wants to compute proofs of evaluation let's say in this example at I I evaluates to Y if you evaluate uh if I evaluates to Y

when you compute the function uh it can the Brewer can compute a short proof and any verifier can check if this evaluation proof is correct so um jumping into how we do our commitments say uh in this example say we have a vector of size 8 from a0 to A7 what we do is um we first have uh we first build a function f when when you plug in the binary decomposition of I say in this context I3 I2 and i1 and we get AI out of it so this is a special polynomial which we built so uh what we do if we first have a vector and we encode it into some polynomial F and the

polynomial when when plugged in with the binary decomposition of the indices in the vector gives out the value that is in the vector um so once we build this polynomial so what we do is we uh use polynomial commitments to Parliament commitments to uh compute the uh the commitment of the vector we use something called as PST commitment it's a multivariate version of kcg commitments and even if you're not familiar with uh polynomial commitments you can think of them as hash function with some cool properties and you should still be able to follow the rest of the talk but in this paper we specifically use something called as PST commitments so a proof of opening in the scheme is fairly straightforward so once we have

once we have committed to the polynomial F which is a multivariate polynomial oh another key detail is are the polynomial F has three variables this is logarithmic and the size of the vector so that's why you in this example we have eight eight elements in the vector that's why we have a polynomial of three variables yeah a proof of opening is just a simple evaluation proof uh if uh if if we can evaluate F at these these binary values and if we get a i out of it then uh we can use the PHD evaluation proof as the proof of opening since um since uh the PHD of PhD commitments

have proof size log and the size of n uh even our Vector commitment proofs are log n where n is the size of the vector in this example I have uh Pi I is which is the proof of opening has values are Pi Pi sub 3 Pi sub I 3 Pi sub I 2 and Pi sub I 1. so uh one two let's say that uh uh if you wanna you want to compute the proof of opening for a0 and let that be uh Pi zero and Pi 0 has three group elements and let's say that you have the the proof of A1 which has a bunch of group element and so on all the way for all the positions in the vector and you have

these group elements so uh it turns out that due to the algebraic properties of our polynomial uh the values that are highlighted in this chunk are actually in fact are identical so we can just replace them all into something called as let's say a group element A1 and when we go down a level below uh the values in this chunk the half this half of the chunk have identical values let's call this to be B1 and the other trunk is also identical and we call and let this be B2 so uh we achieve these properties because of the way we construct the polynomial and we can do this all the way to the uh to the bottommost level and the values

Within These chunks are the same so it's going to be C1 C2 or C3 C4 and so on so um once we have these values it turns out that these proofs form a tree where there is a specific relationship between the parent and the child and uh we uh we build this data structure and we call this as multilinear tree so uh this helps us in uh achieving our maintainability property of our Vector commitment so I'm going to redraw this uh tree in the next slide and we call this to be multilinear tree and the leaves of this tree are the specific values of the vector and all

the way to the root are the group elements that constitute the proof of opening for each each element each value in the in the tree so a proof of opening of Phi will be like I have to travel troubles from The Leaf all the way to the uh Dr root and that makes up the proof so up to say if the position of Phi index file changes by some value Delta then what we do is uh we can update this tree uh using some static information called uh public uh sorry update Keys uh and we use this update key which is specific to uh an index and the value Delta uh that's the value by which the leaf changed and we can fix the we can

update the proofs all the way to the top so so uh um this works because of the way we build our polynomials which I did not tell you how it works I ask you to go look up our paper because you have more details on why this is true but in essence uh we have some static information called update keys that is specific to uh specific to uh index in the vector and we use this value to uh fix the uh to update the proofs along the way so uh so this all so you can see that by fixing the proof to the r to the root we are we can update all proofs and the height of the tree is log n where n is the size of the vector it just takes log

and time to update all proofs um I would love to explain more about how aggregation Works however I'll defer the details the paper here's the quick overview of uh the numbers we have the Benchmark numbers so uh we should we can in our experiments we can see that hyper proofs is uh roughly uh 10x faster than a Merkel tree based on Poseidon however our verification is slower and the proof size is slightly larger however in the context of macro benchmarks when we uh when we do it we have faster end-to-end performance than Mercury based alternatives so uh in conclusion we have a vector commitment scheme that is efficiently

aggregatable maintainable and something called unstealable I didn't get to talk about unstable ability so this is a new novel property which we introduced in this work where approvert can Watermark the proofs they compute and it incentivizes proof computation and end-to-end performance is uh 10x to 40 minutes faster than Mercury based Alternatives and we can we can consider this to be an alternate an algebraic variant of the Merkel trees here is a link to our paper and I'm happy to take questions if we have time thank you [Applause]

great presentation thank you are there any use cases that you're excited about in the short term uh in the short term I'm just saying as a theoretical object but yeah a stateless blockchains is something which we can use in other places where these two properties are useful is something yeah really helpful yeah um can the same technique be applied without needing a trusted setup that's a great question I don't know how to do it but yeah that's we are actively looking into it but I don't know how to do it okay and and the aggregated proof size is that uh how does it grow within or with the uh I'm blanking out on the

asymptotics I think it's log log and uh it uses ideas from uh inner product arguments um I'm blanking out an asymptotic site now yeah cool thank you do we have some other creature [Applause] [Music]