Unit 3: Consensus Algorithms and Bitcoin Introduction - Subjective Questions

The consensus problem requires a collection of distributed nodes to agree on one value or one ordered state, even though messages may be delayed and some nodes may fail.

A correct consensus protocol generally satisfies:

• Agreement: All non-faulty nodes decide the same value.
• Validity: The decided value must be a valid value proposed according to the protocol rules.
• Termination: Every non-faulty node eventually reaches a decision.
• Integrity: A node decides at most once and cannot arbitrarily change its decision.

In a blockchain, consensus enables nodes to agree on the valid transaction history without relying on a central authority. It prevents conflicting transactions and ensures that honest nodes converge on a common ledger state.

Safety and liveness are the two main properties used to analyze consensus protocols.

• Safety means that the protocol never produces inconsistent decisions. For example, two honest nodes must not finalize different blocks at the same blockchain height.
• Liveness means that the protocol continues to make progress. Valid transactions should eventually be included, and new blocks should eventually be finalized.

Network conditions influence these properties:

• During long message delays or a network partition, a protocol may stop making progress to preserve safety.
• If both partitions continue finalizing conflicting values, liveness may be maintained temporarily, but safety is violated.
• Partially synchronous protocols usually guarantee safety at all times and liveness after network delays become bounded.

Therefore, consensus design often prioritizes safety during abnormal network conditions and restores liveness when communication improves.

In a classical Byzantine fault-tolerant protocol, the total number of nodes must satisfy:

where is the total number of nodes and is the maximum number of Byzantine nodes.

A decision generally requires a quorum of at least:

votes. Consider two quorums, each containing nodes, in a system of nodes. Their minimum intersection is:

Thus, the quorums overlap in at least nodes. Since at most nodes are Byzantine, at least one node in the overlap must be honest. An honest node will not vote for two conflicting values in the same consensus round, preventing conflicting decisions.

For example, if , then:

• Minimum total nodes:
• Required quorum:

This quorum-intersection property is fundamental to the safety of Byzantine fault-tolerant consensus.

Consensus algorithms can be classified using several criteria:

• Participation model:

  • Permissionless: Anyone may participate, as in Bitcoin.
  • Permissioned: Validators are identified and authorized.

• Fault model:

  • Crash fault tolerant: Handles nodes that stop responding but do not act maliciously.
  • Byzantine fault tolerant: Handles arbitrary or malicious behavior.

• Finality:

  • Probabilistic finality: Confidence increases as more blocks are added, as in Proof of Work.
  • Deterministic finality: Once committed, a block cannot be reverted without violating protocol assumptions.

• Timing assumption:

  • Synchronous: Assumes a known upper bound on message delay.
  • Asynchronous: Makes no fixed timing-bound assumption.
  • Partially synchronous: Safety is maintained despite delays, while liveness is obtained after the network becomes sufficiently stable.

This classification helps determine whether an algorithm is suitable for a public blockchain, consortium network, or private distributed system.

Crash fault tolerance assumes that faulty nodes may stop, restart, or fail to send messages, but they do not send deliberately conflicting information.

• Common algorithms: Raft and Paxos
• A majority quorum is typically required.
• To tolerate crash failures, a system generally needs at least nodes.

Byzantine fault tolerance assumes that faulty nodes may behave arbitrarily. They may lie, collude, send different messages to different nodes, or attempt to corrupt the protocol.

• Common algorithm: Practical Byzantine Fault Tolerance, or PBFT
• To tolerate Byzantine failures, a classical system generally needs at least nodes.

Byzantine fault tolerance is stronger but usually requires more communication and resources than crash fault tolerance. It is appropriate when participants cannot be fully trusted.

In Proof of Work, participants called miners compete to solve a computational puzzle. A miner repeatedly changes a nonce and hashes the candidate block header until the resulting hash is below the network target.

The main process is:

1. Collect and validate unconfirmed transactions.
2. Construct a candidate block and its Merkle root.
3. Repeatedly modify the nonce or related fields.
4. Compute the block-header hash.
5. Broadcast the block when the hash satisfies the target.
6. Other nodes independently verify the transactions and proof.

Rewriting the blockchain is difficult because changing an old block changes its hash and invalidates every later block reference. The attacker must recompute the work for the modified block and all its successors, and then overtake the cumulative work of the honest network. If honest miners control most hash power, the probability of a successful rewrite decreases rapidly as more blocks are added.

In Proof of Stake, validators lock cryptocurrency as stake and are selected to propose or attest to blocks. Their probability or voting power is usually related to the amount staked, subject to protocol-specific rules.

Comparison with Proof of Work:

• Resource use: Proof of Work consumes substantial computational power and electricity. Proof of Stake primarily relies on locked economic value and uses much less energy.
• Security basis: Proof of Work is secured by the cost of computation and hardware. Proof of Stake is secured by the value at risk through stake.
• Selection: Proof-of-Work miners compete by hashing, whereas Proof-of-Stake validators are selected through stake-weighted and often randomized mechanisms.
• Penalties: Proof of Stake can apply slashing, which destroys part of a validator's stake for signing conflicting blocks or violating rules.
• Finality: Many Proof-of-Stake systems provide explicit finality through validator votes, while Bitcoin's Proof of Work provides probabilistic finality.

Proof of Stake is energy-efficient, but its design must address issues such as stake concentration, long-range attacks, and conflicting votes.

PBFT is a consensus algorithm designed for systems with known participants. A primary node coordinates each consensus round.

Its main phases are:

1. Request: A client submits a request.
2. Pre-prepare: The primary proposes an order for the request.
3. Prepare: Replicas verify the proposal and broadcast prepare messages.
4. Commit: After receiving sufficient matching prepare messages, replicas broadcast commit messages.
5. Reply: The request is executed, and replicas respond to the client.

PBFT can tolerate Byzantine nodes when .

Advantages:

• Deterministic finality
• High transaction throughput in small networks
• No energy-intensive mining
• Tolerance of malicious participants

Limitations:

• Communication overhead is approximately because nodes exchange messages with one another.
• Membership usually needs to be controlled.
• Performance decreases as the validator set grows.

PBFT is therefore more suitable for permissioned and consortium blockchains than very large permissionless networks.

A permissionless blockchain allows unknown participants to join and leave freely. Its consensus algorithm must provide Sybil resistance so that one entity cannot gain unlimited influence by creating many identities. Proof of Work and Proof of Stake use scarce resources, such as computational power or economic stake, to assign influence.

A permissioned blockchain restricts participation to known and authenticated organizations or nodes. It can use voting-based algorithms such as PBFT, Raft, or other Byzantine fault-tolerant protocols.

Key differences include:

• Identity: Permissionless systems use open, pseudonymous participation; permissioned systems use managed identities.
• Performance: Permissioned systems usually offer lower latency and higher throughput.
• Finality: Permissioned Byzantine fault-tolerant protocols often provide deterministic finality.
• Scalability: Permissionless protocols can support very large participant populations, while all-to-all voting protocols scale less effectively.
• Trust: Permissionless systems assume a highly adversarial environment; permissioned systems assume some governance and membership control.

The choice of a consensus algorithm depends on technical, security, and organizational requirements.

Important factors include:

• Trust model: Whether validators are known, partially trusted, or anonymous.
• Fault model: Whether the system must tolerate only crashes or Byzantine behavior.
• Decentralization: The number of independent participants and the acceptable concentration of control.
• Finality: Whether probabilistic confirmation is acceptable or immediate deterministic finality is required.
• Performance: Required throughput, latency, and communication overhead.
• Energy consumption: Whether computation-intensive mining is acceptable.
• Network assumptions: Expected delays, partitions, and node availability.
• Scalability: The expected number of validators and users.
• Governance and regulation: Membership control, auditability, and legal requirements.

For example, a public digital currency may use Proof of Work or Proof of Stake because participation is open. A banking consortium may prefer PBFT-style consensus for fast deterministic finality. A private replicated database with trusted nodes may use Raft because only crash faults need to be handled.

Bitcoin is a peer-to-peer electronic cash system that enables value transfer without a central bank or payment processor.

Its main components are:

• Peer-to-peer network: Nodes exchange transactions and blocks directly.
• Public-key cryptography: Users control funds using private keys and authorize spending through digital signatures.
• Transactions: Bitcoins are transferred by consuming previous unspent outputs and creating new outputs.
• Blockchain: Validated transactions are grouped into blocks linked by cryptographic hashes.
• Proof-of-Work mining: Miners compete to add blocks and secure the transaction history.
• Consensus rule: Nodes follow the valid chain with the greatest cumulative Proof of Work.
• Incentives: Miners receive block subsidies and transaction fees.
• Limited supply: The issuance schedule and periodic subsidy halvings create a predictable monetary supply.

Together, these mechanisms solve double spending, establish a shared ledger, and make historical alteration computationally expensive.

A Bitcoin private key is a randomly selected integer in the valid range of the elliptic-curve group:

where is the order of the generator point. Bitcoin uses the elliptic curve secp256k1. The corresponding public key is computed as:

where is the curve's generator point and is the public key.

The private key is used to create digital signatures that authorize spending. The public key allows nodes to verify those signatures without learning the private key.

The private key must remain secret because control of it effectively means control of the associated funds. If it is stolen, an attacker can create valid signatures and transfer the funds. If it is lost and no backup exists, the funds generally become permanently unspendable. Secure wallets, backups, hardware devices, and seed phrases are therefore used to protect private keys.

Bitcoin combines cryptographic hashes and digital signatures to control the spending of transaction outputs.

• A user generates a private key and derives the corresponding public key.
• A Bitcoin address is produced from public-key or script information using hashing and an address-encoding format.
• When funds are sent, the output usually contains a locking condition identifying the authorized spender.
• To spend that output, the owner provides suitable unlocking data, commonly including a digital signature and public key.
• The signature is generated over a transaction-dependent message using the private key.
• Other nodes use the public key to verify the signature and check that the provided key or script satisfies the output's locking condition.

Hashes provide compact identifiers and tamper evidence, while signatures prove authorization. A signature does not encrypt a transaction; it demonstrates that the holder of the required private key approved the transaction without revealing that key.

Bitcoin uses the Unspent Transaction Output, or UTXO, model. A UTXO is an output of a previous transaction that has not yet been spent.

A transaction contains:

• Inputs: References to previous UTXOs, together with data that satisfies their spending conditions.
• Outputs: New amounts and locking conditions that define who may spend them later.

Inputs consume referenced UTXOs completely. If the selected input value is greater than the amount being paid, the transaction normally creates a change output for the sender.

The transaction fee is:

For example, if the inputs total BTC and the outputs total BTC, then:

Nodes prevent double spending by rejecting a transaction if a referenced output has already been spent or does not exist in the current UTXO set.

A Bitcoin node performs multiple checks before accepting and relaying a transaction. Important checks include:

• The transaction must be correctly encoded and within applicable size and weight limits.
• Each input must reference an existing UTXO.
• The referenced UTXOs must not already have been spent.
• The unlocking data must satisfy the locking script of each referenced output.
• Digital signatures must be valid for the relevant transaction data.
• Input and output values must remain within the permitted monetary range.
• The total input value must be at least the total output value.
• Timelock and sequence conditions must be satisfied.
• A coinbase output must reach the required maturity before it can be spent.

Nodes also apply mempool and relay policies, which may be stricter than the core consensus rules. A transaction can therefore be valid under consensus rules but not immediately relayed by every node.

The Bitcoin blockchain is an ordered sequence of blocks. Each block consists of a header and a list of transactions.

The block header contains fields such as:

• Version
• Previous block hash
• Merkle root
• Timestamp
• Difficulty representation
• Nonce

The previous block hash links a block to its predecessor. If an earlier block changes, its hash changes, breaking the links in all following blocks. This makes tampering evident and requires the associated Proof of Work to be redone.

The Merkle root summarizes all transactions in the block. Transaction hashes are repeatedly combined in pairs and hashed until one root remains. It provides:

• Efficient proof that a transaction is included in a block
• Detection of any change to included transactions
• Compact verification for simplified payment verification clients

A Merkle proof requires only about hashes for a block containing transactions.

Bitcoin mining proceeds through the following stages:

1. Transaction selection: A miner selects valid transactions from its mempool, often prioritizing transactions with higher fee rates.
2. Coinbase creation: The miner creates a special coinbase transaction that claims the allowed block subsidy and transaction fees.
3. Block construction: Transactions are organized into a Merkle tree, and the Merkle root is placed in the block header.
4. Proof-of-Work search: The miner changes the nonce, coinbase extra data, or other permitted fields and repeatedly hashes the block header.
5. Target test: A block is successful when its hash, interpreted as a number, is less than or equal to the target.
6. Propagation: The miner broadcasts the block to peers.
7. Validation: Other nodes verify the Proof of Work, transactions, block structure, and reward amount.
8. Chain extension: If valid, nodes add the block to their accepted chain state.

The successful miner earns the block subsidy plus transaction fees. The coinbase reward becomes spendable only after the required maturity period.

A Proof-of-Work hash is valid when its numerical value is at most a target . For a uniformly distributed -bit hash, there are possible values. The approximate success probability of one hash attempt is:

The expected number of attempts before success is the reciprocal:

If the mining device or network performs hashes per second, the expected discovery time is:

Therefore:

• A lower target decreases the probability of success and increases required work.
• A higher difficulty corresponds to a lower target.
• A higher hash rate reduces the expected time to discover a block if the target remains unchanged.

Bitcoin periodically adjusts its mining target so that blocks continue to be produced near the intended average interval despite changes in total network hash rate.

A temporary fork can occur when two miners discover valid blocks at nearly the same time. Because block propagation takes time, some nodes may receive one block first while other nodes receive the competing block first.

Miners initially build on the valid chain tip they received. Eventually, one branch accumulates more Proof of Work. Bitcoin nodes follow the valid chain with the greatest cumulative Proof of Work, so they converge on that branch. Blocks left outside the selected chain are called stale blocks, and their ordinary transactions may return to mempools if they remain valid and unconfirmed.

A transaction has one confirmation when it appears in an accepted block. Each additional block built after it adds another confirmation. More confirmations mean an attacker would need to redo more Proof of Work to replace the transaction's block and catch up with the honest chain. Confirmations therefore provide increasing probabilistic confidence rather than absolute, immediate finality.

The life cycle of a Bitcoin payment includes the following stages:

1. Key control: The sender's wallet controls private keys capable of satisfying the locking conditions of one or more UTXOs.
2. Transaction construction: The wallet selects UTXOs as inputs, creates the recipient output, usually creates a change output, and determines a transaction fee.
3. Authorization: The wallet signs the required transaction data with the relevant private keys.
4. Broadcast: The signed transaction is sent to peer nodes.
5. Independent validation: Nodes check its syntax, UTXO references, scripts, signatures, values, and double-spending status.
6. Mempool storage: Valid unconfirmed transactions may be stored and relayed.
7. Miner selection: Miners select transactions, commonly according to fee rate, and construct candidate blocks.
8. Proof of Work: Miners repeatedly hash block headers until one finds a hash satisfying the target.
9. Block validation: Nodes verify the winning block, including every transaction, the Merkle root, Proof of Work, and coinbase reward.
10. Consensus and confirmations: Nodes extend the valid chain with the greatest cumulative work. Later blocks increase confidence that the payment will not be reversed.

Interaction of mechanisms:

• Cryptography proves spending authorization and makes data changes detectable.
• Transaction validation enforces monetary and scripting rules.
• Consensus determines the accepted ordering of valid transactions and resolves conflicting spends.
• Mining incentives encourage participants to contribute hash power, include fee-paying transactions, and follow rules because invalid blocks are rejected and yield no usable reward.

Together, these mechanisms enable decentralized ownership transfer while making double spending and historical alteration economically difficult.