If the old and new diagrams' totals are a common F plus the evicted fees and plus the replacement's fee, and both ImprovesFeerateDiagram and the replacement mission's PaysForRBF rate R hold: the new diagram is strictly better and its total fee exceeds the old by at least rate.getFee R.new.vsize. The replacement mission's no-free-relay theorems therefore hold at the pinned revision's actual rules.
Preamble
import Definitions.Def_BitcoinFeerateDiagram
open BitcoinFeerateDiagram BitcoinReplacement
Formal statement
theorem BitcoinFeerateDiagram.no_free_relay_diagram (rate : FeeRate) (R : Replacement)
(old new : List FeeFrac) (F : ℤ) (hold : SizesPos old) (hnew : SizesPos new)
(hfold : diagramFee old = F + totalFee R.evicted) (hfnew : diagramFee new = F + R.new.fee)
(himp : ImprovesFeerateDiagram old new) (hpay : PaysForRBF rate R) :
StrictlyBetter new old ∧ diagramFee old + rate.getFee R.new.vsize ≤ diagramFee new := by sorry
r be a FeeRate (natural numbers fee(r)≥0, size(r)>0),
R be a Replacement (a new transaction R.new with natural-number fee and positive natural-number vsize, a multiset R.evicted of transactions, and a sub-multiset R.direct≤R.evicted),
old and new be arbitrary finite lists of FeeFracs (possibly empty),
F be an arbitrary integer,
and assume
SizesPos(old) and SizesPos(new): every chunk of either list has strictly positive size;
diagramFee(old)=F+totalFee(R.evicted) (the natural-number total fee regarded as an integer);
diagramFee(new)=F+fee(R.new) (regarded as an integer);
ImprovesFeerateDiagram(old,new), i.e. compareChunks(new,old)=greater;
PaysForRBF(r,R), i.e. totalFee(R.evicted)≤fee(R.new) and getFee(r,vsize(R.new))≤fee(R.new)−totalFee(R.evicted).
Then both of the following hold:
StrictlyBetter(new,old): diagram(old,x)≤diagram(new,x) for every rational x≥0, and diagram(old,x)<diagram(new,x) for some rational x≥0;
diagramFee(old)+getFee(r,vsize(R.new))≤diagramFee(new) (in Z), where getFee(r,v)=(fee(r)v+size(r)−1)/size(r) with natural-number floor division.
Binders and edge cases. The chunk lists are tied to R only through hypotheses 2 and 3, i.e. through their total fees and the common integer offset F; nothing relates the chunks' sizes to vsize(R.new) or to the evicted transactions' vsizes, nothing relates individual chunks to individual transactions, and R.direct plays no role. F may be any integer (including negative). Chunk fees are arbitrary integers; the lists are not assumed sorted by feerate; either list may be empty (total fee 0). R.evicted may be the empty multiset (total fee 0). The fee rate r may have fee(r)=0, in which case getFee=0. Argument order: ImprovesFeerateDiagram takes old first and runs compareChunks with new first.
Definitions used, unfolded
Division conventions. Three kinds of division occur.
Default integer divisionn/d with remainder nmodd (Euclidean convention). For d>0: n/d=⌊n/d⌋ and nmodd=n−d⌊n/d⌋∈[0,d), also for negative n (e.g. −7/2=−4, −7mod2=1). For d<0: n/d=−⌊n/∣d∣⌋ and nmodd∈[0,∣d∣). For d=0: n/0=0 and nmod0=n.
Truncated divisiontdiv(n,d) with remainder tmod(n,d)=n−d⋅tdiv(n,d): the quotient is rounded toward zero, so the remainder is 0 or has the sign of n, with ∣tmod(n,d)∣<∣d∣ (e.g. tdiv(−7,2)=−3, tmod(−7,2)=−1). For d=0: tdiv(n,0)=0, tmod(n,0)=n.
Rational division in Q, with the convention q/0=0. For q∈Q, ⌊q⌋ is the greatest integer ≤q and ⌈q⌉ the least integer ≥q.
Below, [P] denotes 1 if the condition P holds and 0 otherwise.
FeeFrac. A FeeFrac is a pair X=(fee(X),size(X)) of two arbitrary integers. Nothing constrains them: either component may be zero or negative, and no machine-word bounds are imposed. Addition and subtraction are componentwise,
X±Y=(fee(X)±fee(Y),size(X)±size(Y)),
and the zero FeeFrac is (0,0). A chunk list is a finite list c=[c1,…,cn] of FeeFracs; the empty list (n=0) is allowed.
byRatioCmp. For FeeFracs X,Y, byRatioCmp(X,Y) is the three-way comparison of the two integers fee(X)⋅size(Y) and fee(Y)⋅size(X):
byRatioCmp(X,Y)=⎩⎨⎧lteqgtif fee(X)size(Y)<fee(Y)size(X),if they are equal,if fee(X)size(Y)>fee(Y)size(X).
No sign condition on the sizes is part of the definition. In particular, byRatioCmp(X,(0,1)) is the comparison of fee(X) with 0, independent of size(X).
PartialOrdering and boolCompare.PartialOrdering is a four-element type with values less, equivalent, greater, unordered. For booleans β0,β1:
sweep.sweep(R0,R1,A0,A1,β0,β1)∈PartialOrdering, where R0,R1 are lists of FeeFracs, A0,A1 are FeeFracs and β0,β1 are booleans, is defined by recursion (each recursive call shortens R0 or R1, so it terminates) as follows.
Both lists empty (R0=R1=[]): the result is boolCompare(β0,β1).
R0=c0::R0′ nonempty, R1=[]: put P=c0+A0 and κ=byRatioCmp(P−A1,(0,1)), i.e. the comparison of fee(P)−fee(A1)=fee(c0)+fee(A0)−fee(A1) with 0 (sizes play no role). Set β0′=β0∨(κ=gt), i.e. β0 or fee(P)>fee(A1); and β1′=β1∨(κ=lt), i.e. β1 or fee(P)<fee(A1). If β0′ and β1′ are both true, the result is unordered; otherwise it is sweep(R0′,[],P,A1,β0′,β1′).
R0=[], R1=c1::R1′ nonempty (mirror image): put P=c1+A1 and κ= comparison of fee(P)−fee(A0) with 0. Set β1′=β1∨(fee(P)>fee(A0)) and β0′=β0∨(fee(P)<fee(A0)). If both are true, the result is unordered; otherwise it is sweep([],R1′,A0,P,β0′,β1′).
Both nonempty, R0=c0::R0′, R1=c1::R1′: put P0=c0+A0 and P1=c1+A1.
(a) If size(P0)>size(P1):κ=byRatioCmp(P1−A0,P0−A0), 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 (size(P0)≤size(P1)):κ=byRatioCmp(P0−A1,P1−A1), 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 unordered 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 boolCompare(true,true)=equivalent 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.
Edge cases: compareChunks([],[])=equivalent; when one list is (or becomes) exhausted, only the fees of the remaining cumulative points versus the other side's accumulated fee are compared (case 2/3 of sweep).
ImprovesFeerateDiagram. For chunk lists old and new (in this argument order),
with rational division (⋅/0=0). It is defined for every rational x, including negative x. For the empty list it is identically 0. When every size is positive, writing Sk=∑i≤ksize(ci) and Fk=∑i≤kfee(ci) (with S0=F0=0) for c=[c1,…,cn], n≥1, the recursion unfolds to: diagram(c,x)=fee(c1)x/size(c1) for all x≤S1 (including negative x); Fk−1+fee(ck)(x−Sk−1)/size(ck) for Sk−1≤x≤Sk; and Fn for x≥Sn — the piecewise-linear function through (0,0),(S1,F1),…,(Sn,Fn), 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 size(c1)<0 gives diagram(c,0)=fee(c1)+diagram(c′,−size(c1)); a chunk with size 0 contributes a jump of fee(c1) just after x=0).
diagramFee, diagramSize. For c=[c1,…,cn]: diagramFee(c)=∑i=1nfee(ci)∈Z and diagramSize(c)=∑i=1nsize(ci)∈Z (both 0 for the empty list).
SizesPos.SizesPos(c) means size(ci)>0 for every chunk ci in c (vacuously true for the empty list). It says nothing about fees, which may be zero or negative.
Dominates, BetterSomewhere, StrictlyBetter. For chunk lists c0,c1:
Dominates(c0,c1): for every rational x≥0, diagram(c1,x)≤diagram(c0,x).
BetterSomewhere(c0,c1): there is a rational x≥0 with diagram(c1,x)<diagram(c0,x).
StrictlyBetter(c0,c1): Dominates(c0,c1) and BetterSomewhere(c0,c1).
Only x≥0 is quantified over (negative x is excluded; x=0 is included), and x ranges over all nonnegative rationals, including points beyond both total sizes.
FeeRate and getFee (from the imported replacement file). A FeeRater consists of natural numbers fee(r)≥0 and size(r) with the built-in requirement size(r)>0. For v∈N,
getFee(r,v)=(fee(r)⋅v+(size(r)−1))/size(r)
computed in the natural numbers with floor division (size(r)−1≥0 since size(r)>0).
Tx, Replacement, totalFee, PaysForRBF (from the imported replacement file). A transaction t is a pair of natural numbers fee(t)≥0, vsize(t) with vsize(t)>0. A ReplacementR consists of a transaction R.new, a finite multiset R.evicted of transactions, and a finite multiset R.direct of transactions with R.direct≤R.evicted (sub-multiset, counting multiplicity); the multisets may be empty. totalFee(s)=∑t∈sfee(t)∈N, summed with multiplicity (0 for the empty multiset). For a FeeRate r,
PaysForRBF(r,R)⟺totalFee(R.evicted)≤fee(R.new) and getFee(r,vsize(R.new))≤fee(R.new)−totalFee(R.evicted),
where the subtraction is truncated subtraction of natural numbers (by the first conjunct it equals the ordinary difference).
Confirmed by the moderator at approval.