* [bitcoin-dev] Getting around to fixing the timewarp attack. @ 2018-08-20 20:14 Gregory Maxwell 2018-08-22 13:48 ` Jorge Timón 2018-08-24 9:35 ` Johnson Lau 0 siblings, 2 replies; 5+ messages in thread From: Gregory Maxwell @ 2018-08-20 20:14 UTC (permalink / raw) To: Bitcoin Dev Since 2012 (IIRC) we've known that Bitcoin's non-overlapping difficulty calculation was vulnerable to gaming with inaccurate timestamps to massively increase the rate of block production beyond the system's intentional design. It can be fixed with a soft-fork that further constraints block timestamps, and a couple of proposals have been floated along these lines. I put a demonstration of timewarp early in the testnet3 chain to also let people test mitigations against that. It pegs the difficulty way down and then churned out blocks at the maximum rate that the median time protocol rule allows. I, and I assume others, haven't put a big priority into fixing this vulnerability because it requires a majority hashrate and could easily be blocked if someone started using it. But there haven't been too many other network consensus rules going on right now, and I believe at least several of the proposals suggested are fully compatible with existing behaviour and only trigger in the presence of exceptional circumstances-- e.g. a timewarp attack. So the risk of deploying these mitigations would be minimal. Before I dust off my old fix and perhaps prematurely cause fixation on a particular approach, I thought it would be useful to ask the list if anyone else was aware of a favourite backwards compatible timewarp fix proposal they wanted to point out. Cheers. ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [bitcoin-dev] Getting around to fixing the timewarp attack. 2018-08-20 20:14 [bitcoin-dev] Getting around to fixing the timewarp attack Gregory Maxwell @ 2018-08-22 13:48 ` Jorge Timón 2018-08-24 9:35 ` Johnson Lau 1 sibling, 0 replies; 5+ messages in thread From: Jorge Timón @ 2018-08-22 13:48 UTC (permalink / raw) To: Gregory Maxwell, Bitcoin Protocol Discussion I only knew about ArtForz's fix, which isn't backwards compatible. https://github.com/bitcoin/bitcoin/compare/0.11...jtimon:hardfork-timewarp-0.11 https://github.com/bitcoin/bips/blob/master/bip-0099.mediawiki#code On Mon, Aug 20, 2018 at 10:14 PM, Gregory Maxwell via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > Since 2012 (IIRC) we've known that Bitcoin's non-overlapping > difficulty calculation was vulnerable to gaming with inaccurate > timestamps to massively increase the rate of block production beyond > the system's intentional design. It can be fixed with a soft-fork that > further constraints block timestamps, and a couple of proposals have > been floated along these lines. > > I put a demonstration of timewarp early in the testnet3 chain to also > let people test mitigations against that. It pegs the difficulty way > down and then churned out blocks at the maximum rate that the median > time protocol rule allows. > > I, and I assume others, haven't put a big priority into fixing this > vulnerability because it requires a majority hashrate and could easily > be blocked if someone started using it. > > But there haven't been too many other network consensus rules going on > right now, and I believe at least several of the proposals suggested > are fully compatible with existing behaviour and only trigger in the > presence of exceptional circumstances-- e.g. a timewarp attack. So > the risk of deploying these mitigations would be minimal. > > Before I dust off my old fix and perhaps prematurely cause fixation on > a particular approach, I thought it would be useful to ask the list if > anyone else was aware of a favourite backwards compatible timewarp fix > proposal they wanted to point out. > > Cheers. > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [bitcoin-dev] Getting around to fixing the timewarp attack. 2018-08-20 20:14 [bitcoin-dev] Getting around to fixing the timewarp attack Gregory Maxwell 2018-08-22 13:48 ` Jorge Timón @ 2018-08-24 9:35 ` Johnson Lau 2018-08-30 20:55 ` Bram Cohen 1 sibling, 1 reply; 5+ messages in thread From: Johnson Lau @ 2018-08-24 9:35 UTC (permalink / raw) To: Gregory Maxwell, bitcoin-dev To determine the new difficulty, it is supposed to compare the timestamps of block (2016n - 1) with block (2016n - 2017). However, an off-by-one bug makes it compares with block (2016n - 2016) instead. A naive but perfect fix is to require every block (2016x) to have a timestamp not smaller than that of its parent block. However, a chain-split would happen even without any attack, unless super-majority of miners are enforcing the new rules. This also involves mandatory upgrade of pool software (cf. pool software upgrade is not mandatory for segwit). The best way is to do it with something like BIP34, which also requires new pool software. We could have a weaker version of this, to require the timestamp of block (2016x) not smaller than its parent block by t-seconds, with 0 <= t <= infinity. With a bigger t, the fix is less effective but also less likely to cause intentional/unintentional split. Status quo is t = infinity. Reducing the value of t is a softfork. The aim is to find a t which is small-enough-to-prohibit-time-wrap-attack but also big-enough-to-avoid-split. With t=86400 (one day), a time-wrap attacker may bring down the difficulty by about 1/14 = 7.1% per round. Unless new blocks were coming incredibly slow, the attacker needs to manipulate the MTP for at least 24 hours, or try to rewrite 24 hours of history. Such scale of 51% attack is already above the 100-block coinbase maturity safety theshold and we are facing a much bigger problem. With t=86400, a non-majority, opportunistic attacker may split the chain only if we have no new block for at least 24 - 2 = 22 hours (2-hours is the protocol limit for using a future timestamp) at the exact moment of retarget. That means no retarget is possible in the next 2016 blocks. Doing a time-wrap attack at this point is not quite interesting as the coin is probably already worthless. Again, this is a much bigger problem than the potential chain spilt. People will yell for a difficulty (and time wrap fix, maybe) hardfork to resuscitate the chain. > On 21 Aug 2018, at 4:14 AM, Gregory Maxwell via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > > Since 2012 (IIRC) we've known that Bitcoin's non-overlapping > difficulty calculation was vulnerable to gaming with inaccurate > timestamps to massively increase the rate of block production beyond > the system's intentional design. It can be fixed with a soft-fork that > further constraints block timestamps, and a couple of proposals have > been floated along these lines. > > I put a demonstration of timewarp early in the testnet3 chain to also > let people test mitigations against that. It pegs the difficulty way > down and then churned out blocks at the maximum rate that the median > time protocol rule allows. > > I, and I assume others, haven't put a big priority into fixing this > vulnerability because it requires a majority hashrate and could easily > be blocked if someone started using it. > > But there haven't been too many other network consensus rules going on > right now, and I believe at least several of the proposals suggested > are fully compatible with existing behaviour and only trigger in the > presence of exceptional circumstances-- e.g. a timewarp attack. So > the risk of deploying these mitigations would be minimal. > > Before I dust off my old fix and perhaps prematurely cause fixation on > a particular approach, I thought it would be useful to ask the list if > anyone else was aware of a favourite backwards compatible timewarp fix > proposal they wanted to point out. > > Cheers. > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [bitcoin-dev] Getting around to fixing the timewarp attack. 2018-08-24 9:35 ` Johnson Lau @ 2018-08-30 20:55 ` Bram Cohen 0 siblings, 0 replies; 5+ messages in thread From: Bram Cohen @ 2018-08-30 20:55 UTC (permalink / raw) To: jl2012, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 5435 bytes --] This seems like a case where a distinction should be made between soft forks which are likely to cause non-upgraded miners to get orphaned and ones where they are. Of course in this case it's only 1/2016 of all blocks so it doesn't really matter, but it's worth thinking about the principle. In general soft forks are better when they don't cause orphaning on non-upgraded miners. The whole problem seems to be caused by the difference between the timestamps at the end of a period and the block right after it. Soft forking to force those to be 'close enough' together sounds like a solid approach. Given that blocks are generally send around fairly quickly, and that blocks more than two hours in the future are ignored, it seems reasonable to not allow a backwards jump of that plus some safety parameter. Let's say three hours. It also feels like a good idea to not allow a jump of more than three hours forwards either, just on principle. That should result in minimal code changes, and rarely any orphaning of non-upgraded miners at all, and still only 1/2016 blocks when they do. And no trace of a hard fork. It suffers from still allowing the attack a little bit, but three hours out of every two weeks seems like no big deal. On Sat, Aug 25, 2018 at 5:10 AM Johnson Lau via bitcoin-dev < bitcoin-dev@lists•linuxfoundation.org> wrote: > To determine the new difficulty, it is supposed to compare the timestamps > of block (2016n - 1) with block (2016n - 2017). However, an off-by-one bug > makes it compares with block (2016n - 2016) instead. > > A naive but perfect fix is to require every block (2016x) to have a > timestamp not smaller than that of its parent block. However, a chain-split > would happen even without any attack, unless super-majority of miners are > enforcing the new rules. This also involves mandatory upgrade of pool > software (cf. pool software upgrade is not mandatory for segwit). The best > way is to do it with something like BIP34, which also requires new pool > software. > > We could have a weaker version of this, to require the timestamp of block > (2016x) not smaller than its parent block by t-seconds, with 0 <= t <= > infinity. With a bigger t, the fix is less effective but also less likely > to cause intentional/unintentional split. Status quo is t = infinity. > > Reducing the value of t is a softfork. The aim is to find a t which is > small-enough-to-prohibit-time-wrap-attack but also > big-enough-to-avoid-split. With t=86400 (one day), a time-wrap attacker may > bring down the difficulty by about 1/14 = 7.1% per round. Unless new blocks > were coming incredibly slow, the attacker needs to manipulate the MTP for > at least 24 hours, or try to rewrite 24 hours of history. Such scale of 51% > attack is already above the 100-block coinbase maturity safety theshold and > we are facing a much bigger problem. > > With t=86400, a non-majority, opportunistic attacker may split the chain > only if we have no new block for at least 24 - 2 = 22 hours (2-hours is the > protocol limit for using a future timestamp) at the exact moment of > retarget. That means no retarget is possible in the next 2016 blocks. Doing > a time-wrap attack at this point is not quite interesting as the coin is > probably already worthless. Again, this is a much bigger problem than the > potential chain spilt. People will yell for a difficulty (and time wrap > fix, maybe) hardfork to resuscitate the chain. > > > > > > On 21 Aug 2018, at 4:14 AM, Gregory Maxwell via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation.org> wrote: > > > > Since 2012 (IIRC) we've known that Bitcoin's non-overlapping > > difficulty calculation was vulnerable to gaming with inaccurate > > timestamps to massively increase the rate of block production beyond > > the system's intentional design. It can be fixed with a soft-fork that > > further constraints block timestamps, and a couple of proposals have > > been floated along these lines. > > > > I put a demonstration of timewarp early in the testnet3 chain to also > > let people test mitigations against that. It pegs the difficulty way > > down and then churned out blocks at the maximum rate that the median > > time protocol rule allows. > > > > I, and I assume others, haven't put a big priority into fixing this > > vulnerability because it requires a majority hashrate and could easily > > be blocked if someone started using it. > > > > But there haven't been too many other network consensus rules going on > > right now, and I believe at least several of the proposals suggested > > are fully compatible with existing behaviour and only trigger in the > > presence of exceptional circumstances-- e.g. a timewarp attack. So > > the risk of deploying these mitigations would be minimal. > > > > Before I dust off my old fix and perhaps prematurely cause fixation on > > a particular approach, I thought it would be useful to ask the list if > > anyone else was aware of a favourite backwards compatible timewarp fix > > proposal they wanted to point out. > > > > Cheers. > > _______________________________________________ > > bitcoin-dev mailing list > > bitcoin-dev@lists•linuxfoundation.org > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > [-- Attachment #2: Type: text/html, Size: 6473 bytes --] ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [bitcoin-dev] Getting around to fixing the timewarp attack. @ 2018-08-29 9:54 Zawy 0 siblings, 0 replies; 5+ messages in thread From: Zawy @ 2018-08-29 9:54 UTC (permalink / raw) To: bitcoin-dev Rather than restricting every timestamp (or just the 2016*N+1 timestamps) to >= 1+ the previous timestamp as recorded on the blockchain, the difficulty calculation could have the same restriction but only in how the timestamps are used. I don't know about backwards compatibility. Either way, this would also prevent the powLimit attack that is also capable of getting "unlimited" blocks in less than 4 weeks of > 50% selfish mining. LTC, BCH, and LTC fixed to the "Zeitgeist" or "timewarp" attack on GeistGeld in 2011 described by Artforz in different ways, but all are still vulnerable by the powLimit attack that I described here: https://github.com/zawy12/difficulty-algorithms/issues/30 Other solutions may not prevent this other attack. ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2018-08-30 20:55 UTC | newest] Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2018-08-20 20:14 [bitcoin-dev] Getting around to fixing the timewarp attack Gregory Maxwell 2018-08-22 13:48 ` Jorge Timón 2018-08-24 9:35 ` Johnson Lau 2018-08-30 20:55 ` Bram Cohen 2018-08-29 9:54 Zawy
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox