A treasury holds collateral and a token claims a share of it. Two promises are usually made about such a token. The first is a price floor: the treasury is always worth at least a published function of the supply. The second concerns timing: fees should reach the treasury at a bounded rate, so that buying just before a fee and redeeming just after it does not pay. The first is a statement about every reachable state, so it is an invariant of a state machine; the second is a bound on round trips through that machine, and it holds exactly as far as Theorem 5 and Theorem 5′ say. This article defines the machine, proves the invariants, and then looks at three questions that sit on top of it: how a floor stated in dollars behaves when the collateral price falls, which cubic Bézier curves can serve as a floor curve, and how rewards can be paid without creating a contest.
All quantities are natural numbers: collateral and tokens in their smallest units, fees in basis points of . Ratios are never divided. They are compared by cross-multiplication, so rounding can never hide a loss. The Lean blocks below concatenate, in reading order, into one file that compiles with core Lean 4 and no external libraries. There is no sorry and no added axiom. The main theorems depend only on propext, Quot.sound and, for one of them, Classical.choice.
Products of variables are outside linear arithmetic. The two tactics below expand every product into a sum of monomials in a fixed order, after which omega treats each monomial as an atom. That is enough for every polynomial inequality in this article, as long as the proof supplies the right nonnegative products as hypotheses.
/-! ## Arithmetic toolkit
Quantities are natural numbers (or integers where signs are needed). Ratios
are never divided; they are compared by cross-multiplication. `poly_nat` and
`poly_int` expand products into monomials in a canonical order, after which
`omega` treats each monomial as an atom. -/
theorem lit_end (n x : Nat) :
x * (no_index (@OfNat.ofNat Nat n (instOfNatNat n))) =
(@OfNat.ofNat Nat n (instOfNatNat n)) * x := Nat.mul_comm _ _
theorem lit_out (n x y : Nat) :
x * ((no_index (@OfNat.ofNat Nat n (instOfNatNat n))) * y) =
(@OfNat.ofNat Nat n (instOfNatNat n)) * (x * y) := Nat.mul_left_comm _ _ _
macro "poly_nat" : tactic => `(tactic| (
simp only [Nat.mul_add, Nat.add_mul, Nat.mul_assoc, Nat.mul_comm, Nat.mul_left_comm,
Nat.reduceMul] at *;
(try simp only [lit_end, lit_out, Nat.reduceMul] at *);
omega))
theorem ilit_end (n : Nat) (x : Int) :
x * (no_index (@OfNat.ofNat Int n _)) = (@OfNat.ofNat Int n _) * x := Int.mul_comm _ _
theorem ilit_out (n : Nat) (x y : Int) :
x * ((no_index (@OfNat.ofNat Int n _)) * y) = (@OfNat.ofNat Int n _) * (x * y) :=
Int.mul_left_comm _ _ _
macro "poly_int" : tactic => `(tactic| (
(try simp only [Int.sub_eq_add_neg, Int.mul_add, Int.add_mul, Int.mul_neg, Int.neg_mul,
Int.neg_add, Int.neg_neg, Int.mul_one, Int.one_mul, Int.mul_assoc, Int.mul_comm,
Int.mul_left_comm, Int.reduceMul, Int.reduceNeg] at *);
(try simp only [ilit_end, ilit_out, Int.reduceMul, Int.reduceNeg] at *);
all_goals omega))
/-- Division by a fixed number is monotone. -/
theorem div_mono {n m : Nat} (h : n ≤ m) (k : Nat) : n / k ≤ m / k := by
rcases Nat.eq_zero_or_pos k with hk | hk
· subst hk; simp
· exact (Nat.le_div_iff_mul_le hk).2 (Nat.le_trans (Nat.div_mul_le_self n k) h)
/-- Dividing by a larger number gives less. -/
theorem div_anti (a : Nat) {b c : Nat} (hcb : c ≤ b) (hc : 0 < c) : a / b ≤ a / c :=
(Nat.le_div_iff_mul_le hc).2
(Nat.le_trans (Nat.mul_le_mul_left _ hcb) (Nat.div_mul_le_self a b))
Backing per token
State. A state is a quadruple :
- , the treasury: collateral credited and available for redemption;
- , the circulating supply;
- , the fee queue: fees received but not yet credited to ;
- , the grant reserve: tokens announced but not yet issued.
The fully diluted supply is and the backing per token is . Backing is measured against , not , so issuing a grant that was announced in advance dilutes nobody.
Redemption. Redeeming tokens pays the pro-rata share less an exit fee of basis points:
Theorem 1 (redemption invariance). A fee-free pro-rata redemption leaves backing unchanged when : . In every case, with rounding down and any exit fee, backing does not fall, against the fully diluted supply and against the circulating supply:
Proof. , so . The exit fee only lowers the payout. Paying against pays at most the share against . ∎
So a treasury that pays redemptions shrinks, but backing per token does not. For example, a treasury of 1000 against 100 tokens has backing 10. Redeeming 40 pays 400, and 600 against 60 is still 10.
-- continues the definitions above
/-! ## Redemption -/
/-- Basis-point denominator. -/
def D : Nat := 10000
/-- Pro-rata share of `r` tokens out of `F`, rounded down. -/
def payout (T F r : Nat) : Nat := r * T / F
/-- The same, less an exit fee of `s` basis points. -/
def exitPay (s T F r : Nat) : Nat := payout T F r * (D - s) / D
theorem payout_le (T C r : Nat) (h : r ≤ C) : payout T C r ≤ T := by
unfold payout
rcases Nat.eq_zero_or_pos C with hC | hC
· subst hC; simp
· exact Nat.div_le_of_le_mul (Nat.mul_le_mul_right T h)
theorem exitPay_le (s T F r : Nat) : exitPay s T F r ≤ payout T F r := by
unfold exitPay
apply Nat.div_le_of_le_mul
rw [Nat.mul_comm D]
exact Nat.mul_le_mul_left _ (Nat.sub_le _ _)
/-- Redemption never lowers backing: `T · (F − r) ≤ (T − payout) · F`. -/
theorem redeem_keeps_backing (T F r : Nat) :
T * (F - r) ≤ (T - payout T F r) * F := by
unfold payout
have hq := Nat.div_mul_le_self (r * T) F
rw [Nat.mul_sub_right_distrib, Nat.mul_sub_left_distrib, Nat.mul_comm T r]
omega
/-- Redemption invariance: when the share divides exactly, backing is unchanged. -/
theorem redeem_exact (T F r : Nat) (hd : F ∣ r * T) :
(T - payout T F r) * F = T * (F - r) := by
unfold payout
have hq := Nat.div_mul_cancel hd
rw [Nat.mul_sub_right_distrib, Nat.mul_sub_left_distrib, hq, Nat.mul_comm r T]
/-- Redemption with an exit fee, paid against the fully diluted supply
`C + G`, keeps backing against both `C + G` and `C`. -/
theorem redeem_fee_keeps (s T C G r : Nat) (hr : r ≤ C) :
T * (C + G - r) ≤ (T - exitPay s T (C + G) r) * (C + G) ∧
T * (C - r) ≤ (T - exitPay s T (C + G) r) * C := by
have e1 := exitPay_le s T (C + G) r
constructor
· exact Nat.le_trans (redeem_keeps_backing T (C + G) r)
(Nat.mul_le_mul_right _ (by omega))
· rcases Nat.eq_zero_or_pos C with hC | hC
· subst hC; simp
· have e2 : payout T (C + G) r ≤ payout T C r := div_anti _ (by omega) hC
exact Nat.le_trans (redeem_keeps_backing T C r) (Nat.mul_le_mul_right _ (by omega))
example : payout 1000 100 40 = 400 ∧ (1000 - 400) * 100 = 1000 * (100 - 40) := by decide
Accretive sale. A sale of new tokens for collateral is accretive if its price is at least the backing: .
Lemma 2. An accretive sale never lowers backing: . More generally, if , any level that the backing meets before the sale () it still meets afterwards.
Proof. Multiply the level by and chain it with the price condition: . Cancel and add . ∎
-- continues the definitions above
/-! ## Accretive issuance -/
theorem accretive_backing (T F f m : Nat) (h : T * m ≤ f * F) :
T * (F + m) ≤ (T + f) * F := by
rw [Nat.mul_add, Nat.add_mul]; omega
/-- Any backing level `num / den` met before an accretive sale is met after it. -/
theorem accretive_keeps_level (T F f m num den : Nat) (hF : 0 < F)
(hlev : F * num ≤ T * den) (h : T * m ≤ f * F) :
(F + m) * num ≤ (T + f) * den := by
have key : F * (m * num) ≤ F * (f * den) := by
calc F * (m * num) = m * (F * num) := by ac_rfl
_ ≤ m * (T * den) := Nat.mul_le_mul_left m hlev
_ = (T * m) * den := by ac_rfl
_ ≤ (f * F) * den := Nat.mul_le_mul_right den h
_ = F * (f * den) := by ac_rfl
have := Nat.le_of_mul_le_mul_left key hF
rw [Nat.add_mul, Nat.add_mul]; omega
The state machine
A floor curve is a function from supply to price, scaled by a constant . The floor holds in a state when the treasury covers the price for every circulating token:
Operations. With floor curve , scale and exit fee :
| operation | guard | effect |
|---|---|---|
fee f | none | |
vest | none | ; , |
burn m | ||
redeem r | , | |
mint f m | , , | , |
grant m | , | , |
genesis f m | , | , |
An operation whose guard fails leaves the state unchanged. The sale price is checked against , the backing including fees still in the queue. The queue releases at most per period, the same rate as the exit fee. Why the two rates match is the subject of Theorems 5 and 5′.
There is no issuance without collateral. A sale must be paid at backing. A grant comes from a reserve that was already counted in . Genesis needs an empty supply.
-- continues the definitions above
/-! ## The state machine -/
structure State where
T : Nat -- treasury: credited collateral
C : Nat -- circulating supply
Q : Nat -- fee queue: received, not yet credited
G : Nat -- grant reserve: announced, not yet issued
deriving Repr, DecidableEq
inductive Op where
| fee (f : Nat) -- a fee arrives and joins the queue
| vest -- one period's release from the queue
| burn (m : Nat) -- tokens destroyed, nothing paid
| redeem (r : Nat) -- tokens destroyed, pro-rata payout less exit fee
| mint (f m : Nat) -- accretive sale of m tokens for f
| grant (m : Nat) -- issue m tokens from the reserve
| genesis (f m : Nat) -- first issuance, only from empty supply
deriving Repr
/-- One period's release: `min(Q, ⌊T · s / D⌋)`. -/
def vestAmt (s : Nat) (st : State) : Nat := min st.Q (st.T * s / D)
/-- The transition function for floor curve `p`, scale `S` and exit fee `s`.
A failed guard leaves the state unchanged. -/
def step (p : Nat → Nat) (S s : Nat) (st : State) : Op → State
| .fee f => { st with Q := st.Q + f }
| .vest => { st with T := st.T + vestAmt s st, Q := st.Q - vestAmt s st }
| .burn m => if m ≤ st.C then { st with C := st.C - m } else st
| .redeem r =>
if r ≤ st.C then
{ st with T := st.T - exitPay s st.T (st.C + st.G) r, C := st.C - r }
else st
| .mint f m =>
if 0 < st.C ∧ (st.T + st.Q) * m ≤ f * (st.C + st.G) ∧
(st.C + m) * p (st.C + m) ≤ (st.T + f) * S
then { st with T := st.T + f, C := st.C + m } else st
| .grant m =>
if m ≤ st.G ∧ (st.C + m) * p (st.C + m) ≤ st.T * S
then { st with C := st.C + m, G := st.G - m } else st
| .genesis f m =>
if st.C = 0 ∧ (st.C + m) * p (st.C + m) ≤ (st.T + f) * S
then { st with T := st.T + f, C := st.C + m } else st
def run (p : Nat → Nat) (S s : Nat) (st : State) (ops : List Op) : State :=
ops.foldl (step p S s) st
/-- The floor holds: `C · p(C) ≤ T · S`. -/
def Floor (p : Nat → Nat) (S : Nat) (st : State) : Prop := st.C * p st.C ≤ st.T * S
def Mono (p : Nat → Nat) : Prop := ∀ a b, a ≤ b → p a ≤ p b
Theorem 3 (master invariant). Let be any monotone floor curve: . For every scale and exit fee , if holds in a state, it holds after every finite sequence of operations.
Proof. By induction on the sequence, it suffices to check one step. A fee changes neither nor . A release only raises . The three issuing operations check the floor in their guard. Burning lowers and, by monotonicity, . For a redemption, Theorem 1 gives , and then
so after cancelling . ∎
The argument uses nothing about except monotonicity. So the curve can be chosen for its shape alone (later sections do this), and the invariant comes for free.
-- continues the definitions above
/-! ## The master invariant -/
theorem floor_after_shrink (p : Nat → Nat) (hp : Mono p) (S T C T' r : Nat)
(h : C * p C ≤ T * S) (hT : T * (C - r) ≤ T' * C) :
(C - r) * p (C - r) ≤ T' * S := by
rcases Nat.eq_zero_or_pos C with hC | hC
· subst hC; simp
· apply Nat.le_of_mul_le_mul_left _ hC
calc C * ((C - r) * p (C - r)) ≤ C * ((C - r) * p C) :=
Nat.mul_le_mul_left C (Nat.mul_le_mul_left (C - r) (hp _ _ (Nat.sub_le C r)))
_ = (C - r) * (C * p C) := by ac_rfl
_ ≤ (C - r) * (T * S) := Nat.mul_le_mul_left (C - r) h
_ = (T * (C - r)) * S := by ac_rfl
_ ≤ (T' * C) * S := Nat.mul_le_mul_right S hT
_ = C * (T' * S) := by ac_rfl
theorem step_floor (p : Nat → Nat) (hp : Mono p) (S s : Nat) (st : State) (o : Op)
(h : Floor p S st) : Floor p S (step p S s st o) := by
unfold Floor at *
cases o with
| fee f => exact h
| vest => exact Nat.le_trans h (Nat.mul_le_mul_right S (Nat.le_add_right _ _))
| burn m =>
simp only [step]; split
· exact Nat.le_trans (Nat.mul_le_mul (Nat.sub_le _ _) (hp _ _ (Nat.sub_le _ _))) h
· exact h
| redeem r =>
simp only [step]; split
· rename_i hr
exact floor_after_shrink p hp S st.T st.C _ r h
(redeem_fee_keeps s st.T st.C st.G r hr).2
· exact h
| mint f m =>
simp only [step]; split
· rename_i hg; exact hg.2.2
· exact h
| grant m =>
simp only [step]; split
· rename_i hg; exact hg.2
· exact h
| genesis f m =>
simp only [step]; split
· rename_i hg; exact hg.2
· exact h
/-- **Master invariant.** For every monotone floor curve `p`, scale `S` and
exit fee `s`, a floor that holds at the start holds after every finite
sequence of operations. -/
theorem run_floor (p : Nat → Nat) (hp : Mono p) (S s : Nat) :
∀ (ops : List Op) (st : State), Floor p S st → Floor p S (run p S s st ops)
| [], _, h => h
| o :: os, st, h => run_floor p hp S s os (step p S s st o) (step_floor p hp S s st o h)
theorem genesis_only_at_zero (p : Nat → Nat) (S s : Nat) (st : State) (f m : Nat)
(hC : 0 < st.C) : step p S s st (.genesis f m) = st := by
simp only [step]
rw [if_neg (by omega)]
Theorem 4 (backing never decreases). Over any finite sequence of fees, releases, burns, redemptions, sales and grants, in any order, the fully diluted backing ends at least where it began:
Consequently the circulating backing never falls below the initial fully diluted backing . In particular, grants can lower circulating backing from at most to , a bound fixed by the reserve at the start.
Proof. Show that every level is preserved by each non-genesis step. Fees and releases leave fixed and do not lower . A burn lowers . A redemption is Theorem 1 against . A sale is Lemma 2, because . A grant moves from to and leaves fixed. Then apply the result with of the initial state. ∎
Genesis is excluded because it sets the initial backing rather than preserving one.
-- continues the definitions above
/-! ## Backing never decreases -/
def Op.accretive : Op → Bool
| .genesis _ _ => false
| _ => true
/-- Fully diluted backing is at least `num / den`. -/
def Backs (num den : Nat) (st : State) : Prop := (st.C + st.G) * num ≤ st.T * den
theorem step_backs (p : Nat → Nat) (S s num den : Nat) (st : State) (o : Op)
(ho : o.accretive = true) (h : Backs num den st) :
Backs num den (step p S s st o) := by
unfold Backs at *
cases o with
| fee f => exact h
| vest => exact Nat.le_trans h (Nat.mul_le_mul_right den (Nat.le_add_right _ _))
| burn m =>
simp only [step]; split
· show (st.C - m + st.G) * num ≤ st.T * den
exact Nat.le_trans (Nat.mul_le_mul_right num (by omega)) h
· exact h
| redeem r =>
simp only [step]; split
· rename_i hr
have := floor_after_shrink (fun _ => num) (fun _ _ _ => Nat.le_refl _) den
st.T (st.C + st.G) _ r h (redeem_fee_keeps s st.T st.C st.G r hr).1
have e : st.C - r + st.G = st.C + st.G - r := by omega
simp only [e]; exact this
· exact h
| mint f m =>
simp only [step]; split
· rename_i hg
have hF : 0 < st.C + st.G := by omega
have hm : st.T * m ≤ f * (st.C + st.G) :=
Nat.le_trans (Nat.mul_le_mul_right m (Nat.le_add_right _ _)) hg.2.1
have := accretive_keeps_level st.T (st.C + st.G) f m num den hF h hm
have e : st.C + m + st.G = st.C + st.G + m := by omega
simp only [e]; exact this
· exact h
| grant m =>
simp only [step]; split
· rename_i hg
have e : st.C + m + (st.G - m) = st.C + st.G := by omega
simp only [e]; exact h
· exact h
| genesis f m => simp [Op.accretive] at ho
theorem run_backs (p : Nat → Nat) (S s num den : Nat) :
∀ (ops : List Op) (st : State), ops.all Op.accretive = true →
Backs num den st → Backs num den (run p S s st ops)
| [], _, _, h => h
| o :: os, st, ha, h => by
simp only [List.all_cons, Bool.and_eq_true] at ha
exact run_backs p S s num den os (step p S s st o) ha.2
(step_backs p S s num den st o ha.1 h)
/-- **Backing never decreases.** After any sequence of non-genesis operations,
`(C' + G') · T ≤ T' · (C + G)`. -/
theorem backing_never_decreases (p : Nat → Nat) (S s : Nat) (st : State) (ops : List Op)
(ha : ops.all Op.accretive = true) :
((run p S s st ops).C + (run p S s st ops).G) * st.T ≤
(run p S s st ops).T * (st.C + st.G) :=
run_backs p S s st.T (st.C + st.G) ops st ha (Nat.le_of_eq (Nat.mul_comm _ _))
/-- Circulating backing never falls below the initial fully diluted backing. -/
theorem circulating_backing_bound (p : Nat → Nat) (S s : Nat) (st : State) (ops : List Op)
(ha : ops.all Op.accretive = true) :
(run p S s st ops).C * st.T ≤ (run p S s st ops).T * (st.C + st.G) :=
Nat.le_trans (Nat.mul_le_mul_right _ (Nat.le_add_right _ _))
(backing_never_decreases p S s st ops ha)
/-- Unpaid issuance is not expressible: an unpaid sale fails the price guard,
an unannounced grant the reserve guard, a second genesis the empty-supply guard. -/
example : let st : State := ⟨1000, 100, 0, 0⟩
run (fun _ => 1) 1 0 st [.mint 0 900, .grant 900, .genesis 0 900] = st := by decide
The fee queue
If fees were credited to the treasury immediately, a trader could buy just before a large fee and redeem just after it, taking a share of a fee that the existing holders would otherwise have received. With a treasury of 1000 against 100 tokens, buying 900 tokens at backing for 9000, letting a fee of 1000 land, and redeeming returns 9900 for 9000. The queue limits how fast a fee reaches the treasury: one period’s release adds at most a fraction of , and the exit fee takes the same fraction back.
Theorem 5 (sandwich bound). From any state and for any exit fee : buy tokens for in an accepted sale, let any fee arrive, let one period’s release happen, and redeem the tokens. The amount returned is at most .
Proof. Write and , and let be the amount released, so . The sale guard gives . Write . The redemption pays at most , and
where the first step uses , so . ∎
Replaying the trade above with returns 8999 for 9000. Theorem 5 covers a round trip that spans exactly one release, and nothing in the machine limits how many releases fall between a purchase and a redemption. A buyer who holds through several releases is a holder for those periods and is paid as one. The same trade held through two releases returns 9088 for 9000. The next theorem gives the exact rate.
Theorem 5′ (holding through releases). From any state: buy tokens for in an accepted sale, then let any sequence of fees and releases happen that contains releases, then redeem the tokens. The amount returned satisfies
Proof. Fees change neither nor the supply. A release raises to with , so . By induction, the treasury after the window satisfies , and the supply is still . The redemption pays at most , and . ∎
So the queue spreads each fee over the periods in which it is released, and the fee goes to whoever holds during those periods, including holders who arrived after it was paid. For the bound is and for it is . For it can exceed , and the two-release trade above shows that a profit of this order does occur. The bound grows by at most the factor per period, the most that one release can add to the treasury. Frontrunning around value transfers of this kind is studied in Flash Boys 2.0: Frontrunning in Decentralized Exchanges, Miner Extractable Value, and Consensus Instability (IEEE Symposium on Security and Privacy, 2020).
-- continues the definitions above
/-! ## The fee queue and the sandwich bound -/
/-- If fees were credited at once: buy 900 at backing 10, a fee of 1000 lands,
redeem; 9000 in, 9900 out. -/
example : payout (1000 + 9000 + 1000) (100 + 900) 900 = 9900 := by decide
/-- Arithmetic core, with `E = D − s`. -/
theorem sandwich_arith (T₁ q m f F E s : Nat) (hD : 0 < E + s)
(hq : q * (E + s) ≤ s * T₁) (hacc : m * T₁ ≤ f * F) :
m * (T₁ + q) * E ≤ (E + s) * (f * F) := by
have h1 : m * E * (q * (E + s)) ≤ m * E * (s * T₁) := Nat.mul_le_mul_left _ hq
have h2 : (m * T₁) * ((E + s) * (E + s)) ≤ (f * F) * ((E + s) * (E + s)) :=
Nat.mul_le_mul_right _ hacc
apply Nat.le_of_mul_le_mul_left _ hD
poly_nat
/-- **Sandwich bound.** Buy `m` tokens for `f`, let any fee `e` arrive, let one
period's release happen, redeem the `m` tokens: the exit value is at most `f`. -/
theorem no_sandwich (p : Nat → Nat) (S s : Nat) (st : State) (f m e : Nat)
(hs : s ≤ D)
(hg : 0 < st.C ∧ (st.T + st.Q) * m ≤ f * (st.C + st.G) ∧
(st.C + m) * p (st.C + m) ≤ (st.T + f) * S) :
let st' := run p S s st [.mint f m, .fee e, .vest]
exitPay s st'.T (st'.C + st'.G) m ≤ f := by
simp only [run, List.foldl, step, if_pos hg]
generalize hq : vestAmt s _ = q
have hqle : q * D ≤ s * (st.T + f) := by
rw [← hq]; unfold vestAmt
have := Nat.div_mul_le_self ((st.T + f) * s) D
have hmin := Nat.min_le_right (st.Q + e) ((st.T + f) * s / D)
simp only at hmin ⊢
rw [Nat.mul_comm s]
exact Nat.le_trans (Nat.mul_le_mul_right D hmin) this
have hacc : m * (st.T + f) ≤ f * (st.C + m + st.G) := by
have := Nat.le_trans (Nat.mul_le_mul_right m (Nat.le_add_right st.T st.Q)) hg.2.1
poly_nat
obtain ⟨E, hE⟩ : ∃ E, D = E + s := ⟨D - s, by omega⟩
have hDpos : 0 < E + s := by rw [← hE]; decide
have core := sandwich_arith (st.T + f) q m f (st.C + m + st.G) E s hDpos
(by rw [← hE]; exact hqle) hacc
have hFpos : 0 < st.C + m + st.G := by omega
unfold exitPay payout
apply Nat.div_le_of_le_mul
have hDE : D - s = E := by omega
rw [hDE]
apply Nat.le_of_mul_le_mul_left _ hFpos
have hx := Nat.div_mul_le_self (m * (st.T + f + q)) (st.C + m + st.G)
calc (st.C + m + st.G) * (m * (st.T + f + q) / (st.C + m + st.G) * E)
= (m * (st.T + f + q) / (st.C + m + st.G) * (st.C + m + st.G)) * E := by ac_rfl
_ ≤ (m * (st.T + f + q)) * E := Nat.mul_le_mul_right E hx
_ ≤ (E + s) * (f * (st.C + m + st.G)) := core
_ = (st.C + m + st.G) * (D * f) := by rw [hE]; ac_rfl
/-- The same trade with the queue and `s = 1 %`: 9000 in, 8999 out. -/
example : let st : State := ⟨1000, 100, 0, 0⟩
let st' := run (fun _ => 0) 1 100 st [.mint 9000 900, .fee 1000, .vest]
st' = ⟨10100, 1000, 900, 0⟩ ∧ exitPay 100 st'.T (st'.C + st'.G) 900 = 8999 := by
decide
/-- Held through two releases instead of one: 9000 in, 9088 out. -/
example : let st : State := ⟨1000, 100, 0, 0⟩
let st' := run (fun _ => 0) 1 100 st [.mint 9000 900, .fee 1000, .vest, .vest]
st' = ⟨10201, 1000, 799, 0⟩ ∧ exitPay 100 st'.T (st'.C + st'.G) 900 = 9088 := by
decide
/-! ### Holding through several releases -/
/-- Fees and releases: the operations that change neither supply nor credited
collateral other than by releasing the queue. -/
def Op.quiet : Op → Bool
| .fee _ => true
| .vest => true
| _ => false
/-- The number of releases in a list of operations. -/
def releases : List Op → Nat
| [] => 0
| .vest :: os => releases os + 1
| _ :: os => releases os
/-- Over fees and releases the supply is fixed, and each release multiplies the
treasury by at most `(D + s) / D`. -/
theorem quiet_growth (p : Nat → Nat) (S s : Nat) :
∀ (w : List Op) (st : State), w.all Op.quiet = true →
(run p S s st w).C = st.C ∧ (run p S s st w).G = st.G ∧
(run p S s st w).T * D ^ releases w ≤ (D + s) ^ releases w * st.T
| [], st, _ => by simp [run, releases]
| o :: os, st, hw => by
simp only [List.all_cons, Bool.and_eq_true] at hw
have ih := quiet_growth p S s os (step p S s st o) hw.2
have e : run p S s st (o :: os) = run p S s (step p S s st o) os := rfl
rw [e]
cases o with
| fee e' => exact ih
| vest =>
obtain ⟨h1, h2, h3⟩ := ih
refine ⟨h1, h2, ?_⟩
have hv : vestAmt s st * D ≤ s * st.T := by
unfold vestAmt
have := Nat.div_mul_le_self (st.T * s) D
have hmin := Nat.min_le_right st.Q (st.T * s / D)
rw [Nat.mul_comm s]
exact Nat.le_trans (Nat.mul_le_mul_right D hmin) this
show _ * D ^ (releases os + 1) ≤ (D + s) ^ (releases os + 1) * st.T
rw [Nat.pow_succ, Nat.pow_succ]
generalize (run p S s (step p S s st .vest) os).T = R at h3 ⊢
generalize D ^ releases os = B at h3 ⊢
generalize (D + s) ^ releases os = A at h3 ⊢
have h3' : R * B ≤ A * (st.T + vestAmt s st) := h3
calc R * (B * D) = (R * B) * D := by ac_rfl
_ ≤ (A * (st.T + vestAmt s st)) * D := Nat.mul_le_mul_right D h3'
_ = A * (st.T * D + vestAmt s st * D) := by
rw [Nat.mul_assoc, Nat.add_mul]
_ ≤ A * (st.T * D + s * st.T) :=
Nat.mul_le_mul_left A (Nat.add_le_add_left hv _)
_ = A * (D + s) * st.T := by
rw [Nat.mul_assoc, Nat.add_mul, Nat.mul_comm st.T D]
| burn _ => simp [Op.quiet] at hw
| redeem _ => simp [Op.quiet] at hw
| mint _ _ => simp [Op.quiet] at hw
| grant _ => simp [Op.quiet] at hw
| genesis _ _ => simp [Op.quiet] at hw
/-- **Holding through `k` releases.** Buy `m` tokens for `f`, then any fees and
releases, `k = releases w` of them, then redeem the `m` tokens: the exit value
`X` satisfies `X · D^(k+1) ≤ f · (D − s) · (D + s)^k`. -/
theorem hold_bound (p : Nat → Nat) (S s : Nat) (st : State) (f m : Nat) (w : List Op)
(hw : w.all Op.quiet = true)
(hg : 0 < st.C ∧ (st.T + st.Q) * m ≤ f * (st.C + st.G) ∧
(st.C + m) * p (st.C + m) ≤ (st.T + f) * S) :
let st' := run p S s st (.mint f m :: w)
exitPay s st'.T (st'.C + st'.G) m * D ^ (releases w + 1) ≤
f * (D - s) * (D + s) ^ releases w := by
have e : run p S s st (.mint f m :: w) =
run p S s ⟨st.T + f, st.C + m, st.Q, st.G⟩ w := by
show run p S s (step p S s st (.mint f m)) w = _
simp only [step, if_pos hg]
simp only [e]
obtain ⟨hC, hG, hT⟩ := quiet_growth p S s w ⟨st.T + f, st.C + m, st.Q, st.G⟩ hw
simp only at hC hG hT
rw [hC, hG, Nat.pow_succ]
generalize (run p S s ⟨st.T + f, st.C + m, st.Q, st.G⟩ w).T = R at hT ⊢
generalize D ^ releases w = B at hT ⊢
generalize (D + s) ^ releases w = A at hT ⊢
have hacc : m * (st.T + f) ≤ f * (st.C + m + st.G) := by
have := Nat.le_trans (Nat.mul_le_mul_right m (Nat.le_add_right st.T st.Q)) hg.2.1
poly_nat
have hFpos : 0 < st.C + m + st.G := by omega
unfold exitPay payout
generalize D - s = E
generalize hP : m * R / (st.C + m + st.G) = P
have hPF : P * (st.C + m + st.G) ≤ m * R := by
rw [← hP]; exact Nat.div_mul_le_self _ _
have hX := Nat.div_mul_le_self (P * E) D
apply Nat.le_of_mul_le_mul_left _ hFpos
calc (st.C + m + st.G) * (P * E / D * (B * D))
= B * (P * E / D * D) * (st.C + m + st.G) := by ac_rfl
_ ≤ B * (P * E) * (st.C + m + st.G) :=
Nat.mul_le_mul_right _ (Nat.mul_le_mul_left B hX)
_ = (P * (st.C + m + st.G)) * (B * E) := by ac_rfl
_ ≤ (m * R) * (B * E) := Nat.mul_le_mul_right _ hPF
_ = (R * B) * (m * E) := by ac_rfl
_ ≤ (A * (st.T + f)) * (m * E) := Nat.mul_le_mul_right _ hT
_ = (m * (st.T + f)) * (A * E) := by ac_rfl
_ ≤ (f * (st.C + m + st.G)) * (A * E) := Nat.mul_le_mul_right _ hacc
_ = (st.C + m + st.G) * (f * E * A) := by ac_rfl
A cap in dollars
A floor is usually published in dollars, while the treasury holds collateral whose price moves. A cap with safety factor requires
This is the floor invariant with curve and scale . Prices change between operations, so the machine is driven by a list of events: operations, each guarded at the current price, and price moves.
Theorem 6 (drawdown). Suppose the cap holds at price and the price falls to with , a drawdown of at most . Then the dollar value of the treasury still covers the published floor: .
The bound is tight. If the cap holds with equality and , every larger drawdown () gives .
Proof. . For tightness, . ∎
The theorem has a precise scope. It protects the floor promise, the inequality between the treasury’s dollar value and the published curve. It does not protect what a holder receives in dollars. A price move changes no field of the state, so the collateral paid for tokens is the same before and after it, and its dollar value falls in exact proportion to the price, whatever is. Backing in collateral survives every price path (it is a collateral quantity, and Theorem 4 holds event by event). Redemption stays pro rata, so a crash gives no advantage to whoever exits first.
After a crash below the cap, every issuing operation is either rejected or lands inside the cap at the new price. Grants stop. A sale goes through only if it brings enough collateral to restore the cap. The last example below starts at the cap with , halves the price, rejects a sale at backing, accepts a sale of 10 tokens for 1200, and ends with backing 20 instead of 10.
-- continues the definitions above
/-! ## A cap in dollars -/
inductive Ev where
| op (o : Op)
| reprice (v : Nat)
/-- Events from collateral price `v`; each operation is guarded by the cap
`kn · C · p(C) ≤ kd · v · T` at the current price. -/
def runV (p : Nat → Nat) (kn kd s : Nat) : Nat → State → List Ev → State
| _, st, [] => st
| v, st, .op o :: es => runV p kn kd s v (step (fun c => kn * p c) (kd * v) s st o) es
| _, st, .reprice v' :: es => runV p kn kd s v' st es
def Ev.accretive : Ev → Bool
| .op o => o.accretive
| .reprice _ => true
/-- Backing, a collateral quantity, never decreases along any price path. -/
theorem backing_any_prices (p : Nat → Nat) (kn kd s num den : Nat) :
∀ (es : List Ev) (v : Nat) (st : State), es.all Ev.accretive = true →
Backs num den st → Backs num den (runV p kn kd s v st es)
| [], _, _, _, h => h
| .op o :: es, v, st, ha, h => by
simp only [List.all_cons, Bool.and_eq_true, Ev.accretive] at ha
exact backing_any_prices p kn kd s num den es v _ ha.2
(step_backs _ _ s num den st o ha.1 h)
| .reprice v' :: es, _, st, ha, h => by
simp only [List.all_cons, Bool.and_eq_true] at ha
exact backing_any_prices p kn kd s num den es v' st ha.2 h
/-- A price move changes no part of the state. -/
theorem reprice_inert (p : Nat → Nat) (kn kd s v v' : Nat) (st : State) :
runV p kn kd s v st [.reprice v'] = st := rfl
/-- Every issuing operation is rejected or lands inside the cap at the
current price. -/
theorem issue_meets_cap (p : Nat → Nat) (kn kd v s : Nat) (st : State) (o : Op)
(hf : ∀ f, o ≠ .fee f) (hv : o ≠ .vest) (hb : ∀ m, o ≠ .burn m)
(hr : ∀ r, o ≠ .redeem r) :
let st' := step (fun c => kn * p c) (kd * v) s st o
st' = st ∨ Floor (fun c => kn * p c) (kd * v) st' := by
cases o with
| fee f => exact absurd rfl (hf f)
| vest => exact absurd rfl hv
| burn m => exact absurd rfl (hb m)
| redeem r => exact absurd rfl (hr r)
| mint f m =>
simp only [step]; split
· rename_i hg; exact Or.inr hg.2.2
· exact Or.inl rfl
| grant m =>
simp only [step]; split
· rename_i hg; exact Or.inr hg.2
· exact Or.inl rfl
| genesis f m =>
simp only [step]; split
· rename_i hg; exact Or.inr hg.2
· exact Or.inl rfl
/-- **Drawdown theorem.** If `κ · C·p(C) ≤ v · T` with `κ = kn/kd` and the
price falls to `v'` with `v · kd ≤ v' · kn`, then `C·p(C) ≤ v' · T`. -/
theorem dollar_floor (kn kd v v' T C pC : Nat) (hk : 0 < kn)
(hcap : kn * (C * pC) ≤ kd * v * T) (hdraw : v * kd ≤ v' * kn) :
C * pC ≤ v' * T := by
apply Nat.le_of_mul_le_mul_left _ hk
calc kn * (C * pC) ≤ kd * v * T := hcap
_ = (v * kd) * T := by ac_rfl
_ ≤ (v' * kn) * T := Nat.mul_le_mul_right T hdraw
_ = kn * (v' * T) := by ac_rfl
/-- **Tightness.** If the cap is met with equality and `T > 0`, any deeper
drawdown (`v' · kn < v · kd`) breaks the floor promise. -/
theorem dollar_floor_tight (kn kd v v' T C pC : Nat) (hT : 0 < T)
(hcap : kn * (C * pC) = kd * v * T) (hdraw : v' * kn < v * kd) :
v' * T < C * pC := by
apply Nat.lt_of_mul_lt_mul_left (a := kn)
calc kn * (v' * T) = (v' * kn) * T := by ac_rfl
_ < (v * kd) * T := Nat.mul_lt_mul_of_pos_right hdraw hT
_ = kn * (C * pC) := by rw [hcap]; ac_rfl
/-- A crash, then recovery by a sale: at half price a sale at backing is
rejected, a sale that restores the cap is accepted, and backing rises. -/
example : let st : State := ⟨1000, 100, 0, 0⟩
runV (fun _ => 10) 2 1 0 2 st [.reprice 1, .op (.mint 10 1), .op (.mint 1200 10)] =
⟨2200, 110, 0, 0⟩ := by decide
Which cubic Bézier curves are floor curves
A cubic Bézier curve with control points , , is on , with
and likewise. To serve as a floor curve, it has to be the graph of a function , read off at . With , the derivative in Bernstein form is
The Bernstein basis and its sign properties are surveyed in The Bernstein polynomial basis: a centennial retrospective (Computer Aided Geometric Design, 2012). In Lean, the derivative is established by an exact Taylor expansion: is a polynomial identity. At with , multiplying by gives the homogeneous form
so the sign of on the rationals in is the sign of on pairs of nonnegative integers. The proofs rest on two identities:
-- continues the definitions above
/-! ## Cubic Bézier coordinates -/
/-- One coordinate of a cubic Bézier curve with controls `x₀, x₁, x₂, x₃`. -/
def bez3 (x0 x1 x2 x3 t : Int) : Int :=
x0 * (1 - t) * (1 - t) * (1 - t) + 3 * x1 * t * (1 - t) * (1 - t) +
3 * x2 * t * t * (1 - t) + x3 * t * t * t
/-- Its derivative, in Bernstein form with coefficients `Δᵢ = xᵢ₊₁ − xᵢ`. -/
def bezD (x0 x1 x2 x3 t : Int) : Int :=
3 * ((x1 - x0) * (1 - t) * (1 - t) + 2 * (x2 - x1) * t * (1 - t) + (x3 - x2) * t * t)
/-- Half the second derivative, and a sixth of the third. -/
def bezH (x0 x1 x2 x3 t : Int) : Int := 3 * ((x2 - 2 * x1 + x0) * (1 - t) + (x3 - 2 * x2 + x1) * t)
def bezK (x0 x1 x2 x3 : Int) : Int := x3 - 3 * x2 + 3 * x1 - x0
/-- Exact Taylor expansion of a cubic: `bezD` is the derivative of `bez3`. -/
theorem bez_taylor (x0 x1 x2 x3 t h : Int) :
bez3 x0 x1 x2 x3 (t + h) = bez3 x0 x1 x2 x3 t + h * bezD x0 x1 x2 x3 t +
h * h * bezH x0 x1 x2 x3 t + h * h * h * bezK x0 x1 x2 x3 := by
unfold bez3 bezD bezH bezK; poly_int
/-- A quadratic in Bernstein form, homogenised at `t = α/(α+β)`:
`a·q² + 2b·pq + c·p²`. -/
def bq (a b c α β : Int) : Int := a * β * β + 2 * b * α * β + c * α * α
/-- `bq` is the homogenisation of `bezD / 3`: it agrees at `β = 1 − α` and is
homogeneous of degree 2. -/
theorem bezD_homog (x0 x1 x2 x3 t : Int) :
bezD x0 x1 x2 x3 t = 3 * bq (x1 - x0) (x2 - x1) (x3 - x2) t (1 - t) := by
unfold bezD bq; poly_int
theorem bq_scale (a b c α β l : Int) : bq a b c (l * α) (l * β) = l * l * bq a b c α β := by
unfold bq; poly_int
Theorem 7 (graph criterion). Let the control points be rational, with . The following are equivalent.
- Every vertical line with meets the curve at exactly one parameter , so the curve is the graph of a function on .
- is strictly increasing on .
- for all .
- , , and or . Equivalently, .
Proof. (1 ⇔ 2) A continuous function on an interval is injective iff it is strictly monotone, by the intermediate value theorem, and fixes the direction. (2 ⇒ 3) is standard. (3 ⇒ 2) is a polynomial that is not identically zero, since its integral is , so it has finitely many zeros, and is strictly increasing. (3 ⇔ 4) is proved in Lean for all rational and integer (rational controls are scaled by a common denominator, which changes no sign), and extends to real by continuity. If and , then either and the vertex gives , or and gives . Conversely, under (4) with we have , and the first identity writes as a sum of two nonnegative terms. ∎
The Lean statements of (3 ⇔ 4) are the integer forms, over rational . The steps (1 ⇔ 2 ⇔ 3) and the passage from rational to real are standard real analysis and are not formalised. For real control points the same two identities give the same proof, but only the rational case is formalised.
Theorem 8 (vertical tangents). Assume the criterion of Theorem 7. Then at an interior parameter iff
or all , which rules out. At the ends, and . Moreover, on all of iff , , and or .
Proof. If , every term of is nonnegative, and with they all vanish only if every . If , then , and forces both squares in the first identity to vanish, so . Conversely, the vertex is a zero when . The strict version follows from the same two identities. ∎
At such a , if also , the tangent is vertical: is unbounded as . For a floor curve this matters. With supply ceiling and , the collateral needed per new token is , so near each unit of collateral admits fewer and fewer tokens, and issuance stalls. Theorem 8 says exactly which control polygons produce this. Choosing control points with and rules it out. The last statement of Theorem 8 is exact: these conditions, or in place of , are the only way to keep everywhere.
-- continues the definitions above
theorem bq_key (a b c α β : Int) :
a * bq a b c α β = (a * β + b * α) * (a * β + b * α) + (a * c - b * b) * (α * α) := by
unfold bq; poly_int
theorem bq_vertex (a b c : Int) : bq a b c (-b) c = c * (a * c - b * b) := by
unfold bq; poly_int
theorem bq_nonneg_of_b (a b c α β : Int) (ha : 0 ≤ a) (hb : 0 ≤ b) (hc : 0 ≤ c)
(hp : 0 ≤ α) (hq : 0 ≤ β) : 0 ≤ bq a b c α β := by
have h1 : 0 ≤ a * β * β := Int.mul_nonneg (Int.mul_nonneg ha hq) hq
have h2 : 0 ≤ b * α * β := Int.mul_nonneg (Int.mul_nonneg hb hp) hq
have h3 : 0 ≤ c * α * α := Int.mul_nonneg (Int.mul_nonneg hc hp) hp
unfold bq; poly_int
theorem sq_nonneg' (x : Int) : 0 ≤ x * x := by
rcases (show 0 ≤ x ∨ x ≤ 0 by omega) with h | h
· exact Int.mul_nonneg h h
· exact Int.mul_nonneg_of_nonpos_of_nonpos h h
/-- **Monotonicity criterion.** `x' ≥ 0` at every `t = α/(α+β) ∈ [0, 1]` iff
`Δ₀ ≥ 0`, `Δ₂ ≥ 0` and (`Δ₁ ≥ 0` or `Δ₁² ≤ Δ₀Δ₂`). -/
theorem bq_nonneg_iff (a b c : Int) :
(∀ α β : Int, 0 ≤ α → 0 ≤ β → 0 ≤ bq a b c α β) ↔
(0 ≤ a ∧ 0 ≤ c ∧ (0 ≤ b ∨ b * b ≤ a * c)) := by
constructor
· intro h
have ha : 0 ≤ a := by have := h 0 1 (by decide) (by decide); unfold bq at this; omega
have hc : 0 ≤ c := by have := h 1 0 (by decide) (by decide); unfold bq at this; omega
refine ⟨ha, hc, ?_⟩
rcases (show 0 ≤ b ∨ b < 0 by omega) with hb | hb
· exact Or.inl hb
· right
rcases (show b ≤ 0 ∨ 0 < b by omega) with _ | _
· rcases (show c = 0 ∨ 0 < c by omega) with hc0 | hcp
· -- c = 0: a + 2b·α goes negative at α = a + 1
subst hc0
have h1 := h (a + 1) 1 (by omega) (by decide)
have h2 : b * (a + 1) ≤ (-1) * (a + 1) :=
Int.mul_le_mul_of_nonneg_right (by omega) (by omega)
unfold bq at h1; poly_int
· -- c > 0: the vertex value is c·(ac − b²)
have h1 := h (-b) c (by omega) (by omega)
rw [bq_vertex] at h1
rcases (show (b * b) ≤ (a * c) ∨ (a * c) < (b * b) by omega) with hh | hh
· exact hh
· have : c * (a * c - b * b) < 0 := Int.mul_neg_of_pos_of_neg hcp (by omega)
omega
· omega
· rintro ⟨ha, hc, hb⟩ α β hp hq
rcases hb with hb | hb
· exact bq_nonneg_of_b a b c α β ha hb hc hp hq
· rcases (show 0 ≤ b ∨ b < 0 by omega) with hb0 | hb0
· exact bq_nonneg_of_b a b c α β ha hb0 hc hp hq
· have hbb : 0 < b * b := Int.mul_pos_of_neg_of_neg hb0 hb0
have hapos : 0 < a := by
rcases (show a = 0 ∨ 0 < a by omega) with h0 | h0
· subst h0; simp at hb; omega
· exact h0
have hk := bq_key a b c α β
have hs := sq_nonneg' (a * β + b * α)
have hr : 0 ≤ (a * c - b * b) * (α * α) :=
Int.mul_nonneg (by omega) (sq_nonneg' α)
rcases (show 0 ≤ (bq a b c α β) ∨ (bq a b c α β) < 0 by omega) with h0 | h0
· exact h0
· have : a * bq a b c α β < 0 := Int.mul_neg_of_pos_of_neg hapos h0
omega
-- continues the definitions above
/-- **Stationary points.** Under the monotonicity criterion, `x'` vanishes at
some interior `t ∈ (0, 1)` iff `Δ₁ < 0 ∧ Δ₁² = Δ₀Δ₂`, or all `Δᵢ = 0`. -/
theorem bq_interior_zero_iff (a b c : Int)
(h : 0 ≤ a ∧ 0 ≤ c ∧ (0 ≤ b ∨ b * b ≤ a * c)) :
(∃ α β : Int, 0 < α ∧ 0 < β ∧ bq a b c α β = 0) ↔
((b < 0 ∧ b * b = a * c) ∨ (a = 0 ∧ b = 0 ∧ c = 0)) := by
obtain ⟨ha, hc, hb⟩ := h
constructor
· rintro ⟨α, β, hp, hq, h0⟩
rcases (show 0 ≤ b ∨ b < 0 by omega) with hb0 | hb0
· right
have h1 : 0 ≤ a * β * β := Int.mul_nonneg (Int.mul_nonneg ha (by omega)) (by omega)
have h2 : 0 ≤ b * α * β := Int.mul_nonneg (Int.mul_nonneg hb0 (by omega)) (by omega)
have h3 : 0 ≤ c * α * α := Int.mul_nonneg (Int.mul_nonneg hc (by omega)) (by omega)
have e1 : a * β * β = 0 := by unfold bq at h0; poly_int
have e2 : b * α * β = 0 := by unfold bq at h0; poly_int
have e3 : c * α * α = 0 := by unfold bq at h0; poly_int
have hq0 : β ≠ 0 := by omega
have hp0 : α ≠ 0 := by omega
refine ⟨?_, ?_, ?_⟩
· rcases Int.mul_eq_zero.1 e1 with e | e
· rcases Int.mul_eq_zero.1 e with e | e
· exact e
· exact absurd e hq0
· exact absurd e hq0
· rcases Int.mul_eq_zero.1 e2 with e | e
· rcases Int.mul_eq_zero.1 e with e | e
· exact e
· exact absurd e hp0
· exact absurd e hq0
· rcases Int.mul_eq_zero.1 e3 with e | e
· rcases Int.mul_eq_zero.1 e with e | e
· exact e
· exact absurd e hp0
· exact absurd e hp0
· left
refine ⟨hb0, ?_⟩
have hbb : 0 < b * b := Int.mul_pos_of_neg_of_neg hb0 hb0
have hle : b * b ≤ a * c := by
rcases hb with hb | hb
· omega
· exact hb
have hk := bq_key a b c α β
rw [h0, Int.mul_zero] at hk
have hs := sq_nonneg' (a * β + b * α)
have hr : 0 ≤ (a * c - b * b) * (α * α) :=
Int.mul_nonneg (by omega) (sq_nonneg' α)
have hz : (a * c - b * b) * (α * α) = 0 := by omega
rcases Int.mul_eq_zero.1 hz with e | e
· omega
· rcases Int.mul_eq_zero.1 e with e | e <;> omega
· rintro (⟨hb0, he⟩ | ⟨rfl, rfl, rfl⟩)
· have hbb : 0 < b * b := Int.mul_pos_of_neg_of_neg hb0 hb0
have hcpos : 0 < c := by
rcases (show c = 0 ∨ 0 < c by omega) with h0 | h0
· subst h0; simp at he; omega
· exact h0
refine ⟨-b, c, by omega, hcpos, ?_⟩
rw [bq_vertex, he, Int.sub_self, Int.mul_zero]
· exact ⟨1, 1, by decide, by decide, by decide⟩
/-- **No vertical tangent.** `x' > 0` on all of `[0, 1]` iff `Δ₀ > 0`,
`Δ₂ > 0` and (`Δ₁ ≥ 0` or `Δ₁² < Δ₀Δ₂`). -/
theorem bq_pos_iff (a b c : Int) :
(∀ α β : Int, 0 ≤ α → 0 ≤ β → 0 < α + β → 0 < bq a b c α β) ↔
(0 < a ∧ 0 < c ∧ (0 ≤ b ∨ b * b < a * c)) := by
constructor
· intro h
have ha : 0 < a := by have := h 0 1 (by decide) (by decide) (by decide); unfold bq at this; omega
have hc : 0 < c := by have := h 1 0 (by decide) (by decide) (by decide); unfold bq at this; omega
refine ⟨ha, hc, ?_⟩
rcases (show 0 ≤ b ∨ b < 0 by omega) with hb | hb
· exact Or.inl hb
· right
have h1 := h (-b) c (by omega) (by omega) (by omega)
rw [bq_vertex] at h1
rcases (show (a * c) ≤ (b * b) ∨ (b * b) < (a * c) by omega) with hh | hh
· have : c * (a * c - b * b) ≤ 0 :=
Int.mul_nonpos_of_nonneg_of_nonpos (by omega) (by omega)
omega
· exact hh
· rintro ⟨ha, hc, hb⟩ α β hp hq hpq
have hk := bq_key a b c α β
have hs := sq_nonneg' (a * β + b * α)
rcases (show α = 0 ∨ 0 < α by omega) with hp0 | hp0
· subst hp0
have : 0 < a * β * β := Int.mul_pos (Int.mul_pos ha (by omega)) (by omega)
unfold bq; poly_int
· rcases hb with hb | hb
· have h1 : 0 ≤ a * β * β := Int.mul_nonneg (Int.mul_nonneg (by omega) hq) hq
have h2 : 0 ≤ b * α * β := Int.mul_nonneg (Int.mul_nonneg hb hp) hq
have h3 : 0 < c * α * α := Int.mul_pos (Int.mul_pos hc hp0) hp0
unfold bq; poly_int
· have hr : 0 < (a * c - b * b) * (α * α) :=
Int.mul_pos (by omega) (Int.mul_pos hp0 hp0)
rcases (show (bq a b c α β) ≤ 0 ∨ 0 < (bq a b c α β) by omega) with h0 | h0
· have : a * bq a b c α β ≤ 0 := Int.mul_nonpos_of_nonneg_of_nonpos (by omega) h0
omega
· exact h0
A family of floor curves
The simplest choice is evenly spaced x-controls . Then , and , so and the curve is the graph of its y-coordinate. With y-controls :
The floor curve. Take (the floor reaches one unit of collateral at full supply), initial slope , and quadratic coefficient , so and :
-- continues the definitions above
/-! ## A family of floor curves -/
/-- Evenly spaced x-controls `0, 1/3, 2/3, 1` (scaled by 3) give `x(t) = t`. -/
theorem even_x (t : Int) : bez3 0 1 2 3 t = 3 * t ∧ bezD 0 1 2 3 t = 3 := by
constructor
· unfold bez3; poly_int
· unfold bezD; poly_int
/-- With `x(t) = t`, y-controls `0, y₁, y₂, y₃` give the cubic
`3y₁u + (3y₂ − 6y₁)u² + (y₃ + 3y₁ − 3y₂)u³`. -/
theorem graph_family (y1 y2 y3 u : Int) :
bez3 0 y1 y2 y3 u =
3 * y1 * u + (3 * y2 - 6 * y1) * u * u + (y3 + 3 * y1 - 3 * y2) * u * u * u := by
unfold bez3; poly_int
/-- The member `y = 0, 7/30, 7/10, 1` (scaled by 30):
`30 · p(u) = 21u + 21u² − 12u³`, i.e. `p(u) = 0.7u + 0.7u² − 0.4u³`. -/
theorem floor_curve (u : Int) : bez3 0 7 21 30 u = 21 * u + 21 * u * u - 12 * u * u * u := by
unfold bez3; poly_int
/-- `p(0) = 0`, `p(1) = 1`, `p'(0) = 0.7`, `p'(1) = 0.9` (all scaled by 30). -/
example : bez3 0 7 21 30 0 = 0 ∧ bez3 0 7 21 30 1 = 30 ∧
bezD 0 7 21 30 0 = 21 ∧ bezD 0 7 21 30 1 = 27 := by decide
Theorem 9 (shape of the floor curve). For every rational :
- for ;
- is increasing on ;
- on , and for every , with equality at ;
- the reserve has slope with on .
Proof. Write and clear denominators. The bounds on are polynomial inequalities in natural numbers; after substituting , or multiplying by a monomial once, every coefficient of the difference is nonnegative. For the upper slope bound, . ∎
By (4), issuing never becomes free once supply is positive: for every the marginal collateral is at least . Near it tends to , so the earliest issuance is nearly free. In the other direction, each unit of collateral always admits at least new tokens, so there is no stall anywhere.
-- continues the definitions above
/-! ### Bounds for every rational `u = a / b` -/
/-- `p(u) > 0` for `0 < u ≤ 1` (times `100 b³`). -/
theorem p_pos (a b : Nat) (ha : 0 < a) (hab : a ≤ b) :
40 * a * a * a < 70 * a * b * b + 70 * a * a * b := by
obtain ⟨y, rfl⟩ := Nat.exists_eq_add_of_le hab
have : 0 < a * a * a := Nat.mul_pos (Nat.mul_pos ha ha) ha
poly_nat
/-- `p` is increasing on `[0, 1]`: `a ≤ b ≤ N` gives `p(a/N) ≤ p(b/N)`. -/
theorem p_mono (a b N : Nat) (hab : a ≤ b) (hbN : b ≤ N) :
70 * a * N * N + 70 * a * a * N + 40 * b * b * b ≤
70 * b * N * N + 70 * b * b * N + 40 * a * a * a := by
obtain ⟨d, rfl⟩ := Nat.exists_eq_add_of_le hab
obtain ⟨e, rfl⟩ := Nat.exists_eq_add_of_le hbN
poly_nat
/-- `p'(u) = 0.7 + 1.4u − 1.2u² ≥ 0.7` on `[0, 1]`: `1.2u² ≤ 1.4u`. -/
theorem p_slope_lower (a b : Nat) (hab : a ≤ b) : 120 * a * a ≤ 140 * a * b := by
have := Nat.mul_le_mul_left (a) hab
poly_nat
/-- `p'(u) ≤ 133/120` for every rational `u`: `1.68u ≤ 0.49 + 1.44u²`,
that is `(12u − 7)² ≥ 0`. -/
theorem p_slope_upper (a b : Int) : 168 * a * b ≤ 49 * b * b + 144 * a * a := by
have h1 := sq_nonneg' (12 * a - 7 * b)
poly_int
/-- The bound is attained at `u = 7/12`. -/
example : 168 * 7 * 12 = 49 * 12 * 12 + 144 * 7 * 7 := by decide
/-- The reserve `R(u) = u · p(u)` has slope `1.4u + 2.1u² − 1.6u³ ≥ 1.4u` on `[0, 1]`. -/
theorem reserve_slope_lower (a b : Nat) (hab : a ≤ b) :
160 * a * a * a ≤ 210 * a * a * b := by
have := Nat.mul_le_mul_left (a * a) hab
poly_nat
/-- ... and at most `1.9` on `[0, 1]`. -/
theorem reserve_slope_upper (a b : Nat) (hab : a ≤ b) :
140 * a * b * b + 210 * a * a * b ≤ 190 * b * b * b + 160 * a * a * a := by
obtain ⟨y, rfl⟩ := Nat.exists_eq_add_of_le hab
poly_nat
For an exact integer floor with supply ceiling , take in millionths, rounded up, and hold it at beyond . Rounding up keeps the certified floor at or above the real curve and within of it. Monotonicity transfers from Theorem 9, so Theorem 3 applies to this exact function, with or without a dollar safety factor.
-- continues the definitions above
/-! ### An exact integer floor on supply `0 … N` -/
/-- `100 N³ · p(x/N)`. -/
def floorNum (N x : Nat) : Nat := 70 * x * N * N + 70 * x * x * N - 40 * x * x * x
/-- `p(c/N)` in millionths, rounded up, held at `1` beyond `N`. -/
def floorMicro (N c : Nat) : Nat :=
let x := min c N
(10000 * floorNum N x + N * N * N - 1) / (N * N * N)
theorem floorNum_mono (N x y : Nat) (hxy : x ≤ y) (hyN : y ≤ N) :
floorNum N x ≤ floorNum N y := by
unfold floorNum
have h1 := p_mono x y N hxy hyN
have h2 : 40 * y * y * y ≤ 70 * y * y * N := by
have := Nat.mul_le_mul_left (y * y) hyN
poly_nat
have h3 : 40 * x * x * x ≤ 70 * x * x * N := by
have := Nat.mul_le_mul_left (x * x) (Nat.le_trans hxy hyN)
poly_nat
omega
theorem floorMicro_mono (N : Nat) : Mono (floorMicro N) := by
intro a b hab
unfold floorMicro
apply div_mono
have := floorNum_mono N (min a N) (min b N) (by omega) (Nat.min_le_right _ _)
have := Nat.mul_le_mul_left 10000 this
omega
#eval (List.range 11).map (fun i => floorMicro 1000 (100 * i))
-- [0, 76600, 164800, 262200, 366400, 475000, 585600, 695800, 803200, 905400, 1000000]
/-- The master invariant for this floor, any `N`, scale and exit fee. -/
theorem curve_floor (N S s : Nat) (ops : List Op) (st : State)
(h : Floor (floorMicro N) S st) :
Floor (floorMicro N) S (run (floorMicro N) S s st ops) :=
run_floor _ (floorMicro_mono N) S s ops st h
/-- The same with a safety factor `κ = kn / kd` at collateral price `v`. -/
theorem curve_dollar_cap (N kn kd v s : Nat) (ops : List Op) (st : State)
(h : Floor (fun c => kn * floorMicro N c) (kd * v) st) :
Floor (fun c => kn * floorMicro N c) (kd * v)
(run (fun c => kn * floorMicro N c) (kd * v) s st ops) :=
run_floor _ (fun a b hab => Nat.mul_le_mul_left kn (floorMicro_mono N a b hab)) _ s ops st h
With and collateral at one dollar, the supply cap at treasury is the largest with . Each figure below is computed by #eval and comes with a certificate: satisfies the cap and does not.
| treasury | cap, | cap, |
|---|---|---|
| $1M | 37,127,793 | 33,267,189 |
| $10M | 113,637,654 | 102,108,002 |
| $100M | 335,253,216 | 302,356,871 |
| $500M | 708,808,733 | 637,667,648 |
The safety factor costs about 10 % of the cap at every treasury level in this range. In return, Theorem 6 lets the floor promise survive a 20 % drawdown.
-- continues the definitions above
/-! ### Supply caps -/
/-- Largest `c` in `[lo, hi]` with `ok c`, for monotone `ok` with `ok lo`. -/
def bsearch (ok : Nat → Bool) : Nat → Nat → Nat → Nat
| 0, lo, _ => lo
| fuel + 1, lo, hi =>
if hi ≤ lo then lo
else
let mid := (lo + hi + 1) / 2
if ok mid then bsearch ok fuel mid hi else bsearch ok fuel lo (mid - 1)
def Nsup : Nat := 1000000000
/-- Within the cap: `κ · c · p(c/N) ≤ T` dollars, collateral at `$1`. -/
def within (kn kd T c : Nat) : Bool := kn * (c * floorMicro Nsup c) ≤ kd * T * 1000000
/-- The supply cap at treasury `T` dollars, `κ = kn / kd`. -/
def cap (kn kd T : Nat) : Nat := bsearch (within kn kd T) 64 0 Nsup
/-- Caps with a certificate: `c` is within, `c + 1` is not. -/
def capChecked (kn kd T : Nat) : Nat × Bool :=
let c := cap kn kd T
(c, within kn kd T c && !within kn kd T (c + 1))
#eval [1000000, 10000000, 100000000, 500000000].map (capChecked 1 1)
#eval [1000000, 10000000, 100000000, 500000000].map (capChecked 5 4)
Rewards as a fixed-rate rebate
Rewards for activity can be paid without any new rule. A payer of a fee receives tokens bought with the share of the fee, where , in an ordinary accretive sale. The rest of the fee joins the queue. If the sale would be rejected, the whole fee joins the queue instead, so no collateral that was paid in is lost: in both cases grows by exactly . The rate is the same for every payer and does not depend on what others pay, so there is nothing to compete for. Because a rebate expands to ordinary non-genesis operations, Theorems 3 and 4 cover it in any interleaving.
Self-dealing means generating a fee only to collect its rebate: the service the fee pays for is worth nothing to the payer, who then redeems the rebate tokens.
Theorem 10 (self-dealing loss). Pay a fee , receive the rebate tokens in an accepted sale, let one period’s release happen, and redeem the tokens. The amount returned satisfies , so the round trip, counted on the rebate tokens alone, loses at least .
Proof. This is Theorem 5 with the sale paid by the share and the remainder as the incoming fee. Then . ∎
The bound concerns the rebate tokens, over one release. It is not a statement about the payer’s whole position. The remainder stays in the queue and is released to whoever holds, so a payer who already holds a share of the supply receives roughly of it back over the following periods, and the net loss is roughly . Self-dealing is expensive for small holders and nearly free for a holder of almost the whole supply, who is in effect paying fees to themself. Holding the rebate tokens through more releases is covered by Theorem 5′.
-- continues the definitions above
/-! ## A fixed-rate rebate -/
/-- A fee `f`: if the sale is accepted, the share `a = ⌊f · ρn / ρd⌋` buys `g`
tokens and the rest joins the queue; otherwise the whole fee joins the queue. -/
def rebate (p : Nat → Nat) (S ρn ρd f g : Nat) (st : State) : List Op :=
if 0 < st.C ∧ (st.T + st.Q) * g ≤ (f * ρn / ρd) * (st.C + st.G) ∧
(st.C + g) * p (st.C + g) ≤ (st.T + f * ρn / ρd) * S
then [.mint (f * ρn / ρd) g, .fee (f - f * ρn / ρd)] else [.fee f]
/-- A rebate expands to ordinary operations, so both invariants cover it. -/
example (p : Nat → Nat) (S ρn ρd f g : Nat) (st : State) :
(rebate p S ρn ρd f g st).all Op.accretive = true := by
unfold rebate; split <;> rfl
theorem rebate_share (ρn ρd f : Nat) : f * ρn / ρd * ρd ≤ f * ρn :=
Nat.div_mul_le_self _ _
/-- No collateral is lost: `T + Q` grows by exactly `f`, accepted or not. -/
theorem rebate_conserves (p : Nat → Nat) (S s ρn ρd f g : Nat) (st : State)
(hρ : ρn ≤ ρd) :
let st' := run p S s st (rebate p S ρn ρd f g st)
st'.T + st'.Q = st.T + st.Q + f := by
have ha : f * ρn / ρd ≤ f :=
Nat.div_le_of_le_mul (by rw [Nat.mul_comm ρd]; exact Nat.mul_le_mul_left f hρ)
unfold rebate
split
· rename_i hg
simp only [run, List.foldl, step, if_pos hg]
omega
· simp only [run, List.foldl, step]
omega
/-- **Self-dealing loss bound.** Pay a fee `f`, receive the `g` rebate tokens
in an accepted sale, let one period's release happen and redeem the `g` tokens:
the exit value `X` satisfies `X · ρd ≤ f · ρn`. -/
theorem self_dealing_loses (p : Nat → Nat) (S s : Nat) (st : State) (ρn ρd f g : Nat)
(hs : s ≤ D)
(hg : 0 < st.C ∧ (st.T + st.Q) * g ≤ (f * ρn / ρd) * (st.C + st.G) ∧
(st.C + g) * p (st.C + g) ≤ (st.T + f * ρn / ρd) * S) :
let st' := run p S s st (rebate p S ρn ρd f g st ++ [.vest])
exitPay s st'.T (st'.C + st'.G) g * ρd ≤ f * ρn := by
have e : rebate p S ρn ρd f g st ++ [.vest] =
[.mint (f * ρn / ρd) g, .fee (f - f * ρn / ρd), .vest] := by
unfold rebate; rw [if_pos hg]; rfl
rw [e]
exact Nat.le_trans (Nat.mul_le_mul_right ρd
(no_sandwich p S s st (f * ρn / ρd) g (f - f * ρn / ρd) hs hg))
(rebate_share ρn ρd f)
Why a proportional contest for a fixed prize cannot clear at backing
The alternative is to fix a prize per period and split it in proportion to the fees paid. That is a Tullock contest. A bidder who spends while the others spend in total receives
Contests of this kind are developed in Efficient Rent Seeking (in Toward a Theory of the Rent-Seeking Society, Texas A&M University Press, 1980) and surveyed in Strategy and Dynamics in Contests (Oxford University Press, 2009). This payoff carries the standard modelling assumptions, which the results below inherit: bidders are risk-neutral, all of them value the prize at the same amount , and a fee is paid only to win a share of the prize, with no value of its own to the payer. All quantities are integers, as everywhere in this article.
Theorem 11 (best response and equilibrium). Let and let be an integer with .
- For every with , .
- If (equivalently ), then is a feasible spend, so it is a best response.
- If (equivalently ), then for every , so spending nothing is a best response.
With , symmetric bidders and , is a mutual best response, and the total spend is
Proof. (1) With , , and because . Cross-multiplied, the difference of the two sides is . (3) From , , so and . For the symmetric case, and satisfy and , and makes . ∎
With a single bidder (, ) and real-valued spends there is no best response: any spend wins the whole prize, and a smaller one does better. With integer spends, as in this article, the smallest positive spend is the best response once . Theorem 11 shows that the symmetric profile is an equilibrium; uniqueness of the equilibrium is shown in On the existence and uniqueness of pure Nash equilibrium in rent-seeking games (Games and Economic Behavior, 1997) and is not formalised here. The next theorem uses only the total spend at the symmetric equilibrium.
Theorem 12 (a contest cannot clear at backing). Suppose the prize is tokens valued at no more than backing, , and the total spend is the symmetric equilibrium spend, with . Then whenever . The spend is below the backing value of the prize, so an accretive sale guard rejects it. When the sale is priced exactly at backing, the contest clears exactly when the prize is worth at least times backing, : twice backing for two bidders.
Proof. . ∎
The sale guard of the machine checks the price against , which is at least the backing. Suppose bidders value the prize at no more than the price at which the same tokens can be bought by an accretive sale, . Theorem 12, applied with in place of , shows that the equilibrium spend fails the guard . Under the assumptions above, a fixed prize sold through a proportional contest is therefore rejected by the guard, unless bidders value it above the price of an accretive sale. The fixed-rate rebate has neither problem, because each payer’s reward is a fixed fraction of what that payer brought in.
-- continues the definitions above
/-! ## Proportional contests for a fixed prize -/
/-- **Best response.** Against total rival spend `Y`, with `w ≥ 0` and
`w² = R·Y`, for every spend `x`: `R·x/(x+Y) − x ≤ R·(w−Y)/w − (w−Y)`,
cross-multiplied by `w (x + Y)`. -/
theorem tullock_best_response (R Y w x : Int) (hw : 0 ≤ w) (hsq : w * w = R * Y) :
w * (R * x - x * (x + Y)) ≤ (x + Y) * (R * (w - Y) - (w - Y) * w) := by
have h1 := congrArg (· * (x + Y)) hsq
have h2 := congrArg (· * w) hsq
have h3 := Int.mul_nonneg hw (sq_nonneg' (w - (x + Y)))
simp only at h1 h2
poly_int
/-- **Corner.** If `w ≤ Y` then every spend `x ≥ 0` earns at most `0`, the
payoff of spending nothing: `R·x ≤ x·(x + Y)`. -/
theorem tullock_corner (R Y w x : Int) (hw : 0 ≤ w) (hY : 0 < Y) (hwY : w ≤ Y)
(hsq : w * w = R * Y) (hx : 0 ≤ x) : R * x ≤ x * (x + Y) := by
have h1 : w * w ≤ Y * Y := Int.mul_le_mul hwY hwY hw (by omega)
have h2 : R * Y ≤ Y * Y := by rw [← hsq]; exact h1
have h3 : R ≤ Y := Int.le_of_mul_le_mul_right h2 hY
have h4 : x * R ≤ x * (x + Y) := Int.mul_le_mul_of_nonneg_left (by omega) hx
rw [Int.mul_comm R x]; exact h4
/-- **Symmetric equilibrium.** If `x · n² = R (n − 1)`, then with rivals
spending `Y = (n − 1) x` the value `w = n x` satisfies `w² = R Y`, so `x = w − Y`
is a best response. -/
theorem tullock_symmetric (R n x : Int) (h : x * n * n = R * (n - 1)) :
(n * x) * (n * x) = R * ((n - 1) * x) := by
have h1 := congrArg (· * x) h
simp only at h1
poly_int
/-- In the symmetric profile the rivals' spend is at most `w`, so `w − Y` is
feasible. -/
theorem tullock_symmetric_feasible (n x : Int) (hx : 0 ≤ x) : (n - 1) * x ≤ n * x := by
have : (n - 1) * x = n * x - x := by rw [Int.sub_mul, Int.one_mul]
omega
/-- Total equilibrium spend `X = R (n − 1) / n` is below the prize. -/
theorem contest_spend_lt_prize (R n X : Nat) (hn : 0 < n) (hR : 0 < R)
(hX : X * n = R * (n - 1)) : X < R := by
obtain ⟨k, rfl⟩ : ∃ k, n = k + 1 := ⟨n - 1, by omega⟩
simp only [Nat.add_sub_cancel] at hX
rcases Nat.lt_or_ge X R with h | h
· exact h
· have := Nat.mul_le_mul_right (k + 1) h
poly_nat
/-- **A contest cannot clear at backing.** Value the prize of `m` tokens at no
more than backing (`R · F ≤ T · m`); total spend `X · n = R (n − 1)` fails the
accretive guard `T · m ≤ X · F`. -/
theorem contest_underprices (R n X T m F : Nat) (hn : 0 < n) (hpos : 0 < T * m)
(hR : R * F ≤ T * m) (hX : X * n = R * (n - 1)) :
¬ (T * m ≤ X * F) := by
intro h
obtain ⟨k, rfl⟩ : ∃ k, n = k + 1 := ⟨n - 1, by omega⟩
simp only [Nat.add_sub_cancel] at hX
have h1 := Nat.mul_le_mul_right (k + 1) h
have h2 : X * (k + 1) * F = R * k * F := by rw [hX]
have h3 : R * F * k ≤ T * m * k := Nat.mul_le_mul_right k hR
poly_nat
/-- At exactly backing, it clears iff the prize is worth `n / (n − 1)` times backing. -/
theorem contest_clears_iff (R n X T m F : Nat) (hn : 0 < n)
(hX : X * n = R * (n - 1)) :
T * m ≤ X * F ↔ T * m * n ≤ R * (n - 1) * F := by
have e : X * F * n = R * (n - 1) * F := by
rw [Nat.mul_right_comm, hX]
constructor
· intro h; rw [← e]; exact Nat.mul_le_mul_right n h
· intro h; rw [← e] at h
rw [Nat.mul_comm (T * m), Nat.mul_comm (X * F)] at h
exact Nat.le_of_mul_le_mul_left h hn
/-- 100 tokens at backing 10 (prize 1000), two bidders, total spend 500:
the sale is rejected. -/
example : let st : State := ⟨1000, 100, 0, 0⟩
run (fun _ => 0) 1 0 st [.mint (1000 * (2 - 1) / 2) 100] = st := by decide
What is proved
- Redemption at the pro-rata share never lowers backing, and with exact division it leaves backing unchanged (Theorem 1).
- For every monotone floor curve, every sequence of operations preserves the floor (Theorem 3).
- Fully diluted backing never decreases under fees, releases, burns, redemptions, accretive sales and grants (Theorem 4).
- Buying before a fee and redeeming after one release never returns more than was paid. Holding through releases returns at most , and for this can exceed (Theorems 5 and 5′).
- A dollar cap with factor protects the floor promise against drawdowns up to , and no further. It never protects dollar exit value (Theorem 6).
- A cubic Bézier curve is a function graph iff its control polygon satisfies and . Its tangent is vertical in the interior exactly when and there (Theorems 7 and 8). The real-analysis steps of Theorem 7 are standard and not formalised.
- The curve is positive and increasing, its slope lies in , and its reserve slope lies in (Theorem 9).
- A fixed-rate rebate never loses collateral, and self-dealing loses at least on the rebate tokens over one release (Theorem 10). With risk-neutral bidders who share a common value and pay fees only for the prize, the symmetric equilibrium of a proportional contest for a fixed prize spends and cannot clear at backing (Theorems 11 and 12). Uniqueness of the contest equilibrium is not formalised here.