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

1 Introducción

Una de las principales razones de la ineficiencia de STARKs es que la mayoría de los valores en los programas reales son relativamente pequeños, como los índices en los bucles for, los valores booleanos, los contadores, etc. Sin embargo, para garantizar la seguridad de las pruebas basadas en árboles de Merkle, cuando se utiliza la 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 primera generación de STARKs tiene un ancho de codificación de 252 bits, la segunda generación tiene un ancho de codificación de 64 bits, y la tercera generación tiene un ancho de codificación de 32 bits, pero el ancho de codificación de 32 bits aún presenta una gran cantidad de espacio desperdiciado. En comparación, el dominio binario permite operar directamente sobre los bits, con una codificación compacta y eficiente sin ningún 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 cifrado avanzado ( AES ), basado en el dominio F28;

• Código de autenticación de mensajes Galois ( GMAC ), basado en el campo 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, basada en el dominio 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. Y el dominio binario utilizado por Binius depende completamente de la extensión de dominio para asegurar su seguridad y usabilidad 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 un dominio pequeño. Sin embargo, la verificación de puntos aleatorios y el cálculo 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 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 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 "hipercubos"; 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 los STARKs, pero se puede considerar el hipercubo como un cuadrado, basando la extensión de Reed-Solomon en ese cuadrado. 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 Oráculo Interactivo Polinómico con Teoría de la Información (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, como núcleo del sistema de prueba, transforma las relaciones computacionales de entrada en ecuaciones polinómicas verificables. Diferentes protocolos PIOP permiten que el probador envíe polinomios de manera gradual a través de la interacción con el validador, de modo que el validador pueda verificar si el cálculo es correcto consultando los resultados de la evaluación de un número reducido de polinomios. Los protocolos PIOP existentes incluyen: PIOP PLONK, PIOP Spartan y PIOP HyperPlonk, que tienen diferentes enfoques para el tratamiento de expresiones polinómicas, afectando así 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 demostrar si se cumple la igualdad polinómica generada por PIOP. PCS es una herramienta criptográfica que permite al demostrador comprometerse a un polinomio y verificar más tarde 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 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 pueden construir sistemas de prueba con diferentes atributos. Por ejemplo:

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

• Plonky2: utiliza PLONK PIOP combinado con FRI PCS y se basa en el dominio de Goldilocks. Plonky2 está diseñado para lograr una 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 SNARK y la eficiencia de la verificación, sino que también determina si el sistema puede lograr la transparencia sin 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. En concreto, Binius incluye cinco tecnologías clave para lograr su eficiencia y seguridad. En primer lugar, la aritmética basada en torres de dominios binarios constituye la base de sus cálculos, permitiendo realizar operaciones simplificadas dentro de los dominios binarios. En segundo lugar, Binius ha adaptado la verificación de productos y permutaciones de HyperPlonk en su protocolo de prueba de Oracle interactivo (PIOP), 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. En cuarto lugar, Binius utiliza una versión mejorada de la prueba de búsqueda Lasso, que proporciona flexibilidad y una fuerte seguridad al mecanismo de búsqueda. Por último, el protocolo utiliza un esquema de compromiso polinómico de campo pequeño (Small-Field PCS), lo que le permite implementar un sistema de prueba eficiente en dominios binarios y reduce los gastos asociados normalmente con dominios grandes.

2.1 Campos finitos: aritmética basada en torres de campos binarios

El campo binario en torre es clave para la implementación de cálculos verificables rápidos, principalmente debido a dos aspectos: cálculo eficiente y aritmética eficiente. El campo binario, en esencia, admite operaciones aritméticas de alta eficiencia, lo que lo convierte en una elección ideal para aplicaciones criptográficas sensibles a los requisitos de rendimiento. Además, la estructura del campo binario admite procesos de aritmética simplificados, 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 completamente sus características jerárquicas a través de la estructura de 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 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 un campo primo, que no puede proporcionar esta representación canónica dentro de un número específico de bits. Aunque un 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 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 la utilizada en AES), la reducción de Montgomery (como la utilizada 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 adición 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 + Y 2.

Como se muestra en la figura 1, una cadena de 128 bits: esta cadena puede interpretarse de varias maneras en el contexto de campos binarios. Puede considerarse como un elemento único en un campo binario de 128 bits, o puede desglosarse 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 un cambio de tipo (typecast) de la cadena de bits, lo que 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 un costo computacional adicional. 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 las operaciones de multiplicación, cuadrado e inversión en campos de torre binarios de n bits (que se pueden descomponer en subcampos de m bits).

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 inspira en HyperPlonk y utiliza una serie de mecanismos de verificación centrales para validar la corrección de polinomios y conjuntos multivariables. Estas verificaciones centrales 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 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, garantizando la consistencia entre múltiples conjuntos.

5. ProductCheck: Verificar 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: Verifica si un polinomio multivariable en un 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: Detecta si la suma de un polinomio multivariable es igual al valor declarado ∑x∈Hµ f(x) = s. Reduce la complejidad computacional para la parte de verificación al transformar el problema de evaluación de polinomios multivariables en evaluación de un polinomio univariable. Además, SumCheck permite el procesamiento por lotes, introduciendo números aleatorios para construir combinaciones lineales que logran 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 realizado mejoras en los siguientes 3 aspectos:

• Optimización de ProductCheck: En HyperPlonk, ProductCheck requiere que el denominador U sea no cero en todo el hipercubo, 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 computacional.

• Manejo del problema de la división por cero: HyperPlonk no pudo manejar adecuadamente la situación 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 en el caso de que el denominador sea cero, el ProductCheck de Binius puede seguir procesándose, permitiendo la generalización a cualquier valor del producto.

• Comprobación de Permutación 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 permutación polinómica más complejas.

Por lo tanto, Binius ha mejorado la flexibilidad y eficiencia del protocolo a través de la mejora del mecanismo existente PIOPSumCheck, especialmente al proporcionar un soporte funcional más fuerte al manejar la verificación de polinomios multivariables más complejos. 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 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 los polinomios derivados de un manejador 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 de orden léxico en elementos más grandes. El operador Pack se aplica a bloques de tamaño 2κ y los agrupa.