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 los STARKs es que la mayoría de los valores en los programas reales son pequeños, como los índices en los bucles for, valores booleanos, contadores, etc. Sin embargo, para garantizar la seguridad de las pruebas basadas en el árbol de Merkle, al expandir los datos utilizando codificación de Reed-Solomon, muchos valores redundantes adicionales ocuparán 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.

La ancho de codificación de la primera generación de STARKs es de 252 bits, la ancho de codificación de la segunda generación de STARKs es de 64 bits, y la ancho de codificación de la tercera generación de STARKs es de 32 bits, pero el ancho de codificación de 32 bits todavía presenta un gran desperdicio de espacio. En comparación, el dominio binario permite operar directamente sobre los bits, codificando de manera compacta y eficiente sin ningún desperdicio de espacio, es decir, la cuarta generación de STARKs.

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. En la actualidad, los campos binarios se utilizan ampliamente en criptografía, y ejemplos típicos incluyen:

• Estándar de Cifrado Avanzado (AES), basado en el campo F28;

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

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

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

Cuando se utilizan dominios más pequeños, las operaciones de extensión son cada vez más importantes para garantizar la seguridad. El dominio binario utilizado por Binius depende completamente de la extensión 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, sino que operan solo en el campo base, logrando así alta eficiencia en un dominio pequeño. Sin embargo, la verificación de puntos aleatorios y los cálculos de FRI aún deben profundizarse en un dominio de extensión más grande para garantizar la seguridad requerida.

Al construir un sistema de prueba basado en el dominio binario, existen 2 problemas prácticos: en STARKs, el tamaño del dominio utilizado al calcular la representación del rastro debe ser mayor que el grado del polinomio; en STARKs, al comprometer el árbol de Merkle, es necesario 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 logra representar los mismos datos de dos maneras diferentes: primero, utilizando polinomios multivariables (específicamente polinomios multilineales) en lugar de polinomios univariables, representando toda la trayectoria de cálculo a través de sus valores en "hiper-cubos" (hypercubes); en segundo lugar, dado que la longitud de cada dimensión del hiper-cubo es 2, no se puede realizar una extensión de Reed-Solomon estándar como en STARKs, pero se puede considerar el hiper-cubo como un cuadrado (square) y realizar la extensión de Reed-Solomon basada en ese cuadrado. Este método, mientras garantiza la seguridad, mejora enormemente la eficiencia del codificado y el rendimiento del cálculo.

2 Análisis de principios

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

• Prueba de Oráculo Interactivo Polinómico de Teoría de la Información (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, como el núcleo del sistema de pruebas, transforma la relación computacional de entrada en ecuaciones polinómicas verificables. Diferentes protocolos PIOP permiten al probador enviar polinomios de forma incremental mediante la interacción con el verificador, de modo que el verificador puede validar si el cálculo es correcto consultando los resultados de la evaluación de unos pocos polinomios. Los protocolos PIOP existentes incluyen: PIOP PLONK, PIOP Spartan y PIOP HyperPlonk, que manejan 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 a través de la cual el probador puede comprometerse a un polinomio y verificar posteriormente el resultado de la evaluación de dicho polinomio, mientras oculta otra información del polinomio. Los esquemas de compromiso polinómico 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 una curva elíptica adecuada, se pueden construir sistemas 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 la eliminación del setup confiable en el protocolo ZCash.

• Plonky2: utiliza PLONK PIOP y FRI PCS combinados, y se basa en el dominio de Goldilocks. Plonky2 está diseñado para lograr recursión eficiente. Al diseñar estos sistemas, el PIOP y el PCS seleccionados deben coincidir con el campo finito o la curva elíptica utilizados, 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 del SNARK y la eficiencia de la verificación, sino que también determina si el sistema puede lograr transparencia sin necesidad de una configuración confiable, y si puede soportar funciones de extensión como pruebas recursivas o pruebas agregadas.

Binius: HyperPlonk PIOP + Brakedown PCS + dominios binarios. Específicamente, Binius incluye cinco tecnologías clave para lograr su eficiencia y seguridad. Primero, la aritmética basada en dominios binarios en torres (towers of binary fields) constituye la base de su computación, permitiendo realizar operaciones simplificadas en el dominio binario. En segundo lugar, Binius adapta la verificación de productos y permutaciones de HyperPlonk en su protocolo de prueba de Oracle interactivo (PIOP), asegurando una verificación consistente y eficiente 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 dominios. Cuarto, Binius utiliza una versión mejorada de la prueba de búsqueda Lasso, proporcionando flexibilidad y una fuerte seguridad al mecanismo de búsqueda. Finalmente, el protocolo emplea un esquema de compromiso polinómico de pequeños dominios (Small-Field PCS), permitiendo así un sistema de pruebas eficiente en el dominio binario y reduciendo los costos generalmente asociados con dominios grandes.

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

El campo binario en torre es clave para implementar cálculos verificables rápidos, principalmente debido a dos aspectos: cálculos eficientes y una aritmética eficiente. El campo binario, en esencia, soporta operaciones aritméticas altamente eficientes, lo que lo convierte en una opción ideal para aplicaciones criptográficas que son 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 sobre el campo binario pueden representarse en una forma algebraica compacta y fácil de verificar. Estas características, junto con la capacidad de aprovechar plenamente sus características jerárquicas a través de la estructura en torre, hacen que el campo binario sea especialmente adecuado para sistemas de prueba escalables como Binius.

Donde "canónico" se refiere a la representación única y directa de los elementos en el 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 tal representación canónica dentro de un número fijo de bits. Aunque el campo primo de 32 bits puede estar contenido en 32 bits, no todas las cadenas de 32 bits pueden corresponder de manera única a un elemento del 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 especiales de reducción 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 documento "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" señala que el campo binario no requiere llevar 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 de (X + Y )2 = X2 + Y2.

Como se muestra en la Figura 1, una cadena de 128 bits: esta cadena se puede interpretar de varias maneras en el contexto del campo binario. Puede considerarse como un elemento único en un campo binario de 128 bits, o puede descomponerse en dos elementos de campo de torre de 64 bits, cuatro elementos de campo de torre de 32 bits, dieciséis elementos de campo de torre de 8 bits, o 128 elementos de campo F2. Esta flexibilidad de representación no requiere ningún costo computacional, solo una conversión de tipo de la cadena de bits, lo que es una propiedad muy interesante y útil. Al mismo tiempo, los elementos de campo pequeños se pueden empaquetar en elementos de campo más grandes sin necesidad de costos computacionales adicionales. El protocolo Binius aprovecha 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 realizar multiplicación, elevación al cuadrado y operaciones de inversión en un campo binario de torre de n bits (que se puede descomponer en subcampos de m bits).

2.2 PIOP: versión adaptada de HyperPlonk Product y PermutationCheck------aplicable a campos binarios

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

1. GateCheck: Verifica si el testigo secreto ω y la entrada pública x satisfacen la relación de cálculo del circuito C(x,ω)=0, para asegurar que el circuito funcione correctamente.

2. PermutationCheck: Verifica si los resultados de evaluación de los 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 en 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, garantizando 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 polinómico.

6. ZeroCheck: Verificar si un polinomio multivariable en el hipercubo booleano en cualquier punto es cero ∏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 multivariable es igual al valor declarado ∑x∈Hµ f(x) = s. Al transformar el problema de evaluación de un polinomio multivariable en la evaluación de un polinomio univariable, se reduce la complejidad computacional para la parte verificada. 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 suma.

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 mejorado en las siguientes 3 áreas:

• Optimización de ProductCheck: En HyperPlonk, ProductCheck requiere que el denominador U sea no cero en todo el hipercubo, y que el producto sea igual a un valor específico; Binius simplifica este proceso de verificación al especializar este valor en 1, reduciendo así la complejidad computacional.

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

• Comprobación de Permutación entre columnas: HyperPlonk no tiene esta función; Binius admite la comprobación de permutación entre múltiples columnas, lo que permite a Binius manejar situaciones de permutación polinómica más complejas.

Por lo tanto, Binius ha mejorado la flexibilidad y eficiencia del protocolo mediante la mejora del mecanismo PIOPSumCheck existente, especialmente al manejar la verificación de polinomios multivariables más complejos, lo que proporciona un soporte funcional más robusto. Estas mejoras no solo abordan las limitaciones en HyperPlonk, sino que también establecen una base para futuros sistemas de prueba basados en dominios 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 es una de las tecnologías clave, que permite generar y operar de manera efectiva polinomios derivados de manejadores de entrada u otros polinomios virtuales. A continuación se presentan dos métodos clave:

• Empaquetado: Este método optimiza la operación empaquetando elementos más pequeños en posiciones adyacentes del orden del diccionario en elementos más grandes. El operador Pack se aplica a bloques de tamaño 2κ y los transforma.