BUIP041 (BUIP038 Counter): Prevent Minority Hash Power From Injecting Very Large Blocks
Proposer: Andrew Stone
Submitted: 2016-12-07
Status: closed
THE PROBLEM
BUIP038 outlines an attack where a minority
of the hash power can, at low probability, temporarily overwhelm the
excessive block (EB) parameter of network nodes by temporarily
out-producing the mining majority for accept depth (AD) blocks. Once a
node’s EB is exceeded, it allows subsequent excessive blocks on that
chain without delay for a period of time. This is colloquially called
the “sticky gate” feature. So if a minority hash power is able to
overwhelm a majority of hash power, that majority no longer limits block
size which BUIP038 claims allows the minority to then add blocks of “any
size at all” onto the blockchain.
This is an interesting attack vector that is/can be defended against in
several ways using the code today:
BUIP038 proposes to revert the sticky gate feature to defeat this
attack. However, reverting the feature does not solve the problem. An
attacker could produce a huge block *as its first fork block* (and
second, third, etc). If the attacker is then able to out-produce the
mining majority for AD blocks, the mining majority will switch to the
attacker’s chain. In other words, is unnecessary to wait for the “sticky
gate” period to produce the huge block. The block can be produced at any
time during the attacker’s attempt.
However, BUIP038 may reduce the number of huge blocks that can be
produced, because there is no 144 block “sticky gate” period. But this
is far from certain if the “majority” miners had different AD settings.
In this case, the “majority” miners will not be working on the same
fork. Instead they will each be working on a fork that starts at their
own AD setting blocks from the tip. This may mean that the attacker’s
hash power becomes the effective majority.
BUIP038 has an extremely detrimental effect on chain convergence. The
intention of the “emergent consensus” algorithm is to allow nodes and
miners to resist undesirable changes to the block size, but to accept
the change if the hash power majority is mining it. But by passing
BUIP038, a miner will never accept the block size change and converge on
the chain tip. It will always attempt to fork to a lower block size,
starting AD blocks behind the tip (a huge disadvantage). Simulations of
both algorithms (see Appendix 1) with various split sizes show that a
BUIP038 has significantly more orphans when blocks are consistently
above one group’s EB. For example, 1000 runs of ~1800 blocks with a 66%
vs 33% split shows a maximum and average of 13 and 2 orphans using the
current algorithm. But if BUIP038 is passed, the maximum and average
number of orphans is 642 and 278 over 1800 blocks. The actual number of
orphans with BUIP038 is unbounded, since the chain never converges,
meaning that 33% of the hash power is producing orphan blocks most of
the time.
I do not believe that the BUIP038 behavior is acceptable to miners,
since orphans and therefore financial losses are unbounded. Yes, miners
could (and should) monitor their networks carefully and move their EB so
as to not trail the chain tip if their EB gate is broken. But if this is
the desired behavior, it is available today — a miner can set its
AD=999999 (to effectively infinity), and remain on his chosen EB until
it is manually moved. But if BUIP038 is passed, there is no way to
create the opposite behavior — to accept the network’s choice and mine
on the tip until the miner manually intervenes. In fact, a good strategy
would be exactly this behavior: build smaller blocks from the chain tip.
At least in this case, your blocks have a high chance of being part of
the blockchain, limiting your financial loss, and your smaller blocks
will reduce the network’s average block size (the network produces an
average block size which is the hash power weighted average of the block
size mined by each miner).
PROPOSED SOLUTION
To solve both the minority attack problem and keep chain’s convergence
properties, the algorithm must be modified to increase the AD in
proportion to how much a block exceeds the EB, compared to prior
excessive blocks. But the initial excessive block should wait at least
AD blocks. So a graph of the EAD is different based on whether this is
the first excessive block or subsequent ones. If its the first, it looks
like a wall with a staircase on top.
2*AD --|
–|
–|
–|
–|
AD |
|
|
|
|
0 EB 2*EB
Subsequent excessive blocks — that is, excessive blocks that are just a
bit bigger than the first one — should not have the initial AD “wall”.
If the initial “wall” existed every time a block was a bit bigger, a
miner could force other miners into the “always trailing” behavior
specified in BUIP038 by increasing the block size by 1 byte every
time.
Let us define internal parameters, the “effective AD” (EAD), and
“effective EB” (EEB).
First, we calculate the EEB:
if none of the last 144 blocks are marked excessive on this chain:
EEB = max(EB, largest block of the last 144 on this chain)
else:
EEB = max(EB, largest block marked excessive of the last 144 on this
chain)
Now say that a block is generated of size S. If S <= EEB, this block
is not excessive so return.
Otherwise the EAD is calculated as follows:
ADfraction = floor(AD*(S — EEB)/EB) # This calculates the “steps” in
the graph. Its basically computing how much bigger the new block is in
fractions of EB. And then waiting “accept depth” times that fraction.
if EEB == EB:
EAD = AD + ADfraction # Add the initial wall
else:
EAD = ADfraction
Then final excessive block determination:
if EAD == 0:
this block is not excessive.
if EAD > 0:
mark this block excessive,
and wait for EAD children before accepting it.
For example, in English, if the new block is 2 EB’s bigger than the last
large block, then reject the chain until it is longer than 2*AD. This
solves the problem of the network allowing huge blocks due to low AD
settings. The bigger the block, the longer the node resists the chain.
If an attacker attempts to grow the block size slowly, other miners will
periodically hit one of the “risers” in the step graph, and resist the
chain for one block. During that period this miner may find a block,
creating a competing chain of small blocks.
If there are 24 hours (144 blocks) of blocks smaller size than the last
excessive block, none of them will be marked excessive, so the next
block would cause a full wait of AD + ADfraction. I do not think it
makes sense to “hiccup” every 24 hours, so the “if” statement in the EEB
calculation handles this case (unmarked blocks must be smaller than or
equal to a prior block that was marked excessive and your node waited
for). This also handles the startup case. On startup, I do not think we
want the AD to trigger for older blocks, especially since users who
don’t care about the EB/AD settings will forget to set them. So on
startup the last 144 blocks are examined, and the EEB is set to the
largest prior block.
This algorithm is not consensus-critical. Other clients can create
different algorithms to penalize very large blocks without breaking
consensus.
Examples:
EB = 1MB
Now 2MB block comes in. This is the first excessive block, so EEB=EB. We
wait AD blocks + AD*(2–1)/1 blocks. That is: 2*AD blocks. Subsequently
EEB will be 2MB.
Now a 10MB block comes after the 2MB (do NOT skip 2*AD blocks when
calculating the next “sticky” point). (10–2)/1 = 8, so we are now stuck
on the 10MB block for 8*AD blocks. EEB=10MB
After the 10MB block, let’s say we hit an 11MB block. (11–10)/1 = 1, so
we are now stuck on the 11MB block for 1*AD blocks. EEB=11MB
Next a 5 MB block comes in. This is less than the EEB so we accept it
immediately.
Next, 143 small blocks pass and a 4MB block comes in. EEB is 5MB because
there are no excessive-marked blocks, and the 5MB block is the largest.
So the 4MB block is accepted immediately. If 145 blocks had passed, then
the EEB would be EB and the 4MB block would be excessive.
APPENDIX 1:
Data from blockchain simulations (cut and paste into a wide text
editor). The simulation is available at
https://github.com/gandrewstone/chainsim:
BUIP041 (this BUIP):
SPLIT (block height, max blocks, avg blocks): max fork depth, max
orphans, avg orphans, { X:Y where Y runs had X forks }
0.500000/0.500000 (1807, 1810, 1669): 4, 33, 5, {0: 73, 1: 365, 2: 186,
3: 129, 4: 103, 5: 47, 6: 42, 7: 16, 8: 18, 9: 10, 10: 5, 11: 2, 12: 3,
15: 1}
0.600000/0.400000 (1793, 1798, 1670): 4, 20, 3, {0: 129, 1: 505, 2: 196,
3: 95, 4: 37, 5: 23, 6: 9, 7: 1, 8: 4, 9: 1}
0.667000/0.333000 (1821, 1822, 1668): 4, 14, 2, {0: 189, 1: 572, 2: 147,
3: 55, 4: 23, 5: 11, 6: 1, 7: 2}
0.750000/0.250000 (1812, 1814, 1669): 4, 14, 1, {0: 276, 1: 596, 2: 103,
3: 20, 4: 4, 8: 1}
0.800000/0.200000 (1794, 1795, 1670): 4, 6, 1, {0: 429, 1: 505, 2: 54,
3: 11, 4: 1}
0.900000/0.100000 (1787, 1788, 1667): 4, 4, 1, {0: 637, 1: 343, 2: 18,
3: 2}
0.950000/0.050000 (1793, 1793, 1667): 2, 2, 1, {0: 806, 1: 192, 2: 2}
BUIP001 + trailing fix (currently released code):
SPLIT (block height, max blocks, avg blocks): max fork depth, max
orphans, avg orphans, { X:Y where Y runs had X forks }
0.500000/0.500000 (1801, 1809, 1673): 4, 34, 5, {0: 60, 1: 386, 2: 207,
3: 134, 4: 76, 5: 48, 6: 38, 7: 15, 8: 14, 9: 8, 10: 1, 11: 3, 12: 4,
13: 4, 17: 1, 18: 1}
0.600000/0.400000 (1788, 1792, 1669): 4, 21, 3, {0: 117, 1: 502, 2: 212,
3: 92, 4: 50, 5: 15, 6: 6, 7: 1, 8: 1, 9: 1, 10: 1, 11: 1, 12: 1}
0.667000/0.333000 (1767, 1771, 1667): 4, 12, 2, {0: 212, 1: 552, 2: 153,
3: 56, 4: 21, 5: 3, 6: 3}
0.750000/0.250000 (1793, 1794, 1669): 4, 8, 1, {0: 338, 1: 558, 2: 72,
3: 21, 4: 9, 5: 1, 6: 1}
0.800000/0.200000 (1823, 1824, 1668): 4, 7, 1, {0: 394, 1: 531, 2: 64,
3: 7, 4: 4}
0.900000/0.100000 (1786, 1786, 1669): 3, 3, 1, {0: 667, 1: 326, 2: 7}
0.950000/0.050000 (1828, 1828, 1665): 4, 4, 1, {0: 811, 1: 186, 2: 3}
BUIP038 (Original BUIP001 commit):
SPLIT (block height, max blocks, avg blocks): max fork depth, max
orphans, avg orphans, { X:Y where Y runs had X forks }
0.500000/0.500000 (940, 1820, 1671): 23, 937, 418, {714: 1, 740: 1, 742:
1, 743: 1, 746: 1, 747: 1, 750: 1, 752: 2, 759: 2, 760: 1, 761: 2, 763:
1, 764: 2, 766: 1, 767: 1, 768: 2, 769: 1, 770: 4, 771: 2, 772: 1, 773:
2, 774: 5, 775: 5, 776: 4, 777: 4, 778: 6, 779: 3, 780: 10, 781: 1, 782:
3, 783: 9, 784: 2, 785: 9, 786: 12, 787: 8, 788: 6, 789: 5, 790: 4, 791:
4, 792: 14, 793: 7, 794: 9, 795: 6, 796: 9, 797: 8, 798: 9, 799: 11,
800: 9, 801: 13, 802: 11, 803: 12, 804: 17, 805: 11, 806: 10, 807: 9,
808: 12, 809: 14, 810: 11, 811: 15, 812: 9, 813: 12, 814: 15, 815: 14,
816: 9, 817: 11, 818: 10, 819: 14, 820: 20, 821: 3, 822: 10, 823: 14,
824: 15, 825: 15, 826: 10, 827: 10, 828: 13, 829: 17, 830: 15, 831: 19,
832: 11, 833: 13, 834: 11, 835: 10, 836: 16, 837: 14, 838: 13, 839: 9,
840: 9, 841: 10, 842: 13, 843: 12, 844: 6, 845: 10, 846: 8, 847: 5, 848:
10, 849: 14, 850: 10, 851: 12, 852: 10, 853: 11, 854: 10, 855: 8, 856:
10, 857: 8, 858: 5, 859: 4, 860: 5, 861: 5, 862: 7, 863: 3, 864: 4, 865:
3, 866: 1, 867: 4, 868: 7, 869: 2, 870: 4, 871: 5, 872: 5, 873: 6, 874:
5, 876: 2, 877: 3, 878: 2, 879: 1, 880: 3, 881: 4, 882: 6, 883: 1, 884:
2, 886: 1, 889: 1, 890: 2, 891: 2, 892: 1, 893: 2, 894: 1, 896: 3, 897:
1, 898: 1, 900: 2, 901: 2, 908: 1, 912: 1, 913: 2, 923: 1, 932: 1}
0.600000/0.400000 (1101, 1800, 1669): 19, 744, 334, {595: 2, 598: 1,
599: 2, 602: 1, 603: 1, 604: 1, 607: 7, 608: 1, 609: 2, 610: 1, 611: 5,
612: 2, 613: 3, 614: 3, 615: 3, 616: 3, 617: 4, 618: 8, 619: 6, 620: 2,
621: 2, 622: 3, 623: 6, 624: 5, 625: 7, 626: 5, 627: 5, 628: 5, 629: 11,
630: 3, 631: 9, 632: 7, 633: 11, 634: 7, 635: 10, 636: 9, 637: 7, 638:
8, 639: 8, 640: 14, 641: 7, 642: 10, 643: 11, 644: 13, 645: 17, 646: 7,
647: 12, 648: 9, 649: 13, 650: 16, 651: 13, 652: 15, 653: 14, 654: 12,
655: 14, 656: 20, 657: 9, 658: 15, 659: 14, 660: 16, 661: 11, 662: 15,
663: 28, 664: 16, 665: 9, 666: 16, 667: 17, 668: 18, 669: 17, 670: 15,
671: 14, 672: 9, 673: 13, 674: 18, 675: 10, 676: 8, 677: 19, 678: 18,
679: 8, 680: 11, 681: 13, 682: 17, 683: 15, 684: 8, 685: 8, 686: 13,
687: 12, 688: 8, 689: 10, 690: 6, 691: 10, 692: 7, 693: 9, 694: 9, 695:
8, 696: 2, 697: 5, 698: 8, 699: 3, 700: 2, 701: 4, 702: 6, 703: 8, 704:
3, 705: 4, 706: 3, 707: 5, 708: 1, 709: 4, 710: 4, 711: 5, 712: 5, 713:
2, 714: 3, 715: 1, 716: 1, 717: 2, 718: 4, 720: 1, 721: 2, 722: 2, 723:
2, 724: 1, 725: 1, 726: 1, 727: 1, 729: 1, 736: 1, 737: 1, 744: 1}
0.667000/0.333000 (1219, 1785, 1670): 21, 624, 278, {512: 3, 513: 4,
514: 6, 515: 4, 516: 7, 517: 8, 518: 3, 519: 5, 520: 5, 521: 9, 522: 10,
523: 11, 524: 9, 525: 8, 526: 8, 527: 10, 528: 13, 529: 9, 530: 10, 531:
11, 532: 13, 533: 7, 534: 15, 535: 12, 536: 15, 537: 13, 538: 10, 539:
19, 540: 20, 541: 17, 542: 16, 543: 20, 544: 11, 545: 19, 546: 24, 547:
12, 548: 13, 549: 14, 550: 17, 551: 19, 552: 11, 553: 22, 554: 9, 555:
13, 556: 15, 557: 26, 558: 15, 559: 32, 560: 15, 561: 17, 562: 10, 563:
14, 564: 17, 565: 13, 566: 13, 567: 16, 568: 14, 569: 17, 570: 10, 571:
15, 572: 10, 573: 4, 574: 9, 575: 10, 576: 7, 577: 13, 578: 15, 579: 12,
580: 11, 581: 7, 582: 10, 583: 7, 584: 5, 585: 9, 586: 5, 587: 10, 588:
4, 589: 2, 590: 1, 591: 1, 592: 3, 593: 5, 594: 4, 595: 4, 596: 4, 597:
1, 598: 2, 599: 2, 600: 3, 601: 3, 602: 1, 603: 2, 604: 2, 606: 1, 607:
1, 611: 1, 612: 1, 613: 1, 615: 1, 624: 1, 476: 1, 479: 1, 483: 1, 484:
1, 488: 1, 489: 2, 498: 1, 499: 2, 501: 3, 502: 2, 503: 3, 505: 1, 506:
2, 507: 4, 508: 1, 509: 2, 510: 2, 511: 2}
0.750000/0.250000 (1362, 1788, 1669): 11, 478, 209, {353: 1, 355: 1,
356: 1, 357: 1, 362: 2, 364: 1, 365: 1, 368: 1, 370: 2, 371: 1, 373: 4,
374: 3, 375: 2, 377: 3, 378: 2, 379: 2, 380: 2, 381: 6, 382: 2, 383: 5,
384: 5, 385: 6, 386: 5, 387: 4, 388: 6, 389: 8, 390: 6, 391: 8, 392: 17,
393: 6, 394: 7, 395: 14, 396: 7, 397: 18, 398: 19, 399: 22, 400: 25,
401: 14, 402: 23, 403: 15, 404: 12, 405: 24, 406: 23, 407: 22, 408: 18,
409: 16, 410: 13, 411: 23, 412: 15, 413: 28, 414: 16, 415: 13, 416: 24,
417: 13, 418: 20, 419: 16, 420: 21, 421: 18, 422: 12, 423: 17, 424: 18,
425: 20, 426: 21, 427: 22, 428: 20, 429: 13, 430: 13, 431: 12, 432: 12,
433: 11, 434: 16, 435: 21, 436: 10, 437: 11, 438: 14, 439: 7, 440: 10,
441: 7, 442: 6, 443: 13, 444: 13, 445: 3, 446: 2, 447: 4, 448: 5, 449:
8, 450: 5, 451: 3, 452: 7, 453: 2, 454: 4, 455: 2, 456: 5, 457: 1, 458:
1, 459: 3, 460: 1, 461: 3, 462: 1, 463: 2, 464: 1, 465: 2, 468: 1, 474:
1, 478: 1}
0.800000/0.200000 (1432, 1786, 1666): 7, 392, 167, {278: 1, 281: 1, 283:
1, 284: 1, 285: 2, 286: 1, 288: 1, 289: 2, 290: 3, 291: 2, 292: 5, 293:
1, 294: 3, 295: 3, 296: 5, 297: 4, 298: 6, 299: 6, 300: 4, 301: 5, 302:
7, 303: 3, 304: 6, 305: 8, 306: 3, 307: 9, 308: 11, 309: 11, 310: 16,
311: 7, 312: 6, 313: 8, 314: 11, 315: 12, 316: 12, 317: 18, 318: 23,
319: 19, 320: 16, 321: 19, 322: 15, 323: 21, 324: 14, 325: 19, 326: 19,
327: 27, 328: 15, 329: 21, 330: 24, 331: 28, 332: 24, 333: 20, 334: 25,
335: 24, 336: 18, 337: 24, 338: 15, 339: 19, 340: 22, 341: 20, 342: 15,
343: 17, 344: 24, 345: 15, 346: 22, 347: 14, 348: 13, 349: 12, 350: 9,
351: 15, 352: 11, 353: 5, 354: 16, 355: 6, 356: 12, 357: 7, 358: 7, 359:
5, 360: 6, 361: 11, 362: 10, 363: 3, 364: 5, 365: 5, 366: 7, 367: 3,
368: 3, 369: 3, 370: 4, 371: 3, 372: 1, 373: 3, 374: 5, 375: 1, 376: 1,
378: 1, 380: 1, 382: 1, 384: 1, 392: 1}
0.900000/0.100000 (1633, 1828, 1667): 4, 211, 84, {131: 2, 133: 1, 135:
4, 136: 2, 137: 3, 138: 2, 139: 2, 140: 4, 141: 4, 142: 5, 143: 6, 144:
4, 145: 8, 146: 10, 147: 10, 148: 12, 149: 10, 150: 16, 151: 19, 152:
14, 153: 19, 154: 17, 155: 14, 156: 35, 157: 25, 158: 23, 159: 34, 160:
25, 161: 28, 162: 21, 163: 34, 164: 32, 165: 29, 166: 29, 167: 23, 168:
35, 169: 37, 170: 19, 171: 29, 172: 31, 173: 32, 174: 24, 175: 26, 176:
24, 177: 21, 178: 29, 179: 22, 180: 18, 181: 15, 182: 17, 183: 8, 184:
7, 185: 7, 186: 12, 187: 10, 188: 11, 189: 3, 190: 5, 191: 4, 192: 2,
193: 2, 194: 3, 195: 2, 196: 2, 197: 1, 198: 3, 199: 3, 200: 2, 201: 1,
203: 1, 204: 1, 205: 1, 208: 1, 211: 1, 113: 1, 122: 1}
0.950000/0.050000 (1706, 1789, 1667): 3, 115, 42, {57: 2, 58: 1, 59: 1,
60: 3, 61: 1, 63: 1, 64: 7, 65: 4, 66: 6, 67: 8, 68: 13, 69: 14, 70: 17,
71: 18, 72: 25, 73: 18, 74: 27, 75: 21, 76: 32, 77: 40, 78: 36, 79: 44,
80: 42, 81: 49, 82: 47, 83: 43, 84: 33, 85: 39, 86: 44, 87: 54, 88: 30,
89: 24, 90: 27, 91: 26, 92: 36, 93: 15, 94: 26, 95: 15, 96: 20, 97: 15,
98: 11, 99: 11, 100: 10, 101: 13, 102: 6, 103: 2, 104: 9, 105: 4, 106:
2, 107: 2, 109: 2, 110: 1, 112: 1, 114: 1, 115: 1}