Browsing by Author "Reisenegger Butrón, Thomas"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Semantics and complexity of bitcoin script
    (2021) Reisenegger Butrón, Thomas; Reutter de la Maza, Juan; Arenas Saavedra, Marcelo Alejandro; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    Con la creciente popularidad de Bitcoin ha surgido la necesidad de entender las funcionalidades, la seguridad y el rendimiento de los distintos mecanismos que componen su protocolo. El lenguaje de programación asociado a Bitcoin, Script, es uno de los principales componentes de las transacciones de Bitcoin. Este fue diseñado deliberadamente para no ser Turing completo, de forma que no fuera posible crear ejecuciones sin fin. Sin embargo, no existen muchos estudios dedicados a analizar las propiedades y limitaciones del lenguaje. Es más, no existe un marco de referencia formal que permita analizar estas características. En este trabajo buscamos proveer este marco de referencia, que permita estudiar Script y analizar ciertos problemas relacionados al lenguaje. Concretamente, definiremos formalmente la semántica de Script y estudiaremos el problema de determinar si un programa definido por un usuario está bien formado, es decir, si puede ser desbloqueado o presenta errores que impiden que esto ocurra. Específicamente, demostraremos que este problema es NP-duro, proveyendo una reducción desde programación lineal entera, y que, para el conjunto más relevante de operadores, si establecemos ciertas suposiciones razonables sobre el uso del lenguaje, el problema se encuentra en NP.