The first part of the text is a response by David A. Harding on the Bitcoin Stack Exchange Q&A site, explaining the "time warp attack". The time warp attack is a weakness at the consensus layer that the "Great Consensus Cleanup" soft fork proposal attempts to address. However, on the testnet 4 where the consensus cleanup soft fork was applied, developer Zawy found a similar attack. The second part is an introduction by murch on the Delving Bitcoin forum about this attack method and his recommended mitigation.
Time Warp Attack
Original link: https://bitcoin.stackexchange.com/questions/75831/what-is-time-warp-attack-and-how-does-it-work-in-general/75834#75834
Author: David A. Harding
The Bitcoin protocol (consensus rules) has two relevant rules regarding the timestamp in the Block header:
- Nodes will not accept a Block with a timestamp more than 2 hours ahead of their local time.
- A Block's timestamp must be greater than the median of the previous 11 Blocks, which is a requirement for it to be accepted by nodes. This rule is called the "Median Time Past (MTP)".
As you mentioned in your question, the change in mining difficulty is calculated based on the difference between the timestamp of the first and last Blocks in a 2016 Block difficulty adjustment period.
Given the above rules, if all miners act in collusion, they can, in the first 2015 Blocks of a period, advance the timestamp of each Block by only 1 second (the minimum increment allowed by the MTP rule) compared to the previous Block. This would only result in a slight decrease in difficulty, but imagine when they set the timestamp of the last Block slightly ahead of the current real time: the median would not change at all.
Real timestamps are in seconds, but here we'll use days to represent a set of 11 timestamps centered around the current time:
[-13, -13, -13, -13, -13, -13, -13, -13, -13, -13, 0]Note: The "-13" means these timestamps represent a time 13 days in the past.
So, the median of these 11 Block timestamps is still -13, meaning that in the last Block of the difficulty adjustment period, when the miners use a timestamp slightly ahead of the current time, going forward they don't need to advance the timestamp more than 1 second - the first Block of the next difficulty period can use the -13 timestamp, effectively starting that period 13 days in the past.
At the end of this second difficulty adjustment period, the miners can again push the timestamps as far forward as possible, so the protocol will think it took 28 days to mine all the Blocks in that period - only half the expected rate - and will therefore halve the mining difficulty for the next period.
At this point, the values used in the MTP rule would look like this:
[-27, -27, -27, -27, -27, -27, -27, -27, -27, -27, 0]The miners can repeatedly execute this attack (pushing the timestamps of the early Blocks in a period as far back as possible, and the last Block's timestamp as far forward as possible), continually reducing the difficulty, until they can mine 2016 Blocks in less than 2016 seconds, at which point they can no longer lower the difficulty further (because the MTP requires each Block's timestamp to advance by at least 1 second).
Your main question was how this attack could be possible without collusion among the majority of miners. Now you can see how it is possible when all miners are colluding. You should be able to see that the choice of timestamps allows a sufficiently lucky attacking miner to reliably prevent the median time from jumping to an honest value.
For example, imagine the timestamps of the previous 11 Blocks were:
[-27, 0, -27, 0, -27, 0, -27, 0, -27, 0, -27]If you sort these timestamps and find the median, you'll see the median is -27, even if 5/11 (45%) of the hash power is honestly mining. But doesn't this mean the attacking miner still needs 55% of the hash power? Maybe not - a large miner with over 30% hash power could use a "selfish mining" attack to gain an advantage, or that miner could directly threaten to orphan Blocks with honest timestamps, forcing honest miners to earn less revenue.
Personally, I don't think this attack is very likely to occur on Bitcoin, as it is slow to execute and very visible, but designers of other protocols may want to keep an eye on parameter changes that could make such attacks easier to execute.
Zawy's Alternating Timestamp Attack
Original link: https://delvingbitcoin.org/t/zawy-s-alternating-timestamp-attack/1062
Author: murch
@zawy yesterday introduced an attack in the Testnet 4 PR. I'll try to explain my understanding of it.
Similar to the time warp attack, this attack requires the attacker to be able to choose the timestamps of the majority of Blocks, but unlike the time warp attack, it does not rely on the difficulty adjustment periods not aligning (the off-by-one error). This attack appears theoretically viable, although it would require 16 weeks of selfish mining (and possibly 50% hash power as a prerequisite), which should make it impractical.
The basic idea of this attack is to lock in the timestamps of the vast majority of Blocks, but alternate between placing timestamps representing the future and the past on the last Block of each difficulty adjustment period, thereby oscillating between maximally lowering and raising the difficulty. This hot and cold cycle allows the attacker to produce many more Blocks than the expected output of honest miners in the same time period.
Specifically, the attacker does the following:
The attacker first pushes the timestamps as far back as possible. In the initial description, the timestamps only advanced 1 second per Block, but timestamps only need to advance every 6 seconds. The miners control a slight majority of hash power, so we expect Blocks to appear about every 20 minutes. Let's assume the Block rate is constant within a difficulty period for simplicity: 'Bit' must be translated into 'Bit'. 'Block' must be translated into 'Block'. 'Consensus' must be translated into 'Consensus'. 'TRON' must be translated into 'TRON'. 'Amp' must be translated into 'Amp'. 'BTC' must be translated into 'BTC'. 'HT' must be translated into 'HT'. 'ENS' must be translated into 'ENS'. 'AR' must be translated into 'AR'. 'XCH' must be translated into 'XCH'. 'AMP' must be translated into 'AMP'. 'RON' must be translated into 'RON'. 'ONG' must be translated into 'ONG'.
The attacker sets the timestamp of the last block of the difficulty adjustment period to 8 weeks after the attack start date. This block will not be accepted by other nodes, as it is more than two hours ahead of the local time of the nodes, so the attacker will be temporarily forked out of the network here. However, this future timestamp allows the attacker to reduce the difficulty of the next period to 1/4 of the current period. The timestamp of the first block of the second difficulty adjustment period also needs to be set to 8 weeks after the attack start date, to meet the requirements of the consensus cleanup proposal.Label Height MTP [s] Timestamp [s] Actual Time Elapsed Difficulty Start 0 < 0 0 0 D 1 < 0 0 20 min D 2 < 0 0 40 min D 3 < 0 0 60 min D … … … … … 6 0 1 2 h D … … … … … 12 1 2 4 h D … … … … …
The attacker continues to mine in the second difficulty period, pushing the timestamp forward as little as possible, and again pushes the timestamp of the last block forward by another 8 weeks, further reducing the difficulty by a factor of 4. Since the attacker controls about half the hash power, it takes 4 weeks to complete the first difficulty period, but only 1 week for the second difficulty period.Label Height MTP [s] Timestamp [s] Actual Time Elapsed Difficulty Start 0 < 0 0 0 D … … … … … 2014 335 336 4 weeks - 40 min D 2015 335 8 w 4 weeks - 20 min D 2016 336 8 w 4 weeks D/4
Zawy also mentions that the attacker can switch between setting the smallest possible timestamp and the largest possible timestamp for the last block of the difficulty adjustment. This can result in some difficulty adjustment periods having a nominal elapsed time of a negative number. However, the difficulty adjustment algorithm will treat this as half a week having elapsed, and still only increase the difficulty by a factor of 4. Even with the new constraint from the consensus cleanup proposal (not allowing the timestamp of the first block of the next difficulty period to be earlier than the last block of the previous period), the attacker can still switch between 1/4 and 1/16 of the starting difficulty. The attacker can complete two difficulty periods every 5/4 weeks.Label Height MTP [s] Timestamp [s] Actual Time Elapsed Difficulty Start 0 < 0 0 0 D 1 < 0 0 1200 D … … … … … 2014 335 336 4 weeks - 40 min D 2015 335 8 w 4 weeks - 20 min D 2016 336 8 w 4 weeks D/4 2017 336 337 4 weeks + 5 min D/4 2018 336 337 4 weeks + 10 min D/4 … … … … … 4030 671 672 5 weeks - 10 min D/4 4031 671 16 w 5 weeks - 5 min D/4 4032 672 16 w 5 weeks D/16 4033 672 673 5 weeks + 75 sec D/16
Once the actual elapsed time reaches 16 weeks, the attacker can publicly reveal the chain they have secretly mined, and (according to the assumption) their cumulative work will be slightly higher, thereby invalidating the 16-week transaction activity on the public network, reorganizing approximately 8064 blocks, and obtaining approximately 39816 block rewards, and may receive more transaction fees than on the public network, as they can package all non-conflicting transactions that have been broadcast during the slow block period on the public network.Label Height MTP [s] Timestamp [s] Actual elapsed time Difficulty Start 0 < 0 0 0 D 1 < 0 0 1200 D … … … … … 2014 335 336 4 weeks - 40 minutes D 2015 335 8 w 4 weeks - 20 minutes D 2016 336 8 w 4 weeks D/4 2017 336 337 4 weeks + 5 minutes D/4 2018 336 337 4 weeks + 10 minutes D/4 … … … … … 4030 671 672 5 weeks - 10 minutes D/4 4031 671 16 w 5 weeks - 5 minutes D/4 4032 672 16 w 5 weeks D/16 4033 672 673 5 weeks + 75 seconds D/16 … … … … … 6047 1007 1008 5 w 42 h - 75 s D/16 6048 1008 1009 5 w 42 h D/4 6049 1008 1009 5 w 42 h + 5 min D/4 … … … … … 8063 1343 1344 6 w 42 h - 5 min D/4 8064 1344 16 w 6 w 42 h D/16 8065 1344 16 w 6 w 42 h + 75 s D/16 … … … … … 10079 1679 1680 6 w 84 h - 75 s D/16 10080 1680 1681 6 w 84 h D/4 10081 1680 1681 6 w 84 h + 5 min D/4 … … … … … 12095 2015 2016 7 w 84 h - 5 min D/4 12096 2016 16 w 7 w 84 h D/16 12097 2016 16 w 7 w 84 h + 75 s D/16 … … … … … label height MTP [s] timestamp [s] elapsed time [s] difficulty start 0 < 0 0 0 D 1 < 0 0 1200 D 2 < 0 0 2400 D 3 < 0 0 3600 D … … … … … 6 0 1 7200 D … … … … … 12 1 2 14400 D … … … … … 2014 335 336 4 w − 40 min D 2015 335 8 w 4 w − 20 min D 2nd diff period 2016 336 8 w 4 w D/4 2017 336 337 4 w + 5 min D/4 2018 336 337 4 w + 10 min D/4 … … … … … 4030 671 672 5 w − 10 min D/4 4031 671 16 w 5 − 5 min D/4 3rd diff period 4032 672 16 w 5 w D/16 4033 672 673 5 w + 75 s D/16 … … … … … 6047 1007 1008 5 w 42 h − 75 s D/16 6048 1008 1009 5 w 42 h D/4 6049 1008 1009 5 w 42 h + 5 min D/4 … … … … … 8063 1343 1344 6 w 42 h − 5 min D/4 8064 1344 8 w 6 w 42 h D/16 8065 1344 8 w 6 w 42 h + 75 s D/16 … … … … … 10079 1679 1680 6 w 84 h − 75 s D/16 10080 1680 16 w 6 w 84 h D/64 10081 1680 16 w 6 w 84 h + 19 s D/64 … … … … … 12095 2015 2016 … D/64 12096 2016 2017 … D/16 12097 2016 2017 … D/16 … … … … … 14111 2351 2352 … D/16 14112 2352 8 w … D/64 14113 2352 8 w … D/64 … … … … … 16127 2687 2688 … D/64 16128 2688 16 w … D/256 16129 2688 16 w … D/256 … … … … … 18143 3023 3024 … D/256 18144 3024 3025 … D/64 18145 3024 3025 … D/64 … … … … … This not only allows attackers to create more blocks, but also exponentially reduces the difficulty.
Conclusion
It may be useful to impose additional requirements on the timestamp for the soft fork, requiring the timestamp of the last block in a difficulty period N to be greater than the first block in the same period. That is, to require:
$$n ∈ ℕ; timestamp_{2016×n} < timestamp_{2016×n+2015}$$
I do not believe that honest mining advancing the timestamp (at least one second, which is indirectly caused by the existing MTP rule) across difficulty periods will conflict with this rule, unless the timestamp is manipulated as extremely as described above. However, to my knowledge, such a rule should be able to reduce this attack surface.
