Análisis de los principios de Binius STARKs y reflexiones sobre su optimización

1 Introducción

Una de las principales razones de la baja eficiencia de STARKs es que la mayoría de los valores en los programas reales son bastante pequeños, como los índices en los bucles for, valores booleanos, contadores, etc. Sin embargo, para garantizar la seguridad de las pruebas basadas en árboles de Merkle, al usar codificación de Reed-Solomon para ampliar los datos, muchos valores redundantes adicionales ocupan todo el dominio, incluso si el valor original en sí es muy pequeño. Para resolver este problema, reducir el tamaño del dominio se ha convertido en una estrategia clave.

Como se muestra en la Tabla 1, el ancho de codificación de la primera generación de STARKs es de 252 bits, el ancho de codificación de la segunda generación de STARKs es de 64 bits, y el ancho de codificación de la tercera generación de STARKs es de 32 bits, aunque el ancho de codificación de 32 bits todavía presenta una gran cantidad de espacio desperdiciado. En comparación, el campo binario permite operar directamente sobre los bits, lo que hace que la codificación sea compacta y eficiente sin ningún espacio desperdiciado, es decir, la cuarta generación de STARKs.

Tabla 1: Rutas de derivación de STARKs

| Álgebra | Ancho de bit | Dominio | |------|------|------| | Primera Generación | 252bit | Campo Primal | | Segunda generación | 64bit | Goldilocks | | Tercera generación | 32bit | Campo primo | | Cuarta Generación | 1bit | Dominio Binario |

En comparación con los campos finitos descubiertos en investigaciones recientes como Goldilocks, BabyBear y Mersenne31, la investigación sobre campos binarios se remonta a la década de 1980. Actualmente, los campos binarios se utilizan ampliamente en criptografía, y ejemplos típicos incluyen:

• Estándar de cifrado avanzado ( AES ), basado en el dominio F28;

• Galois código de autenticación de mensajes ( GMAC ), basado en el campo F2128;

• Código QR, utiliza codificación Reed-Solomon basada en F28;

• Protocolo FRI y zk-STARK originales, así como la función hash Grøstl que llegó a la final de SHA-3, que se basa en el campo F28, es un algoritmo hash muy adecuado para la recursión.

Cuando se utilizan dominios más pequeños, la operación de extensión de dominio se vuelve cada vez más importante para garantizar la seguridad. El dominio binario utilizado por Binius depende completamente de la extensión de dominio para garantizar su seguridad y viabilidad práctica. La mayoría de los polinomios involucrados en los cálculos de Prover no necesitan entrar en la extensión de dominio, sino que operan solo en el dominio base, logrando así una alta eficiencia en dominios pequeños. Sin embargo, la verificación de puntos aleatorios y el cálculo FRI aún requieren profundizar en un dominio de extensión más grande para garantizar la seguridad necesaria.

Al construir un sistema de pruebas basado en el dominio binario, existen 2 problemas prácticos: al calcular la representación de la traza en STARKs, el tamaño del dominio utilizado debe ser mayor que el grado del polinomio; al comprometer el árbol de Merkle en STARKs, se debe realizar la codificación de Reed-Solomon, y el tamaño del dominio utilizado debe ser mayor que el tamaño después de la expansión de la codificación.

Binius propuso una solución innovadora que aborda estos dos problemas por separado y representa los mismos datos de dos maneras diferentes: primero, utilizando un polinomio multivariable (, específicamente un polinomio multilineal ), en lugar de un polinomio univariable, representando toda la trayectoria de cálculo a través de sus valores en "hipercubos" (; en segundo lugar, dado que la longitud de cada dimensión del hipercubo es 2, no se puede realizar una expansión estándar de Reed-Solomon como en STARKs, pero se puede considerar el hipercubo como un cuadrado ), basado en el cual se realiza la expansión de Reed-Solomon. Este método, al garantizar la seguridad, mejora enormemente la eficiencia de codificación y el rendimiento computacional.

2 Análisis de principios

La construcción de la mayoría de los sistemas SNARKs actuales generalmente incluye las siguientes dos partes:

• Prueba de Oracle Interactiva Polinómica de Teoría de la Información (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, como núcleo del sistema de prueba, convierte las relaciones computacionales de entrada en ecuaciones polinómicas verificables. Diferentes protocolos PIOP, a través de la interacción con el verificador, permiten que el probador envíe polinomios de manera gradual, de modo que el verificador pueda validar si el cálculo es correcto consultando solo unos pocos resultados de evaluación de polinomios. Los protocolos PIOP existentes incluyen: PLONK PIOP, Spartan PIOP y HyperPlonk PIOP, cada uno de los cuales trata las expresiones polinómicas de manera diferente, lo que afecta el rendimiento y la eficiencia de todo el sistema SNARK.

• Esquema de Compromiso Polinómico ( Polynomial Commitment Scheme, PCS ): El esquema de compromiso polinómico se utiliza para probar si la igualdad polinómica generada por PIOP es válida. PCS es una herramienta criptográfica que permite al probador comprometerse a un polinomio y luego verificar el resultado de la evaluación de ese polinomio, al mismo tiempo que oculta otra información del polinomio. Los esquemas de compromiso polinómico más comunes incluyen KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) y Brakedown, entre otros. Diferentes PCS tienen diferentes rendimientos, seguridad y escenarios de aplicación.

Según las necesidades específicas, elija diferentes PIOP y PCS, y combine con un campo finito o curva elíptica adecuados, se puede construir un sistema de prueba con diferentes atributos. Por ejemplo:

• Halo2: combina PLONK PIOP y Bulletproofs PCS, y se basa en la curva Pasta. Halo2 se diseñó con un enfoque en la escalabilidad y en la eliminación del setup de confianza en el protocolo ZCash.

• Plonky2: utiliza la combinación de PLONK PIOP y FRI PCS, y se basa en el campo de Goldilocks. Plonky2 está diseñado para lograr recursividad eficiente. Al diseñar estos sistemas, la PIOP y la PCS seleccionadas deben coincidir con el campo finito o la curva elíptica utilizada, para garantizar la corrección, el rendimiento y la seguridad del sistema. La elección de estas combinaciones no solo afecta el tamaño de la prueba y la eficiencia de la verificación del SNARK, sino que también determina si el sistema puede lograr transparencia sin una configuración confiable, y si puede soportar funciones de extensión como pruebas recursivas o pruebas de agregación.

Binius: HyperPlonk PIOP + Brakedown PCS + campos binarios. En concreto, Binius incluye cinco tecnologías clave para lograr su eficiencia y seguridad. Primero, la aritmética basada en torres de campos binarios (towers of binary fields) constituye la base de sus cálculos, permitiendo realizar operaciones simplificadas dentro del campo binario. En segundo lugar, Binius adapta la verificación de productos y permutaciones de HyperPlonk en su protocolo de pruebas Oracle interactivas (PIOP), asegurando una verificación consistente y segura entre las variables y sus permutaciones. Tercero, el protocolo introduce una nueva prueba de desplazamiento multilineal, optimizando la eficiencia de la verificación de relaciones multilineales en pequeños campos. Cuarto, Binius utiliza una versión mejorada de la prueba de búsqueda Lasso, que proporciona flexibilidad y una fuerte seguridad para el mecanismo de búsqueda. Por último, el protocolo utiliza un esquema de compromiso polinómico de campo pequeño (Small-Field PCS), permitiéndole implementar un sistema de pruebas eficiente en campos binarios y reduciendo el costo asociado normalmente con campos grandes.

( 2.1 Campo finito: aritmética basada en torres de campos binarios

Los campos binarios en torre son clave para implementar cálculos rápidos y verificables, principalmente debido a dos aspectos: cálculo eficiente y aritmética eficiente. Los campos binarios, en esencia, permiten operaciones aritméticas altamente eficientes, lo que los convierte en una opción ideal para aplicaciones criptográficas sensibles a los requisitos de rendimiento. Además, la estructura del campo binario apoya un proceso de aritmética simplificado, es decir, las operaciones realizadas en el campo binario pueden ser representadas en una forma algebraica compacta y fácil de verificar. Estas características, junto con la capacidad de aprovechar completamente su naturaleza jerárquica a través de la estructura en torre, hacen que los campos binarios sean particularmente adecuados para sistemas de prueba escalables como Binius.

Donde "canonical" se refiere a la representación única y directa de un elemento en un campo binario. Por ejemplo, en el campo binario más básico F2, cualquier cadena de k bits se puede mapear directamente a un elemento de campo binario de k bits. Esto es diferente de los campos primos, que no pueden proporcionar esta representación canónica dentro de un número fijo de bits. Aunque un campo primo de 32 bits puede caber en 32 bits, no todas las cadenas de 32 bits pueden corresponder de manera única a un elemento de campo, mientras que el campo binario tiene esta conveniencia de mapeo uno a uno. En el campo primo Fp, los métodos de reducción comunes incluyen la reducción de Barrett, la reducción de Montgomery, y métodos de reducción especiales para campos finitos específicos como Mersenne-31 o Goldilocks-64. En el campo binario F2k, los métodos de reducción comunes incluyen la reducción especial ) como se usa en AES ###, la reducción de Montgomery ( como se usa en POLYVAL ) y la reducción recursiva ( como Tower ). El artículo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" señala que en el campo binario no es necesario introducir acarreo en las operaciones de suma y multiplicación, y que la operación de cuadrado en el campo binario es muy eficiente, ya que sigue la regla simplificada (X + Y )2 = X2 + Y 2.

Como se muestra en la Figura 1, una cadena de 128 bits: esta cadena puede ser interpretada de varias maneras en el contexto de un campo binario. Puede ser vista como un elemento único en un campo binario de 128 bits, o desglosada en dos elementos de campo de torre de 64 bits, cuatro elementos de campo de torre de 32 bits, 16 elementos de campo de torre de 8 bits, o 128 elementos de campo F2. Esta flexibilidad de representación no requiere sobrecarga calculacional, solo una conversión de tipo de cadena de bits (typecast), lo cual es una propiedad muy interesante y útil. Al mismo tiempo, los elementos de campo pequeños pueden ser empaquetados en elementos de campo más grandes sin necesidad de sobrecarga calculacional adicional. El protocolo Binius se beneficia de esta característica para mejorar la eficiencia computacional. Además, el artículo "On Efficient Inversion in Tower Fields of Characteristic Two" explora la complejidad computacional de multiplicación, elevación al cuadrado y operaciones inversas en un campo de torre binario de n bits ( descomponible en un subcampo de m bits ).

Figura 1: Dominio binario en torre

( 2.2 PIOP: versión adaptada de HyperPlonk Product y PermutationCheck------aplicable al campo binario

El diseño de PIOP en el protocolo Binius se basa en HyperPlonk y utiliza una serie de mecanismos de verificación fundamentales para validar la corrección de polinomios y conjuntos multivariables. Estos chequeos esenciales incluyen:

1. GateCheck: Verificar si el testigo de confidencialidad ω y la entrada pública x satisfacen la relación de operación del circuito C)x, ω###=0, para asegurar el correcto funcionamiento del circuito.

2. PermutationCheck: Verificar si los resultados de evaluación de dos polinomios multivariables f y g en el hipercubo booleano son una relación de permutación f(x) = f(π)x((, para asegurar la consistencia de la permutación entre las variables del polinomio.

3. LookupCheck: Verifica si la evaluación del polinomio está en la tabla de búsqueda dada, es decir, f)Bµ) ⊆ T(Bµ), asegurando que ciertos valores estén dentro del rango especificado.

4. MultisetCheck: verifica si dos conjuntos multivariables son iguales, es decir, {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, asegurando la consistencia entre múltiples conjuntos.

5. ProductCheck: Verifica si la evaluación de un polinomio racional en el hipercubo booleano es igual a un valor declarado ∏x∈Hµ f(x) = s, para asegurar la corrección del producto del polinomio.

6. ZeroCheck: Verificar si un polinomio multivariado en el hipercubo booleano es cero en cualquier punto ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, para asegurar la distribución de los ceros del polinomio.

7. SumCheck: Verifica si la suma de un polinomio multivariado es igual al valor declarado ∑x∈Hµ f(x) = s. Al transformar el problema de evaluación de polinomios multivariados en uno de evaluación de polinomios univariados, se reduce la complejidad computacional para el verificador. Además, SumCheck también permite el procesamiento por lotes, introduciendo números aleatorios para construir combinaciones lineales que permiten el procesamiento por lotes de múltiples instancias de verificación de sumas.

8. BatchCheck: Basado en SumCheck, verifica la corrección de la evaluación de múltiples polinomios multivariables para mejorar la eficiencia del protocolo.

A pesar de que Binius y HyperPlonk tienen muchas similitudes en el diseño del protocolo, Binius ha realizado mejoras en los siguientes 3 aspectos:

• Optimización de ProductCheck: en HyperPlonk, ProductCheck requiere que el denominador U sea no cero en toda la hipercubierta, y el producto debe ser igual a un valor específico; Binius simplifica este proceso de verificación al especializar dicho valor a 1, reduciendo así la complejidad de cálculo.

• Manejo del problema de la división por cero: HyperPlonk no pudo manejar adecuadamente el caso de división por cero, lo que llevó a no poder afirmar que U es no cero en el hipercubo; Binius manejó correctamente este problema, incluso cuando el denominador es cero, el ProductCheck de Binius puede continuar procesando, permitiendo la extensión a cualquier valor de producto.

• Comprobación de Permutaciones de Filas: HyperPlonk no tiene esta función; Binius admite la comprobación de permutaciones entre múltiples filas, lo que permite a Binius manejar situaciones de arreglos polinómicos más complejas.

Por lo tanto, Binius ha mejorado el mecanismo existente de PIOPSumCheck, aumentando la flexibilidad y eficiencia del protocolo, especialmente al manejar la verificación de polinomios multivariables más complejos, proporcionando un soporte funcional más fuerte. Estas mejoras no solo resuelven las limitaciones en HyperPlonk, sino que también establecen una base para futuros sistemas de pruebas basados en campos binarios.

( 2.3 PIOP: nuevo argumento de desplazamiento multilineal ------ aplicable al hipercubo booleano

En el protocolo Binius, la construcción y el manejo de polinomios virtuales son clave.