ColliderScript: A $50M Bitcoin Covenant With No New Opcodes

While the last year or two have seen a number of proposals for covenant-proposing extensions to Bitcoin, there has always been a suspicion among experts that covenants may be possible without any extensions. Evidence for this has come in two forms: an expanding repertoire of previously-thought-impossible computations in Script (culminating in the BitVM’s project to implement every RISC-V opcode), and a series of “near-misses” by which Bitcoin developers have found ways that covenants would have been possible, if not for some obscure historical quirk of the system.

Ethan Heilman, Avihu Levy, Victor Kobolov and I have developed a scheme which proves this suspicion was well founded. Our scheme, ColliderScript, enables covenants on Bitcoin today, under fairly reasonable cryptographic assumptions and at a probable cost around 50 million dollars per transaction (plus some hardware R&D).

Despite the outlandish costs to use ColliderScript, setting it up is very cheap, and doing so (alongside an ordinary spending mechanism, using Taproot to separate the two) just might save your coins in case a quantum computer shows up out of nowhere and blows up the system.

No doubt many readers, after reading these claims, are raising one eyebrow to the sky. By the time you are done reading this article, the other one will be just as high.

Covenants

The context of this discussion, for those unfamiliar, is that Bitcoin has a built-in programming language, called Bitcoin Script, which is used to authorize the spending of coins. In its earliest days, Script contained a rich set of arithmetic opcodes which could be used to implement arbitrary computations. But in the summer of 2010, Satoshi disabled many of these in order to quash a series of serious bugs. (Returning to the pre-2010 version of Script is the goal of the Great Script Restoration Project; OP_CAT is a less ambitious proposal in the same direction.) The idea of covenants — transactions which use Script to control the quantity and destination of their coins — didn’t appear for several more years, and the realization that these opcodes would’ve been sufficient to implement covenants didn’t come until even later. By that point, the community was too large and cautious to simply “re-enable” the old opcodes in the same way that they’d been disabled.

Covenants are hypothetical Script constructions that would allow users to control not only the conditions under which coins are spent, but also their destination. This is the basis for many would-be constructions on Bitcoin, from vaults and rate-limited wallets, to new fee-market mechanisms like payment pools, to less-savory constructions like distributed finance and MEV. Millions of words have been spent debating the desirability of covenants and what they would do to the nature of Bitcoin.

In this article I will sidestep this debate, and argue simply that covenants are possible on Bitcoin already; that we will eventually discover how they are possible (without great computational cost or questionable cryptographic assumptions); and that our debate about new extensions to Bitcoin shouldn’t be framed as though individual changes will be the dividing line between a covenant-less or covenant-ful future for Bitcoin.

History

Over the years, a tradition developed of finding creative ways to do non-trivial things even with a limited Script. The Lightning Network was one instance of this, as were less widely-known ideas like probabilistic payments or collision bounties for hash functions. Obscure edge cases, like the SIGHASH_SINGLE bug or the use of public key recovery to obtain a “transaction hash” within the Script interpreter, were noticed and explored, but nobody ever found a way to make them useful. Meanwhile, Bitcoin itself evolved to be more tightly-defined, closing many of these doors. For example, Segwit eliminated the SIGHASH_SINGLE bug and explicitly separated program data from witness data; Taproot got rid of public key recovery, which had provided flexibility at the cost of potentially undermining security for adaptor signatures or multisignatures.

Despite these changes, Script hacking continued, as did the belief among die-hards that somehow, some edge-case might be found that would enable covenant support in Bitcoin. In the early 2020s, two developments in particular made waves. One was my own discovery that signature-based covenants hadn’t died with public key recovery, and that in particular, if we had even a single disabled opcode back — OP_CAT — this would be enough for a fairly efficient covenant construction. The other was BitVM, a novel way to do large computations in Script across multiple transactions, which inspired a tremendous amount of research into basic computations within single transactions.

These two developments inspired a lot of activity and excitement around covenants, but they also crystallized our thinking about the fundamental limitations of Script. In particular, it se

emed as though covenants might be impossible without new opcodes, since transaction data was only ever fed into Script through 64-byte signatures and 32-byte public keys, while the opcodes supporting BitVM could only work with 4-byte objects. This divide was termed “Small Script” and “Big Script”, and finding a bridge between the two became synonymous (in my mind, at least) with finding a covenant construction.

Functional Encryption and PIPEs

It was also observed that, with a bit of moon math, it might be possible to do covenants entirely within signatures themselves, without ever leaving Big Script. This idea was articulated by Jeremy Rubin in his paper FE’d Up Covenants, which described how to implement covenants using a hypothetical crypto primitive called functional encryption. Months later, Misha Komorov proposed a specific scheme called PIPEs which appears to make this hypothetical idea a reality.

This is an exciting development, though it suffers from two major limitations: one is that it involves a trusted setup, meaning that the person who creates the covenant is able to bypass its rules. (This is fine for something like vaults, in which the owner of the coins can be trusted to not undermine his own security; but it is not fine for something like payment pools where the coins in the covenant are not owned by the covenant’s creator.) The other limitation is that it involves cutting-edge cryptography with unclear security properties. This latter limitation will fade away with more research, but the trusted setup is inherent to the functional-encryption approach.

ColliderScript

This overview brings us to the current situation: we would like to find a way to implement covenants using the existing form of Bitcoin Script, and we believe that the way to do this is to find some sort of bridge between the “Big Script” of transaction signatures and the “Small Script” of arbitrary computations. It appears that no opcodes can directly form this bridge (see Appendix A in our paper for a classification of all opcodes in terms of their input and output size). A bridge, if one existed, would be some sort of construction that took a single large object and demonstrated that it was exactly equal to the concatenation of several small objects. It appears, based on our classification of opcodes, that this is impossible.

However, in cryptography we often weaken notions like “exactly equal”, instead using notions like “computationally indistinguishable” or “statistically indistinguishable”, and thereby evade impossibility results. Maybe, by using the built-in cryptographic constructs of Big Script — hashes and elliptic curve signatures — and by mirroring them using BitVM constructions in Small Script, we could find a way to show that a large object was “computationally indistinguishable” from a series of small ones? With ColliderScript, this is exactly what we did.

What does this mean? Well, recall the hash function collision bounty that we mentioned earlier. The premise of this bounty is that anybody who can “collide” a hash function, by providing two inputs that have the same hash output, can prove in Big Script that they did so, and thereby claim the bounty. Since the input space of a hash function is much bigger (all bytestrings of up to 520 bytes in size) than the output space (bytestrings of exactly 32 bytes in size), mathematically speaking there must be many many such collisions. And yet, with the exception of SHA1, nobody has found a faster way to find these collisions than by just calling the hash function over and over and seeing if the result matches that of an earlier attempt.

This means that, on average, for a 160-bit hash function like SHA1 or RIPEMD160, a user will need to do at least 2^80 work, or a million million million million iterations, to find a collision. (In the case of SHA1, there is a shortcut if the user is able to use inputs of a particular form; but our construction forbids these so for our purposes we can ignore this attack.) This assumes that the user has an effectively infinite amount of memory to work with; with more realistic assumptions, we need to add another factor of one hundred or so.

If we imagine that SHA1 and RIPEMD160 can be computed as efficiently as Bitcoin ASICs compute SHA256, then the cost of such a computation would be about the same as 200 blocks, or around 625 BTC (46 million dollars). This is a lot of money, but many people have access to such a sum, so this is possible.

To find a triple collision, or three inputs that evaluate to the same thing, would take about 2^110 work, even with very generous assumptions about access to memory. To get this number, we need to add another factor of 16 million to our cost — bringing our total to over 700 trillion dollars. This is also a lot of money, and one which nobody has access to today.

The crux of our construction is as follows: to prove that a series of small objects is equivalent to a single large object, we first find a hash collision between our target object (which we assume can be rerandomized somehow, or else we’d be doing a “second-preimage search” rather than a collision search, which would be much much harder) and an “equivalence tester object”. These equivalence tester objects are constructed in a way that they can be easily manipulated both in Big Script and Small Script.

Our construction then checks, in Bitcoin Script, both that our large object collides with our equivalence tester (using exactly the same methods as in the hash-collision bounty) and that our series of small objects collides with the equivalence tester (using complex constructions partially cribbed from the BitVM project, and described in detail in the paper). If these checks pass, then either our small and big objects were the same, or the user found a triple-collision: two different objects which both collide with the tester. By our argument above, this is impossible.

Conclusion

Bridging Small Script and Big Script is the hardest part of our covenant construction. To go from this bridge to an actual covenant, there are a few more steps, which are comparatively easy. In particular, a covenant script first asks the user to sign the transaction using the special “generator key”, which we can verify using the OP_CHECKSIG opcode. Using the bridge, we break this signature into 4-byte chunks. We then verify that its nonce was also equal to the generator key, which is easy to do once the signature has been broken up. Finally, we use techniques from the Schnorr trick to extract transaction data from the signature, which can then be constrained in whatever way the covenant wants.

There are a few other things we can do: Appendix C describes a ring signature construction that would allow coins to be signed by one of a set of public keys, without revealing which one was used. In this case, we use the bridge to break up the public key, rather than the signature. Doing so gives us a significant efficiency improvement relative to the covenant construction, for technical reasons related to Taproot and detailed in the paper.

A final application that I want to draw attention to, discussed briefly in Section 7.2 of the paper, is that we can use our covenant construction to pull the transaction hash out of a Schnorr signature, and then simply re-sign the hash using a Lamport signature.

Why would we do this? As argued in the above link, Lamport-signing the signature this way makes it a quantum-secure signature on the transaction data; if this construction were the only way to sign for some coins, they would be immune from theft by a quantum computer.

Of course, since our construction requires tens of millions of dollars to use, nobody would make this construction the only way to sign for their coins. But there’s nothing stopping somebody from adding this construction to their coins, in addition to their existing non-quantum-secure methods of spending.

Then, if we woke up tomorrow to find that cheap quantum computers existed which were able to break Bitcoin signatures, we might propose an emergency soft-fork which disabled all elliptic curve signatures, including both Taproot key-spends and the OP_CHECKSIG opcode. This would effectively freeze everybody’s coins; but if the alternative were that everybody’s coins were freely stealable, maybe it wouldn’t make any difference. If this signature-disabling soft-fork were to allow OP_CHECKSIG opcode when called with the generator key (such signatures provide no security anyway, and are only useful as a building block for complex Script constructions such as ours), then users of our Lamport-signature construction could continue to freely spend their coins, without fear of seizure or theft.

Of course, they would need to spend tens of millions of dollars to do so, but this is much better than “impossible”! And we expect and hope to see this cost drop dramatically, as people build on our research.

This is a guest post by Andrew Poelstra. Opinions expressed are entirely their own and do not necessarily reflect those of BTC Inc or Bitcoin Magazine.

Read More[#item_full_content]Bitcoin Magazine – Bitcoin News, Articles and Expert Insights