Análisis de los principios de Binius STARKs y reflexiones sobre su optimización
1 Introducción
Una de las principales razones de la ineficiencia de STARKs es que la mayoría de los valores en los programas reales son bastante pequeños, como los índices en los bucles for, los valores booleanos, los 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 redundantes adicionales ocuparán todo el dominio, incluso si el valor original es muy pequeño. Para abordar este problema, reducir el tamaño del dominio se ha convertido en una estrategia clave.
La anchura de codificación de la primera generación de STARKs es de 252 bits, la segunda generación de STARKs tiene una anchura de codificación de 64 bits, y la tercera generación de STARKs tiene una anchura de codificación de 32 bits, pero la codificación de 32 bits todavía presenta un gran espacio desperdiciado. En comparación, el dominio 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 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 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, basada en el campo F28, es un algoritmo 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. Y el campo binario utilizado por Binius depende completamente de la extensión de campo para garantizar su seguridad y usabilidad 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 operan únicamente 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 necesitan profundizar en un campo 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, se necesita 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 logra representar los mismos datos de dos maneras diferentes: primero, utilizando polinomios multivariables (específicamente polinomios multilineales) en lugar de polinomios univariables, 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 la extensión estándar de Reed-Solomon como en los STARKs, pero se puede considerar el hipercubo como un cuadrado, basando la extensión de Reed-Solomon en ese cuadrado. Este método, al asegurar 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 estar compuestos por las siguientes dos partes:
Prueba de oracle interactivo polinómico de teoría de la información (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, como núcleo del sistema de prueba, 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, lo que permite que el validador verifique si el cálculo es correcto consultando los resultados de evaluación de unos pocos polinomios. Los protocolos PIOP existentes incluyen: PIOP de PLONK, PIOP de Spartan y PIOP de HyperPlonk, entre otros, que tienen 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 demostrar si la 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 los resultados de la evaluación de dicho polinomio, al tiempo que oculta otra información sobre el polinomio. Los esquemas de compromiso polinómico más comunes incluyen KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) y Brakedown, entre otros. Diferentes PCS tienen diferentes rendimientos, seguridad y escenarios de aplicación.
Según las necesidades específicas, 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 y Bulletproofs PCS, y se basa en la curva Pasta. Al diseñar Halo2, se presta atención a la escalabilidad y se elimina la configuración de confianza en el 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 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 la verificación, sino que también determina si el sistema puede lograr transparencia sin la 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 + dominio binario. En concreto, Binius incluye cinco tecnologías clave para lograr su eficiencia y seguridad. Primero, la aritmética basada en torres de dominios binarios constituye la base de su computación, lo que permite realizar cálculos simplificados en el dominio binario. En segundo lugar, Binius adapta la verificación de producto y permutación 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. Tercero, el protocolo introduce una nueva prueba de desplazamiento multilinéal, optimizando la eficiencia de la verificación de relaciones multilinales en dominios pequeños. 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 de polinomios de pequeño dominio (Small-Field PCS), permitiendo un sistema de prueba eficiente en el dominio binario y reduciendo los costos asociados normalmente con dominios grandes.
2.1 Campo finito: aritmética basada en torres de campos binarios
Los campos binarios en torres son clave para implementar cálculos verificables rápidos, 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 al rendimiento. Además, la estructura del campo binario admite un proceso de aritmética simplificado, es decir, las operaciones realizadas en el campo binario se pueden expresar 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 de torre, hacen que los campos binarios sean particularmente adecuados para sistemas de prueba escalables como Binius.
El término "canónico" se refiere a la representación única y directa de elementos 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 de campo binario de k bits. Esto es diferente del campo primo, que no puede 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 cada cadena de 32 bits puede corresponder de manera única a un elemento de campo, mientras que el campo binario ofrece 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 utiliza en AES), la reducción de Montgomery (como se utiliza en POLYVAL) y la reducción recursiva (como Tower). El documento "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" señala que en el campo binario, tanto en las operaciones de suma como de multiplicación no es necesario introducir acarreo, y la operación de cuadrado en el campo 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 puede interpretarse de varias maneras en el contexto de un campo binario. Puede considerarse como un elemento único en un campo binario de 128 bits, o ser descompuesta en dos elementos de campo de torre de 64 bits, cuatro elementos de campo de torre de 32 bits, dieciséis 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 (typecast) de la cadena de bits, 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 documento "On Efficient Inversion in Tower Fields of Characteristic Two" explora la complejidad computacional de realizar multiplicación, cuadrados y operaciones de inversión en un campo binario de torre de n bits (descomponible en subcampos de m bits).
2.2 PIOP: versión adaptada de HyperPlonk Product y PermutationCheck------aplicable a campos binarios
El diseño de PIOP en el protocolo Binius se inspira en HyperPlonk y utiliza una serie de mecanismos de verificación centrales para validar la corrección de polinomios y conjuntos multivariados. Estas verificaciones centrales incluyen:
GateCheck: Verifica si el testigo secreto ω y la entrada pública x satisfacen la relación de cálculo 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 garantizar la consistencia de las permutaciones 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 garantizar la corrección del producto polinómico.
ZeroCheck: Verifica si un polinomio multivariable en un hipercubo booleano es cero en cualquier punto ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, para garantizar 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 del polinomio multivariable en una evaluación de polinomio univariable, 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 y realizar el procesamiento por lotes de múltiples instancias de verificación de sumas.
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 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 dicho valor en 1, reduciendo así la complejidad computacional.
Manejo del problema de la división por cero: HyperPlonk no pudo manejar adecuadamente la situación de división por cero, lo que llevó a no poder afirmar si U es distinto de 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 entre columnas: HyperPlonk no tiene esta función; 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 proporcionar un mejor soporte funcional al manejar la verificación de polinomios multivariables más complejos. Estas mejoras no solo abordan las limitaciones en HyperPlonk, sino que también establecen una base para futuros sistemas de prueba basados en campos binarios.
2.3 PIOP: nuevo argumento de desplazamiento multilineal ------ aplicable a 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 manejadores de entrada u otros polinomios virtuales. A continuación se presentan dos métodos clave:
Empaque:
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.
9 me gusta
Recompensa
9
3
Compartir
Comentar
0/400
BlindBoxVictim
· hace16h
¿32bit? Amigo, es mejor usar papel y lápiz para calcular.
Ver originalesResponder0
AirdropworkerZhang
· hace16h
¿Todavía estás en la competencia? Solo quiero hacer dinero.
Binius: Nueva solución STARKs eficiente 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 ineficiencia de STARKs es que la mayoría de los valores en los programas reales son bastante pequeños, como los índices en los bucles for, los valores booleanos, los 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 redundantes adicionales ocuparán todo el dominio, incluso si el valor original es muy pequeño. Para abordar este problema, reducir el tamaño del dominio se ha convertido en una estrategia clave.
La anchura de codificación de la primera generación de STARKs es de 252 bits, la segunda generación de STARKs tiene una anchura de codificación de 64 bits, y la tercera generación de STARKs tiene una anchura de codificación de 32 bits, pero la codificación de 32 bits todavía presenta un gran espacio desperdiciado. En comparación, el dominio 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 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 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, basada en el campo F28, es un algoritmo 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. Y el campo binario utilizado por Binius depende completamente de la extensión de campo para garantizar su seguridad y usabilidad 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 operan únicamente 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 necesitan profundizar en un campo 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, se necesita 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 logra representar los mismos datos de dos maneras diferentes: primero, utilizando polinomios multivariables (específicamente polinomios multilineales) en lugar de polinomios univariables, 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 la extensión estándar de Reed-Solomon como en los STARKs, pero se puede considerar el hipercubo como un cuadrado, basando la extensión de Reed-Solomon en ese cuadrado. Este método, al asegurar 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 estar compuestos por las siguientes dos partes:
Prueba de oracle interactivo polinómico de teoría de la información (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, como núcleo del sistema de prueba, 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, lo que permite que el validador verifique si el cálculo es correcto consultando los resultados de evaluación de unos pocos polinomios. Los protocolos PIOP existentes incluyen: PIOP de PLONK, PIOP de Spartan y PIOP de HyperPlonk, entre otros, que tienen 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 demostrar si la 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 los resultados de la evaluación de dicho polinomio, al tiempo que oculta otra información sobre el polinomio. Los esquemas de compromiso polinómico más comunes incluyen KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) y Brakedown, entre otros. Diferentes PCS tienen diferentes rendimientos, seguridad y escenarios de aplicación.
Según las necesidades específicas, 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 y Bulletproofs PCS, y se basa en la curva Pasta. Al diseñar Halo2, se presta atención a la escalabilidad y se elimina la configuración de confianza en el 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 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 la verificación, sino que también determina si el sistema puede lograr transparencia sin la 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 + dominio binario. En concreto, Binius incluye cinco tecnologías clave para lograr su eficiencia y seguridad. Primero, la aritmética basada en torres de dominios binarios constituye la base de su computación, lo que permite realizar cálculos simplificados en el dominio binario. En segundo lugar, Binius adapta la verificación de producto y permutación 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. Tercero, el protocolo introduce una nueva prueba de desplazamiento multilinéal, optimizando la eficiencia de la verificación de relaciones multilinales en dominios pequeños. 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 de polinomios de pequeño dominio (Small-Field PCS), permitiendo un sistema de prueba eficiente en el dominio binario y reduciendo los costos asociados normalmente con dominios grandes.
2.1 Campo finito: aritmética basada en torres de campos binarios
Los campos binarios en torres son clave para implementar cálculos verificables rápidos, 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 al rendimiento. Además, la estructura del campo binario admite un proceso de aritmética simplificado, es decir, las operaciones realizadas en el campo binario se pueden expresar 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 de torre, hacen que los campos binarios sean particularmente adecuados para sistemas de prueba escalables como Binius.
El término "canónico" se refiere a la representación única y directa de elementos 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 de campo binario de k bits. Esto es diferente del campo primo, que no puede 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 cada cadena de 32 bits puede corresponder de manera única a un elemento de campo, mientras que el campo binario ofrece 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 utiliza en AES), la reducción de Montgomery (como se utiliza en POLYVAL) y la reducción recursiva (como Tower). El documento "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" señala que en el campo binario, tanto en las operaciones de suma como de multiplicación no es necesario introducir acarreo, y la operación de cuadrado en el campo 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 puede interpretarse de varias maneras en el contexto de un campo binario. Puede considerarse como un elemento único en un campo binario de 128 bits, o ser descompuesta en dos elementos de campo de torre de 64 bits, cuatro elementos de campo de torre de 32 bits, dieciséis 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 (typecast) de la cadena de bits, 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 documento "On Efficient Inversion in Tower Fields of Characteristic Two" explora la complejidad computacional de realizar multiplicación, cuadrados y operaciones de inversión en un campo binario de torre de n bits (descomponible en subcampos de m bits).
2.2 PIOP: versión adaptada de HyperPlonk Product y PermutationCheck------aplicable a campos binarios
El diseño de PIOP en el protocolo Binius se inspira en HyperPlonk y utiliza una serie de mecanismos de verificación centrales para validar la corrección de polinomios y conjuntos multivariados. Estas verificaciones centrales incluyen:
GateCheck: Verifica si el testigo secreto ω y la entrada pública x satisfacen la relación de cálculo 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 garantizar la consistencia de las permutaciones 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 garantizar la corrección del producto polinómico.
ZeroCheck: Verifica si un polinomio multivariable en un hipercubo booleano es cero en cualquier punto ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, para garantizar 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 del polinomio multivariable en una evaluación de polinomio univariable, 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 y realizar el procesamiento por lotes de múltiples instancias de verificación de sumas.
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 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 dicho valor en 1, reduciendo así la complejidad computacional.
Manejo del problema de la división por cero: HyperPlonk no pudo manejar adecuadamente la situación de división por cero, lo que llevó a no poder afirmar si U es distinto de 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 entre columnas: HyperPlonk no tiene esta función; 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 proporcionar un mejor soporte funcional al manejar la verificación de polinomios multivariables más complejos. Estas mejoras no solo abordan las limitaciones en HyperPlonk, sino que también establecen una base para futuros sistemas de prueba basados en campos binarios.
2.3 PIOP: nuevo argumento de desplazamiento multilineal ------ aplicable a 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 manejadores de entrada u otros polinomios virtuales. A continuación se presentan dos métodos clave: