Hírolvasó

The LWN.net Weekly Edition for October 26, 2023 is available.

The kernel has, for many years, had the ability to control how memory allocation is performed in systems with multiple NUMA nodes. More recently, NUMA nodes have also been pressed into service to represent different classes of memory; those nodes are now organized into tiers according to their performance characteristics. While memory-allocation policies can control the placement of pages at the NUMA-node level, the kernel provides no way to connect those policies with memory tiers. This patch series from Gregory Price aims to change this situation by allowing allocations to be placed across tiers in a weighted manner.

The Python Steering Council has posted a detailed plan for the addition of "free-threaded" (no global interpreter lock) support into the Python mainline. It will not be a short process and does not have a guaranteed successful outcome.

Phase I: Experimental phase, which can start immediately, in which the free-threaded build is enabled through a build-time option. This should not be the default install anywhere. At least one major Python release should include this experimental free-threaded build, to allow third-party packages to test and do their own experimentation. In this stage we should make it clear the build is experimental, not supported for “production use”, and may be reverted.

The 6.5.9, 6.1.60, 5.15.137, 5.10.199, 5.4.259, 4.19.297, and 4.14.328 stable kernels have all been released; each contains another set of important fixes.

Security updates have been issued by Debian (gst-plugins-bad1.0, openssl, roundcube, and xorg-server), Fedora (dotnet6.0, dotnet7.0, roundcubemail, and wordpress), Mageia (redis), Oracle (dnsmasq, python27:2.7, python3, tomcat, and varnish), Red Hat (python39:3.9, python39-devel:3.9), Slackware (mozilla and vim), SUSE (openssl-3, poppler, ruby2.5, and xen), and Ubuntu (.Net, linux-gcp-5.15, linux-gkeop-5.15, linux-intel-iotg-5.15, linux-starfive-6.2, mysql-5.7, ncurses, and openssl).

Many home-automation devices come with their own mobile app or cloud service. However, using multiple apps or services is inconvenient, so it's (purposely) tempting to only buy devices from the same vendor, but this can lead to lock-in. One project that lets users manage home-automation devices from various vendors without lock-in is Home Assistant. Over its ten-year existence, it has developed into a user-friendly home-automation platform that caters to both technically inclined and less tech-savvy people.

Version 119.0 of the Firefox browser has been released. The list of changes includes improvements to Firefox View, some PDF-editing improvements, better cookie protection, encrypted client hello support, and more.

Security updates have been issued by Debian (ceph and dbus), Fedora (cachelib, fb303, fbthrift, fizz, folly, matrix-synapse, mcrouter, mvfst, nats-server, nodejs18, proxygen, wangle, watchman, and wdt), Mageia (libcue), Oracle (18, grafana, kernel, nodejs, nodejs:16, nodejs:18, php, php:8.0, and tomcat), Red Hat (python27:2.7, python3, python39:3.9, python39-devel:3.9, toolbox, varnish, and varnish:6), SUSE (fwupdate, gcc13, icu73_2, netty, netty-tcnative, and xen), and Ubuntu (aom, ffmpeg, libvpx, libxpm, linux-aws, linux-gcp-5.4, php7.0, php7.2, ring, and sofia-sip).

As announced on the misc@ mailing list, Otto Moerbeek (otto@), the author of OpenBSD's malloc(3) implementation [a.k.a. "otto malloc"], has written a tutorial on the new malloc(3) leak detection available in OpenBSD 7.4

Read it at: OpenBSD's built-in memory leak detection

Since the publication of that write-up, Otto has committed further enhancements:

CVSROOT: /cvs Module name: src Changes by: otto@cvs.openbsd.org 2023/10/22 06:19:26 Modified files: lib/libc/stdlib: malloc.3 malloc.c Log message: When option D is active, store callers for all chunks; this avoids the 0x0 call sites for leak reports. Also display more info on detected write of free chunks: print the info about where the chunk was allocated, and for the preceding chunk as well. ok asou@

The 2023 election for members of the Linux Foundation Technical Advisory Board will be held during the upcoming Linux Plumbers Conference. The call for nominees has been posted.

The TAB exists to provide advice from the kernel community to the Linux Foundation; it also serves to facilitate interactions both within the community and with outside entities. Over the last year, the TAB has overseen the organization of the Linux Plumbers Conference, released a kernel contribution maturity model for organizations, advised on code-of-conduct issues, and more.

Nominations should be sent in by November 13.

It is probably fair to say that most Linux users spend little time thinking about the troff typesetting program, despite that application's groundbreaking role in computing history. Troff (along with nroff) is still with us, though, even if they are called groff these days, and every now and then they make their presence known. A recent groff change created a bit of a tempest within the Debian community, and has effectively been reverted there. It all comes down to the question of what, exactly, is the character used to mark command-line options on Unix systems?

Security updates have been issued by Debian (krb5, redis, roundcube, ruby-rack, ruby-rmagick, zabbix, and zookeeper), Fedora (ansible-core, chromium, libvpx, mingw-xerces-c, python-asgiref, python-django, and vim), Mageia (cadence, kernel, kernel-linus, libxml2, nodejs, and shadow-utils), Oracle (nghttp2), Slackware (LibRaw), and SUSE (chromium, java-11-openjdk, nodejs18, python-Django, python-urllib3, and suse-module-tools).

Linus has released 6.6-rc7 for testing.

Anyway, while this is all bigger than I'd have liked it to be, if the upcoming week is quiet and normal, this is the last rc and next Sunday will see the final release and then we'll open the merge window for 6.7. I simply am not aware of any issues that would be showstoppers.

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”).

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.

The Vexing Problem of Amounts

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).

A Value Form Bitcoin Script Can Deal With

21M BTC is just under 2^51 satoshis.

We split these bits into a pair of stack values:

• lower 24 bits
• upper bits (27, but we allow up to 31)

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.

Converting A Script-Friendly Pair to an 8-byte Little-Endian Value

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.

Adding Two Script-Friendly Pairs

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.

Checking Script-Friendly Pairs

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.

Summary

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!

Jeff Xu recently proposed the addition of a new system call, named mseal(), that would allow applications to prevent modifications to selected memory mappings. It would enable the hardening of user-space applications against certain types of attacks; some other operating systems have this type of feature already. There is support for adding this type of mechanism to the Linux kernel as well, but it has become clear that mseal() will not land in the mainline in anything resembling its current form. Instead, it has become an example of how not to do kernel development at a number of levels.

Security updates have been issued by Debian (linux-5.10 and webkit2gtk), Fedora (matrix-synapse and trafficserver), Mageia (chromium-browser-stable, ghostscript, libxpm, and ruby-RedCloth), Oracle (.NET 7.0, curl, dotnet7.0, galera, mariadb, go-toolset, golang, java-1.8.0-openjdk, and python-reportlab), Red Hat (php, php:8.0, tomcat, and varnish), Slackware (httpd), SUSE (bluetuith, grub2, kernel, rxvt-unicode, and suse-module-tools), and Ubuntu (dotnet6, dotnet7, dotnet8, linux, linux-aws, linux-aws-5.15, linux-azure, linux-azure-5.15, linux-azure-fde, linux-azure-fde-5.15, linux-gcp, linux-gke, linux-gkeop, linux-hwe-5.15, linux-ibm, linux-ibm-5.15, linux-kvm, linux-lowlatency, linux-lowlatency-hwe-5.15,linux-nvidia, linux-oracle, linux-raspi, linux, linux-aws, linux-aws-5.4, linux-azure, linux-azure-5.4, linux-gcp, linux-gkeop, linux-hwe-5.4, linux-ibm, linux-ibm-5.4, linux-kvm, linux-oracle, linux-oracle-5.4, linux-xilinx-zynqmp, linux, linux-aws, linux-aws-6.2, linux-azure, linux-azure-6.2, linux-azure-fde-6.2, linux-gcp, linux-gcp-6.2, linux-hwe-6.2, linux-kvm, linux-lowlatency, linux-lowlatency-hwe-6.2, linux-oracle, linux-raspi, linux-starfive, linux, linux-aws, linux-azure, linux-azure-4.15, linux-gcp, linux-gcp-4.15, linux-hwe, linux-kvm, linux-oracle, linux, linux-aws, linux-kvm, linux-lts-xenial, linux-azure, linux-bluefield, linux-intel-iotg, linux-oem-6.1, linux-raspi, and mutt).

The 6.5.8, 6.1.59, and 5.15.136 stable kernel updates have been released; each contains another set of important fixes.

When considering the interface provided by the GNU C Library (glibc), thoughts naturally turn to the programming interface as specified by POSIX, along with numerous extensions added over the years. But glibc also provides a "tunables" interface to control how the library operates; rather than being managed by a C API, tunables are set with the GLIBC_TUNABLES environment variable. Glibc tunables have been a part of a few security problems involving setuid binaries, most recently the "Looney Tunables" bug disclosed at the beginning of October. The glibc developers are now considering significant changes to tunable handling in the hope of avoiding such problems in the future.

Security updates have been issued by Debian (node-babel), Fedora (moodle), Gentoo (mailutils), Oracle (go-toolset:ol8 and java-11-openjdk), Red Hat (ghostscript, grafana, java-1.8.0-openjdk, java-11-openjdk, java-17-openjdk, nghttp2, nodejs:16, nodejs:18, and rhc-worker-script), SUSE (cni, cni-plugins, container-suseconnect, containerd, cups, exim, grub2, helm, libeconf, nodejs18, python3, runc, slurm, supportutils, and tomcat), and Ubuntu (glib2.0, openssl, and vips).

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!