Abstract

Smart contracts allow flexible new forms of trust-free cooperation. This gives mechanism designers a new platform in which they can apply game theoretical principles to engineer desirable outcomes. However, as we have seen with the emergence of “dark DAOs,” hostile attackers can just as easily deploy smart contracts that coordinate collusion and otherwise attempt to undermine the goals of a given game theoretical structure. Indeed, attacks on incentive structures that would previously have seemed elaborate and difficult to organize can now execute automatically, requiring no trust in the attacker, via smart contracts. In this work we will analyze the “p+ϵ attack'' on Schelling point based cryptoeconomic systems. Particularly, we will consider design choices that one can apply, slightly modifying these systems, to increase resistance to these types of attacks.

Paper Summaries

“This paper aims to formalize a number of models for focal point games related to blockchains… The authors of this paper aimed to formalize these games and provide proofs for sufficient conditions for when there is a dominant strategy (Section 6, 7). The paper proceeds by analyzing these models in an increasingly realistic manner: (1) All non-attacker votes are honest except 1 who triggers an appeal / re-vote; (2) Randomized budget for the attacker (from a static wealth distribution), randomized appeal; (3) Considers alternative p+ϵ payoff matrices”

“The paper builds on the p+ϵ attack to bribe voting participants by offering to pay each voter a sum, conditional on the ‘honest’ choice gaining a majority of votes (payable if the voter chose the attacker's preferred ‘dishonest’ option), under three scenarios pertaining to the structure of the game. The authors compare the required attacker expenditure to the cost of a 51% attack on a blockchain [and] also evaluate the game under particular assumptions about the distribution of wealth and capping of bribe payouts. Finally, the authors report on the results of a p+ϵ attack they carried out.”

“The paper studies bribery attacks on voting systems. Agents have to vote for either X or Y and receive a reward for voting with the majority. The underlying assumption is that X is the correct answer, and we rely on votes as a blockchain oracle for the correct answer. In the simples utility scheme, an agent receives p for voting with the majority or 0 otherwise. The p+ϵ attack consists of an attacker offering p+ϵ whenever an agent votes Y but the majority votes X. The hope is that the offer serves as a focal point where all agents will accept bribery and vote Y, resulting in the majority voting for Y and the attacker paying nothing. [Additionally, the] paper studies other reward schemes and their resilience to bribery attacks [e.g., Schelling game with penalties, Symbiotic Schelling Game, Redistributive Schelling Game]. The paper also considers the variation where any voter can appeal the current vote by paying R. Once a voter appeal, a new election starts with new independent voters. The result of the last election becomes the result of all previous elections. The paper focuses on the success rate and the worst-case cost of an attack.”

Paper Strengths

“The paper considers many different settings. It does an excellent job of pointing out the limits of their analysis and how the assumptions might be too strong in practice. They exploit these arguments to study variations that are more likely to hold in practice.”

“The paper rigorously defines terms and proves results of each game structure evaluated. The mat initially appears daunting, but once reading the paper, one realizes that each successive game and proof is a variation on a theme, which one is able to follow the argument at various levels of depth (depending upon the amount of detail the reader wants to examine).

One important implication, I think, is the implication that current blockchain validation protocols are potentially vulnerable to p+ϵ attacks.”

Paper Critiques and Author Responses

“The paper alludes to application scenarios, such as block validation in blockchains… [I was left] wishing there was more discussion of the application in some of these circumstances.”

Author Response: Further discussion on these applications has been added to Section 6.

“The precise threat model for each result isn't specified and it is hard to compare the threat models between, e.g., Theorems 7.4 and 7.5”

Author Response: Proposition 7.4 and Theorem 7.5 actually have very similar threat models; there is one additional assumption on the distribution of the budgets of attackers made in Theorem 7.5 that is explicitly listed as a condition in the statement of that result. Essentially, these two results concern two different equilibria in the same game. (There are a couple of paragraphs of exposition on p.12 where we informally compare the relationship between these equilibria to that of the pure and mixed equilibria present in the game of "Chicken".) Moreover, [the current] structure of the paper is such that the assumptions that are required on the model generally through the work are presented in Section 5, but then requirements that are only needed for some results are placed in the statements of those results. Considering the comments of the reviewers, it might be clearer to future readers if we introduce every modeling assumption that is required anywhere in the paper in Section 5, labeled in some way, e.g., "Assumption A: each vote is controlled by a unique entity, Assumption B: the attack and the distribution of fB are common knowledge," etc. and then in a given result say "Under Model BC …" to indicate that assumptions B and C are taken for that result.

“Sections 8, 9 feel a bit rushed and unmotivated (it might make sense to elide them or move them to another paper)… The empirical work has no uncertainty estimates and/or likelihood tests that justify some of the assertions made (e.g., computations of certain tail probabilities do not come with KS tests).”

Author Response: Note that the statistical tests employed in Section 10 are all binomial tests. Thus, as these are exact tests, there is no normal approximation (hence using a KS test to validate the appropriateness of such an approximation is not necessary). The only assumption that one must make to use this test is that the draws of tokens used to determine the participants who have the right to vote are independent (which is explicitly addressed as following in this case from the Kleros random selection process).

“The paper does not define a formal model, and modeling assumptions could be better motivated. It is not clear that it is without loss of generality to assume that a voter can only participate once over all rounds. I can see that this assumption is without loss in some cases, but I am not convinced that it is reasonable throughout the paper. I am also not convinced that at worst-case cost is a very relevant cost in practical settings. The paper mentions adaptations of the attack (Section 9) that would make more effective but I don't find the results on this section convincing.”

“Proposition 9.1: I'm not convinced of this result. In the analysis $f(0) \geq \epsilon > 0$ and $f(1) \geq \epsilon >0$, but Lemma 8.2 requires $f(0) < 0$ or $f(1) < 0$.”

Author Response: [This review] has usefully highlighted some small errors in the statement and proof of Proposition 9.1. It should be assumed that: $d+p < H<Md+Mp$ rather than $d\leq H<Md+Mp$ as currently stated. Then one can prove that $f(0)>0f(0)>0$ as $f(0)=(M−1)d+Mp− min\{(M−1)d+Mp+ϵ,H−d\} =\max\{(M−1)d+Mp-((M−1)d+Mp+\epsilon),(M−1)d+Mp-(H-d)\}= max\{−ϵ,Md+Mp−H\}=Md+Mp−H>0$Similarly, one can prove that $f(1)<0$ as $f(1)=p−\min\{p+\epsilon,H−d\} =\max\{p-(p+\epsilon),p-(H-d)\}=\max\{-\epsilon,d+p-H\}<0.$From that point the proof proceeds unchanged.