# Introduction

This is the first in a series of posts about about covenants in Bitcoin
using Taproot and a (hypothetical) `CAT`

opcode. Historically, and as has
been implemented in Elements,
`CAT`

has been considered to be a covenant opcode only in conjunction with
`CHECKSIGFROMSTACK`

. In this post, which will be much mathier than later ones,
we'll talk about how to abuse the math of Schnorr signatures to emulate the
functionality of `CHECKSIGFROMSTACK`

.

First, some preliminaries. A **covenant** is a hypothetical Bitcoin Script
which restricts the form of the transaction spending the coins. Ordinarily,
Script can only require the presence of certain authentication data for
spending: signatures, hashlock checks, etc. Script cannot enforce velocity
limits, restrict coins to going to certain locations, or anything like that,
because the Script execution environment does not have access to transaction
data. Ultimately, adding covenants to Bitcoin would mean adding the ability
to introspect transactions to Script.

Secondly, `CAT`

is the "concatenation" opcode. Originally present in Bitcoin
but quietly removed in 2010,
`CAT`

takes two elements from the stack, concatenates them, and pushes the
result onto the stack. It can be used to assemble large stack items from
small ones, or to split large items into smaller ones. `CHECKSIGFROMSTACK`

,
which has never been in Bitcoin, is an opcode which allows the user to
check signatures on arbitrary data, unlike the `CHECKSIG`

opcode which checks
a signature on the spending transaaction.

The combination of `CAT`

and `CHECKSIGFROMSTACK`

gives you transaction introspection
in a somewhat clever way: the user provides data for the entire transaction on the
stack; using `CAT`

, the script bundles this all up into one item, which it hashes
and passes to `CHECKSIGFROMSTACK`

to validate a signature on the data. It then
passes the **same signature**, with the same key, to `CHECKSIG`

.If both checks
pass, the user-provided transaction data must have been the actual transaction data.
It is then straightforward to use Script to do whatever checks on this data your
covenant requires.

# ECDSA and Almost-Covenants

Suppose we had `CHECKSIGFROMSTACK`

but not `CAT`

. Then in principle, we could do
a very simple sort of covenant: one where the user provides the **hash** of all
the transaction data and the script checks a signature on this using both `CHECKSIG`

and `CHECKSIGFROMSTACK`

. Without `CAT`

, the script can't recompute the hash from
individually-checkable data, so all it can really do is check the hash for equality
against a specific value, meaning the coins are restricted such that they can only
be spent by a single specific transaction.

It is straightforward to generalize this to a choice of a small number of transactions, but open-ended predicates like "any transaction whose outputs are less than 1 BTC" are out of the question.

It turns out this sort of covenant can't work, for a technical reason: the
transaction data that `CHECKSIG`

checks always includes the txid of the previous
transaction, which is a hash of (among other things) the covenant script itself.
(This isn't quite true because of the `SIGHASH_SINGLE`

bug but for our purposes this
doesn't help anything.) So to be effective, the script would need to include its
own hash, which is impossible.

What makes this observation interesting is that Bitcoin today actually has a way to
get the transaction hash onto the stack like this, which means that if it weren't
for this hash circularity problem, Bitcoin would have Covenants today. And if there
were a way to sign transaction data that didn't include data from the previous transaction,
for example, using the `SIGHASH_NOINPUT`

proposal which is so popular in the Lightning
Network world, Bitcoin would have covenants. Let's see how this works:

ECDSA signatures work as follows: you have a keypair $(x, P = xG)$ which are your signing and verification keys, respectively. If you're not familiar with the mapping $x\mapsto xG$, it maps scalars (integers modulo some large prime) to elliptic curve points (pairs of integers modulo some different prime, which satisfy some particular equation). What's important is (a) it's homomorphic, so $(x + y)G = xG + yG$, and (b) it's believed to be impossible to reverse without a quantum computer. Aside from these two facts it's not important what this mapping looks like on an algorithmic level; we'll just treat it as a black box.

To produce an ECDSA signature, you generate an ephemeral keypair $(k, R = kG)$ then compute
the value $r$ which is the first component of the point $R$, coerced from an integer modulo
the non-scalar prime to an integer modulo the scalar prime. (This design decision was made
for legal reasons, by the way -- incomprehensibility counts as novelty, for patent purposes,
so this design did not violate any existing patents.) You then compute the value
$$ s = k^{-1}(H + rx) $$
where $H$ is the hash of your transaction data. Let's rearrange this by multiplying both sides
by $k$ then running everything through the $\cdot\mapsto\cdot G$ map:
$$ skG = HG + rxG $$
which, for greater clarity, is
$$ sR = HG + rP $$
Rearranging one more time, we get
$$ P = r^{-1}(sR - HG) $$
which, for fixed $R$ and $s$, is a cryptographic hash of the transaction data as long as $H$
is. As it happens, Bitcoin Script has an opcode for "for fixed $R$ and $s$, compute $H$ and
give me such a $P$": `CHECKSIG`

.

Concretely, consider the script `DUP <fixed signature> SWAP CHECKSIGVERIFY`

. This can only
be satisfied if the user puts a satisfying pubkey $P$ on the stack. The script duplicates
it, swaps it with a fixed signature, then calls `CHECKSIGVERIFY`

on `<sig> <P>`

. If the
above equation is satisfied, these are consumed, leaving the copy of $P$ on the stack. If
not, the script fails and the transaction is invalid.

There are two lessons to take from this: first, that it is really easy to get covenants in Bitcoin; second, by abusing the algebra of digital signatures, it's possible to get transaction data onto the stack using signature-checking opcodes.

# BIP340 Signatures and Key-Prefixing

Taproot includes a variant of Schnorr signature called a **BIP340 signature**. These signatures
use the same keys, same elliptic curve, and same group of scalars, but the signing algorithm
is much simpler: you compute the ephemeral $(k, R = kG)$ just like before, but this time
$$ s = k + xe $$
where $e$ is a hash of your public key $P$, the ephemeral key $R$, and the transaction data.
Recall that the reason we couldn't get covenants from ECDSA was that our script would wind
up going into the transaction data, so any target values for $P$ would wind up in our message
hash, but since $P$ itself was supposed to be the hash, we had a circularity and we were stuck.

It would appear that BIP340 puts the nail in the coffin of this style of covenant: $P$ shows up explicitly in the signature hash, so no matter what crazy future sighashing schemes might get included in Bitcoin, this circularity will remain and we are stuck. In fact, this inclusion of $P$ means that BIP340 signatures aren't just signatures, but "signatures of knowledge". This is a term of art which means, roughly, that you are not able to run these signatures backward in any sense. For a long time, I thought this meant that I couldn't abuse BIP340 signatures to get non-signature behavior out of them.

In fact, I was wrong, although I need `CAT`

to get really interesting behavior. The trick is
that, while I can't fix `s`

and `R`

to get a transaction hash out of `P`

, I **can** fix `R`

and `P`

to get a transaction hash out of `s`

. And in fact, the resulting transaction hash is
a "real" hash, in the sense that there aren't any un-Script-able elliptic curve ops involved
in it.

Let's be specific: consider the script `<G> 2DUP SWAP CAT SWAP CHECKSIG`

. This

- takes as input the
`s`

value of the signature, so our stack is simply`s`

; `<G> 2DUP`

adds a fixed`R`

value and duplicates both parts, leaving`s <G> s <G>`

`SWAP CAT`

swaps one copy and concatenates to produce a full signature, leaving the stack as`s <G> <G>s`

`SWAP`

moves the other`<G>`

in place to act as a pubkey, so the stack is`s <G>s <G>`

`CHECKSIG`

interprets the top`<G>`

as a public key, which it verifies the signature`<G>s`

with, consuming both- Now only
`s`

is on the stack.

(Thanks to Dmitry Petukhov for this script, which is smaller than the original one that I had proposed.)

Yikes. What is going on here? Well, the step where we force both $R$ and $P$ to be the
group generator is equivalent to forcing our secret keys $x$ and $k$ to be 1. Our BIP340
signature equation is then
$$ s = 1 + e $$
i.e. the $s$ that our script leaves on the stack is actually a SHA256 hash of our
transaction data, prefixed by a couple copies of $G$ (and a couple copies of
`SHA256("BIP0340")`

because BIP340 loves itself). Veeery interesting. Script has
an opcode `SHA256`

, and we have `CAT`

in the hypothetical world of this post, so
if we could somehow deal with this +1, we'd be able to have the user provide transaction
data which we could constrain then validate against this hash, just like if we had
`CHECKSIGFROMSTACK`

.

In fact this +1 is super easy to deal with. We just require the user grind her transaction
data until the actual hash ends in the byte `01`

, which is pretty cheap (takes 256 tries
on average, which at 250ns per shot would take 64 microseconds, comparable to the signing
algorithm itself). Then her `s`

value will end it 2, which we enforce by asking her to
leave it off; we'll add it ourselves. Concretely we add a `2 CAT`

after the `2DUP`

in our
script, where we're computing $s$ for the signature check, and `1 CAT`

to the end of our
script where we want the result to be our transaction hash. VoilĂ .

## Next Steps

This has been a trip: it turns out that the BIP340 signatures in Taproot, while designed
to be more "covenant-proof" than the old-school ECDSA signatures, actually leave us much
closer to covenants. Indeed, all we need is `CAT`

to get `CAT`

+`CHECKSIGFROMSTACK`

-style
covenants.

However, there is a problem if we hope to construct recursive covenants, which dynamically restrict transaction output scripts to follow certain tempates. In Taproot, transaction outputs are EC public keys, which commit to scripts using an elliptic-curvy hash we don't have in Script. ...Or do we?

I believe the answer is no, but I also believe that we can do some very interesting things with this nonetheless.

A natural question to ask is, are these sighash-templating covenants powerful enough to
actually do anything, given the consensus limits of Script? Readers may recall that we
blogged at Blockstream four years ago
about this but never followed up with practical applications. My belief now is that the
dearth of applications was more a consequence of the incredible difficulty of reasoning
about and constructing Script, and that Miniscript
has since provided some new ways of thinking that will accellerate this kind of development.
And indeed, if you really want to dig into Script, you can construct some pretty cool
things with `CHECKSIGFROMSTACK`

.

In our next posts, we'll talk about how to use auxiliary inputs to simulate `SIGHASH_NOINPUT`

and enable constant-sized backups for Lightning channels, and how to use "value-switching"
to construct Vaults.

In our final post we'll talk about ad-hoc extensions of Miniscript, and how to develop software for these constructions in a maintainable way.