監査の仕組み

中心にある性質は二つである。依頼があったかどうかも、それがどの市場向けかも、外からは見分けられない。それでも、計算ノードの不正は検出できる。ここにあるすべての数値は計測 JSON から生成しており、手で打ったものは一つもない。

出典: qomm/AUDIT.md · artifact（計測の成果物）: audit_slots.json, transport.json, quote_proof.json, three_times.json, multi_asset.json, rounds.json, stages.json, rounds_by_channel.json, prep_split.json

カバー・スロットと実スロットは同じ痕跡を残す

秘密の is_real ビットが回路に入る。回路がこのビットで分岐することは決してない。回路の形は変わらず、このビットが決めるのは、メイカーの状態を動かすか（実スロット）動かさないか（カバー・スロット）だけである。

コンパイラの統計、実行時のラウンド数、送信バイト数がすべて一致する。壁時計時間（実際にかかった時間）の差 0.0103 s は、同じ条件を繰り返したときに見られるばらつき 0.0852 s より小さい。ここで測ったのは MPC ジョブの痕跡である。利用者からノードまでの経路は、下で別に計測する。

三種類の監査と、不正の性質で決まる bond（保証金）の没収額

計算の正しさは、スロットごとの結果のダイジェストで示す。矛盾する署名は、2 枚の受領証で示す。無応答は、期限と不在で示す。すべてのノードが毎スロット受領証を出す、という規則が必要である。実際の依頼があったかどうかにかかわらず、である。この規則がなければ、「応答しなかった」ことを第三者に示せない。資格のあるメイカーの除外は、メイカーの集合を事前に一つのダイジェストに固定しておくことで捕まえる。回路の中でハッシュは計算しない。

すべて検出し、見逃しはなく、正直なノードへの誤った非難もない。二重署名は、それだけで言い逃れのできない証拠なので最も重い。受領証の欠落は、正直なノードにも起こるので最も軽い。重みは相対的である。bond の絶対額は、不正で得られる額の見積もりから決まり、それは配置側の判断である。

利用者からノードまで: 一定周期と中継ホップ

• 一定周期。注文があってもなくても、毎スロット、各ノードへ同じ長さのメッセージを 1 通送る。必要なときだけ話す設計では、話すこと自体が告知になってしまう。
• 加法的秘密分散。端末を出る前に、ノード 1 台につき 1 つのシェア（秘密分散の断片）に分ける。シェア 1 つだけを見ても、一様な雑音と区別できない。
• 中継ホップ。各ホップはメッセージをスロット境界まで保持し、順序を混ぜ直す。最初のホップは送信者のアドレスを知る。二番目のホップは最初のホップしか知らない。

注文を送った利用者と送らなかった利用者は、同じバイト列を送る。ノードが見るバッチは、誰がどれだけ活発だったかにかかわらず同じである。各ホップは実際のソケットで約 4.4 ms かかる。ホップが 1 つだと中継が利用者の IP を見られるので、2 つ以上を推奨する。中継が自分の担当ノードと結託すれば、その 1 つのシェアは送信元と連結できる。注文そのものの復元には、すべてのノードの結託が要る。

計算が正しかったことの証明

シグマ・プロトコルの応答は witness（証明者だけが知る秘密の値）について線形である。そのためノードの定足数は、誰も witness を丸ごと持たないまま、普通の検証器が受理する証明を組み立てられる。汎用 SNARK にはこの構造がない。協調 SNARK（collaborative SNARK）が証明器全体を MPC の中で走らせるのは、そのためである。証明する命題は次のとおり。commit 済み（値を隠したまま固定済み）の値付け規則を commit 済みの依頼に適用すると、各メイカーの key_i が得られる。開示された勝者はその最小値である。最小性と所属を合わせると、返された価格が最良であることをちょうど言っている。

証明と検証の時間はメイカー数に線形である。60 秒の開示や 1 秒の RFS 更新には収まるが、200 ms 未満には収まらない。六つの偽造を試し、すべて拒否された。勝者を最小でないメイカーに入れ替える。勝てないはずの期限切れメイカーを勝たせる。誰も応じられない依頼に「no quote」で答える。勝ったメイカーを無効化する。最小性証明をメイカー間で入れ替える。偽の勝者に最小性を付ける（範囲外の値 −1）。

共同で組み立てるのは、Pedersen commitment の開封 1 件である。7 ノードに配られたスカラーから、その定足数でシグマ証明 1 本を組む（定足数 3 で 4.8 ms、7 で 20.2 ms）。quote proof（見積が規則どおりに計算されたことの証明）の範囲証明は、この線形性を持たない。ビットの取り出しには値そのものが要るからである。したがって共同組み立ての数値は、完全に組み立てた証明の下限である。閾値未満では、組み立てた証明は検証を通らない。それも確認している。

証明器のシェアは回路のシェアである。回路がシェアを保持するようになる前は、シェアは独自の経路で証明器に届いていた。計算とたまたま一致する数についての証明は、計算についての証明ではない。これは、設計が示さずに主張していたものの中で最大だった。いま各ノードは勝者のシェアを書き出し、永続化層がそれを読み戻す。3 台からなる部分集合はどれも同じ値に一致し、2 台では復元できず、1 ビット反転すれば気づく。束縛のページがこの話の続きである。

値付け規則を言語として書く

メイカーの規則は、許された入力だけを参照しなければならない。利用者の身元やアドレスを値付けの入力に使ってはならない。出力の範囲は有界でなければならない。これらはプログラムの静的な性質なので、証明ではなく検査器の仕事である。命令は + − ×、比較、and、そして min max clamp signed である。除算、ループ、添字、属性アクセスはない。文法は借りずに書き下してあるので、この部分集合はパーサが受理するものそのものであり、それ以上ではない。

# the price rule a market maker registers, and nothing else
param ask_level[-2000,2000], spread[2,400], slope[0,16], invcoef[0,8], maxqty[1,1000]
param expiry[0,1000000], active[0,1], use_ref[1,1]
state inv[-4000,4000]
input qty[1,400], ref_mid[90000,110000], now[0,1000000]

ask      = use_ref * ref_mid + ask_level + slope * qty + invcoef * inv
bid      = use_ref * ref_mid + ask_level - spread - slope * qty + invcoef * inv
eligible = (qty <= maxqty) and (expiry > now) and (active == 1)

買値と売値が交差しないことは、検査ではなく恒等式で保証される。ask − bid = spread + 2·slope·qty ≥ 2 なので、交差した見積は書けない。登録できる形は二つある。参照価格との差で表す形と、絶対値で表す形である。絶対値の形は、使える基準がない市場向けである（社債には、差分の基準になる連続的な仲値がない）。どちらを使うかはメイカーの use_ref ビットが選ぶ。検査器は、宣言した値を値付けに使わない規則を拒否する。

検査器が証明なしに導くものは次のとおり。ask、bid、eligible の出力区間、秘密値についての最大次数（2）、回路が必要とするビット幅（どちらの形でも 19）。同じ宣言から、回路の幅と監査の内容の両方が出る。同じ木を一回歩けば、値と証明が一緒に出る。ビット証明 3 本、積の証明 12 本、範囲証明 11 本で、Ed25519 上で構築 28.9 ms、検証 32.2 ms である。規則に項を足すと対応する証明が増えることを、テストが確かめる。状態更新の規則も同じ言語で書き、その監査は約 30 ms である。

依頼がどの市場向けかを隠す

MPC ジョブを市場ごとに分けると、どのジョブが走ったかで市場が知れてしまう。そこで一つの回路がすべての市場を担い、資産を秘密にしたまま参照価格を選ぶ。ref = Σ_a (asset == a) · REF_TABLE[a] は、秘密ビットと公開定数の積なので、乗算の費用はかからない。ラウンド数は資産 1 から 32 まで 64 で変わらない。増えるのは通信量だけで、資産 1 つあたり約 0.04 MB である。試した 8 資産にわたってラウンドとバイト数は同一で、答えだけが違う。ある資産を扱うメイカーが少ないと、答えは「no quote」になる。それ自体が市場の薄さの手がかりになる。回路は同じ形で走り、番兵値（sentinel、該当なしを表す決まった値）を返す。

三つの時刻: 値付け完了、証明完了、決済可能

監査付きの request-for-stream は、1 秒のスロットに収まらない。証明を完成させ、受領証の定足数に達するまでの時間は、遅延に依存しない。配置を近づけても縮まない。手当ては二つある。メイカー数について軽い証明にするか、更新間隔を計測値に合わせて設定するかである。

ラウンドはどこで消え、何が動かすか

開封のチャネル、すなわち比較の連鎖は、malicious（不正な参加者を想定する）でも semi-honest（手順は守るが覗く参加者を想定する）でも、Shamir で 49 ラウンドである。malicious 安全性を落とすと、それ以外のすべてからラウンドが減り（64 から 56）、バイト数は 3.53× 減る。安全性モデルの代価は帯域で払う。遅延はどちらにしても回路の深さに払う。各メイカーの市場を公開し、期限の判定を登録時の監査へ移すと、通信量は 45% 減る。ラウンドは 70 から 69 に動くだけである。前処理をディスクに置くと、残るオンライン段階は、参加者 0 のバイト数の 16%、ラウンドの 71% である。ただしこれは trusted dealer（前処理を配る信頼できる第三者）で計測したものである。trusted dealer はどの配置でも動かせない。したがって確定するのはオンライン段階の大きさであって、それを作る費用ではない。

ラウンドはジョブの性質であって、依頼の性質ではない。同じ比較の層を Q 件の依頼で共有すれば、見積 1 件あたりのラウンドは Q 分の 1 になる。これは一定周期のスロット設計にちょうど合う。これは処理量の話であって、利用者 1 人の待ち時間の話ではない。利用者の待ち時間の上限はスロット周期で決まり、Q は到着頻度に合わせて選ぶ。

計測済み・実装済み・対象外