説明責任と頑健性

「止まらないこと」と「止めようとした相手の名を挙げること」は、別々の性質である。配備中のエンジンはどちらも持たない。逸脱を検出すると、プロトコルは abort（中断）する。このページでは三つのことを書く。それぞれの性質を持つには何が要るか。何を実装したか。そして、abort が liveness（止まらずに動き続けること）の問題ではなく経済的な道具になる環境で、それぞれに何がかかるか。

出典: zkpi/ACCOUNTABILITY.md · artifact（計測結果のファイル）: locate.json, decode_patch.json, robust_atlas.json, robust_atlas_host_c.json, dishonest_majority.json, identity.json, fill_fold.json

説明責任の段階は二つではなく五つ

公開検証可能性はこの段階の上にはない。別の直交する軸であり、「答えは正しく、外部の者もそれを確かめられる」という性質である。公開検証可能でありながら、第 1 段で止まったままのプロトコルもありうる。ここでの状況はまさにそれである。各仕組みの位置は次のとおり。メイカーが配ったシェアは、境界の部分だけ第 4 段。ノードがエンジンに入れる値は第 0 段だったが、いまは回路の中で確かめられる（束縛）。MPC 本体は第 1 段。quote proof（見積が正しく計算されたことの証明）はもう一方の軸にある。

嫌がらせの abort が、一般の MPC よりここで深刻な理由。 たいていの配備では、abort したら再試行するだけである。しかしオークションでは、匿名かつ無償で好きなときに abort できるノードは、気に入らない見積を潰せる。メイカーと結託したノードなら、そのメイカーが不利な約定を食らいそうな回だけを狙って潰せる。これでは、サービス妨害が無償のオプションに変わる。

ここでは頑健性は費用ではなく節約である

n=7 に対する T=2 は t/n = 0.286 で、n/3 を下回る。Goyal、Song、Zhu（CRYPTO 2020）は、t < n/2 で出力保証付きの無条件安全な MPC を与えている。さらに t < n/3 なら、ブロードキャストを一対一の回線で模擬できる。この配備はその厳しい側の領域にあるので、ブロードキャストを仮定しなくてよい。GSZ の代価は、乗算 1 回・参加者 1 人あたり体の元 5.5 個。不正な参加者を特定した後は 7.5 個である。これは何と比べて安いのか。同じホスト上で、二つの回路サイズの間の傾きとして計測した。

出力保証の費用は、配備中のプロトコルのオンライン段階だけと比べても安い。総量と比べれば 6.4× 安い。しかも得られる性質は厳密に多い。したがって、この配備に頑健性がない理由は、設定ではなくエンジンにある。MP-SPDZ の honest majority 向け malicious プロトコルはどれも abort 付き安全性までであり、GSZ は MP-SPDZ に実装されていない。ハーネス（計測用の枠組み）は、信じる前に照合した。GSZ は最良の semi-honest プロトコルを 5.5 と述べ、ハーネスは 5.714 を返す。乗算を加算に置き換えた対照回路では、傾きがゼロになる。

シェアはそれ自体が誤り訂正符号である

開示（値を復元して公開すること）のとき、MP-SPDZ は t+1 個のシェアから値を復元する。次に、それより長い接頭部分のそれぞれからも復元し直し、結果が食い違えば「inconsistent Shamir secret sharing」を投げる。つまり、誤り訂正ができるデータの上で、誤り検出だけを行っている。次数 t の秘密の Shamir シェアは Reed–Solomon 符号語 RS[n, t+1] であり、n=7、t=2 なら距離 5、ちょうど二つの誤りを訂正できる。Berlekamp–Welch 復号は、正しい値と誤りの位置の両方を返す。誤りの位置は、間違ったシェアを送った参加者の名を挙げる。

エンジンは誰が不正をしたか知っているか。答えは否で、しかも素朴な推測は外れる。ある参加者の前処理データを 1 バイト反転させると、犯人が別々の二者でも同じエラー文字列が出る。壊れたデータの持ち主が、他の参加者から見て後で接続する相手である場合、他の参加者は先に接続断で落ちる。だからこれを調べる運営者は、間違ったノードを責めることになる。

T=2 で、訂正できる数も 2。この配備が耐えるよう設計された不正の閾値は、自身のシェア分散で訂正できる数とちょうど一致する。つまり、耐えるはずのすべての不正について、名も挙げられる。誤りが三つになると、復号器は推測せずに拒否する。それが唯一の正しい振る舞いである。費用は、すでに受け取ったデータの上で済み、追加のラウンドはない。誤りなしで 22.9 µs、嘘つき二人で 208 µs。エンジンが行う素の Lagrange 補間は 20.6 µs である。

いまはエンジンに入っている。 malicious Shamir の開示に当てたパッチが、送信者の名を挙げる。「sent by player 1, player 4」、または「more than 2 parties sent wrong shares, which is beyond the decoding capacity of this sharing」と出る。費用はオンライン段階の元の数で 1.50×、単一段階の総量で 1.33×。バッチ化された開示は最も近い 2t+1 者への部分的なブロードキャストだったが、嘘つき二人の位置を特定するには 7 者全員のシェアが要るからである。予測では無償になるはずだった。バッチ化されない側のコード経路を読んで立てた予測だった。一つのコード経路を読み、それが実行される経路だと思い込んで数字を間違えたのは、このプロジェクトで三度目である。

このパッチが名を挙げるのは、形の壊れたシェアを送った参加者である。自分の入力について嘘をついた参加者の名は挙げられない。そしてそちらの方がありそうな攻撃である。自分の入力ファイルの数字を別のものに変えれば、それは別の値の正当なシェア分散になる。符号語としては正しいので、復号で見つけるものがない。これを扱うのが参加者ごとの入力検査である。各参加者の検査が独立に成り立つので、訂正できる数のような上限がない。同じ仕組みで、一つの見積を端から端まで追える。テイカーの数量を差し替えたノードは名を挙げられる。テイカーの依頼は、メイカーの値付け規則とまったく同じように束縛される。これを走らせて、二つの不具合が見つかった。生成器が、ノードに予測できる fixture（テスト用の固定データ）の係数を出していた。体の設定ミスによって、監査が正直な実行で 7 ノード全員を有罪にしていた。後者は、説明責任の仕組みとして最悪の壊れ方である。

第 5 段の実装: ノードが 9 台あれば復号器で足りる

Reed–Solomon が e 個の誤りを訂正できる条件は、n − d ≥ 2e + 1 である。次数削減前の積は d = 2t で、頑健性が求めるのは e = t。よって n ≥ 4t + 1 が要る。n=7、t=2 では積について訂正できる数は 1 で、一つ足りない。n=9 なら 2 で足りる。t < n/3 は、分割、チェックポイント、参加者排除が必要になる線である。t < n/4 は、復号器だけで足りる線である。この二本の線の間を埋めるのが、GSZ の仕組みの全体である。

載せた先は配備中のプロトコルではなく ATLAS（Damgård–Nielsen）である。中継付きの king（復元を一手に担う参加者）と、ランダムな二重シェア分散が、すでにそこにあるからである。「整合しているが間違っている」値が生まれる場所は king であり、king は取り除ける。マスクされた積は秘密ではないので全員に送ってよく、各参加者が自分で符号語を復号する。誰の言葉も信用しなくてよい。

中央の四行が第 5 段である。しかも配備中のものより安い。乗算 1 回・参加者 1 人あたり 18.222 個の元で済み、n=7 の名指し付き malicious Shamir は 64.236 個である。ラウンド数も少ない（king ありの 9 に対して 8）。二台の機械、二つの独立したビルドで計測した。頑健でない部分は三つある。二重シェア分散（前処理。入力を消費しないので abort してよい）、出力の開示、そして入力段階。このうち入力段階こそが重要である。予測は 1.6× 低かった。送信側の通信量だけを数えたモデルによる予測で、食い違いの原因はまだ切り分けていない。帯域以外にかかる費用は、参加する機関が二つ増えることである。リスク一覧はこれを最も重い制約としている。n=7 のまま T=1 に下げても n ≥ 4T+1 は満たし、wire（通信路）上の費用はゼロである。しかしプライバシーの閾値も下がり、結託した任意の 2 ノードがすべての注文を復元できてしまう。市場が選べる案ではない。

honest majority がまったくなかったら

もう一つの手は、代わりに n−1 の不正に耐えることである。これは厳密に強い性質である。同じ傾きのハーネスで計測した。

答えは二つに割れる。オンライン段階では dishonest majority の方が 2.3× 安い。加法的シェア分散の開示は、n がいくつでも、指定された一者を経由する 1 往復で済むからである。総量では 558× 高い。triple の生成には参加者の一対ごとに紛失通信（oblivious transfer）が要り、費用は参加者 1 人あたり相手の数に比例し、全体では二乗になるからである。malicious 安全性を諦めても取り戻せない。費用を決めているのは、攻撃者の振る舞いのモデルではなく、不正者が何人までかのモデルである。実際にかかる費用は帯域ではない。頑健性は「高価」から「不可能」になる。それに、7 者で dishonest majority を配備する者はいないだろう。だから正直な比較は、7 者 Shamir と 2 者 MASCOT の比較である。これはおおよそ Prime Match の形であり、性能ではなく統治の判断になる。それでも、2 者 MASCOT は見積 1 件あたり全体で 475 MB の通信を動かす。現行は 17.9 MB である。

テイカーも参加者の一人である

テイカーの不正は形が違う。約定させる気のない依頼を出し、価格の範囲を無償で読み取る。対策は、暗号で強制できるようにした市場規則である。テイカーは依頼とともに受入水準 L を commit（値を固定して隠す）する。回路は従来どおり勝者を計算し、そのあと比較を 1 回行い、fill × key をトレーダーのマスクの下で返す。水準に達した、または水準より有利な見積は、提示ではなく約定になる。約定なしの場合、テイカーはマスクを外してゼロを得る。テイカーが知るのは約定ビットだけで、他は何も知らない。約定ビット自体もマスクされる。約定ビットが公開だと、cover slot（見せかけの枠）がすべて cover だと分かってしまうからである。

これで探りが止まるわけではない。探る側は L を下から上げていき、毎回「これより悪い」ことを無償で知れる。約定という代価がかかるのは、市場が自分の示した水準より良いと知ることである。これは、板に置かれた指値注文がすでに明かしていることとまったく同じである。したがって、水準を拘束する RFQ の漏れは連続指値板を超えない。むしろ L が表示ではなく commit されるぶん少ない。二分探索をすれば約定の代価がかかる。約定の比較をトーナメントの最終層に折り込むと、費用は +9 ラウンドから +2 ラウンドに下がり、通信量は +3.35% 増えた。深さを幅で買ったからである。未解決の点が二つある。拘束には、テイカーが拒めない決済が要るが、定足数は決済の根拠となるビットを見られない。そして正直なテイカーは last look（約定前の最終確認の機会）を失う。

決まっていないこと

• GSZ はここには実装しておらず、実行もしていない。§第 5 段は GSZ なしで、n ≥ 4T+1 のもとで出力保証に達する。ただしその費用は、GSZ の漸近的な費用の方が安い。
• ここでの第 5 段は乗算についてであり、プロトコル全体ではない。
• 第 4 段を honest majority で実現する費用は不明である。Rivinius et al. は dishonest majority での費用を 11× から 20× と計測したが、t < n/3 の Shamir に対応する数値は見当たらない。
• 掲示板は仮定であり、実装していない。公開監査可能性とブロードキャスト・チャネルの両方が掲示板を必要とする。しかしこのリポジトリにあるのは 1 台の機械上で遅延を模した代理であり、共有の追記専用ログを持つ 7 拠点ではない。
• 入力側の参加者の不正には、ここでは何も対処していない。値付け規則に commit した後でそれを争うメイカーは、契約の問題である。