Block and Transaction Validation Analysis

[Note, data for this document was originally collected using a “debug” build. This has been corrected to use the much more efficient “release” build]

Block (and therefore transaction) validation can consume a tremendous amount of time and processing power due to an oversight in the original code that can cause super-linear transaction validation times. This problem can be solved via a new transaction format, but in the mean time we should to do something — especially since larger blocks could mean even larger transactions and therefore exponentially (in the English sense, encompassing all equations with an exponent, not in the mathematical one specifically referring to e^x) larger validation times.

Bitcoin Unlimited will merge a technology we call “Parallel Validation” that allows short, quick-to-validate sibling blocks to supersede large, slowly-validating blocks. This competition-based approach will cause larger blocks to be orphaned, resulting in miners favoring smaller blocks. However, it still makes sense to provide some very granular “emergent consensus” style limits to very actively discourage extremely costly transactions and blocks.

The current software attempts to solve this problem by counting signature operation (sigops). Unfortunately, it counts the wrong set of sigops! Let’s take 2 transactions as an example, created using the bitcoin RPC’s “create raw transaction” API. The first has 1 input and 10000 outputs, second 10000 inputs and one output.

Transaction 1 reports the following statistics:

`Vin: 1, Vout: 10000length: 340126 bytescalculated sigops: 10000actual sigops: 1 sighash: 340092validation time: 24ms`

Transaction 2 reports something completely different:

`Vin 10000, Vout: 1length: 1474955 bytes calculated sigops: 1actual sigops: 10000sighash: 4100750000validation time: 47,483ms`

As you can see, the calculated sigops are the exact opposite of the actual signature operations, and the validation time is long for the transaction that has 1 “calculated” sigop, and short for the transaction that has 10000.

The problem is that to validate a transaction, the bitcoin client runs the input scripts and then runs the scripts of the prior transaction output (what we call the UTXO — unspent transaction output). This makes sense… the input is attempting to spend the prior output. And the signature instructions need to be in the prior output to ensure that the signature validation is actually executed (unless you are using a P2SH-style tx — the 3xxx addresses, but that is a detail).

And of course, the signature operations in this transaction’s outputs are not run during validation of this transaction. They are run when the next transaction spends these outputs.

So the sigop calculation code includes signature operations that are not relevant, and skips ones that are.

It should be noted that by limiting the number of output sigops, the system ultimately limits the number of inputs in subsequent transactions since the outputs of one transaction become the inputs of another. But since a transaction can contain 1000s of inputs, there is a high possible multiplier.

What does transaction validation really cost?

The following graph shows validation times for “normal” transactions with a different number of inputs and outputs. This data was collected on an Intel 6-core 4.0 Ghz achine. The vertical axis corresponds to milliseconds of validation time, the horizontal left axis corresponds to the number of outputs, and the horizontal right (depth) axis corresponds to the number of inputs:

While a 3.3 second maximum time is not an issue, the situation is very different for small embedded ARM computers, like the RaspberryPI. These are the results for a OrangePI+(basically a RasPi+ with a SATA disk).

A Super-Linear Relationship

To make the super-linear rise clear, the following is a graph of transactions with N inputs and 1 output (blue), and transactions with 1 input and N outputs (orange):

It is quite clear visually that the nonlinear behavior results from the inputs, not the outputs. But we can fit a curve to the data. Let us assume a quadratic model (i.e. ax² + by² + cxy + dx + ey + f):

This results in the following fit:

`X= # inputs, Y= # outputs: Model is: 0.000452*x^2 + -0.000008*y^2 + 0.217728*x +0.075476*y + 0.000289*x*y + 27.769676`

-0.000008 is essentially 0 for the breadth of data collection (1 to 2000 outputs). So numerically and visually, the data does look quadratic in the number of inputs and weakly linearly in the number of outputs.

In this casual report I will not do a formal error analysis because we will not directly use these constants, but graphically in 3d, you can see that the model (red) reasonably captures the trend in the actual data (green). In the 2d projections of the extreme 1 by N cases, it seems to be off only when the number of inputs are 1.

Interpretation

On a modern Intel i7 machine, the absolute time required to validate the worst case “normal” transaction (the collected data uses transactions constructed by bitcoin-cli, so does not include transactions with custom scripts that could be created to specifically increase sigops) is about 30 seconds. So it seems that limiting transactions to a maximum of 1MB is and acceptable solution, even if block size grows. However, these numbers will be much worse for small machines like the Raspberry PI and similar. To support these machines, additional limits would be useful.

It should be clear from the above graphs that the number of inputs is a much better predictor of the validation cost than the total sigops in the transaction. But this data only contains simple transactions with one sigop per input. We know that some inputs require multiple signatures. Ideally, we would count the number of sigops actually required. However, doing so requires access to all the previous transactions. The Satoshi client only keeps “handy” the “UTXO set” (unspent transaction outputs) of the currently active blockchain tip, so this data is available for new blocks extending the chain tip. It is not entirely clear to me why we should not do this since we need to access these previous transaction outputs to validate the block. However, it may have been thought ugly to do so — ideally constraints on the block can be verified without accessing external data.

Regardless, since the bitcoin scripting language does not allow loops, every signature must be in the input script. This means that the length of the input script is a proxy for the number of sigops. [Note, it would be possible for a script to use OP_DUP in the input to repeat the same signature in a space-efficient manner, but it is also possible for the validation code to optimize the case where the exact same signature is validated, by simply remembering prior signature checks]

And we know how transactions are validated. Every OP_CHECKSIG hashes the entire transaction (inputs and outputs) and checks the signature against the hash data.

So a reasonable estimate is:

`transaction effort = length of all inputs * total lengthblock effort = SUM(transaction effort)`

Of course the total length is the sum of the input and output lengths. So this equation can be rewritten as:

`transaction effort = len(inputs)^2 * len(outputs)`

So this estimate is similar to the model we extracted from the data. It captures the quadratic input behavior and the “xy” term. It ignores the linear effects but these are not that important to us anyway.

The final question is what should the default value in Bitcoin Unlimited be for the “excessive effort”. For reasons described in the next section, I propose a value of 150,000,000,000 per MB. The magnitude of this number doesn’t really have a meaning — but this will result in a validation time of approximately 10 seconds per MB on a modern processor. Embedded ARM processors may take several times longer, but this computation remains well within their capabilities, and as I show below, is much lower than the worst blocks on the blockchain today.

What does this mean for the Blockchain?

We can calculate this metric for all blocks currently on the Bitcoin blockchain and sort by largest “effort” (see the bottom of the doc).

All these blocks actually just contain 1 very hard-to-validate transaction. The sizes of these transactions range from 350KB to ~1MB, so not many can fit in a block. This means that a block with these 350KB transactions would take a high but reasonable 30 seconds per MB to validate. So if in the future we discourage just 100 out of 175,195,742 transactions (that’s .00005708% of them), we can solve this problem.

And these costly transactions seem to be “dust sweeping” transactions (I spot checked many, but not all, please contact me if you see something different). But, as far as I know, it is not a big issue to break a sweep transaction into several smaller transactions.

[Note: although this “effort” metric is a more accurate heuristic for predicting validation time than transaction length, in Bitcoin Unlimited we decided to use transaction length (limited to 1MB) since that is compatible with the implicit 1MB transaction limit currently in place given 1MB block sizes. This decision may cause painful validation times for rare miner-created transactions on underpowered ARM machines but will not have a large impact on modern multi-ghz Intel machines]

Appendix: The Highest “effort” Blocks

`block hash, # transactions, max tx length, max # vin, max # vout, block cost, max tx cost('000000000000000003dd2fdbb484d6d9c349d644d8bbb3cbfa5e67f639a465fe', 2, 999657, 5569, 1, 999268159512, 999268133427)('000000000000000000283e9409575c2426cd72fcb722065431c52b5083e5bb58', 2, 999651, 5569, 1, 999243168477, 999243142392)('00000000000000000d63417949af6653756d975f5e60cacff162303efcc41f3e', 2, 999622, 7350, 1, 999222177285, 999222151200)('00000000000000000671d60be5c9439be636a4e00f50c33141ded6a29f816cbc', 2, 999621, 7350, 1, 999221177685, 999221151600)('000000000000000003104258b4af9f6362b9e37cff80a25f521ee222a393330c', 2, 999634, 5569, 1, 999209181635, 999209155550)('0000000000000000058319fa2282779aada74b249369ecf9baa7ffaed3e11fb0', 2, 999611, 5569, 1, 999163200357, 999163174272)('0000000000000000030efd6441dc3520878727dc7c195aa3a268f33f41a344e4', 2, 999608, 5569, 1, 999157202877, 999157176792)('00000000000000000c17f800899d77056a61e0ec5a47402e61eba00ee621ba9f', 235, 926262, 5160, 6, 857932538512, 857906643186)('0000000000000000094b3d68fe7004b683c55aa40b6fb0e633d3f31105bf0831', 346, 897599, 5000, 20, 805660561281, 805631006460)('000000000000000008360c45209d17a47fc4ae9c580e519323c4c7b9b2a6ab58', 371, 897564, 5000, 9, 805603866660, 805568177820)('00000000000000000286409e3efb3e7c0653be26472f19089dbee4861f08e0ad', 119, 886617, 4925, 9, 786424716789, 785988630351)('0000000000000000113ba2a64fdfd175223ba3c3fccd02f3673a92d2303d4d3b', 165, 883773, 4909, 11, 780984714454, 780953965407)('0000000000000000117527da7d5c18cb03e3486b40409acef382be70a7480d69', 207, 854331, 4746, 12, 730140672352, 729813111081)('00000000000000000efc700678729b24309c9a5dfae8c6965c3a493b690f531c', 338, 842481, 4680, 74, 709740975337, 709706836881)('000000000000000003777900d8512b213aa30c1f830c867bc0b09d55796a6041', 489, 842079, 4691, 51, 709127971391, 709047359580)('00000000000000000528f81f5641d0c240176fbfe2a9bc5e92ce06124bfc5224', 279, 840022, 20000, 39, 705963364464, 705618480000)('0000000000000000008368a5c59bf755abd9d967370fe7c7a1c2929684e7e8a2', 273, 840022, 20000, 13, 705918102321, 705618480000)('000000000000000011c34837a74038b730edeaefd3a158d0ba0e1e1390f5c220', 281, 840219, 4667, 10, 705914181075, 705872182995)('0000000000000000053bceb058c6e8fae9efd0c17746e6c845f89ef1d97893f8', 260, 840022, 20000, 51, 705859962311, 705618480000)('00000000000000000bef938ebe4f04049206995fca611c78692606db3871b04c', 376, 840022, 20000, 21, 705810617110, 705618480000)('00000000000000000b8d631639b0dd7ea223f2efc46fc9ab0992f7d612e29c25', 368, 840022, 20000, 101, 705791298560, 705618480000)('00000000000000000e17bc7ba14fc16897a41cb1b2f0b89ddbad2cfe30184a61', 423, 840022, 20000, 16, 705790914100, 705618480000)('000000000000000005780446bbdddfff6e547ab83d39b237ec0f1440ff9af45f', 346, 840022, 20000, 16, 705743934757, 705618480000)('0000000000000000096aa43cd0d602b704bfa23f620141eea4006f179d40ce08', 477, 840022, 20000, 11, 705720326435, 705618480000)('000000000000000012ea0ca9579299ec120e3f57e7c309216884872592b29970', 420, 840022, 20000, 6, 705681723837, 705618480000)('000000000000000007c5ace173341f0bcdfe3a8edcecfb7c23d3336829a2bf80', 253, 839406, 4663, 74, 704772458086, 704535280356)('0000000000000000063e5b9d30e49596fe2219b0decfcf694f00653fc661fa38', 266, 837794, 4654, 21, 701945523339, 701831762916)('00000000000000000d86f6cc57eae1f167321c3650bb238944712dd4e2a1efb0', 188, 832508, 4625, 8, 693811660588, 692974664152)('00000000000000000ec68dc67c0bde9fab8502f95c2bc8894f42959ddffb179a', 278, 831095, 4617, 36, 690825131965, 690652411425)('00000000000000000d60936f7885c4407e0e18a4a9e02bfc97b417d06637f2e0', 394, 828552, 4603, 14, 686526538402, 686432132544)('000000000000000002d10761a51dd948b52af03cc758aa37f15dd14761968a86', 45, 811536, 4507, 5, 659541991519, 658442979744)('000000000000000009327d9cd32c82b78b23f877c82587cfb4d1142e6433cd57', 224, 796238, 4423, 21, 634073229246, 633931253604)('000000000000000009a07b761b0239baf86a3449e25f842a37bc604628e7e87a', 509, 789537, 4386, 13, 623377439128, 623305511409)('000000000000000002a8571bee11074e33021e594b8909d23f28aa2ec6a03d92', 527, 787898, 4377, 12, 620771768498, 620720226564)('00000000000000000d9fa4313b005a54db9242295b5c4ca193f6b676b6069295', 323, 782696, 4348, 151, 613085446559, 612550412736)('000000000000000008fc403e02c73b32a5b6139bd2e4debabdc8df9ba180232d', 299, 773527, 4297, 16, 598527747893, 598308437487)('00000000000000000872231d0d3d402e5dddd30711fdb19f242fd7c59a7f57c6', 430, 772964, 4294, 15, 597485956914, 597411508176)('00000000000000000596cff56060b95758fb6e77f5d0fbf87e5b83989e76be45', 370, 761938, 4233, 9, 582014941473, 580488560804)('00000000000000000ad13642532640c520abfede7f16d80922277471013abb09', 421, 761037, 4227, 12, 579504571396, 579116432409)('000000000000000008cb5666ad253b9308c0c11a581b354f25a76d0effe94f35', 208, 755955, 4199, 21, 571719356275, 571330378215)('0000000000000000063649fc8894f697fc58c7b7d87918c47f462ad8833e5db1', 198, 737559, 5000, 35, 567077766234, 543959350767)('000000000000000000747e3d8314a3e3d21ed2f44d94e256f50b49e741e1fac4', 73, 745449, 4141, 4, 557346698144, 555634575681)('000000000000000007eee2a2844312f5718db70dc3ec6263017ab3e2823c4384', 539, 742362, 4124, 50, 551332389904, 551041950084)('000000000000000015c89ab74c296908c9e5f269508ee410293983b12619085f', 235, 737510, 5000, 7, 546642860065, 543890024680)('00000000000000000c251056710cd5ae9855f8373b64675ada89d96e3292395d', 220, 737548, 5000, 18, 544198251563, 543946075288)('0000000000000000116e7371b8a7c35834d2b62a5806bd04c16bc3474a72cc26', 109, 724941, 4027, 15, 526338649627, 525481458201)('0000000000000000085412139c377478b8a7ff7d31caa35ac160251f411f8d8b', 628, 718410, 3991, 17, 516990431986, 516055455300)('0000000000000000013ec024ffc51a6d87c30362bf6c41b9290fb3db9e2ac508', 171, 701117, 3895, 58, 501481440693, 491508958329)('0000000000000000088ab3a8a791419bfc88b854571894d7dfd7b225e0980a63', 320, 692557, 3847, 151, 483406043326, 479556246751)('00000000000000000ede556711a82f88d1d8669da648a92de134d1f32463da53', 666, 694193, 3856, 19, 482008798325, 481848385809)('00000000000000000e5c87d568324ba252550a4cb02b7279cf398b9994c0c39f', 409, 691939, 3844, 12, 478795452118, 478724224601)('0000000000000000093d5e21b67b8febbf067a538fb6193a4fc0d6948346f24a', 800, 682650, 3792, 167, 466126999742, 465956410500)('0000000000000000013bee13c13c8408e72e75b78800b6493a71fd56f5d975b8', 1032, 655425, 3651, 58, 432757522025, 429543260550)('000000000000000015a382acfc08bd42952fef355b66c9c9e6550353b6c167d0', 663, 655438, 3651, 22, 429664524420, 429560301002)('000000000000000004e568e462c0acf1843ca5dd15bc356a921729cd33b8ae71', 377, 632404, 3513, 54, 413502951557, 399884226896)('0000000000000000054790aa56d6ca30b033233a133d02d308878b719f711b41', 641, 612356, 3411, 18, 412788257766, 374943741732)('00000000000000000bfbefddfe17466b9cbe7dcfec7833f3be1fd5738e964944', 530, 634422, 3524, 2418, 403053803050, 402440520324)('000000000000000007a7648870dbaa5668a6f9307e99060cc7c0703945e098bd', 821, 613585, 3418, 102, 376639652381, 376458327315)('00000000000000000d62348cd0bde52e8cf8aa85df3b0b0d23594565667f58d9', 161, 596708, 3314, 15, 356255535628, 355992412552)('00000000000000000b3424dade9b0402fe56db61c6c7de15c440772c18e7ec0f', 177, 585148, 3250, 8, 342439831082, 342331475032)('000000000000000004bf023e5fe85087d01f1c345de703489b89a429d525c65a', 252, 418687, 2325, 8, 315137532937, 175236838293)('00000000000000000c94ca4441d4f2470188dcb8845820d818cbfaf9f0c838e9', 388, 559319, 3116, 154, 314660386656, 312812015087)('000000000000023d9a3ee2714f4365b2d312700ba113af23084104319133c6c0', 725, 465554, 2585, 24, 295090009096, 216639967252)('000000000000000002ac55f2ada57d8f6034bf079fc3c16cdd961531650045db', 283, 500012, 3390, 22, 294403660972, 249990999640)('0000000000000000120f31d6e21a8976066f1ea8e3652a144d99d3fe10ba461e', 377, 500028, 3390, 15, 293764638072, 250006999608)('000000000000000010889bb61503de0bbcd225c4b57ea0c709f5f6403962ca08', 439, 500048, 3390, 22, 293677436332, 250027000288)('0000000000000000077c1da70b544d3b401805ee4f0f8da8433212049194cb8b', 552, 499992, 3390, 15, 293644521158, 249971000400)('00000000000000000bdf286d03caf440c81c0a49503be628a6ab784b813ab745', 523, 531058, 3600, 101, 288542881258, 282000294928)('00000000000000000ca5400a9d607c7e6cdf95aded1681f043f0e7528ad13a5c', 582, 512204, 2853, 20, 287517152285, 262322717580)('00000000000000000de35723889e1c31ca66d527c4d72ccb726a9841c924c082', 1173, 535796, 2976, 74, 287366298960, 287034489936)('000000000000000006a53e8e9dc2be33f91bf04a3cea4c4cff8a47c1b6520dd8', 1094, 531061, 3600, 30, 286421196770, 282003481159)('00000000000000001474b9a66f8f8b6c890135ae2074ef767493d3f60d0c0044', 705, 500032, 3390, 175, 272044428303, 250010999680)('000000000000000011418703f3e6674e1a19cdfd9955f76ffd646bf2dedcfda3', 515, 486870, 2704, 21, 267978654435, 236986893720)('00000000000000000126b5419f9d31f64fe9e91640b5fc383af629828bbae0fd', 254, 505880, 2810, 74, 256576274071, 255874104000)('000000000000000001dcb26d9a6786955cfdfd94e368c5ca25ae672233823c7d', 1491, 500057, 3390, 41, 251089361416, 250036000855)('000000000000000008686f8ee926d297063471f15693530de1b59393dd5a95cf', 607, 500022, 3390, 3846, 250537960825, 250000999560)('000000000000000001e23249369c26abdd142b506c1796934f2e1780bd15a216', 1481, 500073, 3390, 77, 250227656361, 250052002263)('00000000000000000e700a9de911a57ae5c3ac4238530878ebf18f2cba7d2bb4', 586, 500073, 3390, 102, 250210561024, 250052002263)('000000000000000011bae3d44a6f198f4670bc2502b6cc725f28d9fe04dec5db', 439, 500063, 3390, 102, 250139971582, 250042001323)('000000000000000007b4bd703d1ca95a51b3d70f2b74ddf09942f95cc3a5128b', 474, 500018, 3390, 102, 250096537199, 249996999568)('00000000000000000afa83a2bef7bf2c7c4b055554dc64b31c5f71ddecd9d4e6', 461, 496472, 2758, 21, 246697639731, 246461609072)('000000000000000003d9e27c8aa6b846b1db19df2db50373c643542c62725363', 769, 491111, 2728, 151, 241290452375, 241150725441)('00000000000000000c840c9855a79d9e629d2b4357136df495966b960ec8ff25', 228, 483953, 2688, 11, 234545821649, 234171789969)('000000000000000008fa8784a8921bd64983f60c8daea41b74197ac1921edee9', 740, 471876, 2621, 179, 224194921204, 222613165512)('00000000000000000087036d230bed40f5c74f8c4aa0800c0b4bec183110b773', 372, 469724, 2609, 21, 221870040189, 220603058256)('0000000000000000000812d4b59c826bd2047e72e01c3ba3f3ad517c63e7de64', 714, 464554, 2580, 229, 217097056954, 215773254596)('0000000000000000101c965a762eb6ff0d541a3b03dd96130851d7efee9f57c7', 140, 463683, 2575, 21, 215429176215, 214933299405)('00000000000000001052a4c9af72f80c634e0da86733c1aeca3a206cf1662ccc', 366, 457507, 2541, 60, 211799631965, 209276054489)('0000000000000000021b72ac222d06f424902454c86748f096119ec81e8aeebd', 306, 456711, 2537, 12, 208676485402, 208532872467)('00000000000000001098af47793a0094c310e089efcc81d0ef6dc6cc53b2c198', 1057, 451541, 2508, 61, 204827126763, 203837799007)('00000000000000001196412df6f4d90e1c773a2fc4cb4d4d6b1d1360f5e62438', 1390, 439184, 2439, 74, 193164601772, 192802654368)('00000000000000450634d2a059e1a154cfd5783872ff9c7e788524e81fa163a1', 358, 369986, 2055, 41, 183989940557, 136860041316)('00000000000000000ce1f56134e7d27eee5db75466723e21655e478028fe2576', 491, 425781, 2365, 56, 181738057055, 181255397481)('00000000000000000816cabe4571b0b665993e637d00dba8ac45222b1712a83c', 526, 419896, 9997, 151, 180245981292, 176303413104)('000000000000000006c2664614dacb672c47a42a6ab270d1bdd01abc837c7f6d', 1040, 412318, 2290, 251, 170842082052, 169973147684)('00000000000000000b7df7d919db2b73c23d6c016acae098778ea70c9095e00c', 979, 368776, 2500, 468, 159134078850, 135978774480)('00000000000000000d710f3876a7b235aab173042cfe77ff7d0d1972bc279465', 416, 388415, 2157, 151, 153639042348, 150821932915)('00000000000000000e7c7050d8e8546c1db61a064f2cc6ce5c60f009dde8a875', 1061, 338825, 1882, 142, 141730172877, 114775274625)('00000000000000000a9cd67f563169d5f1452a305d6e311e822e4f9ffc88ca9a', 548, 364589, 2025, 134, 135044516959, 132895971801)('000000000000000009cd352daf6ab3edeceefd21838028d20ea60d0ef282afa8', 387, 359854, 1999, 22, 131024341095, 129453877960)`