summaryrefslogtreecommitdiff
path: root/bb/9a276fc2c14b0eddc7b70907f3c629a0dacbc8
blob: 6cc8529fd16e21c35b66f5fe9634e126d8ddd27d (plain)
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
Return-Path: <jl2012@xbt.hk>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 86C503EE
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri, 30 Sep 2016 10:57:59 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from sender163-mail.zoho.com (sender163-mail.zoho.com
	[74.201.84.163])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id B8B07148
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri, 30 Sep 2016 10:57:56 +0000 (UTC)
Received: from mail.zoho.com by mx.zohomail.com
	with SMTP id 1475233073842978.9735637479434;
	Fri, 30 Sep 2016 03:57:53 -0700 (PDT)
Date: Fri, 30 Sep 2016 18:57:53 +0800
From: Johnson Lau <jl2012@xbt.hk>
To: "bitcoin-dev" <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <1577abe4a84.e9b9c8da3882.6224549273767153798@xbt.hk>
In-Reply-To: 
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Priority: Medium
User-Agent: Zoho Mail
X-Mailer: Zoho Mail
X-Spam-Status: No, score=-0.4 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_NONE, 
	RCVD_IN_SORBS_SPAM, UC_GIBBERISH_OBFU autolearn=no version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
Subject: [bitcoin-dev] New BIP: Limiting excessive SignatureHash operation
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Fri, 30 Sep 2016 10:57:59 -0000

 A new BIP is proposed to prevent excessive O(n^2) SignatureHash operation.

https://github.com/jl2012/bips/blob/sighash/bip-sighash.mediawiki
https://github.com/bitcoin/bitcoin/pull/8755 (Tight estimation)
https://github.com/bitcoin/bitcoin/pull/8756 (Loose estimation)

Two methods of sighash size estimation are proposed, with different tradeof=
f. The tight estimation is more permissive (disabling less txs) but require=
 disabling of OP_CODESEPARATOR, FindAndDelete, and unusual nHashType. The l=
oose estimation is less permissive (may disable more big and strange txs) b=
ut does not depend on further policy/consensus rules. With either type of e=
stimation, normal standard txs (<100kB, P2PK, P2PKH, canonical bare or P2SH=
 multisig) are totally unaffected by this BIP.

  BIP: ?
  Title: Limiting excessive SignatureHash operation
  Author: Johnson Lau <jl2012@xbt.hk>
  Status: Draft
  Type: Standards Track
  Created: 2016-09-21


Abstract

This proposal defines a new type of block-level resources limit, with sever=
al (optional) script restrictions, to prevent excessive SignatureHash opera=
tion.

Introduction

There are 4 ECDSA signature verification codes in the Bitcoin script system=
: CHECKSIG, CHECKSIGVERIFY, CHECKMULTISIG, CHECKMULTISIGVERIFY (=E2=80=9Csi=
gops=E2=80=9D). According to the SIGHASH type, a transaction digest (sighas=
h) is generated with a double SHA256 of a serialized subset of the transact=
ion, with a function called SignatureHash, and the signature is verified ag=
ainst this sighash with a given public key. Due to a design weakness, the a=
mount of data hashing in SignatureHash is proportional to the size of the t=
ransaction. Therefore, data hashing grows in O(n2) as the number of sigops =
in a transaction increases. While a 1 MB block would normally take 2 second=
s to verify with an average computer in 2015, a 1 MB transaction with 5569 =
sigops may take 25 seconds to verify. [1][2][3]

BIP143 fixes this problem by introducing a new SignatureHash algorithm in s=
egregated witness transactions. However, it would not be able and is not in=
tended to fix the problem of pre-segregated witness transactions. This docu=
ment proposes a new type of block-level resources limit to prevent excessiv=
e SignatureHash operation. However, the calculation of sighash is a complic=
ated process involving several consensus-critical procedures, including the=
 use of OP_CODESEPARATOR, the FindAndDelete function, and the interpretatio=
n of nHashType. A correct limitation should be made based on the effects of=
 these procedures.

Specification

Transaction hashable size

Transaction hashable size (TxHashableSize) is defined as the size of a tran=
saction, which:

is serialized without witness data (BIP144), and
has scriptSig in all inputs replaced by zero-size script
TxHashableSize is an estimation of the amount of data hashed with a SIGHASH=
_ALL. Without counting the size of scriptCode and nHashType, it always unde=
restimates the size. However, the difference is negligible since it grows l=
inearly with the number of sigops.
int64_t GetTransactionHashableSize(const CTransaction& tx)
{
    int64_t size =3D ::GetSerializeSize(tx, SER_NETWORK, PROTOCOL_VERSION |=
 SERIALIZE_TRANSACTION_NO_WITNESS);
    for (unsigned int i =3D 0; i < tx.vin.size(); i++) {
        int64_t scriptSigSize =3D tx.vin[i].scriptSig.size();
        size -=3D scriptSigSize;
        // If the scriptSig size is larger than 252, 2 bytes compactSize en=
coding is deducted.
        if (scriptSigSize > 252)
            size -=3D 2;
        /*
         * Theoretically, 4 bytes should be deducted if the scriptSig is la=
rger than 65535 bytes,
         * and 8 bytes should be deducted if it is larger than 4294967295 b=
ytes.
         * However, scriptSig larger than 10000 bytes is invalid so it is n=
ot needed.
         */
    }
    return size;
}
SignatureHash equivalent operation

SignatureHash equivalent operation (SigHashOp) is defined as the maximum po=
ssible number of times which a sigop would perform SignatureHash at the TxH=
ashableSize. Depends on whether some extra restrictions in script use are e=
nforced, there are 2 ways to estimate the SigHashOp:

Loose estimation: A loose SigHashOp estimation does not depend on any extra=
 script restrictions. It assumes that SignatureHash is performed not more t=
han once for every ECDSA signature passing to a sigop. It looks for all sig=
ops in a transaction (even in an unexecuted conditional branch), in scriptS=
ig, in scriptPubKey of the outputs being spent, and in redeemScript of P2SH=
 transactions. Each OP_CHECKSIG or CHECKSIGVERIFY is counted as 1 SigHashOp=
. Each OP_CHECKMULTISIG or CHECKMULTISIGVERIFY is counted as 20 SigHashOp, =
unless all the following conditions are satisfied:

The OP_CHECKMULTISIG or CHECKMULTISIGVERIFY is immediately preceded by a va=
lue push as OP_n (1 =E2=89=A4 n =E2=89=A4 16), denoting the number of publi=
c keys (n).
The n opcodes preceding the OP_n must be push type (i.e. 0x00 =E2=89=A4 opc=
ode =E2=89=A4 0x60), as the public key(s)
The opcodes preceding the public key(s) is a OP_m, with 1 =E2=89=A4 m =E2=
=89=A4 16 and m =E2=89=A4 n, denoting the number of signatures (m)
If all these conditions are met, the OP_CHECKMULTISIG or CHECKMULTISIGVERIF=
Y is counted as m SigHashOp.
SigHashOp of a transaction is the sum of SigHashOp of each of its inputs.

unsigned int CScript::GetSigHashOpCount() const
{
    unsigned int n =3D 0;
    const_iterator pc =3D begin();
    std::vector<opcodetype> pushOpcodes;
    while (pc < end())
    {
        opcodetype opcode;
        if (!GetOp(pc, opcode))
            break; // The script is invalid
        if (opcode =3D=3D OP_CHECKSIG || opcode =3D=3D OP_CHECKSIGVERIFY)
            n++;
        else if (opcode =3D=3D OP_CHECKMULTISIG || opcode =3D=3D OP_CHECKMU=
LTISIGVERIFY) {
            unsigned int nKey =3D 0;
            unsigned int nSig =3D 0;
            // We assume a CHECKMULTISIG will hash the transaction for 20 t=
imes, unless it is in some canonical form.
            n +=3D 20;
            // The number of keys must be k =3D 1 to 16 denoted by OP_k
            if (pushOpcodes.size() >=3D 3 && pushOpcodes.back() >=3D OP_1 &=
& pushOpcodes.back() <=3D OP_16) {
                nKey =3D DecodeOP_N(pushOpcodes.back());
                // All the k + 2 opcodes before the CHECKMULTISIG must be p=
ush only
                if (pushOpcodes.size() >=3D nKey + 2) {
                    opcodetype nSigCode =3D pushOpcodes.at(pushOpcodes.size=
() - nKey - 2);
                    // The number of signatures must be k =3D 1 to 16 denot=
ed by OP_k, and not larger than number of keys
                    if (nSigCode >=3D OP_1 && nSigCode <=3D OP_16) {
                        nSig =3D DecodeOP_N(nSigCode);
                        if (nSig <=3D nKey)
                            // We use the number of signatures as the SigOp=
Count of this CHECKMULTISIG
                            n =3D n - 20 + nSig;
                    }
                }
            }
        }

        if (opcode <=3D OP_16)
            pushOpcodes.push_back(opcode);
        else
            pushOpcodes.clear();
    }
    return n;
}
Tight estimation: An tight SigHashOp estimation depends on these extra cons=
ensus rules for pre-segregated witness scripts:

nHashType is confined to only 6 types: 0x01 for SIGHASH_ALL, 0x02 for SIGHA=
SH_NONE, 0x03 for SIGHASH_SINGLE, 0x81 for SIGHASH_ALL|SIGHASH_ANYONECANPAY=
, 0x82 for SIGHASH_NONE|SIGHASH_ANYONECANPAY, and 0x83 for SIGHASH_SINGLE|S=
IGHASH_ANYONECANPAY. A signature with other nHashType is invalid.
Script with OP_CODESEPARATOR, even in an unexecuted conditional branch, is =
invalid.
Script that involves non-zero FindAndDelete results is invalid.
It also assumes that SignatureHash is performed not more than once in each =
script for each nHashType.
SigHashOp is counted in the same way as the loose estimation. However, if t=
he SigHashOp for a script is found to be larger than 3, it is counted as on=
ly 3 SigHashOp.[4] The SigHashOp of a transaction is the sum of SigHashOp o=
f each of its inputs.

SigHashOp of the generating transaction is defined to be 0.

SignatureHash size

SignatureHash size (SigHashSize) of a transaction is the product of TxHasha=
bleSize and SigHashOp.

SigHashSize of a block is the sum of SigHashSize of all transactions in the=
 block.

Consensus and policy limits for SigHashSize

A new consensus rule is enforced to require that SigHashSize of a block MUS=
T NOT be larger than 500,000,000 (500MB). Consequently, SigHashSize of a va=
lid transaction MUST NOT be larger than 500MB.

A new relay and mempool policy is recommended to reject any unconfirmed tra=
nsaction that has a SigHashSize to Transaction weight ratio larger than 90.=
 This policy limit is equivalent to 36MB SigHashSize for a 100kB non-segreg=
ated witness transaction, or 360MB for a full block of such transactions.

Rationale

Static analysis

This proposal employs a static analysis approach to estimate SigHashSize of=
 transactions and blocks. This allows early rejection of violating transact=
ions and blocks without executing the scripts at all. Despite that the size=
 of scriptCode and nHashType are not considered in the estimation, the diff=
erence is negligible comparing with size of the main transaction body, sinc=
e the overheads grows linearly with the number of sigops, which is mostly r=
estricted by the 80,000 sigop limit (BIP141). [5]

Loose SigHashOp estimation

The loose SigHashOp estimation assumes that SignatureHash is performed not =
more than once for every ECDSA signature passing to a sigop. This assumptio=
n is obviously correct for OP_CHECKSIG and CHECKSIGVERIFY since they would =
never perform SignatureHash more than once, while no SignatureHash would be=
 performed if they happen in an unexecuted conditional branch, or if the si=
gnature is an empty vector. This assumption is also correct for OP_CHECKMUL=
TISIG and CHECKMULTISIGVERIFY with appropriate code refactoring. While a si=
gnature may be verified against multiple public keys, the sighash for this =
signature must remain unchanged across the whole operation and therefore co=
uld be reused. Therefore, SigHashOp of a OP_CHECKMULTISIG and CHECKMULTISIG=
VERIFY is equal to the number of signatures.

Tight SigHashOp estimation with extra script restrictions

The tight SigHashOp estimation is based on more assumptions. It assumes tha=
t the scriptCode serialized within SignatureHash is a constant value for al=
l sigops in an transaction input. For this assumption to be true, we must d=
isable any process that may modify the scriptCode, which are OP_CODESEPARAT=
OR and FindAndDelete. Transactions involving OP_CODESEPARATOR and FindAndDe=
lete are extremely rare in the main network, and arguably all of those were=
 performed for testing purpose. Removal of these operations would have next=
 to no functional loss, significantly simply the consensus-critical logic, =
and reduce the risks of unintentional consensus forks. [6]

The tight SigHashOp estimation also assumes that only 6 nHashType are allow=
ed. This is a relay policy in reference implementation since v0.?, and tran=
sactions with violating signatures are extremely rare in the main network. =
However, at consensus level, SigHashOp could be any value from 0 to 255, an=
d a SIGHASH type could be encoded in multiple ways. For example, there are =
116 ways to denote SIGHASH_ALL. Since nHashType is serialized inside Signat=
ureHash, the sighash produced by different nHashType are not the same, even=
 if all of them were SIGHASH_ALL.

With all these extra consensus rules implemented, we could be assured that =
SignatureHash is performed not more than once in each script for each nHash=
Type, due to the invariability of scriptCode. The 6 nHashType limitation fu=
rther guarantees that each script, with whatever number of sigops, would ne=
ver perform SignatureHash for more than approximately 3 times of TxHashable=
Size (excluding some linearly growing overhead), as shown below:

TxHashableSize could be divided into 3 parts: size of inputs, size of outpu=
ts, and size of overhead including nVersion, nLockTime, and maybe some Comp=
actSize encoding. The size of overhead grows linearly with the number of si=
gops, and is negligible.
SIGHASH_ALL would hash all inputs and outputs of the transaction.
SIGHASH_NONE would hash all inputs of the transaction, but no output is has=
hed.
SIGHASH_SINGLE would hash all inputs of the transaction. It also hashes the=
 scriptPubKey of output with matching index, and all outputs with lower ind=
exes with empty scriptPubKey. With the famous Gauss summation formula, it c=
ould be shown that if a transaction has the same number of inputs and outpu=
ts, and all inputs use a SIGHASH_SINGLE, the worst case would be hashing ap=
proximately 50% of all outputs of the transaction.
nHashType with SIGHASH_ANYONECANPAY would hash only one input, which scales=
 linearly and is negligible. Therefore,
SIGHASH_ALL|SIGHASH_ANYONECANPAY would hash all outputs.
SIGHASH_NONE|SIGHASH_ANYONECANPAY is negligible.
SIGHASH_SINGLE|SIGHASH_ANYONECANPAY would hash approximately 50% of all out=
puts in the worst case.
By adding up the effects of 6 nHashType, it could be shown that the total a=
mount of data hashed would be equal to 3 times of input size and 3 times of=
 output size. Therefore, in the worst case, a script may perform SignatureH=
ash for up to approximately 3 times of TxHashableSize.
SigHashSize policy limit

A policy limit for SigHashSize to Transaction weight ratio is recommended a=
s 90, which is equivalent to 36MB SigHashSize for a 100kB non-segregated wi=
tness transaction. This limit is chosen based on the concept of normal tran=
saction.

A transaction is normal if each SigHashOp consumes at least 70 bytes of spa=
ce in scriptSig on average. According to BIP66, the maximum size of an ECDS=
A signature is 73 bytes, which should consume 74 bytes of scriptSig space i=
ncluding the push opcode. Using the low S value, the maximum signature size=
 becomes 72 bytes. It could be shown that with 99.6% of chance, a randomly =
generated low S signature would be at least 69 bytes (consuming 70 bytes of=
 space in scriptSig).

In actual use, the scriptSig size associated to a SigHashOp is often much m=
ore than 70 bytes. For example, pay-to-public-key-hash transactions and OP_=
CHECKMULTISIG inside P2SH would consume extra scriptSig space with their pu=
blic keys. In such cases, more than 100 bytes of scriptSig would be consume=
d by a SigHashOp.

If a transaction is performing many SigHashOp with disproportionately small=
 scriptSig, very likely it employed some strange scripts, such as using OP_=
DUP to copy a signature.

The size of scriptSig is important in determining the SigHashSize limit, si=
nce it is deducted from the transaction size for the TxHashableSize. Compar=
ing 2 transactions of the same size, the one with more SigHashOp may have s=
maller SigHashSize due to the smaller TxHashableSize. With the 100kB standa=
rd transaction size limit, it could be shown that the maximum SigHashSize h=
appens when there are 714 SigHashOp, consuming at least 714 * 70 =3D 49.98k=
B of scriptSig. With the resulting TxHashableSize =3D 100 - 49.98 =3D 50.02=
kB, the SigHashSize is 50.02kB * 714 =3D 35.7MB, which is just below the re=
commended policy limit.

Despite the limit is determined based on normal transactions, abnormal tran=
sactions may still be accepted as long as they are not too big. For example=
, if the transaction size is 10kB, a transaction may remain standard with t=
he recommended policy limit even if each SigHashOp is associated with only =
7 bytes of scriptSig.

SigHashSize consensus limit

The consensus limit of 500MB SigHashSize per block is based on the policy l=
imit of SigHashSize to Transaction weight ratio. It is set above the policy=
 limit, to make sure that a miner enforcing the policy limit would never pr=
oduce a block violating the consensus rules. The 500MB limit is compromise =
between avoiding loss of functionality (as it may disable some very big tra=
nsactions) and the harm of intentional or unintentional sighash attack init=
iated by a miner.

Deployment

This is a softfork to be deployed with BIP9.

Backward compatibility

Impact of the recommended policy limit

No matter the loose or the tight SigHashOp estimation is employed, this sof=
tfork with recommended policy limit should be completely transparent to use=
rs of normal standard transactions, including pay-to-public-key, pay-to-pub=
lic-key-hash, and P2SH m-of-n OP_CHECKMULTISIG with 1 =E2=89=A4 m =E2=89=A4=
 n =E2=89=A4 15. A complete scan up to block 430368 showed that the transac=
tion 7b587808a7f6b135ef91011be9b42fcbb0892da50963822e47a5827ced8653ce was t=
he normal standard transaction with highest SigHashSize to weight ratio. Wi=
th a ratio of 80.1, it is still well below the policy limit of 90. Should t=
his policy had been deployed since genesis block, all normal standard trans=
actions should still have been accepted.

If the loose estimation had been employed, a few abnormal standard transact=
ions would have been rejected by policy, but were still valid by consensus.=
 This is a full list of the affected transactions:

    bea1c2b87fee95a203c5b5d9f3e5d0f472385c34cb5af02d0560aab973169683
    24b16a13c972522241b65fbb83d09d4bc02ceb33487f41d1f2f620b047307179
    53666009e036171b1aee099bc9cd3cb551969a53315410d13ad5390b8b4f3bd0
    ffc178be118bc2f9eaf016d1c942aec18441a6c5ec17c9d92d1da7962f0479f6
    2f1654561297114e434c4aea5ca715e4e3f10be0be8c1c9db2b6f68ea76dae09
    62fc8d091a7c597783981f00b889d72d24ad5e3e224dbe1c2a317aabef89217e
    d939315b180d3d73b5e316eb57a18f8137a3f5943aef21a811660d25f1080a3f
    8a6bfaa78828a81147e4848372d491aa4e9048631982a670ad3a61402a4ec327
    02cc78789cc070125817189ec378daa750355c8b22bbce982ed96aa549facb1f
    b97a16ae2e8ae2a804ed7965373b42055f811653f4628e4bef999145d4b593bc
    c51ffaf08188859669571f897f119b6d39ea48a9334212f554bf4927401b71f3
    324456fe9ec97a380effba0a0205a226e380790b93e7366d39f2a416a44d2a34
These transactions all used a large number of sigops, and obviously were ma=
de for testing purpose. However, they would have gone through if the tight =
estimation had been used.

Impact of the block-level consensus limit

With the block-level consensus limit of 500MB SigHashSize, transactions wit=
h SigHashSize above 500MB would also become invalid. Up to block 430368, 49=
 transactions would have become invalid with this limit (with either loose =
or tight estimation):

    Transaction ID                                                       Si=
gHashSize
    9c667c64fcbb484b44dcce638f69130bbf1a4dd0fbb4423f58ceff92af4219ec=09 2,2=
15,084,200
    9fdbcf0ef9d8d00f66e47917f67cc5d78aec1ac786e2abb8d2facb4e4790aad6=09 2,2=
15,076,850
    5d8875ed1707cfee2221741b3144e575aec4e0d6412eeffe1e0fa07335f61311=09 1,2=
71,892,772
    cb550c9a1c63498f7ecb7bafc6f915318f16bb54069ff6257b4e069b97b367c8=09 1,2=
71,892,772
    14dd70e399f1d88efdb1c1ed799da731e3250d318bfdadc18073092aa7fd02c2=09 1,2=
71,892,772
    a684223716324923178a55737db81383c28f055b844d8196c988c70ee7075a9a=09 1,2=
71,892,772
    bb41a757f405890fb0f5856228e23b715702d714d59bf2b1feb70d8b2b4e3e08=09 1,2=
71,820,375
    5b0a05f12f33d2dc1507e5c18ceea6bb368afc51f00890965efcc3cb4025997d=09 1,0=
91,954,040
    bb75a8d10cfbe88bb6aba7b28be497ea83f41767f4ee26217e311c615ea0132f=09 1,0=
25,295,000
    5e640a7861695fa660343abde52cfe10b5a97dd8fc6ad3c5e4b2b4bb1c8c3dd9=09 1,0=
25,295,000
    dd49dc50b54b4bc1232e4b68cfdd3d349e49d3d7fe817d1041fff6dd583a6eaf=09 1,0=
25,230,000
    3d724f03e8bcc9e2e3ea79ebe4c6cffca86d85e510742cd6d3ac29d420787a34=09 1,0=
25,210,000
    8bcf8e8d8265922956bda9b651d2a0e993072c9dca306f3a132dcdb95c7cee6e=09 1,0=
25,210,000
    54bf51be42ff45cdf8217b07bb233466e18d23fd66483b12449cd9b99c3a0545       =
995,042,075
    6bb39576292c69016d0e0c1fe7871640aab12dd95874d67c46cf3424822f8dfd=09   9=
88,589,147
    d38417fcc27d3422fe05f76f6e658202d7fa394d0c9f5b419fef97610c3c49f1=09   9=
23,884,836
    66b614e736c884c1a064f7b0d6a9b0abd97e7bb73ac7e4b1b92b493d558a0711=09   9=
02,501,490
    d985c42bcd704aac88b9152aede1cca9bbb6baee55c8577f84c42d600cfec8e4=09   8=
98,372,800
    e32477636e47e1da5fb49090a3a87a3b8ff637d069a70cd5b41595da225e65b4=09   8=
93,548,487
    bf40393fedc45a1b347957124ef9bb8ae6a44feecee10ef2cc78064fabf8125f=09   8=
91,859,369
    1d93bfe18bc05b13169837b6bc868a92da3c87938531d6f3b58eee4b8822ecbf=09   8=
88,420,676
    79e30d460594694231f163dd79a69808904819e2f39bf3e31b7ddc4baa030a04=09   8=
77,542,875
    4eba5deb2bbf3abf067f524484763287911e8d68fb54fa09e1287cf6cd6d1276=09   8=
74,353,609
    c3f2c2df5388b79949c01d66e83d8bc3b9ccd4f85dbd91465a16fb8e21bf8e1b=09   8=
69,060,209
    446c0a1d563c93285e93f085192340a82c9aef7a543d41a86b65e215794845ef=09   8=
33,655,283
    e0c5e2dc3a39e733cf1bdb1a55bbcb3c2469f283becf2f99a0de771ec48f6278=09   8=
02,433,929
    2e7c454cfc348aa220f53b5ba21a55efa3d36353265f085e34053c4efa575fda=09   7=
89,067,716
    01d23d32bccc04b8ca5a934be16da08ae6a760ccaad2f62dc2f337eee7643517=09   7=
85,833,449
    9f8cc4496cff3216608c2f2177ab360bd2d4f58cae6490d5bc23312cf30e72e0=09   7=
75,457,104
    1e700d8ce85b17d713cad1a8cae932d26740e7c8ab09d2201ddfe9d1acb4706c=09   7=
57,230,231
    9db4e0838c55ef20c5eff271fc3bf09a404fff68f9cdad7df8eae732500b983d=09   7=
56,319,396
    763e13f873afa5f24cd33fc570a178c65e0a79c05c88c147335834fc9e8f837b=09   7=
34,988,489
    b8ba939da1babf863746175b59cbfb3b967354f04db41bd13cb11da58e43d2a8=09   7=
32,906,849
    f62f2c6a16b5da61eaae36d30d43bb8dd8932cd89b40d83623fa185b671c67f9=09   7=
23,659,859
    6e278c0ca05bf8e0317f991dae8a9efa141b5a310a4c18838b4e082e356ef649=09   7=
03,394,401
    e3de81a5817a3c825cf44fbf8185e15d446393615568966a6e3fc22cba609c7d=09   6=
97,632,336
    b5ca68205e6d55e87bd6163b28467da737227c6cbcc91cb9f6dc7b400163a12b=09   6=
65,208,049
    9c972a02db30f9ee91cc02b30733d70d4e2d759b5d3c73b240e5026a8a2640c4=09   6=
53,370,601
    02313ac62ca8f03930cdc5d2e437fabc05aea60a31ace18a39678c90b45d32bd=09   6=
22,323,625
    e245f6c3c6b02dc81ea1b6694735565cc535f603708783be027d0e6a94ac3bd5=09   6=
09,926,656
    1cf52f9ef89fa43bb4f042cbd4f80e9f090061e466cbe14c6b7ba525df0e572e=09   6=
07,214,327
    461308024d89ea4231911df4ef24e65e60af2a9204c8282a6b67f4214c1714e7=09   6=
06,137,296
    fa5a58f787f569f5b8fab9dadb2447161fac45b36fb6c2c0f548ed0209b60663=09   5=
89,853,184
    905df97982a2904d6d1b3dfc272435a24d705f4c7e1fc4052798b9904ad5e597=09   5=
46,737,250
    d85ce71f583095a76fb17b5bb2a1cbf369e2a2867ca38103aa310cbb2aaf2921=09   5=
46,737,250
    1b604a075075197c82d33555ea48ae27e3d2724bc4c3f31650eff79692971fb7=09   5=
31,511,200
    ba31c8833b7417fec9a84536f32fcb52d432acb66d99b9be6f3899686a269b2b=09   5=
31,511,200
    92f217ec13ab309240adc0798804b3418666344a5cbfff73fb7be8192dad5261=09   5=
09,443,536
    22e861ee83c3d23a4823a3786460119425d8183783068f7ec519646592fac8c2=09   5=
06,268,969
Extra consensus rules required by tight SigHashOp estimation

Transactions in the main network, up to block 430368, that would have been =
affected by the extra consensus rules are listed below:

Transactions with OP_CODESEPARATOR:

    eb3b82c0884e3efa6d8b0be55b4915eb20be124c9766245bcc7f34fdac32bccb
    055707ce7fea7b9776fdc70413f65ceec413d46344424ab01acd5138767db137
    6d36bc17e947ce00bb6f12f8e7a56a1585c5a36188ffa2b05e10b4743273a74b
    bc179baab547b7d7c1d5d8d6f8b0cc6318eaa4b0dd0a093ad6ac7f5a1cb6b3ba
    4d932e00d5e20e31211136651f1665309a11908e438bb4c30799154d26812491
    0157f2eec7bf856d66714856182a146998910dc6fa576bec200a9fa8039459e7
    ddd070541bf2fddaa5e08a9d93126f73211fe15291beb897c762908949420ad9
    d4a27d10404d87ee0b8a05fb700e55f9f83f80a59ebf87af2fbf87e5c9546177
    492cdb3c95c1fe0c597d8dc847adb5459d403ea083f4b5e706300d437c84748f
    b3e977a2c48145255d84e1c82d4ea07522528991d50ead1cf3a783559d9733e3
Transactions with non-zero FindAndDelete results:

    5df1375ffe61ac35ca178ebb0cab9ea26dedbd0e96005dfcee7e379fa513232f
    ded7ff51d89a4e1ec48162aee5a96447214d93dfb3837946af2301a28f65dbea
    307b173ef009b970c1a0dd67166a8ce3e91fc5551b8950d2d17f1fe0eaa07358
Transactions with abnormal nHashType:

    c99c49da4c38af669dea436d3e73780dfdb6c1ecf9958baa52960e8baee30e73
    0ad07700151caa994c0bc3087ad79821adf071978b34b8b3f0838582e45ef305
    7c451f68e15303ab3e28450405cfa70f2c2cc9fa29e92cb2d8ed6ca6edb13645
    a6c116351836d9cc223321ba4b38d68c8f0db53661f8c2229acabbc269c1b2c8
    f5efee46ccfa4191ccd9d9f645e2f5d09bbe195f95ef5608e992d6794cd653cd
    904bda3a7d3e3b8402793334a75fb1ce5a6ff5cf1c2d3bcbd7bd25872d0e8c1e
    8ac76995ce4ac10dd02aa819e7e6535854a2271e44f908570f71bc418ffe3f02
    e218970e8f810be99d60aa66262a1d382bc4b1a26a69af07ac47d622885db1a7
    ba4f9786bb34571bd147448ab3c303ae4228b9c22c89e58cc50e26ff7538bf80
    38df010716e13254fb5fc16065c1cf62ee2aeaed2fad79973f8a76ba91da36da
Reference Implementation

Policy only:

https://github.com/bitcoin/bitcoin/pull/8755 (Tight estimation)
https://github.com/bitcoin/bitcoin/pull/8756 (Loose estimation)
References

^ CVE-2013-2292
^ New Bitcoin vulnerability: A transaction that takes at least 3 minutes to=
 verify
^ The Megatransaction: Why Does It Take 25 Seconds?
^ It should be noted that since sigops may exist in both scriptSig (non-sta=
ndard and extremely rare) and scriptPubKey, in theory an input may have up =
to 6 SigHashOp
^ Not totally, since it does not count the sigops inside the scriptPubKey o=
f the outputs being spent, while inappropriately counting sigops in scriptP=
ubKey of the current transaction.
^ https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2014-November/006=
878.html
Copyright

This document is placed in the public domain.