Fraud Proofs: Maximising Light Client Security and Scaling Blockchains with Dishonest Majorities

I explained what foot proofs are I'm gonna motivate why we actually need them and what is the problem that we're trying to solve so as we all know at the moment there's a really huge trade off or it's thought to be there's a huge trade off between how much decentralization that your blockchain system has and how much Unchained throughput you can get and effectively the argument goes that the more the bigger the block size the bigger the blockchain the more expensive it is to run a full node and so everyone will have to run a like client instead and the problem with like clients is that they accept blocks that are invalid so if a block contains invalid transactions and they will happily accept that block if the majority of the consensus has actually sort of gain consensus on that block so for example if there's a 51% attack then you could trick a light client into accepting blocks that effectively generate money out of tener or double spend and or break the protocol rules and so on and so forth because they effectively a Jew assume that the majority of the consensus is honest which is a really bad assumption though should we should we should try to eliminate so the big question that we might want to ask ourselves is how could we actually make it possible for like clients to reject these invalid blocks just like full nodes do because if full node receives an invalid block they will reject it so how can we make a light client do the same thing so that they two don't have to trust the miners and they don't have to assume that the majority of the consensus is honest so the solution to this is that we could use fraud and data availability proofs and this is what I'm going to be presenting today is based on a paper that we released last month and this is a joint work with Albert vary from UCL and Vitalik from a Syrian research we also have the link is on the screen and also we have code as well so the basic idea of food proofs is effectively that you have like clients and you have full nodes and like clients only download headers and fullness also download the entire block including the transaction there and if a full mode detects that there is some invalid transaction in that block then they will effectively send send that likely and a compact proof that that block contains invalid transaction and that the size of that proof should be significantly lower than the size of that block so the big the original Bitcoin white paper actually and briefly mentions a concept like this called alerts I wished in a single sentence and the idea of alerts as Satoshi proposed them was that a full mode could send a light client a message to alert them that the block is invalid and that would cause the light client to have to redownload the block and validate that block again but the problem with is with this is that as a full node I could just lie to all the light clients and say all the blocks are invalid and so effectively the were in the worst case scenario the efficiency of the system for lack clients is no better than downloading the whole block chain again so it boils down to running a full mode again so it doesn't really work also has been some discussions in the Bitcoin space about having compact for troops which is what I just discussed but some of these earlier proposals they propose a different fraud proof for every single way to violate the rules of the protocol so for example you might have one for three for double spends one for proof for utx is no existing and so on and so forth so what we can do here and what we're going to do here is simplify everything so that you only need one for proof and to understand how this could work is we have to remind ourselves that we could generalize the blockchain as a state-transition system which is what aetherium actually does so effectively you have a transition function you have that takes in as input the state of the blockchain and some transaction and then every transaction modifies the state of the blockchain in some way and then so between block X I'm block X plus 1 you have a number of transactions and they modify the state in some way and in between those transactions if you apply those transactions sequentially you have many intermediate states as you can see in the diagram so what happens if there's a one transaction is included in the in the block that has an invalid that is invalid and modifies the state an invalid way that is illegal or not allowed so if this is 50 51 percent attack the minor could do this and insert this malicious block into the chain and like clients I'm sorry malicious transaction into the chain and light clients would happily accept it so we need a way to prove we need a way for full nerves to prove that this has happened so that so that light clients can reject the block as well and we need to do this in a compact way so to do this we needed some way to commit to the state of the block chain in the in in the block headers so at the moment a theorem uses petrushka Sri to effectively represent the entire state of the blockchain in a single route and you can effectively represent the entire state of the blockchain as a key value store ie the accounts in the blockchain and values but recently and one of the proposed changes in certain serenity is to actually change this structure to something a much simpler structure called the sparse Merkle tree which is a much simpler way to actually store the entire represent the entire state as a single metal rule and the basic idea of response memory is that it's basically a normal map with tree but with an insanely large number of leaves so if you want it for example to represent every single possible sha-256 hash then the size of your Merkle tree would have it would have 2 to the power of 256 leaves and you might be asking how is it even possible to actually compute this macro tree and actually there's some neat tricks that you can do such as for example and if you consider the fact that most of the leaves in this tree will be empty No we'll have a zero or default value then then you can effectively assume that the vast majority of the intermediate nodes in this tree will have the same value so you don't have to come you don't have to recompute every single node in the tree you can just because you know that the vast majority of these nodes only contain children with zero values so effectively it is pretty much as efficient as a standard map will be and so if we do this then we could effectively do this concept called stateless or clients so and instead of imagining the blockchain as a state transit state transition system imagine the blockchain as a State Route transition system because if we use this map called if you use this bus Merkle tree to represent the state of the entire blockchain as a single merkel root and you include this medical route in every block header which is what a theorem is doing right now using a patrasche we then you could also imagine that there are many intermediate routes between block X and block X plus one or the previous and next books and so if you effectively have this execution trace between every for every single transaction in a block and so what you can do is you can not just include the final state food in the block header you can also include the intermediate state foods in the block header so for example if you wanted to you could include after every single transaction you could include the new state route which is the newest 80 80 bytes state route or you could do after every few transactions it's basically a trade-off between how big the for proof is and how much extra unchained there that you that you want to put in chain so if you want so so then you could easily generate a full proof if you have this intermediate state routes in the blocks effectively the fourth proof would consist of the pre state routes of a transaction the post State Route transaction itself and also the witnesses of that transaction then the witnesses of a transaction are simply all the Merkel proofs of all of the state keys that a transaction accesses in the state Merkle tree and then you will also need the malko proofs for the transaction itself and the free and post a tweet so then this is what effectively what the fourth proof would look like and so that's all good so now we have a working unified foolproof system that only requires one single for proof rather than many different for proofs like some of the earlier ideas were proposing but the problem with this the biggest problem with this is something called the data availability problem and the data availability problem it effectively says that okay so what if a miner only distributes the block headers to the like clients so like clients or you know the block headers but what if no one knows the actual transaction data of the book so just because in the merkel route for the transactions doesn't mean you know what the data behind that my fluid is so if a miner does this then that means a full node wouldn't be able to generate afford proof because they simply would not have the data for that they would not have the data to generate that for proof so so we need a way somehow to guarantee the data availability or availability of the data in the blockchain and Vitalik proposed neat way to do this called an array using array geocoding and the the idea of region coding is that let's suppose that you have some data that is X pieces long what you can do is you can blow up that data to two x pieces long and then if you lose any X pieces in that data you can recover the entire data from any of those X pieces so what that effectively means is that this no longer becomes a 100% data availability problem it only becomes a 50% if they develop a problem because you can recover 100% data just from 50% of their so what that means is that miners if they wanted to hide a single even a single bit or single byte in data they will have to hide at least 50% over there or not release 50% of that they are so what we can do with this is we can require miners to commit to the medical route of the of this blown up or a coded version of the blood layer that is extended to X pieces instead of X pieces and then clients could use this construction to have a guarantee that the data is available and so what I could do is they could randomly sample different pieces of that block of the original block and if we can assume if we assume that the miner is trying to do this attack and has hidden 50% of their then there is a 50% chance in the first sample that you will end up in a part of the block that is unavailable and so if you sample a part of the block that is unavailable ie you request from network to give you the part of the block that is available and you don't receive a response then you would then you don't accept that block because because you think you might because because you haven't received the response to your sample and so if you keep doing more samples you can get a very high probability guarantee and that the block is actually available because so there's an there's there would be a 1 minus 2 to the power of minus s chance of landing on an unavailable block if the block is largely or 50% unavailable so and if you don't and again if you learned unavailable block you don't receive a response and then you don't accept the block problem with this tied to this is that it's not a problem with this yet also the problem of this is in this slide but just as I noted this is for this to work you need a sufficient number of light clients to make enough samples to be able to reconstruct the entire data so for example like if you only have like one client then there's not enough clients to make enough samples for 50% to sample 50% of the blog so then the scheme we didn't work now there are ways to kind of and also there are ways to get around this or well also make it more possible so that you can't fool the first number of clients but I'm not gonna mention it in this talk it will be in the it's in the full version of the paper and there's also more analysis and graphs in the papers that show how many light clients you need exactly so the problem with the schema I've described the problem with the scheme that I've described so far is that what if the miner actually incorrectly applies the erasure code so what if they just insert gibberish in the extended part of the data right so then that's not that wouldn't be useful to anyone because then if you actually lose 50% of the blog then that gibberish data is not going to help you to reconstruct the entire block so if you wanted to prove to prove this to lack clients then you would basically have to give them the entire original data and then they would have to recompute area code themselves to check that is correct and this is going back to square one because you need the entire block to do this check so the full proof it could will be equivalent to the size of the block itself and that's what we're trying to avoid in the first place so the way to fix this is that you could use a multi-dimensional array geocoding and the idea of multi-dimensional image coding is that you have you basically arranged your block data into a square so you cut it up into a number of pieces and the you arrange those pieces in interior Square and then you apply the erasure coding one by one on each row and column of this Square until you can extend into a bigger square and so if one of these rows and columns were incorrectly extended then the size of the foot proof would be limited to a single row or column because only the lifelines would only have to make these proofs at one or one row or column is incorrectly computed to be able to know that the block is invalid and this is much better because this has efficiency of a square root of the block size rather than a block size and with muscle damage with this 2d coding scheme so you can so in the example here I'm using two dimensional encoding but you could go higher you could use higher dimensions if you wanted to although personally I don't think it's worth it because there are other trade-offs so with this scheme you a minor would have to hide 25% of the data to hide the whole square so here's a graph showing given a light client that makes s samples what is the probability that they will land on an unavailable part of the block if the miner has hidden 25% of the square the height and the higher the probability than the higher the probability of a light client detecting that block is not available so we won't probably be high and you can see here that if you do say if he after three samples the probability is about sixty percent for 15 samples the probability is about 99% so so you can get you can get very high probabilities just from a reasonable number of samples so some people might consider that 99 percent is too low it's like if you wanted 99.99% you would need say samples but I think nine nine percent is reasonable because what that would basically mean is that if you are a minor and you wanted to do this attack against someone you would effectively on average need to mind about 100 blocks in order to get a chance of mining of fooling the like lion that you want to or to block into thinking that block is available when it's not so that increases the cost of the attack 100x which which i think is quite make it unreasonably expensive yeah we have some performance measurements I'm not going to go into details to them because I want to take questions but everything is quite efficient so this parameter is I'm assuming that you have an intermediate state route after every ten transactions so the slides of the for proof the state for proof will be about 14 kilobytes everything is less than a few kilobytes basically and the biggest trader of them is that if you're like client that wants to have to have a guarantee that the data's available then you also have to actually download something called the access routes we are basically every single row and column in this in this square has its own medical route that you have to download and that does increase the header by about 10x but you don't have to do this if you do want the data availability guarantees you can still run like superlight clients which have no guarantees but I think like I think this is quite reasonable trade-off and in terms of computation it's all it's all quite efficient the generating the state for proof look quite expensive here but us because my spouse medical tree implementation is quite inefficient verifying for proofs verifying sample responses verifying availability for proofs or all in Slab many second times so it's all PI efficient so if we look at the paper the link is there code is codes in github we have the code for the date availability code they read using a rigid coding also a sparse metallurgy implementation and go and a prototype for the full proofs itself thank you I'll take some questions now the reason for not adding another dimension is just simply is just the right amount that they can the minor needs to fake so actually if you if you add more dimensions the minor it makes it worse from a mystic perspective because the minor has to hide less but of the pieces of block block it's like with the one dimensional scheme you have to hide 50% with the two dimensional scheme you only have to hide 25% with a few dimensional scheme you have to hire 12.5% so that means that that means you have to sample more slices to get the same sample more pieces to get the same guarantee bility of guarantees and also the other problem with having higher dimensions is that it dramatically increases the number of milk routes that my client has download so I don't really think it's worth it unless you have insanely large block size I like incent insanely large intervals between blocks yes so this scheme be used in the context of plasma to force essentially operating party to essentially like either they provide the proof or they get slashed because as far as I'm concerned this allows somebody just you cannot know if they so I'm not an expert on plasma but there was a threat on my theorem research to ask that question and a response was from metallic said that it would be quite reasonable to do that it's like if you wanted to sorry yeah we deposit I think would be quite reasonable to do that and if you wanted to make the plasma operators evasion code dead blocks and then make the clients have to do have to do samples and maybe you could even actually make it on the main chain they have that yeah after some amount of time or some delay you have the main chain sample some of the pieces as well for extra security yeah yeah I think would be quite reasonable question yes works so so I just wondering if you change one entry in the state then how big part of the of the racial coding data structure will change so how does do changes like propagate so how so what happens if you changed the structure of the state okay so so our data structures are based on like three hushing which means we we just change a few entries but each state right just changes as a single entry and the logarithmic number of intermediate try nodes so how much data will change in the racial code after each state right okay so let's go back so this is version of the transaction there so what you're asking is if you change a single transaction how much of the erasure code would change well first of all I'm not sure why it would matter because that would change the medical roots as well so so I don't think there's a specific attack he can be from that but it would actually change it would change a significant portion it wouldn't change the entire original code I think at least yeah it wouldn't change the entire ridgid code but I would say it would change a significant portion of it so it would change at least for example the entire fourth quadrants of the of the square all right doesn't really matter because that would we also change the medical roots of the rows and columns do you write here do you write hello I was wondering if you guys explored more succinct ways of generating about verifying the proof seems to me that it could allow you to go to a higher dimensional yeah and have some blog posts on using things like proximity to make it possible to verify that the erasure code was constructed correctly without having to rely on for proofs and so this is like something completely different like this would be like if you wanted to completely eliminate four proofs then you would need a way for like clients to succeed me verify that the state transitions in the block were valid and also successfully verify that the erasure code was constructed correctly and there are some ideas that I had to do that and explore but there are currently some trade-offs something be ironed out if I recall correctly and one of the ideas had the drawback of potentially requiring medical making Michael branches a hundred times bigger in the worst case scenario but it's definitely something that people are looking into excuse me stuff another round of applause please you