Escrito por: Clase Lambda
Compilador: Bai Ding, Fausto, Nickqiao
Artículo original en inglés publicado el 17 de febrero de 2024.
Las pruebas de conocimiento cero (pruebas ZK) son poderosas primitivas criptográficas que permiten a una parte (el probador) convencer a la otra parte (el verificador) de que una declaración determinada es verdadera y válida sin revelar ninguna información privada. En los últimos años, ZK ha atraído una amplia atención en los campos de la computación privada verificable, proporcionando pruebas de validez para programas informáticos y blockchain, y ha tenido un efecto positivo significativo en el desarrollo del mundo.
Aunque ZK es una tecnología emergente, sus ideas y conceptos básicos se remontan a los años 80. Después de combinarse con cadenas de bloques como Bitcoin y Ethereum, el desarrollo de la tecnología ZK se ha acelerado significativamente, porque la cadena de bloques puede realizar verificación de validez a través de SNARK y STARK, lo que mejora en gran medida la escalabilidad, lo que hace que ZK en la región Blockchain sea un tema candente.
Como lo expresa el fundador de Starkware, Eli Ben-Sasson, en los últimos años hemos sido testigos de una "explosión cámbrica" de sistemas de prueba criptográfica, cada uno con ventajas y desventajas únicas y compensaciones en su diseño. Los avances de hardware, mejores algoritmos, nuevos argumentos y herramientas periféricas han estimulado la mejora del rendimiento de los sistemas ZK y el nacimiento de nuevos sistemas. Se han adoptado muchos sistemas de prueba en aplicaciones prácticas y la gente todavía está ampliando los límites de ZK.
Esto también lleva a la gente a reflexionar profundamente sobre una pregunta: ¿Existe un sistema de prueba ZK universal adecuado para todas las aplicaciones? Creemos que esto es poco probable por tres razones:
diversidad de aplicaciones;
Diferentes tipos de restricciones (incluyendo memoria, tiempo de verificación, tiempo de prueba);
La necesidad de solidez (si un pirata informático compromete un sistema de prueba, aún podemos cambiar a otro sistema como seguro).
Con base en las razones anteriores, ZK demuestra que el sistema debe ser diverso. Pero incluso si hay muchos tipos de sistemas de prueba, debe haber un punto en común importante: las pruebas ZK se pueden verificar rápidamente y tienen una capa de verificación que se puede adaptar fácilmente a nuevos sistemas de prueba para resolver las capas subyacentes (como Ethereum) relacionadas. dificultades.
En el campo ZK, se menciona con frecuencia zk-SNARK. Es una forma de implementar pruebas de conocimiento cero mediante el uso de herramientas matemáticas complejas, como pares bilineales y circuitos aritméticos, para lograr pruebas de conocimiento cero eficientes. La característica de zk-SNARK es que el proceso de prueba es simple y no interactivo. Solo se requiere una única comunicación entre el probador y el verificador sin múltiples interacciones. Además, zk-SNARK tiene un tamaño de prueba muy corto y una alta eficiencia de verificación, lo que lo hace adecuado para su uso en entornos con recursos limitados.
Y zk-STARK es otra forma común diseñada para superar algunas de las limitaciones de zk-SNARK. zk-STARK no depende de configuraciones confiables y utiliza un sistema de construcción matemático más transparente, como compromiso polinómico y operaciones de campo finitos, colisiones hash, etc., para generar y verificar pruebas. zk-STARK es más escalable que zk-SNARK, adecuado para cálculos a mayor escala y la generación de pruebas es más rápida, pero el tamaño de la prueba en sí suele ser mayor.
Se puede decir que zk-SNARK y zk-STARK son formas de uso común en pruebas de conocimiento cero, pero difieren en términos de transparencia, escalabilidad, tamaño de prueba, etc.
En general, un sistema de prueba ZK suele constar de dos partes: PIOP (Polynomial Interactive Oracle) y PCS (Polynomial Commitment Scheme). Las soluciones PIOP comunes incluyen PLONKish, GKR, etc., mientras que las soluciones PCS comunes incluyen FRI, KZG, IPA, etc. Por ejemplo, la versión Zcash de Halo2 usa la implementación Plonkish + IPA. En cuanto a zk-STARK, en realidad se puede considerar. como una solución basada en FRI zk-SNARK especial.
Si entramos en más detalle, los diferentes tipos de sistemas de prueba utilizan diferentes esquemas de compromiso polinómico (PCS), esquemas aritméticos, pruebas oraculares interactivas (IOP) o pruebas comprobables probabilísticas (PCP).
Además, los diferentes sistemas de prueba ZK se diferencian a menudo en los siguientes indicadores:
Supuestos criptográficos: funciones hash resistentes a colisiones, problema de logaritmos discretos en curvas elípticas, conocimiento exponencial
Configuraciones transparentes versus configuraciones confiables
Tiempo dedicado a generar pruebas: lineal vs superlineal
Consumo de tiempo de la prueba de verificación: tiempo constante, tiempo logarítmico, sublineal, lineal
Probar tamaño
La simplicidad de la recursividad
esquema aritmético
Polinomios univariados vs multivariados
A continuación, abordaremos brevemente los orígenes de la tecnología ZK, exploraremos sus componentes básicos y describiremos el ascenso y la caída de los diferentes sistemas a prueba de ZK. Al mismo tiempo, este artículo no proporciona un análisis detallado del sistema de prueba en sí, sino que se centra en aquellos que han tenido un profundo impacto en este campo. Después de todo, el desarrollo de cualquier industria sólo es posible a través de las grandes ideas de los pioneros. y su implementación.
El desarrollo histórico de zk-SNARK
Origen: Décadas de 1980 y 1990
Como mencionamos, la prueba de conocimiento cero no es un concepto nuevo. Su definición, fundamento, teoremas importantes e incluso protocolos importantes relacionados aparecieron ya a mediados de la década de 1980. Apareció por primera vez en Goldwasser y Micali (fundador de Algorand) y Rackoff. artículo "La complejidad del conocimiento de los sistemas de prueba interactivos".
Las ideas y protocolos clave que utilizamos para construir la tecnología ZK-SNARK hoy se desarrollaron en la década de 1990. Por ejemplo, el protocolo Sumcheck simplifica la declaración de la suma de evaluaciones polinómicas multivariadas en puntos seleccionados aleatoriamente en la curva elíptica, este protocolo. sienta una base importante para la tecnología ZK.
Por lo tanto, la germinación de la idea de ZK en realidad precedió al surgimiento de Bitcoin. Sin embargo, en ese momento había una falta general de casos de uso adecuados para ZK y la gente no podía proporcionar la poderosa potencia informática necesaria para cumplir con el sistema de prueba ZK. Después de todo, Internet y los equipos de hardware no se desarrollaron en la década de 1990.
Acuerdo GKR (2007)
GKR (Goldwasser-Kalai-Rothblum) es un protocolo interactivo en el que el tiempo de ejecución del probador está relacionado linealmente con el número de puertas lógicas en el circuito, mientras que el tiempo de ejecución del verificador está relacionado sublinealmente con el tamaño del circuito. En el protocolo GKR, el probador y el verificador deben ponerse de acuerdo sobre los resultados de un circuito aritmético de dos entradas que se ejecuta en un campo finito. El circuito tiene una profundidad de d, siendo la capa d-ésima la capa de entrada y la capa 0. la capa de salida. El protocolo comienza con una declaración sobre la salida del circuito, que se reduce mediante recursividad a una declaración sobre la capa anterior. Finalmente, podemos transformar afirmaciones sobre la salida en afirmaciones sobre los parámetros de entrada del circuito, que pueden verificarse fácilmente. Se puede decir que el protocolo GKR está muy simplificado basándose en el protocolo Sumcheck mencionado anteriormente.
Esquema de compromiso polinómico KZG (2010)
En 2010, tres expertos en el campo ZK: Kate de la institución de investigación alemana MPI-SWS, Zaverucha de la empresa canadiense de criptografía Certicom Research y Goldberg de la Universidad de Waterloo publicaron conjuntamente un artículo "Compromisos de tamaño constante con los polinomios y sus aplicaciones". ". Este artículo propone un esquema de compromiso polinómico utilizando grupos de pares bilineales, denominado KZG.
La promesa consta de un único elemento de grupo, y el remitente puede revelar de manera eficiente cualquier evaluación correcta del polinomio y, con la ayuda de técnicas de procesamiento por lotes, se puede revelar la evaluación de múltiples polinomios. KZG promete convertirse en uno de los componentes básicos de algunos sistemas de prueba ZK conocidos (como halo2 utilizado por el equipo Ethereum PES), y también desempeña un papel central en el EIP-4844 de Ethereum. Para comprender el concepto de tecnología de procesamiento por lotes de manera más intuitiva, puede consultar el artículo sobre el puente Mina-Ethereum. Puente Mina-Ethereum.
Referencia: https://blog.lambdaclass.com/mina-to-ethereum-bridge/
Práctico sistema ZK-SNARK basado en curvas elípticas (2013)
La primera estructura práctica de ZK-SNARK apareció en 2013, requería un paso de preprocesamiento para generar claves de prueba y verificación, y era específica del programa o circuito, sin generalización. El tamaño de estas claves puede ser muy grande y depende de los propios parámetros secretos; si esta confidencialidad se ve comprometida, un atacante puede falsificar la prueba. En un sistema ZK-SNARK tan práctico, convertir el código en una forma demostrable requiere compilar el código en un conjunto matemático de restricciones polinómicas.
Inicialmente, el proceso anterior tenía que realizarse manualmente, lo que consumía mucho tiempo y era propenso a errores. Los cambios tecnológicos posteriores en esta dirección intentaron principalmente resolver los siguientes problemas centrales:
Proporcionar pruebas más eficientes
Reducir el número de preprocesamiento
Permite configuraciones genéricas en lugar de específicas del circuito.
Evite las configuraciones confiables
Desarrollar métodos para describir circuitos utilizando lenguajes de alto nivel en lugar de escribir restricciones polinómicas manualmente.
Acuerdo de Pinocho (2013)
El protocolo Pinocho es el primer sistema práctico zk-SNARK, basado en el Programa de Aritmética Cuadrática (QAP), con un tamaño de prueba inicial de 288 bytes. La cadena de herramientas de Pinocho proporciona un compilador que compila C en circuitos aritméticos, que luego se pueden convertir en QAP. El protocolo Pinocho requiere que el verificador genere claves, que no son universales sino específicas del circuito. Esto demuestra que la complejidad temporal asintótica de la generación del sistema y la configuración de claves aumenta linealmente con el tamaño del cálculo, y el tiempo de verificación aumenta linealmente con el tamaño de las entradas y salidas públicas.
Groth16(2016)
Groth presenta un nuevo algoritmo ZK con mayor rendimiento en el procesamiento de R1CS. R1CS es un sistema de restricciones de rango 1, un sistema de restricciones de primer orden, que es una forma de restricción polinomial en zk-SNARK. La prueba de Gorth es la más pequeña en tamaño de datos (contiene solo tres elementos de grupo) y es rápida de verificar, ya que requiere solo tres operaciones de emparejamiento y un paso de preprocesamiento para estructurar la cadena de referencia. Pero la principal desventaja de Gorth es que cada programa que necesita ser probado requiere diferentes configuraciones de confianza, lo cual es bastante inconveniente en aplicaciones prácticas.
Más tarde, Groth16 se utilizó en ZCash, que es un proyecto de blockchain de privacidad relativamente conocido (el fundador de Starkware, Eli, participó en él).
A prueba de balas y IPA (2016)
Una de las principales debilidades del esquema de compromiso polinómico KZG mencionado anteriormente es que requiere una configuración confiable. Bootle et al. propusieron un sistema eficiente de prueba de conocimiento cero que analiza la apertura de compromisos de Pedersen que satisfacen la relación intrínseca del producto. El producto interno demuestra que la prueba con complejidad lineal requiere mucho tiempo. El número de interacciones entre el probador y el verificador es logarítmico, pero el tiempo de verificación es lineal. Además, Bootle et al. también desarrollaron un esquema de compromiso polinomial que no requiere una configuración confiable. Estas ideas fueron adoptadas posteriormente por Halo2 y Kimchi, entre otros.
Sonic, Marlin y Plonk (2019)
Sonic, Plonk y Marlin abordan la necesidad de configuraciones de confianza en cada programa en el algoritmo Groth16 mediante la introducción de una cadena de referencia estructurada universal y actualizable que permite configuraciones de confianza que solo deben configurarse una vez. Entre ellos, Marlin proporciona un sistema de prueba basado en R1CS y se ha convertido en la tecnología central de Aleo.
Y Plonk introdujo un nuevo esquema aritmético (más tarde llamado Plonkish) y el uso de gran producto para verificar las restricciones de replicación. Plonkish también permite la introducción de puertas lógicas de circuitos especializados para operaciones específicas, las llamadas "puertas personalizadas". Muchos proyectos blockchain conocidos han utilizado versiones personalizadas de Plonk, incluidos Aztec, zkSync, Polygon zkEVM, Mina, Ethereum PSE team, Scroll, etc.
Espartano (2019)
Spartan proporciona un IOP para circuitos descritos utilizando R1CS, aprovechando las características de los protocolos de verificación de suma y polinomios multivariados. Al utilizar un esquema de compromiso polinómico adecuado, implementa un sistema zk-SNARK transparente y genera pruebas con complejidad temporal lineal.
Búsquedas (2020)
Gabizon y Williamson propusieron plookup en su artículo de 2020, utilizando grand-product para demostrar que un valor está contenido en una tabla de verdad precalculada, mostrando cómo introducir el parámetro plookup en el algoritmo Plonk.
Sin embargo, estos argumentos de búsqueda tienen un problema común. El probador necesita gastar enormes costos para construir una tabla de verdad completa, por lo que el trabajo anterior en torno a las búsquedas se ha dedicado a reducir el costo de la prueba.
Más tarde, Haböck introdujo LogUp en el artículo, que utiliza derivadas logarítmicas para transformar cheques de grandes productos en sumas de recíprocos. LogUp es fundamental para mejorar el rendimiento de Polygon zkEVM, ya que requiere dividir toda la tabla de verdad en varios módulos STARK. Estos módulos deben estar vinculados correctamente y las búsquedas entre tablas lo exigen. Desde entonces, la introducción de LogUp-GKR ha mejorado el rendimiento de LogUp a través del protocolo GKR.
Caulk es la primera solución que hace que el tiempo de prueba tenga una relación sublineal con el tamaño de la tabla de verdad. Su complejidad del tiempo de preprocesamiento es O(NlogN) y la complejidad del espacio de almacenamiento es O(N), donde N es el valor de verdad. Tamaño de la mesa. Siguieron otras soluciones, como Baloo, flookup, cq y caulk+. Además, Lasso propone varias mejoras que evitan comprometerse con tablas de verdad cuando tienen una estructura específica.
HyperPlonk (2022)
HyperPlonk se propuso en el artículo "HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates". HyperPlonk se basa en las ideas de Plonk, utilizando polinomios multivariables. No utiliza la división para verificar el cumplimiento de las restricciones, sino que se basa en un protocolo de verificación de suma. Al mismo tiempo, también admite restricciones de orden superior sin afectar el tiempo de generación de la prueba.
Debido al uso de polinomios multivariables, no es necesario realizar una transformada rápida de Fourier (FFT), lo que demuestra que el tiempo de generación aumenta linealmente con el tamaño del circuito. HyperPlonk también presenta un nuevo IOP de permutación adecuado para campos pequeños y adopta un protocolo basado en verificación de suma que reduce la carga de trabajo del probador, el tamaño de la prueba y el tiempo de verificación.
Sistema de prueba ZK que utiliza funciones hash a prueba de colisiones
Al mismo tiempo que se propuso Pinocho en 2013, hubo algunas propuestas para generar circuitos/esquemas aritméticos que podrían demostrar que la ejecución de instrucciones por parte de la máquina virtual era correcta. Aunque desarrollar esquemas aritméticos para máquinas virtuales es más complejo o menos eficiente que escribir circuitos especiales para algunos programas, tiene una ventaja importante: no importa cuán complejo sea el programa, solo necesitas demostrar que se ejecuta correctamente en la máquina virtual.
Algunas de las ideas de TinyRAM se perfeccionaron posteriormente en el diseño de la máquina virtual de Cairo, seguida de zk-evm y zkvm general, entre otras. El uso de funciones hash resistentes a colisiones en sistemas de prueba elimina la necesidad de configuraciones confiables u operaciones de curva elíptica, pero a costa de tiempos de prueba más prolongados.
Pequeña RAM (2013)
En "SNARKs for C", desarrollaron un sistema de prueba basado en PCP para demostrar que los resultados de ejecución de programas escritos en lenguaje C son correctos. El programa está compilado en TinyRAM, una VM simplificada. La VM tiene memoria de acceso aleatorio direccionable a nivel de bytes, el tamaño del circuito crece casi linealmente con la escala computacional y puede manejar de manera eficiente operaciones como bucles, flujo de control y accesos a la memoria.
Entre ellos, PCP se refiere a prueba probabilísticamente verificable, es decir, prueba probabilísticamente verificable. El verificador solo necesita leer una parte de la prueba seleccionada al azar para verificar la validez de la prueba con un alto grado de confianza. A diferencia de los sistemas de prueba tradicionales donde el verificador necesita verificar toda la prueba, el PCP solo requiere una aleatoriedad limitada para lograr una verificación eficiente.
Ligero（2017）
Ligero introdujo un sistema de prueba que permite pruebas de tamaño O (√￣n), donde n es el tamaño del circuito. Organiza coeficientes polinómicos en forma matricial. Brakedown se basa en Ligero e introduce el concepto de esquemas de compromiso polinómicos independientes del dominio.
STARKs (2018)
Los STARK (ARgumentos de conocimiento transparentes escalables) fueron propuestos por Eli Ben-Sasson et al. Alcanzan una complejidad de prueba de 𝑂(log²𝑛), tienen velocidades de verificación rápidas, no requieren una configuración confiable y se especula que son seguros poscuánticos. Son utilizados por Starkware/Starknet con la máquina virtual Cairo. Sus innovaciones clave incluyen la representación algebraica intermedia (AIR) y el protocolo Fast Reed-Solomon Interactive Oracle Proximity Proof (FRI). Además, los STARK también son utilizados por muchos proyectos blockchain conocidos (como Polygon Miden, RiscZero, Winterfell, Neptune, ZeroSync, zkSync, etc.).
nueva dirección de desarrollo
El uso de diferentes sistemas de prueba en aplicaciones prácticas demuestra las ventajas de diferentes métodos y promueve el desarrollo de ZK. Por ejemplo, el esquema aritmético de Plonkish proporciona una forma sencilla de incluir puertas lógicas personalizadas y argumentos de búsqueda; FRI ha demostrado un rendimiento excelente como PCS, lo que llevó al nacimiento de Plonky. Al mismo tiempo, el uso de comprobaciones de grandes productos en AIR (que incorpora AIR aleatorio preprocesado) mejora su rendimiento y simplifica los parámetros de acceso a la memoria. zk-STARK se está volviendo cada vez más popular debido a su mejor eficiencia de generación y la introducción de cada vez más funciones hash compatibles con ZK.
Nuevo esquema de compromiso polinómico (2023)
Con la aparición de SNARK eficientes basados en polinomios multivariados (como Spartan o HyperPlonk), existe un interés creciente en nuevos esquemas de compromiso adecuados para dichos polinomios. Binius, Zeromorph y Basefold proponen nuevas formas de comprometerse con polinomios multilineales. Binius tiene la ventaja de no tener gastos generales para representar tipos de datos (mientras que muchos otros sistemas de prueba utilizan al menos elementos de campo de 32 bits para representar bits individuales) y trabajar en el dominio binario. Este esquema de compromiso utiliza desaceleración, que está diseñado para ser independiente del dominio. Basefold generaliza FRI más allá de Reed-Solomon, permitiendo esquemas de compromiso polinomial (PCS) independientes del dominio.
La independencia del dominio es una propiedad del esquema de compromiso polinómico, lo que significa que en el esquema de compromiso polinómico, el proceso de compromiso no depende de las propiedades específicas de ningún dominio específico. Esto significa que se pueden hacer compromisos con polinomios de cualquier estructura algebraica, como cuerpos finitos, curvas elípticas o incluso anillos enteros.
Sistema de sujeción personalizable (2023)
CCS generaliza R1CS mientras captura la aritmética de R1CS, Plonkish y AIR sin gastos generales adicionales. El uso de CCS combinado con Spartan IOP da como resultado SuperSpartan, que admite restricciones de alta dimensión sin que el probador soporte costos criptográficos proporcionales al orden de las restricciones. En particular, SuperSpartan proporciona un SNARK para AIR a prueba de tiempo lineal.
Resumir
Este artículo revisa el progreso de la tecnología ZK desde mediados de los años 1980. Los avances en informática, matemáticas y hardware, junto con la introducción de blockchain, han llevado al surgimiento de sistemas de prueba ZK nuevos y más eficientes, abriendo el camino a muchas aplicaciones potencialmente transformadoras de la sociedad.
Investigadores e ingenieros han propuesto mejoras al sistema ZK en función de las necesidades, centrándose en aspectos como el tamaño de la prueba, el uso de memoria, la transparencia, la seguridad anticuántica, el tiempo de prueba y el tiempo de verificación. Aunque ZK siempre ha tenido dos categorías principales de soluciones de implementación principales (SNARK y STARK), los límites entre los dos se han desdibujado gradualmente y se están combinando las ventajas de diferentes sistemas de prueba, como la combinación de diferentes esquemas aritméticos con un nuevo esquema de compromiso polinomial.
Podemos esperar que sigan surgiendo nuevos sistemas a prueba de ZK y que su rendimiento siga mejorando. Para las aplicaciones que utilizan estos sistemas de prueba, si no pueden seguir el desarrollo iterativo de la última tecnología y reconstruir y aplicar continuamente los últimos algoritmos, la posición de liderazgo actual será solo temporal.
