Mind the Gap: Application-driven evaluation of Smart Contract languages

[Music] okay all right hi everyone so yeah I'm Andrew Miller I'm a professor at the University of Illinois at urbana-champaign I'm also a member of the research initiative ic3 the initiative for cryptocurrencies and contracts I'm also a board member of the Z cash Foundation and enterprise aetherium Alliance I'm also a technical adviser to a bunch of aetherium related projects for example chain-linked which I know was talked about earlier and what I want to tell you about today is basically a culmination of the last couple of years of research into smart contract programming that I've been doing I've been doing research and cryptocurrencies since prior to aetherium back in the Bitcoin times and have been trying to include etherium smart contract programming in things like assignments at the University of Maryland and like computer security courses since as early back as 2014 like before aetherium was even released and what i want to talk about is basically how we evaluate the languages that we use to write smart contracts in so you all know the story that we now think about crypto currencies as not just on a place where money goes and you can transfer money from one person to another we think more generally about writing programs that run on the blockchain and we need smart contract programming languages to define these now you probably all know that there's two main paradigms for writing smart contracts to run on a blockchain crypto currency you've got your Bitcoin style programming language which is not turing-complete all right and you've got your aetherium style programming languages which are turing-complete ins so you probably you know at least seen this kind of idea this is the main difference between these two programming styles on the right you've got more complicated control flow maybe these are going to be more difficult to analyze and maybe the simplified Bitcoin scripts more rigid less expressive hopefully easier to analyze now there's a version of this talk I give that um really just drives in on this point this really isn't the right way to think about the differences between smart contract programming languages turing completeness is really a red herring it's just not uh it's not the real point you know the compressed version of this I'll just list the the kind of summaries of this all right it's not really the case that aetherium is Turing complete all of the things about halting problem in infinite loops being undecidable they don't apply because of the gasps limit that effectively makes etherion programming not Turing complete you know how long something's going to run at most all right and it's not the case that you'd ever need Turing completeness so it's not necessarily the most important thing that you want anyway and if you have a Turing complete language it doesn't necessarily mean you can do everything you want to in it all right it's not just what you can compute that matters but um how input and output are handled concurrency things like that all right and uh something that I hear a lot but it's not you know it's just not true it's not the case that Turing complete languages are not possible to apply formal validation to it's really awesome that the etherium community's moving full ahead and caring about formal methods and it's the case that formal methods can also apply to you know programs written in a turing-complete language as well maybe it's not decidable maybe you can't do all analysis for all programs but you can still have very effective formal verification methods alright so if you buy this premise and you say ok turing completeness is a red herring how else should we go about evaluating the difference between smart contract programming languages and what do we want from one so the approach that i've been taking in my research i should also say what i'm gonna talk about a couple of different research projects that are joint work with some collaborators of my anudo benta of Ranjit Kumar asan and Patrick McCrory who you would have heard talked earlier and uh one of the breakout sessions and the approach that we've been taking is basically to come up with interesting applications and try to refine them over time to get them as efficient or as effective as we can in some kind of quantitative way and to see how far we can go by implementing these applications in the different smart contract programming languages now there's a common theme that you all this aetherium audience might find heartening that this common theme runs through all of these applications that we've tried which is that there's some quantitative reason where we can do a better job of implementing these applications in aetherium than we can in the Bitcoin style programming language alright and that's what I'm gonna try to explain just to give a quick preview of these three things I'll tell you a little bit about lottery applications in aetherium and to do a coin flip lottery in aetherium you can do quite simply and quite efficiently whereas to try to do the same thing in Bitcoin you require this kind of trade-off of either an exponential amount of computation in the number of parties that are playing or else you have to lock up a bunch of extra money as security deposits that you don't have to in the etherium case and then I'll tell you a little bit later about payment channels and things like the lightning or rated Network and there's an optimization that you can make in etherium that reduces the amount of money that you have to have locked up for a certain amount of time in these payment channels that we can't figure out how to get this benefit in in Bitcoin this trick only works in aetherium all right and then finally all and by telling you a little bit about a poker protocol that we worked on where there's really two properties that you would want and you can't get both of them at the same time with Bitcoin whereas you can do that in aetherium all right so let me start by just introducing this lottery application and let me explain to you how this goes so you all know the lottery application it's perfectly simple you have n players they each put in one coin all right and then some random selection process happens and then one of them walks away with all n of the coins now I'm gonna say that the the condition that I want you would probably think of using the block hash for this let's just say that's out of bounds what we care about is the fair cryptographic on committin reveal kind of lotteries so not relying on a block hash which miners might be able to influence alright so the way that this works the coin flip lottery you've probably seen this in some kind of form it's similar to what um theory emmm name services bidding does all of the parties are going to pick some random value and they're going to before some time limit they're going to place the hash of this random value on the blockchain and then they have up to some time limit after all of the The Commitments are in to reveal what those random values were that they committed to right and then the random winner is some you know decided somehow by adding up all of these secret values that are revealed and then hashing them and that picks one of the winners right now this is simple in order to make it secure though you want to have this or that it's a fair lottery so that even if n minus one of the parties are bad they can't get they can't cheat against the one remaining honest party and where the problem ends up happening that you need a technical solution to is what happens if one of these players just doesn't show up and doesn't reveal their secret value that they committed to in the earlier round all right you have to have some way of handling this case maybe the first thing that you would think of is just to take a security deposit like you have an extra coin that each party has to put in and if they don't reveal their value then they lose that coin all right so this makes sense but it doesn't actually solve the problem because if there are more than one player that collude against you know even the one remaining honest party then just doing this still penalize --is the honest parties that are remaining all right the simple solution doesn't give you a fair lottery now this idea of a coin flip lottery has been an interesting test case it was one of the first smart contracts examples that people tried to work out how to do in Bitcoin and what I'm gonna describe is that the version that you can do in Bitcoin still has this trade off like I mentioned you either have to collect really big security deposits or you have to do a kind of ridiculous amount of extra computation whereas in aetherium there's a way of doing a lottery quite simply that doesn't require any of this extra collateral so to start let me explain how this works in Bitcoin again this has been an important test case for smart contract programming since even prior to aetherium the main tool that we have at our disposal is this idea of a claim or refund gadget it's denoted by this little arrow which has some parameters like an amount of money Q a hash H and some deadlines T and what what this arrow is saying is that Alice is promising to Bob that she's going to reveal the preimage of this hash value by some deadline T and if she fails to reveal that preimage then Bob gets the Q dollars okay so that's what's meant by this claim a refund gadget you know to implement the claim a refund gadget in Bitcoin I won't go all the way through this it's something you can do with the the Bitcoin scripting language it's especially easier now it used to be possible but a lot harder before I check lock time verify it's a lot simpler now with the check lock time verify opcode it's like you make a UT x 0 that has a piece of you know script pub key Bitcoin script in it that says this can be claimed you know before a deadline if you you know reveal the preimage of this hash then then alice can spend it it comes with a signature from alice and the pre image or if time t1 elapses then Bob can take the coin just with his signature he doesn't have to reveal anything but he can only do this after this deadline alright so there's two ways to spend this there's the refund transaction which has to come along with X all right and so Alice can make this by revealing X before the deadline or else a claimed transaction means Alice forfeited it she didn't reveal her pre image in time so Bob gets the coins instead all right so um it actually turned out that a lottery that implemented this was one of the contributions of a really interesting paper that actually won the best paper award in 2014 at the Oakland conference this is the the most prestigious computer security conference and the academic computer security research community and they came up with a way of they didn't express it in terms of the claimed refund that little abstraction came later from Ito and Ranjith but um it uses this basic technique but the catch is that it requires this really large amount of collateral the idea is that every party deposits enough security collateral that if they get caught failing to reveal their committed value they compensate every other party for the total amount that any of the parties could have won so it's like whatever is the total amount of the lottery times the number of parties there are that's what each party has to put up as a security deposit and the way that this is implemented is kind of um a monstrosity this isn't even the full transaction graph of all the parts that are needed it's um this is actually kind of the plain case basically what happens is all of the parties make these claim or refund commitments to each other all right and then they'll all get settled at once but it requires collecting this large amount of security to deposit up front and so each party has to put in N squared coin and so it's n cubed in total is the amount of collateral that's required in addition to the bet now you know and Ranjit came up with a way to improve on this which is also extremely clever and yet you also get the feeling it's kind of complicated I won't be able to you know to even describe it in a way that I think you'll totally be comfortable with it you could think of it like this it involves proceeding in sequential rounds where in each round the parties make a claim or refund to the next party in line all right and then there's like a separate unwinding phase where they also make commitments they make these claim or refunds with that where you have to reveal multiple preimages and each one of them one more preimage than the last it's really hard to describe it but it requires now like a linear number of rounds like you have to do this one at a time the timeouts get larger and larger each time it's kind of like if I'm you know if any party fails to reveal their preimage then the next party in line has enough money to compensate them plus everyone else after this all right the net result is it reduces the total amount of extra security deposits you need to collect down from n cubed in total to merely N squared in total all right but it also comes at a trade-off which is that this ends up stretching out over and rounds like the lottery takes longer the more parties that you have participating whereas the original one took more collateral but you know finished in a constant number of rounds and it still has this quality that I think it's a little bit hard to wrap your head around so I'm not going to try to explain it any more clearly than that the techniques really clever though now you might start to wonder you know is there a simpler way of doing this and so I should say again all of these were done in in Bitcoin prior to aetherium being so widely appreciated anyway we started to look at how you could do a lottery in aetherium and it just immediately was simple oh you can do something a lot easier than this what you can do is have a tournament bracket where you always have two parties just playing a flip game against each other all right and at each time you like lay them out like a tournament bracket after the first two parties play then whoever wins that lottery goes on to the next round all right and then you finally you keep doing this like a tournament until you get to the final of the tournament and then whoever's there wins and now the rule is that the way you handle aborts is that since you're always just playing with an opponent if you fail to reveal your secret in time then the other party wins it's like you forfeit the other party immediately goes on to the next level and this is really easy to do in aetherium because you can keep track of who was the winner at each bracket it's really easy to do this with um lots of contracts like one contract for each match and then the contracts talk to each other it's also easy just to unfold it and write one big contract that keeps an array keeping track of all of the different stages of the tournaments it's really quickly pretty simple at something you could implement in solidity we started to look then at okay so you can do this simple tournament bracket and etherium I should say also that um you know this tournament doesn't require any extra collateral because you don't have to take a security deposit from someone if they forfeit you just you know that the other person goes on to the next level so we looked at to try to see if we could emulate this tournament structure rather than this linear structure or one round expensive structure in Bitcoin and we came up with something that's a little bit unsatisfying but it is still technically a tournament structure we came up with this extension of the claimer refund gadget that's really like a two-way claim a refund gadget it involves a sequence of two transaction scripts rather than just one it's like Alice has a turn to commit bob has a turn Alice has a turn to reveal bob has a turn to reveal you know the net of it is that there are everyone has two all of these transactions have to be signed by all of the parties involved ahead of time like all of the parties in the tournament have to sign all of these transactions everything except for the the hash preimages is the only thing that's left out of the signature all right and you know no matter what there will be like at least this transaction on the blockchain and then you know there's some case where you can go straight to one of these outcomes basically there's three possible transactions that can be the outcomes of this like two of the transactions involve Bob winning one of the the possible output transactions involves Alice winning it's a little bit tricky to explain but it's basically the same kind of thing you're encoding this condition of you know reveal a pre-image before sometime you can do that in Bitcoin script the and chaining these things together by having multiple transactions pre signs that all refer to each other and this structure you can actually combine into a tournament bracket just like the etherium example but with a catch all right so that catches that because in Bitcoin transaction script even making use of Segway even making use of the most modern op codes when you have a transaction that receives inputs you have to expressly indicate the transaction ID of the transaction whose input you know whose outputs you're spending as an input so what that means is that if one of the matches in this first round has three possible output transactions alright then to make the next round of the tournament that depends on it it has to have you know you have to have one pre-signed transaction for each of those possible inputs and so if you have it the the next round of transactions has two possible matches two possible matches it has two like the winner from each of these two matches goes on to the next round you end up having to have three times three different contracts each for each combination of the ways that that could end and then it gets worse from there because now this you know stack of transactions has 27 possible outcomes all right and so the next layer has to have 27 times 27 of those and it goes on by the time you get to the end you you've got this tournament bracket that worked but you end up having an exponential number of transactions that everyone has to sign up front only one of them will end up getting put on the blockchain but you have to sign them all up front and so that's where this exponential amount of computation comes in it's kind of unsatisfying it's a little bit awkward it's kind of like having one hot encoding where the the the one hot is which of these transactions you sign up front actually gets placed on the blockchain and you have one of these you know transactions for every possible combination of all the different ways the tournament could have gone up to that point all right is this a bit of a convoluted structure the lesson that we get here immediately is a qualitative one which is that things that are pretty simple to express an ethereal are sometimes really complicated to express in Bitcoin sometimes there's a way to do it I'm surprised at just how often there's something that I thought there'd be no way to do and yet we can figure out a way to do it in Bitcoin script but it's a little bit on you know unsatisfying and unnecessary early convoluted it's a little bit like trying to build a web browser inside a ti-83 calculator you can do it but ti-83 basic is not the most friendly language to be entering and you know button key presses at a time but really the power of this is that we have not just that qualitative statement but this actually gives us a quantitative statement about the difference between these two programming paradigms all right this is like the scoreboard of how well we can do a lot of reason these different environments write in these original Bitcoin ones you know earlier traded off this amount of you know collateral that you had to take for varying amounts of computation or running time all right and then this weird one that we figured out how to do as this exponential cost but back down to no extra collateral right whereas the one that we get in etherium is pretty efficient in the number of rounds and it doesn't require any extra collateral or any unusual amount of computation all right despite being qualitatively simpler I want to switch to then talking about you know the next application maybe you'll find this one more interesting because payment channels are invoked these days and this is a paper called sprites you can find this paper online all right and the upshot of it is that if you have a lightning Network situation where you have payments that are going across you know some lengths in this payment channel graph the amount of collateral cost that you need is quadratic all right in in the worst case as a function of the length of the hops that you have to go I'll give you some explanation of that whereas in aetherium we can do something simpler and we can reduce this collateral cost from quadratic down to linear so you all know what a payment channel is by now it's where you make a smart contract where you deposit some money for two parties and then after doing that initial deposit you can do off chain payments to each other really rapidly all right and then what's really especially cool about them is that if you have a chain of payment channels from one party to another like you have Alice and Bob here Alice wants to pay Bob she doesn't already have a payment channel to Bob but she has a sequence you know she has some intermediaries to whom she does have payment channels and there's some path of payment channels from her to Bob you can do this linked payment where each party pays the next person down in the chain and you do this in a way where there's like an atom isset II guarantee which means that these parties in the middle they're not losing any money like they're getting X from there and channel they're paying Exxon they're out coming channel they net out alright and there's no risk of them actually losing their money now the fun of this right this is this idea of the Lightning Network that we can have with a relatively small number of payment channels we can build paths connecting any two parties with fairly low path length between them while still each one only is pretty small degree like no one person has to have too many payment channels now what you care about in this case is the collateral cost which is you should think of as like the dollar hours or the money times time that your money's tied up because the payments in a payment channel don't necessarily happen instantaneously especially if one of the parties goes offline so when one of these payments begins it doesn't just happen immediately it's in a pending state for a while until it settles and so this guy is outgoing payment is also in a pending state and if you know something happens and someone doesn't send you know immediately what they should this pending state might last for a while meanwhile this intermediary node is asking when's you gonna get the money back how long is his extra dollar tied up and that's this money times time collateral cost now the way that lightning and also Radin go is that when you establish these linked payments it's like you set up conditional payments from one party to the next and these are you know similar to that claim a refund thing they have a dollar amount they have a pre-image and they have a deadline and what happens is that each deadline has to be a little bit larger than the next it happens in the typical case is that right that this party on the right end has the preimage ex and he waits until he gets his incoming payment and then he goes ahead and reveals it you know anyone who's listening in the typical case it just completes immediately after that it's pretty quick right an entirely off chain but the reason why you need that extra delay is because right what can happen is that if say these two orange colored parties are bad they actually hold on to that preimage ex they don't just send it to everyone when they get their incoming conditional payments made it may be that this guy right here this blue one only finds out about the preimage X because this orange guy was Petty which I mean he waits till the very last possible moment and then actually puts X on the blockchain and gets his payment so when this happens this guy gets it in right at his deadline t plus one this blue guy here has to turn around and then put that Exxon on the blockchain himself in order to get this payment from the other guy all right so as a result he needs to have some extra amount of time he has to wait to see this transaction on the blockchain and then be able to get his transaction in before his timeout goes that's why each party has to have a longer timeout than the party to their right all right so as a result if you have a length L chain of payments that you want to make then you have to have L times whatever's an appropriate amount of time for this guy to you know in the worst case have to have his money locked up and this means that the total collateral cost in the worst case when you know people other people in the chain are delaying in this way is you may have to have l squared you know in total among all of these parties it could be up to L squared times X in dollar hours right this collateral cost now here's what we can do in aetherium this is the idea of sprites it's an optimization we actually come up with a way that you can have chained payments it works really similar to this except the lock times the deadlines for each one of these conditional payments is exactly the same and the way it works is that the rules for settling this payment make use of a global condition not just a local condition the way that you do it and lightning in and Radin we have a single contract we call the global preimage manager and the idea is that rather than requiring each value to be sent on each payment channel the rules for settling this payment channels say go to the global preimage manager contract and check whether a value was published there in time all right what it looks like in the worst case is that if some party goes and puts their value at the last possible moment it's like it sets an on blockchain event that then guarantees that all of the channels if they go to this dispute handling case are going to close in exactly the same way these other parties upstream in the payment channel no longer have a burden of responding and a certain deadline they know that whenever they get around to it the channels are gonna settle in a consistent atomic way which will guarantee that known of the intermediaries lose any money which is what we want all right the key to this is making use of this global pretty image manager contract which is something that's straightforward to do in aetherium before which there's no real way to do it in Bitcoin I'm just gonna really briefly mention this last application of poker I'm not going to go into very details about it although there's a paper online that you can read to see it right online poker is one of these holy grails of cryptographic applications it's really exciting because people like playing poker and it's an interesting exercise of your cryptography because you have private cards that you need to deal and need to keep secret and you know the basic structure of handling the housekeeping of keeping track of like whose turn it is and whether anyone forfeited a turn and therefore needs to be punished that can be handled by the state channel generalization of this payment channels idea so without going into any of the cryptography that's there I just want to point out that there that we've had the sequence of works mostly just a Ramsey de niro I only hoped in this on last one there's really like two parties that you had to two properties that you would like from a good poker application one is that you would like it to be off chain only in the typical case so you can play many rounds of poker without having to make a non chain transaction in pay fees and you would also like the poker game not just to end up telling you who the winner is but to actually like give you the amount of money that you want back okay my screen went out okay so um well I think you got the gist of that end of it the only thing that the only way to get both of these properties combined is to have to make use of the the flexibility and the etherium smart contract model we couldn't find any way of being able to get both of these desired properties both having off train in the usual case and actually being able to do a payment out oh this just drop okay no it's a weirdly next thing I have to open up Hudson James and everyone okay all right yeah the only point I wanted to make yours we want to have both of these qualities like these ones here that say no cash distribution what it means is that you learn who the winner was but it doesn't actually make any money change hands at the end right you want to play poker for some kind of stakes in order to get both of these qualities where you can actually settle for money on chain when you have to but it's off train only in the typical case all right we weren't able to figure out how to do that in Bitcoin whereas all of these one desirable property the other we figured out some way of doing it in Bitcoin but to get both seems to rely on the ability of having like references to dynamic transactions rather than having like a fixed transaction input which is what your is constrained to do in the u TXO model alright so I just want to wrap up in here by saying you know more about what I think is the the lesson that we've learned from this so first of all I think this is a way to go about evaluating the expressiveness of smart contract languages I think that if someone proposes a new smart contract language one of the first things you should try to do is to see can you implement the the high score on the scoreboard for all of these applications if you get stuck there's a sign that there's something you know useful that you would like to be able to do in smart contract programming that this language isn't affording all right there are other like trade-offs and so maybe there's you know some justification like that so for example the the you TXO model in Bitcoin supports benign reorg Slyke if there is a reorg than all of the transactions will be shortly played right after all right and there's some trade-off involving privacy um with sprites so I'm not saying that you absolutely need to have this benefit I think it's the case that doing on you TXO prototyping first actually slows down research by obscuring the main idea behind a smart contract application all right and a sort of obscuring the key ideas and I think that the fact that Radin was designed the way that it is was because it was mimicking the the design and bitcoin which was only necessary because of bitcoins limited script so even the Radin you know clone of the Lightning design fails to make use of a theorems full power even though it's in in the etherium language so you know my suggestion is that you should use a language like aetherium to prototype your new application even if it's something that you're eventually going to eventually try to port to Bitcoin or to other applications so I'll stop there Thanks [Music]