Principles of Distributed Ledgers - Outline

Lecture 1

Cryptographic

• Cryptographic Hash Functions: Properties

• Merkle Trees

• Elliptic Curve Signature Algorithm (ECDSA): Nothing in Bitcoin is encrypted

Addresses

• BTC Address conversion

Transactions

• UTXO (Unspent transaction output): In cryptocurrencies such as Bitcoin, an unspent transaction output (UTXO) is an abstraction of electronic money. Each UTXO is analogous to a coin, and holds a certain amount of value in its respective currency. Each UTXO represents a chain of ownership implemented as a chain of digital signatures where the owner signs a message (transaction) transferring ownership of their UTXO to the receiver's public key.

• Coinbase Transaction: First transaction in a Block, defined by the miner. No inputs required.

Script

• Former UTXO: OP_DUP OP_HASH160 <PubKeyHash> OP_EQUALVERIFY OP_CHECKSIG

• Latter UTXO: <Sig> <PubKey>

• If evals to true \(\rightarrow\) Bitcoin transaction is valid

• Execution time is critical to prevent DoS attacks

• Transaction types: P2PKH; P2SH; Multisignature (m from n)

Wallet

Chain of Blocks

• Header: Block version; Hash of previous block's header; Merkle root; Unix time; Target; Nonce

Lightweight Clients

• SPV Transaction verification: Blockchain with headers only

Lecture 2

Proof of Work

• Find Nonce \(N\), s.t. Hash(Hash(\(B_{\rm former}\))|merkle root|\(N\)) \(<\) target

• Pool: Give proportional reward (pool's difficulty < Bitcoin's difficulty)

Merged Mining

• Assembles a transaction set for both block chains

• Hash the final namecoin block

• Creates a transaction containing this hash and inserts it in the Bitcoin transaction set at the tip of the tree (scriptSig)

• Assembles the final Bitcoin header with this transaction in it and sends out the work units

Mining Pool Dangers

• Influence which transactions enter the blockchain

• Inflate transaction fees/Ethereum gas price

• Collude with each other (to reach 51%, selfish mining)

• Network layer attacks

• Political and Regulatory danger

• Pool operators are trusted to pay out reward

• Influence voting mechanisms (cf. SegWit)

Decentralised Mining

• Each block of the share chain is a share

• Each share chain block has a lower difficulty than the bitcoin block chain

• Once a share satisfies the same difficulty as Bitcoin, it's a valid Bitcoin block

• Coinbase transaction is used for reward and tracking of share chain

Forks

• \(\mathcal{P}\): protocol; \(\mathcal{V}\): Validity set; \(\mathcal{N}\): difference between \(\mathcal{V}\) and \(\mathcal{V}^{\prime}\)

• Hard fork: Previously invalid blocks/transactions are make valid (and vice-versa)

• Soft fork: Only previously valid blocks/transactions are made invalid \(\rightarrow\) reducing functionality

• Segregated Witness

• Vote through blocks

Proof of Stakes/Authority

Lecture 3

Bitcoin and Smart Contracts

• Bitcoin Script: No support for loops

• Bitcoin Script Applications: Proof of Burn; Multisignature addresses; Pay-for-hash pre-image; Micropayment channels

Namecoin

Introduction to Ethereum

• Account Based model: No need to go through whole history; Sequence between any two blocks can be verified; Light clients can sync up quickly

Ethereum Blockchain Structure

• Ethereum Blockchain Structure

• Ethereum Merkle Patricia Tree

Ethereum Accounts and Transactions

• Types of transactions: send; create; call

Ethereum Virtual Machine

• Stack of max depth of 1024

• Memory is zero initialized

• Storage is very expensive (The cost of storing 1 kb is currently 6.4 USD)

Ethereum Transaction Fees

• Each opcode of the EVM has a certain gas cost

• Maximum GAS_LIMIT per block

• If GAS_LIMIT \(\times\) GAS_PRICE > accounts[from].balance, halt execution abruptly

  • accounts[from].balance -= value + gas \(\times\) gasprice

  • accounts[to].balance += value

  • execute(code)

  • accounts[from] += unusedGas \(\times\) gasprice

• If remaining GAS is 0 before termination, throw out-of-gas, and pay miners

Solidity

Lecture 4

Classical Consensus

• In a fully asynchronous system, there is no deterministic consensus solution that tolerates one or more failures

• No algorithm can always reach consensus in bounded time

Blockchain Bootstrapping

• Bootstrap Methods: DNS (Domain Name System) Bootstrap; Hardcoded IPs; Chat/Forums (dangerous)

• Bitcoin Node: TCP based, no authentication/encryption

Network Denial of Service Protection

• DoS Protection Mechanism: Sanity checks (size, encoding); Signature validation; UTXO/double spending validation

• DoS Protection Mechanism is a weakness (directly ban IP)

Network Gossip Protocol

• Standard Transaction/Block advertisement: Hash (36 bytes); Get request; Block

• Send Headers Block advertisement: Header (80 bytes); Get request; Block

• Unsolicited Block Push: Block

• Bitcoin Fibre: Block sketch; Construct; Correct error; Emit (UDP based)

Network Security - Eclipse Attacks

• Request timeouts: block: 20 min; transaction: 2 min

• Blind victim > 20 min: Double spending; Aggravated selfish mining; Network wide DoS

• Being first: connections of adversary:victim \(=800:40\), approximately 90%

• Transactions follow FIFO while Blocks don't

Eclipse Attacks - Delaying Blocks

• Occupy all open connections: not receive block header and version message

• Different blocks timeout are independent

Eclipse Attacks - Double Spending

• Double Spending 0 Confirmation Transactions: Very reliable attack

• Double Spending 1 Confirmation Transactions: Collude with miners

Eclipse Attacks - Denial of Service

• 6000 reachable Bitcoin nodes

• 450,000 TCP connections required

Eclipse Attacks - Hardening the P2P Layer

• Dynamic timeouts

• Handling Transaction Advertisements: filter IP; randomly choose sender

• Updating Block Advertisements: broadcast header instead of hash (so that PoW can be verified)

• After 5 minutes, transaction is received, even if the adversary controls 95% of the inv

Selfish Mining and Eclipse Attacks

• Instead of publishing, keep a block private

• Other miners will perform wasteful computations

• Combine with denying block \(\rightarrow\) higher pool revenue

Lecture 5

Blockchain Security

• Multi-layer: Hardware; Network; Blockchain; Programming Language; Application

Smart Contract Security

• Reentrancy: redefine payable() to call the withdraw repeatedly

• Unprivileged write to storage: user may change the wallet's owner

• Automated Security Analysis: Testing | Dynamic analysis; Symbolic execution | Static analysis; Formal verification

Smart Contract Bug

• Any variable is readable on the public Ethereum blockchain. Declaring a variable private only restricts the automatic creation of getter for that variable, but does not hide it

• Balance should be changed before a transfer is made (to prevent reentrancy attack)

Decentralized Autonomous Organization

Comparing Quantitatively Layer 1 Security

• Faster block generation \(\rightarrow\) Faster payments (less security)

• Bigger block size \(\rightarrow\) More throughput/Slower propagation (less security)

Modeling a Blockchain in an MDP

Quantifying Security with an MDP

• Double-Spending Threshold: transaction value, below which the optimal strategy is honest mining, above which the optimal strategy is double-spending attack

Selfish Mining and the Stale Block Rate

• The higher the stale block rate the higher the relative revenue of selfish mining

• Selfish Mining yields fewer block rewards than honest mining under constant difficulty

Blockchain Network Simulator

• 1 MB blocks, 1 min Block interval \(\rightarrow\) No stale block rate increase

• Drawbacks: TCP protocol (no congestion)

Bitcoin-NG

• The key block miner is the one mining the microblocks

• 60% \(\rightarrow\) latter, 40% \(\rightarrow\) former

Lecture 6

Blockchain Scaling

• Off Chain Transaction: Transaction outside the blockchain, secured by the blockchain

• No consensus latency or mining fees, while still achieving non-custodial security

• Backward compatibility

Channel Networks

Channel Networks State Replacement

• Time Lock State Replacement: T=100,99,98,\(\cdots\), expiry

• Revocation State Replacement: Agree on last state, keep all previous revoked states

• State Replacement Techniques (2016+): State change, everyone signs

Channel Networks HTLC

• Humble Conditional Transfer

• Path-based Payments (HTLC): synchronise a payment among peers on the path

• Path-based virtual Payment Channels (Perun): set up a virtual channel to avoid intermediary peers to be responsive

Channel Networks Routing

• Routing Properties: scalable; effective; efficient

• Routing Approaches: Source-routing; Per-hop routing

• Privacy: Value-Privacy; Transfer-Privacy

Channel Networks Summary

Channel Networks Trusted Execution Environments

• TEEs: Efficient and fast payments among peers

• Privacy: Intermediary nodes are not visible outside the enclave

• Offline Payments: Peers can remain offline!

• Examples: Teechan, Teechain

Payment Channel Hubs

• Payment Channel Hubs are great for instant finality and no trust. But expensive to run.

Commit-Chains

• Off the chain transactions: Like on-chain transactions!

• Constant-size checkpoint

• Without Collateral: Eventual Finality

• With Collateral: Instant Finality!

• Join without on-chain Transaction

• but a centralized Operator!

Commit-Chains Plasma Cash

• Non-Fungible Coins

• Merkle Tree: Every leaf is a coin

Commit-Chains NOCUST

• Deposit a coin: Balance credit in a Merkle Tree

• ZKP: User can directly challenge through Smart Contract

Commit-Chains NOCUST Security

• NOCUST server disappears: on-chain transactions are safe; use insurance pool to recover off-chain transactions

• Users to attempt double-spending: central operator will reject

• NOCUST server colludes with client to attempt double-spending (create or steal): Operator is challenged!

Commit-Chains Summary

Lecture 7

Blockchain Privacy

• Blockchain Privacy is a Multilayer Challenge

Blockchain Privacy Ethical Concerns

Blockchain Privacy Network Layer

• Peer to Peer Network: Validating nodes / Lightweight clients / Miner

• Network Privacy Leakages: IP; Client version; Port scan

Blockchain Privacy Transaction Layer

• Change Address:If new, then likely a change address

• Multi-input Transactions: All inputs can be signed by the same entity

Blockchain Privacy Native Privacy Blockchain

• ZCash: Transparent Transactions/Shielded Transactions

• Monero; CoinJoin: Stealth Addresses

Blockchain Privacy Stealth Addresses

• Hierarchical Deterministic (HD) Wallets: Addresses derived from the same key; From one address cannot derive the other addresses

• Adversary can't see where this transaction is paid to, but port scanner can

• Dark wallet

Blockchain Privacy Ring Signatures

Blockchain Privacy Add-on/Mixer Privacy

• Coinjoin

• Tornado Cash/Miximus/MicroMix

Blockchain Privacy Lightweight Clients

• Private Information Retrieval

• Bloom Filter

• TEEs

Blockchain Privacy Bloom Filter & SPV

• Stair stepping: actual FPR \(\leq\) target FPR

• Resizing/Restarting: different FP \(\rightarrow\) intersection

• Multiple Bloom filters

  • Same seed; Same size: no change

  • Same seed; Resize: improves the attack

  • Restart; Same Size: improves the attack

  • Restart; Resize: totally leaks

• Solution

  • Pre-generate Bitcoin addresses and insert into filter

  • Keep state about outsourced Bloom filter