Skip to content

Latest commit

 

History

History
157 lines (114 loc) · 7.24 KB

06.1-bitcoin.md

File metadata and controls

157 lines (114 loc) · 7.24 KB

Bitcoin

Bitcoin is a decentralized digital currency, without a central bank or single administrator, that can be sent from user to user on the peer-to-peer bitcoin network without the need for intermediaries.

Proof-of-Work (PoW)

  • Proof-of-Work is a process that requires some work to be done before a block can be added to the blockchain;
  • The work is computationally intensive and time-consuming;
  • The work is easy to verify;
  • This limits the rate at which blocks can be added to the blockchain, and thus the rate at which new coins can be created;
  • In bitcoin, miners compete to solve a cryptographic puzzle, they aggregate transactions in blocks, allowing for better throughput;
    • They compete to get block appended to the blockchain, and they are rewarded with new coins.

PoW in Bitcoin

  • Each miner has a transaction pool - set of transactions received over the network or created by the miner;
  • Miners try to create a valid block by solving a puzzle: SHA256(h || T || K || nonce) < D, where:
    • h is the hash of the previous block;
    • T is the set of transactions;
    • K is the public key of the miner;
    • nonce is a random number;
    • D is the difficulty level.
  • When solved, broadcast new block to all miners;
  • A block includes:
    • A subset of transactions from the pool, chosen by the miner;
    • A pointer to the previous block;
    • The identity of the miner;
    • The solution to the puzzle.

Block Dissemination

  • Every node keeps a copy of every block of transactions;
    • Can be a scalability bottleneck;
  • Upon receiving a new block, miners validate the block and its transactions;
    • If valid, they add the block to their local copy of the blockchain and broadcast it to all other miners and start mining the next block.

Clients, Miners and Nodes

  • Clients - users that create transactions and broadcast them to the miners;
  • Miners - nodes that create new blocks solving the PoW puzzle;
  • Full nodes - nodes that keep a full copy of the blockchain;
  • Compact/light nodes - nodes that keep only the block headers.

Properties

  • Prevents sybil attacks - solving the puzzle requires computational power;
  • Tamper-proof - pointer to the previous block;
    • Changing a block would require changing all subsequent blocks;
    • Rewriting the blockchain is computationally infeasible.
  • Provides incentives for miners to behave honestly;
    • Miners are rewarded with new coins;
    • Miners are also rewarded with transaction fees;
  • Generating a block can be seen as a random Poisson process;
    • The time between blocks is exponentially distributed.

Forks

  • Fork - when two miners solve the puzzle at the same time;
    • The blockchain is forked into two chains;
    • Miners will try to mine in parallel chains;
  • Longest chain rule - miners will mine on the longest chain;
    • The longest chain is the one with the most accumulated work;
    • The other chain will be discarded.
  • Problem: lack of finality - a transaction is considered confirmed after a few blocks, but not immediately - probabilistic finality.

Attacks

Double Spending

Spending the same coin twice:

  1. Attacker sends a transaction to a merchant, and also sends the same coin to another merchant;
  2. The attacker tries to mine a block that includes the first transaction, and broadcasts it to the network;
  3. The attacker tries to mine another block that includes the second transaction, and broadcasts it to the network;
  4. The network will accept the first block, and the second block will be discarded.

Rental Attack (51% Attack)

  • An attacker controls more than 50% of the network's computational power;
  • Overly expensive for Bitcoin and Ethereum, but not for smaller blockchains.

Finney Attack

  • Attacker successfully pre-mines a block including a transaction that sends some of his coins back to himself, without broadcasting it;
  • Attacker then makes a purchase from a merchant, and waits for the merchant to deliver the goods;
  • After the goods are delivered, the attacker broadcasts the pre-mined block, overwriting the transaction that paid the merchant.

Mining Pools

  • Mining pool - a group of miners that work together to mine blocks;
    • They share the reward;
    • They share the computational power;
    • They share the risk of not being able to solve the puzzle;
    • They share the risk of being attacked;
  • As mining becomes more difficult, mining pools become more common;
  • CPU mining -> GPU mining -> ASIC mining.

Feather-forking Attack

  • Suppose that a mining pool controls 40% of the network's computational power, and wants to censor Alice;
  • Mining pool announces it will refuse to mine any block that includes a transaction from Alice;
  • Creates a disincentive for every miner to include Alice's transactions in their blocks.

Selfish Mining

  • A mining pool keeps its blocks private - they create their own private fork;
  • When public chain catches up (the public chain is the longest), the pool releases its private chain, and the public chain is discarded.

PoW blockchains vs Consensus

Property Consensus PoW
Termination ✅Correct nodes eventually agree on the same value ✅Blocks are added at a fixed rate
Integrity ✅No correct process decides twice ❌Forks
Agreement ✅All correct processes decide the same value ❌Forks
Validity ✅Decided value has been proposed by some process ❌Byzantine processes can generate transactions
  • Classical consensus emphasizes safety (integrity and agreement);
  • PoW emphasizes liveness (termination and agreement) - the system always makes progress.

Safety vs Liveness tradeoff

Bitcoin Data Structures

Each block in the blockchain is a set of transactions:

  • Transactions can have multiple inputs and <= 2 outputs;
  • It is possible to specify a set of deterministic operations, with conditions on transfer (smart contracts);
  • Each input describes debit -> sender signs handoff of amount (signed with private key);
  • Each output describes credit -> receiver's address and amount.

UTXO (Unspent Transaction Output) Model

  • Blockchains stores all transaction since the beginning of time;
  • Additionally, keeps track of outputs that haven't been spent yet, called unspent transaction outputs (UTXOs);
  • When a transaction is created, it consumes UTXOs and creates new ones.

Bitcoin Scalability and UtreeXO

  • Resources required for running a full node are a problem, as the blockchain grows;
  • Continuously maintaining a set of UTXOs is expensive;
  • Light clients - do not keep state nor validate transactions, but rely on full nodes;
    • Led to the proposal of UtreeXO - a way to compress the UTXO set;
    • A new set of data structures that allow for efficient UTXO set compression;
    • Store only a summary of the UTXO set, and not the entire set.