As noted in my previous post on Dealing with Amounts in Bitcoin Script, it’s possible to use the current opcodes to deal with satoshi values in script, but it’s horribly ugly and inefficient.
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 Arithmetic Opcodes
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?
Generic Variable Length Amounts
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).
Limitations on Variable Operations
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.
Multiply And Divide
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:
- Normalize the inputs to eliminate leading zeros.
- If either input exceeds 128 bits, push 0 0.
- For OP_DIV, if the divisor is 0, push 0 0.
- For OP_MUL, if the output overflows, push 0 0.
- Otherwise the (normalized) result and 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).
Shift Operations, Splitting and Comparison
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.
Use for Merkle Tree Construction.
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.
Summary
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:
- OP_LSHIFT[^simplified]
- OP_RSHIFT[^simplified]
- OP_AND
- OP_OR
- OP_XOR
- OP_INVERT
- OP_MUL[^extended]
- OP_DIV[^extended]
- OP_LEFT
- OP_RIGHT
- OP_SUBSTR
And add the following new ones:
- OP_ADDV: add two little-endian unsigned numbers
- OP_SUBV: sub two little-endian unsigned numbers, push non-negative flag
- OP_GREATERTHANV: compare two little-endian unsigned numbers
- OP_GREATERTHANOREQUALV: compare two little-endian unsigned numbers
- OP_LESSTHANV: compare two little-endian unsigned numbers
- OP_LESSTHANOREQUALV: compare two little-endian unsigned numbers
- OP_BYTEREV: reverse bytes in the top stack element
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.