7. Proofs-of-Custody by Vitalik Buterin and Justin Drake (Ethereum Foundation)

okay proofs of custody so just to give a little bit of context proofs our custody at this quite neat crypto economic construction and the way they fit in the context of sharding is basically to do what I call enhance voting so shouting or part of shouting is about scaling up the data availability problem so not everyone downloads every piece of data and one of the main techniques that we have is to basically sample validators at random from a pool and then we have an honesty assumption at the pool level which gives us some assumption in terms of the committee's but it'd be nice if we could go beyond just honesty and we could start using rationality so financial incentives to make sure that people vote properly in particular when they vote on the availability of data it would be nice if we could have some high level of confidence that they actually have the data that they're voting on and if they have the data at the very least it's available for them and so that's really good so if you have a committee of a thousand and your threshold is 500 then if you have 500 votes and you know 500 people in the network have this data so that's that's pretty good I guess we can start going into details of the construction so the setup is that you have a secret which is unique to you as a validator and you need to keep it secret otherwise if it leaks there will be a slashing condition which will allows whoever reveals the secret to to take half half your deposit and to slash the other half and unchain you have a commitment for that secret and that commitment is a fairly long-lived it could be something like a week or 30 days it doesn't have to be recycled very often and then the question is given a piece of data that the validator is meant to have and by the way that piece of data is identified by its merkel route so instead of just taking the data and identifying it with with its hash which for example is what bitcoin does we have the the data be a power of two so it means that you can very nicely recognize it where each leaf is a a chunk what we call chunk which is 32 bytes so this merkel root is what identifies the data and you want to come up with a scheme where you you prove that you have custody of the data and just in in in a couple of sentences what you do is that you take your your your data D for which you want to prove custody and you split it up into into 32 byte chunks and then for every single chunk you mix in your secret and and and then you merkel eyes that and you get another root are tilled which is basically a route that you and only you should be able to compute and you should only be able to compute it if you have the data so one of the things we want to prevent for example is being able to outsource the computation of this thing to other people but because of the secret part and because of the fact that the secret is mixed in that at every single piece of data you can't and because you can't give away that secret to to third party without risking having your deposit slashed it means that only you can make this computation and forevermore obviously you need the data to be able to do this computation so so you had the data so one of the just to give a bit more context even one of the reasons why it nice to have this this proof of custody scheme is is also to prevent what's called copycat voting so if you're a lazy validator and you don't have much bandwidth to verify the availability of blocks then one perfectly rational strategy would be to wait some period of time and see what other people are voting on and then if many people are saying oh this data is available then you know you also say that it's available but I guess the point of the scheme is that you know that you can't do that you can't be lazy you actually have to download the data and produce this thing now any questions so far as to why this scheme kind of proves that that's but with you would have the data so what one thing that sorry I forget to mention which is very important is that after the 30 days or seven days you reveal your secret so once you've revealed your secret then everyone else can verify the the route the proof of custody that you've submitted and if it turns out that is wrong then you can start engaging in a challenge game so something similar to true bit so the Challenger will have they'll have the secret which is no longer secret it's a public and they'll be able to compute computer route and if it doesn't match engage in the game and then we can go in the details of the game it's quite easy but that's how it works at high level you just threw out 30 days approximately what what kind of timescales would make sense to have this cycle on and why where does it come from all right so you you you you'd like to be able to reuse the secret just for for efficiency but on the other hand you don't want to use it for two longer periods and the reason is that the the proof of custody becomes verifiable only after you've revealed a secret which means that if you start cheating then you might as well cheat as much as much as you can and basically cheat doing the whole 30-day period so you know we want we want to limit the period during which bad things can happen if they do happen why not just use some sort of public key scheme to produce the the secret per per tree or whatever or per day or something like that so that you I mean wouldn't that be so than you know like number one that's like as far as security goes like hashes are pretty much the gold standard the gold standard and you have the most guarantee you'll never have to change it again number two you get much more efficiency because number three like actually the fact that we're using XOR to mix in the data basically means that you can use the branch challenging scheme also like as a way of actually recovering particular pieces of data because if you have the seed then you can get the data right back so like basically between those three there is not real like because this is pretty much the most efficient how do you mix it in xor but then if anyone has a piece of the data at that chunk they can exert it with with the original T and recover your key yes but the point is that the challenge period only starts like basically after it comes time to or rather you can only like you're great and when the proof is provided uh no challenge period keeps going for a while but the point is the proof is provided you have a leaf yes so as soon as the proof is provided the secret is gonna be known regardless right so you know granted if you use public key cryptography it's not but in this case said yes but that's fine so isn't the challenge period the period to reveal the secret know what the period to reveal the secret is before the challenge period okay so in the period to reveal the secret ends when it withdraws the life or rather we know so here's how it works right so basically if so there's some there's some point in time at which you basically have to reveal a secret and you could then as soon as you reveal the secret then the clock starts ticking and well basically if you get challenged during that time then you have to respond to those challenges but as you provide a branch your secret is revealed no correct but the point is really going to be R or yes you reveal a secret before providing any branches yeah I mean I guess the main thing that I didn't understand is so so if you're that the the challenge period doesn't start for quite a long time actually and it seems like that that makes me nervous we can yeah who knows what the threat model is but if you wanted a challenge period to be able to start almost immediately then you could you know say do a diffie-hellman to derive the secret and then or whatever and then you could and then and then you know if the guy needs to reveal the secret for this particular tree then he can do so and so that way your challenge period can start right away which I don't know the other thing that you can do is you can say so like first of all there is going to be a lot effect there's two reasons why you might want to start a challenge right one of them is that you disagree with the commitment and the second is that you think the data is unavailable so for that what we can do is we can try to work the first use case we can only target it after the seat is revealed for the second use case we can allow challenges to happen immediately and if a challenge does happen immediately you can have a rule that says that you pretty much have to submit the seeger to respond to that challenge before you're allowed to do anything else okay so yeah that's I now I see that it's actually in the threat model that you can it's because you can just make the data available or whatever yeah but but even there you kind of have to commit reveal so somehow like how do you reveal your secret before a front-runner does it and take your deposit well because only you have yours oh I see so like how do you publish the secret the answer is that the game for the the place where you can be analyzed for revealing your secret like basically and so like one day you wait for the for the end of that period to finalize before you reveal the secret but you said there's no one to publish a challenge right away oh no I see so basically the idea would be that if someone publishes a challenge right away then you wait until that finalized so then you publish your secret so if you can't respond you can't actually respond to the challenge right away you have to wait for one dynasty okay so there are delays no matter what no matter what in this game right yeah [Music] who don't they're trying to enforce one of them is that the data is available and that they need to make sure it happen happen they need to be able to Avera phi that quickly and the second one that nobody submits false challenges they can just sort that out later and that's okay but like do we want to know that the data is available now well the point of this scheme is sense to say that the data is available now it's to say that either the data is available now or a whole bunch of people are putting their money at risk well like it's deliberately kind of like Cripps we cannot make in that sense I mean it's not clear that they're putting their money at risk if they are have we have the deer right if they actually have the data in though they're not yeah so what this does not guarantee you that fur like so if this does not provide disincentives in the case where a malicious person created the data behind a proposal published the proposal the proposal header without the data but does have all of the all of the data themselves and is willing to only give out specific branches in response to challenges if you want a technology that does survive Maya that that's the route model then you can look at my eraser code ID at availability checking stuff sure so another question why did you change so why not use digital signatures instead of exhorting with yes so as I mentioned right number one it does create the property that you can basically from the responses you can record you can recover the original data number two yeah is that like beats that like makes the proof a little bit smaller and number two it makes the proof smaller number three makes the proof much lighter to verify and number four it like gets to be pure kind of like a purely hash based so there's like much less mmm like which just makes it more possible to set the protocol and stone in stone to not worry about changing it later the first expensive to verify anyway because you're gonna have the data mmm right but the but like it's still the case that you have a yeah so came from a computation time perspective hashes are incredibly cheap but you don't need the data to verify the proof you just need the merkel root and some merkel branches right no the work over but I think by except idea means merkel branches okay yeah so i mean i guess like you might get a factor of like two savings on the size of the proof i'm i'm not sure agree so from a data point of view not much from a computation point a huge mode so what's the disincentive again for revealing s2 like an outsourcer or something like that you said it was disincentivized yeah okay so first of all the outsourcer can submit as ahead of time and basically claim your money now if you if you have a model we're outsourcing to kind of partially trusted outsourcers that have reputations and so they won't do that then we could introduce another kind of game which is basically a kind of deniable challenge so the idea basically is that we allow anyone to kind of gamble on like properties of your future revealed as to some extent and like basically to the extents to which anyone has more than 50% certainty about like some brought about some property of your seed then and they would be they would be able to earn money off of this and they would be like basically in this it would be totally unknown who did this they could do this with a totally unknown accountant it would be indistinguishable from someone and you like just you doing it for fun and you can get around the first like bondage smart contract and you you burn it Sparkle you can you like you can do up on the smart contract you can do you can just use your reputation though I remember the you know in true--but for example they at some point they've introduced like a special so in order to incentivize people checking they've introduced a special game where it does the cheating does actually happen yeah do you have that in there as well or um not yet but it could be added okay on average how many do you expect like a note validator to have to you know how many challenges no just like Oh on average they receive the actual data a month later and they want to compute if it's and then the computation is very trivial like you're basically for one megabyte you're essentially hashing over two megabytes of data okay or so your your X overing over a megabyte and then hashing over two megabytes so you expect them to do it for I just expect like totally random notes to just do a we could even shove it into the default software it's very trivial okay I think we we mean what the the public key based thing or something else oh right yes so one advantage of the proof only being one bit is basically that for the purpose of BLS aggregation if you remember like pls pls signatures you can do them for multiple messages and multiple users but for every user you're adding you're only adding an elliptic curve addition of overhead but for every message you're adding an extra lipstick or pairing of overhead and so for efficiency you want the number of messages to people are signing over to be extremely small and also for an information theoretic reasons you want it to be extremely small because like if we if every single a tester includes a separate proof of custody then we're gone we're going from one bit per validator to 256 bits per validator so with this model like basically there are only two possible probe custody claims that any particular validator could use yes if you're using this pls aggregation and you're also a proposer could you potentially equivocate by like using one signature for like your aggregated total and using another one too to reveal to the network no because what the idea is that the way that you would sign is you're basically like whatever the signature is say of the previous block if you wants to claim as euro you would just sign over that plus zero and then if you want to claim a one you would sign over that hash plus one okay I have to think about it and then like obviously we'd have to have two different good fields for the zero signers and for the one signers