Scalable Blockchains & Asynchronous Programming

Transcript

[Music] so what I wanted to so what I'm planning on talking about today is basically scalability and particularly some of the more detailed implications that this is going to have for how ethereum developers are going to write their cont contracts so we've already talked about scalability quite a lot this morning for about an hour we've uh talked about Casper consensus problems some of the issues that making ethereum scale is necessarily going to entail so you know just to sort of recap all of that very

quickly ethereum right now every single computer in the ethereum network processes every transaction every single maintains the entire State and that is very slow so on the Olympic test debt we achieved a an impressive 20 transactions per second which I believe is roughly what normal computers were able to do at some point in the 1980s so yeah but unlike nearly all other systems in the real world this also does not get more powerful the more nodes join the network surprisingly enough in fact it actually should get slightly less powerful with the universal

logarithm of the size of the network but the basic reason is if you have 10 times more nodes guess what each and every node still processes processes every transaction you still are where you started you just have even more in efficiency so the basic vision for 2.0 is this concept of sharting so instead of having one Global State that's seen by absolutely everyone you it's you split the state up into these sort of chunks that you can call shards and each of these shards is going to contain its own state so you can imagine each Shard containing some some portion of all the accounts and then you have some number of shards you you can imagine potentially having a few hundred a few thousand of these and the state is

represented in a in a Merkel tree as usual Merkel roots of of the state represented in The Shard roots and then you build another mle tree out of The Shard roots and you get the global state route of the entire theorum system so as you can see yes you can still have some concept of sort of global truth even in a scalable context so State split into shards each account is only in one Shard and just the simplest case accounts can only send transactions to or call call Accounts within the same Shard so this is one fairly simple way to do it so basically you know you just sort of split ethereum

up into a few thousand different islands and if he wants to do stuff that kind of interoperates between islands while you just have to figure out some sort of super protocol way to do it but in theory you know you Pro you can probably have a few thousand different applications and each application can kind of do its own thing you could have you know A Shard that has gnosis on it you could have a Shard that has like augur and potentially three other things on it you could have a A Shard that has five other things so this is one place to start so just go into this in sort of much more detail the way that this would work from a transaction standpoint is you have two levels so in Bitcoin in ethereum you have a block header which

is small then you have the set of transactions which is large and in the block header the set of transactions is represented by a mirle route so here we're instead we're going to do a two-l thing so we're going to create this object called a transaction group and so you know the way you can think about this sort of from a big picture standpoint is theoretically even in Bitcoin you don't or even for something like Bitcoin you don't need to have blocks you could have just required transactions to just have proof of work on their own and you could have just made every transaction reference one previous transaction and just made a Chan of transactions as it turns out by introducing one level of inter interaction with blocks you can make

things somewhat more efficient and somewhat more scalable here we're introducing two levels of indirection you have transactions trans actions get cated into transaction groups and then it's going to be the transaction groups that go into the main header chain so transaction transactions what they groups what do they have they have a header and a body the header contains two main components to it the left side contains A Shard ID uh then a pre-state route a post-state route and a receipt route so the pre-state route basically says hey look before these transactions were applied the state route of of Shard 43 was this the postate says after applying all of these transactions the

the state root of Shard 43 is going to be this and then you also say you know because ethereum has this concept of receipts if you apply all these transactions the root of the tree of receipts that they're going to emit is going to be this and each of these transactions has to have a Shard ID as well so you know all these transactions are going to have Shard ID 43 and so the whole thing has Shard ID 43 over here you have you know the idea that in order for this header to be valid it has to be validated by this sort of randomly selected Global sample of validators so we could imagine you'll have like some you know 400 1,000 whatever number of idas of validators inside the entire system and theoretically these don't even need to be the same validators as

the ones that maintain that that actually maintain the top level consensus so you know if you're concerned about sort of O ofn squared stuff slowing down Casper or you know slowing down whatever other consensus algorithm that's fine you can have you can stick to you know 400 validators for Casper and have 40,000 validators for the the bottom level now you know every transaction specifi as an ID a transaction in Shard X means that it does stuff only in chard x a transaction grouping in chard X contains zero or more transactions in chard X and specifies the pre-post state route top level looks like this so this is probably one of the more complicated blockchain diagrams you're going to see this week probably the major competitor

here is going to be Jeff Coleman's Universal hash time graph um so basically you still have a blockchain at the top so you know you can call this the header chain and it contains you know a state route it contains a hash of the previous block it contains metadata just like you know all the metadata we all know and love but it contains two primary Roots one of them is a state route and the state route basically repres represents the entire state so here you have The Shard Roots each Shard itself points to a tree and then you have a transaction group route so instead of just being a Merkel tree of transactions you have a Merkel tree of transaction groups and then each transaction group as usual contains

pre-state postate of The Shard not of the whole not of the entire Global thing and a transaction route and a re with the transaction tree and a receipt route for the receipt tree so one way to think about this sort of intuitively is you can think of the top level as a the top level as a non-scalable ethereum 1.0 style blockchain except it has these funny state transition rules where instead of validating transactions it validates transaction groups and a transaction group is valid if basically the pre-state rout matches and if the signatures are valid and if those two things line up then it takes the

signatures as kind of proxy evidence that everything else was done correctly and then if this transaction group gets in then the post State Route becomes the state route of that particular Shard so question how getting back to how do we do cross Shard transactions so the problem is if we allow just sort of Rand random arbitrary cross cross calling then parallelization becomes impossible you know you could potentially have contracts in 20 different shards all access or modify accounts in 20 other different shards and it could be done in some way that's like completely you know not friendly to any kind of parallel analysis it could

you know it could be non-cut commutative and a whole bunch of intractable ways so solution is to make it asynchronous but how so the basic ingredient here is mer Merkel tree receipts so if you look at just one particular receipt you you might notice that this receipt is part of a tree and this miracle tree has a root over here and this thing is itself part of a tree or rather and then this thing itself is part of a tree which has a mirle root over here so ultimately you could come up with a fairly compact branch and that Branch would ultimately you know have basically be a proof that the receipt

actually was included at this particular time so this gives you proof of existence it does not give you sort of proof of non- double spending but what we're going to do is we're going to add that in but we're going to sort of cleverly add that in in the correct Shard so what I'm basically describing here is a fairly kind of simple sort of standard approach that lets you implement a sort of no. JS style asynchronous programming language on top on top of this sort of eum 2.0 infrastructure and the key piece that you require is you need to have transactions have access to Merkel roots from previous blocks so transactions

here should be able to read pre the global previous state route Global pre previous transaction group route now they don't need to be able to modify anything globally they just needs to read a historical route and that's fairly fairly okay it doesn't sort of prevent parallel analysis or parallel computation at all now what you have here is let's just go through a fairly a fairly sort of uh somewhat involved example it's involved enough to capture all the nuances but it's still sort of as simple as it can be within that context so suppose that you're trying to register a domain name and this domain regist is so devilishly evil that it only accepts gaav coin as payment so the

domain regist lives in Shard 43 and Gaff coin lives in Shard 666 so so the problem is that now this registar charges a fee and so problem is you know let's say I want let's say the fee is 20 Gaff coin let's say I wants to make a transaction which you know pay reg pays the 20 Gaff coin registers a do and registers the domain how does this this sort of Ensemble of the registar and Gaff coin actually verify everything so in general the sort of the the most kind of standard approach so far for

contracts charging users crypto sub currencies in order to actually make payments is a sort of two-step receipt approach where fir where the first step is you send a transaction to the currency and you kind of authorize the other contract as a withdrawer and then you send another transaction to withdraw and then the contract sort of actually debits out sort of debits out of your bank account so this is something that we're going to be discussing probably in more detail uh over the next few days and things like the standard contract interfaces panel but it's roughly the approach right now so over here what we're going to do is we're going to call the function of the name register and you know we're going to say what what

we're going to say is we want to register a domain with some name we want to provide you know what fee we want to provide and we're going to provide the currency Shard and the currency address so basically where Gaff coin lives so what it's going to do is it's going to register a call back ID and then it's going to create a log and this log is basically going to contain all the information so it's going to contain the destination Shard the destination address so it's basically so the log is going to say this log is addressed to gcoin then it's going to say what method is being is being being called here so in this case this contract wants to call the method withdraw it wants to withdraw 20 Gaff coin from my account and the

arguments are from me to the name registry and the value 20 Gaff coin and it's going to say if this suce after this is all this all happens it's going to go to a call back method which is the withdraw call back and it's going to give it the Callback ID now over here I'm also going to in the name register's own storage basically provide some information saying hey look there is this call back that's in that that's being happening and it's in progress right now step two on the Gaff coin side so I made step one I set this transaction on Shard 43 it happened it created a log now now unfortunately this isn't a theorem 1.0

anymore where like all the messages happen automatically in asynchronous programming this is also going to be a second transaction you have to send it so you send a transaction and what this transaction is is it's going to basically all that it contains is a log proof it's just going to contain this Merkel proof of the log that was created in step one so what this contract is going to do is it's going to check the Merle proof and it's going to verify that the Merle proof is actually is actually addressed to Gaff coin and it's also going to verify that this particular log has not yet been

submitted so in Shard 666 it now maintains a record of whether or not this particular callback ID has been spent so then it said spent to true and it calls its own method so in this particular case you know the method could be could be whatever it could be well in this case it's actually going to be processing the withdrawal so it's going to be checking number one is the have I authorized the registra to todraw my Gaff coin number two do I have enough balance and if both of those are true then it's going to it's going to debit my gcoin balance it's going to give the name register on my Gaff coin and I'm it's going to return success otherwise it returns fail so then it's

going it's going to step three and then if that succeeds then you know so it's going to call and it's going to create yet another Reed this time in chard 666 and this receipt basically says okay this computation happened and you have a response step three is basically the same almost the same thing as step two except in the in step two you were verifying that a log proof of the original call and you're verifying that hasn't yet been spent and you're also creating a receipt here you're verifying the call back you're verifying a miracle proof of the call back so you're in the neighbor Shard you're back in chard 43 now you're just verifying a proof that Gaff that a log has been created has

been emitted by the Gaff coin contract and has been is directed at the name register if that's true and if this particular log has not yet been spent then I'm going to say see it's been spent and I'm going to call the method so the method in this case is withdraw a call back and the withdraw a call back basically says if there response is true then set the owner of this particular domain now over here I probably should have also added that if the O if the domain doesn't have an doesn't have an owner yet or something similar so basically you know if the entire payment process including initial transaction processing on the Gaff coin

side and the call back if everything works out fine then I'm going to register the domain name in chard 43 and there you go you have an entire kind of pathway of asynchronous function execution so in practice there are three main use cases for cross contract calling number one is to get information so getting information basically means I wants to call the Bloomberg contract and I wants to find out what the exchange rate is of USD to Euro the second one is send an action without response so one simple use case is let's say I am making a crowd you know I'm building a crowdfunding application I'm building way fund and and the way funds campaign Su a way

funds campaign let's say fails and so I have to refund all the money so I'm just going to do a big huge multi Cent give everyone their money back that's just asynchronous sense does not even require a call back the third one is send an action with a response and Gaff coin is one example you have to send an action tell Gaff coin to withdraw Gaff coin does something and it might return success or might return failure so the second is actually like not problematic at all the first and third Maybe so once you get into asynchronous programming as everyone who has done asynchronous programming will know you run into race conditions you have to think about Mutual exclusion issues and even without that you know JavaScript callback Towers look ugly and they are

annoying and so you know you might want to think about promises you know a things like async map so in general you want kind of programming paradigms that make this kind of stuff easier now skip the E economics because I don't have too much time but that side's also interesting the basic summary is that yes you can do it yes it's fine and in fact even though you need multiple transactions you can actually make it censorship resistant because basically because the log was created you have common knowledge of the facts that theoretically a transaction completing the process can be made and so he can punish validators for not making it within some number of blocks so more

generality here's one possible model first K bits of an address is a Shard ID and K is said by the transaction so every transaction sets its own K you know you could set k equals zero means that your transaction can like do everything globally uh setting k equals 10 means your transaction only affects things that have a particular 10 bit prefix and so forth attempting to synchronously call a contract outside of a Shard and The Shard is kind of this sort of much more fuzzy concept where it's kind of defined by K basically you know if your transaction sets K to to 13 then if you try to do something if one contract tries to call another contract where one of the first 13 bits is different then that triggers an out of

gas exception and so the key Point economically is that transaction groups on all no matter what the k is going to have the same gas limit so if you want you can make a transaction set the K to zero and someone can can callate all these transactions put them together together into a transaction group that has k equals z but here's the thing if you are a top if you are one of someone creating a top level block then you could get one one transaction group at k equals 0 or you can get 32 transaction groups at k equals 5 or you can get 65,536 transaction groups at k equal 16 so in equilibrium the lower your K is

the more expensive it's going to be and that's kind of a way of making this sort of balance and letting people sort of choose along the Curve between synchrony and cost so that's basically it you know welcome to asynchronous theam 2.0 contracts programming