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 numéricos en los programas reales son bastante pequeños, pero para garantizar la seguridad de las pruebas basadas en árboles de Merkle, al usar codificación de Reed-Solomon para expandir los datos, muchos valores redundantes adicionales ocupan todo el campo, incluso si el valor original en sí es muy pequeño. Para abordar este problema, reducir el tamaño del campo se ha convertido en una estrategia clave.

La anchura de codificación de la primera generación de STARKs es de 252 bits, la de la segunda generación es de 64 bits y la de la tercera generación es de 32 bits, pero la codificación de 32 bits aún presenta una gran cantidad de espacio desperdiciado. En comparación, el campo binario permite operar directamente sobre los bits, codificando de manera compacta y eficiente sin espacio desperdiciado, es decir, la cuarta generación de STARKs.

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

• Estándar de Encriptación Avanzada ( AES ), basado en el dominio F28;

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

• Código QR, utiliza 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, basada en el campo F28, es un algoritmo hash muy adecuado para la recursividad.

Cuando se utilizan campos más pequeños, la operación de extensión de campo se vuelve cada vez más importante para garantizar la seguridad. El campo binario utilizado por Binius depende completamente de la extensión de campo 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 campo y solo operan en el campo base, logrando así alta eficiencia en campos pequeños. Sin embargo, la verificación de puntos aleatorios y el cálculo FRI aún deben profundizar en un campo de extensión más grande para garantizar la seguridad necesaria.

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, se necesita realizar la codificación de Reed-Solomon, y el tamaño del dominio debe ser mayor que el tamaño después de la expansión de la codificación.

Binius ha propuesto una solución innovadora que aborda estos dos problemas de manera separada y representa 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 "hipercubos" (hypercubes); en segundo lugar, dado que la longitud de cada dimensión del hipercubo es 2, no se puede realizar una extensión estándar de Reed-Solomon como en STARKs, pero se puede considerar el hipercubo como un cuadrado (square) y realizar la extensión de Reed-Solomon basada en ese cuadrado. Este método, al garantizar la seguridad, mejora significativamente 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 de los sistemas de prueba, transforma las relaciones computacionales de entrada en ecuaciones polinómicas verificables. Diferentes protocolos PIOP permiten que el demostrador envíe polinomios de manera gradual a través de la interacción con el validador, permitiendo que el validador verifique si el cálculo es correcto consultando solo unos pocos resultados de evaluación de polinomios. Los protocolos PIOP existentes incluyen: PIOP PLONK, PIOP Spartan y PIOP HyperPlonk, cada uno de los cuales tiene un enfoque diferente para el tratamiento de expresiones polinómicas, lo que afecta el rendimiento y la eficiencia del sistema SNARK en su conjunto.

• 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 luego verificar el resultado de la evaluación de dicho polinomio, ocultando al mismo tiempo 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, niveles de seguridad y escenarios de aplicación.

Según las necesidades específicas, elige diferentes PIOP y PCS, y combina con un campo finito adecuado o una curva elíptica, se puede construir un sistema de pruebas con diferentes atributos. Por ejemplo:

• Halo2: combina PLONK PIOP y Bulletproofs PCS, y se basa en la curva Pasta. Al diseñar Halo2, se pone énfasis en la escalabilidad y en eliminar la configuración de confianza en el protocolo ZCash.

• Plonky2: combina PLONK PIOP con FRI PCS y se basa en el dominio Goldilocks. Plonky2 está diseñado para lograr recursividad eficiente. Al diseñar estos sistemas, la PIOP y PCS elegidas 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 SNARK y la eficiencia de la verificación, sino que también determina si el sistema puede lograr transparencia sin una configuración confiable y si puede soportar funciones extendidas como pruebas recursivas o pruebas de agregación.

Binius: HyperPlonk PIOP + Brakedown PCS + domini binarios. En concreto, Binius incluye cinco tecnologías clave para lograr su eficiencia y seguridad. Primero, la aritmética basada en torres de dominios binarios constituye la base de sus cálculos, permitiendo realizar operaciones simplificadas dentro del dominio binario. En segundo lugar, Binius en su protocolo de prueba de Oracle interactivo (PIOP) ha adaptado la verificación de producto y permutación de HyperPlonk, asegurando una verificación de consistencia segura y eficiente entre las variables y sus permutaciones. En tercer lugar, el protocolo introduce una nueva prueba de desplazamiento multilineal, optimizando la eficiencia de la verificación de relaciones multilineales en dominios pequeños. 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 campo pequeño (Small-Field PCS), lo que le permite implementar un sistema de prueba eficiente en el dominio binario y reduce los costos normalmente asociados con dominios 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álculos eficientes y aritmética eficiente. Los campos binarios, en esencia, soportan 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 soporta un proceso de aritmética simplificada, 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 de torre, hacen que los campos binarios sean particularmente adecuados para sistemas de prueba escalables como Binius.

"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 puede mapearse 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 ser 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 reducción de Barrett, 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 comúnmente utilizados incluyen reducción especial (como se utiliza en AES), reducción de Montgomery (como se utiliza en POLYVAL) y 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 porque 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 interpretarse de diversas maneras en el contexto del 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 ningún costo computacional, solo una conversión de tipo (typecast) de la cadena de bits, lo cual es una propiedad muy interesante y útil. Al mismo tiempo, los elementos de campo pequeños pueden empaquetarse en elementos de campo más grandes sin necesidad de costo computacional adicional. El protocolo Binius se aprovecha de esta característica para mejorar la eficiencia computacional. Además, el documento "On Efficient Inversion in Tower Fields of Characteristic Two" explora la complejidad computacional de las operaciones de multiplicación, elevación al cuadrado y cálculo de inversos en campos de torre binarios de n bits (que pueden descomponerse en subcampos de m bits).

2.2 PIOP: versión adaptada del Producto HyperPlonk y PermutationCheck------aplicable a dominios 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: Verificar 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: Verificar si los resultados de evaluación de los dos polinomios multivariables f y g en el hipercubo booleano representan una relación de permutación f(x) = f(π(x)), para asegurar la consistencia en el orden de las variables del polinomio.

3. LookupCheck: Verificar 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 garantizar la corrección del producto polinómico.

6. ZeroCheck: Verificar si un polinomio multivariable es cero en cualquier punto del hipercubo booleano ∏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 polinomios multivariables en un problema de evaluación de polinomios univariables, se reduce la complejidad computacional para la parte de verificación. Además, SumCheck también permite el procesamiento por lotes al introducir números aleatorios, construyendo combinaciones lineales para implementar 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 los siguientes 3 aspectos:

• Optimización de ProductCheck: en HyperPlonk, ProductCheck requiere que el denominador U sea diferente de 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 dicho valor a 1, reduciendo así la complejidad computacional.

• Manejo del problema de división por cero: HyperPlonk no pudo manejar adecuadamente los casos 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, ya que incluso en el caso de que el denominador sea cero, el ProductCheck de Binius puede continuar procesándose, 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 disposición polinómica más complejas.

Por lo tanto, Binius ha mejorado la flexibilidad y eficiencia del protocolo mediante la mejora del mecanismo existente PIOPSumCheck, especialmente al proporcionar un soporte funcional más robusto para el manejo de verificaciones de polinomios multivariables más complejas. Estas mejoras no solo abordan las limitaciones en HyperPlonk, sino que también sientan las bases para futuros sistemas de prueba basados en dominios binarios.

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

En el protocolo Binius, la construcción y el manejo de polinomios virtuales es una de las tecnologías clave, capaz de 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:

• Packing: Este método utiliza elementos más pequeños en posiciones adyacentes en el orden del diccionario.