Add function to validate difficulty changes

The rule against difficulty adjustments changing by more than a factor of 4 can
be helpful for anti-DoS measures in contexts where we lack a full headers
chain, so expose this functionality separately and in the narrow case where we
only know the height, new value, and old value.

Includes fuzz test by Martin Zumsande.

4 files changed, 125 insertions, 4 deletions

diff --git a/src/pow.cpp b/src/pow.cpp
index 1414d37564..c0449cac74 100644
--- a/src/pow.cpp
+++ b/src/pow.cpp
@@ -71,6 +71,57 @@ unsigned int CalculateNextWorkRequired(const CBlockIndex* pindexLast, int64_t nF
     return bnNew.GetCompact();
 }
 
+// Check that on difficulty adjustments, the new difficulty does not increase
+// or decrease beyond the permitted limits.
+bool PermittedDifficultyTransition(const Consensus::Params& params, int64_t height, uint32_t old_nbits, uint32_t new_nbits)
+{
+    if (params.fPowAllowMinDifficultyBlocks) return true;
+
+    if (height % params.DifficultyAdjustmentInterval() == 0) {
+        int64_t smallest_timespan = params.nPowTargetTimespan/4;
+        int64_t largest_timespan = params.nPowTargetTimespan*4;
+
+        const arith_uint256 pow_limit = UintToArith256(params.powLimit);
+        arith_uint256 observed_new_target;
+        observed_new_target.SetCompact(new_nbits);
+
+        // Calculate the largest difficulty value possible:
+        arith_uint256 largest_difficulty_target;
+        largest_difficulty_target.SetCompact(old_nbits);
+        largest_difficulty_target *= largest_timespan;
+        largest_difficulty_target /= params.nPowTargetTimespan;
+
+        if (largest_difficulty_target > pow_limit) {
+            largest_difficulty_target = pow_limit;
+        }
+
+        // Round and then compare this new calculated value to what is
+        // observed.
+        arith_uint256 maximum_new_target;
+        maximum_new_target.SetCompact(largest_difficulty_target.GetCompact());
+        if (maximum_new_target < observed_new_target) return false;
+
+        // Calculate the smallest difficulty value possible:
+        arith_uint256 smallest_difficulty_target;
+        smallest_difficulty_target.SetCompact(old_nbits);
+        smallest_difficulty_target *= smallest_timespan;
+        smallest_difficulty_target /= params.nPowTargetTimespan;
+
+        if (smallest_difficulty_target > pow_limit) {
+            smallest_difficulty_target = pow_limit;
+        }
+
+        // Round and then compare this new calculated value to what is
+        // observed.
+        arith_uint256 minimum_new_target;
+        minimum_new_target.SetCompact(smallest_difficulty_target.GetCompact());
+        if (minimum_new_target > observed_new_target) return false;
+    } else if (old_nbits != new_nbits) {
+        return false;
+    }
+    return true;
+}
+
 bool CheckProofOfWork(uint256 hash, unsigned int nBits, const Consensus::Params& params)
 {
     bool fNegative;
diff --git a/src/pow.h b/src/pow.h
index 1d802cd01e..44b9d673ef 100644
--- a/src/pow.h
+++ b/src/pow.h
@@ -20,4 +20,18 @@ unsigned int CalculateNextWorkRequired(const CBlockIndex* pindexLast, int64_t nF
 /** Check whether a block hash satisfies the proof-of-work requirement specified by nBits */
 bool CheckProofOfWork(uint256 hash, unsigned int nBits, const Consensus::Params&);
 
+/**
+ * Return false if the proof-of-work requirement specified by new_nbits at a
+ * given height is not possible, given the proof-of-work on the prior block as
+ * specified by old_nbits.
+ *
+ * This function only checks that the new value is within a factor of 4 of the
+ * old value for blocks at the difficulty adjustment interval, and otherwise
+ * requires the values to be the same.
+ *
+ * Always returns true on networks where min difficulty blocks are allowed,
+ * such as regtest/testnet.
+ */
+bool PermittedDifficultyTransition(const Consensus::Params& params, int64_t height, uint32_t old_nbits, uint32_t new_nbits);
+
 #endif // BITCOIN_POW_H
diff --git a/src/test/fuzz/pow.cpp b/src/test/fuzz/pow.cpp
index 0004d82d66..507ce57ec0 100644
--- a/src/test/fuzz/pow.cpp
+++ b/src/test/fuzz/pow.cpp
@@ -83,3 +83,40 @@ FUZZ_TARGET_INIT(pow, initialize_pow)
         }
     }
 }
+
+
+FUZZ_TARGET_INIT(pow_transition, initialize_pow)
+{
+    FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
+    const Consensus::Params& consensus_params{Params().GetConsensus()};
+    std::vector<std::unique_ptr<CBlockIndex>> blocks;
+
+    const uint32_t old_time{fuzzed_data_provider.ConsumeIntegral<uint32_t>()};
+    const uint32_t new_time{fuzzed_data_provider.ConsumeIntegral<uint32_t>()};
+    const int32_t version{fuzzed_data_provider.ConsumeIntegral<int32_t>()};
+    uint32_t nbits{fuzzed_data_provider.ConsumeIntegral<uint32_t>()};
+
+    const arith_uint256 pow_limit = UintToArith256(consensus_params.powLimit);
+    arith_uint256 old_target;
+    old_target.SetCompact(nbits);
+    if (old_target > pow_limit) {
+        nbits = pow_limit.GetCompact();
+    }
+    // Create one difficulty adjustment period worth of headers
+    for (int height = 0; height < consensus_params.DifficultyAdjustmentInterval(); ++height) {
+        CBlockHeader header;
+        header.nVersion = version;
+        header.nTime = old_time;
+        header.nBits = nbits;
+        if (height == consensus_params.DifficultyAdjustmentInterval() - 1) {
+            header.nTime = new_time;
+        }
+        auto current_block{std::make_unique<CBlockIndex>(header)};
+        current_block->pprev = blocks.empty() ? nullptr : blocks.back().get();
+        current_block->nHeight = height;
+        blocks.emplace_back(std::move(current_block)).get();
+    }
+    auto last_block{blocks.back().get()};
+    unsigned int new_nbits{GetNextWorkRequired(last_block, nullptr, consensus_params)};
+    Assert(PermittedDifficultyTransition(consensus_params, last_block->nHeight + 1, last_block->nBits, new_nbits));
+}
diff --git a/src/test/pow_tests.cpp b/src/test/pow_tests.cpp
index 2f43ae52f7..3695ea9d16 100644
--- a/src/test/pow_tests.cpp
+++ b/src/test/pow_tests.cpp
@@ -20,7 +20,14 @@ BOOST_AUTO_TEST_CASE(get_next_work)
     pindexLast.nHeight = 32255;
     pindexLast.nTime = 1262152739;  // Block #32255
     pindexLast.nBits = 0x1d00ffff;
-    BOOST_CHECK_EQUAL(CalculateNextWorkRequired(&pindexLast, nLastRetargetTime, chainParams->GetConsensus()), 0x1d00d86aU);
+
+    // Here (and below): expected_nbits is calculated in
+    // CalculateNextWorkRequired(); redoing the calculation here would be just
+    // reimplementing the same code that is written in pow.cpp. Rather than
+    // copy that code, we just hardcode the expected result.
+    unsigned int expected_nbits = 0x1d00d86aU;
+    BOOST_CHECK_EQUAL(CalculateNextWorkRequired(&pindexLast, nLastRetargetTime, chainParams->GetConsensus()), expected_nbits);
+    BOOST_CHECK(PermittedDifficultyTransition(chainParams->GetConsensus(), pindexLast.nHeight+1, pindexLast.nBits, expected_nbits));
 }
 
 /* Test the constraint on the upper bound for next work */
@@ -32,7 +39,9 @@ BOOST_AUTO_TEST_CASE(get_next_work_pow_limit)
     pindexLast.nHeight = 2015;
     pindexLast.nTime = 1233061996;  // Block #2015
     pindexLast.nBits = 0x1d00ffff;
-    BOOST_CHECK_EQUAL(CalculateNextWorkRequired(&pindexLast, nLastRetargetTime, chainParams->GetConsensus()), 0x1d00ffffU);
+    unsigned int expected_nbits = 0x1d00ffffU;
+    BOOST_CHECK_EQUAL(CalculateNextWorkRequired(&pindexLast, nLastRetargetTime, chainParams->GetConsensus()), expected_nbits);
+    BOOST_CHECK(PermittedDifficultyTransition(chainParams->GetConsensus(), pindexLast.nHeight+1, pindexLast.nBits, expected_nbits));
 }
 
 /* Test the constraint on the lower bound for actual time taken */
@@ -44,7 +53,12 @@ BOOST_AUTO_TEST_CASE(get_next_work_lower_limit_actual)
     pindexLast.nHeight = 68543;
     pindexLast.nTime = 1279297671;  // Block #68543
     pindexLast.nBits = 0x1c05a3f4;
-    BOOST_CHECK_EQUAL(CalculateNextWorkRequired(&pindexLast, nLastRetargetTime, chainParams->GetConsensus()), 0x1c0168fdU);
+    unsigned int expected_nbits = 0x1c0168fdU;
+    BOOST_CHECK_EQUAL(CalculateNextWorkRequired(&pindexLast, nLastRetargetTime, chainParams->GetConsensus()), expected_nbits);
+    BOOST_CHECK(PermittedDifficultyTransition(chainParams->GetConsensus(), pindexLast.nHeight+1, pindexLast.nBits, expected_nbits));
+    // Test that reducing nbits further would not be a PermittedDifficultyTransition.
+    unsigned int invalid_nbits = expected_nbits-1;
+    BOOST_CHECK(!PermittedDifficultyTransition(chainParams->GetConsensus(), pindexLast.nHeight+1, pindexLast.nBits, invalid_nbits));
 }
 
 /* Test the constraint on the upper bound for actual time taken */
@@ -56,7 +70,12 @@ BOOST_AUTO_TEST_CASE(get_next_work_upper_limit_actual)
     pindexLast.nHeight = 46367;
     pindexLast.nTime = 1269211443;  // Block #46367
     pindexLast.nBits = 0x1c387f6f;
-    BOOST_CHECK_EQUAL(CalculateNextWorkRequired(&pindexLast, nLastRetargetTime, chainParams->GetConsensus()), 0x1d00e1fdU);
+    unsigned int expected_nbits = 0x1d00e1fdU;
+    BOOST_CHECK_EQUAL(CalculateNextWorkRequired(&pindexLast, nLastRetargetTime, chainParams->GetConsensus()), expected_nbits);
+    BOOST_CHECK(PermittedDifficultyTransition(chainParams->GetConsensus(), pindexLast.nHeight+1, pindexLast.nBits, expected_nbits));
+    // Test that increasing nbits further would not be a PermittedDifficultyTransition.
+    unsigned int invalid_nbits = expected_nbits+1;
+    BOOST_CHECK(!PermittedDifficultyTransition(chainParams->GetConsensus(), pindexLast.nHeight+1, pindexLast.nBits, invalid_nbits));
 }
 
 BOOST_AUTO_TEST_CASE(CheckProofOfWork_test_negative_target)