作者：jonasnick
摘要：帶狀態的基於哈希函數也可以非常高效，如果由公鑰生成的簽名的數量較少的話。而帶狀態方案的一個主要問題是需要備份狀態、並且在每一次簽名操作之後都要正確地更新狀態。通過直接結合一種無狀態的基於哈希函數的方案（比如 SPHINCS+ 的一種變種）以及一種不平衡的 XMSS 樹（攜帶一次性簽名公鑰（當然是帶狀態的）），我們得到了一種稱為 “SHRINCS” 的方案。當我們只需要少量簽名的時候，它非常高效，而且可以用一個靜態的種子來備份。更準確地說，SHRINCS 公鑰是帶狀態的和不帶狀態的公鑰的一個哈希值。我們假設密鑰生成發生在能夠安全地保存狀態的簽名設備中。因此，這個簽名器可以使用高效的帶狀態簽名方案來生成簽名。當這個狀態已知已經損壞或丟失的時候（比如說使用一個靜態的種子詞備份復原了錢包），那就只能使用無狀態的簽名方案。因此，SHRINCS 在正常操作中利用了帶狀態簽名方案的效率，同時，保留了健壯的無狀態簽名作為後備。
SHRINCS
Mikhail Kudinov 和我的報告《比特幣適用的基於哈希函數的簽名方案》的附錄部分已經簡要介紹了 SHRINCS 方案。本文提供的是更全面的解釋，希望能得到反饋。
SHRINCS 的構造需要一種無狀態的簽名方案和一種帶狀態的簽名方案（後者要能生成較小體積的簽名）。SHRINCS 由以下算法組成：
- $\textsf{KeyGen}() \rightarrow (\mathit{seed}, \mathit{pk}, \mathit{state})$：這個密鑰生成算法會生成一個主種子、派生出私鑰 $\mathit{sk}_1$ 和 $\mathit{sk}_2$，分別用於帶狀態的和無狀態的簽名方案。使用這兩個私鑰，它分別生成公鑰 $pk1$ 和 $pk2$，用於帶狀態的和無狀態的簽名。最後，$KeyGen$ 返回元組 $(\mathit{seed}, \mathit{pk}, \mathit{state})$，其中，$\mathit{pk} = H(\mathit{pk}_1, \mathit{pk}_2)$，而 $state$ 是帶狀態簽名的初始狀態。
- $\textsf{Restore}(\mathit{seed}) \rightarrow (\mathit{seed}, \mathit{pk}, \mathit{state})$：復原算法，從一個種子中重新派生出 SHRINCS 公鑰，並將 $state$ 設為 $\textsf{LOST}$，並返回元組 $(\mathit{seed}, \mathit{pk}, \mathit{state})$。
- $\textsf{Sign}(\mathit{seed}, \mathit{state}, m) \rightarrow (\mathit{state}’, \mathit{sig})$：如果 $\mathit{state} \neq \textsf{LOST}$，那麼簽名算法就重新派生私鑰 $\mathit{sk}_1$ 和公鑰 $\mathit{pk}_2$，並用 $\mathit{sk}_1$、$\mathit{state}$ 和消息 $m$ 運行帶狀態簽名方案的 $\textsf{Sign}$ 簽名算法。然後，返回更新後的狀態 $\mathit{state}’$ 以及拼接了 $\mathit{pk}_2$ 的簽名。否則（如果狀態已經損壞），那就重新派生出私鑰 $\mathit{sk}_2$ 和公鑰 $\mathit{pk}_1$，並使用 $\mathit{sk}_2$ 和 $m$ 運行無狀態簽名方案，返回 $\mathit{state}’ = \mathit{state}$ 與拼接了 $\mathit{pk}_1$ 的簽名。
- $\textsf{Verify}(\mathit{pk}, m, \mathit{sig}) \rightarrow {\textsf{true}, \textsf{false}}$：驗證算法，將簽名 $\mathit{sig}$ 解析為 $\mathit{sig}’ | \mathit{pk}’$，根據無狀態或帶狀態方案來驗證 $\mathit{sig}’$（在基於哈希函數的簽名方案中，這就意味著復原公鑰），然後檢查兩個公鑰的哈希值等於 $\mathit{pk}$。
所以，在一個能夠保存狀態的簽名器初始化之後，它用帶狀態方案來簽名；但是，無論什麼時候，當一個設備使用種子來複原時，它就只用無狀態方案來簽名。因為在 SHRINCS 中帶狀態簽名模式高效得多，所以，一個復原後的設備來簽名，會比使用最初運行 $\textsf{KeyGen}$ 的設備來簽名昂貴得多。
關於在 SHRINCS 中的無狀態簽名方案，候選有 SLH-DSA，或者我們在報告中詳細介紹的 SPHINCS+ 的一個變種。根據參數的不同，簽名的大小在 3KB 到 8KB 之間，而公鑰是 16 字節（在 NIST 的安全性層級中屬於等級 1）。至於帶狀態簽名方案，SHRINCS 使用我們作為的 “不平衡的 XMSS” 。一個常規的 XMSS 公鑰就是一棵由眾多一次性簽名（OTS）公鑰構建起來的默克爾樹（的樹根）。一次性簽名方案只允許一個公鑰生成一個簽名，否則這個公鑰就不安全了。所以，簽名狀態就是已經制作的簽名的個數，最初是 $q=0$。要用 XMSS 簽名一條消息，簽名人要遞增 $q$，用默克爾樹上的第 $q$ 個一次性公鑰來簽名，然後計算通向樹根的認證路徑（即所謂的 “默克爾證據”）。最終的簽名實質上就是一次性簽名加上認證路徑。
SHRINCS 並非直接使用由一次性簽名（公鑰）所組成的一棵不平衡的默克爾樹，而是在帶狀態簽名方案部分使用不平衡的樹。因此，第一個一次性簽名公鑰位於深度 1，第二個一次性簽名公鑰位於深度 2，以此類推。這就儘可能降低了早期簽名的認證路徑的長度，對於預計只簽名少量次數的場景來說，是理想的。對這種 “不平衡的 XMSS” 方案來說，第 $q$ 個簽名就是第 $q$ 個一次性簽名以及它的認證路徑。在 NIST 的安全等級 1 條件下， 認證路徑的大小是 $q \cdot 16$ 字節，而一次性簽名的大小是 292 字節。更具體地說，我們使用的一次性簽名方案是 WOTS+C（詳情請看論文）。
總結以下，在使用無損的狀態簽名時，SHRINCS 的簽名體積是 $\min(292 + q \cdot 16, s_l) + 16$，其中 $q$ 是已經為這個公鑰在帶狀態模式中生成的簽名的數量，而 $s_l$ 是使用無狀態方案生成的簽名的體積。如果 $q = 1$，簽名比簽名體積最小的 NIST 標準化方案（ML-DSA）還要小 11 倍。我估計，常規的比特幣錢包的平均 $q$ 值在 1 到 2 之間。SHRINCS 的主要缺點在於，它的安全性要求安全的狀態管理。不過，不像完全的帶狀態方案（一旦狀態管理出錯就會引發災難），在 SHRINCS 中，只要你有所疑慮，就總是能切換到無狀態模式。
（完）
