# @file merkle_authpath_verify.py 
# @version 1.1 (2026-01-16T11:51Z)
# @author David Ireland <https://di-mgt.com.au/contact>
# @copyright 2023-26 DI Management Services Pty Ltd
# @license Apache-2.0

"""Verify authentication path for a simple Merkle tree."""

import hashlib

def H(val: str) -> str:
    """Weak hash function that returns a 4-byte hash.

    :param str val: Hex-encoded input.
    :return: Four-byte hash of input encoded in hex.
    :rtype: str
    """
    return hashlib.sha256(bytes.fromhex(val)).hexdigest()[:8]


# Required root value in Merkle tree
root = "03583268"
# Authentication path
authpath = [
"8fc53ad8",
"7890c8b6",
"076f83f6",
]
print("authpath=", [x for x in authpath])
# Known key value
sk = "20149512" # Y_6
print(f"sk={sk}")

# Compute leaf value above sk
idx = 6  # 0-based index of Y_4
ht = 0
node = H(sk)  # leaf node (public key)
print(f"pk={node}")

for ap in authpath:
    print(f"(ht,idx)={ht},{idx}")
    # Get last bit of child idx
    lastbit = idx & 1
    # Move up to next level
    idx >>= 1
    ht += 1
    print(f"child node={node}")
    print(f"authpath={ap}")
    # Last bit of child determines left/right order of authpath
    if (lastbit):
        print(f"m1,m2={ap} {node}") 
        node = H(ap + node)
    else:
        print(f"m1,m2={node} {ap}") 
        node = H(node + ap)
    print(f"node={node}")

print(f"Required root={root}")
assert(root == node)