Develop with pleasure!

福岡でCloudとかBlockchainとか。

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.00.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形式の長さのプレフィックスをつける

ソフトフォークなしで量子安全なトランザクションを作る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に量子耐性を持たせる提案自体は前からあって、このブログでも何回か取り上げてる↓

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は

{\displaystyle 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の公開鍵に変換できる。

具体的には、

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

  1. 部分集合の選択とランポート署名の検証：witnessで渡されたt個のインデックスについて、HORSのプリイメージをコミットメントと照合する（ここはBinohashと完全に同一で、1インデックスあたり9 opcode）
  2. パズル署名の導出：key_nonceをOP_DUPしてOP_RIPEMD160
  3. 検証：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には含まれない

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つの点を送るため、それを識別するための番号

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(" ") }

0 0 0 0
0 1 2 3
0 2 3 1
0 3 1 2

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}であることが実際にどこで効くのかを、ラウンドごとの乗算を数えて確かめる。

R1CSをRubyで実装してみる

Cryptography zk Ruby

ゼロ知識証明の解説では「計算を回路にする」「制約系に落とす」という表現がよく出てくるけど、その最も古典的で、いまだに現役の形式がR1CS (Rank-1 Constraint System) 。Groth16、Spartan、そして最近発表された Flock など、異なる証明系の内部でもR1CSは制約表現として使われている。

前回はSTARK/zkVMをRubyで実装したけど、あちらの制約表現はAIRだった。今回は同じ計算をR1CSで書き、両者の違いを見る。そしてGF(2)上のR1CSについても。

R1CSとは

R1CSは、次の形をした制約の集まりで計算を表現する。

{\langle \mathbf{a}_{k}, \mathbf{z} \rangle \cdot \langle \mathbf{b}_k, \mathbf{z} \rangle = \langle \mathbf{c}_k, \mathbf{z} \rangle \qquad (k = 1, \ldots, m)}

  • {\mathbf{z}} は長さnのwitnessベクトルで、公開値も秘密値も全部ここに並ぶ。
  • {\mathbf{a}_k, \mathbf{b}_k, \mathbf{c}_k} は回路が定める係数ベクトル。
  • {\langle \cdot, \cdot \rangle} は内積。 {\langle \mathbf{a}_k, \mathbf{z} \rangle}は {\mathbf{z}}の成分を係数 {\mathbf{a}_k}で足し合わせたもの、つまり {\mathbf{z}}の線形結合になる。

この制約は、「zの線形結合ひとつと、別の線形結合ひとつを掛けたら、3つ目の線形結合に等しくなる」という意味になる。掛け算がちょうど左辺に1回しか現れないのがポイントで、各制約は「線形形式 × 線形形式」というrank-1型の積に制限されている。"Rank-1"はこの構造に由来する。

行列でまとめると、 {A, B, C \in \mathbb{F}^{m \times n}} を係数ベクトルを行に並べた行列として

{(A\mathbf{z}) \circ (B\mathbf{z}) = (C\mathbf{z})}

（ {\circ} は要素ごとの積 = アダマール積）。R1CSの説明でよく見るこの式は、上の内積形式をm本まとめて書いたもの。

慣習: {z_0 = 1}

{\mathbf{z}}の先頭は定数1とするのが慣習で、 {\mathbf{z}_0 = 1}。そうすることで、線形結合の中で定数項を表現できる。たとえば、xをインデックス1の変数として {\mathbf{z} = \lbrack 1, x, ... \rbrack}と並べた場合、 {\langle \mathbf{a}, \mathbf{z} \rangle = 3x + 5}となる係数ベクトルは、 {\mathbf{a} = \lbrack 5, 3, 0, ... \rbrack}。

この先頭の1は、掛け算を伴わない制約を書くのにも使える。 {\mathbf{b}}としてインデックス0のみが1で、残りは0のベクトル（ {\mathbf{b} = \lbrack 1, 0, 0, ... \rbrack}）を使えば、 {\langle \mathbf{b}, \mathbf{z} \rangle = 1}となり、この場合、 {\langle \mathbf{a}, \mathbf{z} \rangle \cdot \langle \mathbf{b}, \mathbf{z} \rangle = \langle \mathbf{c}, \mathbf{z} \rangle}は、{\langle \mathbf{a}, \mathbf{z} \rangle = \langle \mathbf{c}, \mathbf{z} \rangle}と掛け算のない線形制約になる。

R1CSのコスト

R1CSでコストを数えるときの原則は1つだけ。

制約の本数 = 平坦化した回路の乗算数でほぼ決まる。加算とスカラー倍はタダ。（厳密にはwitnessの長さnもコストになる）

加算や定数倍は係数ベクトルの中に吸収されるので、制約本数は増えない。 {7a + 3b - c + 42} のような式がいくら複雑でも、それは1つの線形結合であって制約1本の一部分にしかならない。

この「加算がタダ、乗算が有料」という非対称性が、R1CSでの回路設計のすべてを決める。そして後述するように、GF(2)上ではこれがXORがタダ、ANDが有料という都合のよい形になる。

例: フィボナッチ平方数列をR1CSにする

実際に任意の計算をR1CSにコンパイルするツールはいろいろ公開されているけど、ここでは前回のBabyStarkと同じフィボナッチ平方数列の題材を使って、実際に計算をR1CSにしてみよう。

フィボナッチ平方数列の計算式： {a_{n+2} = a_{n+1}^{2} + a_n^{2}}

{a_0 = 1} は公開、 {a_1 = w} は証明者だけが知るwitness、数ステップ回した後の値が公開出力。「この出力になる {a_1} を知っている」ことを証明したい。

平坦化

R1CSは掛け算1回しか書けないので、まず式を分解する必要がある。ステップnで新しい変数 {t_n} を導入して、

  • {t_n = a_n \cdot a_n}
  • {a_{n+1} \cdot a_{n+1} = a_{n+2} - t_n}

の2本にする。2本目の右辺 {a_{n+2} - t_n} は線形結合なので、そのまま {C} 行に書ける。足し算のために制約を1本使う必要はない。

というわけでこの平坦化方法では1ステップあたり制約2本、補助変数1個が必要になる。

変数の割り当て

4ステップ（ {a_2} から {a_5} まで生成）だと、 {\mathbf{z}}のインデックスの割当は、

インデックス 内容
0 定数 1
1 out（公開出力）
2–7 {a_0, \ldots, a_5}
8–11 {t_0, \ldots, t_3}

変数12個。制約は、各ステップ2本 × 4 = 8本に、入力の固定 {a_0 = 1} と出力の紐付け {a_5 = \text{out}} を足して計10本。

Rubyで書くと

体はBabyStark と同じBabyBear {p = 2^{31} - 2^{27} + 1} を使う。係数ベクトルはベクトルの成分がほとんど0なのでHashで管理する。

P = 2013265921  # BabyBear
N = 4           # ステップ数
A0 = 2          # a_n の開始インデックス
T0 = 8          # t_n の開始インデックス

# 制約: [A, B, C] の3つ組。各要素は Hash{変数 => 係数}
def build_constraints
  cs = []
  cs << [{A0 => 1}, {0 => 1}, {0 => 1}]              # a_0 * 1 = 1
  N.times do |n|
    # a_n * a_n = t_n
    cs << [{A0 + n => 1}, {A0 + n => 1}, {T0 + n => 1}]
    # a_{n+1} * a_{n+1} = a_{n+2} - t_n
    cs << [{A0 + n + 1 => 1}, {A0 + n + 1 => 1},
           {A0 + n + 2 => 1, T0 + n => P - 1}]
  end
  cs << [{A0 + N + 1 => 1}, {0 => 1}, {1 => 1}]      # a_5 * 1 = out
  cs
end

{-1} を P - 1 と書いているのは、体の元を0以上p未満の整数で表しているため。

witnessの生成は、ただ計算を実行して途中の値を全部記録するだけ。

def build_witness(w)
  a = [1, w]
  N.times { |n| a << (a[n + 1]**2 + a[n]**2) % P }
  t = (0...N).map { |n| a[n]**2 % P }
  [[1, a[N + 1]] + a + t, a[N + 1]]
end

充足判定は定義通り。

def dot(vec, z)
  vec.sum { |i, coeff| coeff * z[i] } % P
end

def satisfied?(constraints, z)
  constraints.all? { |a, b, c| dot(a, z) * dot(b, z) % P == dot(c, z) }
end

動かすと、

z, out = build_witness(3)
cs = build_constraints

p z    # => [1, 143556242, 1, 3, 10, 109, 11981, 143556242, 1, 9, 100, 11881]
p out  # => 143556242
p satisfied?(cs, z)   # => true

# a_1 を改竄すると落ちる
bad = z.dup; bad[3] = 4
p satisfied?(cs, bad) # => false

{a_1 = 3} のとき数列は 1, 3, 10, 109, 11981, 143556242 となり、witnessベクトルにこの全部と補助変数 {t_n = 1, 9, 100, 11881} が並んでいるのが見える。

R1CSのwitnessは「計算を平坦化した際に必要になる入力・中間値、出力を1本のベクトルに並べたもの」で、制約はそのベクトルの整合性チェックリストにすぎない。

AIRとの比較

同じ数列を前回のBabyStarkでAIRで書いたケースと比較すると、

AIR R1CS
形式 実行トレース（行=時刻, 列=レジスタ） 平坦なwitnessベクトル
制約 隣接2行に一様に課す遷移制約 各制約が独立、形はバラバラ
記述量 行数によらず一定（数式数本） 制約数に比例（ {O(m)}）
次数 任意（実装依存だが2より上も可） 2に固定
データの移動 i行目とi+1行目の間のみ 任意（どの変数も参照可）

一番大きな違いは記述量。AIRは {f(g^{2} x) - f(gx)^{2} - f(x)^{2} = 0} という数式1本で1023ステップ全部を表現できた。 フィボナッチ平方数列の場合、どのステップでも同じ形が成り立つから*1。R1CSには同じ制約の繰り返しを1本にまとめる仕組みがないため、制約を {m} 本すべて書き下す必要がある。

このまま単純に扱えばインスタンスサイズは O(m) になる。SNARK/IOP側では、これをそのまま検証者に読ませるのではなく、Trusted Setup、疎行列コミットメント、sumcheck、多項式コミットメントなどを使って、巨大な制約系をsuccinctに扱う手当をしている。

一方でR1CSのメリットは、「どの変数の値をどの制約から参照できるか」の自由度。AIRの制約はトレース上の固定された局所的な範囲しか参照できないので、必要に応じて置換引数やlookupなどの別の仕組みを組み合わせる必要がある。R1CSにはこの隣接制限がなく、どの変数でも自由に参照できる。

R1CSの限界

次数2の壁

R1CSは1つの制約で行える掛け算は1回のみ。したがってR1CSの1本の制約が直接表現できる多項式の次数は2まで。 {x^{4}} を書くには {y = x^{2}, x^{4} = y^{2}} と2本に分割する必要がある。

このような課題を解消するために、Plonkishではセレクターやカスタムゲートによって、1行により複雑な多項式制約を持たせられるようにしている。逆に言うとR1CSの単純さは、次数を上げられない代わりにプロトコルが極めてシンプルになる、というトレードオフになる。

ちなみにR1CS、Plonkish、AIRの3つは、同じ一般形の特殊ケースであることがCCS（Customizable constraint systems）の論文で示されている。

掛け算1回という粒度のギャップ

比較、範囲チェック、ビット分解といった操作はR1CSではコストが高い。例えば「 {x} が32bitに収まる」ことを示す場合。素体 {\mathbb F_p}の元は0〜p-1の整数で、大小比較や「上位ビットが0か」を直接問う手段がない。体の演算は加減乗除だけなので、不等式を書く語彙がない（剰余の結果巡回するから）。そのため、32bitの分解を証明者に提示させるという手段が必要になる。

  1. 証明者が {b_0, ..., b_{31}}をwitnessに追加し、
  2. 各 {b_i}が0か1であることを制約する（ {b_i \cdot b_i = b_i}、Booleanity constraintと呼ぶ）。32本の制約
  3. それらがxを復元することを制約する（ {x = \sum 2^{i}b_i}）。1本の制約

lookupが使える証明系ならテーブル1回引くだけで済む話に、33本の制約を払うことになる。

素体上のR1CSでハッシュ関数を書くのが辛いのは、まさにこれが理由。

GF(2)上のR1CS

ここで体を {GF(2) (=\mathbb{F}_2)} にすると、状況が変わる。

標数2の体では、

  • 加算 = XOR（ {1 + 1 = 0}）
  • 乗算 = AND

なので、先ほどの「制約の本数は乗算数でほぼ決まる」という原則が、GF(2)上では

制約の本数 = ANDゲートの個数、XORはタダ

になる。R1CSの1本の制約は、XORの線形結合同士のANDゲート1個に対応する。ビットが体の元そのものなので、ビット分解もBooleanity constraintも要らない。

PlonkishやAIRなどのより柔軟な形式が提案されたにも関わらず、GF(2)のような次数を上げる必要が薄い文脈では、R1CSのシンプルさがむしろ強みになる。Flockが2026年になってR1CSを選んでいるのはそのため。

例: SHA-256の多数決関数

SHA-256の多数決関数

{\mathrm{Maj}(a,b,c) = (a \land b) \oplus (a \land c) \oplus (b \land c)}

はANDが3つ、XORが2つ。つまりR1CSの制約は3本になる。しかし、これは

 {\mathrm{Maj}(a,b,c) = ((a \oplus b) \land (b \oplus c)) \oplus b}

と書き換えることができ、この場合XORは1つ増えるが、ANDは1個になる。XORはタダなので、これで制約は1本で済む。

この恒等式は、 {(a \oplus b) \land (b \oplus c) = \mathrm{Maj} \oplus b}と移項でき、「線形結合 × 線形結合 = 線形結合」の形なので、R1CS制約1本にそのまま収まる。

A = {a: 1, b: 1} # a + b (= a XOR b)
B = {b: 1, c: 1} # b + c
C = {Maj: 1, b: 1} # Maj + b (= Maj XOR b、標数2では -b = b なので移項しても符号は変わらない)

選択関数のほうも同様に、

{\mathrm{Ch}(e,f,g) = (e \land f) \oplus (\lnot e \land g) = g \oplus (e \land (f \oplus g))}

と書けるのでANDが1個になる。

こういう書き換えを探すのが GF(2) 回路設計の主な作業で、AND数を最小化する問題（Multiplicative Complexity）として研究されている。

ハッシュ関数との相性の良さ

標準ハッシュはビット単位のXOR・ローテート・シフトと、少数の非線形演算でできている。ローテートやシフトは変数の並べ替えにすぎないのでタダ。つまり制約本数はANDゲート数だけで決まる。どれだけ得をするかは関数の構造によるので、まずKeccakで数えてみる。

SHA-3の中核となる1600 bitの置換関数Keccak-f[1600]は、1600 bitの状態に対してθ、ρ、π、χ、ι の5ステップを1ラウンドとして、24ラウンド繰り返す関数。このうち非線形なステップはχのみで、 {a \oplus (\lnot b \land c)}という形をしている。ANDは1 bitあたり1個。状態1600 bitすべてに適用されるので、1ラウンドあたり1600個。残りのθはXORの畳み込み、ρとπはビットの並べ替え、ιは定数のXORで、いずれも制約に一切寄与しない。そのため、Keccak-f[1600] 1回分のR1CSのサイズは

{1600 \times 24 = 38{,}400} 本

総ビット演算数から見れば、制約になるのはごく一部でしかない。

ただ、これはKeccakが例外的にGF(2)フレンドリーだからでもある。SHA-256のように32ビット整数加算を含む関数では、繰り上がりがそのままANDになるので事情が異なる（代表的な最適化Boolean回路では圧縮関数1回で22,573個。うちMaj/Chは4,096個で、残りは加算の繰り上がり）。

それでも素体 + lookup 方式だと、この線形部分にもトレース列とlookupのコストがかかっていた。GF(2) + R1CS では丸ごと消える。Flockが「Boolean回路を直接扱う」と打ち出しているのは、この利点が大きいから。

R1CSから証明系へ

R1CSは、与えられた制約をすべて満たす解が存在するかを問う充足可能性の問題であって、それ自体は証明系ではない（つまり、解を知っていることを、解を見せずに納得させる手段は含まれない）。そのため、ここから先の経路は主に2つある。

経路1: QAP（Groth16）

m本のR1CSの制約を1本の多項式の関係にまとめるのがQAP。

制約1本ごとに評価点 {\omega_k} を割り当て、 {A(\omega_k) = \langle \mathbf{a}_k, \mathbf{z}\rangle} となる多項式 {A(x)}を補間で作る（ {B, C} も同様）。全制約が成り立つということは、 {A(x)B(x) - C(x)} が全評価点を根に持つことなので、消失多項式 {Z(x) = \prod_k (x - \omega_k)} で割り切れることと同値になる。

{A(x)B(x) - C(x) \equiv 0 \pmod{Z(x)}}

前回のBabyStarkで商多項式を作ったのと同じ発想で、これをペアリングで検査するのがGroth16。

経路2: 多変数（Spartan、Flock）

QAPが一変数多項式に補間したのに対し、こちらは多変数の多重線形多項式を使う。

witnessを多重線形多項式とみなし、充足性をsumcheckで検査できる形（zerocheck / lincheck）に変換する（sumcheckについては、以前の記事参照）。sumcheckが最後に残す1点での評価クレームを、多項式コミットメントのオープニングで確かめる。

まとめ

  • R1CSは {(A\mathbf{z}) \circ (B\mathbf{z}) = (C\mathbf{z})} という形の制約系で、平坦化した回路では、制約1本が基本的に1つの乗算に対応し、加算はタダ
  • witnessベクトルは「計算の全実行過程を並べたもの」
  • AIRと違って一様性がないため記述量が {O(m)} になり、前処理・疎コミットメント・バッチ構造のいずれかで手当てが要る
  • 次数2に固定されるのが弱点で、そこを緩めたのがPlonkishのカスタムゲート
  • GF(2)上では「制約 = ANDゲート、XORはタダ」になり、標準ハッシュ関数の表現に極めて有利。Flockが賭けているのはここ。

次はこのGF(2) R1CSを実際に動かす側、つまり二進体 + sumcheck + Ligerito のスタックを追いたい。

*1:AIRの式の数はステップ数ではなく計算の複雑さで決まるので、分岐や複数命令があれば式は増える。それでも繰り返し部分が圧縮されるという性質は変わらない。

⚡ Zap me!

Lightning QR

Lightning Address

techmedia_think@walletofsatoshi.com