Semantics and complexity of bitcoin script
Loading...
Date
2021
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2021