https://techmedia-think.hatenablog.com/entry/2026/02/25/180339

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

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

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

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

ADP

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

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

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

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

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

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

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

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

暗号化

Witness Encryptionの文脈では、

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

という形で暗号化する。

メッセージの埋め込み

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

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

から

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

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

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

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

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

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

復号

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

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

ランダム化

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

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

AADP

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

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

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

分散セットアップ

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

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

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

実用性

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

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

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