2026-03-13

クラスターmempoolのリニアライゼーションアルゴリズム

Bitcoin

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のの値が等しい、つまり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)}$ を最大化する辺を選択する。はシンプレックス法の相対コストに対応。

実用上は全辺非アクティブのゼロ状態からではなく、すでに持っているリニアライゼーションを初期状態として利用する。入力リニアライゼーションの順に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}$ となり制約違反になる

2026-03-08

2つのデータにコミットするOP_PAIRCOMMIT opcodeの提案（BIP-442）

BIP Bitcoin Lightning network

先日BIP-442としてマージされたOP_PAIRCOMMITという新しいopcodeの提案について↓

https://github.com/bitcoin/bips/blob/master/bip-0442.md

Bitcoinでは、ハッシュロックやタイムロックなど単一の項目にコミットする手法はあるものの、複数の項目にまとめてコミットするような機能はない。そこでOP_PAIRCOMMITは、スタック上の2要素を安全にコミットする専用のオペコードとして提案された。

OP_PAIRCOMMITの仕様

OP_PAIRCOMMIT opcodeは、TapscriptのOP_SUCCESS205（0xcd）opcodeを置き換える形で導入される。

この新しいopcodeのスタック操作は以下のとおり：

スタック内の要素が2つ未満の場合、スクリプトの実行は失敗する。
スタック内の要素を ${\lbrack ..., x_1, x_2 \rbrack}$ とした場合（右が最上位）
タグ付きハッシュ関数で ${pc = hash_{PairCommit}(compactsize(len(x_1)) || x_1 || compactsize(len(x_2)) || x_2)}$ を計算し、
スタックから ${x_2, x_1}$ をポップし、
pcをスタックにプッシュする

簡単に言うと、スタックの上位２つの要素を連結して（その際各要素の先頭に長さのプレフィックスを付与）、そのハッシュを計算し、計算結果のハッシュ値をスタックにプッシュするというもの。

OP_CATとの違い

ぱっとみOP_CATと同様の挙動をするけど、違いはデータの長さをプレフィックスとして付与している点。

OP_CATの場合、連結するデータの境目が識別できない。たとえば、

<0x01> <0x0203>
<0x0102> <0x03>

という２つの各データは異なるものの、OP_CATを実行すると同じ<0x010203>というデータになる。スクリプトが意図した分割と異なる分割で同じハッシュを作ることができる。バイトシフト攻撃と呼ばれるこの攻撃をOP_PAIRCOMMITの場合は、上記のようにデータ長をプレフィックスとすることで構造的に防止する。

また、OP_CATの場合、スタック上でトランザクションデータを再構成できるため、スクリプトが自分自身のscriptPubKeyを検証・複製することが可能になり、再帰的コベナントが構築できてしまう。OP_PAIRCOMMITは結果が必ず32バイトのハッシュになるため、元データへの復元が不可能で、この問題を構造的に回避している。逆に言うと、OP_PAIRCOMMITではスタック上でトランザクションデータを構築するようなことはできない。

マークルツリーコミットメント

OP_PAIRCOMMITを使うと、スクリプト内で事前に決めた構造のデータセットに対するコミットメントを作ることができる。

たとえば、a、b、c、dという4つの要素があるツリーに対するコミットメントは、Root = PC(a, PC(b, PC(c, d)))

と計算でき、このようなツリーのメンバーシップ証明などをスクリプトで行うことができる。（ただ、仕様的にはTaptreeとは互換性はない）

LNHANCEでの利用

OP_PAIRCOMMITはもともと単体で提案された訳ではなく、ライトニングネットワーク向けのソフトフォーク提案をまとめた LNHANCE提案（LN + HANCE（enhance））の一部。LNHANCEは、以下の4つのopcodeで構成される。

opcode	BIP	役割
CHECKTEMPLATEVERIFY	BIP-119	トランザクション構造へのコミットメント
CHECKSIGFROMSTACK	BIP-348（ブログ）	スタック上の任意のデータへの署名検証
INTERNALKEY	BIP-349（ブログ）	Taprootの内部鍵をスタックに積む
PAIRCOMMIT	BIP-442（本記事）	2つの要素のペアコミットメント

この主な目的は、LN Symmetry（旧称eltoo）を導入すること。LN Symmetryでは、古い状態のTxがブロードキャストされても、その状態を後続の状態のTxで上書きすることができる。もともとこれは、トランザクションインプットの再バインドを可能にするanyprevout（APO）を利用して、事前署名済みのTxのインプットの参照先を入れ替える（再バインド可能なため）ことで実現する。

その部分をLNHANCEでは

<ctv_hash> OP_CHECKTEMPLATEVERIFY <公開鍵> OP_CHECKSIGFROMSTACK

で実現しようというアプローチ。OP_PAIRCOMMITは内部で、

ある状態nのトランザクションがどういうトランザクション（state-n-hash）で、
nが最終状態になった場合の決済情報（誰にいくら払うか）（recovery-data）

という2つのデータを束ねることで、「state-n-hashに合意するならrecovery-dataも必ずウィットネスに含めなければならない」という強制が生まれる。片方だけ提出するとPCの計算結果が変わりCSFSの検証が失敗するため。これによりコンテスト時にsettlement-txを再構築するために必要なデータ可用性が保証される。

現時点ではAPOもLNHANCEどちらもドラフトなので、どちらが採用されるかまた全く別の提案になるかはまだ不明。

2026-02-25

AADPベースのWitness Encryption

Cryptography Bitcoin

先日Delving Bitcoinに投稿されたBitcoin PIPEs v2↓

delvingbitcoin.org

これは、Witness Encryptionを使ってBitcoinの署名鍵へのアクセスに条件を付けることで、オンチェーンでは単一のSchnorr署名の検証をするだけだけど、その署名を生成するために必要な秘密鍵を入手するためにはある条件を満たす必要があるというルールを強制する仕組み。条件を満たすwitnessを提供できれば、暗号文を復号して秘密鍵を入手できる。

コベナンツを可能にするとあるけれど、実際は秘密鍵の入手方法なので、PIPEs自体が使用するトランザクションの構造を制約するものではないため、厳密にはコベナンツではなく、オペレーターによるマルチシグによるトランザクションの制約などと組み合わせる必要がある。

でも条件が満たされた場合のみ秘密鍵が入手できるというプリミティブは有用。PIPEs v2で提案されているWitness Encryption方式がベースにしているのがAADP（Adaptive Arithmetic Determinant Programs）。

ADP

AADPを理解するためには、まず元となる2020年に発表されたADP（Affine Determinant Program）を理解する必要がある。

有限体 ${F_q}$ の要素で構成されるk×kの正方行列のタプル ${(A, B_1, ..., B_n)}$ を用意する。ここで

Aはベース行列（定数行列）
${B_1, ..., B_n}$ は、各入力ビット ${x_i}$ に対応する行列で、入力bit ${x_i = 1}$ の場合 ${B_i}$ が加算され、0の場合は加算されない

そしてある入力xに対して ${M(x) = A + x_1 \cdot B_1 + x_2 \cdot B_2 + ... + x_n \cdot B_n}$ を計算し、その行列式det(M)を計算する。たとえばq = 7, k = 2で

とした場合、入力が ${(x_1, x_2) = (1, 0)}$ の場合は

入力が ${(x_1, x_2) = (1, 1)}$ の場合は

のように計算される（実際のqは巨大な素数で、kは入力のbit長で決まる）。

アフィン行列式プログラム（Affine Determinant Program）という名称は、Mが入力xに対するアフィン関数となることから来てる。

暗号化

Witness Encryptionの文脈では、

NPステートメントの検証回路をブランチプログラム（入力bitに応じてパスを選択する有向グラフ）に変換し、
1のプログラムからADPの行列タプルを構成（グラフの各辺を行列の要素に対応させる）する。 ${M_0(x) = A + x_1B_1 + ... + x_nB_n}$ を構成し、有効なwitnessが提供された場合のみ ${det(M_0(w) = 0)}$ となる。
メッセージ（秘密鍵）をこの行列のカーネルに埋め込む（ ${M(x) = M_0(x) + msg \cdot E}$ 後述）、
元の構造を隠すためにランダム化する（後述）
暗号文としてランダム化後の行列タプルとEを公開

という形で暗号化する。

メッセージの埋め込み

ここで、カーネルとは行列Mに対してMv = 0を満たす非ゼロのベクトルのセット。たとえば先程の

の場合、Mv = 0を解くと、

から

${4v_1 + 3v_2 \equiv 0 \mod 7}$
${6v_1 + v_2 \equiv 0 \mod 7}$

となり、 ${v_2 \equiv -6v_1 \equiv v_1 \mod 7}$ であるため、 ${4v_1 + 3v_1 = 7v_1 \equiv 0 \mod 7}$ となり、 ${v_1 = 1}$ とした場合のカーネルベクトルは {v = (1, 1)} 。

このカーネルにメッセージmsgを埋め込む。まずmsgなしの行列 ${M_0(x)}$ があり

${det(M_0(x)) = 0}$
${カーネルベクトル v_0 = (v_1, v_2, ..., v_k)}$

になるとして、行列の特定の位置にmsgを加えた ${M(x) = M_0(x) + msg \cdot E}$ を作る。Eは特定の位置に1を持ち他は0の行列で、これによりカーネルベクトルのどの位置にmsgが現れるかが決まる（またEは公開情報）。こうしてカーネルベクトルがmsgに依存するようになる↓

の解→v= (..., .., msg, ..., ...)
                                 ↑
                      特定の位置にmsgが現れる

復号

有効なwitnessを持っていれば、

M(w)を計算し、
det(M(w)) = 0となり、カーネルが非自明
ガウスの消去法等でM(w) · v = 0を解いてカーネルベクトルvを求め
Eを元に、vの該当箇所をmsgとして読み取る

ランダム化

上記の行列タプルをそのまま公開すると、行列の構造を解析してmsgを推測される恐れがあるため、ランダムな行列X、Yを使って公開する行列を ${M(x) \to X \cdot M(x) \cdot Y}$ に変換する。この変換後もdet = 0かどうかの判定結果は変わらない。

ただカーネルベクトルの値は代わる。元の行列のカーネルが ${M(w) \cdot v = 0}$ を満たすvだとすると、ランダム化後の行列 ${X \cdot M(w) \cdot Y}$ のカーネルは ${v' = Y^{-1} \cdot v}$ になる。X、Yを知らない攻撃者は、ランダム化された行列からは元のカーネル構造を復元できず、msgにたどり着けない。一方、有効なwitnessを持つ復号者は、ランダム化後のカーネルベクトルv'からでもmsgを復元できるように、埋め込みの構造が設計されているみたい。

AADP

↑のADPでは入力は0 or 1のビット値に限定されており、これがSNARK検証のような算術回路を扱う際にボトルネックになる。

たとえば、256 bitの素数体 ${F_p}$ 上の回路で変数が100個あるとしたら、ADPでは各変数を256 bitに分解する必要がある。つまり100×256=25,600個の入力bitを必要とする。さらに各変数について、256 bitが本当にある有限体の元のbit分解か検証する制約も追加で必要になり、暗号文のサイズが非現実的なサイズになる。

AADPは入力値としてbit値ではなく有限体の要素として直接扱えるようにすることで効率化を図っている。検証ロジックを（SNARKのR1CSの制約みたいに）算術制約として表現して、各制約をブロック行列に変換する。この各ブロック行列は対応する制約が満たされるとランクが下がり、全制約が同時に満たされると全体の行列式が0になるという構造を持つようにした模様。主に行列の作り方が変わる。

分散セットアップ

↑の構成だと、行列にmsgとして秘密鍵を埋め込むということは、誰かが秘密鍵を知っている必要があるのでは？という疑問が生じる。1人でセットアップを行う場合、その人物が秘密鍵を保持していれば、witnessなしでいつでも資金を盗める。

この問題を解決するため、PIPEs v2では複数の参加者によるマルチパーティ計算（MPC）を使って分散セットアップを行うようになっている。各参加者 ${P_i}$ が秘密鍵の「断片」 ${s_i}$ を生成し（全断片の合算値が秘密鍵になる）、断片を直接組み合わせることなく、MPCプロトコルによって秘密鍵に対応する公開鍵と、秘密鍵を埋め込んだAADP暗号文を計算し、セットアップ完了後、各参加者は自分の断片を破棄するみたい。

この方式の安全性の仮定は「少なくとも1人のセットアップ参加者が正直であれば、誰も秘密鍵を知ることはない」というもの。全参加者が結託した場合のみ秘密鍵が復元可能になる。この信頼モデルはBitVMのn-of-nの信頼の仮定と同じ構造で、完全にトラストレスではない。

実用性

PIPEs v2の論文では、Garudaライクな SNARK検証器をAADPで表現した場合のスペックを以下のように見積もっている。

暗号文のサイズ: 約338 TB。ただし改善の余地はあり。
計算コスト：主な計算コストは行列式の計算。256コアCPUを搭載したマシン約50台で並列化すれば、Bitcoinの1ブロック間隔（約10分）以内に計算可能としている。
実行コスト：クラウドインフラのレンタルで1回のcovenant実行あたり約$100〜200

元のADPベースだと全く不可能だったのが、AADPで高コストだけどなんとか計算可能なレベルなったというのが現状みたい。とは言ってもカジュアルに利用できるようなレベルにはまだない。

2026-02-14

BitVMのストレージ要件を劇的に改善する提案Argo

Cryptography BitVM Bitcoin

先日書いたBitVM 3sは↓

techmedia-think.hatenablog.com

SNARK証明の検証をFraud proofベースで行う仕組み。

SNARKの検証というのは、具体的にはGroth16とかであれば楕円曲線を用いたペアリングの演算を行うことになる。EthereumではBN254やBLS12-381で動作するペアリング演算のプリコンパイルドコントラクトを導入しているけど、当然Bitcoinにはそのような計算をするopcodeは存在しないので、BitVMではこのペアリングの演算をGarbled Circuitで表現している。Groth16と同様の検証を行う場合、この回路は約100億個のゲート（77億のフリーゲート + 27億の非フリーゲート）で構成される。

検証者はこの回路のデータをFraud proofのチャレンジに備えて保持しておく必要がある。回路の構成情報（数十GBくらい？）に加えて、非フリーゲート*1あたり

ガーブルド・テーブル：4行×16 byte = 64 byte
ハッシュコミットメント：2×20 byte = 40 byte

のデータを保持する必要があるため、合計104バイト × 27億ゲート ≈ 280GBのストレージが必要になる。

Argo

そんな中、最近この回路のサイズを劇的に小さくするアイディア（厳密には回路ではなくなる）が発表された↓

eprint.iacr.org

従来のGarbled Circuitでは、回路内の各ワイヤのbit値 ${b \in \lbrace 0, 1 \rbrace}$ にそれぞれランダムなラベル ${\ell_b}$ （128ビットの乱数）を割り当て、各ゲートについて「入力ラベルの組み合わせに対して、どの出力ラベルが得られるか」を暗号化した対応表＝ガーブルド・テーブルを作成する。

この方式だと、256 bitの有限体上の乗算も1 bit単位のゲートに分解する必要があり、SNARK検証器のようなものを作ろうとするとゲート数が爆発的に増える。これは回路全体がずっとbitの世界で処理されるのが根本的な問題。

Argo MACは、演算を回路に変換することなく、

入力値（曲線上の点のbit分解）を準同型MACに変換し、
準同型MAC上で楕円曲線の演算を直接実行する

2により楕円曲線上の演算をネイティブに実行できるので、フリーゲートのようにガーブルド・テーブルのデータを必要とせずに演算ができる。

ITPG

Argo MACでは、1の変換にITPG（Information Theoretic Partial Garbling）という手法を用いる。ITPGは、「秘密の係数を持つ多項式を、秘密を漏らすことなく相手に評価させる」仕組みで、以下のように動作する。

楕円曲線上の点P = (x, y)の準同型MACは ${\phi(P) + K}$ という形で表される。ここでφは楕円曲線の自己準同型写像で、Kはランダムな点。このMAC値の計算をする関数は、各座標が入力座標に対する2次の多項式になり、多項式の係数にはMACの鍵（φ、K）の情報が含まれる。これらの情報は検証者に知られてはいけない。φを恒等写像とした場合、この計算は、単純な楕円曲線上の点の加算P + Kなので、 ${P = (x_P, y_P), K = (x_K, y_K)}$ とした場合、加算結果のヤコビアン座標は以下のように計算される。

${x(P + K) = x_P^{2} x_K + x_Px_K^{2} - 2y_Py_K + 2B}$
${y(P + K) = 3x_P^{2}y_Kx_K - 3 y_P x_P x_K^{2} + y_P^{2} y_K - y_P y_K^{2} - 3y_P B + 3y_K B}$
${z(P + K) = x_P - x_K}$

この式においては、Pの座標 ${ (x_P, y_P)}$ は公開される変数、Kの座標は ${ (x_K, y_K)}$ は秘密の係数として機能する（Bは曲線のパラメーター）。各式は ${ (x_P, y_P)}$ に関して2次の多項式であり、かつ秘密の係数に関しては線形となる。

ITPGでは、この多項式の係数を ${c_j}$ として、各係数をランダムなノイズで隠した状態で検証者に渡す。入力座標xをρ bitに分解すると、 ${\mathbb \sum_{j=0}^{ρ-1} x_j \cdot 2^{j}}$ となるので、各 ${x_j}$ に対して、

${e_{j, b} = c_j \cdot b + r_j}$

を計算する。ここで、 ${c_j}$ は多項式の秘密係数からくる値で、 ${r_j}$ はランダムなノイズ。bit値によりこれは、

b = 0の場合、 ${e_{j, 0} = r_j}$ （ランダム値のみ）
b = 1の場合、 ${e_{j, 1} = c_j + r_j}$ （秘密係数＋ランダム値）

となる。どちらの場合も ${c_j}$ は隠される。

各bitの ${e_{j, 0}, e_{j, 1}}$ を検証者に渡すため、ガーブラーはラベル ${\ell_0, \ell_1}$ で暗号化してアダプターテーブルに格納する： ${\mathcal{E}(\ell_0, e_0), \mathcal{E}(\ell_1, e_1)}$

検証者は、自分のビット値に対応するいずれかのラベルしか知らないため、2つのうち1つしか復号できない。これにより ${c_j}$ が検証者に漏れることはない。

ただ、このままだとノイズが入ったままなので、ノイズ除去をする必要がある。たとえば、 ${F_z = c_0 + c_1 x}$ で考える場合（ ${c_0, c_1}$ は秘密係数、xは公開入力）、ガーブラーがノイズを含めて計算した値を

${e_0 = c_0 + r_0}$
${e_1 = c_1 + r_1}$

とした場合、そのまま計算すると

${e_0 + e_1x = (c_0 + r_0) + (c_1 + r_1)x = F_z + r_0 + r_1x}$

となる。ノイズが残った状態なので、ガーブラーは ${e_2 = -r_1x - r_0}$ を渡す。ガーブラーはすべての値を知ってるのでこの計算は可能。検証者は ${e_2}$ をさらに加算することでノイズを除去できる。このデータはアダプターテーブルに追加フィールド要素として含まれるみたい。

Half Gate

↑のアダプターテーブルは、Half Gate手法を適用することでサイズを半分にできる。具体的には、b = 0の方の出力 ${r_j}$ の値をラベル ${\ell_0}$ のハッシュ値 ${H(\ell_0)}$ とし、テーブルに格納するのを ${\mathcal{E}(\ell_1, e_1)}$ のみとする。こうすると、

b = 0の場合は、 ${H(\ell_0)}$ を計算するだけ
b = 1の場合は、テーブルの内容を ${\ell_1}$ で復号する

と計算できる。

再構成

検証者は全bit分の ${e_{j, b_j}}$ を入手すると、bit位置に応じた ${2^{j}}$ を乗算して合算し、ノイズ除去を行い、MAC値を計算できる。こうして得られたMAC値 ${\lbrack P \rbrack = \phi(P) + K}$ は準同型性を持つため、2つのMAC値を以下のように加算すると

${\lbrack P \rbrack + \lbrack Q \rbrack = \phi(P) + K_P + \phi(Q) + K_Q = \phi(P + Q) + (K_P + K_Q)}$

P + Qに対するMAC値が得られる。この特性により、フリーゲートと同様、ガーブルド・テーブルを必要とせずに楕円曲線上の点の加算ができる。論文では、

In forthcoming work, we will show how to build a garbling scheme for pairing-based SNARK verifiers that respects this MAC structure. In different forthcoming work, Babylon Labs [27] will use our technique in a different way to build a SNARK verifier based on linear pairing witness encryption [28]. In both cases, the key enabling technology that makes these schemes over 1000× more efficient than existing approaches is Argo MAC.

とあり、SNARK検証器全体のガーブリングスキームは後続の論文で公開されるらしい。そのスキームにおいてArgo MACがテーブルサイズの支配的コストとなるため、Groth16検証器全体で約25MBと推定されていて、BitVM 3sの約280GBと比較すると約10,000倍の削減になると。

あと、↑にも書いてあるけどBabylon LabsもArgo MACベースのSNARK検証器の構築を予定しているらしい。

*1:フリーゲートの方は入力ラベルから出力ラベルを導出可能なのでガーブルド・テーブルが不要

2026-02-10

Garbled Circuitを利用した効率的なSNARK検証を提案するBitVM 3s

BitVM Bitcoin Cryptography

BitVM 3について、以前以下の記事を書いたけど↓

techmedia-think.hatenablog.com

このRSAベースのガーブリングスキームには安全性の仮定に誤りがあり取り下げられ、その後BitVM 3sという改訂版が公開された↓

https://bitvm.org/bitvm3.pdf

3sの名前は、Secure、Simple、Bitcoin Scriptベースというところから来てるらしい。

BitVM 3s

BitVM 3-RSAもBitVM 3sもいずれもJeremy Rubinが提案したDelbragのアイディアを元にしたもので、SNARK証明の検証をオンチェーントランザクションを用いたチャレンジ＆レスポンスで実行するBitVM 2のスキームをオフチェーンにオフロードするという点は変わらない。

BitVM 3sのシンプルなブリッジの構成は↓

BitVM 2よりシンプルになってる。

DepositTx：ユーザーがBTCをn-of-nマルチシグにロック。全オペレーターの協力で作成・公開。
WithdrawTx：オペレーターが引き出しを請求する際に公開。セットアップ時に事前署名によるコベナンツを使用。
AssertTx：引き出しを請求するオペレーター自身が公開。担保を差し入れつつ、SNARK証明の入力ラベルをLamport署名で公開。
DisproveTx：不正があった場合に誰でも（パーミッションレス）公開可能。セットアップ時にGarbled Circuitのデータを受け取っていれば、誰でも不正を検出してDisprove Scriptを実行できる。

セットアップ

ガーブラー（証明者、オペレーター）は、SNARK検証用のGarbled Circuitを生成する。Groth16検証回路は約100億ゲート（77億のフリーゲート＋27億の非フリーゲート）で構成される。*1

フリーゲートとはXORゲートのことで、2つの入力ラベルのXOR値を使って出力ラベルを導出できるようにしているため（Free-XOR手法）、ガーブルド・テーブルが不要になる。つまり、出力ラベル = 入力ラベルA ⊕ 入力ラベルB
非フリーゲートはXOR以外のゲートで、（↑のDelbragの記事に書いたように）2つの入力ラベルで出力ラベルを暗号化したガーブルド・テーブルを必要とする。
- ここでは、k = Hash(入力ラベルA ⊕ 入力ラベルB)を計算し、
- kで出力ラベルを暗号化してガーブルド・テーブルのエントリーciphertext = 出力ラベル ⊕ kを導出する

ガーブラーは、各非フリーゲートについて、

ワイヤーラベル：各ワイヤーの0と1の状態に対応する128bitのランダム値（ラベル）。このラベルをBitHash（後述）した値がDisprove Scriptにコミットされる。
ガーブルド・テーブル：2つの入力値の組み合わせ分（合計4つ）、出力ラベルを暗号化したもの
Taprootコミットメント：各ガーブルド・テーブルのエントリーを検証するためのDisprove Script（後述）を含む巨大なTaptree

を生成し、検証者にガーブルド・テーブルのデータと各ワイヤーラベルのハッシュ値を送る。検証者は、これらの情報からTaptree（各リーフがDisprove Scriptでそこに適切なハッシュ値が埋め込まれていること）が正しく構築されていることを検証する。

アサーション

ガーブラーはSNARK証明を公開する。↑のブリッジの例では、これでブリッジの清算をトリガーする。この時、担保として提供する金額はDisprove Scriptが約20KB未満とこれまでに比べて小さいので、$100未満くらい。

AssertTxのインプットのwitnessにはSNARK証明（128 byte）とSNARKの公開入力値（20 byte）に対応するラベルが含まれるため、予め担保UTXOは、これらのデータに対するランポートコミットメントが設定されたロックスクリプトに資金をロックしたものになると思われる。そしてAssertTxで実際のデータとそれに対するランポート署名が提供される。

どうしてランポート署名が必要かというと、ガーブラーはすべてのラベルの値を知っているけど、検証者は与えられたラベル値が0に対応するものか1に対応するものか知る術がない。そのためランポートコミットメントにより、各ビットが指すラベルの値がオンチェーンでコミットすることで、確定したビット列（SNARK証明と公開入力）を誰でもオンチェーンで確認できるようにしている。このラベルと実際のデータの紐付けがないと意味のあるSNARK検証を行っていることを確認できない。

チャレンジ

SNARK証明や回路が不正であれば、検証者はTaptreeのデータを使ってオンチェーンでFraud Proofを提供することで、ガーブラーのアサーションを無効化する。期間内にFraud proofが提供されなければタイムアウトにより証明は有効とみなされる。

Fraud proofには、

計算が不正なゲートの入力ワイヤーラベル
Taptree内の該当ゲート（Tapleaf）のマークルパス
TapleafのDisprove Script

が含まれ、Disprove Scriptでは以下がチェックされる

入力ラベルがコミットされた値と一致するか検証
復号鍵k = Hash(入力ラベルA ⊕ 入力ラベルB)を計算
出力ラベルを復号：出力ラベル = ciphertext ⊕ k
Hash(出力ラベル)がコミットされた値と異なる場合、不正が証明される

BitHash

BitVM 3のコア機能の1つがBitcoin Script向けの新しいハッシュ関数BitHash。BitcoinにはOP_SHA256やOP_RIPEMD160などのハッシュ計算用のopcodeがあるけど、これらはすべて入力値をまるごとハッシュするので、入力の各ビットを個別に取り出して後続の計算に使うといったことができない。また算術系のopcodeも現状32 bit演算しかサポートしていない。*2

BitHashは、128 bitのプリイメージを1 bitずつ処理するハッシュ関数で、各bitの値に応じてRIPEMD160とOP_SHA256のいずれかを適用する。

<bit 127> <bit 126> . . . <bit 1> <bit 0> # 入力値
<初期値> # 0x00000000

128回繰り返し:
  OP_SWAP
  OP_DUP
  OP_TOALTSTACK    // 後で使うために保存
  OP_IF
    OP_RIPEMD160    // ビット = 1 の場合
  OP_ELSE
    OP_SHA256       // ビット = 0 の場合
  OP_ENDIF

OP_DUPとOP_TOALTSTACKは、プリイメージを検証後に再利用するためにアルトスタックに保存するための処理。

OP_XORの課題

↑のFraud proofの検証には１つ問題があって、BitcoinのOP_XOR opcodeは2010年に無効化されており、Great Script Restoration提案などによるソフトフォークでの有効化が必要になる。またその際に、32 bit制限も解除される必要がある。

リソース要件

Garbled Circuitを利用した仕組みにより、BitVM 2と比べてオンチェーントランザクション数が劇的に削減され（約 1,000倍）、担保要件も低下し、BitHashの導入によりBitcoin Scriptの制約下で効率的なハッシュコミットメントを実現し改善が進んできてる。

あとは、Garbled Circuitのデータ約280GBのオフチェーンストレージが大きめか*3。

*1:RSAの場合は、RSA暗号の数学的構造を利用していてGarbled Circuitのラベルを生成・暗号化し、約50億ゲートで構成されていた。

*2:DlbragではBlake3のスクリプト実装を使用しているが、サイズが75KBになり、$10,000超の担保資金が必要になるという課題がある。

*3:Half-gates最適化により194GBに削減可能という話もある

Develop with pleasure!

福岡でCloudとかBlockchainとか。