Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 41 ยท Consensus and Networks

The Double-Spend Problem and Byzantine Faults

Why digital cash needs consensus: double spends, the Byzantine generals problem, Sybil attacks and trust assumptions, with small live Python demos.

A digital coin is just data, and data can be copied. If I give you a file, I still have it. Paper cash cannot be copied this way, but a digital token can, unless something prevents it. Preventing a coin from being spent twice is the double-spend problem, and for decades the only known answer was a trusted middleman such as a bank, which keeps the single authoritative ledger.

A blockchain removes the middleman, and that creates the hard part: a crowd of computers, any of which may be slow, offline or dishonest, must still agree on one history. This lesson explains why agreement is hard, defines the failure model that engineers use (Byzantine faults), looks at the Sybil attack that breaks naive voting, and gives you a feel for the trade-offs with small demos. The rest of this chapter then shows how real networks solve it.

Spending the same coin twice

In UTXO vs Account Model the ledger rejected a second spend because the first one had already been applied. That works when there is one ledger. On a network there are many copies, and two conflicting payments can reach different nodes in different orders.

Suppose Alice has one coin and sends payment A (to Bob) to part of the network and payment B (to Carol) to the other part at the same moment. Each node accepts whichever it sees first, using the simple rule "first seen wins".

Python First seen wins: nodes disagree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The output is:

TEXT
Rule: accept the first payment you see
  node 1: sees ['A', 'B'] -> accepts A, thinks bob owns the coin
  node 2: sees ['B', 'A'] -> accepts B, thinks carol owns the coin
  node 3: sees ['A', 'B'] -> accepts A, thinks bob owns the coin
Do all nodes agree? False

Node 2 now believes Carol owns the coin while the others believe Bob does. Alice has successfully spent one coin twice, and the network has split into two incompatible views. Every rule that does not fix an order for the transactions will fail like this. The core job of a blockchain is to make all honest nodes agree on one total order of transactions, so the first valid spend wins everywhere and the second is rejected everywhere. That agreement process is consensus.

Python Agree on one order, agree on the outcome

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All three nodes print carol owns the coin. The ledger rule is the same, but now every node processes the same ordered list. Which one is chosen (A or B) matters far less than that everyone chooses the same.

Why agreement is hard

Getting a group to agree sounds easy until you list what can go wrong:

  • Messages are delayed, reordered or lost. There is no shared clock, so "first" has no global meaning.
  • Nodes crash and restart. A node that went silent might be dead or just slow, and you cannot tell which.
  • Nodes lie. A hostile node can tell different things to different peers.
  • The network can split into groups that cannot talk to each other for a while (a partition).

Distributed-systems researchers separate two kinds of failure. A crash fault means a node simply stops. A Byzantine fault means a node can do anything: send wrong data, send different answers to different peers, collude with others. Public blockchains must assume Byzantine behaviour because anyone can join and some participants will be attackers.

The Byzantine generals problem

The classic story: several generals surround a city and must agree whether to attack or retreat. They can only communicate by messenger. An attack by only some of them means defeat, so they must all choose the same action. Some generals may be traitors who send conflicting messages.

The key result is a counting argument. With only three generals and one traitor, a loyal general cannot work out who is lying. The demo below shows the commander (the general who proposes the plan) and two lieutenants. Lieutenant 1 hears the commander and also asks Lieutenant 2 what the commander told it.

Python Three generals, one traitor: the view is identical

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see:

TEXT
Scenario A (traitor: lieutenant 2): {'commander says': 'ATTACK', 'lieutenant 2 says commander said': 'RETREAT'}
Scenario B (traitor: the commander): {'commander says': 'ATTACK', 'lieutenant 2 says commander said': 'RETREAT'}
Lieutenant 1 can tell them apart? False

 3 generals can tolerate up to 0 traitor(s)  (need n >= 3f + 1)
 4 generals can tolerate up to 1 traitor(s)  (need n >= 3f + 1)
 7 generals can tolerate up to 2 traitor(s)  (need n >= 3f + 1)
10 generals can tolerate up to 3 traitor(s)  (need n >= 3f + 1)

In scenario A, Lieutenant 1 should attack (the commander is loyal). In scenario B it should do what the loyal Lieutenant 2 does, which is retreat. But the evidence it holds is the same in both, so no rule can be right in both. That is the heart of the classic result: without signatures, agreement among n nodes with f Byzantine ones needs n >= 3f + 1. Signatures and other tricks change the bound in some models, and you will see the practical form in BFT, Delegated and Other Consensus Mechanisms.

flowchart TD
    C["Commander<br/>says ATTACK"] --> L1["Lieutenant 1"]
    C --> L2["Lieutenant 2<br/>(traitor?)"]
    L2 -- "claims: RETREAT" --> L1
    L1 --> Q{"Who is lying?"}

Lieutenant 1 hears ATTACK from one source and RETREAT from another and cannot tell which of them is the traitor.

Sybil attacks: fake identities break voting

The easiest idea for agreement is voting: let nodes vote on the next block and follow the majority. In an open network this fails immediately because identities are free. One attacker can create thousands of fake nodes, called Sybils, and outvote everyone. This is a Sybil attack, named after a famous case study of a person with multiple personalities.

A system that lets anyone join therefore needs a way to make each vote cost something that cannot be faked cheaply. Bitcoin ties voting power to computing work (Proof of Work and Mining), while other chains tie it to locked-up money (Proof of Stake). Permissioned systems avoid the problem by admitting only known members.

Python One identity one vote, or one hash one vote

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The output:

TEXT
Voting by identity:
  honest 100  attacker 1001 -> attacker wins: True
Voting by work:
  honest 100  attacker 30 -> attacker wins: False
The attacker's share of the work is 23.1%, and splitting it over 1000 identities does not change that.

This is why Nakamoto's design was a breakthrough. It is "one CPU, one vote" in the original paper's words: voting power comes from a scarce resource, so creating identities no longer helps an attacker.

Trust assumptions and the CAP intuition

Every consensus design assumes something. Reading the assumption is the quickest way to understand what a system really guarantees.

  • Who may take part? Anyone (permissionless) or a fixed list (permissioned).
  • How much can be dishonest? Classic BFT protocols tolerate fewer than one third faulty nodes. Proof of work tolerates an attacker with less than half of the work (with caveats). Proof of stake sets similar thresholds on stake.
  • What about the network? Some designs assume messages arrive within a known time (synchrony); others work with unknown delays but give up something else.

The CAP theorem gives an intuition for the trade-off when the network splits. During a partition, a system must choose between consistency (every part answers with the same, up-to-date data, so some parts must refuse to answer) and availability (every part keeps answering, so the parts may disagree). Many blockchains lean toward availability: both sides of a partition keep making blocks, and when the partition heals, one side's history is dropped. That is the forks and reorganisations story in Longest Chain Rule, Forks and Reorgs. Others, such as BFT-style chains, lean toward consistency and halt rather than fork.

None of this is a defect. It is the price of agreement among strangers, and each consensus mechanism chooses a different point in the space.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is a double spend?

    Digital data can be copied, so the system must make sure a coin can be spent only once.
  2. 2. Why did the 'first seen wins' rule leave the nodes in disagreement?

    With no agreed order, each node's idea of 'first' depends on its own network delays.
  3. 3. What distinguishes a Byzantine fault from a crash fault?

    A crashed node falls silent. A Byzantine node can behave arbitrarily, including lying differently to different peers.
  4. 4. Why does 'one identity, one vote' fail in an open network?

    When identities cost nothing, the number of identities says nothing about how many independent participants exist.
  5. 5. With the classic oral-messages bound n >= 3f + 1, how many Byzantine nodes can 10 nodes tolerate?

    10 >= 33 + 1, but 10 < 34 + 1, so f = 3.

Summary

  • Digital coins can be copied, so a system must prevent a coin from being spent twice; the root of that is agreeing on one order of transactions.
  • Without an agreed order, "first seen wins" leaves nodes with different ledgers.
  • Public networks must tolerate Byzantine faults: nodes that lie or behave arbitrarily, not only nodes that crash.
  • Classic results say agreement needs roughly n >= 3f + 1 nodes (in the unsigned model), and open networks must also defeat Sybil attacks by tying votes to a scarce resource.
  • Every consensus mechanism states trust assumptions and picks a point in the consistency/availability trade-off.

Next: Longest Chain Rule, Forks and Reorgs, the way Bitcoin-style chains settle disagreements in practice.