計算した値を commit した値に束縛する

メイカー（値付けする側）は、自分の値付け規則を 7 つの計算ノードにシェア（秘密分散の断片）として配る。各ノードは計算の前に、受け取ったシェアを配った側の commitment（値を隠したまま固定する暗号学的な封印）と照らして確かめられる。しかし、ノードがその後 MP-SPDZ に入れる値が、いま確かめたそのシェアであることは、何も強制していない。これがスタックの中央に残る唯一の隙間である。このページで扱うのは、この隙間を閉じることと、その費用を見積もることだけである。

出典: qomm/BINDING.md · 特記なき限り host-a で計測。各方式は、時間を測る前に平文の答えと照合済み

隙間を正確に述べる

配られたシェアに付く署名が与えるのは、検出と行為者の特定であり、防止ではない。入力を差し替えたノードは、後からそれをしたと示せる。それで足りるかどうかは、ノードが誰かで決まる。KYB を済ませ、没収され得る bond（保証金）を差し入れた 7 つの法人なら、行為者の特定だけで縛れる。防止を足しても得るものは少ない。匿名の運営者 7 人なら、何にも縛られない。同じ隙間が三つのモジュールの下にあり、それは一つの隙間である。監査が述べているシェアは、既定では MP-SPDZ が実際に使うシェアではない。MP-SPDZ は自前の素体の上で動くからである。

したがって、端から端まで通る束縛には二つの方法がある。計算を commitment と同じ体の上で走らせるか、両者を commit-and-prove でつなぐかである。この二つが、ここで言う二つの道である。

この機構は新しいものではない。査読で指摘される前に、冒頭で言っておく。Publicly Auditable MPC（Baum, Damgård, Orlandi, SCN 2014）では、入力提供者が Pedersen commitment を公開する。その準同型演算がプロトコルの動作をそのまま写すので、監査人は commitment の上で関数を再実行できる。quote proof（見積が規則どおりに計算されたことの証明）は、この構成の一つの実体化である。ここにあるのは、その応用と、それを動かす費用である。

体が邪魔をする理由

threshold_sigma は、誰も丸ごとは保持していない値について、ノードが何かを証明する手段である。シグマ・プロトコルの応答 z = k + c·w は witness（証明者だけが知る秘密の値）について affine である。そのため各ノードは、自分のシェアから z_i = k_i + c·w_i を計算できる。その断片を群のスカラー体の中で Lagrange 結合すると z になる。これが手法の全部である。設計が汎用 SNARK ではなくシグマ・プロトコルを使う理由も、ここにある。ただし成り立つのは、シェアが群の位数の上にあるときだけである。これを必要とする証明は二つ（quote proof と zkPI で、見出しの主張でもある）。必要としないものも二つ（値付け規則と状態の監査。メイカーは自分の witness を知っている）。

道その一: 体を合わせる

MP-SPDZ を ed25519 の群の位数の上で走らせれば、Lagrange 結合は書かれたとおりに正しくなる。新しい暗号は要らない。既存のコードが、書いてあるとおりの意味を持ち始める。

ラウンド数は変わらない。通信量の増加は、要素の幅が 16 バイトから 32 バイトになった分にちょうど一致する。壁時計時間（実際にかかった時間）の増加は、遅延 15 ms で 7%、120 ms で 6% である。地域をまたぐほど相対的に安くなる。ラウンド数が変わらず、遠距離では往復の時間が支配的だからである。体を合わせる費用は手の届く範囲にあり、これがこのページの大半を決める。

この節がかつて報告していた 7 倍の誤り

最初の版は、ラウンド 2.02×、通信量 14.3× と報告していた。その後の判断はすべて、そこから導いていた。どの体を採るか、入力検査を作る価値があるか、地域をまたいだときの処理量、別の群が助けになるか。すべての原因は、一つの誤ったフラグだった。回路は -P <prime> でコンパイルされていた。MP-SPDZ は、このようにコンパイルするたびに警告を出す。これは効率的でない変種のコードを有効にするものであり、正式な経路は実行時に素数を与える -F である、と。警告は毎回出力にあり、読まれなかった。

その後、存在しない問題に対して三つのものが計測された。edaBits は 2 桁悪化した（前処理を単一段階のハーネスで測っていたためである）。確率的切り捨ては何も変えなかった。二つの本物の手段は、今も効くが不要になった。存在しない障壁を回避する方法を文献にも探した。Rabbit は、体の大きさに比例する比較の費用を取り除く。MP-SPDZ は既にこれを実装している。条件は素数が 2 の冪に近いことで、ed25519 の位数は 2⁻¹²⁷ の差でこれを満たす。ツールが理由を毎回平文で出力している間に、7 倍という数字が三つのリポジトリとスライド一式に公開された。進め方のページは、これを最初の教訓として残している。

道その二: 代わりに入力を検査する

配る側は既に、入力ごとに commitment を公開している。入力が確定した後、Fiat–Shamir で公開の係数を導く。回路は、commit 済みのマスク r に対して s = Σ c_j v_j + r を計算し、s を開く。Pedersen commitment は加算できるので、同じ係数で commitment を一つにまとめられる。s は、そのまとめた commitment を開く値でなければならない。v_j + e_j を入れたノードは、s を Σ c_j e_j だけずらしてしまう。ずれを消すために満たすべき係数は、そのノードが e を選んだ時点にはまだ存在しなかった。公開係数と秘密シェアの積は各ノードの手元で計算できるので、まとめる工程に通信は要らない。s を開く工程だけがラウンドになる。

安全性証明を書いたところ、この検査は健全でなかった。係数は、配る側の commitment から固定されていた。ノードは engine に入力を入れる前にその commitment を読めるので、係数の核（係数との内積が 0 になる誤差の集合）の中から誤差を選べば、確率 1 で検査を通れる。修正では、チャレンジを入力段階の後に引き、その冪を係数に使い、MPC の素数を法として計算する。これで健全性が直る（2⁻⁴² から約 2⁻²⁴⁵ へ）。整数版が必要としていた幅の予算も消える。費用は、一括の検査に比べてラウンド 1 回の追加と通信量 0.39% の増加である。

検出だけなら、全入力に対して 1 回開けば済む。誰が差し替えたかの判定には、ノードごとに 1 回ずつ開く必要がある。この参加者ごとの形は、差し替えたノードの名前を挙げられる。費用は一括の検査の 7.4 倍（166 入力で 103.5 ms）である。名指しできる台数に上限はない。各参加者の検査が、その参加者自身の commitment に対して独立に立つからである。差し替えたノードが何台あっても名指しでき、7 台全部まで試してある。

端から端まで実装して動かした

修正は比較ではなく同一性である。値に commit する参加者と、その値をシェアに分ける参加者を、同じ参加者にする。参加者ファイルを書く一回のパスの中で両方を行う。これで、commit したのに配らない、配ったのに commit しない、ということが起こらない。回路の変更は 1 行である。入力は、公開の Lagrange 係数を使って n 点すべてから 0 の位置で補間する。

artifact（計測の成果物）: binding_chain.json（host-c、メイカー 8 社）· 修正後に小数第 4 位まで再計測。数え上げた値なので、そこまで一致すべきである

連鎖の各方式が何をするか。正直な実行では、86 個の値を一回のパスで commit して分け、602 件のシェア検査が通り、範囲証明は配られた commitment に対して検証される。commit していない値を配った側は、計算が始まる前に、参加者 3 の位置 8 で捕まる。別の値を入力するノードは、配る段階では捕まらない。artifact もそう記している。差し替えられた入力は、別の数の正当なシェアだからである。この最後の場合を捕まえるのが入力検査である。

どちらを採るか

群の位数を採る。壁時計時間で 6 から 8 パーセント、バイト数で 2 倍（見積 1 件・ノード 1 台あたり 2.8 MB に対して 5.5 MB）の費用で、公開検証可能な quote proof が手に入る。入力検査はその上で、速い事前検査として働く。差し替えられた入力を、317 ms かかる証明が検証に失敗した時点ではなく、その場で捕まえる。代替ではなく多層防御である。狭い体での検査は、quote proof を丸ごと省く配置にとっては、引き続き答えである。

commitment 方式は選べる: VOLE-in-the-Head の計測

Rust の commitment トレイトは、継ぎ目を commitment そのものへ移す。指定検証者型の VOLE commitment は体の乗算 1 回で済む。Pedersen では同じ箇所がスカラー乗算になる。scale 1 回の素の比較では 113× の差である。しかし安い方を検査できるのは Δ の保持者だけである。検査しなければならないのは、その場にいなかった規制当局である。これを公開検証可能にするのが VOLE-in-the-Head である。いまは実装済みなので、問いには計測で答えが出る。両方式は同じ命題を証明し、両方とも公開検証可能である。host-a、n=30、167 入力。

つまり 113× は Pedersen に対する優位ではなかった。検査できないことの対価だった。高いのは木（tree）ではない。証明の 88% は VOLE の整合性補正である。これは F₂ 上（FAEST の設定であり、公表されているすべての数値の設定）ではビットだが、127 ビット素数の上では 16 バイトの要素になる。公表されている「指定検証者型の通信量の 2 倍」という数字は、ビットでない witness には持ち越せない。計算量も同様である。同一の木パラメータで、PRG 出力は FAEST の 819 kB に対して 17.8 MB になる。マーケットメイキングの値付け規則はビットではない。深さと繰り返し回数のトレードオフ曲線は、FAEST の表 2 の形を再現している。それがこのハーネスを信じる理由である。

得られるものは本物だが、速度ではない。群がないので、MPC の体が合わせるべき相手がない。対称鍵プリミティブだけなので耐量子である。証明は大きくなるが、commitment は小さい（5,344 B に対して 2,672 B）。問題になるのは、commitment が一回限りであることである。Δ を公開した後は、同じ commitment についての二つ目の命題は何も証明しない。Prover.prove は、この制約を文書に書くのではなく例外を投げる。メイカーの値付け規則は、規則の存続期間中、見積のたびに開かれる。したがってこれは脚注ではなく再設計になる。

別の群なら安くなるか。ならない

128 ビット安全性を求めると、曲線でも乗法群でも、どの離散対数群でもスカラー体はおよそ 256 ビットになる。離散対数ベースの方式で MPC の体を縮めるものはない。群を変えて変わるのは証明の速さである。曲線でない群は、そこで 338× から 475× 遅い。体を縮められる唯一の方向は格子 commitment である。その安全性は法の大きさではなく次元から来る。

耐量子

秘匿計算そのものは既に耐量子である。honest majority（過半数が正直という前提）の Shamir は情報理論的に安全だからである。Pedersen は完全秘匿で、束縛は計算量的である。そのため量子敵が commit された値を知ることは決してない。奪われるのは証明する能力である。この文は慰めになるが、半分しか正しくない。証明している対象はオークションであり、この損失には量子計算機は要らず、時間だけで足りる。メイカーの値付け規則の commitment は、規則の存続期間中ずっと、直接の金銭的動機を持つ敵の前に置かれている。Rivinius らはまさにこの議論をしており、一般論より優れている。

障害は、難しくなる順に三つある。第一に大きさ。シグマ証明は 1 ステップ 4,960 B で、格子での同等物は数キロバイトから数十キロバイトになる。第二に棄却サンプリング。abort（中断）の判定は結合後の応答に対して行うので、ノードは判定のために値を復元しなければならない。棄却は、それが防ぐはずの漏れの後に届く。第三に Shamir に対する短さ。これが構造的な障害である。格子の健全性は短い witness を要するが、Lagrange 係数は任意の体の要素なので、短さは復元を生き残らない。抜け道はいくつかある（保存量 15 倍の複製型秘密分散、係数の小さい方式、格子ベースの閾値署名）が、それぞれ何かと引き換えになる。署名は速度ではなく大きさの問題である。ML-DSA-44 は値付け規則の更新経路で Ed25519 の 14.7 倍のバイト数になるが、現実のメイカーの頻度では毎秒 3 メガバイト未満である。どの理由で格子へ行くにしても、やる仕事は同じである。応答が witness について線形であることを要しない、証明の組み立て方法を作ることである。

量子ネットワークが変えるもの: 一つ

システムがまだ計算量的仮定に頼っている唯一の場所を閉じる。MPC は無条件安全だが、それを運ぶ配管は TLS の上を走る。後に TLS を破る記録者は、すべてのシェアを手にする。一つの都市圏に固定された 7 つの端点は、QKD が向く形である。通信をワンタイムパッドで包むことはできない。最も安い行でも鍵が 62 Mbps 必要で、都市圏 QKD は 0.1 から 10 Mbps しか出ないからである。できるのは対称暗号の鍵更新である。対称暗号は既に量子安全なので、得られるのは次の一点になる。いま記録して後で解読する攻撃に対して、鍵交換の仮定を信頼しなくてよくなる。commitment は救えない。それは工学の限界ではなく不可能性定理（Mayers、Lo–Chau）による。そして証明は、その回線上にいなかった者を納得させなければならない。量子ネットワークは配管を無条件にするが、証明は無条件にしない。

外れた予測の一覧

まとめて置く。当たった予測だけを見せる文書は、規律を報告しているのではなく宣伝しているからである。

VOLE-in-the-Head の外れ 5 件の原因は一つである。witness がビットであるかのように費用を見積もったことである。最も重要な二つの予測は最初から正しかった。それが、否定する計測の下に 1 週間埋もれていた。算術は費用が要素幅の分だと言い、計測は 14 倍だと言った。正しかったのは算術で、ハーネスの設定が誤っていた。ここから持ち出すべき知見はそれである。