A ledger nobody owns
A ledger is a list of who owns what and who paid whom. Every bank keeps one, and so does every land registry, stock exchange and village savings group. Usually exactly one organisation keeps the master copy, and everyone else trusts it to keep that copy honestly.
Now imagine a ledger that several organisations want to share, but none of them is willing to let any other hold the master copy. A group of shipping companies in Rotterdam, Singapore and Durban might want one record of where every container is, yet none wants a competitor to control that record. Or take the most demanding case: a currency in which anyone in the world may hold and send money, with no bank, government or company in the middle, and in which some of the participants are actively trying to cheat.
A blockchain is a design for that last situation: a ledger copied by many independent computers, which agree on its contents, and its order, using cryptography and a consensus protocol, even though some of them may lie. This course is about how such systems work, where they fail, and — in its last level — how the same cryptography lets one computer prove to another that a computation was done correctly.
This first lesson asks the question that should come before any design: what problem is a blockchain solving, and is it your problem? Very often the honest answer is "no", and an ordinary database, run by someone the participants already trust, is cheaper, faster, more private and easier to fix when things go wrong. We will see why, build the one data structure every blockchain shares — a chain of hashes — and end with a decision procedure you can apply to any proposal.
The double-spending problem
A paper banknote is hard to copy, so if you hand it to me, you no longer have it. A digital token is just bytes, and bytes can be copied perfectly. If a "coin" were simply a signed file saying this is coin number 4417, its owner could send identical copies to two shopkeepers. This is double spending, and every digital-money design must stop it.
Signatures do not help on their own. A signature (the subject of a later lesson) proves that the owner of coin 4417 authorised a payment. It cannot prove that the owner did not also authorise a second payment of the same coin to someone else. To catch that, somebody must know about every payment, and must know which came first.
Here is the problem in miniature. Kofi has 10 tokens. Two copies of the ledger, one in Lagos and one in Lima, each check balances carefully, but each knows only what it has seen so far:
class Replica:
"""A naive copy of a token ledger: it checks balances, but only against what it has seen."""
def __init__(self, name, balances):
self.name = name
self.balances = dict(balances)
self.log = []
def apply(self, payer, payee, amount):
if self.balances.get(payer, 0) < amount:
return f"{self.name}: REJECT {payer} -> {payee} {amount} (insufficient funds)"
self.balances[payer] -= amount
self.balances[payee] = self.balances.get(payee, 0) + amount
self.log.append((payer, payee, amount))
return f"{self.name}: accept {payer} -> {payee} {amount}"
start = {"Kofi": 10}
lagos, lima = Replica("Lagos", start), Replica("Lima", start)
# Kofi signs two payments of his only 10 tokens and sends one to each side of the network.
print(lagos.apply("Kofi", "Mei", 10))
print(lima.apply("Kofi", "Ravi", 10))
print("Lagos thinks:", lagos.balances)
print("Lima thinks: ", lima.balances)
# When the replicas finally exchange logs, each order of the two payments gives a different history.
for order in ([("Kofi", "Mei", 10), ("Kofi", "Ravi", 10)], [("Kofi", "Ravi", 10), ("Kofi", "Mei", 10)]):
r = Replica("merged", start)
print([r.apply(*tx) for tx in order][1], "->", r.balances)Both replicas accepted a payment, so Mei and Ravi each believe they were paid, but only one of them can be. Once the replicas compare notes, either history is self-consistent; what is missing is a rule everyone accepts for which payment came first. Each replica was locally correct. The failure is one of agreement on order.
There are two classical ways out.
- A trusted third party sees every payment and decides the order. This is how card payments, bank transfers and mobile money such as Kenya's M-Pesa work: the operator's database is the truth, and the operator is accountable for it.
- Agreement among many parties on a single, growing, ordered history. Every participant keeps a copy, and a protocol makes the copies converge on the same order even if some participants misbehave. That ordered history, cryptographically sealed so that its past cannot be quietly rewritten, is what a blockchain is.
Trusted third parties, and when they are the right answer
"Trusted third party" can sound like an insult in blockchain writing. It should not. Most of the economic world runs on them, and for good reasons.
- A bank keeps account balances, so a transfer is two updates in one database transaction. Double spending is impossible because there is only one copy of the truth.
- A clearing house or central counterparty (for example a stock exchange's clearing arm) sits between buyers and sellers, nets out millions of trades, and guarantees settlement if one side defaults.
- A land registry records who owns each plot, and its records are backed by courts and law.
- A certificate authority vouches that a public key belongs to a website, which is how your browser trusts a TLS connection (applied cryptography).
What these institutions offer, beyond a database, is easy to overlook:
- Accountability and recourse. If a bank makes a mistake or is defrauded, there are regulators, courts, deposit insurance, and someone to phone. Payments can be reversed.
- Privacy. Your balance is not published to the world.
- Efficiency. One well-run database handles tens of thousands of transactions a second with millisecond latency. No replicated protocol among strangers comes close.
- A link to the physical world. A land registry can send a surveyor; a ledger cannot.
A trusted party is the wrong answer when no single party is trusted by everyone who must use the system, when the party itself is the threat (it may censor, freeze or inflate), or when the cost of building and policing such a party across borders is higher than the cost of the alternative. Those situations are real, and they are where blockchains have found their uses. But they are narrower than the enthusiasm of the late 2010s suggested.
Analogy, not a formal construction
A village savings group in which every member keeps a copy of the record book, and every payment is read aloud at the weekly meeting and written into all the books at once, needs no treasurer to trust. It pays for that with a weekly meeting and many tired hands. A town with an honest, audited bank does not need the meeting.
Byzantine faults, Sybils and the two kinds of ledger
Distributed systems taught the failure models. A Byzantine participant may do anything: crash, lie, send different messages to different peers, or collude. Classical Byzantine fault-tolerant (BFT) protocols tolerate up to Byzantine participants among , and they assume that the set of participants is known: everyone knows the public keys and can count votes.
That assumption is exactly what fails in an open network. If anyone may join, an attacker can simply create a thousand identities and outvote everyone. This is the Sybil attack (named by John Douceur in 2002). Counting identities means nothing when identities are free, so an open ledger must count something scarce instead: computing work spent (proof of work) or money locked up as a deposit (proof of stake).
Definition— Ledger, blockchain
A ledger is an ordered, append-only list of records (transactions). A blockchain is a ledger replicated across many nodes, in which records are grouped into blocks, each block contains a cryptographic hash of the previous block, and a consensus protocol decides which block comes next.
Definition— Permissioned and permissionless
A ledger is permissionless if anyone may run a node, read the ledger and take part in consensus without anyone's approval; Sybil resistance must then come from a scarce resource. It is permissioned if a known set of members, admitted by some governance process, runs consensus; classical BFT with known members then applies directly.
| Permissionless | Permissioned | |
|---|---|---|
| Who validates | anyone with the scarce resource | admitted members |
| Sybil resistance | work or stake | identity, contracts, law |
| Consensus | Nakamoto-style or stake-based BFT | classical BFT (or even crash-fault) |
| Examples | Bitcoin, Ethereum, Cardano, Solana | Hyperledger Fabric, R3 Corda, Canton |
| Typical cost | slow, fees, public data | needs governance; often a database would do |
Permissioned ledgers are a sensible tool when several organisations need a shared record and want each to hold a verifiable copy. They are also where many projects discovered that, once the members trust each other enough to admit one another, a shared database with signed audit logs would have done the job. Two well-documented examples: TradeLens, a shipping platform built by Maersk and IBM, was shut down in 2023 after failing to attract enough of the industry; and the Australian Securities Exchange abandoned its ledger-based replacement for its settlement system in 2022, writing off about AUD 250 million. Neither failed because of the cryptography. Both failed on adoption, governance and complexity — the questions the decision procedure below asks first.
A hash-linked, append-only ledger
Every blockchain, whatever its consensus protocol, shares one data structure: each block stores the hash of the previous block. A cryptographic hash such as SHA-256 (recalled in applied cryptography and studied properly in the next lesson) behaves like a fingerprint: change one byte of the input and the output changes unpredictably, and nobody can find two inputs with the same output. So the hash of block 3 depends on block 2's hash, which depends on block 1's, and so on back to the start. Change anything in the past and every later hash changes.
Here is a complete ledger in about forty lines: a land register in which each block records a few transfers. The verify method recomputes every hash and checks every link, and can also compare the head against a hash we trust from somewhere else.
import hashlib
import json
def block_hash(index, prev_hash, entries):
"""SHA-256 of a canonical encoding of the block's contents."""
body = json.dumps({"index": index, "prev": prev_hash, "entries": entries},
sort_keys=True, separators=(",", ":"))
return hashlib.sha256(body.encode()).hexdigest()
GENESIS_PREV = "0" * 64
class Ledger:
"""An append-only list of blocks, each committing to the hash of the one before."""
def __init__(self):
self.blocks = []
def append(self, entries):
index = len(self.blocks)
prev = self.blocks[-1]["hash"] if self.blocks else GENESIS_PREV
block = {"index": index, "prev": prev, "entries": list(entries),
"hash": block_hash(index, prev, entries)}
self.blocks.append(block)
return block["hash"]
def head(self):
return self.blocks[-1]["hash"]
def verify(self, trusted_head=None):
"""Return (True, None) or (False, reason). Checks every link, and the head if one is given."""
prev = GENESIS_PREV
for b in self.blocks:
if b["prev"] != prev:
return False, f"block {b['index']} does not point to block {b['index'] - 1}"
if block_hash(b["index"], b["prev"], b["entries"]) != b["hash"]:
return False, f"block {b['index']} was altered after it was sealed"
prev = b["hash"]
if trusted_head is not None and prev != trusted_head:
return False, "the chain is self-consistent but its head is not the one we trust"
return True, None
ledger = Ledger()
ledger.append(["Amara registers plot 17", "Bilal registers plot 18"])
ledger.append(["Amara sells plot 17 to Chen Wei"])
ledger.append(["Dolores registers plot 19"])
ledger.append(["Chen Wei sells plot 17 to Esi"])
for b in ledger.blocks:
print(b["index"], b["hash"][:16], "<-", b["prev"][:16], b["entries"])
published = ledger.head() # imagine this hash printed in a newspaper every week
print("\nhonest ledger:", ledger.verify(published))
# 1. A clumsy forger edits an old entry.
ledger.blocks[1]["entries"][0] = "Amara sells plot 17 to Faisal"
print("edited entry: ", ledger.verify(published))
# 2. A careful forger also recomputes every hash from block 1 onwards.
prev = ledger.blocks[0]["hash"]
for b in ledger.blocks[1:]:
b["prev"] = prev
b["hash"] = block_hash(b["index"], b["prev"], b["entries"])
prev = b["hash"]
print("rehashed chain:", ledger.verify()) # with no outside anchor, it looks fine
print("against anchor:", ledger.verify(published)) # the published head exposes itThe output tells the whole story of hash chains in four lines:
- The honest ledger verifies.
- Editing block 1's entry is caught at once: its stored hash no longer matches its contents ("block 1 was altered after it was sealed").
- But a forger who recomputes every later hash produces a chain that is perfectly self-consistent. With nothing to compare it against,
verify()says(True, None). - Only the published head exposes the forgery: the rewritten chain ends in a different hash from the one printed in the newspaper.
So a hash chain gives tamper evidence relative to a trusted head. In 1991 Stuart Haber and Scott Stornetta used exactly this to timestamp documents, and in 1995 a company built on their work, Surety, began printing its chain's latest hash in The New York Times every week, so that anyone with an old newspaper could check that no document in the chain had been back-dated. In 2016 the Republic of Georgia's public registry agency agreed with the company Bitfury to anchor hashes of land-title records in Bitcoin, in the same spirit. Note what anchoring does and does not achieve: it proves that a record has not been altered since it was anchored. It cannot prove that the record was true when it was written, and the registry still decides who owns the land.
A blockchain adds two things to this structure: a way for many nodes to agree on which head is the head (consensus), and, in open systems, a cost for producing blocks, so that a forger cannot simply out-write the honest participants.
From timestamps to Ethereum
None of the ingredients of Bitcoin was new in 2008. What was new was the combination.
- 1982–1990: digital cash with a bank. David Chaum's blind signatures (1982) allowed a bank to issue electronic coins that could not be traced to the payer. His company DigiCash ran trials in the 1990s and went bankrupt in 1998. Double spending was prevented by the bank, which checked every coin against its list of spent ones: a trusted third party.
- 1991: hash-linked timestamps. Haber and Stornetta's paper, linked above, chains timestamps with hashes; a follow-up with Dave Bayer (1993) grouped documents into Merkle trees. Three of the eight references in the Bitcoin paper are to their work.
- 1992–1997: computation as a price. Cynthia Dwork and Moni Naor proposed making each e-mail cost a little computation, to deter spam. Adam Back's Hashcash (1997) did it with partial hash collisions — find an input whose SHA-1 hash starts with many zero bits — the exact puzzle Bitcoin miners solve today, with SHA-256.
- 1998–2005: money without a mint. Wei Dai's b-money (1998) and Nick Szabo's bit gold (proposed in 1998, written up in 2005) described money created by solving computational puzzles and recorded by a group of servers. Neither solved, in a fully open network, the problem of who decides the order of transactions. Hal Finney's reusable proofs of work (2004) still relied on a trusted server.
- 2008–2009: Bitcoin. The paper by the pseudonymous Satoshi Nakamoto appeared on 31 October 2008; the first block was mined on 3 January 2009. Its contribution was to use proof of work not merely as a price but as a vote: the chain with the most accumulated work is the agreed history, so outvoting the network requires outspending it. The author's identity remains unknown.
- 2013–2015: Ethereum. Vitalik Buterin's whitepaper (2013) proposed a blockchain whose state is not just balances but programs, called smart contracts, written in a general-purpose language. Ethereum launched on 30 July 2015. A year later a flaw in a contract called The DAO let an attacker drain a large share of its funds; the community's decision to reverse it with a hard fork split the chain into Ethereum and Ethereum Classic. We will meet smart contracts, and their failures, in the Practice level.
Since then the field has produced real engineering advances, many of them in this course: proof-of-stake consensus, rollups, and the verifiable-computation techniques of the last level. It has also produced spectacular failures — exchange collapses, frauds and hacks costing users many billions of US dollars — which a later lesson treats as seriously as the successes.
Do you need a blockchain?
Here is a decision procedure. Work through it in order; the first "stop" is your answer.
- Do you need shared state at all? If one party keeps records only for itself, use a database. Stop.
- Does more than one party need to write? If only one organisation writes and others merely read and check, use a database plus a verifiable log: an append-only hash-linked log whose head is published or signed, like Certificate Transparency (RFC 6962). Readers can detect any rewriting without any consensus protocol. Stop.
- Is there a party all writers already trust to run it — an existing institution, a regulator, a jointly owned company? Let it run a database, and add a verifiable log if you want auditors to be able to check its history. Stop.
- Are the writers a known, limited set that can sign a contract and admit new members? Consider a permissioned ledger with BFT consensus among the members — but first ask whether a shared database operated under a contract, with signed audit logs, would do. Agreeing the governance (who joins, who upgrades the software, who pays) is the hard part either way.
- Must anyone in the world be able to take part without permission, and is resistance to censorship by any single party worth slow confirmation, fees, public data and irreversible mistakes? Then a permissionless blockchain is a candidate.
Two cross-cutting questions apply at every step:
- Where does the data come from? If records describe the physical world — a parcel arrived, a field was planted, a diamond is not a fake — the chain only records what someone claims. This is the oracle problem: the ledger is exactly as trustworthy as whoever writes the input.
- Who can fix a mistake? In a bank, a wrong transfer can be reversed. On a public chain, often nobody can, by design.
Example— Three proposals
A hospital group's patient records, "on a blockchain". One organisation writes; patients' privacy is paramount; mistakes must be corrected. Step 2 stops: a database with access control and an audit log. Putting medical data on a public ledger would be a privacy disaster.
A consortium of six banks reconciling interbank payments. Several writers (step 2 passes), and perhaps none wants another to run the system (step 3 may pass). Step 4 applies: a permissioned system, or a jointly owned utility with a database. Either way the banks remain accountable to their regulators.
Money that a person in any country can hold and send without asking a bank, even one that wants to stop them. No trusted party fits the requirement, writers are unknown and unlimited, and censorship resistance is the point. This is the case for a permissionless blockchain — with its costs and risks, which the rest of the course examines.
Common misconceptions
Misconception
"Data on a blockchain is true." The chain guarantees that a record has not been altered since it was accepted, and that all honest nodes agree on it. It says nothing about whether the record was correct when it was written. Garbage in, permanent garbage out.
Misconception
"A blockchain is immutable." Hash-linking makes changes evident; it does not make them impossible. As the code showed, rewriting a chain with no outside anchor and no cost per block is trivial. Public chains are hard to rewrite because rewriting requires out-competing the honest majority of work or stake — and chains with little work or stake behind them have been rewritten in practice (see Proof of work). Communities have also chosen to rewrite history by social agreement, as Ethereum did after The DAO.
Misconception
"Blockchains remove the need for trust." They move it. You trust the protocol's design, the correctness of the software, the honest majority assumption, the developers who maintain the code, your own key management, and whoever feeds data in. Whether that is less trust than trusting a bank depends on the bank, the chain and the use.
Misconception
"A blockchain is just a slow database." For one writer it is indeed a slow, expensive database. For many mutually distrustful writers with no one they all trust, it solves a problem databases do not address: agreeing on an order of events without a referee. The useful question is never "blockchain or database?" in general, but who must trust whom in this particular case.
Exercises
1. Why blockchains?
Warm-upHumanKofi owns one digital token. He signs a payment of that token to Mei and, a second later, another payment of the same token to Ravi, and sends the two payments to different parts of the network. What is this attack called? (Two words.)
2. Why blockchains?
Warm-upHumanA hash-linked ledger like the one in the lesson has blocks numbered 0 to 99. A forger changes one entry in block 40 and wants the altered chain to pass verify() with no trusted head. How many block hashes must the forger recompute?
3. Why blockchains?
CoreHumanA forger edits block 2 of a ten-block hash-linked ledger and then recomputes the hashes and prev links of blocks 2 to 9. Which check detects the forgery?
4. Why blockchains?
CoreHumanA permissioned ledger is run by a known set of member organisations using a classical BFT protocol. It must keep working correctly even if 4 members are Byzantine (they may crash, lie or collude). What is the smallest number of members it needs?
5. Why blockchains?
CoreHumanA city council issues building permits. Only the council's planning office creates or changes permits. Residents and journalists want to be able to check that no permit was quietly back-dated or deleted. Following the lesson's decision procedure, what should the council build?
6. Why blockchains?
CoreHumanWhich of these does a well-regulated bank typically offer its customers that a permissionless blockchain, by design, does not? Select all that apply.
7. Why blockchains?
CoreComputationalWrite first_bad_block(blocks, trusted_head=None) for the ledger format of the lesson: a list of dicts with keys index, prev, entries and hash. Return
- the index of the first block that is broken — its
indexis not its position, itsprevis not the previous block'shash(orGENESIS_PREVfor block 0), or its storedhashdoes not matchblock_hash(index, prev, entries); len(blocks)if every block is fine buttrusted_headis given and differs from the last block's hash;-1if everything checks out (an empty list checks out).
block_hash and GENESIS_PREV are provided.
Further reading and resources
- Bitcoin: A Peer-to-Peer Electronic Cash System · Satoshi Nakamoto · 2008Nine pages; the first two sections state the double-spending problem and the idea of a timestamp server.
- How to time-stamp a digital document · Stuart Haber and W. Scott Stornetta · 1991The hash-linked chain of timestamps, seventeen years before Bitcoin.
- Pricing via Processing or Combatting Junk Mail · Cynthia Dwork and Moni Naor · 1992The first proposal to make a request cost computation, the idea behind Hashcash and proof of work.
- Do you Need a Blockchain? · Karl Wüst and Arthur Gervais · 2017A published decision flowchart; compare it with the one in this lesson.
- Ethereum whitepaper · Vitalik Buterin · 2013
- The Byzantine Generals Problem · Leslie Lamport, Robert Shostak and Marshall Pease · 1982
- RFC 6962: Certificate Transparency · 2013A public, append-only, verifiable log run by ordinary operators, with no consensus protocol — a useful contrast to a blockchain.
- Bitcoin and Cryptocurrency Technologies · Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller and Steven Goldfeder · 2016Chapter 1 covers the same ground more slowly, with the authors' own examples.