クラスターmempool

GBECの解説動画の資料です。
https://goblockchain.network/2026/04/cluster-mempool/

Transcript

1. クラスターmempool
2. 1 mempool mempoolは未承認トランザクションが一時的に保持されるスペース mempool内のTxはインプット/アウトプットの関係からDAG（有向非巡回グラフ）を形成
3. 2 従来のmempool設計の課題 各Txは複数の祖先（ancestor）および子孫（descendant）を持ち、 子をマイニングするためには必ず親もマイニングする必要がある（パッケージ手数料率の評価） • ancestor fee rate Txをマイニングするために必要な祖先全員を含めた、パッケージ全体の手数料率 • descendant fee rate Txとそれに依存しているすべての子孫を含めたパッケージ全体の手数料率 • ancestor fee rateとdescendant fee rateの非対称性 ◦ マイニングではancestor fee rateでマイニング対象を選択 ◦ mempoolからの排除対象を選択する場合は descendant fee rateで選択 • マイニングされにくく、排除もされにくい Txがmempoolに居座ることになる
4. 3 従来のmempool設計の課題 RBF（Replace-by-Fee）は、Tx単体の手数料率に基づき判断するため、 実際にはマイニング優先度が下がる置換を許してしまうケースがある Lightning NetworkなどのHTLCで、 • HTLC Success Txを低手数料率でmempoolに滞留させ • 相手方のHTLC Timeout TxのRBFを防止する Tx A（3 sat/vB, 100vB, fee=300sat） Tx B（10 sat/vB, 100vB, fee=1000 sat） ancestor fee rateは、 (300 + 1000) / (100 + 100) = 6.5 sat/vB Tx A’（4 sat/vB, 100,000vB, fee=400,000sat） 手数料率、手数料額共にAより高いため（3 sat/vB → 4 sat/vB）置換可能 一方、Tx Bは無効になり排除される(6.5 sat/vB > 4 sat/vBであっても) ※ RBFはTx単体のみをチェックしパッケージを評価しない
5. 4 従来のmempool設計の課題 CPFP（Child pay for Parents）では、子が親の手数料を補填するロジックが 祖先グラフ全体を正確に評価できず、マイナーにとって最適なパッケージ選択が保証されない Tx A（1 sat/vB, 100vB, fee=100sat） Tx B（10 sat/vB, 100vB, fee=1000 sat） Tx C（10 sat/vB, 100vB, fee=1000 sat） Tx B、Tx C共にancestor fee rateは、(100 + 1000) / (100 + 100) = 5.5 sat/vB 実際のマイニング手数料率は (100 + 1000 + 1000) / (100 + 100 + 100) = 7 sat/vB Tx D（6 sat/vB） ancestor fee rateの判断ではTx D > Tx B = Tx Cとなるが 本当は7 sat/vBのA, B, Cをマイニングする方が有利 Tx A, Bマイニング後、 Tx Cのancestor fee rateは10 sat/vB → mempool内のランキングはこの瞬間に何をマイニングするかによって変動する 超低手数料率の子 低手数料率の子がつくと descendant fee rateが下がり排除対象になるリスクが上がる
6. 5 クラスターmempool 1. トランザクション間の依存関係を クラスターとして管理する ◦ クラスターA：[Tx 1 -> Tx 2 -> Tx 3] ◦ クラスターB：[Tx 4] ◦ クラスターC：[Tx 5 -> Tx 6] 2. リニアライゼーション ：クラスター内のTxを最適な順序に並べる ◦ 依存関係を満たしつつ、手数料率が単調非増加のセットになるよう並べる https://techmedia-think.hatenablog.com/entry/2026/03/13/182359 3. チャンク分割：リニアライゼーションを手数料率の変化点で区切ったグループ 4. すべてのクラスターをばらしてチャンク単位でフラットにグローバルソート • マイニングでは先頭のチャンクを順次選択 • 排除は最後尾のチャンクから選択 • マイニングされてもチャンクの順序は変わらない 非対称性を排除
7. 6 クラスターmempool • クラスター： ◦ Tx A: fee=100 sat, size=100vB → 1.0 sat/vB ◦ Tx B: fee=800 sat, size=100vB → 8.0 sat/vB ◦ Tx C: fee=600 sat, size=100vB → 6.0 sat/vB ◦ Tx D: fee=200 sat, size=100vB → 2.0 sat/vB ◦ Tx E: fee=150 sat, size=100vB → 1.5 sat/vB • チャンク： ◦ チャンク１：｛Tx A -> Tx B -> Tx C｝（5.00 sat/vB 300vB） ◦ チャンク２：｛Tx D｝（2.00 sat/vB 100vB） ◦ チャンク３：｛Tx E｝（1.5 sat/vB） Tx A Tx B Tx C Tx D Tx E 依存関係： 単調非増加の確認 : 5.00 ≥ 2.00 ≥ 1.50 ✓ トポロジカル制約 : A→B, A→C, B→D, C→E すべて満たす ✓
8. 7 クラスターmempool 新しいTxが届いたら： • 依存関係がないTxの場合→新しいクラスターを作成→キューに追加 • １つのクラスターの子孫の場合 →該当クラスターに追加し、 ◦ リニアライゼーションを再計算 ◦ 該当クラスターのチャンクについてキューを更新 • 複数のクラスターにまたがる場合： ◦ 対象のクラスターを統合 ◦ マージ後のクラスターのリニアライゼーションを再計算 ◦ 旧チャンクを削除し、新チャンクをキューに追加 ※ 従来のmempoolではTxが届くたびにすべての祖先・子孫の 　 ancestor/descendant feerateを再計算していたが、 　 クラスターmempoolでは影響を受けるクラスターのみの再計算 このケースで対象のクラスター数が増えると 再計算の計算量が爆発する可能性があるため、 クラスターには上限が設けられている
9. 8 従来の手法との対比 従来のmempool クラスターmempool 手数料の評価単位 Tx個別/祖先チェーン クラスター→チャンク マイニング順序 ancestor fee rate リニアライゼーション 排除 descendant fee rate リニアライゼーションの 末尾チャンクから削除 マイニングと排除の一貫性 非対称 同じリニアライゼーションから導出 RBFの判定 部分的な手数料率比較 置換前後のチャンクの手数料率を比較 祖先/子孫の上限 25/25 クラスターサイズの上限 CPFP 祖先のセット単位で比較（近似） クラスター全体で正確に評価