1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
|
Delivery-date: Sat, 27 Sep 2025 06:22:55 -0700
Received: from mail-oa1-f64.google.com ([209.85.160.64])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBAABBJGK37DAMGQELSXMXAQ@googlegroups.com>)
id 1v2Ut4-0007EO-Oi
for bitcoindev@gnusha.org; Sat, 27 Sep 2025 06:22:55 -0700
Received: by mail-oa1-f64.google.com with SMTP id 586e51a60fabf-35568e6088asf4684597fac.0
for <bitcoindev@gnusha.org>; Sat, 27 Sep 2025 06:22:54 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1758979368; cv=pass;
d=google.com; s=arc-20240605;
b=kfK70CIkc44spebQQeF29o4jdBYZRrBdExyIxpoFXtPsikHU+qi+IbFBKRTfKmmVQF
hLbMlf0UGpj2kgSBLHxlO24aXjNlH6mWT+qaYSF+mrs0AF7XuaqtlAMTk3k7UpaLq9mK
4Ecsp3zfOdcENXEtNKN5bAuEfCK67IvbLOnroCe3JYny3X8qOAavJfW8d8emxOz9sQ+S
p7SmvtgE2s9KX8Gl3ES3oU1koAsOUW5rlvmafgWEX8P8WPllXVUjc0Mu0ue0YZOE/aJu
eFs5vlIJ8XvKy1LqSnUyrK7hWNC1Qz3V6sz4EhtDqGUgSf3Bs6zqXBy2XOBrUApd8J7t
O/5g==
ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:content-transfer-encoding
:mime-version:message-id:date:in-reply-to:subject:to:from:sender
:dkim-signature;
bh=PVHG8HwIATqiLddMwMSB7YH2ciLtNoyTHcf5/2JOWtk=;
fh=F2b6pltMnesic29W0SL7vphbqOFUYP8YqURPRv9rp5E=;
b=BvrWz3q72DkWP40ok1UgJcjzEb0up2wutomKPcfre4olxg/a/PCeUy0Dss0M/ruTnF
1/c0tfxKDFak3ebF72DlsHsJjlpjVkLusKLaw+uQlKBTcmGHyyLW2jaaKOr/lTKCPeix
JNT+hgC9DyvFJayyi1SjVaVzGIFczln0CMxBOQ/weYeerPJli5fqQonae1LYpxAKnKjB
pSz9TkB8GNM3eGf+YVqn/SgNaF6YR8GbTRWpj+BEa2dL8tUdr/MIcVimjyS3huc+kDTh
lv8J/cfxHPZN1fLozWSPTHNxwWdFAx5EFfOcwa3rEmvAbtEs6jongQalmpX3hEotToYw
asmQ==;
darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
dkim=pass header.i=@rustcorp.com.au header.s=202305 header.b=edpbFe4S;
spf=pass (google.com: domain of rusty@gandalf.ozlabs.org designates 150.107.74.76 as permitted sender) smtp.mailfrom=rusty@gandalf.ozlabs.org
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlegroups.com; s=20230601; t=1758979368; x=1759584168; darn=gnusha.org;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:content-transfer-encoding
:x-original-authentication-results:x-original-sender:mime-version
:message-id:date:in-reply-to:subject:to:from:sender:from:to:cc
:subject:date:message-id:reply-to;
bh=PVHG8HwIATqiLddMwMSB7YH2ciLtNoyTHcf5/2JOWtk=;
b=gGpEH62RSiFAcp7sxERGXm8rPgGYDSAerRjuvUdeXE7KtMym6tjbq9CBLcRYFPKefm
Fjitiefy/ieuX2dqaPuvAkAsSIOLUAN1AmmrDCQtnehpYbJl6DD1IzTl7Mm7YfSMUv9A
5vaF5A17cFYN08OWcM4fh8Fp06iljGMK56W+c97zUwyTpspZvTb2ggHNtsDN+VSj3epn
pHovsIFrV/XjeNGnVdzJpAiuZcjTEHG/Vc9DBLQsNz+lkb6r6Ph8j53lqrJo2Ojd1ov5
Zz95A74W9bm+9UocIFzRwLmssqsF5G6dWom2NPLppvTKltgrTQjovImQmmt9WvGhrmqm
d/cw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1758979368; x=1759584168;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:content-transfer-encoding
:x-original-authentication-results:x-original-sender:mime-version
:message-id:date:in-reply-to:subject:to:from:x-beenthere
:x-gm-message-state:sender:from:to:cc:subject:date:message-id
:reply-to;
bh=PVHG8HwIATqiLddMwMSB7YH2ciLtNoyTHcf5/2JOWtk=;
b=uKOFFOkk7rVpD8D3SRX3AOyT6r1rbRnMmnhdn237ilAsk+t5XZtU2IsLapZSKl4gor
irklrWTixuyFd9REbzy6tb7HlLshcEWqX6RNq8wPQw4I+HOtmLT+reoPW7I0Jpf29XLq
cJ+Yi9yz62Lul2pde2e07njfmFerkzGGuz7eDyP3eVA4JMLDpjqkveDhGqE6cEwH5l16
YTZQlXgHmzrY68xKfv4bh2EZCEDqoGj3fAXpm0jtjT3ZNDapuaIqsRa93m9Pch99NcZj
4IiYf3yCNiVTAsdOKLLWPyVjM61OkEyLDf5UxMKY935ej3nh/5oGlShIaBVwN+45kIDN
iTJQ==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCUcXwF3yvD+WBvy1wwgGylWjXEPXJMSeXuG9kaekECVRdmXd+dlfujhhZSDN5cCulzbdtlwANiJWBiw@gnusha.org
X-Gm-Message-State: AOJu0Yxhd9UJUNTvXeWzYprlBjmf/WyNE4lEKJw1Zn89BF5gAqgsvZVa
4s8NC4jGiFNvb75GTUJlWEKDIMJh/Q20srXYEHyoti2UtUNzYjhM1Yuu
X-Google-Smtp-Source: AGHT+IF5ZTMiCdt8qdDgwvt+pnUiIsS/TYf6mFsj5DYEt30/0bbJYvqvc3ePhZlyFvVIs++7/SZb6w==
X-Received: by 2002:a05:6870:5593:b0:332:fc:dadc with SMTP id 586e51a60fabf-35ee837d59cmr6407777fac.27.1758979368285;
Sat, 27 Sep 2025 06:22:48 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h="ARHlJd4G8k5qVbAw+9NZz7H8Wjn17Q/BmAejH4du9bY1LjW3Bg=="
Received: by 2002:a05:6870:5486:b0:31d:8e96:6f5e with SMTP id
586e51a60fabf-35eecc43003ls2934937fac.2.-pod-prod-08-us; Sat, 27 Sep 2025
06:22:44 -0700 (PDT)
X-Received: by 2002:a05:6808:191e:b0:43d:3898:ad73 with SMTP id 5614622812f47-43f4cc1f8camr2742337b6e.5.1758979364166;
Sat, 27 Sep 2025 06:22:44 -0700 (PDT)
Received: by 2002:a05:6808:1a15:b0:43f:5b9f:a4a0 with SMTP id 5614622812f47-43f5e0fa8c5msb6e;
Sat, 27 Sep 2025 04:27:55 -0700 (PDT)
X-Received: by 2002:a92:870d:0:b0:40e:a0e1:2f61 with SMTP id e9e14a558f8ab-4259566856cmr117962505ab.26.1758972474621;
Sat, 27 Sep 2025 04:27:54 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1758972474; cv=none;
d=google.com; s=arc-20240605;
b=kuEdTrnPnjw3bHUexSf5CGPKchapRxQAEtqGt1BPFkL+VHDj0ms8NlCLCTSBu3mgC1
Sk9qQTeF5cVB20DyYhpHFjOFB8kgl5Hjv6aC7UcJjjLSmkdR+L6dDzNqFIEgnMSHQEPo
xn/MJcBLnKtJuH8on/fMzxF2bt6w+TNdMByYCmFtxLITuhVjBBCXnQMgkZIkyEMXdQvr
hdrMtTmdcowSbDRDarQcvPQHj66RijCSvMLa0+iK2sNcmhIn23a6V+RUXz7Gy/E0h2OE
kRkjzLTie9YQaupqK1v8ixSM+tBgPAdn/cGgRlQN1GezczQ5ZxeSqZlIwLLN/9KE/ZSp
o9wg==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
h=mime-version:message-id:date:in-reply-to:subject:to:from
:dkim-signature;
bh=x+FcHSftjnKDkAKuxi1Cw9KyFmiRwYyT0qcHJF4qg1o=;
fh=VcGcg+Zjs9gw1uDcHbxsAILhBAcecnbJzZRdxgKVDIc=;
b=acKw2tshAT7D5LD20+K/vVvmQlpN/emnItYj/h2n3YgquzBFj2L30te2QH1pyfip8t
0tAe2sf6nUb63qjuSAVw61tM/j8/L9kPgKmLnIsWAUum+Qxw7t8vXwhUOGxfMwWX2rao
kprIxz3ZN9rUD5hhCMh+GztlM8FZnzljmG9VwgjoC9T1mZ/XMkZfEAOu1575loedtUzk
bKPwHoFKiHp9uzP6r6bfJBk5i3Fz8dgpv6Tp501HoqpmCGx01P6YYDEeMTKeTuUv/Lcm
0smIgtGdh0qU8ffxueLFDX7PPtap3fzBfhOfAVzgZg//ND1yoQ+sJ9cgb3SofKrbKhel
OtdA==;
dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
dkim=pass header.i=@rustcorp.com.au header.s=202305 header.b=edpbFe4S;
spf=pass (google.com: domain of rusty@gandalf.ozlabs.org designates 150.107.74.76 as permitted sender) smtp.mailfrom=rusty@gandalf.ozlabs.org
Received: from mail.ozlabs.org (gandalf.ozlabs.org. [150.107.74.76])
by gmr-mx.google.com with ESMTPS id 8926c6da1cb9f-56a64bb6e18si220859173.1.2025.09.27.04.27.53
for <bitcoindev@googlegroups.com>
(version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);
Sat, 27 Sep 2025 04:27:53 -0700 (PDT)
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;
Received: by gandalf.ozlabs.org (Postfix, from userid 1011)
id 4cYlYc2yGDz4wCT; Sat, 27 Sep 2025 21:27:48 +1000 (AEST)
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"
X-Original-Sender: bitcoin-dev@rustcorp.com.au
X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass
header.i=@rustcorp.com.au header.s=202305 header.b=edpbFe4S; spf=pass
(google.com: domain of rusty@gandalf.ozlabs.org designates 150.107.74.76 as
permitted sender) smtp.mailfrom=rusty@gandalf.ozlabs.org
Content-Transfer-Encoding: quoted-printable
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
<https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: -0.8 (/)
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.
|