Hace algún tiempo estaba traduciendo un libro sobre tecnología a prueba de conocimiento cero. El contenido básico fue traducido a finales del mes pasado. La traducción tomó mucho más tiempo de lo que esperaba. Actualmente estamos discutiendo algunos errores administrativos en el libro con el autor y preparando el borrador final.
De todos modos, finalmente tengo algo de tiempo para mirar algo nuevo. Comencemos con el algoritmo Nova ~
Información relacionada con el algoritmo Nova
Tres datos pueden ayudar a comprender el algoritmo de Nova:
Papel nuevo:
Ataques potenciales de Nova y correcciones correspondientes:
Resumen de comprensión de los posibles ataques de Nova:
Este artículo es una comprensión y un resumen de la información anterior. **Algunas de las imágenes de este artículo provienen de la información anterior y no se etiquetarán una por una en este artículo. **
Empiece con IVC
El algoritmo Nova es un nuevo algoritmo de prueba de conocimiento cero para IVC (Computación Incrementalmente Verificable). IVC, es decir, la misma función calcula iterativamente la salida anterior como la siguiente entrada. El proceso de cálculo iterativo de la función F es el siguiente:
z0 es la entrada inicial y el resultado generado por el cálculo de la función F se utiliza como entrada de la siguiente función F.
Relax R1CS y Slack Commitment R1CS
Como todos sabemos, R1CS es una representación de las restricciones del circuito en tecnología a prueba de conocimiento cero. El R1CS relajado puede verse como una forma extendida de R1CS. Sobre la base de R1CS, se suman un escalar u y un vector de error E. Una instancia de R1CS relajado está representada por (E, u, x).
El compromiso relajado R1CS compromete los vectores E y W basándose en el R1CS relajado. Una instancia de un compromiso de holgura R1CS está representada por (\bar{E}, u, \bar{W}, x), donde x y u son variables públicas.
Ampliación de R1CS a R1CS relajado para esquema de plegado. Tenga en cuenta que desde la perspectiva del R1CS relajado, R1CS es un caso especial. En otras palabras, R1CS también es un R1CS flojo "especial".
Esquema de plegado
Intuitivamente hablando, un esquema de plegado para una relación R consiste en "colapsar" dos instancias que se ajustan a la relación R en una nueva instancia de la relación compuesta R. Slack R1CS/Relax Commitment R1CS puede realizar pliegues similares. El proceso de plegado es similar para ambos. El esquema de plegado de Slack Commitment R1CS es el siguiente:
Todo el esquema de plegado consta de 4 pasos. En el primer paso, el probador P envía un compromiso \bar{T} del elemento cruzado T al verificador. En el segundo paso, el verificador envía un desafío aleatorio r al probador. El tercer paso es el cumplimiento del compromiso que tanto el probador como el verificador deben realizar. En el cuarto paso, el probador actúa solo y suma los vectores E y W de las dos instancias.
Función aumentada F' (Función Argumentada)
Esquema de colapso, la instancia R1CS colapsada se relaja. Entonces, ¿cuáles son los cálculos que demuestran estos ejemplos relajados de R1CS? Obviamente, estos cálculos incluyen cálculos de plegado. Estos cálculos no son sólo la función F en los cálculos de IVC, también se denominan funciones aumentadas F'. El cálculo de la función aumentada F' consta principalmente de dos partes:
Función 1/ F en IVC
2/ Cálculo de plegado de la instancia R1CS
Aspecto ideal
Con la comprensión anterior, puedes imaginar el proceso de plegado:
Entre ellos, circuito es el circuito correspondiente a la función aumentada F'. acc{1,2,3,4,5,6} es una instancia R1CS de compromiso flexible. El circuito tiene dos cálculos: 1/Relajar el plegado de la instancia de compromiso R1CS, como acc1+acc2->acc3. 2/Calcular la función F, cambiando el estado de estado1 a estado2, y luego de estado2 a estado3, etc.
Tenga en cuenta que el circuito correspondiente a la función aumentada F' es en sí mismo una instancia de R1CS, que puede expresarse como una instancia de R1CS relajada. Esos son acc4 y acc6 en la imagen. "Resumir" consiste en convertir una instancia R1CS inactiva en una instancia R1CS comprometida inactiva.
Si observamos detenidamente la entrada del segundo circuito, acc3 es la instancia R1CS de compromiso relajado después del plegado, y acc4 es la instancia R1CS de compromiso relajado que demuestra que acc3 es el resultado de plegado correcto. Estas dos instancias ingresarán al siguiente plegado y generarán acc5. Puede imaginar que si acc3 y acc4 son instancias R1CS de compromiso de holgura satisfactorias, significa que acc3 se deriva de dos instancias R1CS de compromiso de holgura satisfacibles. En otras palabras, acc1 y acc2 son instancias de R1CS de compromiso de holgura satisfacibles. Este tipo de confiabilidad se puede deducir "hacia adelante" paso a paso, demostrando así que el cálculo de la función F en cada circuito es correcto. En general, a través de la satisfacibilidad de dos instancias R1CS de compromiso de holgura correspondientes a un determinado circuito, se puede demostrar que todos los cálculos IVC anteriores son correctos.
Aspecto real
Los amigos que están familiarizados con las pruebas de conocimiento cero saben que las curvas elípticas se utilizan a menudo en esquemas de compromiso polinómico. El compromiso polinomial correspondiente en el dominio escalar está representado por el dominio base de la curva elíptica. Los circuitos R1CS suelen estar representados por el dominio escalar. Mire con atención, el "resumen" en la imagen de arriba implica la conversión de dominio. Es decir, si desea plegar la instancia R1CS de compromiso de holgura correspondiente a un circuito, debe "doblarla" en otro circuito. En este momento, es necesario introducir un ciclo de curva elíptica. Entre dos o más curvas elípticas, el dominio escalar de una curva es el mismo que el dominio base de la otra curva. Casualmente, el dominio escalar de esta curva es el mismo que el dominio base de la curva anterior. Usando un bucle de curva elíptica de este tipo, se puede lograr el "aspecto ideal":
Todo el proceso de plegado se divide en dos circuitos de plegado. La parte superior se puede llamar pliegue del Circuito 1 y la parte inferior se puede llamar pliegue del Circuito 2. Una representación formal de la relación entre los dos circuitos se encuentra en la página 8 del artículo "Ataques potenciales a Nova y correcciones correspondientes". U representa la instancia plegada y u representa la instancia relajada correspondiente a una instancia R1CS. Tenga en cuenta que el Circuito 1 colapsa la instancia R1CS de compromiso de holgura correspondiente al Circuito 2, mientras que el Circuito 2 colapsa la instancia R1CS de compromiso de holgura correspondiente al Circuito 1. El objetivo principal del Circuito 2 es colapsar la instancia R1CS de compromiso de holgura correspondiente al Circuito 1, y el cálculo de la función en su circuito no tiene sentido. En cambio, la función F se implementa en el Circuito 1. Combinado con la "apariencia ideal", podemos adivinar aproximadamente la satisfacibilidad de U{i+2}^2, u{i+2}^1, u{i+2}^2, U{i+2}^1 es una parte importante de la prueba.
Porque el "circuito" se corta en dos partes y el circuito respectivo se dobla en el otro circuito. Hay varios problemas de vinculación entre instancias: la vinculación entre u y U instancias y la vinculación de u instancias que pasan entre dos circuitos. Para resolver estos problemas de vinculación, se introducen variables públicas x_0/x_1 en el circuito, donde x_1 especifica la instancia U de salida del circuito vinculada a la instancia u y la salida de la función F actual (para simplificar la estructura del circuito, no reflejada en la figura). Piensa que si el resultado H_1 de la instancia U se introduce en el circuito, si la instancia u es satisfactoria, x_0/x_1 es real y confiable, es decir, está "ligado" a U. x_0 establece la relación vinculante entre la entrada u y U, y x_1 establece la relación vinculante entre la salida u y U.
Por ejemplo, cuando u{i+1}^1 se usa como entrada de la segunda mitad del circuito, pasa por el Circuito 2 y su salida u{i+1}^2.x0 = u{i+1 }^1.x1, entonces, cuando se ingresa a la parte superior del circuito, si se puede satisfacer u{i+1}^2, entonces su x_0 debe ser igual al resultado de H1 de U_{i +1}^2. Esto se comprueba en el Circuito 1. De esta manera, se garantiza que se pase la instancia correcta entre los dos circuitos.
Prueba de IVC
Para demostrar que el IVC se calcula correctamente en una determinada iteración, es necesario demostrar lógicamente la siguiente información:
Además de demostrar que se pueden satisfacer cuatro instancias, también es necesario probar la relación vinculante entre dos x1, como se muestra en la siguiente figura:
Si esta información es correcta requiere la implementación de un circuito de prueba adicional. Es decir, la prueba del cálculo del IVC es una prueba del circuito. Es concebible que si se trata de un cálculo con muchas iteraciones, originalmente estas iteraciones debían realizarse en el circuito una por una, ahora solo es necesario verificar la satisfacibilidad y las relaciones vinculantes de 4 instancias del circuito. La mejora del rendimiento es enorme.
Corrección de ataques y algoritmos
Al ver la imagen de arriba, tengo una intuición: siento que las instancias de los circuitos superior e inferior están "separadas" y no tienen vinculación. De hecho, así es como se estructura el ataque.
U_i^1 y U{i+1}^2 forjados, aunque son falsificados, son ejemplos satisfactorios. Forje u{i+1}^1, modifique x_0 y x_1 para que correspondan a la instancia U falsificada. Obviamente, la instancia u{i+1}^1 no está satisfecha. Aunque no está satisfecho, el circuito del Circuito 2 aún puede satisfacerse, pero la instancia de salida U {i + 1} ^ 1 no está satisfecha. Si u{i+1}^2 se construye con éxito, el Circuito 1 puede construir u{i+2}^1 y U_{i+2}^2 satisfactorios, y satisfacer la relación vinculante de x1. De esta manera, primero se construye la mitad de la prueba final de falsificación. Mediante simetría, se puede construir la instancia de salida de la mitad inferior. Al "empalmar" los resultados de las dos construcciones, se puede falsificar la prueba del cálculo del IVC.
La lógica de verificación revisada es la siguiente:
El capítulo 6 del documento "Posibles ataques a Nova y las correcciones correspondientes" proporciona un análisis de seguridad detallado. Los amigos interesados pueden consultar el documento original ellos mismos.
La idea básica de Nova es plegar instancias de circuito mediante un esquema de plegado. La lógica es bastante complicada y requiere una reflexión cuidadosa sobre el proceso de plegado del circuito y las relaciones vinculantes en el circuito.
Una palabra para describirlo: Absoluto~
Ver originales
Esta página puede contener contenido de terceros, que se proporciona únicamente con fines informativos (sin garantías ni declaraciones) y no debe considerarse como un respaldo por parte de Gate a las opiniones expresadas ni como asesoramiento financiero o profesional. Consulte el Descargo de responsabilidad para obtener más detalles.
Progreso revolucionario en tecnología de prueba de conocimiento cero: una exploración en profundidad del algoritmo Nova
Hace algún tiempo estaba traduciendo un libro sobre tecnología a prueba de conocimiento cero. El contenido básico fue traducido a finales del mes pasado. La traducción tomó mucho más tiempo de lo que esperaba. Actualmente estamos discutiendo algunos errores administrativos en el libro con el autor y preparando el borrador final.
De todos modos, finalmente tengo algo de tiempo para mirar algo nuevo. Comencemos con el algoritmo Nova ~
Información relacionada con el algoritmo Nova
Tres datos pueden ayudar a comprender el algoritmo de Nova:
Este artículo es una comprensión y un resumen de la información anterior. **Algunas de las imágenes de este artículo provienen de la información anterior y no se etiquetarán una por una en este artículo. **
Empiece con IVC
El algoritmo Nova es un nuevo algoritmo de prueba de conocimiento cero para IVC (Computación Incrementalmente Verificable). IVC, es decir, la misma función calcula iterativamente la salida anterior como la siguiente entrada. El proceso de cálculo iterativo de la función F es el siguiente:
z0 es la entrada inicial y el resultado generado por el cálculo de la función F se utiliza como entrada de la siguiente función F.
Relax R1CS y Slack Commitment R1CS
Como todos sabemos, R1CS es una representación de las restricciones del circuito en tecnología a prueba de conocimiento cero. El R1CS relajado puede verse como una forma extendida de R1CS. Sobre la base de R1CS, se suman un escalar u y un vector de error E. Una instancia de R1CS relajado está representada por (E, u, x).
El compromiso relajado R1CS compromete los vectores E y W basándose en el R1CS relajado. Una instancia de un compromiso de holgura R1CS está representada por (\bar{E}, u, \bar{W}, x), donde x y u son variables públicas.
Ampliación de R1CS a R1CS relajado para esquema de plegado. Tenga en cuenta que desde la perspectiva del R1CS relajado, R1CS es un caso especial. En otras palabras, R1CS también es un R1CS flojo "especial".
Esquema de plegado
Intuitivamente hablando, un esquema de plegado para una relación R consiste en "colapsar" dos instancias que se ajustan a la relación R en una nueva instancia de la relación compuesta R. Slack R1CS/Relax Commitment R1CS puede realizar pliegues similares. El proceso de plegado es similar para ambos. El esquema de plegado de Slack Commitment R1CS es el siguiente:
Todo el esquema de plegado consta de 4 pasos. En el primer paso, el probador P envía un compromiso \bar{T} del elemento cruzado T al verificador. En el segundo paso, el verificador envía un desafío aleatorio r al probador. El tercer paso es el cumplimiento del compromiso que tanto el probador como el verificador deben realizar. En el cuarto paso, el probador actúa solo y suma los vectores E y W de las dos instancias.
Función aumentada F' (Función Argumentada)
Esquema de colapso, la instancia R1CS colapsada se relaja. Entonces, ¿cuáles son los cálculos que demuestran estos ejemplos relajados de R1CS? Obviamente, estos cálculos incluyen cálculos de plegado. Estos cálculos no son sólo la función F en los cálculos de IVC, también se denominan funciones aumentadas F'. El cálculo de la función aumentada F' consta principalmente de dos partes:
Función 1/ F en IVC
2/ Cálculo de plegado de la instancia R1CS
Aspecto ideal
Con la comprensión anterior, puedes imaginar el proceso de plegado:
Entre ellos, circuito es el circuito correspondiente a la función aumentada F'. acc{1,2,3,4,5,6} es una instancia R1CS de compromiso flexible. El circuito tiene dos cálculos: 1/Relajar el plegado de la instancia de compromiso R1CS, como acc1+acc2->acc3. 2/Calcular la función F, cambiando el estado de estado1 a estado2, y luego de estado2 a estado3, etc.
Tenga en cuenta que el circuito correspondiente a la función aumentada F' es en sí mismo una instancia de R1CS, que puede expresarse como una instancia de R1CS relajada. Esos son acc4 y acc6 en la imagen. "Resumir" consiste en convertir una instancia R1CS inactiva en una instancia R1CS comprometida inactiva.
Si observamos detenidamente la entrada del segundo circuito, acc3 es la instancia R1CS de compromiso relajado después del plegado, y acc4 es la instancia R1CS de compromiso relajado que demuestra que acc3 es el resultado de plegado correcto. Estas dos instancias ingresarán al siguiente plegado y generarán acc5. Puede imaginar que si acc3 y acc4 son instancias R1CS de compromiso de holgura satisfactorias, significa que acc3 se deriva de dos instancias R1CS de compromiso de holgura satisfacibles. En otras palabras, acc1 y acc2 son instancias de R1CS de compromiso de holgura satisfacibles. Este tipo de confiabilidad se puede deducir "hacia adelante" paso a paso, demostrando así que el cálculo de la función F en cada circuito es correcto. En general, a través de la satisfacibilidad de dos instancias R1CS de compromiso de holgura correspondientes a un determinado circuito, se puede demostrar que todos los cálculos IVC anteriores son correctos.
Aspecto real
Los amigos que están familiarizados con las pruebas de conocimiento cero saben que las curvas elípticas se utilizan a menudo en esquemas de compromiso polinómico. El compromiso polinomial correspondiente en el dominio escalar está representado por el dominio base de la curva elíptica. Los circuitos R1CS suelen estar representados por el dominio escalar. Mire con atención, el "resumen" en la imagen de arriba implica la conversión de dominio. Es decir, si desea plegar la instancia R1CS de compromiso de holgura correspondiente a un circuito, debe "doblarla" en otro circuito. En este momento, es necesario introducir un ciclo de curva elíptica. Entre dos o más curvas elípticas, el dominio escalar de una curva es el mismo que el dominio base de la otra curva. Casualmente, el dominio escalar de esta curva es el mismo que el dominio base de la curva anterior. Usando un bucle de curva elíptica de este tipo, se puede lograr el "aspecto ideal":
Todo el proceso de plegado se divide en dos circuitos de plegado. La parte superior se puede llamar pliegue del Circuito 1 y la parte inferior se puede llamar pliegue del Circuito 2. Una representación formal de la relación entre los dos circuitos se encuentra en la página 8 del artículo "Ataques potenciales a Nova y correcciones correspondientes". U representa la instancia plegada y u representa la instancia relajada correspondiente a una instancia R1CS. Tenga en cuenta que el Circuito 1 colapsa la instancia R1CS de compromiso de holgura correspondiente al Circuito 2, mientras que el Circuito 2 colapsa la instancia R1CS de compromiso de holgura correspondiente al Circuito 1. El objetivo principal del Circuito 2 es colapsar la instancia R1CS de compromiso de holgura correspondiente al Circuito 1, y el cálculo de la función en su circuito no tiene sentido. En cambio, la función F se implementa en el Circuito 1. Combinado con la "apariencia ideal", podemos adivinar aproximadamente la satisfacibilidad de U{i+2}^2, u{i+2}^1, u{i+2}^2, U{i+2}^1 es una parte importante de la prueba.
Porque el "circuito" se corta en dos partes y el circuito respectivo se dobla en el otro circuito. Hay varios problemas de vinculación entre instancias: la vinculación entre u y U instancias y la vinculación de u instancias que pasan entre dos circuitos. Para resolver estos problemas de vinculación, se introducen variables públicas x_0/x_1 en el circuito, donde x_1 especifica la instancia U de salida del circuito vinculada a la instancia u y la salida de la función F actual (para simplificar la estructura del circuito, no reflejada en la figura). Piensa que si el resultado H_1 de la instancia U se introduce en el circuito, si la instancia u es satisfactoria, x_0/x_1 es real y confiable, es decir, está "ligado" a U. x_0 establece la relación vinculante entre la entrada u y U, y x_1 establece la relación vinculante entre la salida u y U.
Por ejemplo, cuando u{i+1}^1 se usa como entrada de la segunda mitad del circuito, pasa por el Circuito 2 y su salida u{i+1}^2.x0 = u{i+1 }^1.x1, entonces, cuando se ingresa a la parte superior del circuito, si se puede satisfacer u{i+1}^2, entonces su x_0 debe ser igual al resultado de H1 de U_{i +1}^2. Esto se comprueba en el Circuito 1. De esta manera, se garantiza que se pase la instancia correcta entre los dos circuitos.
Prueba de IVC
Para demostrar que el IVC se calcula correctamente en una determinada iteración, es necesario demostrar lógicamente la siguiente información:
Además de demostrar que se pueden satisfacer cuatro instancias, también es necesario probar la relación vinculante entre dos x1, como se muestra en la siguiente figura:
Si esta información es correcta requiere la implementación de un circuito de prueba adicional. Es decir, la prueba del cálculo del IVC es una prueba del circuito. Es concebible que si se trata de un cálculo con muchas iteraciones, originalmente estas iteraciones debían realizarse en el circuito una por una, ahora solo es necesario verificar la satisfacibilidad y las relaciones vinculantes de 4 instancias del circuito. La mejora del rendimiento es enorme.
Corrección de ataques y algoritmos
Al ver la imagen de arriba, tengo una intuición: siento que las instancias de los circuitos superior e inferior están "separadas" y no tienen vinculación. De hecho, así es como se estructura el ataque.
U_i^1 y U{i+1}^2 forjados, aunque son falsificados, son ejemplos satisfactorios. Forje u{i+1}^1, modifique x_0 y x_1 para que correspondan a la instancia U falsificada. Obviamente, la instancia u{i+1}^1 no está satisfecha. Aunque no está satisfecho, el circuito del Circuito 2 aún puede satisfacerse, pero la instancia de salida U {i + 1} ^ 1 no está satisfecha. Si u{i+1}^2 se construye con éxito, el Circuito 1 puede construir u{i+2}^1 y U_{i+2}^2 satisfactorios, y satisfacer la relación vinculante de x1. De esta manera, primero se construye la mitad de la prueba final de falsificación. Mediante simetría, se puede construir la instancia de salida de la mitad inferior. Al "empalmar" los resultados de las dos construcciones, se puede falsificar la prueba del cálculo del IVC.
La lógica de verificación revisada es la siguiente:
El capítulo 6 del documento "Posibles ataques a Nova y las correcciones correspondientes" proporciona un análisis de seguridad detallado. Los amigos interesados pueden consultar el documento original ellos mismos.
La idea básica de Nova es plegar instancias de circuito mediante un esquema de plegado. La lógica es bastante complicada y requiere una reflexión cuidadosa sobre el proceso de plegado del circuito y las relaciones vinculantes en el circuito.
Una palabra para describirlo: Absoluto~