Análisis de los principios de Binius STARKs y reflexión 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, los valores booleanos, los contadores, etc. Sin embargo, para garantizar la seguridad de las pruebas basadas en árboles de Merkle, al usar la codificación de Reed-Solomon para expandir los datos, muchos valores redundantes adicionales ocuparán 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 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 espacio desperdiciado. En comparación, el dominio binario permite operaciones directas sobre los bits, siendo la codificación compacta y eficiente sin ningún espacio desperdiciado, es decir, STARKs de cuarta generación.
En comparación con Goldilocks, BabyBear, Mersenne31 y otros dominios finitos descubiertos en los últimos años, la investigación sobre dominios binarios se remonta a la década de 1980. Actualmente, los dominios binarios se han aplicado 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 mensajes ( GMAC ), basado en el dominio 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, que se basa en el campo F28, es un algoritmo de hash muy adecuado para la recursión.
Cuando se utilizan campos más pequeños, la operación de extensión de campo se vuelve cada vez más importante para garantizar la seguridad. El campo binario utilizado por Binius depende completamente de la extensión de campo 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 campo, sino que solo operan en el campo base, lo que permite lograr alta eficiencia en el campo pequeño. Sin embargo, las verificaciones de puntos aleatorios y los cálculos de FRI aún necesitan profundizar en un campo de extensión más grande para garantizar la seguridad requerida.
Al construir un sistema de prueba basado en el dominio binario, existen 2 problemas prácticos: al calcular la representación de la 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, se debe realizar la 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 propuso una solución innovadora que aborda estos dos problemas por separado 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 "hipercubos" ); en segundo lugar, dado que cada dimensión del hipercubo tiene una longitud de 2, no se puede realizar una extensión de Reed-Solomon estándar como en STARKs, pero se puede considerar el hipercubo como un cuadrado (, y realizar la extensión de Reed-Solomon basada en ese cuadrado. Este método, al asegurar la seguridad, mejora enormemente la eficiencia de codificación y el rendimiento del cálculo.
2. Análisis de principios
La construcción de la mayoría de los sistemas SNARKs actuales generalmente incluye las siguientes dos partes:
Prueba de Oracle Interactiva Polinómica Teórica de la Información )Information-Theoretic Polynomial Interactive Oracle Proof, PIOP(: PIOP como el núcleo del sistema de prueba, transforma la relación de cálculo 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 pueda validar si el cálculo es correcto consultando solo unos pocos resultados de evaluación de polinomios. Los protocolos PIOP existentes incluyen: PLONK PIOP, Spartan PIOP y HyperPlonk PIOP, cada uno de los cuales maneja las expresiones polinómicas de manera diferente, 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 probar si la ecuación polinómica generada por PIOP es válida. PCS es una herramienta criptográfica que permite al probador comprometerse a un polinomio y verificar más tarde el resultado de la evaluación de dicho polinomio, mientras oculta otra información del polinomio. Los esquemas de compromiso polinómico más comunes incluyen KZG, Bulletproofs, FRI ) Fast Reed-Solomon IOPP ( y Brakedown, entre otros. Diferentes PCS tienen diferentes rendimientos, niveles de seguridad y escenarios de aplicación.
Según las necesidades específicas, elija diferentes PIOP y PCS, y combine con un campo finito o una curva elíptica adecuada, se pueden construir sistemas de prueba con diferentes atributos. Por ejemplo:
• Halo2: combina PLONK PIOP y Bulletproofs PCS, y se basa en la curva Pasta. Halo2 fue diseñado con un enfoque en la escalabilidad y en eliminar el setup confiable del protocolo ZCash.
• Plonky2: utiliza PLONK PIOP combinado con FRI PCS y se basa en el dominio de Goldilocks. Plonky2 está diseñado para lograr una recursividad 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 la verificación, sino que también determina si el sistema puede lograr transparencia sin necesidad de una configuración confiable, y si puede soportar funciones extendidas como pruebas recursivas o pruebas agregadas.
Binius: HyperPlonk PIOP + Brakedown PCS + campos binarios. En concreto, Binius incluye cinco tecnologías clave para lograr su eficiencia y seguridad. Primero, la aritmética basada en torres de campos binarios )towers of binary fields( constituye la base de sus cálculos, permitiendo operaciones simplificadas dentro del campo binario. Segundo, Binius adapta la verificación de productos y permutaciones de HyperPlonk en su protocolo de prueba Oracle interactivo )PIOP(, asegurando una verificación consistente de la seguridad y eficiencia entre las variables y sus permutaciones. Tercero, el protocolo introduce una nueva prueba de desplazamiento multilineal, optimizando la eficiencia de la verificación de relaciones multilineales en pequeños campos. Cuarto, Binius utiliza una versión mejorada de la prueba de búsqueda Lasso, que proporciona flexibilidad y una fuerte seguridad al mecanismo de búsqueda. Finalmente, el protocolo emplea un esquema de compromiso polinómico de pequeños campos )Small-Field PCS(, lo que le permite implementar un sistema de pruebas eficiente en el campo binario y reducir los costos normalmente asociados con campos grandes.
) 2.1 Cuerpos finitos: Arithmetización basada en torres de campos binarios
El campo binario en torre es clave para implementar cálculos rápidos y verificables, principalmente debido a dos aspectos: cálculo eficiente y aritmética eficiente. El campo binario admite operaciones aritméticas de alta eficiencia, lo que lo convierte en una opción ideal para aplicaciones criptográficas sensibles a los requisitos de rendimiento. Además, la estructura del campo binario admite un proceso de aritmética simplificado, es decir, las operaciones realizadas sobre el campo binario pueden representarse 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 de torre, hacen que el campo binario sea especialmente adecuado para sistemas de prueba escalables como Binius.
El término "canónico" se refiere a la representación única y directa de elementos en un campo binario. Por ejemplo, en el campo binario más básico F2, cualquier cadena de k bits puede mapearse directamente a un elemento del campo de k bits. Esto es diferente de los campos primos, que no pueden proporcionar esta representación canónica dentro de un número fijo de bits. Aunque un campo primo de 32 bits puede incluirse 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 proporciona esta conveniencia de un mapeo uno a uno. En el campo primo Fp, los métodos de reducción comunes incluyen la reducción de Barrett, la reducción de Montgomery, así como 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 ( utilizada en AES ), la reducción de Montgomery ### utilizada 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, las operaciones de suma y multiplicación no requieren llevar, y 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 de un dominio binario. Puede ser vista como un elemento único en un dominio binario de 128 bits, o ser解析为 dos elementos de dominio de torre de 64 bits, cuatro elementos de dominio de torre de 32 bits, 16 elementos de dominio de 8 bits, o 128 elementos de dominio F2. Esta flexibilidad en la representación no requiere ningún costo computacional, solo una conversión de tipo de cadena de bits )typecast(, que es una propiedad muy interesante y útil. Al mismo tiempo, los elementos de dominio pequeños pueden ser empaquetados en elementos de dominio más grandes sin necesidad de un costo computacional adicional. El protocolo Binius se beneficia de 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 multiplicaciones, cuadrados y operaciones de inversión en un dominio binario de torre de n bits ) descomponiéndolo en un subdominio de m bits (.
![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-5775a629f494c4e01e2b74d864fa4100.webp(
) 2.2 PIOP: versión adaptada del producto HyperPlonk y PermutationCheck------aplicable a campos binarios
El diseño de PIOP en el protocolo Binius se inspiró en HyperPlonk, utilizando una serie de mecanismos de verificación centrales para validar la corrección de polinomios y conjuntos multivariables. Estas verificaciones centrales incluyen:
GateCheck: Verificar si el testigo confidencial ω y la entrada pública x satisfacen la relación de operación del circuito C(x,ω)=0, para asegurar que el circuito funcione correctamente.
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 asegurar la consistencia en la permutación de las variables del polinomio.
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: Verificar 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: Verificar si la evaluación de un polinomio racional en el hipercubo booleano es igual a un valor declarado ∏x∈Hµ f)x( = s, para asegurar la corrección del producto polinómico.
ZeroCheck: Verificar si un polinomio multivariable en el hipercubo booleano es cero en cualquier punto ∏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 que permiten 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 diferente de cero en todo el hipercubo, y que el producto sea igual a un valor específico; Binius simplifica este proceso de verificación al especializar ese valor en 1, reduciendo así la complejidad computacional.
Manejo del problema de división por cero: HyperPlonk no pudo manejar adecuadamente las situaciones de división por cero, lo que llevó a no poder afirmar el problema de no cero de U en el hipercubo; Binius manejó correctamente este problema, incluso en el caso de que el denominador sea cero, el ProductCheck de Binius también puede continuar procesándose, permitiendo la generalización a cualquier valor de producto.
Verificación de Permutación entre columnas: HyperPlonk no tiene esta funcionalidad; 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 PIOPSumCheck existente, especialmente al ofrecer un soporte funcional más fuerte al manejar la verificación de polinomios multivariables más complejos. Estas mejoras no solo resuelven las limitaciones en HyperPlonk, sino que también establecen una base para futuros sistemas de pruebas basados en dominios 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 al hipercubo booleano
En el protocolo Binius, la construcción y el manejo de polinomios virtuales son una de las técnicas clave, que permiten generar y operar de manera efectiva los polinomios derivados de un manejador de entrada u otros polinomios virtuales. A continuación se presentan dos métodos clave:
Packing: Este método es
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
4
Republicar
Compartir
Comentar
0/400
zkProofInThePudding
· hace16h
La ancho se ha comprimido, alcista
Ver originalesResponder0
GweiWatcher
· 08-11 10:29
Parece que todavía se está desperdiciando demasiado.
Binius STARKs: Aplicaciones innovadoras y optimización del rendimiento en el dominio binario
Análisis de los principios de Binius STARKs y reflexión 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, los valores booleanos, los contadores, etc. Sin embargo, para garantizar la seguridad de las pruebas basadas en árboles de Merkle, al usar la codificación de Reed-Solomon para expandir los datos, muchos valores redundantes adicionales ocuparán 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 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 espacio desperdiciado. En comparación, el dominio binario permite operaciones directas sobre los bits, siendo la codificación compacta y eficiente sin ningún espacio desperdiciado, es decir, STARKs de cuarta generación.
En comparación con Goldilocks, BabyBear, Mersenne31 y otros dominios finitos descubiertos en los últimos años, la investigación sobre dominios binarios se remonta a la década de 1980. Actualmente, los dominios binarios se han aplicado 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 mensajes ( GMAC ), basado en el dominio 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, que se basa en el campo F28, es un algoritmo de hash muy adecuado para la recursión.
Cuando se utilizan campos más pequeños, la operación de extensión de campo se vuelve cada vez más importante para garantizar la seguridad. El campo binario utilizado por Binius depende completamente de la extensión de campo 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 campo, sino que solo operan en el campo base, lo que permite lograr alta eficiencia en el campo pequeño. Sin embargo, las verificaciones de puntos aleatorios y los cálculos de FRI aún necesitan profundizar en un campo de extensión más grande para garantizar la seguridad requerida.
Al construir un sistema de prueba basado en el dominio binario, existen 2 problemas prácticos: al calcular la representación de la 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, se debe realizar la 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 propuso una solución innovadora que aborda estos dos problemas por separado 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 "hipercubos" ); en segundo lugar, dado que cada dimensión del hipercubo tiene una longitud de 2, no se puede realizar una extensión de Reed-Solomon estándar como en STARKs, pero se puede considerar el hipercubo como un cuadrado (, y realizar la extensión de Reed-Solomon basada en ese cuadrado. Este método, al asegurar la seguridad, mejora enormemente la eficiencia de codificación y el rendimiento del cálculo.
2. Análisis de principios
La construcción de la mayoría de los sistemas SNARKs actuales generalmente incluye las siguientes dos partes:
Prueba de Oracle Interactiva Polinómica Teórica de la Información )Information-Theoretic Polynomial Interactive Oracle Proof, PIOP(: PIOP como el núcleo del sistema de prueba, transforma la relación de cálculo 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 pueda validar si el cálculo es correcto consultando solo unos pocos resultados de evaluación de polinomios. Los protocolos PIOP existentes incluyen: PLONK PIOP, Spartan PIOP y HyperPlonk PIOP, cada uno de los cuales maneja las expresiones polinómicas de manera diferente, 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 probar si la ecuación polinómica generada por PIOP es válida. PCS es una herramienta criptográfica que permite al probador comprometerse a un polinomio y verificar más tarde el resultado de la evaluación de dicho polinomio, mientras oculta otra información del polinomio. Los esquemas de compromiso polinómico más comunes incluyen KZG, Bulletproofs, FRI ) Fast Reed-Solomon IOPP ( y Brakedown, entre otros. Diferentes PCS tienen diferentes rendimientos, niveles de seguridad y escenarios de aplicación.
Según las necesidades específicas, elija diferentes PIOP y PCS, y combine con un campo finito o una curva elíptica adecuada, se pueden construir sistemas de prueba con diferentes atributos. Por ejemplo:
• Halo2: combina PLONK PIOP y Bulletproofs PCS, y se basa en la curva Pasta. Halo2 fue diseñado con un enfoque en la escalabilidad y en eliminar el setup confiable del protocolo ZCash.
• Plonky2: utiliza PLONK PIOP combinado con FRI PCS y se basa en el dominio de Goldilocks. Plonky2 está diseñado para lograr una recursividad 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 la verificación, sino que también determina si el sistema puede lograr transparencia sin necesidad de una configuración confiable, y si puede soportar funciones extendidas como pruebas recursivas o pruebas agregadas.
Binius: HyperPlonk PIOP + Brakedown PCS + campos binarios. En concreto, Binius incluye cinco tecnologías clave para lograr su eficiencia y seguridad. Primero, la aritmética basada en torres de campos binarios )towers of binary fields( constituye la base de sus cálculos, permitiendo operaciones simplificadas dentro del campo binario. Segundo, Binius adapta la verificación de productos y permutaciones de HyperPlonk en su protocolo de prueba Oracle interactivo )PIOP(, asegurando una verificación consistente de la seguridad y eficiencia entre las variables y sus permutaciones. Tercero, el protocolo introduce una nueva prueba de desplazamiento multilineal, optimizando la eficiencia de la verificación de relaciones multilineales en pequeños campos. Cuarto, Binius utiliza una versión mejorada de la prueba de búsqueda Lasso, que proporciona flexibilidad y una fuerte seguridad al mecanismo de búsqueda. Finalmente, el protocolo emplea un esquema de compromiso polinómico de pequeños campos )Small-Field PCS(, lo que le permite implementar un sistema de pruebas eficiente en el campo binario y reducir los costos normalmente asociados con campos grandes.
) 2.1 Cuerpos finitos: Arithmetización basada en torres de campos binarios
El campo binario en torre es clave para implementar cálculos rápidos y verificables, principalmente debido a dos aspectos: cálculo eficiente y aritmética eficiente. El campo binario admite operaciones aritméticas de alta eficiencia, lo que lo convierte en una opción ideal para aplicaciones criptográficas sensibles a los requisitos de rendimiento. Además, la estructura del campo binario admite un proceso de aritmética simplificado, es decir, las operaciones realizadas sobre el campo binario pueden representarse 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 de torre, hacen que el campo binario sea especialmente adecuado para sistemas de prueba escalables como Binius.
El término "canónico" se refiere a la representación única y directa de elementos en un campo binario. Por ejemplo, en el campo binario más básico F2, cualquier cadena de k bits puede mapearse directamente a un elemento del campo de k bits. Esto es diferente de los campos primos, que no pueden proporcionar esta representación canónica dentro de un número fijo de bits. Aunque un campo primo de 32 bits puede incluirse 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 proporciona esta conveniencia de un mapeo uno a uno. En el campo primo Fp, los métodos de reducción comunes incluyen la reducción de Barrett, la reducción de Montgomery, así como 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 ( utilizada en AES ), la reducción de Montgomery ### utilizada 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, las operaciones de suma y multiplicación no requieren llevar, y 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 de un dominio binario. Puede ser vista como un elemento único en un dominio binario de 128 bits, o ser解析为 dos elementos de dominio de torre de 64 bits, cuatro elementos de dominio de torre de 32 bits, 16 elementos de dominio de 8 bits, o 128 elementos de dominio F2. Esta flexibilidad en la representación no requiere ningún costo computacional, solo una conversión de tipo de cadena de bits )typecast(, que es una propiedad muy interesante y útil. Al mismo tiempo, los elementos de dominio pequeños pueden ser empaquetados en elementos de dominio más grandes sin necesidad de un costo computacional adicional. El protocolo Binius se beneficia de 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 multiplicaciones, cuadrados y operaciones de inversión en un dominio binario de torre de n bits ) descomponiéndolo en un subdominio de m bits (.
![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-5775a629f494c4e01e2b74d864fa4100.webp(
) 2.2 PIOP: versión adaptada del producto HyperPlonk y PermutationCheck------aplicable a campos binarios
El diseño de PIOP en el protocolo Binius se inspiró en HyperPlonk, utilizando una serie de mecanismos de verificación centrales para validar la corrección de polinomios y conjuntos multivariables. Estas verificaciones centrales incluyen:
GateCheck: Verificar si el testigo confidencial ω y la entrada pública x satisfacen la relación de operación del circuito C(x,ω)=0, para asegurar que el circuito funcione correctamente.
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 asegurar la consistencia en la permutación de las variables del polinomio.
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: Verificar 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: Verificar si la evaluación de un polinomio racional en el hipercubo booleano es igual a un valor declarado ∏x∈Hµ f)x( = s, para asegurar la corrección del producto polinómico.
ZeroCheck: Verificar si un polinomio multivariable en el hipercubo booleano es cero en cualquier punto ∏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 que permiten 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 diferente de cero en todo el hipercubo, y que el producto sea igual a un valor específico; Binius simplifica este proceso de verificación al especializar ese valor en 1, reduciendo así la complejidad computacional.
Manejo del problema de división por cero: HyperPlonk no pudo manejar adecuadamente las situaciones de división por cero, lo que llevó a no poder afirmar el problema de no cero de U en el hipercubo; Binius manejó correctamente este problema, incluso en el caso de que el denominador sea cero, el ProductCheck de Binius también puede continuar procesándose, permitiendo la generalización a cualquier valor de producto.
Verificación de Permutación entre columnas: HyperPlonk no tiene esta funcionalidad; 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 PIOPSumCheck existente, especialmente al ofrecer un soporte funcional más fuerte al manejar la verificación de polinomios multivariables más complejos. Estas mejoras no solo resuelven las limitaciones en HyperPlonk, sino que también establecen una base para futuros sistemas de pruebas basados en dominios 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 al hipercubo booleano
En el protocolo Binius, la construcción y el manejo de polinomios virtuales son una de las técnicas clave, que permiten generar y operar de manera efectiva los polinomios derivados de un manejador de entrada u otros polinomios virtuales. A continuación se presentan dos métodos clave: