Si bien en los últimos dos años se han visto una serie de propuestas para ampliar los convenios a Bitcoin, siempre ha habido una sospecha entre los expertos de que los convenios pueden ser posibles. pecado cualquier extensión. La evidencia de esto se ha presentado en dos formas: un repertorio en expansión de cálculos en Script que antes se consideraban imposibles (que culminaron en el proyecto de BitVM para implementar todos los códigos de operación RISC-V), y una serie de «casi accidentes» por los cuales los desarrolladores de Bitcoin han encontrado maneras de que los pactos hubiera sido posiblesi no fuera por alguna oscura peculiaridad histórica del sistema.
Ethan Heilman, Avihu Levy, Victor Kobolov y yo hemos desarrollado un plan que demuestra que esta sospecha estaba bien fundada. Nuestro esquema, ColliderScriptpermite acuerdos sobre Bitcoin hoy, bajo supuestos criptográficos bastante razonables ya un costo probable de alrededor de 50 millones de dólares por transacción (más algo de investigación y desarrollo de hardware).
A pesar de los extravagantes costos de usar ColliderScript, configurarlo es muy barato y hacerlo (junto con un mecanismo de gasto ordinario, usando Taproot para separar los dos) tal vez guarda tus monedas en caso de que una computadora cuántica aparezca de la nada y haga estallar el sistema.
Sin duda muchos lectores, después de leer estas afirmaciones, alzarán una ceja al cielo. Cuando termine de leer este artículo, el otro será igual de alto.
pactos
El contexto de esta discusión, para aquellos que no están familiarizados, es que Bitcoin tiene un lenguaje de programación incorporado, llamado Bitcoin Script, que se utiliza para autorizar el gasto de monedas. En sus inicios, Script contenía un rico conjunto de códigos de operación aritméticos que podían usarse para implementar cálculos arbitrarios. Pero en el verano de 2010, Satoshi desactivó muchos de ellos para solucionar una serie de errores graves. (Volver a la versión anterior a 2010 de Script es el objetivo del Gran proyecto de restauración de guiones.; OP_CAT (Es una propuesta menos ambiciosa en la misma dirección). La idea de convenios (transacciones que utilizan Script para controlar la cantidad y el destino de sus monedas) no apareció durante varios años.y la comprensión de que estos códigos de operación habrían sido suficientes para implementar convenios no llegó hasta incluso más tarde. En ese momento, la comunidad era demasiado grande y cautelosa para simplemente «volver a habilitar» los códigos de operación antiguos de la misma manera que habían sido deshabilitados.
Los pactos son construcciones hipotéticas de scripts que permitirían a los usuarios controlar no sólo las condiciones bajo las cuales se gastan las monedas, sino también su destino. Esta es la base de muchas construcciones posibles sobre Bitcoin, desde bóvedas y billeteras con tasa limitada, hasta nuevos mecanismos de mercado de tarifas como grupos de pagosunas construcciones menos sabrosas como finanzas distribuidas y MEV. Se han gastado millones de palabras debatiendo la conveniencia de los convenios y lo que afectarían a la naturaleza de Bitcoin.
En este artículo eludiré este debate y argumentaré simplemente que los acuerdos ya son posibles en Bitcoin; que eventualmente descubriremos cómo son posibles (sin grandes costos computacionales ni supuestos criptográficos cuestionables); y que nuestro debate sobre nuevas extensiones de Bitcoin no debería enmarcarse como si los cambios individuales fueran la línea divisoria entre un futuro sin pacto o lleno de pactos para Bitcoin.
historia
A lo largo de los años, se desarrolló una tradición de encontrar formas creativas de hacer cosas no triviales incluso con un guión limitado. Lightning Network fue un ejemplo de esto, al igual que ideas menos conocidas como pagos probabilísticos oh recompensas por colisión para funciones hash. Casos extremos oscuros, como el Error SIGHASH_SINGLE o el uso de recuperación de clave pública para obtener un «hash de transacción» dentro del intérprete de Script, fueron anotados y explorados, pero nadie encontró una manera de hacerlos útiles. Mientras tanto, el propio Bitcoin evolucionó para estar más definido, cerrando muchas de estas puertas. Por ejemplo, Segwit eliminó el error SIGHASH_SINGLE y separó explícitamente los datos del programa de los datos de los testigos; Taproot se deshizo de la recuperación de clave pública, que había brindado flexibilidad a costa de socavar potencialmente la seguridad de las firmas de adaptadores o firmas Múltiples.
A pesar de estos cambios, el hackeo de scripts continuó, al igual que la creencia entre los más intransigentes de que, de alguna manera, se podría encontrar algún caso límite que permitiera el soporte de pactos en Bitcoin. A principios de la década de 2020, dos acontecimientos en particular causaron sensación. una era mi propio descubrimiento que los convenios basados en firmas no habían muerto con la recuperación de la clave pública y que, en particular, si tuviéramos siquiera un solo código de operación deshabilitado (OP_CAT), esto sería suficiente para una construcción de convenios bastante eficiente. La otra era BitVMuna forma novedosa de realizar grandes cálculos en Script a través de múltiples transacciones, que inspiró una enorme cantidad de investigación sobre cálculos básicos dentro de transacciones individuales.
Estos dos desarrollos inspiraron mucha actividad y entusiasmo en torno a los convenios, pero también cristalizaron nuestro pensamiento sobre las limitaciones fundamentales de Script. En particular, se
Parecía como si los pactos pudieran ser imposibles sin nuevos códigos de operación, ya que los datos de las transacciones solo se ingresaban en Script a través de firmas de 64 bytes y claves públicas de 32 bytes, mientras que los códigos de operación que soportaban BitVM solo podía funcionar con objetos de 4 bytes. Esta división se denomina «Escritura pequeña» y «Escritura grande»y encontrar un puente entre los dos se convirtió en sinónimo (al menos en mi opinión) de encontrar una construcción de pacto.
Cifrado funcional y PIPE
También se observará que, con un poco de matemáticas lunares, podría ser posible hacer convenios enteramente dentro de las mismas firmas, sin tener que salir del Big Script. Esta idea fue articulada por Jeremy Rubin en su artículo. Pactos FE’d Upque describía cómo implementar convenios utilizando una cripto primitiva hipotética llamada cifrado funcional. Meses después, Misha Komorov propuso una esquema específico llamado PIPEs lo que parece hacer realidad esta idea hipotética.
Se trata de un avance interesante, aunque adolece de dos limitaciones importantes: una es que implica una configuración confiable, lo que significa que la persona que crea el pacto puede eludir sus reglas. (Esto está bien para algo como las bóvedas, en las que se puede confiar en que el propietario de las monedas no socavará su propia seguridad; pero no está bien para algo como los fondos de pago donde las monedas del pacto no son propiedad del creador del pacto. ) La otra limitación es que implica criptografía de vanguardia con propiedades de seguridad poco claras. Esta última limitación desaparecerá con más investigación, pero la configuración confiable es inherente al enfoque de cifrado funcional.
ColliderScript
Esta descripción general nos lleva a la situación actual: nos gustaría encontrar una manera de implementar convenios utilizando la forma existente de Bitcoin Script, y creemos que la manera de hacerlo es encontrar algún tipo de puente entre el «Gran Script» de firmas de transacciones y el «Small Script» de cálculos arbitrarios. Parece que ningún código de operación puede formarse directamente este puente (consulte el Apéndice A de nuestro artículo para obtener una clasificación de todos los códigos de operación en términos de su tamaño de entrada y salida). Un puente, si existiera, sería algún tipo de construcción que tomara un solo objeto grande y demostrara que es exactamente igual a la concatenación de varios objetos pequeños. Parece, según nuestra clasificación de códigos de operación, que esto es imposible.
Sin embargo, en criptografía a menudo debilitamos nociones como «exactamente igual», y en su lugar utilizamos nociones como «computacionalmente indistinguible» o «estadísticamente indistinguible», y así evadimos resultados de imposibilidad. Tal vez, usando las construcciones criptográficas incorporadas de Big Script (hashes y firmas de curvas elípticas) y reflejándolas usando construcciones BitVM en Small Script, podríamos encontrar una manera de mostrar que un objeto grande era «computacionalmente indistinguible» de otro. ¿Una serie de pequeños? Con ColliderScript, esto es exactamente lo que hicimos.
¿Qué quiere decir esto? Bueno, recuerda el recompensa por colisión de función hash que mencionamos anteriormente. La premisa de esta recompensa es que cualquiera que pueda «colisionar» una función hash, proporcionando dos entradas que tengan la misma salida hash, puede demostrar en Big Script que lo hizo y, por lo tanto, reclamar la recompensa. Dado que el espacio de entrada de una función hash es mucho más grande (todas las cadenas de bytes de hasta 520 bytes de tamaño) que el espacio de salida (cadenas de bytes de exactamente 32 bytes de tamaño), matemáticamente hablando debe haber muchas colisiones. de este tipo. Y sin embargo, con el excepción de SHA1nadie ha encontrado una manera más rápida de encontrar estas colisiones que simplemente llamar a la función hash una y otra vez y ver si el resultado coincide con el de un intento anterior.
Esto significa que, en promedio, para una función hash de 160 bits como SHA1 o RIPEMD160, un usuario necesitará realizar al menos 2^80 trabajos, o un millón de millones de iteraciones, para encontrar una colisión. (En el caso de SHA1, existe una atajo si el usuario puede utilizar entradas de una forma particular; pero nuestra construcción los prohíbe, por lo que para nuestros propósitos podemos ignorar este ataque). Esto supone que el usuario tiene efectivamente una cantidad infinita de memoria para trabajar; con supuestos más realistas, necesitamos agregar otro factor de cien aproximadamente.
Si imaginamos que SHA1 y RIPEMD160 se pueden calcular con tanta eficiencia como los ASIC de Bitcoin calculan SHA256, entonces el costo de dicho cálculo sería aproximadamente el mismo que 200 bloques, o alrededor de 625 BTC (46 millones de dólares). Es mucho dinero, pero muchas personas tienen acceso a esa suma, por lo que esto es posible.
para encontrar un triple una colisión, o tres entradas que se evalúen como lo mismo, requerirían aproximadamente 2^110 de trabajo, incluso con suposiciones muy generosas sobre el acceso a la memoria. Llegar este número, necesitamos agregar otro factor de 16 millones a nuestro costo, elevando nuestro total a más de 700 billones de dólares. Esto también es mucho dinero, y uno que nadie tiene acceso a la actualidad.
El quid de nuestra construcción es el siguiente: para demostrar que una serie de objetos pequeños es equivalente a un solo objeto grande, primero encontramos una colisión hash entre nuestro objeto objetivo (que asumimos que se puede volver a aleatorizar de alguna manera, o de lo contrario, haríamos una «búsqueda de segunda preimagen» en lugar de una búsqueda de colisión, que sería mucho más difícil) y un «objeto de prueba de equivalencia». Estos objetos de prueba de equivalencia están construidos de manera que puedan manipularse fácilmente tanto en Big Script como en Small Script.
Luego, nuestra construcción verifica, en Bitcoin Script, que nuestro objeto grande colisiona con nuestro probador de equivalencia (usando exactamente los mismos métodos que en la recompensa de colisión hash) y que nuestra serie de objetos pequeños choca con el probador de equivalencia (usando construcciones complejas parcialmente extraído del proyecto BitVM y descrito en detalle en el artículo). Si estas comprobaciones pasan, entonces nuestros objetos pequeños y grandes eran iguales. es, o el usuario encontró una triple colisión: dos objetos diferentes que chocan con el probador. Según nuestro argumento anterior, esto es imposible.
Conclusión
Unir el guión pequeño y el guión grande es la parte más difícil de la construcción de nuestro pacto. Para pasar de este puente a un pacto real, hay algunos pasos más, que son comparativamente fáciles. En particular, un script de covenant primero le pide al usuario que firme la transacción usando la «clave generadora» especial, que podemos verificar usando el código de operación OP_CHECKSIG. Usando el puente, dividimos esta firma en fragmentos de 4 bytes. Luego verificamos que su nonce también sea igual a la clave del generador, lo cual es fácil de hacer una vez que se ha dividido la firma. Finalmente utilizamos técnicas de la truco de schnorr para extraer datos de transacción de la firma, que luego pueden restringirse de la forma que desee el pacto.
Hay algunas otras cosas que podemos hacer: el Apéndice C describe una construcción de firma en anillo que permitiría firmar monedas con una de un conjunto de claves públicas, sin revelar cuál se usa. En este caso utilizamos el puente para separar al público. clave, en lugar de la firma. Hacerlo nos brinda una mejora significativa de la eficiencia en relación con la construcción del convenio, por razones técnicas relacionadas con Taproot y detalladas en el documento.
Una aplicación final sobre la que quiero llamar la atención, analizada brevemente en la Sección 7.2 del documento, es que podemos usar nuestra construcción de convenio para extraer el hash de transacción de una firma Schnorr y luego simplemente volver a firmar el hash. usando una firma Lamport.
¿Por qué haríamos esto? Como se argumenta en el enlace anterior, la firma Lamport de esta manera la convierte en una firma cuánticamente segura en los datos de la transacción; si esta construccion fuera de la solo forma de firmar por algunas monedas, serán inmunes al robo por parte de una computadora cuántica.
Por supuesto, dado que nuestra construcción requiere decenas de millones de dólares para su uso, nadie haría de esta construcción la única forma de firmar por sus monedas. Pero no hay nada que impida que alguien agregue esta construcción a sus monedas. además de sus actuales métodos de gasto no cuánticos seguros.
Entonces, si mañana nos despertáremos y descubriéramos que existían computadoras cuánticas baratas capaces de romper las firmas de Bitcoin, podríamos proponer una bifurcación suave de emergencia que deshabilitara todas las firmas de curvas elípticas, incluidos los gastos de clave Taproot y el código de operación OP_CHECKSIG. Esto efectivamente congelaría las monedas de todos; pero si la alternativa fuera que las monedas de todos pudieran robarse libremente, tal vez no haría ninguna diferencia. Si este software de desactivación de firmas permite el código de operación OP_CHECKSIG cuando se llama con la clave del generador (tales firmas no brindan seguridad de todos los modos y solo son útiles como bloque de construcción para construcciones de scripts complejas como la nuestra), entonces los usuarios de nuestro software Lamport- La firma constructora podría seguir gastando libremente sus monedas, sin miedo a ser incautadas o robadas.
Por supuesto, necesitarían gastar decenas de millones de dólares para hacerlo, ¡pero esto es mucho mejor que «imposible»! Y esperamos y esperamos ver que este costo disminuya dramáticamente, a medida que la gente avanza en nuestra investigació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.