Unfortunately, when we actually try to use this upgrade flexibility (for OP_CHECKTEMPLATEVERIFY
or OP_TXHASH
for example) we quickly find as Steven Roose pointed out to me that users also want a neutered Segwit v0 variant: using Tapscript requires a 33 byte penalty over simple P2WSH!
The fix is both simple and annoying: allowing the BIP-341 control block to be empty (or, perhaps, 32*m
bytes) to indicate the key is the NUMS point lift_x(0x50929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0)
as suggested by BIP-341. BIP-341 suggests using a tweak of this key, which hides the existence of the script (if it were guessable) but forcing this at users expense was a mistake given the existence of P2WSH.
Regrettably, allowing this simple change requires (I think) using a Segwit version of 2, since BIP-341 defines v1 to fail if the control block is not an accepted length. Others might have an idea if we want to roll in other changes at that point.
Enjoy!
]]>Lightning uses this kind of “anchor” construction, and although it’s only used in the forced-closure case, it’s wasteful of onchain space when it happens. It also uses a “bring your own fee” construction for HTLC transactions, using SIGHASH_SINGLE|SIGHASH_ANYONECANPAY
which means only the input and outputs are fixed, and the operation of this is much smoother in general.
(It’s not coincidence that my main contribution to the Eltoo construction was to use a similar single-input/output scheme to allow such last-minute fee binding and RBF).
More recently, Peter Todd argues that such inefficient fee bumping is a threat to decentralization as it creates significant incentive to use out-of-band fees, which would have to be paid in advance and thus would favor large miners.
If you carefully construct your covenant to allow addition of a fee input (and usually a change output) later, you can avoid the expense of a child transaction and put the fees inline.
If you’re really clever, you can combine multiple covenant transactions into one transaction, and add a fee input/change output to all of them at once and reduce total costs even more. I call this stacking, and my thesis is that Bitcoin fees will rise and eventually make such joining profitable, normal and necessary.
Note that such stacking requires real engineering work: we’ve seen how long it took Bitcoin exchanges to implement even simple batching! And for full disclosure: stacking like this is already possible with Lightning with anchor outputs and HTLC transactions, which are signed with SIGHASH_SINGLE|SIGHASH_ANYONECANPAY
, and yet I still haven’t implemented stacking in Core Lightning!
I now want to discuss the dangers of doing this incorrectly, and how OP_TXHASH
can support doing it in various scenarios.
I vaguely recall first learning of this attack in the context of signing devices, but I cannot find a reference. ~I’ll add one when some clever reader points it out!~ Greg Sanders’s post Hardware Wallet attacks by input ownership omission and fix though I may have cribbed it from Bitcoin OpTech (Greg he also mentioned jl2012 may have been involved).
Consider a transaction designed to take a 1BTC input and pay Bob 0.1BTC, with the remaining 0.9BTC going to a change address. Your software asks a signing device to sign the first input. It checks the input, checks the outputs are correct, prompts the user (telling it we’re paying Bob 0.1BTC) and signs it.
Now consider a transaction which has two identical inputs. Our naive signing device, asked to sign the first input, would see it as valid, and sign it. If we then ask it to sign the second input it would also see it as valid, and sign it. But the transaction would actually pay 1BTC to fees!
I call this a “Partial Validation Attack”, and the same problem can occur with stacking! In this case, it’s the covenant checking the input, not the hardware wallet. If it does not check other inputs (because it wants to allow you to add fees and/or stack other transactions together), and it would allow other covenants to validate the same outputs, it is vulnerable.
Imagine you want to create a covenant that forces a transaction to pay all its input amount to a given address, and you have OP_TXHASH
and OP_CAT
.
You want it to stack, so you simply validate that output #0 go to the given address, and that the amount match the input amount of the current input. This is fairly easy, you can either use OP_TXHASH
to get the hashed amount from output #0, and again from the input and compare, or require the output supply the amount on the stack, duplicate it and hash it, then call OP_TXHASH
to hash the output #0 amount and the current input amount, and make sure that’s what they provided.
Then when you want to spend it, you can pay fees by adding as many inputs (and outputs) as you need without invalidating the transaction.
Now, you create two 1BTC outputs to this covenant address. Mallory creates a transaction which spends both at once: it pays 1BTC to your required address (output #0) and sends the other 1BTC to their own address, stealing your funds. Both inputs’ covenants check that output #0 pays the full amount to the required address, and are satisfied. Oops!
This can avoided in one of four ways:
Of these options, only the final one (relative output addressing) allows stacking, so obviously that’s my preferred approach.
Unfortunately, this stacking is only possible with current OP_TXHASH
if the number of inputs is equal to the number of outputs. This can often be arranged, but any shared UTXO arrangement results in multi-in-single-out and single-in-multi-out. Can we do better?
We can imagine OP_TXHASH
supporting an indexing scheme which lets you refer to “output = input-number * N” (I proposed this as a possibility in my BIP review). (We can also imagine OP_TX
which would let you push the current input number on the stack directly, to do this calculation yourself!).
This would let us stack have several 1-input/2-output txs. But it wouldn’t let us stack different topologies, like a 1-in/2-out on top of a 2-in/1-out tx.
I considered adding an “output accumulator” where some OP_TXHASH field selector would increment the “next output” counter. But writing it up I realized that this fails in the presence of OP_SUCCESS
which can cause an input to be skipped; that would be a hard fork!
If we really want to do this in general, we would need to flag how many outputs each input “owns”, such as in the nSequence
field. And then have a “relative to owned outputs” modifier in OP_TXHASH
. As nSequence
bits are limited and this would irreversibly consume some, I am reluctant to propose this unless real world usage of covenants (i.e. after they’re enabled by a soft-fork) shows it would have real onchain benefits.
You can imagine handing the output number(s) in the witness (and changing them when you stack the transactions), but that re-introduces the “partial transaction” bug. Similarly, providing multiple signatures for different stacking cases would expose you to the issue.
I believe stacking transactions is going to become popular to reduce fees: while this is currently easy for 1-input-1-output transactions, and the OP_TXHASH
proposal makes it possible for N-input-N-outputs, I suspect the N-inputs-1-output an 1-input-N-output cases will be common (shared UTXOs), so we should try to allow those. It would also be nice to design such that we can allow nSequence bits to indicate the number of associated outputs in a future soft fork.
The problem with this is that in Taproot scripts, any unknown opcode (OP_SUCCESSx
) will cause the entire script to succeed without being executed, so we need to hobble this slightly. My previous proposal of some kind of separator was awkward, so I’ve developed a new idea which is simpler.
Currently, the entire tapscript is scanned for the OP_SUCCESS
opcodes, and succeeds immediately if one it found. This would be modified:
OP_SEGMENT
or OP_SUCCESSx
.OP_SEGMENT
is found, the script up to that point is executed. If the script does not fail, scanning continues from that point.OP_SUCCESSx
is found, the script succeeds.This basically divides the script into segments, each executed serially. It’s not quite as simple as “cut into pieces by OP_SEGMENT and examine one at a time” because the tapscript is allowed to contain things which would fail to decode altogether, after an OP_SUCCESSx
, and we want to retain that property.
When OP_SEGMENT
is executed, it does nothing: it simply limits the range of OP_SUCCESS
opcodes.
The ExecuteWitnessScript
would have to be refactored (probably as a separate ExecuteTapScript
since 21 of its 38 lines are an “if Tapscript” anyway), and it also implies that the stack limits for the current tapscript would be enforced upon encountering OP_SEGMENT
, even if OP_SUCCESS
were to follow after.
Interestingly, the core EvalScript
function wouldn’t change except to ignore OP_SEGMENT
, as it’s already fairly flexible.
Note that I haven’t implemented it yet, so there may yet be surprises, but I plan to prototype after the idea has received some review!
Enjoy!
]]>This makes it obvious that we want 64-bit-capable opcodes, and it makes sense to restore disabled opcodes such as OP_AND
/OP_OR
/OP_XOR
/OP_INVERT
, as well as OP_LSHIFT
, OP_RSHIFT
and maybe OP_LEFT
, OP_RIGHT
and OP_SUBSTR
.
Blockstream’s Elements codebase is ahead here, with a full set of 64-bit opcodes available for Liquid. All these operations push a “success” flag on the stack, designed that you can follow with an OP_VERIFY
if you want to assert against overflow. They then provide three conversion routines, to convert to and from CScriptNum, and one for converting from 32-bit/4-byte values.
But frankly, these are ugly. We need more than 31 bits for satoshi amounts, and we may never need more than 64 bits, but the conversions and new opcodes feel messy. Can we do better?
Script amounts are variable length, which is nice when space matters, but terribly awkward for signed values: using the high bit of the last byte, this being little-endian, requires a 0 padding byte if the high bit would otherwise be set. And using negative numbers is not very natural (pun intended!), since we have OP_SUB
already.
What if we simply used unsigned, variable-length little-endian numbers? These are efficient, retain compatibility with current unsigned Script numbers, and yet can be extended to 64 bits or beyond, without worrying about overflow (as much).
I propose OP_ADDV
, which simply adds unsigned two little-endian numbers of arbitrary length. 64 bits is a little simpler to implement, but there are a number of useful bit tricks which can be done with wide values and I can’t see a good reason to add a limit we might regret in future.
OP_SUBV
would have to be Elements-style: pushing the absolute result on the stack, then a “success” flag if the result isn’t negative (effectively, a positive sign bit).
If OP_CAT
is not limited to 520 bytes as per OP_CAT beyond 520 bytes, then we could make OP_ADDV
never fail, since the effective total stack size as per that proposal could not be increased by OP_ADDV
(it consumes its inputs). But that introduces the problem of DoS, since on my laptop 2 million iterations (an entire block) of a mildly optimized OP_ADDV
of 260,000 bytes would take 120 seconds.
Thus, even if we were to allow more then 520 byte stack elements, I would propose either limiting the inputs and outputs to 520 bytes, or simply re-using the dynamic hash budget proposed in that post for arithmetic operations.
Restoring OP_MUL
to apply to variable values is harder, since it’s O(N^2) in the size of the operands: it performs multiple shifts and additions in one operation. Yet both this and OP_DIV
are useful (consider the case of calculating a 1% fee).
I suggest this is a good case for using an Elements-style success flag, rather than aborting the script. This might look like:
0
0
.OP_DIV
, if the divisor is 0, push 0
0
.OP_MUL
, if the output overflows, push 0
0
.1
.Both GCC and clang support an extension for 128 bit operations via __uint128_t
, so this implementation is fairly trivial (OP_MUL
overflow detection is assisted greatly by __builtin_mul_overflow
extension in GCC and clang).
OP_LSHIFT
and OP_RSHIFT
would now be restored as simple bit operations (there’s no sign bit), treating their argument as unsigned rather than a signed amount. OP_LSHIFT
would fail if the result would be excessive (either a 520 byte limit, or a dynamic hash budget limit). Neither would normalize, leaving zero bytes at the front. This is useful when combined with OP_INVERT
to make a mask (0
OP_ADDV
can be used to normalize if you want).
OP_LEFT
, OP_SUBSTR
and OP_RIGHT
should probably return empty on out-of-range arguments rather than failing (I’m actually not sure what the original semantics were, but this is generally sensible).
OP_EQUAL
just works, but we need at least a new OP_GREATERTHANV
, and I suggest the full complement: OP_GREATERTHANOREQUALV
, OP_LESSTHANV
and OP_LESSTHANOREQUALV
.
Regretfully, our comparison opcodes don’t work as OP_LESS
which is required for Merkle Tree construction to examine scripts: the SHA256 hashes there need to be compared big-endian, not little endian! So I suggest OP_BYTEREV
: this adds some overhead (reverse both merkle hashes to compare them), but is generally a useful opcode to have anyway.
We can extend current bitcoin script numbers fairly cleanly by having new opcodes which deal with variable-length little-endian unsigned numbers. The limits on most of these can be quite large, but if we want excessive limits (> 520 bytes) we need to have a budget like the checksig budget.
We can deal easily with current CScriptNum numbers, 32-bit numbers used by nLocktime, and 64-bit numbers used by satoshi amounts.
The soft fork would restore the following opcodes:
And add the following new ones:
This would make it far easier to deal with numeric fields to bring covenant introspection to its full potential (e.g. OP_TXHASH
).
[^simplified] The original versions preserved sign, but we don’t have that. [^extended] These apply to unsigned numbers up to 128 bits, not just signed 31 bit values as the originals did.
]]>OP_CAT
proposal limited the result to be 520 bytes, but
we want more for covenents which analyze scripts (especially since
OP_CAT
itself makes scripting more interesting).
My post showed that it’s fairly simple to allow larger sizes (instead of a limit of 1000 stack elements each with a maximum of 520 bytes each, we reduce the element limit for each element over 520 bytes such that the total is still capped the same).
But consider hashing operations, such as OP_SHA256
. Prior to OP_CAT
,
it can only be made to hash 520 bytes (9 hash rounds) with three
opcodes:
OP_DUP
OP_SHA256
OP_DROP
That’s 3 hash rounds per opcode. With OP_CAT
and no 520 byte stack
limit we can make a 260,000 byte stack element, and that’s 4062 hash
rounds, or 1354 per opcode, which is 450x as expensive so we
definitely need to think about it!
A quick benchmark shows OpenSSL’s sha256 on my laptop takes about 115 microseconds to hash 260k: a block full of such instructions would take about 150 seconds to validate!
So we need to have some limit, and there are three obvious ways to do it:
OP_CAT
to produce more than 520 bytes.OP_CAT
, but still less than 260,000.A quick benchmark on my laptop shows that we can hash about 48k (using the OpenSSL routines) in the time we do a single ECDSA signature verification (and Taproot charges 50 witness weight for each signature routine).
A simple limit would be to say “1 instruction lets you hash about 1k”
and “the tightest loop we can find is three instructions” and so limit
OP_CAT
to producing 3k. But that seems a little arbitrary, and still
quite restrictive for future complex scripts.
A dynamic BIP-342-style approach would be to have a “hashing budget” of some number times the total witness weight. SHA256 uses blocks of 64 bytes, but it is easier to simply count bytes, and we don’t need this level of precision.
I propose we allow a budget of 520 bytes of hashing for each witness byte: this gives us some headroom from the ~1k measurement above, and cannot make any currently-legal script illegal, since the opcode itself would allow the maximal possible stack element.
This budget is easy to calculate: 520 times total witness weight, and
would be consumed by every byte hashed by OP_RIPEMD160
, OP_SHA1
,
OP_SHA256
, OP_HASH160
, OP_HASH256
. I’ve ignored that some of these
hash twice, since the second hash amounts to a single block.
Could this budget ever be limiting to future scripts? Not for the case of “your script must look like {merkle tree of some template}” since the presence of the template itself weighs more than enough to allow the hashing. Similarly for merkle calculations, where the neighbor hashes similarly contribute more than enough for the hash operations.
If you provide the data you’re hashing in your witness, you can’t
reasonably hit the limit. One could imagine a future OP_TX
which let
you query some (unhashed) witness script of (another) input, but even
in this case the limit is generous, allowing several kilobytes of hashing.
Hashing is the obvious case, but several other opcodes work on
arbitrary length elements and should be considered. In particular,
OP_EQUAL
, OP_EQUALVERIFY
, the various DUP opcodes, and OP_CAT
itself.
I would really need to hack bitcoind to run exact tests, but modifying my benchmark to do a memcmp of two 260,000 byte blobs takes 3100ns, and allocating and freeing a copy takes 3600.
The worst case seems to be arranging for 173k on the stack then repeatedly doing:
OP_DUP
OP_DUP
OP_EQUALVERIFY
4MB of this would take about 8.9 seconds to evaluate on my laptop. Mitigating this further would be possible (copy-on-write for stack objects, or adding a budget for linear ops), but 10 seconds is probably not enough to worry about.
]]>I previously looked at Examining ScriptPubkeys, but another useful thing covenants want to enforce is amounts. This is easy for equality, but consider the case where you are allowed to merge inputs: perhaps the first output amount must be the sum of the first and second inputs.
The problem is that Bitcoin Script deals in signed ones-complement values, and 31 bits limits us to 21.47483648 bitcoin. However, using OP_MULTISHA256
or OP_CAT
, it’s possible to deal with full amounts. I’ve written some (untested!) script code below.
Using OP_TXHASH
, we can get SHA256(input amount) and SHA256(output amount) on the stack. Since this involves hashing, we can’t evaluate the number for anything but equality, so as in other cases where we don’t have Fully Complete Covenants we need to have the user supply the actual values on the witness stack, and we test those for the conditions we want, and then make sure they match what OP_TXHASH
says is in the transaction. I usually object to this backwards form (just give me the value on the stack!), but as you’ll see, we couldn’t natively use 64 bit values from OP_TX
anyway (I had proposed pushing two values, which is its own kind of ugly).
21M BTC is just under 2^51 satoshis.
We split these bits into a pair of stack values:
I call this tuple “Script-friendly pair” (SFP) form. Note that all script numbers on stack are represented in little-endian, with a sign bit (0x80 on the last byte). This is a nasty format to work with, unfortunately.
Here’s the code to takes a positive CScriptNum, and produces two stack values which can be concatenated to make a 4 byte unsigned value:
# !UNTESTED CODE!
# Stack (top to bottom): lower, upper
OP_SWAP
# Generate required prefix to append to stack value to make it 4 bytes long.
OP_SIZE
OP_DUP
OP_NOTIF
# 0 -> 00000000
OP_DROP
4 OP_PUSHDATA1 0x00 0x00 0x00 0x00
OP_ELSE
OP_DUP
1 OP_EQUAL OP_IF
# Single byte: prepend 0x00 0x00 0x00
OP_DROP
3 OP_PUSHDATA1 0x00 0x00 0x00
OP_ELSE
OP_DUP
2 OP_EQUAL OP_IF
# Two bytes: prepend 0x00 0x00
2 OP_PUSHDATA1 0x00 0x00
OP_ELSE
3 OP_EQUAL OP_IF
# Three bytes: prepend 0x00
1 OP_PUSHDATA1 0x00
OP_ELSE
# Prepend nothing.
0
OP_ENDIF
OP_ENDIF
OP_ENDIF
OP_ENDIF
OP_SWAP
# Stack (top to bottom): upper, pad, lower
That 46 bytes handles upper. Now lower is a CScriptNum between 0 and 16777215, and we want to produce two stack values which can be concatenated to make an 3 byte unsigned value. Here we have to remove the zero-padding in the four-byte case:
# !UNTESTED CODE!
# Stack (top to bottom): upper, pad, lower
OP_ROT
# Generate required prefix to append to stack value to make it 3 bytes long.
OP_SIZE
OP_DUP
OP_NOTIF
# 0 -> 000000
OP_DROP
3 OP_PUSHDATA1 0x00 0x00 0x00
OP_ELSE
OP_DUP
1 OP_EQUAL OP_IF
# Single byte: prepend 0x00 0x00
OP_DROP
2 OP_PUSHDATA1 0x00 0x00
OP_ELSE
OP_DUP
2 OP_EQUAL OP_IF
# Two bytes. Now maybe final byte is 0x00 simply so it doesn't
# appear negative, but we don't care.
1 OP_PUSHDATA1 0x00
OP_ELSE
# Three bytes: empty append below
3 OP_EQUAL OP_NOTIF
# Four bytes, e.g. 0xff 0xff 0xff 0x00
# Convert to three byte version: negate and add 2^23
# => 0xff 0xff 0xff
OP_NEG
4 OP_PUSHDATA1 0x00 0x00 0x80 0x00
OP_ADD
OP_ENDIF
# Prepend nothing.
0
OP_ENDIF
OP_ENDIF
OP_ENDIF
OP_SWAP
# Stack (top to bottom): lower, pad, upper, pad
You can optimize these 47 bytes a little, but I’ll leave that as an exercise for the reader!
Now we use OP_MULTISHA256
(or OP_CAT
3 times and OP_SHA256
) to
concatentate them to form an 8-byte little-endian number, for
comparison against the format used by OP_TXHASH
.
Basically, 95 bytes to compare our tuple to a hashed value.
Let’s write some code to add two well-formed Script-Friendly Pairs!
# !UNTESTED CODE!
# Stack (top to bottom): a_lower, a_upper, b_lower, b_upper
OP_ROT
OP_ADD
OP_DUP
4 OP_PUSHDATA1 0x00 0x00 0x00 0x01
OP_GREATERTHANOREQUAL
OP_IF
# lower overflow, bump upper.
# FIXME: We can OP_TUCK this constant above!
4 OP_PUSHDATA1 0x00 0x00 0x00 0x01
OP_SUB
OP_SWAP
OP_1ADD
OP_ELSE
OP_SWAP
OP_ENDIF
# Stack now: a_upper(w/carry), lower_sum, b_upper.
OP_ROT
OP_ADD
OP_SWAP
# Stack now: lower_sum, upper_sum
Note that these 26 bytes don’t check that upper doesn’t overflow: if we’re dealing with verified amounts, we can add 16 times before it’s even possible (and it’s never possible with distinct amounts of course). Still, we can add OP_DUP 0 OP_GREATERTHANOREQUAL OP_VERIFY
before the final OP_SWAP
.
The code above assumes well-formed pairs, but since the pairs will come from the witness stack, we need to have a routine to check that a pair is wel-formed:
# !UNTESTED CODE!
# Stack: lower, upper
OP_DUP
# lower must be 0 - 0xFFFFFF inclusive
0
4 OP_PUSHDATA1 0xFF 0xFF 0xFF 0x00
OP_WITHIN
OP_VERIFY
OP_OVER
# upper must be 0 - 0x7FFFFFF inclusive
0
4 OP_PUSHDATA1 0xFF 0xFF 0xFF 0x07
OP_WITHIN
OP_VERIFY
This ensures the ranges are all within spec: no negative numbers, no giant numbers.
While this shows that OP_CAT
/OP_MULTISHA256
is sufficient to deal with bitcoin amounts in Script, the size (about 250 bytes to validate that two inputs equals one output) makes a fairly compelling case for optimization.
It’s worth noting that this is why Liquid chose to add the following 64-bit opcodes to bitscoin script: OP_ADD64
, OP_SUB64
, OP_MUL64
, OP_DIV64
, OP_NEG64
, OP_LESSTHAN64
, OP_LESSTHANOREQUAL64
, OP_GREATERTHAN64
, OP_GREATERTHANOREQUAL64
.
(They also reenabled the bitwise opcodes (OP_XOR
etc) to work just fine with these. They also implemented OP_SCRIPTNUMTOLE64
, OP_LE64TOSCRIPTNUM
and OP_LE32TOLE64
for conversion.)
In my previous post I proposed OP_LESS
which works on arbitrary values, which doen’t work for these because the endian is wrong! As a minimum, we’d need to add OP_LESSTHAN64
, OP_ADD64
and OP_NEG64
to allow 64-bit comparison, addition and subtraction.
But, with only OP_CAT
or OP_MULTISHA256
, it’s possible to deal with amounts. It’s just not pretty!
Thanks for reading!
]]>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.
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:
K
by this value.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):
X
is less than 253:
X
X
X
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:
N
off the stack.N
is not a CScriptNum, fail.N
entries on the stack, fail.N
> 0:
N
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
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:
t
off the stack. If t >= SECP256K1_ORDER, fail.P
off the stack. If it is not a valid compressed pubkey, fail. Convert to Even-Y if necessary. (i.e. lift_x()
).Q = P + t*G
.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
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
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:
H1
and H2
.H1
< H2
, merkle is TaggedHash("TapBranch", H1 + H2)
, otherwise TaggedHash("TapBranch", H2 + H1)
We’ve done this before, it’s just Step 1 as before.
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!
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
:
OP_SEPARATOR
before OP_SUCCESSx
:
OP_SEPARATOR
:
OP_IF
) + (number of OP_NOTIF
) > (number of OP_ENDIF
): failThis 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).
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!
]]>2 BTC for a human-readable bolt 12 offer generator feature integrated into a popular iOS or android bitcoin wallet. “Human-readable” means something that can be used on feature phone without QR or copy/paste ability. For example, something that looks like LN address.
This, of course, is asking to solve Zooko’s Triangle, so one of decentralizationm, human readability, or security needs to compromise! Fortunately, the reference to LN address gives a hint on how we might proceed.
The scenario, presumably, is Bob wants to pay Alice, where Alice shows Bob a “Human Readable Offer” and Bob types it into his phone. Each one runs Phoenix, Greenlight, or (if their phone is too low-end) uses some hosted service, but any new third party trust should be minimized.
There are three parts we need here:
Consider the normal offer case: the offer encodes Alice’s nodeid and description (and maybe other info) about what’s on offer. Bob turns this into an invoice_request, sends an onion message to Alice’s node, which returns the (signed) invoice, which Bob pays. We need to encode that nodeid and extra information as compactly as we can.
The issue of “finding Alice’s node” has been drafted already for BOLT12, at https://github.com/rustyrussell/bolt12address (but it needs updating!). This means that if you say “rusty@blockstream.com” you can get a valid generic offer, either by contacting the webserver at “blockstream.com” or having someone else do it for you (important for privacy!), or even downloading a public list of common receivers.
Note that it’s easier to type *
than @
on feature phones, so I suggest allowing both rusty@blockstream.com
and RUSTY*BLOCKSTREAM.COM
.
Now, presumably, we want a specific invoice: it might be some default “donate to Alice”, but it could be a specific thing “$2 hot dog”. So you really want some (short!) short-code to indicate which invoice you want. I suggest a hash, followed by some randomly chosen alphanumeric string here (case-insensitive!): an implementation may choose to restrict themselves to numbers however, as that’s faster to enter on a feature phone.
invreq_payer_note
field in BOLT 12 or add a new odd field.So, did you even get the right node id? That’s the insecure part; you’re trusting blockstream.com! Checking the nodeid is hard: someone can grind out a nodeid with the same first 16 digits in a few weeks. But I think you can provide some assurance, by creating a 4-color “flag” using the node id and the latest bitcoin blocks: this will change every new block, and is comparable between Alice and Bob at a glance:
This was made using this hacky code which turns my node id 024b9a1fa8e006f1e3937f65f66c408e6da8e1ca728ea43222a7381df1cc449605 into an RGB color (by hashing the nodeid+blockhash).
For a moment, when a new block comes in, one image might be displaced, hence the number, but it’ll only be out by one.
#
SHORT-CODE, and the current nodeid flag.There are probably other ways of doing this, but this method has the advantage of driving maturity in several different areas which we want to see in Bitcoin:
Feel free to contact me with questions!
]]>This power extends script in useful ways, such as allow creation of force spending paths (such as vaults which force spending delays), and rebindable inputs (such as required for Lightning “state fixup” proposals, aka LN-Symmetry). But when we discuss specific proposals (such as OP_TX, OP_TXHASH or OP_CHECKTEMPLATEVERIFY) it’s been difficult to nail down the exact trade-offs made for each one. So I want to describe the landscape (or taxonomy) which we can use to categorize and assess covenants.
Firstly, consider the simplest covenant: OP_TXIDVERIFY. This would check the txid of the spending transaction is equal to the given txid. This is easy to implement both in existing script (replacing OP_NOP3), and in tapscript. It doesn’t actually work, since it makes a commitment circle (the txid contains the txid of the input, which contains the txid…; thanks Jeremy Rubin), but it’s a useful thought experiment.
Now, consider the most complete covenant proposal: OP_TX. The idea is to push some specified field of the spending transaction onto the stack. For efficiency, it would take a bitmap to push multiple fields at once and (because we don’t have OP_CAT) have an option to concatenate them all as push them as one element. There are details here which matter, such as how primitive Bitcoin script is when dealing with numbers, and stack space limits for large transactions, but the idea is simple.
This allows you to do things like “output amount must be > 100000 sats”.
On the spectrum from simplest to most complete, is Russell O’Connor’s OP_TXHASH (which I generalized into the OP_TX proposal), which takes a bitmap from the stack and hashes those fields together, then pushes the resulting hash onto the stack. Of course, you can have multiple OP_IF branches allowing different equalities, but only a handful: you’ll run out of scripts space quite fast. With OP_CAT you could extend this further to assemble a template to compare against at runtime, but we don’t have that so I’ll ignore that for now.
This allows for simple equality tests, such as “output amount must be 100000 sats”.
OP_CHECKTEMPLATEVERIFY is a further restriction on basic equality covenants: it’s like OP_TXHASH with a fixed bitmap. It’s an opinionated subset though, which makes it more powerful than OP_TXIDVERIFY (and usable!): in particular it doesn’t commit to inputs at all (except the input number), but commits to all the outputs; this means you can theoretically add fees and still match, but you can’t have a change output. It’s also usable outside tapscript, since it’s written in the old “don’t-touch-the-stack” script soft-fork style.
Designing in the second half of 2023, I think it’s reasonable to assume covenants are only relevant inside taproot.
This means we have the ability to easily limit it in a way which can be unlimited in stages later via future soft-forks:
As an example, let’s turn OP_TX into OP_TXIDVERIFY. We only define one bit: OP_TX_BIT_TXID. That bit means “push the txid on the stack”, and if anything else is set, OP_TX is interpreted as OP_SUCCESS:
01 OP_TX_BIT_TXID OP_TX <txid> OP_EQUALVERIFY
Similarly, if we want OP_CHECKTEMPLATEVERIFY, we require the following OP_TX bits to be defined:
i.e: (assuming they’re assigned bits from 0 to 10)
02 b1111111111 OP_TX OP_SHA256 <hash> OP_EQUALVERIFY
There are some differences in how fields are hashed, and perhaps their order, but these are cosmetic not functional differences.
Extending this in future simply means defining other fields, and what combinations are allowed.
There are many ways we can argue about how to clip covenants’ wings. But I want to address (and dismiss) one specifically: the idea of restricting recursive covenants which restrict all future descendants.
Any covenant system listed here can restrict outputs. That means I can require that the spending transaction spend to a spending transaction that spends to a spending transaction that spends to…. 100 million transactions later… an output to me. You could prevent this by requiring that any covenant-spending tx itself is not allowed to use covenants at all, but that adds complexity and reduces usefulness.
Mathematically, there’s a difference between being able to restrict transactions to arbitrary depth and to infinite depth. Nobody else cares: either way, there are far better ways to render your coins useless than placing them in a giant chain or loop.
I wrote a previous post on Covenants via Signatures which noted that signatures with BIP-118 can be used to make covenants. This is not a neat design, it’s more like “we have a jackhammer, we can use it to knock in a nail”. On the covenant spectrum, it’s an Equality Covenant between OP_TXHASH and OP_CHECKTEMPLATEVERIFY, in that it can be used with several different field bitmaps, according to the SIGHASH flags used on the signature.
It’s worth noting that Bitcoin’s OP_CHECKSIG (and family) do three things:
OP_TX implements the first, and we already have various OP_SHA256 and similar operations for the second. OP_TXHASH and OP_CHECKTEMPLATEVERIFY combine the first two.
It’s logical to want a separate operation for the third one, hence the proposal to be able to check a signature signs a given hash: OP_CHECKSIGFROMSTACK. This would let you simulate any OP_CHECKSIG variation (depending on what OP_TX/OP_TXHASH flags were enabled):
02 <flags> OP_TX OP_SHA256 <pubkey> OP_CHECKSIGFROMSTACK
We should enable ANYPREVOUT. This will enable LN-symmetry which makes Lightning simpler (and thus more robust!), which has already been implemented. It will also enable covenants, though with a weird requirement for a signature-in-output, which makes them less efficient than they could be, but enables real uses and experimentation to inform future soft forks.
For future covenant soft forks, we should look at complete designs like OP_TX, then clip their wings as desired so we can enable the full functionality later. This may well end up looking like OP_CHECKTEMPLATEVERIFY!
Meanwhile, Greg Sanders, who both refined the OP_VAULT proposal and implemented LN-Symmetry (nee Eltoo), expressed the opinion that we’re fast approaching the edge of Bitcoin Script usability, and he now was firmly of the opinion that a soft fork to introduce Simplicity would be better. Perhaps that will happen instead of OP_TX or the like?
]]>[EDIT: An earlier version claimed we do covenants already. Oops! Thanks Ruben Somsen and Jimmy Song.]
In Bitcoin, covenants refers to restricting how an output is spent: this is from the legal term where conditions on property persist beyond sale. This is usually defined to exclude the “obvious” common requirement that the spending transaction be signed by a given key.
But to step back, there are logically three things OP_CHECKSIG (and friends) do:
For covenants, you really just want the first part: the ability to introspect so you can check whatever feature of the transaction you care about (this is the basis for OP_TX, which takes a bitmap telling it what about the spending transaction to push onto the stack so you can test it). But if you only care about equality, you can get away with something that does the first two things (this insight was the basis for Russell O’Connor’s OP_TXHASH, like OP_TX but always hashes before putting on the stack), and just check the hash is what you expected.
But, Burak points out that if you only care about equality, and are happy to specify all the fields that are covered by signatures (with the various SIGHASH variants), you can simply put a pubkey with pre-made signature and an OP_CHECKSIG into the output script! That constrains the transaction’s fields to hash to whatever that OP_CHECKSIG expects.
This, of course, is overkill: you don’t actually care about the signature operation, you’re just using it test hashes to create covenants. But unfortunately (as pointed out when I posted on Twitter, all excited!), it doesn’t quite work yet, because your signature has to commit to the script which contains the signature: a circular dependency.
But BIP-118 (a.k.a. ANYPREVOUT) proposes new SIGHASH flags which allow you not to commit to the input script, so this covenant-via-signature is possible, and Rearden Code has a tweak which makes this more powerful. I also suspect that you can probably use a simple 0x1
as the pubkey in some cases, since BIP-118 defines that to mean the taproot internal key, saving 32 bytes.