Análisis de los principios de Binius STARKs y reflexiones sobre la optimización

1. Introducción

Una de las principales razones de la ineficiencia 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 Reed-Solomon para expandir los datos, muchos valores redundantes adicionales ocupan todo el campo. Para resolver este problema, reducir el tamaño del campo se convierte en una estrategia clave.

La primera generación de codificación STARKs tiene un ancho de 252 bits, la segunda generación tiene 64 bits y la tercera generación tiene 32 bits, pero el ancho de codificación de 32 bits todavía presenta un gran espacio desperdiciado. En comparación, el dominio binario permite operar directamente sobre los bits, con una codificación compacta y eficiente sin espacio desperdiciado, es decir, la cuarta generación de STARKs.

El dominio binario utilizado por Binius depende completamente de la extensión del campo para garantizar su seguridad y utilidad práctica. La mayoría de los polinomios involucrados en los cálculos de Prover no necesitan entrar en la extensión del campo, sino que operan solo en el campo base, logrando así una alta eficiencia en el campo pequeño. Sin embargo, la verificación de puntos aleatorios y el cálculo de FRI aún requieren profundizar en un campo de extensión más grande para asegurar la seguridad necesaria.

Binius propuso una solución innovadora: primero, utilizar polinomios multivariables (específicamente polinomios multilineales) 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 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, y realizar la extensión de Reed-Solomon basada en ese cuadrado.

2. Análisis de principios

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 operaciones aritméticas altamente eficientes.
• Eficiencia aritmética: la estructura de campo binario admite un proceso aritmético simplificado
• Representación estándar: los elementos en el dominio binario tienen una representación única y directa.

Ventajas del dominio binario:

• La suma y la multiplicación no requieren llevar.
• La operación cuadrática es muy eficiente, siguiendo la regla de simplificación (X + Y)^2 = X^2 + Y^2.
• Indica flexibilidad: una cadena de 128 bits puede considerarse un elemento único en un campo binario de 128 bits, o desglosarse en combinaciones de varios elementos de torre.

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

Mecanismo de verificación central de Binius PIOP:

• GateCheck
• PermutationCheck
• LookupCheck
• MultisetCheck
• ProductCheck
• ZeroCheck
• SumCheck
• BatchCheck

Mejoras de Binius en HyperPlonk:

• ProductCheck optimización
• Manejo del problema de división por cero
• Soporte de PermutationCheck en múltiples columnas

2.3 PIOP: nuevo argumento de desplazamiento multilineal

Métodos clave:

• Empaque: Optimización de operaciones a través del empaquetado de elementos adyacentes
• Operador de desplazamiento: reorganizar elementos dentro del bloque

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

Composición del protocolo Lasso:

• Abstracción de polinomios virtuales en la gran tabla
• Búsqueda de la tabla pequeña
• Verificación de múltiples conjuntos

Adaptación de Binius de Lasso:

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

2.5 PCS: versión adaptada Brakedown PCS

Idea central: packing

Dos esquemas de compromiso polinómico Brakedown basados en el campo binario:

1. Instanciar el 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.

Tecnología principal:

• Compromisos de polinomios de pequeño dominio y evaluación en un dominio extendido
• Construcción de pequeño dominio
• Codificación por bloques y código de Reed-Solomon

3. Pensamiento optimizado

Cuatro puntos clave de optimización:

3.1 PIOP basado en GKR: multiplicación de campo binario basada en GKR

Ventajas en comparación con la solución de búsqueda de Binius:

• Solo se necesita un compromiso auxiliar
• Reducir los gastos de Sumchecks

3.2 ZeroCheck PIOP optimización: balance de costos de cálculo entre Prover y Verifier

Método de optimización:

• Reducir la transmisión de datos del comprobante
• Reducir la cantidad de puntos de evaluación del proveedor de pruebas
• Optimización de interpolación algebraica

3.3 Optimización de PIOP de Sumcheck: Protocolo de Sumcheck basado en pequeños dominios

Punto clave:

• Impacto y factor de mejora del 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 memoria

3.4 PCS optimización: FRI-Binius reducción del tamaño de prueba de Binius

FRI-Binius cuatro innovaciones:

• Polinomio plano
• Polinomio de desaparición de subespacios
• Paquete de base algebraica
• Intercambio de suma de anillo

FRI-Binius PCS proceso:

• Fase de compromiso
• Fase de evaluación

4. Resumen

La propuesta de valor de Binius:

• Puede usar el dominio power-of-two más pequeño para los testigos.
• Propuesta de diseño colaborativo, baja tasa de uso de memoria, prueba rápida
• Eliminar básicamente el cuello de botella en el compromiso de commit de Prover
• El nuevo cuello de botella radica en el protocolo Sumcheck, que se puede resolver de manera eficiente con hardware especializado.

FRI-Binius方案:

• Eliminar los gastos de incorporación de la capa de prueba de dominio
• No causará un aumento drástico en los costos de la capa de prueba de participación.

Progreso actual:

• El equipo de Irreducible desarrolla capas recursivas, en colaboración con Polygon para construir zkVM basado en Binius.
• JoltzkVM pasó de Lasso a Binius
• El equipo de Ingonyama ha implementado la versión FPGA de Binius