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

1 Introducción

Una de las principales razones de la ineficiencia de STARKs es: la mayoría de los valores en los programas reales son bastante 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 expandir los datos utilizando codificación de Reed-Solomon, muchos valores adicionales de redundancia ocupan 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.

El ancho de banda de codificación de la primera generación de STARKs es de 252 bits, el ancho de banda de codificación de la segunda generación de STARKs es de 64 bits, y el ancho de banda de codificación de la tercera generación de STARKs es de 32 bits, pero el ancho de banda de codificación de 32 bits todavía tiene un gran desperdicio de espacio. En comparación, el campo binario permite operar directamente sobre los bits, con 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 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 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 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, 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 garantizar 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 solo necesitan operar en el dominio base, logrando así una alta eficiencia en dominios pequeños. Sin embargo, la verificación de puntos aleatorios y el cálculo FRI aún requieren adentrarse en un dominio de extensión más grande para asegurar la seguridad necesaria.

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 de manera separada y representa los mismos datos de dos maneras diferentes: primero, utilizando un polinomio multivariado ( específicamente un polinomio multilineal ) en lugar de un polinomio univariante, representando toda la trayectoria de cálculo a través de sus valores en los "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 ), basado en el cual se realiza la extensión de Reed-Solomon. Este método, al garantizar la seguridad, mejora enormemente la eficiencia de codificación y el rendimiento computacional.

2 Análisis del Principio

La construcción de la mayoría de los sistemas SNARKs actuales 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 núcleo del sistema de prueba, transforma la relación computacional ingresada en ecuaciones 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 pueda verificar si el cálculo es correcto consultando solo unos pocos resultados de evaluación de polinomios. Los protocolos PIOP existentes incluyen: PIOP PLONK, PIOP Spartan y PIOP HyperPlonk, 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 (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 probador comprometerse a un polinomio y más tarde verificar el resultado de la evaluación de ese polinomio, mientras oculta otra información del polinomio. Los esquemas de compromiso polinómico más 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 el campo finito o la curva elíptica adecuada, se puede construir un sistema de prueba con diferentes atributos. Por ejemplo:

• Halo2: combinando PLONK PIOP y Bulletproofs PCS, y basado en la curva Pasta. Halo2 fue diseñado con un enfoque en la escalabilidad y la eliminación de 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 eficiencias recursivas. Al diseñar estos sistemas, las PIOP y PCS seleccionadas deben coincidir con el campo finito o la curva elíptica utilizados 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 y la eficiencia de verificación de SNARK, sino que también determina si el sistema puede lograr transparencia sin una configuración confiable, y si puede soportar funcionalidades extendidas 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. Primero, la aritmética basada en torres de dominios binarios (towers of binary fields) constituye la base de su cómputo, permitiendo realizar operaciones simplificadas dentro del dominio binario. En segundo lugar, Binius adapta la verificación de productos y permutaciones de HyperPlonk en su protocolo de prueba 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 dominios. Cuarto, Binius utiliza una versión mejorada de la prueba de búsqueda Lasso, proporcionando flexibilidad y una fuerte seguridad para el mecanismo de búsqueda. Finalmente, el protocolo utiliza un esquema de compromiso polinómico de pequeño dominio (Small-Field PCS), permitiendo un sistema de prueba eficiente en el dominio binario y reduciendo la sobrecarga normalmente asociada a dominios grandes.

( 2.1 Campo finito: aritmética basada en torres de campos binarios

Los dominios binarios en torre son clave para implementar cálculos verificables rápidos, principalmente debido a dos aspectos: cálculo eficiente y aritmética eficiente. Los dominios binarios soportan operaciones aritméticas altamente eficientes, lo que los convierte en una opción ideal para aplicaciones criptográficas sensibles al rendimiento. Además, la estructura del dominio binario soporta un proceso de aritmética simplificado, es decir, las operaciones realizadas en el dominio binario pueden expresarse en una forma algebraica compacta y fácil de verificar. Estas características, junto con la capacidad de aprovechar plenamente sus características jerárquicas a través de la estructura en torre, hacen que los dominios binarios sean particularmente adecuados para sistemas de prueba escalables como Binius.

El término "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 del 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 un campo primo de 32 bits puede estar contenido en 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 Barrett, la reducción 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 la reducción especial ) como se usa en AES ###, la reducción 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 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 + Y 2.

Como se muestra en la Figura 1, una cadena de 128 bits: esta cadena puede interpretarse de varias maneras en el contexto del campo binario. Puede considerarse como un elemento único en un campo binario de 128 bits, o puede descomponerse en 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 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 cual 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 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, cuadrados y operaciones de inversión en un campo binario de torre de n bits ( descomponiéndose en un subcampo de m bits ).

( 2.2 PIOP: versión adaptada del producto HyperPlonk y PermutationCheck------aplicable a campos 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 polinomios y conjuntos de múltiples variables. 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: 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 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: Verificar si un polinomio multivariable en el hipercubo booleano es cero en un punto arbitrario ∏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 multivariable en uno univariable, se reduce la complejidad computacional para el validador. Además, SumCheck permite el procesamiento por lotes, introduciendo números aleatorios para construir combinaciones lineales que permiten la verificación de múltiples instancias 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 que el producto sea igual a un valor específico; Binius simplifica este proceso de verificación al especializar ese valor a 1, reduciendo así la complejidad computacional.

• Manejo del problema de división por cero: HyperPlonk no pudo manejar adecuadamente el caso de división por cero, lo que llevó a no poder afirmar que U es no nulo en el hipercubo; Binius manejó correctamente este problema, incluso en el caso de que el denominador sea cero, la ProductCheck de Binius puede seguir procesando, permitiendo la generalizació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 que Binius maneje situaciones de arreglos polinómicos más complejas.

Por lo tanto, Binius ha mejorado la flexibilidad y eficiencia del protocolo mediante la mejora del mecanismo PIOPSumCheck existente, especialmente al proporcionar un soporte funcional más robusto al manejar verificaciones de polinomios multivariados más complejos. Estas mejoras no solo abordan las limitaciones de HyperPlonk, sino que también sientan las bases para futuros sistemas de prueba basados en campos 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 puede 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 optimiza la operación empaquetando elementos más pequeños en posiciones adyacentes de la secuencia del diccionario en elementos más grandes. El operador Pack se aplica a bloques de tamaño 2κ y los combina en un dominio multidimensional.