Merkle Tree Improvement Proposal
メンテナーはふだん 1 日以内に返信
まだ誰も着手していません。
評価
- 難易度
- 5/5
- 見積もり時間
- 1週間以上
- 初心者へのやさしさ
- 25/100
- issue の種類
- 機能追加
- 明瞭さ
- おおむね明確
- 活発さ
- 活発
- 技術スタック
- rust
- 領域
- cryptography
調査の方向性
Read the linked context in issue #1438 and the proposal’s references, RFC 8554 and RFC 8391, then inspect the LMS and XMSS implementations to locate Merkle tree storage and opening generation. Compare the proposed interleaved storage trade-off with current behavior and verify what changes would be needed; done means maintainers agree on a design before implementation. The issue gives measurements but does not name source files or tests.
索引モデルが issue の本文から書いたものです。
説明
Hi, this is my first ever open source issue. Happy to turn this into a PR if the approach makes sense.
The idea is my own, the prototype and measurements were developed with AI assistance (Claude), and all numbers were run and verified locally.
Current LMS and XMSS
As is already reported currently in the LMS scheme there is an overflow or too much storage needed problem as per issue #1438 by L-Soko. Further, the XMSS schemes completely rebuild the merkle trees for every opening request.
Proposal
With a baseline of 2^15 leaves or a height 15 tree and the case that we do not keep anything as is the current XMSS. If we interleave the storage of levels for the merkle trees this would solve storage problems and improve opening times. Let $L_i = \{c_1, c_2,\dots, c_n\}$ as level $i$ and $c_j$ as node $j$ in level $i$ in the merkle tree. Then denote $k$ as the interleave parameter and $b$ as the bottom parameter in which we only start saving starting from the level $b$. If we have $k = 2$, then we interleave every 2 levels and so we only keep the nodes on $L_i$ where $i \ge b$ and $k \mid (i-b)$. If we keep the leaves in storage we would then have $b=0$ and if we exclude the leaves and start interleaving from the level right above the leaf level then $b=1$. We can always exclude the leaves by default and by excluding the leaves and $k=2, b=1$ this save us around 66.7% of the storage needed with a ~33,000x opening speed up compared to rebuilding the whole tree. and if we use $k=2,b=2$ we would have further savings with saving more than 83% of the storage needed compared to keeping the whole tree.
Although against the current LMS which stores the whole tree it will get slower, this would save a lot of memory usage. Only the missing gaps would then have to be computed which keeps the computation on a small subsection of the tree.
Later found that it's similar to one of the intermediate time/storage trade-offs RFC 8554 describes and Cisco's hash-sigs uses a similar layout for its auxiliary data. [RFC 8554, RFC 8391]
Measurements
My environment for measurements: Measured on an Intel Core i7-10750H (6C/12T, no SHA-NI), Ubuntu 24.04 under WSL2, rustc 1.98.1, --release, single-threaded.
LMS
| Stored (H = 15) | Size | stored vs. full | Leaves to be computed / opening | Avg Time |
|---|---|---|---|---|
| Full tree | 2,097,120 B | 100% | 0 | 0.4–3.7 µs |
| b=1, k=2 | 699,040 B | 33.3% | 1 | 0.16–0.21 ms |
| b=2, k=2 | 349,536 B | 16.7% | 3 | 0.50–0.70 ms |
| b=3, k=3 | 149,792 B | 7.14% | 7 | 1.15–1.23 ms |
| b=4, k=4 | 69,920 B | 3.33% | 15 | 2.47–2.65 ms |
| Nothing (full rebuild per signature) | 0 | 0% | 32,767 | 5.76–5.82 s |
All rows are measured except the H20 and H25 full rebuilds. Each authentication path was assembled into a complete LMS signature and accepted by lms-signature's own verifier (200 signing indices per row). Times are medians of 3 runs (H15), 2 runs (H20) and 1 run (H25), single-threaded.
Note: the H20 and H25 full-rebuild times are estimates: the measured single-thread cost per leaf (≈ 153 µs) × the number of leaves. A full rebuild does the same work as key generation, which was run on all 12 threads (H25: 19.5 min); 12 threads ran ≈ 4.4× faster than one on this CPU, which gives ≈ 86 min single-threaded. The H15 rebuild was measured (4.96 s, vs 5.0 s estimated).
| Height | b, k | Stored | storage vs. full | Leaves to be computed / opening | Avg Time |
|---|---|---|---|---|---|
| 15 | full tree | 2.0 MiB | 100% | 0 | 0.5 µs |
| 15 | 1, 2 | 683 KiB | 33.3% | 1 | 0.16 ms |
| 15 | 4, 4 | 68.3 KiB | 3.33% | 15 | 2.3 ms |
| 15 | 5, 5 | 33.0 KiB | 1.61% | 31 | 4.9 ms |
| 15 | nothing (full rebuild) | 0 | 0% | 32,767 | 4.96 s |
| 20 | full tree | 64 MiB | 100% | 0 | 0.8 µs |
| 20 | 1, 2 | 21.3 MiB | 33.3% | 1 | 0.17 ms |
| 20 | 5, 5 | 1.03 MiB | 1.61% | 31 | 5.1 ms |
| 20 | 6, 6 | 520 KiB | 0.79% | 63 | 10.1 ms |
| 20 | nothing (full rebuild) | 0 | 0% | 1,048,575 | ≈ 2.7 min (est.) or ≈ 35 sec (measured on 12 threads) |
| 25 | full tree | 2.0 GiB | 100% | 0 | 1.2 µs |
| 25 | 1, 2 | 683 MiB | 33.3% | 1 | 0.17 ms |
| 25 | 7, 7 | 8.06 MiB | 0.39% | 127 | 21.3 ms |
| 25 | 8, 8 | 4.02 MiB | 0.20% | 255 | 40.6 ms |
| 25 | nothing (full rebuild) | 0 | 0% | 33,554,431 | ≈ 86 min (est.) or ≈ 20 min (measured on 12 threads) |
XMSS
| XMSS-SHA2_h_256 | b, k | Stored | stored vs. full | Leaves to be computed / opening | Total time | Speed-up |
|---|---|---|---|---|---|---|
| 10 | nothing (full rebuild, current) | 0 | 0% | 1,024 | 2.27 s | 1× |
| 10 | 1, 2 | 21 KiB | 33.4% | 1 | 3.3 ms | ~690× |
| 10 | 2, 3 | 9 KiB | 14.3% | 3 | 7.7 ms | ~300× |
| 16 | nothing (full rebuild, current) | 0 | 0% | 65,536 | 145 s | 1× |
| 16 | 1, 2 | 1.3 MiB | 33.3% | 1 | 3.3 ms | ~44,000× |
| 16 | 2, 3 | 585 KiB | 14.3% | 3 | 7.6 ms | ~19,000× |
- 主要言語
- Rust
- スター
- 672
- フォーク
- 213
- 平均マージ
- 23時間 39分
- マージ済み PR(30日)
- 19
環境構築
このプロジェクトには開発コンテナ、Dockerfile、コントリビューションガイドがありません。まず README を読み、一般的な手順ははじめてのコントリビューションガイドを参照してください。
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
RustCrypto/signatures のほかの issue
-
難易度 2/5 1〜3時間 初心者へのやさしさ 82/100
RustCrypto/signatures#1491 · コメント 2 件 ·
メンテナーはふだん 1 日以内に返信
-
難易度 4/5 3〜5日 初心者へのやさしさ 48/100
RustCrypto/signatures#1498 · コメント 1 件 ·
メンテナーはふだん 1 日以内に返信
-
難易度 5/5 1週間以上 初心者へのやさしさ 35/100
RustCrypto/signatures#1479 · コメント 1 件 ·
メンテナーはふだん 1 日以内に返信
-
ecdsa, rfc6979: k, k⁻¹ and the RFC 6979 generator state are not zeroized (FIPS 186-5 § 6.4.1)対応中かも このイシューにリンクされたプルリクエストがオープン中、またはマージ済みです。 オープン
難易度 4/5 3〜5日 初心者へのやさしさ 48/100
RustCrypto/signatures#1472 · コメント 2 件 ·
メンテナーはふだん 1 日以内に返信
-
xmss: XMSS^MT height-40 keys never return `KeyExhausted`; signing after exhaustion returns `Ok` with an invalid signature対応中かも @choksi2212 が 35 日前に担当しました。 オープン
難易度 4/5 3〜5日 初心者へのやさしさ 65/100
RustCrypto/signatures#1453 · コメント 1 件 · リアクション 1 件 ·
メンテナーはふだん 1 日以内に返信
RustCrypto/signatures の issue をすべて見る
似ている issue
-
benchmark-review
難易度 2/5 1〜3時間 初心者へのやさしさ 63/100
メンテナーはふだん 1 日以内に返信
-
area:filesystem bug need-triage
難易度 2/5 1〜3時間 初心者へのやさしさ 85/100
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 78/100
メンテナーはふだん 1 日以内に返信
-
Captions panel does not offer to show an existing transcript対応中かも @thedavidweng が今日担当しました。 オープン
難易度 2/5 1〜3時間 初心者へのやさしさ 72/100
CapSoftware/Cap#4276 · コメント 1 件 ·
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 76/100
libracoder/kiri#364 ·
メンテナーはふだん 1 日以内に返信