041.md

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:

1. The AD can be increased, since the likelihood of a minority out-producing a majority over N blocks decreases exponentially as N increases
2. The huge block must still be propagated and validated by miners. BU theoretical and empirical studies of block propagation and “spy-mining” suggest that a huge block will either be orphaned or be followed by a sequence of empty blocks such that the average block size meets the network’s transaction throughput capacity.

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}