BUIP041 (BUIP038 counter): Preventing a small number of hashing forces from launching large block attacks

0 182

question

BUIP038 describes a small computing power attack method: small computing power may temporarily create multiple blocks that are much larger than the parameter of "larger acceptable block size (EB)", and temporarily pass the parameter of "accepted block depth (AD)" set by the majority computing power. Once the EB value of a node is crossed, the node will allow any larger EB value blocks generated on the chain to be accepted without delay for a period of time afterwards. In layman's terms, it is called the "sticky gate" feature. If a minority computing power can overwhelm the majority computing power, the majority computing power will no longer be able to limit the block size, which is what BUIP038 claims, allowing a minority computing power to add blocks of "arbitrary size" to the blockchain.

This is an interesting attack vector, which can now be defended against in several ways:

1. The AD value can be increased, because the probability that the minority of computing power mines more blocks than the majority of computing power mines more than N blocks decreases exponentially as N increases.

2. Huge blocks still need to be propagated and verified by miners. BU's theoretical and empirical research on block propagation and "spy mining" shows that a huge block will be isolated or followed by a sequence of empty blocks, so that the average block size matches the network transaction throughput.

BUIP038 proposes to restore the "sticky gate" property to defend against this attack. However, restoring this property does not solve the problem. An attacker can produce a huge block* as its first forked block* (and second, third, etc.). If the attacker can mine AD more blocks than the majority can, the majority will be forced to switch to the attacker's branch 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. (Translator's note: I don't understand the logical relationship of the last sentence. 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 could reduce the number of huge blocks that can be mined, since there is no 144 block "sticky gate" period. However, it is far from certain that the "majority" of miners have different AD settings. In this case, the "majority" of miners will not be working on the same branch. Instead, they will each be working on a branch that starts at the tip of their own AD setting block. This may mean that the attacker's hashrate will become an effective majority.

BUIP038 is very detrimental to chain convergence. The purpose of the “emergent consensus” algorithm is to allow nodes and miners to resist bad changes to the block size, but accept such changes if the majority of hashpower is mining the larger block. But with BUIP038, a miner will never accept the block change and converge their chain to the tip of the chain. It will always try to fork to a lower block size, starting AD blocks from behind the tip (a huge disadvantage). Simulations of the two algorithms with various split sizes (see Appendix 1) show that BUIP038 has a lot of orphans when the blocks are always above a group of EB. For example: with the current algorithm, 1000 runs of ~1800 blocks, 66% vs 33% splits show a maximum of 13 orphans and an average of 2 orphans. But if BUIP038 is passed, the maximum and average number of orphans are 642 and 278, over 1800 blocks. BUIP038 The actual number of orphan blocks is infinite because the chain never converges, which means that 33% of the computing power is used to produce orphan blocks most of the time.

I don't believe miners can accept BUIP038's behavior because the economic losses caused by orphaned blocks are uncontrollable. Yes, miners should monitor their network carefully. Miners can (and should) monitor the network carefully and change their EB parameters immediately if they find that their EB gate has been broken and their hashrate is no longer following the tip of the main chain. But if this is what everyone wants, then it should be done - a miner can set AD=99999 (effectively infinity) and keep his choice of EB until it is manually changed. But with BUIP038, there is no way to do the opposite - accept the network's choice and mine at the tip of the chain until manually intervened by the miner. In fact, a good strategy is precisely to build a smaller block from the tip of the chain. At least in this case, your block has a high probability of being part of the chain, and by limiting your economic losses, your smaller block will reduce the average block size of the network (the network produces an average block size where the hashrate is favorable to the size of the block mined by each miner).

Suggested Solutions

In order to solve the problem of minority computing power attacks and maintain the convergence of the chain, the logic must be modified to increase the AD value based on how much the block size exceeds the previous excessive block. However, the initial larger block should wait for at least AD blocks. Therefore, the EAD coordinate graph is not drawn based on the first larger block or subsequent blocks. The first larger block is like a wall. (Translator's note: I don't understand the logic of this sentence for the time being, please forgive me. 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.)

Subsequent larger blocks - that is, larger blocks that are just slightly larger than the first block - should not have an initial AD "wall". If there is an initial "wall" for the first slightly larger block, then a miner could force other miners into the "always follow" behavior specified by BUIP038 by increasing the block size by 1 byte at a time.

Let us define the internal parameters, "Effective AD" (EAD), and "Effective EB" (EEB).

First, we calculate 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)

If none of the last 144 blocks on the chain are marked as larger:

EEB = Maximum (EB, the largest block in the last 144 blocks)

otherwise:

EEB = Maximum (EB, the largest block marked as a larger block in the last 144)

Now, let's generate a block of size S. If S <= EEB, this block is not considered a valid larger block, so return.

In addition, 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

ADfraction=floor (AD*(S-EEB)/EB) # Calculate "steps" in the graph. It mainly calculates the ratio of a new block greater than the EB value and gets a score. Then wait for the "acceptance depth" to be multiplied by the score

If EEB == EB :

EAD = AD + ADfraction # Add initial wall

otherwise:

EAD = ADfraction

Finalizing oversized blocks:

 if EAD == 0:
  This block is not excessive.
if EAD > 0:
mark this block excessive,
   and wait for EAD children before accepting it.

If EAD=0

This block is not a larger block

If EAD > 0 :

Mark this block as too large.

and wait for the sub-EAD before accepting it

For example, in English, if the new block is 2EB larger than the last large block, reject the branch chain until the length of the branch chain reaches 2*AD. This solves the problem of the network allowing large blocks due to low AD settings. The larger the block, the longer the nodes will resist the chain.

If all blocks are smaller than the last larger block within 24 hours (i.e. 144 blocks), no block will be marked as larger, so the next block will result in a full wait height of "AD+ADfraction". I don't think "hiccp" every 24 hours makes sense. So the "if" statement in the EEB calculation handles this case (the unmarked block must be smaller or equal to the previous block marked as larger and the block your node is waiting for). This also fits the case that needs to be handled during the startup phase. At startup, I don't think we want AD to trigger on older blocks, especially users who don't care about EB/AD settings will forget to set these values. Therefore, at least 144 blocks are checked at startup, and the EEB is set to the largest previous block.

This logical algorithm consensus is not critical. Other clients can create different algorithms to penalize large blocks without breaking consensus.

Example:

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.

For example:

EB=1MB

Now we enter the 2MB block. This is the first larger block. So EEB=EB. We wait for AD blocks + AD*(2-1)/1 blocks. That is: 2*AD blocks. Then EEB will become 2MB.

Now a 10MB block appears after 2MB (don't skip 2*AD blocks when calculating the next "sticky point"). (10-2)/2=8, so we are now stuck at 8*AD 10MB blocks. EEB=10 MB.

After 10MB, let's say we find an 11MB block. (11-10)/1=1, so we are now stuck at 1*AD blocks of 11MB. EEB=11MB.

Next, a 5MB block comes in. It's smaller than the EEB, so we accept it immediately.

Next, 143 blocks come through, and a 4MB block comes in. The EEB is 5MB, because there are no blocks marked as oversized, and 5MB is the largest. So the 4MB block is accepted immediately. If 145 blocks have come through, then the EEB becomes the EB and the 4MB block becomes a larger block.

Attachment 1:

The data is from a blockchain simulation (cut and pasted into a wide text editor). This simulation can be found 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}

Translator's note: I am translating a series of technical articles written by Bitcoin Unlimited developers to help Bitcoin users understand the Bitcoin Unlimited client. This series is very technical and I find it very difficult to translate. There are often sentences that I cannot understand, so the translation often has some incoherent parts. Please forgive me.

I would like to express my sincere gratitude to my friend @PC for patiently answering my translation questions about various difficult sentences. Thank you.