Page MenuHomePhabricator

Implement the proposed difficulty adjustement algorithm proposed in the ML
AbandonedPublic

Authored by deadalnix on Sep 29 2017, 12:34.

Details

Reviewers
freetrader
sickpig
schancel
dagurval
Mengerian
maddenw
kyuupichan
Group Reviewers
Restricted Project
Summary

This algorithm has shown to be able to adapt very quickly to hashrate variation while being more stable than other alternatives.

The algorithm is currently not exercised outside of tests as that's be a hard fork and we need a bit ore discussion before proceeding. However, Having the code here and ready would help people experimenting with it.

Test Plan
make check

Diff Detail

Repository
rABC Bitcoin ABC
Branch
newpow
Lint
Lint OK
Unit
No Unit Test Coverage
Build Status
Buildable 940
Build 940: arc lint + arc unit

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
schancel added inline comments.Sep 29 2017, 23:53
src/pow.cpp
239 ↗(On Diff #1449)

This is just to ensure we have a height that is >= that the interval? (I'm asking because a height and an interval wouldn't normally make sense to compare)

261 ↗(On Diff #1449)

suffiscient -> sufficient

What does sufficient mean in this context?

266 ↗(On Diff #1449)

Could we directly iterate backwards over blocks? I assume this performs an O(N) lookup for each iteration of this loop?

269 ↗(On Diff #1449)

I'm missing something. Why do we start with blockCount 3 if we want at least 5?

274 ↗(On Diff #1449)

Is this just defensive programming? How can this ever be true if pindexLast is the descendant of pindexFast?

If it's defensive programming, could you please call that out?

280 ↗(On Diff #1449)

So we find two blocks that took longer to produce than 13 blocks *should* have taken? This could be 5 blocks, or it could be something > 13?

If yes to both, please add a comment as to why 13 blocks.

321 ↗(On Diff #1449)

This all makes sense. I'll look up these GetCompact/SetCompact functions in a bit. I assume they return/set the number of bits required to represent the target?

src/test/pow_tests.cpp
87 ↗(On Diff #1449)

Why did this change? Is it because it's continually calculated now?

217 ↗(On Diff #1449)

Comment says 60s, but looks like every 600s?

224 ↗(On Diff #1449)

stay > stays

237 ↗(On Diff #1449)

My 2¢: I really hate using i++ in an index operation.

242 ↗(On Diff #1449)

witha bogous -> with a bogus

249 ↗(On Diff #1449)

So we produce a bunch of blocks every 60s, then a handful of blocks every 10 minutes, then a single block 100 minutes in the future, and then some more 10 minute blocks?

341 ↗(On Diff #1449)

Should we assert that it has no impact?

This revision now requires changes to proceed.Sep 29 2017, 23:53
zquestz added a subscriber: zquestz.Sep 30 2017, 00:30

I am not the best person to review this logic, but the tests look great, and I put in some minor nits. Thanks for doing this Amaury. Great stuff.

src/pow.cpp
217 ↗(On Diff #1449)

quicly => quickly

src/test/pow_tests.cpp
215 ↗(On Diff #1449)

etablish -> establish

251 ↗(On Diff #1449)

emiting -> emitting

zquestz added inline comments.Sep 30 2017, 00:34
src/pow.cpp
182 ↗(On Diff #1449)

sckewed -> skewed

183 ↗(On Diff #1449)

topmost -> top most

maddenw added a subscriber: maddenw.Sep 30 2017, 01:21
maddenw requested changes to this revision.EditedSep 30 2017, 02:24

Comments say "60 seconds" but code reflecting 600 on line 217.

LINES 2, 3, 4
Copyright (c) mistakes. Bitcoin was not called "Core" until 2014 with version 0.9 in April. Prior copyright verified from looking at earlier releases were credited to "The Bitcoin developers". Also, "The Bitcoin Core developers" should extend to 2017, not 2016.

Please change:

Copyright (c) 2009-2010 Satoshi Nakamoto
Copyright (c) 2009-2016 The Bitcoin Core developers
Copyright (c) 2017 The Bitcoin developers

To:

Copyright (c) 2009-2010 Satoshi Nakamoto
Copyright (c) 2009-2014 The Bitcoin developers
Copyright (c) 2014-2017 The Bitcoin Core developers
Copyright (c) 2017 The Bitcoin developers

Lines 31, 155, 183, 232, 295 and more have spelling mistakes in the comments. Nit picking, but it's financial software. Even comments need to be clean (peoples' money).

I think simulations need to be run against the new difficulty logic independently followed by some peer review before considering the above. The work this was based upon on had simulations, but this too needs to have new simulations and peer review, especially through the specific lens of how miners + EDA have created a choppy difficulty situation for BCC.

Unknown Object (User) added a subscriber: Unknown Object (User).Sep 30 2017, 08:29
Unknown Object (User) added inline comments.
src/pow.cpp
155 ↗(On Diff #1449)

Compte the a target -> Compute the target

179 ↗(On Diff #1449)

assert will crash while pindex->nHeight<3. Should we change this line into:

if (pindex->nHeight < 3) return NULL;

Even comments need to be clean (peoples' money).

Indeed, we cannot count how many people lost money because of comments.

Even comments need to be clean (peoples' money).

Indeed, it's very common for people to lose money because of typos in comments. So that absolutely follows.

src/pow.cpp
179 ↗(On Diff #1449)

No.

231 ↗(On Diff #1449)

Yes.

239 ↗(On Diff #1449)

This ensure we have enough history to use the algorithm. This should never run as we have enough history today.

266 ↗(On Diff #1449)

It doesn't quite work because of the GetSuitableBlock logic. This also use a skiplist so it is log(n). Probably good enough.

269 ↗(On Diff #1449)

Because of GetSuitableBlock, 3 may be enough to get there.

274 ↗(On Diff #1449)

There is no guarantee that timestamps are ordered. There are good reasons for this, that are outside of the scope of this diff.

280 ↗(On Diff #1449)

13 is to make sure we have enough history and because it has no common factor with 2016.

321 ↗(On Diff #1449)

They return a 32bits representation, losing some precision in the process, like floating points.

src/test/pow_tests.cpp
87 ↗(On Diff #1449)

It's correct, but doesn't change much in practice because nBits is constant.

249 ↗(On Diff #1449)

The pattern fit timestamp manipulation. There is one block in there that'll have a negative duration compared to the previous one.

341 ↗(On Diff #1449)

The difficulty should get harder, not stay the same (because previous blocks are coming too fast).

deadalnix updated this revision to Diff 1459.Sep 30 2017, 09:20
deadalnix edited edge metadata.

Fix numerous typos

sickpig edited edge metadata.Sep 30 2017, 12:32

Guess that a link to the email where the algo is described should be put somewhere in the code comment or in the commit message

schancel accepted this revision.Sep 30 2017, 18:13
kyuupichan requested changes to this revision.Oct 1 2017, 03:22
kyuupichan added a subscriber: kyuupichan.

Just some minor typos

src/pow.cpp
156 ↗(On Diff #1449)

is->it

164 ↗(On Diff #1449)

negative, not complement

219 ↗(On Diff #1449)

vary

This revision now requires changes to proceed.Oct 1 2017, 03:22
deadalnix added inline comments.Oct 1 2017, 17:50
src/pow.cpp
164 ↗(On Diff #1449)

No complement. The formula is obviously incorrect using the negative.

deadalnix updated this revision to Diff 1472.Oct 1 2017, 21:06
deadalnix edited edge metadata.

Fix typos

tomtomtom7 added inline comments.
src/pow.cpp
179 ↗(On Diff #1449)

Both actualDuration and work are const.

Nitpick, also trying out review...

Mengerian added inline comments.Oct 3 2017, 19:10
src/pow.cpp
172 ↗(On Diff #1472)

It should be noted that this is a slight approximation.

The exact calculation would be:

return actualDuration * ( (-(work * params.nPowTargetSpacing / actualDuration)) / (work * params.nPowTargetSpacing));

Because the "W" in the formula above represents the work per block, so we substitute

W = (Hash Rate) * (Target time) = (work over interval) * (target time / interval duration)

into

Target = -W / W

(where "-W" is the 256-bit 2's complement simplification of (2^256 - W)

In practice, this makes a very small difference, since it's off-by-one of a large 256 bit number.

deadalnix updated this revision to Diff 1480.Oct 3 2017, 19:56

Tweak the math as per discussion with @Mengerian . It shouldn't change anything in practice as the change is within the rounding error, but it is still better to use the correct math.

Mengerian accepted this revision.Oct 3 2017, 20:13
This comment was removed by Mengerian.
src/pow.cpp
165 ↗(On Diff #1480)

I would rephrase this as:

  • From the total work done and the time it took to produce that much work,
  • we can deduce how much work we expect to be produced in the targeted
  • time between blocks.
Mengerian accepted this revision.Oct 3 2017, 20:16

Updated math looks good

deadalnix updated this revision to Diff 1485.Oct 4 2017, 14:01

Add checkpoints with specific values in tests.
Avoid calling GetAncestor repeatedly when searching for proper bounds for the fast window.

deadalnix marked 39 inline comments as done.Oct 4 2017, 14:10
gebregl added a subscriber: gebregl.Oct 6 2017, 12:13
kyuupichan added inline comments.Oct 7 2017, 05:32
src/pow.cpp
279

This condition is unnecessary and can be removed

dgenr8 added a subscriber: dgenr8.Oct 9 2017, 17:59
dgenr8 added inline comments.
src/pow.cpp
175

This is beautiful.

279

{10,20,30,40,50,60,70,80,90,100,110,65} can happen so this is protecting against underflow in the subtraction below.

297

In this comment, which target is "the most stable value"?

Unknown Object (User) added a subscriber: Unknown Object (User).Oct 12 2017, 09:06
ryanmce added a subscriber: ryanmce.Oct 15 2017, 20:12
ryanmce added inline comments.
src/chain.h
356–361

This looks like an unrelated change.

src/consensus/params.h
10

wildnewlineappeared

src/pow.cpp
170–174

Style-nit: Below, inline comments are using //, but here you're using /*. Consider choosing one and sticking with it. Personally, I prefer /** */ is for docblocks and // for inline comments, so I prefer the style you use below, but I don't care too much as long as you're consistent.

175

+1

185–189

This just repeats the docblock above. Consider removing it.

195–206

Why do swaps rather than just ifs and return the right one? The swaps themselves don't seem important here.

219

grammar-nit: s/ensure/ensures

222

grammar-nit: s/do/does

223

grammar-nit: s/to/too

229–230

I don't love asserts for input validation, only for catching programming errors. Why not just return a "reasonable" value here? Like the previous work, for example?

232–234

I prefer this // style for comments inside of a function.

296

grammar-nit: s/ensure/ensures
grammar-nit: remove the comma after "value"

304

grammar-nit: s/avoid/avoids

305

grammar-nit: s/swing/swings
grammer-nit: s/and to overreact/and overreactions

deadalnix added inline comments.Oct 16 2017, 13:39
src/pow.cpp
229–230

There is no previous work is pindexPrev is null.

deadalnix abandoned this revision.Nov 8 2017, 00:52