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(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,243 @@ +// 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 +#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 ComputeNextWork(const CBlockIndex *pindexPrev, + const CChainParams ¶ms) { + const int64_t targetBlockTime = computeTargetBlockTime(pindexPrev, params); + const int64_t expectedBlockTime = params.GetConsensus().nPowTargetSpacing; + + const int64_t lastBlockTime = + (pindexPrev->pprev == nullptr) + ? expectedBlockTime + : (pindexPrev->GetBlockTime() - pindexPrev->pprev->GetBlockTime()); + const int64_t timeOffset = targetBlockTime - lastBlockTime; + + // 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); + + const arith_uint256 lastBlockWork = + (pindexPrev->pprev == nullptr) + ? pindexPrev->nChainWork + : (pindexPrev->nChainWork - pindexPrev->pprev->nChainWork); + + // Clip adjustment to avoid overflow. + if (xi >= 32) { + return lastBlockWork << 32; + } else if (xi <= -32) { + return lastBlockWork >> 32; + } + + const arith_uint256 offsetWork32 = lastBlockWork * deterministicExp2(xd); + const arith_uint256 nextWork = + xi < 0 ? (lastBlockWork + (offsetWork32 >> 32)) >> (-xi) + : (lastBlockWork << xi) + (offsetWork32 >> (32 - xi)); + + return nextWork; +} + +/** + * 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(); + + 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 nextWork = ComputeNextWork(pindexPrev, chainParams); + const arith_uint256 nextTarget = ComputeTargetFromWork(nextWork); + + 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(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]; + + /** + * Now we aproximate the result using a taylor series. + * + * /!\ 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. It is paramount to run the + * test suite to ensure this is the case if you want to use this on + * another platform. + * + * 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. + */ + 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,657 @@ +// 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, 0x1c102666, 0x1c102802, + 0x1c10299e, 0x1c102b3a, 0x1c102cd6, 0x1c102e72, 0x1c10300e, 0x1c1031ab, + 0x1c103348, 0x1c1034e5, 0x1c103682, 0x1c10381f, 0x1c1039bc, 0x1c103b5a, + 0x1c103cf8, 0x1c103e96, 0x1c104034, 0x1c1041d2, 0x1c104370, 0x1c10450f, + 0x1c1046ae, 0x1c10484d, 0x1c1049ec, 0x1c104b8b, 0x1c104d2a, 0x1c104ec9, + 0x1c105069, 0x1c105209, 0x1c1053a9, 0x1c105549, 0x1c1056e9, 0x1c105889, + 0x1c105a2a, 0x1c105bcb, 0x1c105d6c, 0x1c105f0d, 0x1c1060ae, 0x1c10624f, + 0x1c1063f1, 0x1c106593, 0x1c106735, 0x1c1068d7, 0x1c106a79, 0x1c106c1b, + 0x1c106dbe, 0x1c106f61, 0x1c107104, 0x1c1072a7, 0x1c10744a, 0x1c1075ed, + 0x1c107791, 0x1c107935, 0x1c107ad9, 0x1c107c7d, 0x1c107e21, 0x1c107fc5, + 0x1c10816a, 0x1c10830f, 0x1c1084b4, 0x1c108659, 0x1c1087fe, 0x1c1089a3, + 0x1c108b49, 0x1c108cef, 0x1c108e95, 0x1c10903b, 0x1c1091e1, 0x1c109387, + 0x1c10952e, 0x1c1096d5, 0x1c10987c, 0x1c109a23, 0x1c109bca, 0x1c109d71, + 0x1c109f18, 0x1c10a0c0, 0x1c10a268, 0x1c10a410, 0x1c10a5b8, 0x1c10a760, + 0x1c10a908, 0x1c10aab1, 0x1c10ac5a, 0x1c10ae03, 0x1c10afac, 0x1c10b155, + 0x1c10b2fe, 0x1c10b4a8, 0x1c10b652, 0x1c10b7fc, 0x1c10b9a6, 0x1c10bb50, + 0x1c10bcfa, 0x1c10bea5, 0x1c10c050, 0x1c10c1fb, 0x1c10c3a6, 0x1c10c551, + 0x1c10c6fc, 0x1c10c8a8, 0x1c10ca54, 0x1c10cc00, 0x1c10cdac, 0x1c10cf58, + 0x1c10d104, 0x1c10d2b1, 0x1c10d45e, 0x1c10d60b, 0x1c10d7b8, 0x1c10d965, + 0x1c10db12, 0x1c10dcc0, 0x1c10de6e, 0x1c10e01c, 0x1c10e1ca, 0x1c10e378, + 0x1c10e526, 0x1c10e6d5, 0x1c10e884, 0x1c10ea33, 0x1c10ebe2, 0x1c10ed91, + 0x1c10ef40, 0x1c10f0f0, 0x1c10f2a0, 0x1c10f450, 0x1c10f600, 0x1c10f7b0, + 0x1c10f960, 0x1c10fb11, 0x1c10fcc2, 0x1c10fe73, 0x1c110024, 0x1c1101d5, + 0x1c110387, 0x1c110539, 0x1c1106eb, 0x1c11089d, 0x1c110a4f, 0x1c110c01, + 0x1c110db4, 0x1c110f67, 0x1c11111a, 0x1c1112cd, 0x1c111480, 0x1c111633, + 0x1c1117e7, 0x1c11199b, 0x1c111b4f, 0x1c111d03, 0x1c111eb7, 0x1c11206b, + 0x1c112220, 0x1c1123d5, 0x1c11258a, 0x1c11273f, 0x1c1128f4, 0x1c112aa9, + 0x1c112c5f, 0x1c112e15, 0x1c112fcb, 0x1c113181, 0x1c113337, 0x1c1134ed, + 0x1c1136a4, 0x1c11385b, 0x1c113a12, 0x1c113bc9, 0x1c113d80, 0x1c113f37, + 0x1c1140ef, 0x1c1142a7, 0x1c11445f, 0x1c114617, 0x1c1147cf, 0x1c114987, + 0x1c114b40, 0x1c114cf9, 0x1c114eb2, 0x1c11506b, 0x1c115224, 0x1c1153de, + 0x1c115598, 0x1c115752, 0x1c11590c, 0x1c115ac6, 0x1c115c80, 0x1c115e3b, + 0x1c115ff6, 0x1c1161b1, 0x1c11636c, 0x1c116527, 0x1c1166e2, 0x1c11689e, + 0x1c116a5a, 0x1c116c16, 0x1c116dd2, 0x1c116f8e, 0x1c11714a, 0x1c117307, + 0x1c1174c4, 0x1c117681, 0x1c11783e, 0x1c1179fb, 0x1c117bb8, 0x1c117d76, + 0x1c117f34, 0x1c1180f2, 0x1c1182b0, 0x1c11846e, 0x1c11862d, 0x1c1187ec, + 0x1c1189ab, 0x1c118b6a, 0x1c118d29, 0x1c118ee8, 0x1c1190a8, 0x1c119268, + 0x1c119428, 0x1c1195e8, 0x1c1197a8, 0x1c119968, 0x1c119b29, 0x1c119cea, + 0x1c119eab, 0x1c11a06c, 0x1c11a22d, 0x1c11a3ee, 0x1c11a5b0, 0x1c11a772, + 0x1c11a934, 0x1c11aaf6, 0x1c11acb8, 0x1c11ae7b, 0x1c11b03e, 0x1c11b201, + 0x1c11b3c4, 0x1c11b587, 0x1c11b74a, 0x1c11b90e, 0x1c11bad2, 0x1c11bc96, + 0x1c11be5a, 0x1c11c01e, 0x1c11c1e2, 0x1c11c3a7, 0x1c11c56c, 0x1c11c731, + 0x1c11c8f6, 0x1c11cabb, 0x1c11cc81, 0x1c11ce47, 0x1c11d00d, 0x1c11d1d3, + 0x1c11d399, 0x1c11d55f, 0x1c11d726, 0x1c11d8ed, 0x1c11dab4, 0x1c11dc7b, + 0x1c11de42, 0x1c11e009, 0x1c11e1d1, 0x1c11e399, 0x1c11e561, 0x1c11e729, + 0x1c11e8f1, 0x1c11eaba, 0x1c11ec83, 0x1c11ee4c, 0x1c11f015, 0x1c11f1de, + 0x1c11f3a7, 0x1c11f571, 0x1c11f73b, 0x1c11f905, 0x1c11facf, 0x1c11fc99, + }; + + 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 = { + 0x1c11f111, 0x1c11e590, 0x1c11da17, 0x1c11cea5, 0x1c11c33a, 0x1c11b7d7, + 0x1c11ac7b, 0x1c11a126, 0x1c1195d9, 0x1c118a93, 0x1c117f54, 0x1c11741c, + 0x1c1168ec, 0x1c115dc3, 0x1c1152a1, 0x1c114786, 0x1c113c72, 0x1c113165, + 0x1c11265f, 0x1c111b60, 0x1c111068, 0x1c110577, 0x1c10fa8d, 0x1c10efaa, + 0x1c10e4ce, 0x1c10d9f9, 0x1c10cf2b, 0x1c10c464, 0x1c10b9a4, 0x1c10aeeb, + 0x1c10a439, 0x1c10998e, 0x1c108eea, 0x1c10844c, 0x1c1079b5, 0x1c106f25, + 0x1c10649c, 0x1c105a1a, 0x1c104f9e, 0x1c104529, 0x1c103abb, 0x1c103053, + 0x1c1025f2, 0x1c101b98, 0x1c101144, 0x1c1006f7, 0x1c0ffcb1, 0x1c0ff271, + 0x1c0fe838, 0x1c0fde05, 0x1c0fd3d9, 0x1c0fc9b3, 0x1c0fbf94, 0x1c0fb57b, + 0x1c0fab69, 0x1c0fa15d, 0x1c0f9758, 0x1c0f8d59, 0x1c0f8361, 0x1c0f796f, + 0x1c0f6f83, 0x1c0f659e, 0x1c0f5bbf, 0x1c0f51e6, 0x1c0f4814, 0x1c0f3e48, + 0x1c0f3482, 0x1c0f2ac2, 0x1c0f2109, 0x1c0f1756, 0x1c0f0da9, 0x1c0f0402, + 0x1c0efa62, 0x1c0ef0c8, 0x1c0ee734, 0x1c0edda6, 0x1c0ed41e, 0x1c0eca9c, + 0x1c0ec120, 0x1c0eb7aa, 0x1c0eae3a, 0x1c0ea4d1, 0x1c0e9b6e, 0x1c0e9211, + 0x1c0e88ba, 0x1c0e7f69, 0x1c0e761e, 0x1c0e6cd8, 0x1c0e6398, 0x1c0e5a5e, + 0x1c0e512a, 0x1c0e47fc, 0x1c0e3ed4, 0x1c0e35b2, 0x1c0e2c96, 0x1c0e2380, + 0x1c0e1a6f, 0x1c0e1164, 0x1c0e085f, 0x1c0dff60, 0x1c0df667, 0x1c0ded73, + 0x1c0de485, 0x1c0ddb9d, 0x1c0dd2bb, 0x1c0dc9de, 0x1c0dc107, 0x1c0db836, + 0x1c0daf6a, 0x1c0da6a4, 0x1c0d9de3, 0x1c0d9528, 0x1c0d8c73, 0x1c0d83c3, + 0x1c0d7b19, 0x1c0d7274, 0x1c0d69d5, 0x1c0d613b, 0x1c0d58a7, 0x1c0d5018, + 0x1c0d478f, 0x1c0d3f0b, 0x1c0d368d, 0x1c0d2e14, 0x1c0d25a1, 0x1c0d1d33, + 0x1c0d14cb, 0x1c0d0c68, 0x1c0d040a, 0x1c0cfbb2, 0x1c0cf35f, 0x1c0ceb11, + 0x1c0ce2c9, 0x1c0cda86, 0x1c0cd248, 0x1c0cca10, 0x1c0cc1dd, 0x1c0cb9af, + 0x1c0cb186, 0x1c0ca963, 0x1c0ca145, 0x1c0c992c, 0x1c0c9118, 0x1c0c8909, + 0x1c0c8100, 0x1c0c78fc, 0x1c0c70fd, 0x1c0c6903, 0x1c0c610e, 0x1c0c591e, + 0x1c0c5133, 0x1c0c494d, 0x1c0c416c, 0x1c0c3990, 0x1c0c31b9, 0x1c0c29e8, + 0x1c0c221c, 0x1c0c1a55, 0x1c0c1293, 0x1c0c0ad5, 0x1c0c031c, 0x1c0bfb68, + 0x1c0bf3b9, 0x1c0bec0f, 0x1c0be46a, 0x1c0bdcca, 0x1c0bd52f, 0x1c0bcd99, + 0x1c0bc608, 0x1c0bbe7c, 0x1c0bb6f4, 0x1c0baf71, 0x1c0ba7f3, 0x1c0ba07a, + 0x1c0b9906, 0x1c0b9196, 0x1c0b8a2b, 0x1c0b82c5, 0x1c0b7b64, 0x1c0b7407, + 0x1c0b6caf, 0x1c0b655c, 0x1c0b5e0e, 0x1c0b56c4, 0x1c0b4f7f, 0x1c0b483f, + 0x1c0b4103, 0x1c0b39cc, 0x1c0b3299, 0x1c0b2b6b, 0x1c0b2442, 0x1c0b1d1d, + 0x1c0b15fd, 0x1c0b0ee1, 0x1c0b07ca, 0x1c0b00b7, 0x1c0af9a9, 0x1c0af2a0, + 0x1c0aeb9b, 0x1c0ae49b, 0x1c0add9f, 0x1c0ad6a8, 0x1c0acfb5, 0x1c0ac8c6, + 0x1c0ac1dc, 0x1c0abaf6, 0x1c0ab415, 0x1c0aad38, 0x1c0aa660, 0x1c0a9f8c, + 0x1c0a98bc, 0x1c0a91f1, 0x1c0a8b2a, 0x1c0a8467, 0x1c0a7da9, 0x1c0a76ef, + 0x1c0a7039, 0x1c0a6988, 0x1c0a62db, 0x1c0a5c32, 0x1c0a558d, 0x1c0a4eed, + 0x1c0a4851, 0x1c0a41b9, 0x1c0a3b25, 0x1c0a3496, 0x1c0a2e0b, 0x1c0a2784, + 0x1c0a2101, 0x1c0a1a82, 0x1c0a1408, 0x1c0a0d92, 0x1c0a0720, 0x1c0a00b2, + 0x1c09fa48, 0x1c09f3e2, 0x1c09ed80, 0x1c09e722, 0x1c09e0c9, 0x1c09da74, + 0x1c09d423, 0x1c09cdd6, 0x1c09c78d, 0x1c09c148, 0x1c09bb07, 0x1c09b4ca, + 0x1c09ae91, 0x1c09a85c, 0x1c09a22b, 0x1c099bfe, 0x1c0995d5, 0x1c098fb0, + 0x1c09898f, 0x1c098371, 0x1c097d57, 0x1c097741, 0x1c09712f, 0x1c096b21, + 0x1c096517, 0x1c095f11, 0x1c09590f, 0x1c095311, 0x1c094d16, 0x1c09471f, + 0x1c09412c, 0x1c093b3d, 0x1c093552, 0x1c092f6a, 0x1c092986, 0x1c0923a6, + 0x1c091dca, 0x1c0917f2, 0x1c09121d, 0x1c090c4c, 0x1c09067f, 0x1c0900b6, + 0x1c08faf0, 0x1c08f52e, 0x1c08ef70, 0x1c08e9b5, 0x1c08e3fe, 0x1c08de4b, + 0x1c08d89b, 0x1c08d2ef, 0x1c08cd47, 0x1c08c7a2, 0x1c08c201, 0x1c08bc63, + 0x1c08b6c9, 0x1c08b133, 0x1c08aba0, 0x1c08a611, 0x1c08a085, 0x1c089afd, + 0x1c089578, 0x1c088ff7, 0x1c088a79, 0x1c0884ff, 0x1c087f89, 0x1c087a16, + }; + + 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 = { + 0x1c08a0f2, 0x1c08c880, 0x1c08f0c3, 0x1c0919bf, 0x1c094377, 0x1c096dee, + 0x1c099928, 0x1c09c528, 0x1c09f1f2, 0x1c0a1f89, 0x1c0a4df1, 0x1c0a7d2e, + 0x1c0aad43, 0x1c0ade35, 0x1c0b1007, 0x1c0b42bd, 0x1c0b765c, 0x1c0baae7, + 0x1c0be063, 0x1c0c16d5, 0x1c0c4e40, 0x1c0c86a9, 0x1c0cc015, 0x1c0cfa88, + 0x1c0d3607, 0x1c0d7297, 0x1c0db03c, 0x1c0deefc, 0x1c0e2edc, 0x1c0e6fe0, + 0x1c0eb20f, 0x1c0ef56d, 0x1c0f3a00, 0x1c0f7fcd, 0x1c0fc6da, 0x1c100f2d, + 0x1c1058cb, 0x1c10a3bb, 0x1c10f002, 0x1c113da7, 0x1c118cb0, 0x1c11dd23, + 0x1c122f07, 0x1c128263, 0x1c12d73d, 0x1c132d9c, 0x1c138587, 0x1c13df05, + 0x1c143a1d, 0x1c1496d7, 0x1c14f53a, 0x1c15554d, 0x1c15b719, 0x1c161aa5, + 0x1c167ff9, 0x1c16e71e, 0x1c17501c, 0x1c17bafb, 0x1c1827c4, 0x1c189680, + 0x1c190737, 0x1c1979f3, 0x1c19eebd, 0x1c1a659e, 0x1c1adea0, 0x1c1b59cd, + 0x1c1bd72f, 0x1c1c56d0, 0x1c1cd8ba, 0x1c1d5cf7, 0x1c1de393, 0x1c1e6c98, + 0x1c1ef811, 0x1c1f8609, 0x1c20168c, 0x1c20a9a5, 0x1c213f61, 0x1c21d7cb, + 0x1c2272f0, 0x1c2310dc, 0x1c23b19c, 0x1c24553d, 0x1c24fbcc, 0x1c25a557, + 0x1c2651eb, 0x1c270196, 0x1c27b466, 0x1c286a6a, 0x1c2923b1, 0x1c29e049, + 0x1c2aa042, 0x1c2b63ab, 0x1c2c2a93, 0x1c2cf50b, 0x1c2dc323, 0x1c2e94ec, + 0x1c2f6a77, 0x1c3043d5, 0x1c312117, 0x1c320250, 0x1c32e791, 0x1c33d0ed, + 0x1c34be77, 0x1c35b042, 0x1c36a661, 0x1c37a0e9, 0x1c389fed, 0x1c39a382, + 0x1c3aabbd, 0x1c3bb8b3, 0x1c3cca7a, 0x1c3de129, 0x1c3efcd5, 0x1c401d96, + 0x1c414382, 0x1c426eb2, 0x1c439f3d, 0x1c44d53c, 0x1c4610c9, 0x1c4751fc, + 0x1c4898f0, 0x1c49e5be, 0x1c4b3882, 0x1c4c9157, 0x1c4df059, 0x1c4f55a4, + 0x1c50c155, 0x1c523389, 0x1c53ac5e, 0x1c552bf3, 0x1c56b266, 0x1c583fd7, + 0x1c59d466, 0x1c5b7034, 0x1c5d1362, 0x1c5ebe11, 0x1c607064, 0x1c622a7f, + 0x1c63ec84, 0x1c65b698, 0x1c6788e0, 0x1c696382, 0x1c6b46a4, 0x1c6d326d, + 0x1c6f2704, 0x1c712492, 0x1c732b40, 0x1c753b38, 0x1c7754a4, 0x1c7977b0, + 0x1c7ba487, 0x1c7ddb57, 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, 0x1c7f86e7, 0x1c7f2252, 0x1c7ebe0c, 0x1c7e5a15, + 0x1c7df66d, 0x1c7d9314, 0x1c7d3009, 0x1c7ccd4c, 0x1c7c6add, 0x1c7c08bc, + 0x1c7ba6e8, 0x1c7b4561, 0x1c7ae427, 0x1c7a833a, 0x1c7a2299, 0x1c79c245, + 0x1c79623d, 0x1c790280, 0x1c78a30f, 0x1c7843e9, 0x1c77e50e, 0x1c77867e, + 0x1c772839, 0x1c76ca3e, 0x1c766c8d, 0x1c760f26, 0x1c75b209, 0x1c755535, + 0x1c74f8aa, 0x1c749c68, 0x1c74406f, 0x1c73e4bf, 0x1c738957, 0x1c732e37, + 0x1c72d35f, 0x1c7278cf, 0x1c721e86, 0x1c71c484, 0x1c716ac9, 0x1c711155, + 0x1c70b827, 0x1c705f40, 0x1c70069f, 0x1c6fae44, 0x1c6f562f, 0x1c6efe5f, + 0x1c6ea6d4, 0x1c6e4f8e, 0x1c6df88d, 0x1c6da1d1, 0x1c6d4b59, 0x1c6cf525, + 0x1c6c9f35, 0x1c6c4989, 0x1c6bf421, 0x1c6b9efc, 0x1c6b4a1a, 0x1c6af57b, + 0x1c6aa11f, 0x1c6a4d05, 0x1c69f92e, 0x1c69a599, 0x1c695246, 0x1c68ff34, + 0x1c68ac64, 0x1c6859d5, 0x1c680787, 0x1c67b57a, 0x1c6763ae, 0x1c671223, + 0x1c66c0d8, 0x1c666fcd, 0x1c661f02, 0x1c65ce77, 0x1c657e2b, 0x1c652e1e, + }; + + 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 = { + 0x1c64cf61, 0x1c6470fd, 0x1c6412f1, 0x1c63b53d, 0x1c6357e1, 0x1c62fadc, + 0x1c629e2e, 0x1c6241d7, 0x1c61e5d6, 0x1c618a2c, 0x1c612ed7, 0x1c60d3d8, + 0x1c60792e, 0x1c601ed9, 0x1c5fc4d9, 0x1c5f6b2d, 0x1c5f11d5, 0x1c5eb8d1, + 0x1c5e6020, 0x1c5e07c2, 0x1c5dafb7, 0x1c5d57fe, 0x1c5d0097, 0x1c5ca982, + 0x1c5c52bf, 0x1c5bfc4d, 0x1c5ba62c, 0x1c5b505b, 0x1c5afadb, 0x1c5aa5ab, + 0x1c5a50cb, 0x1c59fc3a, 0x1c59a7f8, 0x1c595405, 0x1c590061, 0x1c58ad0b, + 0x1c585a03, 0x1c580749, 0x1c57b4dc, 0x1c5762bc, 0x1c5710e9, 0x1c56bf63, + 0x1c566e29, 0x1c561d3b, 0x1c55cc99, 0x1c557c43, 0x1c552c38, 0x1c54dc78, + 0x1c548d02, 0x1c543dd7, 0x1c53eef6, 0x1c53a05f, 0x1c535211, 0x1c53040d, + 0x1c52b652, 0x1c5268e0, 0x1c521bb6, 0x1c51ced4, 0x1c51823a, 0x1c5135e8, + 0x1c50e9dd, 0x1c509e1a, 0x1c50529e, 0x1c500768, 0x1c4fbc79, 0x1c4f71d0, + 0x1c4f276d, 0x1c4edd4f, 0x1c4e9377, 0x1c4e49e4, 0x1c4e0096, 0x1c4db78d, + 0x1c4d6ec8, 0x1c4d2647, 0x1c4cde0a, 0x1c4c9611, 0x1c4c4e5b, 0x1c4c06e8, + 0x1c4bbfb8, 0x1c4b78cb, 0x1c4b3220, 0x1c4aebb7, 0x1c4aa590, 0x1c4a5fab, + 0x1c4a1a07, 0x1c49d4a4, 0x1c498f82, 0x1c494aa1, 0x1c490601, 0x1c48c1a1, + 0x1c487d81, 0x1c4839a1, 0x1c47f600, 0x1c47b29f, 0x1c476f7d, 0x1c472c9a, + 0x1c46e9f5, 0x1c46a78f, 0x1c466567, 0x1c46237d, 0x1c45e1d0, 0x1c45a061, + 0x1c455f2f, 0x1c451e3a, 0x1c44dd82, 0x1c449d07, 0x1c445cc8, 0x1c441cc5, + 0x1c43dcfe, 0x1c439d73, 0x1c435e23, 0x1c431f0f, 0x1c42e036, 0x1c42a198, + 0x1c426334, 0x1c42250b, 0x1c41e71c, 0x1c41a967, 0x1c416bec, 0x1c412eaa, + 0x1c40f1a1, 0x1c40b4d2, 0x1c40783c, 0x1c403bde, 0x1c3fffb9, 0x1c3fc3cc, + 0x1c3f8817, 0x1c3f4c9a, 0x1c3f1155, 0x1c3ed647, 0x1c3e9b71, 0x1c3e60d2, + 0x1c3e266a, 0x1c3dec38, 0x1c3db23d, 0x1c3d7878, 0x1c3d3ee9, 0x1c3d0590, + 0x1c3ccc6d, 0x1c3c937f, 0x1c3c5ac7, 0x1c3c2244, 0x1c3be9f6, 0x1c3bb1dc, + 0x1c3b79f7, 0x1c3b4246, 0x1c3b0ac9, 0x1c3ad380, 0x1c3a9c6b, 0x1c3a658a, + 0x1c3a2edc, 0x1c39f861, 0x1c39c219, 0x1c398c04, 0x1c395622, 0x1c392072, + 0x1c38eaf4, 0x1c38b5a8, 0x1c38808e, 0x1c384ba6, 0x1c3816f0, 0x1c37e26b, + 0x1c37ae17, 0x1c3779f4, 0x1c374602, 0x1c371241, 0x1c36deb0, 0x1c36ab4f, + 0x1c36781e, 0x1c36451d, 0x1c36124c, 0x1c35dfab, 0x1c35ad39, 0x1c357af6, + 0x1c3548e2, 0x1c3516fd, 0x1c34e547, 0x1c34b3c0, 0x1c348267, 0x1c34513c, + 0x1c34203f, 0x1c33ef70, 0x1c33becf, 0x1c338e5b, 0x1c335e15, 0x1c332dfc, + 0x1c32fe10, 0x1c32ce51, 0x1c329ebe, 0x1c326f58, 0x1c32401e, 0x1c321111, + 0x1c31e230, 0x1c31b37b, 0x1c3184f1, 0x1c315693, 0x1c312860, 0x1c30fa58, + 0x1c30cc7c, 0x1c309ecb, 0x1c307144, 0x1c3043e8, 0x1c3016b6, 0x1c2fe9af, + 0x1c2fbcd2, 0x1c2f901f, 0x1c2f6396, 0x1c2f3736, 0x1c2f0b00, 0x1c2edef3, + 0x1c2eb310, 0x1c2e8756, 0x1c2e5bc5, 0x1c2e305c, 0x1c2e051c, 0x1c2dda05, + 0x1c2daf16, 0x1c2d844f, 0x1c2d59b0, 0x1c2d2f39, 0x1c2d04ea, 0x1c2cdac2, + 0x1c2cb0c2, 0x1c2c86e9, 0x1c2c5d37, 0x1c2c33ad, 0x1c2c0a49, 0x1c2be10c, + 0x1c2bb7f6, 0x1c2b8f06, 0x1c2b663d, 0x1c2b3d9a, 0x1c2b151d, 0x1c2aecc6, + 0x1c2ac494, 0x1c2a9c88, 0x1c2a74a2, 0x1c2a4ce1, 0x1c2a2545, 0x1c29fdce, + 0x1c29d67c, 0x1c29af4f, 0x1c298847, 0x1c296163, 0x1c293aa4, 0x1c291409, + 0x1c28ed92, 0x1c28c73f, 0x1c28a110, 0x1c287b05, 0x1c28551d, 0x1c282f59, + 0x1c2809b8, 0x1c27e43a, 0x1c27bee0, 0x1c2799a9, 0x1c277494, 0x1c274fa2, + 0x1c272ad3, 0x1c270626, 0x1c26e19c, 0x1c26bd34, 0x1c2698ee, 0x1c2674ca, + 0x1c2650c8, 0x1c262ce7, 0x1c260928, 0x1c25e58a, 0x1c25c20e, 0x1c259eb3, + 0x1c257b79, 0x1c255860, 0x1c253568, 0x1c251291, 0x1c24efda, 0x1c24cd44, + 0x1c24aace, 0x1c248878, 0x1c246643, 0x1c24442e, 0x1c242239, 0x1c240063, + 0x1c23dead, 0x1c23bd17, 0x1c239ba0, 0x1c237a48, 0x1c235910, 0x1c2337f7, + 0x1c2316fd, 0x1c22f622, 0x1c22d565, 0x1c22b4c7, 0x1c229448, 0x1c2273e7, + 0x1c2253a4, 0x1c22337f, 0x1c221379, 0x1c21f391, 0x1c21d3c6, 0x1c21b419, + }; + + 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, 0x1821b419); + + blocks[h] = GetBlockIndex(&blocks[h - 1], -5000000, nBits); + nBits = GetNextGrasbergWorkRequired(&blocks[h++], &blkHeaderDummy, + *chainParams); + BOOST_CHECK_EQUAL(nBits, 0x1421b419); + + blocks[h] = GetBlockIndex(&blocks[h - 1], 3900000, nBits); + nBits = GetNextGrasbergWorkRequired(&blocks[h++], &blkHeaderDummy, + *chainParams); + BOOST_CHECK_EQUAL(nBits, 0x1821b419); + + blocks[h] = GetBlockIndex(&blocks[h - 1], 5000000, nBits); + nBits = GetNextGrasbergWorkRequired(&blocks[h++], &blkHeaderDummy, + *chainParams); + BOOST_CHECK_EQUAL(nBits, 0x1c21b419); + + 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; + + // Mine several blocks at minimal difficulty. Block is skipped to compute + // the next difficulty. + for (int i = 0; i < 10; i++) { + blocks[h] = GetBlockIndex( + &blocks[h - 1], 2 * params.nPowTargetSpacing + 1, powLimitBits); + nBits = GetNextGrasbergWorkRequired(&blocks[h++], &blkHeaderDummy, + *chainParams); + BOOST_CHECK_EQUAL(nBits, 0x1c0ffe3c); + } + + // 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, 0x1c0ffc79); + + // As we mine more blocks with low difficulty, we use our new reference. + for (int i = 0; i < 10; i++) { + blocks[h] = GetBlockIndex( + &blocks[h - 1], 2 * params.nPowTargetSpacing + 1, powLimitBits); + nBits = GetNextGrasbergWorkRequired(&blocks[h++], &blkHeaderDummy, + *chainParams); + BOOST_CHECK_EQUAL(nBits, 0x1c0ffc79); + } +} + +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,22 @@ +// 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) { + /** + * 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