Propuestas de BitVM: una descripción general del discutible paradigma informático de Bitcoin
Durante muchos años, pensamos que la verificación de cálculos arbitrarios en Bitcoin era imposible debido a las limitadas capacidades de secuencias de comandos de la cadena de bloques.
Esto cambió en octubre de 2023 con la publicación del artículo de BitVM, que describía una forma de lograr una validación optimista de cálculos complejos en Bitcoin. Esto es importante porque abre la puerta a infinitas posibilidades, incluida la implementación de puentes más descentralizados entre Bitcoin y otras redes. BitVM recibió la atención que merecía y desbloqueó varias ideas y propuestas nuevas simplemente mostrando que lo imposible era realmente posible sin cambios en el consenso de Bitcoin.
En este artículo, proporcionamos una descripción general de algunas de las propuestas existentes (en el momento de escribir este artículo) para ayudar a las personas a realizar un seguimiento de esta nueva área en rápida evolución que llamamos el "paradigma de computación discutible".
El discutible paradigma de la computación
TrueBit fue pionero en la idea de verificar cálculos arbitrarios en una cadena de bloques. La idea consiste en
- ejecutar un programa fuera de la cadena,
- presentar la prueba de la ejecución en cadena, y
- ejecutar una validación en cadena si alguien cuestiona la prueba.
Esto reduce la cantidad de cálculos ejecutados en cadena a una fracción del total, lo que permite la verificación de cálculos arbitrariamente complejos.
El paradigma establece una forma de representar el estado de una computadora y define una tarea computacional como una secuencia de pasos que modifican este estado. La huella de un cálculo es, pues, una secuencia de estados .
Para validar una tarea computacional, un probador ejecuta la tarea fuera de la cadena y envía el estado final de la computadora a la cadena de bloques. Si nadie cuestiona el resultado, la red acepta el cálculo. Un verificador que no esté de acuerdo con el resultado presentado puede participar en un juego de verificación con el probador para resolver la disputa. Después del juego, el probador es penalizado si el estado final presentado fue erróneo.
El juego de verificación consiste en un protocolo de desafío-respuesta donde el probador revela información que el verificador solicita. El verificador gana si el probador deja de responder en algún momento y, por lo tanto, el probador se ve obligado a revelar la información solicitada. Mediante este sistema, el verificador solicita el estado de la computadora en ciertos pasos. Dado que el verificador no está de acuerdo con el estado final presentado por el probador, debe haber una transición de estado no válida en algún punto del seguimiento computacional. El verificador utiliza un proceso de búsqueda iterativo para identificar esta transición de estado no válida y obliga al probador a revelar sus detalles. Luego, la transición de estado se ejecuta en la cadena y se compara con los datos enviados por el probador. El probador es penalizado si la transición de estado no es válida utilizando los datos proporcionados.
BitVM
El artículo original de BitVM describe una forma de crear un juego de verificación en Bitcoin donde los cálculos se expresan como un circuito de puertas NAND . En su lugar , un diseño más avanzado utiliza instrucciones similares a las de un ensamblaje. Este diseño representa el estado de la computadora en un determinado paso como la raíz de un árbol Merkle donde cada hoja es una dirección y un valor de memoria. Cada paso computacional lee dos entradas de la memoria, ejecuta un código de operación, escribe una salida en la memoria y modifica un contador de programa. La traza del cálculo es la secuencia de raíces de Merkle que representan todos los valores en la memoria en cada paso.
BitVM organiza este rastro en otro árbol Merkle donde cada hoja es la raíz Merkle de la memoria en cada paso computacional.
El juego de verificación en BitVM comienza con una búsqueda binaria en el árbol de seguimiento de Merkle donde el verificador identifica una transición de estado no válida. El probador envía los detalles del paso computacional en conflicto, incluidas sus entradas, código de operación y salida. Luego, el verificador puede cuestionar diferentes partes de la transición de estado, incluido el tipo de instrucción, el contador del programa o los valores de entrada o salida. Realizar esta búsqueda binaria significa que el juego de verificación requiere log 2 (n) rondas para n pasos computacionales.
Para garantizar la autenticidad de todos los datos durante el juego de verificación, el probador debe firmar toda la información enviada en la cadena utilizando firmas Lamport únicas. El verificador gana instantáneamente el juego de verificación al mostrar equivocación, es decir, dos mensajes distintos firmados con la misma clave pública única que pertenece al probador.
BitVM2
En BitVM, el juego de verificación consta de un conjunto de transacciones prefirmadas entre el probador y el verificador. Esto puede funcionar con múltiples verificadores bajo una suposición honesta de 1 de n, pero el conjunto de verificadores debe definirse durante la configuración. BitVM2 es un reemplazo de BitVM que permite una configuración multipartita donde cualquiera puede asumir el papel de verificador.
BitVM2 representa una tarea computacional como una función f(x) = y donde x es la entrada e y es el resultado. La tarea se puede dividir en subtareas f1,f2,…, fn donde f1(x) = z1, f2(z1) = z2,…, fn = y. Si f(x) es un verificador sucinto de conocimiento cero, BitVM2 puede validar cualquier cálculo que pueda expresarse como una prueba de conocimiento cero.
El juego de verificación en BitVM2 consiste en una única transacción donde el probador envía x, y y todos los resultados intermedios z. Esta transacción permite a cualquiera demostrar que el resultado de una de las subtareas no se corresponde con el resultado intermedio presentado por el probador. De esta manera, cualquiera puede convertirse en verificador forzando la ejecución en cadena de la subtarea cuestionada.
En BitVM2, existe un equilibrio entre la cantidad de datos enviados y la cantidad de cálculo ejecutado en la cadena. Cuanto mayor es el número de subtareas, mayor es la cantidad de resultados intermedios que deben enviarse, pero menor es la cantidad de cálculo que se ejecuta en la cadena. BitVM2 reduce el juego de verificación a una ronda, pero aumenta significativamente la cantidad de datos enviados en una sola transacción, ya que la cantidad de resultados intermedios requeridos podría ser de hasta 1000.
BitVMX
BitVMX es similar a BitVM en que representa cálculos utilizando instrucciones similares a las de un ensamblador. Sin embargo, BitVMX no utiliza árboles Merkle para organizar la secuencia de estados. En cambio, BitVMX crea una cadena de hashes para representar el rastro de la computadora. Esto reduce el número de rondas necesarias para identificar la transición de estado no válida al permitir un proceso de búsqueda m-ario que toma log m (n) rondas para n pasos, donde (m-1) es el número de estados que el probador envía en cada redondo. Esto permite una mayor flexibilidad en el juego de verificación y crea un equilibrio entre la cantidad de datos enviados y la cantidad de rondas requeridas. Además de esto, BitVMX requiere menos almacenamiento que BitVM porque no necesita organizar todas las posiciones de memoria en un árbol Merkle. El juego de verificación en BitVMX no requiere un mecanismo para castigar la equivocación como BitVM, pero requiere dos búsquedas m-arias en el peor de los casos, lo que se traduce en 2*log m (n) rondas donde m podría ir de 2 a 16.
Mecanismo de búsqueda n-ario con 64 hashes (m = 64, n = 4, l = 3).
BitSNARK
BitSNARK representa tareas computacionales utilizando solo tres tipos de instrucciones que operan con registros de 256 bits. Estos tres tipos de instrucciones son suficientes para construir un verificador SNARK y, por lo tanto, BitSNARK se limita a la verificación de pruebas SNARK. BitSNARK no utiliza memoria direccionable y define el estado de la computadora en un paso particular como los valores en los registros de 256 bits.
El juego de verificación en BitSNARK consiste en una búsqueda binaria sobre el rastro de ejecución donde, en cada ronda, el probador envía el estado intermedio de los registros en un paso particular. Después de log 2 (n) rondas, el verificador puede identificar una operación no válida que luego se ejecuta en cadena para su validación. La cantidad de datos que el probador envía en cadena depende de la cantidad de registros utilizados para representar el estado, que se espera que sea menos de 30. Aparte de esto, BitSNARK implementa un mecanismo para castigar los errores como BitVM.
SNARKnado
SNARKnado es otra propuesta que se centra en construir un verificador SNARK en lugar de verificar cálculos arbitrarios. SNARKnado representa los cálculos como relaciones polinómicas y ejecuta el juego de verificación directamente sobre estos polinomios. Dado un polinomio, el verificador solicita al probador que presente su evaluación en un punto aleatorio. Si la evaluación es incorrecta, la búsqueda continúa dividiendo el polinomio en subpolinomios pares e impares. Después de varias rondas, el verificador puede identificar el error en el cálculo. El número de rondas requeridas es logarítmico en el grado del polinomio y se estima en alrededor de 4. De esta manera, SNARKnado limita la cantidad de rondas requeridas en el juego de verificación manteniendo baja la cantidad de datos enviados por ronda.
La siguiente tabla muestra un resumen de las diferencias entre los protocolos existentes actualmente:
Conclusión
El discutible paradigma de computación de Bitcoin está evolucionando a un ritmo rápido con la aparición de varias propuestas desde la publicación del artículo original de BitVM. La mayoría de los esfuerzos actuales parecen centrarse en la verificación SNARK y, con la discontinuación de BitVM en favor de BitVM2, BitVMX sigue siendo la única solución diseñada como computadora de uso general.
BitVM2 es el único protocolo que requiere solo una ronda y que permite que cualquiera pueda convertirse en verificador, mientras que el resto de propuestas definen el conjunto de verificadores durante la configuración. BitVM2 logra esto a costa de publicar más datos en una sola transacción. Los otros dos protocolos basados en SNARK ofrecen diferentes compensaciones, y presumiblemente SNARKnado logra un mejor equilibrio entre el número de rondas y la cantidad de datos enviados en la cadena. Sin embargo, todas las soluciones, excepto BitVM, aún están en desarrollo y su rendimiento real puede depender de los detalles de implementación, así como de casos de uso específicos. Además de esto, es probable que veamos mejoras en el protocolo y nuevas propuestas que surjan en los próximos meses.
