EthCC 2: William George

yep nope okay so hi everybody so today I'm going to talk to you about shelling point based games and P plus epsilon attacks so my name is William George I do research for Klaus which is a blockchain based decentralized dispute resolution platform particularly we use shelling points so this research is very relevant to us so I'm gonna begin with an interesting thought experiment of Warren Buffett who wrote an article in 2000 where he sort of bemoaned in the state of us campaign finance law saying that was too easy to make large donations to political actors and sort of change US policy and as a solution to this he proposed as a sort of farce of fanciful fanciful solution to this he proposed a an interesting thought experiment he says okay well suppose that some eccentric billionaire not me not me made the following offer if the bill that he was proposing imposing strict restrictions on campaign finance was defeated if the bills defeated this person the eccentric billionaire would donate a billion dollars in an allowable matter because of course with Liu's campaign finance laws you can donate pretty much whatever you want to the political party that delivered the most votes to getting at the bill passed and then given this diabolical application of game theory the bill would sail through Congress and cost our excentric billion or nothing the idea of being that both parties would be so incentivized to prevent the other party from getting a billion dollars at a minimum that they would be strongly incentivized to vote for the bill but it's because both parties would vote for the bill well then campaign finance laws would have changed which means while all of a sudden it's not possible to give such a large donation anymore because they find its laws are more strict so this kind of kind of bribed this structure or you make a bribe that only pays out if you lose if you don't get you think outcome you want is very interesting and it's going to be sort of the theme of the subject of the rest of the talk okay so imagine to move back a little bit and talk about a shaoling place it base point base games in general before before moving back on to sort of these kinds of bribes and attacks so imagine that you have a vote one of many votes and you're given a binary choice between x and y and you want to vote with the majority for some reason if you vote with the majority you get a reward and if you vote against the majority you get penalized an out priori if you're voting between x and y there's no context like this payoff table here is symmetric so there's not like a necessarily a canonical choice between voting for X or for voting for y but when there's context when they're when they mean something then that might allow you to make a sort of pick out a distinguished choice so for example this system kind of at its base is used by a number of crypto economic systems including truth coin which kind of led to ogre and also then Klaus so for example in augur ultimately when you provide the response to a prediction market who want an election who want a sporting event you're rewarded if you vote if you if you your response agrees with everyone else's with the majority response and you're penalized if you provide a response that disagrees similarly in Clairol's where dispute resolution platform so we imagine that like maybe you Alice hired a freelancer Bob and then there's a dispute over whether Bob did good work and ultimately some some collection of people are voting on who was right between Alice and Bob so in sort of those settings X and y have meaning like x and y will be like who won the election the choices between who owned the election or Alice or Bob who was right in the dispute and then when there's like an honest answer when there's an answer that you can think of as being like the real answer in the real world then you expect people to gravitate towards that and this gets back to an idea of Thomas Schelling called a selling point that when there's a solution in these kind of coordination games that people tend to you that sometimes solutions the people will tend to use in the absence of communication because they seem natural special or relevant to them so this idea of the honest answer being a selling point being a natural solution that people will tend to is kind of the underlying idea behind these selling point buy systems so to illustrate this a little better imagine we're in the case of Alice V Bob and there's some collection of people voters that are ruling between uh no dispute between Alice and Bob then if you're that guy in the middle you have one of the votes and you're trying to imagine okay how are the other people going to vote well I think Alice is right I analyzed the case I I think she has a good case he has a stronger argument than Bob and I think that the other people are going to make the same kind of considerations that I am they're going to like also analyze the case they're probably going to come to the conclusion that Alice's right so and then they're going to think that I'm more likely to pick the honest answer that is to say Alice being right then not if only because I think that they're more likely to pick the oddest at more honest answer is more likely than not so then everybody thinks that everybody else will pick Alice because it's it's this sort of natural canonical solution and then everybody knows so Alice wins so that's sort of the basic idea of shelling point based games work and then there's this interesting attack against them which is kind of a more sophisticated version of the Warren Buffett thought experiment so this was kind of introduced in its form and it's modern more sophisticated form by a blog post by vitalik in 2015 where the idea is imagine you have a payoff table where if you vote X and Jordi's actually get P if you vote y the George is why you get P otherwise you don't get anything and some attacker wants Y to be the answer for whatever reason then what they can do is they can offer a bribe of P plus epsilon which they only pay out the people who vote why vote but the response the attacker wants if the ultimate response is X so I like the Warren Buffett attack and only you know the only path to bribe if your attack fails if you lose so then the idea is that well if I've if the majority is exited about why I get people's Epsilon I get P Plus this a little additional amount Epsilon or as if I'd voted X I don't even gotten P and if I the majority's Y and I vote Y well then I want to be coherent I get P instead of 0 so all of a sudden the incentive structure of the game is warped just by sort of offering this broad the attacker had convinced has incentivized everyone to vote why and then if everyone votes why Wow why win which means the attacker won't actually pay out anything so and it's like a priori you look at this and you're like oh this this is really bad because this is a free attack the attacker can change people's incentives just by offering a by without ever actually having to pay one so to illustrate imagine Bob says people has Absalon attack available maybe he makes some kind of smart contract that commits to that bribe and then everybody's like well you know it's like at least get a little bit better than I would have gotten otherwise voting for Bob's now like a dominant strategy so everybody votes Rob and Bob doesn't pay the bribe so Bob managed to convince change the outcome without actually paying anyone anything so notice there are a couple of nuances here so for one thing if you think you have the decisive vote well then you're in a situation where like things are a little different so imagine this guy in the middle thinks okay one of my two other voters is going to vote Alice one of them is gonna vote Bob so that means that I have the deciding vote either way I vote that choice is gonna win so if I vote X well X is gonna win and if I vote y Y is going to win so these other two diagonals and the path table sort of are relevant because they're not going to happen I'm gonna go to X and it's gonna be X or I'm gonna vote why I mean it's gonna be y so ultimately I have a choice between P and P so from an economic incentive it doesn't matter which one I vote so the taking the bribe is no longer sort of strictly no it's not strictly dominant it's not strictly better for me to take the bribe so that's interesting and this can be generalized into sort of counter coordination defenses and gets people supplant attacks so this was already proposed in metallics blog post and the idea is that say Bob announces people have salon attack available and say these are the five voters they can gather together and be like okay we're going to try to get it we're gonna try to like cheat the cheat we're going to take as much money from Bob as we can and sort of engineer milking him as much for as much money as we can while he still loses so what they do is they gather together and they counter coordinate and maybe one of the five is does her own thing she doesn't want to counter coordinate she goes off on her own so these four people each provide a deposit to a smart contract and then the smart contract is going to try to engineer a narrow loss for Bob with the idea being that if Bob it Bob wins he doesn't pay up the bribe so that doesn't really help people if Bob loses but no one votes with but the attacker well then Bob doesn't really depend on he bribes because you only pay bribes see the people that take that vote with you however if Bob loses narrowly so here are their five voters so if Bob loses like three to two then he has to pay out a couple of bribes so the smart contract tries to engineer that and it's like okay well I see that one of these five people isn't isn't on board so I'm trying to engineer and gets free to to Vic lost for Bob so I'll assume that she's probably no vote Bob and I'll ask one of my four counter coordinators to also vote for Bob and the other three will vote for Alice and that way Alice will narrowly win and Bob will have to pay out as many bribes as possible and then if you think about what payoffs people have well first of all if anyone doesn't vote the way they're supposed to vote according to the counter coordination contract that you can slash their deposit so you can give them a really strong incentive once they've agreed to counter coordinated made the deposit to stay on board so assume everybody votes the way they're supposed to then you can like think about okay I get certain payouts from the coherence game certain pals from Bob's and pals from like the cuts does the counter coordination contract so like each of these people that voted for Alice gets a path from the core here it's again because they were coherent they voted for the winner the person who voted for Bob gets a bribe and the counter coordination contract tries to even them out so it takes the the people who like got a little less because they voted for Alice and it gives them a little more and it takes the person who got voted for Bob and gives them just a little more so that ultimately they wind up what for the same thing and you'll notice that they all get more than they would have gotten if everyone had just voted for Bob or if everyone had just voted for Alice so in a certain sense they they've globally done better everyone has like better off for having except this person this isn't a really stable situation because there's one person who didn't counter coordinate did better than anybody she got the full bride whereas everybody else got sort of like a part of the bribe so from her from an individual voters perspective what you really want to happen is to be this person you want everybody else to counter cord right but not you you want Bob to lose but you go off and take the full bribe by yourself so like you might take you might counter coordinate if you expected that to make a difference and whether bob ultimately wins or not if you think Bob's gonna win or lose sort of regardless of your individual actions there's not a strong instead of incentive to get on board the counter coordination and you sort of have an incentive to try to go off on your own okay so that's sort of what we knew before as Avot Alec's blog post in 2015 so now I'm going to talk to you about a defense against this or at least a partial defense so in close we use an appeal system and the basic idea even for normal bribes and normal attacks is that if like Bob comes along and tries to bribe people like bribes two of my three jurors what would be nice is if Alice can ask for an appeal maybe she had put some in some additional deposit and then somehow like the Claro system will choose more jurors more more voters to rule on a given case and then because there are more jurors more voters well like now it should be harder for Bob to bribe all these people so it should become like less sustainable the more and more people you pick for Bob to maintain an attack and then the idea is that the token that the voters in kleros at least our poll are chosen by a token weighted process so if you draw more and more tokens you appeal a whole bunch of times to draw more and more more voters ultimately you get you go from like a small number of people who vote to like a really large number people that reflect sort of the broad token holding pool and this is in so and in order to like get a corrupt outcome in order to own for it in order for like the broad pool of people to not ultimately come to a good decision you have to corrupt the broad pool so not just some like some selection of three or five jurors but in order for your attack to hold up and repeal you have to sort of be able to corrupt everyone and this is really important to Collaros because ultimately we envision ourselves as a general-purpose dispute resolution platform and some disputes are hard sometimes when you're trying to rule on a dispute you have to like really think about it and put in a lot of effort and if we ask every token holder to put in that effort every time now that would be unsustainable so ideally usually you have a few people that make that effort but then there's always this threat that you'll appeal and like have a larger pool of people so you can get sort of the non duplication of effort that comes with having a small panel of voters by having an appeal system while still having a security level that looks more like is if you asked everyone to vote because in order for an attack to succeed it has to be able to win if you act eventually ask everyone to vote okay so an early version of so the first launch of klaris was this thing called the Doge pilot those are all trial pilot so it's a curated list of Doge images so we wanted to start with something that was sort of low stakes and in a gamified were like to sort of test the crypto economic incentives and in a way in a manner that like if things go wrong wouldn't have been too catastrophic so the idea here is that we have a list of images of doges these shiba inu dogs and if in order to get on the list you're supposed to be an image of the Doge so if someone adds an image to this list the implicit dispute is does this image belong on the list or not someone can flag your image and be like no that's not a Doge that doesn't belong on the list and then alice is the person who says this is should be on the list and bob is the person who says no it shouldn't be on the list and then we offered like sort of artificial incentives to get people to participate in this we offer dogecoin to people who submitted Doge images we offer to like a prize or bounty if someone could get an image of a cat on so that way people had both an incentive to attack and to propose honest submissions to the list and we use this opportunity to do some experiments of people who subs on attacks and sort of see how they went so like this image was one of the ones that we some people's epsilon attack you'll notice that has this block of text here at the bottom that has a link saying attention jurors there's there's a bribe potential for more information please like go to this this link and find out more about the bribe so that way every person who had to rule this case would know there was a bribe they'll be able to see this and they'd be able to find out an important and we did this several times and ultimate let me see that for the most part people didn't really take the bribes so none of the cases that none of the cases had not Doge ultimately winning and in the most extreme case about a third of the total votes voted for Doge so that that's interesting even though people have Epsilon attack like in theory is at least sort of a weakly dominant strategy unless your counter coordinating people didn't take the bribes anyway and we have some more detail in terms of like like analyzing these results if you think of this like a null hypothesis of people taking the bribe at 50% probability because ultimately sort of your baseline for whether the attack is see it or not if you take the null hypothesis of people taking the bribe 50 cent percent probability then it's like kind of it's like extremely unlikely we would've gotten results this extreme with that null hypothesis and also note that most of our token holder is always either either always took the bribe or never took the bribe which is interesting because like we offered bribes of varying levels varying amounts so most people either seem to bribe friendly or bribe hostile so why did why like somebody like ask yourself some questions of what happened Oh for one thing we think it might not be worth people people to take the like the cognitive cost to understand the attack you have to like go read the talax that blog post understand what people s epsilon attack is and then moreover like the bribes can be smart contracted forced you can have a smart contract if it can like absolutely pay you the bribe if you accept the bribe but like you know let our priori the smart contract there's this the attacker is giving to you which necessarily been like audited or for example it could be full of bugs and trapdoors so and particularly you know it's an attacker it's someone trying to get a malicious result through so you don't probably trust them so you want to check the smart contract for yourself but that requires a lot of effort you have to like really thoroughly read the contract so there might there's a cost to accepting the drive in terms of a cognitive effort another possibility is our pool jurors is just really altruistic a lot of these people it's it's sort of this happened in early days so these people might revert people that were enthusiastic about kleros in its beginning they might not want to see a bribe successful against clothes maybe they held kleros pinaki on token already and they thought that the up successful bribe would hurt the value of their token so that it's a possibility that they just didn't take the bribe out of altruism and then if you that might not state the case in the future it's going to continue to sort of monitor as how this evolves as the pool of jurors diversifies and becomes maybe more like the general population and for more information about these kinds of analysis of these specific attacks we just published a book called dispute revolution that's available on our website and you can read a more thorough analysis of these experiments in that book so in terms of just cognitive costs and moral costs already you know that if you add in that cost to the payoff table some stuff changes so depending on how big your moral cognitive cost is so you subtract off like a minus M here for voting Y either for moral or cognitive reasons so if M is like small like really small not a whole lot changes which isn't surprising if M is like gigantic then you'll never you'll never take the bribe no matter what just because you know like if it deeply offends your morality you just won't do it even if there's a financial reward for you for like medium values of n you can see that now the probability the attacker wins is no longer one there you were in like a mixed Nash equilibrium where the attacker doesn't win all the time which means there's an expected cost to the attacker which is much much better than the sort of classical people's epsilon a situation because like it's one thing to have an attack that like might work sometimes but like the attacker risked a lot of money so if the value of the case at stake is like not worth too much and it's like say if it's like a ten thousand dollar dispute and the expected loss of the attacker to like run and attack is like a million dollars that that's kind of okay because like only a crazy attacker would do that so that that's much better than having expected cost of zero which is like sort of what the situation you had in the classical people is up Zack so now I'm gonna talk about some designs we made specifically taken Claro's to minimize the effectiveness of this attack so there's a lot of complicated looking formulas here I apologize but imagine you have M total votes and each person has only one vote that's an assumption that's not necessarily super realistic each person places in a positive D so now if you vote incoherently rather than just not getting P you actually lose a deposit but if you vote coherently you get sort of other people's deposits say little X other votes vote for X little Y other votes vote for Y and then your payoff table looks like this if you vote for X and vote X you get some share of other people's deposits that are split between the coherent people otherwise you you get if you have similar for Y and then people steps on the talk is taking this formula and just adding epsilon to it as as they offered by the bribe and the reason this is helpful I imagine you are in this special case where there M voters in each round that you put in their deposit and all of them take the bribe except for you so their M minus one that take the vibe and I I don't and then my kit my side wins an appeal X ultimately wins an appeal so that person under these under this design choice gets everybody else's deposits in their round they get M minus one D like M minus one deposits so there's sort of a lone voice of reason and they get kind of a jackpot for that so imagine these two people took the bribe or maybe they were just like they thought bob was what should win for whatever reason and this guy's like no no it's Alice and then Alice wins an appeal that person not only has the sort of indication who's having been right he also gets the deposits of the other two people so he gets he's particularly incentivized to be this liked even more so despite what people are voting in his round if he thinks he will be coherent with the ultimate ruling so this recap that I just said so this means that the amount of money the attacker has to lock up actually goes with the square of the number of voters because he has to a theater wants to offer enough money to convince people to not defect and try to be the lone voice of reason he has to offer everyone actually m minus 1 D which means because there M jurors he's offering N squared ish amount of money and that's gonna grow faster than the amount of P amount of tokens locked up in the either by the voters but so at some point you actually get to the point where the attacker can't get enough tokens to pay everyone in with the parameters of our doge Pilate beyond 13 rounds of appeals kind of late but it would only cost about 80 eath to have appealed to the round 13 the attacker cannot lock up enough tokens to a pet to make these people as epsilon broads just because they don't exist so that that's good we can revisit what counter what happens with counter coordination in this framework so now imagine there are multiple rounds and the counter coordinators are sort of participate across multiple rounds what the counter coordination contract try to do is try to get Bob to win by extreme margins in the early rounds and milk as many bribes as possible and large bribes because brought Bob had to pay these people n minus one D in order to keep them on board and then engineer a narrow loss for Bob in the last round and then what happens is similar the last time people vote what they say they were supposed to but they're supposed to vote otherwise they lose their deposit these people don't participate so they'll just take the bribe so pesimistic away and now like these people get large bribes from bob because like they were participants in unanimous rounds in favor of bob these bribes are a little smaller but you you you bob narrowly lost bob lost four to three and then these people like like sort of there's a sharing of Bob's bribes between the two rounds and then you'll notice that taking the bribe in the last round is not as good as counter coordinating in the last round so if you're if you're one of these people like you have no incentive to defect and like to not participate in the counter coordination on the other hand these people like this person did the best so it's still not like it's still there's still some sense of instability because this person who didn't counter coordinate in an early round and got the full bribe the full gigantic bribe in that round they did really well but like counter coordinating and in the last round in later rounds is not is not as helpful and then what sort of happened here is that like you only need a few people up here to take the gigantic bribe to get to a point where a lot of sort of attacker money is sloshing around in paid bribes and you can use that to average out in a way to get bigger values here than here so you only need like a few people to counter coordinate in the early rounds to make the last round have counter coordination be profitable so what this is a done is basically leveraged altruism altruism is now more effective than it needed to be that used to be if you had like you only need yeah so I'd like you you only need a few optimistic people then rather than a lot of altruistic people and a few people that can make a difference in terms of whether counter coordinating like causes the counter for nation to win okay so the attacker can adapt to this he we have a couple of ideas of how the attacker can can change his what he does in order to like preserve the ideas of people's ups on attack without actually having to like go through exactly what I just said which turns out to like not work super well for the attacker so either the attacker can offer a bribe that only pays out in the last round so if you take the bribe an early round you just don't get you don't get the bribe but if you vote with the attacker in the last round you do another possibility to place a cap on what the bribe is paid so that gives you a payoff matrix that looks like this there's now there's now a cap bribe and just talked about the last round version briefly the attack if you're like if you're an individual voter you're thinking okay like now rather than taking the bribe being dominant I have to think am I gonna be in the last round if so taking the bribe is good dominant at least and if not well then I have to think of whether everybody else is gonna take the bribe and then if I should try to hear it with them so it becomes a sort of more complicated calculation for this person and for the we did a been attacked like this it didn't work any better than the other ones in fact in the last round there was actually a lower percentage of people who took the bribe than in previous rounds go figure so in terms of the captive version I guess I'm running out of time so I'm not gonna get well too much on this basically like you wind up with a situation between the pure people's epsilon and the sort of one round people have slept salon where you can still leverage algebra like be voting like participating as a counter coordinator is more effective than it would be didn't have an appeal system but not as effective as it is in a pure version of this attack so then and you wind up in sort of a mixed equilibrium so the voters have to think it's like I should vote for the attack with some probability which adds a level of complication so then just to conclude we already thought that cognitive costs were an obstacle in taking people subcell attacks to begin with that was one of our one of my probably the stronger defenses and then well because pure people's absent attacks are sort of harder or like less effective at least against well-designed appeal systems an attacker can adapt two versions that preserve the spirit of people steps on attack but are even more complicated so the cognitive costs are even higher so then because cognitive costs were already good they should even like they should be an even better defense with an appeal system and of course we're gonna do more experiments [Applause] thank you it gets quite complicated which is quite interesting one thing about the moral costs that I want to ask is do you include reputation or affects the reputation and moral costs I think that that's usually like there's a personal thing like I'm not the person that accepts bribes but maybe it's more important for them to say like I don't want to be seen as a person that takes bribes so I pray no at least not for now so like a priori so we don't have a reputation system built into Klauss at least for the moment so like in theory or pseudo noun and pseudo anonymous but you know maybe at some point but even despite that like it it seems that so either because of the cognitive costs or because of like between some mix of cognitive and moral cause people nonetheless even if they were pseudo anonymous didn't like seem to have some opposition to taking the bribe even if it's is some kind of private morality and another question is have you studied these kind of bribing attacks PF salon attacks in children of baselayer blockchain protocols like proof-of-work mining people considering bribing miners to do certain things if you guys looked at that at all yeah so there are equivalent attacks in terms of private matters so I I haven't thought about how like how like an appealable mining system could work in terms of trying to prepare that but but yes there that those kinds of phenomena exist Thanks hi thanks for the presentation so I've a few questions are there any other attacks to a Chenin game based Oracle or do you think this is the major attack vector for shelling game Oracle's so the other sort of attack that specifically targets kind of shelling protocols or attacks sort of pre revelation attacks where you try to influence people's votes by having already saying that you know like announcing your vote and then if other people want people here with the final answer they'll be like ah this person already voted maybe I should vote the same way too because like that like I can already see there's at least one vote in for that person so you'll notice that like that like the idea of counter coordinating like there's already some you know I think there's some implication to you know how other people are going to vote when your counter coordinating with them so we have ideas on how to defend against pre-authorization attacks and again the appeal system is sort of the best defense because if you're if the attack is someone shouting I'm going to vote for Bob I'm voting for Bob you know if you vote with me like will already be two out of three and be coherent well if you're all if you only get rewarded for being coherent with an eventual appeal then you don't really care about being coherent with that guy saying he's gonna vote for Bob you care about being coherent with some future pool of jurors and some future rounds who haven't even been drawn yet so like that that is already a defense and then two-degree that we need to like sort of defend mutually against people Zeppelin attacks and anti pre revelation attacks like there there are things you can conceivably do where you like counter coordinate from a different address and you make like some kind of zero knowledge proof or something that you're like one of the voters but so yeah though that's the other sort of showing specific attack sorry does this change in a system where you have identities and and then the second question is do you think that shilling game based Oracle's are the best Oracle's it's kind of general yeah so with regard to having only one vote so like a priori as soon as you have this fixed pool of path this panel of like n votes that are trying to coordinate with each other but on a shelling game protocol there's like this attack is there regardless of whether you're one-person one-vote or having a larger pool of people that some of some of the edge-to-edge phenomenon are a little different but like the basic idea is design and what kind of Oracle is best is probably situation dependent but shelling Oracle's are you know one of the one of the natural things you can do in this this kind of scenario thank you [Applause] we have a gray curtain