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

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

で実際に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には含まれない

Develop with pleasure!

福岡でCloudとかBlockchainとか。