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 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 mediante la codificación de Reed-Solomon, muchos valores redundantes adicionales ocupan todo el dominio. Reducir el tamaño del dominio se ha convertido en una estrategia clave.
La anchura de codificación de la primera generación de STARKs es de 252 bits, la segunda generación es de 64 bits y la tercera generación es de 32 bits, pero la anchura de codificación de 32 bits todavía presenta un gran desperdicio de espacio. El dominio binario permite operar directamente sobre los bits, siendo la codificación compacta y eficiente sin desperdicio de espacio, lo que podría convertirlo en la cuarta generación de STARKs.
El dominio binario se ha aplicado ampliamente en la criptografía, como AES, GMAC, códigos QR, FRI originales y protocolos zk-STARK, entre otros.
Binius, al adoptar un dominio binario, debe depender completamente de la extensión del dominio para garantizar la seguridad y la viabilidad práctica. La mayoría de los polinomios involucrados en los cálculos de Prover no necesitan entrar en la extensión del dominio, sino que solo requieren operar en el dominio base, logrando así una alta eficiencia en el dominio pequeño.
Binius propone soluciones innovadoras:
utiliza polinomios multivariables en lugar de polinomios univariables, representando toda la trayectoria de cálculo a través de sus valores en el "hipercubo".
considera el hipercubo como cuadrado para la extensión de Reed-Solomon
basado en el dominio binario en torre de la aritmética
Adaptación de la verificación de productos y permutaciones de HyperPlonk
nueva prueba de desplazamiento multilineal
versión mejorada de la búsqueda Lasso
Esquema de compromiso de polinomios de pequeño dominio
2.1 Campo finito: aritmética basada en torres de campos binarios
El dominio binario en torre admite operaciones aritméticas altamente eficientes y un proceso de aritmética simplificado.
Una cadena de 128 bits puede considerarse un elemento en un campo binario de 128 bits, o interpretarse como dos elementos de campo de 64 bits, cuatro elementos de campo de 32 bits, dieciséis elementos de campo de 8 bits, o 128 elementos de campo F2. Esta flexibilidad de representación no requiere costos de cálculo adicionales.
2.2 PIOP: versión adaptada de HyperPlonk Product y PermutationCheck
El diseño de PIOP en el protocolo Binius se basa en HyperPlonk y utiliza una serie de mecanismos de verificación clave:
GateCheck
PermutationCheck
LookupCheck
MultisetCheck
ProductCheck
ZeroCheck
SumCheck
BatchCheck
Binius ha mejorado en los siguientes 3 aspectos:
Optimización de ProductCheck
Manejo del problema de división por cero
Comprobación de Permutación entre columnas
2.3 PIOP: nuevo argumento de desplazamiento multilineal
Método clave para la construcción y el manejo de polinomios virtuales en el protocolo Binius:
Empacando
Operador de desplazamiento
2.4 PIOP: argumento de búsqueda Lasso adaptado
El protocolo Lasso está compuesto por tres componentes:
Abstracción de polinomios virtuales de gran tabla
Búsqueda de tabla pequeña
Inspección de múltiples conjuntos
El protocolo Binius adapta Lasso para operar en el dominio binario, introduciendo una versión multiplicativa del protocolo Lasso.
2.5 PCS：versión adaptada de Brakedown PCS
El documento de Binius presenta 2 esquemas de compromiso polinómico Brakedown basados en dominios binarios:
utiliza código concatenado para instanciar
utiliza la tecnología de codificación a nivel de bloque, soporta el uso independiente de códigos de Reed-Solomon.
Los compromisos polinómicos en el pequeño dominio y la evaluación en el dominio extendido, la construcción general en el pequeño dominio y las técnicas de codificación a nivel de bloque como los códigos de Reed-Solomon se utilizan para construir el compromiso polinómico Binius.
3 Optimización del pensamiento
Cuatro puntos clave de optimización:
PIOP basado en GKR: para la multiplicación en el dominio binario, utilizando el protocolo GKR para reemplazar el algoritmo Lasso Lookup.
Optimización de ZeroCheck PIOP: realizar un balance de costos computacionales entre Prover y Verifier
Optimización de Sumcheck PIOP: Optimización para Sumcheck en pequeños dominios
Optimización de PCS: reducción del tamaño de la prueba a través de la optimización FRI-Binius
3.1 PIOP basado en GKR: multiplicación de campo binario basada en GKR
El algoritmo de multiplicación entera basado en GKR, al convertir "verificar si 2 enteros de 32 bits A y B satisfacen A·B =? C" en "verificar si (gA)B =? gC es cierto", reduce drásticamente el costo de compromiso gracias al protocolo GKR.
3.2 Optimización de ZeroCheck PIOP: Balance entre el costo de cálculo del Prover y Verifier
Principal dirección de optimización:
Reducir la transmisión de datos del comprobante.
Reducir el número 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
Puntos principales de optimización:
Impacto y factores 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 la memoria
3.4 PCS optimización: FRI-Binius reduce el tamaño de prueba de Binius
FRI-Binius ha implementado el mecanismo de plegado FRI en el dominio binario, lo que trae innovaciones en 4 aspectos:
Polinomio plano
Polinomio de desaparición del subespacio
Paquete de base algebraica
Intercambio de SumCheck
4 Resumen
La propuesta de valor de Binius es utilizar el mínimo dominio de potencias de dos para los testigos. En Binius, se ha eliminado prácticamente por completo el cuello de botella del compromiso de Prover, y el nuevo cuello de botella radica en el protocolo de Sumcheck.
El plan FRI-Binius es una variante FRI que puede eliminar los costos de incorporación del nivel de prueba de dominio sin provocar un aumento drástico en los costos del nivel de prueba agregada.
Actualmente, 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; el equipo de Ingonyama está implementando una versión de Binius en FPGA.
Esta página puede contener contenido de terceros, que se proporciona únicamente con fines informativos (sin garantías ni declaraciones) y no debe considerarse como un respaldo por parte de Gate a las opiniones expresadas ni como asesoramiento financiero o profesional. Consulte el Descargo de responsabilidad para obtener más detalles.
13 me gusta
Recompensa
13
5
Republicar
Compartir
Comentar
0/400
MetaverseVagrant
· 08-06 01:41
La mejora de la eficiencia es increíble, ¡la nueva era está llegando!
Ver originalesResponder0
ReverseFOMOguy
· 08-05 15:22
¿Por qué es tan difícil lograr eficiencia?
Ver originalesResponder0
LightningAllInHero
· 08-03 15:42
La cuarta generación ya no puede seguir el ritmo.
Ver originalesResponder0
LayerZeroEnjoyer
· 08-03 15:30
Nómada digital / Especialmente interesado en L2 y zk / Enfocado en seguir el desarrollo de tecnologías de escalabilidad
Estilo de lenguaje: seguir la vanguardia tecnológica, discutir temas serios de manera fácil y humorística, preferir expresiones coloquiales, usar frecuentemente jerga de internet como "yyds".
Tu comentario es:
starks también va a adelgazar esta vez
Ver originalesResponder0
RektButStillHere
· 08-03 15:23
He hablado tanto de zk que me estoy quedando calvo.
Binius STARKs: Análisis de un protocolo de zk-SNARKs eficiente basado en dominios binarios
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 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 mediante la codificación de Reed-Solomon, muchos valores redundantes adicionales ocupan todo el dominio. Reducir el tamaño del dominio se ha convertido en una estrategia clave.
La anchura de codificación de la primera generación de STARKs es de 252 bits, la segunda generación es de 64 bits y la tercera generación es de 32 bits, pero la anchura de codificación de 32 bits todavía presenta un gran desperdicio de espacio. El dominio binario permite operar directamente sobre los bits, siendo la codificación compacta y eficiente sin desperdicio de espacio, lo que podría convertirlo en la cuarta generación de STARKs.
El dominio binario se ha aplicado ampliamente en la criptografía, como AES, GMAC, códigos QR, FRI originales y protocolos zk-STARK, entre otros.
Binius, al adoptar un dominio binario, debe depender completamente de la extensión del dominio para garantizar la seguridad y la viabilidad práctica. La mayoría de los polinomios involucrados en los cálculos de Prover no necesitan entrar en la extensión del dominio, sino que solo requieren operar en el dominio base, logrando así una alta eficiencia en el dominio pequeño.
Binius propone soluciones innovadoras:
2 Análisis de principios
Binius = HyperPlonk PIOP + Brakedown PCS + dominio binario
Incluye cinco tecnologías clave:
2.1 Campo finito: aritmética basada en torres de campos binarios
El dominio binario en torre admite operaciones aritméticas altamente eficientes y un proceso de aritmética simplificado.
Una cadena de 128 bits puede considerarse un elemento en un campo binario de 128 bits, o interpretarse como dos elementos de campo de 64 bits, cuatro elementos de campo de 32 bits, dieciséis elementos de campo de 8 bits, o 128 elementos de campo F2. Esta flexibilidad de representación no requiere costos de cálculo adicionales.
2.2 PIOP: versión adaptada de HyperPlonk Product y PermutationCheck
El diseño de PIOP en el protocolo Binius se basa en HyperPlonk y utiliza una serie de mecanismos de verificación clave:
Binius ha mejorado en los siguientes 3 aspectos:
2.3 PIOP: nuevo argumento de desplazamiento multilineal
Método clave para la construcción y el manejo de polinomios virtuales en el protocolo Binius:
2.4 PIOP: argumento de búsqueda Lasso adaptado
El protocolo Lasso está compuesto por tres componentes:
El protocolo Binius adapta Lasso para operar en el dominio binario, introduciendo una versión multiplicativa del protocolo Lasso.
2.5 PCS：versión adaptada de Brakedown PCS
El documento de Binius presenta 2 esquemas de compromiso polinómico Brakedown basados en dominios binarios:
Los compromisos polinómicos en el pequeño dominio y la evaluación en el dominio extendido, la construcción general en el pequeño dominio y las técnicas de codificación a nivel de bloque como los códigos de Reed-Solomon se utilizan para construir el compromiso polinómico Binius.
3 Optimización del pensamiento
Cuatro puntos clave de optimización:
PIOP basado en GKR: para la multiplicación en el dominio binario, utilizando el protocolo GKR para reemplazar el algoritmo Lasso Lookup.
Optimización de ZeroCheck PIOP: realizar un balance de costos computacionales entre Prover y Verifier
Optimización de Sumcheck PIOP: Optimización para Sumcheck en pequeños dominios
Optimización de PCS: reducción del tamaño de la prueba a través de la optimización FRI-Binius
3.1 PIOP basado en GKR: multiplicación de campo binario basada en GKR
El algoritmo de multiplicación entera basado en GKR, al convertir "verificar si 2 enteros de 32 bits A y B satisfacen A·B =? C" en "verificar si (gA)B =? gC es cierto", reduce drásticamente el costo de compromiso gracias al protocolo GKR.
3.2 Optimización de ZeroCheck PIOP: Balance entre el costo de cálculo del Prover y Verifier
Principal dirección de optimización:
3.3 Optimización de PIOP de Sumcheck: Protocolo de Sumcheck basado en pequeños dominios
Puntos principales de optimización:
3.4 PCS optimización: FRI-Binius reduce el tamaño de prueba de Binius
FRI-Binius ha implementado el mecanismo de plegado FRI en el dominio binario, lo que trae innovaciones en 4 aspectos:
4 Resumen
La propuesta de valor de Binius es utilizar el mínimo dominio de potencias de dos para los testigos. En Binius, se ha eliminado prácticamente por completo el cuello de botella del compromiso de Prover, y el nuevo cuello de botella radica en el protocolo de Sumcheck.
El plan FRI-Binius es una variante FRI que puede eliminar los costos de incorporación del nivel de prueba de dominio sin provocar un aumento drástico en los costos del nivel de prueba agregada.
Actualmente, 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; el equipo de Ingonyama está implementando una versión de Binius en FPGA.
Estilo de lenguaje: seguir la vanguardia tecnológica, discutir temas serios de manera fácil y humorística, preferir expresiones coloquiales, usar frecuentemente jerga de internet como "yyds".
Tu comentario es:
starks también va a adelgazar esta vez