FeeFrac arithmetic, Core's chunk-diagram comparison, and the cluster-mempool replacement check
DefinitionBitcoinFeerateDiagramA transcription of the cluster mempool's replacement check over the replace-by-fee mission's BitcoinReplacement, at Bitcoin Core revision a773e1e, where it replaced BIP125 rule 3.
FeeFrac — a fee and a size (integers). IsEmpty, mul, mulFallback (the 32-bit split multiplication), div (round down or up), divFallback, ceilDiv, evaluateFee, evaluateFeeDown, evaluateFeeUp — Core's arithmetic, with both code paths. byRatioCmp a b — compare (a.fee · b.size) (b.fee · a.size), the ByRatio ordering; ratio a — fee / size in .
PartialOrdering — less, equivalent, greater, unordered; boolCompare. sweep — the loop of CompareChunks, one equation per iteration over the two chunk lists with the accumulated (fee, size) of each and the two "better somewhere" flags; compareChunks c0 c1 — Core's CompareChunks. ImprovesFeerateDiagram old new — compareChunks new old = greater (policy/rbf.cpp).
diagram cs x — the feerate diagram as a function: the cumulative fee at cumulative size , linear within each chunk and constant after the last; diagramFee, diagramSize — totals. SizesPos — every chunk has positive size; FeeratesNonIncreasing — chunk feerates in non-increasing order. Dominates c0 c1 — diagram c0 ≥ diagram c1 on ; BetterSomewhere c0 c1 — strictly greater at some ; StrictlyBetter — both.
Formalization Note. Imports Mathlib and the replacement mission. The chunk lists (the linearization of the affected clusters, txmempool.cpp/txgraph.cpp) are taken as input; fees and sizes are unbounded integers, so overflow is not modelled.
import Mathlib
import Definitions.Def_BitcoinReplacement
/-!
# Bitcoin Core's feerate-diagram replacement check (`ImprovesFeerateDiagram`)
At bitcoin/bitcoin revision `a773e1e33b349dc819b5a0edc1c7a4839dc73b48` BIP125 rule 3
("the replacement pays a higher feerate than each directly conflicting transaction") is gone from
`policy/rbf.cpp`; it has been replaced by the cluster-mempool check
```cpp
std::optional<std::pair<DiagramCheckError, std::string>> ImprovesFeerateDiagram(CTxMemPool::ChangeSet& changeset)
{
const auto chunk_results{changeset.CalculateChunksForRBF()};
if (!chunk_results.has_value()) { return {DiagramCheckError::UNCALCULABLE, ...}; }
if (!std::is_gt(CompareChunks(chunk_results.value().second, chunk_results.value().first))) {
return {DiagramCheckError::FAILURE, "insufficient feerate: does not improve feerate diagram"};
}
return std::nullopt;
}
```
(`policy/rbf.cpp`, lines 127–140). `CalculateChunksForRBF` (`txmempool.cpp` 1042–1051) returns
`TxGraph::GetMainStagingDiagrams()` (`txgraph.cpp` 2810–2834): `first` is the list of chunk
feerates (`FeeFrac`s) of every *main* cluster that the replacement touches, `second` the list of
chunk feerates of every *staging* cluster (the same transactions with the conflicts removed and the
replacement added), each list sorted by decreasing feerate (`ByRatioNegSize`). The replacement is
accepted iff `CompareChunks(new, old)` is `std::partial_ordering::greater`.
This file transcribes
* `FeeFrac` (`util/feefrac.h`): a (fee, size) pair with `int64_t` fee and `int32_t` size, its `+`
and `-`, the `ByRatio` feerate comparison by cross-multiplication, and the fee evaluation
`EvaluateFee<RoundDown>` together with the `Mul`/`Div` and `MulFallback`/`DivFallback` helpers;
* `CompareChunks` (`util/feefrac.cpp`, lines 12–75): the sweep over the breakpoints of the two
piecewise-linear diagrams, as a function on `List FeeFrac`;
* `ImprovesFeerateDiagram` as the predicate `CompareChunks new old = greater`;
* the mathematical object the sweep compares: the *diagram function* `diagram cs : ℚ → ℚ` of a chunk
list, the piecewise-linear function through the cumulative (size, fee) points, extended
horizontally to the right ("The implied diagram for each starts at (0, 0), then contains for each
chunk the cumulative fee and size up to that chunk, and then extends infinitely to the right with
a horizontal line", `util/feefrac.h`).
The chunk lists themselves (the output of cluster linearisation and chunking,
`ChunkLinearization` in `cluster_linearize.h`) are taken as *input*: nothing here models
clusters, dependencies or linearisations. Machine-integer overflow is not modelled: all arithmetic
is in `ℤ`/`ℚ`, which is what the C++ computes under the documented preconditions
("the sum of the FeeFracs in either of the chunks' data set do not overflow").
-/
namespace BitcoinFeerateDiagram
/-- `struct FeeFrac { int64_t fee; int32_t size; }` (`util/feefrac.h`). A fee and a size; "the size
of a FeeFrac cannot be zero unless the fee is also zero". Modelled with unbounded integers. -/
structure FeeFrac where
/-- `int64_t fee` (satoshi; may be negative, e.g. after `prioritisetransaction`). -/
fee : ℤ
/-- `int32_t size` (vbytes or weight units, depending on the tag). -/
size : ℤ
deriving DecidableEq, Repr
namespace FeeFrac
/-- `FeeFrac()` : the empty `FeeFrac` (fee 0, size 0), the initial value of `accum` in
`CompareChunks`. -/
instance : Zero FeeFrac := ⟨⟨0, 0⟩⟩
/-- `operator+(a, b) = {a.fee + b.fee, a.size + b.size}`. -/
instance : Add FeeFrac := ⟨fun a b => ⟨a.fee + b.fee, a.size + b.size⟩⟩
/-- `operator-(a, b) = {a.fee - b.fee, a.size - b.size}`. -/
instance : Sub FeeFrac := ⟨fun a b => ⟨a.fee - b.fee, a.size - b.size⟩⟩
/-- `IsEmpty()`: `size == 0`. -/
def IsEmpty (a : FeeFrac) : Prop := a.size = 0
/-- `FeeFrac::Mul(int64_t a, int32_t b)` (the `__int128` version): the exact product. -/
def mul (a b : ℤ) : ℤ := a * b
/-- `FeeFrac::MulFallback(int64_t a, int32_t b)`: the 32×64 signed product returned as a pair
`(high, low32)` whose value is `high * 2^32 + low32`:
```cpp
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)};
```
`static_cast<uint32_t>(x)` is `x mod 2^32` and the arithmetic shift `x >> 32` is
`⌊x / 2^32⌋`; in ℤ, `/` and `%` are floor division and nonnegative remainder, which is exactly this. -/
def mulFallback (a b : ℤ) : ℤ × ℤ :=
let low := (a % 2 ^ 32) * b
let high := (a / 2 ^ 32) * b
(high + low / 2 ^ 32, low % 2 ^ 32)
/-- `FeeFrac::Div(__int128 n, int32_t d, bool round_down)`: C++ `/` and `%` truncate towards zero
(`Int.tdiv`, `Int.tmod`), then the quotient is corrected so that the result rounds towards
`-∞` (if `round_down`) or `+∞` (otherwise):
```cpp
int64_t quot = n / d;
int32_t mod = n % d;
return quot + ((mod > 0) - (mod && round_down));
```
Requires `d > 0`. -/
def div (n d : ℤ) (roundDown : Bool) : ℤ :=
n.tdiv d + ((if 0 < n.tmod d then 1 else 0) - (if n.tmod d ≠ 0 ∧ roundDown then 1 else 0))
/-- `FeeFrac::DivFallback(std::pair<int64_t, uint32_t> n, int32_t d, bool round_down)`, the 96/32
division of the value `n.first * 2^32 + n.second` (as produced by `mulFallback`):
```cpp
int64_t quot_high = n.first / d;
int64_t n_low = ((n.first % d) << 32) + n.second;
int64_t quot_low = n_low / d;
int32_t mod_low = n_low % d;
quot_low += (mod_low > 0) - (mod_low && round_down);
return (quot_high << 32) + quot_low;
```
C++ `/`, `%` truncate towards zero; `<< 32` on a signed value is multiplication by `2^32`. -/
def divFallback (n : ℤ × ℤ) (d : ℤ) (roundDown : Bool) : ℤ :=
let quotHigh := n.1.tdiv d
let nLow := (n.1.tmod d) * 2 ^ 32 + n.2
let quotLow := nLow.tdiv d
let modLow := nLow.tmod d
let quotLow' := quotLow + ((if 0 < modLow then 1 else 0) - (if modLow ≠ 0 ∧ roundDown then 1 else 0))
quotHigh * 2 ^ 32 + quotLow'
/-- `CeilDiv(dividend, divisor)` (`util/overflow.h`, unsigned): `dividend / divisor + (dividend %
divisor != 0)`. Stated on `ℤ` for nonnegative operands, where `/` and `%` agree with the unsigned
operations. -/
def ceilDiv (n d : ℤ) : ℤ := n / d + (if n % d ≠ 0 then 1 else 0)
/-- `FeeFrac::EvaluateFee<RoundDown>(int32_t at_size)` (`util/feefrac.h`): the fee for `at_size`
units at this object's feerate, `(fee * at_size) / size` rounded towards `-∞` (`RoundDown`) or
`+∞`. Requires `size > 0` and `at_size ≥ 0`.
```cpp
if (fee >= 0 && fee < 0x200000000) [[likely]] {
if constexpr (RoundDown) { return (uint64_t(fee) * at_size) / uint32_t(size); }
else { return CeilDiv(uint64_t(fee) * at_size, uint32_t(size)); }
} else {
return Div(Mul(fee, at_size), size, RoundDown);
}
```
In the first branch all operands are nonnegative, so the unsigned `uint64_t` operations are the
integer operations on `ℤ` (no overflow by the stated precondition). -/
def evaluateFee (f : FeeFrac) (atSize : ℤ) (roundDown : Bool) : ℤ :=
if 0 ≤ f.fee ∧ f.fee < 2 ^ 33 then
if roundDown then (f.fee * atSize) / f.size else ceilDiv (f.fee * atSize) f.size
else div (mul f.fee atSize) f.size roundDown
/-- `EvaluateFeeDown(at_size) = EvaluateFee<true>(at_size)`. -/
def evaluateFeeDown (f : FeeFrac) (atSize : ℤ) : ℤ := evaluateFee f atSize true
/-- `EvaluateFeeUp(at_size) = EvaluateFee<false>(at_size)`. -/
def evaluateFeeUp (f : FeeFrac) (atSize : ℤ) : ℤ := evaluateFee f atSize false
/-- `ByRatio` comparison `operator<=>(ByRatio a, ByRatio b)`:
```cpp
auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
return cross_a <=> cross_b;
```
i.e. the feerates `a.fee / a.size` and `b.fee / b.size` compared by cross-multiplication, with no
rounding (`std::strong_ordering`, mapped to `Ordering`). -/
def byRatioCmp (a b : FeeFrac) : Ordering := compare (mul a.fee b.size) (mul b.fee a.size)
/-- The feerate of a `FeeFrac` as an exact rational number (`fee / size`). -/
def ratio (a : FeeFrac) : ℚ := (a.fee : ℚ) / (a.size : ℚ)
end FeeFrac
/-- `std::partial_ordering`, the result type of `CompareChunks`. -/
inductive PartialOrdering
| less
| equivalent
| greater
| unordered
deriving DecidableEq, Repr
/-- `better_somewhere[0] <=> better_somewhere[1]` on `bool` (`false < true`), the final `return` of
`CompareChunks` (reached only when at most one of the two flags is set). -/
def boolCompare (b0 b1 : Bool) : PartialOrdering :=
match b0, b1 with
| false, false => .equivalent
| false, true => .less
| true, false => .greater
| true, true => .equivalent
/-- The `do { … } while(true)` loop of `CompareChunks` (`util/feefrac.cpp`, lines 29–71), as a
function of its state: `rem0`, `rem1` are the unprocessed chunks of the two inputs
(`chunk[i][next_index[i]..]`), `acc0`, `acc1` the accumulated points `accum[i]`, and `b0`, `b1` the
flags `better_somewhere[i]`. Each arm is one iteration:
* `done_0 && done_1` → `break`, then `return better_somewhere[0] <=> better_somewhere[1]`;
* exactly one side done → `unproc_side` is the other side, `P = next_point(unproc_side)`,
`A = prev_point(!unproc_side)`, and `cmp = ByRatio{P - A} <=> ByRatio{FeeFrac(0, 1)}`
("act as if AB has slope tail_feerate(of 0)");
* both sides have points left → `unproc_side = next_point(0).size > next_point(1).size`,
`B = next_point(!unproc_side)`, `cmp = ByRatio{P - A} <=> ByRatio{B - A}`, and if
`B.size == P.size` the other side is advanced as well;
then `if (is_gt(cmp)) better_somewhere[unproc_side] = true; if (is_lt(cmp))
better_somewhere[!unproc_side] = true; advance(unproc_side); if (both flags) return unordered;`. -/
def sweep : List FeeFrac → List FeeFrac → FeeFrac → FeeFrac → Bool → Bool → PartialOrdering
| [], [], _, _, b0, b1 => boolCompare b0 b1
| c0 :: r0, [], acc0, acc1, b0, b1 =>
-- done_1: unproc_side = 0, P = chunk[0][next] + accum[0], A = accum[1]
let p := c0 + acc0
let cmp := FeeFrac.byRatioCmp (p - acc1) ⟨0, 1⟩
let b0' := b0 || (cmp == .gt)
let b1' := b1 || (cmp == .lt)
if b0' && b1' then .unordered else sweep r0 [] p acc1 b0' b1'
| [], c1 :: r1, acc0, acc1, b0, b1 =>
-- done_0: unproc_side = 1, P = chunk[1][next] + accum[1], A = accum[0]
let p := c1 + acc1
let cmp := FeeFrac.byRatioCmp (p - acc0) ⟨0, 1⟩
let b1' := b1 || (cmp == .gt)
let b0' := b0 || (cmp == .lt)
if b0' && b1' then .unordered else sweep [] r1 acc0 p b0' b1'
| c0 :: r0, c1 :: r1, acc0, acc1, b0, b1 =>
let p0 := c0 + acc0
let p1 := c1 + acc1
if p0.size > p1.size then
-- unproc_side = 1: P = p1, A = accum[0], B = p0 (B.size ≠ P.size here)
let cmp := FeeFrac.byRatioCmp (p1 - acc0) (p0 - acc0)
let b1' := b1 || (cmp == .gt)
let b0' := b0 || (cmp == .lt)
if b0' && b1' then .unordered else sweep (c0 :: r0) r1 acc0 p1 b0' b1'
else
-- unproc_side = 0: P = p0, A = accum[1], B = p1
let cmp := FeeFrac.byRatioCmp (p0 - acc1) (p1 - acc1)
let b0' := b0 || (cmp == .gt)
let b1' := b1 || (cmp == .lt)
if b0' && b1' then .unordered
else if p1.size = p0.size then sweep r0 r1 p0 p1 b0' b1' -- advance(!unproc_side) too
else sweep r0 (c1 :: r1) p0 acc1 b0' b1'
termination_by r0 r1 => r0.length + r1.length
/-- `CompareChunks(chunks0, chunks1)` (`util/feefrac.cpp`): compare the feerate diagrams implied by
two sorted chunk lists; `next_index = {0, 0}`, `accum = {FeeFrac(), FeeFrac()}`,
`better_somewhere = {false, false}`. -/
def compareChunks (chunks0 chunks1 : List FeeFrac) : PartialOrdering :=
sweep chunks0 chunks1 0 0 false false
/-- `ImprovesFeerateDiagram` (`policy/rbf.cpp`): with `old` the main-mempool diagram
(`chunk_results.first`) and `new` the staging diagram (`chunk_results.second`), the replacement
passes iff `std::is_gt(CompareChunks(new, old))`, i.e. the new diagram is strictly greater. -/
def ImprovesFeerateDiagram (old new : List FeeFrac) : Prop :=
compareChunks new old = .greater
/-- The feerate diagram of a chunk list as a function of cumulative size: it starts at `(0, 0)`,
is linear with slope `c.fee / c.size` across each chunk `c` in order, and is constant (the total
fee) beyond the total size. (For the chunk lists produced by Core every chunk has positive size;
`diagram` is only meaningful under `SizesPos`.) -/
def diagram : List FeeFrac → ℚ → ℚ
| [], _ => 0
| c :: cs, x => if x ≤ c.size then (c.fee : ℚ) * x / c.size else c.fee + diagram cs (x - c.size)
/-- Total fee of a chunk list (the final height of its diagram). -/
def diagramFee (cs : List FeeFrac) : ℤ := (cs.map FeeFrac.fee).sum
/-- Total size of a chunk list (the last breakpoint of its diagram). -/
def diagramSize (cs : List FeeFrac) : ℤ := (cs.map FeeFrac.size).sum
/-- Every chunk has positive size (`Assume(slope_ap.size > 0)` in `CompareChunks`; true of every
chunk of a linearisation, since a chunk is a nonempty set of transactions of positive weight). -/
def SizesPos (cs : List FeeFrac) : Prop := ∀ c ∈ cs, 0 < c.size
/-- The chunks are listed in non-increasing feerate order (`ByRatio` comparison), as
`GetMainStagingDiagrams` sorts them. -/
def FeeratesNonIncreasing (cs : List FeeFrac) : Prop :=
cs.IsChain fun a b => b.fee * a.size ≤ a.fee * b.size
/-- `Dominates c0 c1`: the diagram of `c0` lies (weakly) above the diagram of `c1` at every
nonnegative size. -/
def Dominates (c0 c1 : List FeeFrac) : Prop :=
∀ x : ℚ, 0 ≤ x → diagram c1 x ≤ diagram c0 x
/-- `BetterSomewhere c0 c1`: the diagram of `c0` lies strictly above that of `c1` at some
nonnegative size. -/
def BetterSomewhere (c0 c1 : List FeeFrac) : Prop :=
∃ x : ℚ, 0 ≤ x ∧ diagram c1 x < diagram c0 x
/-- `StrictlyBetter c0 c1`: `c0` dominates `c1` and is strictly better somewhere — the intended
meaning of `CompareChunks(c0, c1) == greater`. -/
def StrictlyBetter (c0 c1 : List FeeFrac) : Prop :=
Dominates c0 c1 ∧ BetterSomewhere c0 c1
end BitcoinFeerateDiagram
Read-back
What the Lean code literally says, in plain math · claude-fable-5-1 (independent sub-agent, blind: Lean code + auditor instructions only)
Read-back: definitions of Def_BitcoinFeerateDiagram
All definitions live in a single namespace. The file imports the standard mathematics library and a companion file of replacement definitions (FeeRate, getFee, Tx, Replacement, totalFee, PaysForRBF), none of which are used by the definitions below. All arithmetic is in the unbounded integers or the rationals .
Division conventions. Three kinds of division occur.
- Default integer division with remainder (Euclidean convention). For : and , also for negative (e.g. , ). For : and . For : and .
- Truncated division with remainder : the quotient is rounded toward zero, so the remainder is or has the sign of , with (e.g. , ). For : , .
- Rational division in , with the convention . For , is the greatest integer and the least integer .
Below, denotes if the condition holds and otherwise.
The definitions, in order
1. FeeFrac. A FeeFrac is a structure with two fields, and , both completely arbitrary integers (zero, negative or huge values allowed; no machine-word bounds, and no requirement that the size be positive or that a zero size forces a zero fee). Equality of FeeFracs is decidable (componentwise) and they have a printable representation.
2. Zero. The zero FeeFrac is .
3. Addition. .
4. Subtraction. .
5. IsEmpty. is the proposition (regardless of the fee).
6. mul. , the exact product of two integers.
7. mulFallback. For integers , with default (floor) integer division by :
Here and also for negative ; the second output component lies in . No bounds on are assumed.
8. div. For integers and a boolean ("round down"), with and (truncated division):
Case by case: if the result is ; if it is when is true and when is false; if it is when is true and when is false. The definition places no condition on : for it gives , , hence ; for the remainder still carries the sign of .
9. divFallback. For a pair of integers , an integer and a boolean , using truncated division throughout:
No range restriction is placed on (it may be negative or ) or on .
10. ceilDiv. For integers , with default (Euclidean) integer division:
The definition is stated for all integers (not only nonnegative ones); for it gives .
11. evaluateFee. For a FeeFrac , an integer and a boolean :
where and "" in the first line is the default (Euclidean) integer division. No condition on (it may be or negative) or on is part of the definition.
12. evaluateFeeDown. .
13. evaluateFeeUp. .
14. byRatioCmp. For FeeFracs , is the three-way comparison of the two integers and :
No sign condition on the sizes is part of the definition. In particular, is the comparison of with , independent of .
15. ratio. , rational division, which yields when .
16. PartialOrdering. A type with exactly four values: , , , (with decidable equality).
17. boolCompare. For booleans :
18. sweep. , where are lists of FeeFracs, are FeeFracs and are booleans, is defined by recursion (each recursive call shortens or , so it terminates) as follows.
- Both lists empty (): the result is .
- nonempty, : put and , i.e. the comparison of with (sizes play no role). Set , i.e. or ; and , i.e. or . If and are both true, the result is ; otherwise it is .
- , nonempty (mirror image): put and comparison of with . Set and . If both are true, the result is ; otherwise it is .
- Both nonempty, , : put and .
- (a) If : , i.e. the comparison of
Set $\beta_1' = \beta_1 \lor (\kappa = \mathrm{gt})$ and $\beta_0' = \beta_0 \lor (\kappa = \mathrm{lt})$. If both are true, the result is $\mathsf{unordered}$; otherwise it is $\mathrm{sweep}(c_0 :: R_0',\ R_1',\ A_0,\ P_1,\ \beta_0', \beta_1')$ (list $0$ and $A_0$ unchanged; the head of list $1$ is consumed and $A_1$ becomes $P_1$).
- (b) Otherwise (): , i.e. the comparison of
Set $\beta_0' = \beta_0 \lor (\kappa = \mathrm{gt})$ and $\beta_1' = \beta_1 \lor (\kappa = \mathrm{lt})$. If both are true, the result is $\mathsf{unordered}$. Otherwise, if $\mathrm{size}(P_1) = \mathrm{size}(P_0)$ the result is $\mathrm{sweep}(R_0', R_1', P_0, P_1, \beta_0', \beta_1')$ (both heads consumed); and if $\mathrm{size}(P_0) < \mathrm{size}(P_1)$ it is $\mathrm{sweep}(R_0',\ c_1 :: R_1',\ P_0,\ A_1,\ \beta_0', \beta_1')$.
The flags only ever change from false to true, and the function returns at the first step at which both become true; a recursive call is made only when at most one of them is true. The case can therefore be reached only if sweep is entered with both flags already true and both lists empty. The definition makes no assumption on signs of fees or sizes, nor on the order of the chunks; zero or negative sizes simply enter the comparisons above.
19. compareChunks. For chunk lists (finite lists of FeeFracs, possibly empty) :
In particular , and once one list is exhausted only fees are compared (cases 2 and 3 of sweep).
20. ImprovesFeerateDiagram. For chunk lists (in this argument order), is the proposition
i.e. the second argument is passed first to compareChunks.
21. diagram. For a chunk list and , is defined recursively:
with rational division (). It is defined for every rational , including negative . For the empty list it is identically . When every size is positive, writing and (with ) for , , the recursion unfolds to: for all (including negative ); for ; and for — the piecewise-linear function through , horizontal to the right. If a size is zero or negative the recursion still evaluates but need not have this shape (e.g. a chunk with gives ; a chunk with size contributes a jump of just after ).
22. diagramFee. ( for the empty list).
23. diagramSize. ( for the empty list).
24. SizesPos. : every chunk of has (vacuously true for the empty list; nothing is said about fees).
25. FeeratesNonIncreasing. means: for every pair of adjacent chunks ,
(integer cross-multiplication). It holds automatically for lists of length or .
26. Dominates. : for every rational , .
27. BetterSomewhere. : there exists a rational with .
28. StrictlyBetter. : and .
In 26–28 only rational are considered ( included, negative excluded), over the whole half-line, including points beyond both lists' total sizes.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.