-- Bank fact: intent-a-plan-keeps-the-route-that-delivers-the-most-and-every-step-after-the-swap-is-covered-by-its-floor -- Primary implementation: agent/src/intent.js (floorAt, feeOf, pickBest, the plan's sizing) and -- agent/src/intentroute.js (the router call: the fee at the hub, the floor at the end). -- Machine checked with Lean 4.22.0, core only, no Mathlib (bank/proofs/lean-toolchain). -- Check it: lean Intent.lean (the #print axioms lines list only Lean's standard axioms) /- THE INTENT SOLVER: a person names where their money goes; the solver rehearses every route between the two ends, keeps the one that delivers the most, floors it at the person's own slippage limit, and sizes every step after the swap from that floor. Stated exactly and proved, for every amount: * the floor is never above the quote, and it gives up at most the person's share of it (rounded down, so never more), * the house's fee is never more than its share of what passes through USDG, and the fee and what goes on add up to it, * what goes on after the fee never falls when more comes in, so a better first side never hurts the second, * the choice among rehearsed routes is one that went through, and nothing that went through delivered more; when nothing went through there is no choice, * THE SEPARABLE CHOICE: when every second side gives more for more, the best first side handed to every second side and the best of those is the best of every pair, fee included, * THE PAIRS THAT SHARE A POOL: a first side sells into USDG and a second side buys out of it, so a pool both cross is crossed in opposite directions and the first side only ever helps the second there; with the best first side's own pairs and every pair whose sides share a pool rehearsed whole, whatever bounds those bounds every pair, and a worked case shows such a pair can deliver more than the separable choice, so they are needed, * a step after the swap that spends the floor is always covered once the swap has gone through, and what the swap brings above its floor stays with the person, * a redemption spends only whole USDG units of HUSD and leaves less than one behind; a mint makes exactly one HUSD unit for every 10^-12 of it. -/ namespace Intent /-- The floor under a quote `q` at a slippage limit of `s` basis points, rounded down (intent.js floorAt). -/ def floorAt (q s : Nat) : Nat := q * (10000 - s) / 10000 /-- The house's fee on `h` passing through USDG at `b` basis points, as the router computes a portion (BipsLibrary). -/ def feeOf (h b : Nat) : Nat := h * b / 10000 /-- What goes on to the second side after the fee. -/ def net (h b : Nat) : Nat := h - feeOf h b /-- The most a list delivers, and nothing for an empty one. -/ def maxOf : List Nat → Nat | [] => 0 | x :: xs => max x (maxOf xs) /-- THE CHOICE among rehearsed routes, each a pair (went through, delivered): the most among those that went through, or none (intent.js pickBest; a tie keeps either, the value is the same). -/ def pick : List (Bool × Nat) → Option Nat | [] => none | (ok, v) :: rest => match pick rest with | none => if ok then some v else none | some w => if ok then some (max v w) else some w /-- The value of the best second side when the first side hands it `x`: the most any of them delivers. -/ def bestSecond (fs : List (Nat → Nat)) (x : Nat) : Nat := maxOf (fs.map (fun f => f x)) theorem floor_le_quote (q s : Nat) : floorAt q s ≤ q := by unfold floorAt have h1 : q * (10000 - s) ≤ q * 10000 := Nat.mul_le_mul_left q (Nat.sub_le 10000 s) have h2 : q * (10000 - s) / 10000 ≤ q * 10000 / 10000 := Nat.div_le_div_right h1 rw [Nat.mul_div_cancel q (by decide : 0 < 10000)] at h2 exact h2 /-- The floor gives up at most the person's share of the quote: (q - floor) * 10000 <= q * s + 9999, so rounding never takes a whole unit more than the limit allows. -/ theorem floor_gives_up_at_most_the_limit (q s : Nat) (hs : s ≤ 10000) : (q - floorAt q s) * 10000 ≤ q * s + 9999 := by unfold floorAt have hsplit : q * (10000 - s) + q * s = q * 10000 := by rw [← Nat.mul_add, Nat.sub_add_cancel hs] have hdm := Nat.div_add_mod (q * (10000 - s)) 10000 have hmod := Nat.mod_lt (q * (10000 - s)) (by decide : 10000 > 0) generalize q * (10000 - s) = x at hsplit hdm hmod generalize q * s = y at hsplit generalize x / 10000 = f at hdm generalize x % 10000 = r at hdm hmod rw [Nat.sub_mul] omega theorem fee_within_its_share (h b : Nat) : feeOf h b * 10000 ≤ h * b := Nat.div_mul_le_self _ _ theorem fee_le_what_passes (h b : Nat) (hb : b ≤ 10000) : feeOf h b ≤ h := by unfold feeOf have : h * b ≤ h * 10000 := Nat.mul_le_mul_left h hb have := Nat.div_le_div_right (c := 10000) this rwa [Nat.mul_div_cancel h (by decide : 0 < 10000)] at this theorem fee_and_net_add_up (h b : Nat) (hb : b ≤ 10000) : feeOf h b + net h b = h := by unfold net have := fee_le_what_passes h b hb omega /-- More through the hub never sends less on: a better first side never hurts the second. -/ theorem net_monotone (h₁ h₂ b : Nat) (hb : b ≤ 10000) (hle : h₁ ≤ h₂) : net h₁ b ≤ net h₂ b := by unfold net feeOf -- h - h*b/10000 = ceil(h * (10000 - b) / 10000), written without the ceiling have e1 := Nat.div_add_mod (h₁ * b) 10000 have e2 := Nat.div_add_mod (h₂ * b) 10000 have m1 := Nat.mod_lt (h₁ * b) (by decide : 10000 > 0) have m2 := Nat.mod_lt (h₂ * b) (by decide : 10000 > 0) have g1 : h₁ * b ≤ h₁ * 10000 := Nat.mul_le_mul_left h₁ hb have g2 : h₂ * b ≤ h₂ * 10000 := Nat.mul_le_mul_left h₂ hb -- the step: h₂ * b - h₁ * b ≤ (h₂ - h₁) * 10000, since b ≤ 10000 have step : h₂ * b ≤ h₁ * b + (h₂ - h₁) * 10000 := by have : h₂ * b = h₁ * b + (h₂ - h₁) * b := by rw [← Nat.add_mul, Nat.add_sub_cancel' hle] rw [this] exact Nat.add_le_add_left (Nat.mul_le_mul_left (h₂ - h₁) hb) _ generalize h₁ * b = p₁ at e1 m1 g1 step generalize h₂ * b = p₂ at e2 m2 g2 step generalize p₁ / 10000 = q₁ at e1 generalize p₂ / 10000 = q₂ at e2 generalize p₁ % 10000 = r₁ at e1 m1 generalize p₂ % 10000 = r₂ at e2 m2 rw [Nat.sub_mul] at step omega theorem le_maxOf (x : Nat) (xs : List Nat) (h : x ∈ xs) : x ≤ maxOf xs := by induction xs with | nil => cases h | cons y ys ih => unfold maxOf cases h with | head => exact Nat.le_max_left _ _ | tail _ hm => exact Nat.le_trans (ih hm) (Nat.le_max_right _ _) theorem maxOf_mem (xs : List Nat) (h : xs ≠ []) : maxOf xs ∈ xs := by induction xs with | nil => exact absurd rfl h | cons y ys ih => unfold maxOf cases ys with | nil => simp [maxOf] | cons z zs => have hm := ih (by simp) by_cases hc : y ≤ maxOf (z :: zs) · rw [Nat.max_eq_right hc]; exact List.mem_cons_of_mem _ hm · rw [Nat.max_eq_left (Nat.le_of_lt (Nat.lt_of_not_le hc))]; exact List.mem_cons_self /-- THE CHOICE IS ONE THAT WENT THROUGH: whatever `pick` returns is the delivery of a route that went through. -/ theorem pick_went_through (rs : List (Bool × Nat)) (v : Nat) (h : pick rs = some v) : (true, v) ∈ rs := by induction rs generalizing v with | nil => simp [pick] at h | cons r rest ih => obtain ⟨ok, w⟩ := r unfold pick at h cases hp : pick rest with | none => rw [hp] at h cases ok <;> simp at h subst h; exact List.mem_cons_self | some u => rw [hp] at h cases ok with | false => simp at h; subst h; exact List.mem_cons_of_mem _ (ih u hp) | true => simp at h by_cases hc : w ≤ u · rw [Nat.max_eq_right hc] at h; subst h; exact List.mem_cons_of_mem _ (ih u hp) · rw [Nat.max_eq_left (Nat.le_of_lt (Nat.lt_of_not_le hc))] at h; subst h; exact List.mem_cons_self /-- A ROUTE THAT WENT THROUGH MEANS THERE IS A CHOICE. -/ theorem pick_ne_none_of_mem (rs : List (Bool × Nat)) (w : Nat) (hw : (true, w) ∈ rs) : pick rs ≠ none := by induction rs with | nil => cases hw | cons q qs ihq => obtain ⟨b', y'⟩ := q unfold pick cases hq : pick qs with | none => cases hw with | head => simp | tail _ hw' => exact absurd hq (ihq hw') | some _ => cases b' <;> simp /-- NOTHING WENT THROUGH MEANS THERE IS NO CHOICE. -/ theorem pick_none_of_none_through (rs : List (Bool × Nat)) (h : ∀ w, (true, w) ∉ rs) : pick rs = none := by induction rs with | nil => rfl | cons q qs ihq => obtain ⟨b', y'⟩ := q have hq : pick qs = none := ihq (fun w hw => h w (List.mem_cons_of_mem _ hw)) cases b' with | true => exact absurd List.mem_cons_self (h y') | false => unfold pick; rw [hq]; rfl /-- NOTHING THAT WENT THROUGH DELIVERED MORE than the choice. -/ theorem pick_is_the_most (rs : List (Bool × Nat)) (v : Nat) (h : pick rs = some v) : ∀ w, (true, w) ∈ rs → w ≤ v := by induction rs generalizing v with | nil => simp [pick] at h | cons r rest ih => obtain ⟨ok, x⟩ := r intro w hw unfold pick at h cases hp : pick rest with | none => rw [hp] at h cases ok with | false => simp at h | true => simp at h; subst h cases hw with | head => exact Nat.le_refl _ | tail _ hm => exact absurd hp (pick_ne_none_of_mem rest w hm) | some u => rw [hp] at h have hu := ih u hp cases ok with | false => simp at h; subst h cases hw with | tail _ hm => exact hu w hm | true => simp at h; subst h cases hw with | head => exact Nat.le_max_left _ _ | tail _ hm => exact Nat.le_trans (hu w hm) (Nat.le_max_right _ _) /-- WHEN NOTHING WENT THROUGH THERE IS NO CHOICE, and when something did there is one. -/ theorem pick_none_iff (rs : List (Bool × Nat)) : pick rs = none ↔ ∀ w, (true, w) ∉ rs := ⟨fun h w hw => pick_ne_none_of_mem rs w hw h, pick_none_of_none_through rs⟩ theorem bestSecond_ge (fs : List (Nat → Nat)) (x : Nat) (f : Nat → Nat) (hf : f ∈ fs) : f x ≤ bestSecond fs x := by unfold bestSecond exact le_maxOf (f x) _ (List.mem_map.mpr ⟨f, hf, rfl⟩) /-- THE SEPARABLE CHOICE IS THE BEST OF EVERY PAIR: when every second side gives more for more, handing the best first side to every second side, and keeping the best of those, delivers at least as much as any first side with any second side, the house's fee taken between them. -/ theorem separable_is_best (firsts : List Nat) (fs : List (Nat → Nat)) (b : Nat) (hb : b ≤ 10000) (mono : ∀ f ∈ fs, ∀ x y, x ≤ y → f x ≤ f y) : ∀ a ∈ firsts, ∀ f ∈ fs, f (net a b) ≤ bestSecond fs (net (maxOf firsts) b) := by intro a ha f hf have h1 : a ≤ maxOf firsts := le_maxOf a firsts ha have h2 : net a b ≤ net (maxOf firsts) b := net_monotone a (maxOf firsts) b hb h1 exact Nat.le_trans (mono f hf _ _ h2) (bestSecond_ge fs _ f hf) /-- AND IT IS ONE OF THE PAIRS: the best first side is a first side, so the value claimed is delivered by a real pair. -/ theorem separable_is_a_pair (firsts : List Nat) (fs : List (Nat → Nat)) (b : Nat) (h1 : firsts ≠ []) (h2 : fs ≠ []) : maxOf firsts ∈ firsts ∧ bestSecond fs (net (maxOf firsts) b) ∈ fs.map (fun f => f (net (maxOf firsts) b)) := ⟨maxOf_mem firsts h1, maxOf_mem _ (by simpa using h2)⟩ /-- THE PAIRS THAT SHARE A POOL ARE TRIED WHOLE, AND THEN NO PAIR IS MISSED. First sides `as` deliver `f a` USDG alone; second sides `bs` deliver `g y x` alone when handed `x`, never less for more; `h a y` is what the pair delivers run whole. Pairs whose sides share no pool run apart (`apart`). A first side sells into USDG and a second side buys out of it, so a pool both cross is crossed in opposite directions: what the first side sold there, the second buys back cheaper, and the kept first side never makes a second side deliver less than alone (`helps`). The solver rehearses the best first side `a₀` with every second side and, whole, every other pair whose sides share a pool; whatever bounds all of those (`withBest`, `whole`) bounds every pair. -/ theorem shared_pairs_cover {α β : Type} (as : List α) (bs : List β) (f : α → Nat) (g : β → Nat → Nat) (h : α → β → Nat) (share : α → β → Bool) (b : Nat) (hb : b ≤ 10000) (a₀ : α) (best : ∀ a ∈ as, f a ≤ f a₀) (mono : ∀ y ∈ bs, ∀ x z, x ≤ z → g y x ≤ g y z) (apart : ∀ a, ∀ y ∈ bs, share a y = false → h a y = g y (net (f a) b)) (helps : ∀ y ∈ bs, share a₀ y = true → g y (net (f a₀) b) ≤ h a₀ y) (v : Nat) (withBest : ∀ y ∈ bs, h a₀ y ≤ v) (whole : ∀ a ∈ as, ∀ y ∈ bs, share a y = true → h a y ≤ v) : ∀ a ∈ as, ∀ y ∈ bs, h a y ≤ v := by intro a ha y hy cases hs : share a y with | true => exact whole a ha y hy hs | false => rw [apart a y hy hs] have h1 : net (f a) b ≤ net (f a₀) b := net_monotone _ _ b hb (best a ha) have h2 : g y (net (f a) b) ≤ g y (net (f a₀) b) := mono y hy _ _ h1 have h3 : g y (net (f a₀) b) ≤ h a₀ y := by cases hs0 : share a₀ y with | true => exact helps y hy hs0 | false => rw [apart a₀ y hy hs0]; exact Nat.le_refl _ exact Nat.le_trans h2 (Nat.le_trans h3 (withBest y hy)) /-- AND THEY ARE NEEDED: a worked case, decided. The best first side brings 1,000 USDG and another 999; a second side alone gives half of what it is handed. The other first side's pair shares a pool with that second side and gets 3 back from what its own sale moved there, so it delivers 502 against the 499 of the best first side's pair: the separable choice alone would have missed it. -/ theorem a_shared_pair_can_deliver_more : (net 1000 10) / 2 = 499 ∧ (net 999 10) / 2 + 3 = 502 ∧ (net 999 10) / 2 + 3 > (net 1000 10) / 2 := by decide /-- A STEP AFTER THE SWAP IS COVERED: it spends the floor, and once the swap has gone through the wallet holds at least the floor; what the swap brought above it stays with the person. -/ theorem a_later_step_is_covered (delivered floor spend : Nat) (hswap : floor ≤ delivered) (hspend : spend = floor) : spend ≤ delivered ∧ delivered - spend + spend = delivered := by subst hspend; exact ⟨hswap, Nat.sub_add_cancel hswap⟩ /-- A REDEMPTION SPENDS WHOLE UNITS: of `h` HUSD (18 decimals) it spends a whole number of USDG units (6 decimals) and leaves less than one behind. -/ theorem redemption_spends_whole_units (h : Nat) : h / 1000000000000 * 1000000000000 ≤ h ∧ h - h / 1000000000000 * 1000000000000 < 1000000000000 := by refine ⟨Nat.div_mul_le_self h 1000000000000, ?_⟩ have e : h - h / 1000000000000 * 1000000000000 = h % 1000000000000 := by rw [Nat.mul_comm]; exact Nat.sub_eq_of_eq_add (Nat.mod_add_div h 1000000000000).symm rw [e]; exact Nat.mod_lt h (by decide) /-- A worked example, decided, from the fork of 15 Nov 2026: a sell of 0.280927 NVDA rehearsed at 45.186425 USDG had a floor of 44.960492 at the default 0.5% limit, and the house's 0.1% of the 45.231656 USDG that passed through the hub was 0.045231, the two adding back to it. -/ theorem the_worked_example : floorAt 45186425 50 = 44960492 ∧ feeOf 45231656 10 = 45231 ∧ net 45231656 10 = 45186425 ∧ pick [(true, 44898810), (false, 0), (true, 45186425), (true, 45170213)] = some 45186425 := by decide end Intent #print axioms Intent.floor_le_quote #print axioms Intent.floor_gives_up_at_most_the_limit #print axioms Intent.fee_within_its_share #print axioms Intent.fee_le_what_passes #print axioms Intent.fee_and_net_add_up #print axioms Intent.net_monotone #print axioms Intent.le_maxOf #print axioms Intent.maxOf_mem #print axioms Intent.pick_went_through #print axioms Intent.pick_ne_none_of_mem #print axioms Intent.pick_none_of_none_through #print axioms Intent.pick_is_the_most #print axioms Intent.pick_none_iff #print axioms Intent.bestSecond_ge #print axioms Intent.separable_is_best #print axioms Intent.separable_is_a_pair #print axioms Intent.shared_pairs_cover #print axioms Intent.a_shared_pair_can_deliver_more #print axioms Intent.a_later_step_is_covered #print axioms Intent.redemption_spends_whole_units #print axioms Intent.the_worked_example