DI Management Home > Cryptography > SPHINCS+ > Merkle Tree

Merkle Tree


The concept of a Merkle Tree as a binary authentication tree was introduced in [MER79].

Merkle Tree with $n=8$

Merkle Tree

Authenticating the leaf values

Example Merkle Tree

Simple Merkle tree

Calculations for example Merkle tree

Our special "weak" hash function $H$ is defined in Python as follows. (Note that the hash digests are computed over the decoded binary values of the hex strings.)

import hashlib
def H(val: str) -> str:
    """Weak hash function returning hex-encoded 4-byte hash."""
    return hashlib.sha256(bytes.fromhex(val)).hexdigest()[:8]

Some sample calculations.

B = H(Y_4) = H(f7d5e02e) = 59bb626f
5 = H(B||C) 
  = H(59bb626f || 804c9bdb) = 7890c8b6
2 = H(5||6)
  = H(7890c8b6 || e090b2ce) = 009a4350
root, 0 = H(1||2) 
  = H(076f83f6 || 009a4350) = 03583268

Python code

Show that the hard-coded authentication path above can be verified, knowing the trusted root value.
# 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)
Output:
authpath= ['804c9bdb', 'e090b2ce', '076f83f6']
key=f7d5e02e
idx=4
child node=59bb626f
authpath=804c9bdb
m1,m2=59bb626f 804c9bdb
node=7890c8b6
idx=2
child node=7890c8b6
authpath=e090b2ce
m1,m2=7890c8b6 e090b2ce
node=009a4350
idx=1
child node=009a4350
authpath=076f83f6
m1,m2=076f83f6 009a4350
node=03583268
Required root=03583268

Benefits of using a Merkle Tree

A warning about Merkle trees

<< previous: Winternitz One-Time Signature (WOTS) Contents next: Basic Merkle Signature Scheme >>

Contact us

To comment on this page or to contact us, please send us a message.

This page first published 17 March 2023. Last updated 17 March 2023.