The Hyper Tree Signature (SIG_HT)

The SLH-DSA hypertree is a tree-of-trees of $d$ Merkle subtrees each of which signs the root value of its subtree using the WOTS+ signature algorithm.

Introduction to the Hypertree | Our example | Recap on WOTS+ signature | The first WOTS+ signature | First authentication path | Second HT subtree layer 1 | Tree addresses and leaf indexes going up the HT tree | Contact us

Introduction to the Hypertree

The Hyper Tree Signature (SIG_HT) consists of $d$ XMSS signatures^[1]. Each XMSS signature consists of a WOTS+ signature of $len \cdot n$ bytes and $h’=h/d$ authentication path values each of $n$ bytes. The length of the hypertree signature is $(h + d\cdot len) \cdot n$ bytes.

In our example, using SHA2-128f, we have $n=16$, $d=22$, $h=66$, $h'=h/d=3$ and $len=35$.

Thus we have $d=22$ Merkle subtrees, each WOTS+ signature is $len \cdot n = 560$ bytes, and each authentication path consists of $h'=3$ values of $n=16$ bytes. The complete HT signature consists of $(h + d\cdot len) \cdot n = (66 + 22 \times 35) \times 16 = 13376$ bytes.

The input to the first WOTS+ signature at layer 0 is the FORS public key value (FORS_PK). The input to subsequent WOTS+ signatures at layers $1$ to $d-1$ is the XMSS public key computed from the previous level. The final root of the hypertree should match the published public key value PK.root.

^[1] XMSS stands for eXtended Merkle Signature Scheme, a concept defined in RFC 8391. But note that SLH-DSA does not implement the actual XMSS scheme as described there. Think of it as a convenient way to describe the structure of SIG_HT (or, alternatively, as a way to confuse the reader).

Our example

Algorithm: SLH-DSA-SHA2-128f
n=16, w=16, h=66, d=22, h'=h/d=3, len=len1+len2=32+3=35

SLH-DSA private key [4n bytes]
D5213BA4BB6470F1B9EDA88CBC94E627   # SK.seed
7A58A951EF7F2B81461DBAC41B5A6B83   # SK.prf
FA495FB834DEFEA7CC96A81309479135   # PK.seed
A67029E90668C5A58B96E60111491F3D   # PK.root

Input to WOTS+ = FORS_PK = 33af163817cd6c2bea881ddf7d2b89ab [32 bytes]

Recap on WOTS+ signature

Recall the basics of a Winternitz One-Time Signature (WOTS)

Given the Winternitz parameter, $w$, and the security parameter, $n$, we compute $len = len_1 + len_2$ where

$len_1 = \lceil 8n/\log(w) \rceil, \quad len_2 = \lfloor \log(len_1 \cdot (w-1))/\log(w) \rfloor + 1$.

In our case with $w=16$ and $n=16$, we obtain $len_1 = 32$ and $len_2 = 3$ giving $len = 35$.

An input message $m$ is interpreted as $len_1$ base-$w$ integers $m_i$, between $0$ and $w-1$. A checksum is computed, $C = \sum_{i=1}^{len_1}(w -1 - m_i)$ over these values, represented as a string of $len_2$ base-$w$ values $C=(C_1, \ldots, C_{len_2})$.

In our example, the input is broken up into 32 blocks of $\log_2(w)=4$ bits and a checksum is computed over these values and broken up into three 4-bit blocks. These blocks are interpreted as integers, denoted $m_0, m_1, \ldots, m_{34}$.

We have a WOTS private key, $sk_0, sk_1, \ldots, sk_{34}$. These values can be computed using SK.seed and the ADRS.

The signature is $\sigma_0, \sigma_1, \ldots, \sigma_{34}$, where $\sigma_i = F^{m_i}(sk_i)$. This is published in the SIG_HT signature value.

The WOTS public key is $pk_0, pk_1, \ldots, pk_{34}$, where $pk_i = F^{w}(sk_i)$. This can either be derived (by anyone) from the signature or directly (by the signer) from the secret keys.

The first WOTS+ signature

To compute a WOTS+ signature, we split up the input into $len_1=32$ blocks of $\log_2(w)=4$ bits, and append a checksum of length $len_2 = 3$ blocks.

Input=33af163817cd6c2bea881ddf7d2b89ab
Input blocks = 0x3, 0x3, 0xa, 0xf, ..., 0xa, 0xb
checksum = 0x0d6 = 0x0, 0xd, 0x6
Final blocks = 0x3, 0x3, 0xa, 0xf, ..., 0xa, 0xb, 0x0, 0xd, 0x6
             =   3,   3,  10,  15, ...,  10,  11,   0,  13,  6
len=35
m = [3, 3, 10, 15, 1, 6, 3, 8, 1, 7, 12, 13, 6, 12, 2, 11, 14,
  10, 8, 8, 1, 13, 13, 15, 7, 13, 2, 11, 8, 9, 10, 11, 0, 13, 6]

# @file wots_checksum.py
"""Split 16-byte message into 4-bit blocks then append 3 x 4-bit checksum."""
w = 16
def wots_chain(msghex, show_debug=False):
    # Split hex string into list of 4-bit nibbles
    # (Cheat: we can just split hex string into separate digits)
    msg = [int(x, 16) for x in msghex]
    if show_debug: print(f"Input blocks={msg}")
    # Compute csum
    csum = 0
    for i in range(len(msg)):
        csum += int(w - 1 - msg[i]) 
    csum &= 0xfff   # truncate to 12 bits
    if show_debug: print(f"checksum={csum:03x}")
    msg.append((csum >> 8) & 0xF)
    msg.append((csum >> 4) & 0xF)
    msg.append((csum >> 0) & 0xF)
    return msg

# Input FORS public key to first WOTS signature
input = '33af163817cd6c2bea881ddf7d2b89ab'
print(f"Input={input}")
msg = wots_chain(input, show_debug=True)
print("Final blocks =", [hex(x) for x in msg])
print(f"len={len(msg)}")
print("m =", msg)

For each integer of value $m_i$ $(i = 0,\ldots, 34)$ we compute the secret key $sk_i$ using the PRF function and then compute $F^{m_i}(sk_i)$, the value of $F$ iterated $m_i$ times on $sk_i$.

For the first WOTS+ private key, at level 0 with tree address 0x7cdcef4b8fdb03b0 and leaf index 0, we have an ADRS type WOTS_PRF (5) and

PK.seed = FA495FB834DEFEA7CC96A81309479135
SK.seed = D5213BA4BB6470F1B9EDA88CBC94E627
ADRS_c = 00 7cdcef4b8fdb03b0 05 00000000 00000000 00000000
wots_sk[0] = PRF(PK.seed, SK.seed, ADRS_c)
   = SHA256(BlockPad(PKseed) + ADRS_c + SKseed)[:32]
   = 63e73e813025f3da3eaacd528833f005

We have $m_0 = 3$, so we compute $F^{3}(sk_0)$ noting that ADRS has type WOTS_HASH (0) and the tree index changes on each iteration.

                                                [tree_index]
i=0 ADRS=00 7cdcef4b8fdb03b0 00 00000000 00000000 00000000
in=63e73e813025f3da3eaacd528833f005
F(PK.seed, ADRS, in)=53d510380d670414c3f6bca4cb2c9bb8
i=1 ADRS=00 7cdcef4b8fdb03b0 00 00000000 00000000 00000001
in=53d510380d670414c3f6bca4cb2c9bb8
F(PK.seed, ADRS, in)=0171b3b9876713ed645cd59b19c44b36
i=2 ADRS=00 7cdcef4b8fdb03b0 00 00000000 00000000 00000002
in=0171b3b9876713ed645cd59b19c44b36
F(PK.seed, ADRS, in)=a328a052f8f91d66a4ab9a12263bb318
ht_sig[0][0]:a328a052f8f91d66a4ab9a12263bb318

a328a052f8f91d66a4ab9a12263bb318  # ht_sig[0][0]

Set SIG_HT = ht_sig[0][0]

This procedure is repeated for all 35 integers $m_i$.

For the final $m_i$, $i = 34 = \text{0x}22$ we have

ADRS_c = 00 7cdcef4b8fdb03b0 05 00000000 00000022 00000000
wots_sk[34] = PRF(PK.seed, SK.seed, ADRS_c)
   = SHA256(BlockPad(PKseed) + ADRS_c + SKseed)[:32]
   = 7ab9ab16844abff424d3c775727b9fe0

and $m_{34} = 6$, so we compute $F^{6}(sk_{34})$

i=0 ADRS=00 7cdcef4b8fdb03b0 00 00000000 00000022 00000000
in=7ab9ab16844abff424d3c775727b9fe0
F(PK.seed, ADRS, in)=ff34a30ddfd7d52148d911b970880599
i=1 ADRS=00 7cdcef4b8fdb03b0 00 00000000 00000022 00000001
in=ff34a30ddfd7d52148d911b970880599
F(PK.seed, ADRS, in)=70a815bf753e466da488d3738b912440
...[CUT]...
i=5 ADRS=00 7cdcef4b8fdb03b0 00 00000000 00000022 00000005
in=249dacc697b2756b5f2701e43d637ad9
F(PK.seed, ADRS, in)=e08660ab55a3008385ae75fa4746ea8d
ht_sig[0][34]:e08660ab55a3008385ae75fa4746ea8d

e08660ab55a3008385ae75fa4746ea8d  # ht_sig[0][34]

Set SIG_HT = SIG_HT || ht_sig[0][i] for $i=1,\ldots, 34$

All 35 HT signature values (560 bytes in total) are output to the first HT signature ht_sig[0]:

a328a052f8f91d66a4ab9a12263bb318  # ht_sig[0][0]
4367731930b4789490bf4594ef7a0163  # ht_sig[0][1]
# [...CUT...]
e08660ab55a3008385ae75fa4746ea8d  # ht_sig[0][34]

Python code

For example Python code to compute the above values, see wots_ht_0.py

This diagram demonstrates how the HT signature is derived from the input.

The input is either the root of the lower HT tree root[i-1] or the FORS public key for the bottom HT tree at layer 0. The input is split into 32 4-bit blocks (shown orange) and the 3 x 4-bit checksum is shown in green.

First authentication path

For the WOTS+ algorithm in our example, we have $len=35$.

NOTE: the computations of the WOTS+ public key and its authentication path are completely independent of the HT signature value. They depend solely on the tree address of the WOTS+ subtree and PK.seed.

The WOTS+ public key is computed by calculating $F^w(sk_i)$ for $0\le i \lt 35$ and concatenating the 35 $n$-byte values. The 560 bytes of the WOTS public key are compressed using $T_{len}$ to obtain the $n$-byte leaf value.

For our example at layer 0 with tree_address=0x7cdcef4b8fdb03b0 and tree_idx=0 we generate the WOTS+ private keys using address type WOTS_PRF (5) and the PRF function. Then use the chain function to compute the corresponding WOTS+ public key $pk=F^w(sk)$ where the ADRS is of type WOTS_HASH (0) and the position in the chain is updated each time before using F.

Generate WOTS+ private key for subtree[0]
this_leaf=0
00 7cdcef4b8fdb03b0 00 00000000 00000000 00000000
sk[0]=63e73e813025f3da3eaacd528833f005
adrs=007cdcef4b8fdb03b000000000000000000000000000
F(0)= 53d510380d670414c3f6bca4cb2c9bb8
adrs=007cdcef4b8fdb03b000000000000000000000000001
F(1)= 0171b3b9876713ed645cd59b19c44b36
adrs=007cdcef4b8fdb03b000000000000000000000000002
F(2)= a328a052f8f91d66a4ab9a12263bb318
#...[CUT...
adrs=007cdcef4b8fdb03b00000000000000000000000000d
F(13)= d3550819ad48bb2e1ec418435e4241f8
adrs=007cdcef4b8fdb03b00000000000000000000000000e
F(14)= 6aaf81cf7d6256f3432b7a5dd1e2839f
pk=6aaf81cf7d6256f3432b7a5dd1e2839f

This calculation is repeated for each of the other 7 leaves in this subtree in order to calculate the authentication path and the tree root.

Python code

wots_ht_0_authpath.py

For layer=0 the authentication path from the leaf to the subtree root can be computed, and this $3n$-byte value is added to the signature value:

de051b9900aab1f5015f0edac6f6c4aa  # ht_auth_path[0]
b0fea3741512bc254e9e2d07c1eb010c
88378feae0988ef4202eea1238ada111

Set SIG_HT = SIG_HT || ht_auth_path[0]

The combination of the 560-byte WOTS+ signature and these 3 $n$-byte authentication paths makes up the XMSS signature, which is included in the HT signature.

The root of this subtree is af0daeccc5501e78851bf9a7896945b5. This is passed as input to the next-higher WOTS+ subtree at layer 1.

The above procedure of computing the $35n$ ht_sig[i] value and the $3n$ authentication path is repeated $d=22$ times. The final root value for the tree at height 0 should equal the published PK.root value in the public key.

Second HT subtree layer 1

leaf_index = tree_address & (2^3 - 1) 
  = 0x28daecdc86eb8761 & 0x7 
  = 1
tree_address = tree_address >> 3
  = 0x28daecdc86eb8761 >> 3
  = 0x51b5d9b90dd70ec

01 051b5d9b90dd70ec 00 00000001 00000000 00000000

35d085225f2c8b976e473afb04ee2801  # ht_sig[1][0]
da342b7fe35fea3966f79c4d167d5aee  # ht_sig[1][1]
#...[CUT]...]
57abba24274d8214a1a825c2f3c8d252  # ht_sig[1][34]

fb2b765aaa0a3beff0da54cbc829529e # ht_auth_path[1]
19b02347b8f91bb92813756c8413b6dd
145c0146b0c77cc9d01c6fceee99a84c

ac592b91178549ebcdc6457337398ee9  # ht_sig[21][0]
0ebe8ef74ae489c0f292bc7e2e5c0692  # ht_sig[21][1]
#...[CUT]...]
b3417643f1ee536de7fa9678eca1b0bc  # ht_sig[21][34]

d7685e5ea26c07d38628ff7ca45ced0e # ht_auth_path[21]
f8004b41e6461e1ea61c2b3f20da8e33
272e8dbbe09a7374427301cf432b77b6

Tree addresses and leaf indexes going up the HT tree

At level 0, the tree address is a number between 0 and $2^{h-h’}-1$, in our case $\{0, 2^{63}-1\}$, and the leaf index is in the range $\{0, h’-1\}$, in our case $0-7$. These two values are derived deterministically from the value of $H_{msg}$.

As we move up the hypertree, the layer, $i$, increases by one, the new tree address and leaf index are computed as follows:

leaf_index[i] = tree_address[i-1] & 0x7    # (2^h' - 1)
tree_address[i] = tree_address[i-1] >> 3   # h'

At the top of the hypertree, we have a single Merkle tree at layer = $d-1$ with tree address 0. The value of the root of this tree calculated as above should be equal to value of the public key root PK.root computed at key generation time.

In our case, for $d=22$, we have the following base ADRS values going up the HT tree:

              layer   treeaddr   type idxleaf 
              [1]          [8]    [1]     [4]
layer= 0,ADRS=00 7cdcef4b8fdb03b0 00 00000000 00000000 00000000
layer= 1,ADRS=01 0f9b9de971fb6076 00 00000000 00000000 00000000
layer= 2,ADRS=02 01f373bd2e3f6c0e 00 00000006 00000000 00000000
layer= 3,ADRS=03 003e6e77a5c7ed81 00 00000006 00000000 00000000
layer= 4,ADRS=04 0007cdcef4b8fdb0 00 00000001 00000000 00000000
layer= 5,ADRS=05 0000f9b9de971fb6 00 00000000 00000000 00000000
layer= 6,ADRS=06 00001f373bd2e3f6 00 00000006 00000000 00000000
layer= 7,ADRS=07 000003e6e77a5c7e 00 00000006 00000000 00000000
layer= 8,ADRS=08 0000007cdcef4b8f 00 00000006 00000000 00000000
layer= 9,ADRS=09 0000000f9b9de971 00 00000007 00000000 00000000
layer=10,ADRS=0a 00000001f373bd2e 00 00000001 00000000 00000000
layer=11,ADRS=0b 000000003e6e77a5 00 00000006 00000000 00000000
layer=12,ADRS=0c 0000000007cdcef4 00 00000005 00000000 00000000
layer=13,ADRS=0d 0000000000f9b9de 00 00000004 00000000 00000000
layer=14,ADRS=0e 00000000001f373b 00 00000006 00000000 00000000
layer=15,ADRS=0f 000000000003e6e7 00 00000003 00000000 00000000
layer=16,ADRS=10 0000000000007cdc 00 00000007 00000000 00000000
layer=17,ADRS=11 0000000000000f9b 00 00000004 00000000 00000000
layer=18,ADRS=12 00000000000001f3 00 00000003 00000000 00000000
layer=19,ADRS=13 000000000000003e 00 00000003 00000000 00000000
layer=20,ADRS=14 0000000000000007 00 00000006 00000000 00000000
layer=21,ADRS=15 0000000000000000 00 00000007 00000000 00000000

from slh_adrs import Adrs
PKseed = 'FA495FB834DEFEA7CC96A81309479135'
w = 16
d = 22
# Starting tree address at layer 0
tree_addr = 0x7cdcef4b8fdb03b0 
tree_idx = 0
print("              layer   treeaddr   type idxleaf ")
print("              [1]          [8]    [1]     [4]")
for layer in range(d):
    adrs = Adrs(Adrs.WOTS_HASH, layer=layer)
    adrs.setTreeAddress(tree_addr)
    adrs.setKeyPairAddress(tree_idx)
    print(f"layer={layer:2d},ADRS={adrs.toHexSP()}")
    # Compute next tree address
    tree_idx = tree_addr & 0x7
    tree_addr >>= 3

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.