原文：Sano y salvo: una inmersión profunda en la seguridad de STARK
Traducción y revisión: "Comunidad China Starknet"
Datos breves destacados
STARK no interactivo se deriva de Interactive Oracle Proof (IOP), compilado en una prueba no interactiva en el modelo de Oracle aleatorio.
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 de STARK
El sistema de prueba STARK, o argumento de conocimiento transparente escalable, es una herramienta poderosa 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 considerará 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 confiabilidad del conocimiento, pero en aras de la simplicidad, este artículo se centrará en casos simples sobre 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 le costaría a un atacante lanzar un ataque exitoso (es decir, encontrar una prueba STARK para una declaración falsa, pero el validador STARK acepta la prueba). 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 la forma en que todo el mundo habla de seguridad en cripto Twitter todos los días. En Twitter, es posible que escuche algo como esto: "Esta solución tiene 96 bits de seguridad". ¿Cómo se traduce esto en nuestra definición 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 con un tiempo de ejecución de 2⁹⁶ o menos tiene una probabilidad de éxito muy pequeña, menos de 2⁹⁶, que es 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 una situación en la 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 (Interactive Oracle Proof), árbol Merkle y hash Fiat-Shamir; nuestro enfoque principal es IOP. Una vez que se especifican estos componentes, podemos compilarlos para generar un STARK. Repasaremos estos componentes en detalle, incluyendo qué son y cómo encajan entre sí.
El primer componente que revisaremos es IOP: 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 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 todos los sistemas STARK actuales y cómo se construye el protocolo ethSTARK. Los STARK no interactivos también son un caso especial de SNARK transparentes (transparente significa que no se requiere una configuración confiable para crear una instancia; "Protocolo Arthur Merlin" o "IOP de moneda pública"). Para ello, 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, el demostrador de trampas tiene algunas vías estratégicas 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 el concepto de fiabilidad estándar del IOP no es suficiente 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, irrumpiendo así en 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, demostraremos que el atacante corre como máximo t pasos y que la probabilidad de que el ataque tenga éxito es como máximo (t) t 2⁹⁶.
PIO y confiabilidad ronda por ronda
La seguridad de STARK depende de su PIO subyacente. Pero ¿qué significa que un IOP tenga 96 bits de seguridad? Por definición estándar, el error de confiabilidad de IOP es 2⁹⁶: esto significa que la probabilidad de que cualquier atacante (independientemente del tiempo de ejecución) pueda engañar al validador es como máximo 2-96. Sin embargo, como comentamos, la confiabilidad del IOP es solo uno de los tres componentes, lo cual no es suficiente para obtener 96 bits de seguridad de un STARK compilado a partir de los tres pasos. Por el contrario, la seguridad del STARK compilado se demuestra asumiendo que el 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 todo el protocolo. 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 a 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 del IOP. 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 (medidas en el número de llamadas hash), entonces puede intentarlo en 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 elementos de error
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, por lo que si tenemos una función hash con una longitud de salida de 192 y un IOP con una confiabilidad ronda por ronda de 96 bits, obtenemos un STARK compilado que es confiable. Error sexual (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 el nivel de seguridad requerido, como 96 bits, el IOP subyacente debe cumplir con la confiabilidad ronda por ronda para garantizar que se mantengan altos niveles 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.
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.
Un análisis en profundidad de la seguridad completa de STARK
原文：Sano y salvo: una inmersión profunda en la seguridad de STARK
Traducción y revisión: "Comunidad China Starknet"
Datos breves destacados
Explicación detallada de la seguridad de STARK
El sistema de prueba STARK, o argumento de conocimiento transparente escalable, es una herramienta poderosa 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 considerará 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 confiabilidad del conocimiento, pero en aras de la simplicidad, este artículo se centrará en casos simples sobre 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 le costaría a un atacante lanzar un ataque exitoso (es decir, encontrar una prueba STARK para una declaración falsa, pero el validador STARK acepta la prueba). 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 la forma en que todo el mundo habla de seguridad en cripto Twitter todos los días. En Twitter, es posible que escuche algo como esto: "Esta solución tiene 96 bits de seguridad". ¿Cómo se traduce esto en nuestra definición de seguridad? No hay una respuesta única a esto, ya que la gente entiende "x bits de seguridad" de manera ligeramente diferente:
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 (Interactive Oracle Proof), árbol Merkle y hash Fiat-Shamir; nuestro enfoque principal es IOP. Una vez que se especifican estos componentes, podemos compilarlos para generar un STARK. Repasaremos estos componentes en detalle, incluyendo qué son y cómo encajan entre sí.
El primer componente que revisaremos es IOP: 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 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 todos los sistemas STARK actuales y cómo se construye el protocolo ethSTARK. Los STARK no interactivos también son un caso especial de SNARK transparentes (transparente significa que no se requiere una configuración confiable para crear una instancia; "Protocolo Arthur Merlin" o "IOP de moneda pública"). Para ello, 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, el demostrador de trampas tiene algunas vías estratégicas 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 el concepto de fiabilidad estándar del IOP no es suficiente 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, irrumpiendo así en 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, demostraremos que el atacante corre como máximo t pasos y que la probabilidad de que el ataque tenga éxito es como máximo (t) t 2⁹⁶.
PIO y confiabilidad ronda por ronda
La seguridad de STARK depende de su PIO subyacente. Pero ¿qué significa que un IOP tenga 96 bits de seguridad? Por definición estándar, el error de confiabilidad de IOP es 2⁹⁶: esto significa que la probabilidad de que cualquier atacante (independientemente del tiempo de ejecución) pueda engañar al validador es como máximo 2-96. Sin embargo, como comentamos, la confiabilidad del IOP es solo uno de los tres componentes, lo cual no es suficiente para obtener 96 bits de seguridad de un STARK compilado a partir de los tres pasos. Por el contrario, la seguridad del STARK compilado se demuestra asumiendo que el 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 todo el protocolo. 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 a 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 del IOP. 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 (medidas en el número de llamadas hash), entonces puede intentarlo en 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 elementos de error
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, por lo que si tenemos una función hash con una longitud de salida de 192 y un IOP con una confiabilidad ronda por ronda de 96 bits, obtenemos un STARK compilado que es confiable. Error sexual (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 el nivel de seguridad requerido, como 96 bits, el IOP subyacente debe cumplir con la confiabilidad ronda por ronda para garantizar que se mantengan altos niveles 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.