本日重點：ht_sign, wots_sign, xmss_sign

Hypertree signature 是由一連串的 XMSS signature 所組成，每一個 XMSS signature 都包括了一個 WOTS+ signature. 產生 WOTS+ signature 的 function 就是 wots_sign，演算法如下

wots_sign 的 line 15 就是 chain，這是 chain 的演算法

chain 會進行若干次的更新 hash address，然後每次更新 hash address 就會計算 F

The chain function updates the hash address in ADRS with each iteration to specify the current position in the chain prior to ADRS’s use in F

在 F 的定義裡，input M 是一個長度為 n 的 bytes 陣列，所以，可以把 tmp 直接設為 out[SPX_N]

chain 的第一個參數 X，雖然演算法只說它是一個 string，不過在整份 FIPS 205 裡，每一次 call chain，X 都是一個長度為 n 的陣列，所以 X 的宣告就直接用 const uint8_t X[SPX_N]

這個 SPX_N 是 parameter sets 的 n，在 SLH-DSA-SHA2-128s 裡，n 就是 16

照 chain 演算法逐行寫，像這樣

void chain(uint8_t out[SPX_N],
           const uint8_t X[SPX_N], 
           const uint8_t i,
           const uint8_t s,
           const unsigned char pk_seed[SPX_N], 
           ADRS adrs)
{
    // 1: tmp <- X
    memcpy(out, X, SPX_N);

    int last_idx = i + s - 1;
    for(unsigned int j = i; j < last_idx; ++j)
    {
        set_hash_addr(adrs, j);
        // 𝑡𝑚𝑝 ← F(PK.seed, ADRS,𝑡𝑚𝑝)
        F(pk_seed, adrs, out, out)
    }
}

FIPS 205 第 23 頁 [1] 有這一段

The xmss_sign function (Algorithm 10) creates an XMSS signature on an 𝑛-byte message 𝑀

xmss_sign 的 M 就是傳給 wots_sign 的 M，所以 wots_sign 的 M 可以直接定義為 uint8_t M[SPX_N]

wots_sign 的 implementation 大概是這樣

void wots_sign(N_BYTES out[SPX_LEN],
               const uint8_t M[SPX_N], 
               const unsigned char sk_seed[SPX_N], 
               const unsigned char pk_seed[SPX_N], 
               ADRS adrs)
{

    ...

    ADRS skADRS;

    // 8: skADRS ← ADRS ▷ copy address to create key generation key address
    memcpy(skADRS, adrs, 32);

    // 9: skADRS.setTypeAndClear(WOTS_PRF)
    set_type_and_clear(skADRS, WOTS_PRF);

    // 10: skADRS.setKeyPairAddress(ADRS.getKeyPairAddress())
    set_key_pair_addr(skADRS, get_key_pair_addr(adrs));

    uint8_t sk[SPX_N];
    for(int i = 0; i < SPX_LEN; ++i)
    {
        // skADRS.setChainAddress(𝑖)
        set_chain_addr(skADRS, i);

        // 𝑠𝑘 ← PRF(PK.seed, SK.seed, skADRS) ▷ compute chain 𝑖 secret value
        prf(pk_seed, sk_seed, skADRS, sk);

        // ADRS.setChainAddress(𝑖)
        set_chain_addr(adrs, i);

        // 𝑠𝑖𝑔[𝑖] ← chain(𝑠𝑘, 0, 𝑚𝑠𝑔[𝑖], PK.seed, ADRS) ▷ compute chain 𝑖 signature value
        // chain(uint8_t out[SPX_N], ...
        chain(out[i], sk_seed, 0, msg[i], pk_seed, adrs);
    }
}

xmss_sign 會呼叫 wots_sign，其所產生的 WOTS+ signature，會成為 XMSS signature 的一部份。接下來的內容，我將盡量不再提到 WOTS+ signature，也盡量不再提到 wots_sign，因為接下來要說的是 ht_sign 如何用 XMSS signature 和 XMSS public key 產生 hypertree signature。

盡量不提 WOTS+ signature 是為了將焦點放在 XMSS signature 和 XMSS public key。

截錄自 Algorithm 19 slh_sign_internal，FIPS 第 35 頁

SIG𝐻𝑇 ← ht_sign(PK_fors, SK.seed, PK.seed,𝑖𝑑𝑥𝑡𝑟𝑒𝑒,𝑖𝑑𝑥𝑙𝑒𝑎𝑓)

截錄自 Algorithm 12 ht_sign，FIPS 第 27 頁

SIG𝑡𝑚𝑝 ← xmss_sign(𝑀, SK.seed,𝑖𝑑𝑥𝑙𝑒𝑎𝑓, PK.seed, ADRS)
SIG𝐻𝑇 ← SIG𝑡𝑚p
𝑟𝑜𝑜𝑡 ← xmss_pkFromSig(𝑖𝑑𝑥𝑙𝑒𝑎𝑓, SIG𝑡𝑚𝑝, 𝑀, PK.seed, ADRS)
for 𝑗 from 1 to 𝑑 − 1 do
    SIG𝑡𝑚𝑝 ← xmss_sign(𝑟𝑜𝑜𝑡, SK.seed,𝑖𝑑𝑥𝑙𝑒𝑎𝑓, PK.seed, ADRS)
    SIG𝐻𝑇 ← SIG𝐻𝑇 ∥ SIG𝑡𝑚p
    if 𝑗 < 𝑑 − 1 then
        𝑟𝑜𝑜𝑡 ← xmss_pkFromSig(𝑖𝑑𝑥𝑙𝑒𝑎𝑓, SIG𝑡𝑚𝑝, 𝑟𝑜𝑜𝑡, PK.seed, ADRS)
    end if
end for

對照著看 Figure 1 (FIPS 205 第8頁)，從 slh_sign_internal 和 ht_sign 能看出，ht_sign 一開始會拿 FORS public key 做為 xmss_sign 的 input，由 xmss_sign 算出 XMSS signature，於是，ht_sign 就取得了第一個 XMSS signature (記住這一個 XMSS signature，它是 HT signature 的第一個 element)。然後，拿此 XMSS signature 給 xmss_pkFromSig 算出 XMSS public key, 這個 XMSS public key 在這裡就是 root，他會用來算 下一個 XMSS signature。

這裡的重點是，XMSS public key 是用來算出 下一個，不是用來回推原本的 XMSS signature。

記住這個 XMSS public key，他在子樹裡是 root，從這一層開始，就會開始走以下的流程

step 1. 拿 root 去給 xmss_sign 計算 XMSS signature (這個 root 雖然代表這一個子樹的 root, 但這個 root 如果用他的上一層來看, 他就是 leaf)
step 2. 拿 XMSS signature 給 xmss_pk_from_sig 計算 xmss public key
step 3. 這個 XMSS public key 視為 root，在 往上一層 的時候，回到 step 1，拿他來計算 XMSS signature，算出來的是上一層的 XMSS signature

References

1. FIPS 205 Stateless Hash-Based Digital Signature Standard