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, como los índices en los bucles for, valores booleanos, contadores, etc. Sin embargo, para garantizar la seguridad de las pruebas basadas en árboles de Merkle, al extender los datos utilizando codificación de Reed-Solomon, muchos valores redundantes adicionales ocupan todo el campo, incluso si el valor original en sí es muy pequeño. Para resolver este problema, reducir el tamaño del campo se ha convertido en una estrategia clave.
El ancho de codificación de los STARKs de primera generación es de 252 bits, el de segunda generación es de 64 bits, y el de tercera generación es de 32 bits, pero el ancho de codificación de 32 bits aún presenta un gran desperdicio de espacio. En comparación, el dominio binario permite operar directamente sobre los bits, con una codificación compacta y eficiente sin ningún desperdicio de espacio, es decir, los STARKs de cuarta generación.
En comparación con los campos finitos descubiertos en investigaciones recientes como Goldilocks, BabyBear y Mersenne31, el estudio de los campos binarios se remonta a la década de 1980. Actualmente, los campos binarios se utilizan ampliamente en criptografía, ejemplos típicos incluyen:
Estándar de cifrado avanzado ( AES ), basado en el campo F28;
Galois código de autenticación de mensaje ( GMAC ), basado en el campo F2128;
Código QR, utiliza codificación Reed-Solomon basada en F28;
Protocolo FRI original y zk-STARK, así como la función hash Grøstl, que llegó a la final de SHA-3, basada en el campo F28, es un algoritmo hash muy adecuado para la recursión.
Cuando se utilizan dominios más pequeños, la operación de extensión de dominio se vuelve cada vez más importante para garantizar la seguridad. El dominio binario utilizado por Binius depende completamente de la extensión de dominio para asegurar su seguridad y viabilidad práctica. La mayoría de los polinomios involucrados en los cálculos de Prover no necesitan entrar en la extensión de dominio, sino que operan solo en el dominio base, logrando así una alta eficiencia en dominios pequeños. Sin embargo, la verificación de puntos aleatorios y los cálculos FRI aún deben profundizar en una extensión de dominio más grande para garantizar la seguridad requerida.
Al construir un sistema de pruebas basado en dominios binarios, existen 2 problemas prácticos: al calcular la representación de traza en STARKs, el tamaño del dominio utilizado debe ser mayor que el grado del polinomio; al comprometer el árbol de Merkle en STARKs, es necesario realizar codificación de Reed-Solomon, y el tamaño del dominio utilizado debe ser mayor que el tamaño después de la expansión de la codificación.
Binius ha propuesto una solución innovadora que aborda estos dos problemas de manera separada y representa los mismos datos de dos maneras diferentes: primero, utilizando un polinomio multivariable ( en lugar de un polinomio univariable, representando toda la trayectoria de cálculo a través de sus valores en los "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 (, basando la extensión de Reed-Solomon en ese cuadrado. Este enfoque, al tiempo que garantiza la seguridad, mejora enormemente la eficiencia de codificación y el rendimiento computacional.
2 Análisis de principios
La construcción de la mayoría de los sistemas SNARKs actualmente generalmente incluye las siguientes dos partes:
Prueba de Oracle Interactiva Polinómica de Teoría de la Información ): PIOP(: PIOP, como núcleo del sistema de pruebas, convierte las relaciones computacionales de entrada en ecuaciones polinómicas verificables. Diferentes protocolos PIOP permiten al probador enviar polinomios de manera gradual a través de la interacción con el verificador, de modo que el verificador puede validar si el cálculo es correcto consultando unos pocos resultados de evaluación de polinomios. Los protocolos PIOP existentes incluyen: PIOP PLONK, PIOP Spartan y PIOP HyperPlonk, entre otros, que tienen diferentes formas de tratar las expresiones polinómicas, lo que afecta el rendimiento y la eficiencia de todo el sistema SNARK.
Esquema de Compromiso Polinómico ) Polynomial Commitment Scheme, PCS (: El esquema de compromiso polinómico se utiliza para demostrar si se cumple la igualdad polinómica generada por PIOP. PCS es una herramienta criptográfica, a través de la cual, el probador puede comprometerse a un polinomio y verificar más tarde el resultado de la evaluación de ese polinomio, al mismo tiempo que oculta otra información del polinomio. Los esquemas de compromiso polinómico comunes incluyen KZG, Bulletproofs, FRI ) Fast Reed-Solomon IOPP ( y Brakedown, entre otros. Diferentes PCS tienen diferentes rendimientos, seguridad y escenarios de aplicación.
Según las necesidades específicas, elige diferentes PIOP y PCS, y combina con un campo finito adecuado o una curva elíptica, se puede construir un sistema de pruebas con diferentes atributos. Por ejemplo:
• Halo2: combinando PLONK PIOP y Bulletproofs PCS, y basado en la curva Pasta. Halo2 se diseñó con un enfoque en la escalabilidad y en eliminar la configuración de confianza del protocolo ZCash.
• Plonky2: utiliza PLONK PIOP combinado con FRI PCS y se basa en el dominio Goldilocks. Plonky2 está diseñado para lograr una recursión eficiente. Al diseñar estos sistemas, la PIOP y la PCS seleccionadas deben coincidir con el campo finito o la curva elíptica utilizada para garantizar la corrección, el rendimiento y la seguridad del sistema. La elección de estas combinaciones no solo afecta el tamaño de la prueba SNARK y la eficiencia de verificación, sino que también determina si el sistema puede lograr transparencia sin la necesidad de una configuración confiable, así como si puede soportar funciones extendidas como pruebas recursivas o pruebas agregadas.
Binius: HyperPlonk PIOP + Brakedown PCS + dominios binarios. En concreto, Binius incluye cinco tecnologías clave para lograr su eficiencia y seguridad. Primero, la aritmética basada en torres de dominios binarios )towers of binary fields( forma la base de su computación, permitiendo realizar operaciones simplificadas dentro de los dominios binarios. En segundo lugar, Binius adapta la verificación de productos y permutaciones de HyperPlonk en su protocolo de prueba de Oracle interactivo )PIOP(, asegurando una verificación de consistencia segura y eficiente entre las variables y sus permutaciones. En tercer lugar, el protocolo introduce una nueva prueba de desplazamiento multilineal, optimizando la eficiencia de la verificación de relaciones multilineales en pequeños dominios. Cuarto, Binius utiliza una versión mejorada de la prueba de búsqueda Lasso, que proporciona flexibilidad y una sólida seguridad al mecanismo de búsqueda. Por último, el protocolo emplea un esquema de compromiso polinómico en pequeños dominios )Small-Field PCS(, lo que le permite implementar un sistema de prueba eficiente en dominios binarios y reducir los gastos generalmente asociados con grandes dominios.
) 2.1 Campo finito: aritmética basada en torres de campos binarios
El dominio binario en torres es clave para lograr cálculos rápidos y verificables, principalmente debido a dos aspectos: el cálculo eficiente y la aritmética eficiente. El dominio binario, por su naturaleza, admite operaciones aritméticas altamente eficientes, lo que lo convierte en una opción ideal para aplicaciones criptográficas sensibles al rendimiento. Además, la estructura del dominio binario admite un proceso de aritmética simplificado, es decir, las operaciones realizadas en el dominio binario se pueden representar en una forma algebraica compacta y fácil de verificar. Estas características, junto con la capacidad de aprovechar plenamente sus características jerárquicas a través de la estructura en torres, hacen que el dominio binario sea especialmente adecuado para sistemas de prueba escalables como Binius.
La palabra "canónico" se refiere a la representación única y directa de los elementos en un campo binario. Por ejemplo, en el campo binario más básico F2, cualquier cadena de k bits se puede mapear directamente a un elemento del campo binario de k bits. Esto es diferente de los campos de números primos, que no pueden proporcionar esta representación canónica dentro de un número fijo de bits. Aunque un campo de números primos de 32 bits puede ser contenido en 32 bits, no todas las cadenas de 32 bits pueden corresponder de manera única a un elemento del campo, mientras que el campo binario tiene esta conveniencia de mapeo uno a uno. En el campo de números primos Fp, los métodos de reducción comunes incluyen la reducción de Barrett, la reducción de Montgomery, y métodos de reducción especiales para campos finitos específicos como Mersenne-31 o Goldilocks-64. En el campo binario F2k, los métodos de reducción comunes incluyen la reducción especial ( como se utiliza en AES ), la reducción de Montgomery ### como se utiliza en POLYVAL ( y la reducción recursiva ) como Tower (. El artículo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" señala que en el campo binario no se requiere llevar en las operaciones de suma y multiplicación, y que la operación de cuadrado en el campo binario es muy eficiente, ya que sigue la regla simplificada )X + Y (2 = X2 + Y 2.
Como se muestra en la Figura 1, una cadena de 128 bits: esta cadena se puede interpretar de varias maneras en el contexto del dominio binario. Puede ser vista como un elemento único en el dominio binario de 128 bits, o ser desglosada en dos elementos de dominio de torre de 64 bits, cuatro elementos de dominio de torre de 32 bits, 16 elementos de dominio de torre de 8 bits, o 128 elementos de dominio F2. Esta flexibilidad de representación no requiere ningún costo computacional, solo una conversión de tipo de la cadena de bits )typecast(, lo que es una propiedad muy interesante y útil. Al mismo tiempo, los elementos de dominio pequeños se pueden empaquetar en elementos de dominio más grandes sin necesidad de costos computacionales adicionales. El protocolo Binius aprovecha esta característica para mejorar la eficiencia computacional. Además, el artículo "On Efficient Inversion in Tower Fields of Characteristic Two" explora la complejidad computacional de realizar multiplicación, cuadrado e inversión en el dominio binario de torre de n bits ) descomponiéndolo en subdominios de m bits (.
![Bitlayer Research: Análisis de principios de Binius STARKs y reflexiones sobre su optimización])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 2.2 PIOP: versión adaptada del producto HyperPlonk y PermutationCheck------aplicable al campo binario
El diseño de PIOP en el protocolo Binius se basa en HyperPlonk, utilizando una serie de mecanismos de verificación clave para validar la corrección de polinomios y conjuntos multivariables. Estas verificaciones clave incluyen:
GateCheck: Verificar si el testigo secreto ω y la entrada pública x satisfacen la relación de operación del circuito C(x,ω)=0, para asegurar el correcto funcionamiento del circuito.
PermutationCheck: Verificar si los resultados de evaluación de dos polinomios multivariables f y g en el hipercubo booleano son una relación de permutación f###x( = f)π(x)(, para garantizar la consistencia de las permutaciones entre las variables polinómicas.
LookupCheck: Verificar si la evaluación del polinomio está en la tabla de búsqueda dada, es decir, f(Bµ) ⊆ T)Bµ(, asegurando que ciertos valores estén dentro del rango especificado.
MultisetCheck: verifica si dos conjuntos multivariables son iguales, es decir, {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H, garantizando la consistencia entre múltiples conjuntos.
ProductCheck: Comprobar si la evaluación de un polinomio racional en el hipercubo booleano es igual a un valor declarado ∏x∈Hµ f)x( = s, para garantizar la corrección del producto polinómico.
ZeroCheck: Verificar si un polinomio multivariable en un hipercubo booleano es cero en un punto arbitrario ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, para asegurar la distribución de los ceros del polinomio.
SumCheck: Verifica si la suma de un polinomio multivariable es igual al valor declarado ∑x∈Hµ f)x( = s. Al transformar el problema de evaluación de un polinomio multivariable en la evaluación de un polinomio univariable, se reduce la complejidad computacional para el verificador. Además, SumCheck también permite el procesamiento por lotes, introduciendo números aleatorios para construir combinaciones lineales y realizar el procesamiento por lotes de múltiples instancias de verificación de suma.
BatchCheck: Basado en SumCheck, verifica la corrección de la evaluación de múltiples polinomios multivariables para mejorar la eficiencia del protocolo.
A pesar de que Binius y HyperPlonk tienen muchas similitudes en el diseño del protocolo, Binius ha realizado mejoras en los siguientes 3 aspectos:
Optimización de ProductCheck: en HyperPlonk, ProductCheck requiere que el denominador U sea no nulo en el hipercubo y que el producto sea igual a un valor específico; Binius simplifica este proceso de verificación especializando ese valor a 1, reduciendo así la complejidad computacional.
Manejo del problema de división por cero: HyperPlonk no pudo manejar adecuadamente la situación de división por cero, lo que llevó a no poder afirmar que U es diferente de cero en el hipercubo; Binius manejó correctamente este problema, incluso en el caso de que el denominador sea cero, el ProductCheck de Binius puede continuar procesando, permitiendo la extensión a cualquier valor de producto.
Verificación de Permutación entre columnas: HyperPlonk no tiene esta función; Binius admite la verificación de permutación entre múltiples columnas, lo que permite a Binius manejar situaciones de disposición polinómica más complejas.
Por lo tanto, Binius ha mejorado la flexibilidad y eficiencia del protocolo mediante la mejora del mecanismo existente PIOPSumCheck, especialmente al manejar la verificación de polinomios multivariables más complejos, proporcionando un soporte funcional más fuerte. Estas mejoras no solo abordan las limitaciones de HyperPlonk, sino que también establecen una base para futuros sistemas de prueba basados en campos binarios.
![Investigación de Bitlayer: Análisis de los principios de Binius STARKs y reflexiones sobre su optimización])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.3 PIOP: nuevo argumento de desplazamiento multilineal ------ aplicable a hipercubo booleano
En el protocolo Binius, la construcción y el manejo de polinomios virtuales es una de las tecnologías clave, capaz de generar y operar de manera efectiva polinomios derivados de manejadores de entrada u otros polinomios virtuales. A continuación se presentan dos métodos clave:
Packing: Este método a través de
Ver originales
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.
7 me gusta
Recompensa
7
7
Compartir
Comentar
0/400
OnChain_Detective
· hace15h
no voy a mentir, este patrón de optimización se ve muy sospechoso... necesitamos una inspección más cercana sobre esos reclamos de dominio binario
Ver originalesResponder0
0xTherapist
· hace20h
¿Y qué si son 32 bits? Todavía es un desperdicio de espacio.
Ver originalesResponder0
CryptoCrazyGF
· hace22h
¿De qué sirve investigar tanto si en la cadena no corre igual de rápido?
Ver originalesResponder0
MemeCurator
· hace22h
¡Si no lo entiendes, lo entenderás!
Ver originalesResponder0
LiquidityWhisperer
· hace23h
Reducción de redundancia binaria, parece que sabe jugar bastante bien.
Ver originalesResponder0
AirdropHunter007
· hace23h
starks también puede perder peso ¡increíble!
Ver originalesResponder0
TopEscapeArtist
· hace23h
Oh, ¿esto es de nuevo el ritmo de querer romper la zona baja técnica? La experiencia histórica me dice que siempre son trampas~
Análisis del protocolo Binius: implementación eficiente de STARKs en el dominio binario
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, como los índices en los bucles for, valores booleanos, contadores, etc. Sin embargo, para garantizar la seguridad de las pruebas basadas en árboles de Merkle, al extender los datos utilizando codificación de Reed-Solomon, muchos valores redundantes adicionales ocupan todo el campo, incluso si el valor original en sí es muy pequeño. Para resolver este problema, reducir el tamaño del campo se ha convertido en una estrategia clave.
El ancho de codificación de los STARKs de primera generación es de 252 bits, el de segunda generación es de 64 bits, y el de tercera generación es de 32 bits, pero el ancho de codificación de 32 bits aún presenta un gran desperdicio de espacio. En comparación, el dominio binario permite operar directamente sobre los bits, con una codificación compacta y eficiente sin ningún desperdicio de espacio, es decir, los STARKs de cuarta generación.
En comparación con los campos finitos descubiertos en investigaciones recientes como Goldilocks, BabyBear y Mersenne31, el estudio de los campos binarios se remonta a la década de 1980. Actualmente, los campos binarios se utilizan ampliamente en criptografía, ejemplos típicos incluyen:
Estándar de cifrado avanzado ( AES ), basado en el campo F28;
Galois código de autenticación de mensaje ( GMAC ), basado en el campo F2128;
Código QR, utiliza codificación Reed-Solomon basada en F28;
Protocolo FRI original y zk-STARK, así como la función hash Grøstl, que llegó a la final de SHA-3, basada en el campo F28, es un algoritmo hash muy adecuado para la recursión.
Cuando se utilizan dominios más pequeños, la operación de extensión de dominio se vuelve cada vez más importante para garantizar la seguridad. El dominio binario utilizado por Binius depende completamente de la extensión de dominio para asegurar su seguridad y viabilidad práctica. La mayoría de los polinomios involucrados en los cálculos de Prover no necesitan entrar en la extensión de dominio, sino que operan solo en el dominio base, logrando así una alta eficiencia en dominios pequeños. Sin embargo, la verificación de puntos aleatorios y los cálculos FRI aún deben profundizar en una extensión de dominio más grande para garantizar la seguridad requerida.
Al construir un sistema de pruebas basado en dominios binarios, existen 2 problemas prácticos: al calcular la representación de traza en STARKs, el tamaño del dominio utilizado debe ser mayor que el grado del polinomio; al comprometer el árbol de Merkle en STARKs, es necesario realizar codificación de Reed-Solomon, y el tamaño del dominio utilizado debe ser mayor que el tamaño después de la expansión de la codificación.
Binius ha propuesto una solución innovadora que aborda estos dos problemas de manera separada y representa los mismos datos de dos maneras diferentes: primero, utilizando un polinomio multivariable ( en lugar de un polinomio univariable, representando toda la trayectoria de cálculo a través de sus valores en los "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 (, basando la extensión de Reed-Solomon en ese cuadrado. Este enfoque, al tiempo que garantiza la seguridad, mejora enormemente la eficiencia de codificación y el rendimiento computacional.
2 Análisis de principios
La construcción de la mayoría de los sistemas SNARKs actualmente generalmente incluye las siguientes dos partes:
Prueba de Oracle Interactiva Polinómica de Teoría de la Información ): PIOP(: PIOP, como núcleo del sistema de pruebas, convierte las relaciones computacionales de entrada en ecuaciones polinómicas verificables. Diferentes protocolos PIOP permiten al probador enviar polinomios de manera gradual a través de la interacción con el verificador, de modo que el verificador puede validar si el cálculo es correcto consultando unos pocos resultados de evaluación de polinomios. Los protocolos PIOP existentes incluyen: PIOP PLONK, PIOP Spartan y PIOP HyperPlonk, entre otros, que tienen diferentes formas de tratar las expresiones polinómicas, lo que afecta el rendimiento y la eficiencia de todo el sistema SNARK.
Esquema de Compromiso Polinómico ) Polynomial Commitment Scheme, PCS (: El esquema de compromiso polinómico se utiliza para demostrar si se cumple la igualdad polinómica generada por PIOP. PCS es una herramienta criptográfica, a través de la cual, el probador puede comprometerse a un polinomio y verificar más tarde el resultado de la evaluación de ese polinomio, al mismo tiempo que oculta otra información del polinomio. Los esquemas de compromiso polinómico comunes incluyen KZG, Bulletproofs, FRI ) Fast Reed-Solomon IOPP ( y Brakedown, entre otros. Diferentes PCS tienen diferentes rendimientos, seguridad y escenarios de aplicación.
Según las necesidades específicas, elige diferentes PIOP y PCS, y combina con un campo finito adecuado o una curva elíptica, se puede construir un sistema de pruebas con diferentes atributos. Por ejemplo:
• Halo2: combinando PLONK PIOP y Bulletproofs PCS, y basado en la curva Pasta. Halo2 se diseñó con un enfoque en la escalabilidad y en eliminar la configuración de confianza del protocolo ZCash.
• Plonky2: utiliza PLONK PIOP combinado con FRI PCS y se basa en el dominio Goldilocks. Plonky2 está diseñado para lograr una recursión eficiente. Al diseñar estos sistemas, la PIOP y la PCS seleccionadas deben coincidir con el campo finito o la curva elíptica utilizada para garantizar la corrección, el rendimiento y la seguridad del sistema. La elección de estas combinaciones no solo afecta el tamaño de la prueba SNARK y la eficiencia de verificación, sino que también determina si el sistema puede lograr transparencia sin la necesidad de una configuración confiable, así como si puede soportar funciones extendidas como pruebas recursivas o pruebas agregadas.
Binius: HyperPlonk PIOP + Brakedown PCS + dominios binarios. En concreto, Binius incluye cinco tecnologías clave para lograr su eficiencia y seguridad. Primero, la aritmética basada en torres de dominios binarios )towers of binary fields( forma la base de su computación, permitiendo realizar operaciones simplificadas dentro de los dominios binarios. En segundo lugar, Binius adapta la verificación de productos y permutaciones de HyperPlonk en su protocolo de prueba de Oracle interactivo )PIOP(, asegurando una verificación de consistencia segura y eficiente entre las variables y sus permutaciones. En tercer lugar, el protocolo introduce una nueva prueba de desplazamiento multilineal, optimizando la eficiencia de la verificación de relaciones multilineales en pequeños dominios. Cuarto, Binius utiliza una versión mejorada de la prueba de búsqueda Lasso, que proporciona flexibilidad y una sólida seguridad al mecanismo de búsqueda. Por último, el protocolo emplea un esquema de compromiso polinómico en pequeños dominios )Small-Field PCS(, lo que le permite implementar un sistema de prueba eficiente en dominios binarios y reducir los gastos generalmente asociados con grandes dominios.
) 2.1 Campo finito: aritmética basada en torres de campos binarios
El dominio binario en torres es clave para lograr cálculos rápidos y verificables, principalmente debido a dos aspectos: el cálculo eficiente y la aritmética eficiente. El dominio binario, por su naturaleza, admite operaciones aritméticas altamente eficientes, lo que lo convierte en una opción ideal para aplicaciones criptográficas sensibles al rendimiento. Además, la estructura del dominio binario admite un proceso de aritmética simplificado, es decir, las operaciones realizadas en el dominio binario se pueden representar en una forma algebraica compacta y fácil de verificar. Estas características, junto con la capacidad de aprovechar plenamente sus características jerárquicas a través de la estructura en torres, hacen que el dominio binario sea especialmente adecuado para sistemas de prueba escalables como Binius.
La palabra "canónico" se refiere a la representación única y directa de los elementos en un campo binario. Por ejemplo, en el campo binario más básico F2, cualquier cadena de k bits se puede mapear directamente a un elemento del campo binario de k bits. Esto es diferente de los campos de números primos, que no pueden proporcionar esta representación canónica dentro de un número fijo de bits. Aunque un campo de números primos de 32 bits puede ser contenido en 32 bits, no todas las cadenas de 32 bits pueden corresponder de manera única a un elemento del campo, mientras que el campo binario tiene esta conveniencia de mapeo uno a uno. En el campo de números primos Fp, los métodos de reducción comunes incluyen la reducción de Barrett, la reducción de Montgomery, y métodos de reducción especiales para campos finitos específicos como Mersenne-31 o Goldilocks-64. En el campo binario F2k, los métodos de reducción comunes incluyen la reducción especial ( como se utiliza en AES ), la reducción de Montgomery ### como se utiliza en POLYVAL ( y la reducción recursiva ) como Tower (. El artículo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" señala que en el campo binario no se requiere llevar en las operaciones de suma y multiplicación, y que la operación de cuadrado en el campo binario es muy eficiente, ya que sigue la regla simplificada )X + Y (2 = X2 + Y 2.
Como se muestra en la Figura 1, una cadena de 128 bits: esta cadena se puede interpretar de varias maneras en el contexto del dominio binario. Puede ser vista como un elemento único en el dominio binario de 128 bits, o ser desglosada en dos elementos de dominio de torre de 64 bits, cuatro elementos de dominio de torre de 32 bits, 16 elementos de dominio de torre de 8 bits, o 128 elementos de dominio F2. Esta flexibilidad de representación no requiere ningún costo computacional, solo una conversión de tipo de la cadena de bits )typecast(, lo que es una propiedad muy interesante y útil. Al mismo tiempo, los elementos de dominio pequeños se pueden empaquetar en elementos de dominio más grandes sin necesidad de costos computacionales adicionales. El protocolo Binius aprovecha esta característica para mejorar la eficiencia computacional. Además, el artículo "On Efficient Inversion in Tower Fields of Characteristic Two" explora la complejidad computacional de realizar multiplicación, cuadrado e inversión en el dominio binario de torre de n bits ) descomponiéndolo en subdominios de m bits (.
![Bitlayer Research: Análisis de principios de Binius STARKs y reflexiones sobre su optimización])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 2.2 PIOP: versión adaptada del producto HyperPlonk y PermutationCheck------aplicable al campo binario
El diseño de PIOP en el protocolo Binius se basa en HyperPlonk, utilizando una serie de mecanismos de verificación clave para validar la corrección de polinomios y conjuntos multivariables. Estas verificaciones clave incluyen:
GateCheck: Verificar si el testigo secreto ω y la entrada pública x satisfacen la relación de operación del circuito C(x,ω)=0, para asegurar el correcto funcionamiento del circuito.
PermutationCheck: Verificar si los resultados de evaluación de dos polinomios multivariables f y g en el hipercubo booleano son una relación de permutación f###x( = f)π(x)(, para garantizar la consistencia de las permutaciones entre las variables polinómicas.
LookupCheck: Verificar si la evaluación del polinomio está en la tabla de búsqueda dada, es decir, f(Bµ) ⊆ T)Bµ(, asegurando que ciertos valores estén dentro del rango especificado.
MultisetCheck: verifica si dos conjuntos multivariables son iguales, es decir, {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H, garantizando la consistencia entre múltiples conjuntos.
ProductCheck: Comprobar si la evaluación de un polinomio racional en el hipercubo booleano es igual a un valor declarado ∏x∈Hµ f)x( = s, para garantizar la corrección del producto polinómico.
ZeroCheck: Verificar si un polinomio multivariable en un hipercubo booleano es cero en un punto arbitrario ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, para asegurar la distribución de los ceros del polinomio.
SumCheck: Verifica si la suma de un polinomio multivariable es igual al valor declarado ∑x∈Hµ f)x( = s. Al transformar el problema de evaluación de un polinomio multivariable en la evaluación de un polinomio univariable, se reduce la complejidad computacional para el verificador. Además, SumCheck también permite el procesamiento por lotes, introduciendo números aleatorios para construir combinaciones lineales y realizar el procesamiento por lotes de múltiples instancias de verificación de suma.
BatchCheck: Basado en SumCheck, verifica la corrección de la evaluación de múltiples polinomios multivariables para mejorar la eficiencia del protocolo.
A pesar de que Binius y HyperPlonk tienen muchas similitudes en el diseño del protocolo, Binius ha realizado mejoras en los siguientes 3 aspectos:
Optimización de ProductCheck: en HyperPlonk, ProductCheck requiere que el denominador U sea no nulo en el hipercubo y que el producto sea igual a un valor específico; Binius simplifica este proceso de verificación especializando ese valor a 1, reduciendo así la complejidad computacional.
Manejo del problema de división por cero: HyperPlonk no pudo manejar adecuadamente la situación de división por cero, lo que llevó a no poder afirmar que U es diferente de cero en el hipercubo; Binius manejó correctamente este problema, incluso en el caso de que el denominador sea cero, el ProductCheck de Binius puede continuar procesando, permitiendo la extensión a cualquier valor de producto.
Verificación de Permutación entre columnas: HyperPlonk no tiene esta función; Binius admite la verificación de permutación entre múltiples columnas, lo que permite a Binius manejar situaciones de disposición polinómica más complejas.
Por lo tanto, Binius ha mejorado la flexibilidad y eficiencia del protocolo mediante la mejora del mecanismo existente PIOPSumCheck, especialmente al manejar la verificación de polinomios multivariables más complejos, proporcionando un soporte funcional más fuerte. Estas mejoras no solo abordan las limitaciones de HyperPlonk, sino que también establecen una base para futuros sistemas de prueba basados en campos binarios.
![Investigación de Bitlayer: Análisis de los principios de Binius STARKs y reflexiones sobre su optimización])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.3 PIOP: nuevo argumento de desplazamiento multilineal ------ aplicable a hipercubo booleano
En el protocolo Binius, la construcción y el manejo de polinomios virtuales es una de las tecnologías clave, capaz de generar y operar de manera efectiva polinomios derivados de manejadores de entrada u otros polinomios virtuales. A continuación se presentan dos métodos clave: