* [bitcoindev] [0/4] A Bitcoin Scripting Proposal BIP Quartet @ 2025-09-27 8:12 Rusty Russell 2025-09-27 11:27 ` [bitcoindev] [1/4] Varops Budget For Script Runtime Constraint Rusty Russell 0 siblings, 1 reply; 5+ messages in thread From: Rusty Russell @ 2025-09-27 8:12 UTC (permalink / raw) To: bitcoindev; +Cc: Julian Moik Hello all! As some of you know, I've been chipping away (with help now from Julian Moik, Cc'd) at a framework to restore bitcoin's scripting language to its original power. My approach has been to stick with Script: even if you prefer other approaches, you should find this restoration and enhancement of script capabilities a useful comparison. Current drafts in "review me!" format: https://github.com/rustyrussell/bips/pull/1 Here is a brief description of each: 1. Varops Budget For Script Runtime Constraint (bip-unknown-varops-budget.mediawiki) This extends and generalizes the sigops budget into a "variable operations" budget, using benchmarks taken from the prototype implementation across various machines. This budget is per transaction, by weight, designed to constrain usage to ensure rapid evaluation without overly restricting scripting ability. 2. Restoration of Script Capabilities Once the safety net of the varops budget is in place, disabled opcodes can be re-enabled, stack object size and total capacity extended, and abitrary-length arithmetic restored (though numbers are now always unsigned). 3. OP_TX Once script can handle large data once more, the problem of introspection is signficantly simplified: we can simply have an opcode which pushes parts of the current transaction onto the stack. The concrete design proposed here is a fruitful area for debate and review. 4. New Opcodes for Tapscript v2 The most speculative part of the series suggests some opcodes which would allow more optimal use of Script: OP_CHECKSIGFROMSTACK, OP_SEGMENT, OP_BYTEREV, OP_ECPOINTADD, OP_INTERNALKEY and OP_MULTI. Some of these are old friends, and others may be new to you: I look forward to your feedback. There is also a prototype implementation we used for testing: https://github.com/jmoik/bitcoin/tree/gsr Thankyou in advance for your consideration! Rusty & Julian. -- You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group. To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/877bxknwk6.fsf%40rustcorp.com.au. ^ permalink raw reply [flat|nested] 5+ messages in thread
* [bitcoindev] [1/4] Varops Budget For Script Runtime Constraint 2025-09-27 8:12 [bitcoindev] [0/4] A Bitcoin Scripting Proposal BIP Quartet Rusty Russell @ 2025-09-27 11:27 ` Rusty Russell 2025-09-27 11:28 ` [bitcoindev] [2/4] Restoration of disabled script functionality (Tapscript v2) Rusty Russell 0 siblings, 1 reply; 5+ messages in thread From: Rusty Russell @ 2025-09-27 11:27 UTC (permalink / raw) To: bitcoindev Hello all! Segwit introduced a runtime accounting system "sigops" for contraining signatures, replacing the global signature limit with a weight-based quota. This generalizes that into a "variable operations" budget, so that we can similarly loosen hardcoded limits (particularly the 520 byte stack element limit). I wanted a simple and practical model of how long stack operations take, depending on their operand size, and to verify it with benchmarks across a range of architectures. The concern you should have is that some operation takes *much* longer than expected. I avoid this primarily by having upper limits (4MB block size, 4MB stack objects, 8MB total stack, 32768 stack elements) which are extreme enough that you can ignore them for real scripts, yet give us a way to test the worst possible case for each operation. Thank you for your consideration! Rusty. <pre> BIP: ? Layer: Consensus (soft fork) Title: Varops Budget For Script Runtime Constraint Author: Rusty Russell <rusty@rustcorp•com.au> Julian Moik <julianmoik@gmail•com> Comments-URI: TBA Status: Draft Type: Standards Track Created: 2025-05-15 License: BSD-3-Clause </pre> ==Introduction== ===Abstract=== This new BIP defines a "varops budget", which generalizes the "sigops budget" introduced in [[bip-0342.mediawiki|BIP342]] to non-signature operations. This BIP is a useful framework for other BIPs to draw upon, and provides opcode examples which are always less restrictive than current rules. ===Copyright=== This document is licensed under the 3-clause BSD license. ===Motivation=== Since Bitcoin v0.3.1 (addressing CVE-2010-5137), Bitcoin's scripting capabilities have been significantly restricted to mitigate known vulnerabilities related to excessive computational time and memory usage. These early safeguards were necessary to prevent denial-of-service attacks and ensure the stability and reliability of the Bitcoin network. However, as Bitcoin usage becomes more sophisticated, these limitations are becoming more salient. New proposals often must explicitly address potential performance pitfalls by severely limiting their scope, introducing specialized caching strategies to mitigate execution costs, or using the existing sigops budget in ad-hoc ways to enforce dynamic execution limits. This BIP introduces a simple, systematic and explicit cost framework for evaluating script operations based on stack data interactions, using worst-case behavior as the limiting factor. Even with these pessimistic assumptions, large classes of scripts can be shown to be within budget (for all possible inputs) by static analysis. ===A Model For Opcodes Dealing With Stack Data=== Without an explicit and low limit on the size of stack operands, the bottleneck for script operations is based on the time taken to process the stack data it accesses (the exceptions being signature operations). The cost model uses the length of the stack inputs (or occasionally, outputs), hence the term "varops". - 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 last two assumptions make a large difference in practice: normal usage on small, cache-hot objects is much faster than this model suggests. But an implementation which is more efficient than the versions modeled does not introduce any problems (though a future soft-fork version may want to reflect this in reduced costings): only an implementation with a significantly worse worst-case behavior would be problematic. ==Design== A per-transaction integer "varops budget" is determined by multiplying the total transaction weight by the fixed factor 5,200<ref>As the most expensive non-signature operation (SHA256 hashing) is 10 varops per byte, and the largest previously-allowed stack element size is 520, it is trivial to demonstrate that no non-signature operation previously allows can violate the varops budget, as the weight of the opcode itself provides 5200 budget).</ref>. The budget is transaction-wide (rather than per-input) to allow for cross-input introspection: a small input may reasonably access larger inputs. Opcodes consume budget as they are executed, based on the length (not generally the value) of their parameters as detailed below. A transaction which exceeds its budget fails to validate. ===Derivation of Costs=== The costs of opcodes were determined by benchmarking on a variety of platforms. As each block can contain 80,000 Schnorr signature checks, we used this as a reasonable upper bound for maximally slow block processing. To estimate a conservative maximum runtime for each opcode, we consider scripts with two constraints: # thescript 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: 5,200 * 4,000,000 (~21b). The script is assumed to execute in a single thread and acts on initial stack elements that are not included in the limits for conservatism. Ideally, on each platform we tested, the worst case time for each opcode would be no worse than the Schnorr signature upper bound: i.e. the block would get no slower. And while CHECKSIG can be batched and/or done in parallel, it also involves hashing, which is not taken into account here (the worst-case being significantly slower than the signature validations themselves). The signature cost is simply carried across from the existing [[bip-0342.mediawiki||BIP-342]] limit: 50 weight units allows 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 40 bytes (160 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. ===Benchmarks=== {| ! Machine ! OS ! Compiler ! Worst-case script ! Worst-case time ! Worst-case Schnorr eq |- | AMD Ryzen 5 3600 | Linux | gcc | MUL_DUP_520Bx2 | 2.30 s | 60261 |- | Intel i5-12500 | Linux | gcc | MUL_DUP_520Bx2 | 2.07 s | 82963 |- | Intel i7-7700 | Linux | gcc | HASH256_DROP_DUP_10KBx2 | 4.73 s | 128598 |- | Apple M4 Pro | macOS | clang | RIPEMD160_DROP_DUP_520Bx2 | 1.18 s | 83382 |} We are looking for more benchmarks, so please contribute with your machine by checking out https://github.com/jmoik/bitcoin/tree/gsr and running ./build/bin/bench_varops --epochs 5 --file data.csv ===Cost Categories=== We divided operations into five speed categories: # Signature operations. # SHA256 operations. # OP_ROLL, which does a large-scale stack movement. # Fast operations: comparing bytes, comparing bytes against zero, copying bytes and zeroing bytes. Empirically, these have been shown to be well-optimized. # Everything else. Each class then has the following costs. # Signature operations cost 260,000 (5,200 * 50) units each. # Hashing costs 10 units per byte hashed. # OP_ROLL costs an additional 24 units per stack entry moved (i.e. the value of its operand). # Fast operations cost 1 unit per byte output. # Other operations cost 2 units per byte output. ===Variable Opcode Budget=== We use the following annotations to indicate the derivation for each opcode: ;COMPARING : Comparing two objects: cost = 1 per byte compared. ;COMPARINGZERO : Comparing an object against zeroes: cost = 1 per byte compared. ;ZEROING : Zeroing out bytes: cost = 1 per byte zeroed ;COPYING : Copying bytes: cost = 1 per byte copied. ;LENGTHCONV : Converting an operand to a length value, including verifying that trailing bytes are zero: cost = 1 per byte copied. ;SIGCHECK : Checking a signature is a flat cost: cost = 260,000. ;HASH : cost = 10 per byte hashed. ;ROLL : cost = 24 per stack element moved. ;OTHER : all other operations which take a variable-length parameter: cost = 2 per byte written. Note that COMPARINGZERO is a subset of COMPARING: an implementation must examine every byte of a stack element to determine if the value is 0. This can be done efficiently using existing comparison techniques, e.g. check the first byte, then `memcmp(first, first+1, len-1)`. Note that LENGTHCONV is used where script interprets a value as a length. Without explicit limits on number size, such (little-endian) values might have to be examined in their entirety to ensure any trailing bytes are zero, implying a COMPARINGZERO operation after the first few bytes. The top of stack is labeled A, with successive values B, C, etc. ==Example Opcodes== The following opcodes demonstrate the approach, with an analysis of how the costs apply: ===Example: Control And Simple Examination Opcodes=== {| ! Opcode ! Varops Budget Cost ! Reason |- |OP_VERIFY |length(A) |COMPARINGZERO |- |OP_NOT |length(A) |COMPARINGZERO |- |OP_0NOTEQUAL |length(A) |COMPARINGZERO |- |OP_EQUAL |If length(A) != length(B): 0, otherwise length(A) |COMPARING |- |OP_EQUALVERIFY |If length(A) != length(B): 0, otherwise length(A) |COMPARING |} ====Rationale==== OP_IF and OP_NOTIF in Tapscript require minimal values, so do not take variable length parameters, hence are not considered here. OP_EQUAL and OP_EQUALVERIFY don't have to examine any data (and the Bitcoin Core implementation does not) if the lengths are different. ===Example: Stack Manipulation=== {| ! Opcode ! Varops Budget Cost ! Reason |- |OP_2DUP |length(A) + length(B) |COPYING |- |OP_3DUP |length(A) + length(B) + length(C) |COPYING |- |OP_2OVER |length(C) + length(D) |COPYING |- |OP_IFDUP |length(A) * 2 |COMPARINGZERO + COPYING |- |OP_DUP |length(A) |COPYING |- |OP_OVER |length(B) |COPYING |- |OP_PICK |length(A) + Length(A-th-from-top) |LENGTHCONV + COPYING |- |OP_TUCK |length(A) |COPYING |- |OP_ROLL |length(A) + 24 * Value of A |LENGTHCONV |- |} ====Rationale==== These operators copy a stack entry, write to another. OP_IFDUP has the same worst-case cost as OP_IF + OP_DUP. OP_ROLL needs to read its operand, then move that many elements on the stack. It is the only operand for which the stack manipuilation cost is variable (and, regretfully, non-trivial), so we need to limit it. A reasonable implementation (and the current bitcoind C++ implementation) is to use 24 bytes for each stack element (a pointer, a size and a maximum capacity), and this value works reasonably in practice. ===Example: Comparison Operators=== {| ! Opcode ! Varops Budget Cost |- |OP_BOOLAND |length(A) + length(B) |COMPARINGZERO |- |OP_BOOLOR |length(A) + length(B) |COMPARINGZERO |- |OP_NUMEQUAL |MAX(length(A), length(B)) |COMPARING + COMPARINGZERO |- |OP_NUMEQUALVERIFY |MAX(length(A), length(B)) |COMPARING + COMPARINGZERO |- |OP_NUMNOTEQUAL |MAX(length(A), length(B)) |COMPARING + COMPARINGZERO |- |OP_LESSTHAN |MAX(length(A), length(B)) |COMPARING + COMPARINGZERO |- |OP_GREATERTHAN |MAX(length(A), length(B)) |COMPARING + COMPARINGZERO |- |OP_LESSTHANOREQUAL |MAX(length(A), length(B)) |COMPARING + COMPARINGZERO |- |OP_GREATERTHANOREQUAL |MAX(length(A), length(B)) |COMPARING + COMPARINGZERO |- |OP_MIN |MAX(length(A), length(B)) * 2 |OTHER |- |OP_MAX |MAX(length(A), length(B)) * 2 |OTHER |- |OP_WITHIN |MAX(length(C), length(B)) + MAX(length(C), length(A)) |COMPARING + COMPARINGZERO |} ====Rationale==== Numerical comparison in little-endian numbers involves a byte-by-byte comparison, then if one is longer, checking that the remainder is all zero bytes. However, OP_MAX and OP_MIN also normalize their result, which means they can't use the optimized comparison routine but must instead track the final non-zero byte to perform truncation. ===Example: Hash Operators=== {| ! Opcode ! Varops Budget Cost | Reason |- |OP_SHA256 |(Length of the operand) * 10 |HASH |- |OP_HASH160 |(Length of the operand) * 10 |HASH |- |OP_HASH256 |(Length of the operand) * 10 |HASH |} ====Rationale==== SHA256 has been well-optimized for current hardware, as it is already critical to Bitcoin's operation. Additional once-off steps such as the final SHA round, and RIPEMD or a second SHA256 are not proportional to the input, so are not included in the cost model. A model for other hash operations (OP_SHA1, OP_RIPEMD160) is possible, but we have not done so. They are not generally optimized, and if they were permitted on large inputs, this would have to be done. ==Reference Implementation== Work in progress: https://github.com/jmoik/bitcoin/tree/gsr ==Thanks== This BIP would not exist without the thoughtful contributions of coders who considered all the facets carefully and thoroughly, and also my inspirational wife Alex and my kids who have been tirelessly supportive of my esoteric-seeming endeavors such as this! In alphabetical order: - Anthony Towns - Brandon Black (aka Reardencode) - John Light - Jonas Nick - Rijndael (aka rot13maxi) - Steven Roose - FIXME: your name here! == Footnotes == <references /> -- You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group. To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/874isonniq.fsf%40rustcorp.com.au. ^ permalink raw reply [flat|nested] 5+ messages in thread
* [bitcoindev] [2/4] Restoration of disabled script functionality (Tapscript v2) 2025-09-27 11:27 ` [bitcoindev] [1/4] Varops Budget For Script Runtime Constraint Rusty Russell @ 2025-09-27 11:28 ` Rusty Russell 2025-09-27 11:29 ` [bitcoindev] [3/4] OP_TX Rusty Russell 0 siblings, 1 reply; 5+ messages in thread From: Rusty Russell @ 2025-09-27 11:28 UTC (permalink / raw) To: bitcoindev; +Cc: Julian Moik Hi all! This BIP is the core restoration. All the operations come back, and stack limits are increased (though not infinitely), and integers are not limited to 31 bits. The main difference is that all integers are now unsigned: the combination of variable length and sign bit was a side-effect of the SSL bignum representation and has proven awkward to deal with. A word on the example implementation which was used to benchmark: it treats numerical stack objects 64 bits at a time, but does not go so far as using assembly code. It also had to implement a proper stack class, because the time to enforce the new "total stack size limit" naively was measurable. I consider it a fair benchmark when considering how a straightforward implementation would perform. Thank you for your consideration, Rusty. <pre> BIP: ? Layer: Consensus (soft fork) Title: Restoration of disabled script functionality (Tapscript v2) Author: Rusty Russell <rusty@rustcorp•com.au> Julian Moik <julianmoik@gmail•com> Comments-URI: TBA Status: Draft Type: Standards Track Created: 2025-05-16 License: BSD-3-Clause </pre> ==Introduction== ===Abstract=== This new BIP introduces a new tapleaf version (0xc2) which restores Bitcoin script to its pre-0.3.1 capability, relying on the Varops Budget in [[bip-unknown-varops-budget.mediawiki|BIP-varops]] to prevent the excessive computational time which caused CVE-2010-5137. In particular, this BIP: - Reenables disabled opcodes. - Increases the maximum stack object size from 520 bytes to 4,000,000 bytes. - Introduces a total stack byte limit of 8,000,000 bytes. - Increases the maximum total number of stack objects from 1000 to 32768. - Removes the 32-bit size restriction on numerical values. - Treats all numerical values as unsigned. ===Copyright=== This document is licensed under the 3-clause BSD license. ===Motivation=== Since Bitcoin v0.3.1 (addressing CVE-2010-5137), Bitcoin's scripting capabilities have been significantly restricted to mitigate known vulnerabilities related to excessive computational time and memory usage. These early safeguards were necessary to prevent denial-of-service attacks and ensure the stability and reliability of the Bitcoin network. Unfortunately, these restrictions removed much of the ability for users to control the exact spending conditions of their outputs, which has frustrated the long-held ideal of programmable money without third-party trust. ==Execution of Tapscript v2== If a taproot leaf has a version of 0xc2, execution of opcodes is as defined below. All opcodes not explicitly defined here are treated exactly as defined by [[bip-0342.mediawiki|BIP342]]. Validation of a script fails if: - It exceeds the remaining varops budget for the transaction. - Any stack element exceeds 4,000,000 bytes. - The total size of all stack (and altstack) elements exceeds 8,000,000 bytes. - The number of stack elements (including altstack elements) exceeds 32768. ===Rationale=== There needs to be some limit on memory usage, to avoid a memory-based denial of service. Putting the entire transaction on the stack is a foreseeable use case, hence using the block size (4MB) as a limit makes sense. However, allowing 4MB stack elements is a significant increase in memory requirements, so a total limit of twice that many bytes (8MB) is introduced. Many stack operations require making at least one copy, so this allows such use. Putting all outputs or inputs from the transaction on the stack as separate elements requires as much stack capacity as there are inputs or outputs. The smallest possible input is 34 bytes (allowing almost 26411 inputs), and the smallest possible output is 9 bytes (allowing almost 111111 inputs). However, empty outputs are rare and not economically interesting. Thus we consider smallest non-OP_RETURN standard output script, which is P2WPKH at 22 bytes, giving a minimum output size of 31 bytes, allowing 32258 outputs in a maximally-sized transaction. This makes 32768 a reasonable upper limit for stack elements. ===SUCCESS Opcodes=== The following opcodes are renamed OP_SUCCESSx, and cause validation to immediately succeed: * OP_1NEGATE = OP_SUCCESS79 * OP_NEGATE = OP_SUCCESS143 * OP_ABS = OP_SUCCESS144<ref>Anthony Towns suggested this could become an opcode which normalized the value on the top of the stack by truncating any trailing zeroes.</ref> ====Rationale==== Negative numbers are not natively supported in v2 Tapscript. Arbitrary precision makes them difficult to manipulate and negative values are not used meaningfully in bitcoin transactions. ===Non-Arithmetic Opcodes Dealing With Stack Numbers=== The following opcodes are redefined in v2 Tapscript to read numbers from the stack as arbitrary-length little-endian values (instead of CScriptNum): 1. OP_CHECKLOCKTIMEVERIFY 2. OP_CHECKSEQUENCEVERIFY 3. OP_VERIFY 4. OP_PICK 5. OP_ROLL 6. OP_IFDUP 7. OP_CHECKSIGADD These opcodes are redefined in v2 Tapscript to write numbers to the stack as minimal-length little-endian values (instead of CScriptNum): 1. OP_CHECKSIGADD 2. OP_DEPTH 3. OP_SIZE In addition, the [[bip-0342.mediawiki#specification|BIP-342 success requirement]] is modified to require a non-zero variable-length unsigned integer value (not <code>CastToBool()</code>): 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. ===Enabled Opcodes=== Fifteen opcodes which were removed in v0.3.1 are re-enabled in v2 Tapscript. If there are less than the required number of stack elements, these opcodes fail validation. Equivalently, a requirement to pop off the stack which cannot be satisfied causes the opcode to fail validation. See [[bip-unknown-varops-budget.mediawiki|BIP-varops]] for the meaning of the annotations in the varops cost field. ====Splice Opcodes==== {| ! Opcode ! Value ! Required Stack Elements ! Varops Cost ! Varops Reason ! Definition |- |OP_CAT |126 |2 |length(A) + length(B) |COPYING | # Pop B off the stack. # Pop A off the stack. # Append B to A. # Push A onto the stack. |- |OP_SUBSTR |127 |3 |length(LEN) + length(BEGIN) + MIN(Value of LEN, length(A) - Value of BEGIN, 0) |LENGTHCONV + COPYING | # Pop LEN off the stack. # Pop BEGIN off the stack. # Pop A off the stack. # Remove BEGIN bytes from the front of A (all bytes if BEGIN greater than length of A). # If length(A) is greater than value(LEN), truncate A to length value(LEN). # Push A onto the stack. |- |OP_LEFT |128 |2 |length(OFFSET) |LENGTHCONV | # Pop OFFSET off the stack. # Pop A off the stack. # If length(A) is greater than value(OFFSET), truncate A to length value(OFFSET). # Push A onto the stack. |- |OP_RIGHT |129 |2 |length(OFFSET) + value of OFFSET |LENGTHCONV + COPYING | # Pop OFFSET off the stack. # Pop A off the stack. # Copy value(OFFSET) bytes from offset length(A) - value(OFFSET) to offset 0, if value(OFFSET) is less than length(A). # Push A onto the stack. |} =====Rationale===== OP_CAT may require a reallocation of A (hence, COPYING A) before appending B. OP_SUBSTR may have to copy LEN bytes, but also needs to read its two numeric operands. LEN is limited to the length of the operand minus BEGIN. OP_LEFT only needs to read its OFFSET operand (truncation is free), whereas OP_RIGHT must copy the bytes, which depends on the OFFSET value. ====Bit Operation Opcodes==== {| ! Opcode ! Value ! Required Stack Elements ! Varops Cost ! Varops Reason ! Definition |- |OP_INVERT |131 |1 |length(A) * 2 |OTHER | # Pop A off the stack. # For each byte in A, replace it with that byte bitwise XOR 0xFF (i.e. invert the bits) # Push A onto the stack. |- |OP_AND |132 |2 |length(A) + length(B) |OTHER + ZEROING | # Pop B off the stack. # Pop A off the stack. # If B is longer than A, swap B and A. # For each byte in A (the longer operand): bitwise AND it with the equivalent byte in B (or 0 if past end of B) # Push A onto the stack. |- |OP_OR |133 |2 |MIN(length(A), length(B)) * 2 |OTHER | # 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. # Push A onto the stack. |- |OP_XOR |134 |2 |MIN(length(A), length(B)) * 2 |OTHER | # 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. # 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. ====Bitshift Opcodes==== Note that these are raw bitshifts, unlike the sign-preserving arithmetic shifts in Bitcoin v0.3.0, and as such they also do not truncate trailing zeroes from results: they are renamed OP_UPSHIFT (nee OP_LSHIFT) and OP_DOWNSHIFT (nee OP_RSHIFT). {| ! Opcode ! Value ! Required Stack Elements ! Varops Cost ! Varops Reason ! Definition |- |OP_UPSHIFT |152 |2 |length(BITS) + (Value of BITS) / 8 + length(A). If BITS % 8 != 0, add length(A) * 2 |LENGTHCONV + ZEROING + COPYING. If BITS % 8 != 0, + OTHER. | # Pop BITS off the stack. # Pop A off the stack. # If A shifted by value(BITS) would exceed the individual stack limit, fail. # If value(BITS) % 8 == 0: simply prepend value(BITS) / 8 zeroes to A. # Otherwise: prepend (value(BITS) / 8) + 1 zeroes to A, then shift A *down* (8 - (value(BITS) % 8)) bits. # Push A onto the stack. |- |OP_DOWNSHIFT |153 |2 |length(BITS) + MAX((length(A) - (Value of BITS) / 8), 0) * 2 |LENGTHCONV + OTHER | # Pop BITS off the stack. # Pop A off the stack. # For BITOFF from 0 to (length(A)-1) * 8 - value(BITS): # Copy each bit in A from BITOFF + value(BITS) to BITOFF. # Truncate A to remove value(OFF) bytes (or all, if value(OFF) > length(A)). # Push A onto the stack. |} =====Rationale===== DOWNSHIFT needs to read the value of the second operand BITS. It then needs to move the remainder of A (the part after offset BITS/8 bytes). In practice this should be implemented in word-size chunks, not bit-by-bit! UPSHIFT also needs to read BITS. In general, it may need to reallocate (copying A and zeroing out remaining words). If not moving an exact number of bytes (BITS % 8 != 0), another pass is needed to perform the bitshift. OP_UPSHIFT can produce huge results, and so must be checked for limits prior to evaluation. It is also carefully defined to avoid reallocating twice (reallocating to prepend bytes, then again to append a single byte) which has the practical advantage of being able to share the same downward bitshift routine as OP_DOWNSHIFT. ====Multiply and Divide Opcodes=== {| ! Opcode ! Value ! Required Stack Elements ! Varops Cost ! Varops Reason ! Definition |- |OP_2MUL |141 |1 |length(A) * 3 |OTHER + COPYING | # Pop A off the stack. # Shift each byte in A 1 bit to the left (increasing values, equivalent to C's << operator), tracking the last non-zero value. # If the final byte overflows, append a single 1 byte. # Otherwise, truncate A at the last non-zero byte. # Push A onto the stack. |- |OP_2DIV |142 |1 |length(A) * 2 |OTHER | # Pop A off the stack. # Shift each byte 1 bit to the right (decreasing values, equivalent to C's >> operator), tracking the last non-zero value. # Truncate A at the last non-zero byte. # Push A onto the stack. |-- |OP_MUL |149 |2 |length(A) + length(B) + (length(A) + 7) / 8 * length(B) * 6 (BEWARE OVERFLOW) |See Appendix | # Pop B off the stack. # Pop A off the stack. # Calculate the varops cost of the operation: if it exceeds the remaining budget, fail. # Allocate an all-zero vector R of length equal to length(A) + length(B). # For each word in A, multiply it by B and add it into the vector R, offset by the word offset in A. # Truncate R at the last non-zero byte. # Push R onto the stack. |- |OP_DIV |150 |2 |length(A) * 9 + length(B) * 2 + length(A)^2 / 3 (BEWARE OVERFLOW) |See Appendix | # Pop B off the stack. # Pop A off the stack. # Calculate the varops cost of the operation: if it exceeds the remaining budget, fail. # If B is empty or all zeroes, fail. # Perform division as per Knuth's The Art of Computer Programming v2 page 272, Algorithm D "Division of non-negative integers". # Trim trailing zeroes off the quotient. # Push the quotient onto the stack. |- |OP_MOD |151 |2 |length(A) * 9 + length(B) * 2 + length(A)^2 / 3 (BEWARE OVERFLOW) |See Appendix | # Calculate the varops cost of the operation: if it exceeds the remaining budget, fail. # If B is empty or all zeroes, fail. # Perform division as per Knuth's The Art of Computer Programming v2 page 272, Algorithm D "Division of non-negative integers". # Trim trailing zeroes off the remainder. # Push the remainder onto the stack. |} =====Rationale===== These opcodes can be computationally intensive, which is why the varops budget must be checked before operations. OP_2MUL and OP_2DIV are far simpler, equivalent to OP_UPSHIFT and OP_DOWNSHIFT by 1 bit, except truncating the most-significant zero bytes. The detailed rationale for these costs can be found in Appendix A. ===Limited Hashing Opcodes=== OP_RIPEMD160 and OP_SHA1 are now defined to FAIL validation if their operands exceed 520 bytes.<ref>There seems little reason to allow large hashing with SHA1 and RIPEMD, and they are not as optimized as SHA256, so we restrict their usage to the older byte limit.</ref> ===Extended Opcodes=== The opcodes OP_ADD, OP_SUB, OP_1ADD and OP_1SUB are redefined in v2 Tapscript to operate on variable-length unsigned integers. These always produce minimal values (no trailing zero bytes). {| ! Opcode ! Value ! Required Stack Elements ! Varops Cost ! Varops Reason ! Definition |- |OP_ADD |147 |2 |MAX(length(A), length(B)) * 4 |ARITH + COPYING | # Pop B off the stack. # Pop A off the stack. # Option 1: trim trailing zeroes off A and B. # If B is longer than A, swap A and B. # For each byte in B, add it and previous overflow into the equivalent byte in A, remembering next overflow. # If there was final overflow, append a 1 byte to A. # Option 2: If there was no final overflow, remember last non-zero byte written into A, and truncate A after that point. # Either Option 1 or Option 2 MUST be implemented. |- |OP_1ADD |139 |1 |MAX(1, length(A)) * 4 |ARITH + COPYING | # Pop A off the stack. # Let B = 1, and continue as OP_ADD. |- |OP_SUB |148 |2 |MAX(length(A), length(B)) * 3 |ARITH | # Pop B off the stack. # Pop A off the stack. # For each byte in B, subtract it and previous underflow from the equivalent byte in A, remembering next underflow. # If there was final overflow, fail validation. # Remember last non-zero byte written into A, and truncate A after that point. |- |OP_1SUB |140 |1 |MAX(1, length(A)) * 3 |ARITH | # Pop A off the stack. # Let B = 1, and continue as OP_SUB. |} ====Rationale==== Note the basic cost for ADD is three times the maximum operand length, but then considers the case where a reallocation and copy needs to occur to append the final carry byte (COPYING, which costs 1 unit per byte). Subtraction is cheaper because underflow does not occur: that is a validation failure, as mathematicians agree the result would not be natural. ===Misc Operators=== The following opcodes have costs below: {| ! Opcode ! Varops Budget Cost ! Varops Reason |- | OP_CHECKLOCKTIMEVERIFY | Length of operand | LENGTHCONV |- | OP_CHECKSEQUENCEVERIFY | Length of operand | LENGTHCONV |- | OP_CHECKSIGADD | MAX(1, length(number operand)) * 4 + 26000 | ARITH + COPYING + SIGCHECK |- | OP_CHECKSIG | 26000 | SIGCHECK |- | OP_CHECKSIGVERIFY | 26000 | SIGCHECK |} ====Rationale==== OP_CHECKSIGADD does an OP_1ADD on success, so we use the same cost as that. For simplicity, this is charged whether the OP_CHECKSIGADD succeeds or not. ===Other Operators=== The varops costs of the following opcodes are defined in [[bip-unknown-varops-budget.mediawiki|BIP-varops]]: * OP_VERIFY * OP_NOT * OP_0NOTEQUAL * OP_EQUAL * OP_EQUALVERIFY * OP_2DUP * OP_3DUP * OP_2OVER * OP_IFDUP * OP_DUP * OP_OVER * OP_PICK * OP_TUCK * OP_ROLL * OP_BOOLOR * OP_NUMEQUAL * OP_NUMEQUALVERIFY * OP_NUMNOTEQUAL * OP_LESSTHAN * OP_GREATERTHAN * OP_LESSTHANOREQUAL * OP_GREATERTHANOREQUAL * OP_MIN * OP_MAX * OP_WITHIN * OP_SHA256 * OP_HASH160 * OP_HASH256 Those with costs not defined here have a cost of 0 (they do not operate on variable-length stack objects). ===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 ==Backwards compatibility== This BIP defines a previous unused (and thus, always-successful) tapscript version, for backwards compatibility. ==Reference Implementation== Work in progress: https://github.com/jmoik/bitcoin/tree/gsr ==Thanks== This BIP would not exist without the thoughtful contributions of coders who considered all the facets carefully and thoroughly, and also my inspirational wife Alex and my kids who have been tirelessly supportive of my esoteric-seeming endeavors such as this! In alphabetical order: - Anthony Towns - Brandon Black (aka Reardencode) - John Light - Jonas Nick - Rijndael (aka rot13maxi) - Steven Roose - FIXME: your name here! ==Appendix A: Cost Model Calculations for Multiply and Divide== 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). ===Multiplication Cost==== For multiplication, the steps break down like so: 1. Allocate and zero the result: cost = length(A) + length(B) (ZEROING) 2. For each word in A: * Multiply by each word in B, into a scratch vector: cost = 3 * length(B) (ARITH) * Sum scratch vector at the word offset into the result: cost = 3 * length(B) (ARITH) Note: we do not assume Karatsuba, Tom-Cooke or other optimizations. This results in a cost of: length(A) + length(B) + (length(A) + 7) / 8 * length(B) * 6. This is slightly asymmetric: in practice an implementation usually finds that CPU pipelining means choosing B as the larger operand is optimal. ===Division Cost==== For division, the steps break down like so: 1. Bit shift both operands to set top bit of B (OP_UPSHIFT, without overflow for B): cost = length(A) * 3 + length(B) * 2 2. Trim trailing bytes. This costs according to the number of byte removed, but since that is subtractive on future costs, we ignore it. 3. If B is longer, the answer is 0 already. So assume A is longer from now on (or equal length). 4. Compare: cost = length(A) (COMPARING) 5. Subtract: cost = length(A) * 3 (ARITH) 6. for (length(A) - NormalizedLength(B)) in words: 1. Multiply word by B -> scratch: cost = NormalizedLength(B) * 3 (ARITH) 2. Subtract scratch from A: cost = length(A) * 3 (ARITH) 3. Add B into A (no overflow): cost = length(A) * 3 (ARITH) 4. Shrink A by 1 word. 7. OP_MOD: shift A down, trim trailing zeros: cost = length(A) * 2 8. OP_DIV: trim trailing zeros: cost = length(A) * 2 Note that the loop at step 6 shrinks A every time, so the *average* cost of each iteration is (NormalizedLength(B) * 3 + length(A) * 6) / 2. The cost of step 6 is: (length(A) - NormalizedLength(B)) / 8 * (NormalizedLength(B) * 3 + length(A) * 6) / 2 The worst case here is when NormalizedLength(B) is 0: length(A) * length(A) / 3. The cost for all the steps in either case is: length(A) * 9 + length(B) * 2 + length(A) * length(A) / 3. -- You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group. To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/871pnsnnhh.fsf%40rustcorp.com.au. ^ permalink raw reply [flat|nested] 5+ messages in thread
* [bitcoindev] [3/4] OP_TX 2025-09-27 11:28 ` [bitcoindev] [2/4] Restoration of disabled script functionality (Tapscript v2) Rusty Russell @ 2025-09-27 11:29 ` Rusty Russell 2025-09-27 11:29 ` [bitcoindev] [4/4] New Opcodes for Tapscript v2 Rusty Russell 0 siblings, 1 reply; 5+ messages in thread From: Rusty Russell @ 2025-09-27 11:29 UTC (permalink / raw) To: bitcoindev; +Cc: Julian Moik Hi all, This BIP presents an implementation of generic introspection, giving a UTXO greater control over the conditions under which it may be spent. It is less polished than the previous two BIP drafts, but also simpler. But there's plenty of room to debate the control word! Three things to note: firstly, this opcode would be possible without the previous two BIPs. However, it would be severely limited by 31 bit arithmetic and the 520 byte limit (the `OP_TXHASH` proposal worked around this by hashing the result, for example, which is awkward for anything other than direct comparisons of large parts of the transaction). Secondly, the reason this is specified now is that its existence clarifies the requirements for varops: if an input can query the rest of the transaction, giving it a budget based on its own weight would be overly restrictive, so the varops budget (unlike the sigops budget) is transaction-wide. Finally, note this contains a runtime OP_SUCCESS semantic, for unknown control word bits. This is the most future-proof option, and as the control word must always be moderated by the script (usually, stated outright), does not seem to leave room for accidental success. Looking forward to your feedback! Rusty. <pre> BIP: ? Layer: Consensus (soft fork) Title: OP_TX Author: Rusty Russell <rusty@rustcorp•com.au> Comments-URI: TBA Status: Draft Type: Standards Track Created: 2025-06-16 License: BSD-3-Clause </pre> ==Introduction== ===Abstract=== This BIP introduces a new opcode (OP_TX) for tapscript v2, which allows for convenient and explicit introspection of the current transaction. It redefines the OP_SUCCESS189 tapscript opcode (0xbd) as OP_TX. ===Copyright=== This document is licensed under the 3-clause BSD license. ===Motivation=== The original Bitcoin design was to avoid reliance on trusted third parties, and the scripting system was a way of ensuring this: that the network itself would enforce the spending conditions for an output. This aim is undermined if users cannot specify, with all possible precision and power, the conditions under which their coins can be spent. [[bip-unknown-script-restoration.mediawiki|BIP-scriptrestore]] restores full programmability to Bitcoin's scripting system, but does not make it convenient. The main missing piece is the ability to directly query the transaction attempting to spend an output, beyond merely checking that it is signed by a given set of keys. Many proposals to use this functionality have emerged, including new signature modes, spending restrictions even in case of leaked key material, and more complicated multiparty protocols. This opcode allows directly extracting each piece of the current transaction's contents (and some of its context) onto the stack. This allows arbitrary arithmetic on values and examination of scripts, but an opcode which only allowed extraction of a single type of value at a time would be inefficient in the very common case where specific fields of the transaction are required to be specific exact values. So we explicitly support extraction of multiple values into a single, concatenated stack element, ready for hashing and comparison. ==OP_TX== OP_TX operates as follows: - If the stack is empty, fail validation. - Pop the ''selection_vector'' off the stack (as a little-endian unsigned variable-length integer). - If ''selection_vector'' contains bits not defined in the table below: - Immediately succeed script validation. - Extract the two input selector bits from ''selection_vector'': - TXSELECT_INPUTSELECT_CURRENT: ''first_input'' = current input, ''num_inputs'' = 1 - TXSELECT_INPUTSELECT_ALL: ''first_input'' = 0, ''num_inputs'' = number of inputs - TXSELECT_INPUTSELECT_SINGLE: - if the stack is empty, fail validation. - otherwise pop ''first_input'' off the stack. ''num_inputs'' = 1. - if the input numbered ''first_input'' does not exist, fail validation. - TXSELECT_INPUTSELECT_RANGE (pop start, number from stack) - if the stack has less than 2 elements, fail validation. - otherwise pop ''num_inputs'' then ''first_input'' off the stack. - Extract the two output selector bits from ''selection_vector'': - TXSELECT_OUTPUTSELECT_CURRENT: ''first_output'' = current input, ''num_outputs'' = 1 - TXSELECT_OUTPUTSELECT_ALL: ''first_output'' = 0, ''num_outputs'' = number of outputs - TXSELECT_OUTPUTSELECT_SINGLE: - if the stack is empty, fail validation. - otherwise pop ''first_output'' off the stack. ''num_outputs'' = 1. - if the output numbered ''first_output'' does not exist, fail validation. - TXSELECT_OUTPUTSELECT_RANGE (pop start, number from stack) - if the stack has less than 2 elements, fail validation. - otherwise pop ''num_outputs'' then ''first_output'' off the stack. - If TXSELECT_COLLATE is set in ''selection_vector'': - push an empty element onto the stack. - "output" means "concatenate to the top stack element". - "varint or int" means output the value as a CompactSize - "variable size object" means the length as a CompactSize, then the object - Otherwise: - "output" means "push a new element on the stack under the previous output elements" (i.e. the last output will be the top stack element). - "varint or int" means output the value as a minimally-encoded little-endian integer - "variable size object" means output the object (without length prepended) Examine bits in ''selection_vector'': - If TXSELECT_VERSION is set: - output the nVersion (32 bits) - If TXSELECT_NUM_INPUTS is set: - output the number of inputs as varint or int - For each existing input ''i'' in the range ''first_input'' to ''first_input'' + ''num_inputs'': - If TXSELECT_INPUT_OUTPOINT_HASH is set: - output input ''i''s outpoint hash (32 bytes) - If TXSELECT_INPUT_OUTPOINT_INDEX is set: - output input ''i''s outpoint index (32 bits) - If TXSELECT_INPUT_SCRIPT is set: - output input ''i''s script as a variable size object - If TXSELECT_INPUT_SEQUENCE is set: - output input ''i''s nSequence (32 bits) - If TXSELECT_INPUT_AMOUNT is set: - output input ''i''s input amount (64 bits) - If TXSELECT_INPUT_SCRIPTPUBKEY is set: - output input ''i''s scriptPubkey as a variable size object - If TXSELECT_INPUT_NUM_WITNESSES is set: - output input ''i''s number of witness elements (including any annex) as varint or int. - For each witness stack element (including any annex) in input ''i'': - If TXSELECT_INPUT_WITNESS is set: - output the witness stack element as a variable size object - If TXSELECT_NUM_OUTPUTS is set: - output the number of outputs as varint or int - For each existing output in the range ''first_output'' to ''first_output'' + ''num_outputs'': - If TXSELECT_OUTPUT_AMOUNT is set: - output this output's amount (64 bits) - If TXSELECT_OUTPUT_SCRIPT is set: - output this output's scriptPubkey as a variable size object - If TXSELECT_LOCKTIME is set: v - output the nLocktime field (32 bits) - If TXSELECT_CURR_INPUT_NUMBER is set: - output the current 0-based input number as varint or int. - The varops cost for each operation is 2 units per byte output. - As always, validation fails if: - the top stack element exceeds 4,000,000 bytes, or - the total bytes on the stack exceeds 8,000,000 bytes, or - the total number of stack entries exceeds 1000, or - the varops cost exceeds the remaining varops budget. ===Rationale=== The runtime success semantics for unknown bits in ''section_vector'' improves upgradability, by allowing other bits to be specified in future in a backwards-compatible manner. Unfortunately, unlike OP_SUCCESS semantics defined in [[bip-0342.mediawiki|BIP342]], this cannot generally be evaluated before script execution begins, because it's possible (and occasionally useful) to allow ''section_vector'' to be altered at runtime. Where this is done, it needs to be constrained to a certain subset anyway (such as setting TXSELECT_COLLATE), so preventing unknown bits is not a significant additional burden on the script. The use of four selection values for inputs and outputs recognises the common cases of either all, or only the current input (and, SIGHASH_SINGLE-style, the matching output) while allowing more flexibility for the general case of requesting specific inputs or outputs. The TXSELECT_COLLATE option is an optimization for concatenation; the representation of numbers changes from arithmetic-convenient to linearization-convenient, and size prepended to variable length objects, so that there is no possible ambiguity over the results. The order of field output is txid order, with fields which do not appear in the txid appended appropriately. Without a strong demonstrated reason for a different ordering in practice, using established ordering should be preferred. The varops cost is slightly higher than simply stack copying, reflecting a conservative view that some fields are not as immediately available as stack elements. It is still cheap enough to allow accessing the entire transaction many times over: the weight of the OP_TX opcode itself provides enough budget to access 2600 bytes. ===Values For TXID-Relevant Selectors=== These selectors enumerate parts of the transaction which are hashed into the txid: {| ! Selector Name ! Selector Value |- |TXSELECT_COLLATE |0x1 |- |TXSELECT_VERSION |0x2 |- |TX1SELECT_NUM_INPUTS |0x4 |- |TXSELECT_INPUT_OUTPOINT_HASH |0x8 |- |TXSELECT_INPUT_OUTPOINT_INDEX |0x10 |- |TXSELECT_INPUT_SCRIPT |0x20 |- |TXSELECT_INPUT_SEQUENCE |0x40 |- |TXSELECT_NUM_OUTPUTS |0x80 |- |TXSELECT_OUTPUT_AMOUNT |0x100 |- |TXSELECT_OUTPUT_SCRIPT |0x200 |- |TXSELECT_OUTPUT_LOCKTIME |0x400 |} ===Values For Input Selector and Output Selector Bits=== The input selectors, controlling which inputs are enumerated, are bits 11 and 12: {| ! Selector Name ! Selector Value |- |TXSELECT_INPUTSELECT_ALL |0 |- |TXSELECT_INPUTSELECT_CURRENT |0x800 |- |TXSELECT_INPUTSELECT_SINGLE |0x1000 |- |TXSELECT_INPUTSELECT_RANGE |0x1800 |} The output selectors, controlling which outputs are enumerated, are bits 13 and 14: {| ! Selector Name ! Selector Value |- |TXSELECT_OUTPUTSELECT_ALL |0 |- |TXSELECT_OUTPUTSELECT_CURRENT |0x2000 |- |TXSELECT_OUTPUTSELECT_SINGLE |0x4000 |- |TXSELECT_OUTPUTSELECT_RANGE |0x6000 |} ===Values For Input Metadata Selection=== These select additional data about the input which is not committed in the txid, as well as the current input number: {| ! Selector Name ! Selector Value |- |TXSELECT_CURR_INPUT_NUMBER |0x8000 |- |TXSELECT_INPUT_AMOUNT |0x10000 |- |TXSELECT_INPUT_SCRIPTPUBKEY |0x20000 |- |TXSELECT_INPUT_NUM_WITNESSES |0x40000 |- |TXSELECT_INPUT_WITNESS |0x80000 |} ==Reference Implementation== None as yet. ==Thanks== I stand here on the shoulder of giants, including Russell O'Connor's original OP_TXHASH proposal and Steven Roose's subsequent elaboration of that work. I also credit Jeremy Rubin for his tireless work exploring the uses of covenants and his OP_CHECKTEMPLATEVERIFY proposal. While I ultimately found those proposal unsatisfying, it was their daunting intellectual prowess which forced me to slowly develop the groundwork for a proposal to meet the high standards they have set. ==TODO== The ordering of bits in the ''selection_vector'' is unoptimized: if a mask only uses the first four bits it can be put on the stack in a single opcode byte, two opcode bytes for eight bits, three for sixteen. This is ripe for consideration by greater minds (aka "bikeshedding"). In particular, an all-zero mask for OP_TX makes no sense, so it could be defined to mean some pre-determined mask: for example, the OP_CHECKTEMPLATEVERIFY proposal commits to the data in (though not the form of) COLLATE|VERSION|NUM_INPUTS|TXSELECT_INPUT_SCRIPT|NUM_OUTPUTS|OUTPUT_AMOUNT|OUTPUT_SCRIPT|OUTPUT_LOCKTIME|CURR_INPUT_NUMBER. -- You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group. To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/87y0q0m8vz.fsf%40rustcorp.com.au. ^ permalink raw reply [flat|nested] 5+ messages in thread
* [bitcoindev] [4/4] New Opcodes for Tapscript v2 2025-09-27 11:29 ` [bitcoindev] [3/4] OP_TX Rusty Russell @ 2025-09-27 11:29 ` Rusty Russell 0 siblings, 0 replies; 5+ messages in thread From: Rusty Russell @ 2025-09-27 11:29 UTC (permalink / raw) To: bitcoindev; +Cc: Julian Moik Hi all! Now for the least polished BIP, which proposes a scattering of new opcodes. These need not be deployed at the same time, and some may not ever qualify. But as they they might have interactions with other proposals, I feel we are obligated to peer over this horizon a little. Many of these are not mine, and I definitely feel remiss in not giving canonical references (I would appreciate this feedback!). Thank you for you consideration! Rusty. <pre> BIP: ? Layer: Consensus (soft fork) Title: New Opcodes for Tapscript v2 Author: Rusty Russell <rusty@rustcorp•com.au> Comments-URI: TBA Status: Draft Type: Standards Track Created: 2025-06-17 License: BSD-3-Clause </pre> ==Introduction== ===Abstract=== This BIP proposes several new opcodes for tapscript v2, to take full advantage of scripting enhancements and covenant facilities offered by OP_TX. ===Copyright=== This document is licensed under the 3-clause BSD license. ===Motivation=== Restoration of opcodes and introspection make script much more useful, and thus increase the range of things we may want to do. This, in turn, highlights some existing shortfalls in Script, both in the way it handles multiple stack objects, and when attempting to reproduce modern Taproot constructions. This list of opcodes is not exhaustive, but each offers some significant capability which was previously impossible or extremely awkward in script. A key motivation for these changes lies in future possible BIPs: once script is well-rounded (if not "complete"), most proposals will be optimizations, whose benifits can be quantitatively assessed based on actual usage. ==New Opcodes== ;OP_CHECKSIGFROMSTACK : A subset of OP_CHECKSIG. With OP_TX and OP_SHA256 we have the part of CHECKSIG which obtains and hashes parts of the transaction. What remains is being able to check a signature against a hash on the stack. OP_CHECKSIGFROMSTACK provides this. The varops cost is the same as a CHECKSIG operation. ;OP_SEGMENT : This opcode remains an NOP. But it makes script parts ''composable'': currently you cannot append two scripts, because OP_SUCCESS causes immediate success without script evaluation. OP_SEGMENT changes this rule to ''segment'' the script into parts, which are evaluated in order. If a segment does not have OP_SUCCESS, that part of the script is evaluated. This allows a transaction to ensure some condition is met, but also allow arbitrary script conditions thereafter. ;OP_BYTEREV : This is the minimium requirement for constructing ordered Merkle trees as specified in Taproot. Unfortunately, hashes need to be compared left to right, where Script opcodes operate right to left (as per little endian numbers). Alternatives would be a direct OP_REVCMP opcode, or even a dedicated Merkle opcode, but byte reversal can be generally useful. ;OP_ECPOINTADD : Also required for constructing Taproot spends. The varops cost is the same as a CHECKSIG operation. ;OP_INTERNALKEY : An optimization: an unspendable keypath for Taproot simply wastes space. If this is not changed in a future version, OP_INTERNALKEY at least allows the script to use this data for something else. An alternative would be another OP_TX ''selection_vector'' bit. See [[bip-0349.mediawiki|BIP-349]]. ;OP_MULTI : Several opcodes would benefit from a variant which takes the number of operands off the stack. Instead of introducing many more opcodes, we propose OP_MULTI as a prefix to the following opcode which pops a number off the stack, and makes the next opcode operate on more than its usual number of operands: OP_CAT, OP_ADD, OP_SHA256, OP_DUP, OP_DROP, OP_MIN, OP_MAX, OP_AND, OP_OR, OP_BOOLAND, OP_BOOLOR, OP_EQUAL. This is simpler than introducing general iteration into script, and intuitive to constrain using varops. It is particularly beneficial when examining inputs or outputs of a transaction, such as calculating fees. ===Rationale=== Bitcoin script was developed long before Taproot: OP_ECPOINTADD and OP_BYTEREV are the minimal missing opcodes required for creating Taproot trees in script. The need for OP_CHECKSIGFROMSTACK and OP_SEGMENT are a side-effect of generic introspection, into the tx itself for arbitrary signature coverage, and into scripts to allow specification of partial spending requirements. OP_INTERNALKEY is trivial, but can save 32 weight on a transaction in many cases, which is a non-trivial savings. OP_MULTI is more complex, but allows for much more general handling of multiple inputs or outputs: bitcoin script does not have iteration, so all possible numbers have to be handled directly, which is unwieldy at best. There are definitely other opcodes which would be helpful, but from this point most are "merely" optimizations from what is now possible. This itself is a major milestone: that future opcode proposals can be assessed numerically, by measuring the impact they would have on aggregate onchain space, and from there assessing whether the cost of implementation and deployment is worth the savings. ===Detailed Specification=== TBA. ==Reference Implementation== None as yet. ==TODO== - Are there other fundamental building blocks we are missing? I don't see an immediate reason for OP_ECPOINTMUL, for example, but it would not be possible in script today (due to varops limits). - If we do want OP_INTERNALKEY, it should probably be a OP_TX selector bit. - Is OP_MULTI too ambitious? I previously considered for-each-input and for-each-output iterators, but this is far simpler. - Can we come up with a better name for OP_CHECKSIGFROMSTACK? Unfortunately OP_CHECKSIG is taken, but OP_THE_REAL_CHECKSIG isn't! == Footnotes == <references /> -- You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group. To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/87tt0om8uz.fsf%40rustcorp.com.au. ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2025-09-27 13:23 UTC | newest] Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2025-09-27 8:12 [bitcoindev] [0/4] A Bitcoin Scripting Proposal BIP Quartet Rusty Russell 2025-09-27 11:27 ` [bitcoindev] [1/4] Varops Budget For Script Runtime Constraint Rusty Russell 2025-09-27 11:28 ` [bitcoindev] [2/4] Restoration of disabled script functionality (Tapscript v2) Rusty Russell 2025-09-27 11:29 ` [bitcoindev] [3/4] OP_TX Rusty Russell 2025-09-27 11:29 ` [bitcoindev] [4/4] New Opcodes for Tapscript v2 Rusty Russell
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox