Quantum Computing (AL-802 (D)) - Unit 3 Short Notes

I. FOUNDATIONS OF BLOCKCHAIN STRUCTURE

A. Public Ledger Concept & Function in Financial Transactions

A public ledger is a decentralized, immutable, and transparent digital record of all transactions shared across a network of nodes. In financial transactions, it eliminates the need for a central authority (e.g., a bank) by enabling direct peer-to-peer value transfer.

Core Functions:

• Transparency: All participants can view transaction history (though identities are pseudonymous).

• Immutability: Once recorded, data cannot be altered retroactively due to cryptographic hashing and consensus.

• Double-Spending Prevention: Sequential block linking and consensus mechanisms ensure a coin isn’t spent twice.

• Auditability: Provides a verifiable trail for regulators and auditors.

[!TIP]

Exam Focus: Contrast with traditional private ledgers. Emphasize how public ledgers achieve trustlessness—nodes trust the protocol, not each other.

Structure: Transactions are grouped into blocks, each containing a block header (metadata) and a body (transaction list). Blocks are chained via the previous block hash in the header, forming a blockchain.

B. Block Architecture: The "Block Within a Block" Paradigm

This refers to the Merkle root embedded within the block header, which cryptographically summarizes all transactions in the block’s body. It is a "block within a block" because the root hash represents the entire transaction set, enabling efficient verification without exposing full data.

Block Structure:

Block Header:

- Version

- Previous Block Hash (link to chain)

- **Merkle Root** (hash of all transactions)

- Timestamp

- Difficulty Target

- Nonce

Block Body:

- Transaction Count

- Transaction List (each transaction has inputs, outputs, scripts)

Role in Structure:

• Integrity: Any change to a transaction alters its hash, propagating up to change the Merkle root, breaking the chain.

• Efficiency: Lightweight nodes (SPV) verify transactions by checking a Merkle proof (path from transaction to root) instead of downloading the entire block.

• Linking: The previous block hash in the header creates the sequential chain, while the Merkle root binds the block’s internal data.

[!COMMON PITFALL]

Do not confuse "block within a block" with nested blocks. It’s a summary (Merkle root) inside the header, not a physical sub-block.

C. Merkle Trees: Construction, Hashing, and Role in Efficient & Secure Data Verification

A Merkle tree (binary hash tree) is a data structure where leaves are hashes of transactions, and each parent node is the hash of its two children. The top node is the Merkle root, stored in the block header.

Construction Steps:

1. Hash each transaction (using SHA-256 twice in Bitcoin: H = SHA256(SHA256(tx))).

2. If odd number of leaves, duplicate the last hash.

3. Pairwise hash: For each pair of child hashes h₁, h₂, compute parent H(h₁ || h₂), where || denotes concatenation.

4. Repeat until one root remains.

Role in Blockchain:

• Efficient Verification: To prove transaction T is in block B, provide T’s hash and sibling hashes along the path to root. The verifier recomputes upward and checks against the stored Merkle root.

• Data Integrity: Any alteration to T changes its hash, altering all ancestors up to the root—detectable by root mismatch.

• Scalability: Enables Simplified Payment Verification (SPV)—light clients verify transactions without full blockchain download.

Example with Numbers:

Transactions: tx1, tx2, tx3, tx4

Leaf hashes: h1=H(tx1), h2=H(tx2), h3=H(tx3), h4=H(tx4)

Level 1: h12 = H(h1 || h2), h34 = H(h3 || h4)

Merkle root: root = H(h12 || h34)

[!TIP]

Exam Problem: Given a Merkle root and a transaction hash, trace the Merkle proof. Always hash in the correct order (left then right).

II. THE BITCOIN NETWORK: MECHANISMS & PARTICIPANTS

A. Bitcoin Peer-to-Peer (P2P) Network Architecture and Transaction Propagation

The Bitcoin network is a decentralized P2P overlay network where nodes (computers running Bitcoin Core) communicate via TCP port 8333. There is no central server; nodes relay information directly.

Node Types:

• Full Nodes: Validate all transactions and blocks, store entire blockchain (~500 GB).

• Miners: Full nodes that also solve PoW puzzles to create blocks.

• SPV Clients: Lightweight nodes that store only block headers and request Merkle proofs.

Transaction Propagation:

1. User signs transaction and broadcasts to connected peers.

2. Each node validates (scripts, double-spend, fees) and forwards to its peers if valid.

3. Transactions enter the mempool (memory pool) awaiting inclusion in a block.

4. Miners select transactions (typically by fee rate) from mempool to build candidate blocks.

5. When a miner finds a valid PoW, the new block is broadcast; nodes verify and add to their chain, removing confirmed transactions from mempool.

Security via Redundancy: Multiple paths ensure eventual consistency even if some nodes are malicious or offline.

[!TIP]

Key Point: Propagation delay can cause temporary forks (orphan blocks). The longest valid chain rule resolves forks.

B. HashCash Proof-of-Work (PoW): Mechanism, Computational Puzzle, and Security Contribution

HashCash PoW (originally by Adam Back, adapted by Bitcoin) is a computational puzzle requiring miners to find a nonce such that the double SHA-256 hash of the block header is below a dynamic target difficulty.

Puzzle Mechanics:

• Block header includes: version, prev_hash, Merkle_root, timestamp, bits (target), nonce.

• Goal: Find nonce such that:

$$ \text{SHA256(SHA256(block\_header))} < \text{target} $$

• Difficulty adjusts every 2016 blocks (~2 weeks) to maintain ~10-minute block time:

$$ \text{new\_target} = \text{old\_target} \times \frac{\text{actual\_time\_taken}}{2016 \times 10 \text{ minutes}} $$

Security Contributions:

• Sybil Attack Resistance: Creating blocks requires real computational work (electricity/hardware), making it costly to spawn many identities.

• Double-Spending Defense: To rewrite history, an attacker must redo PoW for all subsequent blocks, requiring >51% of total network hash power (impractical for Bitcoin).

• Decentralized Consensus: Miners compete; the longest valid chain (most PoW) is accepted as truth.

Numerical Example:

If target = 0000ffff00000000000000000000000000000000000000000000000000000000 (in hex), valid hash must have at least 16 leading zero bits. Miners iterate nonce values until hash meets condition.

[!COMMON PITFALL]

PoW does not solve a "hard mathematical problem"—it’s brute-force search. Security comes from the asymmetry: easy to verify, hard to find.

C. The Bitcoin Miner: Daily Operational Routines, Challenges, and Role in Network Security & Consensus

Daily Routines:

1. Hardware Setup: Use ASIC miners optimized for SHA-256.

2. Software Configuration: Connect to mining pool or run solo; set up Bitcoin Core node.

3. Block Assembly: Fetch transactions from mempool (sorted by fee), compute Merkle root, set timestamp, previous block hash.

4. Mining: Iterate nonce and extra nonce (in coinbase transaction) to find hash below target.

5. Block Propagation: Upon finding valid nonce, broadcast block to network.

6. Reward Collection: Receive block reward (currently 3.125 BTC) + transaction fees after 100 confirmations.

Challenges:

• High Energy Consumption: Mining is electricity-intensive; profitability depends on electricity cost vs. reward.

• Hardware Obsolescence: ASICs become outdated quickly; requires continuous investment.

• Pool Centralization Risk: Most miners join pools (e.g., Foundry USA) for steady income, leading to pool dominance.

• Regulatory & Environmental Scrutiny: Increasing regulations and ESG concerns.

• Orphan Blocks: Found blocks may be stale if another block is propagated first—no reward.

Role in Security & Consensus:

• Consensus Enforcement: Miners enforce protocol rules (e.g., valid transactions, block size limit).

• Chain Growth: By extending the longest valid chain, miners confirm transactions and prevent double-spends.

• Economic Incentives: Block rewards and fees align miner incentives with network security.

[!TIP]

Exam Answer Structure: Describe routine → list challenges → explain how each challenge impacts security (e.g., pool centralization increases 51% attack risk).

III. DISTRIBUTED CONSENSUS ALGORITHMS & FAULT TOLERANCE

A. The Byzantine General Problem: Definition, Implications for Distributed Agreement

Definition: A thought experiment where several Byzantine generals must agree on a common plan of action (attack or retreat). Some generals may be traitors who send conflicting messages to disrupt consensus. The problem is to achieve agreement despite Byzantine faults (arbitrary/malicious behavior).

Implications for Distributed Systems:

• In blockchain, nodes must agree on ledger state despite some nodes being faulty or malicious.

• Fault Tolerance Requirement: To tolerate f Byzantine nodes, system needs at least 3f + 1 total nodes (for deterministic algorithms in asynchronous networks).

• Consensus vs. Byzantine Fault Tolerance (BFT): Traditional consensus (e.g., Paxos) assumes crash faults only. BFT algorithms (e.g., PBFT) handle arbitrary faults.

Relation to Blockchain:

• Permissionless (Bitcoin): Uses PoW as a probabilistic BFT mechanism—probability of attack decreases as confirmations increase.

• Permissioned (Hyperledger Fabric): Uses deterministic BFT algorithms (e.g., PBFT) for finality.

[!TIP]

Key Formula: For n nodes, maximum Byzantine faults tolerated: f < n/3.

B. Lamport-Shostak-Pease (Oral Messages) Algorithm: Handling Byzantine Faults

Also known as the Oral Messages (OM) algorithm, it solves the Byzantine General Problem for a synchronous network where messages can be forged by traitors.

Assumptions:

• Network is synchronous (bounded message delay).

• Messages are signed/unforgeable? In original, messages are oral (no signatures), so traitors can lie.

• Goal: All loyal generals obey the same order; if commander is loyal, all loyal follow his order.

Algorithm (OM(m) for m traitors):

1. Base Case (OM(0)): Commander sends order to each lieutenant. Lieutenants use commander’s order directly.

2. Recursive Step (OM(m)):

   • Commander sends order to each lieutenant.

   • For each lieutenant L_i, let S_i be the set of other lieutenants (excluding commander and L_i).

   • L_i acts as commander for S_i and recursively sends the order he received (using OM(m-1)).

   • After receiving n-1 messages (one from commander, n-2 from other lieutenants), L_i uses a majority function on the set of received orders to decide.

Fault Tolerance: Requires n > 3m (i.e., n ≥ 3m + 1) to tolerate m traitors.

Example: With n=4 generals, m=1 traitor. Each lieutenant receives 3 messages (1 from commander, 2 from others). Majority vote yields correct order if commander loyal.

Limitations:

• Message Complexity: O(n^{m+1})—exponential in m.

• Synchronous Assumption: Unrealistic in real networks with variable latency.

• Not Used in Practice: Too inefficient; Bitcoin’s PoW is more scalable for large n.

[!TIP]

Exam Derivation: Be prepared to prove why n ≥ 3m + 1 is necessary (traitors can create inconsistent views among lieutenants if n ≤ 3m).

C. Paxos Algorithm: Principles for Achieving Consensus in Permissioned/Replicated Systems

Paxos is a family of protocols for achieving consensus in permissioned systems with crash faults (not Byzantine). It ensures that nodes agree on a single value despite node failures and message delays.

Roles:

• Proposer: Suggests a value (e.g., transaction batch).

• Acceptor: Votes to accept proposals; maintains persistent state.

• Learner: Learns the chosen value (e.g., updates ledger).

Two-Phase Process:

1. Prepare Phase:

   • Proposer selects proposal number n, sends Prepare(n) to acceptors.

   • Acceptor responds with Promise(n, last_accepted_value) if n is higher than any seen; else ignore.

2. Accept Phase:

   • If proposer receives promises from majority of acceptors, it sends AcceptRequest(n, value) where value is the highest last_accepted_value from responses, or its own if none.

   • Acceptor accepts if it hasn’t promised a higher number.

   • When majority accepts, value is chosen.

Safety & Liveness:

• Safety: Only one value is chosen; chosen value is valid.

• Liveness: If majority of acceptors are operational and network stable, a value is eventually chosen.

Use in Blockchain:

• Permissioned Blockchains: Hyperledger Fabric’s ordering service uses a variant (Raft, not classic Paxos) for crash fault tolerance.

• Not for Byzantine: Classic Paxos fails with malicious nodes; use PBFT or Tendermint for BFT.

[!TIP]

Common Exam Question: "Explain Paxos phases with diagram." Draw proposer, acceptors, messages (Prepare, Promise, AcceptRequest, Accepted). Highlight majority quorum.