https://techmedia-think.hatenablog.com/entry/2026/03/13/182359

Bitcoin Coreでは、現在mempoolの設計に大幅な見直しが入っている。

mempoolは、まだブロックに格納されていない未承認トランザクションを一時的に保持する仕組みで、mempool内のTxは親子関係からDAG（有向非巡回グラフ）を形成する。マイナーは基本的にこのmempool内のトランザクションから次のブロックに含めるトランザクションを選択するし、mempoolがいっぱいになった場合は、ノードはmempool内のいずれかのトランザクションを排除する。

マイナーは当然手数料の高いトランザクションをマイニングしようとするし、排除が必要な場合は手数料の低いトランザクションを対象にする。一方で、トランザクションには親子関係がありDAG構造を形成するため、収益性の高い/低いトランザクションを決定するのは難しい問題になる。

また、これまでのmempoolの設計では、

マイニング時は、そのTxをマイニングするために必要な（親子関係のある）祖先すべてを含めたパッケージ全体の手数料率を考慮した上でブロックに含めるトランザクションを選択し（ancestor fee rate）、
排除する際には、Txとそれに依存しているすべての子孫を含めたパッケージ全体の手数料率を考慮して決定する（descendat fee rate）

という非対称性のある基準を採用していた。そのため、

マイニングされにくく、排除もされにくいTxがmempoolに居座ることになるケースや、
CPFPでも、祖先グラフ全体を正確に評価できずに、マイナーの収益を最適化するパッケージが選択されないといったケースや、
RBFでは、パッケージではなくTx単体で置換を判断するため、優先度の低い置換を許可してしまうようなケース

が発生し、LNのようなマルチパーティプロトコルの脆弱性につながるような課題があった。

クラスターmempool

このような課題に対応するために、Bitcoin Coreではクラスターmempoolと呼ばれる新しいmempoolの設計が進められている。

クラスターmempoolを簡単に説明すると、

親子関係のあるTxのセットをクラスターとして
クラスター内のTxを依存関係を満たしつつ、手数料率が単調減少するようにソートし（この処理をリニアライゼーションと呼ぶ）
リニアライゼーションを手数料率の変化点で分割し、それをチャンクとし、
最後に全クラスター分フラットにチャンク単位で手数料率順にソートする

ことで、手数料率でソートされたパッケージを加味した順序付けを行う仕組み。詳しくは以前の記事参照。

リニアライゼーションアルゴリズム

クラスターmempoolで、一番コストが高いのはリニアライゼーションの処理。この処理では、クラスター内でトポロジー制約（トランザクションの親子関係）を満たす部分グラフのすべての組み合わせを評価して、手数料収入が最大化される順で並び替える必要がある。たとえば、クラスター内のトランザクション数をnとした場合、理論上の候補の数は≈2ⁿになる。既存のancestor fee rateやdescendant fee rateベースの仕組みでは祖先/子孫を25に制限しているため、同じ条件でも、n = 25、つまり ${2^{25} = 33,554,432}$ に近い数になる。

このリニアライゼーションのアルゴリズムについては、

当初（2023年初頭）：リニアライゼーションにおける最適な順序付けを求めるのはNP困難に近づくためと思われたため、大きなクラスターについては近似アルゴリズムで対処することが検討されていた。
2024年：Dongning GuoとAviv Zoharによってクラスターのリニアライゼーションが線形計画問題（LP= Linear Programming Problem）として定式化できることが発見され、NP困難ではなく多項式時間で解けることが分かり、シンプレックス法が適用できることが判明する。
2025年：
- stefanwouldgoによりクラスターリニアライゼーションの問題が「maximum-ratio closure problem」と呼ばれる問題と等価で、既にmin-cutベースの理論的に最良なアルゴリズムが存在していることが判明する。
- sipaが線形計画問題/シンプレックスの構造を、トランザクショングラフ上のマージ・スプリット操作として直接表現したアルゴリズムとしてスパニングフォレストリニアライゼーション（SFL）を提案し、採用される。

という変遷があった。

線形計画問題への変換

リニアライゼーションを線形計画問題として扱う場合、

各Txiに対して、実数の変数 ${t_i \geq 0}$ を用意する。これはクラスター内で最高手数料率のトポロジカルに有効なサブセット（＝リニアライゼーションの先頭チャンク）を求めるための変数で、そのTxがこのサブセットに含まれる場合は ${t_i > 0}$ 、含まれない場合は ${t_i = 0}$ とし（この場合）、
目的関数を手数料率（手数料合計/サイズ合計）の最大化とし
トポロジー的な依存関係を不等式制約

として表現する。

具体的には親子関係のあるペア（p, c）毎に ${t_p \geq t_c}$ という不等式制約を課す。これにより子がサブセットに含まれる（つまり ${t_c > 0}$ ）なら、その親も必ず含まれる（つまり ${t_p \geq t_c > 0}$ ）ことが保証される。

変数 ${t_i}$ が0 or 1ではなく実数なのは、目的関数が手数料率という比率なので、0ではないすべての ${t_i}$ に同じ定数を掛けたとしても比率自体は変わらない。つまり ${t_i}$ が0.5でも1でも100でも、最終的に選択されるサブセットは同じになる。

目的関数 $g = \frac{\sum_i t_i \cdot fee(i)}{\sum_i t_i \cdot size(i)}$ は、比率のままだと線形にならないので、正規化制約 ${\sum_i t_i \cdot size(i) = 1}$ を追加して分母を固定化して目的関数を ${g = \sum_i t_i \cdot fee(i)}$ という線形関数にする。つまり、サイズは制約条件に移り、 ${t_i}$ が取れる値の範囲をサイズに応じて制限している（サイズが大きいTxの ${t_i}$ を大きくすると、 ${\sum_i t_i \cdot size(i)}$ がすぐに1に達して他のTxの ${t_i}$ に使える余裕がなくなる）。これは、ナップサック問題と似た構造で、容量制約（サイズ）を満たしつつ価値（手数料）を最大化するという形に変換している。

これで標準的な線形計画問題の形式になる。

シンプレックス法

線形計画問題を解くアルゴリズムとしてよく知られているのがシンプレックス法。

シンプレックス法を適用できるようにするために、スラック変数*1 ${d = t_p - t_c \geq 0}$ を導入する。

n個のトランザクションと、m個の依存関係を持つ問題では、n + m + 1個の変数（ ${t_{1...n}, d_{1...m}, g}$ ）とm + 2個の制約がある：

${d_j = t_{p_j} - t_{c_j}}$ （j = 1...m、依存関係）
${g = \sum_i t_i \cdot fee(i)}$ （目的関数）
${\sum_i t_i \cdot size(i) = 1}$ （正規化）

シンプレックス法では、n - 1個の変数を非基底変数として0に固定し、残りを制約から計算される基底変数とする。

たとえば、各Txがそれぞれ単独のチャンクとなる初期状態の場合、すべての ${d_j}$ およびgは基底変数、 ${t_j}$ のうちn - 1個が非基底変数となる。

例えば以下のようなAからGまでのクラスターで考える（説明を簡略化するためサイズはすべて１とする）。基底変数は親がないTxから選択するため*2、ここでは ${t_A = 1}$ を基底変数として残りを ${t_B = t_C = t_D = t_E = t_F = t_G = 0}$ とする。

graph LR
    A["A\nfee=1\n手数料率=1"] --> B["B\nfee=10\n手数料率=10"]
    A --> C["C\nfee=8\n手数料率=8"]
    D["D\nfee=1\n手数料率=1"] --> C
    B --> F["F\nfee=1\n手数料率=1"]
    C --> E["E\nfee=1\n手数料率=1"]
    F --> G["G\nfee=1\n手数料率=1"]
    E --> G

この初期状態では、有効なサブセットは｛A｝のみで、目的関数はg = 1。ここから反復操作を実行する。

ある非基底変数を基底変数に入れる。どの変数を基底変数にするかは、その変数を増やした場合にgがどれだけ良くなるかを表す相対コスト（reduced cost）を計算して選択する。

正規化の式から ${t_A = 1 - t_B - t_C - t_D - t_E - t_F - t_G}$ なので、これを目的関数に代入すると結果は、

${g = 1 + 9 \cdot t_B + 7 \cdot t_C + 0 \cdot t_D + 0 \cdot t_E + 0 \cdot t_F + 0 \cdot t_G}$

となり、相対コストが最大になるのは ${t_B}$ の+9であるため、 ${t_B}$ を基底変数に昇格する。その際、 ${t_B}$ がどこまで増やせるかを決める。 ${d_{A \rightarrow B} = t_A - t_B \geq 0}$ という制約と、正規化の制約と合わせると ${t_A = t_B = 0.5}$ となる。結果、

${d_{A \rightarrow B} = 0}$ となり非基底変数となり、AとBが同じチャンクであることを意味し、
目的関数は ${g = 0.5 + 10 \cdot 0.5 = 5.5}$

となる。

このようにシンプレックス法では、相対コストが正の非基底変数を選んで基底に昇格させ、制約を満たすために最初に0に到達する基底変数を非基底に降格させる。この入れ替えを相対コストが正でなくなるまで反復する。

続きを見ていこう。状態が更新されたら再度、同じ処理を行う。 ${t_A = t_B}$ であるため、正規化の式は ${t_A = \frac{1 - t_C - t_D - t_E - t_F - t_G}{2}}$ となり、目的関数は

${g = 5.5 + 2.5 \cdot t_C - 4.5 \cdot t_D - 4.5 \cdot t_E - 4.5 \cdot t_F - 4.5 \cdot t_G}$

となり、相対コストが最大になるのは ${t_C}$ で、これを基底変数に昇格する。ただ、 ${d_{D \rightarrow C} = t_D - t_C \ge 0}$ という制約があり ${t_D = 0}$ であるため、 ${t_C}$ の値を増やすと制約違反になってしまうので値は0のまま基底変数になり、 ${d_{D \rightarrow C} }$ が非基底変数になり、CとDが同じチャンクになる。そのためCはサブセットには入らない。

三度目の反復では ${t_A = t_B, t_C = t_D}$ を利用する。この場合、目的関数は

${g = 5.5 - 2 \cdot t_C - 4.5 \cdot t_E - 4.5 t_F - 4.5 t_G}$

となり、正の相対コストを持つ非基底変数がなくなり最適解に到達する。

結果、このクラスターのLPの最適解はサブセット｛A, B｝で手数料率は5.5。その後は、A, Bを除外したC, D, E, F, Gに対して新たなLPを解いて次のチャンクを求める作業を繰り返すことで完全なリニアライゼーションを得る。

スパニングフォレスト

上記のシンプレックス法をトランザクショングラフ上で解釈すると、各操作は以下のように対応付けできる。

非基底変数 ${d_j = 0}$ は、親Txと子Txの ${t}$ の値が等しい、つまり2つのTxが同じチャンクに属することを意味する。
基底変数 ${d_j > 0}$ は、親と子が別のチャンクに属することを意味する。
${d_j}$ を基底から非基底にする（= 0にする）ことは、2つのチャンクのマージ（統合）に対応する。
${d_j}$ を非基底から基底にする（> 0にする）ことは、チャンクのスプリット（分割）に対応する。

非基底の ${d_j}$ で結ばれたTxのグループがチャンクを構成するが、その接続にサイクルが生じることはない。つまり各チャンクの内部接続は木構造（スパニングツリー）になり、クラスター全体ではスパニングフォレスト（森）を形成する。これがアルゴリズムの名前の由来。

スパニングフォレストは、シンプレックス法に対して、

${t_i}$ 変数を廃止。シンプレックス法では ${t_i > 0}$ のTxのセットが今のところの解の候補を表していたものの、チャンクの分割状態さえ分かっていれば各チャンクの手数料率を比較するだけでどれが先頭か分かるので、 ${t_i}$ の値を追跡する必要はない。
比較対象を「最高手数料率候補のチャンク vs その他」から「隣接するチャンク同士」に変更。これにより先頭のチャンクだけでなく、すべてのチャンクを同時に最適化する

という変更を行ったもの。

状態は、クラスター内の各依存関係（グラフ上の親子の辺）に対するアクティブ/非アクティブのフラグだけで管理され、アクティブな辺で繋がったTxの集まりが１つのチャンクになる。この状態に対して、以下の２つの操作を適用可能な限り繰り返す：

マージ：非アクティブな辺（p, c）で「子チャンクの手数料率＞親チャンクの手数料率」となる場合、その辺をアクティブにして２つのチャンクを統合する。
スプリット：アクティブな辺を非アクティブにした場合にできる２つのチャンクについて、「親チャンクの手数料率＞子チャンクの手数料率」になるなら分割する。

どちらも適用できなくなったら、チャンクを手数料率の高い順に出力する。

マージが適用できない状態では、高手数料率のチャンクが低手数料率のチャンクに依存しているということがないため、手数料率順に並べるとトポロジー的に有効なリニアライゼーションになる。
スプリットが適用できない状態では、各チャンク内にこれ以上分割して改善できる箇所がないため、出力は最適なリニアライゼーションになる。

つまり、マージはリニアライゼーションをトポロジー的に有効にする操作で、スプリットは改善操作。マージとスプリットの候補が複数ある場合は、

マージをスプリットより優先。
マージ候補が複数ある場合は、子チャンクと親チャンクの手数料率の差が最大のものを選択する。
スプリット候補が複数ある場合は、親チャンク側Aと子チャンク側Bに対して ${q(A, B) = fee(A) \cdot size(B) - fee(B) \cdot size(A)}$ を最大化する辺を選択する。 ${q}$ はシンプレックス法の相対コストに対応。

実用上は全辺非アクティブのゼロ状態からではなく、すでに持っているリニアライゼーションを初期状態として利用する。入力リニアライゼーションの順にTxを処理し、各Txのチャンクが依存する親チャンクより手数料率が高ければマージしていく。ここでは悪い初期リニアライゼーション D, A, C, B, E, F, G（トポロジー的に有効だが最適ではない順序）から開始した場合の処理を追っていく。

マージ

この順にTxを処理してマージ処理を繰り返す。

処理	操作	チャンク状態
D	親なしなので何もしない	[D]1 [A]1 [C]8 [B]10 [E]1 [F]1 [G]1
A	親なしなので何もしない	同上
C	親[A]1と[D]1について [C]8 > [A]1となるのでA→Cをアクティブにしてマージ	[D]1 [AC]4.5 [B]10 [E]1 [F]1 [G]1
	続けて[AC]4.5 > [D]1なのでD→Cをアクティブにしてマージ	[DAC]3.33 [B]10 [E]1 [F]1 [G]1
B	親は[DAC]内のAなので、[B]10 > [DAC]3.33なのでA→Bをアクティブにしてマージ	[DACB]5.0 [E]1 [F]1 [G]1
E	親は[DACB]内のCで[E]1 < [DACB]5.0なのでマージなし	同上
F	親は[DACB]内のBで[F]1 < [DACB]5.0なのでマージなし	同上
G	親はFとEでどちらも手数料率1で[G]1以下なのでマージなし	同上

初期化完了時点で、

graph LR
    subgraph "チャンク[DACB] 手数料率=5.0"
        D["D\nfee=1"] =="アクティブ"==> C["C\nfee=8"]
        A["A\nfee=1"] =="アクティブ"==> C
        A =="アクティブ"==> B["B\nfee=10"]
    end
    B -."非アクティブ".-> F["F\nfee=1\nチャンク[F] 手数料率=1"]
    C -."非アクティブ".-> E["E\nfee=1\nチャンク[E] 手数料率=1"]
    F -."非アクティブ".-> G["G\nfee=1\nチャンク[G] 手数料率=1"]
    E -."非アクティブ".-> G

DACBが1つの大きなチャンクにまとまったが最適ではない（AとBだけなら手数料率5.5になるのに、DとCが混ざって5.0に下がっている）。

スプリット

チャンク[DACB]内の各アクティブ辺について、非アクティブにした場合に親側の手数料率が子側を上回るか（つまり分割すると改善するか）を評価する。

辺	分割結果	親手数料率	子手数料率	q
D→C	{D}と{CAB}	1.0	6.33	${1 \times 3 - 19 \times 1 = -16}$ ✗
A→C	{AB}と{DC}	5.5	4.5	${11 \times 2 - 9 \times 2 = +4}$ ✓
A→B	{DAC}と{B}	3.33	10.0	${10 \times 1 - 10 \times 3 = -20}$ ✗

${q}$ が正になるのはA→Cのみなので、A→Cを非アクティブにして分割する。

graph LR
    subgraph "チャンク[AB] 手数料率=5.5"
        A["A\nfee=1"] =="アクティブ"==> B["B\nfee=10"]
    end
    subgraph "チャンク[DC] 手数料率=4.5"
        D["D\nfee=1"] =="アクティブ"==> C["C\nfee=8"]
    end
    A -."非アクティブ".-> C
    B -."非アクティブ".-> F["F\nfee=1\nチャンク[F] 手数料率=1"]
    C -."非アクティブ".-> E["E\nfee=1\nチャンク[E] 手数料率=1"]
    F -."非アクティブ".-> G["G\nfee=1\nチャンク[G] 手数料率=1"]
    E -."非アクティブ".-> G

スプリット後にマージの確認をする。親チャンク{AB}と子チャンク{DC}については、子の方が低いのでマージ対象にならない。E、F、G手数料率はどのチャンクより低いのでマージ対象にならず終了。

続いて次のスプリット候補を確認する

辺	分割結果	親手数料率	子手数料率	q
A→B	{A}と{B}	1.0	10.0	-9✗
D→C	{D}と{C}	1.0	8.0	-7✗

いずれも子側の方が手数料率が高く、分割しても改善しないので、これ以上適用可能な処理がなくアルゴリズム終了。

結果の出力は、

[A, B] 5.5 → [D, C] 4.5 → [E] 1 → [F] 1 → [G] 1

となる。

シンプレックス法が最高手数料率のトポロジー的に有効なサブセットという1つの最適解を見つけるアルゴリズムで、リニアライゼーションを行うためには、発見されたチャンクを除外して新たなLPを構築して繰り返すというアプローチが必要なのに対して、スパニングフォレストは1回の実行で全チャンクの最適な分割と順序を同時に見つけるアプローチになってる。

計算量

スパニングフォレストの計算量については理論的な保証はまだ確立されておらず、指数的なワーストケースが存在する可能性や終了しないケースが存在する可能性も排除されていないものの、以下のような利点がある

LPの再構築コストがない
既存のリニアライゼーションからインクリメンタルに改善できる
途中で打ち切っても有効なリニアライゼーションが得られる

mempoolの運用という意味では特に2つめが有用で、Txの追加・削除のたびにLPをゼロから解き直すのではなく、前回の結果から少しずつ改善できる。このことからBitcoin Coreではスパニングフォレストベースの実装が進められている。

*1:最適化問題において、不等式制約を等式制約に変換するために導入する変数

*2:もし親のいるBを選択すると、 ${t_B > 0, t_A = 0}$ となるけど、 ${d_{A \rightarrow B} = t_A - t_B \lt 0}$ となり制約違反になる