Hash table quiz: h(w) = length(w) mod 5. Joe (length 3) →
slot 3, but Sue is there.
Collision - weakness of
this hash function.
A hash pointer contains a pointer to data and the cryptographic hash of that data. With it we can get the data and verify it hasn't changed.
Build data structures with hash pointers. A linked list with hash pointers = blockchain.
Each block: data + prev: H(block). Last
block's hash = root. Append by adding block, computing its hash,
storing as new root.
If attacker changes data in a block → hash mismatch in next block's pointer. Changing that hash cascades; root changes. Remembering one root suffices to detect any tampering.
Only you can sign; anyone can verify. Signature is tied to a document - can't cut-and-paste.
Requirements: valid signatures verify; adversary with pk and chosen-message access cannot forge signatures.
If verify(pk, msg, sig)==true, think: pk says "[msg]". To speak for pk you must know sk.
Simplest cryptocurrency: Goofy can create new coins; new coins belong to creator. Owner can spend using crypto.
Goofy creates CreateCoin[uniqueCoinID], signs with
pkGoofy. String + signature = coin. Anyone can verify.
To transfer: create Pay to pkAlice: H(coin),
sign as owner. Recipient can pass on again by creating new Pay
statement signed by them.
Alice pays same coin to Bob and Chuck with two signed statements. Both have valid-looking claims. Main design challenge in digital currency. GoofyCoin does not solve it.
| Type | Characteristic |
|---|---|
| Hot | Connected to internet |
| Cold | Offline |
| Desktop | Laptops, PCs |
| Mobile | QR code, instant payments |
| Online | Cloud-provided |
| Hardware | Top-grade cryptography |
Designated entity (Scrooge) publishes an append-only ledger. All transactions written before acceptance. Prevents double-spending by visibility.
Blockchain signed by Scrooge. Each block: transactions + hash pointer to prev. Scrooge signs final hash. Optimization: multiple transactions per block. Blockchain + signature = append-only - changes cascade and are detectable.
Creates new coins. Each has (num, value, recipient). Valid if signed by Scrooge.
Consumes (destroys) coins; creates new coins of same total value. Valid if: consumed valid, not already consumed, value in = value out, signed by all owners of consumed coins.
Coins never changed, subdivided, or combined directly. Use transactions to do so.
Scrooge prevents double-spending but has too much power: can refuse to endorse, demand fees, create coins for himself. Cryptocurrencies with central authority have failed to take off.
To decentralize: (1) single published blockchain, (2) agreement on valid transactions, (3) agreement on which occurred, (4) decentralized ID assignment, (5) decentralized mining.
Requirements: all correct nodes decide same value; value proposed by some correct node. Bitcoin: peer-to-peer; Alice broadcasts tx to all nodes; Bob's computer may be offline.
Nodes crash, malicious; network imperfect (faults, latency); no global time. Bitcoin: uses incentives; embraces randomness; consensus over long timescale (~1 hour).
| Name | Description |
|---|---|
| Spacebit | Globally accessible blockchain via nanosatellites |
| GetGems | Social platform, crypto for viewing ads; popular in Uzbekistan |
| Dogecoin | P2P; charitable (Jamaican bobsled 2014) |
| Paycoin | White paper: new blockchain variations |
| DAO | Largest crowdfund; smart contract exploit, ~$50M loss |
Creator includes special coin-creation tx (e.g., 25 BTC); halves every 4 years. Collectible only if block in long-term consensus. Finite supply; ~2040.
Output < input; remainder = fee to block creator. Voluntary tip now; may become primary when block reward ends.
Pick node in proportion to resource no one can monopolize. Proof-of-work: proportional to computing power. Alternative: proof-of-stake (ownership).
Find nonce s.t. H(nonce ‖ prev_hash ‖ tx ‖ … ‖ tx) is
very small (below target). Only way: try nonces until lucky.
Attacks infeasible if majority of miners (by hash power) follow the protocol.
| Action | Possible? |
|---|---|
| Steal coins from existing address | No - signatures |
| Suppress tx from blockchain | Yes - refuse to extend |
| Suppress tx from P2P network | No - broadcast |
| Change block reward | No - system rules |
| Destroy confidence | Yes |