This is fo testing for now.
Details
- Reviewers
majcosta Fabien - Group Reviewers
Restricted Project - Commits
- rABC963c8c171c77: Implement Grasberg DAA
ninja check-pow
Diff Detail
- Repository
- rABC Bitcoin ABC
- Lint
Automatic diff as part of commit; lint not applicable. - Unit
Automatic diff as part of commit; unit tests not applicable.
Event Timeline
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. |
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 |
- 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.
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. |
src/pow/grasberg.cpp | ||
---|---|---|
249 ↗ | (On Diff #22518) |
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) |
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. |
Snippet of first build failure:
[0m[1;30minterface_rest.py | ○ Skipped | 0 s [0m[1;30mmempool_accept.py | ○ Skipped | 0 s [0m[1;30mmempool_limit.py | ○ Skipped | 0 s [0m[1;30mmempool_packages.py | ○ Skipped | 0 s [0m[1;30mmempool_persist.py | ○ Skipped | 0 s [0m[1;30mmempool_reorg.py | ○ Skipped | 0 s [0m[1;30mmempool_resurrect.py | ○ Skipped | 0 s [0m[1;30mmempool_spend_coinbase.py | ○ Skipped | 0 s [0m[1;30mmining_prioritisetransaction.py | ○ Skipped | 0 s [0m[1;30mp2p_compactblocks.py | ○ Skipped | 0 s [0m[1;30mp2p_feefilter.py | ○ Skipped | 0 s [0m[1;30mp2p_leak_tx.py | ○ Skipped | 0 s [0m[1;30mrpc_createmultisig.py | ○ Skipped | 0 s [0m[1;30mrpc_estimatefee.py | ○ Skipped | 0 s [0m[1;30mrpc_psbt.py | ○ Skipped | 0 s [0m[1;30mrpc_scantxoutset.py | ○ Skipped | 0 s [0m[1;30mrpc_signmessage.py | ○ Skipped | 0 s [0m[1;30mrpc_signrawtransaction.py | ○ Skipped | 0 s [0m[1;30mrpc_txoutproof.py | ○ Skipped | 0 s [0m[1;30mtool_wallet.py | ○ Skipped | 0 s [0m[1;30mwallet_abandonconflict.py | ○ Skipped | 0 s [0m[1;30mwallet_address_types.py | ○ Skipped | 0 s [0m[1;30mwallet_avoidreuse.py | ○ Skipped | 0 s [0m[1;30mwallet_backup.py | ○ Skipped | 0 s [0m[1;30mwallet_balance.py | ○ Skipped | 0 s [0m[1;30mwallet_basic.py | ○ Skipped | 0 s [0m[1;30mwallet_create_tx.py | ○ Skipped | 0 s [0m[1;30mwallet_createwallet.py | ○ Skipped | 0 s [0m[1;30mwallet_createwallet.py --usecli | ○ Skipped | 0 s [0m[1;30mwallet_dump.py | ○ Skipped | 0 s [0m[1;30mwallet_encryption.py | ○ Skipped | 0 s [0m[1;30mwallet_groups.py | ○ Skipped | 0 s [0m[1;30mwallet_hd.py | ○ Skipped | 0 s [0m[1;30mwallet_import_rescan.py | ○ Skipped | 0 s [0m[1;30mwallet_import_with_label.py | ○ Skipped | 0 s [0m[1;30mwallet_importmulti.py | ○ Skipped | 0 s [0m[1;30mwallet_importprunedfunds.py | ○ Skipped | 0 s [0m[1;30mwallet_keypool.py | ○ Skipped | 0 s [0m[1;30mwallet_keypool_topup.py | ○ Skipped | 0 s [0m[1;30mwallet_labels.py | ○ Skipped | 0 s [0m[1;30mwallet_listreceivedby.py | ○ Skipped | 0 s [0m[1;30mwallet_listsinceblock.py | ○ Skipped | 0 s [0m[1;30mwallet_listtransactions.py | ○ Skipped | 0 s [0m[1;30mwallet_multiwallet.py | ○ Skipped | 0 s [0m[1;30mwallet_multiwallet.py --usecli | ○ Skipped | 0 s [0m[1;30mwallet_resendwallettransactions.py | ○ Skipped | 0 s [0m[1;30mwallet_txn_clone.py | ○ Skipped | 0 s [0m[1;30mwallet_txn_clone.py --mineblock | ○ Skipped | 0 s [0m[1;30mwallet_txn_doublespend.py | ○ Skipped | 0 s [0m[1;30mwallet_txn_doublespend.py --mineblock | ○ Skipped | 0 s [0m[1;30mwallet_zapwallettxes.py | ○ Skipped | 0 s [0m[0;31mp2p_timeouts.py | ✖ Failed | 11 s [0m[0;31m[1m ALL | ✖ Failed | 277 s (accumulated) [0m[0mRuntime: 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
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 :) Beware that this diff doesn't delete all old lines. Is there a way to do a proper multi-line diff in phabricator? |
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
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: 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: 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] 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 |