Page MenuHomePhabricator

Implement Grasberg DAA
ClosedPublic

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

Details

Reviewers
majcosta
Fabien
Group Reviewers
Restricted Project
Commits
rABC963c8c171c77: Implement Grasberg DAA
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
src/pow/grasberg.h
29 ↗(On Diff #22479)

uint32_t n is const, no?

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

similar to the above

majcosta requested changes to this revision.Jul 24 2020, 14:33
This revision now requires changes to proceed.Jul 24 2020, 14:33
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.

Make deterministicExp2 argument const

More typos

src/pow/grasberg.cpp
58

reative -> relative

64

aproximation -> approximation

224

aproximate -> approximate

src/pow/test/grasberg_tests.cpp
263

sevral -> several

627

sevral -> several

src/pow/util.h
11

require -> required

  • Remove possible division by 0 in ComputeTargetFromWork .
  • Implement @marklundeberg 's idea for testnet retargeting

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.

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

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.

Use target instead of work

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.

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.

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

Implement @jhoenicke 's suggestion about how to compute exp2

Fabien requested changes to this revision.Jul 27 2020, 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.Jul 27 2020, 10:46
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.

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

Remove facotrisation from DAA.

Nice improvement !

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

buket => bucket

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

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.

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.

A few typos found by @Mengerian are still here.

src/pow/grasberg.cpp
62 ↗(On Diff #22580)

reative => relative

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

sevral => several

627 ↗(On Diff #22580)

Dito

This revision is now accepted and ready to land.Nov 5 2020, 16:56
This revision was automatically updated to reflect the committed changes.