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

1. Introducción

Una de las principales razones de la ineficiencia de STARKs es que en la mayoría de los programas reales, los valores numéricos son bastante pequeños, pero para garantizar la seguridad de las pruebas basadas en el árbol de Merkle, muchos valores redundantes adicionales ocuparán todo el dominio al utilizar la codificación de Reed-Solomon para expandir los datos, incluso si los valores originales son pequeños. Reducir el tamaño del dominio 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 los 32 bits todavía presentan un gran desperdicio de espacio. El dominio binario permite operaciones directas a nivel de bits, la codificación es compacta, eficiente y sin desperdicio, lo que podría ser la cuarta generación de STARKs.

El dominio binario se aplica ampliamente en criptografía, como AES(F28), GMAC(F2128), códigos QR(F28), etc. Cuando se utiliza un dominio más pequeño, la operación de extensión se vuelve cada vez más importante para garantizar la seguridad. El dominio binario utilizado por Binius depende completamente de la extensión para garantizar la seguridad y la disponibilidad. La mayoría de los cálculos de Prover se realizan en el campo base, de manera eficiente; la verificación de puntos aleatorios y el cálculo de FRI requieren profundizar en un dominio de extensión más grande para garantizar la seguridad.

Soluciones innovadoras de Binius:

1. utiliza múltiples variables ( polinomios multilineales ) en lugar de polinomios univariables, representando la trayectoria de cálculo mediante "hipercubo".
2. considera el hipercubo como cuadrado, basado en el cuadrado para la expansión de Reed-Solomon

2. Análisis de principios

Binius = HyperPlonk PIOP + Brakedown PCS + dominio binario

Cinco tecnologías clave:

1. basado en el dominio binario en forma de torre de la aritmética
2. Adaptación de la verificación de productos y permutaciones de HyperPlonk
3. Nueva prueba de desplazamiento multilineal
4. versión mejorada de Lasso búsqueda de evidencia
5. Esquema de compromiso de polinomios de pequeño dominio

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

Ventajas del dominio binario en torre:

• Cálculo eficiente: el campo binario admite operaciones aritméticas eficientes
• Arithmetización eficiente: la estructura del campo binario admite un proceso de aritmética simplificado
• Aprovechar al máximo las características jerárquicas a través de la estructura de torre

Cadena de 128 bits puede ser interpretada de manera flexible:

• Un elemento único en un campo de 128 bits
• Dos elementos de dominio de torre de 64 bits
• Cuatro elementos de torre de 32 bits
• 16 elementos de dominio de 8 bits
• 128 elementos del campo F2

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

Mecanismo de verificación central de Binius:

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

Binius sobre la mejora de HyperPlonk:

• Optimización de ProductCheck
• Manejar correctamente el problema de la división por cero
• Soporta PermutationCheck entre columnas

2.3 PIOP: nuevo argumento de desplazamiento multilineal

Método clave:

• Empaquetado: Agrupar elementos más pequeños adyacentes en un elemento más grande
• Operador de desplazamiento: reorganizar los elementos dentro del bloque

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

Ventajas del protocolo Lasso:

• Alta eficiencia de prueba: compromiso de m+n elementos de campo
• Sin necesidad de comprometer la tabla grande: puede manejar tablas extremadamente grandes

Binius introduce la versión multiplicativa del protocolo Lasso:

• Generar el "contador de memoria" incremental mediante la multiplicación de dominios binarios.
• La parte que demuestra se compromete a un vector de conteo de lecturas no nulo para garantizar la seguridad

2.5 PCS: versión adaptada Brakedown PCS

Idea central: packing

Dos soluciones:

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

Compromiso de polinomios de pequeño dominio y evaluación de dominio extendido:

• Compromiso en el pequeño dominio K
• Evaluar en un dominio de expansión más grande L/K

Codificación a nivel de bloques y código de Reed-Solomon:

• Permitir el pequeño dominio ( como el polinomio F2) usar el alfabeto de mayúsculas ( como el código Reed-Solomon F216) para un compromiso eficiente.

3. Optimización del pensamiento

Cuatro puntos clave de optimización:

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

Convierte "verificar A·B =? C" en "verificar (gA)B =? gC"

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

3.2 Optimización de ZeroCheck PIOP: Balance de costos de cálculo entre Prover y Verifier

Método de optimización:

• Reducir la transmisión de datos de la parte que prueba
• Reducir la cantidad de puntos de evaluación del comprobante.
• Optimización de interpolación algebraica

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

Áreas de mejora:

• Selección del turno t
• El tamaño del dominio afecta
• Optimización del algoritmo de Karatsuba
• Mejora de la eficiencia de la memoria

3.4 PCS optimización: FRI-Binius reducir el tamaño de la prueba

Cuatro innovaciones:

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

FRI-Binius puede reducir el tamaño de la prueba de Binius en un orden de magnitud.

4. Resumen

Ventajas de Binius:

• Puede utilizar el dominio mínimo de potencia de dos para testigos.
• Prueba rápida de bajo uso de memoria
• Eliminación básica del cuello de botella del compromiso Prover

Nuevo cuello de botella: Protocolo Sumcheck

• Se puede resolver de manera eficiente con hardware especializado

FRI-Binius:

• Eliminar el costo de la incrustación de la prueba de dominio
• No provoca un aumento drástico en los costos de la capa de prueba de participación.

Progreso actual:

• El equipo de Irreducible desarrolla una capa recursiva, en colaboración con Polygon, para construir un zkVM basado en Binius.
• JoltzkVM cambió de Lasso a Binius
• Ingonyama implementa la versión FPGA de Binius