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 usar codificación Reed-Solomon para expandir los datos, muchos valores redundantes adicionales ocupan todo el campo. Reducir el tamaño del campo se convierte en una estrategia clave.

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

Binius adoptó las siguientes tecnologías clave:

• Arithmetización basada en el dominio binario en torre
• Versión mejorada de la verificación de productos y permutaciones de HyperPlonk
• Nueva prueba de desplazamiento multi-lineal
• Versión mejorada del argumento de búsqueda Lasso
• Esquema de compromiso de polinomios de pequeño dominio

2. Análisis de principios

2.1 Arithmetización basada en torres de campos binarios

El dominio binario en forma de torre soporta operaciones aritméticas altamente eficientes, siendo clave para lograr cálculos rápidos y verificables. Sus ventajas incluyen:

• Cálculo eficiente
• Arithmetización eficiente
• Soporte para procesos aritméticos simplificados
• Se puede aprovechar plenamente sus características jerárquicas a través de la estructura de torre.

2.2 Versión adaptada del producto HyperPlonk y PermutationCheck

Binius ha mejorado HyperPlonk en los siguientes aspectos:

• Optimización de ProductCheck: especializar el valor a 1, simplificar el proceso de verificación
• Manejo del problema de división por cero: se puede continuar procesando incluso si el denominador es cero.
• Comprobación de Permutación entre columnas: soporte para la Comprobación de Permutación entre múltiples columnas

2.3 nuevo argumento de desplazamiento multilineal

Binius introdujo dos métodos clave:

• Empaque: Optimización de operaciones a través del empaquetado de elementos adyacentes
• Operador de desplazamiento: reorganiza los elementos dentro de un bloque basándose en el desplazamiento dado.

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

Binius adapta Lasso a operaciones en el dominio binario, introduciendo una versión de multiplicación del protocolo Lasso. La parte que prueba debe comprometer un vector de conteo de lecturas que sea siempre no nulo, para asegurar la seguridad del protocolo.

2.5 versión adaptada Brakedown PCS

Binius ofrece dos esquemas de compromiso polinómico Brakedown basados en el dominio binario:

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

3. Pensamiento optimizado

3.1 PIOP basado en GKR

La operación de multiplicación en el dominio binario basada en GKR solo requiere un compromiso auxiliar, mejorando la eficiencia al reducir los costos de las Sumchecks.

3.2 ZeroCheck PIOP optimización

A través de ajustar la distribución de trabajo entre la parte que prueba y la parte que verifica, se han propuesto varias soluciones de optimización:

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

3.3 Sumcheck PIOP optimización

Ingonyama propuso una mejora al protocolo Sumcheck basado en dominios pequeños:

• La selección de cambio de ronda afecta el rendimiento
• Los campos base más pequeños muestran ventajas más significativas.
• El algoritmo de Karatsuba mejora el rendimiento
• La eficiencia de la memoria ha mejorado

3.4 PCS optimización: FRI-Binius

FRI-Binius ha implementado un mecanismo de plegado FRI en el dominio binario, trayendo 4 innovaciones:

• Polinomio plano
• Polinomio de desaparición del subespacio
• Paquete de base algebraica
• Intercambio de SumCheck

4. Resumen

Binius ha eliminado el cuello de botella del compromiso de Prover, el nuevo cuello de botella está en el protocolo Sumcheck. El esquema FRI-Binius es una variante de FRI que puede eliminar el costo de incrustación de la capa de prueba de dominio. Actualmente, varios equipos están desarrollando aplicaciones relacionadas con Binius.