You can see the final result here.

I had reduced it to a simple test, and you can follow along from there. Not sure how clear I was, since I didn’t know where this would go! You can find the final pull request on GitHub.

Understanding tal is a requirement for coding anything within CLN!

The first video simply sets the groundwork of what the rest of the series should look like.

Ye Olde Bitcoin Script

Most people know that Satoshi disabled OP_CAT and a few other opcodes in v0.3.1, but Anthony Towns pointed out that until v0.3 bitcoin also allowed arbitrary size numbers using the OpenSSL BIGNUM type.

This was early in the project, and I completely understand the desire to avoid DoS immediately and clearly, and restore functionality later once the issues were carefully considered. Unfortunately, the difficult nature of Script enhancements was not deeply appreciated until years later, so here we are!

A Varops Budget: Full Script Restoration Without Denial of Service

BIP-342 replaced the global signature limit with a sigops budget based on weight, designed to be ample for any reasonable signature validation (such as might be produced by miniscript), yet limited enough to avoid denial of service.

We can use the approach for other operations whose expense is related to their operand size, and similarly remove existing arbitrary limits in script. I call this a “varops” budget, as it applies to operations on variable-length operands.

My draft proposal sets the varops budget as simple:

• The transaction weight multiplied by 520.

This ensures that even if the budget were enforced on existing scripts, no script could conceivably fall short (e.g. each OP_SHA256 can always operate on the maximal-size stack object, with its own opcode weight supporting that budget).

Note: the budget is for the entire transaction, not per input: this is in anticipation of introspection opcodes which mean that a fairly short script may nonetheless want to examine other inputs which may be much larger.

The consumption of the various opcodes is as follows (anything not listed doesn’t have a cost):

Removal Of Other Limits

Ethan Heilman’s proposal for restoring OP_CAT maintained a limit of 520 bytes for the result. This can now be removed, in favor of a total stack limit already valid for taproot v1 (1000 elements and 520,000 bytes).

Further, if we were to introduce a new segwit version (such as Anthony Towns’ generalized taproot] or just to allow keyless entry, we can lift these limits to reasonable blocksize maxima (perhaps 10,000 elements totalling 4M bytes).

Minor Changes to Semantics

Values are still little-endian, but unsigned. This simplifies implementation and makes the interaction of bit operations and arithmetic operations far simpler. It allows existing positive numbers to use these opcodes without modification, not requiring conversion.

If a new segwit version were used, existing opcodes can be replaced, otherwise, new opcodes (e.g. OP_ADDV) would be added.

Implementation Details

The v0.3.0 implementation used a simple class wrapper of OpenSSL’s BIGNUM type, but for maximum clarity and simplicity I reimplemented each operation without external dependencies.

Except for OP_EQUAL/OP_EQUALVERIFY, each one converts to and from a little-wordian vector of uint64_t. This could be optimized by doing conversion on demand.

OP_DIV, OP_MOD and OP_MUL are implemented naively (comparison with libgmp’s big number operations shows more sophisticated approaches are astronomically faster).

Benchmarks: Are Limits Low Enough To Prevent DoS?

Are Limits High Enough to Be Ignored?

We can remove the 520 byte limit

We still require a limit on total stack size: with a new segwit version this could be raised to 4000000, or left at 520,000 as per the current limit.

After I’ve had a series of posts looking at Script improvements.

In my previous post on Examing scriptpubkeys in Script I pointed out that there are cases where we want to require a certain script condition, but not an exact script: an example would be a vault-like covenant which requires a delay, but doesn’t care what else is in the script.

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.

Introducing OP_SEGMENT

Currently, the entire tapscript is scanned for the OP_SUCCESS opcodes, and succeeds immediately if one it found. This would be modified:

1. The tapscript is scanned for either OP_SEGMENT or OP_SUCCESSx.
2. If OP_SEGMENT is found, the script up to that point is executed. If the script does not fail, scanning continues from that point.
3. If 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.

Implementation

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!

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.

Stacking Transactions: Adding Fees Later

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.

Partial Validation Attacks: A Primer

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.

Partial Validation Exploit: A Covenant Example.

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!

Avoiding Partial Validation Issues When Stacking Transactions

This can avoided in one of four ways:

1. Specify the entire transaction, CTV-style. But then you cannot add fees inline.
2. Have each input examine all the other inputs. This is limited since there is no looping in Script.
3. Insist the current input also be at index #0, so there can only be one.
4. Use relative output addressing, so we examine the output corresponding to the current input.

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?

Stacking Odd-Shaped Transactions

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.

Side Note: Things That Don’t Work

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.

Summary

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.

Introducing OP_SEGMENT

Currently, the entire tapscript is scanned for the OP_SUCCESS opcodes, and succeeds immediately if one it found. This would be modified:

1. The tapscript is scanned for either OP_SEGMENT or OP_SUCCESSx.
2. If OP_SEGMENT is found, the script up to that point is executed. If the script does not fail, scanning continues from that point.
3. If 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.

Implementation

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!