Develop with pleasure!

福岡でCloudとかBlockchainとか。

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で

 {A = \begin{pmatrix} 3 & 1 \\ 2 & 5 \end{pmatrix}, B_1 = \begin{pmatrix} 1 & 0 \\ 0 & 3 \end{pmatrix}, B_2 = \begin{pmatrix} 0 & 2 \\ 4 & 0 \end{pmatrix}}

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

 {M = A + 1\cdot B_1 + 0 \cdot B_2 = \begin{pmatrix}4 & 1 \\ 2 & 1 \end{pmatrix}}
 {det(M) = 4\cdot 1 - 1 \cdot 2 = 2 \mod 7}

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

 {M = A + 1\cdot B_1 + 1 \cdot B_2 = \begin{pmatrix}4 & 3 \\ 6 & 1 \end{pmatrix}}
 {det(M) = 4\cdot 1 - 3 \cdot 6 = -14 = 0 \mod 7}

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

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

暗号化

Witness Encryptionの文脈では、

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

という形で暗号化する。

メッセージの埋め込み

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

 {M = \begin{pmatrix}4 & 3 \\ 6 & 1 \end{pmatrix}}

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

 {\begin{pmatrix}4 & 3 \\ 6 & 1 \end{pmatrix} \begin{pmatrix}v_1 \\ v_2 \end{pmatrix} =  \begin{pmatrix}0 \\ 0 \end{pmatrix} \mod 7}

から

  • {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に依存するようになる↓

 {M(x) \cdot v = 0}の解→v= (..., .., msg, ..., ...)
                                 ↑
                      特定の位置にmsgが現れる

復号

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

  1. M(w)を計算し、
  2. det(M(w)) = 0となり、カーネルが非自明
  3. ガウスの消去法等でM(w) · v = 0を解いてカーネルベクトルvを求め
  4. 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で高コストだけどなんとか計算可能なレベルなったというのが現状みたい。とは言ってもカジュアルに利用できるようなレベルにはまだない。

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は、演算を回路に変換することなく、

  1. 入力値（曲線上の点のbit分解）を準同型MACに変換し、
  2. 準同型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:フリーゲートの方は入力ラベルから出力ラベルを導出可能なのでガーブルド・テーブルが不要

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では以下がチェックされる

  1. 入力ラベルがコミットされた値と一致するか検証
  2. 復号鍵k = Hash(入力ラベルA ⊕ 入力ラベルB)を計算
  3. 出力ラベルを復号：出力ラベル = ciphertext ⊕ k
  4. 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に削減可能という話もある

P2Pプロトコルの新機能をネゴシエートするためのfeatureメッセージを提案するBIP-434

BIP Bitcoin

先日BIPリポジトリにマージされたBIP-434↓

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

Bitcoinのような分散環境のノード実装は、他のノードと接続しメッセージを交換することでブロックやトランザクションを伝播しチェーンの同期を行う。これを行うためには、互いが送受信するメッセージを解釈し適切に処理できる必要がある。Bitcoinの実装ではこれまで、初期に実装されていたメッセージ以外にも多数の新たなメッセージを導入してきた。当然すべてのノードが一斉にバージョンアップするということはないので、接続相手がどのメッセージをサポートしているのか確認した上で適切な振る舞いをする必要がある。

P2Pプロトコルバージョン

そのためP2Pプロトコルのバージョンを定義し、ノードに接続した後に最初に送信するversionメッセージ内に自身がサポートするP2Pプロトコルのバージョンを指定することで、相手ノードにバージョンを通知している。Bitcoin Coreではこれまで以下のようにこのバージョンをアップグレードすることで新しいP2P機能を導入してきた。

バージョン 時期 Bitcoin Core 導入機能
106 2009/10 0.1.6 versionメッセージにaddress-from、nonce、user-agent、current block heightフィールドを追加
209 2010/5 0.2.9 addrメッセージが複数のネットワークアドレスのリストを受け入れ可能に。メッセージヘッダーにチェックサムフィールドを追加
311 2010/8 0.3.11 alertメッセージを追加
31402 2010/10 0.3.15 addrメッセージにタイムスタンプフィールドを追加
31800 2010/12 0.3.18 getheadersメッセージとheadersメッセージを追加
60000 2012/3 0.6.0 ネットワークプロトコルバージョンをBitcoin Coreのソフトウェアバージョンと分離
60001 2012/5 0.6.1 pongメッセージを追加し、pingメッセージにnonceフィールドを追加
60002 2012/9 0.7.0 mempoolメッセージを追加し、getdataメッセージを拡張しmempool内のトランザクションをダウンロード可能に
70001 2013/2 0.8.0 versionメッセージにfRelayフラグを追加。Bloom Filter用のfilterload、filteradd、filterclear、merkleblockメッセージを追加。notfoundメッセージを追加。getdataメッセージにMSG_FILTERED_BLOCKインベントリタイプを追加
70002 2014/3 0.9.0 rejectメッセージを追加。mempoolメッセージへの応答で必要に応じて複数のinvメッセージを送信
70011 2016/2 0.12.0 NODE_BLOOMサービスビットを導入し、このサービスビットの指定がない状態でのfilter*メッセージを無効化
70012 2016/2 0.12.0 sendheadersメッセージを追加。ノードが新しいブロックのアナウンスをinvではなくheadersメッセージで受信することを優先できるように
70013 2016/8 0.13.0 feefilterメッセージを追加し、alertメッセージシステムを廃止
70014 2016/8 0.13.0 コンパクトブロックリレーのメッセージsendcmpct、cmpctblock、getblocktxn、blocktxnを追加。
70015 2017/1 0.13.2 0.14.2 コンパクトブロックの不正ブロックに対するBAN動作の更新
70016 2021/1 0.21.0 wtxidrelay、sendaddrv2メッセージを追加

ハンドシェイク中のメッセージ送信

versionメッセージのプロトコルバージョンを使わずに導入されたP2Pメッセージもある。BIP-155とBIP-339では、ハンドシェイクにおいて、versionメッセージに対してverackを送信する前に、それぞれsendaddrv2メッセージとwtxidrelayメッセージを送信するというアプローチを採っている。またBIP-330のsendtxrcnclメッセージも同様。

BIP-434が提案された背景

versionメッセージを使ったプロトコルのアップグレードの問題点は、基本的にプロトコルバージョンがインクリメントされていくという点にある。ノードとしてはサポートする必要のない機能であっても、新しい機能をサポートする場合、それ以下のすべての機能をサポートしなくてはならなくなってしまう。こういった機能の展開については、インクリメントされる数値ではなく、LNのfeature bitのような表現方法の方が適している。

また、70001のアップグレードでversionメッセージにfRelayフラグを追加した際は、本来フィールド数が固定されているメッセージにオプショナルフィールドが加わると互換性問題が生じた。

また、ハンドシェイク中に送信されるメッセージについては、未知のメッセージを受け取ったノードがどのような振る舞いをするかに依存した実装になる。未知のメッセージを受け取ったノードはそのメッセージを無視するのであれば問題ないが、未知のメッセージに受け取って際に接続を切断する実装があった場合、将来的にネットワークが分断される可能性がある。Bitcoin Coreでも、version-verack間に未知のメッセージを送るとペナルティが課されるようにハンドシェイクを厳格化し（2017年）、その後wtxidrelayの提案によりversion-verack間の未知のメッセージは無視するよう方針転換（2020年）された経緯がある。

そこで、BIP-434では↑のBIP-339の仕組みを将来のP2Pのアップグレードのために一般化する提案をしている。個別のメッセージではなく、任意の新機能を通知するためのネゴシエーション機能としてfeatureメッセージを導入する。

BIP-434の使用

BIP-434をサポートするノードは、

  • versionメッセージのプロトコルバージョンとして>= 70017を設定する必要がある。
  • プロトコルバージョンが70017未満のピアに対しては、featureメッセージを送信してはならない
  • versionメッセージの後、verackメッセージの前に受信したfeatureメッセージを受け入れなければならない。
  • verackメッセージを送信した後で、featureメッセージを送信してはならない。
  • versionメッセージの後、verackメッセージの前に受信した未知のメッセージは無視すべき。
  • verackメッセージを送信した後で、featureメッセージを受信した場合、無視してもいい。
  • verack後にfeatureメッセージを送信するピアを切断してもいい。
  • featureメッセージにより対象の機能のサポートを示していないピアに、その対象機能が導入するメッセージのverack後の送信を禁止しなければならない。

featureメッセージ

featureメッセージは以下のペイロードを持つ：

名称 型 定義
featureid string 機能の一意識別子。長さを指定するCompactSizeの後にその長さのデータが続く。文字列はASCII文字。BIPが公開されている場合、BIP番号であるべき。
featuredata byte-vector 機能固有の設定データ。長さを指定するCompactSizeの後にデータが続く。これらのデータが解釈されるかはその機能仕様次第。サイズは512 byteを超えてはならない。不要な場合は空のバイト列になる。

ノードは、

  • サポートしていないfeatureidのfeatureメッセージは無視する。
  • 認識していないfeatureidでもfeatureメッセージのペイロードが正しく解析できない場合、送信ピアを切断してもいい。

featureメッセージは１つの機能に対応しているので、複数の機能をサポートする場合は、その数分featureメッセージを送信することになる。feature bitみたいに機能ビットで機能セットを表現せずに個別に送信するのは、機能によっては、featuredataデータが必要になるからかな。

ブラインドMuSig2

musig Schnorr Cryptography Bitcoin

MuSig2は、n-of-nのマルチシグを暗号技術のみで構成するSchnorrベースのスクリプトレスなマルチシグスキーム↓

techmedia-think.hatenablog.com

そのブラインド版がブラインドMuSig2↓

https://github.com/halseth/ephemeral-signing-service/blob/main/doc/general.md

MuSig2の場合、通常署名者は

  • 何のメッセージに署名しているのか
  • 他の署名者の情報（公開鍵）

について知ることができる。ブラインド版は、これらの情報を秘密にしたまま有効なSchnorr署名を構成できるようにしたもの。

署名者であれば一般的には署名内容を把握した上で署名すべきだけど、こういったブラインド署名は、

などのケースにおいて有用な可能性がある。

ブラインドMuSig2

署名者が2人（アリスとボブ）いて、2-of-2のマルチシグを構成する場合、参加者の公開鍵を以下とする（小文字が秘密鍵）。

  • {X_A = x_A G}
  • {X_B = x_B G}

ブラインド版では、署名者が署名内容について知らずに署名をできるようにするためコーディネーターという役割を導入する。このコーディネーターは、署名対象のメッセージ（m）や、参加者、ブラインド係数などの情報を把握するが、署名者の協力がないと（＝署名者の秘密鍵がないと）有効な署名を生成することはできない。

まずコーディネーターは、集約公開鍵を導出する。

ランダムなsalt値rを選択して以下の鍵係数を計算する（saltを使う理由は、署名者が候補となる公開鍵を総当たりで試して、誰と一緒に署名セッションに参加しているかを確認できないようにするため）。

  • {l = H(r || X_A || X_B)}
  • {c_A = H(l || X_A)}
  • {c_B = H(l || X_B)}

続いて、鍵係数を使って集約公開鍵 {X' = c_AX_A + c_BX_B}を計算する。この集約公開鍵の計算自体は、通常のMuSig2と同じ計算。ただブラインド版では各署名者は互いの公開鍵を知らないため、コーディネーターのみが導出できる。各署名者は集約公開鍵を知らないため、オンチェーンにX'が登場しても自分が関与したトランザクションであることが認識できない。

続いて署名の生成。署名者のアリスとボブは、署名に使用する2つの公開ナンスを計算する：

  • {R_A^{1} = r^{1}_AG}と {R_A^{2} = r^{2}_AG}
  • {R_B^{1} = r^{1}_BG}と {R_B^{2} = r^{2}_BG}

コーディネーターは各署名者から受け取った公開ナンスを使って集約ナンスを計算する。

  • {R^{1} = R_A^{1} + R_B^{1}}
  • {R^{2} = R_A^{2} + R_B^{2}}

続いて、ナンスの係数 {b = H(R^{1} || R^{2} || X' || m)}を計算し、集約ナンスを {R = R^{1} + bR^{2}}とする。

公開ナンスの生成から集約ナンスの計算は、通常のMuSig2と同様。ただ署名に使われる最終的なナンスはブラインド値を加味した以下のR'になる。

続いて、ブラインド値 {\alpha_A, \beta_A, \alpha_B, \beta_B, \gamma_A, \gamma_B}を選択し、以下の署名ナンスを計算する：

{R' = R + \gamma_A R^{2}_A + \gamma_B R^{2}_B + \beta_AX_A + \beta_BX_B + (\alpha_A + \alpha_B)G}

続いて署名対象のメッセージmを使って {e = H(R', X', m)}を計算する。

続いて、メッセージをブラインドするために各署名者に対して以下を行う（βはチャレンジeをブラインドし、γはブラインダーbをブラインドする）。

  • アリスに対して
    • {e_A = c_Ae + \beta_A}と {b_A = b + \gamma_A}を計算し、 {(e_A, b_A)}を送る。
  • ボブに対して
    • {e_B = c_Be + \beta_B}と {b_B = b + \gamma_B}を計算し、 {(e_B, b_B)}を送る。

このように、各署名者は署名するメッセージについて何も知らない。

各署名者は、以下のようにブラインド部分署名を計算する。

  • アリスの場合
    • {s'_A = r^{1}_A + b_Ar^{2}_A + e_A x_A = r^{1}_A + (b + \gamma_A)r^{2}_A + ec_Ax_A + \beta_Ax_A}
  • ボブの場合
    • {s'_B = r^{1}_B + b_Br^{2}_B + e_B x_B = r^{1}_B + (b + \gamma_B)r^{2}_B + ec_Bx_B + \beta_Bx_B}

各署名者からブラインド部分署名を受け取ったコーディネーターは、R'に対応させるため以下の加算を行う。

  • {s_A = s'_A + \alpha_A}
  • {s_B = s'_B + \alpha_B}

続いて、部分署名を合算して集約署名を計算する。

{s = s_A + s_B}

{\quad = s'_A + \alpha_A + s'_B + \alpha_B}

{\quad = r^{1}_A + (b + \gamma_A)r^{2}_A + ec_Ax_A + \beta_Ax_A + \alpha_A + r^{1}_B + (b + \gamma_B)r^{2}_B + ec_Bx_B + \beta_B x_B + \alpha_B}

{\quad = (r^{1}_A + r^{1}_B) + b(r^{2}_A + r^{2}_B) + \gamma_A r^{2}_A + \gamma_B r^{2}_B + e(c_Ax_A + c_Bx_B) + \beta_Ax_A + \beta_Bx_B + (\alpha_A + \alpha_B)}

結果の（R', s）がメッセージmおよび集約公開鍵X'に対して有効なSchnorr署名となる。

この署名は以下の署名検証のチェックを満たす。

{sG = (r^{1}_A + r^{1}_B)G + b(r^{2}_A + r^{2}_B)G + \gamma_A r^{2}_AG + \gamma_B r^{2}_BG}

{\qquad + e(c_Ax_A + c_Bx_B)G + \beta_Ax_AG + \beta_Bx_BG + (\alpha_A + \alpha_B)G}

{\quad = R^{1}_A + R^{1}_B + b(R^{2}_A + R^{2}_B) + \gamma_AR^{2}_A + \gamma_BR^{2}_B }

{\qquad + e(c_AX_A + c_BX_B) + \beta_AX_A + \beta_BX_B + (\alpha_A + \alpha_B)G}

{\quad = R + \gamma_AR^{2}_A + \gamma_BR^{2}_B + \beta_AX_A + \beta_BX_B + (\alpha_A + \alpha_B)G + e(X'_A + X'_B)}

{\quad = R' + eX'}

検証式から分かるように、ブラインド値はすべて署名ナンスR'で回収される。

ブラインド値の {\alpha_A, \alpha_B}については、おそらくオンチェーン上のTxを監視してそれらの署名値などと組み合わせて事後分析などできないようにするためのブラインド値と思われるけど、いずれもコーディネーター側でしか計算には使わないので1つあれば十分な気がする。

課題と信頼モデル

MuSig2の設計上の重要な点は、鍵係数（l）とブラインド値（b）の選択。通常のMuSig2の場合、すべての署名者が係数が適切に構成されていることを検証できるけど、ブラインド版ではこれらの値がブラインド化されているため署名者の検証が不可能になる。そのため上記のブラインドモデルはコーディネーターを信頼するモデルとなる。

コーディネーターに悪意がある場合、署名すべきではないメッセージに署名させたり、それにより鍵情報が漏洩する可能性もある。