What is a Merkle Proof ?

A Merkle proof, also known as a Merkle tree proof or a Merkle branch, is a method of proving that a specific transaction or piece of data exists within a larger set of transactions or data, without revealing the entire set. This is done by creating a tree of hashes, where each leaf node represents a transaction or piece of data, and each non-leaf node is the hash of its children. A Merkle proof consists of the set of hashes that link a leaf node to the root of the tree, and can be verified by recomputing the hashes and comparing them to the proof.

Py Code.

Python implementation of the same.

from typing import List
import typing
import hashlib


# Node class to construct the Merkle Nodes
class Node:
    def __init__(self, left, right, value: str) -> None:
        self.left: Node = left
        self.right: Node = right
        self.value = value

    @staticmethod
    def hash(val: str) -> str:
        return hashlib.sha256(val.encode('utf-8')).hexdigest()

    @staticmethod
    def doubleHash(val: str) -> str:
        return Node.hash(Node.hash(val))


class MerkleTree:
    def __init__(self, values: List[str]) -> None:
        self.__buildTree(values)

    # Constructing the merkle tree
    def __buildTree(self, values: List[str]) -> None:
        leaves: List[Node] = [
            Node(None, None, Node.doubleHash(e)) for e in values]
        if len(leaves) % 2 == 1:
            # duplicate last elem if odd number of elements since binary.
            leaves.append(leaves[-1:][0])
        self.root: Node = self.__buildTreeRec(leaves)

    def __buildTreeRec(self, nodes: List[Node]) -> Node:
        half: int = len(nodes) // 2

        if len(nodes) == 2:
            return Node(nodes[0], nodes[1], Node.doubleHash(nodes[0].value + nodes[1].value))

        left: Node = self.__buildTreeRec(nodes[:half])
        right: Node = self.__buildTreeRec(nodes[half:])
        value: str = Node.doubleHash(left.value + right.value)
        return Node(left, right, value)

    def printTree(self) -> None:
        self.__printTreeRec(self.root)

    def __printTreeRec(self, node) -> None:
        if node != None:
            print(node.value)
            self.__printTreeRec(node.left)
            self.__printTreeRec(node.right)

    def getRootHash(self) -> str:
        return self.root.value


if __name__ == "__main__":
    elems = ["This", "is", "a", "Simple", "Merkle", "Tree", "Implementation"]
    mtree = MerkleTree(elems)
    print(mtree.getRootHash())

P.S

Bored / Tinkering around cool shit.