Chapter 7 · Lectures 19 to 20

Alternative Currencies

Bitcoin showed that a public ledger can operate without a trusted center. This chapter studies alternative designs: Ethereum runs programs, Litecoin makes mining memory-intensive, Ouroboros and Algorand assign influence by stake, proofs of space use disk capacity and Zerocash hides transaction details.

What went wrong. In August 2020 an attacker reorged 3,693 blocks of Ethereum Classic and double spent about 807,000 ETC, worth roughly $5.6 million. Renting the hash power cost a small fraction of that, the core weakness of low-hash-rate proof of work chains.

133 slides 5 stages 4 labs 8 exercises Source: 07_Alt_Curr.pdf
How this chapter maps onto the lectures

Lecture 19 (27/11/25) is sections 1 to 5: why alternative currencies, Ethereum and smart contracts, accounts and state, Ethereum's former uncle-block design, Litecoin and scrypt. Lecture 20 (02/12/25) is sections 6 to 13: proof of stake, Ouroboros, Algorand, Byzantine agreement, proofs of space and Filecoin, Permacoin and Primecoin, and Zerocash. Study plans: Lecture 19, Lecture 20.

Section 1Why Alternative Currencies

Lecture 19.

Bitcoin is a ledger with a deliberately narrow scripting language. The deck opens with a contract it cannot express directly: one payment conditioned on an external event, with a different action for each counterparty. Bitcoin Script can check signatures and timelocks, while more elaborate conditions require separate transactions.

The deck lists six limits of Bitcoin and the design choice Ethereum makes for each:

What went wrong. In November 2017 one accidental kill call on a shared Parity library contract froze about 513,000 ETH. Shared code can destroy funds with no thief involved.

Common mistake. Bitcoin and Ethereum are rivals trying to be the same thing. Bitcoin aims at conservative digital scarcity with minimal change. Ethereum is a general-purpose settlement layer that runs programs. Different goals justify different trade-offs in issuance, scripting and governance.

The rest of the chapter changes one parameter at a time. Litecoin makes the hash function memory hard, proof of stake replaces computation with currency, proofs of space replace it with disk, and Zerocash makes the ledger private.

Takeaway

An alternative currency is a design experiment: keep the public ledger, change one resource, language or privacy property and prove that the ledger still agrees.

Section 2Ethereum and Smart Contracts

Lecture 19.

In April 2016 the DAO, a decentralized autonomous organization written as a contract, collected 160 million dollars. In June 2016 an attack on its code drained the funds, and in July 2016 the community applied a hard fork (a protocol change that splits the chain) to reverse the drain.

History

Vitalik Buterin announced Ethereum in January 2014. The July 2014 presale raised 18 million dollars. The first release, Frontier, appeared in July 2015 and the second, Homestead, in March 2016.

The term is older than Ethereum. Nick Szabo proposed smart contracts in the 1990s, with the vending machine as his example. The terms of the deal are built into the mechanism, so payment and selection trigger delivery, with no cashier and no third-party enforcement. An Ethereum contract is the same idea in software, with code as the terms and the network as the enforcer. Whether that code forms a legally binding contract is a separate question; a smart legal contract would need a link to law that the chain does not provide.

The DAO drain is the security case study. The attacker called the DAO's withdraw function repeatedly, each call running before the contract updated its balance. The contract paid every call because each one was valid under its own code. The fork is the standing example that contract code is enforced exactly as written and that governance enters only when the code fails to capture the intent.

What went wrong. Recursive calls to the withdraw function drained 3.6 million ETH in 2016. Each call ran before the balance was updated. The lesson: update balances before calling external code, the checks-effects-interactions pattern.

Contracts are written in high-level languages: Solidity, which resembles JavaScript; Serpent, which resembles Python; and LLL, a Lisp-like language. The compiler emits EVM (Ethereum Virtual Machine) bytecode, a low-level stack-based language. Every Ethereum node runs the EVM, so a deployed contract is executed by the whole network. The language is Turing complete, so execution must be metered.

The meter is gas. It exists to stop denial-of-service abuse. Every transaction pays in proportion to the computation, bandwidth and storage it uses. Every opcode (an operation code) has a gas cost: ADD costs 3, MOD costs 5, KECCAK256 has a base cost of 30 and CREATE has a base cost of 32000. A plain ether transfer has an intrinsic cost of 21000 gas. As a lower-bound example, consider a contract call that runs 100 ADDs, 10 zero-length KECCAK256 operations and 1 CREATE. Memory expansion, transaction data and deposited contract code add further costs:

OpcodeCountGas eachSubtotal
ADD1003300
KECCAK256, base1030300
CREATE, base13200032000
Lower bound32600

The listed operations consume at least 32600 gas before their dynamic costs and transaction-level costs are counted. The sender commits to a gas budget in advance. If execution exceeds the budget it stops, all state changes are reverted and the consumed gas is still charged. Under Ethereum's current fee mechanism, the protocol burns the base fee and pays the priority fee to the block proposer. Users can raise the priority fee to bid for inclusion. This is the economic form of the halting problem: arbitrary code may run, although infinite execution is priced out.

The block time bounds throughput. The scaling work is organized by the scaling trilemma: decentralization, security and scalability pull against each other, because larger or more frequent blocks raise the cost of running a node and concentrate validation on the machines that can keep up. Ethereum's answer is layer-2 rollups. A rollup executes transactions off the main chain and posts the transaction data back to it, so the main chain's security covers the rollup, and rollups are distinguished from sidechains by that data placement, since a sidechain keeps its own data and its own consensus. An optimistic rollup accepts a batch unless a fraud proof appears within a challenge window, and a zero-knowledge rollup posts a validity proof with each batch.

Common mistake. The Merge made Ethereum faster and cheaper. The September 2022 Merge swapped the consensus mechanism and little else. Block time moved from about 13 seconds to a fixed 12. Fees stayed set by demand; cheaper transactions depend on the layer-2 rollups above.

Subtlety

Turing completeness moves the risk from the protocol to the contract. Gas bounds how long execution runs. It says nothing about what the code does. The DAO drain followed the contract's code exactly.

Section 3Accounts and State

Lecture 19.

The basic object in Ethereum is the account. An account holds an address of 20 bytes, a nonce, an ether balance and, for a contract account, code and storage. There are two kinds. An externally owned account is controlled by a secret key. The key holder signs its transactions. A contract account is controlled by its code. It acts only when a transaction calls it. The nonce of an externally owned account counts the transactions sent by that account, so a replayed transaction carries an old nonce and is rejected.

Ethereum keeps this state as an explicit map from every account to its data, beside the blockchain. The contrast with Bitcoin is the state model:

BitcoinEthereum
StateThe set of unspent transaction outputsA map from every account to its data
BalanceDerived: the sum of all Unspent Transaction Outputs (UTXOs) payable to one keyStored in the account
Header commits toThe Merkle root (the root hash of a tree of hashes) of the transactionsA Merkle Patricia root (the root of a hash tree over the account map) of the state

Transactions change the state, so the state can be recomputed from the blockchain by replaying every transaction. Because the header commits to the state root, a node can prove the value of any account against it.

Takeaway

Bitcoin answers "which coins are unspent?" while Ethereum answers "what is the state of every account and contract?" The second question needs a state root in the block header. The state root is what every full node recomputes.

Worked number. Suppose 34 million ETH is staked. A buyer seeking one third of the resulting total must acquire more than 17 million ETH, because each purchase also grows the denominator. At $2,500 per ETH that exceeds $42 billion before price slippage.

Section 4Historical Uncles and the GHOST Rule

Lecture 19.

This section describes Ethereum before the Merge. Under proof of work, blocks arrived roughly every 13 to 15 seconds. Two miners could find blocks at nearly the same time, leaving one outside the main chain as a stale block. Ethereum allowed a later block to cite that stale block as an uncle, also called an ommer. Its miner received a distance-dependent reward. The citing block also received a small reward. A block could name at most two uncles from a limited recent depth.

The design drew on GHOST, the greedy heaviest observed subtree protocol. Uncle rewards reduced the penalty suffered by miners whose valid blocks lost a short propagation race. This helped limit the centralizing effect of network lag.

Ethereum's former proof-of-work algorithm, Ethash, was designed to be memory hard. Every 30000 blocks, about 5.2 days, the protocol generates a directed acyclic graph. Mining requires lookups in that graph, so the miner must precompute and hold it. Verification does not need the graph, so checking a block stays cheap. The memory requirement follows the same design principle as scrypt in the next section: make the expensive resource one that specialized compute cannot skip.

Ethereum retired mining and uncle production in the September 2022 Merge. Current Ethereum uses proof-of-stake validators. Its fork choice is based on validator attestations, and ommer lists remain empty.

Section 5Litecoin and Scrypt

Lecture 19.

Litecoin was released in October 2011 by Charles Lee. It replaces SHA-256 with scrypt, the sequential memory-hard function of Colin Percival (2009), originally proposed to slow offline password guessing. The hash computation must hold a large table in memory, so custom hardware gains little from faster arithmetic alone. The deck records a market capitalization of about 2 billion EUR, with 1 LTC near 30 EUR at the time of writing.

The function has two phases. The initialization phase builds a chain $V_0 = X$, $V_i = \Hash(V_{i-1})$ for $i = 1, \ldots, N$. The second phase starts from $Y = \Hash(V_N)$ and repeats $N$ steps: set $j = Y \bmod N$, then $Y = \Hash(Y \oplus V_j)$. Each step reads one entry $V_j$ selected by the current value of $Y$, so the sequence of reads is unpredictable until the computation runs. The table $V_0, \ldots, V_N$ is where the memory lives.

Percival's result states that scrypt runs in time $O(N)$ and that any computation of it with time $T$ and maximum space $S$ satisfies $S \cdot T \in \Omega(N^2)$, even on parallel machines. Alwen and Serbinenko observed that this maximum-space bound is weak, because a parallel adversary can amortize space across many instances. The right measure is cumulative memory complexity, the sum of the memory actually held at each point in time. Alwen et al. (2016) prove that scrypt is maximally memory hard under that measure.

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 the 32-bit FNV-1a (Fowler-Noll-Vo) hash; the tradeoff structure is Percival's.

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

scrypt prices memory. A miner that stores fewer checkpoints must recompute the missing links, and Percival's bound says that the product of space and time stays large.

Section 6Proof of Stake

Lecture 20.

Bitcoin runs a lottery: the probability of proposing the next block is proportional to the fraction of computing power. Proof of stake runs the same lottery with a different ticket. The probability of winning becomes proportional to the amount of money, the stake, associated with each public key. Shares of coins become voting power. Validators are chosen by stake. The motivation is cost: proof of work pays for security with energy and hardware. A stake-weighted draw runs the lottery without the mining expense.

Context. Proof of stake predates Ethereum. A 2011 Bitcoin Forum thread proposed it, Peercoin deployed an early version in 2012 and later designs address attacks such as nothing-at-stake and long-range history revision.

The attacks follow from cheap block production. In proof of work, producing a block costs real energy. That cost disciplines the miners. Signing a block costs almost nothing, so:

Worked number. A lone slashed validator loses part of its stake immediately and continues to incur penalties. A correlation penalty grows when many validators are slashed around the same time, so a coordinated attack can consume the validator's full 32 ETH balance.

The design responses name the deployed chains. Ethereum replaced Ethash proof of work with proof of stake in September 2022, in an event called the Merge. Each validator stakes 32 ether. Blocks are assigned in 12-second slots. A validator that signs two blocks at the same height forfeits its stake. That penalty answers nothing-at-stake, and finalized checkpoints answer long-range attacks by making old history irreversible. Cardano runs Ouroboros, where each epoch ends with fresh randomness for the next epoch's leader election, and Algorand hides the selection itself, as section 8 shows.

Worked number. A slot lasts 12 seconds and 32 slots form an epoch of 6.4 minutes. Under normal participation, checkpoints become justified and then finalized across successive epochs, so finality usually takes about 13 minutes.

The formal assumption is an honest majority of money. The assumption is weaker than it sounds, because money can buy computing power, so the two resources are convertible. The chapter therefore treats proof of stake as a cryptographic problem: how to sample the next leader from the stake distribution without giving the adversary control over the sample. Three constructions in the deck carry proofs. Ouroboros (Kiayias et al., 2017) generates clean randomness with cryptography. Snow White (Bentov et al., 2019) and Ouroboros Praos (David et al., 2018) use hashing with care. Algorand (Chen and Micali, 2017) also relies on hashing, and follows a different route based on Byzantine agreement.

Attack cost. A proof-of-stake attacker must buy and lock a large share of the stake. Protocol rules can slash provable misbehavior, while social recovery can select a fork on which the attacker's stake has no value.

Section 7Ouroboros

Lecture 20.

The synchronous setting divides time into slots, also called rounds. Messages move through a diffusion mechanism, so a message sent to an honest party is delivered by the end of the slot. The adversary is rushing: it can spoof, inject and reorder messages. The assumptions are that the adversary controls a minority of the stake, that corruptions are delayed and that stake shifts at a bounded rate.

With static stake, each slot is assigned to a party sampled with probability proportional to stake. The elected party signs the block of that slot. Ties are resolved by the longest-chain rule. The deck records the slot sequence as a characteristic string of Bernoulli trials with parameter $1/2 - \varepsilon$. Two adversary advantages appear relative to proof of work: the adversary sees the schedule of leaders in advance and can produce many different blocks for the same slot at no cost.

A characteristic string is forkable when it admits two disjoint paths of the same maximum length. No string of density at most $1/3$ is forkable, while every string of density at least $1/2$ is forkable. The probability that a binomial string with parameter $1/2 - \varepsilon$ is forkable is at most $e^{-\Omega(k)}$, so a chain that is $k$ blocks deep is forkable with exponentially small probability.

With dynamic stake, time is divided into epochs. Each epoch ends with fresh randomness, implemented with cryptography. The next epoch samples leaders from the updated stake. The theorem assumes a corruption delay of $2R - 4k$ slots and gives the standard backbone properties: common prefix with parameter $k$, chain quality, and chain growth with $\tau \ge 1/2$ and $s \ge 2k$. The deck also states an incentive result: a reward mechanism makes following the protocol an approximate Nash equilibrium (no participant gains by deviating alone).

Takeaway

Ouroboros replaces hash power with stake-weighted slot elections. The security statement is a theorem about forkable strings. The probability of a successful fork decreases exponentially in the depth $k$.

Section 8Algorand and Secret Sortition

Lecture 20.

Algorand was developed by a team led by Silvio Micali. The stated goals are a truly distributed system with no concentration of power, no wasted computation, no forks except with negligible probability, and scalability limited by network latency. The adversary model is strong: the adversary can corrupt any honest user immediately, corrupted users coordinate perfectly, and communication is by gossip over a complete asynchronous network where the adversary sees every message from an honest user to a corrupt one. A message sent by an honest user reaches 95% of the honest users, with some latency. The assumption is an honest majority of stake and bounded stake shifts.

Each round selects a leader who assembles and propagates the next block. A set of verifiers reaches agreement on the proposed block. The selection is sortition: automatic, random and weighted by stake. The public value $Q^{r-1}$ associated with the last block seeds the draw. If the outcome were publicly verifiable before the round, the adversary could corrupt the selected users. The outcome is therefore secret: each user obtains a credential proving selection, while the adversary learns the committee only after the committee has spoken.

The mechanism uses unique signatures, where every message has at most one valid signature even under a malicious key. Let $\mathrm{sig}_i(m) = \mathbf{S}(sk_i, \Hash(m))$ and $\mathrm{SIG}_i(m) = (i, m, \mathrm{sig}_i(m))$. User $i$ is the leader of round $r$ when $\Hash(\mathrm{SIG}_i(r, 1, Q^{r-1})) \le p$. Only user $i$ can check the inequality. The credential $\sigma_{i,r} = \mathrm{SIG}_i(r, i, Q^{r-1})$ lets everyone verify the claim afterwards. Verifiers for step $s$ of round $r$ are selected by the same test with $s$ in place of $1$ and a threshold $p'$ chosen so that at least $2/3$ of the verifiers are honest with high probability.

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
Takeaway

Sortition turns stake into a committee without announcing the committee. The credential is published with the first message, so corruption arrives too late to change the draw.

Section 9Byzantine Agreement and Dolev-Strong

Lecture 20.

Once the leader is selected, the verifiers must agree on the proposed block. This is Byzantine agreement, due to Pease, Shostak and Lamport (1980). The agreed block is then certified with digital signatures and propagated to the network.

The classical statement is the Byzantine generals problem. There are $n$ parties connected by point-to-point channels, at most $t < n$ of them malicious. Each party $P_i$ inputs a bit $b_i$ and outputs a bit $\hat b_i$. The requirements are termination, agreement ($\hat b_i = \hat b_j$ for honest $P_i, P_j$) and consistency (if all honest inputs equal $b$, then all honest outputs equal $b$). Either property alone is trivial; the content is holding both in the presence of cheaters.

The deck lists the standard facts. At least $t$ rounds are necessary to tolerate $t$ corruptions deterministically. Randomization helps: Rabin (1983) tolerates $O(\sqrt n)$ corruptions in $O(1)$ rounds, and Feldman and Micali (1988) tolerate $n/4$ corruptions in expected $O(1)$ rounds. Without a public-key infrastructure, Byzantine agreement is possible exactly when $t < n/3$. With signatures, Dolev and Strong (1983) tolerate any $t < n$. Turpin and Coan (1984) extend binary agreement to arbitrary values with two extra rounds.

Broadcast is the sender variant: one sender $P_s$ holds the input, and all honest parties must output the same value, equal to the sender's value when the sender is honest. If $t < n/2$, a broadcast channel implies Byzantine agreement: everyone sends its input over broadcast and outputs the majority. The Dolev-Strong protocol implements broadcast with a public-key infrastructure and tolerates any number of corruptions below $n$.

Each party $P_i$ keeps a set $\mathrm{ACC}_i$ of accepted values and sets $\mathrm{SET}_{i,v}$ of signatures received on value $v$. In round 0 the sender sends $(v, \sigma)$ with $\sigma = \mathbf{S}(sk_s, v)$ and terminates with $v$. In round $r = 1, 2, \ldots$, if $P_i$ receives $(v', \mathrm{SET})$ containing valid signatures on $v'$ from at least $r$ parties including the sender, then $P_i$ adds $v'$ to $\mathrm{ACC}_i$, adds the signatures to $\mathrm{SET}_{i,v'}$, and if $v'$ is new, signs it and forwards the enlarged set. In the final round, $P_i$ outputs 1 if $\mathrm{ACC}_i = \{1\}$, and 0 otherwise.

Consistency follows because an honest sender signs only one value and no other value can carry the sender's signature. Agreement follows because if a corrupt sender signs both values, every honest party sees both by the final round and both output the default 0.

Lab

Dolev-Strong Broadcast

Pick the number of parties, the number of corrupt helpers, and the sender's behavior. Signatures cannot be forged, so a value appears in $\mathrm{ACC}_i$ only when the sender signed it.

-rounds R = t + 1
-agreement
-common decision
Takeaway

Signatures change the threshold. Without a PKI the bound is $t < n/3$; with a PKI, Dolev-Strong reaches agreement for every $t < n$, at the price of $t+1$ rounds.

Section 10Byzantine Agreement Made Simple

Lecture 20.

Micali (2017) gives a protocol tolerating $n/3$ corruptions in expected 6 trivial rounds, using a Public-Key Infrastructure (PKI). The setup assumes that every player has a public key $pk_i$ and that a random string $R$ is independent of the keys. Two idealizations are used: unique signatures, so for every $pk_i$ and message $m$ there is at most one valid signature $\mathrm{SIG}_i(m)$; and a random oracle, so $\Hash(\mathrm{SIG}_i(m))$ behaves as a unique random string.

A generic round starts with a counter $\gamma$, initially 0. Each player collects votes $(b_i^{\text{old}}, \mathrm{SIG}_i(R, \gamma))$ from willing players. If more than $2n/3$ votes are 0, the player sets $b_i^{\text{new}} = 0$. If more than $2n/3$ votes are 1, it sets $b_i^{\text{new}} = 1$. Otherwise it computes $\rho_i = \min_i \Hash(\mathrm{SIG}_i(R, \gamma))$ and sets $b_i^{\text{new}} = \mathrm{lsb}(\rho_i)$, the low-order bit of the minimum. The counter then increments. The minimum acts as a shared coin: nobody controls which player's signature wins. The winner's bit is unbiased enough for the analysis.

If agreement on 0 exists, agreement on 0 is kept. The same holds for 1. If some player sees more than $2n/3$ zeros, no other player can see more than $2n/3$ ones, so the others follow the coin rule. The coin bit comes from an honest player with probability $2/3$, and agreement is reached with probability $1/3$ in every round. Players do not know when agreement happens, so the simple solution repeats for a large $k$, say $k = 300$. The efficient solution runs three correlated executions, one with the coin fixed to 0, one with the coin fixed to 1, and one with the real coin; the first two tell the players when agreement has been reached.

Algorand adapts the protocol in three ways. Gossip replaces multicast. The honest majority is a majority of money, and user counts no longer define it. The fixed string $R$ is replaced by a per-round value $Q^r$ derived from the previous value by a unique signature, with a probabilistic argument that the adversary cannot influence $Q^r$. Player replaceability handles the last issue: each round runs with a fresh set of players, so corrupting the entire committee of one round does not compromise the next round.

Subtlety

The deck closes the Algorand part with a game-theoretic attack due to Houy (2014): an adversary announces the intention to buy more than half of the coins. If holders believe the attack will succeed, the price falls, so the adversary buys cheaply. The defense is economic as much as cryptographic: the value of the coin depends on the belief that the coin will keep its consensus.

Section 11Proofs of Space, SpaceMint and Filecoin

Lecture 20.

Proofs of space replace computation with disk space. The construction in the deck is SpaceMint, based on Dziembowski et al. (2015) and Park et al. (2015). No dedicated hardware helps, energy waste drops, and users can contribute unused disk space. The same idea applies outside currencies: a service can force each account to allocate a large amount of local space and periodically verify that the space is still allocated, which raises the cost of opening many fake accounts.

The protocol has two phases. In Init, the prover receives an identity $id$ and a size $N$, and fills $N$ blocks of length $L$. In Proof, the verifier sends a challenge and the prover answers with a small amount of data. The security properties are completeness, soundness (a cheating prover must still waste a large amount of memory) and efficiency. The trivial construction sends a random string $R = (R_1, \ldots, R_N)$ and later asks for a random subset of $k$ positions. The verifier work and communication are too large. The efficient target is polylogarithmic verifier time, $\mathrm{poly}(\log N, k)$, with prover Init time $\mathrm{poly}(N)$ and proof time $\mathrm{poly}(\log N, k)$.

The technical core is a time-memory tradeoff. A cheating prover stores $N' \ll N$ blocks and recomputes the rest. The construction labels the vertices of a directed acyclic graph $G$ with $N$ vertices: each label depends on the labels of its parents, as $R_i = \Hash_{id}(i, R_a, R_b)$. A bad graph can be relabeled quickly from a small stored set; a good graph cannot. The proof of existence uses graph pebbling (placing pebbles on vertices to model memory use over time). The labels are committed in a Merkle tree (a tree of hashes whose root commits to every leaf), so the prover publishes only the root. Each proof reveals $k$ labels with Merkle authentication paths. The theorem gives an $O(N)$-space, $O(N)$-time proof of space.

SpaceMint turns this into a currency. A joining user declares a memory size, generates $(pk, sk)$, computes $R = f(pk)$ and the commitment $C = \mathrm{Merkle}(R)$, and broadcasts a commit transaction with $(pk, C)$. For each block, a random challenge $x$ is derived. Every miner produces a proof $s_i$. The winner maximizes a score. With equal memory sizes, each miner wins with probability $1/k$, because the answer is fixed by $C$ and $x$. With unequal sizes $N_i$, the score becomes $D_{N_i}(s) = (\mathbf{G}(s)/W)^{1/N_i}$, which restores proportionality. The challenge must not be grindable (an attacker must not be able to bias it by trying many values), so it depends on the previous block's signature and ignores the transaction list, and forks are handled by taking the challenge from a block far enough in the past. Since mining on several forks costs nothing, SpaceMint penalizes a miner who signs competing blocks at the same height.

Filecoin applies the same resource to useful data. Clients pay providers for storage, providers post periodic proofs that they still hold the data and the chain records the agreements. Proof-of-work hashes are discarded after computation; Filecoin's stored bytes continue to serve clients.

Takeaway

A proof of space is a Merkle commitment to a graph labeling that is cheap to check and expensive to fake. The resource being proven is disk. The verifier reads only a logarithmic amount of it.

Section 12Permacoin and Primecoin

Lecture 20.

Permacoin parametrizes proof of work with a large public file, too large for one individual to store, such as a library archive. To solve a puzzle, a miner stores parts of the file; the more is stored, the higher the chance of winning. Permacoin differs from SpaceMint in that it remains a proof of work; its stored data is fixed and useful where SpaceMint's labels are random; and it scales less well. A useful feature is that the puzzles are non-outsourceable: a miner in a pool can steal the solution, so mining pools (groups that share the mining work and split the rewards) lose their point.

Primecoin replaces hashing with the search for chains of primes. A Cunningham chain of the first kind satisfies $p_{i+1} = 2p_i + 1$; the deck's example is $2, 5, 11, 23, 47$. A Cunningham chain of the second kind satisfies $p_{i+1} = 2p_i - 1$. The deck's example for the second kind starts $151, 301, 601, 1201$, and $301 = 7 \cdot 43$ is composite, so that example is not a chain; a correct short chain is $1531, 3061, 6121$. A bi-twin chain interleaves two such chains with twin prime pairs.

Verification must stay fast, so Primecoin limits the size of the primes and allows pseudoprimes (composites that pass the test without being prime), checked with the Fermat test $2^{n-1} \equiv 1 \bmod n$. The quality of a chain is $k + r$, where $k$ counts the true primes in the chain and $r$ measures how close the last candidate is to passing the Fermat test. The solution is linked to the ledger by requiring $p_1 + 1$ to be a multiple of $\Hash(B_i)$, where $B_i$ is the previous block.

Takeaway

Permacoin and Primecoin both make the mining resource useful or mathematically interesting: Permacoin stores data and Primecoin searches prime chains. Each keeps proof of work while changing what the work computes.

Section 13Zerocash

Lecture 20.

Bitcoin's ledger is public. The privacy cost follows directly. A purchase exposes timing, amount and merchant, an account balance is revealed in every transaction. A merchant's cash flow is exposed to competitors. Although the addresses are pseudonyms, the transaction graph plus side information turns addresses into names; the deck cites the FBI investigation of Silk Road as a concrete case. The standard mitigations, fresh addresses per payment and mixing with other users, make analysis harder. The blockchain still keeps the trail forever.

The economic issue is fungibility. A dollar is a dollar regardless of its history. Bitcoin coins carry a public pedigree, so the same coin can be valued differently depending on its past, price discrimination becomes possible, and miners can censor transactions with disfavored histories. Zerocash attacks the problem at the ledger level.

Zerocash is a privacy-preserving cryptocurrency that can sit on top of Bitcoin or a similar system. A transaction reveals none of the origin, the destination or the amount. The ledger carries commitments and proofs. The proof system is a SNARK: an argument that is non-interactive, zero-knowledge, a proof of knowledge and succinct, with short proofs and cheap verification.

The deck derives the construction in six attempts:

POUR transactions (named for pouring value from old coins into new ones) are the single transaction type of the final system: old coins go in, two new coins and an optional public amount come out, with the balance checked by the proof. The security definition for decentralized anonymous payments has three parts:

The recorded performance: proofs are 288 bytes at 128 bits of security, verification takes under 6 ms, proof creation takes under one minute. The system parameters are 869 MB generated once. Parameter generation requires a trusted setup (a one-time ceremony whose secret randomness must be destroyed). The cryptographic assumptions include elliptic curves with pairings, knowledge-of-exponent assumptions, SHA-256, encryption and signatures.

Lab

Commitments, Nullifiers (serial Numbers Published When a Coin Is Spent) and Double Spends

Alice holds a shielded coin of value 100. She transfers part of it to Bob. The ledger sees commitments and one nullifier, so the amounts stay hidden.

-commitments in tree
-nullifiers used
-verdict
Takeaway

Zerocash keeps the public check and removes the public content. The ledger checks that one commitment was consumed and two new commitments are well formed. It learns nothing else.

Section 14Further Resources

Section 15Exercises

A transaction budgets 100,000 gas. Its contract execution consumes 120,000 gas. What does the node do with the state changes and the fee? Why does a Turing-complete EVM need this rule? Drill

All state changes are reverted. The consumed gas is still charged: the base fee is burned and the priority fee goes to the block proposer. The rule is the economic form of the halting problem: the EVM accepts arbitrary code, so execution can run longer than any fixed bound. An exhausted budget stops the execution while still paying for the resources already consumed.

For scrypt with $N = 2^{20}$ blocks, a miner stores $S = N/4$ checkpoints. What is the expected number of recomputed hashes per random query, and what does Percival's bound $S \cdot T \in \Omega(N^2)$ force for the total time? Drill

The checkpoint spacing is $N/S = 4$. A random index lies on average $4/2 = 2$ steps after the nearest stored checkpoint, so the expected recomputation is 2 hashes per query. Percival's bound gives $T \ge N^2/(2S) = N^2/(N/2) = 2N$ hash evaluations in total for a computation that holds at most $S$ blocks, against $2N$ for the honest full-table run. The lab shows the same tradeoff with exact counts for the toy hash.

In Ouroboros, the adversary can produce many blocks for the same slot at no cost. Why does this still not make forks likely, and what is the bound on the probability that a characteristic string with parameter $1/2 - \varepsilon$ is forkable? Attack

Producing many blocks for one slot changes the adversary's options. It does not change the density of the characteristic string. A string of density at most $1/3$ is never forkable, while a binomial string with parameter $1/2 - \varepsilon$ is forkable with probability at most $e^{-\Omega(k)}$, so overtaking a chain $k$ blocks deep stays exponentially small in $k$.

A user holds stake $s_i = 5$ out of 100. The expected committee size is $K = 20$. Compute $p_i$ and decide whether draws $h_i = 0.04$ and $h_i = 0.12$ elect the user. Why must the draw stay secret until the user speaks? Drill

The threshold is $p_i = K s_i / 100 = 20 \cdot 5 / 100 = 1$, capped at 1, so the user is elected when $h_i < 1$, and both draws elect the user. With $s_i = 1$ the threshold would be $0.2$, so $0.04$ elects and $0.12$ does not. The draw must stay secret because the adversary can corrupt any user immediately; if the committee were known before it spoke, the adversary would corrupt the whole committee, so the credential is revealed only with the first message.

In Dolev-Strong with $n = 5$ and $t = 2$ corrupt parties including the sender, how many rounds does the protocol run, and what do honest parties output when the sender signs both 0 and 1? Why can a corrupt helper not introduce a third value? Attack

The protocol runs $t + 1 = 3$ rounds. If the sender signs both values, each honest party sees both signed values by the final round. The rule outputs 1 only when $\mathrm{ACC}_i = \{1\}$, so every honest party outputs 0. A corrupt helper cannot introduce a third value because acceptance requires the sender's signature on it, and signatures cannot be forged.

A proof of space commits $N = 2^{20}$ labels in a Merkle tree and answers $k = 30$ random challenges. How many labels and how many sibling hashes does the proof transmit, and why is the verifier work polylogarithmic? Drill

The proof transmits 30 labels. Each label needs an authentication path of $\log_2 N = 20$ sibling hashes, so the proof carries $30 \cdot 20 = 600$ hashes. The verifier checks each path against the committed root with 20 hash evaluations, for 600 hash evaluations total. Both communication and verifier time are $O(k \log N)$, which is polylogarithmic in $N$.

Primecoin accepts a chain $p_1, \ldots, p_k, p_{k+1}$ where all entries except the last are prime, and assigns quality $k + r$. Explain how the Fermat test enters $r$, and how the chain is linked to the previous block $B_i$. Drill

The last candidate $p_{k+1}$ is checked with the Fermat test $2^{p_{k+1}-1} \equiv 1 \bmod p_{k+1}$. The value $r$ measures how close the candidate comes to passing the test, so a strong pseudoprime raises the quality without being a proven prime. The chain is linked to the ledger by requiring $p_1 + 1$ to be a multiple of $\Hash(B_i)$, so the solution depends on the previous block header.

In Zerocash, a spend publishes a serial number $sn = \PRF(ask, \rho)$ and a proof about some commitment in the tree. Explain why a second spend of the same coin is detected, and why the detection does not reveal which commitment was spent. Attack

The serial number is a deterministic function of the coin's secret data, so spending the same coin twice publishes the same $sn$ twice. The ledger rejects repeats, which makes double spending public. The detection reveals nothing else because the proof only shows that some commitment in the tree opens to that $sn$; the commitment is never named, and all spends against the same anonymity set look identical.

Authorship

These pages are written by a student of the course. The mathematics is stated in the standard way, while the formulation is the author's own, taken from no slide. Errors are the author's alone. Prof. Venturi bears no responsibility for them; where this page and the PDFs differ, the PDFs are authoritative and only material in them is examinable.