14 · Distributed Trust

This is Part II's sixth hearing: computation has spent forty years proving, formally, exactly how much agreement strangers with no shared authority can and cannot reach — and philosophy's social contract is called to answer for what it left out.

Can computers settle what philosophers only argued — how strangers cooperate?

On 3 January 2009, a program mined the first block of a currency that no bank, state, or company controlled. Embedded in that block was a string of text: "The Times 03/Jan/2009 Chancellor on brink of second bailout for banks" — the front-page headline of that day's London Times, quoting the news that the UK government was about to bail out its banking system a second time (Bitcoin Wiki, "Genesis block"). The line proved the block could not have been mined earlier, but it did more than timestamp; it dated the system's birth to the exact week the institutions trust is normally outsourced to had just failed in public. The paper behind it, "Bitcoin: A Peer-to-Peer Electronic Cash System," had been posted to a cryptography mailing list on 31 October 2008 under the name Satoshi Nakamoto — a name nobody has ever conclusively attached to a person. A system built explicitly so that strangers need not trust one another was written by someone none of us can authenticate by any of the ordinary means. That irony is this chapter's opening exhibit.

The social contract has an executable version, and it begins from the same premise the original did. Thomas Hobbes argued in Leviathan (1651) that without an authority capable of enforcing it, agreement among equals is unstable — the state of nature is "a war of all against all," and peace requires transferring judgment to a sovereign strong enough to compel it. Distributed computing's answer, worked out three centuries later, keeps the peace without a sovereign: Leslie Lamport's Paxos ("The Part-Time Parliament," ACM Transactions on Computer Systems, May 1998) and Diego Ongaro and John Ousterhout's Raft ("In Search of an Understandable Consensus Algorithm," USENIX ATC 2014) let any majority of equal replicas bind a decision, tolerating the minority being slow, wrong, or offline. Where Hobbes solved coordination by concentrating judgment in one place, these protocols solve it by counting votes among peers — a social contract that needs a quorum and a clock, never a Leviathan.

Testimony gets harder when a witness may be lying rather than merely mistaken. Leslie Lamport, Robert Shostak, and Marshall Pease posed that sharper version in 1982: generals surrounding a city must reach unanimous agreement — attack or retreat — communicating only by messenger, when some generals or their messages may be actively treacherous. Their result: with unsigned, oral messages, no protocol works unless more than two-thirds of the generals are loyal; among just three participants, a single traitor already defeats two honest ones (Lamport, Shostak & Pease, "The Byzantine Generals Problem," ACM TOPLAS 4, no. 3, July 1982: 382–401). Philosophy's testimony debates — how much a report should be discounted, knowing some sources may be adversarial rather than merely unreliable — get an exact numerical threshold: one-third.

Agreeing on a plan is one thing; agreeing that you have both agreed is another, and it is provably out of reach. In 1975, Akkoyunlu, Ekanadham, and Huber proved that two parties coordinating over a channel that can silently drop messages can never become certain, after any finite exchange, that both sides know the plan is on — any acknowledgment could itself be the message that is lost. Jim Gray gave the result its familiar military name, the Two Generals Problem, in 1978. This is the philosophical structure of common knowledge — I know P, you know P, I know you know P, without end — which David Lewis had formalized in Convention (1969); Joseph Halpern and Yoram Moses gave it a distributed-computing treatment, proving that true common knowledge is unreachable over any channel with even a small chance of failure, and that only finite, nested approximations are ("Knowledge and Common Knowledge in a Distributed Environment," 1984; expanded Journal of the ACM 37, no. 3, 1990). Epistemic logic, usually a philosopher's diagram of nested belief, becomes a protocol with a proven ceiling.

A digital signature lets any stranger verify who a message came from without a shared secret or a vouching intermediary: trust becomes a mathematical relation — only one private key produces what a matching public key can confirm — rather than a social one requiring a notary, a bank, or a state. A ledger extends this from verifying one signature to verifying an entire ordered history, letting mutually suspicious parties agree on a single sequence of events without deferring to any one of them.

Money is where every piece of this machinery bears weight at once. Nakamoto's protocol makes the ledger itself the output of a Byzantine-fault-tolerant vote — proof-of-work — among anonymous, mutually distrustful participants, solving double-spending without the single trusted ledger-keeper Hobbes would have assumed was unavoidable. But philosophy objects here, not merely answers: the whole distributed-trust literature treats trust as solved once nodes agree on facts — which block is valid, whose signature is genuine. Older accounts of trust, including Hobbes's own worry about promises kept only under duress, hold that trust carries normative content no vote over present facts touches — reputation earned over years, forgiveness, the willingness to be vulnerable to someone else's future choice. A blockchain makes forgery costly. It does not make betrayal within the rules — a fraud run entirely inside a legitimate, signed ledger — visible to the protocol at all.

The people, briefly. Hobbes wrote Leviathan out of the English Civil War's chaos. Lamport received the 2013 ACM Turing Award for this and other foundational work in distributed computing, and by his own account wrote "The Part-Time Parliament" as an allegory of a fictional Greek parliament because reviewers found the direct version unreadable. Halpern and Moses built on Lewis's philosophical account of convention to give epistemic logic a computational home. Nakamoto has never been identified.

Connections

Chapter 03 asked whether a machine's answer counts as knowledge; Byzantine fault tolerance is that question with an exact fraction attached. Chapter 06's responsibility gaps recur here as blame distributed the same way trust is. Chapter 07's stack-versus-state tension sharpens once money itself no longer needs a state. Chapter 12's certainty-as-engineering-product reappears in the one-third threshold and the proven ceiling on common knowledge.

Open questions

If perfect common knowledge is provably unreachable over any unreliable channel, is ordinary human coordination — running on language and gesture, channels no more reliable — merely tolerating the same gap with a longer patience for uncertainty? Does a system that formally guarantees agreement on facts quietly redefine "trust" down to "agreement," discarding what the word carried for Hobbes? And if no one — not even a quorum — is identifiable behind a permissionless ledger, whose sovereignty has actually been replaced?

Go deeper

• Thomas Hobbes, Leviathan, 1651.
• Leslie Lamport, Robert Shostak & Marshall Pease, "The Byzantine Generals Problem," ACM Transactions on Programming Languages and Systems 4, no. 3 (July 1982): 382–401; Satoshi Nakamoto, "Bitcoin: A Peer-to-Peer Electronic Cash System," 31 October 2008 — bitcoin.org/bitcoin.pdf.
• Common Knowledge, Stanford Encyclopedia of Philosophy.