Delivery-date: Sat, 27 Sep 2025 06:22:55 -0700
Sender: bitcoindev@googlegroups.com
Received-SPF: pass (google.com: domain of rusty@gandalf.ozlabs.org designates 150.107.74.76 as permitted sender) client-ip=150.107.74.76;
From: Rusty Russell <bitcoin-dev@rustcorp.com.au>
To: bitcoindev@googlegroups.com
Subject: [bitcoindev] [1/4] Varops Budget For Script Runtime Constraint
In-Reply-To: <877bxknwk6.fsf@rustcorp.com.au>
Date: Sat, 27 Sep 2025 20:57:41 +0930
Message-ID: <874isonniq.fsf@rustcorp.com.au>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

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>

=3D=3DIntroduction=3D=3D

=3D=3D=3DAbstract=3D=3D=3D

This new BIP defines a "varops budget", which generalizes the "sigops budge=
t" introduced in [[bip-0342.mediawiki|BIP342]] to non-signature operations.

This BIP is a useful framework for other BIPs to draw upon, and provides op=
code examples which are always less restrictive than current rules.

=3D=3D=3DCopyright=3D=3D=3D

This document is licensed under the 3-clause BSD license.

=3D=3D=3DMotivation=3D=3D=3D

Since Bitcoin v0.3.1 (addressing CVE-2010-5137), Bitcoin's scripting capabi=
lities have been significantly restricted to mitigate known vulnerabilities=
 related to excessive computational time and memory usage.  These early saf=
eguards 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 potent=
ial performance pitfalls by severely limiting their scope, introducing spec=
ialized caching strategies to mitigate execution costs, or using the existi=
ng sigops budget in ad-hoc ways to enforce dynamic execution limits.

This BIP introduces a simple, systematic and explicit cost framework for ev=
aluating script operations based on stack data interactions, using worst-ca=
se behavior as the limiting factor.  Even with these pessimistic assumption=
s, large classes of scripts can be shown to be within budget (for all possi=
ble inputs) by static analysis.

=3D=3D=3DA Model For Opcodes Dealing With Stack Data=3D=3D=3D

Without an explicit and low limit on the size of stack operands, the bottle=
neck for script operations is based on the time taken to process the stack =
data it accesses (the exceptions being signature operations).  The cost mod=
el uses the length of the stack inputs (or occasionally, outputs), hence th=
e 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 mult=
iple times): random accesses would require an extension to the model.
- We assume object size is limited to the entire transaction (4,000,000 byt=
es, 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 a=
n implementation which is more efficient than the versions modeled does not=
 introduce any problems (though a future soft-fork version may want to refl=
ect this in reduced costings): only an implementation with a significantly =
worse worst-case behavior would be problematic.

=3D=3DDesign=3D=3D

A per-transaction integer "varops budget" is determined by multiplying the =
total transaction weight by the fixed factor 5,200<ref>As the most expensiv=
e non-signature operation (SHA256 hashing) is 10 varops per byte, and the l=
argest previously-allowed stack element size is 520, it is trivial to demon=
strate that no non-signature operation previously allows can violate the va=
rops budget, as the weight of the opcode itself provides 5200 budget).</ref=
>.  The budget is transaction-wide (rather than per-input) to allow for cro=
ss-input introspection: a small input may reasonably access larger inputs.

Opcodes consume budget as they are executed, based on the length (not gener=
ally the value) of their parameters as detailed below.  A transaction which=
 exceeds its budget fails to validate.

=3D=3D=3DDerivation of Costs=3D=3D=3D

The costs of opcodes were determined by benchmarking on a variety of platfo=
rms. =20

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 scr=
ipts 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 sta=
ck elements that are not included in the limits for conservatism.

Ideally, on each platform we tested, the worst case time for each opcode wo=
uld be no worse than the Schnorr signature upper bound: i.e. the block woul=
d 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.me=
diawiki||BIP-342]] limit: 50 weight units allows you one signature.  Since =
each transaction gets varops budget for the entire transaction (not just th=
e current input's witness), and each input has at least 40 bytes (160 weigh=
t), this is actually slightly more generous than the sigops budget (which w=
as 50 + witness weight), but still limits the entire block to 80,000 signat=
ures.

=3D=3D=3DBenchmarks=3D=3D=3D

{|
! 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 ./bui=
ld/bin/bench_varops --epochs 5 --file data.csv

=3D=3D=3DCost Categories=3D=3D=3D

We divided operations into five speed categories:

# Signature operations.=20
# SHA256 operations.
# OP_ROLL, which does a large-scale stack movement.
# Fast operations: comparing bytes, comparing bytes against zero, copying b=
ytes and zeroing bytes.  Empirically, these have been shown to be well-opti=
mized.
# 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 valu=
e of its operand).
# Fast operations cost 1 unit per byte output.
# Other operations cost 2 units per byte output.

=3D=3D=3DVariable Opcode Budget=3D=3D=3D

We use the following annotations to indicate the derivation for each opcode=
:

;COMPARING
: Comparing two objects: cost =3D 1 per byte compared.
;COMPARINGZERO
: Comparing an object against zeroes: cost =3D 1 per byte compared.
;ZEROING
: Zeroing out bytes: cost =3D 1 per byte zeroed
;COPYING
: Copying bytes: cost =3D 1 per byte copied.
;LENGTHCONV
: Converting an operand to a length value, including verifying that trailin=
g bytes are zero: cost =3D 1 per byte copied.
;SIGCHECK
: Checking a signature is a flat cost: cost =3D 260,000.
;HASH
: cost =3D 10 per byte hashed.
;ROLL
: cost =3D 24 per stack element moved.
;OTHER
: all other operations which take a variable-length parameter: cost =3D 2 p=
er byte written.

Note that COMPARINGZERO is a subset of COMPARING: an implementation must ex=
amine every byte of a stack element to determine if the value is 0.  This c=
an 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 h=
ave 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.

=3D=3DExample Opcodes=3D=3D

The following opcodes demonstrate the approach, with an analysis of how the=
 costs apply:

=3D=3D=3DExample: Control And Simple Examination Opcodes=3D=3D=3D

{|
! 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) !=3D length(B): 0, otherwise length(A)
|COMPARING
|-
|OP_EQUALVERIFY
|If length(A) !=3D length(B): 0, otherwise length(A)
|COMPARING
|}

=3D=3D=3D=3DRationale=3D=3D=3D=3D

OP_IF and OP_NOTIF in Tapscript require minimal values, so do not take vari=
able 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.

=3D=3D=3DExample: Stack Manipulation=3D=3D=3D

{|
! 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
|-
|}

=3D=3D=3D=3DRationale=3D=3D=3D=3D

These operators copy a stack entry, write to another.  OP_IFDUP has the sam=
e worst-case cost as OP_IF + OP_DUP.

OP_ROLL needs to read its operand, then move that many elements on the stac=
k.  It is the only operand for which the stack manipuilation cost is variab=
le (and, regretfully, non-trivial), so we need to limit it.

A reasonable implementation (and the current bitcoind C++ implementation) i=
s to use 24 bytes for each stack element (a pointer, a size and a maximum c=
apacity), and this value works reasonably in practice.

=3D=3D=3DExample: Comparison Operators=3D=3D=3D

{|
! 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
|}

=3D=3D=3D=3DRationale=3D=3D=3D=3D

Numerical comparison in little-endian numbers involves a byte-by-byte compa=
rison, 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 ca=
n't use the optimized comparison routine but must instead track the final n=
on-zero byte to perform truncation.

=3D=3D=3DExample: Hash Operators=3D=3D=3D

{|
! 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
|}

=3D=3D=3D=3DRationale=3D=3D=3D=3D

SHA256 has been well-optimized for current hardware, as it is already criti=
cal to Bitcoin's operation.  Additional once-off steps such as the final SH=
A round, and RIPEMD or a second SHA256 are not proportional to the input, s=
o 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 pe=
rmitted on large inputs, this would have to be done.

=3D=3DReference Implementation=3D=3D

Work in progress:

	https://github.com/jmoik/bitcoin/tree/gsr

=3D=3DThanks=3D=3D

This BIP would not exist without the thoughtful contributions of coders who=
 considered all the facets carefully and thoroughly, and also my inspiratio=
nal wife Alex and my kids who have been tirelessly supportive of my esoteri=
c-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!

=3D=3D Footnotes =3D=3D

<references />

--=20
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 e=
mail to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/=
874isonniq.fsf%40rustcorp.com.au.