Bitcoin Forum
October 31, 2024, 11:09:28 PM *
News: Latest Bitcoin Core release: 28.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Blocking the time warp attack  (Read 3735 times)
jevon (OP)
Newbie
*
Offline Offline

Activity: 36
Merit: 0


View Profile
October 01, 2012, 09:52:51 PM
Last edit: October 02, 2012, 04:52:52 PM by jevon
 #1

ArtForz posted here how the timestamp constraints can be gamed to walk backwards the timestamps used in difficulty adjustments.

While a 51% attack is still incredibly difficult, this bug greatly increases the potential damage if there is one.

In bitcoin.pdf, a 51% attack was supposed to be at least somewhat limited:
Quote
"Even if this is accomplished, it does not throw the system open to arbitrary changes, such as creating value out of thin air... An attacker can only try to change one of his own transactions to take back money he recently spent."

With the time warp bug, a 51% attacker can create value out of thin air by lowering the difficulty to 1 and generating the remaining 11 million BTC of block rewards for himself. Time warp keeps rewinding time to fit unlimited blocks before the current time. (I think ArtForz actually demonstrated the attack on one of the altcoins)

Since time warp chains are so distinctively different from anything the real network would ever generate, it should be possible to come up with a way to block them without causing compatibility problems.

Rule Idea #2:

Rule: A block is invalid if timestamp is more than 24 hours after GetMedianTimePast()

This limits the divergence between GetMedianTimePast() and single timestamps that the time warp takes advantage of. The time warp depends on making single timestamps far in the future and jumping back to the old time before the median is affected.

It would really only need to apply to the two blocks involved in difficulty adjustment calculations. (only 2 out of 2016 blocks)

It's hard to imagine there ever being a 24 hour gap in practice, but just in case, miners should cap timestamp at GetMedianTimePast() + 24 hours. (this part wouldn't require universal miner support, just enough to push through 2 blocks)
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
October 02, 2012, 01:29:33 AM
 #2

ArtForz posted here how the timestamp constraints can be gamed to walk backwards the timestamps used in difficulty adjustments.

While a 51% attack is still incredibly difficult, this bug greatly increases the potential damage if there is one.

It doesn't just require a simple majority, the chain must also be forked more than two weeks in the past (and at just over two weeks in the past it would take a long time to push the difficulty down), then must catchup and overtake in sum difficulty.  This is _much_ harder than just a majority. With only a 1% advantage you'd be toiling for a very long time in secret to overtake after cutting month back.

Quote
Rule: A block is invalid if its timestamp is less than the timestamps of either of the blocks 2015 and 2016 back.

I don't think that rule is sufficient.  You can tick the clock just 1 second per 5 blocks without advancing forward the oldest permitted time.


 I put a timewarp attack in the testnet3 chain to make it easier to test out rules to deal with it, so you might enjoy playing with that.
jevon (OP)
Newbie
*
Offline Offline

Activity: 36
Merit: 0


View Profile
October 02, 2012, 04:51:46 PM
 #3

It doesn't just require a simple majority, the chain must also be forked more than two weeks in the past (and at just over two weeks in the past it would take a long time to push the difficulty down), then must catchup and overtake in sum difficulty.  This is _much_ harder than just a majority. With only a 1% advantage you'd be toiling for a very long time in secret to overtake after cutting month back.
We shouldn't rely too much on it being harder. The minimum 51% attack currently requires 22Thash. Time warp might require 44Thash to pull off. Someone having 22Thash is unlikely, but 44Thash isn't much less likely than 22Thash. Someone with the ability to get 22Thash could probably get 44Thash too.

The chaos from a time warp attack could be an order of magnitude greater. Much more than the additional difficulty of pulling it off.

Imagine if a time warp attacker divided up 10 million bogus BTC and sent it to every public bitcoin address in the chain. Many businesses would automatically take actions on receiving a confirmed payment, like initiating transfers of their own good BTC or fiat currency. Any bogus BTC circulating would mix with good BTC. All transactions based on mixed money would have to be rewound, but clean transactions would have to stay valid. If someone deposited a mixed transaction and withdrew a clean one, or vice versa, one side is out the money. Also, it would be a terrible mess to clean up all the screwed up wallets that think their coins are spent.

Quote
I don't think that rule is sufficient.  You can tick the clock just 1 second per 5 blocks without advancing forward the oldest permitted time.
I updated the OP to a more obvious idea #2.
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
October 03, 2012, 11:57:08 AM
 #4

It's hard to imagine there ever being a 24 hour gap in practice, but just in case, miners should cap timestamp at GetMedianTimePast() + 24 hours. (this part wouldn't require universal miner support, just enough to push through 2 blocks)
I haven't considered if your newly proposed rule is sufficient yet or if it's otherwise dangerous.  But it's deployment would be a fork risk unless it had super-majority miner support. Otherwise an attacker could intentionally split the network.

Two ways:
(1) If there is an unlikely moderately long gap between the median and now (5 blocks in 24 hours) he can just directly mine one block with a violating timestamp.
(2) Since you're already postulating majority hashpower attackers, one could replace the end of the chain with a violating chunk.

Quote
We shouldn't rely too much on it being harder. The minimum 51% attack currently requires 22Thash. Time warp might require 44Thash to pull off. Someone having 22Thash is unlikely, but 44Thash isn't much less likely than 22Thash. Someone with the ability to get 22Thash could probably get 44Thash too.

The chaos from a time warp attack could be an order of magnitude greater. Much more than the additional difficulty of pulling it off.
I wasn't saying that it isn't a concern, I was just cautioning against overstating it.  I'm not sure about the "order of magnitude worse" part— at the very start it's going to undo four weeks of transactions. That there is also a bunch of new coin created just increases the incentive to for the collective users of bitcoin to voluntarily kill the fork by checkpointing against it at its start point four weeks ago.

Getting a conservative rule in that kills these but which has hopefully never been violated by the mainnet would still be a good idea.  If nothing else the timewarp complicates explaining the security model of Bitcoin.  ("…such an attack can only do X/Y, except for this bug, also allowing Z but doing that is much harder than a simple overpowering…")

jevon (OP)
Newbie
*
Offline Offline

Activity: 36
Merit: 0


View Profile
October 03, 2012, 09:09:33 PM
 #5

I haven't considered if your newly proposed rule is sufficient yet or if it's otherwise dangerous.  But it's deployment would be a fork risk unless it had super-majority miner support. Otherwise an attacker could intentionally split the network.

Two ways:
(1) If there is an unlikely moderately long gap between the median and now (5 blocks in 24 hours) he can just directly mine one block with a violating timestamp.
(2) Since you're already postulating majority hashpower attackers, one could replace the end of the chain with a violating chunk.
Those are valid concerns during phase-in before a majority of miners have the rule, but the usual procedure of making it enable at some future time or block number would cover that.
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!