# @file merkle_authpath_verify.py (2023-03-16T14:29Z)
# @author David Ireland <www.di-mgt.com.au/contact>
# @copyright 2023 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.

    Args:
        val (str): hex-encoded input.

    Returns:
        str: Hex-encoded hash truncated to 4 bytes.
    """
    return hashlib.sha256(bytes.fromhex(val)).hexdigest()[:8]
   

# Required root value in Merkle tree
root = "03583268"
# Authentication path
authpath = [
"804c9bdb",
"e090b2ce",
"076f83f6",
]
print("authpath=", [x for x in authpath])
# Known key value
sk = "f7d5e02e" # Y_4
print(f"key={sk}")

# Compute leaf value above sk
idx = 4  # 0-based index of Y_4
node = H(sk)  # leaf node

for ap in authpath:
    print(f"idx={idx}")
    # Get last bit of child idx
    lastbit = idx & 1
    # Move up to next level
    idx >>= 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)