Fault tolerance and Byzantine faults

The starting question

Seven cashiers, in seven cities, each keep a copy of the same ledger. One morning, one of them stops answering. Another answers, but says "yes" to the Douala cashier and "no" to the Garoua cashier for the same question. Do these two incidents look alike? Treating them the same way would be a serious mistake.

The types of faults

The name comes from the "Byzantine generals problem" (Lamport, Shostak and Pease, 1982): generals must decide together whether to attack, while some are traitors and lie.

A Byzantine fault is not necessarily malicious: a corrupted bit in memory, a software bug or a wrong configuration also produce arbitrary behaviour. But in security we assume the worst: an adversary who knows the protocol.

Why the second costs more

Facing a crash, a reliable node can reason: "what it told me was true". It may only lack information. Facing a Byzantine node, nothing it says is trustworthy, and it can say different things to each peer (this is called equivocation). You must cross-check testimonies, and you need more of them.

A worked example: three nodes, without signatures

Three nodes A, B, C exchanging oral messages (no signatures: each relays what it heard, without proof). A wants to know whether C voted "yes" or "no".

• If C crashed: A hears nothing from C. A knows one voice is missing.
• If C is Byzantine: C says "yes" to A and "no" to B. A asks B: B answers "C told me no". A sees two versions, but cannot know whether C or B is lying: from A's viewpoint the contradiction is symmetric. Without signatures, with three nodes and one faulty, it is impossible to decide. With signatures the diagnosis becomes possible (see below), but lesson 3 shows that a quorum-based protocol still needs at least 4 nodes.

The role of signatures (workshop 105)

If messages are signed, B cannot lie about what C said: it can only present messages really signed by C. But that does not stop C from signing "yes" for A and "no" for B. A signature proves who said what, not that what is said is true or unique. On the other hand, two contradictory messages signed by C constitute a proof of equivocation: anyone can verify that C contradicted itself. This is the basis of automatic punishment (slashing) in some protocols. With signatures, A can therefore establish C's contradiction, but only after the fact: the decision may have been taken in the meantime.

Tolerating crashes: 2f + 1

If we assume only crashes, a majority suffices: with n = 2f + 1 nodes, f can fall and the remaining f + 1 still form a majority. Three nodes tolerate 1 crash; five tolerate 2. This is the model of replication protocols such as Paxos or Raft. It assumes that no node lies.

Your turn

In quorum-sim, set 7 validators and switch one to "offline", then another to "Byzantine". Compare the quorum's behaviour: the offline node removes a voice; the Byzantine one can supply a false or contradictory one.

What this does NOT guarantee

Classifying an incident as a crash is an assumption: a silent node can be Byzantine (it keeps quiet on purpose), and a slow node can pass for dead (lesson 1 of workshop 107).

Recap

• Crash: the node goes quiet, does not lie. Byzantine: arbitrary behaviour, including saying different things to each peer.
• Signatures attribute messages but do not prevent equivocation; they make it provable.
• Crashes only: 2f + 1 nodes. Byzantine faults: more, as we shall see.

The starting question

Four validators must decide which block comes next. How many votes make the decision final? If we say "simple majority, 3 out of 4", is that enough against a Byzantine node? To answer, we need two precise notions.

Safety and liveness

• Safety: "nothing bad ever happens"; here, two honest nodes never decide two different values for the same position.
• Liveness: "something good eventually happens"; here, the system eventually decides.

These are two independent properties. A system that never decides is safe (it never contradicts itself) but not live. Classic BFT protocols are designed so that stopping is better than contradicting oneself: facing crashes or a faulty network, liveness is lost before safety. But facing more than f Byzantine nodes, both can be lost at the same time (lesson 3).

The concept: the quorum

A quorum is a set of nodes whose agreement suffices to validate a step. A simple rule: a value is decided when confirmed by a quorum of size q.

Two conflicting requirements weigh on q:

1. q must not be too large: the system must progress even if f nodes keep silent. So q ≤ n − f.
2. q must not be too small: two quorums must necessarily share an honest node, otherwise two contradictory values could be decided in parallel.

A worked example: four validators, f = 1

n = 4, one Byzantine node possible, q = 3 (we will justify this choice in lesson 3).

• Two quorums of 3 out of 4 share at least 3 + 3 − 4 = 2 nodes.
• At most 1 is Byzantine: at least 1 of the 2 is honest.
• An honest node votes only once per position: it cannot confirm two different values. So the two quorums cannot decide two different values. Safety is preserved.

With q = 2 out of 4: two disjoint quorums {A, B} and {C, D} exist, each could decide a different value. Safety lost even without any fault.

A worked example: seven validators, f = 2

n = 7, q = 5. Two quorums share at least 5 + 5 − 7 = 3 nodes; at most 2 are Byzantine, hence at least 1 honest. And the system lives: 7 − 2 = 5 nodes still answer, which is just a quorum.

Quorum and reading the state

Once the value is decided by a quorum, a client querying a quorum will meet at least one honest node that saw it, but it does not know which one is honest. It needs f + 1 identical answers to be sure that at least one comes from an honest node. This is what lets a client verify without trusting a single server.

What this does NOT guarantee

• A quorum guarantees safety if the number of Byzantine nodes does not exceed f. Beyond that, the guarantees collapse (lesson 3).
• A quorum does not ensure liveness if the network is too slow or cut: you may wait a long time. No decision is not necessarily an attack.
• A quorum proves that "enough nodes voted", not that the decided value is valid: validity is checked by each honest node before voting.

Your turn

In quorum-sim, set 7 validators, 2 Byzantine: is the quorum of 5 reachable? Switch a third to Byzantine or offline and see what the tool reports.

Recap

• Safety = never two contradictory decisions; liveness = we eventually decide. Independent.
• A quorum q must satisfy q ≤ n − f (liveness) and two quorums must share an honest node (safety).
• With n = 4, f = 1: q = 3. With n = 7, f = 2: q = 5.

The starting question

You read everywhere: "a BFT protocol tolerates up to one third of Byzantine nodes". Where does the third come from? Why not a half, as for crashes? And under which conditions is it true?

The assumptions (read before the reasoning)

The counting argument below holds for the following model:

1. n nodes, of which at most f are Byzantine (the rest are honest).
2. Honest nodes follow the protocol; Byzantine ones can do anything, including coordinating.
3. The network may delay messages, but a message between honest nodes eventually arrives. We want safety to hold even without a delay bound, and liveness to hold when the network eventually behaves (the so-called partial synchrony assumption).
4. Messages are authenticated (a node cannot impersonate another). It can, however, say different things to each peer. Transferable signatures do not lower the number of nodes needed under partial synchrony.
5. The protocol is deterministic, on a replicated state machine.

In other models the bounds differ: for example, with a synchronous network (bounded, known delays) and unforgeable signatures, the generals problem can be solved for a larger number of traitors, according to the 1982 paper; without signatures, that same paper gives the bound n > 3f. And in a purely asynchronous network, no deterministic protocol can guarantee termination (while staying safe) if even a single node may crash (result of Fischer, Lynch and Paterson, 1985): this is why partial synchrony is assumed for liveness.

Mind the scope of what follows: the counting shows what a quorum-based decision rule requires. The bound n ≥ 3f + 1 is also established for any protocol (Lamport, Shostak and Pease, 1982, without signatures in a synchronous network; Dwork, Lynch and Stockmeyer, 1988, under partial synchrony) by an indistinguishability argument that we do not reproduce.

The counting argument

We look for the quorum size q and the number of nodes n. Two constraints:

• Liveness: we must be able to decide even if the f Byzantine nodes keep silent. Only n − f nodes answer, so q ≤ n − f.
• Safety: any two quorums overlap in at least 2q − n nodes. Among them, f may be Byzantine, so at least one must be honest: 2q − n ≥ f + 1, i.e. q ≥ (n + f + 1) ÷ 2.

Chaining: (n + f + 1) ÷ 2 ≤ q ≤ n − f, which requires (n + f + 1) ÷ 2 ≤ n − f, i.e. n + f + 1 ≤ 2n − 2f, hence n ≥ 3f + 1.

For n = 3f + 1, the compatible quorum size is q = 2f + 1.

Why 3 nodes cannot tolerate 1 Byzantine node

n = 3, f = 1. We would need q ≤ 2 (liveness) and 2q − 3 ≥ 2, i.e. q ≥ 2.5 (safety): impossible. Concretely: A and B are honest, C is Byzantine. A cannot wait for C (it may stay silent), so it decides with {A, C}; B likewise decides with {B, C}. C votes X with A and Y with B: two contradictory decisions, and the only node common to the two quorums, C, is faulty. This reasoning holds even with signed messages.

The third "as a percentage"

n ≥ 3f + 1 is written f < n ÷ 3: the protocol is safe as long as strictly fewer than one third of nodes are Byzantine. In proof-of-stake chains, n is replaced by the share of stake (the stake is the tokens each validator puts up as collateral; votes are weighted): the assumption becomes "less than one third of the stake is Byzantine".

Convention: in this workshop, a decision requires strictly more than two thirds of the votes (q = 2f + 1 when n = 3f + 1). Other protocol descriptions (see workshop 109) say "two thirds" without saying whether it is strict or inclusive; the difference matters precisely at exactly one third.

What happens beyond f?

n = 4, tolerated f = 1, but two Byzantine nodes B1 and B2, and two honest ones H1 and H2. Quorum q = 3. B1 and B2 vote "X" with H1, forming the quorum {B1, B2, H1}, and vote "Y" with H2, forming {B1, B2, H2}. The two quorums overlap in {B1, B2}: two contradictory decisions for the same position. Safety is lost. The threshold is not a comfort zone: beyond it, the guarantee vanishes entirely.

The founding paper of practical Byzantine fault tolerance is Castro and Liskov's Practical Byzantine Fault Tolerance (OSDI 1999), which works in this model with n ≥ 3f + 1.

What this does NOT guarantee

• The bound says "if at most f are faulty"; it does not say that fewer than f faulty is likely. Who controls the proportion of faulty nodes? In an open network, that is the question of validator identity (proof of stake, permissioning).
• It does not cover attacks on the network itself (manufactured partitions, workshop 107).
• It says nothing about transaction validity, performance, or decentralisation.

Recap

• Constraints: q ≤ n − f (liveness) and 2q − n ≥ f + 1 (safety) give n ≥ 3f + 1 and q = 2f + 1.
• Assumptions: at most f Byzantine, authenticated messages, safety without a delay bound, liveness under partial synchrony.
• Beyond f Byzantine nodes, safety can be lost, not merely degraded.

The starting question

A proof-of-stake network announces: "safe as long as less than one third of the stake is Byzantine". How much money does it cost to exceed that threshold? The answer "a third of the total value" is a starting point, not a result.

What each fraction of the stake allows (in lesson 3's model)

The exact threshold: safety is guaranteed for b < n ÷ 3. At exactly b = n ÷ 3 (when the division is exact), with a quorum strictly above 2/3, safety still holds but liveness is lost; beyond, safety is no longer guaranteed. With an inclusive "at least 2/3" rule, however, exactly one third of faulty nodes already suffices to lose safety.

A worked example

Fictitious network: 2,400,000 tokens staked in total, a token being worth 3 fictitious units.

• One third of the stake: 2,400,000 ÷ 3 = 800,000 tokens.
• Naive price: 800,000 × 3 = 2,400,000 units.

This value is a theoretical floor, not a price. Why?

1. Buying pushes the price up. If the market is thin, acquiring 800,000 tokens costs more than 3 per token (slippage).
2. Stake may be locked: tokens in an unbonding period, held by people who do not sell, or not purchasable.
3. The calculation depends on how stake is acquired. If the attacker buys tokens that are already staked, the total stays 2,400,000 and they need 800,000. If they add fresh stake, the total grows: they need x such that x ÷ (2,400,000 + x) ≥ 1 ÷ 3, i.e. x ≥ 1,200,000 tokens, 50% more.
4. Slashing: if the protocol destroys stake caught in equivocation (the proof from lesson 1), the attack costs the lost stake on top.
5. The gain: the attacker spends only if the expected gain exceeds the cost. A threshold is also a question of incentives, not only of mathematics.

Bribing instead of buying

One can also bribe validators who already hold 800,000 tokens: the cost is then the bribe, not the price of the tokens. If a few large validators concentrate the stake, convincing a few may suffice. Stake concentration is therefore a security measure as much as the total amount.

What this does NOT guarantee

Staying under the third guarantees the protocol's properties within its model. It does not protect against an implementation bug, a stolen validator key (workshop 105) or a partition (workshop 107) that would put honest nodes on the wrong side.

Recap

• At a third of the stake, an attacker can block; beyond it, with the network, they can sometimes contradict. Above two thirds, they decide.
• Theoretical threshold ≠ price: slippage, locking, bribes, penalties and gain all matter.
• Acquiring 1/3 by buying costs 1/3 of the total; by adding fresh stake, 1/2 of the existing total is needed.