Análisis de Binius STARKs y su 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 expandir los datos utilizando codificación de Reed-Solomon, muchos valores de redundancia adicionales ocupan todo el dominio. 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 el ancho de codificación de 32 bits aún presenta un gran desperdicio de espacio. El dominio binario permite operar directamente sobre los bits, con una codificación compacta y eficiente sin ningún desperdicio de espacio, lo que podría ser la cuarta generación de STARKs.

Binius utiliza técnicas como el chequeo de productos y permutaciones de HyperPlonk, mejorado y basado en dominios binarios en torre, y compromisos polinómicos de campo pequeño, para mejorar la eficiencia desde varios ángulos.

2. Análisis de principios

Binius se compone de cinco tecnologías clave:

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

2.1 Arithmetización basada en dominios binarios en torre

El dominio binario en torre admite operaciones aritméticas eficientes y un proceso aritmético simplificado. Los elementos del dominio binario se pueden mapear directamente a cadenas de k bits, lo que ofrece la conveniencia de un mapeo uno a uno.

2.2 Versión adaptada de la verificación de productos y permutaciones de HyperPlonk

Binius se inspiró en el mecanismo de verificación central de HyperPlonk, incluyendo GateCheck, PermutationCheck, LookupCheck, y realizó mejoras en los siguientes aspectos:

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

2.3 Nueva prueba de desplazamiento multilineal

Binius introdujo dos métodos clave, Packing y el operador de desplazamiento, para construir y manejar polinomios virtuales.

2.4 versión adaptada Lasso búsqueda prueba

Binius ha adaptado Lasso para operar en el dominio binario, introduciendo una versión multiplicativa del protocolo Lasso.

2.5 Compromiso de polinomios de pequeño dominio

Binius ofrece dos esquemas de compromiso polinómico Brakedown basados en dominios binarios, utilizando principalmente compromisos polinómicos de pequeño dominio junto con evaluaciones de dominio extendido, construcciones generales de pequeño dominio y técnicas de codificación a nivel de bloque con códigos de Reed-Solomon.

3. Optimización del pensamiento

3.1 PIOP basado en GKR

El algoritmo de multiplicación en el dominio binario basado en GKR, al transformar "comprobar si 2 enteros de 32 bits A y B satisfacen A·B =? C" en "comprobar si (gA)B =? gC es válido", reduce significativamente el costo de compromiso gracias al protocolo GKR.

3.2 ZeroCheck PIOP optimización

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

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

3.3 Sumcheck PIOP optimización

Ingonyama propuso una mejora al protocolo Sumcheck basado en pequeños dominios, centrándose en la selección del número de rondas t.

3.4 PCS optimización: FRI-Binius

FRI-Binius ha implementado el mecanismo de pliegue FRI en el dominio binario, aportando innovaciones en 4 aspectos:

• Polinomio plano
• Polinomio de desaparición del subespacio
• Empaque de base algebraica
• Intercambio de sumas de verificación

4. Resumen

Binius es un "esquema de diseño colaborativo que utiliza hardware, software y el protocolo Sumcheck acelerado por FPGA", que puede demostrar rápidamente con una tasa de uso de memoria muy baja. En Binius, se ha eliminado prácticamente el cuello de botella de compromiso del Prover, y el nuevo cuello de botella radica en el protocolo Sumcheck, que se puede resolver de manera eficiente con hardware especializado.

El esquema FRI-Binius es una variante de FRI que puede eliminar el costo de incrustación del nivel de prueba de dominio sin provocar un aumento drástico en los costos del nivel de prueba de agregación. Actualmente, varios equipos están desarrollando tecnologías relacionadas con Binius, incluyendo capas recursivas, zkVM, etc.