The fee rules of transaction replacement over an abstract mempool
DefinitionBitcoinReplacementAn abstract mempool: no scripts, inputs or topology, only fees and sizes.
Tx — a (modified) fee in satoshi and a positive virtual size. FeeRate — Core's FeePerVSize: fee satoshi per size vbytes with size > 0; FeeRate.perKvB k is CFeeRate(k) ; DEFAULT_INCREMENTAL_RELAY_FEE (sat/kvB at this revision) and defaultIncrementalRelayFee its rate; MAX_REPLACEMENT_CANDIDATES (recorded, unused). FeeRate.getFee r v , computed as in (CFeeRate::GetFee = FeePerVSize::EvaluateFeeUp). Tx.feeRate is the exact fraction (fee, vsize); FeeRate.lt a b and FeeRate.le likewise (ByRatio); Tx.feeRateQ .
Replacement — a new transaction, the multiset evicted of all entries it would remove (all_conflicts: direct conflicts and their descendants) and the sub-multiset direct of direct conflicts (iters_conflicting), with direct ≤ evicted. totalFee, totalVsize sum over a multiset.
PaysMoreThanConflicts R — every direct conflict's fee rate is strictly below the replacement's (FeeRate.lt), BIP125 rule 3 as implemented up to v29. PaysForRBF rate R — totalFee evicted ≤ new.fee and rate.getFee new.vsize ≤ new.fee - totalFee evicted (Core's PaysForRBF: at least the evicted fees, plus the incremental relay fee for the replacement's size). Valid rate R — both. IsChain rate t₀ [R₁, …, Rₙ] — each valid, evicts , evicts 's new transaction; chainEnd t₀ Rs is the last new transaction ( for the empty chain); chainVsizes Rs the list of the new transactions' sizes.
Formalization Note. Imports Mathlib. PaysForRBF is transcribed from revision a773e1e; PaysMoreThanConflicts is absent there (replaced by the cluster-mempool feerate-diagram check, out of scope) and is transcribed from its last form (v29.0) with the exact ByRatio comparison of a773e1e. Fees are modified fees; structural rules, opt-in signalling, package relay and TRUC are not modelled; the eviction multiset is given, not computed from the mempool graph. The getFee of a zero-size or negative rate is not modelled.
import Mathlib
/-!
# Bitcoin Core transaction replacement (BIP125 / RBF) — fee rules, abstract mempool model
This file transcribes the two *fee* rules that Bitcoin Core's `policy/rbf.cpp` imposes on a
replacement transaction, over an abstract mempool with no scripts, no inputs and no topology:
* a transaction is a pair (fee in satoshi, virtual size in vbytes) with positive vsize;
* a replacement is a new transaction together with the multiset of mempool entries it would evict
(`all_conflicts` as `GetEntriesForConflicts` collects it: the directly conflicting entries
`iters_conflicting` plus all their descendants) and the sub-multiset of direct conflicts;
* `PaysForRBF` (revision `a773e1e33b349dc819b5a0edc1c7a4839dc73b48`, `policy/rbf.cpp`) is
transcribed verbatim, with `CFeeRate::GetFee` = `FeePerVSize::EvaluateFeeUp`, i.e. the exact
ceiling `⌈fee · vsize / size⌉` of the configured incremental relay fee rate;
* `PaysMoreThanConflicts` (BIP125 rule 3) is transcribed from the last form in which it existed in
`policy/rbf.cpp` (e.g. tag `v29.0`); at revision `a773e1e` that function has been removed and
replaced by the cluster-mempool feerate-diagram check `ImprovesFeerateDiagram`, which is out of
scope here. Fee rates are compared as `CFeeRate::operator<=>` does at `a773e1e`, i.e. through
`ByRatio` cross-multiplication `a.fee * b.size <=> b.fee * a.size`, with no rounding.
Fees are the mempool's *modified* fees (`GetModifiedFee`), which the model does not distinguish
from raw fees. Nothing here models descendant/package relay, cluster linearisation, the
structural rules (no new unconfirmed inputs, cluster-count limit), or opt-in signalling.
-/
namespace BitcoinReplacement
/-- An abstract mempool transaction: its (modified) fee in satoshi and its virtual size in vbytes.
`CTxMemPoolEntry::GetTxSize()` is always positive, so the model records `0 < vsize`. -/
structure Tx where
/-- Fee in satoshi (`CAmount`, nonnegative for a mempool entry). -/
fee : ℕ
/-- Virtual size in vbytes (`GetVirtualTransactionSize`). -/
vsize : ℕ
/-- Mempool entries have positive virtual size. -/
vsize_pos : 0 < vsize
deriving DecidableEq
/-- A fee rate as Bitcoin Core's `FeePerVSize` stores it at revision `a773e1e`: `fee` satoshi per
`size` vbytes, with `size > 0` (`CFeeRate(const FeePerVSize&)` maps a nonpositive size to the
empty rate, which `GetFee` treats as zero; the model only admits the positive-size case, which is
the one that is reached for a configured incremental relay fee rate). -/
structure FeeRate where
/-- Numerator: satoshi. -/
fee : ℕ
/-- Denominator: vbytes. -/
size : ℕ
/-- `FeePerVSize::EvaluateFee` requires `size > 0`. -/
size_pos : 0 < size
/-- `CFeeRate(const I m_feerate_kvb)` : a rate given in satoshi per 1000 vbytes is stored losslessly
as `FeePerVSize(m_feerate_kvb, 1000)`. -/
def FeeRate.perKvB (satPerKvB : ℕ) : FeeRate := ⟨satPerKvB, 1000, by norm_num⟩
/-- `policy/policy.h` at `a773e1e`: `DEFAULT_INCREMENTAL_RELAY_FEE{100}` (satoshi per kvB), the
default `-incrementalrelayfee`. (Before PR #33106, i.e. up to and including v29.x, it was 1000.) -/
def DEFAULT_INCREMENTAL_RELAY_FEE : ℕ := 100
/-- The node's incremental relay fee rate at default settings:
`CFeeRate{DEFAULT_INCREMENTAL_RELAY_FEE}` = 100 sat per 1000 vB = 0.1 sat/vB. -/
def defaultIncrementalRelayFee : FeeRate := FeeRate.perKvB DEFAULT_INCREMENTAL_RELAY_FEE
/-- `policy/rbf.h`: `MAX_REPLACEMENT_CANDIDATES{100}`, the Rule #5 limit on the number of distinct
mempool clusters a replacement may touch (checked by `GetEntriesForConflicts`; not used by the fee
theorems). -/
def MAX_REPLACEMENT_CANDIDATES : ℕ := 100
/-- `CFeeRate::GetFee(v)` = `FeePerVSize::EvaluateFeeUp(v)` = `CeilDiv(fee * v, size)`, the fee for
`v` vbytes at this rate rounded *up* to the next satoshi: `⌈fee · v / size⌉`, computed in ℕ as
`(fee * v + (size - 1)) / size`. (Only the `fee ≥ 0` branch of `EvaluateFee` is modelled; the
`IsEmpty` and negative-fee special cases of `GetFee` are unreachable for a positive-size,
nonnegative rate.) -/
def FeeRate.getFee (r : FeeRate) (v : ℕ) : ℕ := (r.fee * v + (r.size - 1)) / r.size
/-- `CFeeRate(nFeePaid, virtual_bytes)` for a mempool entry: with `virtual_bytes > 0` the rate is
the exact fraction `FeePerVSize(fee, vsize)`. -/
def Tx.feeRate (t : Tx) : FeeRate := ⟨t.fee, t.vsize, t.vsize_pos⟩
/-- `ByRatio` strict comparison of two fee rates, exactly as `CFeeRate::operator<=>` evaluates it:
`a < b` iff `a.fee * b.size < b.fee * a.size` (cross-multiplication in exact integer arithmetic,
no rounding). -/
def FeeRate.lt (a b : FeeRate) : Prop := a.fee * b.size < b.fee * a.size
/-- `ByRatio` non-strict comparison: `a ≤ b` iff `a.fee * b.size ≤ b.fee * a.size`. -/
def FeeRate.le (a b : FeeRate) : Prop := a.fee * b.size ≤ b.fee * a.size
/-- The fee rate of a transaction as an exact rational number of satoshi per vbyte, used only to
state that the `ByRatio` comparison is the ordinary comparison of fractions. -/
def Tx.feeRateQ (t : Tx) : ℚ := (t.fee : ℚ) / (t.vsize : ℚ)
/-- A candidate replacement, as the RBF checks see it (`MemPoolAccept::ReplacementChecks`):
the new transaction, the multiset `evicted` of all mempool entries that would be removed
(`all_conflicts` = direct conflicts plus all of their descendants), and the sub-multiset `direct`
of the directly conflicting entries (`iters_conflicting`). Entries are recorded by their
(fee, vsize) data only, as a multiset so that distinct entries with equal data are not merged. -/
structure Replacement where
/-- The replacement transaction. -/
new : Tx
/-- Every mempool entry the replacement would evict (`all_conflicts`). -/
evicted : Multiset Tx
/-- The directly conflicting entries (`iters_conflicting`). -/
direct : Multiset Tx
/-- `GetEntriesForConflicts` starts from `iters_conflicting`, so direct conflicts are evicted. -/
direct_le : direct ≤ evicted
/-- `original_fees`: the total (modified) fee of a multiset of mempool entries, the quantity
`MemPoolAccept` sums over `all_conflicts` before calling `PaysForRBF`. -/
def totalFee (s : Multiset Tx) : ℕ := (s.map Tx.fee).sum
/-- Total virtual size of a multiset of transactions. -/
def totalVsize (s : Multiset Tx) : ℕ := (s.map Tx.vsize).sum
/-- BIP125 rule 3 as `PaysMoreThanConflicts` implemented it (`policy/rbf.cpp`, up to v29.x):
for every directly conflicting entry `mi`, with
`original_feerate = CFeeRate(mi->GetModifiedFee(), mi->GetTxSize())`, the replacement is rejected
when `replacement_feerate <= original_feerate`; so it passes iff every direct conflict's fee rate
is strictly below the replacement's, in the `ByRatio` order. -/
def PaysMoreThanConflicts (R : Replacement) : Prop :=
∀ t ∈ R.direct, FeeRate.lt t.feeRate R.new.feeRate
/-- `PaysForRBF(original_fees, replacement_fees, replacement_vsize, relay_fee, txid)` at
`a773e1e`, with `original_fees = totalFee R.evicted`, `replacement_fees = R.new.fee` and
`replacement_vsize = R.new.vsize`:
* Rule #3 (there): reject if `replacement_fees < original_fees`;
* Rule #4: `additional_fees = replacement_fees - original_fees`; reject if
`additional_fees < relay_fee.GetFee(replacement_vsize)`.
The subtraction is performed only after the first check, so ℕ truncated subtraction agrees with
the `CAmount` subtraction. -/
def PaysForRBF (rate : FeeRate) (R : Replacement) : Prop :=
totalFee R.evicted ≤ R.new.fee ∧
rate.getFee R.new.vsize ≤ R.new.fee - totalFee R.evicted
/-- A replacement that passes both fee rules at incremental relay fee rate `rate`. -/
def Valid (rate : FeeRate) (R : Replacement) : Prop :=
PaysMoreThanConflicts R ∧ PaysForRBF rate R
/-- `IsChain rate t₀ [R₁, …, Rₙ]`: a sequence of valid replacements in which `R₁` evicts `t₀` and
each `Rᵢ₊₁` evicts `Rᵢ.new`; so the network relays `R₁.new, …, Rₙ.new` in turn, each one
replacing the previous. -/
def IsChain (rate : FeeRate) : Tx → List Replacement → Prop
| _, [] => True
| t, R :: Rs => Valid rate R ∧ t ∈ R.evicted ∧ IsChain rate R.new Rs
/-- The last transaction of a replacement chain (`t₀` itself for the empty chain). -/
def chainEnd (t₀ : Tx) (Rs : List Replacement) : Tx :=
Rs.foldl (fun _ R => R.new) t₀
/-- The virtual sizes of the replacement transactions of a chain, `vsize(t₁), …, vsize(tₙ)`. -/
def chainVsizes (Rs : List Replacement) : List ℕ := Rs.map fun R => R.new.vsize
end BitcoinReplacement
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: Def_BitcoinReplacement.lean (preamble definitions)
The file imports Mathlib and places every declaration below in a namespace BitcoinReplacement. Throughout, denotes the natural numbers ; subtraction in truncates at ( when ) and division in rounds down. Multisets, the operation (add one copy of to ) and the sub-multiset order on multisets are the standard Mathlib notions. One paragraph follows per definition, in file order.
1. Tx (transaction). A structure with two data fields, and , and one proof field asserting . Thus a transaction is exactly a pair of natural numbers with ; the fee may be . Equality of transactions is decidable and two transactions are equal exactly when their fee and vsize agree (the proof field carries no information). No identifier, inputs, outputs or any other attribute exists in this notion.
2. FeeRate (fee rate). A structure with two data fields, and , and a proof field asserting . Thus a fee rate is a pair of natural numbers with ; the numerator may be . Fee rates are not identified up to proportion: and are distinct values of this type.
3. FeeRate.perKvB. A function sending a natural number to the fee rate , i.e. numerator and denominator .
4. DEFAULT_INCREMENTAL_RELAY_FEE. The natural-number constant .
5. defaultIncrementalRelayFee. The fee rate , i.e. the pair .
6. MAX_REPLACEMENT_CANDIDATES. The natural-number constant . It is not referenced by any other definition in this file.
7. FeeRate.getFee. For a fee rate and a natural number ,
with natural-number (rounding-down) division. Because , the inner subtraction never truncates, and the whole expression equals the ceiling . Edge cases: for every ; for every when ; when and the value is at least ; when it is exactly .
8. Tx.feeRate. For a transaction , the fee rate , with the positivity proof inherited from . No reduction of the fraction is performed.
9. FeeRate.lt. For fee rates and , the proposition
a strict inequality of natural numbers obtained by cross-multiplication, with no rounding. Edge cases: is false; if then holds exactly when ; if then is false.
10. FeeRate.le. For fee rates and as above, the proposition , the non-strict cross-multiplied comparison. It is not referenced by any other definition in this file.
11. Tx.feeRateQ. For a transaction , the rational number , where both naturals are cast into and the division is exact rational division. Since , the division-by-zero convention of is never invoked; exactly when .
12. Replacement. A structure with three data fields and one proof field: a transaction ; a multiset of transactions ; a multiset of transactions ; and a proof that in the sub-multiset order (every transaction value occurs in at most as many times as in ). Nothing else is required: and may both be empty, may equal , may itself occur in or , and multiple copies of equal data are kept distinct by multiplicity only. There is no notion of mempool, conflict, inputs or descendants in the definition; the names of the fields are the only link to such notions.
13. totalFee. For a multiset of transactions, , the sum of the fees counted with multiplicity. For the empty multiset the value is .
14. totalVsize. For a multiset of transactions, , counted with multiplicity; for the empty multiset. It is not referenced by any other definition in this file.
15. PaysMoreThanConflicts. For a replacement , the proposition
The quantification ranges over the elements of only (not ), and multiplicity is irrelevant to it. It is vacuously true when is empty. If it holds only when is empty.
16. PaysForRBF. For a fee rate and a replacement , the conjunction of two natural-number inequalities:
where is truncated subtraction in . Under the first conjunct the subtraction in the second is an ordinary difference; taken on its own, the second conjunct would be satisfied with right-hand side whenever and . does not appear. Edge cases: if is empty the condition is ; if it is .
17. Valid. For a fee rate and a replacement , the conjunction , i.e. all three inequalities of items 15 and 16 together.
18. IsChain. For a fee rate , a transaction and a list of replacements, a proposition defined by recursion on the list: for the empty list it is true (for any and ); for a list whose first element is and whose remainder is , it is
Unfolded for with and : for each , is valid at rate and the transaction value occurs (with any multiplicity ) in . Membership is by value: any element with the same fee and vsize as counts. It is not required that occur in , that contain nothing besides , that the be distinct, or that .
19. chainEnd. For a transaction and a list of replacements, a left fold whose step function discards the accumulator and returns for the current element . Hence and for ; the result depends only on the last element of the list, and on only when the list is empty. No chain hypothesis is involved in the definition.
20. chainVsizes. For a list of replacements , the list of natural numbers , in order; the empty list when . The vsize of any starting transaction is not included.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.