Título: Sano y salvo: una mirada profunda a la seguridad de STARK
Traducción y revisión: "Comunidad China Starknet"
Datos breves destacados
STARK no interactivo se deriva de Pruebas interactivas de Oracle (IOP), compiladas en pruebas no interactivas en el modelo estocástico de Oracle.
Este artículo explica las últimas actualizaciones de la documentación de ethSTARK y proporciona un análisis completo y detallado de la seguridad del protocolo ethSTARK en el modelo aleatorio de Oracle.
Explicación detallada de la seguridad STARK
El sistema de prueba STARK, o argumento de conocimiento transparente escalable, es una poderosa herramienta para la integridad computacional: permite una verificación confiable de la exactitud de los cálculos realizados con datos públicos. En este artículo, profundizaremos en la seguridad proporcionada por las pruebas STARK, las definiremos y exploraremos técnicas para demostrar la seguridad de los esquemas.
(Lea la sección 6 de la documentación de ethSTARK (versión 1.2) para obtener más detalles, así como el importante y completo trabajo independiente sobre este tema realizado por Block et al.)
¿Qué intentamos lograr con el análisis de seguridad? Queremos evitar "ataques exitosos" al sistema STARK causados por una declaración falsa y la prueba STARK aceptada por el validador STARK en respuesta a esa declaración (falsa). Debido a que las tergiversaciones son peligrosas y pueden presentarse en todos los tamaños y formas, queremos estar a salvo de todas ellas. Cualquier declaración falsa, incluso tan trivial como 1+1=3, cuando se combina con una prueba STARK aceptada por un validador STARK, se considera un ataque exitoso al sistema. (Aquellos con experiencia en criptografía pueden estar interesados en saber que STARK también puede satisfacer conceptos de seguridad más sólidos, como la confiabilidad del conocimiento, pero en aras de la simplicidad, este artículo se centrará en el caso simple de confiabilidad).
¿Cómo definimos formalmente la seguridad de un sistema STARK? Esto lo determinamos analizando el "error de confiabilidad". El "error de confiabilidad" mide aproximadamente el "costo" esperado que necesitaría un atacante para lanzar un ataque exitoso (es decir, encontrar una prueba STARK para una declaración falsa que sea aceptada por un validador STARK). Matemáticamente hablando, el error de confiabilidad es una función (t) cuya entrada es el parámetro de tiempo t, que representa el tiempo computacional que el atacante está dispuesto a emplear para lanzar un ataque, y la salida es la probabilidad de que el ataque del atacante tenga éxito (encontrada para declaraciones falsas prueba convincente). Cuanto mayor sea el "coste" t que el atacante esté dispuesto a gastar, mayor será su probabilidad de éxito.
Hasta ahora hemos definido la seguridad de STARK como una función (t), que es diferente de cómo se discute la seguridad en cripto Twitter todos los días. En Twitter, es posible que escuche: "Esta solución tiene 96 bits de seguridad". No hay una respuesta única a esto, ya que la gente entiende "x bits de seguridad" de manera ligeramente diferente:
Interpretado estrictamente, esto significa que para cualquier t entre 1 y 2⁹⁶, el error de confiabilidad es (t) 2⁹⁶. Un atacante que corre por 2⁹⁶ o menos tiene una probabilidad de éxito muy pequeña, menos de 2⁹⁶, o menos de 1 entre mil millones por 1 entre mil millones.
Una interpretación más vaga, y quizás más común, es que la seguridad de 96 bits significa que para cualquier t, existe un caso en el que t/(t) 2⁹⁶. Esto significa que la probabilidad de éxito es (inversamente) lineal con el tiempo de ejecución. Si el atacante tiene un tiempo de ejecución de 2⁸⁶, entonces su probabilidad de éxito es como máximo 2¹⁰.
En este artículo, discutiremos la segunda opción.
De IOP a STARK con seguridad de 96 bits
Entonces, ¿cómo demostramos que una solución tiene 96 bits de seguridad? Para responder a esta pregunta, debemos comprender la estructura de alto nivel sobre la que se construye STARK. STARK consta de tres partes principales: IOP (Prueba interactiva de Oracle), árbol Merkle y hash Fiat-Shamir. Nuestro enfoque principal es IOP. Una vez que se especifican estos componentes, podemos compilarlos para producir un STARK. Repasaremos estos componentes en detalle, incluyendo qué son y cómo encajan entre sí.
El primer componente que revisaremos es el IOP: el IOP es similar a una prueba interactiva estándar, donde el probador y el validador interactúan durante múltiples rondas (estamos limitados a protocolos de monedas públicas, donde el validador solo envía desafíos aleatorios al probador). En un IOP, el verificador no lee completamente el mensaje del probador, sino que toma muestras de una pequeña porción de los bits de cada mensaje del probador. Es por eso que el STARK compilado posteriormente logra su simplicidad.
Dado el IOP, ¿cómo construyo un STARK a partir de él? Los mensajes del probador pueden ser muy largos (de hecho, son más largos que el cálculo mismo). Para comprimir esta información, utilizamos árboles Merkle. Un árbol Merkle es un árbol hash binario en el que cada nodo hoja representa una consulta o una respuesta en el IOP. Las raíces son la promesa de todo el mensaje. Cuando un validador quiere leer una ubicación específica en un mensaje, el probador proporciona el valor de esa ubicación y la ruta de verificación. Luego, el validador puede usar esta ruta para verificar que el valor sea correcto. El validador de IOP lee solo una pequeña cantidad de información de ubicación de la información del probador. Por lo tanto, se pueden implementar protocolos concisos (protocolos con bajo volumen de comunicación) utilizando árboles Merkle.
Rondas de compresión
Podemos elegir STARK interactivo, pero para simplificar el proceso de generación de STARK, generalmente elegimos STARK no interactivo para que el validador no necesite esperar información externa al crear STARK. De hecho, así es como se implementan actualmente todos los sistemas STARK y cómo se construye el protocolo ethSTARK. Los STARK no interactivos también son un caso especial de SNARK transparentes (transparentes significa que no se requiere una configuración confiable para crear instancias; "Protocolo Arthur Merlin" o "IOP de moneda pública"). Para hacer esto, el último paso es aplicar el algoritmo Fiat-Shamir para comprimir múltiples rondas de interacciones en un solo mensaje, lo que llamamos prueba STARK. La transformación Fiat-Shamir es un método para convertir un protocolo interactivo en un protocolo no interactivo. El probador simula un protocolo interactivo mientras habla con la función hash. Para derivar el desafío aleatorio para la ronda i, el probador codifica el registro parcial de la ronda i e interpreta el resultado como el siguiente desafío.
Esto garantiza que el probador no pueda cambiar su respuesta después de generar el desafío. Sin embargo, quienes demuestran hacer trampa tienen algunas vías políticas nuevas que no están disponibles en los IOP interactivos. El probador puede regenerar el desafío del validador modificando la información del último probador, de modo que obtenga un nuevo registro y, por lo tanto, un nuevo desafío. Resulta que los conceptos de fiabilidad estándar del IOP no son suficientes para demostrar la seguridad de la conversión Fiat-Shamir.
Por ejemplo, tenga un IOP de 96 rondas y agregue el siguiente truco al validador: si el primer bit de aleatoriedad del validador es 0 en cada una de las 96 rondas, entonces el validador lo aceptará (sin ver ninguna prueba). Podemos ver que agregar este truco al validador solo agrega un término de 2⁹⁶ al error de confiabilidad del IOP. Sin embargo, después de la transformación Fiat-Shamir, un atacante puede modificar fácilmente la información del probador para garantizar que cada valor hash comience con 0, comprometiendo así el sistema en muy poco tiempo. Tenga la seguridad de que este terrible escenario es sólo un ejemplo teórico y no se aplica a los STARK desplegados. Entonces, echemos un vistazo a por qué nuestro STARK es seguro después de todo. En resumen, mostraremos que, para un atacante que ejecuta como máximo t pasos, la probabilidad de un ataque exitoso es como máximo (t) t 2⁹⁶.
PIO y confiabilidad ronda por ronda
La seguridad de STARK depende de sus IOP subyacentes. Pero ¿qué significa que un IOP tenga 96 bits de seguridad? Por definición estándar, IOP tiene un error de confiabilidad de 2⁹⁶: esto significa que la probabilidad de que cualquier atacante (independientemente del tiempo de ejecución) pueda engañar a un validador es como máximo de 2-96. Sin embargo, como comentamos, la confiabilidad del IOP es solo uno de los tres componentes, lo cual no es suficiente para lograr 96 bits de seguridad de un STARK compilado a partir de los tres pasos. Por el contrario, la seguridad de STARK compilado se demuestra asumiendo que STARK tiene un error de confiabilidad ronda por ronda de 96 bits (a veces se usa una definición similar llamada confiabilidad de recuperación de estado).
Intuitivamente, "solidez ronda por ronda" significa que cada ronda tiene 96 bits de seguridad, no solo el protocolo completo. Para ser más específico, la confiabilidad ronda por ronda se refiere a la existencia de un predicado que puede obtener parte del registro del protocolo y decirnos si este registro es "engañoso": "registro vacío" no es "engañoso", y cuándo Y el registro completo es "engañoso" sólo si lo acepta el validador. Finalmente, para cualquier registro parcial que no "suplante" al validador, la probabilidad de que el registro se convierta en "suplantación" en la siguiente ronda es como máximo 2⁹⁶. Si hay un predicado con estas propiedades, decimos que el protocolo tiene 96 bits de confiabilidad ronda por ronda (este predicado no requiere un cálculo eficiente).
En muchos casos, la gente sólo analiza la confiabilidad de la PIO y no su confiabilidad ronda a ronda. Es cierto que es difícil pensar en un ejemplo (excepto en los ejemplos fabricados) de un IOP que tenga confiabilidad estándar pero no confiabilidad ronda a ronda. Sin embargo, al derivar límites de seguridad específicos, pueden surgir diferencias entre los dos y cada bit cuenta. Por lo tanto, para derivar límites estrictos y específicos, es necesario un análisis riguroso de la confiabilidad ronda por ronda de la PIO. Esto es exactamente lo que estamos haciendo con el protocolo FRI y el ethSTARK IOP en el que se basa STARK IOP. El análisis en sí está lejos de ser trivial y está más allá del alcance de este artículo. Utilizando el nuevo análisis, podemos establecer parámetros precisos para nuestra prueba.
La confiabilidad paso a paso realmente nos brinda la seguridad que necesitamos. El probador puede regenerar el desafío varias veces, pero sabemos que en cualquier ronda, la probabilidad de generar un registro fraudulento es 2⁹⁶. Por lo tanto, si el probador tiene t veces (medido en el número de llamadas hash), entonces puede intentarlo. la mayoría de t veces para obtener un registro engañoso, lo que limita su probabilidad de éxito a (t) t 2⁹⁶.
Agregar todos los errores
Finalmente, para que todo esto sea cierto, debemos asegurarnos de que el probador no pueda alterar el árbol Merkle. Podemos demostrar que mientras el probador no encuentre colisiones en la función hash, no puede hacer trampa en el árbol Merkle. La probabilidad de que un atacante encuentre una colisión usando llamadas t (función hash aleatoria) es como máximo t2/2, que es la longitud de salida de la función hash (causada por la "paradoja del cumpleaños"). función hash La longitud es el doble de la seguridad requerida. Entonces, si tenemos una función hash con una longitud de salida de 192 y un IOP con confiabilidad ronda por ronda de 96 bits, obtenemos un STARK compilado que es confiable. El error lineal (t). )=t2-⁹⁶ + t2 2¹⁹⁶. Dado que t/(t) = t/(t 2⁹⁶+t2 2¹⁹⁶) 1/(2⁹⁶+1/2⁹⁶) = 2²⁹⁵, este esquema tiene 95 bits de sexo de seguridad.
Resumir
En conjunto, STARK proporciona un método poderoso para verificar sin confianza la exactitud de los cálculos realizados con datos públicos. La seguridad de STARK generalmente se mide por el "error de confiabilidad", que representa la probabilidad de que un atacante proporcione con éxito una declaración falsa y convenza al validador con una prueba. Para lograr un nivel de seguridad requerido, como 96 bits, el IOP subyacente debe cumplir con la confiabilidad ronda por ronda, garantizando que se mantenga un alto nivel de seguridad en cada ronda. Analizamos la confiabilidad ronda por ronda de los IOP en los que se basa nuestro STARK para derivar límites de seguridad específicos.