2026-10-17

多数のユーザーで1つのUTXOを共有するLayer Tree

Bitcoin Layer Tree

最近Lightning Labsが発表したUTXOをマルチパーティで共有する新しいスケーリングソリューションLayer Treeについて↓

https://layertree.tech/

論文は、ショートバージョンとフルバージョンの2種類公開されている。

ペイメントチャネルは二者間でUTXOを共有するモデルだけど、こちらは以前記事にしたCoin Poolのように多数のユーザーでUTXOを共有するタイプのソリューション。

ロール

Layer Treeでは以下の3つのロールが登場する。

オペレーター：共有UTXOをセットアップし運営する主体。新しいメンバーをツリーに追加したり、メンバーの残高の変更に対して共同で署名する。また、ライトニングの中継役としてメンバー間の送金の仲介を行う。ただし、参加者の資金には手を出せない。
オーナー：共有UTXO内に資金を持つユーザー。いつでも自分の判断で、残高を引き出すことができる。また自分の残高の一部を切り出して他のユーザーに渡したり、後から換金できるバウチャー（後述）の発行などが可能。リーフの書き換え（鍵や期限、残高の変更）にはオペレーターとの連携が必要。
エビクター：リース期限（後述）を過ぎたメンバーを強制的に退出させることができる。各残高には期限を設定でき、期限が切れると、エビクターがその残高を共有UTXOから外すことができる。外す場合、残高は全額オーナーの受け取り先に支払われる。通常、オペレーターが兼務する。

共有UTXOのセットアップ

参加者の各資金は、オペレーターが運営するマークルツリーのリーフにエンコードされる。

オペレーターはまず、共有UTXOを作るにあたって以下のルールを決める：

ツリーの大きさ：最大で何人までメンバーを受け入れられるようにするか。
サポートする操作：一度に何人まで受け入れるか、まとめて退出できるか、バウチャーを利用可能にするかなど。
オペレーターの鍵：メンバーの加入の承認などに使用
使用するBitcoinのティア（後述）

これらのルールは、共有UTXOのアドレスにコミットされ、後から変更することはできない。

ルールが決まったら最初のツリーを構成する（最初はオペレーター自身の残高だけでもOK）。初期メンバーとその残高をコミットしたツリーを作成する。ツリーの各リーフは、以下のデータで構成される固定長の116 byteのレコード。

フィールド	byte数	エンコード	内容
`amount`	8	`le64`*1	残高（単位はsatoshi）
`exit_key`	32	x-only公開鍵	退出時の受取先の公開鍵
`owner_key`	32	x-only公開鍵	オーナーの公開鍵（退出、更新、バウチャーの認可に使用）
`evictor_key`	32	x-only公開鍵	エビクターの公開鍵
`evict_after`	4	`le32`*2のブロック高	リース期限
`nonce`	4	`le32`	リーフ識別用のnonceで作成時に選択
`seq`	4	`le32`	CLAIM/SPLIT毎にインクリメントする番号で、バウチャーのリプレイ防止

このリーフデータのタグ付きハッシュとamountを元にMerkle-Sum Treeを構成する。そしてツリーのルートハッシュを計算し（root_hashとする）、それを使ってTaprootの内部鍵を計算する↓

P = NUMS + int(H_tag("LayerTree/state", root_hash))・G

※ NUMSはNUMSポイント。内部鍵は上記の形で導出されるのでkey-pathでの引き出しはできない。このツリーは、Tapscriptを含むTaptreeではなく、Layer Treeの参加者の資金にコミットしたツリーで、それがTaprootの内部鍵にコミットしていることになる。

続いて、以下のTapleafを含むTaptreeを構成する：

Tapleaf	やること	必要な署名者
`EXIT_1`	リーフを１つツリーから取り除き、取り除いたリーフの金額を`exit_key`へ支払う	オーナー（期限後はエビクター）
`EXIT_K`	K人分の退出を1 Txで連続実行する	各リーフのオーナー/エビクター
`JOIN_h`	ツリー内の高さhの部分木に、新メンバーのグループをまるごと差し込む	オペレーター
`JOINK_K`	1リーフずつのJOINをK回行う	オペレーター
`UPDATE`	リーフを同じ位置で更新する	オーナー＋オペレーター
`CLAIM`	バウチャーでリーフを切り出す	バウチャー署名
`SPLIT`	署名でリーフを切り出す	オーナー
`EVICT_SUBTREE_h`	期限切れのコホートを一括で追い出し	オペレーター
`REWRITE_h`	ツリー内の部分木を一括で置き換え	変更されるリーフのオーナー＋オペレーター
`DETACH_h`	部分木を別のツリーのアウトプットに切り出す	オペレーター
`RECLAIM_1`	期限後に回収可能なリーフをオペレーターが取り戻す*3	`RECLAIM_KEY`

このTapscript内に冒頭のツリーのルールもコミットされる。上記のTapleafのロジックの実装方法は使用するティア（後述）によって異なる。

上記のTaptreeのルートハッシュと先程の内部鍵からP2TRアドレスを導出し、Merkle-Sum Treeでコミットされた総額と同じ金額をそのアドレス宛に送金することでセットアップが完了する。

※ このセットアップ時には、ツリー内の総額とアウトプットの金額が一致することはコンセンサスで保証されないので、オフチェーンのツリーデータと突き合わせてセットアップの正しさの検証が必要になる。以降の状態遷移においては、コベナンツによってツリーの金額とアウトプットの金額の正しさはコンセンサスで保証されるようになる。

メンバーの参加

共有UTXOのセットアップ後、新しいメンバーの参加はすべてツリーの状態遷移として行われる。JOIN_hを使って、h=0なら1人、hが大きければ最大2^h人をまとめて参加させることができる。

コホートのグラフト

一緒に参加するメンバーのグループをコホートと呼ぶ（通常、同じリース期限を共有する）。ツリー内の高さhのノードの下には2^h個の連続したリーフがぶら下がっていて、この区画がすべて空の場合、この区画の頂点のノードは空ノードを積み上げた結果になるので既知の定数（ ${E_h}$ ）になる。

オペレーターは、コホートのメンバーをリーフとして、高さhの部分木を構成し、その頂点ノードのハッシュ値と合計金額を ${E_h}$ の位置に差し込むことで、複数のメンバーをまとめてツリーに参加させることができる。これをグラフトと呼ぶ。

グラフト前（D=3）                  グラフト後
            root                               root'
          /      \                           /      \
       N(2,0)    E_2   ← 空き区画        N(2,0)    C   ← コホートの頂点
       /  \      /  \                    /  \      /  \
      .    .    E_1  E_1                .    .    .    .
     / \  / \   / \  / \               / \  / \  / \  / \
     A  B -  -  -  -  -  -             A  B -  -  W  X  Y  Z

JOIN_hのwitnessは以下で構成される：

部分木の頂点からルートまでのマークルパス
新しい部分木の頂点のハッシュと合計金額
オペレーターの署名
現在のルートハッシュと、Taptreeのルートハッシュ

これらのwitnessを用いて、スクリプトで以下の検証が行われる

witnessのルートハッシュとTaptreeのルートハッシュから計算したscriptPubkeyが、使用するインプットのscriptPubkeyと一致すること。これでツリーの状態とルールの両方を確認する。
${E_h}$ からマークルパスを使ってルートを計算すると現在のルートになり、その合計金額がインプットの金額と一致すること。これによりツリー内の ${E_h}$ の区画が空いていたことを確認する。
新しい部分木の頂点ノードから同じマークルパスを使って、新しいルートを計算する。
Txのアウトプットが新しいルートと同じTaptreeから導出したP2TRで、金額が、「旧総額＋コホートの合計額」になっていること。

増額分の資金は、トランザクションの別のインプットで補うことになるが、それが誰の資金かはコベナンツでは関知しない。

スクリプトは差し替える部分木の位置より上の層しか計算しないので、コホートが大きいほどトランザクションは小さくなる。

参加者による検証

コベナンツが確認するのは部分木の頂点のハッシュと合計額だけで、その下に本当にリーフが存在するかは検証しない。中身のない部分木がグラフトされると、合計額は合っていても誰もその下のリーフを証明できないため、その分の資金は凍結される（既存のメンバーの残高には影響しない）。

そのため、参加者は資金を投入する前に、未署名のトランザクションについて以下を確認する必要がある：

インプットが、期待する金額で現在のツリーのアウトプットを使用している
空き区画から、マークルパスを使って現在のルートを計算できる
自分のリーフから、部分木内のパスを使ってグラフトする頂点ノードを計算できる（合計額も再計算）
アウトプットが、新しいルートと「旧総額＋部分木の合計額」にコミットしている
自分のリーフのフィールド（金額、鍵、エビクター、リース期限）が合意通りである
自分のインプットとお釣りが合意通りである

確認後、すべてのアウトプットにコミットする署名をすれば、自分の資金は「自分のリーフを含むツリー」を作るトランザクションにしか使われない。

資金の拠出方法

オペレーターが立て替える：オペレーターがコホートの合計額を全額出し、メンバーはグラフトの承認後に、ライトニングやハッシュロック付きバウチャーで残高を購入する。メンバーが支払わないリスクはオペレーターが負う。1人あたりのコストが最も小さい。
各メンバーが拠出する：各メンバーがグラフトTxに自分のインプットを追加して署名する（1人あたり約58 vB増）。全員が署名するまでブロードキャストできないので、1人でも不在だとコホート全体が止まる。
ミックス：一部をオペレーター、一部をメンバーが拠出する。

リース期限

evict_afterは、そのリーフのリース期限を表すブロック高で、賃貸の契約期間のようなもの。この高さを過ぎると、エビクターがそのリーフをツリーから強制的に外せるようになる（nLockTimeがevict_after以上のトランザクションでのみ有効）。ただし外す場合も、リーフの金額は全額exit_key宛に支払う必要があるので、エビクターが資金を奪えるわけではない。

オペレーターから見ると、リース期限は席を貸す期間を区切る仕組みで、主に以下の目的で使われる：

死蔵リーフの回収：連絡がつかなくなったメンバーの席を、期限後に空けることができる。
コホートの一括追い出し：同じリース期限を共有するコホートは、期限後にEVICT_SUBTREE_hで1トランザクションでまとめて追い出せる。

メンバー側は、以下のような選択ができる：

期限の更新：オペレーターと合意してUPDATEでevict_afterを延ばす。
追い出されない設定：期限を遠い将来にするか、evictor_keyを誰も秘密鍵を知らないNUMSポイントにする。
期限0：いつでもエビクターが強制的に外せる必要があるリーフ（チャネルを載せたリーフなど）はevict_after = 0にする。

退出

オーナーはいつでも、オペレーターの協力なしに、1トランザクションでツリーから退出できる。タイムロックも事前署名済みのトランザクションも不要。

EXIT_1のwitnessは以下で構成される：

自分のリーフの位置からルートまでのマークルパス
116 byteの自分のリーフデータ
署名と、オーナーによる退出かエビクターによる追い出しかを示すフラグ
現在のルートハッシュとTaptreeのルートハッシュ

スクリプトは以下を検証する：

ルートハッシュとTaptreeのルートハッシュから計算したscriptPubKeyが、使用中のインプットのscriptPubKeyと一致する
リーフからマークルパスを使ってルートを計算すると、現在のルートになり、その合計額がインプットの金額と一致する
リーフを空ノード ${E_0}$ に置き換えて同じパスで新しいルートを計算する
署名を検証する
- オーナーの場合：owner_keyによるトランザクションへの署名（全アウトプットにコミットするもの）
- エビクターの場合：evictor_keyによる署名、かつnLockTimeがevict_after以上
2つめのアウトプットがP2TR(exit_key)宛になっている。金額は、オーナーの場合はリーフの金額以下（差額は手数料に回せる）、エビクターの場合はリーフの金額と完全に一致
1つめのアウトプットが、新しいルートとTaptreeから導出したP2TRで、金額が「旧総額−リーフの金額」になっている

退出トランザクションのサイズは、深さ16のツリーで約1,020 vB。1インプット1アウトプットの通常のP2TRトランザクション（約111 vB）の約9倍だけど、メンバー数には依存せず、ツリーの深さだけで決まる。同規模のトランザクションツリー（Ark型）から単独で退出する場合は約2,511 vBになる。

複数のリーフをまとめて取り除く操作もあり、1人あたりのコストはまとめるほど小さくなる。EVICT_SUBTREE_hとREWRITE_hは、部分木の内部ノードを1回ずつしか計算しないので、人数が増えるほど1人あたりのコストが下がる。

バウチャー

バウチャーは、オーナーが「自分のリーフから、この内容の新しいリーフを切り出してよい」と署名したメッセージで、いわば小切手のようなもの。受け取った人は、後から好きなタイミングで、発行者の関与なしにCLAIMを使ってこれをツリー上で換金できる。まだツリーに参加していない人にも、バウチャーを渡すことでツリー内でビットコインを送れる。

バウチャーの署名対象は、以下のメッセージのタグ付きハッシュで、

H_tag("LayerTree/voucher", tree_id || body(source_leaf) || claim_leaf)

tree_id：ツリーの識別子。ツリーをセットアップしたTxの0番めのインプットのアウトポイントから導出。
body(source_leaf)：切り出し元のリーフデータからamountを除いた108 byte
claim_leaf：切り出して作る新しいリーフ（116 byte）

CLAIMは、以下の2ステップを1トランザクションで実行する：

切り出し元のリーフの金額を新しいリーフの分だけ減らし、seqを1増やす（金額が0になればその位置は空になる）。
ステップ1の後のツリーで空いていることが証明された位置に、新しいリーフを配置する。

ツリーの総額は変わらないので、共有UTXOの金額も変わらない。またスクリプトは、以下のルールも強制する：

新しいリーフのevictor_keyは切り出し元と同じで、evict_afterも切り出し元より後にできない。これがないと、追い出されそうなメンバーが、残高を追い出されないリーフに逃がせてしまう。
新しいリーフの金額と、切り出し元に残る金額は、いずれもDUST_MIN（推奨330 sat）以上。

ステップ1でseqがインクリメントされるので、切り出し元のリーフの中身が変わり、同じバウチャーの署名は二度と検証を通らない。つまり、バウチャーは1回しか使えない。

※ またバウチャーの署名時からamount以外のリーフデータが更新された場合、バウチャーは無効になるので、基本的にバウチャーは受け取ったらすぐ使う必要がある。

制約

すべての状態遷移は同じUTXOを使用して再作成するので、未承認の遷移はトランザクションのチェーンになる。Bitcoin Coreのリレーポリシー（v31.0より前は未承認の子孫25個、以降のクラスターmempoolであれば64個）によって、他人同士が1人ずつ退出する速度には上限がある。また、チェーンの手前に手数料の低い遷移が1つあると、後続すべての手数料率が抑えられるというピンニングの課題もある。

構造的な対策は、デプロイメントを複数のツリーに分割することになる模様。DETACH_hでコホートを別のアウトプットに切り出すこともできる。

ティア

Layer TreeをBitcoinで利用可能にするためにはコベナンツのサポートが必要になる。Layer Tree自体は独自のコベナンツopcodeは提案しておらず、現在提案中のopcodeを組み合わせて以下の4種類の実現方法を提案している。

ティア	必要なopcode	サポート操作	`EXIT_1`のスクリプト/witness	退出Tx
FULL	BIP-441、`OP_TX`、`OP_CHECKSIGFROMSTACK`、楕円曲線の演算opcode	すべて	2,101 / 902 B	1,020 vB
MID	`OP_CAT`、`OP_TX`、`OP_CHECKSIGFROMSTACK`、`OP_TWEAKADD`	すべて*4	3,367 / 978 B	1,355 vB
MIN	`OP_CAT`、`OP_TWEAKADD`	`EXIT_1`と`SPLIT`のみ	3,640 / 1,175 B	1,473 vB
CCV	`OP_CHECKCONTRACTVERIFY`、`OP_TX`、`OP_CHECKSIGFROMSTACK`*5	すべて	1,716 / 838 B	908 vB

ツリーのデータフォーマットは全ティア共通で、ティアごとに違うのはTapleafのスクリプトの実装方法になる。ツリーはどれか1つのティアで作成し、作成後に変更することはできない。スクリプトのバイト列が違うので、同じパラメータでもティアが違えばTaptreeのルートハッシュも異なる。

いずれにせよ、これらのいずれかの組み合わせを満たすopcode群がソフトフォークで導入される必要がある。

Coin Poolとの違い

どちらも多数のユーザーで1つのUTXOを共有し、各ユーザーが他の参加者の許可なくいつでも退出できる、という目標は同じ。ただし、仕組みは大きく異なる。

	Coin Pool	Layer Tree
オペレーター	なし	あり
状態の更新	全員の署名	関係者（オーナー＋オペレーター）の署名
状態の表現	集約公開鍵＋参加者ごとのTapleaf＋事前署名Tx	Merkle-Sum Treeのルート（内部鍵）＋共通の遷移ルール（Taptree）
単独退出	Update Tx → タイムロック → Withdraw Tx	1トランザクション
退出後の残りのメンバー	Snapshot Txで作り直し	何もしなくていい
メンバーの追加	全員で作り直し	オペレーターによるグラフト
オペレーターへのトラスト	不要	活性のみ（加入、リース後の継続、協調操作）。資金の安全性は不要
退出の集中	課題	課題

*1:64 bitのリトルエンディアン

*2:32 bitのリトルエンディアン

*3:オンチェーン資金を持っていないユーザーがライトニングでツリーに入金を受け取るケースなどで使用

*4:ただしツリーの総額は21.47BTC未満

*5:バウチャー利用時のみ必要

2026-09-22

Liquid Networkのインフレーションバグの仕組み

Elements vulnerability

2026年9月6日に、BlockstreamのLiquid Networkから約4,000BTCが流出した件（サイドチェーン上の資金の約95%が抜かれた）について、その攻撃手法について確認してみた（※ 現時点では、Blockstreamから原因に対する公式な発表はまだない）。

Confidential Transactionと範囲証明

まず前提として、Liquid Networkでは取引金額を第三者に対して秘匿するConfidential Transaction（CT）という仕組みを採用している（CTについては過去のブログ記事やGBEC動画参照）。

トランザクションの各アウトプットの金額とアセット種別は、以下のようなPedersen Commitment（楕円曲線上の点）として表現される。

C = v・H(asset) + r・G

Gは楕円曲線上の生成点（固定値）
vは秘匿対象となる金額
rはブラインドファクター
H(asset)は、アセット毎に決まる生成点*1

一般的に、トランザクション内で勝手にコインを新規発行されていないか（＝アウトプットのコインの合計額がインプットのコインの合計額を超えていないか）をチェックする必要がある。Bitcoinのような価格が明示的に示されているケースであればこれは簡単にチェックすることができるけど、金額が上記のように秘匿されている場合、以下の2つのチェックが必要になる。

バランスチェック（secp256k1_pedersen_verify_tally）：インプットの金額のコミットメントの総和とアウトプットの金額のコミットメントの総和を引いて、結果が単位元になるかをチェックすることで、インプット/アウトプットのバランスが釣り合っていることをチェックする。
範囲証明（secp256k1_rangeproof_verify）：秘匿されているvの値が ${\lbrack 0, 2^{64} )}$ の範囲内に収まっているかどうかチェックする。これがマイナスの金額になっているとバランスチェックをパスする形でインフレーションが可能になるので、バランスチェックとセットで必要になる。

加えて、LiquidのCTでは、コミットメントで使用されているアセットの生成点が正しいアセットに対応しているかをチェックする必要がある。上記のアセットの生成点H(asset)は実際には、アセットを識別できないように、

H' = H(asset) + b・G

のようにランダムに選択されたブラインドファクターbを用いてブラインドされる。このようにブラインドされた状態でもアウトプットのコミットメントのアセット生成点がインプットで使用されている生成点と対応しているかチェックするための仕組みがAsset Surjection Proof（詳細は以前のConfidential Assetsの記事参照）。

キャッシュの実装の脆弱性

今回突かれたのは、上記の範囲証明のチェックのキャッシュについてのノードの実装ミスになる。

範囲証明のチェックを行うsecp256k1_rangeproof_verifyはコスト高な処理のため、Elementsでは一度検証に成功した範囲証明の結果をキャッシュし、同じ範囲証明の再検証をしないようにしている。問題は、この同じ範囲証明か？を判定するために使われるキャッシュキーの作り方にあった。

バグA

Elementsでは2018年の~~0.17.0~~0.14.1時点で、キャッシュのキーは以下のように、salt（ノード起動時に初期化されるランダム値）と範囲証明とコミットメントのデータのハッシュ値で構成されるようになった。

void SignatureCache::ComputeEntryRangeProof(uint256& entry, const std::vector<unsigned char>& proof, const std::vector<unsigned char>& commitment) const {
    CSHA256 hasher = m_salted_hasher_range_proof;
    hasher.Write(proof.data(), proof.size()).Write(commitment.data(), commitment.size()).Finalize(entry.begin());
}

一方、範囲証明を検証するロジックであるVerifyRangeProofでは、これ以外に、アセットの生成点（tag）とscriptPubKey（extra_commit）にも依存している↓

secp256k1_rangeproof_verify(ctx, &min, &max, &commit,
    proof.data(), proof.size(),
    scriptPubKey ...,   // extra_commit
    scriptPubKey.size(),
    &tag);              // asset generator

つまり、検証側ではアセットとスクリプトに依存しているのに、キャッシュのキーはそれをカバーしていない。そのため、正規のアウトプットに対して検証およびキャッシュされた証明を、コミットメントは同じままアセットだけ差し替えたアウトプットに流用すると、キーが一致してキャッシュにヒットし、実行すれば失敗するはずの検証がスキップできる可能性がある。ただ、

同じコミットメント値を再利用し、
最初にキャッシュにのせるための証明は本物であること

といった制約から、実際にインフレーションまでもっていくのはハードルが高い。

バグB

2026年に行われたバグAを塞ぐ修正では、キーにasset_commitmentとscriptPubKeyが追加された（コミットc26d719）。

void SignatureCache::ComputeEntryRangeProof(uint256& entry, const std::vector<unsigned char>& proof, const std::vector<unsigned char>& commitment, const std::vector<unsigned char>& asset_commitment, const CScript& scriptPubKey) const {
    CSHA256 hasher = m_salted_hasher_range_proof;
    hasher.Write(proof.data(), proof.size()).Write(commitment.data(), commitment.size()).Write(asset_commitment.data(), asset_commitment.size()).Write(scriptPubKey.data(), scriptPubKey.size()).Finalize(entry.begin());
}

つまり、キャッシュのキーは以下の連結データのハッシュ値

salt（32 byte） || proof（可変長） || commitment（33 byte） || asset_commitment（33 byte） || scriptPubKey（可変長）

問題となったのは、連結する際に区切りがなく、可変長データが存在すること。

実際のエクスプロイト

実際にオンチェーンで確認できたデータによると、攻撃者はまず細工したscriptPubKeyと正当な範囲証明を持つアウトプットを持つプライマートランザクションを作成し、キャッシュに正規のエントリーを乗せる。このときのキーは以下のような構成：

<salt> || <有効な範囲証明> || <有効な金額> || <L-BTC> || OP_RETURN <負の金額> <L-BTC> OP_RETURN

scriptPubKeyは 6a43 || C1 || X || 6a（6a=OP_RETURN、43=続く67バイトのpush）という構造で、C1（33 byteのコミットメント）、X（L-BTCのアセット生成点）、6a を意図的に並べてある。

次に、無効な範囲証明と巨大な負の値のOP_RETURNアウトプットを持つエクスプロイトトランザクションを作成する。このとき、無効な証明はその末尾がプライマーの<有効な金額> <L-BTC> OP_RETURNと一致するように作る。

<salt> || <有効な範囲証明> <有効な金額> <L-BTC> OP_RETURN || <負の金額> || <L-BTC> || OP_RETURN

すると、||の連結の位置は違うけど、連結後のデータは全く同じになる。

プライマートランザクションで、本物の範囲証明は検証をパスしてキャッシュされ、その後でエクスプロイトトランザクションが処理されると、キャッシュヒットにより範囲証明のチェックはスキップされる。エクスプロイトトランザクション内にさらにこの負の金額と同じだけの正の金額を同居させれば、pedersen_verify_tallyのバランスチェックもパスし、インフレーションが成功する*2。

生成された偽のL-BTCは、その後SideSwapのペグアウトサービスに正面から投入され、当然ながらSideSwapは偽物と本物を区別できず、正規のペグアウト認可でL-BTCをバーンし、「コンセンサス上有効な」引き出しに署名することになったと。

修正

9月9日にリリースされた修正版のElements v23.3.4では、キーの生成は以下のようにデータの長さをプレフィックスとして付加するように修正された（コミットb0a2752）*3。結果、上記のような細工はできなくなる。

void SignatureCache::ComputeEntryRangeProof(uint256& entry,
                                            const std::vector<unsigned char>& proof,
                                            const std::vector<unsigned char>& commitment,
                                            const std::vector<unsigned char>& asset_commitment,
                                            const CScript& script_pub_key) const
{
    HashWriter hasher = m_salted_hasher_range_proof;
    // We commit to both commitments and the scriptPubKey because these are
    // committed to by the rangeproof itself; a change in any of them would
    // invalidate the proof. Since these are exactly the arguments to
    // CachingRangeProofChecker::VerifyRangeProof (below), there is no
    // additional data that could affect the rangeproof's validity.
    // Serialization length-prefixes every field, including the variable-length
    // proof and script, so distinct argument tuples cannot share an encoding.
    hasher << proof << commitment << asset_commitment << script_pub_key;
    entry = hasher.GetSHA256();
}

また、合わせてキャッシュを完全に無効化する-norangeproofcache起動オプションも追加された模様。

今回の脆弱性はコンセンサス仕様のバグではなく、範囲証明の検証を高速化する最適化コードの実装バグ。しかしその検証キャッシュが「検証をスキップするか否か」を決める位置にあるため、影響はコンセンサスクリティカルなものになった。実際、バグBを含むバージョンのElementsを動かすノードがインフレーションブロック（4,050,336）を受理・確定させ、バグBを含まない公式版のノードはこれを拒否して4,050,335で停止するチェーンスプリットが発生。ここで資金流出が現実化したのは、ペグアウトのBTC送金を承認するwatchmanが、この受理側フォークを正当なチェーンとして扱い、バーンされた（偽の）L-BTCに対してメインチェーンのBTCを払い出したためと思われる。サイドチェーンのブロック受理では多数派が正しく拒否していたものの、メインチェーンのBTC送金はそれとは独立に、受理側に追随した連合の署名によって実行された。なお、個々の連合のエンティティが具体的にどのバイナリを動かしていたかは公表されておらず、確定にはBlockstreamの公式発表を待つ必要がある。

9/24にBlockstreamの公式発表が公開された。

これによると、事件の時点で15のfunctionaryはすべて同じ修正済み（バグBを含む）ビルドを動かしていた。したがってスプリットは「バグBを含むか否か」というバージョンの差ではなく、各ノードのキャッシュ状態の差によって生じた。攻撃時に、攻撃に使われたのと同じキャッシュエントリを既に保持していたノードは、範囲証明の検証をスキップしてブロックを受理した。一方、コールドキャッシュのノード（あるいはバグBの修正がまだ適用されておらずバグAのままだったノード）は、実際に範囲証明を検証して失敗し、ブロックを拒否した。攻撃者が、Liquid上に恒常的に現れるL-BTCのアセットタグとよく使われる宛先スクリプト（ペグアウトアドレスなど）を再利用してasset commitmentとscriptPubKeyの2フィールドを固定したため、キャッシュを汚染するための土台となる正規のエントリは、日常的なトランザクションによって絶えず生成される状態だった。

ここで資金流出が現実化したのは、ペグアウトのBTC送金を承認するwatchmanが、受理側のチェーン状態を正当なものとして扱い、バーンされた（偽の）L-BTCに対してメインチェーンのBTCを払い出したため。サイドチェーンのブロック受理では割れが生じていたものの、メインチェーンのBTC送金はそれとは独立に、インフレーションしたL-BTCを「コンセンサス上有効」と認識したfunctionaryの署名によって実行された。なお、Blockstreamはこの流出について、SideSwapのPAKもオンラインキーも侵害されておらず、インフレーションL-BTCが正規のペグアウト手順を通ったことによるものだと説明している。

参考

*1:単純にBitcoinのみをアセットとして使用する場合は、このHは単一の固定値でよく、LiquidのConfidential Assetsの場合は、Bitcoin以外のアセットも扱えるようにするためにこのようなアセット毎の生成点を導入している。

*2:厳密には、プライマートランザクションがブロックに格納されて、そのブロックが各ノードに接続されるとプライマートランザクションのアウトプットの範囲証明はキャッシュから消える。この状況でエクスプロイトトランザクションをブロックに格納して各ノードに有効と判定させるためには、その直前に別のプライマートランザクションをmempoolに入れて再度キャッシュを汚染する必要がある。

*3:<<演算子は、各可変長データに対してCompactSize形式の長さのプレフィックスをつける

2026-08-31

ソフトフォークなしで量子安全なトランザクションを作るQSB

PQC Bitcoin Cryptography

StarkWareのAvihu Mordechai Levyが公開した、Bitcoinのプロトコルを一切変更せずに量子安全なトランザクションを作るというQSB（Quantum Safe Bitcoin）の提案↓

github.com

で実際にmainnetで実行されたトランザクションが↓

https://mempool.space/tx/305a24ffea912b9cf428f29ebf952321c96dab5bab284fc0d0801562f5abab07

QSBは、Bitcoinに新しいポスト量子署名方式を導入する提案というより、既存のBitcoin Scriptを使って、楕円曲線に依存しないPoWを作り、そのPoWによってトランザクションを量子安全なハッシュベース署名に結びつけるというアプローチ。Bitcoin Scriptには量子安全な署名を直接検証するopcodeは現時点ではないので、かなりトリッキーなことをやっている。

OP_CATの再導入や既存のBitcoin Scriptを用いてBitcoinに量子耐性を持たせる提案自体は前からあって、このブログでも何回か取り上げてる↓

Bitcoin Scriptを使ったランポート署名の検証と量子耐性（2021年、Jeremy RubinのOP_CATを使った提案）
ECDSA署名のサイズに対するランポート署名（2024年、Ethan HeilmanのOP_CAT不要の提案）

QSBはこの系譜の延長線上で、直接的にはRobin Linusが2026年に公開したBinohashの改良版になる。この流れを整理しつつ中身を見ていく。

2021年：OP_CATを使う（Jeremy Rubin）

最初のアプローチは、ランポート署名の検証ロジックをBitcoin Scriptで直接組むというもの。ECDSAの署名データのHash160（20 byte）をメッセージとみなして、それに対するランポート署名を検証する。ただ20 byte＝160 bitのメッセージをScriptで扱うにはビット単位の分解と再結合が必要で、OP_CATの再有効化が前提だった。

2024年：署名のサイズにコミットする（Ethan Heilman）

OP_CATなしでやろうとしたのがHeilmanの提案。トランザクションデータそのものではなく、トランザクションに含まれるECDSA署名(r, s)のサイズをメッセージとみなす。

Bitcoin Scriptからトランザクションの中身は読めないけど、OP_SIZEで署名のバイト数は読める。そしてk = 1/2という既知のnonceを使うとrは21 byteの固定値になり（以降r_minと呼ぶ）、あとはsのサイズだけが署名長を決める。sの先頭バイトが0になる確率は1/256なので、「短い署名」を作るのはPoWになる。この1 bitの情報にランポート署名を付ける、というアイディアだった。

ここで面白いのは、n個の署名のうちm個を短くする場合、正規の支払人はどの位置がヒットしてもいいので、成功確率は ${ (\frac{255}{256})^{n-m} \times (\frac{1}{256})^{m} \times {n \choose m}}$ 。一方、プリイメージを見た攻撃者は同じ位置に同じサイズの署名を作らないといけないので、その成功確率は ${ (\frac{255}{256})^{n-m} \times (\frac{1}{256})^{m}}$ 。例示されていたn = 800、m = 10だと、攻撃者は ${2^{84}}$ 回、正規の支払人は1,000回程度の試行で済む。攻撃者のコストを決めているのは ${(\frac{1}{256})^{10} = 2^{-80}}$ の部分、つまりmの方で、nは支払人の割引率 ${ {800 \choose 10} \approx 2^{74.6}}$ を稼ぐために必要な数になっている。

ただ、この方式だと1つの署名から1 bit分しか取れないので、n = 800とすると、そのまま800個のECDSA署名がトランザクションに乗ることを意味する。ロックスクリプトだけで数十KB、非プッシュopcodeも数千個必要で、以下の制限に抵触する：

スクリプト全体のサイズ上限10,000 byte
評価可能なopcode数の上限201*1

そのため当時の記事にも書いたとおり、実用性は微妙だった。

2026年：Binohash（Robin Linus）

これを実用レベルに引き上げたのがBinohash↓

https://robinlinus.com/binohash.pdf

やってることは同じ「トランザクションを一意に指す値を作って、それにランポート署名する」で、二項係数を使う点もHeilmanの手法と変わらない。違うのは二項係数の作り方。

Heilmanの方式の場合、 ${ {800 \choose 10}}$ を得るために、n個の署名を1つずつ実際にグラインドしてサイズを判定する必要があって、そのn個の署名がまるごとオンチェーンに乗る。上述したどおり、これが201と10,000 byteの制限に抵触する。

Binohashが使うのはFindAndDelete。Segwit以前のOP_CHECKMULTISIGは、sighashを計算する前にscriptCodeから検証対象の署名を全部削除するという挙動をする。そのため、ロックスクリプトにn個（たとえば150個）のダミー署名を埋め込んでおいて、そのうちt個を選んでOP_CHECKMULTISIGに渡すと、選んだ部分集合ごとに違うscriptCode＝違うsighashが得られる。

これにより、係数の根拠が「n個の署名」から「どのt個の署名を選択するか」になるのがポイント。ダミーの署名はSIGHASH_SINGLEバグ*2によりトランザクション非依存に作れるので事前計算して使い回せるし、150個の署名プールはロックスクリプトに直書きしてもデータプッシュなのでopcodeの評価数を1つも消費しない。witnessで渡すのはインデックスt個だけ。

効率を比較すると↓

	ダイジェストの候補数	非プッシュopcode	1 bit追加するコスト
Heilman (n = 800, m = 10)	${2^{74.6}}$	約8,800	約600 opcode
Binohash (t = 8, 2ラウンド)	${2^{84.5}}$	197	約2.3 opcode

150個の署名プールはopcodeを消費しない代わりに1ラウンドで約4,650 byteに膨らむ。byte数を払ってopcodeを買っている構造で、これで201の枠に収まる。

Binohashで支払人がやるのは、トランザクションのピンニングとダイジェストの探索の2つ。

ピンニングは、nLocktimeやnSequenceのようなsighashに影響する自由なパラメーターを変えながらPoWパズルを解き、通った値でトランザクションを確定させる処理。以降トランザクションを1 byteでも変更すると解き直しになるので、事実上そのトランザクションに固定（ピン留め）される*3。ピンニングがないと、攻撃者は公開されたダイジェストを見た後にトランザクションのバリアントを安く量産して同じダイジェストになるものを探せてしまう。

ダイジェストの探索は、確定したトランザクションに対して150個のダミー署名からt個を選ぶ組み合わせを総当たりする処理。選んだt個をFindAndDeleteで削除してscriptCodeを作り、そこからsighashを計算してPoWパズルをチェックする。当たった部分集合がそのラウンドのダイジェストで、これを2ラウンド分。当たりが出なければピンニングからやり直し。

そして見つけたダイジェストにランポート署名を付ける。使うのはHORS（Hash to Obtain Random Subset）で、ロックスクリプト側にn個のハッシュコミットメントを並べておき、支払人は選んだt個のプリイメージを開示する。Scriptはそれをハッシュしてコミットメントと照合する。ダイジェストがそもそも「n個からt個を選んだ組み合わせ」なので、HORSとは形がそのまま噛み合う。

Binohashの問題

ここが今回の本題。BinohashのPoWパズルは、Heilmanと同じ署名サイズパズルを使っている。つまり、

r_min（21 byte）より小さいrを持つ曲線点を見つけるのは ${2^{96}}$ かかるから、コインを使用するにはr_minを使うしかない

という前提なんだけど、これ自体も楕円曲線の困難性仮定である。

Shorのアルゴリズムがあれば任意の曲線点の離散対数が求まるので、r = 1（あるいは曲線上の最小の有効なr）に対応する点の秘密鍵が分かる。r_minより5 byte短いrが使えれば、sをグラインドしなくてもOP_SIZEのチェックを通せてしまい、PoWの難易度がゼロになる。

量子コンピューターを想定したスキームの内部に、量子コンピューターで壊れる部品が残っていたと。

QSB

QSBでは↑のPoWパズルを、ハッシュ値がDER形式のECDSA署名に適合するパズルに置き換える。

hash-to-sigパズル

Robin Linus自身が2024年にsha2-ecdsaで指摘していたように↓

ハッシュ関数の出力は、ある確率でそのまま有効なDERエンコードのECDSA署名になる。

つまり、ランダムな入力を変えながらハッシュ計算をしてハッシュ値がたまたまECDSA署名として解釈できる値になるまでグラインドする。

DER形式のECDSA署名の構造は前の記事にも書いたとおり↓

0x30 [全体長] 0x02 [rの長さ] [r] 0x02 [sの長さ] [s] [sighashフラグ]

必要なのは、

先頭バイトが0x30
2バイトめが全体長
整数を表すヘッダーバイト0x02が正しい位置に2回
rの長さ・sの長さが全体長と整合している
rとsが正の整数（先頭バイトのMSB < 128で、不要な先頭の0x00がない）

といった条件。

これを全部同時に満たすランダムなバイト列は当然レアだけど、不可能なほどレアではない。確率は出力が何byteかで変わるので、どのハッシュ関数を使うかの選択になる。20 byte（RIPEMD-160）だと約 ${2^{-46.4}}$ 、32 byte（SHA-256）だと約 ${2^{-45.4}}$ 。32 byteの方が少し高いのは、(rの長さ, sの長さ) の組み合わせが多く取れるから。

なお末尾のsighashフラグバイトは何でもいい。SCRIPT_VERIFY_STRICTENC*4はリレーポリシーであってコンセンサスルールではないので。

これでハッシュの出力がたまたま有効なDER署名になるような入力をグラインドするという新しいPoWパズルができる。難易度は ${2^{46}}$ 前後で固定。そしてこの難易度はハッシュ関数のプリイメージ耐性だけで決まっていて、楕円曲線は一切出てこない。

検証もシンプルで、OP_RIPEMD160してOP_CHECKSIGを評価するだけ。DERとして不正なら署名検証が失敗する。

ハッシュする対象をどうやってトランザクションに縛るか

パズル自体はこれでいいとして、問題は「何をハッシュするか」。トランザクションに縛られていない値をハッシュしても、トランザクションを固定できない。

Bitcoin Scriptからsighashは直接読めないので、QSBが使うのがECDSAの公開鍵の復元。ECDSA署名(r, s)とメッセージハッシュzがあれば、その署名を作った公開鍵Pは

$P = r^{-1}(sR - zG)$

で復元できる。公開値だけの計算なので誰でもできるし、これは安全性の仮定でも何でもない（当然、量子攻撃者にもできる）。

これを使って、トランザクションからsighash zを計算し、zと適当に作成したECDSA署名sig_nonceから公開鍵key_nonceを作る。つまり、sighashそのものをScriptに渡すのではなく、sighashから決まる公開鍵を作ってScriptに渡す。

sig_nonceを固定しておけば、トランザクションが変わってzが変わるたびに、復元されるkey_nonceも変わる。これによって、Scriptから直接読めないsighashを、Scriptのスタックに載せられる33 byteの公開鍵に変換できる。

具体的には、

ロックスクリプトに、SIGHASH_ALL固定の署名sig_nonceをハードコードしておく。sig_nonceはDER形式であればよく、rとsはどんな値でもいい（ただしrについては、secp256k1上の有効なx座標であること）。
支払人はsig_nonceと当該トランザクションのsighash zから key_nonce = Recover(sig_nonce, z) をオフチェーンで計算し、witnessで提供する
ScriptはOP_CHECKSIGVERIFYで(sig_nonce, key_nonce)を検証する

こうすると、sig_nonceの(r, s)は適当に選択した値なので、それとsighash zから復元した公開鍵key_nonceはそのトランザクションでしか成立しない値になる。トランザクションのどこか1 byteでも変えればzが変わり、key_nonceも変わる。つまり、Scriptから読めないsighashを、Scriptのスタック上に載る33 byteの値に変換していることになる。

しかもsig_nonceはロックスクリプトに埋め込むので、sighashフラグはSIGHASH_ALLに固定できる。支払人がANYONECANPAY|NONEを選んでアウトプットへのコミットを外す、というBinohashで指摘されていた攻撃はQSBでは実行できない。

あとはこのkey_nonceをRIPEMD-160してDER署名になっていればいい。

ピンニングスクリプト

ピンニングスクリプトは以下の5つのopcodeで書ける。

// witness: <key_puzzle> <key_nonce>  （key_nonceが上）

<sig_nonce>           // ハードコード、SIGHASH_ALL
OP_OVER               // [1] key_nonceをコピー
OP_CHECKSIGVERIFY     // [2] (sig_nonce＝署名, key_nonce＝公開鍵)を検証
OP_RIPEMD160          // [3] key_nonce -> sig_puzzle
OP_SWAP               // [4] key_puzzleを上に
OP_CHECKSIGVERIFY     // [5] (sig_puzzle＝署名, key_puzzle＝公開鍵)を検証

スタックの遷移を追うと↓（左が先頭）

No	実行処理	実行後のスタック
0	witnessが積まれた状態	`key_nonce key_puzzle`
1	`<sig_nonce>`がプッシュされる	`sig_nonce key_nonce key_puzzle`
2	`OP_OVER`で2番目の要素が複製される	`key_nonce sig_nonce key_nonce key_puzzle`
3	`OP_CHECKSIGVERIFY`が先頭2つを消費。公開鍵＝`key_nonce`、署名＝`sig_nonce`で検証。上述したトランザクションにコミットした公開鍵をスタックに配置するための検証	`key_nonce key_puzzle`
4	`OP_RIPEMD160`で`key_nonce`がハッシュされる	`sig_puzzle key_puzzle`
5	`OP_SWAP`で入れ替え	`key_puzzle sig_puzzle`
6	`OP_CHECKSIGVERIFY`が先頭2つを消費。公開鍵＝`key_puzzle`、署名＝`sig_puzzle`で検証。`key_nonce`のハッシュが正しいDER形式であることの検証。	`（空）`

2つめOP_CHECKSIGVERIFYはDER形式のバリデーターとして振る舞うので、対応する公開鍵key_puzzleは、支払人が(sig_puzzle, z)から公開鍵の復元で求め、witnessに入れる。sig_puzzleがDERとして壊れていると、このOP_CHECKSIGVERIFYが通らない。

ダイジェストラウンド

ダイジェストの作り方はBinohashとほぼ同じ。各ラウンドで、

部分集合の選択とランポート署名の検証：witnessで渡されたt個のインデックスについて、HORSのプリイメージをコミットメントと照合する（ここはBinohashと完全に同一で、1インデックスあたり9 opcode）
パズル署名の導出：key_nonceをOP_DUPしてOP_RIPEMD160
検証：sig_puzzle＋t個のダミー署名＋sig_nonceを(t+2)-of-(t+2)のOP_CHECKMULTISIGで検証

2〜3の前半はピンニングスクリプトの3〜5と同じ仕掛けで、hash-to-sigパズルの判定部分をそのまま使える。違うのはkey_nonceの作られ方で、ピンニングではトランザクション全体のsighashから、ラウンドではsig_nonceがCHECKMULTISIGを通る際のFindAndDelete後のsighashから復元される。ピンニングでパズルを解き直すにはトランザクション自体を変えるしかない。だからトランザクションが固定される。ラウンドの方は、トランザクションを固定したまま部分集合を選び直すだけでパズルの入力が変わる。だから ${2^{42}}$ 通りの探索ができる。

opcodeは、1ラウンドあたり96 opcodeでピンニングの5と合わせて全体では197。

ボーナスキー

署名サイズパズルはOP_SIZEの閾値を変えれば難易度を自由に調整できたけど、hash-to-sigパズルの難易度は ${2^{46.4}}$ に固定されていて、調整する余地がない。

一方でn = 150、t = 8だと ${ {150 \choose 8} \approx 2^{42.3}}$ しかない。パズル目標に対して ${2^{3.7}}$ 足りないので、1つのピンニング済みトランザクションでラウンドが成功する確率は8%程度。2ラウンドとも成功する必要があるから、平均で180回くらいトランザクションを作り直す羽目になる（1回あたり ${2^{46}}$ のグラインド）。

t = 9にすれば ${ {150 \choose 9} \approx 2^{46.2}}$ で目標を超えるけど、署名付き選択を1つ増やすと9 opcode必要で、すでに197 / 201という状況では難しい。

そこで導入されたのがボーナスキー。FindAndDeleteには参加する（＝sighash候補を増やす）けど、HORS検証はスキップする選択のこと。HORSのチェック分（OP_DUP OP_ADD OP_ROLL OP_ROLL OP_HASH160 OP_EQUALVERIFY）が要らないので、3 opcodeで済む↓

// ボーナス選択（3 opcode）
{pos} OP_ROLL     // witnessからインデックスをロール
{n-i} OP_MIN      // サニタイズ
OP_ROLL           // ダミー署名をロール

当然タダではなくて、ボーナスのインデックスは攻撃者が自由に選べるので、その分だけ安全性は下がる。ラウンドあたり ${ {n - t_{signed} \choose t_{bonus}}}$ 倍だけプリイメージのコストが下がる計算。

構成の比較↓

構成	opcode	ダイジェスト	プリイメージ	衝突	グラインド回数
t = 8, 8（ベースライン）	197	84.5 bit	${2^{138}}$	${2^{88}}$	約180回
t = 8+1b, 8	202（超過）	84.5 bit	${2^{131}}$	${2^{85}}$	約13回
t = 8+1b, 7+2b	201	80.4 bit	${2^{118}}$	${2^{78}}$	約1回

推奨は3つめの構成で、201 opcodeにちょうど収まって、グラインドがほぼ1回で済む。プリイメージ耐性を ${2^{138}}$ から ${2^{118}}$ に落とす代わりにオフチェーンコストを激減させるトレードオフ。

制約

いいことばかりではなくて、制約も多い。

レガシースクリプト限定。FindAndDeleteはSegwitで除去されているし、SIGHASH_SINGLEバグもSegwitのsighashアルゴリズムにはない。
bare scriptアウトプットが必要。スクリプトが9,923 byteあってP2SHのredeem scriptの上限（520 byte）に収まらない。
非標準トランザクション。デフォルトのリレーポリシーで伝播しないので、MarathonのSlipstreamみたいなプライベートmempool経由でマイニングプールに直接投げる必要がある。冒頭のトランザクションも、インプット2つのうちアドレスが表示されていない10,000 satsの方がQSBのインプット。bare scriptなのでアドレス表記ができない。

ペーパー自体にも「これは最後の手段として扱われるべき」とはっきり書かれてある。コストもUXも、Bitcoinが想定するユーザー数・金額・スループットにはスケールしないと。

とはいえ、ソフトフォークを待たずにmainnetで実際に動かしてみたのは大きい。

個人的に一番面白かったのは、Scriptから読めないsighashを公開鍵の復元経由でスタック上に乗せる部分。トランザクションのイントロスペクションの手法として、単体で使えそうなトリック。

*1:Tapscriptでは撤廃されてsigopsバジェットに移行

*2:SIGHASH_SINGLEは、自分と同じインデックスのアウトプットのみに署名する署名モード。インプットのインデックスがアウトプットの個数以上だと本来ならエラーになるべきところが、uint256(1)を返す実装になっているバグ。Segwitの導入の際に修正されたもののレガシースクリプトは依然としてこのバグが残ったまま

*3:Binohashではsighashの4モード分すべてのパズルを解く必要があり13 opcodeかかる。Scriptは支払人がどのフラグを使ったか検証できないので、仮にSIGHASH_ALLだけだと攻撃者はSIGHASH_NONEで署名してアウトプットを書き換えられてしまうため

*4:署名のDER形式・sighashフラグの値・公開鍵の形式を厳格にチェックするフラグ。mempoolへの受け入れに使うSTANDARD_SCRIPT_VERIFY_FLAGSには含まれるが、ブロック検証に使うMANDATORY_SCRIPT_VERIFY_FLAGSには含まれない

2026-08-29

LightningでMuSig2を変更せずに閾値署名化する仕組み「Iceberg」

Lightning network Bitcoin Cryptography

ライトニングネットワークではTaprootを用いた新しいチャネルタイプSimple Taproot Channelの導入に向けた開発が進められている。Simple Taproot ChannelではSchnorr署名が使われるため、その線形特性をいかして、参加者を閾値署名グループに置き換えることができるのでは？相手から見れば普通のMuSig2の参加者の1人で、オンチェーンに記録される情報も変わらない。ただできそうに見えて、ライトニング固有の制約がネックになってくる。それを整理して解決策を提案しているのが↓の論文。

eprint.iacr.org

Simple Taproot ChannelとMuSig2

まず前提の確認から。ライトニングチャネルは、ファンディングトランザクションアウトプットを2-of-2でロックし、以後の残高更新をコミットメントトランザクションの署名の交換で行う。新しい状態が作られるたびに直前の状態は失効され、失効済みの状態をブロードキャストするとペナルティで全額を相手に奪われる。このリスクによって両者が最新状態にコミットし続ける、というのが基本構造。

Simple Taproot Channelでは、この2-of-2をMuSig2で実現する。2つのファンディング鍵は1つの集約鍵に統合され、ファンディングアウトプットはその集約鍵のP2TRになる。以降のコミットメントトランザクションも協調閉鎖も、集約鍵に対する単一のSchnorr署名になる。オンチェーンからはシングルシグの支払いと区別がつかず、手数料も小さくなる。

一方で、チャネルの参加者が持っているのは常時オンラインの1本の鍵。オンチェーンのカストディでは2-of-3やt-of-nの閾値署名がよく使われているけど、ライトニングのチャネル端点だけは単一鍵のまま。

この状態で、参加者１人が同様の閾値署名を導入しようとする場合、相手やプロトコルに変更を要求できないのであれば、MuSig2のスキーム内で完結させる必要がある。MuSig2の署名スキームについては以前の記事参照。

単純なアプローチと制約

Schnorr署名なら、t-of-nの閾値署名（FROST系）で単一のSchnorr署名を作れる。であればアリス側の秘密鍵をシェアに分割し、MuSig2の外側から見える「アリスの公開鍵、公開ノンス、部分署名」を、裏でグループが協調して作ればいいというのが単純なアプローチで、方向性としてはこれで合ってる。

ただ以下の制約がネックになる：

メッセージより前にnonceが確定する：revoke_and_ackメッセージに次の状態更新に使用するnext_local_nonces*1を含めているため。
nonceを交換するラウンドに参加するメンバーと、署名ラウンドに参加するメンバーが同一であることが保証されない。そして一度相手方に渡したnonceはそのセッション用に固定され、後から差し替えることができない。
ライトニングでは古い状態への署名は、ペナルティを受けるリスクがあるため、今のチャネル状態についてグループが合意している必要がある。

FROSTのような閾値署名スキームでは、シャミアの秘密分散をベースした検証可能な秘密分散法（VSS）を使用しており、秘密鍵を復元することなく各メンバーがシェアを使って部分署名を計算する。この計算に含まれるラグランジュ係数は署名参加者の集合を考慮して計算されるため、署名者が変わると値も変わる。つまり、各参加者が自分の部分署名を計算するためには、署名者のセットが確定していなければならない。

さらにFROSTで事前共有できるのはnonceのコミットメント（ ${D_i, E_i}$ ）までで、実際のnonceは署名ラウンドで ${\rho_i = H(i, m, nonceコミットメントのリスト)}$ を使って初めて確定する。つまり、メッセージ（ライトニングでは次の状態）が決まる前に外部に渡せるnonceが存在しない。

Iceberg

Icebergは、上記の制約を満たしたままMuSig2の1スロットをt-of-nに置き換える構成。外側（対ボブ）のプロトコルは素のBIP-327のままで、アリスが出す値の作り方だけを差し替える。つまり必要なのは、

公開鍵
公開nonce
部分署名

の３つをグループのメンバーが協調して「単一の署名者が出したのと同じ値」として生成すること。ボブから見ると最初から最後まで通常のMuSig2。

鍵生成

Icebergでは、シャミアの秘密分散ではなく複製型秘密分散（Replicated Secret Sharing）を利用する。

複製型秘密分散では、グループの秘密鍵をサイズt−1の部分集合ごとの加法シェア ${\phi_a}$ に分割する。つまり、

${sk = \sum_a \phi_a}$

で、各シェア ${\phi_a}$ は「部分集合aに属さない」メンバー全員に配布される（同じシェアを複数人が持つので「複製型」）。

(t, n) = (2, 4)、メンバーをA, B, C, Dとした場合で考えると、サイズt - 1 = 1の部分集合は{A}, {B}, {C}, {D}の4つなので、シェアも4つ：

シェア	持つメンバー	持たないメンバー
${\phi_A}$	B, C, D	A
${\phi_B}$	A, C, D	B
${\phi_C}$	A, B, D	C
${\phi_D}$	A, B, C	D

この配り方のポイントは2つ：

任意のt人が集まると全シェアが揃う。どのサイズt−1の部分集合aに対しても、t人の中に必ずaに属さない人がいるため。
t−1人が結託しても、ちょうど「自分たち自身」を添字とするシェア1つだけが欠けるので、秘密について何も分からない。

そして重要なのが、秘密がこの固定された和であること。シャミアベースの方式のように「その場に集まったメンバー」に依存した値が組み立てられるのではなく、誰が参加していようと秘密を構成する要素は同じ。

トレードオフはシェア数で、シェアの総数は「n人からt-1人を選ぶ組み合わせの数＝C(n, t-1)」となり、各メンバーが保持するのはC(n-1, t - 1)個。nが大きくなると組合せ爆発するので大人数のグループには向かないけど、想定ユースケースは1ユーザーの複数デバイスや1社の複数サーバでnはせいぜい十数であれば実用上は問題ない。実測でも長期保持するシェア材料は(2,4)で約100 byte、(3,7)で約484 byte、(4,10)で約2,692 byte。

シェアの配布方法自体は、信頼できるディーラーが配ってもいいし、分散鍵生成（DKG）でもいい（論文はどちらも許容している）。

このシェア ${\phi_a}$ はそのまま秘密鍵の断片として使われるのではなく、PRF（擬似ランダム関数）の鍵として使われる。グループの署名鍵は、鍵用に予約された固定タグ ${w_0}$ でPRFを評価した値の和

${x = \sum_a H_{prf}(\phi_a, w_0)}$

として定義される。そして対応する公開鍵 ${P = xG}$ がMuSig2の鍵集約に渡されるアリスの公開鍵になる。

ただし、この和を計算すると秘密鍵が判明してしまうので実際にこの計算をすることはない。この和を計算することなく公開鍵を計算するのに使われるのがシェアの変換。

シェアの変換

Icebergの各ラウンドで使われているのが、複製シェアをローカルで（通信なしで）シャミアのシェアへ変換する操作。以降、メンバーA〜Dには番号1〜4を振り、この番号がシャミア多項式の評価点を兼ねるものとする。j、kはいずれもメンバー番号で、kは計算している本人。

任意の公開タグwに対して、メンバーkは

${d_k = \sum_{a \in A_k} H_{prf}(\phi_a, w) \cdot L'_a(k)}$

を計算する。 ${A_k}$ はkが持つシェアに対応する部分集合aのセット、 ${L'_a(k) = \prod_{j \in a} (j - k)/j}$ はメンバーや署名参加メンバーに依存しない固定の係数で、事前計算できる。

この ${d_k}$ が、値 ${d = \sum_a H_{prf}(\phi_a, w)}$ （和は全シェアにわたる）のシャミアシェアになる。多項式

${f(Z) = \sum_a H_{prf}(\phi_a, w) \cdot L'_a(Z)}$

に対して、 ${L'_a(0) = 1}$ なので ${f(0) = d}$ 。つまりfは「Z=0に秘密を埋め込んだt−1次の多項式」で、 ${d_k = f(k)}$ はその上の点、すなわちシャミアのシェアそのもの。そして ${f(k)}$ を計算するとき、kが持っていないシェア（＝kを含む部分集合aのシェア）の項は、係数の因子に(k − k) = 0が含まれるため勝手に消える。だから全シェアの和として定義された値のシャミアシェアを、手持ちのシェアだけで計算できる。

(2, 4)のメンバーA（持っているのは ${\phi_B, \phi_C, \phi_D}$ ）で具体的に計算すると、

${d_A = \frac{1}{2} H_{prf}(\phi_B, w) + \frac{2}{3} H_{prf}(\phi_C, w) + \frac{3}{4} H_{prf}(\phi_D, w)}$

となり、持っていない ${\phi_A}$ の項は係数(1−1)/1 = 0で消えている。B, C, Dも同様に計算すると、4人の ${d_k}$ はすべて同じ多項式f上の点になり、任意のt人分をZ=0に向かってラグランジュ補間すればdが得られる。

鍵生成では ${w = w_0}$ として、各メンバーが鍵シェアの公開値 ${P_k = d_k G}$ を共有し、検証の上、補間でグループ公開鍵 ${P = dG}$ が得られる。この ${d = \sum_a H_{prf}(\phi_a, w_0)}$ がグループの秘密鍵になるけど、どこにも現れない。

なお検証には2t−1個のシェアが要る。汚染がt−1人なら、2t−1個の中に必ずt個の正直なシェアが含まれ、そのt個の点が多項式を一意に決めるので、多項式に載らない偽のシェアを検出できる。

nonceの導出（PreRound）

FROSTがネックになったのは、nonceが「各署名者がその場で選択した乱数」から作られるためだった。乱数は本人しか知らないので、その人が署名ラウンドで不在だと誰も代わりにnonceを完成できないし、メンバーが変わればnonceの値自体が変わってしまう。

Icebergはnonceを乱数ではなく、全員が共有しているシェアから決定論的に導出する。タグ ${w = i || sid}$ で上記のシェアの変換を行う（iはnonceのスロット番号*2）。

各メンバーkは、値 ${r_i = \sum_a H_{prf}(\phi_a, i || sid)}$ のシャミアシェア ${r_{i,k}}$ をローカルで計算し、公開値 ${R_{i,k} = r_{i,k} G}$ をブロードキャストする。アグリゲーターは、シェアを検証してラグランジュ補間し、グループのnonce ${R_A}$ を得る。これがBIP-327のpubnonce（66 byte）としてそのままボブに渡る。

「結局ラグランジュ補間を使うの？」と思ったけど、FROSTとの違いは補間の有無ではなく、補間される多項式が固定されているかどうか。FROSTでは署名のたびに各メンバーのフレッシュな乱数が多項式そのものを作るので、参加メンバーが変われば別の多項式＝別の値になる。Icebergでは多項式がシェアとsidから決定論的に決まっているので、どの参加者がどの点を持ち寄っても、補間の結果は同じ値になる。だから、

メッセージを知らなくてもnonceを確定できる（sidさえ決まっていればいい）
どの参加者が計算しても同じ ${R_A}$ になる
第1ラウンドに不在だったメンバーも、後から自分のシェアだけで同じnonceシェアを再計算できる

という、FROSTでネックだった3点がすべて解消される。

そしてsidの値が、この構成をライトニングと接続する鍵になる。sidにはコミットメントトランザクションのコミットメント番号が含まれる。この番号はチャネルの生存期間を通じて一意かつ単調増加で、しかも次のコミットメントトランザクションが組み上がる前から分かっている。だからrevoke_and_ackで次の状態のnonceを先渡しするタイミングでも問題なく導出できる。

決定論的なnonce導出で大丈夫なのか？

単一の署名者であれば、RFC 6979のような決定論的なnonceの導出は推奨されるけど、MuSig2のようなマルチパーティでの署名では話が変わる。チャレンジに含まれる集約nonce Rには他の署名者の値が混ざるため、悪意ある共同署名者が同じメッセージでセッションを張り直して自分のnonceだけ変えれば、こちらのnonceは同じまま異なるチャレンジに署名させられてしまい、秘密鍵の逆算が可能になる。

Icebergでは、「一度しか使われないことをライトニング自身が保証している値」＝コミットメント番号をシードにすることで状態が変わればnonceも必ず変わるようにしている。ライトニングが元々やっている厳格な状態管理を、決定的nonceの安全性の前提として利用する形になる。

ただし「同じコミットメント番号の下で2つの異なるトランザクションに署名させられたら」というケースは、nonce導出の仕組みだけでは防げない。ここで防波堤になるのが3つ目の制約、グループによる現在状態への合意だ。正直なメンバーは1つのsidに対して一度しか署名しない。そしてt−1人の欠陥メンバーを含んだ状態で合意を取るのはビザンチン合意なので、正直なメンバーの厳格な過半数が必要になり、ここからグループサイズの条件n ≥ 3t−2が出てくる。古い状態への署名がペナルティに直結する以上、この合意は閾値化するならどのみち必要なもので、決定的nonceの安全性がそこに相乗りできる形になっている。

署名（SignRound）

メッセージm（コミットメントトランザクション）とボブのnonceが届いたら、各メンバーは自分の鍵シェアとnonceシェアをPRFで再導出し（第1ラウンドに不在だったメンバーもここで初めて計算すればいい）、部分署名

${s_k = r_{1,k} + r_{2,k}\check{b} + c \cdot a \cdot x_k}$

を返す。 ${\check{b}}$ は内側・外側2つのバインディング係数の積、cはチャレンジ、aはグループ鍵に対するMuSig2の鍵集約係数。アグリゲーターが署名参加者のラグランジュ係数で補間するとグループの部分署名 ${s_A}$ が得られ、外側で ${s_A + s_B}$ が最終的なSchnorr署名になる。

プロトコルは2ラウンドで、第1ラウンドはメッセージ確定前に先行実行できる。これはMuSig2自身と同じラウンド構造なので、グループ化してもチャネルプロトコルにラウンドは増えない。

パラメータの読み方

Icebergのしきい値は少し独特な読み方が必要になる：

t	耐えられる汚染	署名クォーラム	最小のn
2	1	3	4
3	2	5	7
4	3	7	10
5	4	9	13

「t人集まれば署名できる」ではない点に注意。tはあくまで「t−1人までの鍵の汚染に耐える」というパラメータで、署名には2t−1人のオンラインが必要（シェア検証のため）、グループはn ≥ 3t−2（状態合意のビザンチン境界のため）。例えばt=3, n=7は「3-of-7」ではなく、「2人まで落ちてもいい、5人で署名するグループ」と読むのが正しい。全員をコールドストレージに置けるわけではなく、守られるのは「チャネル資金を単独で握るホット鍵をなくす」こと。

まとめ

論文では実際にeclairに組み込んだプロトタイプで、チャネルロジックに手を入れずに動作すること、スループットへの影響も(2,4)構成で7%程度に収まることが確認されている。

Icebergの構成を一言でまとめると、「複製型秘密分散のシェアをPRF鍵として、チャネルのコミットメント番号から決定的にnonceを導出する」ことで、ライトニングが課す制約（nonceがメッセージに先行する、メンバーが入れ替わる、状態合意が必要）を同時に解いている。面白いのは、決定的nonceの安全性の前提（同じシードで2回署名しない）を、ライトニングが元々持っている状態管理にそのまま委ねている点で、プロトコルの制約を逆に資源として使う設計になっている。

相手にもプロトコルにもチェーンにも変更を要求せず、片側だけで導入できるという性質は実運用上大きい。シェアのリフレッシュや紛失シェアの修復、メンバー構成の変更（いずれもファンディングアウトプットの集約鍵を維持したまま）は今後の課題として挙げられている。

*1:https://github.com/lightning/bolts/blob/master/bolt-simple-taproot.md#revoke_and_ack-extensions

*2:MuSig2（BIP-327）ではPublic nonceとして2つの点を送るため、それを識別するための番号

2026-08-22

GF(2) R1CSのための二進体タワーをRubyで実装してみる

Ruby Cryptography

前回はR1CSを扱い、最後にGF(2)上では「制約1本 = ANDゲート1個、XORはタダ」になるところまで見た。ただしあれは制約の書き方の話で、証明系ではない。

今回はその先、GF(2)上のR1CSの充足性を実際に検査する側に進む。最初に立ちはだかるのは、体を小さくしたことの代償で、その解決に二進体のタワーを用いる。今回はそこまでをRubyで書いてみた。

GF(2)には元が2つしかない

多くの算術系の証明系では、「多項式の等式が成り立つ」ことを示す形に問題を変換する。ただし全部の点で確かめると点の数に比例する手間がかかるので、ランダムな1点だけ確かめて済ませる。これが成立するのは、2つの多項式が違えばその差は0でない多項式であり、0でない多項式の根の個数は次数以下しかないから。体の元がたくさんあれば、ランダムに選んだ点がたまたま根に当たる確率は小さい。次数 ${d}$ の多項式が大きさ ${|S|}$ の集合からランダムに取った点で0になる確率は高々 ${d / |S|}$ （Schwartz-Zippelの補題）。

問題は ${\mathbb{F}_2}$ だと元が2つしかないこと。これでは「たまたま根に当たる確率が小さい」という前提が成立しない。実際、 ${f(x) = x^{2} + x = x(x+1)}$ は0でも1でも0になる。

解決策は単純で、以前のBabyStarkの記事でもやったようにwitnessは ${\mathbb{F}_2}$ に置いたまま、チャレンジだけ大きな体から取る。ここで小さいのが問題になるのはチャレンジ空間であって、witnessではない。witnessはGF(2)のままでも、GF(2)係数の多項式を拡大体上の多項式として評価することができる。チャレンジを拡大体から選ぶことで、ランダム評価の健全性を確保できる。 ${\mathbb{F}_{2^{128}}}$ からチャレンジを取れば、次数 ${d}$ の多項式を見逃す確率は ${d/2^{128}}$ 。sumcheckなどではdは小さいので実質的に ${2^{-128}}$ のオーダーになる。

そのためには ${\mathbb{F}_2}$ の拡大体が要る。そして拡大体の作り方として二進体で使われるのがタワー構成。

二進体のタワー

たとえば、 ${\mathbb{F}_{2^{16}}}$ を作る場合。元の個数は65536個。16ビットの整数がちょうど65536通りなので、16ビット整数を「体の元のビット表現」として使える。

元どうしの演算のうち、足し算は簡単。標数2の体で加算はXORなので、0xBEEF + 0xCAFEは0xBEEF ^ 0xCAFE。問題は掛け算の方で、0xBEEF × 0xCAFEを整数として計算すると65536を軽く超えて体の外に出てしまう。そこで結果が65536個の元の中に収まるような掛け算の規則を、別に決める必要がある。

掛け算の規則を決める

この規則を決めるために使われるのが既約多項式（それ以上因数分解できない多項式）。

16ビットの整数を「0か1の係数が16個並んだ多項式」とみなす。たとえば 0b1011 なら ${x^{3} + x + 1}$ 。多項式どうしは普通に掛け算できるけど、掛けると次数が上がってしまうので、選んでおいた16次の既約多項式で割って余りを取るようにする。すると、次数が15以下に戻り、また16ビットに収まる。整数の剰余計算と同じ発想で、既約多項式が法の役割をしている。

どういった既約多項式を選ぶかは自由で、選んだ多項式が変われば0xBEEF × 0xCAFEの結果も変わる。体としてはどれを選んでも同じもの（同型）になるので数学的な優劣はないけど、実装のしやすさは変わる。

2次拡大を積み重ねる

↑のような16次の既約多項式を1つ選ぶ方式だと、元は「係数が16個並んだ多項式」になるけど、二進体では拡大体を作るにあたって2次拡大を何段も積み重ねる構成が使われる。元の表し方も変わり、係数を16個並べるのではなく「1つ下の段の元を2つ組にする」という入れ子で表す。

${\mathbb{F}_2 \to \mathbb{F}_{2^{2}} \to \mathbb{F}_{2^{4}} \to \mathbb{F}_{2^{8}} \to \mathbb{F}_{2^{16}}}$

元の表現が1ビット → 2ビット → 4ビット → 8ビット → 16ビット。各段で、1つ下の段の元を2つ組み合わせて上の段の元を作る。塔のように段を積むのでタワー構成と呼ばれている。ここでは、各段を ${T_0, T_1, \ldots, T_4}$ と書くことにする。 ${T_k}$ の元は ${2^{k}}$ ビットで、この記事で使うのは ${T_4 = \mathbb{F}_{2^{16}}}$ 。実際の利用では、 ${T_7 = \mathbb{F}_{2^{128}}}$ を取るけど、読みやすいようこの記事では ${T_4 = \mathbb{F}_{2^{16}}}$ を使用する。

なかでもよく使われるWiedemannの構成では、 ${T_k}$ への拡大に

k = 1の場合は、 ${X_0^{2} + X_0 + 1}$
k ≧ 2の場合は、 ${X_{k-1}^{2} + X_{k-2} X_{k-1} + 1}$

という2次既約多項式を使う。各段は2次拡大なので、必要な既約多項式も2次式1本で済む。

${T_k}$ の元は、上位半分と下位半分がそれぞれ ${T_{k-1}}$ の元になっていて、

${a = a_{hi} X_{k-1} + a_{lo}}$

と分解できる。2つの元を掛けて展開すると ${X^{2}}$ の項が出てくるので、 ${X^{2} = X X_{k-2} + 1}$ で還元して1次に戻す。これをRubyで書くと、

module Tower
  module_function

  # T_k の元 +a+ と +b+ の積を返す。
  # @param a [Integer] T_k の元（2^k ビットに収まる非負整数）
  # @param b [Integer] T_k の元
  # @param k [Integer] タワーの段。T_k = F_{2^(2^k)} を表す
  # @return [Integer] 積。T_k の元
  # @example F_{2^16}（4段）の乗算
  #   Tower.mul(0xBEEF, 0xCAFE, 4) # => 0xB8D3
  def mul(a, b, k)
    return a & b if k == 0 # F_2 の乗算は AND

    half = 1 << (k - 1)  # T_{k-1} のビット数
    mask = (1 << half) - 1
    a_lo, a_hi = a & mask, a >> half
    b_lo, b_hi = b & mask, b >> half

    lo_lo = mul(a_lo, b_lo, k - 1)
    hi_hi = mul(a_hi, b_hi, k - 1)
    cross = mul(a_lo ^ a_hi, b_lo ^ b_hi, k - 1) ^ lo_lo ^ hi_hi # カラツバ法

    gen = k == 1 ? 1 : (1 << (1 << (k - 2)))  # X_{k-2}
    hi = cross ^ mul(hi_hi, gen, k - 1) # X^2 = X*X_{k-2} + 1 で還元
    lo = lo_lo ^ hi_hi

    (hi << half) | lo
  end
end

標数2なので加算はどの段でも単なるXORで済む。

一番下の段まで降りると乗算はa & b、つまりビット単位のANDになる。

mul(a, b, 4)
  └─ mul(..., 3)
       └─ mul(..., 2)
            └─ mul(..., 1)
                 └─ mul(..., 0) → a & b ←ここ

前回の「GF(2)では乗算 = AND」が、ここで実際の演算として現れる（実際には各段でmulを4回呼ぶので、末端のANDは1個ではなく多数になる）。

体になっていることを確かめるには逆元が要るので、冪と合わせて用意しておく。逆元は、乗法群の位数が ${2^{2^{k}} - 1}$ なので ${a^{2^{2^{k}} - 2}}$ で求まる。

module Tower
  module_function

  # 繰り返し二乗法で T_k の元 +a+ の +e+ 乗を返す。
  def pow(a, e, k)
    r, b = 1, a
    while e > 0
      r = mul(r, b, k) if e.odd?
      b = mul(b, b, k)
      e >>= 1
    end
    r
  end

  # T_k の非ゼロ元 +a+ の乗法逆元を返す。
  def inv(a, k) = pow(a, (1 << (1 << k)) - 2, k)
end

実際に動かしてみよう。まず ${T_1 = \mathbb{F}_{2^{2}}}$ の体のすべての元の組み合わせについて乗算表を出してみる。

(0...4).each { |a| puts (0...4).map { |b| Tower.mul(a, b, 1) }.join(" ") }

2の冪乗が2→3→1 と巡回していて、位数3の乗法群になっているのが分かる。0以外の3つの元がちゃんと群をなしている。

乗法の結合則・分配則・逆元を総当たりで確認してみる（ ${T_2 = \mathbb{F}_{2^{4}}}$ の16元で）。

els = (0...16).to_a
k = 2

# 結合則
els.product(els, els).all? { |a, b, c|
  Tower.mul(Tower.mul(a, b, k), c, k) == Tower.mul(a, Tower.mul(b, c, k), k)
} # => true

# 分配則
els.product(els, els).all? { |a, b, c|
  Tower.mul(a, b ^ c, k) == (Tower.mul(a, b, k) ^ Tower.mul(a, c, k))
} # => true

# 逆元
els.drop(1).all? { |a| Tower.mul(a, Tower.inv(a, k), k) == 1 } # => true

${T_4 = \mathbb{F}_{2^{16}}}$ も同様に動く。

ab = Tower.mul(0xBEEF, 0xCAFE, 4)      # => 0xB8D3
Tower.mul(ab, Tower.inv(0xCAFE, 4), 4) # => 0xBEEF

タワーのメリット

タワーで作ると、下の段の元が上の段のビット列にそのまま入る。

${T_4}$ の元0xBEEFは、上位の0xBEと下位の0xEFに分ければ、それぞれが ${T_3}$ の元になっている。逆に ${T_3}$ の元 0xEF を ${T_4}$ の元として扱いたければ、上位を0埋めして0x00EFとするだけ。整数としては同じ値なので、変換という作業が存在しない。

このタワーで一番効果があるのがこれ。

Tower.mul(a, b, 2) == Tower.mul(a, b, 3)   # a, b < 16 なら true
Tower.mul(a, b, 3) == Tower.mul(a, b, 4)   # a, b < 256 なら true

下の段に属する元同士なら、どの段で掛けても同じ答えを返す。 ${T_2 \subset T_3 \subset T_4}$ という包含が、ビット列の表現としてそのまま実現されている。通常の有限体の拡大だと元の表現を変換する必要があるけど、ここでは変換が発生しない。

特に ${\mathbb{F}_2}$ の元、つまり0と1については

${0 \cdot b = 0, \quad 1 \cdot b = b}$

なので、 ${\mathbb{F}_2}$ の元と拡大体の元の積は「選ぶだけ」になる。乗算をする必要もない。

# 0 と 1 については、どんな相手でも計算が要らない
(0...(1 << 16)).step(97).all? { |x|
  Tower.mul(0, x, 4) == 0 && Tower.mul(1, x, 4) == x
} # => true

「witnessは ${\mathbb{F}_2}$ 、チャレンジは ${\mathbb{F}_{2^{16}}}$ 」という構成を効率よく実装できるのは、GF(2)が拡大体の部分体として自然に埋め込まれ、さらにGF(2)の元との積が「選ぶだけ」で済むから。

まとめ

${\mathbb{F}_2}$ は元が2つしかないので、チャレンジをそこから取るとランダム評価による十分な健全性を確保できない。witnessは ${\mathbb{F}_2}$ のまま、チャレンジだけ拡大体から取る
拡大体を作るには掛け算の規則、つまり既約多項式を選ぶ必要がある。選び方は自由だが実装のしやすさが変わる
二進体では2次拡大を積み重ねるタワー構成を使う。Wiedemannの構成なら各段で同じ形の2次既約多項式を使える
タワーの効果は部分体の埋め込みがタダなこと。下の段の元が上の段のビット列にそのまま入り、変換が要らない
結果として小さい体との積が安くなり、witnessとチャレンジで体を使い分けられる

次回は、このタワーの上でsumcheckを動かす。GF(2) R1CSの充足性を「全部の制約が0」から「重み付き総和が0」に変換し、それを1点での評価まで縮める。witnessが ${\mathbb{F}_2}$ であることが実際にどこで効くのかを、ラウンドごとの乗算を数えて確かめる。