diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -534,6 +534,7 @@ policy/settings.cpp pow/daa.cpp pow/eda.cpp + pow/grasberg.cpp pow/pow.cpp rest.cpp rpc/abc.cpp diff --git a/src/Makefile.am b/src/Makefile.am --- a/src/Makefile.am +++ b/src/Makefile.am @@ -201,7 +201,9 @@ policy/settings.h \ pow/daa.h \ pow/eda.h \ + pow/grasberg.h \ pow/pow.h \ + pow/util.h \ protocol.h \ psbt.h \ radix.h \ @@ -338,6 +340,7 @@ policy/settings.cpp \ pow/daa.cpp \ pow/eda.cpp \ + pow/grasberg.cpp \ pow/pow.cpp \ rest.cpp \ rpc/abc.cpp \ diff --git a/src/Makefile.test.include b/src/Makefile.test.include --- a/src/Makefile.test.include +++ b/src/Makefile.test.include @@ -119,6 +119,7 @@ avalanche/test/proof_tests.cpp \ pow/test/daa_tests.cpp \ pow/test/eda_tests.cpp \ + pow/test/grasberg_tests.cpp \ test/scriptnum10.h \ test/activation_tests.cpp \ test/addrman_tests.cpp \ diff --git a/src/pow/daa.cpp b/src/pow/daa.cpp --- a/src/pow/daa.cpp +++ b/src/pow/daa.cpp @@ -7,6 +7,7 @@ #include #include #include +#include /** * Compute a target based on the work done between 2 blocks and the time @@ -36,13 +37,7 @@ } work /= nActualTimespan; - - /** - * We need to compute T = (2^256 / W) - 1 but 2^256 doesn't fit in 256 bits. - * By expressing 1 as W / W, we get (2^256 - W) / W, and we can compute - * 2^256 - W as the complement of W. - */ - return (-work) / work; + return ComputeTargetFromWork(work); } /** diff --git a/src/pow/grasberg.h b/src/pow/grasberg.h new file mode 100644 --- /dev/null +++ b/src/pow/grasberg.h @@ -0,0 +1,33 @@ +// Copyright (c) 2020 The Bitcoin developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#ifndef BITCOIN_POW_GRASBERG_H +#define BITCOIN_POW_GRASBERG_H + +#include + +class CBlockHeader; +class CBlockIndex; +class CChainParams; + +uint32_t GetNextGrasbergWorkRequired(const CBlockIndex *pindexPrev, + const CBlockHeader *pblock, + const CChainParams &chainParams); + +namespace grasberg { + +/** + * Compute the block time we are aiming for. + */ +int64_t computeTargetBlockTime(const CBlockIndex *pindexPrev, + const CChainParams &chainParams); + +/** + * Computes exp2(n) = 2^32 * (2^(n/2^32) - 1) + */ +uint32_t deterministicExp2(const uint32_t n); + +} // namespace grasberg + +#endif // BITCOIN_POW_GRASBERG_H diff --git a/src/pow/grasberg.cpp b/src/pow/grasberg.cpp new file mode 100644 --- /dev/null +++ b/src/pow/grasberg.cpp @@ -0,0 +1,256 @@ +// Copyright (c) 2020 The Bitcoin developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include + +#include +#include +#include +#include + +using namespace grasberg; + +// 2^32 * ln(2) = 2977044471.82 +static constexpr int64_t LN2_32 = 2977044472; + +static constexpr int64_t POW2_32 = int64_t(1) << 32; + +static arith_uint256 ComputeNextTarget(const CBlockIndex *pindexTip, + const CBlockIndex *pindexRef, + const CChainParams ¶ms) { + const int64_t targetBlockTime = computeTargetBlockTime(pindexTip, params); + const int64_t expectedBlockTime = params.GetConsensus().nPowTargetSpacing; + + const int64_t refBlockTime = pindexRef->GetBlockTime(); + const int64_t refBlockInterval = + (pindexRef->pprev == nullptr) + ? expectedBlockTime + : (refBlockTime - pindexRef->pprev->GetBlockTime()); + const int64_t refInterval = + refBlockInterval + pindexTip->GetBlockTime() - refBlockTime; + const int64_t refIntervalSize = pindexTip->nHeight - pindexRef->nHeight; + const int64_t timeOffset = + refInterval - (targetBlockTime + refIntervalSize * expectedBlockTime); + + // Compute the adjustment factor. + const int64_t tau32 = 288 * expectedBlockTime * LN2_32; + const int64_t x32 = (timeOffset * POW2_32) / (tau32 >> 32); + const int32_t xi = x32 >> 32; + const uint32_t xd = x32 & uint32_t(-1); + + /** + * Even though the correct thing to do would be to add 1 to the target, and + * then remove 1 at the end, experimentation showed that the cases in which + * the results differ are vanishingly few and we therefore skip this step. + */ + arith_uint256 lastBlockTarget; + lastBlockTarget.SetCompact(pindexRef->nBits); + + // Clip adjustment to avoid overflow. + if (xi >= 32) { + return lastBlockTarget << 32; + } else if (xi <= -32) { + return lastBlockTarget >> 32; + } + + const arith_uint256 offsetTarget32 = + lastBlockTarget * deterministicExp2(xd); + const arith_uint256 nextTarget = + xi < 0 ? (lastBlockTarget + (offsetTarget32 >> 32)) >> (-xi) + : (lastBlockTarget << xi) + (offsetTarget32 >> (32 - xi)); + + return nextTarget; +} + +/** + * Compute the next required proof of work using a reative work based ASERT + * algorithm. + * + * Because the relation between work and target is not an immediate inverse, + * this is actually the correct thing to do, even though the difference + * shouldn't be big enough to matter in practice most of the time. The algorithm + * uses a combination of lookup table and polynomial aproximation to compute the + * value of the exponential using exclusively integer operations. This removes + * any risk of consensus failure due to inconsistent rounding problems. + * + * This algorithm uses the relative formulation of ASERT in order to allow for + * activation at any point in time without complications. + * + * In addition, this algorithm contains a drift correction mechanism. While + * ASERT by itself drifts very little, the chain is already off schedule. + */ +uint32_t GetNextGrasbergWorkRequired(const CBlockIndex *pindexPrev, + const CBlockHeader *pblock, + const CChainParams &chainParams) { + const Consensus::Params ¶ms = chainParams.GetConsensus(); + const CBlockIndex *pindexTip = pindexPrev; + + if (params.fPowAllowMinDifficultyBlocks) { + // Special difficulty rule for testnet: + // If the new block's timestamp is more than 2* 10 minutes then allow + // mining of a min-difficulty block. + if (pblock->GetBlockTime() > + pindexPrev->GetBlockTime() + 2 * params.nPowTargetSpacing) { + return UintToArith256(params.powLimit).GetCompact(); + } + + // Use the last non-special-min-difficulty-rules-block as a base to + // compute difficulty. + while (pindexPrev->pprev && (pindexPrev->GetBlockTime() > + pindexPrev->pprev->GetBlockTime() + + 2 * params.nPowTargetSpacing)) { + pindexPrev = pindexPrev->pprev; + } + } + + const arith_uint256 nextTarget = + ComputeNextTarget(pindexTip, pindexPrev, chainParams); + + const arith_uint256 powLimit = UintToArith256(params.powLimit); + if (nextTarget > powLimit) { + return powLimit.GetCompact(); + } + + return nextTarget.GetCompact(); +} + +namespace grasberg { + +int64_t computeTargetBlockTime(const CBlockIndex *pindexPrev, + const CChainParams &chainParams) { + const Consensus::Params ¶ms = chainParams.GetConsensus(); + + const int64_t lastBlockTime = pindexPrev->GetBlockTime(); + const int64_t powTargetSpacing = params.nPowTargetSpacing; + const int64_t expectedTime = pindexPrev->nHeight * powTargetSpacing + + chainParams.GenesisBlock().nTime; + const int64_t drift = expectedTime - lastBlockTime; + + const int64_t tau = params.nPowTargetTimespan; + const int64_t x32 = (drift * POW2_32) / tau; + + // 2^32 * ln2(675/600) = 729822323.967 + static constexpr int64_t X_CLIP = 729822324; + + // We clip to ensure block time stay around 10 minutes in practice. + const uint32_t x = std::max(std::min(x32, X_CLIP), -X_CLIP); + + const int64_t offsetTime32 = powTargetSpacing * deterministicExp2(x); + return (powTargetSpacing + (offsetTime32 >> 32)) >> (x32 < 0); +} + +uint32_t deterministicExp2(const uint32_t n) { + /** + * Rescale the computation depending on n for better precision. + * We use the MSB to form 16 buckets. + */ + const uint32_t bucket = n >> 28; + + /** + * Rescale around the middle of the range via: + * exp2(n) = 2^32 * 2^(n/2^32) + * = 2^32 * 2^((n - d)/2^32 + d/2^32) + * = 2^32 * 2^(d/2^32) * 2^((n - d)/2^32) + * Using x = n - d: + * exp2(n) = 2^32 * 2^(d/2^32) * 2^(x/2^32) + */ + const int64_t d = int64_t(2 * bucket + 1) << 27; + const int64_t x = n - d; + + constexpr static uint32_t k0s[16] = { + // 2^32 * (2^(1/32) - 1) = 94047537.3451 + 94047537, + // 2^32 * (2^(3/32) - 1) = 288365825.147 + 288365825, + // 2^32 * (2^(5/32) - 1) = 491287318.545 + 491287319, + // 2^32 * (2^(7/32) - 1) = 703192913.992 + 703192914, + // 2^32 * (2^(9/32) - 1) = 924480371.666 + 924480372, + // 2^32 * (2^(11/32) - 1) = 1155565062.10 + 1155565062, + // 2^32 * (2^(13/32) - 1) = 1396880745.83 + 1396880746, + // 2^32 * (2^(15/32) - 1) = 1648880387.65 + 1648880388, + // 2^32 * (2^(17/32) - 1) = 1912037006.77 + 1912037007, + // 2^32 * (2^(19/32) - 1) = 2186844564.80 + 2186844565, + // 2^32 * (2^(21/32) - 1) = 2473818892.86 + 2473818893, + // 2^32 * (2^(23/32) - 1) = 2773498659.88 + 2773498660, + // 2^32 * (2^(25/32) - 1) = 3086446383.71 + 3086446384, + // 2^32 * (2^(27/32) - 1) = 3413249486.97 + 3413249487, + // 2^32 * (2^(29/32) - 1) = 3754521399.73 + 3754521400, + // 2^32 * (2^(31/32) - 1) = 4110902710.89 + 4110902711, + }; + const uint32_t k0 = k0s[bucket]; + + constexpr int64_t k1s[16] = { + // 2^32 * ln(2) * 2^(1/32) = 3042233257.17 + 3042233257, + // 2^32 * ln(2) * 2^(3/32) = 3176924430.49 + 3176924430, + // 2^32 * ln(2) * 2^(5/32) = 3317578891.51 + 3317578892, + // 2^32 * ln(2) * 2^(7/32) = 3464460657.54 + 3464460658, + // 2^32 * ln(2) * 2^(9/32) = 3617845434.92 + 3617845435, + // 2^32 * ln(2) * 2^(11/32) = 3778021136.56 + 3778021137, + // 2^32 * ln(2) * 2^(13/32) = 3945288422.37 + 3945288422, + // 2^32 * ln(2) * 2^(15/32) = 4119961263.60 + 4119961264, + // 2^32 * ln(2) * 2^(17/32) = 4302367532.19 + 4302367532, + // 2^32 * ln(2) * 2^(19/32) = 4492849616.23 + 4492849616, + // 2^32 * ln(2) * 2^(21/32) = 4691765062.62 + 4691765063, + // 2^32 * ln(2) * 2^(23/32) = 4899487248.21 + 4899487248, + // 2^32 * ln(2) * 2^(25/32) = 5116406080.64 + 5116406081, + // 2^32 * ln(2) * 2^(27/32) = 5342928730.26 + 5342928730, + // 2^32 * ln(2) * 2^(29/32) = 5579480394.39 + 5579480394, + // 2^32 * ln(2) * 2^(31/32) = 5826505095.43 + 5826505095, + }; + const int64_t k1 = k1s[bucket]; + + /** + * /!\ C++ right shift signedness handling is implementation defined. It is + * defined as an arithmetic on all the platform we support, but this + * may not be the case on other platforms. + * + * NB: C++20 defines signed right shift as being arithmetic shifts, so in + * practice, we should see all platforms converge toward that behavior if + * they haven't already. + */ + static_assert( + (int64_t(-1) >> 1) == int64_t(-1), + "deterministicExp2 require a compiler using arithmetic right shift."); + + /** + * Now we aproximate the result using a taylor series. + */ + const int64_t u0 = k0; + const int64_t u1_31 = (x * k1) >> 1; + const int64_t u2_31 = (((x * LN2_32) >> 32) * ((x * k1) >> 32)) >> 2; + + return u0 + ((u1_31 + u2_31) >> 31); +} + +} // namespace grasberg diff --git a/src/pow/pow.cpp b/src/pow/pow.cpp --- a/src/pow/pow.cpp +++ b/src/pow/pow.cpp @@ -13,6 +13,7 @@ #include #include #include +#include #include #include @@ -29,6 +30,10 @@ return pindexPrev->nBits; } + if (IsAxionEnabled(params, pindexPrev)) { + return GetNextGrasbergWorkRequired(pindexPrev, pblock, chainParams); + } + if (IsDAAEnabled(params, pindexPrev)) { return GetNextDAAWorkRequired(pindexPrev, pblock, params); } diff --git a/src/pow/test/CMakeLists.txt b/src/pow/test/CMakeLists.txt --- a/src/pow/test/CMakeLists.txt +++ b/src/pow/test/CMakeLists.txt @@ -14,6 +14,7 @@ TESTS daa_tests.cpp eda_tests.cpp + grasberg_tests.cpp ) target_link_libraries(test-pow server testutil) diff --git a/src/pow/test/grasberg_tests.cpp b/src/pow/test/grasberg_tests.cpp new file mode 100644 --- /dev/null +++ b/src/pow/test/grasberg_tests.cpp @@ -0,0 +1,667 @@ +// Copyright (c) 2015-2019 The Bitcoin Core developers +// Distributed under the MIT/X11 software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include + +#include +#include +#include + +#include + +#include + +#include + +using namespace grasberg; + +BOOST_FIXTURE_TEST_SUITE(grasberg_tests, BasicTestingSetup) + +BOOST_AUTO_TEST_CASE(exp2_test) { + BOOST_CHECK_EQUAL(deterministicExp2(0), 7393); + BOOST_CHECK_EQUAL(deterministicExp2(1), 7394); + BOOST_CHECK_EQUAL(deterministicExp2(42), 7423); + BOOST_CHECK_EQUAL(deterministicExp2(0x000ff1ce), 731582); + BOOST_CHECK_EQUAL(deterministicExp2(0x0badf00d), 137990841); + BOOST_CHECK_EQUAL(deterministicExp2(0x7fffffff), 1779023580); + BOOST_CHECK_EQUAL(deterministicExp2(0x80000000), 1779044161); + BOOST_CHECK_EQUAL(deterministicExp2(0xdeadbeef), 3553899602); + BOOST_CHECK_EQUAL(deterministicExp2(0xfeedcafe), 4270081780); + BOOST_CHECK_EQUAL(deterministicExp2(0xffffffff), 4294952978); + + // 100 randomly picked values. + BOOST_CHECK_EQUAL(deterministicExp2(0x087ae9b4), 0x05f22ba0); + BOOST_CHECK_EQUAL(deterministicExp2(0x5425cdf3), 0x41818d38); + BOOST_CHECK_EQUAL(deterministicExp2(0x8dbb6e9b), 0x77c0bcac); + BOOST_CHECK_EQUAL(deterministicExp2(0xc72cd267), 0xb6fc25e6); + BOOST_CHECK_EQUAL(deterministicExp2(0x9a67c66f), 0x84ded7e2); + BOOST_CHECK_EQUAL(deterministicExp2(0x94667388), 0x7e994a68); + BOOST_CHECK_EQUAL(deterministicExp2(0x589c28c9), 0x456a0034); + BOOST_CHECK_EQUAL(deterministicExp2(0x54a063f8), 0x41ec5408); + BOOST_CHECK_EQUAL(deterministicExp2(0xe4741ebb), 0xdb33b593); + BOOST_CHECK_EQUAL(deterministicExp2(0xed6e1573), 0xe6e48bf4); + BOOST_CHECK_EQUAL(deterministicExp2(0xd74a77d8), 0xca90720f); + BOOST_CHECK_EQUAL(deterministicExp2(0xe9615051), 0xe19549d0); + BOOST_CHECK_EQUAL(deterministicExp2(0x4b52afdf), 0x39ea3f2e); + BOOST_CHECK_EQUAL(deterministicExp2(0x9c23c8e3), 0x86b36ce3); + BOOST_CHECK_EQUAL(deterministicExp2(0x7e3b8bb5), 0x684f5d58); + BOOST_CHECK_EQUAL(deterministicExp2(0x6e2a4d01), 0x58f89c82); + BOOST_CHECK_EQUAL(deterministicExp2(0xf82b8d68), 0xf5427e5c); + BOOST_CHECK_EQUAL(deterministicExp2(0x95c28f4c), 0x80028f01); + BOOST_CHECK_EQUAL(deterministicExp2(0x7e7814bf), 0x688a6e8c); + BOOST_CHECK_EQUAL(deterministicExp2(0x315df77b), 0x249c7b94); + BOOST_CHECK_EQUAL(deterministicExp2(0x64c8d384), 0x5051d896); + BOOST_CHECK_EQUAL(deterministicExp2(0x7e60ec44), 0x6873d4b9); + BOOST_CHECK_EQUAL(deterministicExp2(0x3b8b004f), 0x2cc8ff8f); + BOOST_CHECK_EQUAL(deterministicExp2(0x444c4ea5), 0x34002acc); + BOOST_CHECK_EQUAL(deterministicExp2(0x80759f4a), 0x6a7d67d3); + BOOST_CHECK_EQUAL(deterministicExp2(0xe7e46027), 0xdfa591b5); + BOOST_CHECK_EQUAL(deterministicExp2(0x487b844b), 0x3782900e); + BOOST_CHECK_EQUAL(deterministicExp2(0xdd45a3f4), 0xd20cfc89); + BOOST_CHECK_EQUAL(deterministicExp2(0x3e03f2ea), 0x2ece2945); + BOOST_CHECK_EQUAL(deterministicExp2(0xe69e7c49), 0xddff112d); + BOOST_CHECK_EQUAL(deterministicExp2(0x2901bda5), 0x1e0fcf06); + BOOST_CHECK_EQUAL(deterministicExp2(0x196a8489), 0x123cc6c2); + BOOST_CHECK_EQUAL(deterministicExp2(0x9a19b128), 0x848caa17); + BOOST_CHECK_EQUAL(deterministicExp2(0x0398cca8), 0x028162ed); + BOOST_CHECK_EQUAL(deterministicExp2(0xbef03f61), 0xad4d8523); + BOOST_CHECK_EQUAL(deterministicExp2(0x102e1734), 0x0b7701bf); + BOOST_CHECK_EQUAL(deterministicExp2(0xf363cf7b), 0xeed05b8c); + BOOST_CHECK_EQUAL(deterministicExp2(0x82c00c2d), 0x6cbeab65); + BOOST_CHECK_EQUAL(deterministicExp2(0xcffbcde3), 0xc1947182); + BOOST_CHECK_EQUAL(deterministicExp2(0x18d6f2fe), 0x11cf49ee); + BOOST_CHECK_EQUAL(deterministicExp2(0xde1ea615), 0xd31f1b8d); + BOOST_CHECK_EQUAL(deterministicExp2(0x0e96d48f), 0x0a5088c1); + BOOST_CHECK_EQUAL(deterministicExp2(0x378fa034), 0x298f4811); + BOOST_CHECK_EQUAL(deterministicExp2(0x857061ec), 0x6f68e635); + BOOST_CHECK_EQUAL(deterministicExp2(0xc8408fdd), 0xb8445ed3); + BOOST_CHECK_EQUAL(deterministicExp2(0x09c3db93), 0x06dbe0e5); + BOOST_CHECK_EQUAL(deterministicExp2(0x128598df), 0x0d2a783b); + BOOST_CHECK_EQUAL(deterministicExp2(0x7fa9d335), 0x69b5543c); + BOOST_CHECK_EQUAL(deterministicExp2(0x1177f216), 0x0c66415a); + BOOST_CHECK_EQUAL(deterministicExp2(0xa7b1dfcd), 0x931e2c20); + BOOST_CHECK_EQUAL(deterministicExp2(0xb0be2271), 0x9d1db131); + BOOST_CHECK_EQUAL(deterministicExp2(0x665c61aa), 0x51c21bf0); + BOOST_CHECK_EQUAL(deterministicExp2(0xe4472200), 0xdaf9d7b6); + BOOST_CHECK_EQUAL(deterministicExp2(0x9ba928c3), 0x8631cba4); + BOOST_CHECK_EQUAL(deterministicExp2(0xd1464a98), 0xc327c0e8); + BOOST_CHECK_EQUAL(deterministicExp2(0x64a0901d), 0x502d30d2); + BOOST_CHECK_EQUAL(deterministicExp2(0x636df03b), 0x4f168f27); + BOOST_CHECK_EQUAL(deterministicExp2(0x61bf5d3f), 0x4d90d5fc); + BOOST_CHECK_EQUAL(deterministicExp2(0xa8bf3caa), 0x944498be); + BOOST_CHECK_EQUAL(deterministicExp2(0x683ed475), 0x537c713f); + BOOST_CHECK_EQUAL(deterministicExp2(0xb375673c), 0xa02a26da); + BOOST_CHECK_EQUAL(deterministicExp2(0xcd1e7fa3), 0xbe1b6498); + BOOST_CHECK_EQUAL(deterministicExp2(0x8d064b3f), 0x7708a4f8); + BOOST_CHECK_EQUAL(deterministicExp2(0x83148fe1), 0x6d1229fe); + BOOST_CHECK_EQUAL(deterministicExp2(0xbee2c2b4), 0xad3dd8c8); + BOOST_CHECK_EQUAL(deterministicExp2(0x8f39659e), 0x79461245); + BOOST_CHECK_EQUAL(deterministicExp2(0x0cc3e1a5), 0x0900b2ca); + BOOST_CHECK_EQUAL(deterministicExp2(0xc41798fb), 0xb35600ec); + BOOST_CHECK_EQUAL(deterministicExp2(0x4dc8ef08), 0x3c03ad99); + BOOST_CHECK_EQUAL(deterministicExp2(0x00171815), 0x00101e5c); + BOOST_CHECK_EQUAL(deterministicExp2(0xdb6c9075), 0xcfb98d72); + BOOST_CHECK_EQUAL(deterministicExp2(0x13cd960c), 0x0e19e68c); + BOOST_CHECK_EQUAL(deterministicExp2(0x9e19dd37), 0x88c7eb2c); + BOOST_CHECK_EQUAL(deterministicExp2(0x3afa11d6), 0x2c530f55); + BOOST_CHECK_EQUAL(deterministicExp2(0x03867141), 0x02748a3a); + BOOST_CHECK_EQUAL(deterministicExp2(0x65b991fe), 0x512d588a); + BOOST_CHECK_EQUAL(deterministicExp2(0x8960fee9), 0x7359a227); + BOOST_CHECK_EQUAL(deterministicExp2(0x06302a65), 0x04534fd5); + BOOST_CHECK_EQUAL(deterministicExp2(0x9ab4e776), 0x85301592); + BOOST_CHECK_EQUAL(deterministicExp2(0xd5c11fed), 0xc8a915a9); + BOOST_CHECK_EQUAL(deterministicExp2(0xcd325145), 0xbe3354ff); + BOOST_CHECK_EQUAL(deterministicExp2(0x45dd5919), 0x354f4ffc); + BOOST_CHECK_EQUAL(deterministicExp2(0xa5074b00), 0x9037d65d); + BOOST_CHECK_EQUAL(deterministicExp2(0x19139f48), 0x11fc48be); + BOOST_CHECK_EQUAL(deterministicExp2(0x0ef74095), 0x0a9615eb); + BOOST_CHECK_EQUAL(deterministicExp2(0x6d1ae43b), 0x57fb7ec5); + BOOST_CHECK_EQUAL(deterministicExp2(0x021946f0), 0x01758480); + BOOST_CHECK_EQUAL(deterministicExp2(0xcae745a8), 0xbb705790); + BOOST_CHECK_EQUAL(deterministicExp2(0x47572522), 0x368c5805); + BOOST_CHECK_EQUAL(deterministicExp2(0x576843af), 0x445b2876); + BOOST_CHECK_EQUAL(deterministicExp2(0x5b5734e9), 0x47d432f0); + BOOST_CHECK_EQUAL(deterministicExp2(0xb504a24a), 0xa1ecef9c); + BOOST_CHECK_EQUAL(deterministicExp2(0xa99c6f97), 0x953700b8); + BOOST_CHECK_EQUAL(deterministicExp2(0xd63094c2), 0xc932f989); + BOOST_CHECK_EQUAL(deterministicExp2(0x8339e407), 0x6d3710fc); + BOOST_CHECK_EQUAL(deterministicExp2(0x79056f7b), 0x63430c2d); + BOOST_CHECK_EQUAL(deterministicExp2(0xee327961), 0xe7e7b02e); + BOOST_CHECK_EQUAL(deterministicExp2(0x89c5e1a0), 0x73bf1fc2); + BOOST_CHECK_EQUAL(deterministicExp2(0x1f28adf5), 0x1688db92); + BOOST_CHECK_EQUAL(deterministicExp2(0x74abd815), 0x5f1a2b1d); + + // Check a ton of random values. + MMIXLinearCongruentialGenerator lcg; + for (int i = 0; i < 100000; i++) { + static constexpr int64_t POW2_32 = int64_t(1) << 32; + + const uint32_t n = lcg.next(); + const double d = double(n) / POW2_32; + + const double computed = double(deterministicExp2(n)) / POW2_32; + const double expected = exp2(d) - 1; + + BOOST_CHECK(fabs(computed - expected) < 0.0000034); + } +} + +BOOST_AUTO_TEST_CASE(target_block_time_test) { + const auto chainParams = CreateChainParams(CBaseChainParams::MAIN); + const auto ¶ms = chainParams->GetConsensus(); + + const int nHeight = 100000; + const int64_t expectedBlockTime = + nHeight * params.nPowTargetSpacing + chainParams->GenesisBlock().nTime; + + CBlockIndex block; + block.nHeight = nHeight; + block.nTime = expectedBlockTime; + + // When block come on schedule, the block time is what we expect. + BOOST_CHECK_EQUAL(computeTargetBlockTime(&block, *chainParams), + params.nPowTargetSpacing); + + // As block come later and later, the block time we target gets shorter. + int64_t currentTarget = params.nPowTargetSpacing; + std::vector downSteps = { + 2908, 2916, 2921, 2926, 2931, 2936, 2940, 2946, 2950, 2955, 2961, + 2965, 2970, 2976, 2980, 2986, 2991, 2996, 3001, 3006, 3012, 3017, + 3022, 3027, 3033, 3033, 3043, 3049, 3054, 3059, 3064, 3070, 3075, + 3081, 3086, 3091, 3097, 3103, 3107, 3114, 3119, 3125, 3130, 3136, + 3142, 3147, 3153, 3159, 3165, 3165, 3176, 3182, 3188, 3194, 3199, + 3205, 3211, 3217, 3223, 3228, 3235, 3241, 3246, 3253, 3259, 3265, + }; + + for (int step : downSteps) { + currentTarget--; + for (int i = 0; i < step; i++) { + block.nTime++; + BOOST_CHECK_EQUAL(computeTargetBlockTime(&block, *chainParams), + currentTarget); + } + } + + // Now we reached saturation and the targeted block time will stay where it + // is. + currentTarget--; + for (int i = 0; i < 10000; i++) { + block.nTime++; + BOOST_CHECK_EQUAL(computeTargetBlockTime(&block, *chainParams), + currentTarget); + } + + // As block come sooner and sooner, the block time we target gets longer. + block.nTime = expectedBlockTime; + currentTarget = params.nPowTargetSpacing; + std::vector upSteps = { + 2903, 2902, 2897, 2892, 2887, 2882, 2878, 2872, 2868, 2863, 2859, + 2854, 2849, 2844, 2840, 2835, 2831, 2826, 2822, 2817, 2812, 2809, + 2803, 2799, 2795, 2791, 2780, 2782, 2777, 2772, 2768, 2764, 2759, + 2755, 2750, 2747, 2741, 2738, 2733, 2729, 2724, 2721, 2716, 2712, + 2707, 2704, 2699, 2695, 2692, 2687, 2683, 2679, 2675, 2671, 2661, + 2662, 2659, 2654, 2651, 2646, 2642, 2639, 2634, 2630, 2626, 2622, + 2619, 2614, 2611, 2606, 2603, 2599, 2595, 2591, + }; + + for (int step : upSteps) { + for (int i = 0; i < step; i++) { + block.nTime--; + BOOST_CHECK_EQUAL(computeTargetBlockTime(&block, *chainParams), + currentTarget); + } + currentTarget++; + } + + // Now we reached saturation and the targeted block time will stay where it + // is. + for (int i = 0; i < 10000; i++) { + block.nTime--; + BOOST_CHECK_EQUAL(computeTargetBlockTime(&block, *chainParams), + currentTarget); + } +} + +static CBlockIndex GetBlockIndex(CBlockIndex *pindexPrev, int64_t nTimeInterval, + uint32_t nBits) { + CBlockIndex block; + block.pprev = pindexPrev; + block.nHeight = pindexPrev->nHeight + 1; + block.nTime = pindexPrev->nTime + nTimeInterval; + block.nBits = nBits; + + block.nChainWork = pindexPrev->nChainWork + GetBlockProof(block); + return block; +} + +BOOST_AUTO_TEST_CASE(grasberg_test) { + const auto chainParams = CreateChainParams(CBaseChainParams::MAIN); + const auto ¶ms = chainParams->GetConsensus(); + + std::vector blocks(3000); + + const arith_uint256 powLimit = UintToArith256(params.powLimit); + uint32_t powLimitBits = powLimit.GetCompact(); + arith_uint256 currentPow = powLimit >> 4; + uint32_t initialBits = currentPow.GetCompact(); + + // Genesis block. + blocks[0] = CBlockIndex(); + blocks[0].nHeight = 0; + blocks[0].nTime = 1269211443; + blocks[0].nBits = initialBits; + + blocks[0].nChainWork = GetBlockProof(blocks[0]); + + // Check that we can use Grasberg directly from genesis. + CBlockHeader blkHeaderDummy; + uint32_t nBits = + GetNextGrasbergWorkRequired(&blocks[0], &blkHeaderDummy, *chainParams); + BOOST_CHECK_EQUAL(nBits, 0x1c100197); + + // Mine sevral blocks and check the difficulty. + size_t h = 1; + + // Mine regular 600s blocks. + std::vector diffs = { + 0x1c10032f, 0x1c1004c7, 0x1c10065f, 0x1c1007f7, 0x1c100990, 0x1c100b29, + 0x1c100cc2, 0x1c100e5b, 0x1c100ff4, 0x1c10118d, 0x1c101327, 0x1c1014c1, + 0x1c10165b, 0x1c1017f5, 0x1c10198f, 0x1c101b29, 0x1c101cc4, 0x1c101e5f, + 0x1c101ffa, 0x1c102195, 0x1c102330, 0x1c1024cb, 0x1c102667, 0x1c102803, + 0x1c10299f, 0x1c102b3b, 0x1c102cd7, 0x1c102e73, 0x1c10300f, 0x1c1031ac, + 0x1c103349, 0x1c1034e6, 0x1c103683, 0x1c103820, 0x1c1039bd, 0x1c103b5b, + 0x1c103cf9, 0x1c103e97, 0x1c104035, 0x1c1041d3, 0x1c104371, 0x1c104510, + 0x1c1046af, 0x1c10484e, 0x1c1049ed, 0x1c104b8c, 0x1c104d2b, 0x1c104ecb, + 0x1c10506b, 0x1c10520b, 0x1c1053ab, 0x1c10554b, 0x1c1056eb, 0x1c10588c, + 0x1c105a2d, 0x1c105bce, 0x1c105d6f, 0x1c105f10, 0x1c1060b1, 0x1c106252, + 0x1c1063f4, 0x1c106596, 0x1c106738, 0x1c1068da, 0x1c106a7c, 0x1c106c1e, + 0x1c106dc1, 0x1c106f64, 0x1c107107, 0x1c1072aa, 0x1c10744d, 0x1c1075f0, + 0x1c107794, 0x1c107938, 0x1c107adc, 0x1c107c80, 0x1c107e24, 0x1c107fc8, + 0x1c10816d, 0x1c108312, 0x1c1084b7, 0x1c10865c, 0x1c108801, 0x1c1089a6, + 0x1c108b4c, 0x1c108cf2, 0x1c108e98, 0x1c10903e, 0x1c1091e4, 0x1c10938a, + 0x1c109531, 0x1c1096d8, 0x1c10987f, 0x1c109a26, 0x1c109bcd, 0x1c109d74, + 0x1c109f1c, 0x1c10a0c4, 0x1c10a26c, 0x1c10a414, 0x1c10a5bc, 0x1c10a764, + 0x1c10a90d, 0x1c10aab6, 0x1c10ac5f, 0x1c10ae08, 0x1c10afb1, 0x1c10b15a, + 0x1c10b304, 0x1c10b4ae, 0x1c10b658, 0x1c10b802, 0x1c10b9ac, 0x1c10bb56, + 0x1c10bd01, 0x1c10beac, 0x1c10c057, 0x1c10c202, 0x1c10c3ad, 0x1c10c558, + 0x1c10c704, 0x1c10c8b0, 0x1c10ca5c, 0x1c10cc08, 0x1c10cdb4, 0x1c10cf60, + 0x1c10d10d, 0x1c10d2ba, 0x1c10d467, 0x1c10d614, 0x1c10d7c1, 0x1c10d96e, + 0x1c10db1c, 0x1c10dcca, 0x1c10de78, 0x1c10e026, 0x1c10e1d4, 0x1c10e382, + 0x1c10e531, 0x1c10e6e0, 0x1c10e88f, 0x1c10ea3e, 0x1c10ebed, 0x1c10ed9c, + 0x1c10ef4c, 0x1c10f0fc, 0x1c10f2ac, 0x1c10f45c, 0x1c10f60c, 0x1c10f7bc, + 0x1c10f96d, 0x1c10fb1e, 0x1c10fccf, 0x1c10fe80, 0x1c110031, 0x1c1101e2, + 0x1c110394, 0x1c110546, 0x1c1106f8, 0x1c1108aa, 0x1c110a5c, 0x1c110c0e, + 0x1c110dc1, 0x1c110f74, 0x1c111127, 0x1c1112da, 0x1c11148d, 0x1c111640, + 0x1c1117f4, 0x1c1119a8, 0x1c111b5c, 0x1c111d10, 0x1c111ec4, 0x1c112078, + 0x1c11222d, 0x1c1123e2, 0x1c112597, 0x1c11274c, 0x1c112901, 0x1c112ab6, + 0x1c112c6c, 0x1c112e22, 0x1c112fd8, 0x1c11318e, 0x1c113344, 0x1c1134fa, + 0x1c1136b1, 0x1c113868, 0x1c113a1f, 0x1c113bd6, 0x1c113d8d, 0x1c113f45, + 0x1c1140fd, 0x1c1142b5, 0x1c11446d, 0x1c114625, 0x1c1147dd, 0x1c114996, + 0x1c114b4f, 0x1c114d08, 0x1c114ec1, 0x1c11507a, 0x1c115233, 0x1c1153ed, + 0x1c1155a7, 0x1c115761, 0x1c11591b, 0x1c115ad5, 0x1c115c8f, 0x1c115e4a, + 0x1c116005, 0x1c1161c0, 0x1c11637b, 0x1c116536, 0x1c1166f1, 0x1c1168ad, + 0x1c116a69, 0x1c116c25, 0x1c116de1, 0x1c116f9d, 0x1c11715a, 0x1c117317, + 0x1c1174d4, 0x1c117691, 0x1c11784e, 0x1c117a0b, 0x1c117bc9, 0x1c117d87, + 0x1c117f45, 0x1c118103, 0x1c1182c1, 0x1c11847f, 0x1c11863e, 0x1c1187fd, + 0x1c1189bc, 0x1c118b7b, 0x1c118d3a, 0x1c118ef9, 0x1c1190b9, 0x1c119279, + 0x1c119439, 0x1c1195f9, 0x1c1197b9, 0x1c11997a, 0x1c119b3b, 0x1c119cfc, + 0x1c119ebd, 0x1c11a07e, 0x1c11a23f, 0x1c11a401, 0x1c11a5c3, 0x1c11a785, + 0x1c11a947, 0x1c11ab09, 0x1c11accb, 0x1c11ae8e, 0x1c11b051, 0x1c11b214, + 0x1c11b3d7, 0x1c11b59a, 0x1c11b75d, 0x1c11b921, 0x1c11bae5, 0x1c11bca9, + 0x1c11be6d, 0x1c11c031, 0x1c11c1f6, 0x1c11c3bb, 0x1c11c580, 0x1c11c745, + 0x1c11c90a, 0x1c11cacf, 0x1c11cc95, 0x1c11ce5b, 0x1c11d021, 0x1c11d1e7, + 0x1c11d3ad, 0x1c11d573, 0x1c11d73a, 0x1c11d901, 0x1c11dac8, 0x1c11dc8f, + 0x1c11de56, 0x1c11e01e, 0x1c11e1e6, 0x1c11e3ae, 0x1c11e576, 0x1c11e73e, + 0x1c11e906, 0x1c11eacf, 0x1c11ec98, 0x1c11ee61, 0x1c11f02a, 0x1c11f1f3, + 0x1c11f3bd, 0x1c11f587, 0x1c11f751, 0x1c11f91b, 0x1c11fae5, 0x1c11fcaf, + }; + + for (uint32_t expected : diffs) { + blocks[h] = GetBlockIndex(&blocks[h - 1], 600, nBits); + nBits = GetNextGrasbergWorkRequired(&blocks[h], &blkHeaderDummy, + *chainParams); + BOOST_CHECK_EQUAL(nBits, expected); + h++; + } + + // Mine faster to raise difficulty. + diffs = { + 0x1c11f127, 0x1c11e5a6, 0x1c11da2d, 0x1c11cebb, 0x1c11c350, 0x1c11b7ed, + 0x1c11ac91, 0x1c11a13c, 0x1c1195ef, 0x1c118aa9, 0x1c117f6a, 0x1c117432, + 0x1c116901, 0x1c115dd8, 0x1c1152b6, 0x1c11479b, 0x1c113c87, 0x1c11317a, + 0x1c112674, 0x1c111b75, 0x1c11107d, 0x1c11058c, 0x1c10faa2, 0x1c10efbf, + 0x1c10e4e3, 0x1c10da0e, 0x1c10cf40, 0x1c10c479, 0x1c10b9b9, 0x1c10af00, + 0x1c10a44e, 0x1c1099a3, 0x1c108eff, 0x1c108461, 0x1c1079ca, 0x1c106f3a, + 0x1c1064b1, 0x1c105a2f, 0x1c104fb3, 0x1c10453e, 0x1c103ad0, 0x1c103068, + 0x1c102607, 0x1c101bad, 0x1c101159, 0x1c10070c, 0x1c0ffcc6, 0x1c0ff286, + 0x1c0fe84d, 0x1c0fde1a, 0x1c0fd3ee, 0x1c0fc9c8, 0x1c0fbfa9, 0x1c0fb590, + 0x1c0fab7e, 0x1c0fa172, 0x1c0f976d, 0x1c0f8d6e, 0x1c0f8375, 0x1c0f7983, + 0x1c0f6f97, 0x1c0f65b2, 0x1c0f5bd3, 0x1c0f51fa, 0x1c0f4828, 0x1c0f3e5c, + 0x1c0f3496, 0x1c0f2ad6, 0x1c0f211d, 0x1c0f176a, 0x1c0f0dbd, 0x1c0f0416, + 0x1c0efa76, 0x1c0ef0dc, 0x1c0ee748, 0x1c0eddba, 0x1c0ed432, 0x1c0ecab0, + 0x1c0ec134, 0x1c0eb7be, 0x1c0eae4e, 0x1c0ea4e5, 0x1c0e9b82, 0x1c0e9225, + 0x1c0e88ce, 0x1c0e7f7d, 0x1c0e7632, 0x1c0e6cec, 0x1c0e63ac, 0x1c0e5a72, + 0x1c0e513e, 0x1c0e4810, 0x1c0e3ee8, 0x1c0e35c6, 0x1c0e2caa, 0x1c0e2394, + 0x1c0e1a83, 0x1c0e1178, 0x1c0e0873, 0x1c0dff74, 0x1c0df67b, 0x1c0ded87, + 0x1c0de499, 0x1c0ddbb1, 0x1c0dd2cf, 0x1c0dc9f2, 0x1c0dc11b, 0x1c0db84a, + 0x1c0daf7e, 0x1c0da6b8, 0x1c0d9df7, 0x1c0d953c, 0x1c0d8c87, 0x1c0d83d7, + 0x1c0d7b2d, 0x1c0d7288, 0x1c0d69e9, 0x1c0d614f, 0x1c0d58bb, 0x1c0d502c, + 0x1c0d47a3, 0x1c0d3f1f, 0x1c0d36a1, 0x1c0d2e28, 0x1c0d25b5, 0x1c0d1d47, + 0x1c0d14df, 0x1c0d0c7c, 0x1c0d041e, 0x1c0cfbc6, 0x1c0cf373, 0x1c0ceb25, + 0x1c0ce2dd, 0x1c0cda9a, 0x1c0cd25c, 0x1c0cca24, 0x1c0cc1f1, 0x1c0cb9c3, + 0x1c0cb19a, 0x1c0ca977, 0x1c0ca159, 0x1c0c9940, 0x1c0c912c, 0x1c0c891d, + 0x1c0c8114, 0x1c0c7910, 0x1c0c7111, 0x1c0c6917, 0x1c0c6122, 0x1c0c5932, + 0x1c0c5147, 0x1c0c4961, 0x1c0c4180, 0x1c0c39a4, 0x1c0c31cd, 0x1c0c29fb, + 0x1c0c222f, 0x1c0c1a68, 0x1c0c12a5, 0x1c0c0ae7, 0x1c0c032e, 0x1c0bfb7a, + 0x1c0bf3cb, 0x1c0bec21, 0x1c0be47c, 0x1c0bdcdc, 0x1c0bd541, 0x1c0bcdab, + 0x1c0bc61a, 0x1c0bbe8e, 0x1c0bb706, 0x1c0baf83, 0x1c0ba805, 0x1c0ba08c, + 0x1c0b9918, 0x1c0b91a8, 0x1c0b8a3d, 0x1c0b82d7, 0x1c0b7b76, 0x1c0b7419, + 0x1c0b6cc1, 0x1c0b656e, 0x1c0b5e1f, 0x1c0b56d5, 0x1c0b4f90, 0x1c0b4850, + 0x1c0b4114, 0x1c0b39dd, 0x1c0b32aa, 0x1c0b2b7c, 0x1c0b2453, 0x1c0b1d2e, + 0x1c0b160e, 0x1c0b0ef2, 0x1c0b07db, 0x1c0b00c8, 0x1c0af9ba, 0x1c0af2b1, + 0x1c0aebac, 0x1c0ae4ac, 0x1c0addb0, 0x1c0ad6b9, 0x1c0acfc6, 0x1c0ac8d7, + 0x1c0ac1ed, 0x1c0abb07, 0x1c0ab426, 0x1c0aad49, 0x1c0aa671, 0x1c0a9f9d, + 0x1c0a98cd, 0x1c0a9202, 0x1c0a8b3b, 0x1c0a8478, 0x1c0a7dba, 0x1c0a7700, + 0x1c0a704a, 0x1c0a6999, 0x1c0a62ec, 0x1c0a5c43, 0x1c0a559e, 0x1c0a4efe, + 0x1c0a4862, 0x1c0a41ca, 0x1c0a3b36, 0x1c0a34a7, 0x1c0a2e1c, 0x1c0a2795, + 0x1c0a2112, 0x1c0a1a93, 0x1c0a1419, 0x1c0a0da3, 0x1c0a0731, 0x1c0a00c3, + 0x1c09fa59, 0x1c09f3f3, 0x1c09ed91, 0x1c09e733, 0x1c09e0d9, 0x1c09da84, + 0x1c09d433, 0x1c09cde6, 0x1c09c79d, 0x1c09c158, 0x1c09bb17, 0x1c09b4da, + 0x1c09aea1, 0x1c09a86c, 0x1c09a23b, 0x1c099c0e, 0x1c0995e5, 0x1c098fc0, + 0x1c09899f, 0x1c098381, 0x1c097d67, 0x1c097751, 0x1c09713f, 0x1c096b31, + 0x1c096527, 0x1c095f21, 0x1c09591f, 0x1c095321, 0x1c094d26, 0x1c09472f, + 0x1c09413c, 0x1c093b4d, 0x1c093562, 0x1c092f7a, 0x1c092996, 0x1c0923b6, + 0x1c091dda, 0x1c091802, 0x1c09122d, 0x1c090c5c, 0x1c09068f, 0x1c0900c5, + 0x1c08faff, 0x1c08f53d, 0x1c08ef7f, 0x1c08e9c4, 0x1c08e40d, 0x1c08de5a, + 0x1c08d8aa, 0x1c08d2fe, 0x1c08cd56, 0x1c08c7b1, 0x1c08c210, 0x1c08bc72, + 0x1c08b6d8, 0x1c08b142, 0x1c08abaf, 0x1c08a620, 0x1c08a094, 0x1c089b0c, + 0x1c089587, 0x1c089006, 0x1c088a88, 0x1c08850e, 0x1c087f97, 0x1c087a24, + }; + + for (uint32_t expected : diffs) { + blocks[h] = GetBlockIndex(&blocks[h - 1], 100, nBits); + nBits = GetNextGrasbergWorkRequired(&blocks[h], &blkHeaderDummy, + *chainParams); + BOOST_CHECK_EQUAL(nBits, expected); + h++; + } + + // Mine slow blocks to lower and saturate the diffculty. + diffs = { + 0x1c08a100, 0x1c08c88e, 0x1c08f0d2, 0x1c0919ce, 0x1c094386, 0x1c096dfd, + 0x1c099937, 0x1c09c537, 0x1c09f201, 0x1c0a1f98, 0x1c0a4e00, 0x1c0a7d3d, + 0x1c0aad52, 0x1c0ade44, 0x1c0b1016, 0x1c0b42cd, 0x1c0b766c, 0x1c0baaf8, + 0x1c0be075, 0x1c0c16e7, 0x1c0c4e52, 0x1c0c86bc, 0x1c0cc028, 0x1c0cfa9b, + 0x1c0d361a, 0x1c0d72aa, 0x1c0db050, 0x1c0def10, 0x1c0e2ef0, 0x1c0e6ff5, + 0x1c0eb224, 0x1c0ef582, 0x1c0f3a15, 0x1c0f7fe2, 0x1c0fc6ef, 0x1c100f42, + 0x1c1058e1, 0x1c10a3d1, 0x1c10f019, 0x1c113dbe, 0x1c118cc7, 0x1c11dd3b, + 0x1c122f20, 0x1c12827c, 0x1c12d756, 0x1c132db5, 0x1c1385a0, 0x1c13df1e, + 0x1c143a36, 0x1c1496f0, 0x1c14f553, 0x1c155567, 0x1c15b733, 0x1c161ac0, + 0x1c168015, 0x1c16e73a, 0x1c175038, 0x1c17bb18, 0x1c1827e2, 0x1c18969e, + 0x1c190756, 0x1c197a13, 0x1c19eede, 0x1c1a65c0, 0x1c1adec3, 0x1c1b59f1, + 0x1c1bd754, 0x1c1c56f5, 0x1c1cd8df, 0x1c1d5d1d, 0x1c1de3b9, 0x1c1e6cbe, + 0x1c1ef837, 0x1c1f8630, 0x1c2016b4, 0x1c20a9ce, 0x1c213f8b, 0x1c21d7f6, + 0x1c22731c, 0x1c231109, 0x1c23b1ca, 0x1c24556c, 0x1c24fbfc, 0x1c25a588, + 0x1c26521d, 0x1c2701c9, 0x1c27b49a, 0x1c286a9f, 0x1c2923e7, 0x1c29e080, + 0x1c2aa079, 0x1c2b63e3, 0x1c2c2acc, 0x1c2cf545, 0x1c2dc35e, 0x1c2e9528, + 0x1c2f6ab4, 0x1c304413, 0x1c312156, 0x1c320290, 0x1c32e7d2, 0x1c33d12f, + 0x1c34beba, 0x1c35b086, 0x1c36a6a7, 0x1c37a130, 0x1c38a035, 0x1c39a3cb, + 0x1c3aac07, 0x1c3bb8ff, 0x1c3ccac8, 0x1c3de178, 0x1c3efd26, 0x1c401de8, + 0x1c4143d6, 0x1c426f07, 0x1c439f94, 0x1c44d595, 0x1c461123, 0x1c475258, + 0x1c48994d, 0x1c49e61d, 0x1c4b38e3, 0x1c4c91ba, 0x1c4df0be, 0x1c4f560b, + 0x1c50c1be, 0x1c5233f4, 0x1c53accb, 0x1c552c62, 0x1c56b2d7, 0x1c58404a, + 0x1c59d4db, 0x1c5b70ab, 0x1c5d13db, 0x1c5ebe8d, 0x1c6070e3, 0x1c622b00, + 0x1c63ed08, 0x1c65b71f, 0x1c67896a, 0x1c69640e, 0x1c6b4732, 0x1c6d32fd, + 0x1c6f2797, 0x1c712527, 0x1c732bd7, 0x1c753bd1, 0x1c775540, 0x1c79784e, + 0x1c7ba528, 0x1c7ddbfb, 0x1d00801c, 0x1d008267, 0x1d0084bc, 0x1d00871c, + 0x1d008987, 0x1d008bfd, 0x1d008e7e, 0x1d00910b, 0x1d0093a3, 0x1d009647, + 0x1d0098f7, 0x1d009bb4, 0x1d009e7d, 0x1d00a153, 0x1d00a436, 0x1d00a726, + 0x1d00aa24, 0x1d00ad2f, 0x1d00b048, 0x1d00b370, 0x1d00b6a6, 0x1d00b9eb, + 0x1d00bd3f, 0x1d00c0a2, 0x1d00c415, 0x1d00c797, 0x1d00cb29, 0x1d00cecc, + 0x1d00d280, 0x1d00d644, 0x1d00da1a, 0x1d00de01, 0x1d00e1fa, 0x1d00e605, + 0x1d00ea23, 0x1d00ee54, 0x1d00f298, 0x1d00f6f0, 0x1d00fb5c, 0x1d00ffdc, + 0x1d00ffff, 0x1d00ffff, 0x1d00ffff, 0x1d00ffff, 0x1d00ffff, 0x1d00ffff, + 0x1d00ffff, 0x1d00ffff, + }; + + for (uint32_t expected : diffs) { + blocks[h] = GetBlockIndex(&blocks[h - 1], 3600, nBits); + nBits = GetNextGrasbergWorkRequired(&blocks[h], &blkHeaderDummy, + *chainParams); + BOOST_CHECK_EQUAL(nBits, expected); + h++; + } + + // We floored the difficulty. + BOOST_CHECK_EQUAL(nBits, powLimitBits); + + // Check for 0 solve time. + diffs = { + 0x1d00ff35, 0x1d00fe6b, 0x1d00fda2, 0x1d00fcd9, 0x1d00fc11, 0x1d00fb4a, + 0x1d00fa83, 0x1d00f9bd, 0x1d00f8f8, 0x1d00f833, 0x1d00f76f, 0x1d00f6ab, + 0x1d00f5e8, 0x1d00f526, 0x1d00f464, 0x1d00f3a3, 0x1d00f2e2, 0x1d00f222, + 0x1d00f163, 0x1d00f0a4, 0x1d00efe6, 0x1d00ef28, 0x1d00ee6b, 0x1d00edae, + 0x1d00ecf2, 0x1d00ec37, 0x1d00eb7c, 0x1d00eac2, 0x1d00ea08, 0x1d00e94f, + 0x1d00e896, 0x1d00e7de, 0x1d00e727, 0x1d00e670, 0x1d00e5ba, 0x1d00e504, + 0x1d00e44f, 0x1d00e39a, 0x1d00e2e6, 0x1d00e233, 0x1d00e180, 0x1d00e0ce, + 0x1d00e01c, 0x1d00df6b, 0x1d00deba, 0x1d00de0a, 0x1d00dd5a, 0x1d00dcab, + 0x1d00dbfc, 0x1d00db4e, 0x1d00daa1, 0x1d00d9f4, 0x1d00d948, 0x1d00d89c, + 0x1d00d7f1, 0x1d00d746, 0x1d00d69c, 0x1d00d5f2, 0x1d00d549, 0x1d00d4a0, + 0x1d00d3f8, 0x1d00d350, 0x1d00d2a9, 0x1d00d202, 0x1d00d15c, 0x1d00d0b6, + 0x1d00d011, 0x1d00cf6c, 0x1d00cec8, 0x1d00ce24, 0x1d00cd81, 0x1d00ccde, + 0x1d00cc3c, 0x1d00cb9a, 0x1d00caf9, 0x1d00ca58, 0x1d00c9b8, 0x1d00c918, + 0x1d00c879, 0x1d00c7da, 0x1d00c73c, 0x1d00c69e, 0x1d00c601, 0x1d00c564, + 0x1d00c4c8, 0x1d00c42c, 0x1d00c391, 0x1d00c2f6, 0x1d00c25c, 0x1d00c1c2, + 0x1d00c129, 0x1d00c090, 0x1d00bff8, 0x1d00bf60, 0x1d00bec9, 0x1d00be32, + 0x1d00bd9b, 0x1d00bd05, 0x1d00bc6f, 0x1d00bbda, 0x1d00bb45, 0x1d00bab1, + 0x1d00ba1d, 0x1d00b98a, 0x1d00b8f7, 0x1d00b865, 0x1d00b7d3, 0x1d00b742, + 0x1d00b6b1, 0x1d00b620, 0x1d00b590, 0x1d00b500, 0x1d00b471, 0x1d00b3e2, + 0x1d00b354, 0x1d00b2c6, 0x1d00b239, 0x1d00b1ac, 0x1d00b11f, 0x1d00b093, + 0x1d00b007, 0x1d00af7c, 0x1d00aef1, 0x1d00ae67, 0x1d00addd, 0x1d00ad53, + 0x1d00acca, 0x1d00ac41, 0x1d00abb9, 0x1d00ab31, 0x1d00aaa9, 0x1d00aa22, + 0x1d00a99b, 0x1d00a915, 0x1d00a88f, 0x1d00a80a, 0x1d00a785, 0x1d00a700, + 0x1d00a67c, 0x1d00a5f8, 0x1d00a575, 0x1d00a4f2, 0x1d00a46f, 0x1d00a3ed, + 0x1d00a36b, 0x1d00a2ea, 0x1d00a269, 0x1d00a1e8, 0x1d00a168, 0x1d00a0e8, + 0x1d00a069, 0x1d009fea, 0x1d009f6b, 0x1d009eed, 0x1d009e6f, 0x1d009df2, + 0x1d009d75, 0x1d009cf8, 0x1d009c7c, 0x1d009c00, 0x1d009b84, 0x1d009b09, + 0x1d009a8e, 0x1d009a14, 0x1d00999a, 0x1d009920, 0x1d0098a7, 0x1d00982e, + 0x1d0097b5, 0x1d00973d, 0x1d0096c5, 0x1d00964e, 0x1d0095d7, 0x1d009560, + 0x1d0094ea, 0x1d009474, 0x1d0093fe, 0x1d009389, 0x1d009314, 0x1d0092a0, + 0x1d00922c, 0x1d0091b8, 0x1d009145, 0x1d0090d2, 0x1d00905f, 0x1d008fed, + 0x1d008f7b, 0x1d008f09, 0x1d008e98, 0x1d008e27, 0x1d008db6, 0x1d008d46, + 0x1d008cd6, 0x1d008c66, 0x1d008bf7, 0x1d008b88, 0x1d008b19, 0x1d008aab, + 0x1d008a3d, 0x1d0089cf, 0x1d008962, 0x1d0088f5, 0x1d008888, 0x1d00881c, + 0x1d0087b0, 0x1d008744, 0x1d0086d9, 0x1d00866e, 0x1d008603, 0x1d008599, + 0x1d00852f, 0x1d0084c5, 0x1d00845c, 0x1d0083f3, 0x1d00838a, 0x1d008322, + 0x1d0082ba, 0x1d008252, 0x1d0081eb, 0x1d008184, 0x1d00811d, 0x1d0080b7, + 0x1d008051, 0x1c7febcc, 0x1c7f86e8, 0x1c7f2253, 0x1c7ebe0e, 0x1c7e5a18, + 0x1c7df671, 0x1c7d9318, 0x1c7d300d, 0x1c7ccd51, 0x1c7c6ae2, 0x1c7c08c1, + 0x1c7ba6ee, 0x1c7b4568, 0x1c7ae42f, 0x1c7a8342, 0x1c7a22a2, 0x1c79c24e, + 0x1c796246, 0x1c79028a, 0x1c78a319, 0x1c7843f3, 0x1c77e518, 0x1c778688, + 0x1c772843, 0x1c76ca48, 0x1c766c97, 0x1c760f30, 0x1c75b213, 0x1c75553f, + 0x1c74f8b5, 0x1c749c73, 0x1c74407a, 0x1c73e4ca, 0x1c738962, 0x1c732e42, + 0x1c72d36a, 0x1c7278da, 0x1c721e91, 0x1c71c48f, 0x1c716ad4, 0x1c711160, + 0x1c70b833, 0x1c705f4c, 0x1c7006ab, 0x1c6fae50, 0x1c6f563b, 0x1c6efe6b, + 0x1c6ea6e0, 0x1c6e4f9a, 0x1c6df899, 0x1c6da1dd, 0x1c6d4b65, 0x1c6cf532, + 0x1c6c9f42, 0x1c6c4996, 0x1c6bf42e, 0x1c6b9f09, 0x1c6b4a27, 0x1c6af588, + 0x1c6aa12c, 0x1c6a4d13, 0x1c69f93c, 0x1c69a5a7, 0x1c695254, 0x1c68ff43, + 0x1c68ac73, 0x1c6859e4, 0x1c680797, 0x1c67b58a, 0x1c6763be, 0x1c671233, + 0x1c66c0e8, 0x1c666fdd, 0x1c661f12, 0x1c65ce87, 0x1c657e3b, 0x1c652e2f, + }; + + for (uint32_t expected : diffs) { + blocks[h] = GetBlockIndex(&blocks[h - 1], 0, nBits); + nBits = GetNextGrasbergWorkRequired(&blocks[h], &blkHeaderDummy, + *chainParams); + BOOST_CHECK_EQUAL(nBits, expected); + h++; + } + + // Check for negative solve time. + diffs = { + 0x1c64cf72, 0x1c64710e, 0x1c641302, 0x1c63b54e, 0x1c6357f2, 0x1c62faed, + 0x1c629e3f, 0x1c6241e8, 0x1c61e5e8, 0x1c618a3e, 0x1c612eea, 0x1c60d3eb, + 0x1c607941, 0x1c601eec, 0x1c5fc4ec, 0x1c5f6b40, 0x1c5f11e8, 0x1c5eb8e4, + 0x1c5e6033, 0x1c5e07d5, 0x1c5dafca, 0x1c5d5811, 0x1c5d00aa, 0x1c5ca995, + 0x1c5c52d2, 0x1c5bfc60, 0x1c5ba63f, 0x1c5b506e, 0x1c5afaee, 0x1c5aa5be, + 0x1c5a50de, 0x1c59fc4d, 0x1c59a80b, 0x1c595418, 0x1c590074, 0x1c58ad1e, + 0x1c585a16, 0x1c58075c, 0x1c57b4ef, 0x1c5762d0, 0x1c5710fd, 0x1c56bf77, + 0x1c566e3d, 0x1c561d4f, 0x1c55ccad, 0x1c557c57, 0x1c552c4c, 0x1c54dc8c, + 0x1c548d17, 0x1c543dec, 0x1c53ef0b, 0x1c53a074, 0x1c535226, 0x1c530422, + 0x1c52b667, 0x1c5268f5, 0x1c521bcb, 0x1c51cee9, 0x1c51824f, 0x1c5135fd, + 0x1c50e9f3, 0x1c509e30, 0x1c5052b4, 0x1c50077e, 0x1c4fbc8f, 0x1c4f71e6, + 0x1c4f2783, 0x1c4edd66, 0x1c4e938e, 0x1c4e49fb, 0x1c4e00ad, 0x1c4db7a4, + 0x1c4d6edf, 0x1c4d265e, 0x1c4cde21, 0x1c4c9628, 0x1c4c4e72, 0x1c4c06ff, + 0x1c4bbfcf, 0x1c4b78e2, 0x1c4b3237, 0x1c4aebce, 0x1c4aa5a7, 0x1c4a5fc2, + 0x1c4a1a1e, 0x1c49d4bc, 0x1c498f9a, 0x1c494ab9, 0x1c490619, 0x1c48c1b9, + 0x1c487d99, 0x1c4839b9, 0x1c47f618, 0x1c47b2b7, 0x1c476f95, 0x1c472cb2, + 0x1c46ea0d, 0x1c46a7a7, 0x1c46657f, 0x1c462395, 0x1c45e1e8, 0x1c45a079, + 0x1c455f47, 0x1c451e52, 0x1c44dd9a, 0x1c449d1f, 0x1c445ce0, 0x1c441cdd, + 0x1c43dd16, 0x1c439d8b, 0x1c435e3b, 0x1c431f27, 0x1c42e04e, 0x1c42a1b0, + 0x1c42634c, 0x1c422523, 0x1c41e734, 0x1c41a97f, 0x1c416c04, 0x1c412ec2, + 0x1c40f1b9, 0x1c40b4ea, 0x1c407854, 0x1c403bf6, 0x1c3fffd1, 0x1c3fc3e4, + 0x1c3f882f, 0x1c3f4cb2, 0x1c3f116d, 0x1c3ed65f, 0x1c3e9b89, 0x1c3e60ea, + 0x1c3e2682, 0x1c3dec50, 0x1c3db255, 0x1c3d7890, 0x1c3d3f01, 0x1c3d05a8, + 0x1c3ccc85, 0x1c3c9397, 0x1c3c5adf, 0x1c3c225c, 0x1c3bea0e, 0x1c3bb1f4, + 0x1c3b7a0f, 0x1c3b425e, 0x1c3b0ae1, 0x1c3ad398, 0x1c3a9c83, 0x1c3a65a2, + 0x1c3a2ef4, 0x1c39f879, 0x1c39c231, 0x1c398c1c, 0x1c39563a, 0x1c39208a, + 0x1c38eb0c, 0x1c38b5c0, 0x1c3880a6, 0x1c384bbe, 0x1c381708, 0x1c37e283, + 0x1c37ae2f, 0x1c377a0c, 0x1c37461a, 0x1c371259, 0x1c36dec8, 0x1c36ab67, + 0x1c367836, 0x1c364535, 0x1c361264, 0x1c35dfc3, 0x1c35ad51, 0x1c357b0e, + 0x1c3548fa, 0x1c351715, 0x1c34e55f, 0x1c34b3d8, 0x1c34827f, 0x1c345154, + 0x1c342057, 0x1c33ef88, 0x1c33bee7, 0x1c338e73, 0x1c335e2d, 0x1c332e14, + 0x1c32fe28, 0x1c32ce69, 0x1c329ed6, 0x1c326f70, 0x1c324036, 0x1c321129, + 0x1c31e248, 0x1c31b393, 0x1c318509, 0x1c3156ab, 0x1c312878, 0x1c30fa70, + 0x1c30cc94, 0x1c309ee3, 0x1c30715c, 0x1c304400, 0x1c3016ce, 0x1c2fe9c7, + 0x1c2fbcea, 0x1c2f9037, 0x1c2f63ae, 0x1c2f374e, 0x1c2f0b18, 0x1c2edf0b, + 0x1c2eb328, 0x1c2e876e, 0x1c2e5bdd, 0x1c2e3074, 0x1c2e0534, 0x1c2dda1d, + 0x1c2daf2e, 0x1c2d8467, 0x1c2d59c8, 0x1c2d2f51, 0x1c2d0502, 0x1c2cdada, + 0x1c2cb0da, 0x1c2c8701, 0x1c2c5d4f, 0x1c2c33c5, 0x1c2c0a61, 0x1c2be124, + 0x1c2bb80e, 0x1c2b8f1e, 0x1c2b6655, 0x1c2b3db2, 0x1c2b1535, 0x1c2aecde, + 0x1c2ac4ac, 0x1c2a9ca0, 0x1c2a74ba, 0x1c2a4cf9, 0x1c2a255d, 0x1c29fde6, + 0x1c29d694, 0x1c29af67, 0x1c29885f, 0x1c29617b, 0x1c293abc, 0x1c291421, + 0x1c28edaa, 0x1c28c757, 0x1c28a128, 0x1c287b1d, 0x1c285535, 0x1c282f71, + 0x1c2809d0, 0x1c27e452, 0x1c27bef8, 0x1c2799c1, 0x1c2774ac, 0x1c274fba, + 0x1c272aeb, 0x1c27063e, 0x1c26e1b4, 0x1c26bd4c, 0x1c269906, 0x1c2674e2, + 0x1c2650e0, 0x1c262cff, 0x1c260940, 0x1c25e5a2, 0x1c25c226, 0x1c259ecb, + 0x1c257b91, 0x1c255878, 0x1c253580, 0x1c2512a9, 0x1c24eff2, 0x1c24cd5c, + 0x1c24aae6, 0x1c248890, 0x1c24665b, 0x1c244446, 0x1c242251, 0x1c24007b, + 0x1c23dec5, 0x1c23bd2f, 0x1c239bb8, 0x1c237a60, 0x1c235928, 0x1c23380f, + 0x1c231715, 0x1c22f63a, 0x1c22d57d, 0x1c22b4df, 0x1c22945f, 0x1c2273fe, + 0x1c2253bb, 0x1c223396, 0x1c221390, 0x1c21f3a8, 0x1c21d3dd, 0x1c21b430, + }; + + for (uint32_t expected : diffs) { + blocks[h] = GetBlockIndex(&blocks[h - 1], -100, nBits); + nBits = GetNextGrasbergWorkRequired(&blocks[h], &blkHeaderDummy, + *chainParams); + BOOST_CHECK_EQUAL(nBits, expected); + h++; + } + + // Check for absurd solve time. + blocks[h] = GetBlockIndex(&blocks[h - 1], -3900000, nBits); + nBits = GetNextGrasbergWorkRequired(&blocks[h++], &blkHeaderDummy, + *chainParams); + BOOST_CHECK_EQUAL(nBits, 0x1821b430); + + blocks[h] = GetBlockIndex(&blocks[h - 1], -5000000, nBits); + nBits = GetNextGrasbergWorkRequired(&blocks[h++], &blkHeaderDummy, + *chainParams); + BOOST_CHECK_EQUAL(nBits, 0x1421b430); + + blocks[h] = GetBlockIndex(&blocks[h - 1], 3900000, nBits); + nBits = GetNextGrasbergWorkRequired(&blocks[h++], &blkHeaderDummy, + *chainParams); + BOOST_CHECK_EQUAL(nBits, 0x1821b430); + + blocks[h] = GetBlockIndex(&blocks[h - 1], 5000000, nBits); + nBits = GetNextGrasbergWorkRequired(&blocks[h++], &blkHeaderDummy, + *chainParams); + BOOST_CHECK_EQUAL(nBits, 0x1c21b430); + + blocks[h] = GetBlockIndex(&blocks[h - 1], 9000000, nBits); + nBits = GetNextGrasbergWorkRequired(&blocks[h++], &blkHeaderDummy, + *chainParams); + BOOST_CHECK_EQUAL(nBits, 0x1d00ffff); +} + +BOOST_AUTO_TEST_CASE(testnet_difficulty_drop_test) { + const auto chainParams = CreateChainParams(CBaseChainParams::TESTNET); + const auto ¶ms = chainParams->GetConsensus(); + + std::vector blocks(3000); + + const arith_uint256 powLimit = UintToArith256(params.powLimit); + uint32_t powLimitBits = powLimit.GetCompact(); + arith_uint256 currentPow = powLimit >> 4; + uint32_t initialBits = currentPow.GetCompact(); + + // Genesis block. + blocks[0] = CBlockIndex(); + blocks[0].nHeight = 0; + blocks[0].nTime = 1269211443; + blocks[0].nBits = initialBits; + + blocks[0].nChainWork = GetBlockProof(blocks[0]); + + // Check that we can use Grasberg directly from genesis. + CBlockHeader blkHeaderDummy; + uint32_t nBits = + GetNextGrasbergWorkRequired(&blocks[0], &blkHeaderDummy, *chainParams); + BOOST_CHECK_EQUAL(nBits, 0x1c0ffe3c); + + // Up to 20 mins, difficulty is unchanged. + blkHeaderDummy.nTime = blocks[0].nTime + 2 * params.nPowTargetSpacing; + nBits = + GetNextGrasbergWorkRequired(&blocks[0], &blkHeaderDummy, *chainParams); + BOOST_CHECK_EQUAL(nBits, 0x1c0ffe3c); + + // After 20 mins, difficulty drops. + blkHeaderDummy.nTime++; + nBits = + GetNextGrasbergWorkRequired(&blocks[0], &blkHeaderDummy, *chainParams); + BOOST_CHECK_EQUAL(nBits, powLimitBits); + + // Mine sevral blocks and check the difficulty. + size_t h = 1; + + std::vector diffs = { + 0x1c100c82, 0x1c101ad2, 0x1c10292f, 0x1c103799, 0x1c104610, + 0x1c105494, 0x1c106325, 0x1c1071c2, 0x1c10806d, 0x1c108f25, + }; + + // Mine several blocks at minimal difficulty. Block is skipped to compute + // the next difficulty. + for (uint32_t expected : diffs) { + blocks[h] = GetBlockIndex( + &blocks[h - 1], 2 * params.nPowTargetSpacing + 1, powLimitBits); + nBits = GetNextGrasbergWorkRequired(&blocks[h++], &blkHeaderDummy, + *chainParams); + BOOST_CHECK_EQUAL(nBits, expected); + } + + // Mine one block at regular difficulty, it will now be the new reference + // when skipping over low difficulty blocks. + blocks[h] = GetBlockIndex(&blocks[h - 1], 600, nBits); + nBits = GetNextGrasbergWorkRequired(&blocks[h++], &blkHeaderDummy, + *chainParams); + BOOST_CHECK_EQUAL(nBits, 0x1c108d52); + + diffs = { + 0x1c109c18, 0x1c10aae8, 0x1c10b9c6, 0x1c10c8b1, 0x1c10d7a9, + 0x1c10e6af, 0x1c10f5c2, 0x1c1104e2, 0x1c111410, 0x1c11234b, + }; + + // As we mine more blocks with low difficulty, we use our new reference. + for (uint32_t expected : diffs) { + blocks[h] = GetBlockIndex( + &blocks[h - 1], 2 * params.nPowTargetSpacing + 1, powLimitBits); + nBits = GetNextGrasbergWorkRequired(&blocks[h++], &blkHeaderDummy, + *chainParams); + BOOST_CHECK_EQUAL(nBits, expected); + } +} + +BOOST_AUTO_TEST_SUITE_END() diff --git a/src/pow/util.h b/src/pow/util.h new file mode 100644 --- /dev/null +++ b/src/pow/util.h @@ -0,0 +1,27 @@ +// Copyright (c) 2020 The Bitcoin developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#ifndef BITCOIN_POW_UTIL_H +#define BITCOIN_POW_UTIL_H + +#include + +/** + * Compute a target based on the work require for the next block. + */ +static arith_uint256 ComputeTargetFromWork(const arith_uint256 &work) { + // Special case 0 to avoid division by zero. + if (work == 0) { + return -arith_uint256(1); + } + + /** + * We need to compute T = (2^256 / W) - 1 but 2^256 doesn't fit in 256 bits. + * By expressing 1 as W / W, we get (2^256 - W) / W, and we can compute + * 2^256 - W as the complement of W. + */ + return (-work) / work; +} + +#endif // BITCOIN_POW_UTIL_H