2.3 Merkle trees and blockchain data structures

Merkle trees are fundamental data structures in blockchain technology, enabling efficient verification and tamper-evidence. These hierarchical structures use hashing to create a root hash that summarizes entire datasets, allowing quick comparisons and lightweight verification.

Blockchain data structures offer scalability and security benefits. They enable lightweight synchronization and efficient light client verification, while ensuring data integrity. However, different structures like Patricia trees and Bloom filters come with trade-offs in complexity, storage overhead, and accuracy.

Merkle Trees

Structure and properties of Merkle trees

Top images from around the web for Structure and properties of Merkle trees

• 

  Blockchain, Consensus, and Databases View original

  Is this image relevant?

• 

  Árbol de Merkle - Wikipedia, la enciclopedia libre View original

  Is this image relevant?

• 

  DSHR's Blog: Blockchain: What's Not To Like? View original

  Is this image relevant?

• 

  Blockchain, Consensus, and Databases View original

  Is this image relevant?

• 

  Árbol de Merkle - Wikipedia, la enciclopedia libre View original

  Is this image relevant?

1 of 3

Top images from around the web for Structure and properties of Merkle trees

• 

  Blockchain, Consensus, and Databases View original

  Is this image relevant?

• 

  Árbol de Merkle - Wikipedia, la enciclopedia libre View original

  Is this image relevant?

• 

  DSHR's Blog: Blockchain: What's Not To Like? View original

  Is this image relevant?

• 

  Blockchain, Consensus, and Databases View original

  Is this image relevant?

• 

  Árbol de Merkle - Wikipedia, la enciclopedia libre View original

  Is this image relevant?

1 of 3

• Hierarchical data structures efficiently verify data integrity in blockchain networks
  • Binary tree structure consists of non-leaf nodes hashing two child nodes and leaf nodes hashing individual data blocks or transactions (Bitcoin, Ethereum)
  • Root hash summarizes the entire dataset acts as a fingerprint of the data
• Properties enable efficient verification, tamper-evidence, and space-efficiency
  • Comparing root hashes quickly detects changes in the dataset without needing to compare all data
  • Merkle proofs verify inclusion of specific data without requiring the entire dataset (SPV clients)
  • Tamper-evident as any changes to underlying data alter the root hash, making tampering detectable
  • Space-efficient by storing only the root hash and relevant branches for verification, reducing storage overhead (block headers)

Construction of Merkle trees

• Constructing a Merkle tree starts with leaf nodes and builds bottom-up
  • Calculate the hash of each individual transaction or data block to create leaf nodes (SHA-256)
  • Pair adjacent leaf nodes and hash their concatenated values to create parent nodes
  • Repeat the process until a single root hash is obtained
• Navigating a Merkle tree using Merkle proofs and verification
  • Merkle proofs provide a path from a specific leaf node to the root, including hash values of sibling nodes at each level
  • Verifying Merkle proofs involves recalculating the root hash using the provided leaf node and sibling hashes
  • Compare the calculated root hash with the known root hash to confirm the data's inclusion and integrity

Blockchain Data Structures

Benefits of blockchain data structures

• Scalability benefits enable lightweight synchronization and efficient light client verification
  • New nodes sync with the network by downloading only block headers containing Merkle root hashes, avoiding the need to download and verify the entire blockchain history (Bitcoin, Ethereum)
  • Light clients verify transactions without storing the full blockchain using Merkle proofs and minimal data (mobile wallets)
• Security benefits ensure data integrity and enable simplified payment verification (SPV)
  • Merkle trees provide a tamper-evident structure, ensuring the integrity of the stored data
  • SPV clients securely verify transactions without downloading the entire blockchain, relying on Merkle proofs and block headers for transaction verification

Trade-offs in blockchain data structures

• Patricia trees (tries) offer efficient storage and retrieval but have higher complexity and storage overhead
  • Advantages: faster account lookups and state transitions for account balances and smart contract states (Ethereum)
  • Disadvantages: complex implementation and higher storage overhead for sparse datasets
• Bloom filters enable efficient membership testing but introduce false positives and require periodic rebuilding
  • Advantages: compact probabilistic data structure for quick verification of transaction inclusion without storing the full transaction history
  • Disadvantages: probabilistic nature introduces false positives and requires periodic rebuilding to maintain desired false positive rates
• Sparse Merkle trees efficiently store and verify large, sparse datasets but have increased complexity and higher proof sizes for non-inclusion
  • Advantages: efficient storage and verification of large, sparse datasets and compact proofs of non-inclusion (proving the absence of data)
  • Disadvantages: increased complexity compared to regular Merkle trees and higher proof sizes for non-inclusion proofs compared to inclusion proofs