# Protocolo FRI : STARKS V By [0xFenrir](https://paragraph.com/@0xfenrir) · 2023-04-25 --- "_La matemática, vista correctamente, posee no sólo verdad, sino belleza suprema_" 🙂 Bienvenid@ una vez mas. En la entrega pasada hicimos una demostracion de que CP(composite polynomial) es un polinomio. Sin duda fue interesante, peeero…Pongamoslo asi, lo que haremos es ‘**demostrar que CP está cerca de un polinomio de bajo grado**’, en vez de demostrar que CP es un polinomio. ¿Cómo? ![](https://storage.googleapis.com/papyrus_images/b99a73e068b847a9afd305cab388bfecacd2a084acc092ff593a06066b3e1c48.png) Te recomiendo ir a mi publicación anterior para entender como llegamos hasta aqui, y que algunos nombres se te hagan familiares (para que no tengas esta cara al leer 😨): [https://mirror.xyz/0xc4eAb635B40bF49907375c3C7bd2495e3fDe79df/MFFRG2UNmnykW8nGc0sqc4xDd9wSqfe3l6ZcFH4QZVI](https://mirror.xyz/0xc4eAb635B40bF49907375c3C7bd2495e3fDe79df/MFFRG2UNmnykW8nGc0sqc4xDd9wSqfe3l6ZcFH4QZVI) Introducción a FRI: ------------------- **Fast Reed-Solomon Interactive Oracle Proof of Proximity** (FRI) es un nuevo IOPP (Interactive oracle proof of proximity) para códigos RS (Reed-Solomon). La gran complejidad computacional necesaria para demostrar la pertenencia en códigos RS ha sido un desafío significativo en la práctica. FRI aborda este problema ofreciendo los siguientes beneficios: El **probador** tiene una complejidad aritmética lineal, menor que **6·N**, lo que mejora los IOPP y PCPP anteriores de RS que requerían un tiempo de prueba superlineal para una complejidad de consulta polinomialmente grande. El **verificador** tiene una complejidad aritmética logarítmica (**≤ 21·log N**), con una complejidad de consulta de **2·log N y solidez constante.** FRI proporciona una mejor combinación de complejidad de consulta y solidez que el PCPP (Probabilistically Checkable Proofs of Proximity) cuasilineal de Ben-Sasson y Sudan (SICOMP 2008). ### FRI como solución a los códigos Reed-Solomon: Los códigos Reed-Solomon (RS) son fundamentales en la teoría de codificación algebraica y la informática teórica. Exploraremos diferentes modelos computacionales para problemas de proximidad RS y las soluciones que proporcionan. Los modelos discutidos incluyen: **Pruebas de proximidad RS:** En este modelo, el verificador tiene acceso de oráculo a una función ‘f’ y debe determinar si ‘f’ está en el código RS o lejos de todas las palabras de código sin datos adicionales. Aquí, un demostrador no tiene esfuerzo computacional, cero rondas de interacción y produce una prueba de longitud cero. **Verificación de proximidad RS - Modelo PCPP:** Este modelo utiliza Probabilistically Checkable Proofs of Proximity (PCPP), donde el verificador tiene acceso a una prueba auxiliar π además de la función f. **Verificación de proximidad RS - Modelo IOPP:** Interactive Oracle Proofs of Proximity (IOPP) Es un modelo que incluye varias rondas de interacción, donde el demostrador envía mensajes en respuesta a los mensajes sucesivos del verificador. El verificador consulta mensajes al azar, siendo la complejidad de consulta el número total de entradas leídas de ‘f’ y los mensajes del probador. En este modelo, la longitud de la prueba y la complejidad del probador se pueden reducir sin comprometer la solidez. Visualicemos un **ejemplo** de estos tres modelos utilizando una analogía **con libros, autores y editores**. 1. **Pruebas de proximidad RS:** Imagina que eres un editor que necesita verificar si el libro de un autor sigue un formato o estilo específico (es decir, el libro es una palabra de código). En este caso, no tienes información ni orientación adicionales del autor. Para verificar el formato del libro, tienes que leer algunas páginas al azar (consultas d+1) y ver si se ajustan al formato requerido. Si el libro está lejos del formato deseado, hay una alta probabilidad de que las páginas que revises revelen la discrepancia. 2. **Verificación de proximidad RS - Modelo PCPP:** Ahora, imagina que el autor te proporciona un documento adicional (el PCPP) que ofrece orientación o sugerencias para ayudarte a verificar el formato del libro de manera más eficiente. Este documento lo genera el autor, y tú, como editor, puedes consultar partes aleatorias tanto del libro como del documento de orientación. Las consultas te ayudan a verificar la adherencia del libro al formato requerido con alta confianza. El modelo PCPP reduce el número de consultas que necesitas hacer mientras aumenta la confianza en tu verificación. 3. **Verificación de proximidad RS - Modelo IOPP:** En este escenario, el autor y el editor participan en un proceso interactivo. El autor te envía varios mensajes (pruebas) en respuesta a tus consultas, y puedes consultar partes aleatorias tanto del libro como de estos mensajes. Este modelo interactivo permite más rondas de comunicación entre el autor y el editor, lo que potencialmente reduce la longitud de la prueba y la complejidad del prover sin comprometer la solidez. El ‘compromiso‘ o commitment ---------------------------- ¿Recuerdas como generamos el dominio de evaluacion o que este dominio en mas grande que el original? ¿Codigos de Reed - Solomon? De no ser asi, tranquilo, aqui te dejo un enlace a una de mis publicaciones anteriores: [https://mirror.xyz/0xc4eAb635B40bF49907375c3C7bd2495e3fDe79df/bgWIfmLN-Cg-KggzhpyvYvSSGjwK6XKDMT1HU2T9kZU](https://mirror.xyz/0xc4eAb635B40bF49907375c3C7bd2495e3fDe79df/bgWIfmLN-Cg-KggzhpyvYvSSGjwK6XKDMT1HU2T9kZU) En esta seccion vamos a explicar el flujo de funciones para que ocurra el ‘compromiso‘, pero, ¿Qué es el compromiso en el protocolo FRI? El compromiso implica generar un nuevo dominio de evaluación, generar un nuevo polinomio y evaluar dicho polinomio en el dominio correspondiente. A continuación, se explica el proceso en detalle: ### Generación del dominio: El primer dominio FRI es el dominio original. Cada dominio FRI posterior se obtiene tomando la primera mitad del dominio anterior (descartando la segunda mitad) y elevando al cuadrado cada uno de sus elementos. El primer dominio sera: `dominio_de_evaluación = 𝑤, 𝑤⋅ℎ, 𝑤⋅ℎ^2,..., 𝑤⋅ℎ^8191` La siguiente capa será, por lo tanto: `𝑤^2, (𝑤⋅ℎ)^2, (𝑤⋅ℎ^2)^2,..., (𝑤⋅ℎ^4095)^2` La siguiente capa sera: `𝑤^4,(𝑤⋅ℎ)^4,(𝑤⋅ℎ^2)^4,...,(𝑤⋅ℎ^2047)^4` Y asi sucesivamente. ### Operador de plegado FRI: El primer polinomio FRI es simplemente el polinomio de composición, es decir, CP. Cada polinomio FRI posterior se obtiene al: * Obtener un elemento aleatorio del campo 𝛽. * Multiplicar los coeficientes impares del polinomio anterior por 𝛽. * Sumar pares consecutivos (par-impar) de coeficientes. ![0. Separamos el polinomio original en coeficientes pares e impares, obtenemos un elemento aleatorio beta (𝛽) y lo multiplicamos con el polinomio de coeficientes impares, posteriormente consideramos el nuevo polinomio P1(x^2) = g(y) + 𝛽h(y)](https://storage.googleapis.com/papyrus_images/09b619d449eeb862432d1ed074e35c5fab4e40861e24845e8f65d4aa840ded74.png) 0\. Separamos el polinomio original en coeficientes pares e impares, obtenemos un elemento aleatorio beta (𝛽) y lo multiplicamos con el polinomio de coeficientes impares, posteriormente consideramos el nuevo polinomio P1(x^2) = g(y) + 𝛽h(y) ![1. Separamos el polinomio original en coeficientes pares e impares.](https://storage.googleapis.com/papyrus_images/bc3fb5f4d13ff049f05f0ed63446fafd9fe14d0d8c46f06b25e678e62480a9f9.png) 1\. Separamos el polinomio original en coeficientes pares e impares. ![2. tomamos los elementos pares y hacemos una transformacion siguiendo que g(x^2) -> g(y), es decir, haremos un cambio de variable. ](https://storage.googleapis.com/papyrus_images/e29454f0e0c9cd413660bdeb9400133fcc119147bb927d140ed9bc4cb655564f.png) 2\. tomamos los elementos pares y hacemos una transformacion siguiendo que g(x^2) -> g(y), es decir, haremos un cambio de variable. ![3. Obtenemos un nuevo polinomio par de menor grado que el polinomio par original.](https://storage.googleapis.com/papyrus_images/449b0046216f88a41c9a182063523168f40e2125ffd5ba2aca742fd244421f6a.png) 3\. Obtenemos un nuevo polinomio par de menor grado que el polinomio par original. ![4. Para el caso impar sacamos factor comun una de las 'x' en el polinomio impar transformandolo en un polinomio par. Con este polinomio par podemos realizar la misma sustitución hecha anteriormente g(x^2) -> g(y).](https://storage.googleapis.com/papyrus_images/70af497a526fad0d4f7db74803fdda51d7e98bb468796e2a01d996a9abe1b346.png) 4\. Para el caso impar sacamos factor comun una de las 'x' en el polinomio impar transformandolo en un polinomio par. Con este polinomio par podemos realizar la misma sustitución hecha anteriormente g(x^2) -> g(y). ![5. Obtuvimos otro polinomio de menor grado en función de 'y'.](https://storage.googleapis.com/papyrus_images/86e0773fb2c8811c96ed0a158978a84af6ed0847124aa479c98ac9ac9e54720c.png) 5\. Obtuvimos otro polinomio de menor grado en función de 'y'. ![6. Por ultimo, la 'x' que fue despejada como factor comun en el polinomio impar sera sustituida por 𝛽.](https://storage.googleapis.com/papyrus_images/c502b8b218ff59f29baa911edae253ae7f2f7be5b73915a242c912cfb1c5154d.png) 6\. Por ultimo, la 'x' que fue despejada como factor comun en el polinomio impar sera sustituida por 𝛽. ¿Hasta ahora todo bien? Lo que hicimos fue reducir el grado del polinomio original. Aplicaremos este operador a cada nuevo polinomio que este genere e inmediatamente lo evaluaremos en su correspondente dominio de evaluación. A esto lo llamos ‘commit’ o compromiso, es decir, evaluar un polinomio en un conjunto de puntos. ### Combinando todo para obtener la siguiente capa FRI: El compromiso implica generar un nuevo dominio de evaluación, generar un nuevo polinomio y evaluar dicho polinomio en el dominio correspondiente. A continuación, se explica el proceso en detalle: Tome un polinomio, un dominio y un elemento de campo (nuevamente, 𝛽), y devuelve el siguiente polinomio, el siguiente dominio y la evaluación de ese polinomio en ese dominio. 1. Comenzamos con un polinomio de compromiso, un conjunto de puntos donde evaluamos el polinomio y un árbol Merkle correspondiente a las evaluaciones del polinomio. 2. Creamos listas para almacenar los polinomios, dominios, capas de evaluación y árboles Merkle que vamos a generar. 3. Entramos en un bucle que se ejecuta hasta que el grado del último polinomio en nuestra lista sea mayor a 0. 4. En cada iteración del bucle, recibimos un número aleatorio (beta) desde el ‘channel’ y aplicamos una operación que nos ayuda a obtener el siguiente polinomio, dominio y capa de evaluación. 5. Añadimos estos nuevos valores a nuestras listas de polinomios, dominios y capas de evaluación. 6. Creamos un nuevo árbol Merkle utilizando la capa de evaluación recién generada y lo añadimos a nuestra lista de árboles Merkle. 7. Enviamos la raíz de este árbol Merkle a través de un canal de comunicación (Channel). 8. Una vez que el bucle termina, enviamos el coeficiente principal del último polinomio en nuestra lista a través del canal de comunicación (Channel). Aqui un **diagrama de flujo** de las operaciones que ocurren durante el **‘commitment’** en el tutorial **STARKS101** para una mejor visualizacion de lo que esta ocurriendo. [https://github.com/starkware-industries/stark101/blob/master/tutorial/Stark101-part3.ipynb](https://github.com/starkware-industries/stark101/blob/master/tutorial/Stark101-part3.ipynb) ![Flujo de operaciones durante el 'commitment'.](https://storage.googleapis.com/papyrus_images/45843e9cbb92b3e65fd157335801ea24e7547895f229d69ce039d2bd49db1767.png) Flujo de operaciones durante el 'commitment'. Al final de este proceso, tenemos una serie de listas que contienen información sobre los polinomios, dominios, capas de evaluación y árboles Merkle que se han generado. Estos datos se utilizan posteriormente en el proceso de "decommitment" para verificar si el polinomio original está cerca de un código Reed-Solomon. Canal o Channel --------------- El canal permite la transferencia de información entre ambas partes, facilitando el proceso de interacción en el protocolo. Una de las funciones clave del canal es proporcionar elementos de campo aleatorios durante el proceso de 'commitment'. Estos elementos aleatorios son utilizados para "mezclar" los coeficientes del polinomio en cada paso, lo que garantiza una mayor seguridad en la verificación. En particular estamos usando la heurística de Fiat-Shamir (Fiat-Shamir heuristic). Esta se utiliza para convertir protocolos interactivos en protocolos no interactivos (FRI es interactivo). En lugar de que el verificador genere y envíe desafíos al demostrador, el demostrador genera estos desafíos a partir de una función de hash aplicada a la información previamente compartida. De esta manera, se elimina la necesidad de interacción directa entre el demostrador y el verificador En esta publicacion solo haremos mencion de la heurística de Fiat-Shamir, dado que por si solo requiere un articulo, pero es importante saber que es parte de nuestro proceso para generar elementos aleatorios durante el commit y decommit. ‘Descompromiso‘ o Decommit -------------------------- La fase de **descompromiso** (decommitment phase) es una etapa crucial en la que el **prover revela información adicional necesaria** para que el **verificador compruebe la validez de la prueba**. Durante el descompromiso, el verificador solicita al prover que revele ciertos valores de las capas. Estas solicitudes se basan en consultas aleatorias (𝛽i) para garantizar que el proceso de verificación siga siendo seguro y resistente a manipulaciones. El probador responde a estas solicitudes **compartiendo los valores solicitados** y **Merkle proofs** para garantizar la autenticidad de los valores compartidos. ![1. En la primera ronda el probador enviara f(x), f(x g) y f(x g^2). Con estos valores el verificador puede calcular CP0(x) y comparar con el valor suministrado por el probador usando el 'path', luego envia al prover un elemento aleatorio beta '𝛽'. Con dicho elemento el probador devolvera CP1(x^2) y la ruta o path.](https://storage.googleapis.com/papyrus_images/97e142dcd7490ac138aac10f2e17c3ad2bef363cb76789526cf43794d7d287ef.png) 1\. En la primera ronda el probador enviara f(x), f(x g) y f(x g^2). Con estos valores el verificador puede calcular CP0(x) y comparar con el valor suministrado por el probador usando el 'path', luego envia al prover un elemento aleatorio beta '𝛽'. Con dicho elemento el probador devolvera CP1(x^2) y la ruta o path. ![2. Para calcular CP1(x^2), el verificador solo necesita CP0(x) y CP(-x) por parte del probador y la ruta o path (para comparar con el dado por el probador). ](https://storage.googleapis.com/papyrus_images/8c4528b4b7d6ff43160c94b4d2ee5d001baa57464a9da12432677e2453b6edba.png) 2\. Para calcular CP1(x^2), el verificador solo necesita CP0(x) y CP(-x) por parte del probador y la ruta o path (para comparar con el dado por el probador). ![3. En cada ronda el verificador calculara cada sucesivo CPi.](https://storage.googleapis.com/papyrus_images/99e3728ff97d39f310a5095d72acc98457d65122ac838ce89975bc1be2233f96.png) 3\. En cada ronda el verificador calculara cada sucesivo CPi. El verificador utiliza la información proporcionada durante la fase de descompromiso para comprobar si los valores revelados son consistentes con los compromisos previamente compartidos y si cumplen con las propiedades esperadas. Si el **verificador encuentra que los valores compartidos cumplen con estos criterios**, entonces se convence de que el **probador conoce un polinomio de bajo grado que coincide con los valores iniciales**, lo que completa la **verificación**. wujuuu! 🚀🚀🚀 Cada vez que todo este proceso ocurre lo llamamos **‘queries‘ o consultas**. Una consulta envia todas las capas y las rutas asociadas o paths. El numero de queries dependera del protocolo. En el caso del tutorial STARKS101 hacen 3 consultas. Ver en: [https://github.com/starkware-industries/stark101/blob/master/tutorial/Stark101-part4.ipynb](https://github.com/starkware-industries/stark101/blob/master/tutorial/Stark101-part4.ipynb) Si has llegado hasta aqui, felicitaciones, tienes una mejor intuición matemática sobre el protocolo FRI y los STARKS. Espero te haya gustado. 😁 ![Gracias](https://storage.googleapis.com/papyrus_images/ca5e72a5f8b520ef2708db09838c7fd97edd4f427b929d9128614a6ec11889ce.png) Gracias --- *Originally published on [0xFenrir](https://paragraph.com/@0xfenrir/protocolo-fri-starks-v)*