Page MenuHomePhabricator

Implement Grasberg DAA
Needs ReviewPublic

Authored by deadalnix on Mon, Jul 20, 18:55.

Details

Reviewers
majcosta
Fabien
Group Reviewers
Restricted Project
Summary

This is fo testing for now.

Test Plan
ninja check-pow

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
deadalnix updated this revision to Diff 22479.Thu, Jul 23, 23:46

More nits

Fabien accepted this revision.Fri, Jul 24, 13:39
majcosta added inline comments.Fri, Jul 24, 14:33
src/pow/grasberg.cpp
151 ↗(On Diff #22479)

can we use std::array instead of C-array here?

187 ↗(On Diff #22479)

ditto

src/pow/grasberg.h
29 ↗(On Diff #22479)

uint32_t n is const, no?

src/pow/test/grasberg_tests.cpp
154 ↗(On Diff #22479)

can be constexpr

168 ↗(On Diff #22479)

if we use a std::array<int,66> we can evaluate this at compile time also, doesn't look like this changes

198 ↗(On Diff #22479)

similar to the above

majcosta requested changes to this revision.Fri, Jul 24, 14:33
This revision now requires changes to proceed.Fri, Jul 24, 14:33
deadalnix added inline comments.Fri, Jul 24, 16:46
src/pow/grasberg.cpp
151 ↗(On Diff #22479)

I don't think that would add anything, really.

src/pow/grasberg.h
29 ↗(On Diff #22479)

Sure, I can can do this. It won't change anything in practice though, ints are passed by value so the caller really don't care either way.

src/pow/test/grasberg_tests.cpp
154 ↗(On Diff #22479)

Sure but this is a bit OCD at this point. We are not using this at compile time anyways.

168 ↗(On Diff #22479)

Sure, but then we need to put the exact size in there so changing the test is more burdensome. I'm not convinced this adds much value.

deadalnix updated this revision to Diff 22498.Fri, Jul 24, 17:10

Make deterministicExp2 argument const

More typos

src/pow/grasberg.cpp
58 ↗(On Diff #22498)

reative -> relative

64 ↗(On Diff #22498)

aproximation -> approximation

224 ↗(On Diff #22498)

aproximate -> approximate

src/pow/test/grasberg_tests.cpp
263 ↗(On Diff #22498)

sevral -> several

627 ↗(On Diff #22498)

sevral -> several

src/pow/util.h
11 ↗(On Diff #22498)

require -> required

deadalnix updated this revision to Diff 22502.Fri, Jul 24, 20:00
  • Remove possible division by 0 in ComputeTargetFromWork .
  • Implement @marklundeberg 's idea for testnet retargeting
deadalnix updated this revision to Diff 22503.Fri, Jul 24, 20:08

Add a static assert to check for arithmetic right shift.

We already had unit tests, but this will cause compilation to fail, which is better.

deadalnix updated this revision to Diff 22504.Fri, Jul 24, 20:12

Remove comment siggesting to runt he test suite now that we have a static assert

Harbormaster completed remote builds in B12153: Diff 22503.
deadalnix updated this revision to Diff 22518.Sat, Jul 25, 20:54

Only dirft correct one block with the special testnet rule.

I looked over the code and have some detailed comments.

There is also an overall comment;

Remember that this code basically will be part of the spec. Every implementation needs to have exactly the same rounding behaviour and thus needs to copy the code ported to the language. Doing C-tricks here will make porting the code more difficult to languages that don't distinguish between uint32_t and int32_t. With the current code as it is now, even the division operation in arith_uint256.c is part of the bitcoin cash specificiation. It would be better to keep the dependencies to other libraries small.

It would help to separate in ComputeTargetBlockTime and ComputeNextWork the code that collects the timestamps from the blockchain from the code that does the computation, so that the function that does the computation can be separately unit tested without creating dummy block chains. For reference, it would also help to have a specification a these functions, e.g., what mathematical function they approximate.

src/pow/grasberg.cpp
18 ↗(On Diff #22518)

A better name would be ONE_32, as it is representing the fixed point number 1.

106 ↗(On Diff #22518)

Using work instead of target introduces more rounding errors than using target directly and makes it more complicated porting this code, as you need division on 256 bit numbers.

It would be much easier and more precise to work directly on the bits representation of the difficulty.

118 ↗(On Diff #22518)

As noted by Marc Lundeberg, why not use a simple linear approximation. There is no reason why an exponential should work better here. The absolute difference between a linear function and the exponential should also be just a few seconds.

135 ↗(On Diff #22518)

The implicit cast to uint32_t here that silently adds 2^32 for negative x32 must be documented. The comment should also explain how the effect of this is taken care of by the right shift in line 138 when x32 is negative.

For my taste these bit-fiddling tricks are dangerous and will lead to subtle bugs when trying to port this code to other languages. Note also that the earliest time such a bug will trigger for the main chain is in several years when the blocks will get back to normal 10 minutes intervals.

197 ↗(On Diff #22518)

These constants are almost the same as ((k0 + POW2_32) * LN2_32) >> 32. Does the extra precision really merit doubling the number of magic constants?

249 ↗(On Diff #22518)

Why the >> 1 here and then >>31 in the next line. Are you afraid of overflows? The prescaling should ensure that x is less than 2^27, so there is no overflow in u1+u2.

It deserves more comments, e.g., that the halfing of u1 is counteracted by the >>31 in the next line, while for u2 there is >> 2 because the Taylor series contains 0.5x^2.

Why so complicated? Something like

// scale x so that exp(xscaled) = 2^x, i.e. xscaled= x*ln(2).
int64_t xscaled = (x*LN2_32)>>32;
// approximate exp(xscaled)-1 by the Taylor series x + x^2/2 (the right shift by 33 divides x^2 by 2).
int64_t u = xscaled + (xscaled * xscaled)>>33;
// multiply result by 1+k0.  Note that we need to return (1+k0)*exp(xscaled) - 1 = (1+k0)*(exp(xscaled)-1) +  k0
return k0 + (u * (k0 + POW2_32))>>32

should be similarly accurate, doesn't need k1, and is probably easier to understand.

deadalnix updated this revision to Diff 22524.Sun, Jul 26, 22:10

Use target instead of work

deadalnix added inline comments.Sun, Jul 26, 22:20
src/pow/grasberg.cpp
249 ↗(On Diff #22518)

Why the >> 1 here and then >>31 in the next line. Are you afraid of overflows? The prescaling should ensure that x is less than 2^27, so there is no overflow in u1+u2.

I'm afraid you are incorrect on this one, you can definitively get an oveflow for u1+u2 . This is something I double checked for.

I will play with some of the proposed simplification and see how it goes.

deadalnix added inline comments.Sun, Jul 26, 22:26
src/pow/grasberg.cpp
135 ↗(On Diff #22518)

For my taste these bit-fiddling tricks are dangerous and will lead to subtle bugs when trying to port this code to other languages.

This is interesting. My experience is somewhat the reverse. Not that more bit fiddling is always good - obviously not - but that trying to avoid them and pretend that computer math somehow resemble "real" math is a common source of problems. I will definitively add a comment to explain the right shift business, however. Good call.

deadalnix updated this revision to Diff 22525.Sun, Jul 26, 22:36

Add comments to explain unintuitive "computer math" in computeTargetBlockTime

Snippet of first build failure:

interface_rest.py                       | ○ Skipped | 0 s
mempool_accept.py                       | ○ Skipped | 0 s
mempool_limit.py                        | ○ Skipped | 0 s
mempool_packages.py                     | ○ Skipped | 0 s
mempool_persist.py                      | ○ Skipped | 0 s
mempool_reorg.py                        | ○ Skipped | 0 s
mempool_resurrect.py                    | ○ Skipped | 0 s
mempool_spend_coinbase.py               | ○ Skipped | 0 s
mining_prioritisetransaction.py         | ○ Skipped | 0 s
p2p_compactblocks.py                    | ○ Skipped | 0 s
p2p_feefilter.py                        | ○ Skipped | 0 s
p2p_leak_tx.py                          | ○ Skipped | 0 s
rpc_createmultisig.py                   | ○ Skipped | 0 s
rpc_estimatefee.py                      | ○ Skipped | 0 s
rpc_psbt.py                             | ○ Skipped | 0 s
rpc_scantxoutset.py                     | ○ Skipped | 0 s
rpc_signmessage.py                      | ○ Skipped | 0 s
rpc_signrawtransaction.py               | ○ Skipped | 0 s
rpc_txoutproof.py                       | ○ Skipped | 0 s
tool_wallet.py                          | ○ Skipped | 0 s
wallet_abandonconflict.py               | ○ Skipped | 0 s
wallet_address_types.py                 | ○ Skipped | 0 s
wallet_avoidreuse.py                    | ○ Skipped | 0 s
wallet_backup.py                        | ○ Skipped | 0 s
wallet_balance.py                       | ○ Skipped | 0 s
wallet_basic.py                         | ○ Skipped | 0 s
wallet_create_tx.py                     | ○ Skipped | 0 s
wallet_createwallet.py                  | ○ Skipped | 0 s
wallet_createwallet.py --usecli         | ○ Skipped | 0 s
wallet_dump.py                          | ○ Skipped | 0 s
wallet_encryption.py                    | ○ Skipped | 0 s
wallet_groups.py                        | ○ Skipped | 0 s
wallet_hd.py                            | ○ Skipped | 0 s
wallet_import_rescan.py                 | ○ Skipped | 0 s
wallet_import_with_label.py             | ○ Skipped | 0 s
wallet_importmulti.py                   | ○ Skipped | 0 s
wallet_importprunedfunds.py             | ○ Skipped | 0 s
wallet_keypool.py                       | ○ Skipped | 0 s
wallet_keypool_topup.py                 | ○ Skipped | 0 s
wallet_labels.py                        | ○ Skipped | 0 s
wallet_listreceivedby.py                | ○ Skipped | 0 s
wallet_listsinceblock.py                | ○ Skipped | 0 s
wallet_listtransactions.py              | ○ Skipped | 0 s
wallet_multiwallet.py                   | ○ Skipped | 0 s
wallet_multiwallet.py --usecli          | ○ Skipped | 0 s
wallet_resendwallettransactions.py      | ○ Skipped | 0 s
wallet_txn_clone.py                     | ○ Skipped | 0 s
wallet_txn_clone.py --mineblock         | ○ Skipped | 0 s
wallet_txn_doublespend.py               | ○ Skipped | 0 s
wallet_txn_doublespend.py --mineblock   | ○ Skipped | 0 s
wallet_zapwallettxes.py                 | ○ Skipped | 0 s
p2p_timeouts.py                         | ✖ Failed  | 11 s

ALL                                     | ✖ Failed  | 277 s (accumulated) 
Runtime: 56 s

FAILED: test/CMakeFiles/check-functional 
cd /work/abc-ci-builds/build-without-wallet/test && /usr/bin/cmake -E env /usr/bin/python3.7 ./functional/test_runner.py
ninja: build stopped: subcommand failed.
Build build-without-wallet failed with exit code 1

Each failure log is accessible here:
Bitcoin ABC functional tests: p2p_timeouts.py

deadalnix updated this revision to Diff 22526.Mon, Jul 27, 00:17

Implement @jhoenicke 's suggestion about how to compute exp2

Fabien requested changes to this revision.Mon, Jul 27, 10:46
Fabien added inline comments.
src/pow/grasberg.cpp
67 ↗(On Diff #22526)

This comment is no longer accurate

141 ↗(On Diff #22526)

intereger => integer

144 ↗(On Diff #22526)

Dito

src/pow/test/grasberg_tests.cpp
161 ↗(On Diff #22526)

Remove

This revision now requires changes to proceed.Mon, Jul 27, 10:46
jhoenicke added inline comments.Mon, Jul 27, 11:21
src/pow/grasberg.cpp
152 ↗(On Diff #22526)

Copy over the comment from the header file? Maybe also expand a bit.

This function returns an approximation of 2^n - 1 in 32-bit fixed point notation. Thus the argument is is interpreted as the number (n/2^32) in the interval [0, 1[. The result is also in the interval [0, 1[ and scaled by 2^32.

In other words, this function returns an approximation of (2^(n / 2^32) - 1) * 2^32.

226 ↗(On Diff #22526)

nitpicking my own code :)
It returns exactly the same value but is a tiny bit simpler.

Beware that this diff doesn't delete all old lines. Is there a way to do a proper multi-line diff in phabricator?

deadalnix added inline comments.
src/pow/grasberg.cpp
226 ↗(On Diff #22526)

While your proposal was very good, @markblundeberg ended up sending me something that is both simpler and more precise, that I'm working on integrating now. The progress made here is fantastic, thanks to you and Mark.

deadalnix updated this revision to Diff 22541.EditedMon, Jul 27, 20:50

New, more precise and more concise implementation for deterministicExp2 suggested by @markblundeberg

deadalnix updated this revision to Diff 22543.Mon, Jul 27, 20:55

Remove facotrisation from DAA.

deadalnix updated this revision to Diff 22551.Mon, Jul 27, 22:41

Address @Fabien 's comments

Fabien added a comment.Tue, Jul 28, 08:33

Nice improvement !

src/pow/grasberg.cpp
182 ↗(On Diff #22551)

buket => bucket

deadalnix updated this revision to Diff 22579.Tue, Jul 28, 12:04

Simplify target computation by dropping one bit out of the exp2 compuation. That bit is not significant anyways, so we are good.

deadalnix updated this revision to Diff 22580.Tue, Jul 28, 12:09

Update comments

Comment about the new approximation for exponential:

src/pow/grasberg.cpp
181 ↗(On Diff #22551)

I have my own code to compute Remez-approximated polynomials. It produces a slightly more precise polynom:
2977042781 * x + 1031830288 *x**2 + 237606570 * x**3 + 44970684*x**4.
The difference is small (3.1e-9 vs. 3.8e-9), though. Main purpose of this exercise was to verify the code.

Here is the gnuplot command for plotting relative error (my code optimizes for absolute error, but the difference is small).

plot [0:.25] (1+2977042554./2**32*x + 1031834945./2**32*x**2 + 237575834./2**32*x**3 + 45037112./2**32*x**4)/exp(x*log(2))-1,(1+2977042781./2**32*x + 1031830288./2**32*x**2 + 237606570./2**32*x**3 + 44970684./2**32*x**4)/exp(x*log(2))-1

OTOH, the polynomial from Mark is precise for x=.25, which may be important for monotonicity. If I optimize with this constraint I get:
2977042597*x + 1031835569*x**2 + 237564652*x**3 + 45069083*x**4. The error is around 3.5e-9 so still very slightly better.

plot [0:.25] (1+2977042554./2**32*x + 1031834945./2**32*x**2 + 237575834./2**32*x**3 + 45037112./2**32*x**4)/exp(x*log(2))-1,(1+2977042597./2**32*x + 1031835569./2**32*x**2 + 237564652./2**32*x**3 + 45069083./2**32*x**4)/exp(x*log(2))-1

I guess my suggestion is to use these coefficients: 2977042597, 1031835569, 237564652, 45069083, unless Mark has a reason why his coefficients are better. The difference as I said is very tiny.

If you want to go fancy, you can even get to 6e-10 on the full interval [-.5,.5]
by using an approximation for R(x) = x + 2x/(2^x-1), which is easier to approximate with polynomials:

R(x) * 2^30 = 3098164009 + 124043115 * x^2 + -988834 * x^4

Then compute 2^x - 1 = 2x/(R(x)-x):

plot [-.5:.5] (1 + 2*x*2**30/(3098164009. + 124043115*x**2 + -988834 * x**4 - 2**30 * x)) / (exp(x*log(2)))-1

This requires rescaling x to a signed integer.

deadalnix added inline comments.Fri, Jul 31, 13:18
src/pow/grasberg.cpp
181 ↗(On Diff #22551)

One of the problem with that approach is that x^4 does not fit in a natively supported type. So we' end up with a ton of bit manips, or we'd shift out a few bits, in which case we'll get back to something similar to what Mark produced.

Simplicity is also a benefit here. I'm not convinced the extra precision justify the extra complexity.

Fabien accepted this revision.Mon, Aug 3, 07:55

A few typos found by @Mengerian are still here.

src/pow/grasberg.cpp
62

reative => relative

src/pow/test/grasberg_tests.cpp
263

sevral => several

627

Dito