Designing Smart Contracts With Free Will by Philip Daian (Devcon5)

so like we said we're gonna talk about why all your smart contracts are vulnerable to bribery and what to do about it and this is joint work with a number of excellent co-authors like all good research remember no research is ever an island so let's start by talking about why we're all here and actually one of the interesting reasons we're all here is because of a Polish economist from the 1970s named John Harsanyi who laid the groundwork for this field of study we call mechanism design what is mechanism design it's a field of economics and game theory that takes an engineering based approach to trying to get users to behave a certain way using economic incentives assuming the players in this game will act rationally and in their own self-interest so the field started in the 60s and 70s and consists of several basic components one of them is a mechanism which is a game that has rules a game environment and that players send messages to that game has an outcome and that outcome has what's called a social choice function or social utility function that says how good that outcome is for all the players in the game and therefore for society at large so what you want to do is implement some mechanism that implements some social choice function you find desirable and the hope is that because people act rationally they'll sort of converge on this social choice function you've chosen so what's an example of this well before Devcon I actually found myself pretty hungry and I wanted some toast but I actually couldn't decide whether I wanted regular toast or toast with an image of Jesus on it like you may have seen being popular on on various auction sites obviously I went with the Jesus toast because who wouldn't and so I headed over to ebay and found some auctions on this sort of toast and you can see here this one has a few days left in the auction and it's currently bidding at 1 cent so I was like this is great I put in my bid for 2 cents and I'm gonna win this Jesus toast and sort of fill my hunger the Pens sort of at the last second someone comes in and puts a bid for over $9,000 because they really wanted that piece of toast and I'm sort of left hungry and not knowing what's going on so this sort of highlights a general problem with auctions which is that in auctions you need to play strategically you need to consider how other people are going to act when you choose how you're going to act yourself and the games you sort of play with them like people play on eBay become very complex so one of the early things the field of mechanism design has looked at traditionally is can we improve things like auctions and in terms of the social choice function what our high-level goals are for that function for the seller their goal is to maximize their profit from selling the item of course and for the buyers they don't want to overpay over what they think the item is worth or the minimum they could be paying they don't want to have to think about complex strategies like when should I place my bid do I have to wait until the last second what are other people gonna do in this auction and how can I get this item more cheaply and the buyers also want to win the item if they value it more than any other buyer in the system we also assume the existence of some auctioneer who's this sort of trustworthy third party that runs the mechanism which is sort of a classic assumption in mechanism design that you have this third party that everyone who trusts that's actually running this game that we talked about so can we improve the eBay auction one of the proposals from sort of mechanism designers classically was what's called a VC G auction or Vickery Clarke's Groves auction and the way this works is that all the buyers send a bid in a sealed envelope to the auctioneer and at the end of the auction the auctioneer opens it and the the winner of the item is the highest bidder but he pays the second highest price for the item this model is used very commonly in things like ad sales and you can actually mathematically prove that given a bunch of private valuations on the buyer the best strategy for any buyer in this game is to bid what the item is really worth for them if they over bid in many cases they will lose money over bidding their real valuation and similarly if they under bid they'll lose money so that's great right that's what's called a dominant strategy truthful mechanism in the classic field of mechanism design meaning that a buyers dominance or best strategy is always to tell the truth and traditionally we've wanted to build mechanisms that rdst because they minimize cognitive load and overhead for sort of the players in your system and just make things simpler to think about in reason about and cryptocurrency has sort of continued this broad tradition of mechanism design again by some party or principle using incentives to drive outcomes so this is an example from the Bitcoin white paper satoshi nakamoto who talks about how the incentives in Bitcoin may help nodes to behave honestly in the system and smart contracts have similar overlaps and continuations of this field of study that's been going on since the 70s for example there's this idea that you can take any mechanism that we've been studying for decades and just make it a smart contract get rid of your trusted third party get rid of your auctioneer put it on chain and then we don't have to choose who to trust to play that role we can just sort of converge on this code instead otherwise if you want to build something that no one's ever built before you can use these same techniques that people have been using for decades to sort of analyze your mechanism and give users the properties they want unfortunately there's some challenges in doing this that make smart contracts very different from traditional mechanisms so again in traditional mechanisms you have this trusted third party where as in block chains you're replacing it with the blockchain which has its own sort of set of gotchas including things like how the peer-to-peer network works or how miners choose transactions or sensor transactions also in traditional mechanisms you often assume a permission set of players a known fixed set of players when you analyze your games for example eBay knows all of the accounts that are eligible to participate in a given action and they have permission control over this set so does Google when they're auctioning off ads and because of that you can do things like leveraging identity and there is some trust involved there unlike in smart contracts and cryptographic systems where all you might see is someone's private key and signatures and you might not be able to leverage this shared trust so smart contract mechanism design poses new challenges and chief among these challenges and what we're going to talk about today is the ease of coordinating bribery so last year I wrote a blog post called the dart Dow which if you have in read I highly encourage you to check out and it described a sort of nightmare scenario where people can build bribery systems for smart contracts that operate completely in the dark so no one can tell exactly what players are being bribed to do how many players are being bribed or or or if the attack is even succeeding at all not only that but users are guaranteed that the person that's bribing them is not going to get control of their money so the entire thing is sort of a trustless bribing infrastructure right and the dark Dow is actually a mechanism for bribing other mechanism just and what I'm gonna do today is introduce this new term for you guys that we call anti mechanisms which are all mechanisms that are intended to disrupt other mechanisms so the dark Dao is a particular type of anti mechanism it's called the dark Dao because it's dark or invisible no one can tell exactly what's going on inside it but you could also have a public bribery contract or other form of anti mechanism and what anti mechanisms look like is basically this so on the left you have what what it looks like when users are playing a regular mechanism they're sending messages to this mechanism and the mechanism is coming up with some outputs of the game you can see this mechanism as a smart contract on etherium private keys there on the left sending transactions to the mechanism and some outputs occurring in the state of the system an anti mechanism happens when you have another mechanism that users can play through instead potentially one that can interact with the original mechanism so you can see that they're shown on the right and prime here is an anti mechanism and two users in this case are playing em through em Prime so why does that matter it matters because the existence of these anti mechanisms erode a mechanisms ability to faithfully implement it's social choice function so in terms of optimizing for those goals that we talked about earlier that mechanism design loves to optimize for those goals are highly harmed by the existence of these anti mechanisms not only that but we can actually quantify the security of a given mechanism as the smallest budget anti mechanism that disrupts the properties we design the original mechanism for so I would encourage you guys to stop thinking about anti mechanisms or sorry stop thinking only about mechanisms when you design your smart contracts and your protocols and started thinking about what anti mechanisms could be possible in your system and what the sort of lowest cost of disruption is as a result so for the VCG auction the second price auction we mentioned earlier here's a very simple anti mechanism M Prime all M prime does is it collects bids from its users and it forwards only the top bid to the original mechanism M so why is is playing through M prime always better than playing through M well if the highest bidder plays through M doesn't matter the outcome is the exact same as before so no one's worse off on the other hand if the highest bidder happens to play through M prime then either the second bidder plays to R M Prime which case their bid is never forwarded and the highest bidder ends up paying less or the second bidder plays through em and you get sort of the same outcome again so what we say is that M Prime composed with M or playing M through m Prime in this case dominates in this case weakly dominates playing M directly it's always better for players to play through M Prime and it disrupts what we talked about earlier which is the dominant strategy truthful nature of BCG auctions because the auction is no longer receiving the true valuations from the buyers so in this case VCG in terms of a dominant strategy truthfulness has zero security against bribery and bribery is a huge deal in all these systems we're building a huge deal in smart contracts so if you're building an Oracle you can bribe people to provide certain responses you can bribe them to go offline you can bribe them to choose which point in a continuous time series of data they sample and send into the blockchain if you're running a voter a governance system you can buy people's votes you can pay them to not vote you can otherwise influence governance if you're building an identity system you can build an ting mechanisms that lease people's identities or partition out certain capabilities of the identities as separate from others and for all mechanisms you can bribe players to take certain strategies and even to collude with each other or not participate so the conclusion is basically this at least for now so what are we gonna do about it well first let's talk about the core problem here which is that this Dark Tower these private smart contracts that we're talking about remove a user's free will in the system they do that by restraining the actions a user can take in this cryptographic system and basically shackling them to a certain set of strategies or shackling them to a certain collusive set and we want to get back to sort of a state where users have free will where we know that if they're signing a message they could have signed any other message in the system as well and they're not artificially shackled by some other piece of technology or some anti mechanism so here we define free will as the ability for a user to use their information in this case their keys in aetherium without any external restrictions and in this case we're specifically talking about remote parties people who are trying to bribe or otherwise influence users over a network because that's most of what we're trying to secure against so this problem actually goes beyond crypto currencies this is not only a crypto currency problem these two papers have pointed out similar problems in traditional cryptographic systems so one thing you can do is you can use s jacks or MPC to take a deniable communication protocol where the property is that I can't generate a transcript of the protocol and you can actually generate a transcript that's provable right so I lose all my deniability I can't tell you that no I didn't say this because now the MPC or SGX process is gonna stamp for me that yes I actually did say this or you can use it to do things like bribe people to act a certain way on Facebook or buy their votes in like sort of traditional and voting systems and things like that which is what that paper on the Left deals with so how do we get back to free will well our core task is ensuring that a user has unlimited knowledge or access to their private information such as their keys and that those private information or that private information can't be stored in a secured environment that's somehow shackling the user and our second task is that we want to use this to make a signature scheme that's usable in things like smart contracts so we know that when a user signs the message they actually control their key so we more generally defined free will as the ability of a user to learn their own secrets and we achieve free will by requiring that whenever a user sends a message that involves secret data for example a private key someone can eavesdrop on that message and because the user won't let anyone else eavesdrop on their message that would for example compromise their funds that means that essentially the user is able to eavesdrop on their own data so what we're gonna be doing is sort of designing a scheme we call complete knowledge and users are gonna provide these complete knowledge proofs to the system to prove that they actually know their own secrets and that some human knows this secret and it's not somehow shared across multiple parties or otherwise constrained so I'm gonna flash a bunch of cryptography at you these slides are gonna be on my Twitter if you want to read this in more depth but the only important thing on this slide is sort of these last two bullet points which is that we consider to computation environments one being sort of an untrusted computation environment and another one being an eavesdrop environment and we want to make sure that a user has to send their private data through this environment that they can also eavesdrop on and therefore it can learn their own private data and the way we generate these proofs is we require some proof scheme that matches these two cryptographic definitions the two important properties here are number three and four the first one is unforgeable ax t that means i can't prove to you that i know some secret data that i actually don't know right and the second one is secret eavesdropping which says that i have the ability to eavesdrop on my own data and nobody else in the network can tell whether or not i actually did this eavesdropping or not if they could tell whether i actually did the eavesdropping or not they could simply require me not to do the eavesdropping when they bribe me so it's very critical that the data is able to be eavesdropped on but sort of in the dark and in secret and the basic solutions we use for this are actually quite surprising so there's two possible schemes here one of which is based on Bitcoin Asics and another one of which is based on SG X or trusted hardware so the Bitcoin ASIC solution is to basically do a proof-of-work on your secret key as well as some challenge and then generate a snark that some ASIC has done this proof on a secret key that the snort keep secret that corresponds to a public key that the snark makes public so when the snark is submitted to the network you know that at some point someone put that secret key into an ASIC to generate the pal the SGX solution similarly forces you to send the secret key as input or the secret data as input raw unencrypted input into an SG X chip so on the left this allows users to eavesdrop on their own data because Asics are not secured you don't know what firmware someone else is running on their own ASIC and whether it lets them eavesdrop on their data or not on the right SG X achieves this because as G X enclaves have to be communicated with through an unsecured OS and nobody is sort of in the broader network can tell if the OS that was communicating with the Enclave did or did not need to drop on its secrets so I'm not gonna go through these but check them out later if you're interested in sort of the formal the graphic definitions of both of those schemes what we're actually implementing is a little bit different so the problem with the schemes that I just mentioned is they're a little bit heavy handed and inefficient generating the snark actually takes quite some time so there's this cute little trick you can do for the proof-of-work version where you restrict the non-space of the ASIC and requires someone to try multiple times to sort of generate a proof such that if they try more than once they can recover their own key and with high probability then they'll be able to sort of eavesdrop on themselves so basically the math here works so let's talk about the proof of work version the proof of work version fails in one of several cases so the proof of work version will fail if you can use a CPU to generate the proof of work then SGX can just directly make this proof even though the secret data is never known to the user it also fails if the ASIC fails to find a proof then a user that actually knows their own secret data won't be able to prove that to the network fortunately Bitcoin Asics are much much much faster than CPUs so a hundred thousand times faster than state-of-the-art CPUs at this sort of work and you can see that given even if they're only a hundred times faster the probability that an ASIC will find a solution before a CPU is basically won right so there's sort of a broad range of parameters here for which it's highly likely that an ASIC will be able to find this proof of work but a CPU will not and therefore no sort of SGX process or multi-party computation can also solve this proof of work so these are the marginal CDF's of sort of the times to solve blue you see the probability that an ASIC has solved the puzzle and read the probability that a CPU has solved the puzzle and you can see the ASIC slope is just much steeper so you can sort of parameterize your system to make sure that an ASIC can always give you this proof but a CPU can never give you this proof and therefore no constrained or shackled computing environment can never give you this proof so what we're gonna be doing is releasing this sort of system on aetherium using this kind of an architecture so all you're gonna need to do in your voting contract or anti-bribery mechanism is called a single function on our registry when ck which will tell you the last time that a complete knowledge proof was generated on some key the last time some user proved to the system that they actually are able to learn their key right and users can choose like several backends to do this if they prefer to do it through SGX they can do it through SGX if they prefer to do it through a Bitcoin ASIC they can do that and interestingly enough this also gives us an opportunity to recycle old Bitcoin Asics because even old Asics that are no longer profitable for mining on the network are still much much faster than state-of-the-art CPUs and can still be used kind of to generate these proofs so I recommend to you that if you're designing a system where bribery is a big deal you should use this technique to make sure users actually know their data and they're not being bribed by some sort of shackling mechanism some anti mechanism like we described earlier not that CK is enough by itself though so you need to actually follow this more complex recipe you need to also provide the classical notion of coercion resistance which basically says that a user can secretly change their mind whenever they want so if a user can secretly change their mind whenever they want there's no point in bribing the user because you don't know if they're just gonna go and change their mind later you can't tell if they did that or not right and because you're using CK you know that there's no sort of shackles on the user that prevent them from changing their mind in this way and for stake based systems we want to require this on the state key so we know that whoever signed the message actually has skin in the game and actually has funds at risk sort of using the generation of this message so the high-level takeaway here I guess is that if you don't use this system your protocol is vulnerable to bribery period no exceptions so please don't DM me on Twitter and ask me like are we vulnerable to bribery in collusion if you haven't sort of studied this kind of infrastructure and read this background material because you 100% are and if you're interested in learning more about the technical details or you want to sort of use this in your anti-bribery systems please feel free to reach out to me and I'm happy to chat more it's a very complex sort of topic I only had 20 minutes to describe it I know I sort of flew through it but hopefully you got some takeaways that we can sort of make sure users own their own data in these systems and that's very important to making sure that they're not being bribed all right if you'd like to contact me or learn anything further here's my information as well as funding and a big thanks to all our IC 3 partners and Tyrian community for their support in this research thank you [Applause] you