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

無料レッスン

ゼロ知識証明とは何か

このレッスンのあとで: 対話型の証明を使って、完全性、健全性、ゼロ知識性を説明できる。

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

秘密を言わずに、知っていると示す

ゼロ知識証明は、秘密そのものを見せずに、その秘密を知っていると相手に納得させる方法です。パスワードを送らずにログインしたり、個人のデータについての事実を示したりするのに使います。

今日は、この考え方を表すゲームで遊び、なぜうまくいくのかを数で確かめます。

このレッスンのゴール

メモ

対話型の証明を使って、完全性、健全性、ゼロ知識性を説明できる。

キーワード

ことばいみ
証明者秘密を知っていると主張する人
検証者その主張を確かめる人
チャレンジ検証者がランダムに選ぶ問い
完全性正直な証明者は必ず通ること
健全性ごまかす証明者はほぼ必ず失敗すること
ゼロ知識性主張が正しいこと以外、検証者は何も知らないこと

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

洞窟のゲームは対話型の証明

洞窟には A と B の2本の道があり、奥で鍵のかかった扉がつないでいます。証明者は、扉の合言葉を知っていると言います。

検証者が外で待つ間に、証明者はどちらかの道から入ります。検証者は A か B をランダムに叫び、証明者はその道から出てきます。合言葉を知っていれば必ず出られます。知らなければ、当てずっぽうが合ったときだけで、2回に1回です。

洞窟のゲームを何度も遊ぶ

コマンド
docker exec jupyter python3 steps/cave.py

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

ラボの表示を読む

表示は英語です。passed は通った、cheaters はごまかす人、rounds はラウンドの意味です。

合言葉を知る証明者は、20回中20回通りました。これが完全性です。次に1000人のごまかす人が遊びました。1回目のあと残ったのは493人、2回目のあとは243人、10回目のあとは0人です。1回ごとに、ほぼ半分に減ります。20回なら、ごまかして通れるのは1048576回に1回です。これが健全性です。

例: ごまかして通る確率

ラウンド数すべて通る確率小数
12回に1回0.5
24回に1回0.25
38回に1回0.125
101024回に1回約0.001
201048576回に1回約0.000001

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

試そう: 洞窟でごまかす人

コード: python
import random

rng = random.Random(3)

def one_round(knows_password):
    went_in = rng.choice("AB")
    asked_for = rng.choice("AB")
    if knows_password:
        return True
    return went_in == asked_for

passed = 0
for n in range(10):
    if one_round(False):
        passed = passed + 1
    else:
        print("捕まったラウンド:", n + 1)
        break
print("通ったラウンド数:", passed)
# False を True に変えて、合言葉を知る証明者にし、もう一度実行しましょう。

検証者が何も知らない理由

外から見ると、証明者は言われた道から出てくるだけです。合言葉は一度も聞こえません。

さらに、ゲームを撮った動画は、第三者には何の証明にもなりません。2人が道を前もって決めておき、動画を編集できたからです。にせの記録が本物とまったく同じに見えるなら、本物の記録も何も漏らしていません。これがゼロ知識性の考え方です。

よくある間違い

注意

「ゼロ知識とは、検証者が何ひとつ知らないことだ」と考える人がいます。検証者は1つだけ知ります。主張が正しいということです。知らないのは秘密そのものと、秘密を見つける手がかりです。

ラボのスクリプトを一覧にする

コマンド
docker exec jupyter ls steps

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

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

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