diff options
author | glozow <gloriajzhao@gmail.com> | 2024-03-26 08:48:01 +0000 |
---|---|---|
committer | glozow <gloriajzhao@gmail.com> | 2024-03-26 08:48:37 +0000 |
commit | c2dbbc35b99e3746407a0abba08032e5b0183ce0 (patch) | |
tree | f8068daae5585b1bb3329bcdfbeddcb3147e9d90 /src/util/feefrac.h | |
parent | b44f9e4645c00ee7dd669fdc9024716acdfb4720 (diff) | |
parent | 72959867784098137a50c34f86deca8235eef4f8 (diff) | |
download | bitcoin-c2dbbc35b99e3746407a0abba08032e5b0183ce0.tar.xz |
Merge bitcoin/bitcoin#29242: Mempool util: Add RBF diagram checks for single chunks against clusters of size 2
72959867784098137a50c34f86deca8235eef4f8 Unit tests for CalculateFeerateDiagramsForRBF (Greg Sanders)
b767e6bd47cb0fb8f7aea3fb10c597e59a35bf74 test: unit test for ImprovesFeerateDiagram (Greg Sanders)
7e89b659e1ddd0c04fa2bddba9706b5d1a1daec3 Add fuzz test for FeeFrac (Greg Sanders)
4d6528a3d6bf3821c216c68f99170e2faab5d63c fuzz: fuzz diagram creation and comparison (Greg Sanders)
e9c5aeb11d641b8cae373452339760809625021d test: Add tests for CompareFeerateDiagram and CheckConflictTopology (Greg Sanders)
588a98dccc5dbb6e331f28d83a4a10a13d70eb31 fuzz: Add fuzz target for ImprovesFeerateDiagram (Greg Sanders)
2079b80854e2595f6f696e7c13a56c7f2a7da9f4 Implement ImprovesFeerateDiagram (Greg Sanders)
66d966dcfaad3638f84654e710f403cb0a0a2ac7 Add FeeFrac unit tests (Greg Sanders)
ce8e22542ed0b4fa5794d3203207146418d59473 Add FeeFrac utils (Greg Sanders)
Pull request description:
This is a smaller piece of https://github.com/bitcoin/bitcoin/pull/28984 broken off for easier review.
Up to date explanation of diagram checks are here: https://delvingbitcoin.org/t/mempool-incentive-compatibility/553
This infrastructure has two near term applications prior to cluster mempool:
1) Limited Package RBF(https://github.com/bitcoin/bitcoin/pull/28984): We want to allow package RBF only when we know it improves the mempool. This narrowly scoped functionality allows use with v3-like topologies, and will be expanded at some point post-cluster mempool when diagram checks can be done efficiently against bounded cluster sizes.
2) Replacement for single tx RBF(in a cluster size of up to two) against conflicts of up to cluster size two. `ImprovesFeerateDiagram` interface will have to change for this use-case, which is a future direction to solve certain pins and improve mempool incentive compatibility: https://delvingbitcoin.org/t/ephemeral-anchors-and-mev/383#diagram-checks-fix-this-3
And longer-term, this would be the proposed way we would compute incentive compatibility for all conflicts, post-cluster mempool.
ACKs for top commit:
sipa:
utACK 72959867784098137a50c34f86deca8235eef4f8
glozow:
code review ACK 72959867784098137a50c34f86deca8235eef4f8
murchandamus:
utACK 72959867784098137a50c34f86deca8235eef4f8
ismaelsadeeq:
Re-ACK https://github.com/bitcoin/bitcoin/commit/72959867784098137a50c34f86deca8235eef4f8
willcl-ark:
crACK 72959867784098137a50c34f86deca8235eef4f8
sdaftuar:
ACK 72959867784098137a50c34f86deca8235eef4f8
Tree-SHA512: 79593e5a087801c06f06cc8b73aa3e7b96ab938d3b90f5d229c4e4bfca887a77b447605c49aa5eb7ddcead85706c534ac5eb6146ae2396af678f4beaaa5bea8e
Diffstat (limited to 'src/util/feefrac.h')
-rw-r--r-- | src/util/feefrac.h | 160 |
1 files changed, 160 insertions, 0 deletions
diff --git a/src/util/feefrac.h b/src/util/feefrac.h new file mode 100644 index 0000000000..48bd287c7c --- /dev/null +++ b/src/util/feefrac.h @@ -0,0 +1,160 @@ +// Copyright (c) The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#ifndef BITCOIN_UTIL_FEEFRAC_H +#define BITCOIN_UTIL_FEEFRAC_H + +#include <stdint.h> +#include <compare> +#include <vector> +#include <span.h> +#include <util/check.h> + +/** Data structure storing a fee and size, ordered by increasing fee/size. + * + * The size of a FeeFrac cannot be zero unless the fee is also zero. + * + * FeeFracs have a total ordering, first by increasing feerate (ratio of fee over size), and then + * by decreasing size. The empty FeeFrac (fee and size both 0) sorts last. So for example, the + * following FeeFracs are in sorted order: + * + * - fee=0 size=1 (feerate 0) + * - fee=1 size=2 (feerate 0.5) + * - fee=2 size=3 (feerate 0.667...) + * - fee=2 size=2 (feerate 1) + * - fee=1 size=1 (feerate 1) + * - fee=3 size=2 (feerate 1.5) + * - fee=2 size=1 (feerate 2) + * - fee=0 size=0 (undefined feerate) + * + * A FeeFrac is considered "better" if it sorts after another, by this ordering. All standard + * comparison operators (<=>, ==, !=, >, <, >=, <=) respect this ordering. + * + * The CompareFeeFrac, and >> and << operators only compare feerate and treat equal feerate but + * different size as equivalent. The empty FeeFrac is neither lower or higher in feerate than any + * other. + */ +struct FeeFrac +{ + /** Fallback version for Mul (see below). + * + * Separate to permit testing on platforms where it isn't actually needed. + */ + static inline std::pair<int64_t, uint32_t> MulFallback(int64_t a, int32_t b) noexcept + { + // Otherwise, emulate 96-bit multiplication using two 64-bit multiplies. + int64_t low = int64_t{static_cast<uint32_t>(a)} * b; + int64_t high = (a >> 32) * b; + return {high + (low >> 32), static_cast<uint32_t>(low)}; + } + + // Compute a * b, returning an unspecified but totally ordered type. +#ifdef __SIZEOF_INT128__ + static inline __int128 Mul(int64_t a, int32_t b) noexcept + { + // If __int128 is available, use 128-bit wide multiply. + return __int128{a} * b; + } +#else + static constexpr auto Mul = MulFallback; +#endif + + int64_t fee; + int32_t size; + + /** Construct an IsEmpty() FeeFrac. */ + inline FeeFrac() noexcept : fee{0}, size{0} {} + + /** Construct a FeeFrac with specified fee and size. */ + inline FeeFrac(int64_t f, int32_t s) noexcept : fee{f}, size{s} {} + + inline FeeFrac(const FeeFrac&) noexcept = default; + inline FeeFrac& operator=(const FeeFrac&) noexcept = default; + + /** Check if this is empty (size and fee are 0). */ + bool inline IsEmpty() const noexcept { + return size == 0; + } + + /** Add fee and size of another FeeFrac to this one. */ + void inline operator+=(const FeeFrac& other) noexcept + { + fee += other.fee; + size += other.size; + } + + /** Subtract fee and size of another FeeFrac from this one. */ + void inline operator-=(const FeeFrac& other) noexcept + { + fee -= other.fee; + size -= other.size; + } + + /** Sum fee and size. */ + friend inline FeeFrac operator+(const FeeFrac& a, const FeeFrac& b) noexcept + { + return {a.fee + b.fee, a.size + b.size}; + } + + /** Subtract both fee and size. */ + friend inline FeeFrac operator-(const FeeFrac& a, const FeeFrac& b) noexcept + { + return {a.fee - b.fee, a.size - b.size}; + } + + /** Check if two FeeFrac objects are equal (both same fee and same size). */ + friend inline bool operator==(const FeeFrac& a, const FeeFrac& b) noexcept + { + return a.fee == b.fee && a.size == b.size; + } + + /** Compare two FeeFracs just by feerate. */ + friend inline std::weak_ordering FeeRateCompare(const FeeFrac& a, const FeeFrac& b) noexcept + { + auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size); + return cross_a <=> cross_b; + } + + /** Check if a FeeFrac object has strictly lower feerate than another. */ + friend inline bool operator<<(const FeeFrac& a, const FeeFrac& b) noexcept + { + auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size); + return cross_a < cross_b; + } + + /** Check if a FeeFrac object has strictly higher feerate than another. */ + friend inline bool operator>>(const FeeFrac& a, const FeeFrac& b) noexcept + { + auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size); + return cross_a > cross_b; + } + + /** Compare two FeeFracs. <, >, <=, and >= are auto-generated from this. */ + friend inline std::strong_ordering operator<=>(const FeeFrac& a, const FeeFrac& b) noexcept + { + auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size); + if (cross_a == cross_b) return b.size <=> a.size; + return cross_a <=> cross_b; + } + + /** Swap two FeeFracs. */ + friend inline void swap(FeeFrac& a, FeeFrac& b) noexcept + { + std::swap(a.fee, b.fee); + std::swap(a.size, b.size); + } +}; + +/** Takes the pre-computed and topologically-valid chunks and generates a fee diagram which starts at FeeFrac of (0, 0) */ +std::vector<FeeFrac> BuildDiagramFromChunks(Span<const FeeFrac> chunks); + +/** Compares two feerate diagrams. The shorter one is implicitly + * extended with a horizontal straight line. + * + * A feerate diagram consists of a list of (fee, size) points with the property that size + * is strictly increasing and that the first entry is (0, 0). + */ +std::partial_ordering CompareFeerateDiagram(Span<const FeeFrac> dia0, Span<const FeeFrac> dia1); + +#endif // BITCOIN_UTIL_FEEFRAC_H |