Análisis de los principios de Binius STARKs y reflexiones sobre su optimización
1 Introducción
Una de las principales razones de la baja eficiencia de STARKs es que la mayoría de los valores en los programas reales son bastante pequeños, como los índices en bucles for, valores booleanos, contadores, etc. Sin embargo, para garantizar la seguridad de las pruebas basadas en árboles de Merkle, al ampliar los datos utilizando codificación de Reed-Solomon, muchos valores redundantes adicionales ocupan todo el campo, incluso si el valor original 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, 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 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 ningún desperdicio de espacio, es decir, los STARKs de cuarta generación.
En comparación con Goldilocks, BabyBear, Mersenne31 y otros campos finitos descubiertos 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;
Código de autenticación de mensajes Galois ( GMAC ), basado en el campo F2128;
Código QR, utiliza codificación Reed-Solomon basada en F28;
Protocolo FRI original y zk-STARK, así como la función hash Grøstl, que llegó a la final de SHA-3, basada en el campo F28, es un algoritmo de hash muy adecuado para la recursión.
Cuando se utilizan campos más pequeños, la operación de extensión de campo se vuelve cada vez más importante para garantizar la seguridad. El campo binario utilizado por Binius depende completamente de la extensión de campo para 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 operan en el campo base, logrando así alta eficiencia en campos pequeños. Sin embargo, la verificación de puntos aleatorios y el cálculo 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: al calcular la representación de trace en STARKs, el tamaño del dominio utilizado debe ser mayor que el grado del polinomio; al comprometer el árbol de Merkle en STARKs, se debe realizar la codificación de Reed-Solomon, y el tamaño del dominio utilizado debe ser mayor que el tamaño después de la expansión de 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 polinomios multilineales en lugar de polinomios univariados, 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 extensión estándar de Reed-Solomon como en STARKs, pero se puede considerar el hipercubo como un cuadrado, basando la extensión de Reed-Solomon 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 núcleo del sistema de pruebas, transforma las relaciones computacionales de entrada en ecuaciones polinómicas verificables. Diferentes protocolos PIOP permiten al probador enviar polinomios progresivamente a través de la interacción con el validador, de modo que el validador puede verificar si el cálculo es correcto al consultar los resultados de la evaluación de unos pocos polinomios. Los protocolos PIOP existentes incluyen: PLONK PIOP, Spartan PIOP y HyperPlonk PIOP, cada uno de los cuales maneja las expresiones polinómicas de manera diferente, lo que afecta el rendimiento y la eficiencia de todo el sistema SNARK.
Esquema de Compromiso Polinómico ( Polynomial Commitment Scheme, PCS ): El esquema de compromiso polinómico se utiliza para probar si 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 verificar más tarde el resultado de la evaluación de ese polinomio, mientras oculta otra información sobre el 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 un campo finito o una curva elíptica adecuada, 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. Halo2 se diseñó con un enfoque en la escalabilidad y en eliminar la configuración confiable del protocolo ZCash.
Plonky2: utiliza PLONK PIOP combinado con FRI PCS y se basa en el dominio de Goldilocks. Plonky2 está diseñado para lograr una recursividad eficiente. Al diseñar estos sistemas, la PIOP y la PCS seleccionadas deben coincidir con el campo finito o la curva elíptica utilizada para garantizar la corrección, el rendimiento y la seguridad del sistema. La elección de estas combinaciones no solo afecta el tamaño de la prueba SNARK y la eficiencia de la verificación, sino que también determina si el sistema puede lograr transparencia sin necesidad de una configuración confiable y si puede soportar funciones extensibles 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 sus cálculos, permitiendo realizar operaciones simplificadas en el dominio binario. En segundo lugar, Binius adapta la verificación de productos y permutaciones de HyperPlonk en su protocolo de prueba Oracle interactivo (PIOP), asegurando una verificación de consistencia segura y eficiente entre las variables y sus permutaciones. En tercer lugar, 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. Por último, el protocolo utiliza un esquema de compromiso polinómico de pequeño dominio (Small-Field PCS), lo que le permite implementar un sistema de pruebas 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
El campo binario en torre es clave para implementar cálculos verificables rápidos, principalmente debido a dos aspectos: cálculos eficientes y aritmética eficiente. El campo binario, en esencia, admite operaciones aritméticas altamente eficientes, lo que lo convierte en una opción ideal para aplicaciones criptográficas que son sensibles al rendimiento. Además, la estructura del campo binario admite un proceso de aritmética simplificada, es decir, las operaciones realizadas en el campo binario pueden expresarse 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 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 elementos en el dominio binario. Por ejemplo, en el dominio binario más básico F2, cualquier cadena de longitud k se puede mapear directamente a un elemento del dominio binario de k bits. Esto es diferente del dominio primo, que no puede proporcionar esta representación canónica dentro de un número fijo de bits. Aunque el dominio primo de 32 bits puede caber en 32 bits, no cada cadena de 32 bits puede corresponder de manera única a un elemento del dominio, mientras que el dominio binario tiene esta conveniencia de mapeo uno a uno. En el dominio 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 dominios finitos específicos como Mersenne-31 o Goldilocks-64. En el dominio 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 usa en POLYVAL (, y la reducción recursiva ), como en Tower ###. El artículo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" señala que en el dominio binario no se necesita introducir acarreo en las operaciones de suma y multiplicación, y que la operación de cuadrado en el dominio binario es muy eficiente, ya que sigue la regla simplificada (X + Y )2 = X2 + Y 2.
Como se muestra en la Figura 1, una cadena de 128 bits: esta cadena se puede interpretar de varias maneras en el contexto de un dominio binario. Puede considerarse como 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, 16 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 realizar multiplicación, elevación al cuadrado y operaciones de inversión en un dominio de torre binario de n bits ( descomponible en un subdominio de m bits ).
( 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 inspira 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: Verificar si el testigo confidencial ω y la entrada pública x satisfacen la relación de operación del circuito C)x,ω(=0, para asegurar el correcto funcionamiento del circuito.
PermutationCheck: Verifica 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, asegurando 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: 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 la evaluación de un polinomio unidimensional, se reduce la complejidad computacional para el verificador. Además, SumCheck 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 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 no nulo en todo el hipercubo, y el producto debe ser 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 la situación de división por cero, lo que impidió afirmar que U es no cero 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 múltiples columnas: HyperPlonk no tiene esta función; Binius admite la comprobació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 PIOPSumCheck existente.
Binius: STARKs optimizados sobre dominios binarios
Análisis de los principios de Binius STARKs y reflexiones sobre su optimización
1 Introducción
Una de las principales razones de la baja eficiencia de STARKs es que la mayoría de los valores en los programas reales son bastante pequeños, como los índices en bucles for, valores booleanos, contadores, etc. Sin embargo, para garantizar la seguridad de las pruebas basadas en árboles de Merkle, al ampliar los datos utilizando codificación de Reed-Solomon, muchos valores redundantes adicionales ocupan todo el campo, incluso si el valor original 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, 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 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 ningún desperdicio de espacio, es decir, los STARKs de cuarta generación.
Tabla 1: Ruta de derivación de STARKs
| Álgebra | Ancho de codificación | Implementación representativa | |------|----------|------------| | Primera Generación | 252bit | StarkWare | | Segunda generación | 64bit | Plonky2 | | 3ª Generación | 32bit | BabyBear |
| Cuarta Generación | 1bit | Binius |
En comparación con Goldilocks, BabyBear, Mersenne31 y otros campos finitos descubiertos 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:
Cuando se utilizan campos más pequeños, la operación de extensión de campo se vuelve cada vez más importante para garantizar la seguridad. El campo binario utilizado por Binius depende completamente de la extensión de campo para 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 operan en el campo base, logrando así alta eficiencia en campos pequeños. Sin embargo, la verificación de puntos aleatorios y el cálculo 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: al calcular la representación de trace en STARKs, el tamaño del dominio utilizado debe ser mayor que el grado del polinomio; al comprometer el árbol de Merkle en STARKs, se debe realizar la codificación de Reed-Solomon, y el tamaño del dominio utilizado debe ser mayor que el tamaño después de la expansión de 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 polinomios multilineales en lugar de polinomios univariados, 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 extensión estándar de Reed-Solomon como en STARKs, pero se puede considerar el hipercubo como un cuadrado, basando la extensión de Reed-Solomon 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 núcleo del sistema de pruebas, transforma las relaciones computacionales de entrada en ecuaciones polinómicas verificables. Diferentes protocolos PIOP permiten al probador enviar polinomios progresivamente a través de la interacción con el validador, de modo que el validador puede verificar si el cálculo es correcto al consultar los resultados de la evaluación de unos pocos polinomios. Los protocolos PIOP existentes incluyen: PLONK PIOP, Spartan PIOP y HyperPlonk PIOP, cada uno de los cuales maneja las expresiones polinómicas de manera diferente, lo que afecta el rendimiento y la eficiencia de todo el sistema SNARK.
Esquema de Compromiso Polinómico ( Polynomial Commitment Scheme, PCS ): El esquema de compromiso polinómico se utiliza para probar si 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 verificar más tarde el resultado de la evaluación de ese polinomio, mientras oculta otra información sobre el 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 un campo finito o una curva elíptica adecuada, 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. Halo2 se diseñó con un enfoque en la escalabilidad y en eliminar la configuración confiable del protocolo ZCash.
Plonky2: utiliza PLONK PIOP combinado con FRI PCS y se basa en el dominio de Goldilocks. Plonky2 está diseñado para lograr una recursividad eficiente. Al diseñar estos sistemas, la PIOP y la PCS seleccionadas deben coincidir con el campo finito o la curva elíptica utilizada para garantizar la corrección, el rendimiento y la seguridad del sistema. La elección de estas combinaciones no solo afecta el tamaño de la prueba SNARK y la eficiencia de la verificación, sino que también determina si el sistema puede lograr transparencia sin necesidad de una configuración confiable y si puede soportar funciones extensibles 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 sus cálculos, permitiendo realizar operaciones simplificadas en el dominio binario. En segundo lugar, Binius adapta la verificación de productos y permutaciones de HyperPlonk en su protocolo de prueba Oracle interactivo (PIOP), asegurando una verificación de consistencia segura y eficiente entre las variables y sus permutaciones. En tercer lugar, 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. Por último, el protocolo utiliza un esquema de compromiso polinómico de pequeño dominio (Small-Field PCS), lo que le permite implementar un sistema de pruebas 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
El campo binario en torre es clave para implementar cálculos verificables rápidos, principalmente debido a dos aspectos: cálculos eficientes y aritmética eficiente. El campo binario, en esencia, admite operaciones aritméticas altamente eficientes, lo que lo convierte en una opción ideal para aplicaciones criptográficas que son sensibles al rendimiento. Además, la estructura del campo binario admite un proceso de aritmética simplificada, es decir, las operaciones realizadas en el campo binario pueden expresarse 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 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 elementos en el dominio binario. Por ejemplo, en el dominio binario más básico F2, cualquier cadena de longitud k se puede mapear directamente a un elemento del dominio binario de k bits. Esto es diferente del dominio primo, que no puede proporcionar esta representación canónica dentro de un número fijo de bits. Aunque el dominio primo de 32 bits puede caber en 32 bits, no cada cadena de 32 bits puede corresponder de manera única a un elemento del dominio, mientras que el dominio binario tiene esta conveniencia de mapeo uno a uno. En el dominio 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 dominios finitos específicos como Mersenne-31 o Goldilocks-64. En el dominio 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 usa en POLYVAL (, y la reducción recursiva ), como en Tower ###. El artículo "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" señala que en el dominio binario no se necesita introducir acarreo en las operaciones de suma y multiplicación, y que la operación de cuadrado en el dominio binario es muy eficiente, ya que sigue la regla simplificada (X + Y )2 = X2 + Y 2.
Como se muestra en la Figura 1, una cadena de 128 bits: esta cadena se puede interpretar de varias maneras en el contexto de un dominio binario. Puede considerarse como 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, 16 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 realizar multiplicación, elevación al cuadrado y operaciones de inversión en un dominio de torre binario de n bits ( descomponible en un subdominio de m bits ).
( 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 inspira 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: Verificar si el testigo confidencial ω y la entrada pública x satisfacen la relación de operación del circuito C)x,ω(=0, para asegurar el correcto funcionamiento del circuito.
PermutationCheck: Verifica 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, asegurando 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: 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 la evaluación de un polinomio unidimensional, se reduce la complejidad computacional para el verificador. Además, SumCheck 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 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 no nulo en todo el hipercubo, y el producto debe ser 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 la situación de división por cero, lo que impidió afirmar que U es no cero 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 múltiples columnas: HyperPlonk no tiene esta función; Binius admite la comprobació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 PIOPSumCheck existente.
![Bitl