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
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Körper | ganze Zahlen modulo einer Primzahl, mit Addition und Multiplikation | modulo 97 |
| Gatter | eine Summe oder ein Produkt mit seinem Ausgang | |
| Zeuge | ein Wert für jede Leitung, das Geheimnis eingeschlossen | |
| Bedingung | eine Gleichung, die der Zeuge erfüllen muss | |
| SNARK | ein 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
docker exec jupyter python3 steps/constraints.pyHier 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
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
| Gatter | Bedingung: links mal rechts gleich Ausgang | Mit x = 6 |
|---|---|---|
| x_squared = x mal x | x mal x = x_squared | 6 mal 6 = 36 |
| two_x = x plus x | (x + x) mal 1 = two_x | 12 mal 1 = 12 |
| out = x_squared plus two_x | (x_squared + two_x) mal 1 = out | 48 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
docker exec jupyter grep -n def circuit.pyHier 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.