Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 3.10, pp. 13–14 — the star supports F\mathcal FF and costs ∑ic(fi)−c(fh)\sum_i c(f_i)-c(f_h)∑i​c(fi​)−c(fh​)

Proved
LNTopology.StarBound.star_supports_cost

by mikedeng1 · Oct 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

lightning-networknetwork-designp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1payment-channels

Let VVV be a finite set of nodes, ccc a channel cost function satisfying (MO), (SY), (CI) and (SA), and F=(fi)i∈V\mathcal F=(f_i)_{i\in V}F=(fi​)i∈V​ a payment flow with

∑i∈Vfi=0.\sum_{i\in V}f_i=0 .i∈V∑​fi​=0.

Then for every hub h∈Vh\in Vh∈V, the star Λh\Lambda^{h}Λh centered at hhh

  1. is a Lightning Network (anti-symmetric),
  2. supports F\mathcal FF, and
  3. has cost
c(Λh)=∑i∈Vc(fi)−c(fh).c(\Lambda^{h})=\sum_{i\in V}c(f_i)-c(f_h).c(Λh)=i∈V∑​c(fi​)−c(fh​).

This is the construction behind the upper bound of Theorem 3.10 and behind Corollary 3.12: choosing a hub with c(fh)=max⁡ic(fi)c(f_h)=\max_i c(f_i)c(fh​)=maxi​c(fi​) gives a supporting network of cost ∑ic(fi)−max⁡ic(fi)\sum_i c(f_i)-\max_i c(f_i)∑i​c(fi​)−maxi​c(fi​).

Formalization Note. The paper fixes the hub with f0=max⁡ifif_0=\max_i f_if0​=maxi​fi​ and then writes c(f0)=max⁡ic(fi)c(f_0)=\max_i c(f_i)c(f0​)=maxi​c(fi​); this fails when the most negative flow has the larger magnitude. The statement here holds for every hub, which is what the paper's computation ∑i=0nc(fi)−c(f0)\sum_{i=0}^n c(f_i)-c(f_0)∑i=0n​c(fi​)−c(f0​) shows; the hub maximizing c(fh)c(f_h)c(fh​) is chosen in Theorem 3.10. The star uses λi,h=fi\lambda_{i,h}=f_iλi,h​=fi​ (the paper writes λ0,i=fi\lambda_{0,i}=f_iλ0,i​=fi​, the opposite sign under the row-sum convention); the cost is the same by (SY). (SA) is in its corrected form, for all x,y>0x,y>0x,y>0.

Preamble
import Mathlib
import Definitions.Def_LNTopology_StarBound_Model
import Definitions.Def_LNTopology_Local_Star
Formal statement
namespace LNTopology.StarBound

/-- Proof of Theorem 3.10, pp. 13–14: when `∑ i, f i = 0`, the LNTopology.Local.star centered at any hub `h`
is a Lightning Network that supports `f`, and its cost is `∑_i c (f i) - c (f h)`. -/
theorem star_supports_cost {V : Type*} [Fintype V] [DecidableEq V] (c : ℝ → ℝ)
    (hc : IsChannelCost c) (f : V → ℝ) (hf : ∑ i, f i = 0) (h : V) :
    IsLN (LNTopology.Local.star f h) ∧ Supports (LNTopology.Local.star f h) f ∧
      cost c (LNTopology.Local.star f h) = ∑ i, c (f i) - c (f h) := by sorry

end LNTopology.StarBound
Source
Guasoni, Huberman & Shikhelman, Lightning Network Economics: Topology, SSRN 4439190 (version of Feb. 3, 2023), pp. 13–14 (PDF 14–15), App. C, proof of Theorem 3.10 (upper bound)
Human review
  • Endorsed by Shuze Chen · Oct 14, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 14, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me