Bitcoin Core  27.99.0
P2P Digital Currency
feeratediagram.cpp
Go to the documentation of this file.
1 // Copyright (c) 2023 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 <stdint.h>
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 <assert.h>
16 
17 namespace {
18 
23 FeeFrac EvaluateDiagram(int32_t size, Span<const FeeFrac> diagram)
24 {
25  assert(diagram.size() > 0);
26  unsigned not_above = 0;
27  unsigned not_below = diagram.size() - 1;
28  // If outside the range of diagram, extend begin/end.
29  if (size < diagram[not_above].size) return {diagram[not_above].fee, 1};
30  if (size > diagram[not_below].size) return {diagram[not_below].fee, 1};
31  // Perform bisection search to locate the diagram segment that size is in.
32  while (not_below > not_above + 1) {
33  unsigned mid = (not_below + not_above) / 2;
34  if (diagram[mid].size <= size) not_above = mid;
35  if (diagram[mid].size >= size) not_below = mid;
36  }
37  // If the size matches a transition point between segments, return its fee.
38  if (not_below == not_above) return {diagram[not_below].fee, 1};
39  // Otherwise, interpolate.
40  auto dir_coef = diagram[not_below] - diagram[not_above];
41  assert(dir_coef.size > 0);
42  // Let A = diagram[not_above] and B = diagram[not_below]
43  const auto& point_a = diagram[not_above];
44  // We want to return:
45  // A.fee + (B.fee - A.fee) / (B.size - A.size) * (size - A.size)
46  // = A.fee + dir_coef.fee / dir_coef.size * (size - A.size)
47  // = (A.fee * dir_coef.size + dir_coef.fee * (size - A.size)) / dir_coef.size
48  assert(size >= point_a.size);
49  return {point_a.fee * dir_coef.size + dir_coef.fee * (size - point_a.size), dir_coef.size};
50 }
51 
52 std::weak_ordering CompareFeeFracWithDiagram(const FeeFrac& ff, Span<const FeeFrac> diagram)
53 {
54  return FeeRateCompare(FeeFrac{ff.fee, 1}, EvaluateDiagram(ff.size, diagram));
55 }
56 
57 std::partial_ordering CompareDiagrams(Span<const FeeFrac> dia1, Span<const FeeFrac> dia2)
58 {
59  bool all_ge = true;
60  bool all_le = true;
61  for (const auto p1 : dia1) {
62  auto cmp = CompareFeeFracWithDiagram(p1, dia2);
63  if (std::is_lt(cmp)) all_ge = false;
64  if (std::is_gt(cmp)) all_le = false;
65  }
66  for (const auto p2 : dia2) {
67  auto cmp = CompareFeeFracWithDiagram(p2, dia1);
68  if (std::is_lt(cmp)) all_le = false;
69  if (std::is_gt(cmp)) all_ge = false;
70  }
71  if (all_ge && all_le) return std::partial_ordering::equivalent;
72  if (all_ge && !all_le) return std::partial_ordering::greater;
73  if (!all_ge && all_le) return std::partial_ordering::less;
74  return std::partial_ordering::unordered;
75 }
76 
77 void PopulateChunks(FuzzedDataProvider& fuzzed_data_provider, std::vector<FeeFrac>& chunks)
78 {
79  chunks.clear();
80 
81  LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 50)
82  {
83  chunks.emplace_back(fuzzed_data_provider.ConsumeIntegralInRange<int64_t>(INT32_MIN>>1, INT32_MAX>>1), fuzzed_data_provider.ConsumeIntegralInRange<int32_t>(1, 1000000));
84  }
85  return;
86 }
87 
88 } // namespace
89 
90 FUZZ_TARGET(build_and_compare_feerate_diagram)
91 {
92  // Generate a random set of chunks
93  FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
94  std::vector<FeeFrac> chunks1, chunks2;
95  FeeFrac empty{0, 0};
96 
97  PopulateChunks(fuzzed_data_provider, chunks1);
98  PopulateChunks(fuzzed_data_provider, chunks2);
99 
100  std::vector<FeeFrac> diagram1{BuildDiagramFromChunks(chunks1)};
101  std::vector<FeeFrac> diagram2{BuildDiagramFromChunks(chunks2)};
102 
103  assert(diagram1.front() == empty);
104  assert(diagram2.front() == empty);
105 
106  auto real = CompareFeerateDiagram(diagram1, diagram2);
107  auto sim = CompareDiagrams(diagram1, diagram2);
108  assert(real == sim);
109 
110  // Do explicit evaluation at up to 1000 points, and verify consistency with the result.
111  LIMITED_WHILE(fuzzed_data_provider.remaining_bytes(), 1000) {
112  int32_t size = fuzzed_data_provider.ConsumeIntegralInRange<int32_t>(0, diagram2.back().size);
113  auto eval1 = EvaluateDiagram(size, diagram1);
114  auto eval2 = EvaluateDiagram(size, diagram2);
115  auto cmp = FeeRateCompare(eval1, eval2);
116  if (std::is_lt(cmp)) assert(!std::is_gt(real));
117  if (std::is_gt(cmp)) assert(!std::is_lt(real));
118  }
119 }
T ConsumeIntegralInRange(T min, T max)
A Span is an object that can refer to a contiguous sequence of objects.
Definition: span.h:98
constexpr std::size_t size() const noexcept
Definition: span.h:187
FUZZ_TARGET(build_and_compare_feerate_diagram)
#define LIMITED_WHILE(condition, limit)
Can be used to limit a theoretically unbounded loop.
Definition: fuzz.h:23
Data structure storing a fee and size, ordered by increasing fee/size.
Definition: feefrac.h:39
int64_t fee
Definition: feefrac.h:63
int32_t size
Definition: feefrac.h:64
std::partial_ordering CompareFeerateDiagram(Span< const FeeFrac > dia0, Span< const FeeFrac > dia1)
Compares two feerate diagrams.
Definition: feefrac.cpp:22
std::vector< FeeFrac > BuildDiagramFromChunks(const Span< const FeeFrac > chunks)
Takes the pre-computed and topologically-valid chunks and generates a fee diagram which starts at Fee...
Definition: feefrac.cpp:10
assert(!tx.IsCoinBase())