Traitors, Pass-the-Phone

Setup: enter names in seating order and pick one or two traitors. The phone secretly chooses the commander and the traitors. The commander may be a traitor too, and traitors are told who their fellow traitor is.

One private turn each. The commander goes first. A loyal commander picks one order for everyone, and a traitor commander can send each lieutenant a different one. Then each lieutenant, in turn, sees what the commander told them and passes it on to every other lieutenant. Loyal lieutenants relay honestly and automatically. Traitors can claim anything, and something different to each person. This is Lamport's Oral Messages algorithm with one round of relays, OM(1).

Nobody chooses their action. Each loyal lieutenant follows the majority of the orders they heard (ties mean retreat). That's the point: the question isn't whether you can out-think the traitor, but whether any fixed rule can survive them.

The reveal: every message drawn as an arrow, lies marked, each loyal lieutenant's inbox, and the verdict. The phone keeps a running tally of loyal wins by player count, so the 3-player vs 4-player difference shows up over a few games.

Bots: tap human next to a seat to hand it to the phone. Bots move without a pass screen, so nobody learns anything from their turn. A loyal bot follows the protocol like any loyal player. A traitor bot plays perfectly: it tries every combination of messages it could send (or 4,096 random ones in the largest sealed games), assumes any traitor still to move will help, and picks a combination that beats the loyal side, if one exists. Set traitors can be to bots only and the humans are all on the same side, against the machine.

Watch bots play needs no people at all. It deals game after game at 3 and at 4 generals with a perfect traitor. At 3, the traitor wins about a third of the time. At 4, it searches every lie in every game and never finds one that works. That's the theorem, one game at a time.

Sealed orders: switch orders are to sealed. Now every order carries the commander's seal, and each lieutenant adds their own when they relay it. Nobody can forge a seal, so a traitor lieutenant can only pass the sealed order on or withhold it. A traitor commander can seal both orders, or neither, for anyone, and shares those seals with a fellow traitor. Loyal lieutenants relay every new sealed order they get, one extra round per traitor. At the end, a loyal general holding one order follows it. One holding both orders has proof that the commander lied, and retreats, and so does one holding none. This is Lamport's Signed Messages algorithm, SM(m).

With seals, 3 players and 1 traitor stops being a losing game. The trick that beat spoken orders was a lieutenant claiming "the commander told me retreat". Now that claim has to come with the commander's seal on it, and the traitor doesn't have one. In the game, traitors act only in the relay round. That keeps it to one turn each without changing the result: SM(m) is proven to hold even against traitors who act in any round.

Here is the whole proof that three generals can't beat one traitor. Put yourself in the shoes of lieutenant L1, circled below, in two different situations.

Why must L2 retreat in B? From L2's side, B looks exactly like a third situation: a loyal commander ordering retreat, with L1 as a traitor who claims the order was attack. In that situation L2 must obey the commander, and retreat. L2 can't tell the two apart either, so L2 retreats in B too. That forces L1's hand.

So with three generals, every possible rule loses somewhere. In this game the rule is majority, ties to retreat, and it loses in situation A. That's exactly the case the bots keep finding: a loyal commander ordering attack, and a traitor lieutenant muttering "retreat".

More traitors. Now suppose there are f traitors and only 3f generals. Split the generals into three teams of at most f each and let each team play one of the three roles above. One whole team can be traitors, so the three-general trap applies to the teams. That's why you need at least 3f + 1 generals to survive f traitors: 4 for one traitor, 7 for two. You also need f relay rounds on top of the commander's own messages. Fischer and Lynch proved you can't do it in fewer.

What the seals change. Situation A depends on L2 being able to say "the commander told me retreat" without proof. With sealed orders, a claim needs the commander's seal on it, and L2 doesn't have one for retreat. In B, the traitor commander's two contradictory seals end up in everyone's hands, and that's evidence against the commander, not against L2. The two situations stop looking alike, and the bound drops from 3f + 1 generals to any number of traitors, given f relay rounds. Real systems use digital signatures as the seals.

Flight computers

The problem was invented for aircraft. SRI's SIFT project, funded by NASA in the late 1970s, asked how many computers you need to fly a plane when one of them might fail in the worst way possible. Worst case isn't a computer that crashes. It's one that tells different neighbours different things. That sounds paranoid until you see how it happens: a sensor or bus signal sitting right at the threshold between 0 and 1 gets read as 0 by some receivers and 1 by others. Driscoll and colleagues at Honeywell collected real cases of this in avionics hardware.

The Boeing 777's primary flight control system has three primary flight computers. Each one has three lanes, and each lane uses a different processor: an Intel 80486, a Motorola 68040, and an AMD 29050. Nine computers in all, "triple-triple". Inside each computer the lanes check each other, and the three computers' outputs are combined by taking the middle value, so a lane or computer that goes wrong gets outvoted and cut out. The dissimilar processors guard against the other lesson from the Vote exhibit: three copies of the same bug are one bug.

Blockchains

Byzantine agreement has always needed a fixed list of who's voting. 3f + 1 counts identities. On the open internet, identities are free, so one attacker can show up as a thousand generals and own any majority. That's a Sybil attack.

Bitcoin's 2008 paper got around this by not counting identities at all. Its vote is "one-CPU-one-vote": the longest chain of proof-of-work wins, so your say is proportional to the computing power you burn. Traitors are bounded by how much hardware they can pay for, not by how many names they can make up. The cost is that agreement is only ever probable, getting more certain with every block, never final the way a Byzantine protocol is.

Proof-of-stake chains went back to the classic protocol and weighted the votes. Ethereum, Cosmos and similar systems finalize a block when validators holding more than two-thirds of the stake sign it. That's 3f + 1, counted in money instead of generals, with digital signatures as the seals.