A simple Merkle Tree implementation (Courtesy: https://www.codementor.io/blog/merkle-trees-5h9arzd3n8)

merkle_tree.py

from hashlib import sha256


class Node:
    """A Merkle tree node
    
    Stores the computed hash and the parent of the node

    Args:
      hash: Hash of the (left + right) children
    """

    def __init__(self, hash):
        self.hash = hash
        self.parent = None
        self.left = None
        self.right = None

    def __str__(self):
        return self.hash


class MerkleTree:
    """A Merkle tree

    Stores the entire tree comprised of Nodes. The tree is recursively
    built in a bottom-up fashion, starting with the leaf nodes and then
    their parents until we reach the root

    Args:
        data_chunks: Chunks of data as ``list`` or ``tuple``
    """

    def __init__(self, data_chunks=None):
        self.leaves = []
        self.__set_leaves(data_chunks)
        self.root = self.__build_tree(self.leaves)

    def __set_leaves(self, data_chunks):
        """Converts data chunks to leaf nodes"""
        for chunk in data_chunks or []:
            self.leaves.append(Node(MerkleTree.compute_hash(chunk)))

    def __create_parent(self, left, right):
        parent = Node(MerkleTree.compute_hash(left.hash + right.hash))
        parent.left, parent.right = left, right
        left.parent, right.parent = parent, parent
        return parent

    def __build_tree(self, leaves):
        if not leaves:
            return None
        n_leaves = len(leaves)
        if n_leaves == 1:
            return leaves[0]
        parents = []
        for i in range(0, n_leaves, 2):
            left = leaves[i]
            right = leaves[i + 1] if i + 1 < n_leaves else left
            parents.append(self.__create_parent(left, right))
        return self.__build_tree(parents)

    def __generate_audit_trail(self, node, trail):
        """Generate audit trail for a node

        Builds up the audit trail for a node in bottom-up fashion

        Args:
            node: Node for which the trail has to be generated
            trail: Accumulator for the final trail
        """
        if node == self.root:
            trail.append(node.hash)
            return
        is_left = node.parent.left == node
        if is_left:
            trail.append((node.parent.right.hash, not is_left))
        else:
            trail.append((node.parent.left.hash, not is_left))
        return self.__generate_audit_trail(node.parent, trail)

    def get_audit_trail(self, chunk_hash):
        trail = []
        for data_node in self.leaves:
            if data_node.hash == chunk_hash:
                self.__generate_audit_trail(data_node, trail)
        return trail

    @staticmethod
    def compute_hash(data):
        data = data.encode("utf-8")
        return sha256(data).hexdigest()


def verify_audit_trail(chunk_hash, audit_trail):
    """Verify the audit trail

    Follow the audit trail and compute the hash until you reach the root.
    Finally, compare the computed hash with the hash of the root.

    Args:
        chunk_hash: Hash of a data chunk
        audit_trail: Audit trail for the chunk
    
    Returns:
        ``bool``: True if legit, False otherwise
    """
    if not audit_trail:
        return False
    proof_so_far = chunk_hash
    for node in audit_trail[:-1]:
        hash, is_left = node
        proof_so_far = MerkleTree.compute_hash(
            hash + proof_so_far if is_left else proof_so_far + hash)
    # Verify the proof so far against the root's hash
    return proof_so_far == audit_trail[-1]