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 los STARKs es que la mayoría de los valores numéricos en los programas reales son relativamente pequeños. Sin embargo, para garantizar la seguridad de las pruebas basadas en el árbol de Merkle, al utilizar la codificación de Reed-Solomon para extender los datos, muchos valores redundantes adicionales ocuparán todo el dominio, incluso si el valor original es muy pequeño. Para abordar este problema, reducir el tamaño del dominio se convierte 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, la de la tercera generación es de 32 bits, pero la codificación de 32 bits todavía presenta un gran desperdicio de espacio. En comparación, el campo binario permite operar directamente sobre los bits, con una codificación compacta y eficiente sin ningún desperdicio de espacio, es decir, la cuarta generación de STARKs.

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

• Estándar de cifrado avanzado ( AES ), basado en el campo F28
• Código de autenticación de mensajes Galois ( GMAC ), basado en el campo 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, y que se basa en el campo F28, es un algoritmo hash muy adecuado para la recursión.

Al utilizar dominios más pequeños, la operación de extensión de dominios se vuelve cada vez más importante para garantizar la seguridad. El dominio binario utilizado por Binius depende completamente de la extensión de dominios para asegurar 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 dominios, sino que solo requieren operar en el dominio base, logrando así alta eficiencia en dominios pequeños. Sin embargo, la verificación de puntos aleatorios y el cálculo de FRI aún deben profundizarse en una extensión de dominios más grande para garantizar la seguridad requerida.

Al construir un sistema de pruebas basado en el campo binario, existen 2 problemas prácticos: al calcular la representación de la traza en STARKs, el tamaño del campo 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 campo 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 ( 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 cada dimensión del hipercubo tiene una longitud de 2, no se puede realizar una expansión estándar de Reed-Solomon como en el caso de STARKs, pero se puede considerar el hipercubo como un cuadrado ( y realizar la expansión de Reed-Solomon basada en ese cuadrado. Este método, al asegurar 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 actualmente generalmente incluye las siguientes dos partes:

• Prueba de Oracle Interactiva Polinómica Teórica 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 igualdades polinómicas verificables. Diferentes protocolos PIOP permiten al probador enviar polinomios de manera gradual a través de la interacción con el validador, de modo que el validador puede 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: PLONK PIOP, Spartan PIOP y HyperPlonk PIOP, cada uno con diferentes enfoques para el tratamiento de expresiones polinómicas, lo que afecta el rendimiento y la eficiencia de todo el sistema SNARK.

• Esquema de Compromiso Polinómico ), PCS (: El esquema de compromiso polinómico se utiliza para probar si la igualdad polinómica generada por PIOP es válida. El PCS es una herramienta criptográfica que permite al demostrador comprometerse a un polinomio y validar 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 ), IOPP de Reed-Solomon Rápido ( y Brakedown, entre otros. Diferentes PCS tienen diferentes desempeños, niveles de seguridad y escenarios de aplicación.

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

• Halo2: combinado con PLONK PIOP y Bulletproofs PCS, basado en la curva Pasta. Halo2 se diseñó con un enfoque en la escalabilidad y en eliminar el trusted setup del 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, el PIOP y PCS elegidos 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. Específicamente, 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 su cálculo, permitiendo realizar operaciones simplificadas dentro del campo binario. En segundo lugar, Binius, en su protocolo de prueba de Oracle interactiva )PIOP(, adapta las verificaciones de producto y permutación de HyperPlonk, asegurando una verificación de consistencia segura y eficiente entre las variables y sus permutaciones. Tercero, el protocolo introduce una nueva prueba de desplazamiento multilineal, optimizando la eficiencia en la verificación de relaciones multilineales en campos 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 permite implementar un sistema de prueba eficiente en el campo binario, reduciendo los costos generalmente asociados 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, en esencia, soportan operaciones aritméticas altamente eficientes, lo que los convierte en una elección ideal para aplicaciones criptográficas que son sensibles al 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 su naturaleza jerárquica a través de la estructura de torre, hacen que los campos binarios sean especialmente 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 puede ser mapeada directamente a un elemento de campo binario de k bits. Esto es diferente del campo primo, que no puede proporcionar tal representación canónica dentro de un número fijo de bits. Aunque un campo primo de 32 bits puede caber dentro de 32 bits, no cada cadena de 32 bits puede corresponder de manera única a un elemento del campo, mientras que el campo binario tiene esta conveniencia de un 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, las operaciones de suma y multiplicación no requieren llevar, y la operación de cuadrado del 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 interpretarse de varias maneras en el contexto de un dominio binario. Puede considerarse como un elemento único en un dominio binario de 128 bits, o puede interpretarse como dos elementos de dominio de torre de 64 bits, cuatro elementos de dominio de torre de 32 bits, 16 elementos de dominio de torre de 8 bits, o 128 elementos de dominio F2. Esta flexibilidad de representación no requiere ningún costo computacional, 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 dominio pequeños pueden empaquetarse en elementos de dominio 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 multiplicaciones, elevaciones al cuadrado y operaciones de inversión en un dominio binario de torre de n bits ) descomponiéndolo en un subdominio de m bits (.

![Bitlayer Research: Análisis de los principios 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 dominio binario

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

1. GateCheck: Verifica si el testigo privado ω 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: 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 las permutaciones entre 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, 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: Verificar si un polinomio multivariable 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 multivariable es igual al valor declarado ∑x∈Hµ f)x( = s. Al transformar el problema de evaluación de polinomios multivariables en la evaluación de un polinomio univariable, 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 realizado mejoras 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 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, incluso en el caso de que el denominador sea cero, el ProductCheck de Binius puede continuar procesándose, permitiendo la promoció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 permutaciones 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 tratar con la verificación de polinomios multivariables más complejos, proporcionando un soporte funcional más fuerte. Estas mejoras no solo abordan las limitaciones en HyperPlonk, sino que también sientan las bases para futuros sistemas de pruebas basados en campos binarios.

![Bitlayer Research: Análisis de los principios de Binius STARKs y reflexiones sobre su optimización])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(

) 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 son una de las tecnologías clave, que pueden generar y operar de manera efectiva polinomios derivados de un manejador de entrada u otros polinomios virtuales. A continuación, se presentan dos métodos clave:

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