Covenants are a construction to allow introspection: a transaction output can place conditions on the transaction which spends it (beyond the specific “must provide a valid signature of itself and a particular pubkey”).

My preferred way of doing instrospection is for Bitcoin Script have a way of asking for various parts of the transaction onto the stack (aka OP_TX) for direct testing (Fully Complete Covenants, as opposed to using some tx hash, forcing the Script to produce a matching hash to pass (Equality Covenants). In the former case, you do something like:

# Is the nLocktime > 100?
OP_TX_BIT_NLOCKTIME OP_TX 100 OP_GREATERTHAN OP_VERIFY

In the latter you do something like:

# They provide nLocktime on the stack.
OP_DUP
# First check it's > 100
100 OP_GREATERTHAN OP_VERIFY
# Now check it's actually the right value, by comparing its hash the hash of nLocktime
OP_SHA256
OP_TX_BIT_NLOCKTIME OP_TXHASH OP_EQUALVERIFY

However, when we come to examining an output’s ScriptPubkey, we’re forced into the latter mode unless we’re seeking an exact match: the ScriptPubkey is (almost always) a one-way function of the actual spending conditions.

Making a Simple Taproot, in Script

Let’s take a simple taproot case. You want to assert that the scriptPubkey pays to a known key K, or a script given by the covenent spender. This is the simplest interesting form of Taproot, with a single script path.

The steps to make this into a ScriptPubkey (following BIP 341) are:

  1. Get a tagged tapleaf hash of the script
  2. Tweak the key K by this value.
  3. Prepend two bytes “0x51 0x20”.
  4. Compare with the ScriptPubkey of this tx.

Step 1: We need OP_CAT, or OP_MULTISHA256

If we spell out the things we need to hash, it looks like:

SHA256(SHA256("TapLeaf") + SHA256("TapLeaf") + 0xC0 + CSCRIPTNUM(LEN(script)) + script)

CSCRIPTNUM(X) is (if X is in canonical form, as it will be from OP_SIZE):

  • if X is less than 253:
    • X
  • otherwise, if the length is less than 256:
    • 0xFD 0x00 X
  • otherwise, if the length is less than 65536:
    • 0xFD X
  • otherwise, we don’t care, make shorter scripts!

The obvious way to do this is to enable OP_CAT, but this was removed because it allows construction of giant stack variables. If that is an issue, we can instead use a “concatenate-and-hash” function OP_MULTISHA256, which turns out to be easiest to use if it hashes the stack from top to bottom.

OP_MULTISHA256 definition:

  1. If the stack is empty, fail.
  2. Pop N off the stack.
  3. If N is not a CScriptNum, fail.
  4. If there are fewer than N entries on the stack, fail.
  5. Initialize a SHA256 context.
  6. while N > 0:
    1. Pop the top entry off the stack.
    2. Hash it into the SHA256 context
    3. Decrement N
  7. Finish the SHA256 context, and push the resulting 32 bytes onto the stack.

The result is either:

# Script is on stack, produce tagged tapleaf hash

# First, encode length
OP_SIZE
OP_DUP
# < 253?
OP_PUSHDATA1 1 253 OP_LESSTHAN 
OP_IF
	# Empty byte on stack:
	0
OP_ELSE
	OP_DUP
	# > 255?
	OP_PUSHDATA1 1 0xFF OP_GREATERTHAN 
	OP_IF
		OP_PUSHDATA1 1 0xFD
	OP_ELSE
		# Needs padding byte
		OP_PUSHDATA1 2 0xFD 0x00
	OP_ENDIF
OP_ENDIF

# Push 0xC0 leaf_version on stack
OP_PUSHDATA1 1 0xC0

# Push hashed tag on stack, twice.
OP_PUSHDATA1 7 "TapLeaf"
OP_SHA256
OP_DUP

# Now, hash them together
6 OP_MULTISHA256

Or, using OP_CAT (assuming it also concatenates the top of stack to second on stack):

# Script is on stack, produce tagged tapleaf hash

# First, encode length
OP_SIZE
OP_DUP
# < 253?
OP_PUSHDATA1 1 253 OP_LESSTHAN 
OP_NOTIF
	OP_DUP
	# > 255?
	OP_PUSHDATA1 1 0xFF OP_GREATERTHAN 
	OP_IF
		OP_PUSHDATA1 1 0xFD
	OP_ELSE
		# Needs padding byte
		OP_PUSHDATA1 2 0xFD 0x00
	OP_ENDIF
	OP_CAT
OP_ENDIF
# Prepend length to script
OP_CAT

# Prepend 0xC0 leaf_version
OP_PUSHDATA1 1 0xC0
OP_CAT

# Push hashed tag on stack, twice, and prepend
OP_PUSHDATA1 7 "TapLeaf"
OP_SHA256
OP_DUP
OP_CAT
OP_CAT

# Hash the lot.
OP_SHA256

Step 2: We need to Tweak a Key, OP_KEYADDTWEAK

Now, we need to tweak a public key, as detailed in BIP 341:

def taproot_tweak_pubkey(pubkey, h):
    t = int_from_bytes(tagged_hash("TapTweak", pubkey + h))
    if t >= SECP256K1_ORDER:
        raise ValueError
    P = lift_x(int_from_bytes(pubkey))
    if P is None:
        raise ValueError
    Q = point_add(P, point_mul(G, t))
    return 0 if has_even_y(Q) else 1, bytes_from_int(x(Q))

Let’s assume OP_KEYADDTWEAK works like so:

  1. If there are less than two items on the stack, fail.
  2. Pop the tweak t off the stack. If t >= SECP256K1_ORDER, fail.
  3. Pop the key P off the stack. If it is not a valid compressed pubkey, fail. Convert to Even-Y if necessary. (i.e. lift_x()).
  4. Q = P + t*G.
  5. Push the X coordinate of Q on the stack.

So now we just need to create the tagged hash, and feed it to OP_KEYADDTWEAK:

# Key, tapscript hash are on stack.

OP_OVER
OP_PUSHDATA1 8 "TapTweak"
OP_SHA256
OP_DUP

# Stack is now: key, tapscript, key, H(TapTweak), H(TapTweak)
4 OP_MULTISHA256
OP_KEYADDTWEAK

Or with OP_CAT instead of OP_MULTISHA256:

# Key, tapscript hash are on stack.

OP_OVER
OP_PUSHDATA1 8 "TapTweak"
OP_SHA256
OP_DUP

# Stack is now: key, tapscript, key, H(TapTweak), H(TapTweak)
OP_CAT
OP_CAT
OP_CAT
OP_SHA256
OP_KEYADDTWEAK

Step 3: We Need To Prepend The Taproot Bytes

This is easy with OP_CAT:

# ScriptPubkey, Taproot key is on stack.

# Prepend "OP_1 32" to make Taproot v1 ScriptPubkey
OP_PUSHDATA1 2 0x51 0x20
OP_CAT
OP_EQUALVERIFY

With OP_MULTISHA256 we need to hash the ScriptPubkey to compare it (or, if we only have OP_TXHASH, it’s already hashed):

# ScriptPubkey, Taproot key is on stack.

OP_SHA256
# Prepend "OP_1 32" to make Taproot v1 ScriptPubkey
OP_PUSHDATA1 2 0x51 0x20
2 OP_MULTISHA256

# SHA256(ScriptPubkey) == SHA256(0x51 0x20 taproot)
OP_EQUALVERIFY

Making a More Complete Taproot, in Script

That covers the “one key, one script” case.

If we have more than one taproot leaf, we need to perform the merkle on them, rather than simply use the taproot leaf directly. Let’s assume for simplicity that we have two scripts:

  1. Produce the tagged leaf hash for scripts, call them H1 and H2.
  2. If H1 < H2, merkle is TaggedHash("TapBranch", H1 + H2), otherwise TaggedHash("TapBranch", H2 + H1)

Step 1: Tagged Hash

We’ve done this before, it’s just Step 1 as before.

Step 2: Compare and Hash: We Need OP_LESS or OP_CONDSWAP

Unfortunately, all the arithmetic functions except OP_EQUAL only take CScriptNums, so we need a new opcode to compare 32-byte blobs. Minimally, this would be OP_LESS, though OP_CONDSWAP (put lesser one on top of stack) is possible too. In our case we don’t care what happens in unequal lengths, but if we assume big-endian values are most likely, we could zero-prepend to the shorter value before comparing.

The result looks like this:

# Hash1, Hash2 are on the stack.

# Put lesser hash top of stack if not already
OP_LESS
OP_NOTIF OP_SWAP OP_ENDIF

OP_PUSHDATA1 9 "TapBranch"
OP_SHA256
OP_DUP

4 OP_MULTISHA256

Or, using OP_CAT and OP_CONDSWAP:

# Hash1, Hash2 are on the stack.

# Put lesser hash top of stack if not already
OP_CONDSWAP

OP_PUSHDATA1 9 "TapBranch"
OP_SHA256
OP_DUP

OP_CAT
OP_CAT
OP_CAT
OP_SHA256

So now we can make arbitrarily complex merkle trees from parts, in Script!

Making More Useful Templates: Reducing the Power of OP_SUCCESS

Allowing the covenant spender to specify a script branch of their own is OK if we simply want a condition which is “… OR anything you want”. But that’s not generally useful: consider vaults, where you want to enforce a delay, after which they can spend. In this case, we want “… AND anything you want”.

We can, of course, insist that the script they provide starts with 1000 OP_CHECKSEQUENCEVERIFY. But because any unknown opcode causes immediate script success (without actually executing anything), they can override this test by simply inserting an invalid opcode in the remainder of the script!

There are two ways I can see to resolve this: one is delegation, where the remainder of the script is popped off the stack (OP_POPSCRIPT?). You would simply insist that the script they provide be exactly 1000 OP_CHECKSEQUENCEVERIFY OP_POPSCRIPT.

The other way is to weaken OP_SUCCESSx opcodes. This must be done carefully! In particular, we can use a separator, such as OP_SEPARATOR, and change the semantics of OP_SUCCESSx:

  • If there is an OP_SEPARATOR before OP_SUCCESSx:
    • Consider the part before the OP_SEPARATOR:
      • if (number of OP_IF) + (number of OP_NOTIF) > (number of OP_ENDIF): fail
      • Otherwise execute it as normal: if it fails, fail.
  • Succeed the script

This insulates a prefix from OP_SUCCESSx, but care has to be taken that it is a complete script fragment: a future OP_SUCCESSx definition must not turn an invalid script into a valid one (by revealing an OP_ENDIF which would make the script valid).

Summary

I’ve tried to look at what it would take to make generic convenants in Script: ones which can meaningfully interrogate spending conditions assuming some way (e.g. OP_TXHASH) of accessing an output’s script. There are reasons to believe this is desirable (beyond a completeness argument): vaulting in particular requires this.

We need three new Script opcodes: I’ve proposed OP_MULTISHA256, OP_KEYADDTWEAK and OP_LESS, and a (soft-fork) revision to treatment of OP_SUCCESSx. None of these are grossly complex.

The resulting scripts are quite long (and mine are untested and no doubt buggy!). It’s 41 bytes to hash a tapleaf, 19 to combine two tapleaves, 8 to compare the result to the scriptpubkey. That’s at least 109 witness weight to do a vault, and in addition you need to feed it the script you’re using for the output. That seems expensive, but not unreasonable: if this were to become common then new opcodes could combine several of these steps.

I haven’t thought hard about the general applicability of these opcodes, so there may be variants which are better when other uses are taken into account.

Thanks for reading!