blockchain.merkle_tree

Merkle Tree Construction and Verification

This module implements the construction of a Merkle Tree and verification of inclusion proofs for blockchain data integrity.

Each leaf is a SHA-256 hash of a transaction, and internal nodes are computed by hashing the concatenation of their child nodes.

References: https://en.wikipedia.org/wiki/Merkle_tree

Functions

build_merkle_tree(→ list[list[str]])	Build a Merkle Tree from the given leaf nodes.
merkle_root(→ str)	Return the Merkle root hash for a given list of data.
sha256(→ str)	Compute the SHA-256 hash of the given string.
verify_proof(→ bool)	Verify inclusion of a leaf using a Merkle proof.

Module Contents

blockchain.merkle_tree.build_merkle_tree(leaves: list[str]) → list[list[str]]

Build a Merkle Tree from the given leaf nodes.

Args:

leaves: List of data strings (transactions).

Returns:

A list of lists representing tree levels, with the last level containing the Merkle root.

>>> len(build_merkle_tree(["a", "b", "c", "d"])[-1][0])
64

blockchain.merkle_tree.merkle_root(leaves: list[str]) → str

Return the Merkle root hash for a given list of data.

>>> r = merkle_root(["tx1", "tx2", "tx3"])
>>> isinstance(r, str)
True

blockchain.merkle_tree.sha256(data: str) → str

Compute the SHA-256 hash of the given string.

Args:

data (str): Input string.

Returns:

str: Hexadecimal SHA-256 hash of the input.

Example:

>>> sha256("abc")
'ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad'

blockchain.merkle_tree.verify_proof(leaf: str, proof: list[str], root: str) → bool

Verify inclusion of a leaf using a Merkle proof.

Args:

leaf: Original data string. proof: List of sibling hashes up the path. root: Expected Merkle root hash.

Returns:

True if proof is valid, else False.

>>> data = ["a", "b", "c", "d"]
>>> tree = build_merkle_tree(data)
>>> root = tree[-1][0]
>>> leaf = "a"
>>> proof = [sha256("b"), sha256(sha256("c") + sha256("d"))]
>>> verify_proof(leaf, proof, root)
True