Distributed Systems Security experimental

Distributed Systems Security Consensus, Byzantine fault tolerance, clock and event-ordering attacks, and blockchain security, from Lamport's 1978 logical clocks through Paxos, Raft, and Practical Byzantine Fault Tolerance to Bitcoin and SUNDR, benchmarked against MIT's current 6.5840 and 6.852J, with Plan 9 and Inferno as a contrasting historical case study. Foundations: Fault Models and the Limits of Agreement. Crash faults versus Byzantine faults, and the Fischer-Lynch-Paterson impossibility result. Distinguish a crash (fail-stop) fault from a Byzantine fault and explain why the distinction determines what a distributed protocol must defend against. State the Fischer-Lynch-Paterson result, apply it to a proposed consensus design, and explain its practical implication for consensus protocol design. Distributed systems without shared memory or a shared clock, Crash faults versus Byzantine faults, Synchronous versus asynchronous system models, The Fischer-Lynch-Paterson (1985) impossibility result, Why an attacker's capability maps onto a fault model Two Different Kinds of Failure A distributed system has no shared memory and no shared clock. Every coordinating decision, whether two replicas agree on a value, whether a log entry is committed, whether a payment has cleared, has to be reached by exchanging messages over a network that can delay, drop, or reorder them. Before any of this course's protocols make sense, one distinction has to be fixed: what kind of failure is the protocol built to survive? A crash (fail-stop) fault is the simplest case. A process stops executing and sends nothing further. Other processes may notice its silence, but it never sends a message it should not have sent. A Byzantine fault, named after the Byzantine Generals problem this course studies in Module 2, is strictly worse. A Byzantine process can do anything: send different values to different peers, forge messages, stay silent selectively, or collude with other faulty processes. It is not merely broken, it is actively adversarial. This distinction is the organizing spine of the whole course. A protocol engineered only to tolerate crash faults, such as the Paxos and Raft algorithms studied next, provides no security guarantee once an attacker compromises a participant, because a compromised participant does not crash, it lies. The Limits of What Agreement Can Guarantee Even restricting attention to the easier, crash-only case, there is a hard mathematical limit on what any consensus protocol can promise. In 1985 Michael Fischer, Nancy Lynch, and Michael Paterson published "Impossibility of Distributed Consensus with One Faulty Process" in the Journal of the ACM. Their result, now known by the authors' initials as the Fischer-Lynch-Paterson (FLP) result, proves that in a purely asynchronous system, one with no bound on message delay or relative processing speed, no deterministic algorithm can guarantee that all correct processes reach consensus in bounded time if even a single process may crash. There always exists some adversarial scheduling of messages that can delay agreement forever. This is not a defect in any particular algorithm; it is a property of the asynchronous model itself. Real systems such as Paxos and Raft remain useful in practice because they add timeouts, leader election, and partial-synchrony assumptions, which make indefinite delay astronomically unlikely even though FLP guarantees it remains theoretically possible. Synchronous Versus Asynchronous Models A synchronous system assumes a known upper bound on message delay and processing speed; under that assumption, consensus tolerating even Byzantine faults is provably solvable. An asynchronous system makes no such assumption: a message that has not yet arrived is indistinguishable from one that never will. Every protocol in this course sits somewhere on this spectrum, and the CyBOK (Cyber Security Body of Knowledge) Distributed Systems Security knowledge area treats the choice of model as inseparable from the choice of what an attacker is assumed capable of (Suri, 2021). Why This Course Starts Here CyBOK frames Distributed Systems Security through two complementary perspectives: securing a distributed system's own coordination mechanisms against faulty or malicious participants, and using distribution itself as a security mechanism. Every module that follows is an instance of one or the other. Modules 1 and 2 secure coordination against crash and then Byzantine participants. Module 3 secures the ordering of events itself. Module 4 shows distribution used as a security mechanism twice over, once through Bitcoin's proof-of-work and once through the Secure Untrusted Data Repository (SUNDR)'s fork consistency. Module 5 closes with a historical contrast and a capstone that asks a simple question with real consequences: given a stated adversary, which mechanism actually applies? Related CCI capabilities Computer Architecture (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/computer-architecture/). Optics Primer Series (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/optics/). Maths Refresher Series, Finance (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/maths-finance/). System Dynamics (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/system-dynamics/). CCI Lab: Run it, build with it, read the thinking, reuse the data. (https://www.cambridgecyberinternational.com/en/insights/lab/) Consensus Algorithms: Paxos and Raft. Majority-quorum agreement among crash-fault processes, and why it does not defend against a lying replica. Explain how Paxos achieves agreement among crash-fault processes using a majority quorum, and construct a message-flow trace for a two-round Paxos instance. Explain why Raft was designed for understandability and how it separates leader election, log replication, and safety. Replicated state machines as the goal of consensus, Paxos: proposers, acceptors, learners, and the majority quorum, Raft: leader election, log replication, and safety, Why Raft was designed to be more understandable than Paxos, Consensus tolerates crashes, not lies Agreement Among Replicas That Only Crash The goal behind both algorithms in this module is a replicated state machine: several replicas that apply the same sequence of operations in the same order, so that each ends up in the same state even though some may crash along the way. If replicas agree on the order of operations, the system as a whole survives the loss of any minority of them. Paxos Leslie Lamport's Paxos, described accessibly in his 2001 paper "Paxos Made Simple," solves this through three logical roles: proposers suggest values, acceptors vote on them, and learners find out what was chosen. A value becomes chosen once a majority quorum of acceptors has accepted it, not all of them. The majority requirement is not an arbitrary design choice. Any two majority quorums drawn from the same total set of acceptors must overlap in at least one acceptor. That overlap is exactly what prevents two different values from both being chosen: whichever acceptor sits in both quorums cannot have voted for two different values, so at most one value can ever collect a majority. Raft Diego Ongaro and John Ousterhout published Raft, "In Search of an Understandable Consensus Algorithm," at the 2014 USENIX Annual Technical Conference, where a shorter version of the paper won a Best Paper Award. Raft is designed to be equivalent in fault tolerance and efficiency to multi-Paxos but structured so engineers can actually reason about it correctly. It separates the problem into three named sub-problems: leader election, log replication, and safety. The paper's own user study, forty-three students at two universities learning both algorithms, found that students answered questions about Raft correctly more often than equivalent questions about Paxos, evidence for the paper's central understandability claim. What Neither Algorithm Promises A five-replica Paxos or Raft cluster tolerates up to two crashes, since three of five still form a majority. Neither algorithm, in its standard form, tolerates a Byzantine replica. If a replica in either system is compromised and begins sending different, contradictory messages to different peers rather than simply going silent, the majority-quorum reasoning that makes both algorithms correct no longer holds. That is precisely the harder problem Module 2 takes up. Related CCI capabilities Computer Architecture (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/computer-architecture/). Optics Primer Series (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/optics/). Maths Refresher Series, Finance (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/maths-finance/). System Dynamics (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/system-dynamics/). CCI Lab: Run it, build with it, read the thinking, reuse the data. (https://www.cambridgecyberinternational.com/en/insights/lab/) Byzantine Fault Tolerance. The Byzantine Generals problem, its quorum bound, and Practical Byzantine Fault Tolerance. State the Byzantine Generals problem and the quorum bound required to tolerate f Byzantine participants. Explain how Practical Byzantine Fault Tolerance (PBFT) made Byzantine agreement practical for asynchronous networks, and compute the minimum quorum size for a given number of Byzantine-tolerant replicas. The Byzantine Generals problem (Lamport, Shostak, and Pease, 1982), The 3f+1 quorum bound for unsigned messages, Castro and Liskov's Practical Byzantine Fault Tolerance (1999), View changes and the primary/backup structure, PBFT's legacy in permissioned blockchain consensus The Byzantine Generals Problem In 1982, Leslie Lamport, Robert Shostak, and Marshall Pease published "The Byzantine Generals Problem" in ACM Transactions on Programming Languages and Systems. The paper poses the problem as several generals surrounding a city, who must agree on a common plan, attack or retreat, by exchanging messengers, when some generals, or the messengers themselves, may be traitors who deliver conflicting orders to different generals. The paper's central, quantitative result is a quorum bound. For the classic setting, oral (unsigned) messages, agreement tolerating f traitors among n generals is possible only if n is at least 3f + 1. A system that must tolerate three Byzantine participants therefore needs at least ten participants in total, not merely four. If messages can be digitally signed, the bound relaxes considerably: a traitor cannot forge a loyal general's signed statement, so agreement becomes possible against any number of traitors short of the full set. Making Byzantine Agreement Practical The Byzantine Generals result is a foundational proof, not an engineering blueprint. That gap was closed by Miguel Castro and Barbara Liskov's Practical Byzantine Fault Tolerance (PBFT), presented at the third USENIX Symposium on Operating Systems Design and Implementation (OSDI) in February 1999. PBFT was the first Byzantine-fault-tolerant state-machine-replication protocol efficient enough to run on an asynchronous network such as the internet, rather than requiring the strict synchrony assumptions earlier theoretical work had needed. PBFT organizes replicas around a primary and backups. Clients send requests to the primary, which proposes an ordering; backups exchange messages to confirm the ordering across a quorum before executing it. The standard configuration tolerating f Byzantine replicas requires at least 3f + 1 total replicas, the same bound the 1982 paper established. A view change mechanism lets the system replace a faulty or unresponsive primary and continue operating, rather than stalling indefinitely. From PBFT to Blockchain Consensus PBFT's quorum structure, a known, fixed set of replicas reaching deterministic finality once a quorum of correctly signed messages has been exchanged, maps directly onto a consortium of mutually distrusting organizations that need to validate a shared ledger. That structural fit is why PBFT-lineage protocols became an ancestor of consensus mechanisms used in permissioned blockchain platforms, where membership is known and bounded but no single organization is fully trusted. Module 4 contrasts this fixed-membership model with Bitcoin's open, unbounded, proof-of-work approach to the same underlying Byzantine agreement problem. Why This Is a Harder Problem Than Module 1's Paxos and Raft's majority-quorum reasoning depends on a faulty replica doing nothing worse than staying silent. A Byzantine replica can actively lie, sending one value to one peer and a different value to another. Detecting or outvoting deliberate deception, rather than merely tolerating silence, is what requires the larger 3f + 1 quorum and the additional message rounds that both the 1982 theoretical result and the 1999 practical protocol introduce. Related CCI capabilities Computer Architecture (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/computer-architecture/). Optics Primer Series (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/optics/). Maths Refresher Series, Finance (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/maths-finance/). System Dynamics (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/system-dynamics/). CCI Lab: Run it, build with it, read the thinking, reuse the data. (https://www.cambridgecyberinternational.com/en/insights/lab/) Time, Ordering, and Clock Attacks. Lamport's logical clocks and happens-before relation, and attacks on physical time synchronization. Apply Lamport's happens-before relation and logical clocks to order a small set of concurrent events, and explain why they let a distributed system order events without a shared physical clock. Describe how clock-synchronization protocols such as NTP can be attacked, and why event ordering is a distinct CyBOK-recognized attack surface. Lamport's 1978 logical clocks and the happens-before relation, Vector clocks as a refinement, The Network Time Protocol and why synchronized physical clocks are hard to secure, Clock-skew and NTP spoofing attacks, Event-ordering attacks in distributed logs and audit trails Ordering Events Without a Shared Clock In July 1978, Leslie Lamport published "Time, Clocks, and the Ordering of Events in a Distributed System" in Communications of the ACM. The paper defines the happens-before relation: event a happens before event b if both occur in the same process with a before b, or a is the sending of a message and b is its receipt, or the relation extends transitively across such steps. Two events that are not linked by happens-before are concurrent, and no absolute ordering between them exists or is needed. A Lamport logical clock assigns each event a counter. A process increments its own counter for each local event; when it sends a message it attaches its current counter value, and the receiving process sets its own counter to a value greater than both its prior value and the value carried in the message. This is enough to establish a consistent total order that respects happens-before, without any process ever consulting a shared physical clock. Vector clocks, a later refinement, extend this idea to distinguish events that are causally ordered from events that are merely concurrent, something a single Lamport counter cannot always do on its own. Physical Clocks Are a Different, Attackable Surface Logical clocks solve ordering inside the protocol itself. Physical time synchronization, needed for certificate expiry checks, time-based access tokens, and forensic log reconstruction, is a separate network service, most commonly the Network Time Protocol (NTP), and it is externally attackable in a way a purely logical clock is not. In 2016, Aanchal Malhotra, Isaac Cohen, Erik Brakke, and Sharon Goldberg published "Attacking the Network Time Protocol" at the Network and Distributed System Security Symposium. They showed that an on-path attacker who could intercept traffic to an NTP server could quickly shift a client's clock, and, more strikingly, that an off-path attacker, with no privileged network position at all, could disable a client's NTP synchronization using an extremely low-rate, single-packet attack. Because so much downstream security tooling silently assumes an accurate clock, a successful clock-skew attack can undermine certificate validation, expire or fail to expire access tokens incorrectly, and corrupt the perceived order of events in an audit trail. Event-Ordering Attacks as a Distinct Pillar CyBOK treats event-ordering manipulation as a security concern in its own right, distinct from confidentiality or availability. Reordering or manipulating the perceived sequence of events can conceal or misrepresent malicious actions in a log without ever disclosing data (a confidentiality breach) or blocking access to it (an availability breach). A forensic investigation, or a consensus protocol, that trusts a manipulated event order can reach an entirely wrong conclusion about what actually happened and when. Consensus protocols such as Raft address a narrower version of this same problem internally: a monotonically increasing term or epoch number lets replicas recognize and discard messages from a stale, already-superseded leader, functioning as a purpose-built logical clock for exactly one kind of event. This module's placement is deliberate. Manipulating time and event order is one concrete technique a Byzantine participant from Module 2 can use, and the blockchain systems covered in Module 4 depend heavily on ordering transactions into a single, agreed sequence without any trusted central clock at all. Related CCI capabilities Computer Architecture (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/computer-architecture/). Optics Primer Series (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/optics/). Maths Refresher Series, Finance (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/maths-finance/). System Dynamics (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/system-dynamics/). CCI Lab: Run it, build with it, read the thinking, reuse the data. (https://www.cambridgecyberinternational.com/en/insights/lab/) Peer-to-Peer Systems and Blockchain Security. Bitcoin's proof-of-work, Sybil and Eclipse and fifty-one-percent attacks, and SUNDR's fork consistency. Explain how Bitcoin's proof-of-work makes Sybil attacks costly rather than administratively prevented, compute the cost of a fifty-one-percent attack given a stated hash-rate distribution, and describe the Eclipse attack threat model. Explain how SUNDR's fork consistency lets a client detect a lying, untrusted server without trusting it, illustrating distribution as a security mechanism. Nakamoto's Bitcoin design and the double-spend problem, Proof-of-work as Sybil resistance, The fifty-one-percent attack, The Eclipse attack, SUNDR and fork consistency: distribution as a security mechanism Agreement Among Strangers Every mechanism studied so far assumes a known, fixed set of participants. Satoshi Nakamoto's 2008 paper "Bitcoin: A Peer-to-Peer Electronic Cash System" solves a harder version of the same underlying Byzantine agreement problem: reaching agreement on a shared transaction history among an open, unbounded set of mutually anonymous, unvetted participants, any of whom could be malicious, without any central clearinghouse. Bitcoin's answer is a proof-of-work blockchain. Transactions are broadcast peer-to-peer; the chain representing the greatest accumulated computational work is treated as the network's canonical history. Nodes may leave and rejoin at will, accepting the longest valid chain as proof of what happened while they were away. Proof-of-Work as Sybil Resistance In a 2002 paper at the first International Workshop on Peer-to-Peer Systems, John Douceur described the Sybil attack: an adversary who creates many fake identities to gain disproportionate influence over a system that assumes one identity equals one unit of trust. Bitcoin does not attempt to prevent Sybil attacks by vetting identities; it makes them pointless by tying influence to computational work rather than identity count. Creating a million fake identities provides no advantage without the proportional computation to back each one. Three Distinct Threat Models These three attacks are related but genuinely distinct, and each demands a different specific defense. A fifty-one-percent attack occurs when an entity or coalition controls a majority of the network's hash rate, in principle allowing it to rewrite recent blocks or double-spend, since the "honest majority" assumption underlying proof-of-work no longer holds. An Eclipse attack, described by Ethan Heilman, Alison Kendler, Aviv Zohar, and Sharon Goldberg at the 2015 USENIX Security Symposium, is narrower in scope but does not require anything like network-wide majority control: an attacker who controls enough Internet Protocol (IP) addresses can monopolize all of a single victim node's peer connections, isolating it from the honest network and enabling attacks such as double-spending against that one victim specifically. Distribution as a Security Mechanism: SUNDR Bitcoin uses distribution to reach agreement among strangers. Jinyuan Li, Maxwell Krohn, David Mazieres, and Dennis Shasha's Secure Untrusted Data Repository (SUNDR), presented at the Operating Systems Design and Implementation Symposium (OSDI) in 2004, uses distribution for a narrower but equally important purpose: letting a client detect that an untrusted server is lying, without ever needing to trust it. SUNDR provides fork consistency: if a malicious server presents different, inconsistent histories of file changes to different clients, those clients can detect the divergence as long as they eventually communicate with each other, even though neither client ever had reason to trust the server itself. SUNDR predates Bitcoin by four years, yet this module places it after the blockchain material deliberately. Seeing "distribution as a security mechanism" first at internet scale, in an open, adversarial, permissionless setting, makes SUNDR's narrower and earlier guarantee, detecting rather than preventing a single untrusted server's misbehavior, easier to place in context as a related but more modest instance of the same underlying idea: use the fact that there is more than one observer to catch a lie that no single observer could catch alone. Related CCI capabilities Computer Architecture (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/computer-architecture/). Optics Primer Series (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/optics/). Maths Refresher Series, Finance (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/maths-finance/). System Dynamics (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/system-dynamics/). CCI Lab: Run it, build with it, read the thinking, reuse the data. (https://www.cambridgecyberinternational.com/en/insights/lab/) Historical Contrast and Capstone: Plan 9, Inferno, and Choosing a Trust Model. Plan 9 and Inferno's unified-namespace, ticket-based trust model, contrasted with Byzantine and blockchain models, plus a capstone. Distinguish Plan 9 and Inferno's unified-namespace, ticket-based authentication model of distributed trust from the Byzantine fault-tolerant and blockchain models covered earlier in the course. Given a stated adversary model, select and justify an appropriate consensus, Byzantine fault tolerance, or blockchain mechanism (capstone). Plan 9 from Bell Labs: one namespace for all resources via 9P, Plan 9's authentication: ticket-based authentication and the factotum service, Inferno: Limbo, the Dis virtual machine, and the Styx protocol, Why 'authenticate once to a trusted protocol' is a different answer than 'tolerate a lying participant', Capstone: choosing a mechanism for a stated adversary model A Different Philosophy of Distributed Trust Everything studied so far answers the question "how do we agree despite a lying or crashing participant?" Plan 9 from Bell Labs, built by Rob Pike, Dave Presotto, Ken Thompson, and Howard Trickey, and its successor Inferno, built at Lucent Technologies and later maintained by Vita Nuova, answer a different question: how do we unify access to every resource, local files, devices, remote services, and processes, under one authenticated protocol, so that trust only has to be established once? Plan 9 presents every resource, wherever it physically lives, through a single hierarchical namespace, accessed uniformly through the 9P protocol. Authentication is centralized: historically a ticket-based exchange and later a dedicated factotum service establish a user's identity once, after which the entire unified namespace is available without per-service logins. Inferno carries the same philosophy further: applications written in the Limbo language run on the Dis virtual machine and communicate over Styx, an evolution of 9P, with public-key authentication and optional per-channel encryption and authentication added, alongside per-process namespace isolation. Why Plan 9 and Inferno Are a Contrast, Not a Backbone Neither system's security model addresses this course's central concern. Both assume that once a participant has authenticated to the trusted protocol, it is treated as trustworthy from then on. Neither specifies what happens when an already-authenticated participant then behaves arbitrarily, sending conflicting information to different peers, which is precisely the Byzantine fault tolerance and consensus problem Modules 1 through 4 address. Building this course around Plan 9 and Inferno, however historically interesting, would leave every CyBOK-graded topic, consensus, Byzantine fault tolerance, clock attacks, blockchain security, untaught. They earn one module here, as a single supplementary case study in a genuinely different, complementary answer to the trust problem, not as this course's spine. Capstone: Choosing a Mechanism for a Stated Adversary Every mechanism in this course was designed for a specific adversary model. Choosing correctly means starting from that model, not from whichever mechanism is newest or most familiar. The capstone exercise asks each learner to produce a short memo that states an adversary model explicitly, fixed or open membership, crash-only or Byzantine behavior, and matches it to the mechanism from this course whose own stated assumptions the scenario actually satisfies. A fixed, single-organization deployment that can only fail by crashing calls for Paxos or Raft. A known consortium of mutually distrusting organizations that might act maliciously calls for a Practical Byzantine Fault Tolerance (PBFT)-lineage protocol. An open, permissionless network with no vetting at all calls for a proof-of-work blockchain. The single continuity across this entire course, from Module 0's fault models to this capstone, is that no mechanism studied here, not Paxos, not PBFT, not Bitcoin, not the Secure Untrusted Data Repository (SUNDR), not Plan 9's authentication model, is universally correct outside the specific assumptions it was designed to satisfy. Related CCI capabilities Computer Architecture (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/computer-architecture/). Optics Primer Series (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/optics/). Maths Refresher Series, Finance (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/maths-finance/). System Dynamics (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/system-dynamics/). CCI Lab: Run it, build with it, read the thinking, reuse the data. (https://www.cambridgecyberinternational.com/en/insights/lab/)