Análisis de principios de Binius STARKs y reflexión sobre su optimización
1. Introducción
A diferencia de los SNARKs basados en curvas elípticas, los STARKs pueden considerarse como SNARKs basados en hash. Una de las principales razones por las que la eficiencia de los STARKs es baja actualmente 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 asegurar la seguridad de las pruebas basadas en el árbol de Merkle, al usar codificación de Reed-Solomon para expandir los datos, muchos valores redundantes adicionales ocuparán todo el dominio, incluso si el valor original en sí es muy pequeño. Para resolver este problema, reducir el tamaño del dominio se ha convertido en una estrategia clave.
La primera generación de STARKs tiene un ancho de codificación de 252 bits, la segunda generación de STARKs tiene un ancho de codificación de 64 bits, y la tercera generación de STARKs tiene un ancho de codificación de 32 bits, pero el ancho de codificación de 32 bits todavía presenta una gran cantidad de espacio desperdiciado. 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.
En comparación con los dominios finitos descubiertos en años recientes como Goldilocks, BabyBear y Mersenne31, la investigación sobre dominios binarios se remonta a la década de 1980. En la actualidad, los dominios binarios se aplican 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, 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, que se basa en el campo F28, es un algoritmo hash muy adecuado para la recursividad.
Cuando se utilizan dominios más pequeños, la operación de extensión de dominio se vuelve cada vez más importante para garantizar la seguridad. El dominio binario utilizado por Binius depende completamente de la extensión de dominio para asegurar 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 dominio, sino que solo es necesario operar 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 requieren profundizar en un dominio de extensión más grande para garantizar la seguridad necesaria.
Al construir un sistema de pruebas 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, 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 por separado y representa los mismos datos de dos maneras diferentes: primero, utilizando un polinomio multivariable (, específicamente un polinomio multilineal ), en lugar de un polinomio univariante, 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 ), y basar 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 mayoría de los sistemas SNARKs actuales generalmente constan de las siguientes dos partes:
Prueba de Oráculo Interactivo Polinómico Teórico de la Información ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP ): PIOP, como el núcleo del sistema de pruebas, transforma las relaciones computacionales de entrada en igualdades 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 los resultados de la evaluación de un número reducido de 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 demostrar si se cumple la igualdad polinómica generada por PIOP. PCS es una herramienta criptográfica, a través de la cual, el comprobador puede comprometerse a un polinomio y verificar más tarde los resultados de la evaluación de dicho polinomio, mientras oculta otra información del polinomio. Los esquemas de compromiso polinómico más comunes son 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, elige diferentes PIOP y PCS, y combina 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. En el diseño de Halo2, se presta atención a la escalabilidad y a la eliminación del trusted setup en el protocolo ZCash.
• Plonky2: utiliza PLONK PIOP y FRI PCS combinados, 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 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 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 de agregación.
Binius: HyperPlonk PIOP + Brakedown PCS + campos binarios. Específicamente, 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 computación, permitiendo realizar operaciones simplificadas en campos binarios. En segundo lugar, Binius adapta las verificaciones de productos y permutaciones de HyperPlonk en su protocolo de prueba de Oracle interactivo (PIOP), asegurando una verificación de consistencia segura y eficiente entre variables y sus permutaciones. Tercero, el protocolo introduce una nueva prueba de desplazamiento multilineal que optimiza la eficiencia en la verificación de relaciones multilineales en dominios pequeños. Cuarto, Binius utiliza una versión mejorada de la prueba de búsqueda de Lasso, que proporciona flexibilidad y una sólida seguridad al mecanismo de búsqueda. Por último, el protocolo utiliza un esquema de compromiso polinómico de pequeños dominios (Small-Field PCS), lo que le permite implementar un sistema de pruebas eficiente en campos binarios y reduce los gastos generalmente asociados con dominios grandes.
( 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álculo eficiente y aritmética eficiente. Los campos binarios, en esencia, admiten operaciones aritméticas altamente eficientes, lo que los convierte en una opción ideal para aplicaciones criptográficas sensibles a los requisitos de rendimiento. Además, la estructura del campo binario admite 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.
Donde "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 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 ) utilizada en AES ###, la reducción de Montgomery ( utilizada en POLYVAL ) y la reducción recursiva ( como Tower ). El artículo "Explorando el Espacio de Diseño de Implementaciones de Hardware ECC en Campos Primos vs. Campos Binarios" señala que el campo binario no requiere la introducción de 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 se puede interpretar de varias maneras en el contexto del campo binario. Puede considerarse como un elemento único en un campo binario de 128 bits, o puede desglosarse 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 de campo de 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ñ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 ).
( 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, utilizando 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 satisfacen la relación de operación del circuito C)x,ω###=0, para asegurar que el circuito funcione correctamente.
PermutationCheck: Verifica si los resultados de evaluación de los dos polinomios multivariables f y g en el hipercubo booleano son una relación de permutación f(x) = f(π)x((, para asegurar la consistencia del orden 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 del polinomio.
ZeroCheck: Verificar si un polinomio multivariable en el hipercubo booleano es cero en cualquier punto ∏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 un polinomio multivariable en la evaluación de un polinomio univariable, 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 implementan 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 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 pudo manejar adecuadamente los casos de división por cero, lo que impide afirmar que U es no cero en el hipercubo; Binius manejó correctamente este problema, incluso cuando el denominador es cero, el ProductCheck de Binius puede continuar procesando, permitiendo la generalización a cualquier valor de producto.
Verificación de Permutación de columnas: HyperPlonk no tiene esta función; Binius admite la verificació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 a través de
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.
Binius STARKs: Sistema eficiente de zk-SNARKs en el dominio binario
Análisis de principios de Binius STARKs y reflexión sobre su optimización
1. Introducción
A diferencia de los SNARKs basados en curvas elípticas, los STARKs pueden considerarse como SNARKs basados en hash. Una de las principales razones por las que la eficiencia de los STARKs es baja actualmente 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 asegurar la seguridad de las pruebas basadas en el árbol de Merkle, al usar codificación de Reed-Solomon para expandir los datos, muchos valores redundantes adicionales ocuparán todo el dominio, incluso si el valor original en sí es muy pequeño. Para resolver este problema, reducir el tamaño del dominio se ha convertido en una estrategia clave.
La primera generación de STARKs tiene un ancho de codificación de 252 bits, la segunda generación de STARKs tiene un ancho de codificación de 64 bits, y la tercera generación de STARKs tiene un ancho de codificación de 32 bits, pero el ancho de codificación de 32 bits todavía presenta una gran cantidad de espacio desperdiciado. 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.
En comparación con los dominios finitos descubiertos en años recientes como Goldilocks, BabyBear y Mersenne31, la investigación sobre dominios binarios se remonta a la década de 1980. En la actualidad, los dominios binarios se aplican 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, 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, que se basa en el campo F28, es un algoritmo hash muy adecuado para la recursividad.
Cuando se utilizan dominios más pequeños, la operación de extensión de dominio se vuelve cada vez más importante para garantizar la seguridad. El dominio binario utilizado por Binius depende completamente de la extensión de dominio para asegurar 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 dominio, sino que solo es necesario operar 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 requieren profundizar en un dominio de extensión más grande para garantizar la seguridad necesaria.
Al construir un sistema de pruebas 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, 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 por separado y representa los mismos datos de dos maneras diferentes: primero, utilizando un polinomio multivariable (, específicamente un polinomio multilineal ), en lugar de un polinomio univariante, 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 ), y basar 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 mayoría de los sistemas SNARKs actuales generalmente constan de las siguientes dos partes:
Prueba de Oráculo Interactivo Polinómico Teórico de la Información ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP ): PIOP, como el núcleo del sistema de pruebas, transforma las relaciones computacionales de entrada en igualdades 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 los resultados de la evaluación de un número reducido de 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 demostrar si se cumple la igualdad polinómica generada por PIOP. PCS es una herramienta criptográfica, a través de la cual, el comprobador puede comprometerse a un polinomio y verificar más tarde los resultados de la evaluación de dicho polinomio, mientras oculta otra información del polinomio. Los esquemas de compromiso polinómico más comunes son 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, elige diferentes PIOP y PCS, y combina 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. En el diseño de Halo2, se presta atención a la escalabilidad y a la eliminación del trusted setup en el protocolo ZCash.
• Plonky2: utiliza PLONK PIOP y FRI PCS combinados, 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 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 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 de agregación.
Binius: HyperPlonk PIOP + Brakedown PCS + campos binarios. Específicamente, 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 computación, permitiendo realizar operaciones simplificadas en campos binarios. En segundo lugar, Binius adapta las verificaciones de productos y permutaciones de HyperPlonk en su protocolo de prueba de Oracle interactivo (PIOP), asegurando una verificación de consistencia segura y eficiente entre variables y sus permutaciones. Tercero, el protocolo introduce una nueva prueba de desplazamiento multilineal que optimiza la eficiencia en la verificación de relaciones multilineales en dominios pequeños. Cuarto, Binius utiliza una versión mejorada de la prueba de búsqueda de Lasso, que proporciona flexibilidad y una sólida seguridad al mecanismo de búsqueda. Por último, el protocolo utiliza un esquema de compromiso polinómico de pequeños dominios (Small-Field PCS), lo que le permite implementar un sistema de pruebas eficiente en campos binarios y reduce los gastos generalmente asociados con dominios grandes.
( 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álculo eficiente y aritmética eficiente. Los campos binarios, en esencia, admiten operaciones aritméticas altamente eficientes, lo que los convierte en una opción ideal para aplicaciones criptográficas sensibles a los requisitos de rendimiento. Además, la estructura del campo binario admite 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.
Donde "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 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 ) utilizada en AES ###, la reducción de Montgomery ( utilizada en POLYVAL ) y la reducción recursiva ( como Tower ). El artículo "Explorando el Espacio de Diseño de Implementaciones de Hardware ECC en Campos Primos vs. Campos Binarios" señala que el campo binario no requiere la introducción de 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 se puede interpretar de varias maneras en el contexto del campo binario. Puede considerarse como un elemento único en un campo binario de 128 bits, o puede desglosarse 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 de campo de 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ñ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 ).
( 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, utilizando 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 satisfacen la relación de operación del circuito C)x,ω###=0, para asegurar que el circuito funcione correctamente.
PermutationCheck: Verifica si los resultados de evaluación de los dos polinomios multivariables f y g en el hipercubo booleano son una relación de permutación f(x) = f(π)x((, para asegurar la consistencia del orden 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 del polinomio.
ZeroCheck: Verificar si un polinomio multivariable en el hipercubo booleano es cero en cualquier punto ∏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 un polinomio multivariable en la evaluación de un polinomio univariable, 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 implementan 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 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 pudo manejar adecuadamente los casos de división por cero, lo que impide afirmar que U es no cero en el hipercubo; Binius manejó correctamente este problema, incluso cuando el denominador es cero, el ProductCheck de Binius puede continuar procesando, permitiendo la generalización a cualquier valor de producto.
Verificación de Permutación de columnas: HyperPlonk no tiene esta función; Binius admite la verificació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 a través de