The Global Time Agreement Puzzle
Bitcoin is an ingeniously-designed digital currency system with revolutionary potential. This post discusses a purely theoretical vulnerability in bitcoin's de-facto timestamp handling.
By announcing inaccurate timestamps when connecting to a node, an attacker can alter a node's network time counter and deceive it into accepting an alternate block chain. This could significantly increase the chances of a successful double-spend, drain a node's computational resources, or simply slow down the transaction confirmation rate.
Unlike other attacks, this would still be possible even when all nodes maintain communication with honest peers. A limited timestamp-based disruption is also possible against nodes that use NTP and maintain synchronized clocks.
This can be addressed by determining acceptable timestamp ranges solely based on previous block timestamps. Additional measures include narrowing acceptable time ranges, using the system time rather than estimated network time, and blocking untrusted peers.
Bitcoin Basics
Some background on how bitcoin works: Bitcoin transactions are stored in a globally-readable block chain. Each individual block contains a list of transactions, a proof of work (a partial hash collision that depends in part on the preceding block), a timestamp representing the approximate time the block was created, and some additional information. (See a complete block here.)
A block reward is generated with each new block until the pre-defined limit of 21 million bitcoins is reached. Each new block represents a confirmation of previously stored transactions, making it increasingly harder to revert those transactions. Approximately 126,500 blocks have been created to date with a value of $46 million at current rates.
The block timestamps allow the system to regulate the production of bitcoins. The required difficulty level for the proof of work is automatically adjusted based on the amount of time it took to create previous blocks, with the goal of producing 1 block every 10 minutes and thus maintaining a stable expansion rate.
Timestamp Hacking
Each node internally maintains a counter that represents the network time. This is based on the median time of a node's peers which is sent in the version message when peers connect. The network time counter reverts to the system time however if the median time differs by more than 70 minutes from the system time.
An attacker could potentially slow down or speed up a node's network time counter by connecting as multiple peers and reporting inaccurate timestamps. For instance, a relatively small number of Tor clients could send enough messages to take over the node's median time.
An advanced attack would involve speeding up the clocks of a majority of the network's mining resources while slowing down the target's clock. Since the time value can be skewed by at most 70 minutes, the difference between the nodes would be 140 minutes.
Creating a "Poison Pill" Block
The network time is used to validate new blocks. As a precaution, nodes reject any block timestamp that is greater than 2 hours from the current network time. Block timestamps that are earlier than the median time of the past 11 blocks are also rejected. This validation puts upper and lower bounds on the acceptable range of block timestamps.
The attacker would then create a new block with a timestamp set 190 minutes ahead of the real time. (The amount of time required to generate a block would depend on the attacker's share of the network's total power, but it could be done 10 times a week on average by someone with a relatively small 1% share.)
The target node would reject this new block (because the timestamp is 260 minutes past its own slowed-down network time) and continue using the previous chain. However the miners would accept the block (because it's no more than 120 minutes past their own sped-up network time).
The target would now be isolated from the network's normal transaction processing. As network processing continues, each new block created by the miners would appear to be invalid (because it would bear a timestamp 140 minutes past the target's network time). The target would immediately drop invalid blocks (in CheckBlock()) without bothering to request and re-check the blocks' ancestors. The attack could continue indefinitely until either an unaffected node or the target itself creates a block, clocks are reset, or operators intervene.
Double-Spending
The target wouldn't receive legitimate transaction confirmations during the attack window. This would be a period of time during which an attacker could feed confirmations to the target without honest nodes intervening. The attacker knows that those confirmations will be reverted later by the global chain. As long as poisoned blocks continue to be generated, the attacker can continue sending confirmations on the stale chain that the target is using.
An attacker with 10% of the network power would be able to send 6 confirmations in 5 and a half hours with a success rate of over 10%. After 6 confirmations, the standard bitcoin interface changes a transaction's status to confirmed. With 3.3 hours, the attacker would have a greater than 1% success rate. A low probability attack could be attempted automatically many times in order to yield a success.
Once the network stabilizes, the global chain would take precedence and the ephemeral confirmations that the attacker sent to the target would be reverted.
A timestamp attack wouldn't require displacing all of a node's honest peers with malicious nodes (as in some other Sybil-style attack variants).
Restricted Time Window
Even if during the attack a non-poisoned block gets created, the attack window would still be at least 140 minutes. An attacker with 10% of the network's power would be able to issue 6 confirmations during that time with a success rate of 0.147% (a 6-fold increase over the 0.024% chance of reverting 6 confirmations in a standard double-spend attack). The attacker could still add another poisoned block on his own to reset the attack window back to 0 and continue generating confirmations, giving him another edge.
In the case where only the target's network time counter was altered (and the rest of the network's resources were untouched), there would be at least 70 minutes during which the target would be isolated without having honest nodes intervene. The target would be working on a stale chain while the main network moves on.
Effect on Miners
If the attack target is a miner, then its mining power would be drastically reduced because it would be working on a stale chain while the network has moved on to another block. A rogue miner could do this repeatedly to its competitors to increase its share of the network.
Such an attack could theoretically work even if the target's network time only differed by a second from the majority of the network's resources. The target would see that the new block was 1 second beyond the 2 hour threshold and reject it, continuing to work on a stale block. (Similary a node with a clock running 1 second fast relative to the true network time could be presented with a timestamp that most would reject as invalid.) This would cause a network split without disrupting network traffic. In practice, network latency would need to be added to the time difference. Some miners use custom clients that simply don't use their peers' time at all. This can mitigate some issues, but doesn't prevent timestamp splits.
More Elaborate Scenario
In an elaborate heist scenario worthy of Ocean's 11, an attacker could attempt to take the target node offline (by a network DoS, power outage, or some other means) for as much time as would be needed to generate enough confirmations on the alternate chain along with a new block on the global chain with the usual 2 hour timestamp. The new block would be posted to the global chain just before bringing the target back online (ensuring the target will reject the global chain even after re-connecting to an honest peer) and the remaining confirmations would be sent, completing the transaction and providing a generous window of time in which to get away before the target becomes aware of the global chain.
Solutions
Use the node's system time instead of the network time to determine the upper limit of block timestamps and when creating blocks.
A common approach to maintaining the time is NTP, however assuming a dependency on NTP could introduce centralized or concentrated points of failure and a potential reliance on trusted time servers. (Note, see also http://www.cs.bu.edu/~goldbe/NTPattack.html.) Using a hardware time source rather than a network time source would require additional calibration and maintenance. Even with reasonably good timekeeping, a disagreement among nodes of only a second or slightly longer (something that will happen as nodes gradually calibrate their clocks) could allow an attacker to split the network or isolate a node.
Tighten the acceptable time ranges.
The node's network time could be restricted to a value within 30 minutes. This changes the maximum initial attack window to between 30 and 60 minutes instead of 70 and 140, but would not prevent splits entirely. Nodes with incorrect daylight savings handling might be left behind though.
Use only trusted peers.
Requiring secure nodes to use only trusted peers could make those nodes less secure since a small number of trusted peers may be subverted. A fully decentralized system doesn't require placing trust in a select group of peers. Requiring operators to maintain their own networks or have geographically distributed servers would also be additional maintenance and syncing issues. Using trusted peers or your own distributed network wouldn't by itself resolve the global time agreement problem.
Monitor network health and shutdown if there's suspicious activity.
Definitely a good thing, but wouldn't resolve conflicts automatically.
Require more confirmations before accepting a transaction.
Great, but there should be a balance between expediency and the probability of reversal. A significant financial attack could still be successful if other miners have their clocks moved forward or if the target is taken offline, even when the required number of confirmations is increased.
Use the median block chain time exclusively when validating blocks.
This would ensure no timestamp splits are possible and would be a complete solution. This is already done on the timestamp's lower bound and could be applied similarly to the upper bound. For instance, the client could ensure that block creation times couldn't grow faster than a certain rate.
If the maximum growth factor were say 1.5 and the median block creation time was 10 minutes, the next creation time would be restricted to 15 minutes or less. In the case of an actual network slow down, the median time would adjust soon enough because it grows exponentially (15, 22.5, 33.75, 50.63, etc.).
This would mean it might take slightly longer for the network to adjust to drops in computing power, but the adjustment would still take place within a reasonable amount of time. Individual timestamps might not reflect a block's precise creation time, but that isn't required - the median creation time within a difficulty segment would still be reliable enough for the purposes of moderating difficult levels.
Assuming honest nodes maintain enough computing power (the fundamental requirement of the decentralized system) and continue using accurate timestamps, it would be difficult to artificially accelerate the chain's timestamps for a sustained period of time and no timestamp-based splits would be possible.
This would ensure that no two peers could disagree on whether a block was valid or not since they are no longer using their own variable time clocks but are using the timestamps embedded in the chain itself.
What about miner incentives?
The median time approach, while technically sound and consistent to all nodes, could give honest miners a financial incentive to defect by posting inflated timestamps and keeping the difficulty level artificially low. Since each block adds 50 bitcoins to the creator's account, a low difficulty setting would allow miners to generate more block bounties in less time. Transactions would be processed more quickly than usual, but confirmations would be less reliable (because they represent less computational work). Such activity could reduce confidence in bitcoin (one reason why miners might not defect).
One way to moderate this is would be by introducing a simple voting mechanism where bitcoin account holders would periodically submit their desired inflation or deflation rate through a cryptographically secure vote stored in the block chain (which could later be purged to save space).
This would in effect create a decentralized central bank, where currency holders decide somewhat democratically on their desired level of expansion. The currency wouldn't be deflationary or inflationary in principle, since prevailing market conditions and the community's own aggregate economic interests would determine supply.
If miners held a majority of currency in reserve, they would still dominate any voting system, but they would need to take the minority view into account, since minority users could switch to alternative currencies and the market would shrink.
Use delayed timestamp validation.
Nodes can retain blocks with excessive timestamps in memory and re-check them later (possibly by setting an alarm). At most a certain number of blocks would be retained in a queue sorted by timestamp and descending difficulty. Nodes would then rejoin the main chain as soon as their system clocks catch up. This has the advantage that significant block timestamp inflation isn't possible, but it's more complex, and timestamp-based splits would still be possible. The delay required to synchronize however would be minimized compared to an approach that only relied on the system time.
The bitcoin client is an amazing system and is already incredibly robust. Network health and timestamp validation bring up external issues that systems and routers connected to the global net will assess. Bitcoin is a welcome alternative for many individuals and businesses and I expect its user base to continue growing at a rapid pace.
Feel free to share some bitcoins at 19k9vzFZJ4tJsJ4RaSMMfLfMneN2VZkzXB :)
