Difficulty adjustment / time issues
19 messages, 13 Sep to 7 Nov 2011. Started by Gavin Andresen.
Luke Dashjr (4), Gavin Andresen (3), Greg Maxwell (2), theymos (2), Pieter Wuille (2), Vladimir Marchenko, John Smith, Kyle Jerviss, +3 more
Background:
Timejacking: http://culubas.blogspot.com/2011/05/timejacking-bitcoin_802.html
And a recent related exploit launched against the low-difficulty alternative chains: https://bitcointalk.org/index.php?topic=43692.msg521772#msg521772
Seems to me there are two fundamental problems:
1) Bitcoin should be overlapping the ranges of block timestamps that it uses to calculate difficulty adjustments.
2) Bitcoin's "what time is it" code is kind of a hack.
Fixing (1) would mean a potential block-chain split; before considering doing that I'd like to consider second-best solutions.
Fixing (2) is easier; incorporating a ntp library and/or simply removing the bitcoin mining code from the client but requiring pools and miners to have accurate-to-within-a-minute system clocks (or their blocks will be "discouraged") seems reasonable to me. If you want to produce blocks that the rest of the network will accept, run ntp on your system.
I THINK that fixing (2) will make (1) a non-issue-- if miners can't mess around with block times very much then it will be very difficult for them to manipulate the difficulty for their benefit.
Quoted text (1 line)
> 2) Bitcoin's "what time is it" code is kind of a hack.
...
Quoted text (6 lines)
> Fixing (2) is easier; incorporating a ntp library and/or simply > removing the bitcoin mining code from the client but requiring pools > and miners to have accurate-to-within-a-minute system clocks (or their > blocks will be "discouraged") seems reasonable to me. If you want to > produce blocks that the rest of the network will accept, run ntp on > your system.
...
Quoted text (3 lines)
> -- > Gavin Andresen >
As a miner I fully support route (2) and do not think that this would cause any serious issues or discontent among miners. Most miners surely are running ntpd already. Those who mess with the clock intentionally will have to play ball.
Quoted text (4 lines)
> Fixing (2) is easier; incorporating a ntp library and/or simply > removing the bitcoin mining code from the client but requiring pools > and miners to have accurate-to-within-a-minute system clocks (or their > blocks will be "discouraged") seems reasonable to me.
Incorporating NTP seems overkill. Most OSes come with NTP support integrated these days (even XP did?), there is no excuse to not be running it, especially on a server.
If you want to
Quoted text (3 lines)
> produce blocks that the rest of the network will accept, run ntp on > your system. >
Requiring it for miners sounds very reasonable.
JS
Gavin Andresen wrote:
Quoted text (32 lines)
> Background: > > Timejacking: > http://culubas.blogspot.com/2011/05/timejacking-bitcoin_802.html > > And a recent related exploit launched against the low-difficulty > alternative chains: > https://bitcointalk.org/index.php?topic=43692.msg521772#msg521772 > > > Seems to me there are two fundamental problems: > > 1) Bitcoin should be overlapping the ranges of block timestamps that > it uses to calculate difficulty adjustments. > > 2) Bitcoin's "what time is it" code is kind of a hack. > > > Fixing (1) would mean a potential block-chain split; before > considering doing that I'd like to consider second-best solutions. > > Fixing (2) is easier; incorporating a ntp library and/or simply > removing the bitcoin mining code from the client but requiring pools > and miners to have accurate-to-within-a-minute system clocks (or their > blocks will be "discouraged") seems reasonable to me. If you want to > produce blocks that the rest of the network will accept, run ntp on > your system. > > I THINK that fixing (2) will make (1) a non-issue-- if miners can't > mess around with block times very much then it will be very difficult > for them to manipulate the difficulty for their benefit. >
The first thing I always do when I grab the source for my colo server is patch util.cpp so that GetAdjustedTime() returns GetTime() with no adjustment. But I'm the kind of guy that buys special GPS receivers because stratum 2 isn't low enough and occasionally checks ebay for caesium fountains.
NTP has been around for long enough now that there is no reason for the client to screw with the clock. If the client sees different times on the network, it should issue a warning, and if it is off too far, it should give an error and fail to run (and/or peers should reject it).
But that doesn't solve the whole problem, because the block timestamp checking is based on the assumption that the node is looking at the bitcoin clock rather than the, ahem, real clock. If we change the idea of network time to NTP, we will then need to write (and test!) new block timestamp rules to account for the new assumptions.
I'm not sure that just fixing item 2 is going to stop the attacks found by ArtForz, et al. Some of the attacks Art pointed out are particularly bad because they change the incentive structure of the system, at least in the short term. We need to flip that back around ASAP.
Also, this is going to cause problems for at least one pool operator.
On Tuesday, September 13, 2011 11:06:37 AM Gavin Andresen wrote:
Quoted text (6 lines)
> Fixing (2) is easier; incorporating a ntp library and/or simply > removing the bitcoin mining code from the client but requiring pools > and miners to have accurate-to-within-a-minute system clocks (or their > blocks will be "discouraged") seems reasonable to me. If you want to > produce blocks that the rest of the network will accept, run ntp on > your system.
This is not currently reasonable. Rolling extranonce is not efficient, and using it to generate work for 400+ GH/s worth of miners every new block (longpoll) can easily take seconds. Noncerange helps a little, but has poor support presently, and still requires an otherwise-unique work per 4 GH/s. That only leaves pools with the time header to play with. Furthermore, within- a-minute accuracy basically forces all miners to rollntime-- I'm not against this result, but it does mean many miners and pools will be left out in the cold.
Quoted text (3 lines)
> I THINK that fixing (2) will make (1) a non-issue-- if miners can't > mess around with block times very much then it will be very difficult > for them to manipulate the difficulty for their benefit.
Miners already have very limited area to mess around with block times. My understanding of these attacks is that they somehow bypass the limitations in place.
Quoted text (5 lines)
> But that doesn't solve the whole problem, because the block timestamp > checking is based on the assumption that the node is looking at the bitcoin > clock rather than the, ahem, real clock. If we change the idea of network > time to NTP, we will then need to write (and test!) new block timestamp > rules to account for the new assumptions.
Why?
The block timestamp rules currently give HOURS of wiggle-room for timestamps. We can't change those rules without risking a chain split.
Here's a thumbnail sketch of what I'm thinking:
When new tip-of-chain blocks are received, IF their timestamp is unreasonable with respect to system time and the previous block's timestamp, then add them to a 'discouraged' list. (but follow the current rules for outright rejecting blocks based on timestamps too far in the future or past)
Modify the getwork code to build on the second-from-tip block if the first-on-tip block is on the discouraged list.
Assuming a majority of pools/miners adopt the "discourage blocks with stale timestamps" rule, that should squash any incentive for cartels to try to start playing with difficulty-- you would have to have 50+% power to start, or you risk producing mostly orphan blocks.
Quoted text (1 line)
> Also, this is going to cause problems for at least one pool operator.
I'll trade more security for "make at least one pool operator have to do some work" any day.
On Wednesday, September 14, 2011 10:45:36 AM Gavin Andresen wrote:
Quoted text (2 lines)
> The block timestamp rules currently give HOURS of wiggle-room for > timestamps. We can't change those rules without risking a chain split.
And those hours of wiggle-room are not enough to cause a problem. The problem only comes in (AFAIK) when the existing rules are *not* enforced.
Quoted text (4 lines)
> Assuming a majority of pools/miners adopt the "discourage blocks with > stale timestamps" rule, that should squash any incentive for cartels > to try to start playing with difficulty-- you would have to have 50+% > power to start, or you risk producing mostly orphan blocks.
As this is against pools/miners' interests, and doesn't seem to solve any real problems, I'm going to discourage its adoption if it ever gets done.
Am I the only one to think putting pools at a disadvantage is actually desirable? Back when pools started to appear we all had huge reservations about putting so much control into the hands of a few pool operators, but nowadays it seems that having pool operators control a vast majority of the computational power is desired. I do like pools (I use them myself), but we should put the security of the protocol in first place and then only think about individual players. Always remember that the problems pool operators encounter are likely also the ones of a potential attacker that tries to accumulate 50%+ of the network power :-)
Regards, Chris On Wed, Sep 14, 2011 at 5:43 PM, Luke-Jr <luke@dashjr•org> wrote:
Quoted text (29 lines)
> On Wednesday, September 14, 2011 10:45:36 AM Gavin Andresen wrote: > > The block timestamp rules currently give HOURS of wiggle-room for > > timestamps. We can't change those rules without risking a chain split. > > And those hours of wiggle-room are not enough to cause a problem. > The problem only comes in (AFAIK) when the existing rules are *not* > enforced. > > > Assuming a majority of pools/miners adopt the "discourage blocks with > > stale timestamps" rule, that should squash any incentive for cartels > > to try to start playing with difficulty-- you would have to have 50+% > > power to start, or you risk producing mostly orphan blocks. > > As this is against pools/miners' interests, and doesn't seem to solve any > real > problems, I'm going to discourage its adoption if it ever gets done. > > > ------------------------------------------------------------------------------ > BlackBerry® DevCon Americas, Oct. 18-20, San Francisco, CA > Learn about the latest advances in developing for the > BlackBerry® mobile platform with sessions, labs & more. > See new tools and technologies. Register for BlackBerry® DevCon today! > http://p.sf.net/sfu/rim-devcon-copy1 > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge•net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development >
On Wed, Sep 14, 2011 at 3:45 PM, Gavin Andresen <gavinandresen@gmail•com> wrote:
Quoted text (7 lines)
> Modify the getwork code to build on the second-from-tip block if the > first-on-tip block is on the discouraged list. > > Assuming a majority of pools/miners adopt the "discourage blocks with > stale timestamps" rule, that should squash any incentive for cartels > to try to start playing with difficulty-- you would have to have 50+% > power to start, or you risk producing mostly orphan blocks.
Of course, if only a small percentage of mining power adopts this scheme, everyone that does so will presumably be harming themselves by doing so since they're essentially increasing the odds that the next block they mine will become invalid...
On Wed, Sep 14, 2011 at 3:52 PM, Aidan Thornton <makosoft@gmail•com> wrote:
Quoted text (4 lines)
> Of course, if only a small percentage of mining power adopts this > scheme, everyone that does so will presumably be harming themselves by > doing so since they're essentially increasing the odds that the next > block they mine will become invalid...
Perhaps better thing to do is to also delay the _forwarding_ of these blocks _and_ blocks that extend them, until extended one more time.
This policy, if adopted by the forwarding nodes (who really shouldn't care for much other than the overall health of bitcoins) puts miners at risk if they don't run the augmented extension policy.
Though I generally agree with Luke that we should just fix the root cause even though it forks the chain. Not for his reasons (I don't give a crap about the burden on _one_ pool operator— the rest cope with bitcoind scaling fine without excessive dependance on ntime rolling), but simply because not fixing it makes the bitcoin security model harder to explain and analyze.
"Here is a vulnerability, but its offset by this workaround" is inferior to "the system is secure against this kind of attack".
Quoted text (2 lines)
> Perhaps better thing to do is to also delay the _forwarding_ of these > blocks _and_ blocks that extend them, until extended one more time.
Excellent idea, that gets the incentives right.
RE: fixing the root cause with a forking change:
What do other people think? I think it is too high risk for too little benefit and shouldn't be done until we have a really compelling reason to introduce a forking change.
The first really compelling reason I can think of is removing the MAX_BLOCK_SIZE limit (but does something clever to prevent the rogue-miner-sends-you-a-valid-10Terabyte-block attack).
On Wed, Sep 14, 2011 at 4:28 PM, Gavin Andresen <gavinandresen@gmail•com> wrote:
Quoted text (3 lines)
> What do other people think? I think it is too high risk for too > little benefit and shouldn't be done until we have a really compelling > reason to introduce a forking change.
Could we bundle this and potential future blockchain-splitting changes - to implement them in a major release (down the road)? Or save them for when they are very necessary?
TL;DR shelf it until needed, have it written just in case.
-Alex
A better retarget strategy might be to use the real average time between all of the blocks in the interval so that no blocks are treated specially in the calculation. I agree that this is not important enough to fork the chain over, though. An attacker would have to maintain control for a *very* long time because of Bitcoin's long retarget interval. (Maybe this kind of thing is why the retarget interval is so long?)
I don't like requiring block times to be within minutes of reality. It would be fine if only miners had to keep accurate time, but clients will also need to have good time in order to see if a block will be discouraged. A discouraged block should not count toward confirmations. If relays will also discourage blocks, then they'll need accurate time as well.
The network should not be allowed to adjust your time by more than 40 minutes to prevent the timejacking attack, but I don't see a problem with the other time rules. Time is only used for retargets and LockTime, so it only needs to be generally accurate.
On Wed, Sep 14, 2011 at 5:36 PM, Alex Waters <ampedal@gmail•com> wrote:
Quoted text (11 lines)
> On Wed, Sep 14, 2011 at 4:28 PM, Gavin Andresen <gavinandresen@gmail•com> wrote: > >> What do other people think? I think it is too high risk for too >> little benefit and shouldn't be done until we have a really compelling >> reason to introduce a forking change. > > Could we bundle this and potential future blockchain-splitting changes > - to implement them in a major release (down the road)? Or save them > for when they are very necessary? > > TL;DR shelf it until needed, have it written just in case.
I'm generally opposed to doing "too much" at once in this kind of change.
Some changes, like this one, are completely uncontroversial (except some argument about having fork causing change at all) where some have more complicated social/economic impacts (the block size being among them, though probably not the worst).
Moreover, the longer we go between such changes the more the cost is perceived to be infinite. Better to take one per year, with six months of gap between implementation, and give everyone the right expectations than to have prolonged arguments due to our inexperience that only get trumped by emergency changes.
General network health and user security _requires_ periodic upgrades in any case, and will for the foreseeable future. The whole notion that old versions will _stop working_ would be a pretty good thing at this point in bitcoin's existence, judging by the high number of pre-.24 listeners still reported.
On Wednesday, September 14, 2011 5:51 PM, "Gregory Maxwell" <gmaxwell@gmail•com> wrote:
Quoted text (5 lines)
> General network health and user security _requires_ periodic upgrades > in any case, and will for the foreseeable future. The whole notion > that old versions will _stop working_ would be a pretty good thing at > this point in bitcoin's existence, judging by the high number of pre- > .24 listeners still reported.
Backward-compatibility is valuable. I believe version 0.1 will still more or less work on the current network. This is a real selling point for Bitcoin: the code is solid enough that even 2-year-old clients are still working.
On Wednesday, September 14, 2011 4:09:00 PM Gregory Maxwell wrote:
Quoted text (2 lines)
> Though I generally agree with Luke that we should just fix the root > cause even though it forks the chain.
I don't support this, unless all other chain-forking-needed changes are made at the same time. I do point out that changing the time rules *does not help*.
Quoted text (3 lines)
> Not for his reasons (I don't give a crap about the burden on _one_ pool > operator— the rest cope with bitcoind scaling fine without excessive > dependance on ntime rolling),
The rest don't generate rewards immediately as the same block being mined. They either eat the loss of invalid blocks, or wait for 100+ confirmations before paying. Also, restricting the time rules basically breaks miners without rollntime support (such as Phoenix).
On Tue, Sep 13, 2011 at 11:06:37AM -0400, Gavin Andresen wrote:
Quoted text (8 lines)
> Background: > > Timejacking: > http://culubas.blogspot.com/2011/05/timejacking-bitcoin_802.html > > And a recent related exploit launched against the low-difficulty > alternative chains: > https://bitcointalk.org/index.php?topic=43692.msg521772#msg521772
Here is an idea for an alternative (simple but hacky) solution: * Keep all network rules as they are now. * The timestamp value of mutliple-of-2016-blocks is set equal to the highest timestamp that occurred in the previous 11 blocks, instead of the current time. This will always obey the previous rules (it's always at least the median of the past 11 blocks, and never more in the future than them).
Initially, roll out software that only uses this new rule for block creation, but doesn't enforce it. When enough miners have upgraded, choose a point in the future where it becomes mandatory (causing a block chain split only for those creating blocks using old software).
If i understand the problem correctly, this will prevent an attacker from introducing a time lapse in between the 2015-block windows. One problem i do see, is that it prevents X-Roll-Time for miners. Maybe a short interval (1 minute? 10 minutes?) instead of a fixed value could be allowed for the multiple-of-2016 blocks.
Comments?
On Monday, November 07, 2011 10:02:43 AM Pieter Wuille wrote:
Quoted text (2 lines)
> Maybe a short interval (1 minute? 10 minutes?) instead of a fixed > value could be allowed for the multiple-of-2016 blocks.
Reminder that there is *already* a short interval only allowed for blocks in general...
On Mon, Nov 07, 2011 at 10:27:57AM -0500, Luke-Jr wrote:
Quoted text (6 lines)
> On Monday, November 07, 2011 10:02:43 AM Pieter Wuille wrote: > > Maybe a short interval (1 minute? 10 minutes?) instead of a fixed > > value could be allowed for the multiple-of-2016 blocks. > > Reminder that there is *already* a short interval only allowed for blocks in > general...
In chains where no timejacking attack is going on, yes. In the common case the timestamp is limited to a range of [5 blocks in the past ... 2 hours in the future].
However, during a timejacking attack, the timestamps of multiple-of-2016 blocks are essentially independent from the others. In such a case, most timestamps are very low, and only those of multiple-of-2016-blocks correspond to the current time. Each 2016*N-1 to 2016*N transition incurs an arbitrary large forward shift to the present time, each 2016*N to 2016*N+1 transition does a time shift backwards again that is allowed because the median allows single outliers. By fixing the timestamp occasionally more tightly to the maximum, instead of the median, no such time lapses are possible.
Updated proposed rule: limit the timestamp of multiple-of-2016-blocks to [max(past 11 timestamps)+1 ... current_time+7200], essentially just using a maximum instead of a median. I believe that is enough to prevent the attack.