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 en los programas reales son pequeños, como los índices en bucles for, valores booleanos, contadores, etc. Sin embargo, para garantizar la seguridad de las pruebas basadas en árboles de Merkle, al usar la codificación de Reed-Solomon para expandir los datos, muchos valores redundantes 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 primera generación de STARKs tiene un ancho de codificación de 252 bits, la segunda generación de STARKs tiene un ancho de codificación de 64 bits, y la tercera generación de STARKs 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 campo binario permite operar directamente sobre los bits, con codificación compacta y eficiente sin espacio desperdiciado, es decir, la cuarta generación de STARKs.

En comparación con los campos finitos descubiertos en investigaciones recientes como Goldilocks, BabyBear y Mersenne31, 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 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, que está basada 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 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 dominio, sino que operan solo en el campo base, logrando así alta eficiencia en dominios pequeños. Sin embargo, las verificaciones de puntos aleatorios y los cálculos FRI aún deben profundizar en una extensión de dominio más grande para garantizar la seguridad requerida.

Al construir un sistema de prueba basado en un 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; en el compromiso del á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 ambos problemas y representa los mismos datos de dos maneras diferentes: primero, utilizando un polinomio multivariado ( que es un polinomio multilineal ) en lugar de un polinomio univariado, 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 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 Oracle Interactiva Polinómica de Teoría de la Información ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP ): PIOP, como núcleo del sistema de pruebas, transforma las relaciones computacionales de entrada en ecuaciones polinómicas verificables. Diferentes protocolos PIOP permiten que el probador envíe polinomios progresivamente a través de la interacción con el validador, de manera que el validador pueda verificar si el cálculo es correcto consultando los resultados de la evaluación de unos pocos polinomios. Los protocolos PIOP existentes incluyen: PLONK PIOP, Spartan PIOP y HyperPlonk PIOP, cada uno de los cuales tiene un enfoque diferente para el manejo 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, 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, 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 o curva elíptica adecuada, se puede construir un sistema de prueba con diferentes atributos. Por ejemplo:

• Halo2: combina PLONK PIOP y Bulletproofs PCS, basado en la curva Pasta. Halo2 fue diseñado con un enfoque en la escalabilidad y en eliminar la configuración de confianza 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 recursividad eficiente. Al diseñar estos sistemas, la elección de PIOP y PCS debe coincidir con el campo finito o la curva elíptica utilizada para garantizar la corrección, el rendimiento y la seguridad del sistema. Esta elección de combinaciones no solo afecta el tamaño de la prueba de SNARK y la eficiencia de la verificación, sino que también determina si el sistema puede lograr transparencia sin necesidad de un entorno de confianza, y si puede soportar funciones de extensión como pruebas recursivas o pruebas agregadas.

Binius: HyperPlonk PIOP + Brakedown PCS + campo binario. 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, permitiendo 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 de consistencia 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 pequeños campos. Cuarto, Binius utiliza una versión mejorada de la prueba de búsqueda Lasso, proporcionando flexibilidad y robusta seguridad al mecanismo de búsqueda. Finalmente, el protocolo utiliza un esquema de compromiso polinómico de pequeño campo (Small-Field PCS), permitiendo la implementación de un sistema de pruebas eficiente en el campo binario y reduciendo los gastos 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 lograr cálculos rápidos y verificables, principalmente debido a dos aspectos: cálculo eficiente y aritmética eficiente. Los campos binarios, en esencia, admiten 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 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 en torre, hacen que los campos binarios sean especialmente 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 se puede mapear 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 el 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 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, 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 reducciones especiales ) como las que se usan en AES ###, reducción de Montgomery ( como se usa 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 los campos binarios no es necesario introducir acarreo en las operaciones de suma y multiplicación, y las operaciones de cuadrado en campos binarios son muy eficientes, ya que siguen la regla simplificada de (X + Y )2 = X2 + Y 2.

Como se muestra en la figura 1, una cadena de 128 bits: esta cadena se puede interpretar de varias maneras en el contexto de un campo binario. Puede considerarse como un elemento único en un campo binario de 128 bits, o interpretarse como dos elementos de campo de torre de 64 bits, cuatro elementos de campo de torre de 32 bits, dieciséis 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 de cadena de bits (typecast), lo cual es una propiedad muy interesante y útil. Al mismo tiempo, los elementos de campo pequeños se pueden empaquetar en elementos de campo 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 campos de torre binaria de n bits ( descomponiéndose 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 basa en HyperPlonk y utiliza una serie de mecanismos de verificación centrales para validar la corrección de los polinomios y conjuntos multivariables. Estas verificaciones centrales incluyen:

1. GateCheck: Verifica si el testimonio 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: Verificar si los resultados de evaluación de los dos polinomios multivariados 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 polinómicas.

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: 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 del polinomio.

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 polinomios univariables, se reduce la complejidad computacional del 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 sumas.

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 distinto 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 ese valor en 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 el problema de no cero de U 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, lo que permite la promoción a cualquier valor de producto.

• Comprobación de Permutación de múltiples columnas: HyperPlonk no tiene esta función; Binius permite realizar 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 mejoró la flexibilidad y eficiencia del protocolo mediante la mejora del mecanismo PIOPSumCheck existente, especialmente al manejar la verificación de polinomios multivariables más complejos, proporcionando un soporte funcional más fuerte. Estas mejoras no solo resolvieron las limitaciones de HyperPlonk, sino que también sentaron las bases para futuros sistemas de prueba basados en campos 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, que permite 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 a través de