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 un bucle for, los valores booleanos, los contadores, etc. Sin embargo, 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 ocuparán todo el campo, incluso si el valor original en sí 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 la primera generación de STARKs es de 252 bits, el ancho de codificación de la segunda generación de STARKs es de 64 bits, y el ancho de codificación de la tercera generación de STARKs 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 campo binario permite operar directamente sobre los bits, con una codificación compacta y eficiente sin ningún espacio desperdiciado, es decir, la cuarta generación de STARKs.
En comparación con los dominios finitos descubiertos en investigaciones recientes como Goldilocks, BabyBear y Mersenne31, la investigación sobre los 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 campo F28;
Código de autenticación de mensajes Galois ( GMAC ), basado en el dominio 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 de 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 debe depender 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 operan en el dominio base, logrando así una alta eficiencia en dominios pequeños. Sin embargo, el chequeo de puntos aleatorios y el cálculo de FRI aún deben profundizar en una extensión de dominio más grande para garantizar la seguridad requerida.
Al construir un sistema de pruebas basado en campos binarios, existen 2 problemas prácticos: al calcular la representación de la traza en STARKs, el tamaño del campo utilizado debe ser mayor que el grado del polinomio; al comprometer el árbol de Merkle en STARKs, es necesario realizar la codificación de Reed-Solomon, y el tamaño del campo 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 de manera separada y representa los mismos datos de dos formas diferentes: primero, utilizando un polinomio multivariado (, específicamente un polinomio multilinario ), en lugar de un polinomio univariado, para representar 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 los STARKs, pero se puede considerar el hipercubo como un cuadrado ), y realizar la extensión de Reed-Solomon basada 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 actualmente suele incluir las siguientes dos partes:
Prueba de Oracle Interactiva Polinómica Teórica de la Información (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, como núcleo del sistema de pruebas, transforma la relación de cálculo de entrada en igualdad polinómica verificable. Diferentes protocolos PIOP, a través de la interacción con el validador, permiten que el probador envíe polinomios de manera gradual, de modo que el validador pueda verificar si el cálculo es correcto al consultar los resultados de la evaluación de un número limitado de polinomios. Los protocolos PIOP existentes incluyen: PLONK PIOP, Spartan PIOP y HyperPlonk PIOP, cada uno de los cuales tiene un enfoque diferente para el tratamiento de expresiones polinómicas, lo que afecta el rendimiento y la eficiencia de todo el sistema SNARK.
Esquema de Compromiso Polinomial ( Polynomial Commitment Scheme, PCS ): El esquema de compromiso polinomial se utiliza para demostrar si se cumple la ecuación polinómica generada por PIOP. PCS es una herramienta criptográfica que permite al probador comprometerse a un polinomio y luego validar el resultado de la evaluación de ese polinomio, mientras oculta otra información sobre el polinomio. Los esquemas de compromiso polinomial más 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, elige diferentes PIOP y PCS, y en combinación con un campo finito o curva elíptica adecuados, se pueden construir sistemas de prueba con diferentes atributos. Por ejemplo:
• Halo2: combinando PLONK PIOP con Bulletproofs PCS y basado en la curva Pasta. Halo2 se diseñó con un enfoque en la escalabilidad y la eliminación del setup confiable en el protocolo ZCash.
• Plonky2: utiliza PLONK PIOP combinado con FRI PCS, y se basa en el campo Goldilocks. Plonky2 está diseñado para lograr una recursión eficiente. Al diseñar estos sistemas, la 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 una configuración confiable previa, y si puede soportar funciones extendidas como pruebas recursivas o pruebas agregadas.
Binius: HyperPlonk PIOP + Brakedown PCS + dominio binario. Específicamente, Binius incluye cinco tecnologías clave para lograr su eficiencia y seguridad. Primero, la aritmética basada en torres de dominios binarios (towers of binary fields) constituye la base de su cálculo, permitiendo realizar operaciones simplificadas dentro del dominio binario. En segundo lugar, Binius, en su protocolo de prueba de Oracle interactivo (PIOP), adapta la verificación de producto y permutación de HyperPlonk, asegurando una verificación de consistencia segura y eficiente entre las variables y sus permutaciones. Tercero, el protocolo introduce una nueva prueba de desplazamiento multilineal, optimizando la eficiencia de la verificación de relaciones multilineales en pequeños dominios. Cuarto, Binius utiliza una versión mejorada de la prueba de búsqueda Lasso, proporcionando flexibilidad y una fuerte seguridad al mecanismo de búsqueda. Por último, el protocolo utiliza un esquema de compromiso polinómico de pequeño dominio (Small-Field PCS), permitiéndole implementar un sistema de pruebas eficiente en el dominio binario y reduciendo los costos generalmente asociados con grandes dominios.
( 2.1 Campo finito: aritmética basada en torres de campos binarios
Los campos binarios en torre son clave para implementar cálculos rápidos y verificables, principalmente debido a dos aspectos: cálculos eficientes y aritmética eficiente. Los campos binarios, por su naturaleza, soportan operaciones aritméticas altamente eficientes, lo que los convierte en una elección ideal para aplicaciones criptográficas sensibles a los requisitos de rendimiento. Además, la estructura de campo binario admite un proceso de aritmética simplificado, es decir, las operaciones realizadas sobre 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 jerarquía 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 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 un 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, así como 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 comúnmente utilizados 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 "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" señala que en el campo binario no es necesario introducir acarreo en las operaciones de suma y multiplicación, y que la operación de cuadrado en el campo binario es muy eficiente, ya que sigue la regla simplificada de (X + Y )2 = X2 + Y 2.
Como se muestra en la Figura 1, una cadena de 128 bits: esta cadena puede interpretarse de varias maneras en el contexto de un campo binario. Puede considerarse un elemento único en un campo binario de 128 bits, o descomponerse en dos elementos de campo de torre de 64 bits, cuatro elementos de campo de torre de 32 bits, 16 elementos de campo de torre de 8 bits, o 128 elementos de campo F2. Esta flexibilidad de representación no requiere ningún costo computacional, solo una conversión de tipo de cadena de bits (typecast), lo que es una propiedad muy interesante y útil. Al mismo tiempo, los elementos de campo pequeños se pueden empaquetar en elementos de campo más grandes sin necesidad de costos computacionales adicionales. El protocolo Binius aprovecha esta característica para mejorar la eficiencia computacional. Además, el artículo "On Efficient Inversion in Tower Fields of Characteristic Two" explora la complejidad computacional de realizar multiplicación, cuadrado y operaciones de inversión en un campo binario de torre de n bits ( descompuesto en un subcampo de m bits ).
( 2.2 PIOP: versión adaptada del producto HyperPlonk y PermutationCheck------aplicable a campos binarios
El diseño de PIOP en el protocolo Binius se basa en HyperPlonk y utiliza una serie de mecanismos de verificación clave para validar la corrección de polinomios y conjuntos multivariables. Estas verificaciones clave incluyen:
GateCheck: Verifica si el testigo de confidencialidad ω y la entrada pública x satisfacen la relación de operación del circuito C)x,ω###=0, para asegurar el correcto funcionamiento del circuito.
PermutationCheck: Verificar si los resultados de evaluación de dos polinomios multivariables f y g en el hipercubo booleana 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: Verificar si la evaluación del polinomio está en la tabla de búsqueda dada, es decir, f)Bµ) ⊆ T(Bµ), asegurando que ciertos valores estén dentro del rango especificado.
MultisetCheck: Verifica si dos conjuntos multivariables son iguales, es decir, {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, garantizando la consistencia entre múltiples conjuntos.
ProductCheck: Verificar si la evaluación de polinomios racionales 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 un 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 polinomios univariables, reduce la complejidad computacional para el 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 mejorado 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 este valor en 1, reduciendo así la complejidad computacional.
Manejo del problema de división por cero: HyperPlonk no pudo manejar adecuadamente las situaciones de división por cero, lo que llevó a la incapacidad de 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 también puede continuar procesándose, permitiendo la extensió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 permutación entre varias columnas, lo que permite a Binius manejar situaciones de arreglos polinómicos más complejas.
Por lo tanto, Binius ha mejorado el mecanismo existente PIOPSumCheck, aumentando la flexibilidad y eficiencia del protocolo, especialmente al manejar la verificación de polinomios multivariables más complejos, proporcionando un soporte funcional más fuerte. Estas mejoras no solo abordan las limitaciones de HyperPlonk, sino que también sientan las bases 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, virtual
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.
14 me gusta
Recompensa
14
5
Compartir
Comentar
0/400
AirdropHunter007
· hace12h
¿Cuánto se puede aprovechar de esto?
Ver originalesResponder0
GateUser-3824aa38
· 07-20 17:31
¡Sólo 32 dígitos y ya es demasiado! ¡Es suficiente para competir!
Ver originalesResponder0
SchroedingerGas
· 07-20 17:30
¡La tarifa de gas es realmente demasiado abstracta! ¿Quién lo entiende?
Ver originalesResponder0
WhaleWatcher
· 07-20 17:23
Optimización de dominio alcista, ya era hora de que este círculo cambiara.
Ver originalesResponder0
MechanicalMartel
· 07-20 17:08
stark es demasiado pesado, ¿cuándo podrá ser más rápido?
Análisis del protocolo Binius: optimización e innovación de STARKs bajo 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 los programas reales son bastante pequeños, como los índices en un bucle for, los valores booleanos, los contadores, etc. Sin embargo, 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 ocuparán todo el campo, incluso si el valor original en sí 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 la primera generación de STARKs es de 252 bits, el ancho de codificación de la segunda generación de STARKs es de 64 bits, y el ancho de codificación de la tercera generación de STARKs 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 campo binario permite operar directamente sobre los bits, con una codificación compacta y eficiente sin ningún espacio desperdiciado, es decir, la cuarta generación de STARKs.
Tabla 1: Ruta de derivación de STARKs
| Álgebra | Ancho de codificación | Sistema representativo | |------|----------|----------| | Primera generación | 252bit | StarkWare | | Segunda generación | 64bit | Plonky2 | | Tercera generación | 32bit | Polygon zkEVM | | Cuarta generación | 1bit | Binius |
En comparación con los dominios finitos descubiertos en investigaciones recientes como Goldilocks, BabyBear y Mersenne31, la investigación sobre los 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 campo F28;
Código de autenticación de mensajes Galois ( GMAC ), basado en el dominio 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 de 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 debe depender 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 operan en el dominio base, logrando así una alta eficiencia en dominios pequeños. Sin embargo, el chequeo de puntos aleatorios y el cálculo de FRI aún deben profundizar en una extensión de dominio más grande para garantizar la seguridad requerida.
Al construir un sistema de pruebas basado en campos binarios, existen 2 problemas prácticos: al calcular la representación de la traza en STARKs, el tamaño del campo utilizado debe ser mayor que el grado del polinomio; al comprometer el árbol de Merkle en STARKs, es necesario realizar la codificación de Reed-Solomon, y el tamaño del campo 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 de manera separada y representa los mismos datos de dos formas diferentes: primero, utilizando un polinomio multivariado (, específicamente un polinomio multilinario ), en lugar de un polinomio univariado, para representar 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 los STARKs, pero se puede considerar el hipercubo como un cuadrado ), y realizar la extensión de Reed-Solomon basada 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 actualmente suele incluir las siguientes dos partes:
Prueba de Oracle Interactiva Polinómica Teórica de la Información (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, como núcleo del sistema de pruebas, transforma la relación de cálculo de entrada en igualdad polinómica verificable. Diferentes protocolos PIOP, a través de la interacción con el validador, permiten que el probador envíe polinomios de manera gradual, de modo que el validador pueda verificar si el cálculo es correcto al consultar los resultados de la evaluación de un número limitado de polinomios. Los protocolos PIOP existentes incluyen: PLONK PIOP, Spartan PIOP y HyperPlonk PIOP, cada uno de los cuales tiene un enfoque diferente para el tratamiento de expresiones polinómicas, lo que afecta el rendimiento y la eficiencia de todo el sistema SNARK.
Esquema de Compromiso Polinomial ( Polynomial Commitment Scheme, PCS ): El esquema de compromiso polinomial se utiliza para demostrar si se cumple la ecuación polinómica generada por PIOP. PCS es una herramienta criptográfica que permite al probador comprometerse a un polinomio y luego validar el resultado de la evaluación de ese polinomio, mientras oculta otra información sobre el polinomio. Los esquemas de compromiso polinomial más 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, elige diferentes PIOP y PCS, y en combinación con un campo finito o curva elíptica adecuados, se pueden construir sistemas de prueba con diferentes atributos. Por ejemplo:
• Halo2: combinando PLONK PIOP con Bulletproofs PCS y basado en la curva Pasta. Halo2 se diseñó con un enfoque en la escalabilidad y la eliminación del setup confiable en el protocolo ZCash.
• Plonky2: utiliza PLONK PIOP combinado con FRI PCS, y se basa en el campo Goldilocks. Plonky2 está diseñado para lograr una recursión eficiente. Al diseñar estos sistemas, la 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 una configuración confiable previa, y si puede soportar funciones extendidas como pruebas recursivas o pruebas agregadas.
Binius: HyperPlonk PIOP + Brakedown PCS + dominio binario. Específicamente, Binius incluye cinco tecnologías clave para lograr su eficiencia y seguridad. Primero, la aritmética basada en torres de dominios binarios (towers of binary fields) constituye la base de su cálculo, permitiendo realizar operaciones simplificadas dentro del dominio binario. En segundo lugar, Binius, en su protocolo de prueba de Oracle interactivo (PIOP), adapta la verificación de producto y permutación de HyperPlonk, asegurando una verificación de consistencia segura y eficiente entre las variables y sus permutaciones. Tercero, el protocolo introduce una nueva prueba de desplazamiento multilineal, optimizando la eficiencia de la verificación de relaciones multilineales en pequeños dominios. Cuarto, Binius utiliza una versión mejorada de la prueba de búsqueda Lasso, proporcionando flexibilidad y una fuerte seguridad al mecanismo de búsqueda. Por último, el protocolo utiliza un esquema de compromiso polinómico de pequeño dominio (Small-Field PCS), permitiéndole implementar un sistema de pruebas eficiente en el dominio binario y reduciendo los costos generalmente asociados con grandes dominios.
( 2.1 Campo finito: aritmética basada en torres de campos binarios
Los campos binarios en torre son clave para implementar cálculos rápidos y verificables, principalmente debido a dos aspectos: cálculos eficientes y aritmética eficiente. Los campos binarios, por su naturaleza, soportan operaciones aritméticas altamente eficientes, lo que los convierte en una elección ideal para aplicaciones criptográficas sensibles a los requisitos de rendimiento. Además, la estructura de campo binario admite un proceso de aritmética simplificado, es decir, las operaciones realizadas sobre 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 jerarquía 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 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 un 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, así como 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 comúnmente utilizados 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 "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" señala que en el campo binario no es necesario introducir acarreo en las operaciones de suma y multiplicación, y que la operación de cuadrado en el campo binario es muy eficiente, ya que sigue la regla simplificada de (X + Y )2 = X2 + Y 2.
Como se muestra en la Figura 1, una cadena de 128 bits: esta cadena puede interpretarse de varias maneras en el contexto de un campo binario. Puede considerarse un elemento único en un campo binario de 128 bits, o descomponerse en dos elementos de campo de torre de 64 bits, cuatro elementos de campo de torre de 32 bits, 16 elementos de campo de torre de 8 bits, o 128 elementos de campo F2. Esta flexibilidad de representación no requiere ningún costo computacional, solo una conversión de tipo de cadena de bits (typecast), lo que es una propiedad muy interesante y útil. Al mismo tiempo, los elementos de campo pequeños se pueden empaquetar en elementos de campo más grandes sin necesidad de costos computacionales adicionales. El protocolo Binius aprovecha esta característica para mejorar la eficiencia computacional. Además, el artículo "On Efficient Inversion in Tower Fields of Characteristic Two" explora la complejidad computacional de realizar multiplicación, cuadrado y operaciones de inversión en un campo binario de torre de n bits ( descompuesto en un subcampo de m bits ).
( 2.2 PIOP: versión adaptada del producto HyperPlonk y PermutationCheck------aplicable a campos binarios
El diseño de PIOP en el protocolo Binius se basa en HyperPlonk y utiliza una serie de mecanismos de verificación clave para validar la corrección de polinomios y conjuntos multivariables. Estas verificaciones clave incluyen:
GateCheck: Verifica si el testigo de confidencialidad ω y la entrada pública x satisfacen la relación de operación del circuito C)x,ω###=0, para asegurar el correcto funcionamiento del circuito.
PermutationCheck: Verificar si los resultados de evaluación de dos polinomios multivariables f y g en el hipercubo booleana 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: Verificar si la evaluación del polinomio está en la tabla de búsqueda dada, es decir, f)Bµ) ⊆ T(Bµ), asegurando que ciertos valores estén dentro del rango especificado.
MultisetCheck: Verifica si dos conjuntos multivariables son iguales, es decir, {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, garantizando la consistencia entre múltiples conjuntos.
ProductCheck: Verificar si la evaluación de polinomios racionales 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 un 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 polinomios univariables, reduce la complejidad computacional para el 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 mejorado 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 este valor en 1, reduciendo así la complejidad computacional.
Manejo del problema de división por cero: HyperPlonk no pudo manejar adecuadamente las situaciones de división por cero, lo que llevó a la incapacidad de 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 también puede continuar procesándose, permitiendo la extensió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 permutación entre varias columnas, lo que permite a Binius manejar situaciones de arreglos polinómicos más complejas.
Por lo tanto, Binius ha mejorado el mecanismo existente PIOPSumCheck, aumentando la flexibilidad y eficiencia del protocolo, especialmente al manejar la verificación de polinomios multivariables más complejos, proporcionando un soporte funcional más fuerte. Estas mejoras no solo abordan las limitaciones de HyperPlonk, sino que también sientan las bases 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, virtual