Limits on Revocable Proof Systems with Miranda Christ | a16z crypto research

Transcript

very happy to have one of our own back in the house Miranda Christ who's one of our some research interns Last Summer and she'll be talking about an FC paper that she has with Joe Benoit that got some of like the best paper reviews that I've ever seen so I think this could wind up being a quite fundamental result looking forward to hearing the details all yours Miranda thank you I'll be talking about um my work that will be appearing at FC limits on stateless blockchains this is Joint work with Joe Bono and this was done mostly while I was an intern at a16d crypto research last summer which was a lot of fun so I'm sure you all already know what a blockchain is but

today I'm going to be treating it as a pretty simple kind of data structure and so I'll start by describing the functionality that I'm going to talk about today so at its core a blockchain involves two kinds of parties users that submit transactions and validators who are responsible for determining whether these transactions are valid so in particular we want to make sure that a user Alice actually has the money she's trying to spend uh and one problem that we care a lot about in blockchains is the double spending problem where Alice goes and spends a coin and then she later comes back and tries to spend that same coin again and now she shouldn't be able to

do this because the coin has already been spent but we need to make sure that whatever underlying data structure we have for our blockchain doesn't allow Alice to sort of reuse a coin that she's already spent and we also want to make it very easy for people to be validators because usually we'll have some sort of assumption that the blockchain runs smoothly as long as half of the validators are honest or something like that and the easier it is for regular people to become validators the easier it'll be by say like a lot of large numbers uh for us to have a majority of honest validators so it's very important to make um becoming a validator pretty accessible and cheap so we have our users and validators and

what happens in our blockchain is users will have coins that they want to spend and validators will maintain a set of all valid coins and so if this user is trying to spend its coin c it'll send a transaction to the validators and the validators since they have the set of all valid coins we'll be able to determine by looking at the set and the transaction whether to accept or reject the transaction so the validator can just check whether the coin is in this valid set um and accept if so now as I've described the validator's job so far the validator has to maintain directly the set of all valid coins and the set might be very big in particular

for Bitcoin this set is the number of unspent transaction outputs which I have graphed here from the beginning of Bitcoin until right about now and you can see that this value has been growing pretty steadily over time can I ask a question um is this tied to the utxo model where so you seem to be saying that the set of transactions sorry a bunch of coins are valid and as opposed to a bunch of coin user pairs are valid is this choice of like how you define the set of valid things relevant to the results you're getting yeah good question so that's the way I'm going to describe it for this talk but it actually doesn't matter so our

results also apply to say like coin user pairs like you said also if you're maintaining instead of a set of coins a list of account balances um anything like that the results will still apply but uh just like for now we can think of our blockchain as operating in the utxo model thanks okay so for Bitcoin right now the amount of data that validators have to store in order to maintain the set isn't too large it's only a few gigabytes um but again if the trend continues then the number of etx's continues to grow this might become a problem down the road so even though it's not so bad now it is something that we'll have to deal with

later especially when we take him into account the fact that Bitcoin right now supports relatively few transactions per second about seven and Visa which is much more practical supports up to 24 000 transactions per second so if our longer term goal is to have a blockchain that supports truly everyday transactions and achieves a throughput closer to Visa then if we scale up the number of utxas proportionally the storage cost will become prohibitive for validators so it'll be 3 400 times a few gigabytes which starts to become more than any of us can store on our laptops and you would need specialized hardware for this so now I'll finally tell you what a

stateless blockchain is um it was proposed to address this growing State problem and make it so that validators don't have to store this full set of coins directly so in the stateless blockchain model we have validators storing only a constant sized state which I'll call B um and constant sides means that it doesn't grow as the number of coins in the set grows so this is very small you can think of it as say a Merkle root and now users are responsible for submitting proofs that their transactions are valid so since the validator doesn't store the entire set of valid coins anymore the user will have to prove to the validator that its coin is unspacked so here that's shown where the user

again has their coin c and along with C the user stores a proof pie that c hasn't been spent yet and as before when the user wants to make a transaction it sends this transaction to a validator but now in addition to the transaction itself the user attaches that proof and so the validator will check if the transaction is valid by looking at its state V the transaction and this proof and then it'll decide again whether to accept or reject so how do we actually build a stateless blockchain I'll start by walking you through a pretty simple example using a Merkle tree this is not the best construction

um but it'll help illustrate what a stateless blockchain does exactly so here we have our Merkle tree and we're going to use the leaves of the tree to store the unspent coins so the idea is we're going to use this Merkle tree to succinctly store the set of unspent coins and these coins are coins are at the leaves and the validators will store the root as their constant sized state so the way that this root is computed is by taking the hash of say these two coins to obtain this node then taking the hash of these two nodes to obtain the root and so the root will sort of commit to all of the unspent coins and the

validators will store only this root which has constant size relative to the number of coins and the proofs that users maintain to prove that their coins are unspent are the Merkel inclusion proofs of the other so here if this coin is Alice's the inclusion proof that she maintains is its Partners up the path from her coin to the root so these two circled nodes um and when Alice wants to spend her coin she sends this coin along with the proof and validators can check by hashing Alice's coin with this first part of the proof to get this and then hashing this with the next node and the

proof to get the root and so validators can check that the root obtained this way by using the proof and the transaction matches the route that they're storing but one problem with this construction is that Alice's proof changes when for example Bob's coin is spent so Alice keeps Bob's coin as part of her inclusion proof and if Bob spends this coin then in the Merkle tree this coin will be removed so say this node will be Rewritten with all zeros um and now since this is part of Alice's proof Alice will have to change her proof and thinking about like what this means for the blockchain this starts to become

a bit annoying say I'm Alice and I just want to put my coin away in a wallet and leave it alone and come back and spend it in a month if some Far Away Bob makes a transaction I will have to change my proof so instead of leaving my wallet alone I'm going to have to constantly be looking and seeing what transactions other users are making and updating my proof based on what they do so I as Alice can't operate in isolation I need to care about what everyone else in the world is doing on the blockchain if I want to make sure my proof is up to date and this is very annoying for me but there's some hope that we can do better than the Merkel tree and in fact

there are several more efficient constructions that are efficient in different ways so one other thing you might have noticed with the Merkle tree is that the inclusion proofs are quite long since Alex has to include the entire path of the tree so the groups aren't constant sized they're logarithm exercise but these more efficient constructions in particular a construction from RSI accumulators and the construction on hyper proofs from Vector commitments uh achieve constant size inclusion proofs which is much better uh vertical trees which were proposed by ethereum uh cut down on the size of the inclusion proofs but not quite to constant and this is a nice proposal as well

one other thing to note about hyper proofs is they have a nice sort of batching technique where if you're updating many users proofs at once then you can do it more efficiently in batch uh compared to how long it would take if you computed each user's proof individually or updated each user's proof individually so there are some nice improvements here but Unfortunately they all share the same problem uh which is that they require frequent proof updates so for all of these like we saw in the Merkel tree example if Bob's fences coin then Alice will have to update her proof um but rather like uh sorry if it's a

stupid question but I don't understand how you update uh once the proof is used like even before like Bob using Alice's proof somebody has to have some sort of State here because I unless you not be allowed to use the proof twice so you're asking how the validators update state after Alice spencercoin yeah sure yeah so here because when Alice makes her transaction she submits her coin and she submits her inclusion proof the values can use this inclusion proof to update the root of the Merkle tree and the way that they do this is they reset Alice's coins leave to be all

zeros and then they can hash it with this node and her inclusion proof to get the new value for this node then hash the new value of this node with the value of this node and obtain a new value for the root and then everybody else needs to recompute their proofs as well exactly yeah when the route changes everyone else needs to recompute their proof proof and so that's why this construction is a bit problematic but yeah the nice thing about Merkel trees is you can update the validator state based only on Alice's coin and the inclusion proof that she gives um and this will be true of the next example that I show as well so I'll walk through a construction from

RSA accumulators mostly to get us familiar with accumulators and also see some improvements that we can make about why the problem of proof updates uh Is Still Remains so with the RSA accumulator construction we are going to use an accumulator to store the set of valid coins and I'll describe to you now how this accumulator works we assume that we're given a generator G for a group of unknown order and the way that we're going to store the set X of all valid coins is we'll compute a state B sub X which is equal to G raised to the product of all x's and X so here we can assume that each

coin is connected to some string that is a prime uh some coins are represented by primes and then we can take the product of all of these primes um and raise the generator to this power so this is what the validators store to capture the set of valid coins um and the way that a membership proof for some coin y in the set is computed is it's going to be the state raised to the power of 1 over Y and the way that we can compute this if we know all the coins in the set X is we just compute the product of all of those coins but omit Y and then we raise G to this power

um so one thing to note here is we can't compute directly this like arbitrary element to the one over y power um unless we can do something special uh because we can't because given the strong RSI assumption in general it's hard to find this y Prime such that um or sorry it's hard to compute this value B sub X is the one over y Prime for arbitrary y Prime but because of the way that this is constructed because it's the product of everything in the set X we can compute this to the one over y just by omitting y from that product

so one convenient fact to note here is that the state for the set you get when you remove Y is equal to the membership proof for y being an X um and why is this useful so remember that the validators store a current state that they're going to need to update when a transaction is made so if the current state stored as V sub X and Alice spends a coin why the validators will need to change the state to now capture the new set that you get when you remove y and since Alice submitted this proof Pi sub y with her transaction

validators first check that this proof raised the wife power is indeed equal to the Old State um and if it is they accept her transaction and then because the new state that validator should store is equal to Alice's membership proof validators can compute the new state just by setting it equal to the proof that Alice submitted uh and so this is very nice this is sort of analogous to the way that I show to update the Merkle root using the inclusion proof before um but this is even cleaner it doesn't really require any computation for the validators they just set the new state equal to the proof but now one problem is that the other

users in the system hold proofs that are valid for the Old State but not the new state the new state is base of x to the 1 over Y and now these old proofs won't be valid with the new state because the way you check if a proof is valid is you raise this proof to the X and this is the x is going to be V sub X that's not going to be equal to V sub x to the 1 over y so that's a bit of a problem um it means that none of the old proofs of other users will be valid anymore and one cool Insight that this RSI accumulator paper has is that there are tricks for computing this new state so

all of the other or for computing this new proof so all the other users can update their proofs relatively efficiently but the fact that they have to do this update at all is a huge problem um because it means that they'll have to be online and they'll have to be monitoring other users transactions so sort of no matter how efficient you can make this proof update as long as the update has to happen it's very annoying so again when a transaction is made in this construction all other users have to update their proofs which is undesirable and and so another question when I spend by why I give it to you suppose I give I spend my why and I give it to you

how do you create a new profile like that's fact that you can spend your Z now yeah it's non-trivial so there's some like number Theory tricks that they do um but uh yeah you are able to do it with the information uh that is out there so yeah I'm not going to describe it now because it's actually a little bit involved um yeah sorry uh so the question that this leads us to ask is whether it's even possible to have a stateless blockchain where users

never have to update their proofs um and one place to look for this answer is an impossibility result by Camacho and javia from 2010 and this applies only to accumulators it says that if n elements are stored in an accumulator and half of these elements are deleted then it takes roughly n information to update the remaining elements proofs so this sort of intuitively tells us that a lot of the remaining elements proofs will have to change um because in order to update these proofs you need a lot of information uh linear and n

but it sort of doesn't apply directly to stateless blockchains yet um and so that is the question that we address in this work and unfortunately unfortunately we find that no we can't have a stateless blockchain where users never have to update their proofs and our informally stated theorem says that for a blockchain with end coins where users never have to update their proofs validators must store a state of size Omega of n um so if you have no proof updates then sort of asymptotically validators might as well store the full State uh there's

no asymptotically compressed uh scheme that you can have is this assuming that anybody can trade with anybody or will this be true even if I have end users but only another two can trade amount of stuff with another and over two can only trade among themselves good question this assumes that everyone can trade with everybody um sort of split the chain into a bunch of distinct chains where in each chain users can only interact with others in that chain then maybe you could get some savings but as long as you want everyone to be able to trade with everyone else the impossibility holds so I'll walk you through sort of a high

level overview of how our proof works we are going to show an information theoretic impossibility so basically we're going to say that if such a stateless blockchain exists um then we're going to be able to violate the laws of information Theory and sort of compress information more than it should be able to be compressed so you can think of the stainless blockchain as like a compression tool it takes this big state and compresses it into a small state and if a really good stateless blockchain exists then it's doing impossibly good compression and the way our argument will go is we're going to consider two users

Allison Bob who share a stateless blockchain and Alice is going to secretly choose a set of coins to spend and she's going to tell Bob which set she chose by transmitting him some bits and we're going to show that she can use and possibly a few bits to tell Bob which set she chose to spend so this will be our contradiction and the first thing that we need to do um is formally model a stateless blockchain which we do now so at its core a blockchain basically needs to capture a set of provable

statements that can later be revoked and what I mean here is provable statements are of the form I Alice have this coin and these statements can be revoked when I as Alice spend that coin so we need to capture some statements that at one point are true but might later become false uh and we call this sort of protocol or data structure a revocable proof system uh and we assume that at the beginning of time we're given some set of true statements so this is say an initial set of unspent coins and there should be a function that

takes in the set s and computes the state that the validators store this V along with proofs for each of the coins that each of them are valid there is also a revoke function that takes in the full state it takes in a subset of statements T that are going to be revoked and it outputs an updated State B Prime and updated proofs for all of the elements that were not revoked and there's also this verify function that is what the validators run to make sure that a transaction is valid so the verify function takes in the state a specific statement or coin and a proof

of that statement and it outputs either true or false we want two properties from a revocable proof system the first is correctness which says that proofs of true statements always verify so for blockchains this says that if if Alice behaves honestly and has a coin she should actually be able to spend this coin um and security says that it's hard to find a false statement and a verifying proof for that statement so again applied to blockchains this says that Alice shouldn't be able to convince validators to let her spend a coin that she doesn't actually have

okay so now that we have our model I'll show you our argument um we assume that Alice and Bob are two users of a stateless blockchain and so they agree ahead of time on a set of statements s say a set of initial valid coins and a proof of each of these statements and also a starting succinct State for the blockchain now Alice is going to choose her secret subset of coins to spend or revoke and she's going to run the revoke function to compute the updated State V Prime and she chooses the secrets that

uniformly at random now she sends the updated State V Prime to Bob and Bob is going to try to compute what set Alice chose to revoke so the way that Bob is going to do this is he's going to go through all statements in the set s and check if their proofs verify against the new state and now Bob is going to Output a guess of the set that Alice revoked so the way that he does this is if he sees a statement who's proof no longer verifies then he includes it in this set because that should mean that the statement was

revoked so now I'll argue that with high probability Bob is successful in reconstructing the set that Alice spent remembering that correctness says that proofs of non-revoked statements still hold so this means that if a statement wasn't revoked then since its proof still holds Bob will not include it in this guess of the remote set and security says that proofs of revoked statements do not hold so this means that if something was revoked then it's proof will no longer verify and so Bob will include it in the set that he

outputs uh and so this set should be correct and you might have noticed that I said with high probability here and the reason why Bob doesn't succeed all of the time is because our security guarantee is just that it's hard to find a false statement and a verifying proof for that statement not necessarily that it's impossible so these false proofs might exist but it should be computationally hard for Bob to find them so with negligible probability um Bob might happen to find a proof for a remote statement but this really should not happen uh

okay and so why is it a contradiction that Bob succeeds in reconstructing this set well remember that Alice had two to the size of s or to the little n choices of this set to revoke and we know that information theoretically her choice should take n Bits to encode if she's communicating it to Bob but here all that Alice sent to Bob was this updated State V Prime which remember is constant so instead of taking M bits to encode her set Alice has encoded it and only a constant number of bits and this is impossible so this tells us that such a stateless

blockchain can't exist uh because then Alice would succeed in this impossible encoding uh Miranda yeah let me just make sure I'm glad you deter with high probability comment I was literally wondering exactly that when he talks about it so just to make sure it's not so much like Bob getting lucky finding some fake proof it's just you there's some chance however small that when you go from V to V prime it just so happens that when a girl proves still works for one of the revoked statements is that right yeah exactly okay yeah yeah so if that's true then Bob sort of really succeeds in finding a

fake proof not not through any like Bob's not trying to find a fake proof it's just kind of bad luck with the uh with the update function I guess right yeah exactly okay all right thanks yeah uh some like annoying stuff to deal with that so the proof ends up looking less clean than how I'm presenting it here um but yeah that's sort of just a technicality uh sorry did you have a question uh it may be part of the unclean stuff in the paper now but I guess I'm curious whether the fact that Alice needs like exactly and bits so in code versus like

slightly less because of this I'm just curious whether this probabilistic part implies something about the total information necessary not being fully ambits but maybe slightly elapsed yeah so it implies that um her choice should really take n minus one bits to encode but yeah the loss is so small that it doesn't end up mattering for the bound asymptotically but actually actually Miranda is your is your Omega event actually n minus one or is it really like is it really like some constant less than one times that yeah I'm saving the theorem statement you

showed us earlier right you talked about needing Omega event updates like does the does the proof actually show a leading coefficient of one is it really like n minus a little low of n or is it really like you only get a half n or a third n or something like that yeah for um for this theorem where you have no proof updates I'm pretty sure it's really a leading constant of one but I would have to check to be a hundred percent sure maybe I missed it but I don't think he used any interaction between the coins uh any interaction you said yeah so even if you have two communities that don't interact with themselves that

seems linear updates are necessary linear communication is necessary um um one thing you could do is you could like have a global State V Prime uh for each of your sort of sub chains where each has an insular community that can only interact with each other and then you can ensure that if a coin is spent within your community you might have to change your proof but if a coin is spent in another Community then you don't have to change your proof and so you can get um

a sort of trade-off between the number of V primes that you store and how often you have to update your proof but I think you're right as stated um this proof still goes through uh even without some interaction assumption the next question that we ask since we can't have a stateless blockchain where users never update their proofs is whether we can relax this and only ask for a blockchain where users don't update their proofs very often and we show that the answer is unfortunately still no where if we have a constant say

blockchain with end coins and a constant fraction of coins are spent then roughly a constant fraction of the user's must update their proofs and I'll show you how we can modify the old version of the proof uh to get the slightly stronger result so remember before Alice was choosing this set of coins to revoke and getting an updated State and now she does an additional step here where she's also going to create a list of all of the non-revoked statements whose proofs happen to change so and I knew kind of

stateless blockchain we might have proofs changing occasionally uh and so Alice is going to make a list of these statements his proofs just happened to change when the state was updated and she's going to send this list to Bob along with the updated state now Bob is going to have to do some additional work when he constructs his guess of what set Alice chose to revoke and so when he checks if proofs of statements still verify against the new state he's also going to check if each statement is included in this list and he's going to Output a guess again

so what is this guess now it's going to include all statements whose proofs both no longer verify and that were not included in the list so what this list tells Bob is it consists of statements whose proof's no longer verify but not because those statements were revoked um because they just happened to change when the state was updated so if Bob sees that a statement is in this list he knows that it wasn't revoked its proof just change so he includes exactly uh the set of statements whose proofs don't verify and that were not included in this special list

and for the same reasons as before with high probability Bob is successful in reconstructing this set but the information that Alice sends to Bob has changed a little bit so in addition to sending this constant size State V Prime she's also sending this list l and the size or the length of the list depends on how many statements had their proofs changed so suppose that we have a stateless blockchain where at most K proves change in any state update then Alice is able to write this list using K log n Bits where to write down each statement or to write down the index of

each statement it takes log n Bits And they're at most K of these statements in the list so the list takes K log n Bits um and again the size of the state that she sends is constant so Alice has encoded this set in constant plus K log n Bits um but again it should take roughly n or accounting for the with high probability it should take n minus 1 bits uh for Alice to do this so actually yeah this tells us that the leading constant in that theorem is one so this gives us that o of 1 plus K log n should be at least M

minus one and rearranging uh is how we get our theorem so to State the theorem again and show you visually what it tells us um we have that for any status blockchain with end coins when a constant fraction of coins are spent then nearly a constant fraction of users have to update their proofs so this says that there's a roughly linear relationship between the number of witness or proof changes and the number of uh deleted elements or remote statements so I've plotted this relationship uh for varying sizes of the state the succinct

state that validators store and this says that as more elements are deleted more witnesses change um and what you'll notice is here each of these curves is just duplicated and shifted to the right as the size of the validators state increases uh so what this tells us is we eventually start to get this linear trade-off or near linear trade-off um between a relationship between the number of deleted elements and the number of witness changes and increasing the size of the state that validators store doesn't help very much it just sort of delays when we start to see this

relationship uh and so we can increase the size of the succinct state but it doesn't help us that much so Miranda this this this log Factor did you have a sense of this as an artifact of the argument or something unavoidable yeah uh it might be an artifact of the argument like the way that we encode the list is pretty simple we just write down each of the K indices so I think you could do a little bit better for some regimes of like the relationship between K and N

um it's like you don't really care anything I mean the Bob already knows the pie eyes right so you're literally just encoding the indices right of the statements with the proof updates yeah yeah so there's some hope that for like some regimes you could shave off the log n uh but like I tried thinking about how to encode the lists in a fancier way and it seemed like for some case this was kind of the best you could do uh yeah but like like k equals n over two kind of regime you're saying yeah yeah exactly yeah yeah okay

um but in practice like the log and the denominator is kind of in my mind it's kind of just a constant um or nearly a constant yeah so here here's another graph um where this is going back to the thing I pointed out early on where if you want to scale up the throughput uh then we'll start running into problems so here each of the curves represents a blockchain with different throughput where it only goes up to 100 transactions per second which is still very far from say Visa which was at roughly 24 000.

um and again on the y-axis we have the number of witness changes but here it's the number of witness changes per day and sorry here I'm using witness and proof interchangeably so the number of proof changes per day and on the x-axis we have the logarithm base two of the size of the state that the validators store um and so you can see here that the number of proof changes per day is basically the same as the size of the state increases up to some sort of threshold value at which point you start

to get big improvements um but for say the 100 transaction per second blockchain the size of the global state is still pretty big so it's like 2 to the 26th or something like that um at the x-axis and this tells us that unless you're willing to store something close to the full State uh you're not really going to get a useful trade-off between the size of the state that the validators store and the number of witness changes that you see per day um so basically up until you reach this point sort of varying the size of the

state that validators store is not going to help you so what does this result tell us in practice you might see it and think that stateless blockchains are dead and definitely it tells us that there's no Holy Grail data structure that solves this proof update issue on its own so like no matter how clever we are uh we're not going to be able to sort of math away the proof changes that users have to do and this is because the state that's being stored has to go somewhere so an analogy that I like is if you squeeze a water balloon then you're

never actually going to make the water balloon any smaller the water is just going to seep through your fingers and go somewhere else so what's happening in the stateless blockchains is if you're taking the state away from the validators then instead it's sort of being offloaded to users in the form of these proof updates um so really the state is just being distributed among the users when you take it away from the validators but not All Is Lost uh there are some constant factors State compression tricks that can help in practice um and if you really want to use a new model maybe you can have users Outsource

these proof updates to a third party that stores the entire state so you can still have validators storing a constant sized State and users storing these proofs but a third party that stores the full State can update these proofs on behalf of the users and this is called the proof serving node model uh and there's been some work in particular hyper proofs explores this pretty thoroughly and talks about coming up with an incentive system um to maybe incentivize these proof serving nodes to uh update these proofs where the users pay them some small fee for maintaining their proof for them but there's still a lot of work to do

here and I'm curious to see where this model goes especially because now it seems like this might be the best bet for stateless blockchains actually working so this revocable proof system that we defined for the paper is actually much more General than only capturing stateless blockchains uh again it really has these three functionalities a way to compute a succinct state from a larger set of true statements a way to revoke some of these statements and a way to verify any of these true statements um and there are many other things that fit this model one thing that kind of fits it is

actually Roll-Ups and so one implication that this has for Roll-Ups is you can't have a roll-up that has persistent account balance or any other kind of proofs so imagine that you want to have some roll up that puts the succinct State on chain and allows users to prove a statement about their account balance where the proof lasts for many many blocks say hopefully the proof lasts forever so you want us to be able to say that she has at least one coin in her account and as long as she doesn't spend that coin her proof of this still holds uh here the Roll Up is providing the same functionality as the stateless

blockchain where you have a succinct State that's put on chain and the state changes over time as other users are making transactions um and so it says that Alice's statement about having a coin must have a changing proof as the succinct State on chain is changing as well so there's sort of no way uh to get around this impossibility by using something like a roll up and in addition this impossibility result applies to any data structure that can be used to build a revocable proof system um and we saw construction a construction of a stateless blockchain from an accumulator for example so we

know that an accumulator can be used to build a revocable proof system and there are many other data structures of interest that can build a revocable proof system as well so this includes also Vector commitments map commitments and authenticated dictionaries so what are impossibility results says about these is if you have a succinct Global State say a commitment to a vector um that's where where the elements of the vector are sort of controlled by different users where each user maintains a proof for their element then if other users change their elements and the resulting commitment is updated then the original user will have to change

their proof foreign so thanks for listening uh if you're curious to checking out the paper it's available on ePrint and we'll be appearing at Financial crypto and I'm happy to take any more questions um does uh does that impossibility result for the revocable proof systems does that capture things like um like the weird vdf proof of work style like short-lived proofs that kind of thing you know methods for kind of like pushing the revocability kind of outside

of the accumulator system so what are these short-lived proofs used for um basically they are a way of of kind of um revoking a proof by uh making it you can't tell whether or not um like the proof was valid or someone running a vdf basically solved some puzzle that allowed them to create fraudulent versions of this same proof oh I see okay I vaguely remember these so I think with those you still aren't supposed to have a proof of a statement that's false so maybe like after is that correct

I'm not sure I I think that's the case um in which case the impossibility should still go through so because it's like information theoretic um it doesn't matter how long this game between Alice and Bob takes so even if it might take Bob or even if it might take Alice a long time to say compute the new state or even if it took a long time to compute the proofs to begin with sort of time doesn't matter and our argument and so I would expect it to still go through if you have vdfs so Miranda just going back to the roll-up interpretation

so should I sort of think of that as I don't know I had this mental model I was like okay so a new state diff say is published every block on L1 by the roll up let's just say you know saying what account balance has changed right and so you might expect something like like the obvious way to do it is just kind of like with every block if okay kind of balance has changed you just sort of publish basically you know the new Merkel route and sort of you know some the corresponding kind of you know proofs so the people following along can sort of update the the Merkle tree and so I think what you're saying is that basically the proof size it does does your results say this your proof size

should be scaling with the number of accounts that get touched per update is that a consequence um I don't have anything about the proof size I guess so one thing this says is if you want the user's old proofs to directly verify with the new state then the new state will have to be quite large but it doesn't rule out the possibility of including enough information in each block uh to update all of the proofs

so you're saying any roll-up that's just sort of posting updates frequently maybe you can escape this impossibility uh possibly but I think the amount of information that you would have to post to let everyone update the proofs would be very large right so that's that gets into the proof size kind of thing right so like if you do it infrequently I mean basically I mean your result is kind of saying you can't do clever batching of this stuff right yeah so I feel like that is a pretty that is a pretty natural interpretation in the roll-up world which is you know as accounts get touched somehow that information needs

to get communicated down maybe it's infrequent updates that are big updates maybe it's frequent updates that are small updates but like the total amount of updating stuff that's that's being posted has to be scaling when the number of accounts that are affected yeah yeah that's true but I think like changing the proof size is sort of not the bottleneck like our impossibility goes through even if the proofs are extremely large um because when when Alice and Bob are communicating right Alice is only sending the new Global state to Bob and so it goes through even if the proofs are arbitrarily large uh so I guess applied to Roll-Ups that

would say that um the size of what's on chain in every block would have to be quite large even if the user's proofs are long as well Miranda is my interpretation correct uh that what you're saying is impossible for Roll-Ups is if I want to have a roll up with small footprints on chain such that a user of the roll up can come online once get a proof that they have something on the roll up and go away for a month later come back to the base chain and be able to use that stale proof this is not possible unless the

footprint was in fact linear size I think that's what your result is saying yeah yeah that's much better stated exactly like it doesn't matter that my proof was massive the point is that I was offline for a while and now there's just no hope of me yeah I'm happy about it yeah exactly sure but just to clarify if I come back to withdraw from the roll up on the main chain but I can observe the full history of the roll up say if it posts some updates frequently then potentially I could I I can't update my proof in order to withdraw right because there are some linear amount of Transformations that have happened possibly they have enough information to

allow me to update the proof yeah yeah that's true but if you wanted the original proof to hold like directly verified against the new state of the roll-up without any sort of updates based on the prior history then the new state of the roll-up would have to be quite large but yeah it doesn't rule out being able to look at the history and sort of update your proof um late all right great well thanks so much Miranda good talk excellent very cool result