Implement and Explain a Merkle Tree

Problem Statement

A Merkle tree is a binary tree where every leaf node represents the cryptographic hash of a data block, and every non-leaf node represents the cryptographic hash of its concatenated children's hashes. Merkle trees enable efficient and secure verification of contents in large data structures.

Implement a MerkleTree class using Python's hashlib.sha256 that supports constructing a tree from a list of string data blocks, generating the Merkle root hash, generating an audit proof for a specific leaf, and verifying a proof against a known root.

Hashing Conventions

• Leaf hash: sha256(data.encode('utf-8')).hexdigest()
• Parent hash: sha256((left_hash + right_hash).encode('utf-8')).hexdigest()
• If a level has an odd number of nodes (greater than 1), duplicate the last node's hash to form a pair.

Class Interface

class MerkleTree:
    def __init__(self, data_blocks: list[str]):
        """
        Initializes the Merkle tree with a non-empty list of data strings.
        """
        pass

    def get_root(self) -> str:
        """
        Returns the hex digest of the Merkle root.
        """
        pass

    def get_proof(self, index: int) -> list[tuple[str, str]]:
        """
        Generates an audit proof for the leaf at `index` (0-based).
        Each element in the proof list is a tuple: (sibling_hash, direction),
        where direction is 'L' if sibling is on the left, or 'R' if on the right.
        The list should be ordered from leaf level up to the root level.
        """
        pass

    @staticmethod
    def verify_proof(data: str, proof: list[tuple[str, str]], root: str) -> bool:
        """
        Verifies whether `data` belongs to the tree represented by `root`
        using the provided `proof`.
        """
        pass

Constraints

• 1 <= len(data_blocks) <= 10^4
• Each block is an ASCII string of length 1 <= len(data) <= 10^3
• 0 <= index < len(data_blocks)

Example

tree = MerkleTree(["a", "b", "c"])
root = tree.get_root()
proof = tree.get_proof(0)

# Leaf 0 has sibling leaf 1 on the right
# Level 0 hashes: [H("a"), H("b"), H("c"), H("c")] (c is duplicated)
# Parent 0: H(H("a") + H("b")), Parent 1: H(H("c") + H("c"))
# Root: H(Parent 0 + Parent 1)

assert MerkleTree.verify_proof("a", proof, root) == True
assert MerkleTree.verify_proof("tampered", proof, root) == False

Edge Cases to Consider

• Single element lists (len(data_blocks) == 1).
• Odd numbers of elements at multiple levels of the tree.