Lecture 19 · Thursday 27 November 2025

Ethereum and smart contracts

The lecture compares four changes to Bitcoin's design. Ethereum adds a virtual machine and explicit state, Cardano assigns block production by stake through Ouroboros, Algorand selects committees by secret sortition and Litecoin makes mining memory-intensive.

Deck: 07_Alt_Curr.pdf Chapter 7 Sections 1 to 5

Where the Course WasRecap of Lecture 18

Lecture 18 finished Chapter 6 on Bitcoin: eventual consensus under forks, the script language and payment channels, with Lightning as the network of hash-locked channels (payments that unlock when a secret is revealed). The ledger model is fixed there: unspent transaction outputs, proof of work and a longest-chain rule. This lecture keeps the ledger and changes the language, the state model, the consensus resource and the mining function.

Where It Goes NextWhat This Lecture Adds

Ethereum adds a Turing-complete virtual machine: contracts compile to EVM (Ethereum Virtual Machine) bytecode, every node executes them and gas (a fee on computation) prices each opcode (machine instruction). The ledger becomes a state machine: accounts carry nonces (transaction counters) and balances, contracts carry code and storage. The block header commits to a state root (a hash of the entire account state). Under Ethereum's retired proof-of-work design, fast blocks produced stale blocks outside the main chain. Later blocks could cite them as uncles under a GHOST (Greedy Heaviest-Observed Sub-Tree) inspired design. Cardano enters through Ouroboros, where slot leaders are sampled by stake and security is stated with forkable strings (a worst-case measure of how the chain can fork). Algorand replaces the chain race with a committee protocol: secret sortition (a cryptographic lottery) picks a leader and verifiers, and Byzantine agreement (a vote that tolerates malicious members) certifies the block. Litecoin changes the hash function to scrypt and makes memory the mining resource.

Study PlanWhat to Read, in Lecture Order

  1. Why alternative currencies: the six limits of Bitcoin that the deck lists plus the design choice each alternative changes.
  2. Ethereum and smart contracts: the history through the DAO (Decentralized Autonomous Organization) fork, the EVM (Ethereum Virtual Machine), and gas as the price of Turing completeness.
  3. Accounts and state: externally owned accounts versus contract accounts and the state map. Study the comparison with Bitcoin's Unspent Transaction Output (UTXO) model.
  4. Historical uncles and the GHOST (Greedy Heaviest-Observed Sub-Tree) rule: stale blocks under pre-Merge proof of work, uncle rewards and the memory-hard Ethash Directed Acyclic Graph (DAG).
  5. Litecoin and scrypt: the two-phase construction, Percival's $S \cdot T \in \Omega(N^2)$ bound, and cumulative memory complexity.

AnimationEthereum Executes Against State

The stage below steps through one transaction: the account state before and the signed transaction, followed by execution that increments the nonce (the account's transaction counter) and moves value. The final step shows the state root that commits to the result.

AnimationCardano and Ouroboros Slot Elections

Ouroboros is the proof-of-stake (consensus where stake replaces hash power) protocol behind Cardano. The stage shows an epoch of slots, the stake-weighted election of leaders and chain growth. It also shows the private fork that stays short with exponentially small probability.

Animation and LabAlgorand Sortition (Committee Selection by Lottery)

Algorand elects a committee without publishing it. The stage shows stake bars, private draws, the elected committee and the voting steps. The lab runs the same draw on ten users with adjustable adversary stake.

Lab

Secret Cryptographic Sortition

Ten users hold stake. Each draws $h_i$ and is elected when $h_i < p_i = K s_i / 100$. The leader is the elected user with the smallest $h_i$.

-committee size
-honest stake share
-leader

LabLitecoin and the Memory Tradeoff

The lab builds the scrypt chain and answers random queries with fewer stored checkpoints. The mean recomputation approaches half the checkpoint spacing. The printed bound is Percival's.

Lab

Scrypt and the Time-Memory Tradeoff

Build the chain $V_i = \Hash(V_{i-1})$, then answer random queries with fewer stored blocks. The toy hash is 32-bit FNV-1a (Fowler-Noll-Vo); the tradeoff structure is Percival's.

-mean recomputed hashes
-predicted gap/2
-Percival lower bound

PracticeExercises for This Lecture