Aclarar el desarrollo histórico de la tecnología ZK

ZK Pruebas es un poderoso primitivo criptográfico que permite que una parte (proverbio) convencer a la otra parte (verbo) de que una declaración dada es verdadera y válida sin revelar ninguna información privada.En los últimos años, ZK ha recibido atención generalizada en los campos de la computación privada verificable, proporcionando prueba de efectividad para los programas de computadora y blockchain, y ha jugado un papel positivo significativo en el desarrollo del mundo.

Aunque ZK es una tecnología emergente, sus ideas y conceptos básicos se remontan a la década de 1980.Después de combinarse con blockchains como Bitcoin y Ethereum, el desarrollo de la tecnología ZK se ha acelerado significativamente.Debido a que Blockchain puede demostrar su efectividad a través de Snark y Stark, y mejorar en gran medida su escalabilidad, esto hace que ZK sea popular en el campo Blockchain.

Como dijo el fundador de Starkware, Eli Ben-Sasson, en los últimos años hemos sido testigos de la «explosión del cámbrico» del sistema de prueba criptográfica.Cada sistema de prueba tiene sus propias fortalezas y debilidades únicas y se intercambia cuando se diseña.El avance del hardware, los mejores algoritmos, los nuevos argumentos y las herramientas periféricas han estimulado la mejora del rendimiento del sistema ZK y el nacimiento de un nuevo sistema.Se han adoptado muchos sistemas de prueba en aplicaciones prácticas, y las personas aún están ampliando los límites de ZK.

Esto también lleva a las personas a pensar profundamente sobre una pregunta:¿Existe un sistema universal de prueba de ZK para todas las aplicaciones?No creemos que sea muy probable.Hay tres razones:

1. Diversidad de aplicaciones;

2. Diferentes tipos de restricciones (incluida la memoria, el tiempo de verificación y el tiempo de prueba);

3. La necesidad de robustez (si un sistema de prueba está pirateado, aún podemos cambiar a otros sistemas como seguro).

Según las razones anteriores, el ZK demuestra que el sistema debería ser diverso.Pero incluso si hay muchos tipos de sistemas de prueba, debe haber una comunidad significativa: la prueba de ZK se puede verificar rápidamente.Y tener una capa de verificación puede adaptarse fácilmente al nuevo sistema de prueba para resolver las dificultades relevantes de la capa subyacente de las que depende (como Ethereum).

En el campo ZK, ZK-Snark se menciona con frecuencia.Es una forma de realizar una prueba de conocimiento cero, que permite una prueba eficiente de conocimiento cero mediante el uso de herramientas matemáticas complejas como el emparejamiento bilineal y los circuitos aritméticos.La característica de ZK-Snark es que el proceso de prueba es simple y no interactivo, y solo se requiere una sola comunicación entre el Prover y el verificador y el verificador, no se requieren interacciones múltiples.también,El tamaño de prueba de ZK-Snark es muy corto y tiene 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 limitaciones de ZK-Snark.ZK-Stark no se basa en entornos confiables y utiliza sistemas de construcción matemáticos más transparentes, como el compromiso polinómico y las operaciones de dominio finito, colisiones hash, etc. para generar y verificar las pruebas.ZK-Stark es más escalable que ZK-Snark, adecuado para la computación a mayor escala, lo que demuestra generar más rápido, pero la prueba en sí suele ser de mayor tamaño.

Se puede decir que ZK-Snark y ZK-Stark son formas de uso común en la prueba de conocimiento cero, pero varían en términos de transparencia, escalabilidad, tamaño de prueba, etc.

En general,Un sistema de prueba de ZK generalmente incluye dos partes: PIOP (oráculo interactivo polinomial) y PC (esquema de compromiso polinómico).Las soluciones de PIOP comunes incluyen Plonkish, GKR, etc., mientras que las soluciones de PCS comunes incluyen FRI, KZG, IPA, etc. Por ejemplo, la versión ZCash de Halo2 utiliza el método de implementación de PLONKISH+IPA. ser considerado como un ZK-Snark especial basado en viernes.

Si es más detallado, los diferentes tipos de sistemas de prueba utilizarán diferentes esquemas de compromiso polinómico (PC), esquemas aritméticos, pruebas interactivas de Oracle (PIO) o pruebas de probabilidad (PCP).

Más,Diferentes sistemas de prueba de ZK a menudo difieren en los siguientes indicadores:

Hipótesis criptográfica: función de hash anticollision, problemas logarítmicos discretos en curvas elípticas, conocimiento exponencial
Configuración transparente frente a la configuración de confianza
Lento para generar pruebas: lineal vs hiperlineal
Lundo para la verificación de las pruebas: tiempo constante, tiempo de registro, sublinear, lineal
Probar el tamaño del tamaño
La simplicidad de la recursión
Esquema aritmético
Univariado vs polinomio multivariado

A continuación, hablaremos brevemente sobre el origen de la tecnología ZK, exploraremos sus bloques de construcción básicos y describiremos el aumento y la caída de los diferentes sistemas de prueba de ZK.Al mismo tiempo, este artículo no realiza un análisis detallado del sistema de prueba en sí, sino que se centra en aquellos que han tenido un profundo impacto en el campo.Después de todo, el desarrollo de cualquier industria solo es posible a través de las grandes ideas de los pioneros y atrayendo a la práctica.

El contexto de desarrollo histórico de ZK-Snark

Origen: 1980 a 1990s

Como mencionamos, la prueba de conocimiento cero no es un concepto nuevo.La primera aparición fue en Goldwasser, Micali (fundador de Algorand) y los documentos de RackoffLa complejidad del conocimiento de los sistemas de prueba interactiva«medio.

yLas ideas y protocolos clave que utilizamos para construir tecnología ZK-Snark se publicaron en la década de 1990.Por ejemplo, el protocolo SumCheck simplifica la declaración de suma de evaluación de múltiples polinomios a la evaluación única de puntos seleccionados al azar en la curva elíptica, que sienta una base importante para la tecnología ZK.

Por lo tanto, la aparición de ideas ZK es en realidad mucho antes que la aparición de Bitcoin.Sin embargo, en ese momento, había una falta general de casos aplicables para ZK, y las personas no podían proporcionar la potente potencia informática requerida para cumplir con el sistema de prueba de ZK.

Protocolo GKR (2007)

GKR (Goldwasser-Kalai-Rothblum) es un protocolo interactivo.En el protocolo GKR, el prover y el verificador deben acordar los resultados de la operación del circuito aritmético de doble entrada en un dominio finito, cuya profundidad es D, la capa d-th es la capa de entrada y el 0-° La capa es la capa de salida.El protocolo comienza con una declaración sobre la salida del circuito y lo simplifica a una declaración de la capa anterior por recursivamente.Finalmente, podemos convertir la declaración en la salida en una declaración de los parámetros de entrada del circuito, que se verifica fácilmente.Se puede decir que el protocolo GKR está altamente simplificado en función del protocolo SumCheck antes mencionado.

Solución 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 compañía de criptografía canadiense Certicom Research y Goldberg de la Universidad de Waterloo publicó conjuntamente un documento «Compromisos de tamaño constante para polinomials y sus aplicaciones》.Este papelSe propone un esquema de compromiso polinómico utilizando grupos de pares bilineales, llamado KZG.

Esta promesa consiste en un elemento de grupo separado, y el comitvero puede revelar eficientemente cualquier evaluación correcta del polinomio, y con la ayuda de la tecnología de procesamiento por lotes, se puede revelar la evaluación de múltiples polinomios.KZG prometió convertirse en uno de los bloques de construcción básicos de algunos sistemas de prueba de ZK conocidos (como Halo2 utilizados por el grupo Ethereum PES), y también jugó 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 de Mina-Ethereum.

Referencia: https://blog.lambdaclass.com/mina-to-ethereum-fridge/

Sistema práctico de ZK-Snark basado en curvas elípticas (2013)

La primera estructura práctica de ZK-Snark apareció en 2013 y requirió un paso de preprocesamiento para generar una clave de prueba y una clave de verificación, y es específica de programas o circuitos y no universales.Estas claves pueden ser de gran tamaño y depender de los parámetros secretos en sí mismas;En este práctico sistema ZK-SNARK, para convertir el código en una forma probada, es necesario compilar el código en un conjunto de formas matemáticas de restricciones polinomiales.

Al principio, el proceso anterior debe completarse manualmente, lo que requiere mucho tiempo y es propenso a errores.Más tarde, en respuesta a los cambios tecnológicos en esta dirección, tratamos principalmente de resolver los siguientes problemas centrales:

Proporcionar pruebas más eficientes
Reducir el número de preprocesamiento
Implementar configuraciones universales en lugar de circuitos específicos
Evite la configuración confiable
Desarrollar métodos para describir los circuitos en idiomas de alto nivel, en lugar de escribir restricciones polinomiales manualmente

Protocolo de Pinocho (2013)

El protocolo de Pinocho es el primer sistema ZK-Snark que está realmente disponible.Según un programa aritmético cuadrático (QAP), el tamaño de prueba inicial es de 288 bytes.La cadena de herramientas de Pinocho proporciona un compilador que compila el lenguaje C en circuitos aritméticos, que se pueden convertir aún más en QAP.El protocolo de Pinocho requiere que el verificador genere claves que no son universales pero que sean específicos del circuito.La complejidad del tiempo progresivo de la generación del sistema y la configuración clave del sistema de prueba está linealmente relacionada con la escala de cálculo, y el tiempo de verificación está relacionado linealmente con el tamaño de la entrada y salida comunes.

Groth16 (2016)

Groth introdujo un nuevo algoritmo ZK-ILM que tiene un mayor rendimiento en el manejo de R1C.R1CS es un sistema de restricción de primer orden, que es un formulario de restricción polinomial en ZK-Snark.La prueba de Gorth es el tamaño de datos más pequeño (incluidos solo tres elementos de grupo), y la velocidad de verificación es muy rápida.Simplemente haga tres operaciones de emparejamiento y un paso de preprocesamiento que estructura la cadena de referencia.Pero la principal desventaja de Gorth es que cada programa que debe probarse requiere diferentes configuraciones de confianza, lo cual es bastante inconveniente en las aplicaciones prácticas.

Más tarde, Groth16 se utilizó en Zcash, un proyecto de blockchain de privacidad relativamente famoso (involucrado por el fundador de Starkware Eli).

Bulletproofs e IPA (2016)

Una de las principales debilidades del esquema de compromiso polinómico KZG antes mencionado es la necesidad de un entorno confiable.Bootle et al.La prueba de la prueba del producto interno con complejidad lineal lleva tiempo, el número de interacciones entre el Prover y el verificador es logarítmico, pero el tiempo de verificación es lineal.Además, Bootle et al.Estas ideas fueron adoptadas más tarde por Halo2 y Kimchi.

Sonic, Marlin y Plonk (2019)

Sonic, Plonk y Marlin resuelven el problema de que cada programa en el algoritmo GROTH16 requiere configuraciones confiables, introduciendo una cadena de referencia estructurada común y actualizada (utilizada para implementar configuraciones confiables que solo requieren una vez).en,Marlin proporciona un sistema de prueba basado en R1CS y se ha convertido en la tecnología central de Aleo.

Plonk presenta un nuevo esquema aritmético (más tarde conocido como Plonkish) y utiliza el producto de abuelo para verificar las restricciones de replicación.Plonkish también permite la introducción de puertas lógicas de circuito dedicadas para operaciones específicas, las llamadas «puertas personalizadas».Muchos proyectos de blockchain bien conocidos han utilizado versiones personalizadas de Plonk, incluidos Aztec, Zksync, Polygon Zkevm, Mina, Ethereum PSE Group y Scroll.

espartano(2019)

Spartan proporciona una PIO para los circuitos descritos utilizando R1Cs, utilizando las características de los polinomios multivariados y los protocolos de prueba de suma.Al utilizar un esquema de compromiso polinómico adecuado, implementa un sistema transparente ZK-SNARK y la complejidad del tiempo para generar la prueba es lineal.

Buscas (2020)

Gabizon y Williamson propusieron un avance en su artículo en 2020,Uso de un gran producto para demostrar que se incluye un valor en la tabla de verdad precalculada, que muestra cómo introducir parámetros de reducción en el algoritmo PLONK.

Sin embargo, estos argumentos de búsqueda tienen un problema común, y los procesadores deben gastar mucho dinero para construir una mesa de verdad completa, por lo que el trabajo previo en torno a las búsquedas se ha dedicado a reducir el costo de la prueba.

Más tarde, Haböck introdujo logup en su artículo, que utiliza derivados de registros para convertir la verificación del producto Grand-Product en la suma de los recíprocos.Logup es crítico para las mejoras de rendimiento en Polygon Zkevms, ya que necesitan dividir toda la tabla de verdad en múltiples módulos Stark.Estos módulos deben estar correctamente vinculados, y las búsquedas transversales pueden forzar esto.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 para hacer la relación sublineal probada con el tamaño de la tabla de verdad.Siguieron otras soluciones, como Baloo, Flookup, CQ y Caulk+.Además, Lasso propone varias mejoras para evitar comprometerse con la tabla de verdad cuando tiene una estructura específica.

Hyperplonk (2022)

Hyperplonk se propuso en el papel «Hyperplonk: plonk con prover en tiempo lineal y puertas personalizadas de alto grado».Hyperplonk se basa en el concepto de Plonk y adopta polinomios multivariados.En lugar de usar la división para verificar la ejecución de restricciones, se basa en el protocolo de prueba de suma.Al mismo tiempo, también admite restricciones de orden superior sin afectar el tiempo de generación de pruebas.

Debido a que se utilizan polinomios multivariados, no es necesario realizar una transformación rápida de Fourier (FFT), se demuestra que el tiempo generado está relacionado linealmente con la escala del circuito.Hyperplonk también introduce un nuevo PIO de permutación para campos pequeños y adopta un protocolo basado en suma que reduce la carga de trabajo de los protuberancias, el tamaño de la prueba y el tiempo de verificación.

Sistema de prueba de ZK utilizando la función hash anticollision

Si bien se propuso Pinocho en 2013, hay algunas soluciones para generar esquemas de circuito/aritmética que pueden probar que la máquina virtual ejecuta las instrucciones correctamente.Aunque desarrollar un esquema aritmético para una máquina virtual es más complejo o menos eficiente que escribir circuitos dedicados para algunos programas, tiene una ventaja importante: no importa cuán complejo sea el programa, solo demuestre que se ejecuta correctamente en la máquina virtual.

Posteriormente, algunas ideas en Tinyram se mejoraron en el diseño de máquinas virtuales de El Cairo, seguidas de ZK-EVM y ZKVM de propósito general.El uso de funciones hash resistentes a la colisión en sistemas de prueba elimina la necesidad de configuraciones confiables o operaciones de curva elíptica, pero a costa de la prueba más.

Tinyram (2013)

En «Snarks for C», desarrollaron un sistema de prueba basado en PCP para demostrar que los resultados de ejecución de los programas escritos en C son correctos.El programa se compila en Tinyram, una VM simplificada.La VM tiene memoria aleatoria direccionable a nivel de byte, y el tamaño del circuito aumenta cuasi linealmente en la escala informática, y puede manejar las operaciones de manera eficiente como bucles, flujos de control y acceso a la memoria.

en,PCP se refiere a una prueba probable probabilísticamente, lo que significa que la prueba de probabilidad puede verificar la validez de la prueba con una alta confianza leyendo una pequeña parte del contenido seleccionado al azar en la prueba.A diferencia de los sistemas de prueba tradicionales donde los verificadores deben verificar toda la prueba, PCP solo requiere una aleatoriedad limitada para lograr una verificación eficiente.

Ligero (2017)

Ligero introdujo un sistema de prueba que puede implementar pruebas de tamaño O (√￣n), donde n es el tamaño del circuito.Organiza coeficientes polinomiales en forma de matriz.Braedown se basa en Ligero e introduce el concepto de un esquema de compromiso polinómico independiente del dominio.

Starks (2018)

Starks (argumentos transparentes escalables de conocimiento) fueron propuestos por Eli Ben-Sasson et al.Implementan la complejidad de prueba de? (¿Log²⁡?), Tienen velocidades de verificación rápidas, no requieren una configuración confiable y se especula que es una seguridad posterior al quanten.Los ponen en uso mediante máquinas virtuales Starkware/Starknet y El Cairo.Sus innovaciones clave incluyen la representación intermedia algebraica (AIR) y los protocolos rápidos de prueba de prueba de oráculo (FRI) interactivos de Reed-Solomon.Además, los Starks también son utilizados por muchos proyectos de blockchain bien conocidos (como Polygon Miden, Risczero, Winterfell, Neptuno, 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 manera fácil de incluir puertas lógicas personalizadas y argumentos de búsqueda;Mientras tanto, el uso de la verificación de productos de abuelos en el aire (aire aleatorizado que trae preprocesamiento) mejora su rendimiento y simplifica los parámetros de acceso a la memoria.ZK-Stark se está volviendo cada vez más popular porque es mejor en la eficiencia de la generación y se están introduciendo más funciones hash amigables con ZK.

Nuevo esquema de compromiso polinómico (2023)

Con la aparición de snarks eficientes basados en polinomios multivariados, como Spartan o Hyperplonk, existe un creciente interés en los nuevos esquemas de compromiso aplicables a tales polinomios.Binius, Zeromorph y Basefold proponen nuevas formas de prometer polinomios multilineales.Binius tiene la ventaja de no tener una sobrecarga adicional al denotar tipos de datos (mientras que muchos otros sistemas de prueba usan al menos elementos de campo de 32 bits para representar bits únicos) y trabajar en dominios binarios.El esquema de compromiso utiliza un frenado diseñado para fines independientes del campo.Basefold generaliza el FRI además de Reed-Solomon, logrando así un esquema de compromiso polinómico independiente del dominio (PCS).

El dominio independiente es una propiedad de un esquema de compromiso polinómico, que se refiere al proceso de compromiso en un esquema de compromiso polinómico que no depende de propiedades específicas de ningún dominio en particular.Esto significa que se pueden hacer compromisos a polinomios de cualquier estructura algebraica, como dominios finitos, curvas elípticas e incluso anillos enteros.

Sistema de restricción personalizable (2023)

CCS generaliza R1C mientras captura la aritmética de R1C, plonkish y aire sin sobrecarga adicional.El uso de CCS en combinación con PIO espartana puede generar SuperSpartan, lo que respalda las restricciones de alta dimensión sin la necesidad de soportar el costo de cifrado proporcional al orden de restricción.En particular, SuperSpartan proporciona a Air un sarcástico de tiempo lineal a prueba de tiempo.

Resumir

Este artículo revisa el progreso de la tecnología ZK desde mediados de la década de 1980.Los avances en ciencias de la computación, matemáticas y hardware, junto con la introducción de blockchain, han dado lugar a sistemas de prueba de ZK nuevos y más eficientes, abriendo el camino para muchas aplicaciones que pueden cambiar la sociedad.

Los investigadores e ingenieros propusieron mejoras al sistema ZK basado en la demanda, centrándose en el tamaño de la prueba, el uso de la memoria, la transparencia, la resistencia a la seguridad cuántica, el tiempo de prueba y el tiempo de verificación.Aunque siempre ha habido dos categorías principales de las soluciones de implementación convencionales de ZK (Snark y Starks), los límites entre los dos se han bordeado gradualmente y se están combinando las ventajas de diferentes sistemas de prueba, como combinar diferentes soluciones aritméticas con nuevos compromiso polinómico esquema.

Podemos esperar que el nuevo sistema de prueba de ZK continúe emergiendo y el rendimiento continúe mejorando.Para aplicaciones que utilizan estos sistemas de prueba, si no pueden seguir el desarrollo iterativo de las últimas tecnologías y reconstruir continuamente y aplicar los últimos algoritmos, su posición de liderazgo actual es solo temporal.

Enlace original:https://blog.lambdaclass.com/our-highly-subjective-view-on-tistory-of-zero-knowledge-proofs/