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 programas reales son bastante pequeños, pero 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 ocupan todo el dominio, incluso si el valor original es muy pequeño. Para resolver este problema, reducir el tamaño del dominio se ha convertido en una estrategia clave.
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 aún presenta una gran cantidad de espacio desperdiciado. En comparación, el dominio binario permite operar directamente sobre los bits, lo que resulta en una codificación compacta y eficiente sin desperdicio de espacio, es decir, los STARKs de cuarta generación.
En comparación con los dominios finitos descubiertos en investigaciones recientes como Goldilocks, BabyBear y Mersenne31, la investigación sobre dominios binarios se remonta a la década de 1980. Actualmente, los dominios 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 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, que se basa 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 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 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 dominio, sino que solo operan en el dominio base, logrando así una alta eficiencia en dominios pequeños. Sin embargo, la verificación de puntos aleatorios y el cálculo de FRI aún necesitan profundizar en una extensión de dominio más grande para garantizar la seguridad requerida.
Al construir un sistema de prueba basado en el campo binario, existen 2 problemas prácticos: en STARKs, al calcular la representación de la traza, el tamaño del campo utilizado debe ser mayor que el grado del polinomio; en STARKs, al comprometer el árbol de Merkle, se debe hacer una 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 ha propuesto una solución innovadora que aborda ambos problemas por separado y representa los mismos datos de dos maneras diferentes: en primer lugar, utilizando polinomios multivariables (en concreto, polinomios multilineales) en lugar de polinomios univariables, representando toda la trayectoria de cálculo a través de sus valores en "hipercubos" (hypercubes); 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 el caso de STARKs, pero se puede considerar el hipercubo como un cuadrado (square) y realizar la extensión de Reed-Solomon basada en ese cuadrado. Este método, al garantizar la seguridad, mejora considerablemente 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 prueba, transforma la relación de cálculo 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 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, entre otros, que manejan 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 una igualdad polinómica generada por PIOP es válida. El PCS es una herramienta criptográfica que permite al probador comprometerse a un polinomio y luego verificar el resultado de la evaluación de ese 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, niveles de seguridad y escenarios de aplicación.
Según las necesidades específicas, elige diferentes PIOP y PCS, y combina con un campo finito o curva elíptica adecuada, se puede construir un sistema de prueba 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 y FRI PCS, y se basa en el dominio de Goldilocks. Plonky2 se diseñó para lograr una recursión eficiente. Al diseñar estos sistemas, el PIOP y el PCS seleccionados 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 admitir funciones ampliadas como pruebas recursivas o pruebas agregadas.
Binius: HyperPlonk PIOP + Brakedown PCS + campo binario. Específicamente, Binius incluye cinco tecnologías clave para lograr su eficiencia y seguridad. Primero, la aritmética basada en torres de campos binarios 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 de consistencia segura y eficiente entre las variables y sus permutaciones. En tercer lugar, el protocolo introduce una nueva prueba de desplazamiento multilinéal, optimizando la eficiencia de la verificación de relaciones multilineales en pequeños campos. Cuarto, Binius utiliza una versión mejorada de la prueba de búsqueda Lasso, que proporciona flexibilidad y una fuerte seguridad al mecanismo de búsqueda. Finalmente, el protocolo utiliza un esquema de compromiso de polinomios de pequeño campo (Small-Field PCS), lo que le permite implementar un sistema de prueba eficiente en el campo binario y reducir los costos generalmente asociados con campos grandes.
2.1 Campo finito: aritmética basada en torres de campos binarios
El campo binario en torre es clave para lograr cálculos verificables rápidos, principalmente debido a dos aspectos: el cálculo eficiente y la aritmética eficiente. Los campos binarios, por su naturaleza, admiten operaciones aritméticas altamente eficientes, lo que los convierte en una opción ideal para aplicaciones criptográficas sensibles al rendimiento. Además, la estructura del campo binario admite un proceso de aritmética simplificado, es decir, las operaciones realizadas sobre el campo binario se pueden representar en una forma algebraica compacta y fácil de verificar. Estas características, junto con la capacidad de aprovechar al máximo 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 un elemento en el dominio binario. Por ejemplo, en el dominio binario más básico F2, cualquier cadena de k bits se puede mapear directamente a un elemento del dominio de k bits. Esto es diferente del dominio primo, que no puede proporcionar esta representación canónica dentro de un número determinado de bits. Aunque el dominio primo de 32 bits puede incluirse en 32 bits, no todas las cadenas de 32 bits pueden 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 reducciones especiales (como se usa en AES), reducción de Montgomery (como se usa en POLYVAL) y 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 dominio binario no es necesario 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 de (X + Y )2 = X2 + Y2.
Como se muestra en la Figura 1, una cadena de 128 bits: esta cadena se puede interpretar de varias maneras en el contexto de los campos binarios. Puede ser vista como un elemento único en un campo binario de 128 bits, o puede ser desglosada en dos elementos de campo torre de 64 bits, cuatro elementos de campo torre de 32 bits, 16 elementos de campo torre de 8 bits, o 128 elementos de campo F2. Esta flexibilidad de representación no requiere ningún costo computacional, solo una conversión de tipo (typecast) de la cadena de bits, lo que 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 se beneficia de 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 las operaciones de multiplicación, elevación al cuadrado y cálculo de inversos en un campo binario torre de n bits (que puede descomponerse 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 y utiliza una serie de mecanismos de verificación centralizados para validar la corrección de polinomios y conjuntos de múltiples variables. Estas verificaciones centrales incluyen:
GateCheck: Verifica si el testigo confidencial ω y la entrada pública x cumplen con la relación de operación del circuito C(x,ω)=0, para asegurar que el circuito funcione correctamente.
PermutationCheck: Verifica 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 de la permutación entre las variables del polinomio.
LookupCheck: Verifica si la evaluación del polinomio está en la tabla de búsqueda dada, es decir, f(Bµ) ⊆ T(Bµ), asegurando que ciertos valores estén dentro del rango especificado.
MultisetCheck: Verifica si dos conjuntos multivariables son iguales, es decir, {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, garantizando la consistencia entre múltiples conjuntos.
ProductCheck: 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: Verifica 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: 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 un polinomio univariable, se reduce la complejidad computacional para el verificador. Además, SumCheck también permite el procesamiento por lotes al introducir números aleatorios, construyendo combinaciones lineales para 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 mejorado en los siguientes 3 aspectos:
Optimización de ProductCheck: En HyperPlonk, ProductCheck requiere que el denominador U sea siempre distinto de cero en el hipercubo, y que el producto sea igual a un valor específico; Binius simplifica este proceso de verificación al especializar dicho valor a 1, reduciendo así la complejidad computacional.
Manejo del problema de división por cero: HyperPlonk no pudo manejar adecuadamente la situación de división por cero, lo que llevó a no poder 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.
Verificación de Permutación entre 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 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, especialmente al proporcionar un soporte funcional más robusto en el manejo de la verificación de polinomios multivariables más complejos. Estas mejoras no solo abordan las limitaciones en 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, que permite generar y operar de manera efectiva polinomios derivados de un manejador de entrada u otros polinomios virtuales. A continuación, se presentan dos métodos clave:
Empaquetado: Este método optimiza la operación empaquetando elementos más pequeños en posiciones adyacentes en el orden del diccionario en elementos más grandes. El operador Pack se aplica a bloques de tamaño 2κ y los combina en un solo elemento en un dominio de alta dimensión. A través de la expansión multilineal.
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.
Innovación de Binius: solución de optimización STARKs basada en el dominio binario
Análisis de los principios de Binius STARKs y reflexiones sobre su optimización
1 Introducción
Una de las principales razones de la baja eficiencia de STARKs es que la mayoría de los valores en programas reales son bastante pequeños, pero 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 ocupan todo el dominio, incluso si el valor original es muy pequeño. Para resolver este problema, reducir el tamaño del dominio se ha convertido en una estrategia clave.
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 aún presenta una gran cantidad de espacio desperdiciado. En comparación, el dominio binario permite operar directamente sobre los bits, lo que resulta en una codificación compacta y eficiente sin desperdicio de espacio, es decir, los STARKs de cuarta generación.
En comparación con los dominios finitos descubiertos en investigaciones recientes como Goldilocks, BabyBear y Mersenne31, la investigación sobre dominios binarios se remonta a la década de 1980. Actualmente, los dominios 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 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, que se basa 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 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 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 dominio, sino que solo operan en el dominio base, logrando así una alta eficiencia en dominios pequeños. Sin embargo, la verificación de puntos aleatorios y el cálculo de FRI aún necesitan profundizar en una extensión de dominio más grande para garantizar la seguridad requerida.
Al construir un sistema de prueba basado en el campo binario, existen 2 problemas prácticos: en STARKs, al calcular la representación de la traza, el tamaño del campo utilizado debe ser mayor que el grado del polinomio; en STARKs, al comprometer el árbol de Merkle, se debe hacer una 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 ha propuesto una solución innovadora que aborda ambos problemas por separado y representa los mismos datos de dos maneras diferentes: en primer lugar, utilizando polinomios multivariables (en concreto, polinomios multilineales) en lugar de polinomios univariables, representando toda la trayectoria de cálculo a través de sus valores en "hipercubos" (hypercubes); 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 el caso de STARKs, pero se puede considerar el hipercubo como un cuadrado (square) y realizar la extensión de Reed-Solomon basada en ese cuadrado. Este método, al garantizar la seguridad, mejora considerablemente 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 prueba, transforma la relación de cálculo 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 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, entre otros, que manejan 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 una igualdad polinómica generada por PIOP es válida. El PCS es una herramienta criptográfica que permite al probador comprometerse a un polinomio y luego verificar el resultado de la evaluación de ese 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, niveles de seguridad y escenarios de aplicación.
Según las necesidades específicas, elige diferentes PIOP y PCS, y combina con un campo finito o curva elíptica adecuada, se puede construir un sistema de prueba 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 y FRI PCS, y se basa en el dominio de Goldilocks. Plonky2 se diseñó para lograr una recursión eficiente. Al diseñar estos sistemas, el PIOP y el PCS seleccionados 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 admitir funciones ampliadas como pruebas recursivas o pruebas agregadas.
Binius: HyperPlonk PIOP + Brakedown PCS + campo binario. Específicamente, Binius incluye cinco tecnologías clave para lograr su eficiencia y seguridad. Primero, la aritmética basada en torres de campos binarios 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 de consistencia segura y eficiente entre las variables y sus permutaciones. En tercer lugar, el protocolo introduce una nueva prueba de desplazamiento multilinéal, optimizando la eficiencia de la verificación de relaciones multilineales en pequeños campos. Cuarto, Binius utiliza una versión mejorada de la prueba de búsqueda Lasso, que proporciona flexibilidad y una fuerte seguridad al mecanismo de búsqueda. Finalmente, el protocolo utiliza un esquema de compromiso de polinomios de pequeño campo (Small-Field PCS), lo que le permite implementar un sistema de prueba eficiente en el campo binario y reducir los costos generalmente asociados con campos grandes.
2.1 Campo finito: aritmética basada en torres de campos binarios
El campo binario en torre es clave para lograr cálculos verificables rápidos, principalmente debido a dos aspectos: el cálculo eficiente y la aritmética eficiente. Los campos binarios, por su naturaleza, admiten operaciones aritméticas altamente eficientes, lo que los convierte en una opción ideal para aplicaciones criptográficas sensibles al rendimiento. Además, la estructura del campo binario admite un proceso de aritmética simplificado, es decir, las operaciones realizadas sobre el campo binario se pueden representar en una forma algebraica compacta y fácil de verificar. Estas características, junto con la capacidad de aprovechar al máximo 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 un elemento en el dominio binario. Por ejemplo, en el dominio binario más básico F2, cualquier cadena de k bits se puede mapear directamente a un elemento del dominio de k bits. Esto es diferente del dominio primo, que no puede proporcionar esta representación canónica dentro de un número determinado de bits. Aunque el dominio primo de 32 bits puede incluirse en 32 bits, no todas las cadenas de 32 bits pueden 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 reducciones especiales (como se usa en AES), reducción de Montgomery (como se usa en POLYVAL) y 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 dominio binario no es necesario 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 de (X + Y )2 = X2 + Y2.
Como se muestra en la Figura 1, una cadena de 128 bits: esta cadena se puede interpretar de varias maneras en el contexto de los campos binarios. Puede ser vista como un elemento único en un campo binario de 128 bits, o puede ser desglosada en dos elementos de campo torre de 64 bits, cuatro elementos de campo torre de 32 bits, 16 elementos de campo torre de 8 bits, o 128 elementos de campo F2. Esta flexibilidad de representación no requiere ningún costo computacional, solo una conversión de tipo (typecast) de la cadena de bits, lo que 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 se beneficia de 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 las operaciones de multiplicación, elevación al cuadrado y cálculo de inversos en un campo binario torre de n bits (que puede descomponerse 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 y utiliza una serie de mecanismos de verificación centralizados para validar la corrección de polinomios y conjuntos de múltiples variables. Estas verificaciones centrales incluyen:
GateCheck: Verifica si el testigo confidencial ω y la entrada pública x cumplen con la relación de operación del circuito C(x,ω)=0, para asegurar que el circuito funcione correctamente.
PermutationCheck: Verifica 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 de la permutación entre las variables del polinomio.
LookupCheck: Verifica si la evaluación del polinomio está en la tabla de búsqueda dada, es decir, f(Bµ) ⊆ T(Bµ), asegurando que ciertos valores estén dentro del rango especificado.
MultisetCheck: Verifica si dos conjuntos multivariables son iguales, es decir, {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, garantizando la consistencia entre múltiples conjuntos.
ProductCheck: 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: Verifica 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: 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 un polinomio univariable, se reduce la complejidad computacional para el verificador. Además, SumCheck también permite el procesamiento por lotes al introducir números aleatorios, construyendo combinaciones lineales para 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 mejorado en los siguientes 3 aspectos:
Optimización de ProductCheck: En HyperPlonk, ProductCheck requiere que el denominador U sea siempre distinto de cero en el hipercubo, y que el producto sea igual a un valor específico; Binius simplifica este proceso de verificación al especializar dicho valor a 1, reduciendo así la complejidad computacional.
Manejo del problema de división por cero: HyperPlonk no pudo manejar adecuadamente la situación de división por cero, lo que llevó a no poder 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.
Verificación de Permutación entre 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 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, especialmente al proporcionar un soporte funcional más robusto en el manejo de la verificación de polinomios multivariables más complejos. Estas mejoras no solo abordan las limitaciones en 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, que permite generar y operar de manera efectiva polinomios derivados de un manejador de entrada u otros polinomios virtuales. A continuación, se presentan dos métodos clave: