Por qué no puedo entender la prueba de conocimiento cero: análisis de malentendidos comunes de ZKP

"He dado vueltas innumerables veces en el campo de las pruebas de conocimiento cero. La razón por la que he tomado muchos desvíos es que tengo malentendidos preconcebidos sobre las pruebas de conocimiento cero desde el principio. El marco, porque el marco es incorrecto, es imposible construir una casa que no se derrumbe sobre la base de ella.

En este artículo, intentaré corregir estos conceptos erróneos. Si estás aprendiendo pruebas de conocimiento cero y te sientes confundido, espero que los errores que cometí puedan iluminarte; si recién estás comenzando a entender las pruebas de conocimiento cero, espero que este artículo le ayudará a construir un marco básico. En mi opinión, estos puntos discutidos en el artículo son el misterio de la prueba de conocimiento cero y revelan por qué funciona la prueba de conocimiento cero.

Cabe señalar que el siguiente conocimiento corregido puede seguir siendo un conocimiento inexacto, solo puede usarlo como referencia y seguir cuestionándolo.

1. La prueba de conocimiento cero es un método de prueba

Si conocemos el algoritmo de la evolución del universo, pero no conocemos el valor inicial del universo, en este momento Alicia dice que conoce el valor inicial, pero no le creemos, entonces toma un conjunto de datos como entrada del algoritmo, calcula una pasada y obtiene un El universo es exactamente igual que el universo En este momento, ¿creeremos que el conjunto de datos de Alicia es el valor inicial del universo? Lo creeremos.

Esta es una prueba de conocimiento cero, para ser precisos, debería llamarse prueba de conocimiento cero. A través de este método de prueba, Alice puede demostrar que tiene conocimiento (el valor inicial del universo) sin filtrar el conocimiento.

Si observa el proceso de prueba de Alice, encontrará que solo involucra tres objetos: valor inicial, algoritmo evolutivo y resultado evolutivo (status quo), que podemos resumir como: entrada de algoritmo, algoritmo, salida de algoritmo y prueba de conocimiento cero. Es necesario poder probar que la salida es efectivamente calculada por la entrada a través de un cierto algoritmo.

De esta manera, si el verificador ve que la salida es correcta y la prueba muestra que la salida se calculó usando la entrada, entonces el verificador puede confiar en la entrada sin conocer la entrada.

La pregunta resultante es: ¿cómo probar que la salida es calculada por la entrada a través de un cierto algoritmo? ¿En lugar de otras entradas, otras salidas u otros algoritmos? Este es el problema que pretende resolver el protocolo de prueba de conocimiento cero.

En la serie de protocolos zk-SNARK, el método adoptado es convertir la entrada, el algoritmo y la salida en un polinomio y vincular los tres a través del polinomio. Si se puede demostrar que Alice conoce el polinomio, se puede considerar que el algoritmo de entrada calcula la salida de Alice.

Con todo, debido a que las pruebas de conocimiento cero se usan ampliamente para lograr la protección de la privacidad, y la protección de la privacidad significa no filtrar datos, es más fácil para nosotros pensar en cómo oculta los datos desde el principio. Pero si usa "cómo logra el conocimiento cero" como pista para entenderlo, será un desastre, y si usa "cómo logra la prueba" como pista, una línea lo atravesará claramente.

2. La prueba de conocimiento cero solo puede lograr el "conocimiento cero" del conocimiento específico

Las herramientas criptográficas, como las funciones hash y los algoritmos de cifrado basados ​​en curvas elípticas, pueden ocultar cualquier dato en casi cualquier situación (en términos prácticos, si el espacio de entrada es demasiado pequeño, no se puede ocultar); cuando sabemos que el conocimiento cero la prueba no puede filtrar conocimiento, a menudo pensamos que se le puede entregar conocimiento arbitrario para su procesamiento, pero de hecho, la prueba de conocimiento cero solo puede realizar "conocimiento cero" de conocimiento específico en escenarios específicos.

Volviendo al ejemplo de Alice, en su proceso de prueba de conocimiento cero, están involucradas al menos tres cosas que pueden llamarse conocimiento: 1. El valor inicial del universo, 2. El algoritmo de evolución del universo, 3. El resultado de la evolución de el universo. ¿No se pueden revelar estos diferentes tipos de conocimiento a través de pruebas de conocimiento cero? No, incluso debemos conocer el algoritmo de evolución y el resultado de la evolución del universo para probar si Alice conoce el valor inicial del universo.

En otras palabras, la prueba de conocimiento cero solo puede probar pero no filtrar el conocimiento de la posición de "entrada". Al pensar o utilizar un protocolo de prueba de conocimiento cero para resolver un problema, es necesario ver si el conocimiento que no se quiere filtrar se puede colocar en la posición de entrada y una salida que se puede juzgar como verdadera o falso se puede generar a través de un algoritmo definido (más precisamente, puede ser No para construir una relación NP).  

Por ejemplo, si Alicia afirma conocer un número x sin ninguna condición adjunta, es difícil para nosotros usar la prueba de conocimiento cero para demostrar que conoce el número x sin revelar x; pero si Alicia afirma conocer un número x que satisface A cierta condición a, entonces primero puede tener un algoritmo, la salida del algoritmo debe cumplir con la condición a (se puede convertir a la salida debe ser verdadera), y luego, si la entrada x puede satisfacer este algoritmo, puede creer que el número x satisface la condición a. Esto también significa que Alice puede usar los datos sin filtrarlos.

Sin embargo, hay otro lugar confuso aquí, es decir, la prueba de conocimiento cero no prueba directamente que alguien tiene la capacidad de resolver un determinado problema, como la capacidad de resolver el problema de los tres colores del mapa, prueba que alguien sabe un conjunto del problema desatar. (Nota: puede probar que el probador tiene el poder de cómputo para resolver el problema de los tres colores pidiéndole que resuelva varias instancias diferentes del problema de los tres colores). 

Esto está relacionado con la construcción del protocolo de prueba de conocimiento cero. Como se mencionó anteriormente, lo que prueba es un polinomio que une la entrada, el algoritmo y la salida, en lugar de un polinomio que resuelve el algoritmo. Prueba que el polinomio es De hecho, es para probar que existe una relación definida entre la entrada, el algoritmo y la salida, no para probar otras cosas.  

Por un lado, esta estructura limita la aplicación de la prueba de conocimiento cero. Solo puede realizar una prueba de entrada de conocimiento cero cuando la entrada, el algoritmo y la salida están completos. Si la salida es verdadera, se puede creer que la entrada es verdadero; pero por otro lado, esta construcción extiende la otra aplicación de las pruebas de conocimiento cero, es decir, si la entrada es verdadera, también podemos confiar en que la salida sea verdadera.

3. ¿Por qué la prueba de conocimiento cero encaja tan bien con la cadena de bloques 

Blockchain activa la aplicación de prueba de conocimiento cero, y la prueba de conocimiento cero proporciona una excelente solución para blockchain.La razón principal por la que los dos pueden promocionarse mutuamente radica en las características del sistema de blockchain y el método de prueba de las características de prueba de conocimiento cero, no solo porque las pruebas de conocimiento cero pueden proteger la privacidad.

Recordemos que hacemos el gran problema de la prueba matemática, que es una especie de prueba inferencial, con un proceso de derivación estricto y verificable; pero existe otro tipo de prueba llamada prueba interactiva, que no pasa la deducción, pero con la ayuda de la probador En la interacción con el verificador, el verificador hace preguntas al probador, y si el probador puede dar la respuesta correcta, se considera que la proposición afirmada por el probador es correcta.

Para dar un ejemplo que no es particularmente preciso: Alice afirma que cuando la entrada del universo es x, la salida es 42, y la prueba inferencial significa que necesita sustituir x en el cálculo paso a paso, calcular 42 y mostrar el proceso de cálculo para la verificación; interactivo La fórmula de prueba parece ser: dale al verificador un transbordador de universo paralelo, el verificador viaja aleatoriamente al universo con salida (la entrada es x), y luego juzga si la afirmación de Alice es creíble de acuerdo con si la la salida del universo es 42.

En comparación con la prueba de razonamiento, el verificador de prueba interactiva solo necesita verificar uno o varios puntos, lo cual es una razón importante por la cual la prueba de conocimiento cero encaja con blockchain: blockchain es un sistema distribuido, cada Nodo tiene que repetir el trabajo de verificación, Beneficiándose de solo necesitar verificar el punto de desafío, el sistema de prueba de conocimiento cero sucinto (Sucinto) puede reducir el trabajo de verificación, y lo que proporciona al verificador es una prueba que es mucho más pequeña que la propuesta original.

Hablando visualmente: en un sistema sin cadena de bloques, la prueba de conocimiento cero reduce el trabajo de un verificador y puede aumentar el trabajo de un probador al mismo tiempo (no necesariamente una relación 1: 1). Sin embargo, en el sistema de cadena de bloques, si hay 100 nodos, la carga de trabajo total se puede reducir en 100, y solo se agrega un certificador en este momento, entonces este beneficio es obvio.

Además, desde la perspectiva de usar la prueba de conocimiento cero para resolver problemas, los recursos de espacio y tiempo en la cadena de bloques son extremadamente escasos, y la prueba de conocimiento cero simple produce pruebas pequeñas y un tiempo de verificación corto, lo cual es adecuado como prueba. en la solución blockchain.s.

Sin embargo, debe tenerse en cuenta que la prueba interactiva solo necesita verificar los puntos de desafío.Otra diferencia entre la prueba inferencial que la acompaña y la prueba interactiva es que la prueba inferencial puede probar si una proposición es verdadera, pero la prueba interactiva solo puede probar que una proposición es verdadera. la proposición está en el si es probable.

Es decir, si la proposición reclamada por el probador es incorrecta, pero el probador obtiene la respuesta correcta cuando el verificador hace la pregunta, el verificador pensará que la proposición es verdadera. Por lo tanto, en el diseño del protocolo de prueba de conocimiento cero, una parte muy importante del trabajo es usar métodos matemáticos para que sea casi imposible que el probador obtenga la respuesta correcta (basado en ciertas suposiciones sobre el poder de cómputo del probador). , el probador usa pruebas falsas para convencer al verificador de que es cierto) La probabilidad de es una función despreciable).

Volvamos a zk-SNARK. zk-SNARK convierte la prueba de la relación entre la entrada, el algoritmo y la salida en un polinomio que une la relación entre los tres y puede proporcionar al verificador un transbordador de universo paralelo. En el protocolo Pinocchio (un tipo de zk-SNARK), la prueba interactiva se ve así:

El probador afirma conocer un polinomio p(x), que se puede descomponer en t(x) y h(x), es decir, p(x)=t(x) h(x); el verificador elige aleatoriamente un desafío punto s, al encriptar s, el probador solo puede calcular p(s) y h(s), pero no puede calcular t(s); el probador le da p(s) y h(s) al verificador, y verifica si el el probador tiene t(s), puede calcular si t(s) h(s) es igual a p(s), si son iguales, se cree que el probador realmente conoce un polinomio.

Conocer un polinomio significa que existe una relación definida entre la entrada, el algoritmo y la salida. Si la salida es verdadera, podemos creer que la entrada es verdadera sin conocer la entrada, es decir, realizar una prueba de conocimiento cero. Entonces, hasta ahora, no solo sabemos que la prueba de conocimiento cero es un método de prueba, sino también cómo se hace.

4. No se deje engañar por "no se requiere interacción"

La prueba de conocimiento cero es un sistema de prueba interactivo que se basa en dos elementos importantes: la interacción y la aleatoriedad.

Interacción significa que una parte propone un desafío y la otra parte da una prueba, sin esta interacción no se puede realizar una prueba de conocimiento cero, aleatorio significa que el punto de desafío debe ser aleatorio, es decir, no puede ser predicho por el probador. , de lo contrario, el probador puede Construir una prueba falsa en el punto de desafío. Si Alicia sabe de antemano que el verificador irá al universo paralelo No. 73, puede cambiar la respuesta del No. 73 a 42 por adelantado.  

Entonces, ¿por qué zk-SNARK se llama a sí mismo no interactivo (Non-interactive)? En la llamada prueba interactiva, el verificador primero debe dar un punto aleatorio y luego el probador construye la prueba; en la llamada prueba no interactiva, como el protocolo de Pinocho, ya no se requiere que el verificador dé un punto aleatorio. En cambio, un tercero de confianza otorga puntos aleatorios durante la fase de inicialización, de modo que el probador puede dar la prueba directamente, y el verificador solo necesita verificar la prueba, y no hay necesidad de interacción entre el verificador y el probador

El punto aleatorio proporcionado por un tercero de confianza es la configuración de confianza (Configuración de confianza) del protocolo Pinocho. En comparación con la interacción directa, la configuración de confianza debe proporcionar t(s) adicionales además del punto aleatorio s ), porque el verificador necesita verificar con t(s). Pero el problema es que el probador no puede conocer t(s), de lo contrario, puede construir fácilmente una prueba falsa, por lo que se necesita usar un método para transformar t(s), de modo que se pueda usar la t(s) transformada para verificación, pero no disponible para cálculos probadores. El protocolo de Pinocho elige una operación de emparejamiento bilineal para hacer esto.

Por lo tanto, ninguna interacción es más un proceso técnico. Para las pruebas de conocimiento cero, la verificación siempre se realiza en puntos de desafío aleatorios. La diferencia es de dónde provienen los puntos de desafío. Para diferentes protocolos específicos, el método elegido al reemplazar la interacción por la no interacción será bastante diferente, incluso si todos se llaman protocolos zk-SNARK, esta es una atención adicional.

5. Modularización y Disciplinas Jóvenes

Espero que los cuatro puntos anteriores puedan ayudarlo a comprender las pruebas de conocimiento cero. Al final del artículo, hay dos pequeños entendimientos que pueden salir mal.

Primero, el protocolo de prueba de conocimiento cero, como zk-SNARK, no se desarrolla en torno a una determinada fórmula central, es modular y cada módulo es responsable de completar su propio trabajo, y luego todos se combinan. Entonces, si desea comprender la prueba de conocimiento cero captando un punto central, será más difícil. Una mejor manera es entenderlo a través de una pista.

Al mismo tiempo, zk-SNARK no se refiere a un protocolo específico. Es un término general para una clase de métodos. Los módulos que lo componen generalmente permanecerán sin cambios, pero los métodos específicos seleccionados por estos módulos son variables. Entonces, cuando vea diferentes zk-SNARK, no se confunda, salte y mírelo a la altura del módulo, en lugar de quedarse atascado en métodos específicos.

En segundo lugar, tal vez porque la prueba de conocimiento cero se trata de matemáticas, a menudo le da a la gente la sensación de un tema antiguo, pero de hecho, la investigación sobre la prueba de conocimiento cero aún es muy temprana y la aplicación de la prueba de conocimiento cero acaba de comenzar. . Al elegir usar pruebas de conocimiento cero, los desarrolladores no solo necesitan diseñar un conjunto de teorías maduras, sino también encontrar/inventar métodos y aplicarlos al mismo tiempo.

Así que tal vez podamos ser más pacientes con las pruebas de conocimiento cero. Puede ser una parte importante del mundo digital en el futuro. No es solo una herramienta para usar los datos que constituyen el mundo digital, sino también una herramienta para salvar la recursos más escasos en el mundo digital.

Imagen de portada vía Unsplash de Beatriz Pérez Moya

Gracias: Guo Yu

Escrito por: Li Hua, Investigador Especial de Ambi Lab

Tags：

Intercambio de Ethereum