Demostrar tu edad sin enseñar tu cumpleaños
Un circuito aritmético escribe algo sobre un secreto como sumas y productos pequeños que tienen que cumplirse todos. Un SNARK es una prueba corta de que conoces valores que los cumplen todos.
Así un sistema puede comprobar que tienes más de 18 años, o que estás en una lista, sin ver los datos privados.
Al terminar esta lección
Nota
Puedo escribir un enunciado sobre un secreto como restricciones y comprobar un testigo con ellas.
Palabras clave
| Palabra | Qué significa | Ejemplo |
|---|---|---|
| Cuerpo | los enteros mod un primo, con suma y producto | mod 97 |
| Puerta | una suma o un producto con su salida | |
| Testigo | un valor para cada cable, secreto incluido | |
| Restricción | una ecuación que el testigo tiene que cumplir | |
| SNARK | una prueba corta de que existe un testigo, rápida de comprobar |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Un enunciado se convierte en puertas
Toma el enunciado "conozco un x tal que x por x más 2 por x es 48". Pártelo en pasos que hagan una sola cosa: x2 = x por x, two_x = x más x, out = x2 más two_x. Cada paso es una puerta. El laboratorio llama x_squared a x2.
El probador rellena todos los cables, y eso es el testigo. La parte pública es out = 48. Todos los valores viven en un cuerpo, aquí mod 97.
Comprueba un testigo con las puertas
docker exec jupyter python3 steps/constraints.pySe muestra aquí y no se ejecuta. Pulsa Iniciar laboratorio para escribirlo en el terminal de tu propio laboratorio.
Lee lo que imprimió el laboratorio
El script imprime en inglés: witness es el testigo y gate la puerta. Para x = 6 el testigo es x_squared = 36, two_x = 12 y out = 48, y la primera puerta mala es -1, es decir, ninguna. Se cumplen todas.
Un probador con x = 5 que dice que out es 48 falla en la puerta 2, la última suma, porque 25 más 10 es 35. Un testigo falso no puede cumplir todas las puertas.
Pruébalo: puertas para un cubo
F = 97 # cada suma y cada producto se toman mod 97
# Enunciado: "conozco un x con x * x * x + 2 * x = 33", y 33 es público.
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], "se cumple:", value == w[gate[3]])
# Cambia x = 3 por x = 4 (out sigue en 33) y ejecuta otra vez. ¿Qué puerta falla?
Una comprobación de rango se hace con bits
Para demostrar que un x secreto está entre 0 y 15 sin enseñarlo, el probador da cuatro bits. Dos tipos de restricción los comprueban. Cada bit b tiene que cumplir b por b igual a b, y eso solo lo hacen 0 y 1. Y los bits, con pesos 1, 2, 4 y 8, tienen que sumar x.
El laboratorio comprobó 11 como 1, 1, 0, 1: verdadero. Un bit de 2 rompió la primera regla: falso.
Ejemplo: puertas como restricciones
| Puerta | Restricción, izquierda por derecha igual a salida | Con x = 6 |
|---|---|---|
| x2 = x por x | x por x = x2 | 6 por 6 = 36 |
| two_x = x más x | (x + x) por 1 = two_x | 12 por 1 = 12 |
| out = x2 más two_x | (x2 + two_x) por 1 = out | 48 por 1 = 48 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Dónde entra un SNARK
Hasta ahora el verificador comprobaba el testigo viéndolo, y eso enseña el secreto. Un SNARK permite al probador convencer al verificador de que ese testigo existe. La prueba ocupa unos cientos de bytes y se comprueba rápido, sea cual sea el tamaño del circuito.
Lenguajes como Noir y Circom convierten un enunciado en restricciones como estas. Este laboratorio no los ejecuta: no tiene probador, así que el circuito se queda en Python.
Lista las funciones de circuit.py
docker exec jupyter grep -n def circuit.pySe muestra aquí y no se ejecuta. Pulsa Iniciar laboratorio para escribirlo en el terminal de tu propio laboratorio.
Un error frecuente
Advertencia
Mucha gente cree que un SNARK demuestra que el enunciado tiene sentido. Solo demuestra que se cumplen las restricciones. Si falta una restricción, como la regla del bit, un probador puede cumplir las demás con valores que nadie pretendía.