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

1 Introducción

A diferencia de los SNARKs basados en curvas elípticas, los STARKs pueden considerarse como SNARKs basados en hash. Una de las principales razones de la ineficiencia actual de los STARKs es: la mayoría de los valores numéricos 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 expandir los datos, muchos valores de redundancia adicionales ocuparán todo el campo, incluso si el valor original es muy pequeño. Para resolver 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 anchura de codificación de la segunda generación de STARKs es de 64 bits, y la anchura de codificación de la tercera generación de STARKs es de 32 bits, pero la codificación de 32 bits aún presenta un gran desperdicio de espacio. En comparación, el dominio binario permite operar directamente sobre los bits, con una codificación compacta y eficiente sin desperdicio de espacio, es decir, la cuarta generación de STARKs.

En comparación con los dominios finitos descubiertos en investigaciones recientes como Goldilocks, BabyBear y Mersenne31, la investigación sobre dominios binarios se remonta a la década de 1980. Actualmente, los dominios binarios se aplican ampliamente en criptografía, 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, 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, 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 del Prover no necesitan entrar en la extensión de dominio, sino que solo operan bajo el dominio base, logrando así una alta eficiencia en dominios pequeños. Sin embargo, las verificaciones de puntos aleatorios y los cálculos de FRI aún necesitan profundizar en un dominio de extensión más grande para garantizar la seguridad requerida.

Al construir sistemas de prueba basados en dominios binarios, existen 2 problemas prácticos: al calcular la representación del rastro 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 de manera separada y representa los mismos datos de dos formas diferentes: primero, utilizando un polinomio multivariable ( 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 cada dimensión del hipercubo tiene una longitud de 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 (, sobre el cual se realiza la extensión de Reed-Solomon. Este método, al garantizar la seguridad, mejora enormemente la eficiencia de la 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 Basada en Teoría de la Información )Information-Theoretic Polynomial Interactive Oracle Proof, PIOP(: PIOP, como el núcleo del sistema de prueba, transforma las relaciones computacionales de entrada en ecuaciones polinómicas verificables. Diferentes protocolos de PIOP permiten que el probador envíe polinomios de manera incremental a través de la interacción con el verificador, de modo que el verificador pueda validar si el cálculo es correcto consultando únicamente los resultados de evaluación de un número reducido de polinomios. Los protocolos de PIOP existentes incluyen: PIOP PLONK, PIOP Spartan y PIOP HyperPlonk, cada uno de los cuales maneja 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 una igualdad polinómica generada por PIOP es válida. 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, 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 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 enfoca 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 de Goldilocks. Plonky2 está diseñado para lograr una recursión 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 necesidad de una configuración confiable y si puede soportar funciones extensibles como pruebas recursivas o pruebas agregadas.

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, lo que permite realizar operaciones simplificadas en el campo 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, segura 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 campos pequeños. Cuarto, 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. 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 campo binario y reduce la sobrecarga normalmente asociada 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álculos eficientes y aritmética eficiente. Los campos binarios esencialmente soportan operaciones aritméticas altamente eficientes, lo que los 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 soporta 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 completamente 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.

Donde "canónico" se refiere a la representación única y directa de un elemento 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, donde no se puede proporcionar esta representación canónica dentro de un número fijo de bits. Aunque el campo primo de 32 bits puede contenerse 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 la conveniencia de este 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, así como 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 ( utilizada en AES ), la reducción de Montgomery ### utilizada en POLYVAL ( y la reducción recursiva ) utilizada en Tower (. El artículo "Explorando el espacio de diseño de implementaciones de ECC de Campo Primo vs. Campo Binario" 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 + Y2.

Como se muestra en la Figura 1, una cadena de 128 bits: esta cadena puede interpretarse de varias maneras en el contexto de un campo binario. Puede considerarse 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 del campo F2. Esta flexibilidad en la representación no requiere ningún costo computacional, solo una conversión de tipo de cadena de bits )typecast(, 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 multiplicación, cuadratura y operaciones de inversión en campos de torre binaria de n bits ) descomponiéndose en subcampos de m bits (.

![Investigación de Bitlayer: Análisis del principio de Binius STARKs y reflexiones sobre su optimización])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(

) 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 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 operación 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 en la permutación de 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: Comprobar 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 del polinomio.

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 multivariado en un problema de evaluación de un polinomio univariado, 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 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 no nulo 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 a 1, reduciendo así la complejidad de cálculo.

• Manejo del problema de división por cero: HyperPlonk no logró 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 en el caso de que el denominador sea cero, el ProductCheck de Binius puede continuar procesando, permitiendo la generalización a cualquier valor de producto.

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

Por lo tanto, Binius ha mejorado el mecanismo existente 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 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, 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:

• Empaque: Este método utiliza las posiciones adyacentes más pequeñas en el orden del diccionario