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 bastante pequeños, pero para garantizar la seguridad de las pruebas basadas en árboles de Merkle, al utilizar la codificación de Reed-Solomon para expandir los datos, muchos valores redundantes adicionales ocupan todo el dominio. Reducir el tamaño del dominio se convierte en una estrategia clave.

La primera generación de codificación STARKs tiene un ancho de 252 bits, la segunda generación es de 64 bits y la tercera generación es de 32 bits, pero el ancho de codificación de 32 bits todavía tiene un gran desperdicio de espacio. En comparación, el dominio binario permite realizar operaciones 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.

El dominio binario se ha aplicado ampliamente en la 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, utilizando 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

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.

Binius propuso una solución innovadora:

• Utilizar un polinomio multivariable (específicamente un polinomio multilinéal) en lugar de un polinomio univariable, representando toda la trayectoria de cálculo a través de sus valores en el "hipercubo".
• Considerar el hipercubo como un cuadrado, y realizar la expansión de Reed-Solomon basada en ese cuadrado.

2 Análisis de principios

Binius = HyperPlonk PIOP + Brakedown PCS + dominio binario

Binius incluye cinco tecnologías clave:

1. Arithmetización basada en el dominio binario en torre
2. Versión adaptada de la verificación de producto y permutación de HyperPlonk
3. Nueva prueba de desplazamiento multilineal
4. Versión mejorada de la búsqueda Lasso
5. Esquema de compromiso de polinomios de pequeño dominio

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

Ventajas del dominio binario en torre:

• Cálculo eficiente: el campo binario admite esencialmente operaciones aritméticas altamente eficientes.
• Eficiencia aritmética: la estructura de campo binario admite un proceso de aritmética simplificado
• Representación flexible: una misma cadena puede interpretarse de múltiples maneras en el contexto del dominio binario.
• No se requiere reducción: el campo binario no necesita llevar en las operaciones de suma y multiplicación.
• Cálculo cuadrático eficiente: (X + Y)2 = X2 + Y2

2.2 PIOP: versión adaptada del producto HyperPlonk y PermutationCheck

Mecanismo de verificación central:

1. GateCheck
2. PermutationCheck
3. LookupCheck
4. MultisetCheck
5. ProductCheck
6. ZeroCheck
7. SumCheck
8. BatchCheck

Comparado con las mejoras de HyperPlonk:

• Optimización de ProductCheck
• Manejo del problema de división por cero
• Comprobación de Permutación de Filas

2.3 PIOP: nuevo argumento de desplazamiento multilineal

Método clave:

• Packing: Optimizar la operación mediante el empaquetado de elementos más pequeños en posiciones adyacentes en el orden lexicográfico en elementos más grandes.
• Operador de desplazamiento: reordena los elementos dentro del bloque, realizando un desplazamiento cíclico basado en la cantidad de desplazamiento dada.

2.4 PIOP: versión adaptada del argumento de búsqueda Lasso

Ventajas del protocolo Lasso:

• Prueba eficiente: para m búsquedas en una tabla de tamaño n, solo se necesita comprometer m+n elementos de dominio.
• No se requiere compromiso de la tabla grande: si la tabla t está estructurada, no es necesario comprometerla, se pueden manejar tablas enormes.

Composición del protocolo Lasso:

• Abstracción de polinomios virtuales de gran tabla
• Búsqueda de pequeñas tablas
• Comprobación de múltiples conjuntos

Adaptación de Binius a Lasso:

• Introducir la versión multiplicativa del protocolo Lasso
• Se requiere que la parte que prueba se comprometa a un vector de conteo de lectura que sea siempre distinto de cero.

2.5 PCS: versión adaptada de Brakedown PCS

Idea principal: packing

Dos soluciones:

1. Adoptar código concatenado
2. Utiliza la tecnología de codificación a nivel de bloque, soporta el uso independiente de códigos de Reed-Solomon.

Principales tecnologías:

• Compromisos de polinomios de pequeño dominio y evaluación en dominios extendidos
• Construcción de microdominios
• Codificación a nivel de bloques y códigos de Reed-Solomon

3 Optimización del pensamiento

Cuatro puntos clave de optimización:

1. PIOP basado en GKR: para la operación de multiplicación en el dominio binario
2. Optimización de ZeroCheck PIOP: Balance de costos de cálculo entre Prover y Verifier
3. Optimización de Sumcheck PIOP: protocolo Sumcheck basado en pequeños dominios
4. Optimización de PCS: FRI-Binius reduce el tamaño de prueba de Binius

3.1 PIOP basado en GKR: multiplicación de campos binarios basada en GKR

Idea central:

Verificar si 2 enteros de 32 bits A y B cumplen A·B =? C Convertir a
"Verificando (gA)B =? gC si es válido"

Ventajas:

• Solo se necesita un compromiso auxiliar
• Reducir el costo de Sumchecks

3.2 ZeroCheck PIOP optimización

Dirección de optimización:

• Reducir la transmisión de datos de la parte que prueba
• Reducir el número de puntos de evaluación del comprobante
• Optimización de interpolación algebraica

3.3 Sumcheck PIOP optimización

Mejoras clave:

• Selección de cambio de ronda
• El impacto del tamaño del dominio en el rendimiento
• Beneficios de la optimización del algoritmo de Karatsuba
• Mejora de la eficiencia de la memoria

Resultados específicos:

• En el caso de que el campo sea GF[2], el rendimiento del algoritmo 4 es casi 30 veces superior al del algoritmo ingenuo.
• El algoritmo 4 solo requiere 0.26MB de memoria, mientras que el algoritmo 3 necesita 67MB

3.4 PCS Optimización: FRI-Binius

Cuatro puntos innovadores:

1. Polinomio plano
2. Polinomio de desaparición del subespacio
3. Paquete base algebraico
4. Intercambio de anillos SumCheck

Efecto: Reducir el tamaño de la prueba de Binius en un orden de magnitud.

4 Resumen

Ventajas de Binius:

• Puede utilizar el dominio de potencia de dos más pequeño para los testigos
• Bajo uso de memoria, prueba rápida
• Se eliminó prácticamente el cuello de botella en el compromiso commit de Prover.

FRI-Binius方案: Eliminar el costo de incrustación del nivel de prueba de dominio sin provocar un aumento drástico en el costo del nivel de prueba de agregación.

Últimos avances:

• El equipo de Irreducible está desarrollando su capa recursiva y colaborando con el equipo de Polygon para construir un zkVM basado en Binius.
• JoltzkVM está pasando de Lasso a Binius para mejorar su rendimiento recursivo
• El equipo de Ingonyama está implementando la versión FPGA de Binius