Programa de prueba de conocimiento cero. Protocolo de prueba de conocimiento cero para información confidencial. Definición formal de protocolos de prueba interactivos.

Ya hemos visto qué es un Zk-SNARK o protocolo de prueba de concepto. conocimiento cero en palabras simples, pero en este artículo nos gustaría profundizar en parte técnica de este fenómeno.

Protocolo de prueba de conocimiento cero: ¿cómo funciona?

Entonces, como recordatorio, la prueba de acuerdo nulo le permite demostrar que es propietario de cierta información sin revelar su contenido. Para implementar este concepto, será necesario introducir 3 algoritmos a la vez, que denominaremos GK, P y V. Consideremos su propósito:

• GK es un generador de claves que acepta entradas α y el programa C, generando dos claves: una clave de verificación para la PK del fermentador y una clave de verificación para la VK de verificación. Estas claves son públicas para todas las partes involucradas en la prueba.
• P es un usuario que necesita utilizar 3 tipos de datos de entrada como prueba: 1) clave de verificación PK; 2) entrada aleatoria X, que estará a disposición pública de las partes; 3) una afirmación que debe probarse sin revelar su significado: W. El propio algoritmo P genera una prueba que satisfará las siguientes condiciones: Prueba = P (PK; X; W).
• V es un algoritmo verificador que devuelve una variable booleana. Se puede representar en dos valores: TRUE (verdadero) o FALS (falso). Entonces, el verificador toma los siguientes datos de entrada V(VK; X; Prueba), en función de los cuales determina si es verdadero o falso.

Así es como funciona un protocolo de prueba de conocimiento cero. Lo único de lo que me gustaría hablar por separado es el significado. α, mencionado en el párrafo sobre GK. El hecho es que este parámetro complica significativamente el uso de Zk-SNARK en aplicaciones reales, porque cualquiera que lo posea puede crear una Prueba falsa, a la que el sistema devolverá Verdadero. Los desarrolladores de ZCash, una criptomoneda que utiliza tecnología de prueba cero, han estado luchando con este problema durante mucho tiempo.

Hermosa terminología es una de las ventajas. criptografía moderna. Los nombres de bandas punk o los apodos de Tumbl son como suenan términos criptográficos como "predicado incondicional", "función de trampilla" o "criptoanálisis diferencial imposible"). Me parece que un término como " conocimiento cero".

Pero la belleza del término "conocimiento cero" lleva a su abuso. La gente inmediatamente piensa que conocimiento cero se está convirtiendo en sinónimo de “muy, muy seguro”. Por esta razón, estas palabras se agregan a los nombres de los sistemas de seguridad y redes anónimas– que en realidad no tiene nada que ver con el protocolo de conocimiento cero.

Dijimos todo esto para enfatizar lo principal: prueba de conocimiento cero es uno de los más herramientas poderosas criptografía jamás desarrollada. Pero, lamentablemente, se ha estudiado relativamente poco. Intentemos dar una explicación no matemática de lo que hace que ZK (conocimiento cero) sea tan especial. Aquí hablaremos de algunos protocolos ZK actuales.

Origen del conocimiento cero

Antes de Goldwasser y otros, la mayor parte del trabajo en esta área se centraba en sistemas de prueba de corrección. Es decir, en los casos en los que un atacante, el Probador, intenta engañar al Controlador dándole un valor falso. Pero Goldwasser, Micali y Rakoff miraron el lado opuesto de este problema. En lugar de preocuparse sólo por el Probador, preguntaron: ¿qué pasa si no confías en el Controlador?

Estaban especialmente preocupados por la posibilidad de fuga de información. Específicamente, preguntaron cuánto información adicional¿Recibirá el Responsable al probar que la afirmación es cierta?

Es importante señalar que esto no es sólo un interés teórico. Hay aplicaciones reales y prácticas en las que estas cosas son importantes.

He aquí uno de ellos: imagina que el cliente está en mundo real quiere iniciar sesión en el servidor web usando una contraseña. El enfoque estándar del "mundo real" para resolver el problema implica almacenar una versión hash de la contraseña en el servidor. Iniciar sesión en un sistema de este tipo se considera una especie de "confirmación" de que el hash de la contraseña proporcionada es el resultado de la función hash. Contraseña actual. Y, lo que es más importante, como "confirmación" de que el cliente realmente conoce la contraseña.

La mayoría de los sistemas en el mundo real implementan este "reconocimiento". de la peor manera posible de lo posible. El cliente simplemente pasa la contraseña original al servidor, que recalcula el hash de la contraseña y lo compara con el valor almacenado. El problema aquí es obvio: el servidor recibe mi contraseña en el formato más atractivo para los piratas informáticos: “texto sin formato”. Y el usuario sólo puede rezar para que la seguridad del servidor no se vea comprometida.

Lo que propusieron Goldwasser, Micali y Rakoff fue la esperanza de nuevos métodos de confirmación. Si se implementan por completo, las pruebas de conocimiento cero podrán proporcionar pruebas del problema descrito anteriormente. Sin divulgar un solo dato que corresponda a que “esta afirmación es cierta”.

Ejemplo del "mundo real"

Hasta ahora hemos hablado de cosas bastante abstractas. Sigamos adelante y traigamos ejemplo real(un poco loco) por el protocolo de conocimiento cero.

Para ayudarme a explicar este ejemplo, supongamos que soy un magnate de las telecomunicaciones y estoy en el proceso de lanzar un nuevo red celular. Mi estructura de red se presenta a continuación en este gráfico. Cada vértice del gráfico representa transmisor móvil y las líneas de conexión (bordes) muestran dónde se superponen dos celdas. En estos lugares, los transmisores interferirán entre sí. Es bueno que mi estructura de red permita configurar cada torre en uno de tres rangos de frecuencia para evitar tal influencia.

Así, la tarea de desplegar mi red se reduce a asignar su propio carril a cada torre de tal forma que las células no se crucen. Si utilizamos colores para representar bandas de frecuencia, podemos desarrollar rápidamente una solución a este problema:

Por supuesto, muchos de vosotros ya lo habéis notado. Lo que he descrito aquí es sólo caso especial famoso problema teórico. Se llama "problema de coloración de gráficos de tres colores". Quizás también conozcas uno muy característica interesante este problema. Para algunos gráficos, es muy difícil encontrar una solución o incluso determinar que dicha solución existe. El problema de colorear un gráfico con tres colores (y buscar una respuesta a la pregunta de si existe tal solución para este caso), como se sabe, pertenecen a la categoría de problemas NP-completos.

No hace falta decir que los acertijos con juguetes anteriores son fáciles de resolver. Pero ¿y si no fuera tan fácil? Por ejemplo, imagina que mi red comunicaciones celulares era muy grande y complejo. En este caso, no tendría suficiente potencia informática para encontrar una solución. En este caso sería recomendable delegar el problema en otra persona. Para aquellos que tienen suficiente potencia informática. Por ejemplo, podría pedirle a Google que solucione este problema.

Pero hay un problema.

Supongamos que Google me dará toda la potencia informática que necesito para encontrar una solución para colorear correctamente mi gráfico. Ciertamente no les pagaré hasta que esté seguro de que tienen esta solución. Al mismo tiempo, Google no me proporcionará una copia de la decisión hasta que la pague. Estamos en un callejón sin salida.

EN vida real El sentido común nos dice que la respuesta a este dilema tiene que ver con abogados y cuentas de depósito en garantía. Pero aquí no estamos hablando de la vida real, sino de criptografía. Y, si alguna vez has leído el trabajo de los criptógrafos, ya sabrás que la única forma de encontrar una solución a un problema es idear algo completamente loco. solución técnica. Solución técnica loca (con sombreros)

Imaginemos que los empleados de Google consultaran a Silvio Micali del MIT y este preguntara a sus colegas Oded Goldreich y Avi Wigderson. Después de consultar, desarrollaron un protocolo que es tan hermoso que ni siquiera requiere computadoras. Se utilizará un gran almacén con existencias de lápices de colores y papel. También necesitarás una gran cantidad de sombreros.

Vamos a ver cómo funciona

Primero, iré a un almacén y cubriré el piso con papel para crear un espacio que represente mi red celular. Entonces saldré del almacén. Ahora Google puede entrar, mezclar la colección de lápices y elegir tres colores (como rojo/azul/púrpura, como en este ejemplo) y el color para representar la solución. Tenga en cuenta que no importa el color específico que se utilice.

Antes de salir del almacén, Google cubre cada top con un sombrero. Cuando regrese esto es todo lo que veré:

Obviamente, este enfoque protegerá perfectamente secreto de google. Pero esto no me ayudará en absoluto. Es posible que Google esté completando los colores al azar y, por lo tanto, en el orden incorrecto. O tal vez no completaron nada en absoluto.

Para convencerme de que el problema realmente se resolvió, Google me da la oportunidad de "comprobar" el resultado del color del gráfico. Tengo derecho a elegir, en orden aleatorio, una cara de este gráfico (es decir, a lo largo de una línea entre dos sombreros adyacentes). Google quitará estos dos sombreros, mostrándome una pequeña parte de la solución:

Tenga en cuenta que mi experimento tiene dos resultados posibles:

Si dos vértices mostrados tienen el mismo color (¡o ningún color!), entonces estoy seguro de que Google me está mintiendo. En este caso, no le pagaré a Google ni un centavo. Si los dos vértices mostrados tienen varios colores, lo que significa que Google no me engaña en este caso.

Espero que la primera afirmación sea obvia. El segundo requerirá más explicación detallada. El problema es que incluso si el experimento tuvo éxito, Google aún puede engañarme. Aun así, sólo miré debajo de dos sombreros. Si hay E bordes distintos en el gráfico, lo más probable es que Google pueda proporcionar mala decisión. Por ejemplo, después de una prueba me están engañando con la probabilidad (E-1)/E (que para 1000 aristas sería 99,9%).

Por suerte, Google tiene la respuesta a esta pregunta. ¡Simplemente ejecutaremos el protocolo nuevamente!

Cogemos papel en blanco para crear una nueva copia del gráfico. Google ahora está adoptando una nueva combinación aleatoria de tres lápices de colores. Luego completan el gráfico con la solución correcta, pero usando un nuevo conjunto aleatorio de tres colores.

Nuevamente realizamos la operación con sombreros. Vuelvo atrás y selecciono aleatoriamente nuevos vértices. Miremos nuevamente la lógica descrita anteriormente. Esta vez, si todo va bien, estaré mucho más seguro de que Google me está diciendo la verdad. Esto se debe a que, para engañarme, Google tendría que tener suerte dos veces.

Un evento así puede ocurrir, pero su probabilidad será aún menor. La probabilidad de que Google me engañe dos veces seguidas es (E-1)/E*(E-1)/E (o alrededor del 99,8% de probabilidad para nuestro ejemplo de 1000 aristas).

Afortunadamente, no tenemos que detenernos en dos intentos. Lo intentaremos una y otra vez hasta que estemos convencidos de que Google, con un alto grado de probabilidad, está diciendo la verdad.

Le insto a que no confíe en mi palabra. Pruebe este Javascript y compruébelo usted mismo.

Tenga en cuenta que nunca estoy completamente seguro de que Google esté siendo honesto; siempre existe una pequeña posibilidad de que me estén engañando. Pero después grandes cantidades iteraciones (E^2, como en nuestro caso), eventualmente llegaré al punto en el que Google me está engañando con una probabilidad insignificante, suficiente para una aplicación práctica. Después de eso, puedo fácilmente darle el dinero a Google.

Es importante que Google también esté protegido en este caso. Si intento aprender algo guardando y analizando notas entre ejecuciones del protocolo, fallaré porque Google usa colores aleatorios en cada iteración. Información limitada, que puedo conseguir no me aporta nada. No hay forma de unir estos datos.

¿Qué hace que este ejemplo sea "conocimiento cero"?

Estoy tratando de convencerte de que este protocolo no permite que se filtre información. solución de google. ¡Pero no tienes que confiar en mi palabra! La primera regla de los criptógrafos es nunca creer en tales cosas sin pruebas.

Goldwasser, Micali y Rakoff propusieron tres criterios que todo protocolo de conocimiento cero debe cumplir. Informalmente se pueden describir de la siguiente manera:

Lo completo. Si Google me dice la verdad, entonces debería tener pruebas contundentes de ello (evidencia de alta probabilidad). Fiabilidad. Google sólo podrá convencerme si realmente dice la verdad. “Divulgación cero” (este criterio realmente se llama así). No tengo que averiguar nada más que la solución de Google que obtuve.

Ya hemos discutido los argumentos a favor de la exhaustividad. El protocolo eventualmente me convencerá (con una posibilidad insignificante de error) si lo ejecuto suficientes veces. La fiabilidad también es bastante fácil de demostrar. Si Google intenta engañarme lo detectaré en la gran mayoría de los casos.

La propiedad más difícil sigue siendo el “conocimiento cero”. Para entenderlo, hagamos un experimento mental bastante extraño.

Experimento mental con máquinas del tiempo.

Primero, comencemos con una suposición descabellada. Imaginemos que los ingenieros de Google no son tan inteligentes como la gente cree. Trabajan en este problema semana tras semana y no encuentran una solución. Doce horas antes de la fecha límite, Google se desespera. Deciden engañarme y dicen que tienen un libro para colorear para el Conde (aunque en realidad no tienen ninguno).

Su idea es pasarse por el taller de GoogleX y tomar prestado el prototipo de la máquina del tiempo de Google. El plan original era retroceder unos años y utilizar el dinero extra. tiempo de trabajo para encontrar nuevas soluciones al problema. Desafortunadamente, como ocurre con muchos otros prototipos de Google, la máquina del tiempo tenía una serie de limitaciones. Lo más importante es que sólo puede viajar en el tiempo cuatro minutos y medio.

Por tanto, no es necesario utilizar una máquina del tiempo para aumentar el tiempo que lleva completar un trabajo. Pero aún así, resulta que esta tecnología tan limitada puede usarse para engañarme.

Realmente no sé qué está pasando aquí. Pero parece que sería útil.

El plan resultó ser endiabladamente sencillo. Si Google no sabe cómo se debe colorear el gráfico, simplemente colorea el papel al azar y luego cubre los vértices con sombreros. Si por suerte los picos resultan ser Colores diferentes, todos daremos un suspiro de alivio y seguiremos trabajando, creyendo que todo está bien.

Supongamos que me quito un par de sombreros y descubro dos vértices del mismo color. Si el protocolo se implementa de la forma habitual, Google fracasará en este caso. Pero usamos una máquina del tiempo. Siempre que Google se encuentra en una posición incómoda, simplemente corrige la situación. Es decir, un empleado de Google especialmente designado acciona el interruptor, el tiempo retrocede cuatro minutos y medio y equipo de google colorea el gráfico con una solución aleatoria completamente nueva. Después de eso, adelantan el tiempo y vuelven a intentarlo.

Básicamente, la máquina del tiempo permite a Google "arreglar" cualquier inicio de sesión fallido en el protocolo de tal manera que no sospecharía nada. Dado que los malos resultados sólo ocurrirán 1/3 de las veces, el tiempo de ejecución esperado del protocolo (desde la perspectiva de Google) es sólo marginalmente más largo que si el protocolo se ejecutara de manera justa. Desde mi punto de vista, ni siquiera sé que este viaje en el tiempo esté ocurriendo.

Este último punto es el más importante. Desde mi punto de vista, interactúo con el protocolo de la misma manera, haya o no una máquina del tiempo. Y, sin embargo, vale la pena señalarlo nuevamente: en la versión de la máquina del tiempo, Google no tiene absolutamente ninguna información sobre cómo colorear el gráfico.

¿Y qué se sigue de esto?

Lo que acabamos de mostrar es un ejemplo teórico. En un mundo donde el tiempo sólo avanza y nadie puede engañarme con una máquina del tiempo, el protocolo del sombrero funciona correctamente. Después de E^2 rondas de ejecutarlo, debería estar seguro (no completamente, pero con una probabilidad insignificante de hacer trampa) de que el gráfico está coloreado correctamente y que Google ha proporcionado la información correcta.

Si se puede manipular el tiempo (en particular, si Google puede "rebobinar el tiempo"), entonces puede falsificar el protocolo, incluso si no tiene ninguna información sobre cómo se debe colorear el gráfico.

Desde mi punto de vista, ¿cuál es la diferencia entre estos dos protocolos? Tienen la misma distribución estadística y transmiten la misma cantidad de información útil.

Lo creas o no, esto demuestra algo muy importante.

En particular, se supone que yo (el Verificador) tengo algún tipo de estrategia que me permitirá "extraer" información útil sobre cómo Google realiza la coloración en caso de lanzar un protocolo honesto. Entonces mi estrategia debería funcionar igual de bien si me dejo engañar por la máquina del tiempo. Las ejecuciones del protocolo son, desde mi punto de vista, estadísticamente idénticas. Físicamente no puedo mostrar la diferencia.

Por tanto, la cantidad de información que recibiré en el “experimento real” y en el “experimento de la máquina del tiempo” es completamente idéntica. La cantidad de información que Google pone en el experimento de la máquina del tiempo es exactamente cero. Por lo tanto, incluso en el mundo real, no habrá fuga de información. Sólo queda demostrar que los informáticos tienen una máquina del tiempo (shhh, es un secreto).

Cómo deshacerse de los sombreros y las máquinas del tiempo

Por supuesto, en realidad no querríamos ejecutar el protocolo usando sombreros. E incluso Google (muy probablemente) no tiene una máquina del tiempo real.

Para unir todas estas cosas, necesitamos llevar este protocolo al mundo digital. Para hacer esto, necesitamos un equivalente digital de un “sombrero”: algo que oculte el significado digital y al mismo tiempo “vincule” el significado y su creador (creando un “compromiso”), de modo que no pueda cambiar de opinión. .

Por suerte, tenemos una gran herramienta para esta aplicación. Se llama esquema de compromiso digital. Un esquema de compromiso permite a una de las partes crear un "compromiso" para un mensaje, mantenerlo en secreto y luego abrir el "compromiso" para ver qué hay dentro. Se pueden construir a partir de varios componentes, incluso de los fuertes funciones criptográficas hash.

Habiendo recibido el diagrama de compromiso, reunimos todos los componentes para lanzar en en formato electrónico Protocolo de conocimiento cero. El evaluador primero codifica la coloración de los vértices como un conjunto. mensajes digitales(por ejemplo, los números 0, 1, 2), luego genera obligaciones digitales para cada uno. Estas obligaciones se transmiten al Responsable. Cuando el Controlador abre un borde, el Probador revela los valores de las obligaciones que corresponden a los dos vértices.

Así logramos deshacernos de los sombreros. Pero, ¿cómo demostramos que este protocolo es de conocimiento cero?

Pero ahora estamos en mundo digital. Por tanto, no necesitamos una máquina del tiempo para confirmar que el protocolo funciona. El truco clave es que el protocolo no funcionará entre dos personas, sino entre dos programas informáticos diferentes (o, más formalmente, dos máquinas probabilísticas de Turing).

Ahora podemos probar el siguiente teorema: si el Controlador va a extraer información útil de una ejecución normal del protocolo, obtendrá la misma cantidad de información útil que de una ejecución "trampa" del protocolo, donde el Probador no introdujo cualquier información para empezar.

Estamos hablando de programas informáticos y pueden "retroceder en el tiempo". Por ejemplo, considere usar una máquina virtual que pueda tomar instantáneas. Un ejemplo de "rebobinar el tiempo" utilizando máquinas virtuales. Inicialmente, la máquina virtual sigue un camino, regresa a estado original, luego la ejecución se bifurca a una nueva ruta.

Incluso si no consideras maquinas virtuales, cualquier programa de computadora se puede "rebobinar" para estado previo, simplemente ejecutando el programa desde el principio y enviando los mismos datos como entrada. Siempre que las entradas (incluidas las entradas números al azar), son fijos, el programa siempre seguirá la misma ruta de ejecución. Así podremos rebobinar el programa, iniciándolo desde el principio y “bifurcando” su ejecución cuando el programa alcance un determinado punto deseado.

En última instancia, lo que obtenemos se puede representar como un teorema. Si para el Controlador hay programa de computadora, que extrae con éxito información útil del Probador (interactuando con el protocolo), luego el Probador puede usar el truco de rebobinar el programa, alimentando al Controlador con soluciones aleatorias. Utiliza la misma lógica que ya aplicamos anteriormente: si el Controlador puede extraer información exitosamente ejecutando un protocolo real, entonces obtendrá la misma cantidad de información ejecutando un protocolo falso basado en rebobinar el programa. Pero como el protocolo falso no transmite ningún dato útil, no hay información que pueda extraerse. Así, la información que el Responsable puede extraer es siempre nula.

¿Qué se sigue de todo esto?

En resumen, podemos decir que el protocolo es completo y fiable. Podemos hablar de fiabilidad en cualquier situación en la que ambas partes no intenten engañarse mutuamente.

Al mismo tiempo, el protocolo tiene conocimiento cero. Para demostrar esto, mostramos que un programa que ejecuta el Controlador para extraer información podrá extraer datos de un programa que no tiene datos significativos. Esto lleva a una contradicción evidente, que nos dice que el protocolo en cualquier situación no filtra información.

esto nos da ventajas importantes. Dado que cualquiera puede crear una transcripción falsa (como el ejemplo de Google en el que intentaron convencerme de que tenían una solución), no puedo reproducir la transcripción para probar mi caso ante nadie más (como un juez). El juez dirá que no está seguro de que la grabación se haya realizado con honestidad y no haya sido editada (como en el ejemplo de Google y el uso de la máquina del tiempo). Esto significa que la transcripción en sí no contiene ninguna información. El protocolo sólo tiene sentido si yo mismo participé y puedo estar seguro de que todo sucedió en tiempo real.

¡Evidencia para todas las NP!

Para los que han llegado hasta aquí, les tengo una noticia importante. La tarea de colorear una red celular en tres colores es interesante en sí misma, pero eso no es todo. Verdadero cosa interesante El problema de la coloración de tres colores es que pertenece a la clase de NP-completo. Esto significa que cualquier otro problema que pertenezca a la clase NP se puede reducir a este.

En pocas palabras, Goldrich, Micali y Widgerson demostraron que existen ZK "eficientes" para una amplia clase de problemas útiles. Muchos de ellos son mucho más interesantes que el problema de asignar frecuencias en una red celular.

Simplemente encuentra la afirmación (en NP) que deseas probar y la traduce a un problema de coloración de gráficos de tres colores. Desde este punto podrás ejecutar una versión digital de nuestro protocolo con sombreros.

En lugar de resultados

Por supuesto, sería increíblemente estúpido comenzar a utilizar este protocolo en la práctica de inmediato. Su coste computacional incluirá tamaño global la declaración inicial y la evidencia, más el costo de traducir el problema en un gráfico, y otras E^2 ejecuciones del protocolo, que son necesarias para verificar la exactitud de la solución. En teoría esto es "efectivo", pero como coste total la prueba será un polinomio de la longitud de la entrada; en la práctica esto no es aplicable.

Por lo tanto, hasta ahora sólo hemos demostrado que tales pruebas son posibles. Queda por encontrar evidencia que sea lo suficientemente práctica para un uso real.

Notas

* Formalmente, el propósito de una prueba interactiva es convencer al Controlador de que una determinada cadena pertenece a un idioma en particular. Normalmente, el Probador en las tareas tiene potencia ilimitada y el Controlador tiene una capacidad limitada para realizar cálculos.

**Este ejemplo se basa en solución original Goldwasser, Micali y Rakoff, y un tutorial sobre sombreros desarrollado por Silvio Micali.

****** Se puede construir un ejemplo simple de compromiso utilizando una función hash de ejemplo. Para crear un compromiso con el valor "x", simplemente generamos una cadena (suficientemente larga) de números aleatorios, que llamamos "sal", y el compromiso de salida es C = hash(sal || x). Para abrir un compromiso, simplemente abre "x" y "sal". Cualquiera puede verificar que el compromiso original es válido recalculando el hash nuevamente. Este método seguro bajo algunos supuestos moderadamente fuertes sobre la función misma.

Pruebas de conocimiento cero poscuánticas– protocolos cero pruebas de conocimiento, que son cuánticamente estables.

Se considera que los sistemas/protocolos resistentes a lo cuántico son aquellos sistemas/protocolos que no pueden verse comprometidos mediante el uso de potencia informática. computadora cuántica. El término estabilidad cuántica se introduce en la criptografía poscuántica.

Declaración del problema de seguridad de la información.

Las computadoras cuánticas tienen grandes poder computacional. En este momento Esta dirección se está desarrollando rápidamente. Con todo ello, el aumento de la investigación en este ámbito (que sin duda es característica positiva) reduce la confiabilidad de los criptosistemas modernos en uso, por ejemplo aquellos basados ​​en la factorización de números enteros o problemas de logaritmos discretos.

ZKBoo

ZKBoo se basa en protocolo informático confidencial (MPC). La idea de ZKBoo es sustituir el MPC por una descomposición (2,3) de la cadena.

La prueba se construye según el siguiente esquema:

1) P calcula f mediante descomposición y captura 3 estados;

2) P envía las obligaciones y resultados de cada estado después de usar la heurística FS;

3) La respuesta es que 2 de 3 estados se abren para cada N lanzamiento;

4) V verifica que los datos de salida estén completos de la recuperación; comprueba que cada uno de los 2 estados abiertos se calcule correctamente y calcula si la llamada se calcula correctamente.

El número de lanzamientos se elige de modo que el error sea insignificante, de modo que la posibilidad de que un atacante acceda a todos los lanzamientos sea mínima.

ZKB++

ZKB++ es versión modificada ZKBoo.

1) Descomposición: en Vista1 y Vista2, P debe incluir k(i) ya que x(i) puede calcularse de manera determinista mediante V;

2) Sin incluir datos de entrada: las participaciones de entrada generadas pseudoaleatoriamente usando k(i) no necesitan incluirse en la representación cuando e = 1. Los datos solo deben enviarse si e = 2 o e = 3, ya que para el tercer estado, los datos de entrada no se pueden obtener del inicial, ya que se genera pseudoaleatoriamente usando k(i);

3) Sin obligaciones de envío;

4) Sin extras secuencia aleatoria por obligaciones;

5) Sin considerar el resultado: el resultado puede calcularse a partir del resto de la evidencia;

6) Sin incluir la representación del estado: V puede recalcular el estado considerando solo k(e) y k(e+1) aleatorios.

El circuito ZKB++ completo se muestra en la Figura 1.

Las mejoras realizadas para optimizar ZKBoo reducen el tamaño de las pruebas en un factor de 2 para ZKB++.