Escrito por: Kang Shuaiyue, CEO de Fox Tech; Meng Xuanji, Científico Principal de Fox Tech.
Introducción
La técnica de prueba de conocimiento cero en criptografía tiene amplias aplicaciones en el mundo web3, incluyendo cálculos de privacidad, zkRollup, etc. El FOAKS utilizado en el proyecto Layer2 FOX es un algoritmo de prueba de conocimiento cero. En esta serie de aplicaciones, hay dos atributos extremadamente importantes para los algoritmos de prueba de conocimiento cero, que son la eficiencia del algoritmo y la interactividad.
La importancia de la eficiencia del algoritmo es evidente, un algoritmo eficiente puede reducir significativamente el tiempo de ejecución del sistema, disminuyendo así la latencia del cliente y mejorando notablemente la experiencia del usuario y la eficiencia, esta es también una de las razones importantes por las que FOAKS se esfuerza por lograr un tiempo de prueba lineal.
Por otro lado, desde la perspectiva de la criptografía, el diseño de sistemas de prueba de conocimiento cero a menudo depende de múltiples interacciones entre el probador y el verificador. Por ejemplo, en muchas de las historias que se utilizan en artículos de divulgación sobre pruebas de conocimiento cero, como la historia de la "cueva de conocimiento cero", la implementación de la prueba depende de la transmisión de información en múltiples rondas entre Alibaba (el probador) y el periodista (el verificador). Sin embargo, de hecho, en muchos escenarios de aplicación, depender de interacciones puede hacer que el sistema ya no sea utilizable, o aumentar drásticamente la latencia. Así como en los sistemas de zkRollup, esperamos que el probador (es decir, el folder en FOX) pueda calcular correctamente el valor de prueba localmente sin depender de la interacción con el verificador.
Desde esta perspectiva, cómo transformar un protocolo de prueba de conocimiento cero interactivo en uno no interactivo es una cuestión muy significativa. En este artículo, presentaremos cómo FOX utiliza la heurística clásica de Fiat-Shamir para generar el desafío en Brakedown y lograr el proceso del protocolo no interactivo.
Desafío en la prueba de conocimiento cero
Los algoritmos de prueba de conocimiento cero se han vuelto extremadamente populares a medida que se han expandido sus aplicaciones, y en los últimos años han surgido varios algoritmos, incluidos FOAKS, Orion, zk-stark, entre otros. Estos algoritmos, así como la lógica de prueba central del protocolo sigma en la criptografía temprana, son en esencia que el probador (Prover) envía un valor al verificador (Verifier), y el verificador genera un desafío (Challenge) a través de un número aleatorio local, enviando este valor de desafío aleatorio al probador, quien debe tener realmente el conocimiento para poder responder correctamente al verificador. Por ejemplo, en la cueva de conocimiento cero, el periodista lanza una moneda y le dice a Alibaba si debe salir por el lado izquierdo o derecho; aquí, "izquierda y derecha" es el desafío para Alibaba, y si realmente conoce el hechizo, podrá salir por la dirección requerida, de lo contrario, tendrá una probabilidad del 50% de fallar.
Aquí notamos que la generación del desafío es un paso clave que tiene dos requisitos: aleatoriedad e impredecibilidad por parte del probador. El primer requisito, la aleatoriedad, garantiza su propiedad probabilística. El segundo requisito, si el probador puede predecir el valor del desafío, significaría que la seguridad del protocolo se vería comprometida, ya que el probador podría responder sin tener conocimiento. Se puede hacer una comparación, si Alibaba puede predecir por qué lado el periodista le pide que salga, aunque no tenga el hechizo, podría entrar en ese lado de antemano, logrando así pasar el protocolo.
Por lo tanto, necesitamos un método que permita al probador generar localmente un número aleatorio impredecible, que también pueda ser verificado por el verificador, logrando así un protocolo no interactivo.
Función hash
El nombre de la función hash puede no ser desconocido para nosotros, ya sea en el protocolo de consenso de Bitcoin POW, que sirve como un problema matemático para la minería, o para comprimir datos, construir códigos de verificación de mensajes, etc., la función hash está presente. Y en los diferentes protocolos mencionados anteriormente, se utilizan varias propiedades diferentes de la función hash.
Más específicamente, las propiedades de una función hash segura incluyen los siguientes puntos:
Compresión: una función hash determinística puede comprimir mensajes de longitud arbitraria a una longitud fija.
Eficiencia: dado un input x, calcular la salida h(x) es fácil.
Resistencia a colisiones: dado un input x1, encontrar otro input x2 tal que h(x1) = h(x2) es difícil.
Cabe señalar que si una función hash satisface la resistencia a colisiones, también debe satisfacer la propiedad de unicidad, es decir, dado un output y, encontrar x tal que h(x) = y es difícil. En criptografía, aún no se ha podido construir una función que teóricamente cumpla con la unicidad absoluta, pero en la práctica, la función hash puede considerarse esencialmente como una función unidireccional.
De este modo, se puede observar que las diferentes aplicaciones mencionadas anteriormente corresponden a diferentes propiedades de la función hash. Al mismo tiempo, decimos que la función hash también tiene un papel muy importante al proporcionar aleatoriedad; aunque actualmente no se puede construir un generador de números aleatorios perfecto según los requisitos teóricos de criptografía, la función hash también puede desempeñar este papel en la práctica, lo que proporciona una base para la técnica de la heurística de Fiat-Shamir que se presenta a continuación.
Heurística de Fiat-Shamir
De hecho, la heurística de Fiat-Shamir utiliza funciones hash para realizar operaciones hash sobre los scripts generados previamente, obteniendo así un valor que se utiliza como el valor del desafío.
Porque al considerar la función hash H como una función aleatoria, el desafío es elegido de manera uniforme y aleatoria, independiente de la información pública y el compromiso del probador. El análisis de seguridad considera que Alice no puede predecir la salida de H, solo puede tratarla como un oráculo. En este caso, la probabilidad de que Alice dé una respuesta correcta sin seguir el protocolo (especialmente cuando no conoce el secreto necesario) es inversamente proporcional al tamaño del rango de H.
Figura 1: Implementación de pruebas no interactivas utilizando la Heurística de Fiat-Shamir
FOAKS no interactivo
En esta sección, mostramos específicamente la aplicación de la heurística de Fiat-Shamir en el protocolo FOAKS, principalmente para generar el desafío en la parte de Brakedown, logrando así un FOAKS no interactivo.
Primero, vemos que en el paso de generación de pruebas de Brakedown, los pasos que requieren un desafío son la "verificación de proximidad" y la parte de prueba del árbol de Merkle (los lectores pueden referirse al artículo anterior para entender el protocolo de compromiso polinómico en FOAKS). Para el primer punto, el proceso original es que el probador necesita verificar un vector aleatorio generado por el verificador, el proceso de cálculo se muestra en la siguiente figura:
Figura 2: Comprobaciones de Brakedown en la prueba no interactiva FOAKS
Ahora usamos una función hash, permitiendo que el probador genere este vector aleatorio por sí mismo.
Definimos γ0=H(C1,R, r0,r1), en consecuencia, también se necesita agregar este paso de cálculo de γ0 en el cálculo de verificación. De acuerdo con esta construcción, se puede observar que antes de generar el compromiso, el probador no puede predecir el valor del desafío de antemano, por lo tanto no puede "hacer trampa" de antemano según el valor del desafío, es decir, generar un valor de compromiso falso, y además, debido a la aleatoriedad de la salida de la función hash, este valor de desafío también cumple con la aleatoriedad.
Para el segundo punto, definimos Î =H(C1,R, r0,r1,c1,y1,cγ0,yγ0).
Usamos pseudocódigo para dar las funciones de prueba y verificación de los compromisos polinómicos no interactivos modificados, que son las funciones utilizadas en el sistema FOAKS.
function PC. Commit(ϕ):
Parse fue una matriz de k × k. El probador calcula localmente la codificación del código tensor C1, C2, C1 es una matriz de k × n, C2 es una matriz de n × n.
for i ∈ [n] do
Calcular la raíz del árbol de Merkle Roott=Merkle.Commit(C2[:,i])
Calcular una raíz de árbol de Merkle R=Merkle.Commit([Root0,......Rootn-1]), y output R como el compromiso.
function PC. Prover(ϕ, X, R)
El probador genera un vector aleatorio γ0 ∈ Fk calculando: γ0 =H(C1,R, r0,r1)
Proximidad:
Consistencia:
El probador envía c1,y1,cγ0,yγ0 al verificador.
El probador calcula un vector Î como desafío, en el cual Î = H(C1,R, r0,r1,c1,y1,cγ0,yγ0)
for idx ∈ Î do
El probador envía C1 [:,idx] y la prueba del árbol de Merkle de Rootidx para C2 [:,idx] bajo R al verificador
function PC. VERIFY_EVAL(ΠX,X,y= ϕ (X),R)
Proximidad: ∀idx ∈ Î, Cγ0 [idx] == <γ0, C1[:,idx]> y Ec(yγ0) == Cγ0
Consistencia: ∀idx ∈ Î, C1 [idx] == <γ0, C1[:,idx]> y Ec(y1) == C1
y==
∀idx ∈ Î, Ec ( C1[:,idx]) es consistente con ROOTidx, y la prueba del árbol de Merkle de ROOTidx es válida.
Output acepta si todas las condiciones anteriores se mantienen. De lo contrario, output rechaza.
Conclusión
Muchos algoritmos de prueba de conocimiento cero dependen de la interacción entre el probador y el verificador, pero estos protocolos de prueba interactivos no son adecuados para aplicaciones que persiguen la eficiencia y tienen altos costos de comunicación en la red, como la protección de la privacidad de los datos en cadena y zkRollup. A través de la heurística de Fiat-Shamir, es posible permitir que el probador genere números aleatorios "desafíos" localmente sin comprometer la seguridad del protocolo, y que puedan ser verificados por el probador. Con este método, FOAKS también logra pruebas no interactivas y se aplica en el sistema.
Referencias
1.Fiat, Amos; Shamir, Adi (1987). "Cómo probarte a ti mismo: Soluciones prácticas a problemas de identificación y firma". Avances en Criptología — CRYPTO' 86. Notas de Conferencia en Informática. Springer Berlín Heidelberg. 263: 186–194. doi:10.1007/3-540-47721-7_12. ISBN 978-3-540-18047-0.
2.https://www.cnblogs.com/zhuowangy2k/p/12246575.html