[Bitcoin-development] Difficulty adjustment / time issues

[Bitcoin-development] Difficulty adjustment / time issues

[Gavin Andresen]

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.

-- 
--
Gavin Andresen

Re: [Bitcoin-development] Difficulty adjustment / time issues

[Vladimir Marchenko]

> 2) Bitcoin's "what time is it" code is kind of a hack.
...
> 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.
...
> --
> 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.

--
Vladimir
-
http://bitcoin.org.uk/forums - clean and moderated bitcoin forum

Re: [Bitcoin-development] Difficulty adjustment / time issues

[John Smith]

[-- Attachment #1: Type: text/plain, Size: 593 bytes --]

> 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
> produce blocks that the rest of the network will accept, run ntp on
> your system.
>

Requiring it for miners sounds very reasonable.

JS

[-- Attachment #2: Type: text/html, Size: 963 bytes --]

Re: [Bitcoin-development] Difficulty adjustment / time issues

[kjj]

Gavin Andresen wrote:
> 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.

Re: [Bitcoin-development] Difficulty adjustment / time issues

[Gavin Andresen]

> 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.

> 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.

-- 
--
Gavin Andresen

Re: [Bitcoin-development] Difficulty adjustment / time issues

[Luke-Jr]

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.

Re: [Bitcoin-development] Difficulty adjustment / time issues

[Christian Decker]

[-- Attachment #1: Type: text/plain, Size: 2109 bytes --]

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:

> 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&reg; DevCon Americas, Oct. 18-20, San Francisco, CA
> Learn about the latest advances in developing for the
> BlackBerry&reg; mobile platform with sessions, labs & more.
> See new tools and technologies. Register for BlackBerry&reg; 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
>

[-- Attachment #2: Type: text/html, Size: 2807 bytes --]

Re: [Bitcoin-development] Difficulty adjustment / time issues

[Aidan Thornton]

On Wed, Sep 14, 2011 at 3:45 PM, Gavin Andresen <gavinandresen@gmail.com> wrote:
> 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...

Re: [Bitcoin-development] Difficulty adjustment / time issues

[Gregory Maxwell]

On Wed, Sep 14, 2011 at 3:52 PM, Aidan Thornton <makosoft@gmail.com> wrote:
> 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".

Re: [Bitcoin-development] Difficulty adjustment / time issues

[Gavin Andresen]

> 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).

-- 
--
Gavin Andresen

Re: [Bitcoin-development] Difficulty adjustment / time issues

[Alex Waters]

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.

-Alex

Re: [Bitcoin-development] Difficulty adjustment / time issues

[Gregory Maxwell]

On Wed, Sep 14, 2011 at 5:36 PM, Alex Waters <ampedal@gmail.com> wrote:
> 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.

Re: [Bitcoin-development] Difficulty adjustment / time issues

[theymos]

On Wednesday, September 14, 2011 5:51 PM, "Gregory Maxwell" <gmaxwell@gmail.com> wrote:
> 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.

Re: [Bitcoin-development] Difficulty adjustment / time issues

[Luke-Jr]

On Wednesday, September 14, 2011 4:09:00 PM Gregory Maxwell wrote:
> 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*.

> 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).

Re: [Bitcoin-development] Difficulty adjustment / time issues

[Luke-Jr]

On Tuesday, September 13, 2011 11:06:37 AM Gavin Andresen wrote:
> 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.

> 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.

Re: [Bitcoin-development] Difficulty adjustment / time issues

[theymos]

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.

Re: [Bitcoin-development] Difficulty adjustment / time issues

[Pieter Wuille]

On Tue, Sep 13, 2011 at 11:06:37AM -0400, Gavin Andresen wrote:
> 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?

-- 
Pieter

Re: [Bitcoin-development] Difficulty adjustment / time issues

[Luke-Jr]

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...

Re: [Bitcoin-development] Difficulty adjustment / time issues

[Pieter Wuille]

On Mon, Nov 07, 2011 at 10:27:57AM -0500, Luke-Jr wrote:
> 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.

-- 
Pieter