ColliderScript: Covenants in Bitcoin via 160-bit hash collisions

Ethan Heilman1 , Victor I. Kolobov2 , Avihu M. Levy2 , and Andrew Poelstra3

1
[Link]@[Link]
2
StarkWare, {victor.k,avihu}@[Link]
3
Blockstream, apoelstra@[Link]

November 7, 2024

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: SHA1 and RIPEMD.
By the birthday bound this should cost ∼ 280 work. Each spend of our covenant costs ∼ 286
hash queries and ∼ 256 bytes of space. For security, we rely on an assumption regarding the
hardness of finding a 3-way collision (with short inputs) in 160-bit hash functions, arguing that if
the assumption holds, breaking covenant enforcement requires ∼ 2110 hash queries. To put this in
perspective, the work to spend our covenant is ∼ 33 hours of the Bitcoin mining network, whereas
breaking our covenant requires ∼ 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 transac-
tions 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, SHA1 and
RIPEMD, have been written.

1 Introduction
Since its inception, Bitcoin has contained a scripting language used to express conditions under which
coins are spent. In 2010, in response to multiple bug reports, Satoshi removed several opcodes from the
language [43, 42]. While it was not realized at the time, this removal split the language into two parts:
“Big Script,” a set of opcodes used to manipulate signatures, hashes and other cryptographic objects;
and “Small Script,” a set of opcodes which do arbitrary computations but only on 32-bit inputs.
This bifurcation is important because Big Script’s OP CHECKSIG opcode, which verifies a signature
on the full transaction data, is the only opcode capable of full transaction introspection. By transaction
introspection, we mean the ability of a Bitcoin script to examine the bytes of transaction that is
attempting to spend that output, i.e., the spending transaction. The “Schnorr trick” [35, 36] provides
a way to structure a signature provided to OP CHECKSIG such that we can extract the hash of the
spending transaction (aka, the sighash) from the signature.
Big Script is not expressive enough to enforce arbitrary spending conditions on the bytes of the
spending transaction using the sighash (hash of the spending transaction). Small Script is expressible
enough to enforce these conditions, but because OP CHECKSIG requires a signature much larger than
32 bits, Small Script cannot perform operations on such signatures.
Scripts which can introspect into the data of the spending transaction are termed covenants [32], and
have been a recent major source of controversy and research in Bitcoin [6, 47, 46, 22, 40]. Covenants,
if possible in Bitcoin, would enable new functionality such as rate-limited wallets and vaults [33] and
more efficient layer-two protocols [1].

1
 The most direct way to enable covenants would be to extend the Bitcoin Script language to include
transaction introspection opcodes, which directly copy transaction data onto the stack to be processed
by other opcodes. A less direct way would be to heal the split between Big Script and Small script, e.g.
by enabling the OP CAT concatenation opcode. However, any changes to Bitcoin must have consen-
sus across all economic stakeholders, and because of the controversy around covenants in particular,
consensus on any changes may not be achieved quickly.
In this paper, we propose ColliderScript, a novel way to bridge Big Script and Small Script, allowing
transaction signatures to be manipulated in such a way that any signed transaction data can be
extracted. Our key idea is exploit SHA1 and RIPEMD1 collisions to show that a signature encoded as a
vector of 32-bit Small Script elements and a Big Script signature represent the same signature. We refer
to this as an equivalence check. The key idea behind this equivalence check is that H(s1 ) = H(π) = H(s2 )
where π ̸= s1 implies that s1 = s2 even if you can’t directly compare s1 and s2 . For 160-bit hash
functions, finding single collisions to perform our equivalence check is practical but finding the triple
collisions needed to break out equivalence check is not practical. Using this idea we construct a small-
to-big equivalence check showing that a Big Script object is the same as a Small Script object. Our
parameters are not exact, as our construction depends on the Small Script implementation of SHA1
and RIPEMD, which, as of this writing, hasn’t been written yet.
In particular, we show the following
Proposition 1 (Informal). Under some assumptions on SHA1 and RIPEMD, there is a Bitcoin
locking script capable of small-to-big equivalence check, such that
• The script uses less than 4 million weight units (bytes) i.e., small enough to be a valid transaction.

• To prove small-to-big equivalence check, the spender needs to provide the locking script with input
which requires computing ∼ 286 hash queries, and using ∼ 256 bytes of memory.
• An adversary needs to perform significantly more work to fool the equivalence check, roughly 2110
queries.
In addition, this construction requires a globally one-time precomputation of 283 − 293 hashes. More-
over, a covenant locking script exists with roughly the same parameters (see Figure 8)
Throughout this paper when we talk about Bitcoin script we mean Bitcoin Tapscript (BIP-342
[53]). Our scheme only works for Tapscript and can not be used for pre-Tapscript Bitcoin script. One
of reasons it does not work on pre-tapscript is that we rely on Schnorr signatures to recover bytes of
the spending transaction from the signature and Schnorr signatures are not available in pre-Tapscript.
We treat SHA1 and RIPEMD as ideal 160-bit hash functions despite collision attacks on SHA1 [45,
29] that are well below the 280 cost of a generic attack on an ideal 160-bit function. We discuss in
Section 7.1 why we consider this a reasonable assumption to make.
Our paper is organized as follows. In Section 1.1 we provide an outline of how our technique works.
We follow this with a comparison to related work in Section 1.2. Section 2 defines notation and gives
an overview of Bitcoin and Bitcoin scripts, and transaction introspection. In Section 3, we present
definitions for covenants and equivalence checks in Bitcoin. Then we introduce Bitcoin equivalence
tester sets (Section 4), our equivalence check construction (Section 5) and propose parameters to
instantiate our construction with (Section 6). Section 7 discusses the security of our scheme. Finally
we conclude and discuss future directions (Section 8)

1.1 Outline of techniques

Here we provide an algorithm description for checking the equivalence of a signature in “Big Script” to
the same signature in “Small Script” and how it relates to our covenant construction. We emphasize
that the full fledged covenant construction is more complicated than what we present in this section
but it follows the same template.
Our covenant has the following template:
• The transaction, tx, attempting to spend the covenant provides:
1 Throughout, RIPEMD refers to RIPEMD-160.

2
 – s1 , a signature on the spending transaction2 ;
– ⟨s2 ⟩32 , a small-script representation of s1 . That is, we chop s2 into 32-bit chunks, which is
the largest element size that Small Script can manipulate;
– π = (ω, t), the equivalence witness used to show s1 is equivalent to ⟨s2 ⟩32 i.e., s1 = s2 .
• The covenant being spent:
– Verifies s1 represents a valid signature of the spending transaction, by running OP CHECKSIG
– Applies our equivalence check using the equivalence witness π = (ω, t) to verify that indeed
⟨s2 ⟩32 is a small-script representation of s1 .
– Knowing that ⟨s2 ⟩32 is a small-script representation of the valid signature on the spending
transaction, uses auxiliary information, TxData, to extract the actual data of the spending
transaction, tx.
– Check conditions on the tx, and accept/reject accordingly
Big Script and Small Script have different limitations with respect to the operations they can
perform. In Big Script we can do very few operations: hashing, checking equality, and in some cases
treating elements as public keys or signatures to perform signature verification. The latter being
accomplished by the OP CHECKSIG opcode, which, importantly, is the only way to access data related
to the spending transaction in Bitcoin script. In Small Script we don’t have access to the spending
transaction data but we can compute arbitrary logic (though due to the limited number of available
opcodes, this comes at a cost). For complex operations such as implementing cryptographic hash
functions, this severely limits the number of Small Script hash function calls a single script can make.
With the above limitations in mind, we define a special set D, indexed by π = (ω, t), where ω is
a Small Script element to be hashed iteratively, alternately using RIPEMD or SHA1 according to the
bits of a binary vector t = (t0 , . . . , t||t||−1 ). In pseudo code, to generate dω,t ∈ D from (ω, t) we perform
the following algorithm, to which we refer as [Link]:
1. Let res ← ω
2. For i = 0, . . . , (||t|| − 1):
(
SHA1(res), ti = 0
• res ←
RIPEMD(res), ti = 1

3. Return dω,t ← res

Crucially, as ω is readable in Small Script, this algorithm can be implemented both in Big Script
(using OP RIPEMD160 and OP SHA1) and in Small Script (using explicit implementations of these hash
functions)3 . For ease of collisions we need a hash function that can take a input of roughly 100-bits.
An illustration of how [Link] is computed is given in Figure 1 (Right). To prove s1 (an element of
Big Script) and s2 (an array of Big Script elements) are equivalent using the set D, the core idea is to
find d ∈ D such that SHA1(s1 ) = d = SHA1(s2 ). Here the first equality can be verified in Big Script
and the second equality in Small Script. We claim that this is sufficient to imply that s1 = s2 .
Whenever s1 = s2 then clearly SHA1(s1 ) = SHA1(s2 ), and if we assume D is large enough and
that we have freedom to vary s1 , finding an appropriate d is feasible, as it reduces to finding a single
collision. To argue soundness, suppose that s1 ̸= s2 . That means that an attacker wishing to prove
false equivalence will need to find SHA1(s1 ) = SHA1(s2 ) = d with s1 , s2 , d distinct. Soundness follows
from the assumption that finding a triple collision (with short inputs) is hard.
Next, we outline how a (regular) collision in SHA1 can be found efficiently. Note that the size of
SHA1 digest is 160 bit. Hence one straightforward way to find collisions is to precompute and store a
subset of D of size 280 , and then perform a search on the set of signatures s to find a collision. This
requires (on average) ∼ 280 work and ∼ 280 bits of memory, the latter making it infeasible.
2 We don’t use the security properties of the signature here; we use it only to allow Bitcoin script to access the spending

transaction data, as the message being signed is a hash of the spending transaction data (also known as a sighash).
3 We utilize hash functions as these are the only opcodes capable of mutating an element in Big Script. Furthermore,

we need their explicit implementations in Small Script. Hence, we restrict ourselves to only SHA1 and RIPEMD, as we
expect them to have a reasonable Small Script implementation cost.

3
 Signature Signature Spending
Equivalence witness π (Small Script) txn bytes ω t=<0,1,1,0>
(Big Script)
sighash of the
spending txn ω t <s2>32 <TxData>32 𝒟gen(ω,t)
s1 t0=0 t0=1
public Recover
SigHashS SHA-1 RIPEMD
key
<sighash>S t1=0 t1=1 ...
CHECKSIG SHA-1
...
𝒟 gen(ω,t)
...
𝒟 gen(ω,t)S SHA-1S SHA-1 RIPEMD

If True: EQUAL
dω,t <dω,t>32
EQUALS
Enforce
CovenantS
... t2=0 t2=1

SHA-1 RIPEMD
s1 commits to
spending txn bytes
... t3=0 t3=1
If both are equal:
then equivalence check passes (s1 = s2) SHA-1 RIPEMD

dω,t
=SHA1(RIPEMD(RIPEMD(SHA-1(ω)))

Figure 1: (Left) Visualization of the Tapscript of our equivalence check based covenant. Functions
denoted with subscript S and grey background are evaluated in small script, i.e., built out of Small
Script opcodes such as OP ADD that operate on Small Script elements (0 to 33-bit values). Elements
pushed on the stack from the spending transaction are colored purple.
(Right) Our function [Link] which recursively hashes a seed ω using either SHA1 or RIPEMD based
on the bitstring. For brevity t we use a t of length 4 of bits. In practice t is 70 bits. The path executed
through [Link] when t = ⟨0, 1, 1, 0⟩ is highlighted in orange.

-collision

Figure 2: A cycle where each arrow is an evaluation of h, which by the birthday bound, is expected
to be of length ∼ 280 . Since the two values in red evaluate to x0 , they constitute a collision for h. With
probability 1/2 it will be a collision between the set D and the signatures of the spending transaction.

To significantly reduce the memory requirement define a function h, that given some input, outputs
either SHA1(s), where s is a valid signature on the spending transaction, or SHA1(d) for some d ∈ D.
More concretely, (
SHA1(s(x)), first bit of x is 0,
h(x) =
[Link](dω(x),t(x) ), first bit of x is 1,
where there is some deterministic way to derive s = s(x), ω = ω(x), and t = t(x) from x. Then, the
goal is to find a cycle in the repeated application of h, namely, values

x0 , x1 = h(x0 ), x2 = h(x1 ), . . . , xk+1 = h(xk ),

such that xk+1 = x0 . This will, with a probability of 1/2, result in two inputs, s and d = [Link](dω(x),t(x) ),
such that SHA1(s) = d (for example, x0 = SHA1(s) and xk+1 = d). Figure 2 illustrates collision de-
tection using a cycle. Relying on known cycle search algorithms [23, 49] it yields, for D sufficiently
large, an algorithm with ∼ 280 running time complexity and a manageable memory cost. Nevertheless,
analyzing the best concrete parameters for this construction is the main challenge of this work.

4
 BLAKE3

BLAKE3 BLAKE3 BLAKE3 BLAKE3

SHA1 RIPEMD

Figure 3: A Small Script cost saving technique for generating D’s elements. Instead of computing
all log2 |D| layers in Small Script, the first u layers are committed to a BLAKE3 (truncated to 128-bit
hashes) Merkle tree. To generate an element in this new approach, a value from D’s binary tree’s u-th
layer, Lu , is decommitted from the Merkle tree, followed by log2 |D| − u layers computed as before,
using SHA1 and RIPEMD. Blue circles are 160-bit, while red circles are 128-bit. Because BLAKE3’s
input size is 512-bit, we can pack three 160-bit values (leaf) or four 128-bit values (inner node) together.

To summarize, our covenant, as shown in Figure 1 (Left), proceeds as follows, given input s1 (in
Big Script), s2 (in Small Script), (ω, t = (t0 , . . . , t||t||−1 )) (in Small Script), and some auxiliary data:
1. In Big Script, verify that s1 represents a valid signature of the spending transaction, tx

2. In Big Script, compute dω,t and check that SHA1(s1 ) = dω,t

3. In Small Script, compute dω,t and check that SHA1(s2 ) = dω,t
4. In Small Script, use the auxiliary information to extract from s2 the transaction data, tx
5. In Small Script, check conditions on the data tx, and accept/reject accordingly

To spend the above covenant, a spender will need to run an off-chain algorithm to find a collision
between the signatures of the spending transaction and D’s elements. This algorithm will produce a
valid s1 and (ω, t) for the spender to use.

Reducing Small Script costs. Our equivalence check requires the implementation of SHA1 and
RIPEMD in Small Script. As of writing, no one has published source code for Small Script implemen-
tations of these hash functions. Even though we expect their implementation to be somewhat efficient,
their size could still end up being prohibitive. To mitigate this, we propose to precompute a subtree
of the binary tree generating the elements of D, committing it to a Merkle tree using any collision
resistant hash function which admits an efficient Small Script implementation4 .
More concretely, we propose to commit the first u layers of the binary tree of D into a Merkle
tree root which is hardcoded into the covenant script. Then, generating an element of D will require
decommiting the u-th layer from the Merkle tree, followed by log2 |D| − u computations of either SHA1
or RIPEMD in Small Script. An illustration of our approach is given in Figure 3.
While the above technique requires a globally one time precomputation of size 2u , the savings in
Small Script cost are significant. Computing each layer of the binary tree of D incurs the cost of both
SHA1 and RIPEMD, due to how Bitcoin script length is measured. Here, for the first u layers, we
instead reduce the cost per layer to a single hash function computation. To instantiate our scheme,
we choose BLAKE3, which has an efficient Small Script implementation [5] of ∼ 45K opcodes.
Finally, we use a quaternary Merkle tree (radix 4), as opposed to the binary tree used to generate
the elements of D, thus obtaining further savings, as even fewer BLAKE3 evaluations are then required.
4 This change applies only to the Small Script generation of D’s elements. In Big Script, we still use OP SHA1 and

OP RIPEMD160 to generate D’s elements.

5
 Transaction Transaction

Figure 4: Sufficiently powerful covenants, such as the ones enabled through OP CAT, lend themselves
to general smart contract designs on Bitcoin [24]. In this example, a locking script (visualized as a
lock) can enforce that: (i) it can only be spent by a transaction with the same format and locking
script – providing logic persistence on-chain; and (ii) the state transition from st to st+1 , was attested
by π to be a valid state transition – providing state or data persistence on-chain. Our covenant also
enables this kind of simple smart contract design.

1.2 Related Work

In the following, we briefly survey related work on Bitcoin covenants, including research related to
OP CAT and BitVM. In addition, we mention research into hash functions, together with work on their
Small Script implementation, which is relevant to our work.

Covenants. Covenants were first proposed on the Bitcoin-talk forum in 2013 [32]. [33] provided a
comprehensive treatment of covenants in an academic paper and launched a long line of research [6,
47, 46, 22]. There have been several proposed upgrades to Bitcoin that would introduce covenants
including: OP PUSHTXDATA [27], OP CTV (BIP-119) [40], OP VAULT (BIP-345) [34], and OP TXHASH and
OP CHECKTXHASHVERIFY [38].
A less direct path to having covenants on Bitcoin involves re-enabling previously disabled Bitcoin
opcodes, which indirectly yield covenants. An example of this is OP CAT [18] which using the Schnorr
trick [35, 36] allows for covenants. Another example is the “Great Script Restoration” (GSR) [41].
GSR calls to re-enable OP CAT together with other useful, previously disabled, opcodes such as OP MUL,
enabling not only covenants but also a more expressive on-chain logic for Bitcoin.

OP CAT. Research into the power of Bitcoin script with OP CAT has been a very fruitful direction. It
has been demonstrated that OP CAT is sufficiently powerful to almost arbitrarily constrain the spending
transaction. In particular, this technique is sufficiently powerful to force having the same locking
script and retaining state across multiple transactions. OP CAT-based stateful computation, as seen in
Figure 4, has been successfully implemented and referred to by multiple names, such as “state caboose”
[8], “recursive covenants” [44], and “finite state machine” [48], among others.
Moreover, OP CAT in particular has been identified as very advantageous for scaling computation
on Bitcoin, via STARK-based proof systems, such as [16], which lend themselves to an efficient verifier
implementation in an OP CAT-enabled Bitcoin Script [3].

The BitVM paradigm. This is a proposal by Linus [30] to obtain stateful computation on Bit-
coin without requiring support for “true covenants” by instead utilizing presigned transactions. This
technique achieves stateful computation in the following way:

• Data persistence - This is achieved via Lamport signatures, through an anti-equivocation

mechanism. Essentially, the operator commits to partial values of some encoding of the program
execution through Lamport signatures. These partial values are effectively stored in a global
key-value store, which provides a form of persistent data storage, as these values can be accessed
from any Bitcoin script (or any other blockchain, for that matter). Because of the equivocation
mechanism, it is a fraud proof-based system, with some “slashing” enacted on the operator in
case of equivocation to disincentivise fraudulent execution.

6
 • Logic persistence - This is achieved through the predefined validators presigning multiple
transactions which follow a certain template. Then, during runtime, the operators commit to
the inputs and partial values of computation. Hence, participants are guaranteed that the others
have no way to spend the locked funds in a way that can break the intended logical flow. As
pointed out by [28], this is related to the concept of connectors introduced in the Ark protocol [1].
The requirement for all n validators to sign template transactions is the source of the 1-out-of-n
honesty assumption in the BitVM protocol.
BitVM was originally presented in a two-party setting with an operator and a verifier but has since
been extended into multiple protocol variants with multiple predefined operators and multiple verifiers.
Unlike the original BitVM proposal which uses NAND-gate circuits, BitVM1 and BitVMX [28] work
by fraud proving on-chain the execution of a virtual CPU to m predefined verifiers. In contrast,
BitVM2 [31] uses a different design, and allows any onlooker to act permissionlessly as a verifier
in case of fraudulent execution, which yields an improved security guarantee. Unlike BitVM1 and
BitVMX, BitVM2 requires a different protocol for each circuit, and thus BitVM2 directly considers
fraud proving the execution of a proof system verifier, which can remain the same while executing
different (provable) programs. Hence, BitVM1 and BitVMX provide potentially cheaper operator
off-chain costs via direct CPU execution, while BitVM2 yields a stronger security guarantee.
BitVM2 in particular has given rise to multiple new scaling solutions for Bitcoin. For a compre-
hensive list of Bitcoin layer 2s, consult the Bitcoin Layers website [2]. For an overview and background
on BitVM and its variants, we refer to [37, 28] and references therein.

Covenants without a soft fork. There are proposals to bring covenants into Bitcoin without a soft
fork, such as [39, 25]. However, these require heavy cryptographic tools such as Functional Encryption
[7]. Our work only involves finding collisions in 160-bit hash functions.

Hash functions and collisions. Both for our construction and security analysis, we rely on ana-
lyzing the effectiveness of finding collisions in hash functions. For our covenant construction, we use a
parallel collision finding algorithm based on distinguished points, in similar vein to [49]. Our algorithm
exhibits a time-memory trade-off [19], improving upon which is an important future research direction.
For our security, we rely on hardness of finding a 3-way collision in ideal hash functions. This is
in spite of SHA1 having nontrivial collision attacks [45, 29], and, in general, finding 3-way collision
sometimes being as easy as finding a regular collision [21]. Nevertheless, the adversary is required to
supply short inputs in our setting, so we believe our assumptions to hold.
The most expensive aspect of our construction is the ∼ 280 off-chain compute cost. We expect
possible improvements can come from two directions:
• Non-trivial collision attacks on SHA1 (or RIPEMD), which will lower our covenant off-chain cost
(while still keeping finding 3-way collisions infeasible).
• Precomputation methods to reduce the off-chain per-spend cost of the covenant5 . This is not
trivial because we find collisions of the form f (π) = gtx (ρ), where f is always the same hash
function, while gtx depends on the transaction data (hence only known during runtime).
Finally, a major component in our scheme is the computation of Merkle trees. While we use the
standard construction, the improvements shown in [13, 12] could be useful to gain more efficiency in
our setting.

Small Script implementation. We base our construction on the implementation of hash functions
in Small Script. The BitVM project [4] has compiled a large library of nontrivial Small Script compu-
tations, including BLAKE3 and SHA256 [20, 14]. Our construction also relies on implementations for
SHA1 and RIPEMD, which, as the writing of this paper, don’t exist yet.
[9, 10] design a small integer multiplication system for Bitcoin’s Small Script, while [54] design a
large integer multiplication system.
Another possibly relevant work in this domain is that of evaluating Lamport signatures in pre-
taproot scripts [17].
5 In our construction, we only use precomputation to reduce the Small Script cost of our covenant. Performing

precomputation to also reduce off-chain compute cost can be very useful.

7
2 Preliminaries
2.1 Notation
Elliptic curve arithmetic. We’ll use capital Latin letters to denote points on Bitcoin’s elliptic
curve, secp256k1. We’ll also denote by aB the multiplication of a secp256k1 point B by a scalar a

Bitwise operations. ∥x∥ denotes the size of a value in bits. We use the following notation for
bitwise manipulation: By x | a , we denote the bit at the index a in x. Extending this notation to
b
ranges, x | a denote the bit string in x that starts at position a and continues to position b (inclusive).
To represent the concatenation of x to y we write x∥y.
S32
Bitcoin script. We denote by S = i=0 {0, 1}i the set of Small Script elements, and by B =
S4160 i
i=0 {0, 1} the set of Big Script elements. Observe that S ⊂ B. We’ll usually use lowercase Greek
letters to for elements of S, such as σ ∈ S, and lowercase Latin letters for elements of B (which may
also lie in S). For elements v ∈ B, we’ll denote their encoding as arrays of k-bit elements by ⟨v⟩k ,
where common choices will be k = 1 (boolean array) and k = 32 (so ⟨v⟩32 ∈ S ∗ ). We refer to ⟨v⟩32 as
the small-script representation of v.
We refer to the set of Script opcodes whose allowable inputs all lie in S as “Small Script opcodes”,
and all others as “Big Script opcodes”. In addition, we’ll denote by FuncS = {fS : S ∗ → S ∗ } the set of
functions implementable using exclusively Small Script opcodes, and by FuncB = {fB : B ∗ → B ∗ } the
set of functions implementable using exclusively Big Script opcodes6 . In addition, we’ll use X = {0, 1}∗
to denote the domain of functions implementable by off-chain algorithms (for instance, on an x86
processor).
Furthermore, we will abuse notation, and not distinguish between fS and the Small Script imple-
menting it, with the right notion being clear from context. Similarly, for gB , we’ll associate it with its
Big Script implementation. Moreover, we’ll write ∥fS ∥ to refer to the length of the script.
Since Small Script can express any computation, in particular for any fB ∈ FuncB there is fS ∈
FuncS such that for every b ∈ B it holds that ⟨fB (b)⟩32 = fS (⟨b⟩32 ). We refer to fS as the small-script
equivalent of fB 7 . If it were possible in Script to demonstrate equivalence of an element b ∈ B and
⟨b⟩32 ∈ S ∗ , this would allow us to do arbitrary computations on elements b of Big Script, by using
Small Script opcodes on ⟨b⟩32 .

Algorithm notation. Our algorithms may run in four different settings. To distinguish between
these settings, we attach a subscript to the algorithm name. If the algorithm runs off-chain, we simply
denote it as Algorithm, without subscript. When an algorithm is specifically intended to run in Big
Script, we attach a subscript to its name as AlgorithmB . Similarly, if it is intended to run in Small
Script, we denote it as AlgorithmS . Finally, we’ll use AlgorithmsS,B to denote algorithms implementable
in Bitcoin script, using all available opcodes.
For algorithms with binary output {0, 1}, we’ll sometimes write “success” or “accept” when referring
to the value 1, and, similarly, we’ll replace 0 by “fail” or “reject”.

2.2 Bitcoin overview

2.2.1 UTXO model
The Bitcoin blockchain consists of a series of blocks, each of which are a series of transactions, each
of which atomically creates and destroys a set of unspent transaction outputs (UTXOs). UTXOs
consist of a scriptPubKey (also known as a locking script), which is described below, and an integer
amount measured in satoshis, which are 10−8 BTC. The UTXOs that a transaction creates are called
(transaction) outputs while those that it destroys are called (transaction) inputs. Inputs refer to
the outputs of previous transactions, identifying them by the transaction identifier (TXID) and an
index within the list of that transaction’s outputs. To be accepted by the network, the total value
6 In Section 2.2.3 we give explicit definitions of Small Script and Big Script opcodes, and we provide a full list of all

opcodes in Appendix A. Also, while we defined FuncS and FuncB as function families implementable via a subset of
available opcodes, an actual Bitcoin script could compute both.
7 In fact, any function f : X → {0, 1}∗ has a small-script equivalent f .
S

8
 Transaction 1

1₿ 0.3 ₿
Transaction 3

0.6 ₿
0.6₿ 0.3 ₿
Transaction 2

0.1₿ 0.2 ₿
0.4 ₿ 0.1 ₿
0.1 ₿
Figure 5: Transactions in the UTXO model. Transaction 3 spends UTXOs from Transactions 1 and
2 using witnesses x1 and x2 , respectively, given to their respective locking scripts (scriptPubKey). The
UTXOs after the creation of Transaction 3 are highlighted in blue.

of a transaction’s outputs must be less than or equal to the total value of its inputs. The difference
between the two is the network fee, which is effectively transferred to the creator of the block which
includes the transaction.
There is one special kind of input called a coinbase input, which is allowed to exist in the first
transaction of a block. The coinbase input implicitly has a value equal to the total of the network fee
of all transactions in the block, plus a block subsidy, currently equal to 3.125 BTC, which is how coins
are initially introduced into the network. If the first transaction in the block itself has a network fee,
i.e. the block creator does not claim the total available amount, the excess is destroyed.
This model of transactions, in which UTXOs are atomically created and destroyed by transactions,
is termed the UTXO model. The state of the Bitcoin network consists entirely of its the set of UTXOs,
with the blockchain serving as a transcript of the transactions that led to this state. An illustration
of the UTXO model is given in Figure 5.
It differs from the account model, in which coins are distributed among labeled accounts with
variable balances. In the account model, transactions increase and decrease accounts. Individual
transactions typically debit a single account and may credit multiple accounts. Here the state of the
network consists of the total balance on all accounts. The most notable example of the account model
is the Ethereum network, whose state additionally includes a global key-value store used to implement
a “smart contracting” system.
Unlike the account model, in which transactions may be arbitrarily reordered prior to an inclusion
in a block (subject to the constraint that no account balance goes below zero), in the UTXO model
transactions that manipulate “the same coins” have a strict ordering. Transactions which spend
UTXOs must come after the transactions which created them, and because UTXOs are labelled by
TXIDs, any change to an earlier transaction in the chain will invalidate a later transaction. The UTXO
model is simpler and more efficient to implement, and makes atomicity easier to reason about, while
generally being more complex to use for multi-transaction protocols.

2.2.2 Locking scripts

Above we described a UTXO as a pair of an amount and a scriptPubKey, or “script public key”. A
scriptPubKey is a locking script for a UTXO. Every input in a transaction must provide a witness for
the scriptPubKey in its UTXO, which consists of an initial stack of input data for which the script
accepts. The script is defined in an opcode language called Bitcoin Script and is evaluated by a script
interpreter implemented in every validating node on the network. Formally, we write

LockingScriptS,B (w; tx) → {0, 1}

9
where w represents the witness and tx the spending transaction which spends the UTXO. Technically,
the interpreter may abort rather than returning either value, but our purposes an abort is equivalent
to returning the value 0 (in both cases the spending transaction is disallowed by the network). We
will therefore ignore this possibility to keep our notation simple.
Bitcoin Script is a stack-based language which is conceptually similar to Forth, and shares many of
its opcodes, while being more limited. In particular, Script has no looping facilities, hence its running
time is proportional to its length. It also has limited facilities for doing general computation.
Additionally, there are several resource limits which apply to Bitcoin Script: the stack may not
exceed 1000 elements at any point during execution; no stack element may exceed 520 bytes in size;
and the transaction itself (including all scripts) may not exceed 4 million “weight units”, where each
weight unit roughly corresponds to one opcode or one byte of explicit data.
The limitation of Script which is most salient to our purposes is that Bitcoin Script has very little
access to the transaction context. In Big Script, which contains only a small set of cryptographic
operations, we can validate digital signatures on transaction data; in Small Script we can do arbitrary
computations, but only with objects of size at most 4 bytes, and with no access to transaction data.

2.2.3 Big Script and Small Script

In this section, we overview the capabilities of Big Script versus Small Script. Explicitly, Big Script,
which can implement any function in FuncB , contains opcodes for
• Checking signatures on transaction data: OP CHECKSIG and its variants OP CHECKSIGVERIFY,
OP CHECKSIGADD (in Taproot) and OP CHECKMULTISIG (pre-Taproot).
• Computing SHA1, SHA256 and RIPEMD hashes of arbitrary data, and variants HASH160
(SHA256 followed by RIPEMD) and HASH256 (SHA256 composed with itself).
• Checking equality between two stack elements of arbitrary size: OP EQUAL.
• Determining the size, in bytes of any element: OP SIZE. This opcode provides a mapping from
Big Script elements to Small Script elements, but not a useful one because all signatures (and
all hashes, etc.) have the same size.
• Interpreting arbitrarily-sized elements as booleans, with all-bits-zero elements being false and all
other values being true 8 . Such booleans are used by the OP IF opcode and its variants, which
enable branching.
As with OP SIZE, the branching opcodes provide a mapping from Big Script into Small Script,
but not a useful one, because the set of elements which evaluate to false is very small and does
not overlap with any valid signatures or public keys.
Here the term “arbitrary” refers to stack elements of byte-length 0 up to 520. In practice, we never
need to manipulate objects larger than 65 bytes long, so this upper limit is irrelevant to us.
Meanwhile, Small Script, which can implement any function in FuncS , contains opcodes for
• Adding and subtracting 32-bit signed-magnitude integers, but notably not multiplying or dividing
them, as well as some other simple arithmetic;
• Numerical comparisons of such integers, as well as minimizing and maximizing, and variants;
• Equality checking via OP EQUAL, as in Big Script;
• Hash functions, the same as in Big Script, though the output of hash functions are not accessible
to Small Script;
• A limited form of transaction introspection in the form of the OP CHECKSEQUENCEVERIFY and
OP CHECKLOCKTIMEVERIFY opcodes, which do an inequality check between a 40-bit signed-magnitude
number and the sequence (resp. locktime) fields of a transaction. These fields affect the time
at which a transaction becomes valid, but not its semantics, making this particular form of
introspection useless for covenants.
8 More correctly, given a stack element of arbitrary size, if any bit is one except the first bit, then the element is

considered to be true. In particular, the empty string is false.

10
 Since the OP LESSTHANOREQUAL opcode is complete in the sense that any finite computation can
be expressed as a circuit of such operations, it is possible to express any computation in Small Script.
The extra opcodes such as addition allow us to do so more efficiently, but even so, a basic operation
such as 31-bit multiplication requires about 500 opcodes to implement [10].
A list of Big Script and Small Script opcodes can be found in Appendix A.

2.2.4 Schnorr signature messages

In Bitcoin, the Schnorr signature algorithm uses as a message a tagged hash applied to a serialization
of the spending transaction, specified in Bitcoin’s Taproot Schnorr signature standard [51, 52]. This
notion is of central importance to this work, as this tagged hash holds the necessary information to
perform transaction introspection and, consequently, covenants. In Definition 8 of Appendix B, we
give a full description of this function. Here, instead, we abstract it away using the following definition
Definition 1 (Schnorr sighash). We denote by SchnorrHashR,P : X → B the algorithm, parameterized
by two elliptic curve points R and P , which takes as input a transaction tx, serializes it, and hashes
it according to the description in Appendix B. Similarly, we will define by SchnorrHashR,PS the small
script equivalent, such that

SchnorrHashR,P
S (⟨tx⟩32 ) = ⟨SchnorrHash
R,P
(tx)⟩32 .

Whenever R and P are both equal the generator G, we’ll simply omit them and write SchnorrHash.

2.2.5 Tapleaf tragedy

In later sections, we will find ourselves writing scripts that need to index into very large lookup
tables. The natural way to do this is with a Merkle tree, which we will implement using BLAKE3
(see Section 5.2 for more information). However, implementing Merkle tree lookups directly in Script
is very expensive. A natural suggestion is to lever Taproot’s built-in Merkle tree lookup functionality.
More specifically, rather than having one script which commits to a the root of a Merkle tree and
uses witness data to index into the tree, we could instead have a large Taptree, each branch of which is
an individual script. The individual scripts would each commit to a single piece of data (or the root of
a sub-tree), and indexing would be done by simply choosing which Tapbranch to use in a given spend.
Unfortunately, such a trick will not work for our purposes, due to the way we construct our covenant.
Our construction requires the index (ω, t) of some dω,t ∈ D to be independent of the transaction’s
signature, to be able to utilize collision attacks on 160-bit hash functions. Using a Taptree eliminates
this possibility, as it, by definition, encodes information about (ω, t). A more formal discussion of this
point can be found in Remark 2.
We refer to this problem as the Tapleaf tragedy. If it were possible to bypass it,
the on-chain cost of our covenant would mostly vanish.

Instead of ∼ 4 million opcodes, the covenant logic cost would be less than a quarter of that, and
the expensive precomputation phase would not be required. This is because the vast majority of our
on-chain cost comes from generating elements from the set D in Small Script.
Finally, we make two observations about the tapleaf tragedy:

• If there was a sighash mode which did not commit to the Tapleaf, such as the proposed
SIGHASH ANYPREVOUTANYSCRIPT [11], the tragedy would not apply and we may be able to imple-
ment some forms of covenant this way.
• If we were not looking up the hash of a signature, but instead the hash of some other data, the
tragedy would not apply. This excludes any form of covenant functionality, since transaction
data is only available to Script through signatures, but it may still enable some interesting use
cases. See Appendix C for an example.

11
2.3 Hash functions
In this work, we will focus on the following hash functions:
1. SHA1 : X → {0, 1}160 ;
2. RIPEMD : X → {0, 1}160 ;

3. SHA256 : X → {0, 1}256 ;

4. BLAKE3 : X → {0, 1}256 .
Below, we list the properties these hash functions have, that are important for our constructions.

Big Script. SHA1 and RIPEMD are available as opcodes in Big Script, while BLAKE3 is not.
SHA256, HASH160, and HASH256 are also available as opcodes, but we don’t utilize them to generate
the set D, as they all depend on a Small Script implementation of SHA256, which is costly.

Small Script. Small Script implementations for BLAKE3 and SHA256 implementations are avail-
able in BitVM’s repository, requiring, for a single block input of 512 bit, ∼ 45K and ∼ 296K opcodes [5],
respectively9 . Recently, the SHA256 script was improved by Tomer Giladi [14] in two key ways:
• The Small Script cost was reduced to just ∼ 211K opcodes;
• The stack size usage was reduced from 979 elements (out of the 1000 total limit of Bitcoin), to
just 732 elements, which is much more workable.
In contrast to the above, SHA1 and RIPEMD don’t have a Small Script implementation as of the
writing of this paper. Nevertheless, we believe that an efficient implementation of them is possible, so
we make the following conjecture:
Conjecture 1. SHA1 and RIPEMD are implementable in Small Script. For a single block input of
320 bit, the former requires ∼ 70k opcodes, while the latter requires ∼ 90k opcodes.

Security model. For simplicity of analysis, we consider all aforementioned hash functions as ideal
random functions, namely we work in the random oracle model. For some of them, SHA1 in particular,
there are non-trivial 2-way collision attacks [45]. Moreover, [21] showed that sometimes finding an n-
way collision is not even harder than finding 2-way collisions. Nevertheless, all of these attacks require
long inputs. Here, in contrast, the adversary is only ever allowed to supply short inputs, at the length
of at most a few blocks, so these attacks do not apply. Hence, the best possible attacks on hash
functions in our model follow the birthday bound:
Fact 1. Let f : X → {0, 1}m be a random function. Given an oracle access to f :
• Finding distinct x0 , x1 such that f (x0 ) = f (x1 ) requires on average Θ(2m/2 ) queries to f ;
• Finding distinct x0 , x1 , x2 such that f (x0 ) = f (x1 ) = f (x2 ) requires on average Θ(22m/3 ) queries
to f .

2.4 Transaction grinding and the Schnorr trick

In similar fashion to the Schnorr trick [35, 36], in this work we’ll be interested in grinding transaction
data until the transaction hash satisfies certain conditions. In the following, we define a function
TxGrind, which is able to alter some data in a transaction while keeping its semantic meaning intact.
Definition 2 (Transaction grinding). Let TxGrind(tx, ρ) be a function with input transaction data
tx ∈ B and random data ρ ∈ S ∗ , that always outputs transactions tx′ that are equivalent to tx, but
tx′ also embeds the data ρ inside it in some unimportant data field.
9 Unfortunately, we cannot completely avoid computing SHA256 in Small Script, as SchnorrHash, which is required

for transaction introspection, depends on it.

12
Example 1. An example TxGrind could be embedding the data ρ inside the nLockTime field. Alter-
natively, we can put it in an OP RETURN script in an additional output.
Next, we move on to describing the Schnorr trick, beginning by outlining the OP CHECKSIG opcode
for Taproot.
Definition 3. Let SchnorrCheckSigB : B × B → {0, 1} be the OP CHECKSIG opcode for Taproot, as
defined in Definition 7 of Appendix B, via the following formula
(
1, sG = R + HashBIP0340/challenge (R∥P ∥MsgHash(tx))P,
SchnorrCheckSigB (R∥s, P ) =
0, otherwise

where tx is the spending transaction.

The significance of the Schnorr trick lies in it being a way to force the spender to provide a slightly-
altered, hashed form of tx as part of a signature provided as input to the locking script. These slight
alterations can be undone and the transaction data pulled apart. We outline how this is done below.

Schnorr trick stage I. The locking script asks the spender to provide

s = SchnorrHash(tx) = HashBIP0340/challenge (G∥G∥MsgHash(tx)) + 1,

the authenticity of which it can check by running SchnorrCheckSigB (G∥s, G), i.e., by validating a
signature where both the public key P and nonce R are equal to the generator G.
Note that in Big Script there is no way to check that indeed R = G, without a special opcode such
as OP CAT. Nevertheless, since we can show small-to-big equivalence, we can just check that R = G is
enforced in Small Script.

Schnorr trick stage II. As SchnorrHash outputs a B element, it is not possible to get from s to
s − 1 or vice versa. In the original OP CAT-based Schnorr trick, this was dealt with using an additional
invocation of OP CAT along with the Small Script opcode OP 1ADD. However, since in this work we can
show small-to-big equivalence, we’ll implement OP 1ADDS which increments a 256-bit input by 1. More
formally,
OP 1ADDS (⟨x⟩32 ) = ⟨x + 1⟩32 .
This is sufficient to bridge the gap from s (which appears in the above signature signature) to s − 1
(which is a hash of our transaction data). Below we argue that this operation is efficient.
Fact 2. For OP 1ADDS on an 256-bit input it holds that ∥OP 1ADDS ∥ ≤ 400.
Remark 1. Since the OP CAT-based Schnorr trick uses OP SHA256 in Big Script, it is limited to trans-
actions whose serialized size is at most 520 bytes, which is the maximum size of a single stack element.
In contrast, we compute SHA256 in Small Script; hence, in our case, the bottleneck is instead the
Small Script cost of evaluating SHA256 on the serialized transaction.

3 Equivalence check in Bitcoin

In this section we define the Bitcoin equivalence check, a notion that is the main focus of this work.
Later, we show how to construct a covenant given a construction for such an equivalence check.
The definition we end up with is somewhat involved, the reason being that we’re not able to prove
the equivalence of any arbitrary signature s and its small-script representation ⟨s⟩32 directly. Instead,
we need to grind our transaction until we’re able to find a semantically equivalent transaction whose
Schnorr signature’s small-to-big equivalence we can prove.
More concretely, we’ll use an off-chain algorithm Prove which will simultaneously find the following:
• Randomness ρ, such that the spending transaction tx is grinded with this randomness, obtaining
a semantically equivalent transaction tx = tx(ρ);
• π = (ω, t) such that the element dω,t ∈ D collides (over SHA1) with the signature s of tx(ρ).

13
 Honest
Adversary
Spender
1. Run ) to get 1. Let , and some
2. Compute signature of witness
3. Output 2. Output

Locking Locking
Script Script
1. Run 1. Run
2. Run 2. Run

ACCEPT REJECT

Figure 6: (Left) Equivalence check in the honest spender case. After running Prove, the spender can
convince the locking script that a transaction’s signatures are equivalent. (Right) Equivalence check
in the malicious case. An adversary shouldn’t be able to find signatures s1 ̸= s2 whose equivalence
they can prove via some witness π.

Once we find such ρ and π by running Prove, as spenders, we’ll provide π to the locking script, together
with signatures of tx(ρ), namely s and ⟨s⟩32 . Then, to check the equivalence of the provided signatures
s and ⟨s⟩32 , the locking script will run CheckB and CheckS , which, using π, will check their collision
with dπ in Big Script and Small Script, respectively, as was described in our equivalence check template
from Section 1.1. In Figure 6 we illustrate this process, and, below, we formally define it.
Definition 4. A Bitcoin equivalence check is a tuple of algorithms Π = (Prove, CheckB , CheckS ),
relative to a transaction grinder TxGrind, with the following syntax:
• Prove(tx) → (ρ, π): On input transaction tx, the algorithm outputs randomness ρ ∈ X and a
witness π ∈ S ∗ .
• CheckB (R||s, π) → {0, 1}: On input s ∈ {0, 1}256 , elliptic curve point R, and witness π, the
algorithm either accepts (outputs 1) or rejects (outputs 0).
• CheckS (⟨R||s⟩32 , π) → {0, 1}: On input ⟨R||s⟩32 , where s ∈ {0, 1}256 and R is an elliptic curve
point, and witness π, the algorithm either accepts (outputs 1) or rejects (outputs 0).
We require Π to satisfy the following properties:
• Completeness:10 For any transaction tx, if (ρ, π) ← Prove(tx), then

Pr [CheckB (G||stx,ρ , π) = CheckS (⟨G||stx,ρ ⟩32 , π) = 1] ≥ 1/2,

where stx,ρ = SchnorrHash(TxGrind(tx, ρ)) + 1.

• Soundness: We say Π is (S, T, ϵ)-sound if for any adversary A bounded by time T and space S
it holds that
R′ ||s′ ̸= R||stx
 

Pr  and (tx, R, R′ , s′ , π) ← A ≤ ϵ,
′ ′
CheckB (R ||s , π) = CheckS (⟨R||stx ⟩32 , π) = 1

where stx = SchnorrHashR,G (tx) + 1.

Efficiency. In this work, we’ll be interested in the efficiency of Π = (Prove, CheckB , CheckS ). The
time complexity of Prove will be measured by total hash function evaluations, and the space complexity
will be measured by the number of memory bytes required. The efficiency of CheckB , CheckS will be
measured by how many Bitcoin opcodes and stack spaces are required for execution.
10 For simplicity of analysis we choose ≥ 1/2 as the completeness probability threshold. By running Prove multiple

times, this can be extended to ≥ 1 − ϵ with a multiplicative overhead of log(1/ϵ) to the spender’s time complexity.

14
3.1 A Tapscript covenant
By default, a Bitcoin locking script, LockingScriptS,B (w; tx), does not depend on tx, with the exception
of timelock opcodes. However, in this work, we’ll construct a covenant using a Taproot script, allowing
the locking script to enforce conditions on the spending transaction tx.
To define a covenant, first, we need to define how it chooses a transaction to accept or reject. We’ll
abstract it a way using a predicate P, such that P(tx) = 1 means the transaction tx is accepted by the
covenant, and P(tx) = 0 means it is rejected.
As before, here, our full-fledged definition will be somewhat involved. This is because, similar to
the Schnorr trick [35, 36] covenant, as spenders, we’re not able to provide the covenant locking script
with an arbitrary valid transaction. Instead, we need to choose a desired valid transaction and grind
semantically equivalent transactions, until we find one which the covenant will accept. Below, we call
this grinding algorithm Offchain, and unlike the OP CAT-based construction, Offchain in our construction
will need to do quite a bit of work (in particular, it will compute Prove from our equivalence check).
Indeed, the definition we give below can also be applied to capture the OP CAT-based covenant.
Definition 5. Let PS be a predicate over transactions such that, for the transaction grinder TxGrind,
it holds that for all ρ and tx,
PS (tx) = 1 ⇒ PS (TxGrind(tx, ρ)) = 1.
A covenant, relative to TxGrind and PS , is a tuple of algorithms Σ = (LockingScriptS,B , Offchain) with
the following syntax:
• LockingScriptS,B (w; tx) → {0, 1}: On input witness w ∈ B ∗ , and being spent by a transaction tx,
the locking script either accepts (outputs 1) or rejects (outputs 0).
• Offchain(tx) → (w, ρ): On input transaction tx, output witness w and randomness ρ.
The algorithms of Σ should satisfy the following requirements:
• Completeness: If PS (tx) = 1 and (w, ρ) ← Offchain(tx), then
 
Pr LockingScriptS,B (w; TxGrind(tx, ρ)) = 1 ≥ 1/2

• Soundness: We say Σ is (S, T, ϵ)-sound if for any adversary A bounded by time T and space S
it holds that
Pr PS (tx∗ ) = 0 and LockingScriptS,B (w∗ ; tx∗ ) = 1 (w∗ , tx∗ ) ← A ≤ ϵ
 

In Algorithm 1 we provide pseudocode for performing a covenant in Bitcoin Tapscript.

Proposition 2. Let Π be a Bitcoin equivalence check with (S, T, ϵ) soundness. Then, Σ from Algo-
rithm 1 is a covenant with (S ′ , T ′ , ϵ′ ) soundness, where S ≈ S ′ , T ≈ T ′ , and |ϵ − ϵ′ | is bounded by the
success probability of the adversary to find a collision for SHA25611 .
Proof. We argue correctness and soundness separately.

Correctness: Let tx be a transaction such that PS (tx) = 1. Since (ρ, π) ← Π.Prove(tx), by Π’s
completeness it holds, with probability at least 1/2, that
Π.CheckB (G||stx,ρ , π) = Π.CheckS (⟨G||stx,ρ ⟩32 , π) = 1,
where stx,ρ = SchnorrHash(TxGrind(tx, ρ)) + 1. Hence, since R1 = R2 = G, steps 1–4 don’t fail.
Moreover, by the definition of SchnorrCheckSigB , steps 5–6 don’t fail. Finally, by assumption on tx,
PS (TxGrind(tx, ρ)) = 1, so step 7 doesn’t fail.

Soundness: Let A be an adversary that wins the security game of Σ with probability ϵ, requiring S
space and T time. In other words, by step 1, A outputs w∗ = (⟨tx⟩32 , π, R1 ||s1 , ⟨R2 ||s2 ⟩32 ) and tx∗
such that
Pr PS (tx∗ ) = 0 and LockingScriptS,B (w∗ ; tx∗ ) = 1 = ϵ.
 

Denote the event when the above happens by E. We’ll build an adversary A′ to break Π with roughly
the same probability. A′ , which has space and time complexity similar to A, does the following:
11 In the random oracle model, for an adversary doing at most T ′ queries to SHA256, this is approximately (T ′2 )/2257 .

15
Algorithm 1 A Bitcoin covenant for a spending transaction tx that uses our equivalence check.

Notation: Let Π be a Bitcoin equivalence check relative to TxGrind.

Offchain(tx) :

1. Let (π, ρ) ← Π.Prove(tx)

2. Let s = SchnorrHash(TxGrind(tx, ρ)) + 1
3. Output witness (⟨TxGrind(tx, ρ)⟩32 , π, G||s, ⟨G||s⟩32 ) and randomness ρ
LockingScriptS,B (⟨tx⟩32 , π, R1 ||s1 , ⟨R2 ||s2 ⟩32 ; spender tx):

1. If the witness does not have the correct format (number of elements and their length): return
Fail
2. If Π.CheckB (R1 ||s1 , π) ̸= 1: return Fail
3. If Π.CheckS (⟨R2 ||s2 ⟩32 , π) ̸= 1: return Fail

4. If ⟨R2 ⟩32 ̸= ⟨G⟩32 : return Fail

5. If SchnorrCheckSigB (R1 ||s1 , G) ̸= 1: return Fail
6. If SchnorrHashS (⟨tx⟩32 ) + 1 ̸= ⟨s2 ⟩32 : return Fail

7. If PS (⟨tx⟩32 ) ̸= 1: return Fail ▷ Inspect the data of ⟨tx⟩32 according to covenant requirements
8. Return Success

1. Execute A to receive w∗ = (⟨tx⟩32 , π, R1 ||s1 , ⟨R2 ||s2 ⟩32 ) and tx∗ .

2. Return (tx, R2 , R1 , s1 , π).
We claim that
 
R1 ||s1 =
̸ R2 ||stx
Pr  and E  ≥ 1 − ϵSHA256 ,
CheckB (R1 ||s1 , π) = CheckS (⟨R2 ||stx ⟩32 , π) = 1

where stx = SchnorrHashR2 ,G (tx) + 1 and ϵSHA256 is the success probability of the adversary to find a
collision for SHA256. Since we’re in event E, the negation of steps 1–7 holds. In particular, because of
steps 1–2, it is sufficient to show that R1 ||s1 ̸= R2 ||stx with high probability to break the soundness
of Π. By step 6, we know that s2 = stx . Moreover, by step 5, it holds that if R1 = kG then

s1 = k + SchnorrHashkG,G (tx∗ ).

If k ̸= 1, by step 4, it holds that R1 ̸= R2 and our claim follows. Suppose then, instead, that k = 1.
Hence, for s1 = s2 to hold it must be that

SchnorrHash(tx) = SchnorrHash(tx∗ ).

However, by step 7 we deduce that tx ̸= tx∗ as they evaluate to different values of PS . Thus, by the
security of SHA256, the probability an adversary can find such tx, tx∗ is at most ϵSHA256 . Taking the
negation, with probability at least 1 − ϵSHA256 we have that R1 ||s1 ̸= R2 ||stx , breaking the soundness
of Π, as required.

12 Checking element length can be done with OP SIZE.

16
Remark 2 (Tapleaf tragedy). The difficulty of using Taproot’s built-in Merkle tree lookup functional-
ity, which can potentially provide significant bitcoin script savings, lies in the difficulty of implementing
Prove for the equivalence check in this setting. As long as the transaction, tx, does not depend on π,
Prove in our construction is essentially looking for a pair (π, ρ) that satisfies an equality of the form
f (π) = gtx (ρ), where f, gtx : B → {0, 1}160 behave like hash functions. This is solvable via collision
finding algorithms, which we utilize. However, when using Taproot’s Merkle tree functionality, the
transaction description becomes dependent on π, tx = tx(π). This requires a solution of the form
f (π) = gtx (ρ, π), which is no longer amenable to collision finding attacks.

4 Realizing Bitcoin equivalence tester sets

In this section we formalize the notion of a set D from the introduction, which will be useful for our
equivalence check.
Definition 6. A set D = {dω,t ∈ B}ω∈S,t∈B is a Bitcoin equivalence tester set 12 if it satisfies that
• the mapping (ω, ⟨t⟩1 ) 7→ dω,t is in FuncB , whose implementation we’ll denote by [Link] ,

• the mapping (ω, ⟨t⟩1 ) 7→ ⟨dω,t ⟩32 is in FuncS , whose implementation we’ll denote by [Link] .
We’ll also denote by just [Link] the off-chain computation of dω,t .
Next, we move on to constructing a Bitcoin equivalence tester set, taking inspiration from the
GGM pseudorandom function construction [15]. The reason for such a construction is that SHA1 and
RIPEMD are the only hash functions that simultaneously (a) exist as opcodes in Big Script and (b)
we expect them to have a reasonable Small Script implementation cost.

Algorithm 2 Bitcoin equivalence tester set D

GenB (ω, ⟨t⟩1 ):
1. Let d ← ω
2. For each ti compute
(
SHA1B (d), ti = 0
• d←
RIPEMDB (d), ti = 1

3. Return d
GenS (ω, ⟨t⟩1 ):
1. Let δ ← ω

2. For each ti compute

(
SHA1S (δ), ti = 0
• δ←
RIPEMDS (δ), ti = 1

3. Return δ

Proposition 3. Algorthim 2 is a Bitcoin equivalence tester set D such that

• Evaluating [Link] requires at most ||t|| hash opcodes;
• Assuming Conjecture 1, evaluating [Link] requires at most ∼ 160, 000 · ||t|| opcodes;
12 Even though we write ω ∈ S, in our actual construction we will be able to utilize ||ω|| = 33, which is no longer a Small

Script element. This is because, while 33-bit elements are not directly readable in Small Script, they can nevertheless
be generated via OP ADD and other arithmetic opcodes, as these are allowed to output values with a carry.

17
 Collision1 Detected! Collision2 Detected!
Run1 and Run2 hit DP2 Run1 and Run3 hit DP3
DP1 DP2 DP3

g g g f g g f g g f g g g
f ...
Run1

DP4 f
g g g f g Collision1 Collision2
f
Run2
g
DP5 DP6

f g g f g g f f g g f
Run3

2z hashes between DPs

Figure 7: An example execution of our parallel collision algorithm. The circles are 160-bit hash values
ρ, the values that we store as distinguished points we denote with DPi . The lines represent a query to
either f or g. Collisions are detected when two runs generate the same distinguished point. Collision1
is useless collision because the collision is between the same function f (x) = f (x′ ). Collision2 can be
used to spend a covenant because the collisions f (x) = g(x′ ).

• Suppose that ||ω|| = 33 and 35 ≤ ||t|| ≤ 75. Then, in the random oracle model,

|D| ≥ (1 − 2−15 )2||ω||+||t||

with probability at least 1 − 2−19 .

We prove Proposition 3 in Appendix D. In the following sections, for simplicity of analysis, we

assume that |D| = 2||ω||+||t|| exactly, as the deviations of |D| from this size are negligible.

5 Finding 160-bit collisions

Here we describe our algorithm for finding a collision between a signature and a value in D used in
our equivalence check. We pattern our algorithm on the parallel search distinguished points collision
finding approach from [49]. The main challenge we face in designing this algorithm is dealing with the
cost of pseudo-collisions that arise from the constraints on number of bits used for our input to [Link].
Our equivalence check requires finding a collision between two different 160-bit hash functions
f (x) = g(x′ ). By f (x) we denote the hash function that performs [Link]. By g(x) we denote the hash
function that hashes a Bitcoin signature on a spending transaction. We are only interested in collisions
of the form f (x) = g(x′ ). We refer to collisions of the form f (x) = f (x′ ) or g(x) = g(x′ ) as useless
collisions as we can’t use them in our covenants. We combine f and g into a single function h which
calls f if the input is prefixed with at least c zeros and calls g otherwise.
(
c
f(x), x | 0 = {0}c
h(x) = c
g(x), x | 0 ̸= {0}c

This parameter c allows us to adjust the probability of f (x) or g(x) being called on a random input
to h(x). Let’s look at these functions f (x) and g(x) in more detail:

||ω|| c+||ω||+||t||+1
f(x) : {0, 1}||w||+||t|| → {0, 1}160 , x 7→ [Link](x | c , x | c+||ω||+1 )
g(x) : {0, 1}160 → {0, 1}160 , x 7→ SHA1(G||(SchnorrHash(TxGrind(tx, x)) + 1))

18
Algorithm 3 Our algorithm for finding collisions needed for our Bitcoin equivalence check

Notation: Let D be the Bitcoin equivalence tester set from Algorithm 2. We write
c+||ω|| c+||ω||+||t||+1
f(x)= [Link](x | c , x | c+||ω||+1 )
g(x)= SHA1(G||(SchnorrHash(TxGrind(tx,
( x)) + 1))
c
f(x), x | 0 = {0}c
h(x)= c
g(x), x | 0 ̸= {0}c
where we denote the size of w by ||ω||, the size of t by ||t||, and the number of zeros to be a
distinguished point by z. Here, the variable c determines frequency of queries to f to g. At c = 0 they
are both called the an equal number of times, each time c is increased by one, the number of queries
to g doubles and the number of queries to f is reduced by half.

ProveRun(tx, DP):
1. Draw random ρ from S 5
2. Initialize empty prev values table: PT

3. [Link] ← ρ
4. y ← h(ρ)
160
5. While not (y | 160−z = {0}z and y ∈ DP): ▷ While no colliding DP found
• PT[y] ← ρ
160
• If y | 160−z = {0}z and y ∈
/ DP: ▷ New DP found
– DP[y] ← [Link]
– PT ← Empty
– [Link] ← ρ
• ρ←y
• y ← h(ρ)
6. y ′ ← DP[y]
7. While y ′ ∈
/ PT :

• ρ′ ← y ′
• y ′ ← h(ρ′ )
8. return ρ′ , PT[y ′ ] ▷ Collision Found
Prove(tx):

1. Initialize empty dist. point table: DP

2. While True: ▷ Loop can run in parallel
• x, x′ ← ProveRun(tx, DP)
c c
• If x | 0 = {0}c and x′ | 0 ̸= {0}c : ▷ Useful Collision
c+||ω|| c+||ω||+||t||+1 ′
– return π = (ω ← x |c ,t ← x | c+||ω||+1 ) and ρ ← x
c c
• If x |0 ̸= {0}c and x′ | 0 = {0}c : ▷ Useful Collision
′ c+||ω|| ′ c+||ω||+||t||+1
– return π = (ω ← x |c ,t ← x | c+||ω||+1 ) and ρ ← x

19
 The function f (x) maps the input value x to (ω, t) and then returns [Link](ω, t) as its output. To
keep the number of hash function calls low in our equivalence check we use a witness (ω, t) whose size
is less than 160-bits. To map an 160-bit input x to a ||ω|| + ||t|| < 160-bit input (ω, t) we truncate the
bits of x. This results in pseudo-collisions where x ̸= x′ but a collision because the difference between
x and x′ was removed by truncation. Inputs to f will necessarily start with c zero bits. Since these
bits will always be zero, we drop these c bits.
We will now walk through our collision finding algorithm shown in Figure 7. The algorithm starts r
parallel runs. Each run is seeded with a different random value ρ. And recursively calls h(ρ) supplying
the output from the last call as the input to the next hash function call:

h(. . . h(h(ρ)) . . . )
Each generated hash output is written to a hash table denoted, PT. This table, PT, is reset each
time the instance hits a distinguished point so that it doesn’t grow without bound. For our algorithm,
we define a distinguished point as an output that ends with at least z zero bits.
160
y | 160−z = {0}z

When an instance generates a distinguished point, it checks if the distinguished point already exists
in a table of distinguished points which we denote DP. What we do next depends on if the output
already in the distinguished points table or not.
If the output y does not exist in the distinguished points table, i.e., y ∈ / DP, we add y in the
Distinguished Points table using y as the key and [Link] as the value. The variable [Link] stores
the last distinguished point this run encountered or the initial random seed ρ it started from. We need
to set DP[y] ← [Link] so that if we hit this distinguished point again we can reconstruct the chain
of calls to h allowing us to find the exact set of inputs which generated the collision. After adding the
new distinguished point to the table we continue recursively calling h.
If on the other hand the output does exist in the distinguished points table, i.e., y ∈ DP, we have
detected that a collision occurred. To determine when the collision happened, we reconstructing the
chain until we find some output that collides with an output in the previous values table (PT) of the
current instance
h(. . . h(h(DP[y])) . . . )) ∈ PT
Once we have found this match, we have found the colliding inputs

x = h(. . . h(h(DP[y])) . . . )

x′ = PT[h(. . . h(h(DP[y])) . . . )]
h(x) = h(x′ )
We know that x ̸= x′ because the prior input in the chain would have been identified as the collision.
Once we have this collision we check if it is a useful f (x) = g(x′ ) collision. Remember that h
chooses whether to call f or g based if the input is prefixed by c zeros. Hence we can determine if we
have a useful collision by checking that one of the two returned input is prefixed by c zero bit and the
other input is not prefixed by c zero bits. That is, we have a useful collision when:
c c c c
(x | 0 = {0}c and x′ | 0 ̸= {0}c ) or (x | 0 ̸= {0}c and x′ | 0 = {0}c ).

If the collision found is a useless collision, we restart the instance with a new random seed. If we have
found a useful collision we stop our search return the colliding ρ and (ω, t):

[Link](ω, t) = SHA1(G||(SchnorrHash(TxGrind(tx, ρ)) + 1))

Algorithm 3 presents a collision finding technique, which will be part of our Bitcoin equivalence
check Π = (Prove, CheckB , CheckS ). The full construction is given in Algorithm 4, which, when com-
bined with Algorithm 1, yields a covenant for Bitcoin.
To summarize the discussion above, we deduce the following
Proposition 4. Π = (Prove, CheckB , CheckS ) as described in Algorithm 4, when instantiated with the
correct parameters (such that the success probability ≥ 1/2), satisfies the Completeness property of a
Bitcoin equivalence check.

20
Algorithm 4 Bitcoin equivalence check
Notation: Let D be the Bitcoin equivalence tester set from Algorithm 2.

Prove(tx):
1. Return the result of Prove(tx) from Algorithm 3.
CheckB (R||s, ω, ⟨t⟩1 ):
1. If the input does not have the correct format (number of elements and element length): return
Fail
2. Let d = [Link] (ω, ⟨t⟩1 )
3. Return Success if and only if SHA1B (d) = SHA1B (R||s).
CheckS (⟨R||s⟩32 , ω, ⟨t⟩1 ):

1. If the input does not have the correct format (number of elements and element length): return
Fail
2. Let δ = [Link] (ω, ⟨t⟩1 )
3. Return Success if and only if SHA1S (δ) = SHA1S (⟨R||s⟩32 ).

In regards to Algorithm 4, in the next sections, we’ll analyze the space and time complexity of
Π.Prove, followed by the Small Script cost of Π.CheckS . After this, we’ll instantiate Π with concrete
parameters and analyze its soundness.

5.1 Time and space cost

In this section we summarize the time and space of our collision finding algorithm, namely Π.Prove
from Algorithm 4. Appendix F provides the complete derivation of this analysis.
Our analysis depends on the following variables:

z: The number of zeros that identifies a point as a distinguished point.

qf : The number of unique queries to f is 2qf
qg: The number of unique queries to g is 2qg

where, for a given parameter c, it holds that qg − qf = c. Note that Prove in Algorithm 3 does not
have an explicit running time due to the “While True” in step 2. Instead, by choosing to terminate
the loop early and controlling the value c, it is possible to freely control the values qf and qg.
The probability of a useful collision i.e., a collision allows us to spend a covenant, is:
(qf +qg−160)
1 − e−2
(0)
Thus when qf +qg = 160 we have a greater than 1/2 probability of a useful collision because 1−e−2 ≈
0.632. As we will show next this does not tell us the total work we need to do. This is because not every
query to f or g is unique due to useless collisions i.e., collisions not useful for spending a covenant.

Useless collisions: Each time we hit a collision it takes us 2z−1 additional hash queries before we
reach a distinguished point in the distinguished point table. Then determining where the collision
occurred requires an additional 2z−1 work. Thus, each collision we encounter costs an additional
2z−1 + 2z−1 = 2z work. Most of the useless collisions we generate are pseudo-collisions i.e., collisions
that arise because we truncate the bits of the input inside of f . The expected number of f (x) = f (x′ )
collisions these including pseudo-collisions is:

22qf −||w||−||t||−1

21
As we don’t truncate the input in g, g does not generate any pseudo-collisions. The expected number
of g(x) = g(x′ ) useless collisions for 2qg queries to g as:

22qg−160−1

The total number of useless collisions is given by:

22qf −||w||−||t||−1 + 22qg−160−1

For a greater 1/2 probability of finding a useful collision, qf + qg ≥ 160 the expected work is:

2z × (22qf −||w||−||t||−1 + 22qg−160−1 )

Additional hash queries in f : Notice that f costs more hash queries than g because f contains
[Link] which performs one hash query per bit in t. We can count these additional queries by multiplying
by ||t||. For useless collisions:

22qf +log2 ||t||+z−||w||−||t||−1 + 22qg+z−160−1

For the number of unique queries:

2qf × ||t|| + 2qg = 2qf +log2 ||t|| + 2qg

Time cost: As we have a greater than 1/2 probability of finding a useful collision when qf +qg = 160,
we set qf + qg = 160 and define qg as a function of qg = 160 − qf giving us the total time cost of:

2qf +log2 ||t|| + 2160−qf + 22qf +log2 ||t||+z−||w||−||t||−1 + 22(160−qf )+z−160−1

Space cost: The space cost of our algorithm is simply storing our distinguished points table. We
define our distinguished points as an output which has at least z zero bits at the end. This means
that 2−z is probability of a query to the hash function producing a distinguished point and 2z is the
number of queries between two distinguished points. A naive approach would be for each row on the
distinguished point table to include the distinguished point (size 160/8 = 20 bytes), and the previous
distinguished point (or random seed of the run).
Observing the fact that distinguished points are added to the table as they are discovered, if we
group distinguished point by the run which discovered them the previous distinguished point will just
be the previous row in the table allowing us to reference it implicitly using only negligible space.
Since all distinguished points end in z we don’t need to store the z all zero bits. Thus a row in our
distinguished point table is (160 − z)/8 bytes. If the total number of unique queries we make is Q = 2q ,
then distinguished point table will have 2q−z rows and the table will use space 2q−z × (20 − z/8).
Each parallel run stores the table PT of the previous hash outputs. When a run hits a distinguished
point, that runs PT is reset to empty. The space need for PT is the number of parallel runs, r, times
the expected number of outputs between distinguished points 2z . This results in 20 × r × 2z space. We
employ a time space trade-off here by only storing every 2z/2 -th output in PT and then reconstruct
the matching region of the PT for an increase in 2z /2z/2 = 2z/2 time and r × 20 × 2z/2 space. This
value is small enough relative to the other values in time and space that we can ignore it.
Thus the total space cost is:

(20 − z/8) × (2qf −z + 2(160−qf )−z )

To summarize,
Proposition 5. Let qf, ||ω||, ||t||, z be positive integers such that qf ≤ 160 and ||ω|| + ||t|| ≤ 160.
Then, the total running time of Prove in Algorithm 4 is given by at most

2qf +log2 ||t|| + 2160−qf + 22qf +log2 ||t||+z−||w||−||t||−1 + 22(160−qf )+z−160−1

hash function evaluations and its total memory usage in bytes is given by

(20 − z/8) × (2qf −z + 2(160−qf )−z ).

22
 While Proposition 5 estimates the off-chain complexity of Prove, we are also interested in the Small
Script cost of CheckS . As it is, the cost is too prohibitive to fit into 4 million opcodes due to the
complexity of [Link] , as given in Proposition 3. In the following section, we improve the Small
Script cost of CheckS via precomputing part of [Link] and storing it in a Merkle tree, which can be
implemented using any hash function. We choose to use BLAKE3 due to its cheap Small Script cost.

5.2 Reducing Small Script costs with BLAKE3

The essential idea here is to replace many of hash function queries needed to compute [Link] in Small
Script with a lookup table that maps the first u-bits of the equivalence witness π = (ω, t) to output of
[Link] on that truncated witness. Rather than storing this enormous lookup table in Small Script we
use a Merkle tree to commit to it and the spending transaction simply proves that a particular input,
output pair exist in the Merkle tree. This allows us to compress the bytes we need for our Small Script
RIPEMD and SHA1 queries.
Using a Merkle tree has several space savings advantages. First, the hash function used to compute
this Merkle tree can be any hash function. We use BLAKE3 as it is currently the most compact
available implementation of hash function in Small Script. Second, we only need one BLAKE3 query
per level of the tree, whereas each RIPEMD and SHA1 query requires having Small Script code for
both hash functions for each bit of t. Third, we can truncate the output of BLAKE3 to 128-bits and
have a radix 4 Merkle tree, further reducing the number of hash function calls we need in Small Script.
Below, we look at how to construct this Merkle tree, why it is safe to truncate the BLAKE3 output
from 512-bits to 128-bits in the Merkle tree, and how we can get even more Small Script savings by
replacing the first 5 levels of the Merkle tree with a lookup table.

5.2.1 Constructing the Merkle tree

We parameterize our Merkle tree with the value u, which is number of bits of the equivalence witness,
π = (ω, t) that the Merkle tree will compress. That is, u layers of the binary tree of D will be stored
in the Merkle tree and the rest ||ω|| + ||t|| − u layers will be computed using RIPEMD and SHA1.
Each leaf of the Merkle tree consists of three outputs from [Link]: BLAKE3([Link](π)||[Link](π +
1)||[Link](π + 2)). As BLAKE3 has a message block size of 512-bits, it allows us to put three 160-bit
[Link](π) values in a single BLAKE3 message block. All other nodes in the Merkle tree are the hash
of four nodes rather than three.
The leaves of Merkle are sorted by the from low to high by the equivalence witness, with left most
leaf being
[Link](ω = 0, t = 0)||[Link](ω = 0, t = 1))||[Link](ω = 0, t = 2)
and the right most leaf being

[Link](ω = 2||ω|| −1, t = 2||t|| −3)||[Link](ω = 2||ω|| −1, t = 2||t|| −2))||[Link](ω = 2||ω|| −1, t = 2||t|| −1)

In this way, the Merkle tree commits to the equivalence witness, the input to [Link], as well as
committing to the output of [Link] for that particular input. Thus, the Merkle path allows us enforce
the relationship between input (ω, t) and outputs [Link](ω, t) by checking if the leaf position in the
Merkle tree matches the equivalence witness supplied by the spending transaction.
Throughout the Merkle tree computation, we truncate the output of BLAKE3 to 128 bits to save
space by having one one BLAKE3 compression function call per inner node. Hence, each inner node
of the Merkle tree takes four BLAKE3 outputs truncated to 128 bits, x0 , x1 , x2 , x3 , and computes
128−1
another (truncated) hash over them as follows: BLAKE3(x0 ||x1 ||x2 ||x3 ) | 0 . The Merkle tree is
radix 4, but the leaves contain three outputs. Thus, the depth of the Merkle tree is log4 (n/3), where
n = 2u is in the number of values committed to.

Cutting the top off of the tree. We can gain additional savings in bytes by replacing the top
five levels of the tree with a lookup table. Storing a lookup table of size uses 16 × 45 = 16, 384 bytes
allowing us to save five BLAKE3 calls and each BLAKE3 call costs ∼ 45, 000 bytes. Spaces savings
5 × 45, 000 − 16, 384 = 208, 616 bytes. If we store 290 leaves in the Merkle tree, we get a depth of 45
in the Merkle tree, removing the top 5 levels we require 40 only BLAKE3 evaluations.

23
Is 128-bit truncation safe? Considering the size of this Merkle tree and the truncated output of
128-bits there are bound to be a large number of collisions within the Merkle tree itself. To address
this, the membership test checks both that the output exists in the Merkle tree and also that it is the
correct output for equivalence witness π = (ω, t) by checking the leafs position in the Merkle tree. The
intuition here is that because the Merkle root was created in a trusted manner, for any particular leaf
of the Merkle tree, an attacker needs to find the 2nd preimage of the root or any node on the path to
the root, as opposed to just finding a collision between nodes (which is easier).
As given in [26], the probability of a collision in a Merkle tree of output size of m, and path depth
of k is, where the root is fixed and known is:
−m −m
2−m + e−2 − e−(k+1)2

Thus, for example, for m = 128 and k = 90 we get an adversary advantage of

−128 −128
2−128 + e−2 − e−(90+1)2 = 91 × 2−128 ≈ 2121.5 .

Thus, our Merkle tree provides ≈ 121.5 bits of security.

To summarize, we get the following result
Proposition 6. It is possible to precompute 2u hashes, modifying CheckS from Algorithm 4 such that
• its Small Script cost is

∼ 17, 000 + (⌈log4 (2u /3)⌉ + 1 − 5) · ||BLAKE3S || + (||ω|| + ||t|| − u) · (||SHA1S || + ||RIPEMDS ||),

as opposed to the old cost of

∼ ||t|| · (||SHA1S || + ||RIPEMDS ||).

• Moreover, for any integer 0 ≤ ℓ ≤ ⌈log4 (2u /3)⌉, Prove from Algorithm 4 is modified accordingly
as follows:
– there is an additional off-chain memory overhead of 4ℓ+2 /3 bytes;
– there is an additional off-chain computational overhead of ≈ 2u−2·ℓ hashes.

Proof. The CheckS Small Script cost claim follows from the discussion above and Proposition 3.
The additional off-chain overhead for Prove follows from the fact that we only the store the Merkle
tree root in the locking script. To spend the locking script, decommiting the Merkle tree is required.
Our solution is to keep the first ℓ layers of the radix 4 tree in storage while using ≈ 2u−2·ℓ hashes to
compute the last layers of the Merkle tree. Since we store 128-bit hashes per leaf, they require 4 bytes
each.

As an example instantiation for Proposition 6, let ||ω|| = 33, ||t|| = 67, u = 90, and assume
Conjecture 1 holds. This implies a set D of size 2100 , which, when using 290 precomputation, reduces
the cost of CheckS to about 3.3 million opcodes, versus 16 million using the naive approach. Choosing
ℓ = 20, the off-chain overhead of Proposition 6 is ∼ 5.86 terabytes of memory and computing ∼ 250
hashes per spend, which is negligible compared to the cost of other parts of Prove. In 8 we show how
given a Small Script implementation size of SHA1 and RIPEMD we can choose a u that allows our
covenant to fit in a 4 MB Bitcoin transaction

6 Concrete parameters and costs

One challenge we face is how to perform the equivalence check in Small Script while (a) being feasible to
execute off-chain and (b) staying under the maximum Bitcoin script size of roughly 4 million opcodes.

24
Figure 8: (Left) Plots the maximum allowable size that the small script implementation of SHA1 and
RIPEMD can be for a particular size of Merkle tree before the covenant transaction will be greater
than 4 Megabytes, e.g., for a Merkle tree containing 290 elements (u = 90), the summed small script
implementation of SHA1 and RIPEMD can not be larger than 130,922 opcodes. (Right) Graphs the
cost in number of hash queries needed to honestly spend a covenant for different equivalence witness
sizes, compared with the cost to break the covenant.

6.1 Likely parameters

To minimize ||t||, we choose the largest value allowed by Small Script ||w|| = 33 bits13 . As ||w|| + ||t|| is
likely be much smaller than 160, the number of f to f collisions will be much larger than the number
of g to g useless collisions when qf = qg. We can reduce the overall number of useless collisions by
making g more frequent than f by adjusting c.
The space requirements depend on size of the distinguished points table which is a function of both
qf and z. Assuming no more than 4096 16-TB hard drives for the distinguished points gives us a limit
of 256 bytes. We note that this space cost is not unreasonable, especially as cloud services can provide
petabytes of storage for a monthly fee, and as long as multiple covenants are computed sequentially,
this cost is amortized over all the covenants evaluated during that period of time.
Our choice of parameters places the following restrictions on qf and z:

256 ≥ (20 − z/8) × (2qf −z + 2(160−qf )−z )

We find that14 for z = 33, qf = 75, qg = 85, ||t|| = 70, ||ω|| = 33 we get time 286.11 and space 255.99 .

Small Script cost. We rely on Proposition 6, together with the implementations from [5, 14] and
Conjecture 1. We’ll make a few additional comments:
1. When computing the last layers of D, it is possible to replace the last layer cost of ||SHA1|| +
||RIPEMD|| by just min{||SHA1||, ||RIPEMD||}. This is because the last layer can either compute
a hash function if tj = 1 or use the identity function if tj = 0.
2. Extracting the transaction data from the SchnorrHash requires at least two SHA256S evaluations.
If the size of the transaction is small, each SHA256S evaluation will be on a single input block
(SHA256S ’s cost grows linearly with the number of input blocks).
13 While Small Script opcodes can not take a 33-bit element as an input, the Small Script OP ADD can generate a 33 bit

output. This allows us to verify the equivalence between a 33-bit element and that element represented in Small Script
as a 32-bit and 1-bit element by adding the smaller elements to together and checking equality.
14 A less conservative choice of 258 distinguished points table size would reduce the hash queries to 284.86 .

25
 3. To compute CheckS , a Schnorr signature needs to be evaluated on with SHA1S . We assume this
requires 70K additional opcodes.
Recall that |D| = 2103 , where ||ω|| = 33 and ||t|| = 70. Thus, choosing to perform 2u precompu-
tation in Proposition 6, where u = 90, we can make the following estimation on the covenant’s Small
Script cost:

2 · 211K + (17K + (⌈log4 (290 /3)⌉ + 1 − 5) · 45K) + (12 · 160K + 70K) + 70K,

which totals to about 4.34 million opcodes, just above Bitcoin’s 4 million opcode limit.
We mention multiple ways to go below this limit. One of them is to instead choose u = 93 in
Proposition 6, resulting in the following cost

2 · 211K + (17K + (log4 (293 /3) + 1 − 5) · 45K) + (9 · 160K + 70K) + 70K,

which totals to 3.91 million opcodes. Another possible choice is to note that, as mentioned in Sec-
tion 5.2, BLAKE3 can be replaced with any other hash function in our Merkle tree construction. Thus,
we make the following conjecture

Conjecture 2. There exists a Bitcoin-friendly hash function implementable in Small Script, that, for
a single block input of 512 bit, requires ∼ 35k opcodes.
This brings our previous calculation to

2 · 211K + (17K + (⌈log4 (290 /3)⌉ + 1 − 5) · 35K) + (12 · 160K + 70K) + 70K,

which totals to just about 3.93 million opcodes.

As another example of parameter instantiation, suppose we still use BLAKE3, but assume a more
aggressive version of Conjecture 1, where SHA1 and RIPEMD are also as efficient as BLAKE3, each
requiring ∼ 45K opcodes. This allows us to get away with only 286 precomputation cost, i.e., u = 86.
In this scenario, the total cost is

2 · 211K + (17K + (⌈log4 (286 /3)⌉ + 1 − 5) · 45K) + (16 · 90K + 70K) + 45K,

bringing us to 3.72 million opcodes.

Finally, in Figure 8 (left) we assume SHA1 and RIPEMD are equal in size and then we plot the
precompuation cost 2u needed to keep the transaction under the 4MB size limit. For u = 90, both
hash functions must sum to 130, 922

2 · 211K + (17K + (⌈log4 (290 /3)⌉ + 1 − 5) · 45K) + (12 · 130K + 65K) + 65K,

costing 3.98 million opcodes15 .

7 Security discussion
We now turn our attention to the security of our equivalence check. The job of an attacker is break
soundness, i.e., construct an input (⟨tx⟩32 , π, R1 ||s1 , ⟨R2 ||s2 ⟩32 ; spender tx) to our equivalence check
which passes the equivalence check but the Big Script input, R1 ||s1 , and the Small Script input, R2 ||s2
are not in fact equivalent, R1 ||s1 ̸= R2 ||s2 . This necessarily requires finding a triple collision:

SHA1(R1 ||s1 ) = [Link](ω, t) = SHA1(R2 ||s2 )

We present two potential attacks that aim to find a triple collision and break soundness. We treat
SHA1 and RIPEMD as 160-bit ideal hash functions. In the next Section 7.1 we outline our arguments
for why we consider SHA1 reasonable to model as an ideal hash function given known weaknesses [45]
leaving a more detailed analysis for future work.
15 We provide our code for this at [Link]/EthanHeilman/collision-covenants/settings

26
Approach 1 (Fix and Search):
1. Find R1 ||s1 and (ω, t) such that SHA1(R1 ||s1 ) = [Link](ω, t) using our collision finding algorithm.
2. Then attempt to transform this into a triple collision by finding a value R2 ||s2 such that
SHA1(R2 ||s2 ) = [Link](π) and R1 ||s1 ̸= R2 ||s2 .
Since (ω, t) is fixed, finding SHA1(R2 ||s2 ) = [Link](π) is requires computing the second preimage
of R1 ||s1 which needs 2160 queries (assuming a secure hash function).

Approach 2 (Meet-in-the-Middle):
1. Generate P = 2p unique pairs of signatures (R1 ||s1 , R2 ||s2 ), (R3 ||s4 , R4 ||s4 ), . . . such that each
pair collides SHA1(Ri ||si ) = SHA1(Rj ||sj ). The signature on the left will be accepted by the
covenant, the signature on the right would be rejected by the covenant.
2. Then try to find a π that collides with one of these pairs such that
SHA1(Ri ||si ) = SHA1(Rj ||sj ) = [Link](ω, t)

We consider an attacker with infinite space that is concerned only with the time cost. This allows
the attacker to find collisions by simply by constructing a giant lookup table. In Appendix G we
include an analysis in which the attacker can not use more than 264 bytes and uses a distinguished
points parallel collision algorithm. We do not include it here as it does not alter the time cost.
We denote the number of queries we make in step 1 as 2q1 and the number of queries we make in
step 2 as 2q2 +log2 (||t||) . The log2 (||t||) in step 2 is the result of the ||t|| additional queries that are made
to perform a query to [Link]. To succeed with greater than 1/2 probability the attacker must make:
2q1 + 2q2 +log2 (||t||)
queries, such that q2 ≤ ||ω|| + ||t|| and the following inequality holds:
22q1 −161 · 2q2
≥ 1/2
2160
Simplifying the inequality we get:
2q1 + q2 ≥ 320.
Thus to find the work the attacker needs to do, we find a q1 , q2 which minimizes the number of queries,
which satisfying the two conditions.
The above gives us the time cost of our best attack on our equivalence-check, but in the context
of covenants the number of queries in step 1 doubles. This is because to cheat a covenant, you need
one of the colliding signatures to pass the covenant’s rules and the other colliding signatures to be
rejected by the covenant. Since only half of these collisions generated in step 1 can be used to break
our covenant, this requires twice as many unique queries for step one increasing the threshold for the
attacker to:
2q1 + q2 ≥ 321.
Plugging in our proposed witness size parameters of ||ω|| = 33 and ||t|| = 70 we get q1 = 109.3764
and q2 = 102.2471 which requires
2109.3764 + 2102.2471+6.12 = 2109.3764 + 2108.3671 ≈ 2109.9
queries and satisfies the conditions q2 = 102.2471 ≤ 103 and
2 · 109.3764 + 102.2471 ≈ 321.
The time cost of creating a transaction that honestly spends the covenant is 286.11 . The time
cost of constructing a transaction that cheats the covenant is 2109.9 . The means that for our proposed
parameters an attacker must do 223.79 = 14, 504, 500 times more work than an honest spender. Figure 8
(Right) shows how the cost in queries to honestly spend or attack our covenant changes for different
sizes of equivalence witness sizes.
The Bitcoin hash rate is roughly 700 exahashes/second. This is 269.25 hashes/second, 285.64
hash/day, 291.12 hashes/year. Honestly spending a covenant has work roughly in terms of number
of hash queries to roughly 33 hours of Bitcoin mining. Cheating such a covenant based on the best
attack we have developed costs 450, 136 years of the Bitcoin mining network.

27
7.1 SHA1 known weaknesses
Our above security analysis models SHA1 as an ideal hash function despite SHA1’s known weaknesses
that place the cost of finding collisions at 263.4 [29], well below the generic collision resistance, 280 of
a 160-bit hash function that we assume. We leave a full analysis for future work, but we present three
brief arguments why this is a reasonable assumption.
All known attacks on SHA1’s collision resistance that rely on colliding messages that are many
message blocks long and with the attacker determining some bytes of the colliding messages. An
attacker attempting to break the soundness of our covenant construction is much more constrained.
The attacker neither has more than one or two message blocks to work with, nor can the attacker
determine bits of the message blocks.
If an attacker were to achieve collisions under these much more restrictive conditions, we could
deploy the hardened SHA1 countermeasure [45] in Small Script. Small Script would detect messages
with bit patterns that could result in a collision and reject that input. While not explored in this
paper, this level of control over when to allow or not allow a SHA1 collision in Small Script could
enable a reduction in the computational cost of our protocol without damaging soundness.
Finally we could make SHA1 collisions between Big Script and Small Script signatures impossible
by using RIPEMD to hash the signature rather than SHA1.

7.2 Quantum attacks

Unlike approaches based on functional encryption [39, 25], the security of our approach depends only
on the difficulty of colliding ideal hash functions. Even though we uss elliptic curve signatures in
our construction, we only require they be correct, not that they are sound. Similarly, while Taproot
signatures would be forgeable by a quantum computer, commitments to Tapleaves would likely remain
strong commitments, meaning that Taproot scripts would continue to be secure.
While giving concrete bounds is outside of the scope of this paper (and likely to depend on the
real-world parameters of a quantum computer), we can expect our approach to remain practically
secure against quantum attacks.
We also observe that the heavy computational cost in our construction occurs in two places: in a
globally one-time precomputation, and at the time that a covenant construction is used. It is therefore
very cheap for users to write and deploy covenant scripts if they do not expect to actually use them.
We therefore suggest that users of Bitcoin could use our covenant construction to produce scripts
that require a Lamport signature over transaction data in order to be satisfied. While the resulting
script will be very large, they can hide it in a Taproot leaf where it will never be serialized on-chain
unless it is used. In the case of a “surprise quantum computer” which forces Bitcoin to suddenly
disable all elliptic curve cryptography including taproot key spends, such users will still be able to
spend their coins (though at enormous cost). If a large quantity of users do this, it may be possible
for the Bitcoin chain to survive such an event, even if no better solution is found or deployed.

8 Conclusion
In this paper we showed how to construct a covenant in Bitcoin, without the need of a soft fork. Our
construction relied on existing opcodes, such as OP SHA1 and OP RIPEMD160, to build an equivalence
check between Bitcoin’s Big Script (which has access to transaction information) and Small Script
(which can perform arbitrary computation on said information).
To achieve this, we built a Bitcoin equivalence tester set D, whose elements can be generated in
both Big Script and Small Script. Thus, showing the equivalence of a Big Script element and its Small
Script representation amounts to finding hash collisions with elements of the set D. To find collisions,
we design a parallel collision finding algorithm based on distinguished points. Fooling our covenant
requires finding a 3-way collision with short inputs, which we assume to be hard.

8.1 Future work

We list directions for future work, some of which were mentioned in the introduction.

28
Small Script hash implementations. In Conjecture 1 we make assumptions on the Small Script
cost of SHA1 and RIPEMD. To fully realize our scheme requires these hash functions to be effi-
ciently implemented in Small Script. Moreover, while in Section 5.2 we utilized the somewhat efficient
BLAKE3, an even cheaper “Bitcoin-friendly” hash function would greatly reduce the opcode cost of
our covenant. Finally, our covenants uses SHA256 in Small Script – reducing the cost of these expensive
SHA256 calls greatly reduce transaction size.

Improved cryptographic primitives for Bitcoin. Beyond finding “Bitcoin-friendly” hash func-
tions, as mentioned in the previous paragraph, other improvements to our scheme are likely applicable.
A major component in our scheme is the computation of Merkle trees. While we use the standard
construction, the improvements shown in [13, 12] could be useful to gain more efficiency in either the
off-chain cost or Small Script cost of our covenant. Moreover, considering other techniques to reduce
the Small Script cost of generating D’s elements, such as utilizing “Bitcoin-friendly” cryptographic
accumulators, is another avenue for future research.

Cryptanalysis of SHA1. This paper treats SHA1 and RIPEMD as ideal 160-bit hash function
despite practical attacks on SHA1 [45] that are well below the 280 cost of a generic collision on an
ideal 160-bit function. If such attacks were shown to be applicable to our equivalence check, depending
on the details they could help or hurt our equivalence check. If we could exploit SHA1 cryptanalytic
weaknesses in our collision finding algorithm, we could reduce the work to find needed collisions. In
fact, the idea of exploiting SHA1 weaknesses to perform an equivalence check was part of the inspiration
that resulted in this paper. On the other hand, if these weaknesses could be used to reduce the cost
of finding triple collisions for inputs accepted by our equivalence they could weaken our soundness.

Better time-space trade offs. For our covenant construction, we use a parallel collision finding
algorithm based on distinguished points, in similar vein to [49]. Our algorithm exhibits a time-memory
trade-off [19], improving upon which is an important future research direction.
The most expensive aspect of our construction is the > 280 off-chain compute cost. We expect
possible improvements can come from two directions:
• Non-trivial collision attacks on SHA1 (or RIPEMD), which will lower our covenant off-chain cost
(while still keeping finding 3-way collisions infeasible).
• Precomputation methods to reduce the off-chain per-spend cost of the covenant. This is not
trivial because we find collisions of the form f (π) = gtx (ρ), where f is always the same hash
function, while gtx depends on the transaction data (hence only known during runtime).

8.2 Acknowledgements
The authors are indebted to Gil Segev for invaluable discussions in the early stages of this work. We
also thank Weikeng Chen, Robin Linus, Neha Narula, Noam Nisan, Jeremy Rubin, and Madars Virza
for helpful discussions and feedback.

References
[1] Ark. [Link]
[2] Bitcoin Layers. [Link]
[3] Bitcoin Wildlife Sanctuary. [Link]
[4] BitVM. [Link]
[5] BitVM Github. [Link]
[6] M. Bartoletti, S. Lande, and R. Zunino. Bitcoin covenants unchained. In Leveraging Applications
of Formal Methods, Verification and Validation: Applications: 9th International Symposium on
Leveraging Applications of Formal Methods, ISoLA 2020, Rhodes, Greece, October 20–30, 2020,
Proceedings, Part III 9, pages 25–42. Springer, 2020.

29
 [7] D. Boneh, A. Sahai, and B. Waters. Functional encryption: Definitions and challenges. In Y. Ishai,
editor, Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, Providence,
RI, USA, March 28-30, 2011. Proceedings, volume 6597 of Lecture Notes in Computer Science,
pages 253–273. Springer, 2011.
[8] W. Chen. CAT and Schnorr tricks. [Link]
gadgets.
[9] W. Chen. How to do Circle STARK math in Bitcoin?, 2024.
[Link]
[10] W. Chen. New multiplication algorithm for Circle STARK, 2024.
[Link]

[11] D. Christian and J. Rubin. BIP-118 - SIGHASH ANYPREVOUT, Feb. 2017.

[Link]/ajtowns/bips/blob/bip-anyprevout/[Link].
[12] C. Dhar, Y. Dodis, and M. Nandi. Revisiting collision and local opening analysis of ABR hash.
In D. Dachman-Soled, editor, 3rd Conference on Information-Theoretic Cryptography, ITC 2022,
July 5-7, 2022, Cambridge, MA, USA, volume 230 of LIPIcs, pages 11:1–11:22. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2022.
[13] Y. Dodis, D. Khovratovich, N. Mouha, and M. Nandi. T5: hashing five inputs with three com-
pression calls. IACR Cryptol. ePrint Arch., page 373, 2021.
[14] T. Giladi. [Link]

[15] O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions (extended ab-
stract). In 25th Annual Symposium on Foundations of Computer Science, West Palm Beach,
Florida, USA, 24-26 October 1984, pages 464–479. IEEE Computer Society, 1984.
[16] U. Haböck, D. Levit, and S. Papini. Circle starks. IACR Cryptol. ePrint Arch., page 278, 2024.

[17] E. Heilman. Signing a bitcoin transaction with lamport signatures (no changes needed), 2024.
[Link]/g/bitcoindev/c/mR53go5gHIk.
[18] E. Heilman and A. Sabouri. BIP-347 - OP CAT in Tapscript, Dec. 2023.
[Link]/bitcoin/bips/blob/master/[Link].
[19] M. Hellman. A cryptanalytic time-memory trade-off. IEEE transactions on Information Theory,
26(4):401–406, 1980.
[20] M. Jonas. Optimizing Algorithms for Bitcoin Script, June 2024.
[Link]/knowledge/optimizing-algorithms-for-bitcoin-script.
[21] A. Joux. Multicollisions in iterated hash functions. application to cascaded constructions. In
M. K. Franklin, editor, Advances in Cryptology - CRYPTO 2004, 24th Annual International
CryptologyConference, Santa Barbara, California, USA, August 15-19, 2004, Proceedings, volume
3152 of Lecture Notes in Computer Science, pages 306–316. Springer, 2004.
[22] U. Kirstein, S. Grossman, M. Mirkin, J. Wilcox, I. Eyal, and M. Sagiv. Phoenix: A formally
verified regenerating vault. arXiv preprint arXiv:2106.01240, 2021.

[23] D. E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-
Wesley, Boston, third edition, 1997.
[24] V. I. Kolobov. The path to general computation on Bitcoin, 2024.
[Link]

[25] M. Komarov. Bitcoin PIPEs - Covenants and ZKPs on Bitcoin Without Soft Fork, May. 2024.
[Link]/uploads/[Link].

30
[26] O. Kuznetsov, A. Rusnak, A. Yezhov, K. Kuznetsova, D. Kanonik, and O. Domin. Merkle trees
in blockchain: A study of collision probability and security implications. Internet of Things, page
101193, 2024. [Link]/pdf/2402.04367.
[27] j. Lau. Op pushtxdata, 2017, 2017. [Link]/jl2012/bips/blob/vault/[Link].
[28] S. D. Lerner, R. Amela, S. Mishra, M. Jonas, and J. Á. Cid-Fuentes. Bitvmx: A cpu for universal
computation on bitcoin. arXiv preprint arXiv:2405.06842, 2024.
[29] G. Leurent and T. Peyrin. {SHA-1} is a shambles: First {Chosen-Prefix} collision on {SHA-1} and
application to the {PGP} web of trust. In 29th USENIX Security Symposium (USENIX Security
20), pages 1839–1856, 2020. [Link]/conference/usenixsecurity20/presentation/leurent.

[30] R. Linus. Bitvm: compute anything on bitcoin, 2023. [Link]/[Link].

[31] R. Linus, L. Aumayr, A. Zamyatin, A. Pelosi, Z. Avarikioti, and M. Maffei. Bitvm2: bridging
bitcoin to second layers, 2024. [Link]/bitvm [Link].
[32] G. Maxwell. Coincovenants using scip signatures, an amusingly bad idea. Bitcoin-talk, Aug 2013.
[Link]

[33] M. Möser, I. Eyal, and E. Gün Sirer. Bitcoin covenants. In Financial Cryptography and
Data Security: FC 2016 International Workshops, BITCOIN, VOTING, and WAHC, Christ
Church, Barbados, February 26, 2016, Revised Selected Papers 20, pages 126–141. Springer, 2016.
[Link]
[34] J. OB́eirne, G. Sanders, and A. Towns. BIP-345 - OP VAULT, Feb. 2023.
[Link]/bitcoin/bips/blob/master/[Link].
[35] A. Poelstra. CAT and Schnorr Tricks I, Janary 2021. [Link]/andrew/blog/cat-and-
[Link].
[36] A. Poelstra. CAT and Schnorr Tricks II, Feb 2021. [Link]/andrew/blog/cat-and-
[Link].
[37] A. Poelstra. Script State from Lamport Signatures, May 2024.
[Link]
[38] S. Roose. BIP-Proposed - OP TXHASH and OP CHECKTXHASHVERIFY, Sept. 2023.
[Link]/bitcoin/bips/pull/1500.

[39] J. Rubin. FE’d Up Covenants, May. 2024. [Link]/public/pdfs/[Link].

[40] J. Rubin and J. OB́eirne. BIP-119 - CHECKTEMPLATEVERIFY, Jan. 2020.
[Link]/bitcoin/bips/blob/master/[Link].
[41] R. Russell. The Great Script Restoration Project, May 2024.
[Link]/watch?v=rSp8918HLnA.
[42] N. Satoshi. CVE-2010-5137: OP LSHIFT crash, Aug 2010.
[Link]/wiki/Common Vulnerabilities and Exposures#CVE-2010-5137.
[43] N. Satoshi. “misc changes”, Aug 2010. [Link]/bitcoin/bitcoin/commit/4bd188c43.

[44] sCrypt. Bitcoin OP CAT Use Cases Series #4: Recursive Covenants, 2024.
[Link]
6a3127a24af4.
[45] M. Stevens, E. Bursztein, P. Karpman, A. Albertini, and Y. Markov. The first collision for full sha-
1. In Advances in Cryptology–CRYPTO 2017: 37th Annual International Cryptology Conference,
Santa Barbara, CA, USA, August 20–24, 2017, Proceedings, Part I 37, pages 570–596. Springer,
2017.

31
[46] J. Swambo, S. Hommel, B. McElrath, and B. Bishop. Bitcoin covenants: Three ways to control
the future. arXiv preprint arXiv:2006.16714, 2020.
[47] J. Swambo, S. Hommel, B. McElrath, and B. Bishop. Custody protocols using bitcoin vaults.
arXiv preprint arXiv:2005.11776, 2020.
[48] Taproot Wizards. A Prototype Vault using CAT. [Link]
wizards/purrfect vault.
[49] P. C. Van Oorschot and M. J. Wiener. Parallel collision search with cryptanalytic applications.
Journal of cryptology, 12:1–28, 1999. [Link]/ paulv/papers/[Link].
[50] N. van Saberhagen. CryptoNote v2.0, Oct 2013. [Link] bryan/papers2/bitcoin/[Link].

[51] J. Wuille, P. Nick and T. Ruffing. BIP-340 - Schnorr Signatures for secp256k1, Janary 2020.
[Link]/bitcoin/bips/blob/master/[Link].
[52] J. Wuille, P. Nick and A. Towns. BIP-341 - Taproot: SegWit version 1 spending rules, Janary
2020. [Link]/bitcoin/bips/blob/master/[Link].

[53] J. Wuille, P. Nick and A. Towns. BIP-342 - Validation of Taproot Scripts, Janary 2020.
[Link]/bitcoin/bips/blob/master/[Link].
[54] d. Zakharov, O. Kurbatov, M. Bista, and B. Bist. Optimizing big integer multiplication on bitcoin:
Introducing w-windowed approach. Cryptology ePrint Archive, 2024. [Link]/2024/1236.

A Big Script and Small Script Opcodes

Throughout this paper we have divided Bitcoin Script into two subsets, Small Script and Big Script,
with the distinction that the former is able only to operate on 32-bit (4-byte) values. In this Appendix
we make this distinction precise, by listing every opcode of Script and describing the size of its inputs
and outputs.
First, each opcode is one byte in size. Of the 256 possible values for a byte, 100 are “failure” or “no-
op” opcodes. If present in a script, they have no effect (except possibly to invalidate the transaction),
so for our purposes we can ignore them.
Of the remaining 156,
• 96 are “push” opcodes which simply push data onto the stack. In Small Script, these can be
used to push data of up to 4 bytes in size.
• 17 are “stack manipulation opcodes” (e.g. OP 2DROP or OP ROT). These simply rearrange stack
elements regardless of size, and therefore can be executed either in Big Script or Small Script.
• The OP IFDUP deserves a category of its own, since it takes an arbitrarily-sized input, interprets
it as a boolean (which means that every bit except the most-significant one is 0), and duplicates
its input if so.
• 5 are “control flow opcodes” (OP IF, OP NOTIF, OP ELSE, OP ENDIF, OP VERIFY) and can be exe-
cuted in either context.
(Strictly speaking, OP IF and OP NOTIF are legal only with inputs of 0 or 1. But it is easy to
transform an input of any size into this form, e.g. by OP SIZE OP 0NOTEQUAL.)

For the remaining 38 opcodes, we look more carefully at their allowed input sizes and possible
output sizes. We list them in Table 1.
In the table, a dash indicates a 0-sized input or output, and “Small∗ ” indicates an opcode that
may output a 5-byte value but typically outputs a Small Script value. (OP CLTV and OP CSV simply
output their input unchanged). It is always possible to detect these cases in Script and handle them
separately, so these opcodes can be considered to have Small Script outputs.
For a given script, we say that it is a Small Script while the elements on the stack during its
execution are 4 bytes or smaller, and call it a Big Script otherwise. In general, we cannot say that an

32
entire script is a “Big Script” or “Small Script”, but we can say whether the execution is currently “in
Big Script” or “in Small Script”, and say which opcodes are permissible in this context.
As we see from the table, the 5 signature-checking opcodes cannot be used with Small Script inputs
(and in fact, cannot be used with the outputs of any opcodes except push opcodes, since the required
input sizes do not match the output sizes of any other opcodes). We further see that the 5 hashing
opcodes, whose outputs are marked “Big,”, can be used in any context, but once used, will leave the
script in a Big Script context.
Finally, we see that the opcodes OP SIZE, OP EQUAL, OP EQUALVERIFY, and OP NOT can be used to
move from Big Script back to Small Script. (In Taproot it is impermissible to use OP NOT in this way,
but it can be simulated with OP IFDUP and OP SIZE; see above.) However, these opcodes all lose all or
most of the information available from the Big Script stack elements, and therefore cannot be used to
bridge Big Script and Small Script.

B Schnorr SigHash
The data to be signed in Bitcoin’s Taproot Schnorr signature implementation [52, 53] takes as input
the contents of the surrounding transaction as well as a sighash flag, which is appended to the serialized
signature and determines which parts of the transaction are to be signed.
There are two variants of the signature hash: one used in “key spends” which is used when no
script is provided, and one used by “script spends” which are signature checks invoked from within a
script. Only the latter is relevant for our purposes, so we will disregard keyspends from now on.
The data to be signed is hashed using a BIP-0340 tagged hash [51] defined as

HashTapSighash (x) = SHA256(SHA256(TapSighash)∥SHA256(TapSighash)∥x)

where here ∥ indicates concatenation and TapSighash is the literal ASCII encoding of that word.
The exact data which is signed is then

M = HashTapSighash (0x00∥SigMsg(hash type, 1)∥ext)

where the constant 0x00 is fixed and the constant 1 indicates that this is a script spend. The function
SigMsg(hash type, 1) is in turn defined as the serialization of:
• hash type (1 byte);
• Transaction version (4 bytes, little endian);

• Transaction locktime (4 bytes, little endian);

• If the high bit of hash type is unset,
– sha prevouts, the SHA256 hash of all input outpoints;
– sha amounts, the SHA256 hash of all input amounts;
– sha scriptpubkeys, the SHA256 hash of all input scriptPubKeys (serialized as script with
length prefix);
– sha sequences, the serialization of all input sequence numbers (4 bytes each, little endian);
• If the lowest 2 bits of hash type are 0 or 1,

– sha outputs, the serialization of all transaction outputs;

• 0x03 if an annex (auxiliary data to be signed is present; otherwise 0x02;
• If the high bit of hash type is set,
• sha outputs, the serialization of all transaction outputs;

– The outpoint of the input being signed for;

– The amount of the input being signed for;

33
Table 1: Bitcoin Script opcodes and their input and output sizes. A dash indicates a 0-sized input
or output, and “Small∗ ” indicates an opcode that may output a 5-byte value but typically outputs a
Small Script value. (OP CLTV and OP CSV simply output their input unchanged).

Opcode Input Size Output Size

OP DEPTH – Small
OP SIZE Any Small
OP EQUAL Any Small
OP EQUALVERIFY Any –
OP 1ADD Small Small∗
OP 1SUB Small Small∗
OP NEGATE Small Small∗
OP ABS Small Small
OP NOT Any Small
OP 0NOTEQUAL Small Small
OP ADD Small Small∗
OP SUB Small Small∗
OP BOOLAND Small Small
OP BOOLOR Small Small
OP NUMEQUAL Small Small
OP NUMEQUALVERIFY Small –
OP NUMNOTEQUAL Small Small
OP LESSTHAN Small Small
OP GREATERTHAN Small Small
OP LESSTHANOREQUAL Small Small
OP GREATERTHANOREQUAL Small Small
OP MIN Small Small
OP MAX Small Small
OP WITHIN Small Small
OP CODESEPARATOR – –
OP CLTV Small∗ Small∗
OP CSV Small∗ Small∗
OP RIPEMD160 Any Big (20)
OP SHA1 Any Big (20)
OP SHA256 Any Big (32)
OP HASH160 Any Big (20)
OP HASH256 Any Big (32)
OP CHECKSIG Big (32, 64) Small
OP CHECKSIGVERIFY Big (32, 64) –
OP CHECKSIGADD Big (32, 64) Small
OP CHECKMULTISIG Big Small
OP CHECKMULTISIGVERIFY Big Small

34
 – The scriptPubKey of the input being signed for;
– The sequence number of the input being signed for;
We observe that the fields sha amounts and sha scriptpubkeys, while present in the signature hash,
are not present in the transaction itself. (Conversely, the witness data of the transaction is not present
in the signature hash.) Therefore, when we refer to the signature hash as the “transaction data” this
is actually a slight abuse of terminology.
Definition 7. In the main body, we’ll write, for a transaction tx,
MsgHash(tx) = M = HashTapSighash (0x00∥SigMsg(hash type, 1)∥ext)
to refer to the transaction serialization and hashing procedure defined above.
With the signature hash M defined as above, we can describe the BIP-0340 Schnorr signature
algorithm. First, we need another tagged hash:
HashBIP0340/challenge (x) = SHA256(SHA256(BIP0340/challenge)∥SHA256(BIP0340/challenge)∥x)
where as above, the text is ASCII-encoded.
Then a BIP-0340 signature with public key P = xG is defined by:
k ←uniform {0, 1}256
R ← kG
e ← HashBIP0340/challenge (R∥P ∥M )
s ← k + ex
σ ← R∥s
We assuming no sighash flag is attached to the signature. This causes Bitcoin to use the flag
SIGHASH DEFAULT, which sets hash type to 0, signing all inputs and all outputs of the transaction.
Definition 8. In the Schnorr signature above, we define SchnorrHashR,P as the transaction serial-
ization and hashing to produce the message for the signature algorithm. That is, we define, for a
transaction tx,
SchnorrHashR,P (tx) = HashBIP0340/challenge (R∥P ∥M )
as above.

B.1 Schnorr Trick

The Schnorr trick [35, 36] uses the above construction, but chooses the secret key x and secret nonce
k both to be 1, rather than uniformly random. The above equation then reduces to
s ← 1 + HashBIP0340/challenge (R∥P ∥M )
σ ← R∥s
Which can be verified by using OP CAT and OP EQUALVERIFY to ensure that R = G, directly setting
P = G, then using OP CHECKSIGVERIFY to verify that the above equation holds.
Then, by using OP CAT and OP SHA256 to recompute M and HashBIP0340/challenge (R∥P ∥M ) + 1,
transaction data can be extracted from M .
In the original Schnorr trick, the addition by 1 required special consideration. In particular, it
assumed that only the last byte of the signature would be affected by the addition, and used OP CAT to
separate and ignore this last byte (since when comparing 256-bit hashes for equality, ignoring a single
byte will not meaningfully affect security).
However, this assumption fails to hold for 1/256 of possible transaction hashes. The original Schnorr
trick addressed this by asking the user to grind their signatures to ensure this was not the case.
This amount of grinding is very small (requiring no extra signatures at all 255/256 of the time), and
can be made smaller by ignoring more suffix bytes. But for our purposes, any amount of grinding would
complicate our algorithm and potentially make an already-expensive process much more expensive.
We therefore address the addition by 1 differently: rather than assuming it affects only a single byte,
and ignoring it, we address it head-on by implementing a 256-bit addition in Small Script.

35
C Ring Signatures Without Blake3 Merkle Trees
In Section 2.2.5 we described the “Tapleaf tragedy,” which is that we cannot use Taproot trees as
lookup tables for transaction signatures, since transaction signatures change uncontrollably when we
change which branch we reveal. This means that to implement covenants via a small-to-big equivalence
check on signatures, we must implement Merkle tree lookups directly in Script. We used BLAKE3 for
this purpose since it is the most efficiently implementable in Script.
In Remark 2 we observed that nearly all of the on-chain cost of our covenant construction could
be avoided, if not for the Tapleaf tragedy.
However, while signatures are the only type of object visible to Big Script which we might want to
manipulate using Small Script. There are also public keys, which are a fixed size (32 bytes in Taproot
script).
To illustrate how this might be useful, we describe a ring signature construction. We assume we
have access to a zero-knowledge proof construction for set membership which can be implemented for
secret signing keys in Small Script. For example, one could use a linkable ring signature [50] for which
the keypairs were of the form (x, xH) with H a fixed nonstantand generator for the secp256k1 curve,
and whose key images were of the form xG, where G is the standard generator. By ring-signing the
empty string, a user identified by a ring signature key in the set {x1 H, . . . , xn H} can prove that a
transaction signing key xi G uses some xi from the set without revealing each one.
Now, even assuming a ring signature primitive, it is not possible to directly ring-sign a Bitcoin
transaction. The reason, as always, is that our ring signature is implemented in Small Script, which
does not have access to transaction data. We could provide transaction data to Small Script by using
the covenant construction of this paper, but there is a more efficient way: rather than using the
small-to-big equivalence check to feed transaction data from Big Script to Small Script, we use the
equivalence check to feed a public key from Small Script to Big Script. By applying the equivalence
check to a public key rather than signature, we can do (part of) our Merkle tree lookup using Taproot
trees rather than expensive Small Script construction.
In more detail, our construction is as follows:
Let G be the the standard generator of the secp256k1 elliptic curve, and H an alternate nothing-up-
my-sleeve (NUMS) generator. Then, a set of users {Ui }i generate random secret keys xi and publish
public keys xi H. Using the set of keys {xi H}i they construct a Bitcoin script which:
• First, checks a linkable ring signature ⟨σ⟩32 on an empty message against key image ⟨I⟩32 , where
the ring signature passes if and only if I = xi G for some xi .
• Then, does a small-to-big equivalence check between a proposed public key I and ⟨I⟩32
• Then calls OP CHECKSIG using the public key I to verify a signature on the transaction itself.
Essentially, we are using the linkable ring signature “backward,” exchanging the roles of key images
and public keys. By validating the ring signature in Small Script, we obtain a key image whose discrete
logarithm is equal to that of one of the ring signature keys. We then use the small-to-big equivalence
check to move this key image into Big Script, where it is interpreted as an ordinary signing key for a
Bitcoin transaction.
The above approach is a rough sketch; it is unlikely to be the most efficient construction, and does
not attempt to preserve privacy across transactions (e.g. by making H be unique per transaction).
But it illustrates the potential of this approach.

D Proof of Proposition 3
To prove the last part of Proposition 3, we’ll need the following lemmas.
Lemma 1 (Poisson approximation of balls and bins). Suppose you throw m balls into n bins, each
ball independently landing on a bin uniformly at random. Let Em be a monotone event whose indicator
random variable is a function of f (L1 , . . . , Ln ), where Li is the number of balls in bin i. Consider
a second experiment where we choose n independent random variables Z1 , . . . , Zn , where each Zi ∼
P ois(λ) follows a Poisson distribution with parameter λ = m/n. Then,

Pr[f (L1 , . . . , Ln )] ≤ 2 · Pr[f (Z1 , . . . , Zn )].

36
 Here, we say that Em is a monotone event if it always holds that either Pr[Em ] ≤ Pr[Em′ ] or
Pr[Em ] ≥ Pr[Em′ ] for m′ < m. The events we are interested in will be monotone.
Lemma 2 (Chernoff’s inequality). Suppose
Pn that X1 , . . . , Xn are independent random variables taking
values in {0, 1}. In addition, let X = i=1 Xi and µ = E[X]. Then for any δ > 0 it holds that
!µ
e−δ
Pr [X ≤ (1 − δ)µ] < 1−δ
.
(1 − δ)

In particular, for δ = 2−20 , we have that

µ
Pr [X ≤ (1 − δ)µ] < 1 − 2−41 .
Proof of Proposition 3. The claim about evaluating [Link] is trivial, and the claim about evaluating
[Link] follows from Conjecture 1.
Now, for a function f and a set S, define f (S) = {f (s)|s ∈ S}. To bound |D|, we make the following
definitions:
L0 = {0, 1}33
L1 = SHA1(L0 ) ∪ RIPEMD(L0 )
L2 = (SHA1(L1 ) ∪ RIPEMD(L1 )) \ L1
L3 = (SHA1(L2 ) ∪ RIPEMD(L2 )) \ (L2 ∪ L1 )
..
.
||t||−1

[
L||t|| = SHA1(L||t||−1 ) ∪ RIPEMD(L||t||−1 ) \ Lj
j=1

where, by definition, |D| ≥ |L||t|| |. Our strategy will be to prove that |Li | is sufficiently large for each i.
A subtlety arises in that we work in the random oracle model. Thus, for simplicity of analysis we’d like
to require that all Li and Lj are sampled independently, whenever i ̸= j, as otherwise, we might visit
values that were already queried to the random oracle. This is why in the construction we required
that Li is disjoint from Li−1 , Li−2 , . . . , L1 .
To this end, for some {αi }i to be specified later, we’ll define a sequence of events
B1 :|L1 | = 234
B2 :|L2 | = 235
..
.
B34 :|L34 | = 277
B35 :|L35 | ≥ 278 α35
..
.
B||t|| :|L||t|| | ≥ 233+||t|| α||t|| .
Since it holds that h i
Pr |D| ≥ 233+||t|| α||t|| ≥ Pr B||t|| ,
 

we’ll bound the probability of the latter from below. Starting by bounding Bi for i = 1, it holds that
2·34−160
Pr [B1 ] ≥ e−2 ≥ 1 − 2−92 ,
where the inequality follows by the usual birthday bound. For i = 2, define
f2 = SHA1(L1 ) ∪ RIPEMD(L1 ).
L
By using the union bound, we get that
h i h i
f2 | < 235 B1 − Pr L
Pr [B2 |B1 ] ≥ 1 − Pr |L f2 ∩ L1 ̸= ∅ B1 .

37
Bounding these quantities we get that
h i
Pr |L f2 | < 235 B1 ≤ 22·35−160 = 2−90 ,
h i
35
Pr L f2 ∩ L1 ̸= ∅|B1 ≤ 1 − 234−160 2 ≤ 2−90 ,

where the latter inequality uses the fact that |L1 | is at most 234 , so in the random oracle model, we’re
essentially throwing 235 balls into 2160 bins, hoping that they all miss the |L1 | ≤ 234 bins. Hence

Pr [B2 |B1 ] ≥ 1 − 2−89 .

Continuing with a similar analysis for i = 3, . . . , 34 (where we define L

fi similarly to how we defined
L2 ), we get that
f
h i
Pr |L fi | < 233+i Bi−1 ≤ 22·(33+i)−160 ≤ 2−26 ,
 
i−1
[
234+i
Pr fLi ∩ Lj ̸= ∅|Bi−1  ≤ 1 − 233+i−160 ≤ 2−26 ,
j=1

Hence, for i = 3, . . . , 34, it holds that

Pr [Bi |Bi−1 ] ≥ 1 − 2−25 .

 
For i ≥ 35 a different strategy is needed. To bound Pr |Li | < 233+i αi Bi−1 , we’ll apply Lemma 1.
33+i−160
This implies there are independent Bernoulli random variables Xj ∼ Ber 1 − e−2 such that
 160 33+i 
2 X −2
Pr |Li | < 233+i αi Bi−1 ≤ 2 · Pr  Xi < 233+i αi  ,
 
j=1

where Xj equals 1 if bin j is nonempty in round i. In total there are 2160 bins, but we exclude 233+i
of them, which are potentially occupied by values from L1 , . . . , Li−1 . Applying Lemma 2, we get that
 160 33+i 
2 X −2

µ
Pr  Xj ≤ (1 − δ)µ < 1 − 2−41 ,
j=1
 33+i−160

where µ = (2160 − 233+i ) 1 − e−2 . To make it applicable to the previous bound we choose

(1 − δ)µ
αi = ,
233+i
which satisfies |αi − 1| ≤ 2−15 . Since µ ≥ 232+i ≥ 267 , it holds that
 160 33+i 
2 X−2

267
Pr  Xj ≤ (1 − δ)µ < 1 − 2−41 ≤ 2−1,000,000 ,
j=1

meaning we can mostly neglect it. In total we get that

||t||
Y
35
Pr[|D| > (1 − 2−15 )2||ω||+||t||| ] ≥ Pr[B1 ] · Pr[Bj |Bj−1 ] ≥ 1 − 2−25 ≥ 1 − 2−19 .
j=2

E Hash function collisions

Here we list some basic results on hash function collisions.

38
E.1 Expected collisions per Number of queries
Here we give the equation for the expected number of collisions, E[C], after Q = 2q queries to a hash
function whose output size is N = 2n , i.e., , n bit length output. The probability of any two queries
Q! Q2 −Q 2q q
colliding is: 2−n . The number of possible collisions for Q queries is Q = 2 2−2 .


2 = 2!(Q−2)! = 2
Thus, the expected number of collisions is the probability of a collision times the number of possible
ways a collision count occur:

22q − 2q
 
Q
E[C] = 2−n = = 22q−n−1 − 2q−n−1
2 2n+1
We can drop the last part of this equation 2q−n−1 as it is insignificant for size of numbers we are
using.:

E[C] ≈ 22q−n−1

E.2 Collisions between two hash functions

Here we derive the expected collisions and probability of one or more collisions between two n bit hash
functions, Ha , Hb after 2a queries to Ha and 2b queries to Hb .
We are only concerned with collisions between the two hash functions, that is Ha (x) = Hb (x′ ) where
x ̸= x′ . We do not count collisions that occur within the same hash function Ha (x) = Hn (x′ ).
The expected number of collisions between them Ha (x) = Hb (x′ ) after 2a queries to Ha and and 2b
queries to Hb is:

1 2a+b
2a × 2b × = = 2a+b−n
2n 2n
The probability of at least one collision between Ha and Hb is:
1 2a+b a+b−n
1 − (1 − ) ≈ 1 − e−(2 )
2n

F Time and space cost of our distinguished points collision

algorithm
We define the hash functions f and g take ρ ∈ {0, 1}160 as input:

||ω|| ||ω||+||t||+1
f (ρ) : {0, 1}||w||+||t|| → {0, 1}160 is [Link](ρ | 1 , ρ | ||ω||+1 )
g(ρ) : {0, 1}160 → {0, 1}160 SHA1(G||(SchnorrHash(TxGrind(tx, ρ)) + 1))

We define the following variables as:

z: The number of zeros that identifies a point as a distinguished point.

qf : The number of unique queries to f is 2qf
qg: The number of unique queries to g is 2qg

The probability of a useful collision i.e., a collision allows us to spend a covenant, is:
qf +qg−160
1 − e−2
We have greater than 1/2 probability of a useful collision when qf + qg ≥ 160. As we will show
below this does not tell us the total work we need to do. This is because not every query to f or g is
unique due to useless collisions i.e., collisions that are not useful for finding a covenant.

39
F.1 Distinguished Point Table Size
We define our distinguished points as an output which has at least z zero bits at the end. This means
that 2−z is probability of a query to the hash function producing a distinguished point and 2z is the
number of queries between two distinguished points.
A naive approach would be for each row on the distinguished point table to include the distinguished
point (size 160/8 = 20 bytes), and the prev distinguished point. As the distinguished points are added
to the table in as they are discovered, the previous distinguished point can simply be the previous
address in memory, letting us reference it implicitly without using any space. Since all distinguished
points end in z we can truncate the z all zero bits. Thus a row in our distinguished point table is
(160 − z)/8 bytes.
If the total number of unique queries we make is Q = 2q , then distinguished point table will have
q−z
2 rows, the table will use space:
2q−z × (20 − z/8)

F.2 The Useless Collisions Problem

Collisions such as f (ρ) = f (ρ′ ) or g(ρ) = g(ρ′ ) do not help us show equivalence. We term such
collisions, useless collisions. Only collisions between f and g e.g., f (ρ) = g(ρ′ ) are useful for showing
equivalence.
Each time we hit a collision it takes us 2z−1 additional hash queries before we hit reach a dis-
tinguished point in the distinguished point table. Then determining where the collision occurred to
determine if the collision is a useless collision or not requires an additional 2z−1 work. Thus, each
useless collision we encounter costs an additional 2z−1 + 2z−1 = 2z work.
Pseudo-collisions are collisions that arise we not all the bits of the input to a hash function influence
the output. In our case pseudo-collisions arise when ||w|| + ||t|| is less than ρ, as f can not fit all the
bits of ρ into f causing a truncation of ρ. As the size of ρ is 160 then we encounter pseudo-collisions in
f when ||w|| + ||t|| < (||rho|| = 160) i.e., the domain of f , {0, 1}||w||+||t|| , is smaller than ρ ∈ {0, 1}160 .
||w||+||t|| ||w||+||t||
f (ρ) = f (ρ′ ); ρ ̸= ρ′ ; ρ | 0 = ρ′ | 0
Pseudo-collisions presents a serious problem of wasted work for our collision finding algorithm
because the size constraints of Small Script forces us to significantly truncate ρ in f . The expected
number of f to f collisions, including pseudo-collisions, for 2qf queries to f is (See Appendix E.1):

22qf −||w||−||t||−1

We can also compute the expected number of g to g useless collisions for 2qf queries to g as:

22qg−160−1

As ||w|| + ||t|| is likely be much small than 160 the number of f to f collisions is likely to much
larger than the number of g to g useless collisions if qf = qg. We can reduce the overall number of
useless collisions by making g more frequent than f . The total number of useless collisions is given by:

22qf −||w||−||t||−1 + 22qg−160−1

As shown earlier, for a greater 1/2 probability of finding a useful collision, qf +qg ≥ 160. Whatever
we subtract from qf , we must add to qg.
Now we look at much work is wasted for each useless collision. Each time we hit a collision it
takes us 2z−1 additional hash queries before we hit reach a distinguished point in the distinguished
point table. Then we need to determining the preimage of the collision to determine if the collision is
a useless collision or not requires an additional 2z−1 work. Thus, each useless collision we encounter
costs an additional 2z−1 + 2z−1 = 2z work.
The total wasted work, is:

2z × (22qf −||w||−||t||−1 + 22qg−160−1 ) = 22qf +z−||w||−||t||−1 + 22qg+z−160−1 )

40
Figure 9: Our equation for the number of queries need to find a collision for our collision finding
algorithm. Rather than a 160-bit hash functions, we use 40-bit hash functions and compare this against
an implementation of our collision finding algorithm. We use ||ω|| = 10 and z = 3. We run the attack
20 times per position.

F.3 Additional Work in f

The hash function f calls the function [Link] which will make an additional hash function query for
each bit in t for ||t|| additional hash function calls. It is not unreasonable to view ||t|| as a constant
and treat [Link] a single hash function call for the purpose of computing work. In our setting we are
considered with practical collisions, and want to choose parameters so we include the number of hash
function calls in [Link] as additional queries. Thus, the additional cost of a call to f vs g is ||t||.

F.4 Time and Space for a Useful Collision

The number of unique queries is including the additional work in f is:

2qf × (||t||) + 2qg = 2qf +log2 ||t|| + 2qg

The amount of wasted work we have to do is:

22qf +log2 ||t||+z−||w||−||t||−1 + 22qg+z−160−1

The total amount of time work to find a useful collision is 2qf +log2 ||t|| +2qg +22qf +log2 ||t||+z−||w||−||t||−1 +
2qg+z−160−1
2 where qf + qg ≥ 160. For qf + qg = 160 we can simplify this by defining qg as
qg = 160 − qf :

Work(qf, ||t||, ||w||, z) = 2qf +log2 ||t|| + 2160−qf + 22qf +log2 ||t||+z−||w||−||t||−1 + 22(160−qf )+z−160−1

The space requirements are:

(20 − z/8) × (2qf −z + 2(160−qf )−z )

F.5 Tests on truncated outputs

To validate our math we implemented our collision attack against hash functions truncated to an 40-bit
output. In Figure 9 we graph the result of our experimental runs of this collision attack against our
work equation.
This requires generalizing our work equation above for n-bit outputs

Work(qf, ||t||, ||w||, z) = 2qf +log2 ||t|| + 2n−qf + 22qf +log2 ||t||+z−||w||−||t||−1 + 22(n−qf )+z−n−1 .

41
For two 48-bit hash functions, z = 6, ||ω|| = 10, ||t|| = 20, qf = 2−7 , qg = 1

2qf +log2 20 + 240−qf + 22qf +log2 20+z−10−20−1 + 22(40−qf )+6−40−1

G Attacks on our Equivalence Checks

In this appendix we provide a detailed walk through of the best attacks we have developed against our
equivalence check. To break our equivalence check an attacker must break soundness, i.e., construct
an input
(⟨tx⟩32 , π, R1 ||s1 , ⟨R2 ||s2 ⟩32 ; spender tx)
to our Tapscript equivalence check which passes the equivalence check but the Big Script input, R1 ||s1 ,
and the Small Script input, R2 ||s2 are not in fact equivalent, R1 ||s1 ̸= R2 ||s2 . This necessarily requires
a finding a triple collision:

SHA1(R1 ||s1 ) = [Link](π) = SHA1(R2 ||s2 )

We present two potential attacks that aim to find a triple collision and break soundness. We treat
SHA1 and RIPEMD as 160-bit ideal hash functions. For a discussion of the known weaknesses of
SHA1 in see Section 8.

Approach 1 (fix and search):

1. Find R1 ||s1 and π such that SHA1(R1 ||s1 ) = [Link](π) using our collision finding algorithm.

2. Then attempt to transform this into a triple collision by finding a value R2 ||s2 such that
SHA1(R2 ||s2 ) = [Link](π) and R1 ||s1 ̸= R2 ||s2 .
Since π is fixed, finding SHA1(R2 ||s2 ) = [Link](π) is finding the second preimage of R1 ||s1 which
requires 2160 queries assuming the underlying hash function is secure.

Approach 2 (Meet-in-the-Middle):
1. Generate P = 2p unique pairs of signatures (R1 ||s1 , R2 ||s2 ), (R3 ||s4 , R4 ||s4 ), . . . such that each
pair collides SHA1(Ri ||si ) = SHA1(Rj ||sj ). The signature on the left will be accepted by the
covenant, the signature on the right would be rejected by the covenant.
2. Then try to find a π that collides with one of these pairs such that

SHA1(Ri ||si ) = SHA1(Rj ||sj ) = [Link](ω, t)

We first analyze the cost of this attack against an attacker that has infinite space. This allows the
attacker to use a lookup table to find collisions in 160-bit hash functions in only 280 queries. We follow
this analysis with a more realistic analysis in which the attacker has space constraints and must use
distinguished points collision algorithm.

Attacker with infinite space. We consider an attacker with infinite space that is concerned only
with the time cost. In step one finding 2p = 22q−160−1 pairs of colliding signatures requires 2q =
2(p+161)/2 queries.
2p = 22q−160−1
p = 2q − 161
(p + 161)/2 = q
We denote the number of queries we make in step 1 as 2q1 and the number of queries we make in
step 2 as 2q2 +log2 (||t||) . The log2 (||t||) in step 2 is the result of the ||t|| additional queries that are made
to perform a query to [Link]. To succeed with greater than 1/2 probability the attacker must make:

2q1 + 2q2 +log2 (||t||)

42
queries, such that q2 ≤ ||ω|| + ||t|| and the following inequality holds:

22q1 −161 · 2q2

≥ 1/2
2160
22q1 −161+q2 −160 ≥ 1/2
Simplifying the inequality we get:
2q1 − 161 + q2 ≥ 159
2q1 + q2 ≥ 320
Thus to find the work the attacker needs to do, we find a q1 , q2 which minimizes the number of queries,
which satisfying the two conditions.
The above gives us the time cost of our best attack on our equivalence-check, but in the context
of covenants the number of queries in step 1 doubles. This is because to cheat a covenant, you need
one of the colliding signatures to pass the covenant’s rules and the other colliding signatures to be
rejected by the covenant. Since only half of these collisions generated in step 1 can be used to break
our covenant, this requires twice as many unique queries for step one increasing the threshold for the
attacker to:
2q1 + q2 ≥ 321.
Plugging in our proposed witness size parameters of ||ω|| = 33 and ||t|| = 70 we get q1 = 109.3764
and q2 = 102.2471 which requires

2109.3764 + 2102.2471+6.12 = 2109.3764 + 2108.3671 ≈ 2109.9

queries and satisfies the conditions q2 = 102.2471 ≤ 103 and

2 · 109.3764 + 102.2471 ≈ 321.

The time cost of creating a transaction that honestly spends the covenant is 286.11 . The time
cost of constructing a transaction that cheats the covenant is 2109.9 . The means that for our proposed
parameters an attacker must do 223.79 = 14, 504, 500 times more work than an honest spender. Figure 8
(Right) shows how the cost in queries to honestly spend or attack our covenant changes for different
sizes of equivalence witness sizes.
The Bitcoin hash rate is roughly 700 exahashes/second. This is 269.25 hashes/second, 285.64
hash/day, 291.12 hashes/year. Honestly spending a covenant has work roughly in terms of number
of hash queries to roughly 33 hours of Bitcoin mining. Cheating such a covenant based on the best
attack we have developed costs 450, 136 years of the Bitcoin mining network.

Attacker with bounded space. Now we consider an attacker who does not have infinite space.
We assume they use the distinguished points approach to find 2p collisions. This only impacts step 1,
as we assume the attacker can store the 2p colliding pairs needed in step 2 because given the likely
values of ||ω|| + ||t|| the value 2p is will to be less than 264 . We shown above in step 1 we need to make
q = 2161−(||ω||+||t||)/2 queries to generate 2p = 2(159+1)−(||ω||+||t||) collisions. The +1 comes from the
fact that half the collisions are useless, so we need to double the number of collisions we are finding.
Using the distinguished points approach each collision costs an additional 2z time. This results in a
step 1 time cost of:
2161−(||ω||+||t||)/2 + 2z+160−(||ω||+||t||)
We need to store 2161−(||ω||+||t||)/2−z distinguished points and each distinguished point costs 20 −
(z/8) bytes for a total space cost of (20 − z/8) × 2161−(||ω||+||t||)/2−z bytes. We limit the attacker to
264 bytes, that is roughly 1 million 16-TB hard drives.

264 = (20 − z/8) × 2161−(||ω||+||t||)/2−z

Plugging in (||ω|| + ||t||) = 103 then:

264 = (20 − z/8) × 2161−103/2−z = (20 − z/8) × 2109.5−z

43
solving for z we get z = 49.29 which gives us a time cost for step 1

2(159−103)/2+81.5 + 249.29+160−103 = 2109.5 + 2106.29

These means that attackers with ≥ 264 space has roughly the same attack time cost as an attacker
with unlimited space. Not this only holds for a attacker than wants to break one covenant. An attacker
that has infinite space can reuse the work from step two in additional attacks by constructing a [Link]
lookup table.
Our analysis assumes that none of the pairs collide with other pairs as p < 80 this is unlikely. The
q = 2103 queries to [Link] will generate 22×103+160−1 = 2206−160−1 = 245 colliding outputs. These
colliding outputs from [Link] are wasted work, but 247 is so small we can ignore it.

44