Título original reenviado 'Vitalik explica Binius en detalle: un sistema de prueba eficiente basado en campos binarios'

Esta publicación está destinada principalmente a lectores que estén familiarizados aproximadamente con la criptografía de la era de 2019, especialmente SNARKs y STARKs. Si no lo estás, te recomiendo leer primero esos artículos. Un agradecimiento especial a Justin Drake, Jim Posen, Benjamin Diamond y Radi Cojbasic por sus comentarios y revisión.

Durante los últimos dos años, STARKs se han convertido en una tecnología crucial e irremplazable para hacer de manera eficiente pruebas criptográficas fáciles de verificar de declaraciones muy complicadas (por ejemplo, demostrar que un bloque de Ethereum es válido). Una razón clave es el tamaño reducido de los campos: mientras que SNARKs basados en curvas elípticas requieren trabajar con enteros de 256 bits para ser suficientemente seguros, STARKs te permiten usar tamaños de campo mucho más pequeños, que son más eficientes: primero el campo Goldilocks (enteros de 64 bits), y luego Mersenne31 y BabyBear (ambos de 31 bits). Gracias a estas ganancias de eficiencia, Plonky2, que utiliza Goldilocks, es cientos de veces más rápido en demostrar muchos tipos de cálculos que sus predecesores.

Una pregunta natural que surge es: ¿podemos llevar esta tendencia a su conclusión lógica, construyendo sistemas de prueba que funcionen aún más rápido operando directamente sobre ceros y unos? Esto es exactamente lo que Binius está tratando de hacer, utilizando una serie de trucos matemáticos que lo hacen muy diferente de los SNARKs y STARKs de hace tres años. Esta publicación analiza las razones por las cuales los campos pequeños hacen que la generación de pruebas sea más eficiente, por qué los campos binarios son excepcionalmente poderosos y los trucos que Binius utiliza para hacer que las pruebas sobre campos binarios funcionen de manera tan efectiva.

Binius. Al final de esta publicación, deberías ser capaz de entender cada parte de este diagrama.

Recap: campos finitos

Una de las tareas clave de un sistema de prueba criptográfica es operar sobre grandes cantidades de datos, manteniendo los números pequeños. Si puedes comprimir una declaración sobre un gran programa en una ecuación matemática que involucra unos pocos números, pero esos números son tan grandes como el programa original, no has ganado nada.

Para hacer aritmética complicada manteniendo los números pequeños, los criptógrafos generalmente usan aritmética modular. Elegimos algún número primo 'módulo' p. El operador % significa 'tomar el resto de': 15 % 7=1, 53 % 10=3, etc (nota que la respuesta siempre es no negativa, por ejemplo -1 % 10=9).

Probablemente ya has visto aritmética modular, en el contexto de sumar y restar tiempo (por ejemplo, ¿qué hora es cuatro horas después de las 9:00?). Pero aquí, no solo sumamos y restamos módulo algún número, también multiplicamos, dividimos y tomamos exponentes.

Redifinimos:

Las reglas anteriores son todas autoconsistentes. Por ejemplo, si p=7, entonces:

5+3=1 (because 8%7=1)

1-3=5 (porque -2%7=5)

2*5=3

3/5=2

Un término más general para este tipo de estructura es un campo finito. Un campo finito es una estructura matemática que obedece las leyes habituales de la aritmética, pero donde hay un número limitado de valores posibles, por lo que cada valor se puede representar en un tamaño fijo.

La aritmética modular (o campos primos) es el tipo más común de cuerpo finito, pero también hay otro tipo: los campos de extensión. Probablemente ya hayas visto un campo de extensión antes: los números complejos. "Imaginamos" un nuevo elemento, al que etiquetamos i, y declaramos que satisface i2=−1. A continuación, puedes tomar cualquier combinación de números regulares e i, y hacer cálculos matemáticos con ella: (3i+2)∗(2i+4)= 6i2+12i+4i+8=16i+2. Del mismo modo, podemos tomar extensiones de campos primos. A medida que comenzamos a trabajar en campos que son más pequeños, las extensiones de los campos primos se vuelven cada vez más importantes para preservar la seguridad, y los campos binarios (que usa Binius) dependen completamente de las extensiones para tener una utilidad práctica.

Resumen: aritmetización

La forma en que los SNARKs y STARKs prueban cosas sobre programas de computadora es a través de aritmetización: conviertes una afirmación sobre un programa que deseas probar, en una ecuación matemática que involucra polinomios. Una solución válida a la ecuación corresponde a una ejecución válida del programa.

Para dar un ejemplo simple, supongamos que calculé el 100-ésimo número de Fibonacci y quiero demostrarte cuál es. Creo un polinomio 𝐹 que codifica los números de Fibonacci: así que 𝐹(0)=𝐹(1)=1, 𝐹(2)=2, 𝐹(3)=3, 𝐹(4)=5, y así sucesivamente durante 100 pasos. La condición que necesito demostrar es que 𝐹(𝑥+2)=𝐹(𝑥)+𝐹(𝑥+1) en el rango 𝑥={0,1…98}. Puedo convencerte de esto dándote el cociente:

donde Z(x) = (x-0)(x-1) …(x-98). . Si puedo demostrar que existe F y H que satisfacen esta ecuación, entonces F debe satisfacer F(x+2)-F(x+1)-F(x) en el rango. Si además verifico que F satisface F(0)=F(1)=1, entonces F(100) debe ser en realidad el número Fibonacci 100.

Si quieres demostrar algo más complicado, entonces reemplazas la relación “simple” 𝐹(𝑥+2)=𝐹(𝑥)+𝐹(𝑥+1) con una ecuación más complicada, que básicamente dice que “𝐹(𝑥+1) es la salida de inicializar una máquina virtual con el estado 𝐹(𝑥) y ejecutar un paso computacional”. También puedes reemplazar el número 100 con un número mayor, por ejemplo, 100000000, para acomodar más pasos.

Todos los SNARKs y STARKs se basan en esta idea de usar una ecuación simple sobre polinomios (o a veces vectores y matrices) para representar un gran número de relaciones entre valores individuales. No todos implican comprobar la equivalencia entre pasos computacionales adyacentes de la misma manera que arriba: PLONK no lo hace, por ejemplo, y tampoco lo hace R1CS. Pero muchos de los más eficientes sí lo hacen, porque hacer cumplir la misma verificación (o las mismas pocas verificaciones) muchas veces hace más fácil minimizar el sobrecosto.

Plonky2: from 256-bit SNARKs and STARKs to 64-bit… solo STARKs

Hace cinco años, un resumen razonable de los diferentes tipos de prueba de conocimiento cero era el siguiente. Hay dos tipos de pruebas: SNARKs (basadas en curvas elípticas) y STARKs (basadas en hash). Técnicamente, los STARKs son un tipo de SNARK, pero en la práctica es común usar "SNARK" para referirse solo a la variedad basada en curvas elípticas, y "STARK" para referirse a construcciones basadas en hash. Los SNARKs son pequeños, por lo que puedes verificarlos muy rápidamente y ajustarlos fácilmente a la cadena. Los STARKs son grandes, pero no requieren configuraciones confiables y son resistentes a los cuánticos.

STARKs trabajan tratando los datos como un polinomio, calculando evaluaciones de ese polinomio en una gran cantidad de puntos, y usando la raíz de Merkle de esos datos extendidos como el "compromiso polinómico"

Un dato clave de la historia es que los SNARKs basados en curvas elípticas se utilizaron primero de forma generalizada: fue necesario esperar hasta aproximadamente 2018 para que los STARKs fueran lo suficientemente eficientes gracias a FRI, y para entonces Zcash ya llevaba más de un año en funcionamiento. Los SNARKs basados en curvas elípticas tienen una limitación clave: si deseas utilizar SNARKs basados en curvas elípticas, entonces la aritmética en estas ecuaciones debe realizarse con enteros módulo el número de puntos en la curva elíptica. Este es un número grande, generalmente cerca de 2256: por ejemplo, para la curva bn128, es 21888242871839275222246405745257275088548364400416034343698204186575808495617. Pero el cálculo real se realiza con números pequeños: si piensas en un programa "real" en tu lenguaje favorito, la mayoría de las cosas con las que trabaja son contadores, índices en bucles, posiciones en el programa, bits individuales que representan Verdadero o Falso, y otras cosas que casi siempre serán solo unos pocos dígitos de longitud.

Incluso si sus datos "originales" están compuestos por "números" pequeños, el proceso de prueba requiere calcular cocientes, extensiones, combinaciones lineales aleatorias y otras transformaciones de los datos, lo que conduce a un número igual o mayor de objetos que, en promedio, son tan grandes como el tamaño completo de su campo. Esto crea una ineficiencia clave: para demostrar un cálculo sobre n valores pequeños, debe realizar aún más cálculos sobre n valores mucho más grandes. Al principio, los STARK heredaron el hábito de usar campos de 256 bits de los SNARK, y sufrieron la misma ineficiencia.

Una extensión Reed-Solomon de algunas evaluaciones polinomiales. Aunque los valores originales son pequeños, los valores adicionales explotan hasta el tamaño completo del campo (en este caso 2 elevado a la potencia 31 -1)

En 2022, se lanzó Plonky2. La principal innovación de Plonky2 fue hacer que el módulo aritmético fuera un número primo más pequeño: 2⁶⁴−2³²+1=18446744069414584321. Ahora, cada suma o multiplicación siempre se puede hacer en solo unas pocas instrucciones en una CPU, y el hash de todos los datos juntos es 4 veces más rápido que antes. Pero esto viene con un problema: este enfoque es solo para STARK. Si intenta usar un SNARK, con una curva elíptica de un tamaño tan pequeño, la curva elíptica se vuelve insegura.

Para seguir siendo seguros, Plonky2 también necesitaba introducir campos de extensión. Una técnica clave en la verificación de ecuaciones aritméticas es "muestrear en un punto aleatorio": si quieres comprobar si 𝐻(𝑥)∗𝑍(𝑥) realmente es igual a 𝐹(𝑥+2)−𝐹(𝑥+1)−𝐹(𝑥), puedes elegir alguna coordenada aleatoria 𝑟, proporcionar pruebas de apertura de compromiso polinomial que demuestran 𝐻(𝑟), 𝑍(𝑟), 𝐹(𝑟), 𝐹(𝑟+1) y 𝐹(𝑟+2), y luego comprobar realmente si 𝐻(𝑟)∗𝑍(𝑟) es igual a 𝐹(𝑟+2)−𝐹(𝑟+1)−𝐹(𝑟). Si el atacante puede adivinar la coordenada de antemano, el atacante puede engañar al sistema de prueba, por eso debe ser aleatorio. Pero esto también significa que la coordenada debe ser muestreada de un conjunto lo suficientemente grande como para que el atacante no pueda adivinarla por casualidad. Si el módulo está cerca de 2²⁵⁶, esto es claramente el caso. Pero con un módulo de 2⁶⁴−2³²+1, no estamos del todo allí, y si bajamos a 2³¹−1, definitivamente no es el caso. Intentar falsificar una prueba dos mil millones de veces hasta que uno tenga suerte está absolutamente dentro del alcance de las capacidades de un atacante.

Para detener esto, muestreamos 𝑟 de un campo de extensión. Por ejemplo, puedes definir 𝑦 donde 𝑦³=5, and take combinations of 1, 𝑦 and 𝑦². Esto aumenta el número total de coordenadas nuevamente a aproximadamente 2⁹³La mayor parte de los polinomios calculados por el demostrador no entran en este campo de extensión; simplemente utilizan enteros módulo 2³¹−1, y por lo tanto todavía obtienes todas las eficiencias al usar el campo pequeño. Pero la verificación de puntos aleatorios y el cálculo de FRI, se sumergen en este campo más grande, para obtener la seguridad necesaria.

Desde pequeños primos a binario

Las computadoras realizan operaciones aritméticas representando números más grandes como secuencias de ceros y unos, y construyendo "circuitos" sobre esos bits para calcular cosas como la suma y la multiplicación. Las computadoras están especialmente optimizadas para realizar cálculos con enteros de 16 bits, 32 bits y 64 bits. Módulos como 2⁶⁴−2³²+1 and 2³¹−1 son elegidos no solo porque encajan dentro de esos límites, sino también porque se alinean bien con esos límites: puedes hacer multiplicación módulo 2⁶⁴−2³²+1 al hacer multiplicaciones regulares de 32 bits y desplazar y copiar las salidas bit a bit en varios lugares; este artículo explica bien algunos de los trucos.

Lo que sería aún mejor, sin embargo, es hacer cálculos en binario directamente. ¿Y si la suma pudiera ser simplemente XOR, sin necesidad de preocuparse por el desbordamiento de sumar 1 + 1 en una posición de un solo bit a la siguiente posición de bit? ¿Y si la multiplicación pudiera ser más paralelizable de la misma manera? Y todas estas ventajas vendrían además de poder representar los valores Verdadero/Falso con solo un bit.

Capturar directamente estas ventajas de realizar cálculos binarios es exactamente lo que Binius está tratando de hacer. Una tabla de la presentación del zkSummit del equipo de Binius muestra las ganancias de eficiencia:

A pesar de tener aproximadamente el mismo “tamaño”, una operación de campo binario de 32 bits requiere 5 veces menos recursos computacionales que una operación sobre el campo de Mersenne de 31 bits.

De polinomios univariados a hipercubos

Supongamos que estamos convencidos por este razonamiento y queremos hacer todo sobre bits (ceros y unos). ¿Cómo nos comprometemos realmente con un polinomio que represente mil millones de bits?

Aquí nos enfrentamos a dos problemas prácticos:

1. Para que un polinomio represente muchos valores, esos valores deben ser accesibles en evaluaciones del polinomio: en nuestro ejemplo de Fibonacci anterior, 𝐹(0), 𝐹(1) ... 𝐹(100), y en un cálculo más grande, los índices llegarían a millones. Y el campo que usamos debe contener números que lleguen a ese tamaño.

2. Demostrar cualquier cosa sobre un valor al que nos estamos comprometiendo en un árbol de Merkle (como hacen todos los STARKs) requiere codificarlo con Reed-Solomon: extendiendo 𝑛 valores en, por ejemplo, 8𝑛 valores, utilizando la redundancia para evitar que un probador malicioso haga trampa falsificando un valor en medio del cálculo. Esto también requiere tener un campo lo suficientemente grande: para extender un millón de valores a 8 millones, necesitas 8 millones de puntos diferentes en los que evaluar el polinomio.

Una idea clave en Binius es resolver estos dos problemas por separado, y hacerlo representando los mismos datos de dos maneras diferentes. Primero, el polinomio en sí. Los SNARK basados en curvas elípticas, los STARK de la era 2019, Plonky2 y otros sistemas generalmente se ocupan de polinomios sobre una variable: F(x). Binius, por su parte, se inspira en el protocolo espartano, y trabaja con polinomios multivariantes: F(x1,x2... xk). De hecho, representamos toda la traza computacional en el "hipercubo" de evaluaciones donde cada xi es 0 o 1. Por ejemplo, si quisiéramos representar una secuencia de números de Fibonacci, y todavía estuviéramos usando un campo lo suficientemente grande como para representarlos, podríamos visualizar los primeros dieciséis de ellos como algo así:

Es decir, 𝐹(0,0,0,0) sería 1, 𝐹(1,0,0,0) también sería 1, 𝐹(0,1,0,0) sería 2, y así sucesivamente, hasta llegar a 𝐹(1,1,1,1)=987. Dado un hipercubo de evaluaciones, hay exactamente un polinomio multilíneal (grado-1 en cada variable) que produce esas evaluaciones. Así que podemos pensar en ese conjunto de evaluaciones como representando el polinomio; nunca necesitamos realmente molestarnos en calcular los coeficientes.

Este ejemplo es, por supuesto, solo para fines ilustrativos: en la práctica, el objetivo de ir a un hipercubo es permitirnos trabajar con bits individuales. La forma “Binius-native” de contar números de Fibonacci sería utilizar un cubo de dimensiones superiores, utilizando cada conjunto de por ejemplo 16 bits para almacenar un número. Esto requiere cierta astucia para implementar la suma de enteros sobre los bits, pero con Binius no es demasiado difícil.

Ahora, llegamos a la codificación de borrado. La forma en que funcionan los STARK es: se toman n valores, Reed-Solomon los extiende a un mayor número de valores (a menudo 8n, generalmente entre 2n y 32n), y luego se seleccionan aleatoriamente algunas ramas de Merkle de la extensión y se realiza algún tipo de comprobación sobre ellas. Un hipercubo tiene una longitud de 2 en cada dimensión. Por lo tanto, no es práctico extenderlo directamente: no hay suficiente "espacio" para muestrear ramas de Merkle a partir de 16 valores. Entonces, ¿qué hacemos en su lugar? ¡Pretendemos que el hipercubo es un cuadrado!

Simple Binius - un ejemplo

Ver aquípara una implementación de Python de este protocolo.

Vamos a través de un ejemplo, utilizando enteros regulares como nuestro campo por conveniencia (en una implementación real estos serán elementos de campo binario). Primero, tomamos el hipercubo al que queremos comprometernos, y lo codificamos como un cuadrado:

Ahora, extendemos Reed-Solomon el cuadrado. Es decir, tratamos cada fila como si fuera un polinomio de grado 3 evaluado en x = {0, 1, 2, 3} y evaluamos el mismo polinomio en x = {4, 5, 6, 7}:

¡Observa que los números aumentan rápidamente! Por eso, en una implementación real, siempre usamos un campo finito para esto, en lugar de enteros regulares: si usáramos enteros módulo 11, por ejemplo, la extensión de la primera fila sería [3, 10, 0, 6].

Si quieres jugar con la extensión y verificar los números aquí por ti mismo, puedes usar mi código de extensión Reed-Solomon simple aquí.

A continuación, tratamos esta extensión como columnas y creamos un árbol de Merkle de las columnas. La raíz del árbol de Merkle es nuestro compromiso.

Ahora, supongamos que el probador quiere probar una evaluación de este polinomio en algún momento r={r0,r1,r2,r3}. Hay un matiz en Binius que lo hace algo más débil que otros esquemas de compromiso polinómico: el probador no debería saber, o ser capaz de adivinar, s, hasta después de que se comprometiera con la raíz de Merkle (en otras palabras, r debería ser un valor pseudoaleatorio que dependa de la raíz de Merkle). Esto hace que el esquema sea inútil para la "búsqueda en la base de datos" (p. ej. "ok, me diste la raíz de Merkle, ¡ahora demuéstrame P(0,0,1,0)!"). Pero los protocolos reales de prueba de conocimiento cero que usamos generalmente no necesitan "búsqueda en la base de datos"; simplemente necesitan verificar el polinomio en un punto de evaluación aleatorio. Por lo tanto, esta restricción está bien para nuestros propósitos.

Supongamos que elegimos 𝑟={1,2,3,4} (en este punto, el polinomio se evalúa en −137; puedes confirmarlocon este código. Ahora, entramos en el proceso de hacer la prueba. Dividimos 𝑟 en dos partes: la primera parte {1,2} que representa una combinación lineal de columnas dentro de una fila, y la segunda parte {3,4} que representa una combinación lineal de filas. Calculamos un "producto tensorial", tanto para la parte de la columna:

Y para la parte de la fila:

Lo que esto significa es: una lista de todos los posibles productos de un valor de cada conjunto. En el caso de la fila, obtenemos:

[(1-r2)(1-r3), (1-r3), (1-r2)r3, r2*r3]

Usar r={1,2,3,4} (por lo tanto r2=3 y r3=4):

[(1-3)(1-4), 3(1-4),(1-3)4,34] = [6, -9 -8 -12]

Ahora, calculamos una nueva "fila" 𝑡′, tomando esta combinación lineal de las filas existentes. Es decir, tomamos:

Puedes ver lo que está sucediendo aquí como una evaluación parcial. Si multiplicáramos el producto tensorial completo ⨂𝑖=03(1−𝑟𝑖,𝑟𝑖) por el vector completo de todos los valores, obtendrías la evaluación 𝑃(1,2,3,4)=−137. Aquí estamos multiplicando un producto tensorial parcial que solo utiliza la mitad de las coordenadas de evaluación, y estamos reduciendo una cuadrícula de valores 𝑁 a una fila de valores 𝑁. Si le das esta fila a otra persona, pueden usar el producto tensorial de la otra mitad de las coordenadas de evaluación para completar el resto de la computación.

El probador proporciona al verificador esta nueva fila, 𝑡′, así como las pruebas de Merkle de algunas columnas muestreadas al azar. Esto es 𝑂(𝑁) datos. En nuestro ejemplo ilustrativo, haremos que el probador proporcione solo la última columna; en la vida real, el probador necesitaría proporcionar unas docenas de columnas para lograr una seguridad adecuada.

Ahora, aprovechamos la linealidad de los códigos Reed-Solomon. La propiedad clave que utilizamos es: tomar una combinación lineal de una extensión de Reed-Solomon da el mismo resultado que una extensión de Reed-Solomon de una combinación lineal. Este tipo de "independencia del orden" a menudo ocurre cuando tienes dos operaciones que son lineales.

El verificador hace exactamente esto. Calculan la extensión de 𝑡′, y calculan la misma combinación lineal de columnas que el probador calculó antes (pero solo a las columnas proporcionadas por el probador), y verifican que estos dos procedimientos den la misma respuesta.

En este caso, extender 𝑡′, y calcular la misma combinación lineal ([6,−9,−8,12]) de la columna, dan la misma respuesta: −10746. Esto prueba que la raíz de Merkle fue construida "de buena fe" (o al menos "lo suficientemente cerca"), y coincide con 𝑡′: al menos la gran mayoría de las columnas son compatibles entre sí y con 𝑡′.

Pero el verificador aún necesita verificar una cosa más: verificar realmente la evaluación del polinomio en {𝑟0..𝑟3}. Hasta ahora, ninguno de los pasos del verificador realmente dependía del valor que afirmaba el demostrador. Así es como hacemos esa verificación. Tomamos el producto tensorial de lo que etiquetamos como la parte de la "columna" del punto de evaluación:

En nuestro ejemplo, donde r={1,2,3,4} por lo que la mitad de la columna seleccionada es {1,2}), esto es igual a:

Entonces ahora tomamos esta combinación lineal de 𝑡′:

Lo que equivale exactamente a la respuesta que obtienes si evalúas el polinomio directamente.

Lo anterior está bastante cerca de una descripción completa del protocolo Binius “simple”. Esto ya tiene algunas ventajas interesantes: por ejemplo, como los datos se dividen en filas y columnas, solo necesitas un campo de la mitad del tamaño. Pero esto no se acerca a realizar todos los beneficios de hacer cálculos en binario. Para eso, necesitaremos el protocolo Binius completo. Pero primero, obtengamos una comprensión más profunda de los campos binarios.

Campo binario

El campo más pequeño posible es la aritmética módulo 2, tan pequeño que podemos escribir sus tablas de adición y multiplicación:

Podemos hacer campos binarios más grandes tomando extensiones: si comenzamos con 𝐹2 (enteros módulo 2) y luego definimos 𝑥 donde 𝑥2=𝑥+1, obtenemos la siguiente tabla de adición y multiplicación:

Resulta que podemos expandir el campo binario a tamaños arbitrariamente grandes repitiendo esta construcción. A diferencia de los números complejos sobre los reales, donde puedes añadir un nuevo elemento 𝑖, pero no puedes añadir ningún otro más (los cuaterniones sí existen, pero son matemáticamente extraños, por ejemplo, 𝑎𝑏≠𝑏𝑎), con los campos finitos puedes seguir añadiendo nuevas extensiones para siempre. Específicamente, definimos los elementos de la siguiente manera:

Y así sucesivamente. A menudo se denomina la construcción de torres, debido a cómo cada extensión sucesiva puede considerarse como la adición de una nueva capa a una torre. Esta no es la única forma de construir campos binarios de tamaño arbitrario, pero tiene algunas ventajas únicas de las que Binius se aprovecha.

Podemos representar estos números como una lista de bits, por ejemplo, 1100101010001111. El primer bit representa múltiplos de 1, el segundo bit representa múltiplos de 𝑥0, luego los bits subsiguientes representan múltiplos de: 𝑥1, 𝑥1∗𝑥0, 𝑥2, 𝑥2∗𝑥0, y así sucesivamente. Esta codificación es buena porque puedes descomponerla:

Esta es una notación relativamente poco común, pero me gusta representar los elementos del campo binario como enteros, tomando la representación de bits donde los bits más significativos están a la derecha. Es decir, 1=1, 𝑥₀=01=2, 1+𝑥₀=11=3, 1+𝑥₀+𝑥₂=11001000=19, y así sucesivamente. 1100101010001111 es, en esta representación, 61779.

La adición en un campo binario es simplemente XOR (como también lo hace la resta, por cierto); tenga en cuenta que esto significa x+x=0 para cualquier x. Para multiplicar dos elementos x*y, hay un algoritmo recursivo muy simple: dividir cada número por la mitad:

Luego, divida la multiplicación:

La última pieza es la única un poco complicada, porque tienes que aplicar la regla de reducción y reemplazar 𝑅𝑥∗𝑅𝑦∗𝑥𝑘2 con 𝑅𝑥∗𝑅𝑦∗(𝑥𝑘−1∗𝑥𝑘+1). Hay formas más eficientes de hacer multiplicaciones, análogas del algoritmo de Karatsuba y transformadas rápidas de Fourier, pero dejaré que el lector interesado lo descubra como ejercicio.

La división en campos binarios se realiza combinando la multiplicación y la inversión. La forma 'simple pero lenta' de hacer la inversión es una aplicación del pequeño teorema de Fermat generalizado. También existe un algoritmo de inversión más complicado pero más eficiente, que puedes encontrar aquíPuedes usar el código aquípara jugar con la adición, multiplicación y división de campos binarios tú mismo.

Izquierda: tabla de adición para elementos de campo binario de cuatro bits (es decir, elementos formados solo por combinaciones de 1， 𝑥₀，𝑥₁ y 𝑥₀𝑥₁).

Correcto: tabla de multiplicación para elementos de campo binario de cuatro bits.

Lo hermoso de este tipo de campo binario es que combina algunas de las mejores partes de los enteros 'regulares' y la aritmética modular. Al igual que los enteros regulares, los elementos del campo binario no tienen límites: puedes seguir extendiéndolos tanto como desees. Pero al igual que en la aritmética modular, si realizas operaciones sobre valores dentro de un cierto límite de tamaño, todas tus respuestas también se mantienen dentro del mismo límite. Por ejemplo, si tomas potencias sucesivas de 42, obtienes:

Después de 255 pasos, estás de vuelta a 42²⁵⁵ = 1. Al igual que los enteros positivos y la aritmética modular, siguen las leyes matemáticas usuales: ab=ba, a(b+c)=a b+a*c, hay incluso algunas leyes nuevas extrañas.

Finalmente, los campos binarios facilitan el manejo de bits: si haces matemáticas con números que caben 2^k bits, entonces toda tu salida también encajará 2 k bits. Esto evita el embarazo. En el EIP-4844 de Ethereum, cada "bloque" de un blob debe ser un módulo digital 52435875175126190479447740508185965837690552500527637822603658699938581184513, por lo que codificar los datos binarios requiere desechar algo de espacio y hacer una verificación adicional para asegurarse de que cada elemento almacene un valor menor que 2²⁴⁸. Esto también significa que las operaciones de campo binario son súper rápidas en computadoras, tanto en CPUs como en diseños teóricamente óptimos de FPGA y ASIC.

Lo que todo esto significa es que podemos hacer algo como la codificación Reed-Solomon que hicimos anteriormente, de una manera que evite por completo la "explosión" de números enteros, como vimos en nuestro ejemplo, y de una manera muy "explosiva". De manera "nativa", el tipo de computación en la que las computadoras son buenas. El atributo "split" de los campos binarios: cómo lo hacemos 1100101010001111=11001010+10001111*x₃y luego dividirlo según nuestras necesidades también es crucial para lograr mucha flexibilidad.

Binius completo

Ver aquípara una implementación de Python de este protocolo.

Ahora podemos llegar a “full Binius”, que ajusta “simple Binius” para (i) trabajar en campos binarios, y (ii) permitirnos comprometernos con bits individuales. Este protocolo es difícil de entender, porque va y viene entre diferentes formas de ver una matriz de bits; ciertamente me llevó más tiempo entenderlo de lo que normalmente me lleva entender un protocolo criptográfico. Pero una vez que entiendes los campos binarios, la buena noticia es que no hay ninguna “matemática más difícil” en la que Binius dependa. No se trata de apareamientos de curvas elípticas, donde hay madrigueras de álgebra y geometría más profundas a las que adentrarse; aquí, los campos binarios son todo lo que necesitas.

Veamos nuevamente el diagrama completo:

A estas alturas, deberías estar familiarizado con la mayoría de los componentes. La idea de "aplanar" un hipercubo en una cuadrícula, la idea de calcular una combinación de filas y una combinación de columnas como productos tensoriales del punto de evaluación, y la idea de verificar la equivalencia entre "extensión de Reed-Solomon y luego calcular la combinación de filas" y "calcular la combinación de filas y luego extensión de Reed-Solomon", estaban todos en el simple Binius.

¿Qué hay de nuevo en "full Binius"? Básicamente tres cosas:

• Los valores individuales en el hipercubo, y en el cuadrado, tienen que ser bits (0 o 1)
• El proceso de extensión extiende bits en más bits, agrupando bits en columnas y pretendiendo temporalmente que son elementos de campo más grandes
• Después del paso de combinación de filas, hay un paso de "descomposición en bits" por elementos, que convierte la extensión de nuevo en bits

Pasaremos por ambos a su vez. Primero, el nuevo procedimiento de extensión. Un código de Reed-Solomon tiene la limitación fundamental de que si estás extendiendo 𝑛 valores a 𝑘∗𝑛 valores, necesitas estar trabajando en un campo que tenga 𝑘∗𝑛 valores diferentes que puedas usar como coordenadas. Con 𝐹₂(también conocido como bits), no puedes hacer eso. Y así que lo que hacemos es "empacar" 𝐹 adyacentes₂elementos juntos en valores más grandes. En el ejemplo aquí, estamos empaquetando dos bits a la vez en elementos en {0,1,2,3}, porque nuestra extensión solo tiene cuatro puntos de evaluación y eso es suficiente para nosotros. En una prueba "real", probablemente agruparíamos 16 bits a la vez. Luego hacemos el código de Reed-Solomon sobre estos valores empaquetados y los desempaquetamos nuevamente en bits.

Ahora, la combinación de filas. Para que las comprobaciones de "evaluar en un punto aleatorio" sean criptográficamente seguras, necesitamos que el punto se muestree de un espacio bastante grande, mucho más grande que el hipercubo en sí mismo. Por lo tanto, mientras que los puntos dentro del hipercubo son bits, las evaluaciones fuera del hipercubo serán mucho más grandes. En nuestro ejemplo anterior, la "combinación de filas" termina siendo [11,4,6,1].

Esto presenta un problema: sabemos cómo combinar pares de bits en un valor más grande, y luego hacer una extensión de Reed-Solomon sobre eso, pero ¿cómo hacer lo mismo con pares de valores mucho más grandes?

El truco en Binius es hacerlo por bits: observamos los bits individuales de cada valor (por ejemplo, para lo que hemos etiquetado como “11”, eso es [1,1,0,1]), y luego extendemos por filas. Es decir, realizamos el procedimiento de extensión en la fila 1 de cada elemento, luego en la fila 𝑥0, luego en el “𝑥₁“fila, luego en la 𝑥₀∗𝑥₁fila, y así sucesivamente (bueno, en nuestro ejemplo de juguete nos detenemos ahí, pero en una implementación real iríamos hasta 128 filas (siendo la última 𝑥₆∗ …∗ 𝑥₀.))

Recapitulando:

• Tomamos los bits en la hipercubo, y los convertimos en una cuadrícula
• Luego, tratamos grupos adyacentes de bits en cada fila como elementos de campo más grandes, y hacemos aritmética en ellos para extender las filas de Reed-Solomon
• Entonces, tomamos una combinación de fila de cada columna de bits y obtenemos una columna de bits (mucho más pequeña para cuadrados mayores de 4x4) para cada fila como salida
• Entonces, miramos la salida como una matriz y tratamos los bits de eso como filas nuevamente

¿Por qué funciona esto? En matemáticas 'normales', la capacidad de (a menudo) realizar operaciones lineales en cualquier orden y obtener el mismo resultado deja de funcionar si empiezas a dividir un número en dígitos. Por ejemplo, si comienzo con el número 345, y lo multiplico por 8 y luego por 3, obtengo 8280, y si hago esas dos operaciones al revés, también obtengo 8280. Pero si inserto una operación de 'dividir por dígito' entre los dos pasos, se descompone: si haces 8x luego 3x, obtienes:

Pero si haces 3x, y luego 8x, obtienes:

Pero en un campo binario construido con una estructura de torre, este enfoque sí funciona. La razón radica en su separabilidad: si multiplicas un valor grande por un valor pequeño, lo que sucede en cada segmento se queda en cada segmento. Si multiplicamos 1100101010001111 por 11, esto es lo mismo que la primera factorización de 1100101010001111, que es

Y luego multiplicando cada componente por separado por 11.

Poniéndolo todo junto

Generalmente, los sistemas de prueba de conocimiento cero funcionan haciendo afirmaciones sobre polinomios que representan simultáneamente afirmaciones sobre las evaluaciones subyacentes: tal como vimos en el ejemplo de Fibonacci, 𝐹(𝑋+2)−𝐹(𝑋+1)−𝐹(𝑋)=𝑍(𝑋)∗𝐻(𝑋) verifica simultáneamente todos los pasos del cálculo de Fibonacci. Verificamos afirmaciones sobre polinomios demostrando evaluaciones en un punto aleatorio. Esta verificación en un punto aleatorio sirve para comprobar todo el polinomio: si la ecuación polinómica no coincide, la probabilidad de que coincida en una coordenada aleatoria específica es muy pequeña.

En la práctica, una fuente importante de ineficiencia proviene del hecho de que en los programas reales, la mayoría de los números con los que estamos trabajando son pequeños: índices en bucles for, valores Verdadero/Falso, contadores y cosas similares. Pero cuando "extendemos" los datos utilizando la codificación Reed-Solomon para darles la redundancia necesaria para hacer que las comprobaciones basadas en pruebas de Merkle sean seguras, la mayoría de los valores "adicionales" terminan ocupando el tamaño completo de un campo, incluso si los valores originales son pequeños.

Para solucionar esto, queremos hacer el campo lo más pequeño posible. Plonky2 nos llevó de números de 256 bits a números de 64 bits, y luego Plonky3 avanzó aún más a 31 bits. Pero incluso esto no es óptimo. Con campos binarios, podemos trabajar con bits individuales. Esto hace que la codificación sea 'densa': si tus datos subyacentes reales tienen n bits, entonces tu codificación tendrá n bits, y la extensión tendrá 8 * n bits, sin sobrecarga adicional.

Ahora, veamos el diagrama por tercera vez:

En Binius, nos comprometemos con un polinomio multilíneo: un hipercubo 𝑃(x₀,x₁,…x_k), donde las evaluaciones individuales P(0,0... 0), P(0,0... 1) hasta P(1,1,... 1) Guardamos los datos que nos interesan. Para probar una evaluación en un punto, "reinterpretamos" los mismos datos como un cuadrado. A continuación, extendemos cada fila, utilizando la codificación Reed-Solomon sobre grupos de bits, para dar a los datos la redundancia necesaria para que las consultas aleatorias de la rama de Merkle sean seguras. A continuación, calculamos una combinación lineal aleatoria de filas, con coeficientes diseñados para que la nueva fila combinada contenga realmente la evaluación que nos interesa. Tanto esta fila recién creada (que se reinterpreta como 128 filas de bits) como algunas columnas seleccionadas aleatoriamente con ramas de Merkle, se pasan al verificador.

A continuación, el verificador realiza una "combinación de filas de la extensión" (o más bien, unas pocas columnas de la extensión) y una "extensión de la combinación de filas", y verifica que las dos coincidan. A continuación, calculan una combinación de columnas y comprueban que devuelve el valor que reclama el demostrador. Y está nuestro sistema de prueba (o más bien, el esquema de compromiso polinómico, que es el componente clave de un sistema de prueba).

¿Qué no cubrimos?

• Algoritmos eficientes para extender las filas, que son necesarios para realmente hacer la eficiencia computacional del verificador. Utilizamos transformadas rápidas de Fourier sobre campos binarios, descritas aquí(aunque la implementación exacta será diferente, porque esta publicación utiliza una construcción menos eficiente que no se basa en la extensión recursiva).
• Arithmetization. Los polinomios univariados son convenientes porque puedes hacer cosas como F(X+2)-F(X+1)-F(X) = Z(X)*H(X) para relacionar pasos adyacentes en el cálculo. En un hipercubo, “el siguiente paso” es mucho menos interpretable que “X+1”. Podrías hacer X+k, potencias de k, pero este comportamiento de salto sacrificaría muchas de las ventajas clave de Binius. La solución se presenta en la Papel Binius(Ver Sección 4.3), pero esto es un profundo agujero de conejo en sí mismo.
• Cómo realizar de manera segura comprobaciones de valor específico. El ejemplo de Fibonacci requiere verificar las condiciones límite clave: F(0)=F(1)=1 y el valor de F(100). Pero con Binius “crudo”, es inseguro verificar en puntos de evaluación preconocidos. Existen formas bastante simples de convertir una comprobación de evaluación conocida en una comprobación de evaluación desconocida, utilizando lo que se llaman protocolos de comprobación de suma; pero no entraremos en esos detalles aquí.
• Los protocolos de búsqueda, otra tecnología que ha estado ganando uso recientemente como una forma de crear sistemas de prueba ultraeficientes. Binius se puede combinar con los protocolos de búsqueda para muchas aplicaciones.
• Yendo más allá del tiempo de verificación de la raíz cuadrada. La raíz cuadrada es costosa: una prueba de bits de Binius es de aproximadamente 11 MB de largo. Puede remediar esto utilizando algún otro sistema de prueba para hacer una 'prueba de una prueba de Binius', obteniendo así la eficiencia de Binius en probar la declaración principal y un tamaño de prueba pequeño. Otra opción es el protocolo FRI-Binius mucho más complicado, que crea una prueba de tamaño polilogarítmico (como FRI regular).
• Cómo Binius afecta lo que se considera como 'amigable con SNARK'. El resumen básico es que, si utilizas Binius, ya no necesitas preocuparte mucho por hacer que la computación sea 'amigable con la aritmética': los hashes 'regulares' ya no son más eficientes que los hashes aritméticos tradicionales, la multiplicación módulo o módulo ya no es una gran molestia en comparación con la multiplicación módulo , y así sucesivamente. Pero este es un tema complicado; muchas cosas cambian cuando todo se hace en binario.

Espero muchas más mejoras en las técnicas de demostración basadas en campos binarios en los próximos meses.

Descargo de responsabilidad：

1. Este artículo es reimpreso de [GatePanews]. Reenviar el Título Original 'Vitalik详解Binius：基于二进制字段的高效证明系统'. Todos los derechos de autor pertenecen al autor original [Vitalik Buterin*]. Si hay objeciones a esta reimpresión, por favor contacte al Gate Learnequipo, y lo manejarán rápidamente.
2. Descargo de responsabilidad: Las opiniones expresadas en este artículo son únicamente las del autor y no constituyen asesoramiento de inversión.
3. Las traducciones del artículo a otros idiomas son realizadas por el equipo de Gate Learn. A menos que se mencione, está prohibido copiar, distribuir o plagiar los artículos traducidos.