Yesterday, I came up with a new algorithm for making secret reorg attacks very expensive and difficult to pull off. This new algorithm is designed to avoid the permanent chainsplit vulnerabilities of ABC 0.18.5 while being more effective at punishing malicious behavior.
The key to the new algorithm is to punish exactly the behavior that indicates malice. First, publishing a block after another block at the same height has arrived on the network suggests malice or poor performance, and the likelihood of malice increases as the delay increases. A good algorithm would penalize blocks in proportion to how much later they were published after the competing block. Second, building upon a block that was intentionally delayed is also a sign of malice. Therefore, a good algorithm would discount the work done by blocks based not only on their own delays, but the delays that were seen earlier in that chain as well. Since the actions at the start of the fork are more culpable (as they generate the split), we want to weight those blocks more heavily than later blocks.
I wrote up an algorithm that implements these features. When comparing two chains, you look at the PoW done since the fork block, and divide that PoW by a penalty score. The penalty score for each chain is calculated as the sum of the penalty scores for each block. Each block's penalty score is equal to the apparent time delay of that block[1], divided by 120 seconds[2], and further divided by the square[3] of that block's height[4] from the fork.
This algorithm has some desirable properties:
- It provides smooth performance. There are no corners or sharp changes in its incentive structure or penalty curve.
- It converges over very long time scales. Eventually, if one chain has more hashrate than the other and that is sustained indefinitely, the chain with the most hashrate will win by causing the chain penalty score for the slower (less-PoW) chain to grow.
- The long-term convergence means that variation in observed times early in the fork will not cause permanent chainsplits.
- Long-term convergence means that nodes can follow the standard most-PoW rule during initial block download and get the same results unless an attack is underway, in which case the node will only temporarily disagree.
- Over intermediate time scales (e.g. hours to weeks), the penalty given to secret-mining deep-reorg chains is very large and difficult to overcome even with a significant hashrate advantage. The penalty increases the longer the attack chain is kept secret. This makes attack attempts ineffective unless they are published within about 20 minutes of the attack starting.
- Single-block orphan race behavior is identical to existing behavior unless one of the blocks has a delay of at least 120 seconds, in which case that chain would require a total of 3 blocks to win (or more) instead of just 2.
- As the algorithm strongly punishes hidden chains, finalization becomes much safer as long as you prevent finalization from happening while there are known competitive alternate chains. However, this algorithm is still effective without finalization.
I wrote up this algorithm into a Python sim yesterday and have been playing around with it since. It seems to perform quite well. For example, if the attacker has 1.5x as much hashrate as the defenders (who had 100% of the hashrate before the fork), mine in secret for 20 minutes before publishing, and if finalization is enabled after 10 blocks when there's at least a 2x score advantage, then the attacker gets an orphan rate of 49.3% on their blocks and is only able to cause a >= 10 block reorg in 5.2% of cases, and none of those happen blindly, as the opposing chain shows up when most transactions have about 2 confirmations. If the attacker waits 1 hour before publishing, the attack is even less effective: 94% of their blocks are orphaned, 95.6% of their attempts fail, 94.3% of the attacks end with defenders successfully finalizing, and only 0.6% of attack attempts result in a >= 10 block reorg.
The code for my algorithm and simulator can be found on my antiReorgSim Github repository. If you guys have time, I'd appreciate some review and feedback. To run it:
git clone https://github.com/jtoomim/antiReorgSim.git cd antiReorgSim python reorgsim.py # use pypy if you have it, as it's 30x faster
Thanks! Special thanks to Jonald Fyookball and Mark Lundeberg for reviewing early versions of the code and the ideas. I believe Jonald is working on a Medium post based on some of these concepts. Keep an eye out for it.
Note 1: This time delay is calculated by finding the best competing chain's last block with less work than this one and the first block with more work than this one and interpolating the time-first-seen between the two. The time at which the block was fully downloaded and verified is used as time-first-seen, not the time at which the header was received nor the block header's timestamp.
Note 2: An empirical constant, intended to be similar to worst-case block propagation times.
Note 3: A semi-empirical constant; this balances the effect of early blocks against late blocks. The motivation for squaring is that late blocks gain an advantage for two multiplicative reasons: First, there are more late blocks than early blocks. Second, the time deltas for late blocks are larger. Both of these factors are linear versus time, so canceling them out can be done by dividing by height squared. This way, the first block has about as much weight as the next 4 blocks; the first two blocks have as much weight as the next 9 blocks; and the first (n) blocks have about as much weight as the next (n+1)2 blocks. Any early advantage can be overcome eventually by a hashrate majority, so over very long time scales (e.g. hours to weeks), this rule is equivalent to the simple Satoshi most-PoW rule, as long as the hashrate on each chain is constant. However, over intermediate time scales, the advantage to the first seen blocks is large enough that the hashrate will likely not remain constant, and hashrate will likely switch over to whichever chain has the best score and looks the most honest.
Note 4: The calculation doesn't actually use height, as that would be vulnerable to DAA manipulation. Instead, the calculation uses pseudoheight, which uses the PoW done and the fork block's difficulty to calculate what the height would be if all blocks had the fork block's difficulty.
[link] [comments]
source https://www.reddit.com/r/btc/comments/9zrmtx/a_better_antireorg_algorithm_using_firstseen/
No comments:
Post a Comment