From: Rusty Russell <bitcoin-dev@rustcorp•com.au>
To: bitcoindev@googlegroups.com
Subject: [bitcoindev] [1/4] Varops Budget For Script Runtime Constraint
Date: Sat, 27 Sep 2025 20:57:41 +0930 [thread overview]
Message-ID: <874isonniq.fsf@rustcorp.com.au> (raw)
In-Reply-To: <877bxknwk6.fsf@rustcorp.com.au>
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.
next prev parent reply other threads:[~2025-09-27 13:22 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-09-27 8:12 [bitcoindev] [0/4] A Bitcoin Scripting Proposal BIP Quartet Rusty Russell
2025-09-27 11:27 ` Rusty Russell [this message]
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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=874isonniq.fsf@rustcorp.com.au \
--to=bitcoin-dev@rustcorp$(echo .)com.au \
--cc=bitcoindev@googlegroups.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox