クリーム色の背景、色付き表示、高コントラスト、大きな文字のほうが読みやすいですか?配色と文字を選ぶと、すべてのページに一度で反映されます。

無料レッスン

回路と制約、SNARK の位置

このレッスンのあとで: 秘密についての主張を制約として書き、証人がそれを満たすかを確かめることができる。

70分のレッスンコマンド2件ゼロ知識証明ラボ:コミットメント、Schnorr、Fiat-Shamir、Merkle の証明を Python で

誕生日を見せずに年齢を示す

算術回路は、秘密についての主張を、すべて成り立つべき小さな和と積の集まりとして書いたものです。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乗のゲート

コード: python
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 × xx × x = x26 × 6 = 36
two_x = x + x(x + x) × 1 = two_x12 × 1 = 12
out = x2 + two_x(x2 + two_x) × 1 = out48 × 1 = 48

学生が入力するセルは、このプレビューでは空白です。

SNARK はどこに入るか

ここまで検証者は、証人を見て確かめていました。これでは秘密が見えてしまいます。SNARK を使うと、証明者は、そのような証人があることを検証者に納得させられます。証明は数百バイトで、回路の大きさに関係なく、すぐに確かめられます。

Noir や Circom などの言語は、主張をこのような制約に変えます。このラボではそれらを動かしません。証明器がないので、回路は Python のままです。

circuit.py の関数を一覧にする

コマンド
docker exec jupyter grep -n def circuit.py

ここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。

よくある間違い

注意

「SNARK は主張がまともであることを証明する」と考える人がいます。証明するのは、制約が成り立つことだけです。ビットの決まりのような制約が1つ抜けていると、証明者は、作った人が考えてもいない値で残りを満たせます。

このラボとソースについて: ゼロ知識証明ラボ:コミットメント、Schnorr、Fiat-Shamir、Merkle の証明を Python で

授業で使いますか?このモジュールを学生に割り当てると、教員用ガイド、自動採点つきの課題、学生ごとのラボを使えます。