blockchain.merkle_tree
======================

.. py:module:: blockchain.merkle_tree

.. autoapi-nested-parse::

   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
---------

.. autoapisummary::

   blockchain.merkle_tree.build_merkle_tree
   blockchain.merkle_tree.merkle_root
   blockchain.merkle_tree.sha256
   blockchain.merkle_tree.verify_proof


Module Contents
---------------

.. py:function:: 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


.. py:function:: 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


.. py:function:: 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'


.. py:function:: 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