算術回路の作り方と、壊し方

下の 2 層があってもいちばん上が間違っていれば、「嘘の主張に対する完璧な証明」ができあがる。 Week 1 が土台と呼ばれるのはそういう意味。

ZK / zero-knowledge proof

ゼロ知識証明

秘密を渡さずに、条件を満たしていることだけを相手に納得させる技術。 「ゼロ知識」は相手に知識を一切与えないという意味で、 「証明」はそれでも嘘はつけないという意味。この 2 つが同時に立つのが肝。

例: 身分証を見せずに「20 歳以上」だけを示す。残高を見せずに「足りている」だけを示す。
今回なら: 資格 (2, 3, 1) を明かさずに「granted = 1 にできる」ことだけを示す。

MPC / multi-party computation

秘密計算（マルチパーティ計算）

複数人が秘密を持ち寄り、誰も他人の値を知らないまま、計算結果だけを全員で得る技術。 値を意味のない断片（シェア）に割って配り、断片のまま計算する。 断片を 1 つ見ても何も分からないが、規定の人数分そろえば元に戻る。

例: 3 人が年収を明かさずに、平均年収だけを知る。
今回なら: 人事部が role、セキュリティ部が clearance、拠点管理が region を持ち、 互いの値を知らないまま granted を出す。

FHE / fully homomorphic encryption

完全準同型暗号

暗号化したまま計算できる暗号。 「準同型」は構造を保つという意味で、暗号文どうしを操作すると 中身にも同じ計算が反映される。「完全」は何回でも、どんな組み合わせでもできるということ。 計算する側は最後まで中身を知らない。

例: 暗号化した医療データをクラウドに解析させる。クラウドは何も学ばない。
今回なら: 暗号化した資格を送り、暗号のまま判定した暗号化 granted を受け取る。

signal

信号

回路に出てくる変数。値は有限体 F_p の元。今回は 7 本（資格 3 本 + フラグ 3 本 + 出力 1 本）。

constraint

制約

「この式は 0」という条件。今回は 8 本。回路の安全性は、この 8 本で全部決まる。

witness

witness（証拠）

7 本すべてに値を入れた割当。prover が「これで全制約を 0 にできる」と主張して差し出すもの。

1. 巨大な素数 p で割った余りの世界

   p = 21888242871839275222246405745257275088548364400416034343698204186575808495617（BN254 の scalar field）。 足し算も掛け算も、やったあとに p で割った余りを取る。数がいくら大きくなっても、この 1 本の帯の中に収まる。

   なぜ余りの世界なのか: 暗号は「決まった大きさの数」を扱う必要があるから。 実数のように無限に伸びる値は、暗号の道具に載せられない。

2. 足す・引く・掛ける・割るが全部できる（＝体）

   p が素数なので、0 以外のどの元にも逆数がある。負の数も普通に扱える （−6 は p − 6 と同じもの）。

   実務上の注意: 一方で「大小比較」と「範囲」は自然には存在しない。 x < 8 のような条件は、それ専用の制約（range proof）を書かないと表現できない。 今回は許可リストが値を 2〜3 個に固定するので、範囲の心配が要らない設計になっている。

3. 零因子がない — これが今回の主役

   a · b = 0 なら、a = 0 か b = 0 のどちらかが必ず成り立つ。 「どちらも 0 でないのに掛けたら 0」は起きない（整数と同じ感覚でよい）。

   ここから何が言えるか: f · (何かの積) = 0 という制約を書いておけば、 f ≠ 0 だと分かった瞬間、積の方が 0 でなければならないと断言できる。 許可リストの強制は、まるごとこの性質の上に乗っている。

1. 暗号がすり抜けさせられるのは「構造がもともと持っている演算」だけ

   準同型（homomorphism）とは構造を保つ写像のこと。 暗号化を E とすると、E(a) ⊕ E(b) = E(a + b) のような性質が成り立つとき、 暗号文のまま計算ができる。

   ここが肝: 保てるのは、その構造がもともと持っている演算だけ。 暗号が新しい操作を発明することはできない。すでにある演算を、暗号の壁の向こう側に そのまま持ち越すのが準同型だから。

2. そして、体や環という構造には演算が 2 つしかない

   平文が住んでいるのは 環（足し算と掛け算ができる世界）か 体（さらに割り算もできる世界）。 そして環の定義に書かれている演算は、加法と乗法のちょうど 2 つ。それだけ。

   だから比較は「直接には」運べない: 「<」は環の公理に入っていないので、 準同型で保ちようがない。「+ と × だけ」は暗号の都合ではなく、代数の定義そのもの。 （欲しければビットに分解して + と × から組み立て直す。 Week 5 で扱う TFHE の Programmable Bootstrapping は、その組み立てを暗号側で肩代わりして 暗号文に任意の表引きを適用できるようにする技術——底では同じ 2 つの演算の上に立っている。）

3. 実例 — 指数法則を借りるだけで、加算が 1 つ手に入る

   平文 m を g^m の形で隠す方式なら、暗号文どうしを掛けると g^a · g^b = g^(a+b)。平文の足し算になっている。 教科書的な RSA なら m₁^e · m₂^e = (m₁m₂)^e で、こちらは平文の掛け算。

   何をしているのか: どちらも新しい操作を作ってはいない。 指数法則というすでにある構造をそのまま借りているだけ。 そして片方しか手に入らない。+ と × を任意の回数こなせる方式（FHE）は 2009 年の Gentry まで作れなかった——回数制限つきで両方持つ方式はそれ以前からあったが、 制限を外すのがそれほど難しかった。

4. 比較は、原理的に存在できない

   有限体には、+ と × と両立する大小関係が存在しない。 仮に 0 < 1 と決めると、両辺に 1 を足して 1 < 2、 さらに足して……と続き、いつまでも 0 に戻れないはずだが、 有限体では p 回足すと 0 に戻ってしまう。順序と矛盾する。

   実務での意味: 「x < 8」という順序は体に備わっていないので、そのままでは書けない。 書きたければ + と × から組み立て直す —— x をビットに分解して各ビットに b·b−b=0 を課し Σ bᵢ2ⁱ = x で繋ぐか、範囲が狭いなら (x−0)(x−1)…(x−7) = 0 と積で書く。 range proof が高価なのはこれが理由で、今回の課題が「許可リスト方式」なのも、 それを避けた設計になっている。

5. MPC でも、まったく同じ壁がある

   秘密分散では、各人が持つシェアを足すだけで秘密の和のシェアになる（通信ゼロ・無料）。 掛け算もできるが、多項式の次数が倍になるので次数を戻すための通信が要る。

   だから MPC のコストは乗算ゲートの数で測る。 加算は無料、乗算は有料、 それ以外の操作はそもそも定義されていない。ZK とは技術がまったく違うのに、 使える演算が同じ 2 つに落ち着くのは、根が同じ代数だから。

6. ZK の検証も、多項式でなければ成立しない

   証明系は「全制約が満たされている」を「ある多項式が恒等的に 0」に翻訳し、 ランダムな 1 点で評価するだけで検査する。 次数 d の 0 でない多項式は零点を高々 d 個しか持てないので、 でたらめに選んだ点でたまたま 0 になる確率は無視できるほど小さい。

   この「1 点で全体を代表できる」性質は多項式だけのもので、 多項式は + と × で作られる。だから制約は多項式でなければならない。 SNARK 系の検証がミリ秒で終わる理由は、ここまで遡る。

1. 資格を入力信号として宣言する

   cs.input("role", role) のように、名前を決めて 3 本置く。

   なぜ名前が固定なのか: 採点器は名前で信号を探す。ここが違うと、回路が正しくても評価されない。 現実でも、証明系は「どの信号が公開入力か」を名前や位置で識別する。

2. フィールドごとに補助フラグを 1 本ずつ足す

   f_role, f_clearance, f_region。 「このフィールドは許可リストに入っている」という主張を表す信号。

   なぜ補助信号が要るのか: 3 条件の AND を 1 本の巨大な式で書くと次数が跳ね上がり、 実際の証明系では扱えない。中間結果に名前を付けて次数を下げるのは回路設計の基本動作で、 Circom を書くときも同じことをする。

3. フラグをビットに縛る（部品①を 3 本 + 出力用に 1 本）

   f · f − f = 0 を、3 つのフラグと granted に課す。

   なぜ granted にも要るのか: granted は外に出る出力だから。 ビットに縛らなければ granted = 6 のような値も許され、 「1 かどうか」で判定する検証側が壊れる。

4. リンクを 3 本張る（部品③）— ここを 1 本でも落とすと壊れる

   f_role · (role−2)(role−5)(role−6) = 0 を、3 フィールドすべてに。

   落とすとどうなるか: そのフィールドはフラグと切り離され、 「リストに入っていないのにフラグ 1」が成立してしまう。 これが今回の Part B で突く穴そのもの。下のラボでスイッチを切れば実物が見られる。

5. AND を取って出力にする

   granted − f_role · f_clearance · f_region = 0。 フラグがビットなら、この積は「3 つとも 1 のときだけ 1」になる。最後に cs.set_output(granted)。

   これが健全性の要: granted = 1 を主張した瞬間、積が 1 になり、 3 つのフラグはどれも 0 でなくなる。すると 3 本のリンクが一斉に発動し、 3 フィールドすべてを許可リストに縛りにいく。ここまでが一本の論理の鎖で、 どの環が欠けても嘘の証明が通る。

6. 信号と制約の「形」を入力値に依存させない

   if role in ROLE_OK: で制約を出し分けてはいけない。値は入力ごとに変わってよいが、 式の集合はどの資格でも完全に同じでなければならない。

   なぜそんな制限が: 現実の回路は一度コンパイルされ、全員が同じものを使う。 形が秘密で変わるなら、形そのものが秘密を漏らすし、verifier は検証すべき式を固定できない。 採点器の test_structure_is_value_independent はこれを見ている。

# (1) フラグはすべてビット
cs.assert_zero(f_role * f_role - f_role)
cs.assert_zero(f_clearance * f_clearance - f_clearance)
cs.assert_zero(f_region * f_region - f_region)
cs.assert_zero(granted * granted - granted)

# (2) メンバーシップリンク（3 フィールドすべてに必要）
cs.assert_zero(f_role      * _membership_product(r, ROLE_OK))
cs.assert_zero(f_clearance * _membership_product(c, CLEARANCE_OK))
cs.assert_zero(f_region    * _membership_product(g, REGION_OK))

# (3) granted は 3 フラグの AND
cs.assert_zero(granted - f_role * f_clearance * f_region)

最後の行がこの課題の主題。制約を書き忘れた回路は、正直に使っている限り完璧に正常動作する。 テストも通る。攻撃されて初めて分かる。だから「壊れているかを自分から探しにいく」道具（＝採点器の全探索）が要る。

数字の出どころ: region のリンクを外すと region が 8 通りすべて自由になり、 role と clearance は許可内に縛られたままなので 3 × 3 × 8 = 72、 うち正当な 18 を引いて 54。role のリンクを外した場合は 8 × 3 × 2 = 48 から 18 を引いて 30。 許可リストが狭いフィールドほど、リンクを失ったときの被害が大きい。

1. 回路を読んで、無い制約を探す

   challenge.py には 7 本しか制約がない。自分が組んだ 8 本と突き合わせると、 f_region · (region−1)(region−6) = 0 だけが無い（コメントとして残っている）。

   探し方のコツ: 「何が書いてあるか」ではなく「対称性が崩れている場所」を見る。 3 フィールドを同じ形で扱っているはずの回路で、1 つだけ扱いが違えば、そこが穴。

2. その 1 本が何を守っていたかを言葉にする

   守っていたのは「f_region = 1 なら region ∈ {1, 6}」という含意。 無いということは、f_region は region の値と完全に無関係になれる。

   残っている制約を確認する: f_region をビットに縛る制約と AND の制約は残っている。 だが、どちらも region の値そのものには一切触れていない。 誰も region を見ていない——これが攻撃可能である証拠。

3. 正直な witness から出発する

   challenge.honest_witness(2, 3, 1) で、正当な資格の割当を作る。 これで 7 本の信号名がすべて正しく揃う。

   ハマりどころ: challenge.py のフラグ名は f_clearance であって f_clear ではない。名前を 1 つでも間違えると、採点器は制約を評価する前に 「attack() の witness に足りない信号」として不合格にする （DSL の _resolve を直接叩いた場合は KeyError）。 正直な割当から作れば、この事故は起きない。

4. 縛られていない信号だけを書き換える

   region を許可リスト外の 0 に。f_region は 1 のまま。 granted は 1·1·1 = 1 のまま。role と clearance には触らない —— こちらのリンクは生きているので、動かせば即座に違反になる。

   成立の確認: ビット制約 4 本 ✓／role・clearance のリンク 2 本 ✓（値は正当なまま）／ AND ✓。7 本すべて 0 で、granted = 1、しかし資格 (2, 3, 0) は不正。 本来入れない人が入れた。

witness = challenge.honest_witness(2, 3, 1)
witness["region"]   = 0   # 許可リスト {1,6} の外
witness["f_region"] = 1   # 止める制約が無い
witness["granted"]  = 1   # 1·1·1 = 1
return witness

「Noir は Rust で書ける」はほぼ当たり。ただし正確には Rust に似た独自言語で、 ACIR という中間表現に落ちるため証明系を差し替えられる。 本当に Rust そのものを書くのは halo2 / arkworks（回路をコードで組む）と zkVM（普通のプログラムを書く）。

// <== は「代入 ＋ 制約」
inter <== in1 * in2;

// <-- は「代入だけ」。制約は作られない
bit <-- (in1 >> 0) & 1;
bit * (bit - 1) === 0;   // ← 手で書く

// Safety: 下の assert で out を縛っている
let out = unsafe { u72_to_u8(num) };

let mut reconstructed: u72 = 0;
for i in 0..8 {
    reconstructed += (out[i] as u72 << (56 - 8*i));
}
assert(num == reconstructed);  // ← ここで初めて縛られる