Deep dive on griefing factors - William George (@williamhwgeorge) @ETHDubaiConf

Transcript

uh indeed i i'm william uh i'm a researcher for the clerus cooperative so if you're not familiar with claros it's a blockchain place dispute resolution platform uh and i'm going to have sort of a more cryptoeconomics mechanism design talk where i talk about some of the research that we've done at claros to try to make clear with resistance to certain kinds of attacks called briefs uh both and you know sort of take build on some of the general conclusions of this research uh and have several examples a couple of which come from from claros uh so to illustrate what a grief is uh i'll start with a real world example and because klaus's dispute resolution platform i'll use an example involving disputes so in the real world in

traditional courts traditional dispute resolution it's sometimes possible uh to frivolously sue someone so you can spend resources lawyer fees uh to force somebody else to defend themselves and you're imposing a cost upon yourself because you hire your own lawyers but you're forcing this other side your opponent to defend themselves too so that forces them to take on a cost and this like idea that i'm harming myself to harm somebody else that's what we call a grief uh and sometimes in some jurisdictions maybe a judge at the end of the case will realize your dispute was frivolous and force you to pay the legal fees of

your opponent maybe maybe not depends on the case and the jurisdiction uh and so why would anybody do this uh well maybe they're your competitor uh and they think they have a bigger budget for law fees than you do so they're trying to drive you out of business uh maybe you live in a in a jurisdiction where um you have some underlying case that has some payment at the end that you like realize that morally you have to go the other the other person but you want to delay it because you think that whatever interest you might have to pay through the court will be less than like the real interest rate so you're reducing your time adjusted your liability uh maybe you short sold the stock of the defendant maybe you have a non-economic ideological reason you could be an ngo that just as opposed to the business model of the

party you're suing uh so you have lots of reasons um so this idea of a grief uh was uh really sort of pioneered by vitalik and the first reference that i'm aware of at least where he sort of discusses it in these kinds of terms and uses these words is in a blog post from 2016 called the triangle of harm where he analyzes griefs on consensus algorithms uh and he defines this measure of grief uh that he calls a griefing factor uh which is the harm that you do somebody else divided by the cost that you do to yourself so if i um uh and this could be monetary so for

example it can be harm in euro terms or cryptocurrency terms uh i'll have a couple examples at the end it'll be non-monetary um so like for example uh if i can spend one euro to do five euros of harm to somebody else that has a griefing factor of five uh so to have a slightly more complicated example uh this is a payoff table uh so if you're not familiar with sort of game theory and economics literature the idea is that it tells we have a two-player game so each of alice and bob can do take two actions where alice can play you or d up or down and bob can play l or right

l or r left or right and then so you have some four of possible outcomes of the game and each in each outcome you have the payoffs for the two players so for example if alice plays you and bob plays l then you're in the upper left corner of the table so that the numbers in that that box tell you what each player should be paid alice is the first number bob this payment is the second number so ul gives you a payment of alice of one and a payment to bob of two uh if alice plays d and both plays l then you're in the lower left and they both get zero uh and a fundamental concept in game theory literature is the notion of equilibrium which is a strategy that neither player if they're rational would want to

deviate from neither player regrets uh so here ul is in equilibrium uh because alice you know what can she do she can play d instead of u uh but that takes her payment from one to zero uh bob could play r into the l but that takes his payment from two to zero so neither player wants to do that if they're rational but not everybody's rational uh so for example alex could look at this and be like wait why does bob get two and i only hit one screw you bob uh and um decides to blow up the negotiation and play d instead of you even though that cost her something to cost bob more and there's psychology research that shows that people actually often think like this if they um think that they're getting a raw deal

and somehow a game is unfair they're willing to take a loss to have sort of what they see something of a more just outcome uh but this is a sort of grief uh where here if um compared to like the default of playing ul uh and this is kind of an annoying technical point we always have to consider a grief compared to the default option of doing something else so there are like four different possible outcomes of this game and we consider one of them to be the default the equilibrium strategy ul and all the other sort of groups are compared to that uh but compared to the default of playing ul alice's grief of deviating it costs her one and does bob damage of two so it has a different factor of two okay

so the term comes from gaming sort of as you can see defined here i'm not sure if it might be blurry but a griefer in multiplayer games is someone who does harm to others without really having a benefit to themselves if they had a benefit to themselves would be called cheating and i'm going to survey a few of the existing thoughts people have had about this this idea and then i'll touch on some of my own research and some of the ways i've been thinking about this uh so there's a long traditional economics literature on sabotage it's not it's you know it's a basic concept it's not it's not like a surprising idea uh and people economists have analyzed sabotage but usually it's built into the payoff matrices they

consider uh so if you consider that sort of like two by two matrix i had a couple slides ago um most economists look at situations like okay like i have competitors they benefit from sabotaging each other and then i'll construct this game that builds in the sabotage to how the players benefit the players payoffs and then i'll analyze that uh and the power of the notion of griefing and griefing factors is you don't have to know how the other side is benefiting from the grief in order to do this analysis um you can say okay like this strategy it has a grouping factor of x i don't know why anyone would do it but if they did this is grieving factor and then you can just try to design your game in a way that keeps the griefing factors down by

having to predict in advance how others benefit so there's this flexibility in this this idea um so another sort of point of existing research that relates to again work that vitalik did is on the notion of discouragement attacks uh and relatedly evolutionary stability so here the idea is you might have a game where if everybody plays normally honestly everybody gets some kind of gain everybody benefits but um one player can decide to deviate that and posing a loss on herself uh but also imposing a loss on the other players i'll have an example of this in a couple slides and then the idea being that the one the griefer is willing to take a loss so that the other players who were still

performing honestly also take losses uh and hopefully at some point they'll they'll cite it themselves well why am i playing this game or doing my best and i'm taking a loss and they'll just give up and leave and the griefer will be left with control of the system so a specific example is in proof-of-work mining and there's this pre-print paper analyzing griefs and proof of work mining by these researchers from the university of london and the singapore university of technology and design where they prove that in fact the equilibria in the game of how much mining power you decide to use how much hash power you decide to use is not like it has a discouragement attack it's not in their words evolutionary stable basically miners are incentivized to

mine a little more than what this sort of cost benefit analysis of the rewards would tell them to to reduce the so take a like take a larger percentage of the total mining rewards uh even though they're spending more electricity so they have like not maximizing their profit but they take a larger percentage of the rewards and because they took a larger percentage of the awards they reduce the rewards of the other players which might drive them to a loss and maybe push them out uh the people of the ethereum foundation have spent a lot of time thinking about grief in the context of um like the proof of consensus algorithm so in proof of stake there are various actions you can do depending on the tasks assigned to you it feels like you're in a tester or a block producer

and you can fail to do those tasks which generally produces some kind of grief and you can see that they've basically designed the system in a way that the griefs aren't too big no matter which one of these griefing actions you do and these numbers are based on the sort of real payoffs as of a couple weeks ago they vary slightly based on the state of the network um okay so that's all interesting but as i said like greece exists in the old world why do we talk about them so much in in blockchain world uh and i have a couple theories for why they're particularly relevant to us uh and why this is something that we as we've innovated and researched on and it wasn't necessarily in the past uh so first of all as we sort of already hit

on with the litigation example external incentives can lead someone to do something which looks like a grief if you just consider the internal incentives of the game and that's very much a thing in in crypto economic and blockchains uh you as a mechanism designer can build your protocol and you can say okay i i've done a good job uh whatever honest strategy i want people to do ul that's it's a dominant strategy everybody's gonna do it uh and then you realize that somebody can issue some kind of atomic interaction via transaction take a flash alone i don't know uh connecting you to a different app a different dap that changes the effective payoffs for the participants maybe this is a maybe you designed like some kind of

oracle and in order to mess with the oracle you have to take on some fees and take a loss nobody would do that right but you know when somebody manipulates your oracle to use it false information on some other platform they might be able to gain uh and here this path example that i had from a couple slides ago now alice what looked like a grief before is actually some kind of dominant strategy a second reason why i think this is relevant in crypto economics is we have particular issues with oracle's continuing on the theme of oracle's in centralized systems some kind of benevolent dictator can make a subjective judgment that some behavior constitutes a grief or an attack and they can punish accordingly in a video game if i go around griefing people essentially i might get banned uh in

that court example at the end of the case maybe the judge orders me to pay the legal fees of the other side in blockchain this is really hard uh it's generally not possible to have this kind of benevolent dictator that comes in at the end and makes everything right and finally some people just want to watch the world burn trolls are a thing uh and uh maybe we have more of them than other fields maybe um okay so now i'm gonna hit on some things that are more related to my work so i apologize for the math i promise we'll be pictures in a second uh this looks at how equilibria change when you have griefing players uh and the idea is

okay take the formula that i defined for what a grouping factor was and it expanded out a little bit so like on the top i have the sum of the harms that i do to the other players the sum of the differences of their utilities based on my grief uh on the denominator i have the difference in my own utility and then i'm going to rearrange that uh and in the second line uh i've rearranged the formula and then you say if the player is going to commit a grief they have to have some reason they did that even if they're just a pure troll uh so they have to get some kind of extra utility when you think about a broader notion of their utility that's going to encourage them to take on this grief so i'm going to define another auxiliary utility function utility function that's

going to add that in basically and in order to be willing to do this grief in equilibrium uh they have to get at least enough utility from the grief to take on whatever they lost to the sort of internal utility function uh so you define this u prime uh which just captures that basically uh so you think of each player having some kind of greeting factor that they're willing to grief at uh a lambda i so like each each participant might have different lambda eyes depending on how trollish there are maybe maybe my lime to i is five uh some more trolley player would be willing to grief at like a lambda i of like one they're willing to do like a worse grief and they still do it uh and then for you to find the uis uh in terms of this line at the bottom

that's sort of what gives you people being willing to grief in equilibrium and what essentially happens is you take the old utility they had and then you just add in lambda i inverse times the harm they did so if i could do two harm and i have a greeting factor of five uh i took my old utility and the extra utility that i got from the grief is two over five uh and another technical point remember before i said that the base point the like the thing the the outcome that you're gifting with respect to uh term is important in defining your grief uh you can actually get rid of that when you take this perspective of equilibrium uh there's uh when you look at this payoff formula utility formula the term with that in it just cancels out and you

get this other auxiliary utility function which is the second line and here basically i've taken the perspective that instead of getting pleasure from harming others i have i'm annoyed while others do well which is kind of the same thing uh if i look at the example at the bottom um you know in the upper left each player gets one utility and i can say i like like if they weren't trolls that would be that would be the utility they have but if they are griefing players maybe alice says oh like i got a utility but so did bob and you know maybe i don't like bob and i wanted to do poorly uh so i lose a little bit of utility because bob got utility okay so i threw the formulas sorry about that uh and um

now at each tuple of lambda eyes each sort of pro each list of trolliness of the different players you have uh you have a set of utility functions that defines the game and as you change as long as you change the game and you can consider the equilibria in each version of this game uh which gives you a sense of how stable your system is like how much did the equilibrium change when you have super trollish players versus not so trollish players and if the changes are really radical uh maybe your game isn't so stable and maybe you could be just destroyed by an army of trolls um so here in this this payoff table abstract example that i had before uh you get this this picture uh of um as

you vary the lambda one and lambda two uh you have different regions that you pass through where each you have different equilibria behavior uh so each time you cross a dotted line this sort of behavior your game just radically changes uh and this picture might seem a little artificial because i have a two-player game and they're both trolls they're both griefers uh that kind of seems like spy versus spy but you can take the same perspective where you have end players k-trolls uh and um you still can do the same thing you'd have like a k-dimensional space where you can look at the picture of how the behavior of the games change uh you know even though you have n total players in your game uh so this gives you a graphical way of looking at the stability of your system uh and as an example back to the proof

of work mining example from that paper from the people from university of london in the singapore university of design and technology i can extend their work where i look at that game in the same sort of analysis only now i vary the griefingness of my players uh and you see that the unique equilibria the unique equilibrium in that game is this is is this um this this formula here uh which determines the hash power and equilibrium of each of the minor mining players uh and this player this formula is really nice because it's continuous in lambda and lambda i uh like ideally the best case scenario would be that no matter how goofy your players were that this behavior game has never changed uh

you always got the same equilibrium uh but like kind of the next best thing that can happen uh is that if you have more or less scripting players your game doesn't change too much it changes really slowly in a continuous way and if you look at this if for like all like reasonable lambda eyes the amount of mining that the players do barely changes unless you have like a lunatic that's willing to grief at really small grouping factors at which point then then their qi changes uh so you have this very continuous very very minimal change from the presence of grieving players you're very resistant to griefs okay so now just sort of uh hitting briefly on some griefs that caused non-financial harm so in the shanghai dos attacks the

griefers spent gas to perform the attack and as far as we know they didn't seem to have any kind of financial benefit from doing this attack uh but what they did was they increased the copy bit you know there were different sets of attacks but generally they increased the computational load on node operators using different node node software uh so here the harm is in computation having to be done and the cost isn't gas another situation that we frequently have to think about is delay griefs where the harm is done in time in terms of time so now it's harm in terms of time divided by cost which might still be monetary uh and as an example in claros again it's a dispute resolution platform

uh we have a notion of appeals sometimes you can appeal fervorously uh similarly to the kind of frivolous litigation in the similar first and then in the real world example uh so maybe your case starts with three jurors you appeal next time there might be 7 15 31 doubling plus one every time but the number of jurors roughly doubles and each time you appeal you increase the amount of time that it takes to resolve the case by roughly a fixed period it depends a little bit on what case you're talking about maybe it's a week maybe it's three days but each time you appeal you get additional appeal period which is fixed but the cost of doing the appeal is proportional to the number of jurors

so it's growing exponentially it's growing as 2 to the n which means that your griefing factor for appealing n times is o n over 2 to the n so asymptotically it's not very big maybe the first appeal is cheap enough that you're willing to do it you know it doesn't cost too much yet because you're only seven jurors but you can still delay it for a week but if you have more and more appeals uh the cause the cost of appealing for a month for more is is maybe is prohibitive uh which is not necessarily um a kind of asymptotic behavior that you science see with the real world from this litigation so asymptotically as you grow the griefs aren't too bad uh

some other prominent delay griefs you can have frivolous challenges on curated lists whether that curated list is using klaros or some other mechanism in roll-ups uh specifically in arbitrary you can challenge a state update which starts an interactive game that interactive game takes some amount of time that results in a delay uh and all of these examples touch on issues with oracle's the sort of broader point i made at the beginning about how our oracles aren't all that great uh in that like claros is a subjective article to it has to do with disputes what is the right answer of dispute arbitrarily if you sort of squint and think abstractly when you're doing a state update on l1 you're kind of doing an oracle operation about what's happening on the l2 uh l1 doesn't know what the right

answer dispute is it doesn't know what the right state of l2 is until you tell it that information and this process of telling that information might be subject to delay griefs i um that's it like that is one trade-off you can make when you're designing that game okay so just to conclude uh griefs can be results of hidden motives or they might just be the results of trolling this is particularly relevant for the interconnected world of blockchains because of external motivations uh griefing factor approach allows you to abstract away what those external motivations are and just try to optimize for your griefs and thinking about the variation in terms of this like geometry game

geometry diagram that i showed can give you a global sense of whether your system is stable to different levels of briefing it's possible that your groups might be explicit uh maybe sometimes they're the unintended results of like how much um some operation costs and gas or something uh like you didn't intend when you created the design of your game they can be financial or involve time or some other resource and what you really care about is them not being too bad as you have sort of whales and larger players uh that could do real harm okay so thank you and i'd be happy to answer any questions of their time thank you very much

so i'm ready to take questions uh could you explain the logic behind lambda inverse in your equation yeah like why is it an inverse versus like a lambda or no i got the lambda i in the last equation yeah could you could you explain i couldn't get that part the i got the equation but not the lambda inverse part yeah so the lambda is uh i replaced the gf thing uh so like the idea is that i define a griefing factor in terms of this thing in the first line in the second line of rearrange the first line and in the third line i take this perspective that each player has some griefing factor

that they're willing to grief at now uh and um so i assigned each player orlando that is their their like their level of griefiness uh so you'll notice that it just like replaces the the gf yeah okay i got that thanks [Music] anyone else uh so is it possible right now we define harm and gain in scalar values uh is it possible that uh the values of the attacker and uh the attacked may be a little bit more complex or maybe valued at different uh from different perspective in a different way is there a way to account that in those equilibria formulas too yeah so i mean in order to do this kind

of analysis with the the pictures uh you need to have um some payoff table for how you think people are what utility they get from playing the game it doesn't have to necessarily be like constant values like this uh they can have like a continuum of different values for like infinitely different many outcomes of the game but you have to be able to assign some utility to each player in each outcome right seems fair so alternatively we probably could just add multiple units there right that you just don't get paid in one unit but like in three different units i guess yeah you know you could if people have sort of complex motivations you need

some way to like smash them together into a utility function all right team sir oh yeah uh is there any research on bribing on the d5 ecosystem the token bribes do they become griefing on bribing yeah yeah so some of our other research uh is like related to uh bro special kinds of bribes in klaus because you know another thing you might try to do is try to bribe the jurors uh there are specifically um very interesting broads called people's episode attacks that we published a paper on recently this is again based on like a blog post of italic where he sort of introduced this attack back in the day on a system that was like a

predecessor influencer of claros uh and um of course there's research on bribing in the economics literature more generally so the so yes there's research on driving the kind of line where a bribe becomes a grief or where like an attack becomes a grief is where the you don't know what utility the the attacker is getting from doing the attack uh so with the bribe maybe you you can have this perspective um of having a specific outcome that they're trying to get uh that you know the utility of that and you can do like a maybe a richer analysis of the game because you have this extra information about what their goal is

you