本日重點：XMSS signature、hypertree

前幾天我們己經實作了 FORS 相關的演算法和 ADRS 的 member function，今天我們將從 FIPS 205 裡學習 hypertree, FORS signature 和 XMSS Signature 彼此的關係。

FIPS 205 第 7 頁

A hypertree is a tree of XMSS trees, as depicted in Figure 1.

Figure 1

從 d 開始看，d 從最上層開始往下減到 0，所以如果是 由下往上計算，layer address 就是由 0 到 d-1.

HT signature 的格式在第 26 頁

每一個 layer，都有一個 XMSS signature，所以我們在 ht_sign 裡找找 xmss_sign， 它會 call d 次 xmss_sign，產生 d 個 XMSS signature (line 3,4,11,12)，然後將這 d 個 XMSS signature 組成 HT signature

Figure 1 的最底下有 FORS signature，於是我們要看 FORS signature 的產生需要什麼，在 FIPS 205 Page 30, 31 這麼說的

The address ADRS must have the layer address set to zero (since the XMSS tree that signs a FORS key is always at layer 0), the tree address set to the XMSS tree that signs the FORS key

於是我們知道 xmss 最底層 layer 0 是用來計算 FORS signature

ht_sign 會產生 d 個 XMSS signature (layer 0 ~ d-1)，它的主要步驟如下

1. xmss_sign 產生 XMSS signature (line 3,4) -> layer 0 的 XMSS signature
2. xmss_pkFromSig 拿 XMSS signature 做為 input 去產生 n-byte 的 root value (line 5)
3. xmss_sign 簽 root value，產生 XMSS signature (line 11,12)
4. xmss_pkFromSig 拿 XMSS signature 做為 input 去產生 下一個 root value (line 14)
5. 重複的產生 layer 1 ~ (d-1) 的 XMSS signature

這裡要注意，最底層的 d 是零，所以，root 從 line 5 到 line 14，是一個一路往上簽章的過程，從 line 9 的 ADRS.setLayerAddress(𝑗)，能看出這個 j 是從 1 一路加到 (d-1)。

接著就是 xmss_sign 如何產生 XMSS signature，xmss_sign 的演算法在第 24 頁

wots_sign 在 line 7，然後和 authentication path 合併就是 XMSS signature

至此，我們探討了 XMSS signature、wots_sign 和 authentication path 是怎麼產生 hypertree，明天我們將在這個基礎上將程式寫出來。

References

1. FIPS 205 Stateless Hash-Based Digital Signature Standard