En los últimos seis meses se han visto varias propuestas de mejora de Bitcoin Script: gatoaritmética de 64 bits, así como algunas ideas más antiguas (CTV) e ideas de futuro lejano (Chialisp y Sencillaz). Esta actividad ha eclipsado en gran medida algunos cambios revolucionarios en nuestra comprensión del Bitcoin Script existente, cambios que forman la base de BitVM pero que también pueden formar la base de otras mejoras igualmente interesantes.
Este artículo intenta resumir y organizar la investigación sobre Script realizada por otras personas. No reclamo la originalidad o autoridad de nada de lo descrito aquí.
Secuencia de comandos Bitcoin
Como muchos lectores saben, Bitcoin Script es un lenguaje de programación simple integrado en la cadena de bloques de Bitcoin, que se utiliza para controlar bajo qué condiciones pueden mover las monedas. Con diferencia, el uso más común de Script es simplemente comprobar una firma con una única clave de verificación de firma. Aunque las direcciones de Bitcoin han cambiado a lo largo de los años, cada forma de dirección ha admitido este uso de secuencias de comandos de primera clase: las claves de firma se pueden codificar directamente en direcciones de Bitcoin, y las billeteras saben cómo expandir estas claves en programas completos que verifican las firmas. en esas llaves.
El script puede hacer muchas más cosas: puede verificar preimágenes hash, verificar bloqueos de tiempo relativos y absolutos, y puede realizar un razonamiento simple para estas combinar comprobaciones de varias maneras. Esta es la premisa detrás de Miniscript: podemos generalizar la noción de expandir una clave en un Script a la noción de expandir un conjunto arbitrariamente grande de condiciones de firma en un Script.
Técnicamente, el script puede hacer incluso más que esto: puede sumar y restablecer números de 32 bits, puede hacer hash de datos y verificar la igualdad de los valores hash, y puede reorganizar y manipular una «pila» de valores de varias maneras interesantes. Sin embargo, Script tiene muchas limitaciones: carece de códigos de operación para realizar aritmética simple como la multiplicación, es (casi) incapaz de razonar sobre objetos de más de 32 bits y (casi) no tiene la capacidad de realizar una introspección de los datos. de las transacciones. La última limitación es la razón por la cual el soporte de covenant parece requerir un softfork, y las limitaciones anteriores son la razón por la cual Script, hasta hace poco, nunca se usamos para calcular funciones «interesantes».
Por ejemplo, para multiplicar dos números de 16 bits en Script, usando solo los códigos de operación de suma y resto que proporciona Script, debe dividirlos en bits (al requerir que los bits se proporcionen como datos testigo, luego duplicarlos y sumarlos para reconstruir el número original) y luego implementar la multiplicación en términos de sumas de estos bits. El código resultante implicaría varias docenas de códigos de operación para una sola multiplicación.
Antes de Taproot, Script tenía un límite artificial de 201 códigos de operación por programa, y como las multiplicaciones individuales consumían más de una cuarta parte de este presupuesto, era imposible hacer mucho. Después de Taproot, se eliminó el límite de 201 códigos de operación, pero cada código de operación aún ocupa un byte testigo, lo que significa que los programas de varios kilobytes serán prohibitivamente costosos para que las billeteras comunes los coloquen en la cadena de bloques.
Y sin una introspección de transacciones, ni siquiera está claro para qué serán buenos los grandes cálculos.
Después de todo, si se pueden hacer cálculos arbitrarios sobre valores arbitrarios, pero esos valores no están vinculados a datos de transacciones en la cadena de bloques, ¿cómo pueden esos cálculos agregar semántica útil a Bitcoin?
Firmas Lamport
Las firmas Lamport fueron inventadas en 1979 por Leslie Lamport, aunque son inseguras sin las funciones hash criptográficas modernas, que no existieron hasta la década de 1990, y son uno de los pocos objetos criptográficos de esa época que perduran hasta el día de hoy. Su popularidad duradera proviene de su simplicidad y del hecho de que su seguridad contra las computadoras cuánticas depende sólo de funciones hash de apariencia suficientemente aleatoria, a diferencia de las propuestas más modernas y eficientes de esquemas de firma cuánticos seguros.
Sin embargo, las firmas Lamport tienen dos grandes inconvenientes: (1) son terriblemente ineficientes, ya que requieren varios kilobytes de datos tanto para las claves como para las firmas, y (2) son de un solo uso. Esto significa que si un usuario firma más de un mensaje, es posible que un tercero falsifique más mensajes, haciendo que todas las firmas pierdan su valor. Esto se puede mitigar, por ejemplo, haciendo que su “clave pública” sea un árbol Merkle de millones de claves de un solo uso, pero esto va más allá de los límites de lo práctico.
Estas limitaciones han hecho que las firmas Lamport sean populares como «esquema de firma de respaldo» para Bitcoin en caso de un avance en la computación cuántica, pero han impedido su uso como firmas primarias en cualquier sistema ampliamente implementado.
La forma en que funcionan es simple: supongamos que el mensaje a firmar tiene 256 bits de ancho. Esto se puede garantizar ejecutando primero un mensaje de longitud arbitraria a través de la función hash SHA256. La clave pública del usuario consta de 256 pares de hashes (512 en total). Para firmar un mensaje, revela una preimagen para un hash en cada par, eligiendo la preimagen a revelar en función de una parte del mensaje.
Un verificador de firmas vuelve a codificar el mensaje y las imágenes previas para garantizar que todos sean coherentes.
En 2021, Jeremy Rubin publicó una entrada en el blog afirmando que Bitcoin Script puede verificar directamente las firmas Lamport en valores de 33 bits. Su mecanismo era muy inteligente. Bitcoin Script no tiene un código de operación para leer bits individuales de un número, ni puede realizar las operaciones bit necesarias para construir un número a partir de bits. Pero Script tiene un código de operación para sumar dos números, y al agregar números diferentes donde cada uno tiene un solo bit establecido, es posible construir o deconstruir bit a bit un número.
Utilizando esta información, Rubin verifica una firma Lamport, codificada como una serie de preimágenes hash, de la siguiente manera:
- Para cada preimagen, calcula su hash y compárelo con un par de valores objetivo (que comprenden la clave pública) incrustados en el script.
- Si el hash coincide con el primer miembro del par, se trata de un bit 0; El guión no hace nada en este caso.
- Si coincide con el segundo miembro, es de 1 bit. En este caso, agregue una potencia particular de 2 a un acumulador.
- (Si no coincide con ninguno de los miembros, la firma no es válida y el script debería cancelarse).
El valor final del acumulador será entonces igual al número con signo, construido sumando potencias de dos correspondientes a cada bit en su expansión binaria.
Esto ya es interesante: significa que para ciertos tipos de aplicaciones de «firma de Oracle», puede verificar las firmas directamente en Bitcoin Script, asumiendo que tiene un Oracle que está dispuesto a producir firmas Lamport únicas en eventos específicos y que conoce una Lamportar la clave pública con antelación para cada evento. Por ejemplo, el resultado de un partido deportivo específico se puede codificar como un solo bit. La partición particular se puede codificar utilizando unos pocos bits. Una marca de tiempo particular puede (probablemente) codificarse en 33 bits. Etcétera. Y, por supuesto, al verificar Múltiples firmas Lamport, puede obtener firmas de manera efectiva en tantos bits como desee.
Sin la capacidad de firmar mensajes grandes, no se puede obtener una firma en los datos de la transacción y, por lo tanto, no se pueden obtener acuerdos. (¿O podemos?)
BitVM y Equivocación
Esta publicación del blog de Jeremy Rubin se demostró en gran medida una curiosidad en ese momento y se perdió entre discusiones más amplias sobre su propuesta y acuerdos OP_CTV. En diciembre de 2023, fue citado indirectamente en el OP_CAT BIP por Ethan Heilman y Armin Sabourilo que le dio una nueva audiencia entre las personas que pensaban de manera diferente sobre Bitcoin Script.
La gente pensaba diferente porque en octubre de 2023, apenas dos meses antes, Robin Linus había anunciado en la lista de correo su proyecto BitVM—un proyecto ambicioso para realizar cálculos arbitrarios en Bitcoin Script dividiendo programas en múltiples transacciones. Cada una de las transacciones individuales realiza una única operación simple, con los resultados de una operación conectada a las entradas de otra a través de una construcción reveladora de preimagen hash que se parece sospechosamente a una firma Lamport.
El truco aquí es que si un usuario Lamport firma varios mensajes con la misma clave, el resultado serán dos hashes en el mismo par de hash cuyas preimágenes son conocidas. Esto es fácil de verificar en Script, que se puede usar para construir una «transacción de reducción» que tomará monedas de un usuario si hace esto. Una transacción de este tipo sería válida exactamente en el caso de que un usuario firme públicamente dos mensajes con la misma clave. Las transacciones de reducción se utilizan dentro de protocolos de transacciones múltiples para castigar a los usuarios que se portan mal, generalmente perdiendo un bono que deben publicar con anticipación.
Por lo tanto, estas firmas Lamport, en lugar de simplemente perder seguridad cuando se usan más de una vez, se pueden configurar para castigar activamente a un usuario que firma varias veces. Esto tiene aplicaciones obvias para una firma de Oracle donde se supone que un firmante debe dar fe de exactamente un resultado de un evento de la vida real; Queremos disuadir a dicho firmante de afirmar que, por ejemplo, ambos equipos ganaron un partido deportivo en particular. Pero ésta es una idea aún más poderosa de lo que parece.
En la literatura criptográfica, cuando una parte revela dos valores para algo que se supone es único, esto se llama equívoco. Podemos Piense en una transacción de recorte como una medida anti-equívoco.porque castiga a cualquier firmante que produzca firmas en la misma clave con el mismo mensaje.
Entonces nuestra firma Lamport con construcción anti-equivocación tiene el efecto de asignar claves públicas a valores específicos e inmutables. En otras palabras, tenemos un almacén global clave-valor accesible desde Script, con la curiosa propiedad de que cada entrada en el almacén global puede ser configurada por una persona específica (la persona que conoce las preimágenes de esa clave), pero solo puede ser establecido una vez para siempre. También se puede acceder a este almacén de valores clave desde cualquier transacción de Bitcoin (o una transacción en cualquier cadena de bloques, en realidad) independientemente de su conexión con otras transacciones.
Este almacén clave-valor tiene del orden de 2^256 entradas, la mayoría de las cuales no son accesibles ya que nadie conoce las imágenes previas de sus claves, por lo que si bien es un «almacén global clave-valor» compartido por todos los programas posibles que utilizan este Lamport construcción de firma, no puede llenarse y no hay riesgo de que los datos de un programa puedan bloquear accidentalmente los datos de otro, o que un valor que debería ser establecido por un usuario pueda ser establecido por otro. El almacén clave-valor tampoco se almacena en ningún lugar en su totalidad.
BitVM y sus variantes utilizan este hecho para vincular la salida de una operación con la entrada de la siguiente: un programa determinado se puede dividir en una larga serie de operaciones básicas, por ejemplo, códigos de operación en el conjunto de instrucciones RISC-V, y cada una de estas operaciones Las básicas se pueden implementar mediante un programa de script autónomo que busca las entradas y salidas de la operación en el almacén clave-valor, verifica que estén relacionadas correctamente y, de alguna manera, castiga al usuario si no.
El sistema BitVM completo es mucho más complicado q ue esto: para cada programa, crea un espacio de memoria direccionable del almacén clave-valor; cada operación necesita buscar sus entradas y salidas en este espacio de memoria; cada operación necesita rastrear un contador de programa y otros estados más allá de sus entradas y salidas; y todo está vinculado con protocolos interactivos y árboles de transacciones no confirmadas para garantizar que las sanciones reductoras se apliquen correctamente y que incluso un solo paso incorrecto en un programa de millas de millones de pasos pueda ser enfocado y castigado. Pero este artículo no trata sobre BitVM y no lo exploraremos.
Interludio: guión pequeño y guión grande
Nos tomamos un momento para recordarle al lector que Script solo puede realizar cálculos no triviales en valores de 32 bits de ancho o menos. Dichos valores son «scriptnums» y Script tiene muchos códigos de operación para manipularlos interpretándolos como enteros con signo o valores booleanos, a veces como ambos.
Al utilizar BitVM o un mecanismo similar para dividir programas de script en múltiples transacciones, puede realizar cálculos arbitrarios en Small Script, desde verificación ZKP hasta verificación de prueba de trabajo y factorización numérica.
Los valores mayores a 32 bits sólo pueden manipularse mediante un pequeño conjunto de códigos de operación de propósito específico: pueden ser codificados, interpretados como claves públicas o firmas para verificar la firma de una transacción, su tamaño en bytes puede calcularse y pueden ser transferidos. aro y la pila como manchas opacas. El único cálculo «real» de propósito general que se puede hacer con ellos es una verificación de igualdad, que por sí sola proporciona muy poco valor.
Describimos el mundo de los valores de 32 bits como «Small Script», que es computacionalmente expresivo pero no puede acceder a los datos de las transacciones de ninguna manera. Al mundo de valores más grandes lo llamamos «Big Script» y podemos acceder a los datos de las transacciones a través del código de operación CHECKSIG. También es posible verificar hash preimágenes en Big Script, y esto es esencial para implementar firmas Lamport, pero eso es prácticamente lo único que puedes hacer en Big Script.
Es imposible unir de manera útil los dos mundos: puede aplicar hash a un valor Pequeño para obtener un valor Grande, pero luego no puede aprender nada sobre el valor Grande que no sepa ya. Y puedes usar el código de operación TAMAÑO para conocer el tamaño de un valor Grande, pero si este valor representa un hash, una clave pública o una firma, entonces su tamaño es fijo para que no nada aprenda nuevo. (Aunque antes de Taproot, las firmas tenían un tamaño variable, y es Es posible que pueda extraer información de la transacción. de una transacción de paso de CHECKSIG adecuadamente restringida).
Todo esto para recordar al lector que, si bien esta nueva funcionalidad de script es interesante, proporciona mucha expresividad de cálculo sin la capacidad de inspeccionar datos de transacciones y, por lo tanto, no se puede utilizar para bóvedas u otras aplicaciones de covenant.
el código de operación CAT proporciona un mecanismo para unir los dos scripts, razón por la cual CAT es suficiente para proporcionar convenios. Esta es también la razón por la que hay tantas maneras en las que Script «casi» admite convenios, o en las que propuestas no relacionadas con convenios como CAT resultan habilitar convenios: prácticamente cualquier código de operación que tome valores pequeños y genere valores grandes, o viceversa. -versa, se puede utilizar para introducir datos de transacciones de Big Script en un programa general de Small Script. Incluso una ruptura suficientemente mala del código de operación SHA1 probablemente podría usarse como puente, porque entonces podría hacer «cálculos» con valores grandes interpretándolos como hashes SHA1 y encontrando preimágenes pequeñas para ellos.
Interludio: agujeros de gusano
En realidad, existe una manera de obtener convenios en Small Script, suponiendo que tenga suficiente poder computacional. Al salir «fuera» del Script, los usuarios pueden validar la propia cadena de bloques de Bitcoin, así como la transacción que contiene el Script (debe evitar codificar directamente sus propios datos para evitar tener un tamaño infinito, pero esto se puede hacer por medios indirectos). ; consulte la siguiente sección para obtener más detalles), y luego imponer restricciones adicionales a la transacción imponiendo esas restricciones a esta «visión» validada internamente de sí misma.
Esta idea podría permitir la creación de alguna funcionalidad de covenant limitada, pero es importante recordar que el acceso correcto al almacén clave-valor, que es necesario para dividir grandes cálculos, no se aplica directamente. En lugar de ello, es necesario imponer algún mecanismo adicional para hacer cumplir sanciones drásticas en caso de acceso incorrecto. Esto complica enormemente la implementación de acuerdos tipo bóveda cuya funcionalidad depende de que ciertos patrones de gasto sean realmente imposibles, y no sólo desincentivados.
tres en raya
Hasta ahora hemos hablado sobre la característica anti-equivocación de las firmas Lamport y cómo esto puede usarse para efectuar un «almacenamiento clave-valor global» en Bitcoin Script, que a su vez puede usarse para pasar datos entre programas Script y dividirlos. grandes cálculos en muchas partes independientes. Pero hay otro aspecto interesante y quizás sorprendente de las firmas Lamport, y es que permiten comprometerse con un valor único en un script sin que ese valor afecte el TXID de su transacción.
Esto tiene dos consecuencias: una es que podemos confirmar datos en una transacción sin afectar su TXID, lo que significa que potencialmente podemos cambiar parámetros dentro de un programa Script sin invalidar cadenas de transacciones no confirmadas. La otra es que podemos confirmar datos sin afectar el hash de la firma, lo que significa que los usuarios pueden «prefirmar» una transacción sin conocer primero todos sus datos.
(Por cierto, estas propiedades se aplican a cualquier esquema de firma, siempre que haya una verificación para castigar la firma de múltiples valores. Lo interesante de las firmas Lamport es que podemos usarlas en Bitcoin hoy).
La capacidad de poner datos en un programa Script sin afectar el TXID de la transacción contenida abre la puerta a construcciones en las que un programa puede hacer referencia a su propio código (por ejemplo, inyectando el propio TXID en el programa, que es un hash de todos los datos de la transacción, incluido el programa). Se llama Quiningy se puede utilizar para habilitar la delegación y crear convenios recursivos. Esta habilidad es la motivación detrás del combinador de desconexión en Simplicity. Sin embargo, dado que solo podemos validar firmas Lamport en Small Script, lo que excluye objetos tan grandes como txids, parece que actualmente no hay nada que podamos hacer en esa dirección. Sin embargo, nada nos impide emular pactos no recursivos con trucos similares.
describimos un ejemplo debido a supertestnet en Github.
Consideremos el juego tres en raya, jugado entre dos personas que se turnan para marcar una cuadrícula de tres por tres. Las reglas son simples: ningún jugador puede marcar un cuadrado ya marcado, y si cualquiera de los jugadores marca tres cuadrados seguidos (horizontal, vertical o diagonalmente), gana. Imagine que estos jugadores quieren jugar este juego en cadena, representando cada turno mediante una transacción.
Por supuesto, en paralelo a estas transacciones, tendrían una única transacción de «camino feliz» en la que ambas partes simplemente entregarían monedas al ganador de modo que, si estuvieran de acuerdo sobre los eventos del juego, en realidad no necesitarían publicar. ¡el individuo gira! Pero también es importante construir la transcripción completa del juego para que, en caso de disputas, la cadena de bloques pueda mediar.
Un enfoque que podría adoptar es modelar el juego como una serie de transacciones prefirmadas, cada una de las cuales requiere la firma de ambos jugadores. El primer jugador tiene nueve movimientos posibles. Entonces el segundo jugador firmaría los nueve y el primer jugador firmaría el que quisiera tomar. Luego, para cada uno de los nueve movimientos posibles, el segundo jugador tiene ocho movimientos; entonces el primer jugador firma los ocho, y el segundo jugador elige uno para firmar, y así sucesivamente.
Resulta que esto no funciona del todo: debido a que cualquiera de los jugadores puede negarse a firmar un movimiento en particular, no hay forma de asignar culpas en caso de que el juego se estanque y, por lo tanto, no hay incentivo para que el jugador perdedor completa el juego. . Para evitar esta situación, cada jugador debe firmar todos los movimientos de su contraparte antes de que comience el juego. Entonces un jugador sólo puede negarse a firmar sus propios movimientos, y esto puede desincentivarse fácilmente agregando condiciones de pérdida de tiempo a las transacciones.
Como alternativa a que cada jugador firme los movimientos de los demás, se podría contratar a un tercero de confianza para que firme previamente cada movimiento. Pero el resultado es el mismo: se deben firmar todas las series posibles de transacciones. Para el juego de tres en raya, hay 255168 rutas para un total de 549945 transacciones prefirmadas. Esto está traspasando los límites de la practicidad, y está claro que tal estrategia no se generalizará a juegos no triviales. Para el ajedrez, por ejemplo, estos valores están limitados a continuación por el número de shannonque es 10^120.
La razón por la que tenemos una explosión tan grande es que estamos distinguiendo entre movimientos por transacciones distintas, cada una de las cuales debe configurarse antes de que comience el juego.
Sin embargo, usando firmas Lamport, podemos hacerlo mucho mejor:
- Cada juego de tres en raya tiene (como máximo) nueve movimientos,
- Cada uno de los cuales es una transición entre dos estados de la junta, que son lo suficientemente pequeños como para ser firmados por Lamport,
- Y cada transición debe obedecer reglas que sean lo suficientemente simples como para codificarlas razonablemente dentro de Script.
Por lo tanto, podemos abordar el juego de manera diferente: cada jugador genera una clave pública Lamport con la que firmar el estado del juego después de cada uno de sus movimientos (por lo que el primer jugador genera 5 claves, el segundo jugador 4) . Luego generan una serie de 9 transacciones cuyos taptrees de salida tienen tres ramas:
- Una rama de “movimiento ordinario”, que consta de
- Una firma ordinaria de ambos jugadores;
- Una firma Lamport sobre el estado del juego anterior del jugador correspondiente,
- Una firma Lamport en el siguiente estado del juego del otro jugador,
- Y una comprobación, implementada en Script, de que los estados de los dos juegos estén correctamente relacionados (se diferencian exactamente en un movimiento legal del jugador correcto).
- Una “condición de victoria”, que consiste en
- Una firma ordinaria de ambos jugadores;
- Una firma Lamport en el estado del juego anterior del jugador correspondiente,
- Una comprobación, implementada en Script, de que este jugador ha ganado el juego.
- Una condición de “tiempo de espera”, que consiste en
- Una firma ordinaria de ambos jugadores;
- Un bloqueo de tiempo relativo que ha expirado.
La transacción final, en lugar de una rama de «movimiento normal», tiene una rama de «empate», ya que si todos los movimientos se han completado sin ganar, no hay ningún ganador y presumiblemente las monedas en juego deberían volver a sus propietarios. originales.
Como antes, cada jugador firma previamente todas las transacciones, de las cuales hay 27, incluidas las transacciones de «condición de ganancia» (que envían todas las monedas al jugador ganador), transacciones de «condición de tiempo de espera» (que envían todas las monedas al jugador que no se agotó el tiempo) y “condición de empate”.
Y por cierto, si bien las reglas del ajedrez son un poco más complicadas, y el estado del tablero puede requerir múltiples valores de 32 bits para ser representado, y puede haber más de 9 movimientos, aún es factible realizar exactamente lo mismo. estafa destrucción.
Árboles de transacciones
En el ejemplo anterior, aprovechamos mucho el hecho de que las reglas del tres en raya se pueden incrustar en el propio script, lo que significa que un usuario no puede firmar de manera útil un estado de juego no válido. (Si firman un movimiento no válido, la transacción que representa el movimiento no será válida, y las transacciones que representan todos los movimientos futuros también serán inválidas porque depende de él. Entonces, todo lo que el atacante habrá logrado es filtrar parte de su clave de firma de Lamport, permitiendo que el otro jugador potencialmente forje movimientos en su nombre.
También aprovechamos que nuestro protocolo completo no era muy largo: como máximo 9 movimientos. Esto significa que si un jugador se niega a completar el juego, o lo completo pero no reconoce el resultado, es razonable publicar la transcripción completa del juego en el recurso. Para muchos juegos esto es suficiente.
Está fuera del alcance de esta publicación de blog, pero hay muchos trucos que podemos jugar con este modelo: verificar los cálculos de una sola parte como un «juego» entre un probador y un verificador, subcontratar uno o ambos roles, combinar múltiples pasos en transacciones únicas. con taptrees grandes, reemplazando la transcripción lineal con una búsqueda binaria de pasos no válidos, etc. Estos trucos forman la base de BitVM, BitVM 2, BitVMX, etc.
Usando estos trucos, podemos reducir el costo de los protocolos existentes que dependen de árboles de transacciones no firmadas. Un documento clásico de Bitcoin de 2017 de Bentov y Miller sostiene que los protocolos con estado en el modelo UTXO siempre sufren una explosión exponencial en relación con protocolos análogos en el modelo de cuenta, por ejemplo, en Ethereum. Utilizando las firmas Lamport como almacén global de valores-clave, podemos refutar parcialmente este documento. ¡Pero nos hemos quedado sin espacio y necesitaremos explorar esto en nuestra próxima publicación!
Expresiones de gratitud
Me gustaría agradecer a Robin Linus y Ethan Heilman por revisar un borrador inicial de esta publicación.
Esta es una publicación invitada de Andrew Poelstra. Las opiniones expresadas son enteramente propias y no reflejan necesariamente las de BTC Inc o Bitcoin Magazine.