Data Structures and CAP Theorem

Data Structures in Blockchain

Merkle Trees

• Purpose: Ensure data integrity and efficient verification.

• How It Works:

  • Each transaction in a block is hashed.

  • Hashes are paired and hashed recursively until a single Merkle root is generated.

  • The Merkle root is stored in the block header. Any change to a transaction alters the root, making tampering detectable.

• Use Cases:

  • Bitcoin: Verifies transactions without downloading the entire block.

  • Ethereum: Part of the block header for transaction validation.

Patricia Tries (Merkle Patricia Tries)

• Purpose: Efficiently store and retrieve key-value data (e.g., account balances, smart contract states).

• How It Works:

  • Combines a trie (prefix tree) with Merkle hashing.

  • Each node is hashed, and the root hash represents the entire dataset.

  • Enables succinct proofs to verify data inclusion or state changes.

• Use Cases:

  • Ethereum: Stores account states, transaction receipts, and transaction lists.

  • Enables light clients to verify balances without storing the full blockchain.

Block and Block Header Structures

Block Structure

• Header: Contains metadata for validation and linking to the previous block.

  • Components:

    • Previous Block Hash: Links to the prior block, forming the chain.

    • Merkle Root: Hash of all transactions in the block.

    • Timestamp: When the block was mined.

    • Nonce: Random number used in mining (PoW).

    • Difficulty Target: Mining complexity (PoW).

  • Example: Bitcoin’s header is 80 bytes; Ethereum’s includes state roots.

• Body: Contains the list of transactions or smart contract operations.

Key Roles:

• Immutability: Changing any transaction invalidates the Merkle root, breaking the chain.

• Efficiency: Light clients verify transactions using Merkle proofs without full block data.

CAP Theorem and Blockchain Design

CAP Theorem Overview

A distributed system can guarantee only two of three properties:

• Consistency (C): All nodes see the same data simultaneously.

• Availability (A): The system remains operational despite node failures.

• Partition Tolerance (P): The system functions during network splits.

Blockchain Implications

• Partition Tolerance (P) is Mandatory: Blockchains are decentralized and must handle network splits.

• Tradeoffs:

  • Public Blockchains (AP): Prioritize Availability and Partition Tolerance.

    • Example: Bitcoin and Ethereum tolerate temporary inconsistencies (e.g., forks) but resolve them via consensus (eventual consistency).

    • During partitions, nodes may see different chains until the network reconciles.

  • Private/Permissioned Blockchains (CP): Prioritize Consistency and Partition Tolerance.

    • Example: Hyperledger Fabric ensures all nodes agree on the state, even if some are offline.

CAP in Practice

• Eventual Consistency: Public blockchains achieve consistency over time (e.g., through longest-chain rules).

• Tradeoff Challenges:

  • Scalability vs. Security: High throughput (e.g., Solana) risks centralization or reduced decentralization.

  • Finality: Some chains (e.g., Ethereum post-merge) use checkpointing for faster finality.