Análisis de los principios de Binius STARKs y reflexiones sobre su optimización
1 Introducción
A diferencia de los SNARKs basados en curvas elípticas, los STARKs pueden ser considerados como SNARKs basados en hash. Actualmente, una de las principales razones de la ineficiencia de los STARKs es que en la mayoría de los programas reales, los valores numéricos son pequeños, como índices de bucle, valores booleanos, contadores, etc. Sin embargo, para garantizar la seguridad de las pruebas basadas en árboles de Merkle, al usar codificación de Reed-Solomon para expandir los datos, muchos valores redundantes ocuparán todo el campo, incluso si los valores originales son pequeños. Para resolver este problema, reducir el tamaño del campo se convierte en una estrategia clave.
La primera generación de STARKs tiene un ancho de código de 252 bits, la segunda generación de 64 bits y la tercera generación de 32 bits, pero la codificación de 32 bits aún tiene mucho espacio desperdiciado. En comparación, el campo binario permite operar directamente sobre los bits, con una codificación compacta y eficiente sin desperdicio, lo que se puede considerar como la cuarta generación de STARKs.
En comparación con los campos finitos descubiertos en los últimos años como Goldilocks, BabyBear y Mersenne31, la investigación sobre campos binarios se remonta a la década de 1980. Actualmente, los campos binarios se utilizan ampliamente en criptografía, como en el campo AES(F28, el campo GMAC)F2128, y la codificación Reed-Solomon del código QR(F28, entre otros. Los protocolos FRI originales y zk-STARK, así como la función hash Grøstl, que fue finalista en SHA-3, también se basan en el campo F28.
Al usar dominios más pequeños, 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 asegurar la seguridad y la disponibilidad. La mayoría de los polinomios involucrados en los cálculos de Prover solo necesitan operar en el campo base, logrando así alta eficiencia en el campo pequeño. Sin embargo, la verificación de puntos aleatorios y los cálculos de FRI aún deben realizarse en un campo de extensión más grande para garantizar la seguridad requerida.
Existen dos problemas prácticos al construir un sistema de prueba basado en el dominio binario:
Al calcular la representación de la traza en STARKs, el tamaño del dominio debe ser mayor que el grado del polinomio.
En STARKs, al comprometerse con el árbol de Merkle, es necesario realizar la codificación de Reed-Solomon, y el tamaño del campo utilizado debe ser mayor que el tamaño después de la expansión de la codificación.
Binius propuso soluciones innovadoras para abordar estos dos problemas:
Utilizar un polinomio multivariable ) en lugar de un polinomio univariante, representando toda la trayectoria de cálculo a través de sus valores en el "hipercubo".
Debido a que cada dimensión del hipercubo tiene una longitud de 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 y realizar una extensión de Reed-Solomon basada en ese cuadrado.
Este método mejora significativamente la eficiencia de codificación y el rendimiento computacional, al mismo tiempo que garantiza la seguridad.
2 Análisis de principios
Actualmente, la mayoría de los sistemas SNARKs generalmente constan de dos partes:
Prueba de oráculo interactivo polinómico de teoría de la información ( PIOP ):
Como núcleo del sistema de prueba, convierte la relación computacional de entrada en ecuaciones polinómicas verificables. A través de la interacción con el verificador, el probador envía polinomios de manera gradual, permitiendo que el verificador valide la corrección del cálculo al consultar una pequeña cantidad de resultados de polinomios. Los protocolos PIOP existentes incluyen PLONK PIOP, Spartan PIOP y HyperPlonk PIOP, entre otros.
Esquema de compromiso polinómico (PCS):
Se utiliza para demostrar si se cumplen las igualdades polinómicas generadas por PIOP. PCS es una herramienta criptográfica, el demostrador puede comprometerse a un polinomio y validar su resultado de evaluación más tarde, mientras oculta otra información del polinomio. Los PCS comunes incluyen KZG, Bulletproofs, FRI y Brakedown.
Según las necesidades, elija diferentes PIOP y PCS, y combine con un campo finito o una curva elíptica adecuada para construir un sistema de pruebas con diferentes atributos. Por ejemplo:
Arithmetización basada en el dominio binario en torre: constituye la base del cálculo, implementando operaciones simplificadas en el dominio binario.
Adaptación de la verificación de productos y permutaciones de HyperPlonk: asegurarse de la verificación de consistencia eficiente entre variables y permutaciones.
Nueva prueba de desplazamiento multilineal: optimización de la eficiencia de verificación de relaciones multilineales en pequeños dominios.
Mejorar la demostración de búsqueda de Lasso: proporcionar flexibilidad y seguridad al mecanismo de búsqueda.
Esquema de compromiso de polinomios de pequeño dominio: implementación de un sistema de prueba eficiente sobre un campo binario, reduciendo los costos relacionados con un campo grande.
( 2.1 Campo Finito: 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 la eficiente computación y a la eficientización aritmética. El campo binario, en esencia, soporta operaciones aritméticas altamente eficientes, convirtiéndose en una opción ideal para aplicaciones criptográficas sensibles al rendimiento. La estructura del campo binario soporta un proceso de aritmética simplificada, y las operaciones realizadas en el campo binario pueden representarse en una forma algebraica compacta y fácil de verificar. Estas características, junto con la capacidad de aprovechar completamente sus características jerárquicas a través de la estructura en torre, hacen que el campo binario sea especialmente adecuado para sistemas de prueba escalables como Binius.
"canónico" se refiere a la representación única y directa de los elementos en el campo binario. Por ejemplo, en el campo binario 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 primos, que no pueden proporcionar esta representación canónica dentro de un número determinado de bits. Aunque un campo primo de 32 bits puede caber en 32 bits, no cada cadena de 32 bits puede 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 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 comúnmente utilizados incluyen la reducción especial ) como AES utiliza (, la reducción de Montgomery ) como POLYVAL utiliza ### 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 es necesario introducir acarreo 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 + Y2.
Una cadena de 128 bits se puede interpretar de varias maneras en el contexto de un dominio binario. Puede considerarse como un elemento único en un dominio binario de 128 bits, o descomponerse 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 en el dominio F2. Esta flexibilidad de representación no requiere ningún costo computacional, simplemente una conversión de tipo de cadena de bits, 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 costo computacional adicional. El protocolo Binius aprovecha esta característica para mejorar la eficiencia computacional.
El artículo "On Efficient Inversion in Tower Fields of Characteristic Two" explora la complejidad computacional de realizar operaciones de multiplicación, cuadrado e inversión en un campo binario en torres de n bits donde ( se descompone en un subcampo de m bits ).
( 2.2 PIOP: versión adaptada de HyperPlonk Product y PermutationCheck------aplicable a campos binarios
El diseño de PIOP en el protocolo Binius se inspira en HyperPlonk, utilizando una serie de mecanismos de verificación fundamentales para validar la corrección de polinomios y conjuntos multivariables:
GateCheck: Verifica si el testigo secreto ω y la entrada pública x satisfacen la relación de operación del circuito C)x, ω(=0, asegurando el correcto funcionamiento del circuito.
PermutationCheck: Verificar si los resultados de evaluación de los dos polinomios multivariables f y g en el hipercubo booleano son una relación de permutación f)x### = f(π)x(), asegurando la consistencia de la permutación entre 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: 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: Verificar si la evaluación de un polinomio racional en el hipercubo booleano es igual a un valor declarado ∏x∈Hμ f(x) = s, asegurando la corrección del producto polinómico.
ZeroCheck: Verificar si un polinomio multivariable en un hipercubo booleano es cero en cualquier punto ∏x∈Hμ f(x) = 0, ∀x ∈ Bμ, asegurando la distribución de los ceros del polinomio.
SumCheck: Verificar si la suma de un polinomio multivariable es igual al valor declarado ∑x∈Hμ f(x) = s. Al transformar el problema de evaluación del polinomio multivariable en uno de evaluación de polinomio univariable, se reduce la complejidad computacional del validador. 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 sumas.
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 siempre no nulo en el hipercubo, y que el producto sea igual a un valor específico; Binius simplifica este proceso de verificación al especializar este valor a 1, reduciendo 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 lleva a no poder afirmar que U es no cero en el hipercubo; Binius manejó este problema correctamente, incluso en el caso de que el denominador sea cero, el ProductCheck de Binius también puede continuar procesando, permitiendo la generalización a cualquier valor de producto.
Comprobación de Permutación entre columnas: HyperPlonk no tiene esta función; Binius admite la comprobación de permutación entre varias 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 PIOP SumCheck existente, especialmente al manejar la verificación de polinomios multivariables más complejos, proporcionando un soporte funcional más robusto. Estas mejoras no solo abordan las limitaciones en HyperPlonk, sino que también establecen las bases para futuros sistemas de prueba basados en campos binarios.
( 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 son una de las tecnologías clave, capaces de generar y manipular de manera efectiva polinomios derivados de un identificador de entrada u otros polinomios virtuales. A continuación se presentan dos métodos clave:
Packing: Este método optimiza las operaciones empaquetando elementos más pequeños en posiciones adyacentes de la orden de diccionario en elementos más grandes. El operador Pack se aplica a bloques de tamaño 2κ y los combina en un solo elemento en un dominio de alta dimensión. A través de la Extensión Multilineal ), MLE(, este polinomio virtual puede evaluarse y procesarse de manera eficiente, convirtiendo la función t en otro polinomio, mejorando así el rendimiento computacional.
Operador de desplazamiento: El operador de desplazamiento reorganiza los elementos dentro de un bloque, realizando un desplazamiento cíclico basado en un desplazamiento dado o. Este método es aplicable a bloques de tamaño 2b, donde cada bloque realiza el desplazamiento según el desplazamiento. El operador de desplazamiento se define mediante la detección del soporte de la función, asegurando consistencia y eficiencia al manejar polinomios virtuales. La complejidad de evaluar esta construcción crece linealmente con el tamaño del bloque, siendo especialmente adecuada para procesar grandes conjuntos de datos o en escenas de alta dimensión dentro de hipercubos booleanos.
![Bitlayer Research: Análisis de los principios de Binius STARKs y su pensamiento de optimización])https://img-cdn.gateio.im/webp-social/moments-7f96976952fd0f8da0e93ff1042a966d.webp###
( 2.4 PIOP: versión adaptada del argumento de búsqueda Lasso ------ aplicable a dominios binarios
El protocolo Lasso permite que la parte que prueba comprometa un vector a ∈ Fm y demuestre que todos sus elementos existen en una tabla previamente especificada t ∈ Fn. Lasso desbloquea el concepto de "buscar singularidades")lookup singularities( y puede aplicarse a esquemas de compromiso de polinomios multilineales. Su eficiencia se refleja en los siguientes dos aspectos:
Eficiencia de la prueba: para m búsquedas en una tabla de tamaño n, el probador solo necesita comprometer m+n elementos de dominio. Estos elementos de dominio son pequeños y están en el conjunto {0,...,m}. En el esquema de compromiso basado en múltiples exponentiaciones, el costo computacional del probador es O)m + n### operaciones de grupo( como
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.
9 me gusta
Recompensa
9
4
Republicar
Compartir
Comentar
0/400
DeadTrades_Walking
· hace7h
Se ha jugado la compresión de dominio.
Ver originalesResponder0
zkProofInThePudding
· hace7h
No tengo habilidades, solo estoy desperdiciando un poco de espacio.
Binius: Optimización e innovación de STARKs basados en dominios binarios
Análisis de los principios de Binius STARKs y reflexiones sobre su optimización
1 Introducción
A diferencia de los SNARKs basados en curvas elípticas, los STARKs pueden ser considerados como SNARKs basados en hash. Actualmente, una de las principales razones de la ineficiencia de los STARKs es que en la mayoría de los programas reales, los valores numéricos son pequeños, como índices de bucle, valores booleanos, contadores, etc. Sin embargo, para garantizar la seguridad de las pruebas basadas en árboles de Merkle, al usar codificación de Reed-Solomon para expandir los datos, muchos valores redundantes ocuparán todo el campo, incluso si los valores originales son pequeños. Para resolver este problema, reducir el tamaño del campo se convierte en una estrategia clave.
La primera generación de STARKs tiene un ancho de código de 252 bits, la segunda generación de 64 bits y la tercera generación de 32 bits, pero la codificación de 32 bits aún tiene mucho espacio desperdiciado. En comparación, el campo binario permite operar directamente sobre los bits, con una codificación compacta y eficiente sin desperdicio, lo que se puede considerar como la cuarta generación de STARKs.
En comparación con los campos finitos descubiertos en los últimos años como Goldilocks, BabyBear y Mersenne31, la investigación sobre campos binarios se remonta a la década de 1980. Actualmente, los campos binarios se utilizan ampliamente en criptografía, como en el campo AES(F28, el campo GMAC)F2128, y la codificación Reed-Solomon del código QR(F28, entre otros. Los protocolos FRI originales y zk-STARK, así como la función hash Grøstl, que fue finalista en SHA-3, también se basan en el campo F28.
Al usar dominios más pequeños, 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 asegurar la seguridad y la disponibilidad. La mayoría de los polinomios involucrados en los cálculos de Prover solo necesitan operar en el campo base, logrando así alta eficiencia en el campo pequeño. Sin embargo, la verificación de puntos aleatorios y los cálculos de FRI aún deben realizarse en un campo de extensión más grande para garantizar la seguridad requerida.
Existen dos problemas prácticos al construir un sistema de prueba basado en el dominio binario:
Binius propuso soluciones innovadoras para abordar estos dos problemas:
Este método mejora significativamente la eficiencia de codificación y el rendimiento computacional, al mismo tiempo que garantiza la seguridad.
2 Análisis de principios
Actualmente, la mayoría de los sistemas SNARKs generalmente constan de dos partes:
Prueba de oráculo interactivo polinómico de teoría de la información ( PIOP ): Como núcleo del sistema de prueba, convierte la relación computacional de entrada en ecuaciones polinómicas verificables. A través de la interacción con el verificador, el probador envía polinomios de manera gradual, permitiendo que el verificador valide la corrección del cálculo al consultar una pequeña cantidad de resultados de polinomios. Los protocolos PIOP existentes incluyen PLONK PIOP, Spartan PIOP y HyperPlonk PIOP, entre otros.
Esquema de compromiso polinómico (PCS): Se utiliza para demostrar si se cumplen las igualdades polinómicas generadas por PIOP. PCS es una herramienta criptográfica, el demostrador puede comprometerse a un polinomio y validar su resultado de evaluación más tarde, mientras oculta otra información del polinomio. Los PCS comunes incluyen KZG, Bulletproofs, FRI y Brakedown.
Según las necesidades, elija diferentes PIOP y PCS, y combine con un campo finito o una curva elíptica adecuada para construir un sistema de pruebas con diferentes atributos. Por ejemplo:
Binius incluye cinco tecnologías clave:
Arithmetización basada en el dominio binario en torre: constituye la base del cálculo, implementando operaciones simplificadas en el dominio binario.
Adaptación de la verificación de productos y permutaciones de HyperPlonk: asegurarse de la verificación de consistencia eficiente entre variables y permutaciones.
Nueva prueba de desplazamiento multilineal: optimización de la eficiencia de verificación de relaciones multilineales en pequeños dominios.
Mejorar la demostración de búsqueda de Lasso: proporcionar flexibilidad y seguridad al mecanismo de búsqueda.
Esquema de compromiso de polinomios de pequeño dominio: implementación de un sistema de prueba eficiente sobre un campo binario, reduciendo los costos relacionados con un campo grande.
( 2.1 Campo Finito: 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 la eficiente computación y a la eficientización aritmética. El campo binario, en esencia, soporta operaciones aritméticas altamente eficientes, convirtiéndose en una opción ideal para aplicaciones criptográficas sensibles al rendimiento. La estructura del campo binario soporta un proceso de aritmética simplificada, y las operaciones realizadas en el campo binario pueden representarse en una forma algebraica compacta y fácil de verificar. Estas características, junto con la capacidad de aprovechar completamente sus características jerárquicas a través de la estructura en torre, hacen que el campo binario sea especialmente adecuado para sistemas de prueba escalables como Binius.
"canónico" se refiere a la representación única y directa de los elementos en el campo binario. Por ejemplo, en el campo binario 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 primos, que no pueden proporcionar esta representación canónica dentro de un número determinado de bits. Aunque un campo primo de 32 bits puede caber en 32 bits, no cada cadena de 32 bits puede 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 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 comúnmente utilizados incluyen la reducción especial ) como AES utiliza (, la reducción de Montgomery ) como POLYVAL utiliza ### 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 es necesario introducir acarreo 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 + Y2.
Una cadena de 128 bits se puede interpretar de varias maneras en el contexto de un dominio binario. Puede considerarse como un elemento único en un dominio binario de 128 bits, o descomponerse 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 en el dominio F2. Esta flexibilidad de representación no requiere ningún costo computacional, simplemente una conversión de tipo de cadena de bits, 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 costo computacional adicional. El protocolo Binius aprovecha esta característica para mejorar la eficiencia computacional.
El artículo "On Efficient Inversion in Tower Fields of Characteristic Two" explora la complejidad computacional de realizar operaciones de multiplicación, cuadrado e inversión en un campo binario en torres de n bits donde ( se descompone en un subcampo de m bits ).
( 2.2 PIOP: versión adaptada de HyperPlonk Product y PermutationCheck------aplicable a campos binarios
El diseño de PIOP en el protocolo Binius se inspira en HyperPlonk, utilizando una serie de mecanismos de verificación fundamentales para validar la corrección de polinomios y conjuntos multivariables:
GateCheck: Verifica si el testigo secreto ω y la entrada pública x satisfacen la relación de operación del circuito C)x, ω(=0, asegurando el correcto funcionamiento del circuito.
PermutationCheck: Verificar si los resultados de evaluación de los dos polinomios multivariables f y g en el hipercubo booleano son una relación de permutación f)x### = f(π)x(), asegurando la consistencia de la permutación entre 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: 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: Verificar si la evaluación de un polinomio racional en el hipercubo booleano es igual a un valor declarado ∏x∈Hμ f(x) = s, asegurando la corrección del producto polinómico.
ZeroCheck: Verificar si un polinomio multivariable en un hipercubo booleano es cero en cualquier punto ∏x∈Hμ f(x) = 0, ∀x ∈ Bμ, asegurando la distribución de los ceros del polinomio.
SumCheck: Verificar si la suma de un polinomio multivariable es igual al valor declarado ∑x∈Hμ f(x) = s. Al transformar el problema de evaluación del polinomio multivariable en uno de evaluación de polinomio univariable, se reduce la complejidad computacional del validador. 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 sumas.
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 siempre no nulo en el hipercubo, y que el producto sea igual a un valor específico; Binius simplifica este proceso de verificación al especializar este valor a 1, reduciendo 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 lleva a no poder afirmar que U es no cero en el hipercubo; Binius manejó este problema correctamente, incluso en el caso de que el denominador sea cero, el ProductCheck de Binius también puede continuar procesando, permitiendo la generalización a cualquier valor de producto.
Comprobación de Permutación entre columnas: HyperPlonk no tiene esta función; Binius admite la comprobación de permutación entre varias 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 PIOP SumCheck existente, especialmente al manejar la verificación de polinomios multivariables más complejos, proporcionando un soporte funcional más robusto. Estas mejoras no solo abordan las limitaciones en HyperPlonk, sino que también establecen las bases para futuros sistemas de prueba basados en campos binarios.
( 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 son una de las tecnologías clave, capaces de generar y manipular de manera efectiva polinomios derivados de un identificador de entrada u otros polinomios virtuales. A continuación se presentan dos métodos clave:
Packing: Este método optimiza las operaciones empaquetando elementos más pequeños en posiciones adyacentes de la orden de diccionario en elementos más grandes. El operador Pack se aplica a bloques de tamaño 2κ y los combina en un solo elemento en un dominio de alta dimensión. A través de la Extensión Multilineal ), MLE(, este polinomio virtual puede evaluarse y procesarse de manera eficiente, convirtiendo la función t en otro polinomio, mejorando así el rendimiento computacional.
Operador de desplazamiento: El operador de desplazamiento reorganiza los elementos dentro de un bloque, realizando un desplazamiento cíclico basado en un desplazamiento dado o. Este método es aplicable a bloques de tamaño 2b, donde cada bloque realiza el desplazamiento según el desplazamiento. El operador de desplazamiento se define mediante la detección del soporte de la función, asegurando consistencia y eficiencia al manejar polinomios virtuales. La complejidad de evaluar esta construcción crece linealmente con el tamaño del bloque, siendo especialmente adecuada para procesar grandes conjuntos de datos o en escenas de alta dimensión dentro de hipercubos booleanos.
![Bitlayer Research: Análisis de los principios de Binius STARKs y su pensamiento de optimización])https://img-cdn.gateio.im/webp-social/moments-7f96976952fd0f8da0e93ff1042a966d.webp###
( 2.4 PIOP: versión adaptada del argumento de búsqueda Lasso ------ aplicable a dominios binarios
El protocolo Lasso permite que la parte que prueba comprometa un vector a ∈ Fm y demuestre que todos sus elementos existen en una tabla previamente especificada t ∈ Fn. Lasso desbloquea el concepto de "buscar singularidades")lookup singularities( y puede aplicarse a esquemas de compromiso de polinomios multilineales. Su eficiencia se refleja en los siguientes dos aspectos: