No free relay: a chain of replacements pays the incremental fee for every byte it relayed
ProvedBitcoinReplacement.bandwidth_paidFor any rate, any and any chain IsChain rate t₀ Rs of replacements with new transactions : . The final transaction's fee covers the original fee plus the incremental relay fee of every replacement relayed along the way, in Core's own rounded-up GetFee.
import Definitions.Def_BitcoinReplacement
theorem BitcoinReplacement.bandwidth_paid (rate : BitcoinReplacement.FeeRate)
(t₀ : BitcoinReplacement.Tx) (Rs : List BitcoinReplacement.Replacement)
(h : BitcoinReplacement.IsChain rate t₀ Rs) :
t₀.fee + ((BitcoinReplacement.chainVsizes Rs).map rate.getFee).sum ≤
(BitcoinReplacement.chainEnd t₀ Rs).fee := by sorryRead-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: BitcoinReplacement.bandwidth_paid
Setting (unfolded from the preamble). All declarations live in a namespace BitcoinReplacement. A transaction is a pair of natural numbers together with a proof that ; may be . Two transactions are equal exactly when their fees and virtual sizes agree. A fee rate is a pair of natural numbers together with a proof that ; may be , and nothing identifies with . For a fee rate and a natural number ,
computed with natural-number (rounding-down) division; since the inner subtraction is exact, and the value equals . In particular , and for every whenever .
A replacement consists of a transaction , a multiset of transactions , a multiset of transactions , and a proof that as multisets (every transaction value occurs in at most as many times as it occurs in ). Either multiset may be empty, may itself occur in , and no other relation between the three components is imposed. For a multiset of transactions, , summed with multiplicity, so .
is valid at rate (written ) when all three of the following hold:
- () for every transaction value occurring in , (a strict cross-multiplied comparison in ; vacuously true when is empty; nothing is required of elements of that do not occur in );
- (, first conjunct) ;
- (, second conjunct) , where is truncated natural-number subtraction (it returns when the subtrahend exceeds the minuend; under item 2 it coincides with ordinary subtraction).
A list of replacements () is a chain at rate from (written ) when, writing for , for every with : is valid at rate , and the transaction value occurs in the multiset . Membership is by value: any element of with the same fee and virtual size as counts; it is not required that occur in , nor that contain nothing else. The empty list is a chain from any at any rate. The chain end is when and is itself when (it depends only on the last replacement). The chain vsizes is the list , empty when . Below, always denotes , i.e. it is when .
Statement. For every fee rate , every transaction , and every list of replacements () such that holds, the following inequality of natural numbers holds:
where , each summand is the separately rounded-up quantity , and the sum is over the list after applying to each entry.
Edge cases. When the sum is empty and , so the claim reads . When every summand is and the claim reads . The relation is non-strict. No hypothesis other than the chain condition is assumed on , or the ; in particular the fee and the evicted/direct multisets of each are otherwise arbitrary.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.