Análisis del principio de Binius STARKs y su pensamiento de optimización

1 Introducción

A diferencia de los SNARK basados en curvas elípticas, los STARK se pueden considerar como SNARK basados en hash. Una de las principales razones de la ineficiencia actual de los STARK es que la mayoría de los valores del programa real son pequeños, como los índices en bucles for, los valores verdaderos y falsos, los contadores, etc. Sin embargo, para garantizar la seguridad de las pruebas basadas en árboles de Merkle, cuando los datos se amplían con la codificación Reed-Solomon, muchos valores redundantes adicionales ocupan todo el dominio, aunque los valores originales sean muy pequeños. Para resolver este problema, reducir el tamaño del dominio se convierte en una estrategia clave.

Como se muestra en la Tabla 1, los STARK de primera generación son de 252 bits, los STARK de segunda generación son de 64 bits y los STARK de tercera generación son de 32 bits. Por el contrario, el dominio binario permite operaciones directas de alineación de bits y es compacto y eficiente en la codificación sin desperdiciar espacio, es decir, STARK de 4ª generación.

Tabla 1: Vías de evolución de los STARK

| Característica | STARKs de primera generación | STARKs de segunda generación | STARKs de tercera generación | STARKs de cuarta generación(Binius) | |------|-------------|-------------|-------------|---------------------| | Ancho de bits de código | 252 bits | 64 bits | 32 bits | 1bit | | Sistema de Representación | StarkWare | Plonky2 | Osito | Binio |

En comparación con los dominios finitos descubiertos en los últimos años, como Goldilocks, BabyBear y Mersenne31, el estudio de los dominios binarios se remonta a los años 80 del siglo pasado. En la actualidad, los dominios binarios se han utilizado ampliamente en criptografía, los ejemplos típicos incluyen:

• Estándar de cifrado avanzado (AES), basado en dominios F28;

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

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

• Los protocolos FRI y zk-STARK originales, así como la función hash Grøstl que llegó al finalista SHA-3, que se basa en el dominio F28 y es un algoritmo de hash muy adecuado para la recursividad.

Cuando se utilizan dominios más pequeños, la expansión de las operaciones de dominio se vuelve cada vez más importante para garantizar la seguridad. El dominio binario utilizado por Binius, por otro lado, debe depender completamente de la expansión del dominio para garantizar su seguridad y disponibilidad real. La mayoría de los polinomios involucrados en los cálculos de Prover no necesitan ingresar al dominio expandido, sino que solo necesitan operar bajo el dominio base, logrando así una alta eficiencia en dominios pequeños. Sin embargo, las comprobaciones de puntos aleatorios y los cálculos de FRI aún deben perforarse en un área de expansión más grande para garantizar la seguridad requerida.

Al construir un sistema de prueba basado en dominios binarios, existen dos problemas prácticos: al calcular la representación de trazas en STARKs, el tamaño del dominio utilizado debe ser mayor que el orden del polinomio; Cuando se promete el árbol de Merkle en STARK, debe codificarse en Reed-Solomon y el tamaño del dominio utilizado debe ser mayor que el tamaño de la extensión de codificación.

Binius propone una solución innovadora que aborda estos dos problemas por separado y lo hace representando los mismos datos de dos maneras diferentes: primero, utilizando polinomios multivariados (específicamente, multilineales) en lugar de polinomios univariados, y representando toda la trayectoria computacional por su valor en los "hipercubos"; En segundo lugar, dado que la longitud de cada dimensión del hipercubo es 2, no es posible hacer la extensión estándar de Reed-Solomon como los STARK, pero el hipercubo se puede tratar como un cuadrado basado en la extensión de Reed-Solomon. Este método mejora en gran medida la eficiencia de la codificación y el rendimiento informático, al tiempo que garantiza la seguridad.

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 polinomial teórico de la información (PIOP) :P IOP como núcleo del sistema de prueba, transformando las relaciones computacionales de las entradas en ecuaciones polinómicas verificables. Diferentes protocolos PIOP permiten al probador enviar polinomios paso a paso interactuando con el validador, lo que permite al validador verificar que el cálculo es correcto consultando los resultados de la evaluación de un pequeño número de polinomios. Los protocolos PIOP existentes incluyen PLONK PIOP, Spartan PIOP e HyperPlonk PIOP, todos los cuales manejan expresiones polinómicas de manera diferente, 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 demostrar si la ecuación polinómica generada por PIOP es verdadera. PCS es una herramienta criptográfica a través de la cual un probador puede comprometerse con un determinado polinomio y luego verificar los resultados de la evaluación de ese polinomio, mientras oculta otra información sobre el polinomio. Los esquemas de compromiso polinómico comunes incluyen KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) y Brakedown. Los diferentes PCS tienen diferentes escenarios de rendimiento, seguridad y aplicación.

De acuerdo con los requisitos específicos, se pueden seleccionar diferentes PIOP y PCS, y combinados con campos finitos adecuados o curvas elípticas, se pueden construir sistemas de prueba con diferentes propiedades. Por ejemplo:

• Halo2: Desarrollado por PLONK PIOP combinado con Bulletproofs PCS y basado en curvas de pasta. Halo2 se diseñó teniendo en cuenta la escalabilidad, además de eliminar la configuración de confianza del protocolo ZCash.

• Plonky2: Combina PLONK PIOP con FRI PCS y se basa en el dominio Ricitos de Oro. Plonky2 es para una recursividad eficiente. Al diseñar estos sistemas, el PIOP y el PCS seleccionados deben coincidir con el dominio 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 al tamaño de la prueba y a la eficiencia de la verificación de los SNARK, sino que también determina si el sistema puede lograr la transparencia sin necesidad de configuraciones de confianza, y si puede admitir funciones ampliadas, como pruebas recursivas o pruebas agregadas.

Binius: HyperPlonk PIOP + Brakedown PCS + Dominio binario. En concreto, Binius incluye cinco tecnologías clave para lograr su eficiencia y seguridad. En primer lugar, la aritmética basada en las torres de campos binarios forma la base de sus cálculos, que pueden realizar operaciones simplificadas en los campos binarios. En segundo lugar, en su protocolo interactivo Oracle Proof Protocol (PIOP), Binius adaptó el producto HyperPlonk y la comprobación de permutaciones para garantizar una comprobación de coherencia segura y eficiente entre las variables y sus permutaciones. En tercer lugar, el protocolo introduce un nuevo argumento de desplazamiento multilineal para optimizar la eficiencia de la verificación de la relación multilineal en un dominio pequeño. En cuarto lugar, Binius adopta una versión mejorada del argumento de búsqueda Lasso, que proporciona flexibilidad y una gran seguridad para el mecanismo de búsqueda. Por último, el protocolo utiliza un esquema de compromiso polinómico de campo pequeño (PCS de campo pequeño), lo que le permite implementar un sistema de prueba eficiente en el dominio binario y reducir la sobrecarga típicamente asociada con dominios grandes.

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

El dominio binario de la torre es la clave para una computación rápida y verificable, que se atribuye principalmente a dos aspectos: la computación eficiente y la aritmética eficiente. Los dominios binarios admiten inherentemente operaciones aritméticas altamente eficientes, lo que los hace ideales para aplicaciones de criptografía que son sensibles a los requisitos de rendimiento. Además, la estructura del dominio binario admite un proceso aritmético simplificado, es decir, las operaciones realizadas en el dominio binario se pueden representar en una forma algebraica compacta y fácilmente verificable. Estas características, combinadas con la capacidad de aprovechar al máximo su naturaleza jerárquica a través de estructuras de torre, hacen que el dominio binario sea particularmente adecuado para sistemas de prueba escalables como Binius

donde "canónico" se refiere a una representación única y directa de un elemento en el dominio binario. Por ejemplo, en el dominio binario más básico F2, cualquier cadena de k bits se puede asignar directamente a un elemento de dominio binario de k bits. Esto contrasta con el campo de números primos, que no puede proporcionar tal representación canónica dentro de la posición dada. Aunque un campo de número primo de 32 bits puede estar contenido en un sistema de 32 bits, no todas las cadenas de 32 bits corresponden de forma única a un elemento de dominio, y los campos binarios tienen la comodidad de esta asignación uno a uno. En el dominio primario 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 Ricitos de Oro-64. En el dominio binario F2k, los métodos de reducción comúnmente utilizados incluyen la reducción especial (por ejemplo, utilizada en AES), la reducción de Montgomery (por ejemplo, utilizada en POLYVAL) y la reducción recursiva (por ejemplo, Tower). El artículo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" señala que el dominio binario no necesita introducir carry tanto en la suma como en la multiplicación, y que la operación al cuadrado del dominio binario es muy eficiente porque sigue (X + Y )2 = X2 + Y 2.

! Bitlayer Research: Pensamiento de optimización y análisis de principios de Binius STARKs

Como se muestra en la Figura 1, una cadena de 128 bits: esta cadena se puede interpretar de varias maneras en el contexto del dominio binario. Se puede ver como un elemento único en un dominio binario de 128 bits, o se puede resolver como dos elementos de torre de 64 bits, cuatro elementos de torre de 32 bits, 16 elementos de torre de 8 bits o 128 elementos de dominio F2. La flexibilidad de esta representación no requiere ninguna sobrecarga computacional, solo un encasillamiento de cadenas bit a bit, que es una propiedad muy interesante y útil. Al mismo tiempo, los elementos de dominio pequeños se pueden empaquetar en elementos de dominio más grandes sin sobrecarga 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, cuadratura e inversión en un dominio binario de torre de n bits que se puede descomponer en subdominios de m bits.

2.2 PIOP: versión adaptada de HyperPlonk Product y PermutationCheck ------ aplicable a campo binario

El diseño PIOP en el protocolo Binius toma prestado de HyperPlonk y emplea una serie de mecanismos de verificación básicos para verificar la corrección de polinomios y conjuntos multivariados. Estas pruebas básicas incluyen:

1. GateCheck: Verifique si el testigo confidencial ω y la entrada pública x satisfacen la relación de operación del circuito C(x, ω)=0 para garantizar el correcto funcionamiento del circuito.

2. PermutationCheck: Verifique que los resultados de la evaluación de los dos polinomios multivariados f y g en el hipercubo booleano sean relaciones de permutación f(x) = f(π(x)) para asegurar la consistencia en la disposición entre las variables polinómicas.

3. LookupCheck: Verifique que el polinomio se evalúe en una tabla de búsqueda determinada, es decir, f(Bμ) ⊆ T(Bμ), asegurándose de que ciertos valores estén dentro del rango especificado.

4. MultisetCheck: Comprueba si los dos conjuntos multivariantes son iguales, es decir, {(x1,i,x2,)}i∈H={0192837465574839201y1,i,y2,(}i∈H para garantizar la coherencia entre varios conjuntos.

5. ProductCheck: Comprueba si la evaluación de un polinomio racional en un hipercubo booleano es igual a un valor declarado ∏x∈Hμ f)x( = s para garantizar la corrección del producto polinómico.

6. ZeroCheck: Verifique que un polinomio multivariante sea cero en cualquier punto del hipercubo booleano∏x∈Hμ f)x( = 0,∀x ∈ Bμ para garantizar la distribución cero del polinomio.

7. SumCheck: Comprueba si el valor de la suma del polinomio multivariante es el valor declarado ∑x∈Hμ f)x( = s. Al transformar el problema de evaluación de polinomios multivariados en evaluación de polinomios univariantes, se reduce la complejidad computacional del verificador. Además, SumCheck también permite el procesamiento por lotes, mediante la introducción de números aleatorios, la construcción de combinaciones lineales para lograr el procesamiento por lotes de múltiples instancias de verificación de suma.

8. BatchCheck: Basado en SumCheck, verifique la exactitud de múltiples evaluaciones polinómicas multivariantes para mejorar la eficiencia del protocolo.

Aunque hay muchas similitudes entre Binius e HyperPlonk en términos de diseño de protocolo, Binius ha realizado mejoras en los siguientes tres aspectos:

• Optimización de ProductCheck: En HyperPlonk, ProductCheck requiere que el denominador U sea distinto de cero en todas partes del hipercubo, y el producto debe ser igual a un valor específico; Binius simplifica este proceso de comprobación especializando este valor a 1, reduciendo así la complejidad computacional.

• Manejo del problema de dividir cero: HyperPlonk no logra manejar adecuadamente el caso de división cero, lo que resulta en la incapacidad de afirmar el problema distinto de cero de U en el hipercubo; Binius maneja esto correctamente, y ProductCheck de Binius continúa procesando incluso cuando el denominador es cero, lo que permite generalizaciones a valores de producto arbitrarios.

• PermutationCheck: Esta función no está disponible en HyperPlonk; Binius admite PermutationCheck entre varias columnas, lo que permite a Binius manejar permutaciones polinómicas más complejas.

Por lo tanto, a través de la mejora del mecanismo PIOPSumCheck existente, Binius mejora la flexibilidad y la eficiencia del protocolo, especialmente cuando se trata de una verificación polinómica multivariante más compleja, y proporciona un soporte funcional más fuerte. Estas mejoras no solo abordan las limitaciones de HyperPlonk, sino que también proporcionan una base binaria para el futuro