Matemáticas lunares de las pruebas de conocimiento cero
Las pruebas de conocimiento cero demuestran que ejecutaste un cálculo correctamente sin revelar las entradas de dicho cálculo. Un lenguaje de programación de conocimiento cero es una forma conveniente de representar ese cálculo.
Una analogía común, pero engañosa, para las pruebas de conocimiento cero es “Puedo probar que tengo más de 21 años sin mostrarte mi tarjeta de identificación”. Formulada de esta manera, no puedes crear una prueba de conocimiento cero.
Las pruebas de conocimiento cero no prueban el conocimiento. Prueban el cálculo correcto para la salida pública de un algoritmo público sin revelar las entradas del cálculo.
Así que las tarjetas de identificación de conocimiento cero no funcionan de esa manera. Usemos un ejemplo real. Es posible tomar un número conocido, digamos 1,093,073, y crear una prueba de que multiplicaste dos números para obtenerlo sin revelar esos dos números (en este caso 1103 y 991).
La prueba de conocimiento cero para esto tendría tres componentes:
- dos números (los llamamos fields), en este caso, versiones encriptadas de 1103 y 991
- una gran cadena de bytes (la prueba)
- una descripción programática del algoritmo de multiplicación
Es un poco engañoso llamar a las entradas “encriptadas” porque no hay una forma natural de desencriptarlas, pero es una manera razonable de pensarlo. Puedes hacer cosas matemáticamente sensatas con las entradas, pero no puedes determinar cuáles eran sus valores originales.
Puedes pensar en las pruebas de conocimiento cero como una versión altamente generalizada de las firmas digitales.
Con las firmas digitales, estás probando el conocimiento de una clave privada sin compartir dicha clave privada. Pruebas este conocimiento poniendo primero a disposición un mensaje y una clave pública. Luego muestras una firma que es consistente con el mensaje y la clave pública.
La analogía para las pruebas de conocimiento cero funciona así:
(salida pública, entrada encriptada, prueba de conocimiento cero) —> firma digital
(algoritmo) —> clave pública.
Produces una prueba (la cadena de bytes) que es consistente con la salida y el algoritmo. El verificador no puede ejecutar realmente el cálculo, pero puede verificar que:
- el algoritmo
- la salida
- las entradas encriptadas, y
- la cadena de la prueba
sean todos consistentes entre sí.
En las firmas digitales, la dirección pública se conoce de antemano. En las aplicaciones de conocimiento cero, el algoritmo que estás ejecutando se conoce de antemano. Las firmas digitales cambian dependiendo del mensaje que estés firmando. Del mismo modo, en las pruebas de conocimiento cero, la cadena de tu prueba cambiará con las entradas y salidas que estés probando.
En forma general, un cálculo de conocimiento cero se ve así:
prove(inputs, algorithm_description) -> (encrypted_inputs, proof, public_output)
verify(encrypted_inputs, proof, algorithm_description) == public_output
Un ejemplo más interesante es mover dinero en una criptomoneda como zcash. Cada transacción para mover dinero es una transición de estado, que en sí misma es un cálculo. La salida pública es el suministro total (que no cambia módulo las recompensas de los mineros). La entrada encriptada es la transferencia de saldo entre direcciones.
Dado que las pruebas de conocimiento cero son solo cálculos, se prestan muy naturalmente a ser descritas con lenguajes de programación. ¿Recuerdas la descripción programática del algoritmo de multiplicación de antes? Eso se puede representar convenientemente en un lenguaje de programación tradicional que lo compilará en “matemáticas lunares” detrás de escena.
Sin más preámbulos, aquí está la lista de lenguajes de programación de conocimiento cero.
Circom, producido por iden3
Si vienes de un entorno de ingeniería eléctrica, alégrate. La forma dominante de representar cálculos en conocimiento cero es con circuitos booleanos. Los circuitos booleanos son en realidad ecuaciones matemáticas gigantescas, por lo que se convierten fácilmente en las ecuaciones de matemáticas lunares que ocurren detrás de escena.
Te estarás preguntando, si el conocimiento cero se representa con circuitos, ¿cómo se puede llevar a cabo algo como un algoritmo hash o un bucle for? Esto requiere varios pasos, mientras que un circuito calcula las cosas de una sola vez.
Esto se logra tratando cada paso como un circuito separado y teniendo una lista de pruebas para cada paso. Esto es afortunado para nosotros, porque describir la mayoría de los cálculos en términos de circuitos es todo un desafío.
Afortunadamente, en lugar de tener que implementar ALU (unidades lógico-aritméticas) nosotros mismos, Circom proporciona una capa de abstracción sobre ellas. Aquí está el código para sumar dos números:
pragma circom 2.0.0;
template Add(){
//Declaration of signals
signal input in1;
signal input in2;
signal output out;
out <== in1 + in2;
}
component main {public [in1,in2]} = Add();
Estas plantillas te permiten ensamblar bloques de construcción para realizar operaciones mucho más complicadas, como concatenar cadenas de bytes, aritmética de curvas elípticas o funciones hash.
Zokrates
Si seis líneas de código para sumar dos números te desaniman, afortunadamente existen abstracciones de más alto nivel para esto. Así es como lo hace Zokrates:
def main(field x, field y) -> field {
field z = x + y;
return z;
}
¿Por qué los lenguajes de programación de conocimiento cero se refieren a los números como fields? Las matemáticas en las pruebas de conocimiento cero siempre se realizan módulo un número primo grande (como en la mayoría de los algoritmos criptográficos). El término “field” aquí es la abreviatura de “campo finito” ya que la cantidad de valores posibles que puede tomar el número es finita. Específicamente, es el tamaño del número primo sobre el cual estás haciendo aritmética modular.
Obviamente, probar que conoces la suma de dos números sin revelar esos números no es muy interesante. Aquí tienes una mejor aplicación usando el ejemplo del principio.
Tarjeta de identificación de conocimiento cero en Zokrates
Algoritmo de tarjeta de identificación de prueba de conocimiento cero
Con algunas modificaciones, podemos hacer que nuestra tarjeta de identificación de conocimiento cero funcione.
Para empezar, no es posible demostrar la edad sin que alguna autoridad verifique que naciste en cierta fecha. Pero aquí hay una manera de convertir el conocimiento de un hecho en la prueba de un cálculo.
El gobierno toma tu fecha de cumpleaños, tu número de identificación ciudadana y un salt aleatorio. Concatenan estas cadenas, las hashean y firman digitalmente el resumen hash. Cuando vayas a un establecimiento a pedir algo que requiera demostrar que eres mayor de 21 años, proporcionarías tu cumpleaños encriptado, tu identificación ciudadana encriptada, tu salt aleatorio encriptado, el hash que firmó el gobierno y la prueba de cadena de bytes.
El objetivo es probar que puedes llevar a cabo correctamente el algoritmo para producir el hash firmado.
Normalmente, no puedes concatenar valores encriptados y recuperar el hash firmado, pero ahí es donde entra la programación de conocimiento cero. En realidad no estás hasheando las entradas encriptadas, estás demostrando que realizaste un cálculo correctamente sin revelar las entradas.
En Zokrates, esto parece sorprendentemente ergonómico:
import "hashes/sha256/512bitPacked" as sha256packed;
def main(private field birthday,
private field citizenId,
private field salt,
public requiredBirthday,
public field hashFirst128bits,
public field hashSecond128bits) {
field[2] hash = sha256packed([birthday, citizenId, salt]);
assert(hash[0] == hashFirst128bits);
assert(hash[1] == hashSecond128bits);
assert(birthday < requiredBirthday);
return;
}
// the signature for the hash would be validated in a traditional way
Esto no parece tan aterrador, ¿verdad? Estamos asegurando que los valores secretos generen el hash esperado y asegurándonos de que la entrada correspondiente a birthday cumpla con el umbral.
Una cosa que salta a la vista: ¿cómo puede ejecutarse la línea
assert(birthday < requiredBirthday)
si birthday está encriptado?
El código se compila en matemáticas donde esto tiene un significado real; no se “ejecuta” de la manera en que normalmente pensamos en ello. De manera similar, el circuito hash no está realmente hasheando las entradas. Simplemente verifica que las entradas encriptadas sean consistentes con la salida hash pública como una función del circuito subyacente y la prueba que lo acompaña.
Whitepaper original de Zokrates, publicado en IEEE 2018 (http://www.ise.tu-berlin.de/fileadmin/fg308/publications/2018/2018_eberhardt_ZoKrates.pdf)
Leo
La cadena de bloques Aleo es una cadena de contratos inteligentes centrada en la privacidad, con Leo como su lenguaje de programación principal. Puedes ver cómo es el lenguaje en su playground en línea.
Al momento de escribir este artículo, solo se ha lanzado la red de prueba (testnet).
Aquí está el lenguaje sumando dos números juntos:
program helloworld.aleo {
transition main(public a: u32, b: u32) -> u32 {
let c: u32 = a + b;
return c;
}
}
Whitepaper de Leo / artículo académico: https://eprint.iacr.org/2021/651.pdf
Aplicaciones de Capa Dos (Layer Two)
Aunque las pruebas de conocimiento cero son famosas por la privacidad, tienen un poderoso caso de uso para la escalabilidad de blockchain. Recuerda, el verificador no puede realmente hashear o sumar las entradas encriptadas para obtener resultados sensatos. Simplemente validan que las entradas, salidas, el circuito y las pruebas sean consistentes.
Curiosamente, probar la consistencia es computacionalmente más fácil que llevar a cabo el cálculo real. Esto significa que el productor de bloques que ensambla la transacción tiene una cantidad considerable de carga computacional porque debe realizar el cálculo y producir las pruebas, pero los otros validadores que están validando el bloque propuesto tienen mucho menos trabajo que hacer porque solo tienen que validar la prueba, lo cual es asintóticamente más fácil.
El consenso no ocurre cuando se produce el bloque, ocurre cuando más de dos tercios de la red acuerdan que el bloque es válido. Cuanto más pesado sea el cálculo que tienen que llevar a cabo, más tiempo tomará el consenso, y esto causa cuellos de botella en el rendimiento.
Debido a que este caso de uso se optimiza para una verificación rápida, no debes asumir que las operaciones son privadas por defecto. Las implementaciones de los siguientes lenguajes no necesariamente optimizan la preservación de la privacidad a menos que lo digan explícitamente.
Noir de Aztec
Noir es el lenguaje para Aztec, una L2 enfocada en la privacidad para Ethereum. La sintaxis está fuertemente inspirada en Rust; incluso la herramienta de construcción se llama “nargo”, un obvio guiño al cargo de Rust.
Aquí está Noir sumando dos números juntos:
fn foo(x : Field, y : Field) -> Field {
x + y
}
En Rust, y en Noir, las sentencias que no tienen punto y coma se interpretan como retornos de función, por si te preguntabas por qué desapareció la declaración de retorno.
Cairo de Starkware
Starknet es otra L2.
El nombre es un acrónimo de CPU Algebraic Intermediate Representation (Representación Intermedia Algebraica de CPU). Los lenguajes de representación intermedia pretenden estar apenas “por encima del ensamblador”, pero en las pruebas de conocimiento cero, el “ensamblador” son las fórmulas algebraicas para probar el conocimiento cero.
Los desarrolladores de C o C++ (o los desarrolladores de Solidity cómodos con el ensamblador) se sentirán como en casa con este lenguaje ya que es de bastante bajo nivel. Aquí está el playground de Cairo.
Manteniendo la tradición, Cairo se refiere a los números como “fields” pero los llama “field elements” y eso se condensa en “felt” en la sintaxis (field + element).
Aquí está Cairo sumando dos números:
%builtins output
// Import the serialize_word() function.
from starkware.cairo.common.serialize import serialize_word
func main{output_ptr: felt*}() {
tempvar x = 12;
tempvar y = 14;
tempvar z = x + y;
serialize_word(z);
return ();
}
Whitepaper de Cairo: https://eprint.iacr.org/2021/1063.pdf
Solidity
¡¿No esperabas ver esto aquí, verdad?!
Es posible que hayas escuchado algo de expectativa alrededor de las “zk evms” que Polygon y Matter Labs están produciendo. La gran noticia es que puedes compilar Solidity puro a bytecode EVM regular y también producir una prueba de conocimiento cero de que ejecutaste el bytecode correctamente. Esto, por supuesto, requiere una máquina virtual especializada, que las empresas tienden a nombrar como alguna variación de “zk evm”.
Puedes pensar en el estado de la EVM como si estuviera representado por dos arreglos: el stack y la memoria. Cada operación altera el stack y/o la memoria. Cada paso es una prueba de que la forma en que alteraste el estado es consistente con el opcode que acabas de ejecutar y el estado anterior.
Debido a esta innovación, es probable que Solidity siga siendo relevante durante mucho tiempo, ¡así que echa un vistazo a nuestro Solidity bootcamp! Es un requisito previo para nuestro zero knowledge bootcamp.
Cuál debería usar y recursos adicionales
Si planeas desarrollar en Aleo, Starknet o Aztec, tendrás que usar sus respectivos lenguajes. Pero si estás intentando desarrollar un contrato inteligente en Ethereum que esté centrado en la privacidad, necesitarás usar Circom o Zokrates. Noir actualmente también tiene soporte limitado para compilar a Solidity.
Si bien puede ser tentador saltar directamente a usar un lenguaje más amigable que Circom, vale la pena desarrollar una intuición de cómo funciona la programación de circuitos. Después de todo, los lenguajes aquí en última instancia se compilan a algo similar. Notarás restricciones extrañas en los lenguajes posteriores a Circom en esta lista que no tendrán sentido a menos que tengas una idea de lo que está sucediendo bajo el capó. Por ejemplo, todas las ramas de las sentencias “if” se ejecutan en Zokrates, y la memoria no se puede sobrescribir en Cairo.
No existe tal cosa como una introducción suave a las matemáticas detrás de las pruebas de conocimiento cero, pero este artículo debería ser comprensible para cualquiera que haya tomado precálculo o un curso básico de criptografía.
Practica rompecabezas de conocimiento cero
Si quieres una introducción suave a Circom, lee su documentación e intenta resolver nuestros Zero Knowledge Puzzles de código abierto.
Publicado originalmente el 22 de diciembre de 2022