Merkle Tree Improvement Proposal

オープン
#1,460 コメント 8 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 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 を読み、一般的な手順ははじめてのコントリビューションガイドを参照してください。

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

RustCrypto/signatures のほかの issue

RustCrypto/signatures の issue をすべて見る

似ている issue

Rust の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。