Unit 3: Consensus Algorithms and Bitcoin Introduction

I. Orientation

Blockchain systems coordinate a shared history among independent computers without relying on one central administrator. Consensus algorithms provide the rules for agreeing on that history, while Bitcoin combines cryptography, peer-to-peer networking, transactions, a blockchain ledger, and mining to implement decentralized digital money.

A. Defining principles

• Distributed setting: Several nodes maintain replicas of the same ledger and communicate over a network that may be delayed or unreliable.
• Agreement: Correct nodes should decide on the same valid value, block, or transaction history.
• Validity: A decided value must satisfy the protocol rules; invalid transactions must not enter the ledger.
• Fault assumptions: Nodes may crash, disconnect, behave maliciously, or attempt to create conflicting histories.
• Cryptographic identity: Public keys identify recipients, while private keys authorize spending through digital signatures.
• Immutability convention: Confirmed records are treated as increasingly difficult to alter, although blockchain data is not physically impossible to rewrite.
• Economic security: In Bitcoin, computational work and block rewards make honest participation more attractive than attacks.

II. Introducing the consensus problem — Agreement in a distributed network

The consensus problem asks how distributed nodes can agree on one result when communication is imperfect and some participants may fail or act maliciously.

A. Introducing the consensus problem

A consensus protocol allows nodes to agree on one ordered sequence of operations despite uncertainty about other nodes and network conditions.

• Agreement: If two honest nodes decide, they must decide the same value. For example, one node cannot accept transaction T1 while another accepts a conflicting transaction T2 as final.
• Validity: The decision must be supported by an admissible proposal, such as a correctly signed transaction or a valid block.
• Termination: Every honest node should eventually decide, assuming the network and timing conditions required by the protocol.
• Double-spending conflict: Alice might broadcast two transactions spending the same 1 BTC to Bob and Carol; consensus determines which transaction belongs to the accepted history.
• Impossibility boundary: In a completely asynchronous network, a deterministic protocol cannot guarantee both termination and safety when even one process may fail, a result associated with the FLP impossibility theorem.

III. Consensus analysis and design — Turning requirements into protocol rules

Consensus design begins by specifying the system model, the required guarantees, and the mechanism by which nodes select a common history.

A. Consensus analysis and design

A sound design connects fault assumptions and network conditions to explicit safety, liveness, and performance goals.

• System model: Specify whether nodes are crash-faulty or Byzantine-faulty. A Byzantine node may send different messages to different peers or propose invalid blocks.
• Safety: “Nothing bad happens.” Two finalized blocks must not conflict, and a valid ledger transition must preserve rules such as inputs >= outputs.
• Liveness: “Something good eventually happens.” Valid transactions should be included, and the system should continue producing decisions.
• Network model: Synchronous systems provide known message-delay bounds; asynchronous systems provide no dependable timing bound. Partially synchronous systems assume bounds eventually become reliable.
• Quorum reasoning: In a Byzantine system with 3f + 1 nodes, protocols such as PBFT generally require at least 2f + 1 matching votes to commit while tolerating f Byzantine nodes.
• Design trade-off: Increasing confirmation requirements improves confidence but increases latency; larger validator sets improve distribution but may increase communication overhead.

IV. Consensus classification — Grouping protocols by their trust model

Consensus algorithms can be classified by how participants are admitted, how leadership is chosen, and what resource or authority determines the decision.

A. Consensus classification

Classification helps compare protocols with different assumptions rather than treating all agreement mechanisms as interchangeable.

• Permissionless consensus: Anyone can join, as in Bitcoin. Identity is not a sufficient basis for voting because participants can create many identities.
• Permissioned consensus: Membership is controlled, so known organizations may use voting-based protocols such as PBFT or Raft.
• Crash fault tolerance: Raft and Paxos address nodes that stop or lose messages but do not fully address malicious behavior.
• Byzantine fault tolerance: PBFT and related protocols tolerate actively dishonest nodes under a specified threshold, commonly fewer than one-third of validators.
• Resource-based consensus: Proof of Work uses computation, while Proof of Stake uses economically locked stake to influence block proposal and validation.
• Leader-based versus leaderless: Raft elects a leader; PBFT uses a primary and backups; Nakamoto consensus allows miners to compete to publish the next block.

V. Consensus algorithms — Mechanisms for selecting one history

A consensus algorithm defines message exchange, proposal rules, validation, conflict resolution, and the conditions under which a decision is final.

A. Consensus algorithms

Different algorithms provide different forms of finality, scalability, fault tolerance, and participation.

• Raft: A leader replicates log entries to followers; an entry is committed after a majority acknowledges it. With five nodes, at least three votes are needed for a majority.
• PBFT: A primary proposes a value, and replicas exchange pre-prepare, prepare, and commit messages. With 3f + 1 replicas, the protocol tolerates f Byzantine faults.
• Proof of Work: Miners search for a nonce such that the block hash is below a target:

  SHA256(SHA256(block_header)) < target

The nonce is the adjustable value; the target controls difficulty.

• Proof of Stake: A validator is selected using stake-related rules, proposes a block, and may lose stake for provably dishonest behavior. Security depends on the value at risk and enforcement mechanism.
• Probabilistic finality: Bitcoin transactions become more reliable as additional blocks build on them, rather than becoming mathematically final immediately.
• Deterministic finality: Many permissioned Byzantine protocols finalize a block once the quorum certificate is formed; conflicting final decisions should be impossible under the fault assumptions.

VI. Choosing an algorithm — Matching consensus to the application

Algorithm selection should follow operational requirements, participant trust, fault model, and acceptable performance rather than popularity alone.

A. Choosing an algorithm

The appropriate algorithm is the one whose assumptions match the real deployment environment.

• Participant admission: Use permissioned voting when validators are known organizations; use permissionless mechanisms when open participation is essential.
• Fault type: Raft is appropriate for crash failures, but a hostile validator requires Byzantine fault tolerance or another adversarial model.
• Finality requirement: Financial settlement may require deterministic finality; applications accepting delayed certainty may use Bitcoin-style confirmations.
• Performance target: Voting protocols can offer high throughput in small validator groups, while global permissionless networks sacrifice speed for openness and censorship resistance.
• Energy and cost: Proof of Work requires substantial electricity and specialized hardware; Proof of Stake reduces computation but introduces stake concentration and governance concerns.
• Centralization risk: Examine who controls validators, mining hardware, stake, network connectivity, and protocol upgrades.

VII. Bitcoin—an overview — A decentralized electronic cash system

Bitcoin was introduced in 2008 under the name Satoshi Nakamoto and launched in January 2009 as a peer-to-peer system for transferring value without a central financial intermediary.

A. Bitcoin—an overview

Bitcoin uses a public ledger and economic incentives to make a single transaction history credible in an open network.

• Peer-to-peer network: Nodes relay transactions and blocks directly rather than through a central server.
• Unspent transaction outputs: Bitcoin tracks spendable outputs, called UTXOs, rather than account balances. A wallet balance is the sum of UTXOs controlled by its keys.
• Supply rule: New bitcoin is issued through block subsidies, and the subsidy halves approximately every 210,000 blocks; the maximum supply is approximately 21 million BTC.
• Consensus rule: Nodes independently verify scripts, signatures, transaction values, block structure, and Proof of Work.
• Longest-chain principle: More precisely, nodes follow the valid chain with the greatest accumulated work, not merely the chain with the greatest number of blocks.
• Decentralization objective: No single node decides validity; each node applies the protocol rules to independently check received data.

VIII. Cryptographic keys — Controlling ownership and authorization

Bitcoin ownership is represented by the ability to produce a valid signature for an unspent output, not by a name stored in the ledger.

A. Cryptographic keys

A key pair creates a practical authorization system in which the private key remains secret and the public key can be shared.

• Private key: A randomly generated secret number, typically 256 bits in the secp256k1 system, authorizes spending. Anyone obtaining it can usually spend the associated funds.
• Public key: Derived mathematically from the private key and used to verify signatures. Deriving the private key from the public key is computationally infeasible with current methods.
• Digital signature: The spender signs transaction data with the private key; nodes verify the signature using the public key.

  signature = Sign(private_key, transaction_data)
  valid = Verify(public_key, transaction_data, signature)

• Address: A human-friendly representation derived from a public key or script, often using hashing and encoding. An address is not itself a private key.
• Hashing: Functions such as SHA-256 produce fixed-length digests used in addresses, transaction identifiers, and Proof of Work.
• Key loss: If the private key is destroyed, the network cannot identify an authorized spender, so the associated UTXOs may become permanently inaccessible.

IX. Transactions — Authorized changes to the UTXO set

A Bitcoin transaction consumes previous unspent outputs and creates new outputs that specify future spending conditions.

A. Transactions

Transactions transfer control by satisfying locking conditions on existing outputs and creating new locked outputs.

• Inputs: Each input references a previous transaction output through its transaction identifier and output index, then supplies an unlocking script or witness.
• Outputs: Each output contains a value in satoshis and a locking script, commonly requiring a signature corresponding to a public-key hash.
• Fee calculation: The transaction fee is the input total minus the output total:

  fee = sum(input_values) - sum(output_values)

If inputs total 100,000 satoshis and outputs total 99,000, the fee is 1,000 satoshis.

• Validation: Nodes check that referenced outputs exist and are unspent, signatures satisfy the scripts, and total output value does not exceed total input value.
• Coinbase transaction: The first transaction in a block creates the miner’s subsidy and collects transaction fees; it has no ordinary previous-output inputs.
• Mempool status: A valid transaction may wait in a node’s memory pool before a miner includes it in a block.

X. Blockchain — An append-oriented public ledger

The blockchain is an ordered chain of blocks in which each block commits to earlier data and records a set of validated transactions.

A. Blockchain

Blocks provide structure, ordering, and evidence of accumulated computational work.

• Block header: Important fields include the previous block hash, Merkle root, timestamp, difficulty target, and nonce.
• Previous-hash link: Each block stores the hash of its predecessor. Altering an old block changes its hash and breaks every later link.
• Merkle tree: Transaction hashes are paired and repeatedly hashed until one Merkle root summarizes all transactions in the block. A proof can establish inclusion without transmitting every transaction.
• Genesis block: Bitcoin’s first block, created in January 2009, has no ordinary predecessor and establishes the initial chain.
• Confirmation: A transaction included in one block has one confirmation; each subsequent block adds another. More confirmations increase the work an attacker must replace.
• Forks: Two valid blocks may temporarily compete at the same height. Nodes eventually converge on the branch with the greatest accumulated work, while transactions on the losing branch may return to the mempool.

XI. Mining — Proof of Work and block production

Mining is the competitive process through which Bitcoin participants propose blocks and prove that they performed computational work.

A. Mining

Miners assemble candidate blocks, search for a valid hash, broadcast successful results, and receive rewards when the network accepts their block.

• Candidate construction: A miner selects transactions, builds a Merkle root, inserts the previous block hash, and chooses a timestamp, target, and nonce.
• Nonce search: The miner repeatedly changes the nonce and sometimes the coinbase transaction until the double SHA-256 hash is below the target. Each attempt is independent, making repeated guessing necessary.
• Difficulty adjustment: Bitcoin adjusts the target every 2,016 blocks so the expected block interval remains near 10 minutes, despite changes in total network hash rate.
• Block reward: The miner receives the block subsidy plus transaction fees through the coinbase transaction. The subsidy is reduced by half at each halving event.
• Chain selection: If competing valid blocks appear, nodes build on the chain containing the most accumulated work. A miner attempting to reverse a payment must privately redo the target block and catch up with honest miners.
• Security limitation: Proof of Work does not eliminate attacks; an entity controlling a majority of mining power could reorganize recent history or censor transactions, though it cannot normally create valid coins from nothing or spend without satisfying transaction rules.