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, como los índices en los bucles for, los valores booleanos, los contadores, etc. Sin embargo, para asegurar la seguridad de las pruebas basadas en árboles de Merkle, al usar codificación de Reed-Solomon para ampliar 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.
Como se muestra en la Tabla 1, el ancho de codificación de la primera generación de STARKs es de 252 bits, el ancho de codificación de la segunda generación de STARKs es de 64 bits, y el ancho de codificación de la tercera generación de STARKs 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 campo binario permite operar directamente sobre los bits, codificando de manera compacta y eficiente sin desperdicio de espacio, es decir, la cuarta generación de STARKs.
Tabla 1: Ruta de derivación de STARKs
En comparación con Goldilocks, BabyBear y Mersenne31, que son descubrimientos recientes en el campo de los cuerpos finitos, la investigación sobre cuerpos binarios se remonta a la década de 1980. Actualmente, los cuerpos 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 mensajes ( GMAC ), basado en el dominio F2128;
Código QR, utiliza codificación Reed-Solomon basada en F28;
Protocolo original FRI 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 hash muy adecuado para la recursión.
Cuando se utilizan campos más pequeños, las operaciones de extensión de campo son cada vez más importantes para garantizar la seguridad. El campo binario utilizado por Binius depende completamente de la extensión de campo para garantizar 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 necesitan operar en el campo base, logrando así una alta eficiencia en campos pequeños. Sin embargo, la verificación de puntos aleatorios y los cálculos FRI aún deben profundizar en un campo de extensión más grande para garantizar la seguridad requerida.
Al construir un sistema de pruebas basado en el dominio binario, existen 2 problemas prácticos: el tamaño del dominio utilizado al calcular la representación del trazo en STARKs 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 de manera separada y representa los mismos datos de dos formas diferentes: primero, utilizando un polinomio multivariable (, específicamente un polinomio multilineal ), en lugar de un polinomio univariable, para representar toda la trayectoria de cálculo a través de sus valores en "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 ), y realizar la extensión de Reed-Solomon basada en ese cuadrado. Este método, al garantizar 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 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 pruebas, transforma la relación computacional 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 validador, de modo que el validador pueda verificar si el cálculo es correcto consultando solo unos pocos resultados de evaluación de polinomios. Los protocolos PIOP existentes incluyen: PIOP PLONK, PIOP Spartan y PIOP HyperPlonk, cada uno de los cuales tiene diferentes enfoques para el tratamiento de expresiones polinómicas, lo que a su vez afecta el rendimiento y la eficiencia de todo el sistema SNARK.
Esquema de Compromiso de Polinomios ( Polynomial Commitment Scheme, PCS ): El esquema de compromiso de polinomios se utiliza para probar 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 luego verificar el resultado de la evaluación de ese polinomio, mientras oculta otra información sobre el polinomio. Los esquemas de compromiso de polinomios 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, elija diferentes PIOP y PCS, y combine con un campo finito o una curva elíptica adecuada, se puede construir un sistema de prueba con diferentes atributos. Por ejemplo:
• Halo2: combina PLONK PIOP y Bulletproofs PCS, y se basa 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: combina PLONK PIOP con FRI PCS y se basa en el dominio de Goldilocks. Plonky2 está diseñado para lograr una recursión eficiente. Al diseñar estos sistemas, la PIOP y la PCS elegidas 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 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 su cálculo, permitiendo realizar operaciones simplificadas en el campo binario. En segundo lugar, Binius adapta la verificación de productos y permutaciones de HyperPlonk en su protocolo de prueba Oracle interactiva (PIOP), asegurando una verificación coherente y segura 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 campos pequeños. Cuarto, Binius utiliza una versión mejorada de la prueba de búsqueda Lasso, proporcionando flexibilidad y una sólida seguridad para el mecanismo de búsqueda. Finalmente, el protocolo utiliza un esquema de compromiso polinómico de campo pequeño (Small-Field PCS), lo que le permite implementar un sistema de prueba eficiente en el campo binario y reducir el gasto normalmente asociado con campos grandes.
( 2.1 Campos finitos: aritmética 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: el cálculo eficiente y la aritmética eficiente. El campo binario soporta esencialmente operaciones aritméticas altamente eficientes, lo que lo convierte en una opción ideal para aplicaciones criptográficas que son sensibles a los requerimientos de rendimiento. Además, la estructura del campo binario apoya un proceso de aritmética simplificado, es decir, las operaciones realizadas sobre el campo binario pueden ser representadas 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 torre, hacen que el campo binario sea especialmente adecuado para sistemas de prueba escalables como Binius.
Donde "canónico" se refiere a la representación única y directa de los elementos en el 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 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 caber 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 primo 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 documento "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" señala que el campo binario no necesita 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 + Y 2.
Como se muestra en la figura 1, una cadena de 128 bits: esta cadena puede interpretarse de varias maneras en el contexto de un campo binario. Puede considerarse un elemento único en un campo binario de 128 bits, o interpretarse como dos elementos de campo de torre de 64 bits, cuatro elementos de campo de torre de 32 bits, 16 elementos de campo de torre de 8 bits, o 128 elementos de campo F2. Esta flexibilidad en la representación no requiere ningún costo computacional, solo un cambio de tipo en la cadena de bits (typecast), lo cual es una propiedad muy interesante y útil. Al mismo tiempo, los elementos de campo pequeños pueden empaquetarse en elementos de campo 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 multiplicación, elevación al cuadrado y operaciones de inversión en un campo de torre binario de n bits ( descomponible en un subcampo de m bits ).
Figura 1: Dominio binario en torre
( 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 basa en HyperPlonk, adoptando una serie de mecanismos de verificación centrales para validar la corrección de polinomios y conjuntos multivariables. Estas verificaciones centrales incluyen:
GateCheck: Verifica si el testigo de confidencialidad ω y la entrada pública x cumplen con 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 el orden de las variables del polinomio.
LookupCheck: verifica 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, para asegurar la corrección del producto polinómico.
ZeroCheck: Verificar si un polinomio multivariable en el hipercubo booleano en cualquier punto es cero ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, para asegurar 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 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 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 no nulo en todas partes del hipercubo, y que el producto sea igual a un valor específico; Binius simplifica este proceso de verificación al especializar este valor en 1, reduciendo así la complejidad computacional.
Manejo del problema de división por cero: HyperPlonk no logró manejar adecuadamente los casos de división por cero, lo que impide afirmar que U es diferente de cero en el hipercubo; Binius manejó este problema correctamente, incluso en el caso de que el denominador sea cero, el ProductCheck de Binius 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 verificación de permutaciones 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 proporcionar 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 sientan las bases para futuros sistemas de prueba basados en campos binarios.
( 2.3 PIOP: nuevo argumento de desplazamiento multilineal------aplicable a
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
5
Republicar
Compartir
Comentar
0/400
BlockchainBard
· hace8h
¡STARKs están ocupando cada vez menos espacio!
Ver originalesResponder0
StakeHouseDirector
· hace8h
¡Optimizar, optimizar, el espacio ocupado sigue siendo demasiado grande!
Ver originalesResponder0
MetaverseLandlord
· hace8h
Solo sé apilar parámetros técnicos, me está mareando.
Ver originalesResponder0
WhaleWatcher
· hace9h
¿Todos los días se habla de mejorar la eficiencia, pero esta eficiencia aún no ha mejorado?
Ver originalesResponder0
AirdropBuffet
· hace9h
Hermano, la optimización es tan feroz, pero aún así no puede competir.
Análisis del principio de Binius STARKs: aplicación innovadora y optimización de la eficiencia 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 ineficiencia 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 asegurar la seguridad de las pruebas basadas en árboles de Merkle, al usar codificación de Reed-Solomon para ampliar 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.
Como se muestra en la Tabla 1, el ancho de codificación de la primera generación de STARKs es de 252 bits, el ancho de codificación de la segunda generación de STARKs es de 64 bits, y el ancho de codificación de la tercera generación de STARKs 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 campo binario permite operar directamente sobre los bits, codificando de manera compacta y eficiente sin desperdicio de espacio, es decir, la cuarta generación de STARKs.
Tabla 1: Ruta de derivación de STARKs
En comparación con Goldilocks, BabyBear y Mersenne31, que son descubrimientos recientes en el campo de los cuerpos finitos, la investigación sobre cuerpos binarios se remonta a la década de 1980. Actualmente, los cuerpos 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 mensajes ( GMAC ), basado en el dominio F2128;
Código QR, utiliza codificación Reed-Solomon basada en F28;
Protocolo original FRI 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 hash muy adecuado para la recursión.
Cuando se utilizan campos más pequeños, las operaciones de extensión de campo son cada vez más importantes para garantizar la seguridad. El campo binario utilizado por Binius depende completamente de la extensión de campo para garantizar 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 necesitan operar en el campo base, logrando así una alta eficiencia en campos pequeños. Sin embargo, la verificación de puntos aleatorios y los cálculos FRI aún deben profundizar en un campo de extensión más grande para garantizar la seguridad requerida.
Al construir un sistema de pruebas basado en el dominio binario, existen 2 problemas prácticos: el tamaño del dominio utilizado al calcular la representación del trazo en STARKs 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 de manera separada y representa los mismos datos de dos formas diferentes: primero, utilizando un polinomio multivariable (, específicamente un polinomio multilineal ), en lugar de un polinomio univariable, para representar toda la trayectoria de cálculo a través de sus valores en "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 ), y realizar la extensión de Reed-Solomon basada en ese cuadrado. Este método, al garantizar 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 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 pruebas, transforma la relación computacional 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 validador, de modo que el validador pueda verificar si el cálculo es correcto consultando solo unos pocos resultados de evaluación de polinomios. Los protocolos PIOP existentes incluyen: PIOP PLONK, PIOP Spartan y PIOP HyperPlonk, cada uno de los cuales tiene diferentes enfoques para el tratamiento de expresiones polinómicas, lo que a su vez afecta el rendimiento y la eficiencia de todo el sistema SNARK.
Esquema de Compromiso de Polinomios ( Polynomial Commitment Scheme, PCS ): El esquema de compromiso de polinomios se utiliza para probar 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 luego verificar el resultado de la evaluación de ese polinomio, mientras oculta otra información sobre el polinomio. Los esquemas de compromiso de polinomios 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, elija diferentes PIOP y PCS, y combine con un campo finito o una curva elíptica adecuada, se puede construir un sistema de prueba con diferentes atributos. Por ejemplo:
• Halo2: combina PLONK PIOP y Bulletproofs PCS, y se basa 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: combina PLONK PIOP con FRI PCS y se basa en el dominio de Goldilocks. Plonky2 está diseñado para lograr una recursión eficiente. Al diseñar estos sistemas, la PIOP y la PCS elegidas 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 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 su cálculo, permitiendo realizar operaciones simplificadas en el campo binario. En segundo lugar, Binius adapta la verificación de productos y permutaciones de HyperPlonk en su protocolo de prueba Oracle interactiva (PIOP), asegurando una verificación coherente y segura 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 campos pequeños. Cuarto, Binius utiliza una versión mejorada de la prueba de búsqueda Lasso, proporcionando flexibilidad y una sólida seguridad para el mecanismo de búsqueda. Finalmente, el protocolo utiliza un esquema de compromiso polinómico de campo pequeño (Small-Field PCS), lo que le permite implementar un sistema de prueba eficiente en el campo binario y reducir el gasto normalmente asociado con campos grandes.
( 2.1 Campos finitos: aritmética 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: el cálculo eficiente y la aritmética eficiente. El campo binario soporta esencialmente operaciones aritméticas altamente eficientes, lo que lo convierte en una opción ideal para aplicaciones criptográficas que son sensibles a los requerimientos de rendimiento. Además, la estructura del campo binario apoya un proceso de aritmética simplificado, es decir, las operaciones realizadas sobre el campo binario pueden ser representadas 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 torre, hacen que el campo binario sea especialmente adecuado para sistemas de prueba escalables como Binius.
Donde "canónico" se refiere a la representación única y directa de los elementos en el 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 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 caber 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 primo 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 documento "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" señala que el campo binario no necesita 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 + Y 2.
Como se muestra en la figura 1, una cadena de 128 bits: esta cadena puede interpretarse de varias maneras en el contexto de un campo binario. Puede considerarse un elemento único en un campo binario de 128 bits, o interpretarse como dos elementos de campo de torre de 64 bits, cuatro elementos de campo de torre de 32 bits, 16 elementos de campo de torre de 8 bits, o 128 elementos de campo F2. Esta flexibilidad en la representación no requiere ningún costo computacional, solo un cambio de tipo en la cadena de bits (typecast), lo cual es una propiedad muy interesante y útil. Al mismo tiempo, los elementos de campo pequeños pueden empaquetarse en elementos de campo 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 multiplicación, elevación al cuadrado y operaciones de inversión en un campo de torre binario de n bits ( descomponible en un subcampo de m bits ).
Figura 1: Dominio binario en torre
( 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 basa en HyperPlonk, adoptando una serie de mecanismos de verificación centrales para validar la corrección de polinomios y conjuntos multivariables. Estas verificaciones centrales incluyen:
GateCheck: Verifica si el testigo de confidencialidad ω y la entrada pública x cumplen con 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 el orden de las variables del polinomio.
LookupCheck: verifica 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, para asegurar la corrección del producto polinómico.
ZeroCheck: Verificar si un polinomio multivariable en el hipercubo booleano en cualquier punto es cero ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, para asegurar 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 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 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 no nulo en todas partes del hipercubo, y que el producto sea igual a un valor específico; Binius simplifica este proceso de verificación al especializar este valor en 1, reduciendo así la complejidad computacional.
Manejo del problema de división por cero: HyperPlonk no logró manejar adecuadamente los casos de división por cero, lo que impide afirmar que U es diferente de cero en el hipercubo; Binius manejó este problema correctamente, incluso en el caso de que el denominador sea cero, el ProductCheck de Binius 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 verificación de permutaciones 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 proporcionar 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 sientan las bases para futuros sistemas de prueba basados en campos binarios.
( 2.3 PIOP: nuevo argumento de desplazamiento multilineal------aplicable a