Difficulty adjustment needs modifying

[kano]

Allowing asymmetric adjustments can lead to security problems.  Artforz described a few when this came up on alternate chains.

Yep that's what the first post directly implies
Asymmetric

However, making the vague 'can lead to security problems' comment is rather pointless.

The obvious security problem would be a sudden drop in difficulty well below the network hash rate.
That's the point of having a delay after a difficulty change and also have the % high

Feel free to suggest values based on some reasonably complex but viable calculation
(mine are just based on a feel of the actual network, watching the difficulty prediction after a change and seeing what happened with the hacks in the scam coins - but 'feeling' are often wrong and that's also why I've wanted to put the idea up for discussion)

I'm sure there are other 'security problems', but at least mention them ...
Even the current bitcoin has a WELL known one - 51% ... that seems to have the only well known reasonable fix of checkpoints that are implemented.

Edit: though I can't find any code to stop a fork from below the checkpoint ... hmm

[Gavin Andresen]

I'm sure there are other 'security problems', but at least mention them ...

He did. He said ArtForz brought them up in the Alternative Currencies board.

See this thread for details:
  https://bitcointalk.org/index.php?topic=43692.msg521772#msg521772

[kano]

I'm sure there are other 'security problems', but at least mention them ...

He did. He said ArtForz brought them up in the Alternative Currencies board.

See this thread for details:
  https://bitcointalk.org/index.php?topic=43692.msg521772#msg521772

Yes well that one has been discussed to death over there and there is even a fix for it, but no I've not looked at the bitcoin git to see if a related commit has gone in there ...

OK, so that one's OK to ignore. Anyone got some more?

I am quite serious about this idea because I hear a lot of people saying 'bitcoin will die soon' and although that really doesn't matter, I'm interested in it staying alive and this particular issue is one that could make a hiccough turn into a nightmare.
It is pretty easy to see the problem but (as I said) the solution should be to handle the unexpected case of it happening and otherwise have no effect.

I'm also certain that if the discussion changed to completely replacing the current 2016 method the discussion would go on forever and never be implemented.

Edit: all things in economics have ups and downs, but it's a really good idea to not help the bad downs go down faster yourself.

[Gavin Andresen]

Fine, then ponder this for a while:
  https://bitcointalk.org/index.php?topic=42417.msg517020#msg517020

Executive summary:  asymmetric difficulty adjustments and adjustments based on time are really, really hard to get correct.

I haven't thought about it hard, but I trust ArtForz when he says he thinks it is IMPOSSIBLE to get it right.

[Transisto]

How much hashing power do people running BF3 have to think this affect Bitcoin ?

10 min for a transaction is already so long than having it take even 30 min would not change usage much.

Sorry I don't see where this is going at all.

... As if not enough people have near free electricity and brought GPU specifically for mining that price of BTC or a game release threaten the network ...

[kano]

Fine, then ponder this for a while:
  https://bitcointalk.org/index.php?topic=42417.msg517020#msg517020

Executive summary:  asymmetric difficulty adjustments and adjustments based on time are really, really hard to get correct.

I haven't thought about it hard, but I trust ArtForz when he says he thinks it is IMPOSSIBLE to get it right.

Well that's a link back to around when he first pointed out the issue.
So your saying his fix that even he proposed doesn't work?
(yes I haven't looked at his fix - I guess I was silly to trust ArtForz's comments about there being a fix )

Anyway, there's a 144 block buffer in my suggestion already (the 12 block test can only re-diff once before the buffer hits again)
My reasoning for the buffer was to avoid statistical variance after a re-diff - but it seems to help with the time problem also.

The 'ArtForz' takeover requires 51% which really is a non issue for the main block chain.
If we suddenly fall low enough for someone to do a 51% takeover (other than a company like MS or google or a large government who could do it now anyway) then with the current software everyone will just ride it straight to the ground anyway due to no re-diff happening ever again.

* kano ... wanders off to read up about the problems with the time fix and who actually implemented it ...

How much hashing power do people running BF3 have to think this affect Bitcoin ?

10 min for a transaction is already so long than having it take even 30 min would not change usage much.

Sorry I don't see where this is going at all.

... As if not enough people have near free electricity and brought GPU specifically for mining that price of BTC or a game release threaten the network ...

Going ... it's about the problem that if the network hash power did drop drastically, then the next difficulty recalculation could end up being weeks or even months away.
That would of course have obvious roll on effects on the new hashing power ... and could lead to a rather drastic downward spiral ... which could lead to all sorts of financial issues and decisions by the few companies/people who do allow BTC payments (among other things)

Edit: as stated in my first post

[kjj]

Fine, then ponder this for a while:
  https://bitcointalk.org/index.php?topic=42417.msg517020#msg517020

Executive summary:  asymmetric difficulty adjustments and adjustments based on time are really, really hard to get correct.

I haven't thought about it hard, but I trust ArtForz when he says he thinks it is IMPOSSIBLE to get it right.

Well that's a link back to around when he first pointed out the issue.
So your saying his fix that even he proposed doesn't work?
(yes I haven't looked at his fix - I guess I was silly to trust ArtForz's comments about there being a fix )

Anyway, there's a 144 block buffer in my suggestion already (the 12 block test can only re-diff once before the buffer hits again)
My reasoning for the buffer was to avoid statistical variance after a re-diff - but it seems to help with the time problem also.

The 'ArtForz' takeover requires 51% which really is a non issue for the main block chain.
If we suddenly fall low enough for someone to do a 51% takeover (other than a company like MS or google or a large government who could do it now anyway) then with the current software everyone will just ride it straight to the ground anyway due to no re-diff happening ever again.

* kano ... wanders off to read up about the problems with the time fix and who actually implemented it ...

I'm of the opinion that if there is ever a huge sudden decline in the hashing power, there won't be a system to worry about.

But, since your scenario is about what to do in exactly that situation, you can't hide behind the "but bitcoin is huge" thing any more, because 51% isn't a big deal at that scale.

At any rate, the big problem is that it aligns the incentives in a bad way.  With an asymmetric system, each miner has a personal incentive to join the cabal.  The current system is careful about keeping the interests of each participant aligned with the interests of the system as a whole.

[maaku]

Unless I'm seriously misunderstanding, no one is discussing asymmetric adjustments here..

You are.  This is exactly what is under discussion.

From the OP: “It would (as I said) be an up or down adjustment test, not just for downward adjustments.”

Maybe I'm misunderstanding what you mean by asymmetric?

EDIT: Regarding ArtForz's attack (the one you linked to), it was against against an off-by-one error in the implementation of bitcoin. That sort of thing is really orthogonal to the discussion here. Unless there is another attack he published that I'm not aware of?

[Transisto]

...it's about the problem that if the network hash power did drop drastically, then the next difficulty recalculation could end up being weeks or even months away.
That would of course have obvious roll on effects on the new hashing power ... and could lead to a rather drastic downward spiral ... which could lead to all sorts of financial issues and decisions by the few companies/people who do allow BTC payments (among other things)...

The network hash could drop drastically if ... :

• New hype game come out : 1-3% drop (very likely, insignificant)
  
• Bitcoin price drop to ~1$: 40-50% drop depending on popularity of PFGAs,ASICs (Yes, many people actually pay this little and others use the heat for other purposes.)
  (very unlikely, can be tolerated)
• Natural disasters of the order to affect ~50% of world population at once for more than 1 month, (Yellowstone ?, Impact ?, Geomagnetic storm ?)
• Voluntary attempt at destabilizing the network in preparation of 51% attack,  Example: Massive sellout dropping the price to ~1$, combined with a 20-40% addition in hashing power at start of new adjustment (51% attack would now require ~33%) They'd need to attack fast because we'd have time to spread to word and keep mining at lost.
• ... ?

_{*Given 1.6m difficulty}

[kano]

Fine, then ponder this for a while:
  https://bitcointalk.org/index.php?topic=42417.msg517020#msg517020

Executive summary:  asymmetric difficulty adjustments and adjustments based on time are really, really hard to get correct.

I haven't thought about it hard, but I trust ArtForz when he says he thinks it is IMPOSSIBLE to get it right.

Well that's a link back to around when he first pointed out the issue.
So your saying his fix that even he proposed doesn't work?
(yes I haven't looked at his fix - I guess I was silly to trust ArtForz's comments about there being a fix )

Anyway, there's a 144 block buffer in my suggestion already (the 12 block test can only re-diff once before the buffer hits again)
My reasoning for the buffer was to avoid statistical variance after a re-diff - but it seems to help with the time problem also.

The 'ArtForz' takeover requires 51% which really is a non issue for the main block chain.
If we suddenly fall low enough for someone to do a 51% takeover (other than a company like MS or google or a large government who could do it now anyway) then with the current software everyone will just ride it straight to the ground anyway due to no re-diff happening ever again.

* kano ... wanders off to read up about the problems with the time fix and who actually implemented it ...

I'm of the opinion that if there is ever a huge sudden decline in the hashing power, there won't be a system to worry about.

But, since your scenario is about what to do in exactly that situation, you can't hide behind the "but bitcoin is huge" thing any more, because 51% isn't a big deal at that scale.

At any rate, the big problem is that it aligns the incentives in a bad way.  With an asymmetric system, each miner has a personal incentive to join the cabal.  The current system is careful about keeping the interests of each participant aligned with the interests of the system as a whole.

Hmm misunderstanding there I think.

I'm not hiding behind anything - you obviously misread.
My point says that if that happens it will probably be a scenario that falls into my suggested code 'intercept'.
However, without anything to handle it "everyone will just ride it straight to the ground anyway due to no re-diff happening ever again."

The estimate change I keep seeing for the current difficulty is 7% to 10% as it stands now.
If we see it reach 20% then not having something in place to handle 50% early would be tantamount to bitcoin suicide in my opinion.

I'd also say that everyone would have the same disincentive if the problem occurred.
The death of bitcoin (though that would be an incentive for those who want that ...)
I can't see "the interests of the system as a whole" related to the problem the system ignores if halfway through a 2016 the network hash rate has dropped to 50%
The possibility of a 50% drop causing a downward spiral are not nothing and are not related to aligned incentives at all ...

[kano]

...it's about the problem that if the network hash power did drop drastically, then the next difficulty recalculation could end up being weeks or even months away.
That would of course have obvious roll on effects on the new hashing power ... and could lead to a rather drastic downward spiral ... which could lead to all sorts of financial issues and decisions by the few companies/people who do allow BTC payments (among other things)...

The network hash could drop drastically if ... :

• New hype game come out : 1-3% drop (very likely, insignificant)
  
• Bitcoin price drop to ~1$: 40-50% drop depending on popularity of PFGAs,ASICs (Yes, many people actually pay this little and others use the heat for other purposes.)
  (very unlikely, can be tolerated)
• Natural disasters of the order to affect ~50% of world population at once for more than 1 month, (Yellowstone ?, Impact ?, Geomagnetic storm ?)
• Voluntary attempt at destabilizing the network in preparation of 51% attack,  Example: Massive sellout dropping the price to ~1$, combined with a 20-40% addition in hashing power at start of new adjustment (51% attack would now require ~33%) They'd need to attack fast because we'd have time to spread to word and keep mining at lost.
• ... ?

_{*Given 1.6m difficulty}

It seems to have dropped as much as 10% at the moment ...

I'm not saying this will happen, I'm suggesting a change in case it does happen.

Think of it this way: Is everyone who takes life insurance suicidal?

[kjj]

Unless I'm seriously misunderstanding, no one is discussing asymmetric adjustments here..

You are.  This is exactly what is under discussion.

From the OP: “It would (as I said) be an up or down adjustment test, not just for downward adjustments.”

Maybe I'm misunderstanding what you mean by asymmetric?

EDIT: Regarding ArtForz's attack (the one you linked to), it was against against an off-by-one error in the implementation of bitcoin. That sort of thing is really orthogonal to the discussion here. Unless there is another attack he published that I'm not aware of?

If the difficulty adjustment takes fewer blocks in certain circumstances, that is what I mean by asymmetric.  And it can be gamed.

[kano]

Unless I'm seriously misunderstanding, no one is discussing asymmetric adjustments here..

You are.  This is exactly what is under discussion.

From the OP: “It would (as I said) be an up or down adjustment test, not just for downward adjustments.”

Maybe I'm misunderstanding what you mean by asymmetric?

EDIT: Regarding ArtForz's attack (the one you linked to), it was against against an off-by-one error in the implementation of bitcoin. That sort of thing is really orthogonal to the discussion here. Unless there is another attack he published that I'm not aware of?

That is the one he's referring to.
I've spent a little time finding related links:

ArtForz' last post about it (Forum time: September 13, 2011, 06:37:13 PM)
https://bitcointalk.org/index.php?topic=42417.msg523751#msg523751
saying that bitcoin doesn't have the fix included

I then went through the bitcoin git and read all the commits since 12/13 Sep:
https://github.com/bitcoin/bitcoin/commits/master

(AND a complete off topic comment on the last lot of commits:
LOL you let namecoin merged mining sneak in - did anyone realise that's what this is?
https://github.com/bitcoin/bitcoin/pull/476
Oh well, I guess it doesn't matter that they will be adding extra non-bitcoin data to the block-chain ...)

ArtForz' comment that there is a fix for the timewarp exploit:
https://bitcointalk.org/index.php?topic=42417.msg523714#msg523714

GG Git: ArtForz' NTP commit:
https://github.com/Lolcust/GeistGeld/commit/a25e1ce480f5bfbf7529bccd56df28b54c0eea77
basically trying to keep bitcoin's time accurate with the -ntp option
(on linux install ntpd as I always have )

But I can't find the change to the actual calculation ...
and I can't find anything like this link of Gavin's anywhere in GG or bitcoin:
https://bitcointalk.org/index.php?topic=42417.msg517020#msg517020

[kano]

Unless I'm seriously misunderstanding, no one is discussing asymmetric adjustments here..

You are.  This is exactly what is under discussion.

From the OP: “It would (as I said) be an up or down adjustment test, not just for downward adjustments.”

Maybe I'm misunderstanding what you mean by asymmetric?

EDIT: Regarding ArtForz's attack (the one you linked to), it was against against an off-by-one error in the implementation of bitcoin. That sort of thing is really orthogonal to the discussion here. Unless there is another attack he published that I'm not aware of?

If the difficulty adjustment takes fewer blocks in certain circumstances, that is what I mean by asymmetric.  And it can be gamed.

Yep it may take 1/14 of the blocks when needed.
So how can it be gamed ... unless you are simply referring to Artforz' attack he did on GG?
(that I have made a few comments about in the post above)

[ArtForz]

Unless I'm seriously misunderstanding, no one is discussing asymmetric adjustments here..

You are.  This is exactly what is under discussion.

From the OP: “It would (as I said) be an up or down adjustment test, not just for downward adjustments.”

Maybe I'm misunderstanding what you mean by asymmetric?

EDIT: Regarding ArtForz's attack (the one you linked to), it was against against an off-by-one error in the implementation of bitcoin. That sort of thing is really orthogonal to the discussion here. Unless there is another attack he published that I'm not aware of?

That is the one he's referring to.
I've spent a little time finding related links:

ArtForz' last post about it (Forum time: September 13, 2011, 06:37:13 PM)
https://bitcointalk.org/index.php?topic=42417.msg523751#msg523751
saying that bitcoin doesn't have the fix included

I then went through the bitcoin git and read all the commits since 12/13 Sep:
https://github.com/bitcoin/bitcoin/commits/master

(AND a complete off topic comment on the last lot of commits:
LOL you let namecoin merged mining sneak in - did anyone realise that's what this is?
https://github.com/bitcoin/bitcoin/pull/476
Oh well, I guess it doesn't matter that they will be adding extra non-bitcoin data to the block-chain ...)

ArtForz' comment that there is a fix for the timewarp exploit:
https://bitcointalk.org/index.php?topic=42417.msg523714#msg523714

GG Git: ArtForz' NTP commit:
https://github.com/Lolcust/GeistGeld/commit/a25e1ce480f5bfbf7529bccd56df28b54c0eea77
basically trying to keep bitcoin's time accurate with the -ntp option
(on linux install ntpd as I always have )

But I can't find the change to the actual calculation ...
and I can't find anything like this link of Gavin's anywhere in GG or bitcoin:
https://bitcointalk.org/index.php?topic=42417.msg517020#msg517020

Nope, bitcoin still has the off-by-1, as for now it's deemed "too big to fail" and fixing it would mean a backwards-incompatible change to the blockchain.

The off-by-1 fix is completely orthogonal to the NTP stuff.
It's right here:
https://github.com/Lolcust/GeistGeld/commit/f9523f33ec22e26b7781f5a545fc74b4ecdc31a6#diff-3

Iirc my "why asymmetric diff adjustment is bad" was in a thread discussing SCs adjustment algo, and so far every asymmetric diff adjustment method I bothered to figure out a optimal strategy on has the same problem, a 51% attacker can create more blocks in the same nTime window than "he should be able to" while only doing the same # of hashes as the real chain over the same nTime window. And every time the factor gained happened to come out exactly as the maximum down adjustment over the maximum up adjustment for the same # of blocks.
Trivial example for how time-based has the same flaw, let's say daily retarget and /4 *4 limits
official chain hashes along at difficulty 1 for 2 days, so it has 2 difficulty-days and takes 2 days worth of nTime.
attackers chain has 0 blocks on day 1 (= diff retargets by /4), 8 times the normal blocks at diff 1/4 on day 2 (=diff retargets *4 and is back to 1 afterwards), so the attackers chain has a total of 1/4 * 8 = 2 difficulty-days, starts and ends with diff 1, also takes 2 days worth of nTime, but contains 4 times the # of blocks of the official chain.

[maaku]

Trivial example for how time-based has the same flaw, let's say daily retarget and /4 *4 limits
official chain hashes along at difficulty 1 for 2 days, so it has 2 difficulty-days and takes 2 days worth of nTime.
attackers chain has 0 blocks on day 1 (= diff retargets by /4), 8 times the normal blocks at diff 1/4 on day 2 (=diff retargets *4 and is back to 1 afterwards), so the attackers chain has a total of 1/4 * 8 = 2 difficulty-days, starts and ends with diff 1, also takes 2 days worth of nTime, but contains 4 times the # of blocks of the official chain.

Other clients won't accept the new blockchain unless it represents more work, which at no point it does... unless you side network has 51% the hash power of the main network, which would make this just a fancy 51% attack (50% in this example), and is not exploitable otherwise, no?

[ArtForz]

Yep, all the "fucking with timestamps" are "only" worsening the result of 51% attacks.
The problem is this changes the economic incentives of miners, as "defecting" is suddenly a lot more profitable...

Short version of the simple version, cooperators are mining "as planned", defectors fork the chain and communicate to collectively build a alternate version with optimally adjusted timestamps, N is the fraction of "cooperating" hashrate:

Bitcoin as planned:
N = 1 cooperate, everyone gets 1.
N > 0.5 cooperate, cooperators get 1/N, defectors get 0.
N < 0.5 cooperate, cooperators get 0, defectors get 1/(1-N).
N = 0 cooperate, everyone gets 1.

Solidcoin/ixcoin/i0coin/... with *1.1 /4 limits (edit: in theory, as the real chains all also have the same off-by-1 in their retargeting):
N = 1 cooperate, everyone gets 1.
N > 0.5 cooperate, cooperators get 1/N, defectors get 0.
N < 0.5 cooperate, cooperators get 0, defectors get 3.6/(1-N).
N = 0 cooperate, everyone gets 3.6.

Bitcoin with off-by-1:
N = 1 cooperate, everyone gets 1.
N > 0.5 cooperate, cooperators get 1/N, defectors get 0.
N < 0.5 cooperate, cooperators get 0, defectors get near infinite (really (what difficulty should be)/(minimum difficulty)).
N = 0 cooperate, everyone gets near INF.

edit: forgot, all current *1.1 /4 chains *also* have the off-by-1, so it's really "near infinite" for "defectors get a majority" there, too...

[maaku]

Under the “bitcoin as planned” alternative there is no incentive either way, so fix the off-by-1 and make sure adjustments are +/- the same maximum ("symmetric" by everyone but kjj's definition) and we're done, right? In other words, you need the off-by-1 or asymmetry for this to be exploitable, right?

Also, once new coins are not being generated, the issue goes away as well, right? It doesn't matter how many blocks you generate if the entire subsidy is coming from transaction fees (a blocknumber based demurrage would still suffer the same problem, however).

[Meni Rosenfeld]

Solidcoin/ixcoin/i0coin/... with *1.1 /4 limits (edit: in theory, as the real chains all also have the same off-by-1 in their retargeting):
N = 1 cooperate, everyone gets 1.
N > 0.5 cooperate, cooperators get 1/N, defectors get 0.
N < 0.5 cooperate, cooperators get 0, defectors get 3.6/(1-N).
N = 0 cooperate, everyone gets 3.6.

Can't this kind of problem be solved with a term corresponding to the I in PID? If more blocks than normal are found consistently, this will kick in and increase the difficulty.

Also, the suggestion in the OP isn't to change the limits asymmetrically. It's to expedite the adjustment when the recent history indicates the next adjustment is expected too far in the future. If the hashrate goes backup, the difficulty can rapidly increase just fine. Maybe even make it so that in this scenario the difficulty can even more easily go up, to further decrease any gameability.

All I'm saying is that just because some alts came up with a half-assed algo, doesn't mean the doomsday problem is unsolvable.

Under the “bitcoin as planned” alternative there is no incentive either way, so fix the off-by-1 and make sure adjustments are +/- the same maximum ("symmetric" by everyone but kjj's definition) and we're done, right? In other words, you need the off-by-1 or asymmetry for this to be exploitable, right?

Done with ArtForz's attack, yes. But not with the problem of the OP.

Also, once new coins are not being generated, the issue goes away as well, right? It doesn't matter how many blocks you generate if the entire subsidy is coming from transaction fees (a blocknumber based demurrage would still suffer the same problem, however).

I believe so. But the dynamics of that era are still not understood well enough even without considering potential attacks.

[Zibbo]

Wouldn't it be easiest to keep the original retarget algo (with 2016 block window etc), but just do the retargetting more often so that retarget windows overlap? You could retarget every block if you wanted (or every 10 or whatever).

With system like this, for example Namecoin difficulty would have dropped to "profitable" levels a long long time ago, and it would have suffered only a temporary slowdown.

Is there a downside to a system like this that I don't see? Some problem it doesn't solve or some exploit it introduces? It seems so simple :-)