Lässt es sich mit cremefarbenem Papier, einer Tönung, mehr Kontrast oder größerer Schrift besser lesen? Wählen Sie Ihre Farben und Ihre Schrift, einmalig für alle Seiten.

Kostenlose Lektion

Schaltkreise, Bedingungen und wo SNARKs passen

Nach dieser Lektion: Ich kann eine Aussage über ein Geheimnis als Bedingungen schreiben und einen Zeugen dagegen prüfen.

Lektion, 70 Min.2 BefehleZero-Knowledge-Lab: Commitments, Schnorr, Fiat-Shamir und Merkle-Beweise in Python

Das Alter beweisen, ohne den Geburtstag zu zeigen

Ein arithmetischer Schaltkreis schreibt eine Aussage über ein Geheimnis als kleine Summen und Produkte, die alle gelten müssen. Ein SNARK ist ein kurzer Beweis, dass man Werte kennt, die jede davon erfüllen.

So kann ein System prüfen, dass Sie über 18 sind oder auf einer Liste stehen, ohne die privaten Daten zu sehen.

Am Ende dieser Lektion

Notiz

Ich kann eine Aussage über ein Geheimnis als Bedingungen schreiben und einen Zeugen dagegen prüfen.

Schlüsselwörter

BegriffWas er bedeutetBeispiel
Körperganze Zahlen modulo einer Primzahl, mit Addition und Multiplikationmodulo 97
Gattereine Summe oder ein Produkt mit seinem Ausgang
Zeugeein Wert für jede Leitung, das Geheimnis eingeschlossen
Bedingungeine Gleichung, die der Zeuge erfüllen muss
SNARKein kurzer, schnell prüfbarer Beweis, dass ein Zeuge existiert

Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.

Eine Aussage wird zu einer Liste von Gattern

Nehmen Sie die Aussage „Ich kenne x mit x mal x plus 2 mal x gleich 48“. Zerlegen Sie sie in Schritte, die jeweils eine Sache tun: x_squared = x mal x, two_x = x plus x, out = x_squared plus two_x. Jeder Schritt ist ein Gatter.

Der Beweiser füllt jede Leitung aus, das ist der Zeuge. Öffentlich ist out = 48. Alle Werte liegen in einem Körper, hier modulo 97.

Einen Zeugen gegen die Gatter prüfen

Befehl
docker exec jupyter python3 steps/constraints.py

Hier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.

Lesen Sie, was das Lab gedruckt hat

Für x = 6 ist der Zeuge x_squared = 36, two_x = 12 und out = 48. Das erste schlechte Gatter ist -1, also keines. Jedes Gatter gilt.

Ein Beweiser mit x = 5, der out = 48 behauptet, scheitert an Gatter 2, der letzten Addition, denn 25 plus 10 ist 35. Ein falscher Zeuge kann nicht jedes Gatter erfüllen.

Probieren Sie es: Gatter für eine Kubikzahl

Code: python
K = 97  # jede Summe und jedes Produkt wird modulo 97 gerechnet

# Aussage: "Ich kenne x mit x * x * x + 2 * x = 33", und 33 ist öffentlich.
gatter = [
    ["mal", "x", "x", "x2"],
    ["mal", "x2", "x", "x3"],
    ["plus", "x", "x", "zwei_x"],
    ["plus", "x3", "zwei_x", "aus"],
]

x = 3
w = {"x": x, "x2": x * x % K, "x3": x * x * x % K, "zwei_x": 2 * x % K, "aus": 33}

for g in gatter:
    a = w[g[1]]
    b = w[g[2]]
    if g[0] == "mal":
        wert = a * b % K
    else:
        wert = (a + b) % K
    print(g[0], g[1], g[2], "->", g[3], "gilt:", wert == w[g[3]])
# Setzen Sie x = 4 statt x = 3 (aus bleibt 33). Welches Gatter scheitert?

Eine Bereichsprüfung besteht aus Bits

Um zu beweisen, dass ein geheimes x zwischen 0 und 15 liegt, ohne es zu zeigen, gibt der Beweiser vier Bits an. Zwei Arten von Bedingungen prüfen sie. Jedes Bit b muss b mal b gleich b erfüllen, was nur 0 und 1 tun. Und die Bits, mit 1, 2, 4 und 8 gewichtet, müssen x ergeben.

Das Lab prüfte 11 als 1, 1, 0, 1: wahr. Ein Bit mit dem Wert 2 brach die erste Regel: falsch.

Beispiel: Gatter als Bedingungen

GatterBedingung: links mal rechts gleich AusgangMit x = 6
x_squared = x mal xx mal x = x_squared6 mal 6 = 36
two_x = x plus x(x + x) mal 1 = two_x12 mal 1 = 12
out = x_squared plus two_x(x_squared + two_x) mal 1 = out48 mal 1 = 48

Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.

Wo ein SNARK hinzukommt

Bisher hat der Prüfer den Zeugen geprüft, indem er ihn sah. Das zeigt das Geheimnis. Mit einem SNARK überzeugt der Beweiser den Prüfer, dass ein solcher Zeuge existiert. Der Beweis ist wenige hundert Bytes groß und schnell geprüft, egal wie groß der Schaltkreis ist.

Sprachen wie Noir und Circom übersetzen eine Aussage in solche Bedingungen. Dieses Lab führt sie nicht aus: Es hat keinen Beweiser, darum bleibt der Schaltkreis in Python.

Die Funktionen in circuit.py auflisten

Befehl
docker exec jupyter grep -n def circuit.py

Hier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.

Ein häufiger Fehler

Warnung

Viele glauben, ein SNARK beweise, dass die Aussage sinnvoll ist. Er beweist nur, dass die Bedingungen gelten. Fehlt eine Bedingung, etwa die Regel für Bits, kann ein Beweiser den Rest mit Werten erfüllen, die nie gemeint waren.

Über dieses Lab und seinen Quellcode: Zero-Knowledge-Lab: Commitments, Schnorr, Fiat-Shamir und Merkle-Beweise in Python

Sie unterrichten eine Gruppe? Weisen Sie dieses Modul Ihren Studierenden zu, mit Handbuch für Lehrende, automatisch geprüften Aufgaben und einem Lab für jede Person.