BACKGROUND
------------------------------------------------------
In November, Bitcoin ABC introduced "auto-finalization" and "parked blocks" functionality in order to mitigate the risk of 51% attacks.
Roughly, the way auto-finalization works is that after receiving a new block, a node will look back ten blocks prior and mark that previous block as finalized, which means that the node will not reorg past that point without manual intervention. This prevents attackers from double spending with large reorgs, and thus provides some protection for exchanges and the like.
The parked blocks functionality is intended to prevent against medium-length reorgs by adding a proof of work penalty. Specifically, a 4+ block reorg requires double the PoW; a 1 or 2 block reorg requires an extra 1/2 blocks' worth of PoW, and a 3 block reorg requires an extra blocks' worth of PoW. These are approximations, because of BCH's DAA which changes each block, but you can find this implemented in FindMostWorkChain() in validation.cpp.
When these changes were added, there was some discussion on r/btc about how auto-finalization could lead to chain splits because an attacker could mine a 10 block secret chain and broadcast it right at the perfect time that the honest network has broadcast its 10th block from the fork point; however, this is a difficult attack to pull off, and the parked blocks functionality actually makes it such that the attacker would need to mine more like 20 blocks secretly (approximately, because of the DAA), which makes it nearly impossible.
However, I did not see significant discussion regarding the implications of the parked block functionality itself, and the negative way in which it interacts with auto-finalization. Here is my attempt to rectify that, by presenting an attack that could cause chain splits with moderate probability even for attackers with minority hash rate.
ATTACK:
----------------------------------------------------
1) Somehow force a soft-split with the parked chain.
2) Make sure that the soft split continues until both sides finalize a block on their side of the split (possibly via balancing hashpower on both sides of the soft split).
More specifically:
1) Mine 3 blocks before the honest network mines three blocks, and broadcast block 3 when you detect honest block 3 has been broadcast.
2) Mine such that the difficulty/work condition is fulfilled (see step 2 below regarding lowering the difficulty): block1 + 1/2*priv2 + 1/2*pub2 > pub4 + priv4. If this condition isn't met, the attacker can just try to win the split from the next step and get 3-4 block rewards
3) Ensure that each side of the soft split mines block 4 before the other side mines block 5, moving into the double-PoW penalty phase. This may require withholding blocks temporarily if "too far ahead", such that there is a 3vs3 split. Since this could happen, it improves our probability of success compared to the calculations below.
4) Mine at the tip of whichever chain is behind, such that neither side reorgs before finalizing a block on their side of the split. That is, each side must mine 7 blocks w/o being reorg'd. (Must mine 1 before the other mines 4, or 2 before 8, etc.)
--Analysis is for step 4 is complicated and thus omitted below, but this is likely to succeed, and extremely likely to succeed if the network is split close to evenly or if the attacker has substantial hash power.
Analysis:
----------------------------------------------------------
Let x = attacker hash rate; y = main chain hash rate after soft split; z = alt/"attack" chain hash rate after soft split.
-----STEP 1-------------
--Start by assuming the attacker has just mined a block and keeps it secret; then they must win 2 blocks before the honest chain wins 3
--There are 6 possible ways to win: AA, AHA, HAA, AHHA, HHAA, HAHA (A = attacker block; H = honest block.)
Pr[success] = x^2 + 2*x^2*(1-x) + 3*x^2*(1-x)^2
x = 1/20 --> 1.4%
x = 1/10 --> 5.23%
x = 1/4 --> 26.17%
x = 1/3 --> 40.74%
x = 1/2 --> 68.75%
x = 3/5 --> 82.08%
------STEP 2---------------
Ideally, the 4th block for both chains will be of the proper difficulty that would prevent either chain from being reorged by seeing that 4th block, in which case the soft split should persist. This occurs if the following conditions are met:
1) In order to prevent the 4th honest block from reorging our 3 private blocks, we need: privChainWork + 1/2*(privBlock1work + privBlock2work) > mainChainWork
2) In order to prevent the 4th attack block from reorging the 3 public blocks, we need: mainChainWork + 1/2*(pubBlock1work + pubBlock2work) > privChainWork
Note that pubBlock1work == privBlock1work in all cases. Some algebra:
Condition 1 --> priv1 + priv2 + priv3 + 1/2*priv1 + 1/2*priv2 > pub1 + pub2 + pub3 + pub4
Condition 2 --> pub1 + pub2 + pub3 + 1/2*pub1 + 1/2*pub2 > priv1 + priv2 + priv3 + priv4
--> priv1 + priv2 + priv3 > pub1 + pub2 + pub3 + pub4 - (1/2*priv1 + 1/2*priv2)
--> pub1 + pub2 + pub3 > priv1 + priv2 + priv3 + priv4 - (1/2*pub1 + 1/2*pub2)
--> pub1 + pub2 + pub3 > pub1 + pub2 + pub3 + pub4 - (1/2*priv1 + 1/2*priv2) + priv4 - (1/2*pub1 + 1/2*pub2)
--> 0 > pub4 + priv4 - (1/2*priv1 + 1/2*priv2) - (1/2*pub1 + 1/2*pub2)
--> (1/2*priv1 + 1/2*priv2) + (1/2*pub1 + 1/2*pub2) > pub4 + priv4
--> block1 + 1/2*priv2 + 1/2*pub2 > pub4 + priv4
This is extremely likely if the difficulty is decreasing, which can happen on the private chain by mining blocks with future timestamps, and is likely on the main chain as well, since it will have less hashpower than before the fork point.
------STEP 3------------------------
--What is the probability that both chains mine block 4 before the other mines block 5?
--Assume both chains have 3 blocks already and the attacker has no secret blocks. If the attacker successfully mined block 4 already, our chances would be higher, so this is an underestimate.
--The chance of success depends on how much hash is on each side, which we don't know. Here we analyze two possibilities:
1) y = z (attacker's best case);
2) y = 3z (1/4 of the honest hash is on one side, 3/4 on the other)
--For case 1, assume the miner simply shuts off until one side wins a block, and then immediately mines the other side. They could also pick a side to start with, but we ignore that possibility. For case 2, we assume the attacker mines on the minority chain until a block is mined, and switches if the minority chain wins the first block.
Case 1:
Pr[success] = x + z = x + y
x = 1/20 --> 52.5%
x = 1/10 --> 55%
x = 1/4 --> 62.5%
x = 1/3 --> 66.67%
x = 1/2 --> 75%
x = 3/5 --> 80%
Case 2:
Pr[success] = (x+z)*(x+y) + y*(x+z) = x^2 + 2xy + 2yz + xz
x = 1/20 --> 42.41%
x = 1/10 --> 47.13%
x = 1/4 --> 60.16%
x = 1/3 --> 66.67%%
x = 1/2 --> 78.13%
x = 3/5 --> 84%
-----END STEP 3---------------------
EXAMPLE: Attacker has x fraction of the hash rate, and if he successfully finishes step 1, we assume that the difficulty works out in step 2 about half the time (probably a significant underestimate). Assume that each step is independent (not true, and causes an underestimate of success probability). Assume that the soft split that results splits the hash power 3 to 1, as in case 2 above. What is the probability of getting to the final step of the attack? How many initial blocks can the attacker expect to throw out before succeeding, and how long should this take given their hash rate?
x = 1/20 --> 0.3% --> 334 blocks thrown out, 6680 blocks total, 46.4 days
x = 1/10 --> 1.23% --> 82 blocks thrown out, 820 blocks total, 5.7 days
x = 1/4 --> 7.87% --> 13 blocks thrown out, 52 blocks total, 8.7 hours
x = 1/3 --> 13.58% --> 8 blocks thrown out, 24 blocks total, 4 hours
x = 1/2 --> 26.86% --> 4 blocks thrown out, 8 blocks total, 1.3 hours
x = 3/5 --> 34.47% --> 3 blocks thrown out, 5 blocks total, < 1 hour
DISCUSSION
-------------------------------------------
There are tradeoffs between protecting against chain-split attacks and protecting against deep reorgs, and a chain like that of BCH, with minority SHA-256 hashrate, must tread carefully. However, I think I have demonstrated here that there isn't a tradeoff when you have both parked blocks AND auto-finalization - the security assumption of "everything is fine if majority hashrate is honest" is no longer true, because a 33% attacker can cause a far worse outcome than a deep reorg.
That said, unlike with 51% attacks, this particular attack is one that isn't as likely to be profitable for the attacker financially, so it may not be exploited by random Internet bad guys. Also, it would require some more complicated software and is less likely to succeed without some amount of network intelligence, like knowing which nodes are miners or exchanges to target. However, it CAN still be profitable in a number of ways: shorting BCH, low-conf double spends, and/or the possible selfish mining profits that could accrue from a failure at some step of this strategy.
Timejacking may be useful to smooth over some of the parts of the attack by making sure that a timejacked node will view a block as valid/invalid when the rest of the network doesn't, via timestamp manipulation. This can buy the attacker a little bit of time, and "shape" the network such that he knows which side of the split his targets may be on. Furthermore, if the attacker fails to split the network somewhat evenly, then he can ignore the minority side of the fork and immediately start trying again on the majority side, in an attempt to cause a 3-way split.
Finally, while you may believe that this attack is improbable, the prevailing wisdom of this sub is that a super powerful cabal of bankers will stop at nothing to destroy Bitcoin Cash (operating via their alleged proxy, Blockstream), and since a well-resourced attacker should be able to pull this attack off, I believe y'all should be more concerned than you have been. My recommendation is to remove the parked block functionality from ABC entirely, and accept the risk of medium-length reorgs.
[link] [comments]
source https://www.reddit.com/r/btc/comments/am8fsl/bitcoin_abcs_parked_blocks_feature_allows/
No comments:
Post a Comment