zkStudyClub: Aggregatable Subvector Commitments with Alin Tomescu (VMWare Research)

Transcript

all right so um for this study club for this uk study club we have alin tomesku welcome to the study club uh thank you he's going to be talking about aggregateable subvector commitments for stateless cryptocurrencies which is a paper that recently came out and yeah i think as as you were saying before this is the first time i guess you're presenting it and talking about it well i think we're excited to hear more we'll take it away cool cool thanks for having me anna and thanks everyone for coming so this is work with the thai avram from vmware research and the ethereum foundation research team vitalik justin dankrad and dimitri um so let's see let's talk about the

motivation of this work which is stateless cryptocurrencies so as many of you know in in account based cryptocurrencies we have the stateful transaction validation so what happens is you get a transaction to transfer coins from a user with public eye to another user with public ej and you're transferring v points and the miners go on on disk and they check that the user with public key i has enough coins to transfer to user j and this is fine and by the way so when i say state what i mean here is a dictionary that maps a public key to the balance of that account and there's also a counter there so because you want to prevent replay attacks and some folks in the community have made a few

observations so did you notice that you could actually authenticate the state and verify transaction against the digest and if you do this each block t has a digest dt of the latest state and miners no longer have to stay store the state because each user gives a proof of their balance with respect to the digest and in particular because the state changes the digest changes which means the proof has to be perpetually updated um so this is called stateless transaction validation and it slightly changes the transaction format so now as before you're transferring money from pki to pkj v coins but the transaction needs to say hey i have a proof pi i that proves user

i as balance i greater than the number of coins being transferred and this proof pi i is valid with respect to the digest at time t dt and the miner has this digest and can verify these transactions now there's some some details about how to do this right which i won't go into but at a high level this is what's happening and a really important question is why do this why go stateless and i think one answer is faster validation so there was a a paper by chippewa noi papamantu in zhang which showed that stateless validation can scale much better for really large numbers of accounts you get less storage for miners which means there's a lower barrier to entry

in the cryptocurrency and you get a potentially more distributed system and and also it makes sharding very easier because as miners switch charts they don't have to download the state of that chart so i'm gonna stop here for questions uh with respect to stateless cryptocurrencies does this make sense uh i actually i never what wha why is it called the stateless uh there's some digest of the there is a state right it's just a compressed state or something no i mean yeah yes i i agree with you ariel i think it's a it's a bit of a misnomer because there is a state it's just a digest it's called stateless because you

know the 40 gigabytes or whatever hundreds of gigabytes of account database is gone and you're replacing that with 32 bytes okay that's what i thought i just wanted yeah sure yeah yeah it's a it's an unfortunate name i think i guess state minimized might be slightly better what state minimized yes yes yeah i mean one way in which you you could call it actually stateless is that if the state is only 32 bytes then uh validation of a block becomes kind of actually a pure function and it actually can look like a pure function in the code so not fully but that's uh also something

i see let's see so that's like a pl perspective on things yeah yeah all right so uh now i want to talk about how to actually build stateless cryptocurrencies from something called a vector commitment or a vc scheme and anna pointed out that when i say vc i really mean vector commitment i don't mean verifiable computations so keep that in mind throughout the talk um so ideally you want an authenticated dictionary not a vc because remember the state is a dictionary that maps a public key to the balance of that public key and the transaction counter which for the purpose of this talk we'll ignore the counters uh but it turns out a vector commitment is sufficient um and let's see how this works well the

idea is you have a the eighth position of the vector store the hash of the user's public key concatenated with that user's balance and the public key is now slightly different than before it's the index i of the user concatenated with the traditional public key which is your normal public key that you use to sign transactions and something called an update key which is user specific and which should be small and this update key will be used to update the vector commitment when a the balance of the user changes um so let me show you a little bit kind of um what how this works so now consider you know miners that get these transactions and have to validate them and then include them in the next block

so and then also consider users that sort of keep up with the blockchain they get new blocks and they see transactions in these blocks and they have to apply these transactions their proofs and update their proofs remember each user i has a proof pi i that's valid with some digest that with respect to some digest at time t but as transactions get added to the blockchain this digest t changes and therefore each user i has to update their pi i uh by applying these new transactions to their proof so we can sort of build a list of the requirements that we need from a vector commitment scheme and one thing you need is you need to be able to verify that user i has balance i so you need this api that takes a verification key for the vc scheme

the digest at time t the balance and the public key of the user and the proof pi i and checks hey is v of i equal to this does this user have this balance um and this verification key is sort of a global succinct thing that all the users have and all the miners have so it's constant size and then miners need to have a way to update digest because remember i i'm a minor i have digest dt and now i'm working on digest dt plus one so every time i get i validate a transaction i need to include it in block t plus one so i need to update digest dt plus one with with the i need to update the state in digest et plus one so for example if i get this transaction that transfers coins from i to j

in in dt plus one i need to update i'se balance uh to decrease it by minus v and i need to update jay's balance to increase it by plus v um so so for each user i uh that changed their balance i need to do this update digest call and then as users download the new blocks with new transactions they need to update their proofs so again each transaction will change the balances of two users and the user will have to call update proof twice for those two changes per transaction and here i'm making use of this update keys so when when user i's balance changes to update the digest the miner needs to update key and remember the subject key is part of the public key of the user so the miner

has it and similarly when a user needs to update their proof because the balance of user j changed they have a user js update here again which is part of user js public key which is part of the transaction [Music] and another thing that you kind of want is remember each transaction has this proof pi i of user i's balance so if i have b transactions i would have to include b of these proofs in the in the block so it's really nice to aggregate them if i could if i could take b constant size groups and aggregate them into one constant size proof that would be fantastic and for that i would need to slightly tweak the verify pause api where i now take a set of users public keys and balances and a single constant size proof for all of these

balances does this make sense so far any questions okay um and the other thing yeah alan so you know your last step is kind of your conversion function in that sense right that's the one that would give you the law your state compression in that sense can you uh say can i even hear the first part when you when you actually pass the whole things you're you're getting a state compression in a single step when i pass also you you you batch the whole transaction set uh in aggregate yeah yes

yes so i'm aggregating uh b proofs into a single constant sized proof okay sorry so thanks okay sort of the update of the state of the blockchain if i understood the question correctly i think is step two is sort of update of the blockchain state i think yes that's what the miner does in step two as the miner works on block t plus one they need to uh update the digest of this block because this block you know has state t plus one and state t plus one has digest t plus one um but again the state yeah of the digest

again ask again the digest what of the digest aggregation of the digest there's no aggregation of the digest you can make it just as this as the merkle root the equivalent of americorps yes so you could think of it that way i suppose really each block t has a digest dt of the state at time t so dt perfectly summarizes the full state at time t and remember the state is just the balances of all the users so one way to to implement dt is indeed

via a merkle tree built over all of the accounts just like in ethereum it's a little bit like coda does it right so each transaction updates the states and in quota they just you know they they just put i mean they say the forgers or the miners or the snark worker in their case puts the transaction one after the other and each each of these transactions updates a state in in that case and you know they the proof is from one state to the other one where the next one takes the state of the previous one and in your case it's there is a an open way of updating states yeah yeah so does this rely on all of the balances

being public like encoder when you've updated the tree it's a it's a very interesting question because uh um if it didn't you could kind of get an anonymous cryptocurrency um so there might be ways of hiding the balances since miners get these transactions that reveal the balances there's no hiding uh so can there be a partition attack there i'm sorry can there be a partition attack possible that's the consensus layer this is independent of the consensus layer i mean i i guess you can use pedestrian commitments and that would hide the

values it wouldn't hide the transaction graph um sure you need to update these peterson commitments somehow and store them in the vc the pearson commitments might be if they're over elliptic curve groups they might fit i guess in a in a vc uh if you pick the right curves um that might work i mean i guess like if you just use peterson commitments then wouldn't the proof to uh that something is a member of the commitment be a linear time to verify or is there some way to do it faster well i think

the the idea is to use uh here's some commitments inside the vector commitment so the proof is still constant size yeah okay so let's move on because we could discuss here for a long time i just want to make sure that that the high level idea of stateless cryptocurrencies from vcs is clear and again the key operations is each miner has to be able to verify a proof with respect to the digest dt miners have to be able to uh compute new digest by incorporating the transactions and calling up the digest and users have to be able to update their proofs and proof aggregation is a nice thing to have but not necessary and the other thing is we would also like to be able to compute all users proofs fast if we have the full state at

time t can we compute all proofs by i at time t and this is useful for building something that is called a proof serving note in case users don't want to spend the time to update their proofs and we'll talk about this later in the talk so let me tell you what what our contributions are and for that i'm just going to show you a table that compares our vc scheme with the previous work n is the size of the vector and v is the number of proofs we are aggregating because i mentioned their variation before and so what i'm going to look at is i'm going to look at the size of the verification key because each user and miner has to store it the size of the upks because each transaction stores it the size of the proof uh because each transaction has a proof

but then we will also see if proofs can be aggregated into a constant size proof and then the time to verify such an aggregated proof i also want to look at the time to update a proof and the time to compute all proofs for proof serving notes and we can start with a a classic vector commitment stream by catalano and fiore which was extended by lion malavolta unfortunately this scheme has large vrk and upk and no efficient way of computing all proofs it does support batch proofs but it does not support aggregation from constant size proof to batchpro so you have to compute the batch from scratch which is no good for a stateless cryptocurrency then there's the famous kcg polynomial commitments unfortunately as described

in their paper they don't really tackle the problem of updating proofs now our work does exactly that in some sense it takes the scheme by kcg and enhances it in various ways with update keys with proof updates and with proof aggregation uh and with a way to pre-computerial proofs there's another variation of the kcg scheme which uses lagrange polynomials but uses it in such a way that they get really large verification and update keys and again no way to prove all uh computal proofs efficiently and actually this scheme in particular is very interesting because they actively prevent aggregation so if you're ever interested in the scheme that prevents aggregation of proofs this is your scheme you should take a

look at it uh then there's a scheme by chiproni papamantuan zhang which is based on multivariate polynomial commitments and gets logarithmic sized parameters verification key update key and logarithmic size proofs so this is nice but it's a little bit less than ideal but it's already great [Music] we have a question i guess i think that was just a bit of background noise but i think the person just muted so that's right um we also came up with a scheme very similar to to cpc uh which uh has kind of the same concrete performance actually but it supports batch proofs unfortunately it does not support aggregation

and then there's some really new nice work called point proofs which unfortunately has a large verification key and large update key and doesn't have a way to compute all proofs but fortunately it has really nice features which actually are not reflected in in this slide so a really nice feature that it has is it can aggregate uh batch proofs themselves it can aggregate batch proofs into a single uh proof and these batches can be can be bruce over different commitments so i i i recommend you take a look at this paper because it's really nice and then we have our work so our work has a verification key of size b if you want to be able to verify aggregate proofs from b individual proofs constant size update keys constant size proofs

and we support proof aggregation in quasi-linear time and we have a way to compute all proofs in n log n time so so as you can see like um we sort of uh fix the disadvantages of previous schemes um and i didn't mention it here but all of these schemes presented so far can verify these uh individual proofs in in uh in constant time mostly or in logarithmic time for this larger proof and they can update digest in constant time i mean people are asking to compare this to local trees can you do that quickly sure sure so for miracle trees the verification key is constant sized uh unfortunately for merkle trees you cannot do the proof

update the the update key to update the proof after so to update pi i after a change to j i need jay's markle proof so there's no you know static update key that i can use to do the proof update to miracle tree and there's actually a really nice paper that explores a status crypto currencies based on merkle trees by leo raisin and some other folks i believe uh it's called improving authenticated dictionaries with applications to cryptocurrencies i think um but yeah the fundamental problem there is is if i want to update pi i after a change to j different than i i need jay's marco proof whereas in these schemes if i want to update pi i after change to j all i need is the static information

called upk j and obviously like other disadvantages of merkle proofs are the proof size is there's no proof aggregation and that's about it there's a very efficient way to prove all everything in more countries it takes order and time action but yeah thanks for the the question that's actually really a good question um okay so let me let me tell you our techniques so what we're doing is we're going to build vc from univariate polynomial commitments from kcg commitments and we're going to enhance them using some a couple of tricks and the main trick that we use is partial fraction decomposition actually which was something justin drake and vitalik buterin observed that can be used to activate kcg proofs and we use it in

in a few different ways and then we also use roots of unity to get certain certain efficiencies okay so i'm first going to talk to you about how to commit the vectors and i'm going to talk to you about how to compute and update proofs and then about proof aggregation and then i'm going to conclude so some of you are familiar with this kcg scheme the idea of the scheme is that you have these uh n strong divi helm and public parameters uh where this trapped or tau is unknown to anybody and then if you have any polynomial phi of degree less than or equal to n with coefficients 5 0 through phi n we can commit to phi as g to the phi of tau now you might ask how do you compute 5 tau since tau is unknown

and the answer there is you take these public parameters these bases and you raise them to the coefficients of the polynomial and if you carry out the math you get something looking like this you exponentiate you're multiplying the exponent and then since it's the same it's the same base you can add things in the exponent and then this is actually phi of tau in the exponent um and now you i also want to mention that you can interpolate a polynomial phi from its n evaluations or end points in order n log squared and field operations so if i'm given x i and phi of x i for n different points i can compute these coefficients and n log squared n and if these x i's are actually roots of unity i can do it in n log n

and the time to commit here is actually order n i just do an order in size multi-exponentiation um okay so then uh the earliest work that actually uses lagrange basis polynomials is cdhk15 as far as i could tell if you have an earlier reference for this i would be very grateful i couldn't find anything earlier but it's possible there might be something earlier and the idea is that you you to to do a vector commitment you have this polynomial phi such that phi of i is equal to v i which is the i f element of the vector and then you can interpolate phi of x using lagrange interpolation so it kind of looks like a linear combination of the vi's and these lagrange polynomials and the lagrange polynomials look like

this and they kind of look a bit complicated but their key property is that if you take l i and you evaluate it at i you get one and if you take l i and you evaluate it at j you get zero so as a result phi of i is v i and phi of j is v j and stuff cancels out really nicely in this sum i won't go into details here but feel free to look into this after if you're not familiar with it um and this scheme the cdhk scheme sets up these lagrange basis polynomial commitments so they commit to these lagrange coefficients and they put them in there in their public parameters and there's n of these and there's a really important question about how fast can you do this how fast you can compute these commitments because you have n polynomials of degree n each so

it seems like it would take you n squared time but it turns out there's faster way faster ways of doing it and then to commit to the vector v what they do is they uh take each li and they raise it to its corresponding vi and if you expand this expression out you get something like this so you just get this in the exponent of g and this is actually just g to the phi of tau so you've committed to this phi of x in order and time um so now that's the the vector commitment uh digest it's just this c this group element and now how do you update it well if you consider phi prime of x to be the updated polynomial after a change delta i to an element vi you notice that phi prime of x is just

phi of x plus delta i times l i of x because the only thing that's changed about it vi is this delta i think and then you can easily update you can easily implement this update digest call by basically taking the old commitment c and multiplying it by li raised to delta i so you get something looking like this where you expand the expression which gives you exactly g to the phi prime of tau and basically all we need to do to to have this work is make sure that our upk i's include these li commitments which are needed to update c in this fashion um so why why does the formula depend on vi why doesn't which formula 11

formula 10 it does depend on an i so i have this li which depends on i now vi is the old value and the new value is delta i plus vi so i should have made that clear in the slide so i'm changing vi from vi to vi plus delta i so the v i is already in phi of x and i'm just adding this deltoid to it yeah that's my failure i should fix that um right so all i want to underline here is that for these updates to work efficiently i need to make these allies part of upki so upki has one li so it's still constant size that's good i want the pkis to be small okay so let's talk about computing and

updating proofs and here this is really just a refresher because we're using the kcg poly commit scheme and if i want to prove that vi is the ith element i'll just do a kcg evaluation proof so what i'm going to do is i'll have to interpolate phi of x and n log squared and time from the vector v and then i'll have to compute this quotient polynomial which is just phi of x minus vi divided by x minus i and i can do this in order in time and then i can commit to this quotient using an order in size multi-x and the proof is just the so the proof is just the commitment to this quotient um and it's constant size and to verify it i can use pairings and i i need this g to the tau

from the verification key and i check this pairing equality i take the commitment i divide it by g to the vi i put the proof here and here i have g to the tau minus gi let's expand this expression a little bit to make sure it makes sense so this is just g to the phi tau and pi i is the commitment to q i and here i have g to the tau minus i now i can use the property of the pairing to pair these two in the exponents so i get this here and here it's just a minus and now really what i'm checking is i'm checking phi of tau minus v i is q i of tau times tau minus psi so really i'm checking that q i that this this definition for qi holds at the secret trap door tau and

that's enough for security um so it's a normal kcg proof uh unfortunately it does take n log squared and time to compute because you need to interpolate the spy which is kind of annoying we actually give a new technique to compute this proof in order in time without interpolating 5x by putting certain information in upki's and you can see the appendix in our paper for that i'm not going to go over that in this talk because it turns out you actually never need to compute proofs from scratch in the stateless cryptocurrency unless you're a proof serving note but we have a different technique for that um all right so let's talk about uh actually what we bring to the table we bring to the table this new technique to update a proof pi i after a change to to to of to the

vector and let's consider changing vi itself so changing the same position for which the proof is computed and then we'll also handle the case where we have a change to v j and j is different than i so for this let's consider the quotient polynomial the new quotient polynomial for the new proof pi i prime so i'm changing i'm updating pi i to a new pi i prime and this pi prime is a commitment to this q i prime and v i has changed to v i plus delta i and if you look at this new quotient polynomial well it's it's you know it's it takes the updated polynomial phi and we're subtracting the value that we're proving

so that's the updated value vi plus delta i and we're dividing by x minus sign and if we expand this expression out a little bit you know phi prime of x as we saw before is just the old phi of x plus the delta i at position i and i'm going to put the minus inside the parentheses and i'm going to group these things slightly differently so i'm going to take this vi and move it here and this delta ili i'm going to move it here and i'm going to factor out the delta i and what i'll have you notice now is that this part is actually the old quotient commitment for the for the old proof pi i and now i've managed to express the new quotient as a sum of the

old quotient plus delta i times this annoying thing which i don't really know what to do with and what i'm actually going to do with this thing is i'm going to i'm going to put it in my upk in my update key i'm going to commit to it using kcg and the new proof pi i prime can be computed as basically i take the old proof which is just this q i of x and i take this ui commitment which is this guy and i raise this to delta i which is that guy so now i can update my proof like this i want to stop here for a second to ask if this makes sense i'm going a little bit fast too yeah actually i really oh sorry i was just gonna say i really appreciate your going through the

algebraic steps here especially for the recording uh i don't quite understand the first step here how do you get this uh quotient is given by this i feel like there should be a multiple of lagrange bases in there somewhere so um let me go back to the previous slide remember that in general if i compute a proof for vi the quotient looks like this do you agree on that okay yeah so i'll have to let's call myself of that but given that so this is so this is the polynomial remainder theorem the idea is that you write phi of x as qi of x times x minus i plus v i so if you look at the polynomial remainder theorem this is in the blog post on my website too it might give you some intuition on this and now here

there's a new polynomial because the vector changed and there's a new value because the value changed but the structure is the same it's like polynomial minus value divided by x minus sign great thank you very much great yeah and i'm glad that you think this is helpful because i i was also hoping it would be right so job done actually all i need to do to update a proof pi i after a change to vi itself is include this ui commitment in upki and then i can update the proof now there's a question how fast can i compute all of these uis and i'll deal with that question later but if i do it naively it's going to take me quadratic time because these are degree and polynomials and i need to compute n n of them for each different i

okay uh if there's any more questions on this i'm happy to take another question so that i think you know to look at the uh the half empty glass it seems like uh this is saying that like kzg is sort of uh malleable like in the sense that i can open uh there's some polynomial i i don't actually know that was committed to and it was opened and now i can open a like a change of this polynomial at some point that was never opened even though i don't actually know the it's the same point though it's uh you're updating uh at a point that was previously opened

uh yeah still i'm saying like it's a it means like if i open uh a poly not like it's not if i open the i mean it's it's secondary maybe to this but like i can open a polynomial that i don't uh know yes yes so you you had a previous opening and you've changed the polynomial and now you can get a new opening for this change polynomial as how i would summarize your concern which could be problematic for some applications right yeah no here here it uh it's the the half empty have full glass so yeah it's something to yeah to think about in other context that's right i mean it's yeah it's not fundamentally different from other homomorphic commitments right you can do a similar thing with pages and commitments

not polynomials but a similar thing right oh yeah maybe you're right maybe it's the same thing yeah um yeah so peterson is super homomorphic you can you can take two commitments and add them you can take two proofs and combine them um i touch upon that a little bit in the blog post actually um okay so now i also want to talk about the case sorry one more question yeah regarding uh you've mentioned it twice now the question of how fast one can compute these things and i'm just wondering uh i can understand why it would be a question with the lagrange polynomials

because if you are i guess a minor or something like this you will probably need to know all of them if you want to update the commitment um but they're they're included as part of the upk so whenever you update position i you have your pki which has lagrange i so actually as a miner you store constant sized amount of things and you just use information from the transaction to update things that's the high level goal of our design here we want miners to store constant size things and users store constant size things how does the miner they've got the correct upk good excellent question actually that's a that's a a very important thing to do we point this out in our paper

uh the upks are verifiable and we show in the paper how to verify them we also touch upon it in the blog post cool yeah but sorry i didn't get to ask my question which was this ui which is only relevant to participant number i and you could imagine that this participant is tasked with computing the ui themselves no yes you could and the participant could spend order and time to compute its ui actually that would be a reasonable way perhaps to set up the scheme but we actually give what we think is a better way which is at the time you set up the the the cryptocurrency you do an n login computation that computes all of these uis and puts them somewhere on a server

and each user i can go and fetch his and i'm not touching upon it here but i'll touch upon it later okay thank you yeah okay and then the user can verify that they'd be given the right ep yes that's correct yes that's neat yes um doesn't this require that all users have to be known at the inception of the cryptocurrency then uh it requires that the bound on the number of users is known because kcg is bounded um now how do you register a user we discussed that in the paper it's we use a mechanism similar to cpz uh when we address some denial of

service attacks there's there's something i haven't mentioned here i think which is what your question uh points to i haven't mentioned how uh users register in the system there's a there's a there's a scheme for doing that and it's actually a bit problematic so don craig and i had some conversations about um the implications of this and user registrations is something that you'd like to avoid so it could be the case that vcs are not the ideal primitive to build uh status cryptocurrencies on because of this registration subtlety and i touch upon this in the paper a little bit does that answer your question to some extent oh yes it does thank you okay all right so now i want to talk about

the different case where again i want to update the proof for vi but it's not that vi changed i have a different vector position v j that changed and j is different than i so i'm going to do the same thing as before i'm going to consider the the the quotient polynomial for this new updated proof pi i prime when v j changed to v j plus delta j and again like there's a new polynomial phi prime of x and i'm proving things for v i remember v i didn't change v j changed so v i stay the same and i'm the the proof is computer in this manner and i can expand out this phi prime of x it's just the old phi prime of x plus the change for for position j and i have a vi here as before

and now i reorganize things a little bit i move this vi in here and i put this dj over there and i get something looking like this and again i'll have you notice that this is actually the old qi of x right this is the old quotient polynomial for the pi i proof and i have this nasty little thing here um and the delta j and what i'm going to do is uh i'm going to commit this nasty little thing and i'll call this uij and i'm going to commit to it and let's call the polynomial uh that this polynomial uh big ui j of x and now i'll have you notice that i can update the proof as

the old proof pi i times uij raised to delta j so this is the this equation except it's in in kcg form right so i'm taking the quotient uh this polynomial it's here and i'm raising it to delta j right uh so the problem here however is that if i want to update pi i after any after a change to any j i need this upk j to include all possible uijs for all possible i's different than j so that means these upkjs will be linear sized so i want to take a a a second break here to make sure this point gets through so because i'm trying to update

any position i using the information from upkj i need to include uij for all possible eyes does that make sense yep yeah so that would make my upk js linear size so that's a no go and this is some basically a problem that i run into a couple of years ago when i was first thinking about the scheme and i tried solving it by myself and i things only really clicked after i read vitalik and justin's post on uh using polynomial commitments to do a proof aggregation using partial fraction decomposition so can you um have upk elements for the the numerator and the denominator separately

because the numerators depends on trey and the generator and these pencil 9. that's we do something like that but it's not exactly like you can have a commitment to lj and a commitment to x minus i and get a commitment to the division unfortunately kcg doesn't allow us to do that as far as i can tell but it allows us to do something good enough actually so you already have the right intuition we do so you commit to one divided by x minus sign is that right and then you can multiply them give me a second and i'll show you sorry but if you have a better idea after they'll be great to chat so what we actually do is we include enough information in upki and in upkj to reconstruct uij in constant time so

let me show you how this works so let me define this polynomial a of x that has a root at every point i in the vector so every vector position um and then i i want to point out that you can rewrite a lagrange coefficient as a of x divided by a prime of j which is the derivative of a times x minus j now i have an appendix on why that's the case i'm not going to explain why that's the case just believe me you can read a lagrange coefficient in this form and now i want to look at what this ui j of x which is l j of x divided by x minus i looks like well it looks like this rewritten lagrange coefficient divided by x minus

sign and i'm going to rewrite it a little bit i'm going to move this a prime of j here and i'm going to move this x minus i in the denominator right and now i'll call this thing w i j of x and this thing is a constant i can actually compute this constant so it also happens that if i have a of x divided by x minus i and a of x divided by x minus j i can take a linear combination of the with these two constants and actually get a of x divided by both of them or i can get w i j of x and if you consider me having commitments to these two polynomials that means i can actually get a commitment to this polynomial by

taking the linear combination of them so that's exactly what we do is we include these commitments to these two polynomials so upki has a commitment to this kind a of tau divided by tau minus i and i compute uij as this i take a i and i raise it to this and i take aj and i raise it to this so this corresponds to what i'm doing here and then i take the result which is w i j of x and raise it to this which corresponds to this so i get exactly uij of x which corresponds to uh the the end uh thing that i need that uij commitment now the the idea here is that if each upki includes this a i

and this a prime of i uh which i will need uh for for for this uh exponentiation for this guy then i can i can uh use your pki and apkj to compute uij again i want to take a break here to make sure things make some some sense so it's a good time to ask some questions so one of the points made actually in the chat was uh adrian was asking for the blog post that you're talking about the blog post that is related to this paper and the other questions from olivier the upki sounds like yippee i like that that's uh that that gives us a better

title for this paper uh let me give you the blog post right now uh uh oh you you oh it's in the chat oh okay sorry never mind uh let me return to the slides um okay uh all right so does this make sense so so dyra i think you were asking about uh how we do this before so this is how how we use two separate pieces of information did you have another idea i'm just trying to go through my head why 31 is true um yeah okay yeah you can also feel free to read

the blog post after this talk which kind of explains the same thing maybe with a bit more detail and again like i have a problem here because i have to compute all of these ais since i need to put one of them in upki and i'll talk about how to do this fast later okay which kind of brings me to the last part of the talk aggregating proof so remember i have a bunch of transactions in a block each transaction well the miner gets a bunch of transactions and wants to put them in a block and they each have a proof ideally i'd like to take these proofs and aggregate them into a single constant size proof and i call this constant size proof and i sub vector proof um so let's see first how we could compute such a proof from scratch i'm not aggregating i'm just computing it

from scratch if i had the vector because uh we'll we'll use this to to actually build the aggregation and actually an iso vector proof is just a kcg batch proof uh so uh again my goal is to prove that to to construct a proof for all vi for all i in big i so i have a subset of position v i's and the subset is called big i that's why this is called an iso vector proof so this is terminology introduced by lion malavolta and let me define this polynomial uh a big i of x which has a root at every i in big i and i'll define this other polynomial

r big i of x and our big i of little i is equal to vi and i'm going just i'm just going to interpolate this using lagrange interpolation but i want you to notice that the lagrange coefficients are slightly different now because i'm going through all j in this big i set i'm not going through all j from 0 to n right so ri of x will have degree um uh order i basically um and now the batch proof for kcg is just a commitment to this quotient polynomial you take phi of x you subtract this degree i polynomial from it and you divide by this accumulator polynomial i call it a i of x some other folks call it a vanishing

polynomial or a zero polynomial and again note that a i of i is 0 for all i and ri of i is vi for for roi that's how these polymers are defined and and i can compute these two polynomials in order i log squared i field operations using efficient interpolation algorithms and then i can compute qi in n log n field operations using an fft based division um and an i sub vector proof is just a commitment to the q i polynomial and i can compute this in n minus i exponentiations and to verify it i used the pairing as before it's very similar to verifying a single proof except here i have the

remainder polynomial commitment rather than just a single element vi and here i have the accumulator over all points rather than the accumulator over one point um and notice that the verification key now has to have all of these g to the tau to the i's from zero to the big i so as the verifier because the verifier needs to reconstruct this commitment and this commitment and for that it's going to need these g to the tau to the i powers so if i want to verify sub vector proofs for sets of size b i need a vrk that has size b so again i'm going to take a second to make sure this this makes sense any questions here

can you motivate that definition of an li star well um it's actually you could actually also define li star or for zero from zero through n if you wanted to rather than a j and i you could do j and zero n and you would still get a polynomial ri of x that has this property but it has a higher degree now and it actually i'm not sure that the proof aggregation works anymore if you define it in that way uh actually the cdhk15 paper defines it in that way and they actually actively prevent aggregation so i can say that does that answer your question partially at least and partially yeah but really all you want is an ri that is

equal to vi and this is one way of getting it another way is to say j from zero to n uh but to actually get aggregation to work this is the only way i can figure out to get it to work i could be wrong about that though star is the lagrange base on the set i right yeah um okay let's let's talk about aggregation since we're running before you move on there's there was one um there's one sort of mention in the chat here just like a double check on point 31 good i don't let's go back want to just go back to that point 31 uh let me see the chat is the result of a partial fraction yes

that's exactly right it's a very simple case for partial fraction decomposition cool so so so let me just repeat the question for the chap just to double check 31 is the result of a partial fraction decomposition and that's exactly right and it's a very simple example of a partial fraction decomposition okay so let's talk about aggregation we're basically almost done and here we use partial fraction decomposition in a more general sense and this was first observed by justin drake and vitalik butter in in their post on on polynomial commitments for reducing state in ethereum and the idea here is that if i have a fraction like this one over some product of x i x minus i's i can write it as a sum of these

coefficients and these smaller fractions and so we use exactly this property and these coefficients are actually you know you can take the derivative of this polynomial and you can evaluate it at each eye and that that's how you get these coefficients um and in appendix 2 i explain why this is the case it's actually a consequence of lagrange interpolation at least that's an easy way for me to understand it so what we do to aggregate is we decompose the quotient q i of x corresponding to the i sub vector proof and we do this as follows so remember this is the quotient as we defined it before and let's expand it out a little bit so let's write it as this it's the same thing as before and now let's decompose these these fractions

so in particular actually let's not decompose them yet let's first rewrite the ri as this which was the lagrange form of ri and now let's decompose so i can decompose a i of x and i can decompose uh well i can actually rewrite li of x as this this was a property that i mentioned earlier and it's an appendix one of this slide and now notice that ai of x cancels with this guy here um so i can rewrite as this so i've canceled these guys and i get this and here i'm just moving phi of x here right and now let's rewrite it a little bit differently so what i'm doing here is

i'm noticing that i have the same denominator here so i can actually write as phi of x minus vi divided by this denominator and then i'm pulling out a part of the denominator and now what i have is i actually have a linear combination of the qi so i've expressed q of big i which is the quotient for the iso vector proof as a linear combination of the little qis which are the quotients of the individual proofs for each vi right and this is basically what the post by uh drake and butarine observe and the coefficients are these um so if i want to aggregate a proof pi i from

a bunch of little pi i's i and big i what i do is i interpolate ai of x i can do this in i log square to high i compute its derivative a i prime of x then i can evaluate this derivative at all i to get all of the coefficients using a polynomial multipoint evaluation and now i can compute pi i as follows i can take each individual pi i and i can raise it to 1 over this derivative at i and basically equation 44 here corresponds to this equation 43 here i should have put that on the next slide right so q i corresponds to pi i and these are the coefficients and the sum turns into a product

because uh i'm doing k sorry small this step three you can do that for any uh set i also yes any set i not roots of unity uh even a subset of roots of unity not one through n but a subset like what is the constant uh oh but it's it's like log squared instead of log i guess yes yes exactly because the subset is arbitrary that's exactly right but but what is like the is it constant like two in the o or is it the big constant you can see this reference for the

constants it's quite efficient in practice i'll say um i've implemented this in c plus plus um so it's efficient to practice so so it would be um just i log i if it were all the um the roots of unity uh just yeah so just to clarify like you're the recurrence uh that gives you this is t of n is two times t of n over two plus an order n log n division so you're doing order n log n divisions in in a tree like fashion that are so you're doing one big division and then two half divisions and then four and over four divisions and that's kind of the complexity of this multi-point evaluation got it yeah so this is kind of the full

half cup of kcg manability and you can actually easily combine them into one short proof yes yes and again there's schemes like cdhk 15 which actively prevent you from doing this as a security feature um but okay so that's it job done i can have a bunch of pi eyes for a bunch of vi's and i can aggregate them into a constant sized pi of big i using this technique okay so i'm ready to conclude uh what we did here is we gave a new aggregateable sub-vector connection scheme that has constant size sub-vector proofs and normal proofs and constant sized update keys and

constant size verification proofs can be aggregated efficiently into a sub-vector proof proofs can be updated efficiently and you can use this to bootstrap a highly efficient account based stateless cryptocurrency uh see our paper for more details on that other goodies that are not in the stock we have this new formalization that accounts for these update keys so dire i asked about the verifiability of these update keys which is very important each update key is actually verifiable against the verification key there's no proof just the update key itself is verifiable we have a new security definition for kcg batch proofs with a proof uh reduction to n strong diffie-hellman uh because

unless you redefine kcg batch for security you can't reduce the sub vector security to kcg this is in the appendix of our paper we also talk a lot a lot about some subtleties of vc based status cryptocurrencies which i mentioned before like user registration verifying update keys denial of service on user registration and so on we also can support aggregating multiple iso vector proofs that are built with respect to different commitments using techniques presented in in the point bruce paper and in a previous paper by bonnet drake and some others i believe now remember i i mentioned that i'll i deferred a few things about computing public parameters fast

and to do that i actually need to use roots of unity so our scheme actually uses phi at omega i is equal to vi rather than phi at i is equal to vi and omega is a primitive and root of union and it has several advantages so the first advantage is you can compute the public grammar is very efficiently given just powers of tau so suppose you do an mpc and you get these g to the delta di's very efficiently what you can do after is you can compute the lis the lagrange polynomial commitments via an inverse fft so the earliest reference cycle i could find for this is in madars versus thesis then you can compute the ais which which

are needed to update the proofs via this new technique by feist kovratovic to compute kcg proves fast which only works if you have roots of unity then we give a new technique for computing the uis which is very similar to the fk technique in the sense that it also uses an fft and you can also compute all of the uis in n log n time and you can see our paper for that and a nice thing is that since due to the tau i's are updatable our public parameters are updatable too because all of these things can be rederived after you update the due to the towers another nice thing is that using the fk technique you can pre-compute all

n proofs in n log n time for the users so this is useful for proof serving nodes if you're going to have those to avoid users updating their proofs i also mentioned that you need this a prime of eyes in the upki during the proof update but you can actually remove them because they have a closed form formula that's really nice when you use roots of unit and that's basically it i can't believe i fitted this in an hour so i'm ready for questions nice uh so maybe in the 30 seconds we have left i just wanted to clarify it seems like updating requires on operations for all the other users did i understand that correctly uh good so that's a good question that

the talk didn't talk about so if i'm a user and i have my proof and i've i'm trying to catch up with with the blockchain which has been new transactions i need to do order b work me as a user now if i'm a proof serving node and i have n proofs for all of the end users for every transaction that's new in the blockchain i need to do order n work so that's really impractical you shouldn't do things that way a better way to do things i think is if i'm a proof serving node every time period i i'm going to spend n log n time and compute all proofs from scratch and then when a user asks me for a proof i give them a slightly out of date proof and i ask them to update it with the new

transactions in the block does that address your question i think so yeah i mean it's awesome it's it's not um terribly impractical um zero cash or z cash um if you hold a note then you have to update it for every new note commitment um there are ways of making that more efficient um that's just local tree based i see you mean if you have a merkle proof and zero cash for your note is that what you mean yeah you have to update your markup profile good good yes but uh yeah so that means that uh is that i think that's more efficient

than a vc right because you can uh batch proof updates better with michael trees uh yeah um it's just that we don't at the moment um do it in the most efficient way and it turns out not to be a big problem um i'm happy to to spend a few more minutes on questions i i do have to run to a meeting but i think i can be a few minutes late [Music] it just just maybe a remark so this uh computing that these allies yeah inverse f of t so that was really that's like the heavy

part or that was the heavy part in the like the z cache uh both both setups uh and uh yeah so it's also described in this paper with uh of mine with uh sean and uh and um matt green uh the um uh is it like one of the uh um trusted papers for mpc um a multi-party protocol for a computing the parameters of uh yeah that's before 17 yeah before 2017 i see so interesting so you and madars might have discovered this independently is what i'm hearing i know i i

no i think i think they knew it uh they knew it before they they knew it already uh uh yeah well they were discussing it or before zeke like before z cash or during they were discussing it before yeah i see uh the scalable multi-party computation for zk stock parameters in the random beacon model paper uh no so that was like about the second set up i mean that also contains the fft part but yeah the first paper contains the fft part in more detail uh actually maybe i wouldn't i wouldn't quote that paper right now because i i still need to edit it to to fix the uh

the snark bug that uh it doesn't mention so so actually just ignore my uh comment in the last minute that's a multi-party protocol for construction public prime mr pinocchio zk stock yeah yeah okay um what are the challenges of uh making this uh also zero knowledge can you say that again uh so i it's there's a few challenges so how do you update proofs pi i after a change to j since uh that kind of leaks j you want to update

a proof after a change to a vector position without knowing the changed vector position um yeah this is the reason why it's hard to have account based private cryptocurrencies basically yes um in general like i'm also not sure about how to prove a secret opening of a secret position in a vector commitment although i think that should be possible uh there's some paper from 2013 that does that but not for lagrange-based vcs um updating the digest is also tricky again you want to update the digest after an update to a secret position um but i think now we're kind of conflating stateless

cryptocurrencies with anonymous cryptocurrencies we're trying to talk about stateless anonymous cryptocurrencies which is an even higher bar if you can remember that 2013 paper then yes it's by call and let me just put it here in the chat thank you oh sorry not privately everyone yeah it's this paper um yeah i guess to anybody who's watching this on youtube i'll copy the chat into the notes so you should be able to find these links there as well great great

any more questions so i think we might be able to rap all right thank you thank you so much everyone yeah thank you for doing this study club with us thanks for everything it's been fun all right thank you elaine see you see you everyone