1  // Copyright (c) 2023-present The Bitcoin Core developers
  2  // Distributed under the MIT software license, see the accompanying
  3  // file COPYING or http://www.opensource.org/licenses/mit-license.php.
  4  
  5  #include <cstdint>
  6  
  7  #include <vector>
  8  
  9  #include <util/feefrac.h>
 10  #include <policy/rbf.h>
 11  
 12  #include <test/fuzz/fuzz.h>
 13  #include <test/fuzz/util.h>
 14  
 15  #include <cassert>
 16  
 17  namespace {
 18  
 19  /** Takes the pre-computed and topologically-valid chunks and generates a fee diagram which starts at FeeFrac of (0, 0) */
 20  std::vector<FeeFrac> BuildDiagramFromChunks(const std::span<const FeeFrac> chunks)
 21  {
 22      std::vector<FeeFrac> diagram;
 23      diagram.reserve(chunks.size() + 1);
 24  
 25      diagram.emplace_back(0, 0);
 26      for (auto& chunk : chunks) {
 27          diagram.emplace_back(diagram.back() + chunk);
 28      }
 29      return diagram;
 30  }
 31  
 32  
 33  /** Evaluate a diagram at a specific size, returning the fee as a fraction.
 34   *
 35   * Fees in diagram cannot exceed 2^32, as the returned evaluation could overflow
 36   * the FeeFrac::fee field in the result. */
 37  FeeFrac EvaluateDiagram(int32_t size, std::span<const FeeFrac> diagram)
 38  {
 39      assert(diagram.size() > 0);
 40      unsigned not_above = 0;
 41      unsigned not_below = diagram.size() - 1;
 42      // If outside the range of diagram, extend begin/end.
 43      if (size < diagram[not_above].size) return {diagram[not_above].fee, 1};
 44      if (size > diagram[not_below].size) return {diagram[not_below].fee, 1};
 45      // Perform bisection search to locate the diagram segment that size is in.
 46      while (not_below > not_above + 1) {
 47          unsigned mid = (not_below + not_above) / 2;
 48          if (diagram[mid].size <= size) not_above = mid;
 49          if (diagram[mid].size >= size) not_below = mid;
 50      }
 51      // If the size matches a transition point between segments, return its fee.
 52      if (not_below == not_above) return {diagram[not_below].fee, 1};
 53      // Otherwise, interpolate.
 54      auto dir_coef = diagram[not_below] - diagram[not_above];
 55      assert(dir_coef.size > 0);
 56      // Let A = diagram[not_above] and B = diagram[not_below]
 57      const auto& point_a = diagram[not_above];
 58      // We want to return:
 59      //     A.fee + (B.fee - A.fee) / (B.size - A.size) * (size - A.size)
 60      //   = A.fee + dir_coef.fee / dir_coef.size * (size - A.size)
 61      //   = (A.fee * dir_coef.size + dir_coef.fee * (size - A.size)) / dir_coef.size
 62      assert(size >= point_a.size);
 63      return {point_a.fee * dir_coef.size + dir_coef.fee * (size - point_a.size), dir_coef.size};
 64  }
 65  
 66  std::weak_ordering CompareFeeFracWithDiagram(const FeeFrac& ff, std::span<const FeeFrac> diagram)
 67  {
 68      return FeeRateCompare(FeeFrac{ff.fee, 1}, EvaluateDiagram(ff.size, diagram));
 69  }
 70  
 71  std::partial_ordering CompareDiagrams(std::span<const FeeFrac> dia1, std::span<const FeeFrac> dia2)
 72  {
 73      bool all_ge = true;
 74      bool all_le = true;
 75      for (const auto p1 : dia1) {
 76          auto cmp = CompareFeeFracWithDiagram(p1, dia2);
 77          if (std::is_lt(cmp)) all_ge = false;
 78          if (std::is_gt(cmp)) all_le = false;
 79      }
 80      for (const auto p2 : dia2) {
 81          auto cmp = CompareFeeFracWithDiagram(p2, dia1);
 82          if (std::is_lt(cmp)) all_le = false;
 83          if (std::is_gt(cmp)) all_ge = false;
 84      }
 85      if (all_ge && all_le) return std::partial_ordering::equivalent;
 86      if (all_ge && !all_le) return std::partial_ordering::greater;
 87      if (!all_ge && all_le) return std::partial_ordering::less;
 88      return std::partial_ordering::unordered;
 89  }
 90  
 91  void PopulateChunks(FuzzedDataProvider& fuzzed_data_provider, std::vector<FeeFrac>& chunks)
 92  {
 93      chunks.clear();
 94  
 95      LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 50)
 96      {
 97          chunks.emplace_back(fuzzed_data_provider.ConsumeIntegralInRange<int64_t>(INT32_MIN>>1, INT32_MAX>>1), fuzzed_data_provider.ConsumeIntegralInRange<int32_t>(1, 1000000));
 98      }
 99      return;
100  }
101  
102  } // namespace
103  
104  FUZZ_TARGET(build_and_compare_feerate_diagram)
105  {
106      // Generate a random set of chunks
107      FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
108      std::vector<FeeFrac> chunks1, chunks2;
109      FeeFrac empty{0, 0};
110  
111      PopulateChunks(fuzzed_data_provider, chunks1);
112      PopulateChunks(fuzzed_data_provider, chunks2);
113  
114      std::vector<FeeFrac> diagram1{BuildDiagramFromChunks(chunks1)};
115      std::vector<FeeFrac> diagram2{BuildDiagramFromChunks(chunks2)};
116  
117      assert(diagram1.front() == empty);
118      assert(diagram2.front() == empty);
119  
120      auto real = CompareChunks(chunks1, chunks2);
121      auto sim = CompareDiagrams(diagram1, diagram2);
122      assert(real == sim);
123  
124      // Do explicit evaluation at up to 1000 points, and verify consistency with the result.
125      LIMITED_WHILE(fuzzed_data_provider.remaining_bytes(), 1000) {
126          int32_t size = fuzzed_data_provider.ConsumeIntegralInRange<int32_t>(0, diagram2.back().size);
127          auto eval1 = EvaluateDiagram(size, diagram1);
128          auto eval2 = EvaluateDiagram(size, diagram2);
129          auto cmp = FeeRateCompare(eval1, eval2);
130          if (std::is_lt(cmp)) assert(!std::is_gt(real));
131          if (std::is_gt(cmp)) assert(!std::is_lt(real));
132      }
133  }