feeratediagram.cpp raw
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::strong_ordering CompareFeeFracWithDiagram(const FeeFrac& ff, std::span<const FeeFrac> diagram)
67 {
68 return ByRatio{FeeFrac{ff.fee, 1}} <=> ByRatio{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 = ByRatio{eval1} <=> ByRatio{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 }
134