Consensus as a Coordination Game

Distributed consensus is usually taught as a fault-tolerance problem: some processes are correct and follow the protocol, some are faulty and do not, and the engineering task is to guarantee agreement as long as the faulty ones stay under a bound. Game theory asks a different question about the same system — not “what will a broken node do?” but “what would a self-interested node do?” — and the two questions have different answers. The reframing is not decoration. It produced a third fault class (rational nodes, which follow the protocol only where following it pays), a protocol family designed around that class (BAR: Byzantine–Altruistic–Rational, Aiyer et al., SOSP 2005), a set of impossibility results with different bounds from the classical ones (Halpern & Vilaça 2020; Abraham, Dolev & Halpern 2007), and — in blockchains — the discovery that a protocol everyone believed was incentive-compatible was not (Eyal & Sirer 2013). This note applies the vocabulary of Nash Equilibrium, Mechanism Design, and Incentive Compatibility to agreement protocols. It does not re-explain how consensus works — see The Byzantine Generals Problem, Practical Byzantine Fault Tolerance, and Consensus in Databases with Raft and Paxos for that. It also tries to be honest about where the game framing genuinely adds insight and where it is only relabelling; that boundary is drawn explicitly in the penultimate section.

Mental Model — Consensus Is Two Different Games Wearing the Same Name

The single most useful thing the game-theoretic lens does is force you to say which game you think you are playing, because the word “consensus” covers two structurally different ones.

A coordination game is a game in which the players’ interests are aligned on the fact of agreeing, even if they disagree about what to agree on. The purest form has multiple Nash equilibria, all of them “everybody picks the same thing,” and no equilibrium in which players pick differently. The Stanford Encyclopedia’s treatment calls the two-equilibrium version Hi-lo and uses it precisely to make the point that Nash equilibrium alone “is our only solution concept, [then] we shall be forced to say that either of these outcomes is equally persuasive as a solution” (SEP, Game Theory). The problem in a coordination game is not that anyone wants to defect — it is that nobody knows which equilibrium the others are heading for.

An adversarial game is a game in which at least one player’s payoff is increasing in your loss. The Byzantine setting is this: the Byzantine Generals paper grants traitors the ability to “send conflicting information to different parts of the system,” with no constraint that they gain anything by it. A Byzantine node is not merely uncoordinated; it is not modelled as having a utility function at all.

Consensus protocols are almost always described in the second frame and almost always deployed in a setting that is really a mixture of both plus a third thing. That third thing — a node that has a utility function, will follow the protocol when following pays, and will quietly shirk when it does not — is the contribution of the BAR model.

flowchart TB
    subgraph CG["Coordination game"]
        direction TB
        CG1["All players prefer<br/>agreement to disagreement"]
        CG2["Multiple equilibria:<br/>one per agreeable value"]
        CG3["Hard part: equilibrium<br/>SELECTION, not enforcement"]
        CG1 --> CG2 --> CG3
    end
    subgraph AG["Adversarial / Byzantine game"]
        direction TB
        AG1["f players have<br/>unknown or hostile utility"]
        AG2["No equilibrium reasoning<br/>applies to them at all"]
        AG3["Hard part: guarantee the<br/>rest agree ANYWAY"]
        AG1 --> AG2 --> AG3
    end
    subgraph BAR["BAR model (Aiyer et al. 2005)"]
        direction TB
        B1["Byzantine: arbitrary"]
        B2["Altruistic: obeys<br/>even when it should not"]
        B3["Rational: obeys iff<br/>obeying maximises utility"]
        B1 --- B2 --- B3
    end
    CG --> BAR
    AG --> BAR

What it shows and the insight to take: the two classical framings sit at opposite ends — one assumes everybody wants the same thing, the other assumes some players want the opposite — and BAR is the merge. The insight is that the interesting failure mode of a real deployed consensus system is neither of the endpoints. It is a node that is neither broken nor malicious, that would very much like the system to reach agreement, and that would nonetheless prefer someone else pay the bandwidth bill.

Consensus as a Coordination Game, Properly

Take the simplest honest model. n processes each hold an input value; each strictly prefers that its own value be decided, prefers any decision to no decision, and is indifferent to everything else. Halpern and Vilaça formalise exactly this and call it caring only about consensus: write β0ᵢ for process i’s payoff if its own initial preference is decided, β1ᵢ if consensus is reached on somebody else’s value, and β2ᵢ if no consensus is reached at all. The assumption is β0ᵢ > β1ᵢ > β2ᵢ for every i (Halpern & Vilaça 2020, §3). Reading the symbols: the first inequality says you would rather win than merely agree; the second says you would rather merely agree than have the system hang. That second inequality is what makes it a coordination game — disagreement is the worst cell for everyone.

For two processes with binary inputs, the payoff matrix is the following, with the row player’s payoff first:

	Column decides 0	Column decides 1
Row decides 0	(β0, β1)	(β2, β2)
Row decides 1	(β2, β2)	(β1, β0)

Both diagonal cells are pure Nash equilibria: given that the other process is deciding 0, deciding 0 yields β1 (or β0) which beats β2. Neither off-diagonal cell is stable. This is the textbook shape of a coordination game with distributional conflict — sometimes called Battle of the Sexes — and it already tells you three things about consensus that the fault-tolerance framing does not:

1. A consensus protocol is an equilibrium-selection device. Its job is not to make agreement attractive — agreement is already attractive to everyone — but to make one particular agreement predictable. Leader election, ballot numbers, view numbers, round-robin sender rotation: all of these are focal-point machinery. This is why the BAR authors note in a footnote that because the protocol “can be regarded as coming from an external authority, some prefer to regard such an equilibrium as a correlated equilibrium” — the protocol is the correlating device, exactly Aumann’s construction (Aiyer et al. 2005, §3 fn. 1).
2. Validity is what makes the game non-trivial. Without it, “everyone always decides 0” is a perfectly good equilibrium and a perfectly useless protocol. The Byzantine Generals paper makes this same observation without the game vocabulary: its condition IC2 exists precisely to rule out the degenerate constant protocol.
3. The deviation to worry about is bias, not sabotage. If a rational process deviates, the likely result is still a consensus — just on a value it preferred. Halpern and Vilaça make this point sharply: “When the agent deviates from the purported equilibrium, consensus is still reached, just on a different value.” Classical fault tolerance has no vocabulary for this failure, because by its lights nothing failed.

The Impossibility That Only the Game Framing Can State

Here is the first result that is genuinely not a relabelling. Consider fair consensus, where the decided value is drawn uniformly from the participants’ inputs — the natural fairness notion when you do not want any process to have undue influence, and the one you want for, say, deciding whether to commit or abort a transaction across mutually distrustful parties.

Theorem 1 (Halpern & Vilaça 2020). If ~σ solves fair consensus, agents care only about consensus, and f ≥ 1, then ~σ is not an f-Nash equilibrium.

The term f-Nash equilibrium (their generalisation of ex post Nash equilibrium) means: for every fixed failure pattern with at most f crashes, and every fixed vector of initial preferences, no process can raise its expected utility by deviating. In plain terms: no matter what the adversary does, honesty is optimal. The theorem says no fair consensus protocol has this property, even for a single crash failure, even in a synchronous system.

The proof is a short indistinguishability argument, and it is worth walking because it shows where the game content lives. Fix an initial configuration where every process except i prefers 0, and i prefers 1. By fairness, in the failure-free pattern the decision is 1 with positive probability. But in the pattern where i crashes immediately, before sending anything, no process can distinguish the run from one where i also preferred 0, so validity forces the decision to 0. Between “i never crashes” and “i crashes before speaking” there must be a minimal failure pattern F* at which 1 first becomes possible. Now let some process j that receives i’s round-m message under F* simply pretend it did not — the system slides to a pattern below F*, where the decision is 0 with probability 1. If j prefers 0, that lie is a strict improvement. The protocol is therefore not an equilibrium.

Notice what did the work: nothing broke. j executed a perfectly well-formed protocol step; it merely lied about its inbox. No classical correctness property was violated by j — the run it produced is a legal run of the protocol under a different (permitted) failure pattern. This is a failure mode that only exists once you grant processes preferences.

sequenceDiagram
    participant i as Process i (prefers 1)
    participant j as Process j (prefers 0, RATIONAL)
    participant k as Process k (prefers 0)
    Note over i,k: Context: minimal failure pattern F* where "1" is still reachable
    i->>j: round m: my value is 1
    i--xk: (crashes; k receives nothing)
    Note over j: Honest play: report "heard 1 from i"<br/>=> decision is 1 with positive prob.<br/>=> j gets β1
    j->>k: "I heard NOTHING from i"
    Note over j,k: Run is now indistinguishable from F' < F*<br/>=> decision is 0 with probability 1<br/>=> j gets β0 > β1

What it shows and the insight to take: the diagram traces the single deviation that kills ex post equilibrium for fair consensus. The insight is that the profitable lie is not a lie about a value — those are what signatures and quorum certificates already prevent — but a lie about what was not received. Silence is unforgeable and unattributable, so no cryptography closes this hole. This is the same “he said/she said” problem the BAR authors identify as their hardest case: “a node may decline to send a message that it should send… it is difficult for any third party to decide whether an accusation of inaction is legitimate.”

The escape is to weaken the solution concept. If you assume a probability distribution π over contexts (failure pattern plus initial configuration) rather than demanding optimality against every context, equilibrium returns. Halpern and Vilaça’s protocol σ^cons is a π-Nash equilibrium — and even a sequential equilibrium, meaning the threats it relies on are credible off the equilibrium path — provided π supports reachability (it puts small probability on failure patterns that isolate a surviving process) and is uniform (equivalent failures of different processes are equiprobable), and provided f + 1 < n (Theorems 2–4). The protocol’s enforcement mechanism is worth noting because it is pure mechanism design: every process counts apparent crashes, and if it ever observes more than f apparent crashes it decides ⊥ — no consensus. A process that fakes a crash therefore risks pushing the run over the abort threshold if f others really do crash, and since β2 is the worst payoff, the gamble is only worth taking when real crashes are unlikely. The threat of global failure is the punishment that disciplines the individual lie.

Note the arithmetic. The classical synchronous crash-tolerant consensus algorithm tolerates up to n − 1 crashes — Halpern and Vilaça open by observing that consensus “can be achieved in synchronous systems even if we allow Byzantine failures,” and the crash case is the easy one. The equilibrium version needs f + 1 < n, i.e. n ≥ f + 2. One extra process. Hold that number; it recurs.

Uncertain

Verify: the exact classical bound f ≤ n − 1 for synchronous crash-fault consensus. Reason: it is standard textbook material (the f + 1-round flooding algorithm), but I did not fetch a primary source stating it during this research — Halpern & Vilaça assert the possibility result without restating the bound. To resolve: check Lynch, Distributed Algorithms, Ch. 6, or Attiya & Welch Ch. 5. The comparison being drawn — that the equilibrium version needs strictly more processes than the correctness version — is stated directly by Halpern & Vilaça’s f + 1 < n and is not in doubt.

The BAR Model — Adding a Third Fault Class

The BAR model comes from a specific engineering problem: building cooperative services spanning multiple administrative domains (MADs) — peer-to-peer backup among dorm residents, cooperative archival storage, wireless mesh routing — where “nodes collaborate to provide some service that benefits each node, but there is no central authority that controls the nodes’ actions” (Aiyer et al. 2005, §1). The authors’ complaint about the classical model is exact: in MADs, “the classical dichotomy between correct and faulty nodes” fails, and it is “not sufficient to verify experimentally that a protocol tolerates a collection of attacks identified by the protocol’s creator.”

Their three classes, quoting the definitions:

• Altruistic nodes “follow the suggested protocol exactly… Intuitively, altruistic nodes correspond to correct nodes in the fault-tolerance literature.”
• Rational nodes “are self-interested and seek to maximize their benefit according to a known utility function. Rational nodes will deviate from the suggested protocol if and only if doing so increases their net utility from participating in the system.” The utility function must account for costs — CPU cycles, storage, network bandwidth, message overhead, power, threat of financial sanction — and benefits.
• Byzantine nodes “may deviate arbitrarily from the suggested protocol for any reason. They may be broken… or may just be optimizing for an unknown utility function that differs from the utility function used by rational nodes — for instance, ascribing value to harm inflicted on the system.”

That last clause is the crisp definition of the Byzantine/rational boundary: Byzantine is not “malicious,” it is “utility function unknown to the protocol designer.” Once you have written down a utility function you have moved a node out of the Byzantine class and into the rational one, and gained the right to reason about its best responses.

The paper then defines two correctness targets, and the distinction between them is the most reusable idea in the whole area:

• IC-BFT (Incentive-Compatible Byzantine Fault Tolerant): the protocol delivers its safety and liveness properties and “it is in the best interest of all rational nodes to follow the protocol exactly.” Following the protocol is an equilibrium.
• BART (Byzantine Altruistic Rational Tolerant): the protocol delivers its properties “in the presence of all rational deviations from the protocol.” Rational nodes may take local shortcuts; the guarantees hold anyway.

IC-BFT is a strict subset of BART. The engineering reading: IC-BFT says nobody wants to cheat; BART says cheating does not matter. BART is weaker and often the achievable one, because it does not require you to have enumerated every profitable deviation — only to have made none of them harmful.

flowchart LR
    A["Protocol P"] --> Q1{"Safety + liveness<br/>hold under all<br/>rational deviations?"}
    Q1 -->|No| BAD["Not BART<br/>(a selfish node can<br/>break agreement)"]
    Q1 -->|Yes| BART["BART"]
    BART --> Q2{"Is following P<br/>a best response for<br/>every rational node?"}
    Q2 -->|No| B2["BART only:<br/>tolerant of shirking,<br/>but shirking happens"]
    Q2 -->|Yes| IC["IC-BFT<br/>(strictly stronger)"]
    IC --> NOTE["Classical BFT sits<br/>OUTSIDE this diagram:<br/>it assumes non-Byzantine<br/>= altruistic"]

What it shows and the insight to take: the decision tree separating the two BAR correctness classes, with classical BFT deliberately drawn as off-diagram. The insight is that classical BFT is not a weaker point on this scale — it is a claim on a different axis, because it silently assumes every non-Byzantine node is altruistic. A PBFT deployment across administrative domains is not “BART with a smaller f”; it is a protocol whose guarantees say nothing at all about the case that actually occurs.

Mechanism Design Inside a Consensus Protocol

The BAR paper’s replicated state machine is PBFT with the incentives fixed, and the specific fixes are the most concrete instance in the systems literature of Mechanism Design applied to a protocol. Reading them as mechanism design rather than as engineering tricks is what P8 of the Games and Strategic Systems in C MOC is for.

Accountability first. “If nodes are accountable for their behavior, then rational peers have an incentive to behave correctly.” The easy case is a self-contained cryptographic Proof Of Misbehavior (POM) — a node signs a promise to store a file under a given hash, then signs a response containing different data, and the two messages together are a signed confession. Aggressively Byzantine behaviour is the easy case precisely because it is provable.

Limit non-determinism. “Non-determinism offers nodes the choice of multiple behaviors… Self-interested nodes can hide behind non-determinism to shirk work.” This principle drives the single largest structural change: the BART state machine is built on Terminating Reliable Broadcast (TRB) rather than on consensus. In TRB only the designated sender may propose in a given instance, and the instance can end only two ways — everyone adopts the sender’s value, or everyone adopts a default. Under a consensus primitive, a new leader elected after a timeout “may prevent progress by selfishly trying to make the state machine adopt its value rather than the sender’s.” Fewer legal outcomes means fewer profitable ones. In game terms: shrink the strategy space until the deviations you cannot punish stop existing.

Cost-balance the residual non-determinism. Where a node still has a choice, engineer the alternatives to cost the same. The paper’s example: after a timeout a node may legitimately send either the sender’s command or a senderTO timeout message — so senderTO is padded “to always be of the length of the largest possible command so that lying would not allow a node to save bandwidth.” Similarly, a list of up-to-date nodes is transmitted as an n-bit vector rather than a variable-length list, “so that the sender saves no network bandwidth by sending incomplete information.” This is the purest possible mechanism-design move: make the honest action weakly dominant by flattening the payoff differences that made dishonesty attractive.

Enforce predictable communication with local tit-for-tat. All communication goes through message queues. A queue from x to y interleaves outbound messages with bubbles — placeholders for messages x expects from y, each guarded by a predicate. x cannot send past a bubble until a message from y satisfying that predicate fills it. Combined with quorums of size n − f − 1, this gives a rational node a concrete reason to send: if r withholds a message from s, then s ignores r thereafter; in the worst case f Byzantine nodes also refuse to talk to r, and r can no longer assemble a quorum during its own turn as sender. It is excluded from the service. Since the service is assumed to be worth far more than a message, sending is rational. This is Tit for Tat implemented as a socket-level data structure — and, exactly like the tournament version, its purpose is to make defection carry a future cost inside a repeated game.

Penance for untimeliness. Timing-based non-determinism is not covered by the above, so each node maintains an untimely vector; when it becomes sender it publishes that vector, and every indicted node must send a penance message — deliberately expensive make-work — to every non-sender before it can continue using the system. Three constraints are stated on the penance design: the expected benefit of being late must be less than the expected penance cost; the sender is excused from receiving penances so it is not punished for reporting truthfully; and the spurious work Byzantine nodes can induce via false accusations is bounded. That middle constraint is a textbook incentive-compatibility patch — do not tax the reporter.

Rotate the leader. Traditional state machines have a client send its command to a leader, “but a rational sender would have no incentive to act on a remote client’s wishes.” BAR rotates the sender role round-robin so that every node’s participation buys it a periodic right to propose. Participation is priced in future proposal rights.

And the extra node. The BART state machine needs 3f + 2 replicas, not 3f + 1 — equivalently, at most (n − 2)/3 nodes may be Byzantine. The reason is a conflict of interest, not a fault-tolerance argument: if sender s of instance i is slow and a new leader must finish the instance, every node except s wants a timely conclusion, while s wants its own value adopted rather than the default and “can take steps that compromise liveness.” The extra node lets the protocol exclude s from the steps that complete its own instance. Recall Halpern and Vilaça’s n ≥ f + 2 against the classical n ≥ f + 1. In both cases the price of turning a correctness property into an equilibrium property is exactly one more node, spent on removing a participant from a decision in which it has a stake. That recurrence is the strongest evidence that the game framing is doing real work rather than decorating.

flowchart TB
    subgraph DEV["Deviations a rational node might attempt"]
        D1["Send wrong data"]
        D2["Send nothing"]
        D3["Exploit a legal<br/>non-deterministic choice"]
        D4["Be late"]
        D5["Ignore a remote<br/>client's request"]
    end
    subgraph MECH["BAR countermeasure"]
        M1["POM: self-contained<br/>signed confession"]
        M2["Message-queue bubbles:<br/>local tit-for-tat exclusion"]
        M3["Limit non-determinism (TRB)<br/>+ cost balancing"]
        M4["Penance: mandatory<br/>make-work"]
        M5["Round-robin sender:<br/>participation buys<br/>proposal rights"]
    end
    D1 --> M1
    D2 --> M2
    D3 --> M3
    D4 --> M4
    D5 --> M5
    M1 & M2 & M3 & M4 & M5 --> OUT["Following the protocol<br/>is a best response<br/>=> IC-BFT"]

What it shows and the insight to take: each profitable deviation mapped to the mechanism that prices it out. The insight is the ordering of difficulty, which is the opposite of intuition: lying is the easy attack to defeat (signatures make it provable), silence and legal-but-lazy choices are the hard ones (nothing to prove), and every one of BAR’s non-obvious design decisions exists to handle the hard cases rather than the dramatic one.

The follow-on system, BAR Gossip (Li et al., OSDI 2006), applies the same playbook to peer-to-peer streaming: verifiable pseudo-random partner selection removes the choice of whom to gossip with (limiting non-determinism again), a Balanced Exchange protocol makes each trade incentive-compatible by construction, and an Optimistic Push protocol acts as a safety net for chunks that balanced trading cannot place. Reported results: over 99% convergence with all clients selfish and non-colluding, over 95% with 40% colluding, and over 93% with 20% Byzantine.

Rereading 3f + 1: Where the Analogy Holds and Where It Breaks

The Games and Strategic Systems in C MOC proposes reading the 3f + 1 bound as “a statement about which games are winnable.” That framing is partly right, and it is worth being precise about which part, because the sloppy version is exactly the kind of confident-but-wrong claim this vault is meant to avoid.

What the classical bound actually is. n > 3m (Lamport, Shostak & Pease 1982) is a theorem about the existence of a protocol satisfying two logical predicates (IC1 agreement, IC2 validity) against an unconstrained adversary. There is no utility function anywhere in the statement, no notion of “better off,” and therefore nothing an equilibrium concept can attach to. Likewise FLP — “every protocol for this problem has the possibility of nontermination, even with only one faulty process” — is a statement about adversarial scheduling in an asynchronous model. The scheduler in FLP is not a player; it is a quantifier. Calling either of these an “equilibrium result” is a category error, and the vault’s FLP Impossibility Result and The Byzantine Generals Problem notes should be read as the primary statements.

Where the game framing gives a genuinely different bound. Abraham, Dolev and Halpern define (k, t)-robustness, which combines two independent generalisations of Nash equilibrium (Abraham, Dolev & Halpern 2007; survey in Abraham, Alvisi & Halpern 2011):

• k-resilience: no coalition of at most k players can all do better by jointly deviating. Nash equilibrium is the k = 1 case. Their Example 1 shows the gap: n players each choose 0 or 1; all-zeros pays everyone 1; if exactly two play 1 those two get 2 and everyone else gets 0; otherwise everyone gets 0. All-zeros is a Nash equilibrium — a lone deviator drops everyone to 0 including itself — but it is not 2-resilient, because a pair gains.
• t-immunity: the non-deviating players are not made worse off by arbitrary, possibly coordinated behaviour of up to t players. Their Example 2 shows this is a different axis: n players who all stay and bargain get 2 each, anyone who goes home gets 1, anyone who stays when not everyone stays gets 0. “Everyone stays” is k-resilient for every k < n — it is the best possible outcome — and yet it is not even 1-immune, because a single unexplained departure zeroes everyone.

(k, t)-robustness requires both, simultaneously and jointly: no coalition of k can all gain, no matter which t players are strange and what they do, even if the k + t of them pool their private information. Nash equilibrium is (1, 0)-robustness. And the headline bound is:

Theorem 1(a). If 3(k + t) < n, then any (k, t)-robust equilibrium of a game with a mediator can be implemented by cheap talk (in O(c) rounds for a mediator of circuit depth c). Theorem 2. If 2k + 3t < n ≤ 3k + 3t, there is a game and a strongly (k, t)-robust mediator equilibrium with a (k + t)-punishment strategy for which no bounded-round cheap-talk implementation exists.

Set k = 1 (no coalitions) and t = f: the condition becomes n > 3f + 3. The shape is the same as n > 3f, and the mechanism of the proof descends from the same indistinguishability arguments — but the constant is different and the variable is different, because k is a quantity classical BFT has no name for. Byzantine fault tolerance counts faulty nodes; (k, t)-robustness counts faulty nodes plus colluding rational nodes, and charges three of each. That is a real generalisation, not a relabelling. It also explains BAR’s otherwise-odd assumption that “rational nodes do not collude — colluding nodes are classified as Byzantine”: that assumption is precisely the choice to set k = 1 and fold all coalition risk into t.

Where the analogy breaks outright. The same survey supplies the counterexample, and it is devastating for naive optimism. Consider a system that must run a consensus protocol, where communication costs something and the functionality is worth something. Is there a nontrivial (1, 1)-robust equilibrium in which the functionality is attained? No — for any n. The argument is two lines: any protocol that attains the functionality must send some first message, say from i to j; let j be the single strange player who never communicates with anyone; then i strictly gains by never messaging j (its outcome is unchanged, its bandwidth bill is lower); so the profile is not (1, 1)-robust. “The problem here is that (k, t)-robustness guarantees k-resilience irrespective of the actions of the t Byzantine players… it will be hard to achieve if, for example, communication is not free.”

This is why real BAR systems do not claim (k, t)-robustness. They use the weaker maximin posture: BAR assumes rational nodes “are conservative when computing the impact of Byzantine nodes on their utility” — each rational node assumes f Byzantine nodes are present and behaving in the way that minimises its utility, and best-responds to that worst case. The survey names this explicitly: “Aiyer et al. use the latter approach. Effectively, they are modeling Byzantine behavior as responding to any given candidate rational strategy with a behavior that minimizes the rational players’ payoff.” The cost of that move is stated just as plainly: “If the Byzantine players do play an unanticipated strategy, then the strategy used by the rational players may be painfully far from a best response.”

Concept	What it quantifies over	Consensus analogue	Honest verdict
n > 3f (BFT)	Protocols vs unconstrained adversary	The classical bound	Not an equilibrium statement at all
FLP	Adversarial schedules, async	Termination impossibility	Not an equilibrium statement at all
Nash = (1,0)-robust	Unilateral deviation	“Nobody alone gains by lying”	Too weak: ignores coalitions and faults
k-resilient	Coalitions up to k	Colluding validators / mining pools	Often does not exist for k ≥ 2
t-immune	Arbitrary behaviour of t	Byzantine nodes	The direct game-theoretic import of BFT
(k, t)-robust, 3(k+t) < n	Both, jointly	The strong reread of 3f + 1	Real generalisation; usually unachievable when messages cost
Maximin / IC-BFT	Best response to worst-case f	What BAR actually delivers	Achievable; guarantee is conditional on the Byzantine model

What it shows and the insight to take: the ladder from the weakest to the strongest solution concept, with the classical distributed-computing results deliberately marked as not belonging on it. The insight is that the honest sentence is not “3f + 1 is an equilibrium condition” but “there is a bound with the same three-fold structure, 3(k + t) < n, which strictly generalises 3f + 1 by charging for coalitions as well as faults — and it is usually too strong to implement, so deployed systems settle for maximin.”

Blockchains: Where the Incentives Became Load-Bearing

BAR was an academic model built for dorm-room backup services. Permissionless blockchains made the same model unavoidable at scale, because they replaced the membership assumption with an incentive assumption. The Bitcoin whitepaper states the incentive-compatibility claim informally in §6: a greedy attacker with more CPU power than all honest nodes combined “ought to find it more profitable to play by the rules, such rules that favour him with more new coins than everyone else combined, than to undermine the system and the validity of his own wealth” (Nakamoto 2008). That sentence is a game-theoretic assertion with no proof attached, and it turned out to be false — not because the majority attack analysis is wrong, but because it analysed the wrong deviation.

Selfish mining: the honest protocol is not an equilibrium

Eyal and Sirer’s Selfish-Mine (arXiv:1311.0243v5) is a strategy in which a colluding pool withholds discovered blocks and reveals them strategically, forcing honest miners to waste work on a branch that will be orphaned. The strategy depends only on the difference in length between the pool’s private chain and the public chain, which makes it a small state machine over the pool’s lead.

stateDiagram-v2
    [*] --> S0
    S0 : lead 0 — no private branch
    S1 : lead 1 — one block withheld
    S2 : lead 2
    S3 : lead 3 or more
    S0p : state 0-prime — tie, two public branches of length 1
    S0 --> S1 : pool mines (freq a)
    S1 --> S2 : pool mines (freq a)
    S2 --> S3 : pool mines (freq a)
    S3 --> S2 : others mine (freq 1-a)
    S1 --> S0p : others mine (freq 1-a); pool publishes its 1 block
    S2 --> S0 : others mine (freq 1-a); pool publishes all and wins 2
    S0p --> S0 : pool extends private branch (freq a); pool wins 2
    S0p --> S0 : others extend POOL branch (freq g(1-a)); pool wins 1
    S0p --> S0 : others extend PUBLIC branch (freq (1-g)(1-a)); pool wins 0

What it shows and the insight to take: the Markov chain over the selfish pool’s lead, transcribed from the state machine in Eyal & Sirer’s Figure 1 and their Algorithm 1. In the diagram a stands for α, the pool’s fraction of total mining power, and g for γ, the fraction of honest miners who, in a tie, build on the pool’s block rather than the honest one (plain letters are used because mermaid state labels do not reliably render Greek). The insight is that all of the strategy’s profit is concentrated in state 0' — the deliberately manufactured tie — and the payoff there is governed entirely by γ, a network propagation parameter, not a protocol parameter. The attack is an attack on message ordering, monetised.

Solving the chain gives the pool’s revenue share, and the profitability condition (their Observation 1) is:

(1 − γ) / (3 − 2γ)  <  α  <  1/2

Walking the symbols: α is the pool’s share of hash power; γ ∈ [0, 1] is the share of honest miners that adopt the pool’s block in a tie; the left-hand expression is the threshold above which selfish mining out-earns honest mining. Read off the three cases the paper states:

γ (tie-breaking)	Threshold α	Meaning
0	1/3	Honest miners always hear the honest block first — the best case, and the upper bound on the threshold for any γ
1/2	1/4	Ties broken uniformly at random
→ 1	→ 0	Pool wins every race to propagate — a pool of any size profits

The paper’s claim about deployed Bitcoin is the alarming one: “the current Bitcoin protocol has γ → 1, and therefore a threshold of almost zero,” because a well-connected pool that has pre-positioned its block can flood it the instant an honest block appears. Their proposed fix is a protocol change with no consensus-rule impact — on hearing of competing branches of the same length, propagate all of them and choose which to mine on uniformly at random — which pins γ = 1/2 and so raises the threshold to 1/4. They note the fix is backwards-compatible and progressive: any fraction of miners adopting it lowers γ and raises the threshold.

Uncertain

Verify: whether Bitcoin Core today implements the uniform random tie-break, and what γ is in the current network. Reason: the γ → 1 claim is dated November 2013 (arXiv v5) and describes a network whose relay topology (compact blocks, FIBRE, Erlay) has changed substantially since; I did not fetch any current Bitcoin Core source or measurement study during this research. To resolve: read the current src/validation.cpp chain-tip selection logic on a pinned Bitcoin Core tag and a recent block-propagation measurement paper. The mathematics above (the threshold formula and the three γ cases) is verified directly against the paper and is not in doubt; only its present-day applicability is.

Note also that the task framing “the honest protocol is not an equilibrium above ~1/3 hash power” understates the result. 1/3 is the threshold in the most favourable case, γ = 0; the paper’s whole point is that the real threshold is lower and, under its network assumptions, near zero.

The Miner’s Dilemma: a genuine Prisoner’s Dilemma inside consensus

The follow-up, Eyal’s The Miner’s Dilemma (arXiv:1411.7099), analyses open mining pools infiltrating one another via block withholding — sending partial proofs of work to a rival pool to collect a share of its revenue while discarding any full proofs, so the rival’s payout per member drops. The results, in the paper’s own words: “With any number of pools, no-pool-attacks is not a Nash equilibrium. With two pools, or any number of identical pools, there exists an equilibrium that constitutes a tragedy of the commons where the pools attack one another and all earn less than they would have if none had attacked. For two pools, the decision whether or not to attack is the miner’s dilemma, an instance of the iterative prisoner’s dilemma.”

This is the cleanest link in the vault between The Prisoner’s Dilemma and a production consensus system, and it also connects to Iterated Games and the Shadow of the Future: the paper observes that the game “is played daily by the active Bitcoin pools, which apparently choose not to attack” — cooperation sustained by repetition and reputation exactly as in Tit for Tat, and exactly as fragile.

Slashing: mechanism design as a consensus rule

Proof-of-stake protocols took the opposite route — instead of hoping the equilibrium holds, they price the deviation directly. Casper the Friendly Finality Gadget (Buterin & Griffith 2017) defines two slashing conditions, and its central property is accountable safety: “two conflicting checkpoints cannot both be finalized unless ≥ 1/3 of validators violate a slashing condition (meaning at least one third of the total deposit is lost).” A violation is a self-contained on-chain proof — “the evidence of the violation can be included into the blockchain as a transaction, at which point the validator’s entire deposit is taken away with a small ‘finder’s fee’ given to the submitter.”

That is BAR’s Proof Of Misbehavior with a bond attached, and it is worth naming the correspondence precisely, because it is the same mechanism twice:

	BAR (2005)	Casper FFG (2017)
Evidence object	Proof Of Misbehavior (POM): two contradictory signed messages	Slashable evidence: two conflicting votes
Punishment	Eviction, badlist, external sanction	Entire staked deposit destroyed
Reporter incentive	Sender is excused from penances it reports	Finder’s fee to the submitter
Safety framing	Safety holds if ≤ (n−2)/3 Byzantine	Accountable safety: conflict ⟹ ≥ 1/3 of stake slashed

The conceptual move both make is the same: convert an unattributable protocol violation into an attributable, provable, and priced one. Everything else in incentive-aware consensus is a variation on making deviations visible.

Uncertain

Verify: how faithfully Ethereum’s deployed consensus layer (Gasper) implements the two slashing conditions as stated in the 2017 Casper FFG paper. Reason: the paper predates the merged Ethereum beacon chain by years and explicitly describes itself as a finality gadget over a proof-of-work proposal mechanism; the shipped design differs. To resolve: read the current consensus-specs phase0/beacon-chain.md slashing sections against the paper. The claims above are attributed to the 2017 paper only.

Failure Modes and Gotchas

The trivial equilibrium is always there, and it is silence. Every incentive analysis of a message-passing protocol has a Nash equilibrium in which nobody sends anything. The survey states it flatly: “There is a trivial equilibrium: no one sends any messages. Clearly this is an equilibrium. No rational player is motivated to send a message if no one else is going to send a message” (Abraham, Alvisi & Halpern 2011). Amoussou-Guenou et al. prove the consensus-specific version for committee-based blockchains: Proposition 2 — “When f < ν and n − f ≥ ν, there exists a Nash equilibrium in which rational players never check blocks’ validity nor send messages, so that no block is ever accepted” (arXiv:1902.07895), where ν is the majority threshold. This is a coordination failure in the technical sense: safety holds vacuously, liveness dies, and no participant is doing anything wrong. Any claim that “protocol X is a Nash equilibrium” is nearly worthless without also stating that the silent equilibrium has been excluded or made unattractive.

The pivotality trap. The same paper’s Proposition 1 is a subtler and more disturbing result: when f ≥ ν, there is an equilibrium in which rational validators propose valid blocks but do not check the blocks they vote on. The reasoning is that a rational validator recognises it is not pivotal — if the block is invalid the Byzantine players will carry it anyway, and if it is valid the other rational players will — so paying the verification cost c_check buys nothing. This is the consensus analogue of rational ignorance in voting, and it means a protocol can satisfy every safety property on paper while the validation that gives those properties their meaning is not actually happening.

Utility functions are assumptions, and unstated ones are bugs. The BAR paper is explicit that its results depend on four technical assumptions about rational nodes: long-term benefit from participation; conservatism about Byzantine impact (each node best-responds to the worst case); acceptance of Nash equilibrium as a behavioural prediction; and no collusion — “colluding nodes are classified as Byzantine.” Drop the last and you have moved from k = 1 to k > 1, where k-resilient equilibria frequently do not exist at all. Drop the first — say, a node near the end of its participation horizon — and every threat-based mechanism in the protocol becomes an empty threat.

The equilibrium can be worse than the correct protocol. “There is no reason for an equilibrium to be a good outcome.” Real BAR systems pay for their guarantees in ways operators notice: BAR-Backup, BAR Gossip and Equicast “do not allow dynamic membership, require nodes to waste network bandwidth by sending garbage data to balance bandwidth consumption, and provide little flexibility to adapt to changing system conditions.” The cost-balancing principle literally means transmitting padding, and the reported BART state machine throughput was 15 request batches per second — orders of magnitude below what a non-incentive-aware BFT engine of the same era achieved. This is The Price of Anarchy paid in advance, as a deliberate design cost.

A propagation parameter can be the whole security argument. Selfish mining’s threshold is governed by γ, which is not in any consensus rule — it is an emergent property of network topology and relay software. A protocol can be secure in its specification and insecure in its deployment because someone improved their peering. Any incentive claim that quietly assumes uniform propagation should be treated as unverified.

Silence is the attack that cryptography does not close. Both BAR and Halpern–Vilaça converge on the same hardest case from opposite directions: BAR’s “he said/she said” problem about a message that was never sent, and Halpern–Vilaça’s proof that the profitable deviation is pretending not to have received. Signatures make lying about content provable; nothing makes an omission provable. Every practical answer — message-queue bubbles, penances, timeouts, slashing for inactivity — is a statistical or punitive substitute, never a proof.

Alternatives and When to Choose Them

Model	Assumes	Buys you	Choose when
Classical BFT (Practical Byzantine Fault Tolerance)	Non-faulty ⟹ altruistic; n ≥ 3f+1	Simplest reasoning, best performance	One administrative domain — your own replicas, your own operators
BAR / IC-BFT	Rational majority with known utility, no collusion; n ≥ 3f+2	Guarantees that survive selfishness	Multiple administrative domains, closed membership, strong identities
BART (weaker BAR)	Same, but only that deviations are harmless	Achievable without enumerating every deviation	You cannot bound the deviation space but can bound its damage
(k,t)-robustness	Coalitions up to k, arbitrary t; 3(k+t) < n	Strongest guarantee; no regrets even if Byzantine identities leak	Theory, and settings where communication is genuinely free
π-Nash (Halpern–Vilaça)	A known distribution over failure patterns; f+1 < n	Equilibrium where ex post equilibrium provably cannot exist	You have real failure statistics for your fleet
Cryptoeconomic / slashing	Participants hold a bond worth more than the attack	Attributable, priced deviations without membership control	Open membership; no way to know who anyone is

The decision is essentially about what you can assume about membership. Classical BFT assumes you own the nodes. BAR assumes you can identify them (its threat model explicitly rules out Sybil attacks by requiring identities “expensive to obtain,” and the paper says outright: “We do not target open membership peer-to-peer systems”). Cryptoeconomics assumes you cannot identify anyone and therefore prices behaviour with capital instead. Choosing a model you cannot justify — running PBFT across parties who do not trust each other, and calling the non-faulty ones “correct” — is the single most common error the game framing exposes.

Production Notes

Concrete measured results from the primary sources, with their as-of dates:

• BAR-B (SOSP 2005). The BART replicated state machine “executes batches of 15 requests per second,” and the BAR-B cooperative backup service “can back up 100 MB of data to 10 nodes in under 4 minutes while guaranteeing data recovery despite the failure of 3 nodes.” Quorums are n − f − 1 in the base protocol, reduced to ⌈(n+f)/2⌉ once the badlist mechanism converts local suspicion into globally agreed proofs of misbehaviour.
• BAR Gossip (OSDI 2006). Over 99% convergence for broadcast updates with all clients selfish and non-colluding; over 95% with up to 40% colluding; over 93% with 20% Byzantine (Li et al. 2006).
• Selfish mining (FC 2014 / arXiv 2013). Verified by the authors against a simulator of 1,000 miners at identical rates, with a subset of 1000α acting as the pool. The context in the paper is a network “at over 42 × 10¹⁸ FLOPS” with “a total market capitalization around 1.5 billion US Dollars as of October 2013” — worth quoting because it dates the deployment claims precisely.
• Miner’s Dilemma (2014). The paper’s most useful production observation is behavioural, not mathematical: the pool-attack game “is played daily by the active Bitcoin pools, which apparently choose not to attack.” An equilibrium prediction and observed behaviour diverging is a data point about the model, not about the operators.

The recurring engineering lesson across all four is that incentive-aware consensus buys its guarantees with throughput and flexibility, and it does so for a class of failure that classical BFT does not even name. If your replicas are in your own racks, that is a bad trade. If they are on strangers’ machines, the classical guarantees were never true in the first place.

Uncertain

Verify: whether any widely deployed production system today advertises IC-BFT or BART guarantees. Reason: BAR-B, BAR Gossip and Equicast are research prototypes; the survey (Abraham, Alvisi & Halpern 2011) lists exactly these three as its examples and notes their operational limitations, and I found no primary engineering write-up of a shipped BAR-model system during this research. Modern proof-of-stake systems use the related but distinct cryptoeconomic approach (bonds and slashing) rather than the BAR model’s identity-and-sanction approach. To resolve: a survey of production BFT deployments’ stated fault models.

See Also

• Games and Strategic Systems in C MOC — the parent MOC; this note is the P8 rung that rereads the vault’s own systems as games
• The Byzantine Generals Problem — the 3f + 1 bound in its original, non-game-theoretic form; read it first
• Practical Byzantine Fault Tolerance — the protocol BAR’s state machine is a modified version of
• Consensus in Databases with Raft and Paxos — the crash-fault setting Halpern & Vilaça analyse
• FLP Impossibility Result — the impossibility that is not an equilibrium statement, and why that distinction matters
• Nash Equilibrium — the solution concept (1, 0)-robustness specialises to
• Correlated Equilibrium — arguably the right concept for a protocol issued by an external authority
• The Prisoner’s Dilemma and Tit for Tat — the miner’s dilemma is an instance of the first; BAR’s message queues implement the second
• Iterated Games and the Shadow of the Future — why long-term participation makes BAR’s threats credible
• Mechanism Design and Incentive Compatibility — the vocabulary BAR’s design principles instantiate
• The Price of Anarchy — the efficiency loss BAR pays up front in padding and throughput
• Congestion Control as a Game — the sibling P8 note where a selfish sender’s incentives point the wrong way
• Security as an Adversarial Game — the sibling P8 note on the limits of the adversarial framing
• Distributed Systems MOC