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 se pueden considerar como SNARKs basados en hash. Una de las principales razones de la baja eficiencia de los STARKs en la actualidad es que la mayoría de los valores numéricos en programas reales son bastante pequeños, como índices en bucles for, 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 de redundancia adicionales ocuparán todo el dominio, incluso si los valores originales son muy pequeños. Para resolver este problema, reducir el tamaño del dominio se ha convertido en una estrategia clave.
La anchura de codificación de los STARKs de primera generación es de 252 bits, la de segunda generación es de 64 bits y la de tercera generación es de 32 bits, pero la anchura de codificación de 32 bits aún presenta un gran desperdicio de espacio. En comparación, el dominio binario permite operar directamente sobre los bits, codificando de manera compacta y eficiente sin ningún desperdicio de espacio, lo que puede considerarse como la cuarta generación de STARKs.
En comparación con los campos finitos descubiertos en investigaciones recientes 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, ejemplos típicos incluyen:
Estándar de Cifrado Avanzado ( AES ), basado en el dominio F28
Código de autenticación de mensajes Galois ( GMAC ), basado en el dominio 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 extensión del dominio se vuelve cada vez más importante para garantizar la seguridad. El dominio binario utilizado por Binius debe depender completamente de la extensión del dominio para garantizar su seguridad y utilidad práctica. La mayoría de los polinomios involucrados en los cálculos de Prover no necesitan entrar en la extensión del dominio, sino que operan solo en el campo base, logrando así una alta eficiencia en el dominio pequeño. Sin embargo, la verificación de puntos aleatorios y los cálculos de FRI aún deben profundizar en un dominio 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, es necesario 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 ( que es un polinomio multilineal ) 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 la longitud de cada dimensión del hipercubo es 2, no se puede realizar una expansión estándar de Reed-Solomon como en STARKs, pero se puede considerar el hipercubo como un cuadrado ), y realizar la expansión de Reed-Solomon basada en ese cuadrado. Este método, al tiempo que asegura la seguridad, mejora enormemente la eficiencia de codificación y el rendimiento computacional.
2 Análisis de principios
La mayoría de los sistemas SNARKs actuales suelen incluir 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 las relaciones computacionales de entrada en ecuaciones polinómicas verificables. Diferentes protocolos PIOP permiten al probador enviar polinomios de forma 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: PLONK PIOP, Spartan PIOP y HyperPlonk PIOP, cada uno de los cuales tiene diferentes enfoques para el manejo de expresiones polinómicas, lo que afecta el rendimiento y la eficiencia de todo el sistema SNARK.
Esquema de Compromiso Polinómico (Polynomial Commitment Scheme, PCS): El esquema de compromiso polinómico se utiliza para probar si una ecuación polinómica generada por PIOP es válida. PCS es una herramienta criptográfica que permite al probador comprometerse con un polinomio y verificar más tarde 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, niveles de seguridad y escenarios de aplicación.
Según las necesidades específicas, elija diferentes PIOP y PCS, y combine con el campo finito o la curva elíptica adecuados, se puede construir un sistema de pruebas con diferentes atributos. Por ejemplo:
• Halo2: combina PLONK PIOP y Bulletproofs PCS, y se basa en la curva Pasta. Al diseñar Halo2, se presta atención a la escalabilidad y se elimina el trusted setup del protocolo ZCash.
• Plonky2: utiliza PLONK PIOP combinado con FRI PCS, y se basa en el dominio de Goldilocks. Plonky2 se diseñó para lograr una recursividad eficiente. Al diseñar estos sistemas, la PIOP y el PCS seleccionados 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 y la eficiencia de verificación de SNARK, sino que también determina si el sistema puede lograr transparencia sin necesidad de una configuración confiable, y si puede soportar funciones de extensión como pruebas recursivas o pruebas de agregación.
Binius: HyperPlonk PIOP + Brakedown PCS + dominios binarios. En concreto, Binius incluye cinco tecnologías clave para lograr su eficiencia y seguridad. Primero, la aritmética basada en torres de dominios binarios (towers of binary fields) constituye la base de su computación, permitiendo realizar operaciones simplificadas dentro del dominio 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 multilineal, optimizando la eficiencia de la verificación de relaciones multilineales en pequeños dominios. Cuarto, Binius utiliza una versión mejorada de la prueba de búsqueda Lasso, proporcionando flexibilidad y una fuerte seguridad al mecanismo de búsqueda. Finalmente, el protocolo utiliza un esquema de compromiso polinómico de pequeños dominios (Small-Field PCS), lo que le permite implementar un sistema de prueba eficiente en el dominio binario y reducir los costos normalmente asociados con grandes dominios.
( 2.1 Campo finito: 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 al rendimiento. Además, la estructura de los campos binarios soporta 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 sus características jerárquicas a través de la estructura en 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 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 determinado de bits. Aunque un campo primo de 32 bits puede estar contenido en 32 bits, no todas las cadenas de 32 bits pueden corresponder de manera única a un elemento del campo, mientras que el campo binario tiene esta conveniencia de mapeo uno a uno. En el campo 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 usa en AES ###, la reducción de Montgomery ( como se usa 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 porque 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 campo binario. Puede considerarse un elemento único en un campo binario de 128 bits, o puede descomponerse en 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 del campo 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 campo pequeño 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 realizar multiplicaciones, cuadrados e inversiones en un campo de torre binario de n bits que ( puede descomponerse en subcampos de m bits ).
( 2.2 PIOP: versión adaptada de HyperPlonk Product y PermutationCheck------aplicable al campo binario
El diseño de PIOP en el protocolo Binius se basa en HyperPlonk y utiliza una serie de mecanismos de verificación clave para validar la corrección de polinomios y conjuntos multivariables. Estas verificaciones clave 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 el correcto funcionamiento del circuito.
PermutationCheck: Verificar si los resultados de evaluación de dos polinomios multivariables f y g en el hipercubo booleano forman una relación de permutación f(x) = f(π)x((, para asegurar la consistencia de las permutaciones 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, para asegurar la corrección del producto del polinomio.
ZeroCheck: Verificar si un polinomio multivariable en un hipercubo booleano en un punto arbitrario es cero ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, para garantizar la distribución de los ceros del polinomio.
SumCheck: Detecta 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 la evaluación de polinomios univariables, se reduce la complejidad computacional del 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 distinto 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 a 1, reduciendo así la complejidad de cálculo.
Manejo del problema de división por cero: HyperPlonk no pudo manejar adecuadamente los casos de división por cero, lo que lleva 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 puede continuar procesando, permitiendo la generalización a cualquier valor de producto.
Comprobación de Permutación de columnas: HyperPlonk no tiene esta funcionalidad; Binius admite la comprobación de permutación entre múltiples columnas, lo que permite a Binius manejar situaciones de permutación polinómica más complejas.
Por lo tanto, Binius ha mejorado la flexibilidad y eficiencia del protocolo mediante la mejora del mecanismo existente PIOPSumCheck, especialmente al manejar la verificación de polinomios multivariables más complejos, proporcionando un soporte funcional más fuerte. Estas mejoras no solo resuelven las limitaciones de HyperPlonk, sino que también sientan las bases para futuros sistemas de prueba basados en dominios 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 es una de las tecnologías clave, capaz de generar y operar de manera efectiva los múltiplos derivados de un manejador de entrada u otros polinomios virtuales.
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.
Análisis de los principios de Binius STARKs: Innovación en el dominio binario y optimización del rendimiento
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 se pueden considerar como SNARKs basados en hash. Una de las principales razones de la baja eficiencia de los STARKs en la actualidad es que la mayoría de los valores numéricos en programas reales son bastante pequeños, como índices en bucles for, 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 de redundancia adicionales ocuparán todo el dominio, incluso si los valores originales son muy pequeños. Para resolver este problema, reducir el tamaño del dominio se ha convertido en una estrategia clave.
La anchura de codificación de los STARKs de primera generación es de 252 bits, la de segunda generación es de 64 bits y la de tercera generación es de 32 bits, pero la anchura de codificación de 32 bits aún presenta un gran desperdicio de espacio. En comparación, el dominio binario permite operar directamente sobre los bits, codificando de manera compacta y eficiente sin ningún desperdicio de espacio, lo que puede considerarse como la cuarta generación de STARKs.
En comparación con los campos finitos descubiertos en investigaciones recientes 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, ejemplos típicos incluyen:
Cuando se utilizan dominios más pequeños, la operación de extensión del dominio se vuelve cada vez más importante para garantizar la seguridad. El dominio binario utilizado por Binius debe depender completamente de la extensión del dominio para garantizar su seguridad y utilidad práctica. La mayoría de los polinomios involucrados en los cálculos de Prover no necesitan entrar en la extensión del dominio, sino que operan solo en el campo base, logrando así una alta eficiencia en el dominio pequeño. Sin embargo, la verificación de puntos aleatorios y los cálculos de FRI aún deben profundizar en un dominio 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, es necesario 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 ( que es un polinomio multilineal ) 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 la longitud de cada dimensión del hipercubo es 2, no se puede realizar una expansión estándar de Reed-Solomon como en STARKs, pero se puede considerar el hipercubo como un cuadrado ), y realizar la expansión de Reed-Solomon basada en ese cuadrado. Este método, al tiempo que asegura la seguridad, mejora enormemente la eficiencia de codificación y el rendimiento computacional.
2 Análisis de principios
La mayoría de los sistemas SNARKs actuales suelen incluir 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 las relaciones computacionales de entrada en ecuaciones polinómicas verificables. Diferentes protocolos PIOP permiten al probador enviar polinomios de forma 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: PLONK PIOP, Spartan PIOP y HyperPlonk PIOP, cada uno de los cuales tiene diferentes enfoques para el manejo de expresiones polinómicas, lo que afecta el rendimiento y la eficiencia de todo el sistema SNARK.
Esquema de Compromiso Polinómico (Polynomial Commitment Scheme, PCS): El esquema de compromiso polinómico se utiliza para probar si una ecuación polinómica generada por PIOP es válida. PCS es una herramienta criptográfica que permite al probador comprometerse con un polinomio y verificar más tarde 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, niveles de seguridad y escenarios de aplicación.
Según las necesidades específicas, elija diferentes PIOP y PCS, y combine con el campo finito o la curva elíptica adecuados, se puede construir un sistema de pruebas con diferentes atributos. Por ejemplo:
• Halo2: combina PLONK PIOP y Bulletproofs PCS, y se basa en la curva Pasta. Al diseñar Halo2, se presta atención a la escalabilidad y se elimina el trusted setup del protocolo ZCash.
• Plonky2: utiliza PLONK PIOP combinado con FRI PCS, y se basa en el dominio de Goldilocks. Plonky2 se diseñó para lograr una recursividad eficiente. Al diseñar estos sistemas, la PIOP y el PCS seleccionados 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 y la eficiencia de verificación de SNARK, sino que también determina si el sistema puede lograr transparencia sin necesidad de una configuración confiable, y si puede soportar funciones de extensión como pruebas recursivas o pruebas de agregación.
Binius: HyperPlonk PIOP + Brakedown PCS + dominios binarios. En concreto, Binius incluye cinco tecnologías clave para lograr su eficiencia y seguridad. Primero, la aritmética basada en torres de dominios binarios (towers of binary fields) constituye la base de su computación, permitiendo realizar operaciones simplificadas dentro del dominio 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 multilineal, optimizando la eficiencia de la verificación de relaciones multilineales en pequeños dominios. Cuarto, Binius utiliza una versión mejorada de la prueba de búsqueda Lasso, proporcionando flexibilidad y una fuerte seguridad al mecanismo de búsqueda. Finalmente, el protocolo utiliza un esquema de compromiso polinómico de pequeños dominios (Small-Field PCS), lo que le permite implementar un sistema de prueba eficiente en el dominio binario y reducir los costos normalmente asociados con grandes dominios.
( 2.1 Campo finito: 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 al rendimiento. Además, la estructura de los campos binarios soporta 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 sus características jerárquicas a través de la estructura en 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 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 determinado de bits. Aunque un campo primo de 32 bits puede estar contenido en 32 bits, no todas las cadenas de 32 bits pueden corresponder de manera única a un elemento del campo, mientras que el campo binario tiene esta conveniencia de mapeo uno a uno. En el campo 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 usa en AES ###, la reducción de Montgomery ( como se usa 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 porque 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 campo binario. Puede considerarse un elemento único en un campo binario de 128 bits, o puede descomponerse en 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 del campo 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 campo pequeño 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 realizar multiplicaciones, cuadrados e inversiones en un campo de torre binario de n bits que ( puede descomponerse en subcampos de m bits ).
( 2.2 PIOP: versión adaptada de HyperPlonk Product y PermutationCheck------aplicable al campo binario
El diseño de PIOP en el protocolo Binius se basa en HyperPlonk y utiliza una serie de mecanismos de verificación clave para validar la corrección de polinomios y conjuntos multivariables. Estas verificaciones clave 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 el correcto funcionamiento del circuito.
PermutationCheck: Verificar si los resultados de evaluación de dos polinomios multivariables f y g en el hipercubo booleano forman una relación de permutación f(x) = f(π)x((, para asegurar la consistencia de las permutaciones 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, para asegurar la corrección del producto del polinomio.
ZeroCheck: Verificar si un polinomio multivariable en un hipercubo booleano en un punto arbitrario es cero ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, para garantizar la distribución de los ceros del polinomio.
SumCheck: Detecta 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 la evaluación de polinomios univariables, se reduce la complejidad computacional del 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 distinto 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 a 1, reduciendo así la complejidad de cálculo.
Manejo del problema de división por cero: HyperPlonk no pudo manejar adecuadamente los casos de división por cero, lo que lleva 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 puede continuar procesando, permitiendo la generalización a cualquier valor de producto.
Comprobación de Permutación de columnas: HyperPlonk no tiene esta funcionalidad; Binius admite la comprobación de permutación entre múltiples columnas, lo que permite a Binius manejar situaciones de permutación polinómica más complejas.
Por lo tanto, Binius ha mejorado la flexibilidad y eficiencia del protocolo mediante la mejora del mecanismo existente PIOPSumCheck, especialmente al manejar la verificación de polinomios multivariables más complejos, proporcionando un soporte funcional más fuerte. Estas mejoras no solo resuelven las limitaciones de HyperPlonk, sino que también sientan las bases para futuros sistemas de prueba basados en dominios 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 es una de las tecnologías clave, capaz de generar y operar de manera efectiva los múltiplos derivados de un manejador de entrada u otros polinomios virtuales.