Back to blog

制約を 1 本書き忘れた回路は、誰でも通れる――算術回路とアンダー制約

zk-tokyo Advanced Cryptography Program 2026 の Week 1 で算術回路を扱いました。回路に if が書けない理由、制約を 1 本落とすと権限のない資格が 54 通り通ってしまうこと、そして Circom や Noir で同じバグがどう現れるかをまとめます。実際に回路を壊せる自習ノートも公開しました。

zk-tokyo のAdvanced Cryptography Program 2026を受講しています。Week 1 のテーマは算術回路でした。

課題を解いていて、ゼロ知識証明そのものよりも先に理解しておくべきことがあると気づきました。回路は普通のプログラムとまったく違う書き方をします。その違いが、そのまま脆弱性の形になります。

この記事はその要点をまとめたものです。手を動かせる自習ノートも別に用意しました。

回路には if が書けない

ゼロ知識証明や秘密計算がやりたいのは、中身を見ずに計算することです。値は暗号化されていたり、複数人に分割されていたりします。

このときif (role == 2)は書けません。分岐先を選ぶには中身を見る必要があるからです。さらに、どちらに進んだかという事実そのものが秘密を漏らします。

そこで、あらゆる計算を足し算と掛け算だけの式に翻訳します。この 2 つは、暗号化されたままでも実行できる操作だからです。判定結果は「この式の値が 0 かどうか」で表します。true と false という型は存在しません。

こうして出来上がった「0 になるべき式の集まり」が算術回路です。

回路は計算しない。答え合わせをする

もう 1 つ、普通のプログラムとの決定的な違いがあります。

回路は入力から答えを計算しません。証明者が答えを先に主張して、回路はその主張が嘘でないことだけを確かめます。

分かりやすい例が割り算です。回路に除算ゲートはありません。そこで証明者に「1/x の答えは y です」と主張させ、回路はx * y - 1 == 0という制約を 1 本置くだけにします。難しい計算は証明者にやらせ、検証側は掛け算 1 回で検算します。

Week 1 の課題も同じ形でした。アクセス制御の判定で「役職が許可リストに入っているか」を回路は計算しません。証明者がフラグを 1 と主張し、回路は「その主張が嘘なら 0 にならない式」を置くだけです。

# 普通のプログラム。計算して決める
if role in {2, 5, 6}:
    f_role = 1
else:
    f_role = 0

# 回路。主張させて、嘘を禁じる
f_role * f_role - f_role == 0
f_role * (role - 2) * (role - 5) * (role - 6) == 0

下のコードには「f_role を 1 にせよ」と命じる行がどこにもありません。値を入れるのは証明者の自由で、回路にできるのは禁止だけです。

だから、書き忘れがそのまま通る

ここから回路に固有のバグが生まれます。

主張ベースの設計なので、その主張が嘘でないことの確認を書き忘れると、嘘がそのまま通ります。普通のプログラムなら計算を書き忘れれば動きません。しかし回路では、確認を書き忘れても正直に使っている限り完璧に正常動作します。テストも通ります。

Week 1 の課題では、わざと制約を 1 本抜いた回路が用意されていました。私は自分で解いた回路からも同じ 1 本を抜いてみました。すると採点器が反例を出してきます。

回路がアンダー制約です。authorized でない資格
role/clearance/region=(2, 3, 0) でも granted=1 にできます。

regionの許可リストは{1, 6}なので、region = 0は本来通ってはいけません。それでもフラグを 1 のまま置けてしまい、アクセスが許可されます。誰もregionの値を見ていないからです。

どの制約が効いていたのか

8 本の制約を 1 本ずつ外して、権限のない 494 通りの資格のうち何通りが通ってしまうかを数えました。

外した制約通ってしまう不正資格
フラグをビットに縛る 4 本0
role のメンバーシップリンク30
clearance のメンバーシップリンク30
region のメンバーシップリンク54
AND（出力の定義）494

被害の大きさは、その 1 本が守っていた自由度で決まります。regionの許可は 2 個しかないため、リンクを外すと自由になる値が 6 通りに広がります。出力の定義を外すとフラグ全部が無意味になり、全滅します。

面白いのはビット制約です。外しても採点器を破れません。granted に 1 を主張した時点で積が 1 になり、フラグはどれも 0 でなくなるため、残りのリンクが効き続けるからです。

ただし消してよいという意味ではありません。採点器が反例を出さないことと、安全であることは別です。今回たまたま健全だっただけで、フラグを他の回路と共有した瞬間に前提が崩れます。

実務でも同じ形で現れる

この課題は学習用の小さな DSL でしたが、バグの形は実際のツールでも変わりません。

Circomでは、代入と制約が別の記号になっています。<==は代入と制約の両方を行いますが、<--は代入だけで制約を作りません。公式ドキュメントのレンジプルーフの例ですら、<--の直後にbits[k] * (bits[k] - 1) === 0;を手で書いています。この 1 行を忘れると、今回と同じ穴が空きます。

Noirはもう少し親切です。unconstrained関数の戻り値は制約されていないため、呼び出し側でunsafeブロックに包み、// Safety:コメントで理由を書き、自分でassertして縛ることをコンパイラが要求します。

どちらも構造は同じです。重い計算は証明者にやらせ、回路は答え合わせだけをします。縛り忘れたらそのまま通るというリスクの形も同じです。

持ち帰った問い

Week 1 で得たものを 1 つに絞ると、次の問いになります。

この信号を縛っている式は、どれか。

答えられない信号が 1 本でもあれば、そこが次の穴になります。証明系が保証してくれるのは「制約を満たす witness を知っている」ことだけで、その制約が仕様と合っているかは何も言ってくれません。健全な証明系と、制約が足りない回路を組み合わせると、偽の主張に対する完璧な証明ができあがります。

自習ノートを公開しました

読むだけでは定着しないので、ブラウザ内で回路を壊せるノートを作りました。

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

制約 8 本にそれぞれスイッチがあり、切るとその 1 本を書き忘れた回路になります。権限のない 494 通りの資格を総当たりして、何通り通ってしまうかをその場で計算します。上の表は、この機能で実測した数値です。

理解度を確かめる検問モードも入れました。あなたが検証者の席に座り、提出された witness と回路を審査します。問題は毎回その場で生成されるので、答えを覚えても意味がありません。

単一の HTML ファイルで、外部への通信はありません。数値はすべてブラウザ内で計算しています。