Llegamos a ustedes gracias a:



Columnas de opinión

¿Qué es zk-SNARK?

Por: Matthew Tyson, fundador de Dark Horse Group

[25/09/2022] Zk-SNARK, que significa conocimiento o argumento sucinto no interactivo de conocimiento cero, es el protocolo de conocimiento cero más popular.

[Reciba lo último de CIO Perú suscribiéndose a nuestro newsletter semanal]

Este es un espacio de creciente importancia, ya que los sistemas de conocimiento cero son un área de desarrollo activo que puede alterar el funcionamiento de la autenticación. Si bien las matemáticas son intensas, las ideas generales no son difíciles de entender.

¿Qué es el conocimiento cero?

El conocimiento cero es el intento de utilizar la menor cantidad posible de información al verificar una declaración. Sirve para crear pruebas que eviten la transferencia de datos adicionales.

La 'zona cero' para este campo es el artículo Knowledge Complexity of Interactive Proof Systems, que apareció en algunas ediciones durante los años ochenta. Como su nombre lo indica, el documento se compromete a obtener una comprensión de cómo se comporta el conocimiento en declaraciones de prueba entre sistemas que interactúan.

Este artículo se entiende mejor como un descendiente del artículo seminal de Stephen Cook de 1971 The Completeness of Theorem Deving Procedures, que inspiró el campo de la teoría de la complejidad en la informática. El artículo de Cook intentó examinar y poner límites a la complejidad de los algoritmos de forma explícita. De manera paralela, el artículo sobre la complejidad del conocimiento puso el conocimiento en un enfoque explícito, intentando poner límites superiores e inferiores a su alrededor en las demostraciones.

Conocimiento cero y autenticación

Por prueba, podemos entender autenticación. Cuando dos o más sistemas de software están en comunicación y una de las partes realiza una afirmación, ¿cómo prueba su afirmación a las otras partes? El conocimiento cero analiza cómo se hace esto y propone métodos alternativos a los enfoques inexpertos, métodos que reducen la cantidad de fuga de conocimiento y, por lo tanto, mejoran la seguridad del sistema en general.

Por ejemplo, en un enfoque inexperto, un sistema puede afirmar tener conocimiento de una contraseña. Para demostrarlo a otro sistema, simplemente se transmitiría la contraseña. Los protocolos de conocimiento cero funcionan para convencer con un mínimo de conocimiento, sin enviar la contraseña en sí en este ejemplo. Tales pruebas se basan en la probabilidad. Estas permiten la alta probabilidad de que la autenticación sea válida.

Las pruebas interactivas requieren el diálogo continuo entre las partes. El probador y el verificador se involucran en una dinámica de ida y vuelta, donde el verificador interroga al probador para obtener información. Cada respuesta correcta aumenta la confianza del verificador (reduce la probabilidad de que el probador esté mintiendo) en la afirmación del probador. La innovación contenida en las pruebas zk-SNARK es que este proceso de diálogo está encapsulado en un paquete seguro que se puede entregar, una vez, del probador al verificador. A partir de entonces, el verificador puede interactuar con la prueba misma. Por lo tanto, son pruebas no interactivas.

Las pruebas no interactivas se demostraron por primera vez en 1988, en el artículo Non-interactive Zero-Knowledge. Este trabajo planteó la viabilidad de encapsular pruebas de conocimiento cero en un formato no interactivo. En el 2012, le siguió el artículo From Extractable Collision Resistance to Succinct Non-Interactive Arguments of Knowledge, and Back Again, que introdujo SNARKs. Desde entonces, la historia ha sido la de refinar e implementar gradualmente la idea básica.

Implementaciones de zk-SNARK

Si la idea de SNARK se ve como una especificación conceptual, entonces la primera (casi) implementación práctica es el protocolo Pinocchio, propuesto en el 2013. En ese documento, se describe un esquema para el cómputo público verificable, en el que se pueden usar recursos de cómputo no confiables para confirmar la ejecución de funciones. Esta idea se elaboró y describió con más detalle en Succinct Non-Interactive Zero Knowledge for a Von Neumann Architecture

La conclusión de gran parte del trabajo aquí es que zk-SNARK parece ser un matorral matemático impenetrable. De hecho, existen hazañas mentales impresionantes que incluyen saltos intuitivos al estilo de Diffie-Hellman, así como una cantidad increíble de trabajo duro para lograr las transformaciones que sustentan los sistemas de trabajo. Mucha inspiración y transpiración.

La complejidad de zk-SNARK se ve agravada por su novedad. La teoría en sí, como ha podido ver, es un desarrollo reciente y aún se está elaborando. Las implementaciones son un área especialmente activa, ya que los fundamentos se abstraen y luego se integran en bibliotecas destinadas a aplicaciones y casos de uso específicos. Esos casos de uso en sí mismos se están descubriendo a medida que la aplicabilidad de zk-SNARK se prueba en la práctica con sistemas en funcionamiento.

Los casos de uso y los sistemas de software que los soportan son de mayor interés aquí, pero antes de pasar a eso, obtengamos una comprensión más profunda de cómo funciona zk-SNARK sin profundizar demasiado en las matemáticas.

Cómo funciona zk-SNARK

ZK-SNARK verifica, fundamentalmente, que se ha realizado un cálculo. Esto se hace tomando el cálculo original (es decir, una función) y expresándolo en un formato muy específico. Esto se logra a través de una serie de transformaciones matemáticas. Ese formato final es el formato real de zk-SNARK, que se puede usar para demostrar que se ha realizado el cálculo con el input dado (el input se llama testigo en zk-SNARK, porque se puede usar para demostrar que se ha producido el cálculo con ese argumento).

Dos comentarios son apropiados acerca de ese arreglo. En primer lugar, para muchas aplicaciones, como probar la posesión de una contraseña, el arreglo requiere primero modificar la afirmación deseada en un equivalente funcional. Por ejemplo, en el caso de una contraseña, la contraseña de texto sin formato se puede ejecutar a través de un algoritmo hash. Lo que luego se probará es que el hash se ejecutó contra la contraseña, lo que equivale a probar la posesión de la contraseña.

El otro comentario es que la naturaleza de la computación verificable abre un nuevo modelo de computación que tiene implicaciones más allá de la simple autenticación de declaraciones. Ese modelo permite la externalización de la computación a recursos de terceros, incluso en un ambiente sin confianza, porque el recurso puede demostrar criptográficamente la ejecución. Esto tiene consecuencias importantes para las blockchains, porque en lugar de verificar las transacciones transmitiendo la información real, las blockchains pueden usar zk-SNARK para transmitir solo la prueba. El protocolo MINA es un ejemplo de una blockchain que funciona en esta línea de pensamiento.

De esta forma, el outsourcing de la computación también puede tener casos de uso más allá de blockchain, al crear una especie de mercado de computación sin la necesidad de organizaciones de terceros confiables. Hoy en día, esas organizaciones son generalmente proveedores de nube de varios tipos.

Las transformaciones que usa SNARK, después de que la declaración se expresa como una función, siguen este patrón general (del documento de aritmética cuadrática de Vitalik Buterin): el cálculo original -> circuito algebraico -> sistema de restricción de rango 1 (R1CS) -> programa de aritmética cuadrática (QAP) -> PCP lineal -> prueba interactiva lineal -> zkSNARK.

El documento al que se hace referencia ofrece una buena descripción de las primeras cuatro transformaciones. Para un excelente recorrido en inglés sencillo de todo el proceso, se recomienda leer The Why and How of zk-SNARK. Otro buen recurso para zk -SNARK, y el conocimiento cero en general, es el blog Zero-Knowledge.

El truco clave que realiza zk-SNARK es convertir el cálculo en una forma polinomial. En ese formato, el cálculo se puede probar probando puntos en el gráfico de polinomios. Eso significa que, en lugar del polinomio en sí, las soluciones del polinomio se utilizan para verificar que el probador está realmente en posesión de la prueba. Al probar una serie de puntos, la prueba aumenta la confiabilidad probable.

Entonces, la primera parte de las transformaciones son responsables de convertir una función en una forma matemática (circuito algebraico -> R1CS), luego convertirla en un polinomio (QAP) y luego convertirla en una forma que sea verificable de manera eficiente (PCP lineal -> Prueba lineal Interactiva) y finalmente una forma transmisible: el propio SNARK.

Puede haber otros enfoques para encapsular pruebas de conocimiento cero en una forma no interactiva, pero hoy en día, este es el enfoque principal.

Aplicaciones para zk-SNARK

Además del potencial para mover blockchains a computación verificable, zk-SNARKs puede soportar la autenticación de estilo de conocimiento cero, tanto en términos de proporcionar credenciales para iniciar sesión como más ampliamente para establecer declaraciones. Por ejemplo, afirmar que el usuario tiene una cuenta bancaria por un monto determinado (esto requeriría interactuar con el banco como un tercero).

Al usar zk-SNARKs, es posible una especie de autenticación anónima. Es decir, el usuario puede demostrar que se le permite acceder a un recurso basado simplemente en un hecho que poseen, en lugar de su identidad. Dicho mecanismo aumenta la seguridad de los sistemas seguros al limitar la cantidad de conocimiento intercambiado al realizar actividades de autenticación.

Finalmente, es posible implementar sistemas de pago totalmente anónimos con zk-SNARK. Una transacción puede continuar verificando los fondos disponibles, asegurándose de que estén depositados, verificando la entrega de bienes y completando el contrato, todo sin divulgar la identidad de ninguna de las partes.

Matthew Tyson, arquitecto de software, es uno de los fundadores de Dark Horse Group, Inc. Él cree en la tecnología que prioriza a las personas. Cuando no toca la guitarra, Matt explora las áreas rurales y las filosóficas internas. Ha escrito para JavaWorld desde el 2007.