j2 PAIN 05 Robert Habermeier Light Clients for Heavy Chains

I work for parity technologies so some of you might know about parity already if not I'll give a brief description of what we do which is what we would call core technology so things like if you're in clients but also just lower-level applications or like infrastructure projects that other apps can can leverage so today I'm going to be talking a bit about our aetherium client specifically the light client framework so I would break this down first into defining yeah so I would put this down first to defining different classifications of aetherium clients so first we have our basic full nodes so what full nodes do is they download every single header every single block they execute them all in order starting from the Genesis make sure that not only is the consensus done correctly but also all the transactions execute correctly and all the data checks out so this is actually a fairly heavy operation and any of you have tried to run a full node recently you might notice that this is using a lot of storage on your computer a lot of CPU a lot of memory so then the next level down would be light clients so that's primarily what I'm going to talk about today so what a light client does is it just checks the block headers so it starts at the Genesis say and downloads all the headers starting from there and it verifies that consensus has been done correctly but it doesn't execute the transactions in the block so it does lose a little bit of information along the way and perhaps a little bit of security and the last classification of a theorem clients is one that I'm call thin clients so a thin client is basically just a wrapper around a remote node so you have a website that knows a node somewhere else and it just asks it for data unproven about the state of the etherium chain so if we talk about the security guarantees of a light client it checks the validity of headers so checks the proof of work or perhaps once the theorem moves to proof of stake I would check a signature by some Authority or validator but it doesn't check the validity of state ditions that transactions have been executed correctly or that blocker woods have been given out so to think a bit what kind of attacks this leaves us open to we have to think about the behaviors of other nodes on the system so first of all we have an honest majority assumption with the miners so if you take this assumption that the majority of miners aren't going to be producing invalid blocks then unless you have some other minor directly targeting you and sending you invalid blocks you won't be able to see invalid blocks that have those invalid state transitions which you wouldn't be able to detect as a light client so that leaves us open to a very targeted sort of attack where you have an attacker who knows that you're running a light client and for whatever reason it's valuable to him to take up all your pure slots and start sending you invalid blocks to try and fool you into sending a transaction that you don't want to because another thing that can't happen is for him to trick you into thinking that the into sending no so well actually that's not correct so he can he can fool you into thinking that the current state is different and he can send you proofs on that but if you do go back and check that the transactions have been done correctly which you would if you have a high-value application that's running you cannot be full so we have a goal when we're designing our network protocol so the first goal is to minimize the round trips and bandwidth so we have a few core pieces one of which is back referencing the second of which is to check state proofs and the third which is a pub sub Network protocol and the goals are really to leverage that security assumption of the etherium chain as highly as possible so we've checked the consensus and that means that we trust some block header hash this block header contains a state tree root and we want to say that any state data that we read from the Train can be provably connected to this state tree root so we design all of our requests around this provable data and the last thing is we want to think about avoiding denial of service or just spam of protocol servers so when you're a light client you have to ask your peers prove this data exists in the state right now and if we don't have some kind of layer to prevent people from making tons and tons of requests it could be that the protocol servers are overwhelmed by that so we want to think a bit further in the future about things like micro payments and we would leverage technology like state channels for example to make those micro payments very small but actually provide an economic incentive to serve that data so to speak about back referencing this is I think a really critical part of that light client protocol because as you recall we don't have the state so we might want to fetch a block header and then from that block header get a state proof of an account accounts existence and then we have from that account structure we can get a reference to another Merkle tree which stores the storage for that contract so we have three pieces of things that we want to fetch we want to fetch the header then the account and then some storage so that actually logically requires three requests but imagine if you have a 100 millisecond latency with your peer if you go there and back and there and back and there and back that's 600 milliseconds of latency and that's actually a very long time to make a simple contract call to your peer so we have this idea that we have heterogeneous requests embedded in a single packet where the later requests in the packet can reference data that's output by the prior so in this way we can do these three requests or basically any other kinds of requests for example even smart contract executions they're they're very composable we can do all of that in a single round trip and it's still provably secure but you get a much lower latency and that's a better user experience so to speak a bit more about state proofs we have a state tree here right so that root of that tree the very top node is embedded into the block header through a cryptographic reference and when we execute a turing-complete smart contract it's actually unpredictable which pieces of data we want to fetch from that state tree because it requires execution of arbitrary code so if you are using a light client and you want to say do an ethereal name service lookup like this might require fetching all kinds of different pieces of data from the network and if you were just executing it locally and every time you need a piece of data to go to a peer and ask give me this account give me this storage it would actually take a really long time so the second aspect of our minimizing round-trips goal is to do entire transaction state proofs so that when you want to see what the result of a call would be prospectively you can just ask a peer prove this call to me and not just do it piecewise which is too inefficient and the last thing is we introduced a model of something called request credits so these servers give the light client peers little credits that can be used to make requests so credits might recharge slowly over time this is how it works now so every time you want to make a request for say a header or a piece of the state you use a little bit of these credits and different servers will have different costs it'll be based on you know their Imperial measurements of how long it takes to serve a specific request so that makes it adaptive to improvements in storage hardware or growth of the etherium state etc so this is actually a pretty generic scheme that can be used to leverage micro payments as well so instead of having them recharge over time when you pay a server they give you some request credits so the last thing we want to think about is this concept of a publish/subscribe system so our full node peers as a light client know a lot better when something has changed in a contract than we do because we just don't have that state and it's fairly bandwidth intensive to download the updated state every block so if we can introduce a publish/subscribe system our peers can push that data to us as it's updated but the hard part is there's no really there's no real way to check if a full node peer has just skipped sending us something that has changed but what we can do is also farm out requests to multiple peers and if they differ perhaps there can be some kind of on chain dispute resolution where a bond gets slashed but this is definitely an area for open research so another optimization that we have in light current client is this idea that we shouldn't have to store all the block headers from the Genesis up until now it's something like 5 million or so now it's just gonna keep growing so that's a lot of block headers to keep around so we have an idea that we can instead store a mapping from block number to the hash of that header and the total difficulty of that header in the form of a Merkel tree but we actually split this mapping up into several different pieces and once every n headers like n is 2048 or 4096 and so we have blocks from 1 to 2048 all in one of these mappings and after we've passed that block on the light client we just generate that mapping locally and throw it all those headers and we keep that mapping in a Merkel tree and keep the root of that so that means that if we have any full node peer who has the same history as us they can also generate that exact same Merkel tree and prove the header hash of any block in that history to us and that allows us to keep say 2048 blocks well a reference to them in only 32 bytes so if we ever want to get those historical blocks we can do so securely but we don't have to keep them ourselves and warp sync is really important because light clients are a lot faster because they don't have to do this heavy operation of executing the transactions and regenerating the next state tree to apply those updates is actually very heavy it's really the bottleneck for full nodes right now but even so initial sync can be fairly slow if you start at the Genesis and you verify the proof of work for five million headers it's going to take ages so we have to think about other ways to sync so warp sync is this idea that you can jump directly to the head of the chain with some level of security so on proof-of-work this is possible with thin-client security so at the very beginning we just sort of get a trusted header hash and start from there so we can't actually validate anything about this header hash but then once we've downloaded the ancestry leading up to that and we can do that in the background we have a much higher security level which would be equivalent to a typical light client security level after this e is which makes some changes to how historical block hashes are stored in the state we should be able to do a proof-of-work warp sync as well as under proof of stake systems or proof of authority systems to do a warp sync with full light client security from the very beginning and that agent block download can then be done on the background potentially only on Wi-Fi and I would say a fast and secure warp sync or there's the ability to get to the head of the chain quickly is really crucial for introducing a micropayments based scheme because you can't actually enter into any kind of state channel contract unless you're already at the head of the chain which means that full node peers would have to serve those blocks those Blockheads necessary to synchronize for free while serving other requests for a cost and that's a strange balance in the model because you it opens up servers to spam very easily so one final distinction I would like to make is that secure warp sync is different from having a hard-coded header hash or something equivalent to that in the client so one thing you can do in a client is just say when you make a release we hard-code the latest hash of the chain we said ok light clients pick up from here and that requires an additional level of trust in the developer as opposed to a trustless warp sync where we're relying on cryptographic properties so to speak about micropayments a bit this is essentially the scheme that we have so a light client and server open a state channel between each other.they the client pays the server for every bit of data that can only really be done at the head of the chain because until you trust those headers at the head of the chain you can't interact with any smart contracts there reliably so our idea for how people can use this light client is actually very flexible because we've written it in rust and rust is very flexible in terms of where we can compile and deploy it to so right now we're building the light client for Android and iOS it can be embedded in mobile apps but one thing we're actually thinking of is to take the light client and compile it down to web assembly and then embed that in a Chrome extension which can give a web 3j S instance to any web pages so you would actually have a light aetherium node that gives you really good security guarantees just running in your browser easy as installing a Chrome extension so we've begun work on compiling the light client to web assembly it's fairly difficult because it's a it's a very restrictive platform that doesn't have much in terms of you know the standard library API czar or what have you that exists already so we would need some some glue there on the Jas side but it actually is possible and rust is very well suited to that because it's such a low-level language one of the hardest problems I would say for D app developers using like client is how we can search those historical logs so I would say a lot of the apps make requests to a node that looks something like give me all the token transfers from the Genesis up until now for this account and that requires searching all these log events from the very beginning that's really slow already on a full node but on a light client it is really slow the reason is because we have to fetch all these headers and scan there's a bloom filter in each header and we have to scan those bloom filters and the problem with these bloom filters is that they're limited to 2048 bits and they're getting more and more full because they don't scale with the gas Thomas you have more transactions more events but the bloom filters don't get any bigger which means the false positive rate goes higher so you end up getting more and more false positives with each passing day that you download headers and you accidentally download receipts that are actually useless to you so I'll talk about a few different ways that log searching can be done so the standard way is basically just download the blooms for say block ABCD or rather you download the whole header and the bloom is contained therein and let's say we want to find a bloom filter where bits two and five are set so we can just check all those individually so this this first one matches the second or this first one doesn't match the second one does match this filter the third one does match and the fourth one doesn't but you can imagine if you had to do that five million times that it could be quite slow another approach is to do something that I would call horizontal ization which is for splitting up blocks into batches and then generating a bit vector or rather 2048 bit vectors each with the length of how like how large that group of blocks is so let's say we're doing it with four blocks and we have eight bits and this sort of little bloom filter that I'm talking about but in practice that's 2048 and the entries of these bit vectors are just whether that bit corresponding bit was set in the bloom of the corresponding block so we've horizontal eyes and now we would check for bits two and bit five and we can just download those bit vectors so they look a little bit more like this and we can check those without downloading quite as much data the problem is this doesn't work that well when the blooms are full because we still have false positive rates it requires a fair amount of overhead on the full nodes to generate or store those historic hit horizontal eyes filters because they have to keep them for the historic blocks and it requires an overhead on light clients to track the hashes or some other kind of reference to those horizontal eyes filters so it's not a perfect solution but it can be an improvement I'd also like to talk a bit about light clients role in sharding so sharding is is very hotly anticipated in the etherium community we're just we want to scale we want to get more transactions so light clients are actually crucial to that because it's not really possible to be a full node on every chart there may be some super nodes but on average you would just be following one or two shards and being a light clients on others so that you can check that certain receipts or transactions have been produced on other shards that are then coming over to yours but you don't actually verify absolutely everything there how are we doing on time good I'd also like to talk a bit about Casper FFG because this is a an upcoming improvement to aetherium scalability solution it's like the first step in the Casper roadmap so Casper FFG gives us finality so the ability to see whether block hashes have been finalized and won't be reverted the problem with Casper FFG as it stands is that this justification information about how the validators have voted on specific block hashes is stored in a smart contract and light clients don't have access to that data easily so they can't follow this full fork choice protocol of first following the highest justified chain based on the Casper FFG and then following total difficulty so it's a bit of a struggle to think of how light clients can fit in with this probably they'll just tend to follow the the total difficulty based chain and assume that the justifications will follow that or they could have peers send them like compact justification proofs of certain checkpoints in the Casper FFG system but one thing that light clients can do is fairly easily follow dynamic validator sets under Casper so again the light clients can't read the validator set from the contract each block because they don't store the state so they would you know if you have to every single block make a contract call to read what the next Casper FFG validator set is that's fairly difficult like that's a lot of overhead for syncing but they can still follow chains with dynamic validator sets if changes are only applied on finality so this is something that's actually the light client model can already support so if we have a handoff proof from one validator set to the next in essence that the previous validator set this says this is going to be the next validator set and then they finalized the block where that statement is made then a light client can get you know just have that whole thing sent to them so they can see okay this block that statement was made about the next validator set and then this block is finalized by that previous validator set so now I know that the set has switched to the next one there is a slight caveat there if you use that to do an efficient warp sync where you can just jump to the head of the chain which is that you can have a prior validator set once they're no longer staked to just stop you know they don't have any incentive to keep behaving correctly so they could sort of just make stuff that was in a really ancient block and just sort of fork off from there and fool you so that's a little bit of a slight security compromise but if that doesn't work for your security model you can always just sync the whole chain and this is actually especially crucial this dynamic stats approach is really crucial in a pure proof of stake chain where validators sign blocks so right now it's possible just to follow that total difficulty from mining but when the blocked verification itself involves checking signatures on a block and not doing proof of work verification we need light clients to be able to follow that so just to give a little diagram of that whole thing you can see first we have a block all the way on the very left and that's under validator set a so we say everything before this Green Line is under validator set a and the next one is under validator set B and the first block we have a signal to the change to be created and the light client can read that it may be through a log event or something similar and then a few blocks later that change is finalized so any blocks building on that the light client can then see should be validated under the assumption that validator set B is working on them so to speak to the developers in the audience when you build an app on the light client just what are some pitfalls you can can avoid so the first one of course is this eath get logs so it's fine when you're watching the head of the chain especially if you're doing it in a publish/subscribe way that okay a new block comes in we check a bloom filter then we get the receipts if it matches etc but if you're going to history it doesn't really work so we have a few approaches which I talked about before one is to search locally the other is to search locally with the stored metadata with that horizontal eyes filters and the third approach is to have peers search which again we can't always validate because we don't know if peers excluded something so there's there's a few trade offs there but the fact is none of them are really going to be super fast another thing is getting anything by a hash because hashes don't really leak any information about the block number where any changes occurred so if if you want to get a block by hash and we have a situation where not everybody stores all blocks then it doesn't give the light client any information about who they should ask for that data likewise if you're trying to request state data at that block or transactions or receipts for example if you want to get a transaction by hash and it's an ancient transaction like it happened ages ago that requires full node peers to stored an expensive index of all hashes to the block hash and index where they occurred and that's already around two gigabytes now I think for recent transactions is usually fine because they'll have them cached but if you're looking in the history it just doesn't it can't be done quickly and the last thing is estimation of gas that's crucial when you're trying to make a call to a contract that you know how much gas it's going to use but the problem is because if theorem smart contracts are taurine complete we can't predict that beforehand so it also can vary from block to block because a base it can be based on how the state has changed in the meantime so when we're estimating gas we'll first start with a high upper limit and then a low lower limit and we'll sort of binary chop to get in the middle but another annoying thing is that smart contracts can actually see how much gas is remaining and branch on that so it adds another level of inconsistency to actually the ability to reliably estimate gas so it should be used sparingly because it can it can cause a very high overhead on the node especially if the contract branches in case of different amounts of gas being remaining for example if you do your first estimation and then you realize oh we can probably go a little bit lower and you do a second estimation but the same state proof isn't sufficient for that second estimation with lower gas you would have to then go to a full node peer and get another state proof and that's fairly heavy so I think it's interesting to think about how the light client might fit into the broader ecosystem so light clients can work on mobile devices and whisper for example makes a really powerful tool for messaging between peers in a decentralized anonymous and private way and it actually works pretty well for say medium latency state channels not where you have thousands of transactions per second but maybe where you have one every 10 seconds or anything slower than that and for example there's a project called status which is already showing how that can be used that you can have a mobile app that's running a light clients and running whisperer for chat for state channels for applications so as far as our roadmap goes for the parity light client you can actually use it today so you can run parity with the dash dash Lite flag in beta releases and it'll start to sync the change if it starts from the Genesis don't worry it might take a while because it has to get all those headers we've already got a pull request open for that essentially hard-coded header hash if you trust that it is opted out so that would get you to the head of the chain very quickly if you trust hard-coded header hash that's in the client the UI is still being rebuilt around light client best practices because it takes a lot of effort as a developer to think about what kind of load you're imposing on the local node and if you're running a full node you've got everything locally and you don't have those same performance implications but when you're writing a UI based theory map around a light client you have to be very careful about that and we're also starting the work to compile down to web assembly where you can embed a light client in your browser so if you're interested in following the progress all the code is open source we've got that in the main parody etherium repository you can follow that at this github link parody tech slash parody and we encourage you to check it out or even contribute if you have any questions now would be the time yeah so the the protocols are different primarily because of this round trip based stuff that I was talking about before so what go go le s allows you to do is have multiple requests of the same kind in a single packet but not multiple requests of different kinds where the later ones reference outputs of the priors the other main difference is with this canonical hash tree stuff so go has a canonical hash tree that's generated for all blocks up until now but now is changing periodically whereas aetherium or sorry parity aetherium is doing that with smaller canonical hash trees that the light client can generate locally so it can stay up-to-date without having to get any trusted information from the developers or other full notes anything else well thank you very much [Applause]