Dublin Core
Title
Semantics and complexity of bitcoin script
Subject
005.13
Ciencias de la computación
Lenguajes de secuencias de comandos (Ciencia de la computación)
Bitcoin
Criptomonedas
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2021
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.
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.
Creator
Reisenegger Butrón, Thomas
Date
2021-06-10T12:09:42Z
2021-06-10T12:09:42Z
2021
Contributor
Reutter de la Maza, Juan
Arenas Saavedra, Marcelo Alejandro
Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Rights
acceso abierto
Format
x, 175 páginas
application/pdf
Language
en
Type
tesis de maestría
Identifier
10.7764/tesisUC/ING/60581
https://doi.org/10.7764/tesisUC/ING/60581
https://repositorio.uc.cl/handle/11534/60581