Authentication Path for a Merkle Tree

This page looks at how to compute and verify the authentication path for a Merkle Tree.

We use JavaScript to display the mathematics on this page. Please enable JavaScript in your browser for it to work.

Paths in a binary tree

Here is an 8-node tree with each node indexed $0,1,\ldots$ from left to right at each level. The value in magenta is the value of that index expressed in binary.

Paths in a binary tree

The leaf values $Y_0, \ldots, Y_7$ are the secret keys. The nodes at height 0 are referred to as the public keys. The public key is computed by $H(Y_i)$, for some hash function $H()$.

On-path nodes

For the example secret key $Y_6$ we have $idx=6$. We express the index in binary with $a$ binary digits: $6 = 110’b$. We can use these binary digits to plot a path from the root to our required leaf at index 6.

Start at the root node, for each digit in the binary representation move down left if the digit is 0 and move down right if the digit is 1. Following the binary numbers, you can see it goes
$0 + \color{blue}{1} \rightarrow \color{magenta}{1} + \color{blue}{1} \rightarrow \color{magenta}{11} + \color{blue}{0} \rightarrow \color{magenta}{110}$.

This gets us to $node(0,6)$ as shown by the blue line in the diagram. These nodes on the path (shown blue) are called the on-path nodes.

Computing the authentication path

The authentication path nodes are the siblings of the on-path nodes. If the on-path node has index $idx$ then the authentication path node is given by $idx \oplus 1$, where $\oplus$ is the bitwise XOR operation. In Python idx ^ 1.

The operation $n \oplus 1$ equals $n+1$ if $n$ is even and $n-1$ if $n$ is odd (it flips the least-significant bit). This is exactly the calculation we need to find the index of the sibling node.

To find the parent of a node with index $idx$ compute $\lfloor idx/2 \rfloor$. In Python idx // 2 or idx >> 1.

If the height of the tree is $a$ then the authentication path has exactly $a$ values, one at each height $0 \le h \lt a$.

To compute the values of the authentication nodes at heights above zero, we need to recursively compute the values of their children.

Note that this will require computing the value of all nodes in the tree except the on-path nodes.

To find the index of the authentication node on the next level up, compute $\lfloor idx/2 \rfloor \oplus 1$. In Python

a = 3 # Number of levels
idx = 6 # leaf index
authpath = [0] * a
authpath[0] = idx ^ 1
for i in range(1, a):
    idx = idx // 2
    authpath[i] = idx ^ 1
print(authpath)  # [7, 2, 0]

Example Merkle Tree

Here is a simple example of a Merkle tree. To make the representation of the tree manageable, we cheat and simplify the hash function so it only outputs a digest value of 4 bytes (see below). This is obviously not secure, but it makes displaying the results less cumbersome, and still shows the underlying concept.
In this example, we have eight secret key values, $Y_0,\ldots,Y_7$, each 4 bytes long represented in hexadecimal. These secret keys are computed using a hash function make_sk over a secret "seed" and the position of the key in the tree.
We use the notation $(h, i)$ to denote the node at height $h$ with index $i$, numbered from left to right starting at 0.
The leaf nodes at height $0$ contain the 4-byte hash of each key, $(0,i)=H(Y_i)$. These are the public keys.
Each internal node contains the hash of its left and right child node value, $H(\mathtt{left} || \mathtt{right})$

Simple Merkle tree

The authentication path for $Y_6$ is $(0,7) \rightarrow (1,2) \rightarrow (2,0)$.
In this case we have leaf $Y_6=\texttt{20149512}$ and the authentication path values are
- $(0,7) = \texttt{8fc53ad8}$
- $(1,2) = \texttt{7890c8b6}$
- $(2,0) = \texttt{076f83f6}$
Given these values, a verifier can recompute the value of the root node and compare this to the published root value.

Computing the root node

Uising our notation above, the root node is $node(a, 0)$. This value is stored as part of a Merkle signature and is used to verify an authentication path for a revealed secret key.

To compute the root node we always need to compute every node in the tree. There are different ways to do this. You can use the TreeHash algorithm and compute node(a, 0). Or, simpler, just compute the $2^a$ nodes at the base of the tree, then compute the pairwise hashes of each level until you reach a array of length one.

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 value of the hex string input then truncated.)

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 in pseudocode.

Revealed secret key, Y_6='20149512'
authpath=['8fc53ad8', '7890c8b6', '076f83f6']
node(0,6)=H(Y_6)=H('20149512')='ef137f8f'
node(0,7)=authpath[0]='8fc53ad8'
node(1,3)=H('ef137f8f'+'8fc53ad8')='e090b2ce'
node(1,2)=authpath[1]='7890c8b6'
node(2,1)=H('7890c8b6'+'e090b2ce')='009a4350'
node(2,0)=authpath[2]='076f83f6'
root=node(3,0)=H('076f83f6'+'009a4350')='03583268'

Python code

Our simple function make_sk to derive the private key value is

def make_sk(sk_seed, height, index):
    """Generate a private key value given a secret key and address.

    :param str sk_seed: Secret key seed (hex string).
    :param int height: Height value to encode into address.
    :param int index: Index value to encode into address.
    :return: Derived private key value (4-byte hash as hex string).
    :rtype: str
    """
    adrs = "{:04x}".format(height) + "{:04x}".format(index)
    DPRINT("adrs=", adrs, bytes.fromhex(adrs))
    return H(seed + adrs)

# Generate all keys at leaf level 0
sk_seed = '900150983cd24fb0'  # The first 8 bytes of MD5('abc')
keys = [make_sk(sk_seed, 0, i) for i in range(8)]
print("keys =", keys)
# ['827efcd2', '29bb074b', 'a92eb2d2', 'e411ba45', 'f7d5e02e', 'a1644275', '20149512', '286c0ebd']

Generating the complete tree using `hash_pairwise`

A straightforward way to generate the entire tree is to take an array of $2n$ nodes and hash the values “pairwise” to create a new array of $n$ nodes. This can be repeated until we have only one node left - the root node.

def hash_pairwise(hashes):
    """Hash 2n hex values pairwise.

    :param list hashes: Array of 2*n hex strings to be hashed pairwise.
    :return: Array of n hex-encoded hash strings H(node_{2i} || node_{2i+1})
             for 0 <= i < n.
    :rtype: list
    """
    n = len(hashes) // 2
    out = ['' for x in range(n)]
    for i in range(n):
        h = H(hashes[2 * i] + hashes[2 * i + 1])
        out[i] = h
    return out

# Hash the keys to leaf nodes
hashes = [H(k) for k in keys]
print("leaf nodes=", hashes)

# Compute the Merkle tree nodes
while (len(hashes) > 1):
    hashes = hash_pairwise(hashes)
    print(hashes)

root = hashes[0]
print(f"Root node is {root}")
assert(root == "03583268")

Output:

keys = ['827efcd2', '29bb074b', 'a92eb2d2', 'e411ba45', 'f7d5e02e', 'a1644275', '20149512', '286c0ebd']
size=8
leaf nodes= ['33d97727', 'cbe3b654', 'db516084', 'c700ae29', '59bb626f', '804c9bdb', 'ef137f8f', '8fc53ad8']
['9aed1e96', '2da82279', '7890c8b6', 'e090b2ce']
['076f83f6', '009a4350']
['03583268']
Root node is 03583268

Generating the authentication path using the TreeHash algorithm

The following Python code demonstrates the TreeHash algorithm using our simple hash function. gen_auth_path generates the authentication path for a given leaf, working up the tree using the “XOR with one” trick to find the sibling node. compute_node computes the value of a node in the tree, recursively computing each descendent.

def compute_node(sk_seed, i, z):
    """Compute a node in the Merkle tree.

    :param str sk_seed: Secret key seed (hex string).
    :param int i: Index of the node.
    :param int z: Height of the node.
    :return: Hash value of the node.
    :rtype: str
    """
    node = None
    if z == 0:
        sk = make_sk(sk_seed, 0, i)
        node = H(sk)
        DPRINT(f"node: i = {i} sk={sk} node={node}")
    else:
        lnode = compute_node(sk_seed, 2*i, z-1)
        rnode = compute_node(sk_seed, 2*i + 1, z-1)
        node = H(lnode + rnode)
        DPRINT(f"node: ({z},{i}) {lnode}||{rnode} = {node}")
    return node

def gen_auth_path(sk_seed, a, idx):
    """Generate authentication path (AUTH) for a leaf.

    :param str sk_seed: Secret key seed (hex string).
    :param int a: Height of the AUTH path.
    :param int idx: Leaf index for which to generate the AUTH.
    :return: List of node hashes (hex strings) forming the AUTH path.
    :rtype: list
    """
    auth = [None] * a
    for j in range(a):
        s = idx // (1 << j) ^ 1
        DPRINT(f"j={j} s={s}")
        auth[j] = compute_node(sk_seed, s, j)
        DPRINT(f"auth[{j}]={auth[j]}")
    return auth
        
a = 3
idx = 6
print(f"leaf_index={idx}")
print(f"sk[{idx}]={keys[idx]}")
auth = gen_auth_path(sk_seed, a, idx)
print("auth =", auth)
# auth = ['8fc53ad8', '7890c8b6', '076f83f6']

# Compute root node
DPRINT("Computing root...")
root = compute_node(sk_seed, 0, a)
print(f"root={root}")
assert(root == '03583268')

Output:

leaf_index=6
sk[6]=20149512
auth = ['8fc53ad8', '7890c8b6', '076f83f6']
root=03583268

Alternatively, we can use the hash_pairwise function to compute the authentication path, given the value of all 8 public keys

# Hash the keys to leaf nodes
hashes = [H(k) for k in keys]
print("public keys =", hashes)

# Compute AUTHPATH given public keys in `hashes` 
a = 3
idx = 6
print(f"leaf_index={idx}")
print(f"sk[{idx}]={keys[idx]}")
authpath = ['' for x in range(a)]
i = idx ^ 1
j = 0
authpath[j] = hashes[i]
for j in range(1, a):
    hashes = hash_pairwise(hashes)
    i = (i // 2) ^ 1
    authpath[j] = hashes[i]
print("authpath =", authpath)
# authpath = ['8fc53ad8', '7890c8b6', '076f83f6']

public keys = ['33d97727', 'cbe3b654', 'db516084', 'c700ae29', '59bb626f', '804c9bdb', 'ef137f8f', '8fc53ad8']
leaf_index=6
sk[6]=20149512
authpath = ['8fc53ad8', '7890c8b6', '076f83f6']

Verifying the authentication path

Show that the hard-coded authentication path above can be verified, knowing the trusted root value and revealed secret key.

# 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
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)

Output:

authpath= ['8fc53ad8', '7890c8b6', '076f83f6']
sk=20149512
pk=ef137f8f
(ht,idx)=0,6
child node=ef137f8f
authpath=8fc53ad8
m1,m2=ef137f8f 8fc53ad8
node=e090b2ce
(ht,idx)=1,3
child node=e090b2ce
authpath=7890c8b6
m1,m2=7890c8b6 e090b2ce
node=009a4350
(ht,idx)=2,1
child node=009a4350
authpath=076f83f6
m1,m2=076f83f6 009a4350
node=03583268
Required root=03583268

<< previous: Merkle Tree

Contents

next: Few Time Signature (FTS) >>

Rate this page

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 16 February 2026.

Authentication Path for a Merkle Tree

Paths in a binary tree

On-path nodes

Computing the authentication path

Example Merkle Tree

Computing the root node

Calculations for example Merkle tree

Python code

Generating the complete tree using hash_pairwise

Generating the authentication path using the TreeHash algorithm

Verifying the authentication path

Rate this page

Contact us

Generating the complete tree using `hash_pairwise`