Análisis de los principios de Binius STARKs y reflexiones sobre su optimización
1 Introducción
Una de las principales razones por las que la eficiencia de STARKs es baja es que la mayoría de los valores en los programas reales son 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 expandir los datos utilizando codificación de Reed-Solomon, 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 los STARKs de primera generación es de 252 bits, el ancho de codificación de los STARKs de segunda generación es de 64 bits, y el ancho de codificación de los STARKs de tercera generación es de 32 bits, pero el ancho de codificación de 32 bits todavía tiene un gran espacio desperdiciado. En comparación, el campo binario permite operar directamente sobre los bits, con una codificación compacta y eficiente sin ningún espacio desperdiciado, es decir, los STARKs de cuarta generación.
En comparación con Goldilocks, BabyBear, Mersenne31 y otros descubrimientos recientes en campos finitos en los últimos años, la investigación sobre 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 mensajes ( GMAC ), basado en el campo F2128;
Código QR, utilizando 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 ampliación de dominio se vuelve cada vez más importante para garantizar la seguridad. El dominio binario utilizado por Binius depende completamente de la ampliación de dominio para asegurar su seguridad y usabilidad práctica. La mayoría de los polinomios involucrados en los cálculos de Prover no necesitan entrar en la ampliación de dominio, sino que operan solo en el dominio base, logrando así alta eficiencia en dominios pequeños. Sin embargo, la verificación de puntos aleatorios y el cálculo de FRI aún deben profundizarse en un dominio de ampliación más grande para garantizar la seguridad requerida.
Al construir un sistema de pruebas basado en un campo binario, existen 2 problemas prácticos: al calcular la representación de la traza en STARKs, el tamaño del campo 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 campo 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 logra representar los mismos datos de dos maneras diferentes: primero, utilizando un polinomio multivariable ( específicamente un polinomio multilineal ) 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 los 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 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 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 incremental 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 tiene un enfoque diferente para el manejo de expresiones polinómicas, afectando así el rendimiento y la eficiencia del sistema SNARK en su conjunto.
Esquema de Compromiso Polinómico ( Polynomial Commitment Scheme, PCS ): El esquema de compromiso polinómico se utiliza para probar si se cumple una igualdad polinómica generada por PIOP. El PCS es una herramienta criptográfica que permite al probador comprometerse a un polinomio y verificar posteriormente el resultado de la evaluación de ese polinomio, mientras 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, elija diferentes PIOP y PCS, y combine con un campo finito o una curva elíptica adecuados, se puede construir un sistema de pruebas con diferentes atributos. Por ejemplo:
• Halo2: combina PLONK PIOP con Bulletproofs PCS, y se basa en la curva Pasta. Halo2 se diseñó con un enfoque en la escalabilidad y en eliminar el trusted setup del protocolo ZCash.
• Plonky2: combina PLONK PIOP con FRI PCS y se basa en el dominio de Goldilocks. Plonky2 está diseñado para lograr recursividad eficiente. Al diseñar estos sistemas, la PIOP y el PCS elegidos deben coincidir con el campo finito o la curva elíptica utilizados 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 requerir una configuración confiable, así como si puede soportar funciones de extensión como pruebas recursivas o pruebas agregadas.
Binius: HyperPlonk PIOP + Brakedown PCS + dominio binario. 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 de Oracle interactivo (PIOP), asegurando una verificación consistente y segura entre las variables y sus permutaciones. Tercero, el protocolo introduce una nueva prueba de desplazamiento multilinéal, optimizando la eficiencia de la verificación de relaciones multilinales en campos pequeños. 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. Finalmente, el protocolo emplea 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 reduce los costos generalmente asociados con campos grandes.
( 2.1 Campos finitos: aritmética basada en torres de campos binarios
Los campos binarios en torre son clave para implementar cálculos rápidos y verificables, principalmente debido a dos aspectos: cálculos eficientes y aritmética eficiente. Los campos binarios, en esencia, soportan operaciones aritméticas altamente eficientes, lo que los convierte en una elección ideal para aplicaciones criptográficas sensibles a los requisitos de rendimiento. Además, la estructura de los campos binarios apoya un proceso de aritmética simplificado, es decir, 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 plenamente su naturaleza jerárquica a través de la estructura de torre, hacen que los campos binarios sean particularmente adecuados para sistemas de prueba escalables como Binius.
El término "canónico" se refiere a la representación única y directa de un elemento 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 de 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 el 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 ) 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 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 + Y 2.
Como se muestra en la Figura 1, una cadena de 128 bits: esta cadena puede interpretarse de varias maneras en el contexto del dominio binario. Puede considerarse un elemento único en un dominio binario de 128 bits, o puede descomponerse en dos elementos de dominio de torre de 64 bits, cuatro elementos de dominio de torre de 32 bits, dieciséis 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 cadena de bits (typecast), lo cual es una propiedad muy interesante y útil. Al mismo tiempo, los elementos de dominio pequeños pueden empaquetarse 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 la multiplicación, el cuadrado y la operación de inversión en dominios de torre binaria de n bits ( descompuestos en subdominios de m bits ).
Figura 1: Dominio binario en torre
( 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 centrales para validar la corrección de los polinomios y conjuntos multivariables. Estas verificaciones centrales incluyen:
GateCheck: Verifica si el testigo privado ω 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 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: Verifica 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 del polinomio.
ZeroCheck: Verificar si un polinomio multivariable en el hipercubo booleano en un punto arbitrario es cero ∏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 polinomios multivariables en uno de evaluación de polinomios univariables, se reduce la complejidad computacional para el verificador. Además, SumCheck 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 la división por cero: HyperPlonk no pudo manejar adecuadamente el caso de la división por cero, lo que llevó a no poder afirmar el problema de que U es no nulo 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 generalización a cualquier valor de producto.
Comprobación de Permutación de Filas: HyperPlonk no tiene esta función; Binius admite la verificación de permutación entre varias columnas, lo que permite a Binius manejar situaciones más complejas de arreglos polinómicos.
Por lo tanto, Binius ha mejorado la flexibilidad y eficiencia del protocolo a través de la mejora del mecanismo PIOPSumCheck existente, especialmente al manejar la verificación de polinomios multivariables más complejos, proporcionando un soporte funcional más sólido. Estas mejoras no solo abordan 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 al hipercubo booleano
En el protocolo Binius, la construcción y el manejo de polinomios virtuales son importantes.
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.
11 me gusta
Recompensa
11
6
Compartir
Comentar
0/400
MissedTheBoat
· hace18h
¡La compacidad es el camino! ¡Caída en paracaídas!
Ver originalesResponder0
GasBandit
· 08-05 20:35
¿Y cómo se te ocurrió optimizar starks?
Ver originalesResponder0
CryptoComedian
· 08-05 20:35
Escribir la tesis de ancho de presión, he escrito tres generaciones y no he cumplido con los estándares.
Ver originalesResponder0
BlockchainThinkTank
· 08-05 20:23
Creemos que la optimización de zkp aún se encuentra en una etapa temprana, por lo que se debe tener precaución al considerar este tipo de soluciones para mejorar la eficiencia.
Ver originalesResponder0
MentalWealthHarvester
· 08-05 20:17
Otra vez es la época dorada de mis grandes STARKs, aún se puede seguir excavando.
Ver originalesResponder0
LayoffMiner
· 08-05 20:08
¿En qué estás pensando? El gas no puede bajar y aún así lo complican tanto.
Nueva idea de optimización de STARKs: Binius impulsa el desarrollo del dominio binario
Análisis de los principios de Binius STARKs y reflexiones sobre su optimización
1 Introducción
Una de las principales razones por las que la eficiencia de STARKs es baja es que la mayoría de los valores en los programas reales son 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 expandir los datos utilizando codificación de Reed-Solomon, 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 los STARKs de primera generación es de 252 bits, el ancho de codificación de los STARKs de segunda generación es de 64 bits, y el ancho de codificación de los STARKs de tercera generación es de 32 bits, pero el ancho de codificación de 32 bits todavía tiene un gran espacio desperdiciado. En comparación, el campo binario permite operar directamente sobre los bits, con una codificación compacta y eficiente sin ningún espacio desperdiciado, es decir, los STARKs de cuarta generación.
| Tiempo | STARKs | Ancho de codificación | |------|--------|----------| | 2018 | Primera generación | 252bit | | 2021 | Segunda generación | 64bit | | 2022 | Tercera generación | 32bit | | 2023 | 4ª generación | 1bit |
Tabla 1: Ruta de derivación de STARKs
En comparación con Goldilocks, BabyBear, Mersenne31 y otros descubrimientos recientes en campos finitos en los últimos años, la investigación sobre 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 mensajes ( GMAC ), basado en el campo F2128;
Código QR, utilizando 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 ampliación de dominio se vuelve cada vez más importante para garantizar la seguridad. El dominio binario utilizado por Binius depende completamente de la ampliación de dominio para asegurar su seguridad y usabilidad práctica. La mayoría de los polinomios involucrados en los cálculos de Prover no necesitan entrar en la ampliación de dominio, sino que operan solo en el dominio base, logrando así alta eficiencia en dominios pequeños. Sin embargo, la verificación de puntos aleatorios y el cálculo de FRI aún deben profundizarse en un dominio de ampliación más grande para garantizar la seguridad requerida.
Al construir un sistema de pruebas basado en un campo binario, existen 2 problemas prácticos: al calcular la representación de la traza en STARKs, el tamaño del campo 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 campo 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 logra representar los mismos datos de dos maneras diferentes: primero, utilizando un polinomio multivariable ( específicamente un polinomio multilineal ) 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 los 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 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 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 incremental 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 tiene un enfoque diferente para el manejo de expresiones polinómicas, afectando así el rendimiento y la eficiencia del sistema SNARK en su conjunto.
Esquema de Compromiso Polinómico ( Polynomial Commitment Scheme, PCS ): El esquema de compromiso polinómico se utiliza para probar si se cumple una igualdad polinómica generada por PIOP. El PCS es una herramienta criptográfica que permite al probador comprometerse a un polinomio y verificar posteriormente el resultado de la evaluación de ese polinomio, mientras 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, elija diferentes PIOP y PCS, y combine con un campo finito o una curva elíptica adecuados, se puede construir un sistema de pruebas con diferentes atributos. Por ejemplo:
• Halo2: combina PLONK PIOP con Bulletproofs PCS, y se basa en la curva Pasta. Halo2 se diseñó con un enfoque en la escalabilidad y en eliminar el trusted setup del protocolo ZCash.
• Plonky2: combina PLONK PIOP con FRI PCS y se basa en el dominio de Goldilocks. Plonky2 está diseñado para lograr recursividad eficiente. Al diseñar estos sistemas, la PIOP y el PCS elegidos deben coincidir con el campo finito o la curva elíptica utilizados 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 requerir una configuración confiable, así como si puede soportar funciones de extensión como pruebas recursivas o pruebas agregadas.
Binius: HyperPlonk PIOP + Brakedown PCS + dominio binario. 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 de Oracle interactivo (PIOP), asegurando una verificación consistente y segura entre las variables y sus permutaciones. Tercero, el protocolo introduce una nueva prueba de desplazamiento multilinéal, optimizando la eficiencia de la verificación de relaciones multilinales en campos pequeños. 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. Finalmente, el protocolo emplea 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 reduce los costos generalmente asociados con campos grandes.
( 2.1 Campos finitos: aritmética basada en torres de campos binarios
Los campos binarios en torre son clave para implementar cálculos rápidos y verificables, principalmente debido a dos aspectos: cálculos eficientes y aritmética eficiente. Los campos binarios, en esencia, soportan operaciones aritméticas altamente eficientes, lo que los convierte en una elección ideal para aplicaciones criptográficas sensibles a los requisitos de rendimiento. Además, la estructura de los campos binarios apoya un proceso de aritmética simplificado, es decir, 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 plenamente su naturaleza jerárquica a través de la estructura de torre, hacen que los campos binarios sean particularmente adecuados para sistemas de prueba escalables como Binius.
El término "canónico" se refiere a la representación única y directa de un elemento 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 de 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 el 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 ) 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 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 + Y 2.
Como se muestra en la Figura 1, una cadena de 128 bits: esta cadena puede interpretarse de varias maneras en el contexto del dominio binario. Puede considerarse un elemento único en un dominio binario de 128 bits, o puede descomponerse en dos elementos de dominio de torre de 64 bits, cuatro elementos de dominio de torre de 32 bits, dieciséis 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 cadena de bits (typecast), lo cual es una propiedad muy interesante y útil. Al mismo tiempo, los elementos de dominio pequeños pueden empaquetarse 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 la multiplicación, el cuadrado y la operación de inversión en dominios de torre binaria de n bits ( descompuestos en subdominios de m bits ).
Figura 1: Dominio binario en torre
( 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 centrales para validar la corrección de los polinomios y conjuntos multivariables. Estas verificaciones centrales incluyen:
GateCheck: Verifica si el testigo privado ω 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 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: Verifica 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 del polinomio.
ZeroCheck: Verificar si un polinomio multivariable en el hipercubo booleano en un punto arbitrario es cero ∏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 polinomios multivariables en uno de evaluación de polinomios univariables, se reduce la complejidad computacional para el verificador. Además, SumCheck 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 la división por cero: HyperPlonk no pudo manejar adecuadamente el caso de la división por cero, lo que llevó a no poder afirmar el problema de que U es no nulo 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 generalización a cualquier valor de producto.
Comprobación de Permutación de Filas: HyperPlonk no tiene esta función; Binius admite la verificación de permutación entre varias columnas, lo que permite a Binius manejar situaciones más complejas de arreglos polinómicos.
Por lo tanto, Binius ha mejorado la flexibilidad y eficiencia del protocolo a través de la mejora del mecanismo PIOPSumCheck existente, especialmente al manejar la verificación de polinomios multivariables más complejos, proporcionando un soporte funcional más sólido. Estas mejoras no solo abordan 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 al hipercubo booleano
En el protocolo Binius, la construcción y el manejo de polinomios virtuales son importantes.