diff --git a/src/chain.h b/src/chain.h --- a/src/chain.h +++ b/src/chain.h @@ -353,9 +353,12 @@ }; arith_uint256 GetBlockProof(const CBlockIndex &block); -/** Return the time it would take to redo the work difference between from and + +/** + * Return the time it would take to redo the work difference between from and * to, assuming the current hashrate corresponds to the difficulty at tip, in - * seconds. */ + * seconds. + */ int64_t GetBlockProofEquivalentTime(const CBlockIndex &to, const CBlockIndex &from, const CBlockIndex &tip, diff --git a/src/consensus/params.h b/src/consensus/params.h --- a/src/consensus/params.h +++ b/src/consensus/params.h @@ -7,6 +7,7 @@ #define BITCOIN_CONSENSUS_PARAMS_H #include "uint256.h" + #include #include diff --git a/src/pow.h b/src/pow.h --- a/src/pow.h +++ b/src/pow.h @@ -27,4 +27,11 @@ */ bool CheckProofOfWork(uint256 hash, uint32_t nBits, const Consensus::Params &); +/** + * Bitcoin cash's difficulty adjustment mechanism. + */ +uint32_t GetNextCashWorkRequired(const CBlockIndex *pindexPrev, + const CBlockHeader *pblock, + const Consensus::Params ¶ms); + #endif // BITCOIN_POW_H diff --git a/src/pow.cpp b/src/pow.cpp --- a/src/pow.cpp +++ b/src/pow.cpp @@ -1,5 +1,6 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers +// Copyright (c) 2017 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. @@ -149,3 +150,124 @@ return true; } + +/** + * Compute the a target based on the work done between 2 blocks and the time + * required to produce that work. + */ +static arith_uint256 ComputeTarget(const CBlockIndex *pindexFirst, + const CBlockIndex *pindexLast, + const Consensus::Params ¶ms) { + assert(pindexLast->nHeight > pindexFirst->nHeight); + + /** + * From the total work done and the time it took to produce that much work, + * we can deduce how much work we expect to be produced in the targeted time + * between blocks. + */ + arith_uint256 work = pindexLast->nChainWork - pindexFirst->nChainWork; + work *= params.nPowTargetSpacing; + + // In order to avoid difficulty cliffs, we bound the amplitude of the + // adjustement we are going to do. + assert(pindexLast->nTime > pindexFirst->nTime); + int64_t nActualTimespan = pindexLast->nTime - pindexFirst->nTime; + if (nActualTimespan > 288 * params.nPowTargetSpacing) { + nActualTimespan = 288 * params.nPowTargetSpacing; + } else if (nActualTimespan < 72 * params.nPowTargetSpacing) { + nActualTimespan = 72 * params.nPowTargetSpacing; + } + + 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; +} + +/** + * To reduce the impact of timestamp manipulation, we select the block we are + * basing our computation on via a median of 3. + */ +static const CBlockIndex *GetSuitableBlock(const CBlockIndex *pindex) { + assert(pindex->nHeight >= 3); + + /** + * In order to avoid a block is a very skewed timestamp to have too much + * influence, we select the median of the 3 top most blocks as a starting + * point. + */ + const CBlockIndex *blocks[3]; + blocks[2] = pindex; + blocks[1] = pindex->pprev; + blocks[0] = blocks[1]->pprev; + + // Sorting network. + if (blocks[0]->nTime > blocks[2]->nTime) { + std::swap(blocks[0], blocks[2]); + } + + if (blocks[0]->nTime > blocks[1]->nTime) { + std::swap(blocks[0], blocks[1]); + } + + if (blocks[1]->nTime > blocks[2]->nTime) { + std::swap(blocks[1], blocks[2]); + } + + // We should have our candidate in the middle now. + return blocks[1]; +} + +/** + * Compute the next required proof of work using a weighted average of the + * estimated hashrate per block. + * + * Using a weighted average ensure that the timestamp parameter cancels out in + * most of the calculation - except for the timestamp of the first and last + * block. Because timestamps are the least trustworthy information we have as + * input, this ensures the algorithm is more resistant to malicious inputs. + */ +uint32_t GetNextCashWorkRequired(const CBlockIndex *pindexPrev, + const CBlockHeader *pblock, + const Consensus::Params ¶ms) { + // This cannot handle the genesis block and early blocks in general. + assert(pindexPrev); + + // 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 (params.fPowAllowMinDifficultyBlocks && + (pblock->GetBlockTime() > + pindexPrev->GetBlockTime() + 2 * params.nPowTargetSpacing)) { + return UintToArith256(params.powLimit).GetCompact(); + } + + // Compute the difficulty based on the full adjustement interval. + const uint32_t nHeight = pindexPrev->nHeight; + assert(nHeight >= params.DifficultyAdjustmentInterval()); + + // Get the last suitable block of the difficulty interval. + const CBlockIndex *pindexLast = GetSuitableBlock(pindexPrev); + assert(pindexLast); + + // Get the first suitable block of the difficulty interval. + uint32_t nHeightFirst = nHeight - 144; + const CBlockIndex *pindexFirst = + GetSuitableBlock(pindexPrev->GetAncestor(nHeightFirst)); + assert(pindexFirst); + + // Compute the target based on time and work done during the interval. + const arith_uint256 nextTarget = + ComputeTarget(pindexFirst, pindexLast, params); + + const arith_uint256 powLimit = UintToArith256(params.powLimit); + if (nextTarget > powLimit) { + return powLimit.GetCompact(); + } + + return nextTarget.GetCompact(); +} diff --git a/src/test/pow_tests.cpp b/src/test/pow_tests.cpp --- a/src/test/pow_tests.cpp +++ b/src/test/pow_tests.cpp @@ -84,7 +84,7 @@ blocks[i].nTime = 1269211443 + i * params.nPowTargetSpacing; blocks[i].nBits = 0x207fffff; /* target 0x7fffff000... */ blocks[i].nChainWork = - i ? blocks[i - 1].nChainWork + GetBlockProof(blocks[i - 1]) + i ? blocks[i - 1].nChainWork + GetBlockProof(blocks[i]) : arith_uint256(0); } @@ -106,6 +106,7 @@ block.nTime = pindexPrev->nTime + nTimeInterval; block.nBits = nBits; + block.nChainWork = pindexPrev->nChainWork + GetBlockProof(block); return block; } @@ -119,12 +120,14 @@ arith_uint256 currentPow = powLimit >> 1; uint32_t initialBits = currentPow.GetCompact(); - // Genesis block? + // Genesis block. blocks[0] = CBlockIndex(); blocks[0].nHeight = 0; blocks[0].nTime = 1269211443; blocks[0].nBits = initialBits; + blocks[0].nChainWork = GetBlockProof(blocks[0]); + // Pile up some blocks. for (size_t i = 1; i < 100; i++) { blocks[i] = GetBlockIndex(&blocks[i - 1], params.nPowTargetSpacing, @@ -187,4 +190,181 @@ powLimit.GetCompact()); } +BOOST_AUTO_TEST_CASE(cash_difficulty_test) { + SelectParams(CBaseChainParams::MAIN); + const Consensus::Params ¶ms = Params().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]); + + // Block counter. + size_t i; + + // Pile up some blocks every 10 mins to establish some history. + for (i = 1; i < 2050; i++) { + blocks[i] = GetBlockIndex(&blocks[i - 1], 600, initialBits); + } + + CBlockHeader blkHeaderDummy; + uint32_t nBits = + GetNextCashWorkRequired(&blocks[2049], &blkHeaderDummy, params); + + // Difficulty stays the same as long as we produce a block every 10 mins. + for (size_t j = 0; j < 10; i++, j++) { + blocks[i] = GetBlockIndex(&blocks[i - 1], 600, nBits); + BOOST_CHECK_EQUAL( + GetNextCashWorkRequired(&blocks[i], &blkHeaderDummy, params), + nBits); + } + + // Make sure we skip over blocks that are out of wack. To do so, we produce + // a block that is far in the future, and then produce a block with the + // expected timestamp. + blocks[i] = GetBlockIndex(&blocks[i - 1], 6000, nBits); + BOOST_CHECK_EQUAL( + GetNextCashWorkRequired(&blocks[i++], &blkHeaderDummy, params), nBits); + blocks[i] = GetBlockIndex(&blocks[i - 1], 2 * 600 - 6000, nBits); + BOOST_CHECK_EQUAL( + GetNextCashWorkRequired(&blocks[i++], &blkHeaderDummy, params), nBits); + + // The system should continue unaffected by the block with a bogous + // timestamps. + for (size_t j = 0; j < 20; i++, j++) { + blocks[i] = GetBlockIndex(&blocks[i - 1], 600, nBits); + BOOST_CHECK_EQUAL( + GetNextCashWorkRequired(&blocks[i], &blkHeaderDummy, params), + nBits); + } + + // We start emitting blocks slightly faster. The first block has no impact. + blocks[i] = GetBlockIndex(&blocks[i - 1], 550, nBits); + BOOST_CHECK_EQUAL( + GetNextCashWorkRequired(&blocks[i++], &blkHeaderDummy, params), nBits); + + // Now we should see difficulty increase slowly. + for (size_t j = 0; j < 10; i++, j++) { + blocks[i] = GetBlockIndex(&blocks[i - 1], 550, nBits); + const uint32_t nextBits = + GetNextCashWorkRequired(&blocks[i], &blkHeaderDummy, params); + + arith_uint256 currentTarget; + currentTarget.SetCompact(nBits); + arith_uint256 nextTarget; + nextTarget.SetCompact(nextBits); + + // Make sure that difficulty increases very slowly. + BOOST_CHECK(nextTarget < currentTarget); + BOOST_CHECK((currentTarget - nextTarget) < (currentTarget >> 10)); + + nBits = nextBits; + } + + // Check the actual value. + BOOST_CHECK_EQUAL(nBits, 0x1c0fe7b1); + + // If we dramatically shorten block production, difficulty increases faster. + for (size_t j = 0; j < 20; i++, j++) { + blocks[i] = GetBlockIndex(&blocks[i - 1], 10, nBits); + const uint32_t nextBits = + GetNextCashWorkRequired(&blocks[i], &blkHeaderDummy, params); + + arith_uint256 currentTarget; + currentTarget.SetCompact(nBits); + arith_uint256 nextTarget; + nextTarget.SetCompact(nextBits); + + // Make sure that difficulty increases faster. + BOOST_CHECK(nextTarget < currentTarget); + BOOST_CHECK((currentTarget - nextTarget) < (currentTarget >> 4)); + + nBits = nextBits; + } + + // Check the actual value. + BOOST_CHECK_EQUAL(nBits, 0x1c0db19f); + + // We start to emit blocks significantly slower. The first block has no + // impact. + blocks[i] = GetBlockIndex(&blocks[i - 1], 6000, nBits); + nBits = GetNextCashWorkRequired(&blocks[i++], &blkHeaderDummy, params); + + // Check the actual value. + BOOST_CHECK_EQUAL(nBits, 0x1c0d9222); + + // If we dramatically slow down block production, difficulty decreases. + for (size_t j = 0; j < 93; i++, j++) { + blocks[i] = GetBlockIndex(&blocks[i - 1], 6000, nBits); + const uint32_t nextBits = + GetNextCashWorkRequired(&blocks[i], &blkHeaderDummy, params); + + arith_uint256 currentTarget; + currentTarget.SetCompact(nBits); + arith_uint256 nextTarget; + nextTarget.SetCompact(nextBits); + + // Check the difficulty decreases. + BOOST_CHECK(nextTarget <= powLimit); + BOOST_CHECK(nextTarget > currentTarget); + BOOST_CHECK((nextTarget - currentTarget) < (currentTarget >> 3)); + + nBits = nextBits; + } + + // Check the actual value. + BOOST_CHECK_EQUAL(nBits, 0x1c2f13b9); + + // Due to the window of time being bounded, next block's difficulty actually + // gets harder. + blocks[i] = GetBlockIndex(&blocks[i - 1], 6000, nBits); + nBits = GetNextCashWorkRequired(&blocks[i++], &blkHeaderDummy, params); + BOOST_CHECK_EQUAL(nBits, 0x1c2ee9bf); + + // And goes down again. It takes a while due to the window being bounded and + // the skewed block causes 2 blocks to get out of the window. + for (size_t j = 0; j < 192; i++, j++) { + blocks[i] = GetBlockIndex(&blocks[i - 1], 6000, nBits); + const uint32_t nextBits = + GetNextCashWorkRequired(&blocks[i], &blkHeaderDummy, params); + + arith_uint256 currentTarget; + currentTarget.SetCompact(nBits); + arith_uint256 nextTarget; + nextTarget.SetCompact(nextBits); + + // Check the difficulty decreases. + BOOST_CHECK(nextTarget <= powLimit); + BOOST_CHECK(nextTarget > currentTarget); + BOOST_CHECK((nextTarget - currentTarget) < (currentTarget >> 3)); + + nBits = nextBits; + } + + // Check the actual value. + BOOST_CHECK_EQUAL(nBits, 0x1d00ffff); + + // Once the difficulty reached the minimum allowed level, it doesn't get any + // easier. + for (size_t j = 0; j < 5; i++, j++) { + blocks[i] = GetBlockIndex(&blocks[i - 1], 6000, nBits); + const uint32_t nextBits = + GetNextCashWorkRequired(&blocks[i], &blkHeaderDummy, params); + + // Check the difficulty stays constant. + BOOST_CHECK_EQUAL(nextBits, powLimitBits); + nBits = nextBits; + } +} + BOOST_AUTO_TEST_SUITE_END()