BIP440: Varops Budget for Script Runtime Constraint, BIP441: Restoration of disabled Script (tapleaf 0xc2) #2118

How did you get to 34 bytes for the smallest possible input? As far as I’m aware, the smallest possible input is 41 bytes. (32+4 for the outpoint, 4 for sequence, 1 for input script length).

Good catch, fixed!

consistency nit

- The number of stack elements (including altstack elements) exceeds 32,768.

Fair. There's a 1000 to fix too.

These are currently all rendered on a single line, but I assume you wanted to produce a numbered list:

# OP_CHECKLOCKTIMEVERIFY
# OP_CHECKSEQUENCEVERIFY
# OP_VERIFY
# OP_PICK
# OP_ROLL
# OP_IFDUP
# OP_CHECKSIGADD

Thanks! Turns out I used Markdown formatting in a few places. I toyed with the idea of converting to md, but I think it would just confuse existing reviewers.

Rendered as a single line. See above.

I was surprised that you align different lengths in the front instead of the back. I would have expected padding in the front instead of the back for bitwise AND.

For bitwise AND on little-endian encoded values you pad the shorter one in the back, if you would pad it in the front you would change its value. x & 0 = 0 zeroes out the high bytes which is what you would expect when ANDing with a narrower value.

From what I understand, the endianness is relevant to how the data is serialized on chain. I don’t see why endianness would be or should be relevant to the stack operations and find this approach to describing the opcodes needlessly confusing. The opcodes operate on numbers, not on serialized data, so describing the operations abstractly would seem more useful to me.

You are confused. Endianness absolutely applies to stack values. It's just that with so many opcodes disabled, it's hard to tell. Once you can alter at a bit level, it becomes salient.

When considering the costs of operations, the serialized data is the key, not (usually!) the number. Adding 1 to 0 could be cheap, or could be expensive (if either number is serialized with 2MB of 0 at the end).

I added a comment in the rationale:

All opcodes are described in exact (painstaking) byte-by-byte operations, so that their varops budget can be easily derived. Note that this level of detail is unnecessary to users of script, only being of interest to implementers.

I see, I expected from title and abstract that this document would be directed at users of script, and that the second document would cover budgets and how costs were selected directed at the implementers.

Maybe this is obvious to other readers, but I assume that you mean that the result of the bitwise OR of A and B plus the tail of A are pushed to the stack? If so, this could be expressed more clearly.

Line 213 should say explicitly that it's altering A.

Here's the diff:

@@ -210,7 +212,7 @@ OP_LEFT only needs to read its OFFSET operand (truncation is free), whereas OP_R
 # Pop B off the stack.
 # Pop A off the stack.
 # If B is longer than A, swap B and A.
-# For each byte in B (the shorter operand): bitwise OR it with the equivalent byte in A.
+# For each byte in B (the shorter operand): bitwise OR it into the equivalent byte in A (altering A).
 # Push A onto the stack.
 |-
 |OP_XOR
@@ -222,13 +224,13 @@ OP_LEFT only needs to read its OFFSET operand (truncation is free), whereas OP_R
 # Pop B off the stack.
 # Pop A off the stack.
 # If B is longer than A, swap B and A.
-# For each byte in B (the shorter operand): exclusive OR it with the equivalent byte in A.
+# For each byte in B (the shorter operand): exclusive OR it into the equivalent byte in A (altering A).
 # Push A onto the stack.
 |}
 
 =====Rationale=====
 
-OP_AND, OP_OR and OP_XOR are assumed to fold the results into the longer of the two operands.  This is an OTHER operation (i.e. cost is 2 per byte), but OP_AND needs to do this until one operand is exhausted, and then zero the rest (ZEROING, cost 1 per byte).   OP_OR and OP_XOR can stop as soon as the shorter operand is exhausted.
+OP_AND, OP_OR and OP_XOR are assumed to fold the results into the longer of the two operands.  This is an OTHER operation (i.e. cost is 2 per byte), but OP_AND needs to do this until one operand is exhausted, and then zero the rest (ZEROING, cost 1 per byte).   OP_OR and OP_XOR can stop processing the operands as soon as the shorter operand is exhausted.
 
 ====Bitshift Opcodes====
 

I assume you mean that the result of the XOR concatenated with the remaining bytes of A is pushed to the stack, but if so (or not so), it’s not clear.

Yes, same problem as above.

…can stop because the remaining bits of the longer operand will not be changed by the operation? But are they preserved or not?

They are. They pop, fold, push. It's the folding step that can terminate early.

Uh. “prepend”? Isn’t an upshift usually bit shifting to the left in binary representation? Is this description based on endianness? I would have expected that endianness is just relevant to how numbers are read and written to the stack, but when describing the bit operations we would still operate on them in the binary representation. I.e. wouldn’t an upshift append zeroes on the right?

If I’m not stumbling completely in the dark here, could you please clarify whether you are describing the operations based on the little endian numbers or in binary representation?

Yes these descriptions are definitely based on endianness, I think it would be confusing to use the "wrong" endianness in the descriptions here, so we prepend to upshift because the most significant byte is on the right.

But I agree that the current state is also confusing and it should clarify that this is not describing the more common binary representation with MSB on the left, but the layout of the actual byte vectors.

Thanks, glad to hear that my issue was heard, but I think the underlying issue here is that this description mixes serialization format and stack operations. Just because the data is encoded little-endian in the serialization format doesn’t mean that implementers would handle the data that way after reading it. Describing the operations abstractly on basis of them just being numbers (or on binary for bitwise operations) seems much preferable, as long as the explanation makes clear how the specification is meant to be read.

No, that would completely defeat the point. We need to specify it to this level for our model of costs. There are no invisible steps.

If an implementation reads it as a number and converts it to its preferred endian, they have to do a lot of work to determine what the additional costs of that step are, because it's not costed here. Perhaps they can do an analysis and show that they do not meaningfully exceed the budget doing so.

It's absolutely possible to have a higher-level description, and move the exact description of each opcode to an appendix. But mainly that's obvious?

My misunderstanding was that you are not describing the opcodes in this document for users of script, but that you’re defining them to explain the cost model. This was not obvious to me from title and abstract.

I’m still confused by these descriptions. Why are we even talking about bytes at all?

I think I understand what you mean, but the way it’s described seems confusing to me.

It seems to me that this description is mixing stack operation descriptions with implementation details. I haven’t read the second document yet, but I thought the other one was dealing with the Varops costs?

I would have e.g., expected the definition of OP_MUL to be something along the lines of:

| Word | Opcode | Hex | Input | Output | Description | | OP_MUL | 149 | 0x97 | [a, b] | [a×b] | Pops two elements off the stack, multiplies them, pushes result to the stack |

I’m not sure why the opcode descriptions would need to mention bytes at all—even if the implementation of the stack operation would then obviously be much smarter about how the bytes are modified to achieve the result efficiently.

I think you're missing the varops cost entirely?

My first impression from title “Restoration of disabled script functionality” and (previous) abstract was that this document would be about describing the restored opcodes behavior. I expected that the second document would be about the budget and the costs?

It was not clear to me that this document’s main purpose was to explain the assigned costs for the reintroduced opcodes rather than the functionality of the opcodes themselves. On second read and with your recent commentary, it seems to me now that explaining the behavior of the opcodes themselves is at most a secondary goal of the document or assumed to be known to the readers already.

I’m again confused by trailing zeroes vs leading zeroes. Please clarify how we should be thinking about numbers.

Because MUL and DIV normalize the results, you need to do that step. This has a cost associated with it, so must be described.

You didn't get to it (perhaps we should hoist this higher?) but it is spelled out in it its own section:

===Normalization of Results===

Note that only arithmetic operations (those which treat operands as numbers) normalize their results: bit operations do not. Thus operations such as "0 OP_ADD" and "2 OP_MUL" will never result in a top stack entry with a trailing zero byte, but "0 OP_OR" and "1 OP_UPSHIFT" may.

To be clear, the following operations are arithmetic and will normalize their results:

• OP_1ADD
• OP_1SUB
• OP_2MUL
• OP_2DIV
• OP_ADD
• OP_SUB
• OP_MUL
• OP_DIV
• OP_MOD
• OP_MIN
• OP_MAX

We have so many concepts that are “v2”, perhaps consider giving your script variant a more distinct name.

Good point! It's only marginally better than "New Tapscript" :)

Since Julian chose Tapleaf 0xC2, we can use "0xC2 Tapscript" explicitly.

Was the cost of removing trailing bytes the reason for not normalizing results of bit operations? Otherwise, it might be interesting to explain this design decision in the Rationale.

This made me think! Actually, the question is more "why do arithmetic operators do it?", and that's mainly tradition. It saves a bit of budget with chained operations but nobody should care. It allows canonical comparison, i.e. "" is 0, but that's also a bit obscure.

Here's what I ended up with:

<ref>Such non-arithmetic operations can used to operate on values such as preimages or (with introspection) parts of transactions, where truncation of zeros would be unexpected. One could argue that even arithmetic operators should not normalize, but that would be a gratuitous and surprising change. Note that "0 OP_ADD" can always be used to cheaply normalize the top stack element.</ref>

Nit: title is over 50 characters.

Formatting nit: this cuts off text in the default view, perhaps use different formatting here.

<img width="1046" height="222" alt="Image" src="https://github.com/user-attachments/assets/bd688e5b-44d5-4948-ad49-1940652f0912" />

After the tail is copied to the front, don’t you still need to truncate?

# Copy value(OFFSET) bytes from offset length(A) - value(OFFSET) to offset 0, if value(OFFSET) is less than length(A).
# Truncate A to length value(OFFSET)

What happens if A is shorter than OFFSET?

Clarified:

3. If value(OFFSET) is less than length(A), copy value(OFFSET) bytes from offset length(A) - value(OFFSET) to offset 0 in A, and truncate A to length(A) - value(OFFSET). Otherwise truncate A to length 0.

This copies the original code:

            case OP_LEFT:
            case OP_RIGHT:
            {
                // (in size -- out)
                if (stack.size() < 2)
                    return false;
                valtype& vch = stacktop(-2);
                int nSize = CBigNum(stacktop(-1)).getint();
                if (nSize < 0)
                    return false;
                if (nSize > vch.size())
                    nSize = vch.size();
                if (opcode == OP_LEFT)
                    vch.erase(vch.begin() + nSize, vch.end());
                else
                    vch.erase(vch.begin(), vch.end() - nSize);
                stack.pop_back();
            }
            break;

I assume that it is considered obvious that any overflowing bit is pushed to next next byte. However, if that is obvious, why does the specification of OP_ADD below explicitly mention “For each byte in B, add it and previous overflow into the equivalent byte in A, remembering next overflow.”? Should that also be mentioned here on OP_2MUL and OP_2DIV?

Yeah, these are less completely described than the OP_ADD case. But the overflow has huge impact on costs, because of the worst case (copying the entire thing to add one byte at the end), so it does need to be explicitly mentioned.

How's this?

# Shift each byte in A 1 bit to the left (increasing values, equivalent to C's << operator), overflowing into the next byte.

And for OP_2DIV:

# Shift each byte in A 1 bit to the right (decreasing values, equivalent to C's >> operator), taking the top bit from the next byte, and tracking the last non-zero value.

Is the idea that A could have started with one or more trailing zero bytes? I don’t see how A could ever gain a trailing zero byte from OP_2MUL, since only a left-shifted 1 would overflow to the next byte, which is explicitly described.

Exactly, A does not have to be normalized on input.

OP_DOWNSHIFT explicitly mentions that the excess downshifted bits are truncated, should that also be mentioned here?

There's no truncation, since it's only 1 bit (except for post-normalization) With DOWNSHIFT, if it's more than 7 bits, there's truncation. That's why they're described differently.

Does “those” refer to items from this list that are not defined in the second document or to additional unnamed opcodes?

Any opcodes not mentioned in this document or the preceding list have a cost of 0 (they do not operate on variable-length stack objects).

Multiplication and division require multiple passes over the operands, meaning a cost proportional to the square of the lengths involved, and the word size used for that iteration makes a difference.  We assume 8 bytes (64 bits) at a time are evaluated, and the ability to multiply two 64-bit numbers and receive a 128-bit result, and divide a 128-bit number by a 64-bit number to receive a 128-bit quotient and remainder.  This is true on modern 64-bit CPUs (sometimes using multiple instructions).

* We assume that the manipulation of the stack vector itself (e.g. OP_DROP) is negligible (with the exception of OP_ROLL)
* We assume that memory allocation and deallocation overhead is negligible.
* We do not consider the cost of the script interpretation itself, which is necessarily limited by block size.
* We assume implementations use simple linear arrays/vectors of contiguous memory.
* We assume implementations use linear accesses to stack data (perhaps multiple times): random accesses would require an extension to the model.
* We assume object size is limited to the entire transaction (4,000,000 bytes, worst-case).
* Costs are based on the worst-case behavior of each opcode.

# the script size is limited by the existing weight limit of 4,000,000 units and
# the script can only consume the varops budget of a whole block: 10,000 * 4,000,000 (40b).

The signature cost is simply carried across from the existing [[bip-0342.mediawiki|BIP-342]] limit: 50 weight units allow you one signature.  Since each transaction gets varops budget for the entire transaction (not just the current input's witness), and each input has at least 41 bytes (164 weight), this is actually slightly more generous than the sigops budget (which was 50 + witness weight), but still limits the entire block to 80,000 signatures.

I'm tempted to ignore this one for being too pedantic, so then when other people notice it I can claim even more pedantically that the existing text is technically correct!

Or, y'know, I could just admit I'm wrong.

Use pound sign for numbered list

Pound sign for numbered list

Suggesting an unnumbered list as it line breaks as currently formatted.

BIP3 specifies that the Changelog is listed most recent version first.

I assume that you meant 2026 for version 0.2.0, or it would predate version 0.1.0.

- 0.2.0 (2026-02-21): increase in cost for hashing and copying based on benchmark results.
- 0.1.0 (2025-09-27): first public posting

No Changelog present.

Asterisks for unnumbered list here as well.

Sorry, I didn’t account for another fun aspect of MediaWiki syntax when I made my suggestion: square brackets are used to signify external links, and therefore these stack depictions show only the first "word" in the brackets:

<img width="1051" height="878" alt="Image" src="https://github.com/user-attachments/assets/b74c9892-32df-47c7-926e-a557cab09849" />

Either of these should work:

|\[A B\]

or

|<nowiki>[A B]</nowiki>

FML. I thought about omitting the [ altogether, but it does seem more idiomatic. Good catch!

I thought I was going crazy, when I looked at the rendered document

<img width="616" height="161" alt="Image" src="https://github.com/user-attachments/assets/d1d3d924-c0ac-4c1e-8e91-2258ee964f9b" />

and then the MediaWiki source code, but alas, just another MediaWiki quirk: single square brackets are used to signify external links. To render them as text, they need to be escaped. I think either of these should work:

If there are fewer than the required number of stack elements, these opcodes fail validation.  These are popped off the stack in right-to-left order, i.e. \[A B\] means pop B off the stack, then pop A off the stack.

If there are fewer than the required number of stack elements, these opcodes fail validation.  These are popped off the stack in right-to-left order, i.e. <nowiki>[A B]</nowiki> means pop B off the stack, then pop A off the stack.

A bit late to tell you now, but we accept submissions either in MediaWiki or in Markdown format! ;-)

Yes, I read that when I read BIP 3, but mediawiki was the norm when I started. As you can tell, I'm more familiar with md. And tables are a md extension, since it's not really a standard. GH supports them so maybe that's moot?

Happy to redo it, if it makes people happy...

Nah, just if Markdown is your preference, you can do the next one in Markdown. And yeah, tables work on GitHub with Markdown.

This Description and Definition appear to be at odds.

Let’s say that A: 0x00112233DEADBEEF and OFFSET is 5. Per the Description I would expect:

    A: 0x00112233DEADBEEF
    OFFSET 5:      ^
    OUTPUT: 0xADBEEF

I.e., three bytes starting with the byte at position 5 are copied to the front.

Per the Definition: copy 5 bytes from offset 8-5 = 3 to offset 0:

    A: 0x00112233DEADBEEF
    ↦ 0x33DEADBEEFADBEEF

Truncate to length(A)-value(OFFSET) (3):

    ↦ 0x33DEAD

I guess this should read:

|Extract the right bytes of A, from OFFSET onwards
|
# Pop operands off the stack.
# If value(OFFSET) is less than length(A), copy length(A) - value(OFFSET) bytes from offset value(OFFSET) to offset 0 in A, and truncate A to length(A) - value(OFFSET).  Otherwise truncate A to length 0.
# Push A onto the stack.

This correct: great catch. Doesn't alter the cost, fortunately.

|\[A B\]

and below

Note that only arithmetic operations (those which treat operands as numbers) normalize their results: bit and byte operations do not.<ref>Such non-arithmetic operations be can used to operate on values such as preimages or (with introspection) parts of transactions, where truncation of zeros would be unexpected.  One could argue that even arithmetic operators should not normalize, but that would be a gratuitous and surprising change.  Note that "0 OP_ADD" can always be used to cheaply normalize the top stack element.</ref>  Thus operations such as "0 OP_ADD" and "2 OP_MUL" will never result in a top stack entry with a trailing zero byte, but "0 OP_OR" and "1 OP_UPSHIFT" may.<ref>The original Bitcoin implementation had a similar operational split, but OP_LSHIFT and OP_RSHIFT did normalize, which was almost a requirement given that they also preserved the sign of the shifted operand</ref>

I get the idea, I think you be the wrong position in though!

This is now rendered as a numbered list. Perhaps indenting plus italicization would meet your expectation?

Previously:

: ''If the execution results in anything but exactly one element on the stack which evaluates to true with <code>CastToBool()</code>, fail.''

Now:

: ''If the execution results in anything but exactly one element on the stack which contains one or more non-zero bytes, fail.''

I really want to label it 4 (ii), to make it clear. I have open-coded that.

BTW https://www.mediawiki.org/wiki/Help:Formatting implies that : for indent is evil, so I'll avoid.

This sentence is ambiguous. I think you mean that it’s setting the new value of this byte’s top bit from the next byte’s bottom bit, but it could be read as taking the next byte’s top bit.

# Shift each byte in A 1 bit to the right (decreasing values, equivalent to C's >> operator), taking the next byte’s bottom bit as the value of the top bit, and tracking the last non-zero value.

Gotta love little endian. I always have to use a whiteboard: eg. value is 1 + 256*3, so 769:

00000001 00000011

Divide by 2 is 384:

10000000 00000001

So, yes, you're right.

I think :s/128 bit quotient/128-bit quotient/ got lost?

Multiplication and division require multiple passes over the operands, meaning a cost proportional to the square of the lengths involved, and the word size used for that iteration makes a difference.  We assume 8 bytes (64 bits) at a time are evaluated, and the ability to multiply two 64-bit numbers and receive a 128-bit result, and divide a 128-bit number by a 64-bit number to receive a 128-bit quotient and remainder.  This is true on modern 64-bit CPUs (sometimes using multiple instructions).

(No action necessary as these documents are already fairly mature, but I find that also in text documents limiting lines to at most 120 characters makes diffs and review comments more compact and easier to parse, and I usually recommend that to authors in the BIPs repository when they can still expect a number of revisions. See e.g., https://sembr.org/)

I made the final fixup simply "wrap at 78 outside tables".

I think ease of review is important.

In case you didn’t notice, your commit message mentions italicization, but that would be two single-quotes <code>''</code>, not two backticks <code>``</code>.

<img width="996" height="163" alt="Image" src="https://github.com/user-attachments/assets/f27366af-686b-4f3b-9fdb-11101121d2d9" />

I’m feeling a bit silly to talk so much about formatting, but I was just looking at the document, and given that the right element in the square brackets is the "top"" of the stack, maybe line breaks in the Input Stack column are sub-optimal:

<img width="310" height="448" alt="Image" src="https://github.com/user-attachments/assets/c41d6f61-ed04-455f-b228-da47ba1c6485" />

Using <pre> works, but formats it as code (which may be acceptable), using an actual non-breakable space character (U+00A0) does work without changing the appearance at preventing the line break: https://github.com/murchandamus/bips/commit/254f4b56536d00694cea9cd61a454bf68b7d888d, rendered file: https://github.com/murchandamus/bips/blob/254f4b56536d00694cea9cd61a454bf68b7d888d/bip-unknown-script-restoration.mediawiki#splice-opcodes

No, this matters. Sure, I never read the formatted version, preferring plain text, but I know others will. Thanks for doing this investigation!

* 0.2.0: 2026-02-21: increase in cost for hashing and copying based on benchmark results.
* 0.1.0: 2025-09-27: first public posting

I think we crossed a wire here. I had tried and discarded the idea of using an HTML code ( ) in the <nowiki> but that looked terrible. I had then recommended on using a UTF-8 non-breakable space character instead (U+00a0). Like so (space in suggestion is actually a non-breakable space):

|<nowiki>[A B]</nowiki>

Preventing a linebreak in the title seems like a good idea, but it seems to be a bit unreliable:

<img width="128" height="476" alt="Image" src="https://github.com/user-attachments/assets/4f2a8d8e-847f-44e7-83b6-cdeb583266ec" />

I think we crossed a wire. I had tried and discarded the idea of using an HTML code ( ) in the <nowiki> because it looked terrible (like you ;)). I had then recommended on using a UTF-8 non-breakable space character instead (U+00a0). As follows (the spaces in my suggestion are actually a non-breakable space UTF-8 characters (U+00a0)):

|<nowiki>[A BEGIN LEN]</nowiki>

Preventing a linebreak in the title sounds like a good idea, but it seems to be a bit unreliable for the longer stacks:

<img width="1065" height="523" alt="Image" src="https://github.com/user-attachments/assets/dd765417-a37b-4464-be76-3dd696928526" />

You time-traveler. It’s still the 26th here. 😁

Assignment was at 2026-03-25–21:50Z, so that should please read:

  Assigned: 2026-03-25

Assignment was at 2026-03-25–21:50Z, so that should please read:

  Assigned: 2026-03-25