Paper 2024/1802

ColliderScript: Covenants in Bitcoin via 160-bit hash collisions

Ethan Heilman
Victor I. Kolobov, StarkWare
Avihu M. Levy, StarkWare
Andrew Poelstra, Blockstream
Abstract

We introduce a method for enforcing covenants on Bitcoin outputs without requiring any changes to Bitcoin by designing a hash collision based equivalence check which bridges Bitcoin's limited Big Script to Bitcoin's Small Script. This allows us evaluate the signature of the spending transaction (available only to Big Script) in Small Script. As Small Script enables arbitrary computations, we can introspect into the spending transaction and enforce covenants on it. Our approach leverages finding collisions in the $160$-bit hash functions: SHA-1 and RIPEMD-160. By the birthday bound this should cost $\sim2^{80}$ work. Each spend of our covenant costs $\sim2^{86}$ hash queries and $\sim2^{56}$ bytes of space. For security, we rely on an assumption regarding the hardness of finding a $3$-way collision (with short random inputs) in $160$-bit hash functions, arguing that if the assumption holds, breaking covenant enforcement requires $\sim2^{110}$ hash queries. To put this in perspective, the work to spend our covenant is $\sim33$ hours of the Bitcoin mining network, whereas breaking our covenant requires $\sim 450,000$ years of the Bitcoin mining network. We believe there are multiple directions of future work that can significantly improve these numbers. Evaluating covenants and our equivalence check requires performing many operations in Small Script, which must take no more than $4$ megabytes in total size, as Bitcoin does not allow transactions greater than $4$ megabytes. We only provide rough estimates of the transaction size because, as of this writing, no Small Script implementations of the hash functions required, SHA-1 and RIPEMD-160, have been written.

Note: Fixes typos, updates security assumption

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
BitcoinSHA-1RIPEMD-160collisionscovenantsMerkle tree
Contact author(s)
ethan r heilman @ gmail com
victor k @ starkware co
avihu @ starkware co
apoelstra @ blockstream com
History
2024-11-11: last of 2 revisions
2024-11-04: received
See all versions
Short URL
https://ia.cr/2024/1802
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1802,
      author = {Ethan Heilman and Victor I. Kolobov and Avihu M. Levy and Andrew Poelstra},
      title = {{ColliderScript}: Covenants in Bitcoin via 160-bit hash collisions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1802},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1802}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.