誕生日を見せずに年齢を示す
算術回路は、秘密についての主張を、すべて成り立つべき小さな和と積の集まりとして書いたものです。SNARK は、それらをすべて成り立たせる値を知っている、という短い証明です。
こうすれば、個人のデータを見ずに、18歳以上であることや、リストに載っていることを確かめられます。
このレッスンのゴール
メモ
秘密についての主張を制約として書き、証人がそれを満たすかを確かめることができる。
キーワード
| ことば | いみ | れい |
|---|---|---|
| 体 | 素数で割った余りの整数で、足し算と掛け算ができるもの | 97 で割った余り |
| ゲート | 1つの和か積と、その出力 | |
| 証人 | 秘密も含めた、すべての線の値 | |
| 制約 | 証人が満たさなければならない式 | |
| SNARK | 証人があることを示す短い証明で、すぐに確かめられるもの |
学生が入力するセルは、このプレビューでは空白です。
主張はゲートの並びになる
「x × x + 2 × x が48になる x を知っている」という主張を考えます。1つのことだけをする手順に分けます。x2 = x × x、two_x = x + x、out = x2 + two_x です。1つ1つの手順がゲートです。
証明者は、すべての線に値を入れます。これが証人です。公開する部分は out = 48 です。どの値も体の中にあり、ここでは97で割った余りです。
証人をゲートで確かめる
docker exec jupyter python3 steps/constraints.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
ラボの表示を読む
witness は証人、gate はゲート、first bad gate は最初に失敗したゲートです。ラボは x2 を x_squared と書いています。
x = 6 のとき、証人は x_squared = 36、two_x = 12、out = 48 で、最初に失敗したゲートは -1、つまり1つもありません。すべてのゲートが成り立ちます。x = 5 で out を48と主張すると、最後の足し算のゲート2で失敗します。25 + 10 は35だからです。うその証人は、すべてのゲートを満たせません。
試そう: 3乗のゲート
F = 97 # 和も積もすべて 97 で割った余りで計算します
# 主張: 「x * x * x + 2 * x = 33 になる x を知っている」。33 は公開です。
gates = [
["mul", "x", "x", "x2"],
["mul", "x2", "x", "x3"],
["add", "x", "x", "two_x"],
["add", "x3", "two_x", "out"],
]
x = 3
w = {"x": x, "x2": x * x % F, "x3": x * x * x % F, "two_x": 2 * x % F, "out": 33}
for gate in gates:
a = w[gate[1]]
b = w[gate[2]]
if gate[0] == "mul":
value = a * b % F
else:
value = (a + b) % F
print(gate[0], gate[1], gate[2], "->", gate[3], "成り立つ:", value == w[gate[3]])
# x = 3 を x = 4 に変えて (out は 33 のまま)、もう一度実行しましょう。どのゲートが失敗しますか。
範囲の確認はビットでできている
秘密の x が0から15の間にあることを見せずに示すには、証明者は4つのビットを渡します。2種類の制約で確かめます。まず、各ビット b は b × b = b を満たさなければなりません。これを満たすのは0と1だけです。次に、1、2、4、8の重みをつけたビットの合計が x にならなければなりません。
ラボは11を 1, 1, 0, 1 として確かめ、True でした。2のビットは最初の決まりを破り、False でした。
例: ゲートを制約として書く
| ゲート | 制約 (左 × 右 = 出力) | x = 6 のとき |
|---|---|---|
| x2 = x × x | x × x = x2 | 6 × 6 = 36 |
| two_x = x + x | (x + x) × 1 = two_x | 12 × 1 = 12 |
| out = x2 + two_x | (x2 + two_x) × 1 = out | 48 × 1 = 48 |
学生が入力するセルは、このプレビューでは空白です。
SNARK はどこに入るか
ここまで検証者は、証人を見て確かめていました。これでは秘密が見えてしまいます。SNARK を使うと、証明者は、そのような証人があることを検証者に納得させられます。証明は数百バイトで、回路の大きさに関係なく、すぐに確かめられます。
Noir や Circom などの言語は、主張をこのような制約に変えます。このラボではそれらを動かしません。証明器がないので、回路は Python のままです。
circuit.py の関数を一覧にする
docker exec jupyter grep -n def circuit.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
よくある間違い
注意
「SNARK は主張がまともであることを証明する」と考える人がいます。証明するのは、制約が成り立つことだけです。ビットの決まりのような制約が1つ抜けていると、証明者は、作った人が考えてもいない値で残りを満たせます。