Samantha selects a secure hash function \(\mathcal{H}\) (e.g., SHA-256) and a tree height \(h\).

She then generates \(2^h\) one-time signature key pairs \((sk_i, pk_i)\) for \(i = 0\) to \(2^h-1\). Each key pair will be used to sign one message.

For this demonstration, we're using Lamport-Diffie one-time signatures for the underlying signing mechanism.

Samantha now creates the leaf nodes of the Merkle tree by hashing each one-time public key:

\(L_i = \mathcal{H}(pk_i)\) for each one-time public key \(pk_i\)

These leaf nodes form the bottom level of the Merkle tree.

Samantha builds the Merkle tree by hashing pairs of nodes at each level:

For each level \(j\) from \(h-1\) down to 0:

• Each node is computed as \(N_{j,k} = \mathcal{H}(N_{j+1,2k} \| N_{j+1,2k+1})\)
• Where \(\|\) represents concatenation

The root of the tree \(N_{0,0}\) becomes Samantha's public key, which she sends to Victor.

To sign the message, Samantha needs to choose a one-time signature key pair that hasn't been used before.

For this demonstration, she selects key pair \(i\), where the index \(i\) is determined based on the signing sequence (typically starting from 0).

Samantha uses the selected one-time key pair \((sk_i, pk_i)\) to create a one-time signature \(\sigma_i\) of the message \(M\) using the Lamport-Diffie signature algorithm.

Samantha computes the authentication path from leaf \(i\) to the root:

• She identifies index \(i\) in binary form to determine the path through the tree
• For each level, she includes the sibling node of the node on the path
• This creates an authentication path \(Auth_i\) with exactly \(h\) nodes

The complete signature is \(S = (i, pk_i, \sigma_i, Auth_i)\), which Samantha sends to Victor along with the message.

After signing, Samantha marks the \(i\)-th key pair as used to prevent reuse.

This is a critical step because reusing a one-time signature key would compromise security.

Victor first verifies the one-time signature \(\sigma_i\) against the provided one-time public key \(pk_i\) and the message \(M\).

Next, Victor computes the leaf node value \(L_i = \mathcal{H}(pk_i)\).

This is the starting point for verifying the authentication path.

Victor recomputes the root node using the authentication path:

1. He initializes computed node \(CN = L_i\)
2. For each level \(j\) from \(h-1\) down to 0:
   • If \(i\) indicates a left child, he computes \(CN = \mathcal{H}(CN \| Auth_i[j])\)
   • If \(i\) indicates a right child, he computes \(CN = \mathcal{H}(Auth_i[j] \| CN)\)

Finally, Victor compares the computed root value with Samantha's public key \(N_{0,0}\).

The signature is valid only if both:

1. The one-time signature verification succeeds, and
2. The computed root equals Samantha's public key