Research / 2026

Rotating mailboxes over opportunistic forwarding

Draft · the definitions and theorems on this page are machine-checked in Lean; independent review is in progress.

Signed packets, mailbox ids rotated per epoch by a pseudorandom function of a shared secret, a skew-tolerant polling window and TTL-bounded flooding over contacts, combined so that authentic messages reach their recipient with no server, account or fixed address. Each property is proved for the combination in an idealised symbolic model, with the core statements checked in Lean.

Opportunistic forwardingTemporal graphsSymbolic cryptography
2d + 1
mailbox ids a receiver polls to absorb a clock offset of up to d epoch lengths; with d = 0 an offset of one epoch length is missed
iff
flooding delivers within H hops exactly when a time-respecting journey of at most H hops exists in the TTL window
0 axioms
used by the Lean proof that authenticity holds over every relay path

Two people who share a secret want to exchange messages without a server, without accounts and without either of them having a fixed address. The only means of transport is that devices meet: when two are within range of a short-range link they can pass data, and otherwise they carry it. None of the parts needed for this is new. Signatures, pseudorandom functions, time-stepped codes and epidemic forwarding are all standard. The point of this article is the combination: I state the goal precisely, show how four known components fit together to reach it, and prove that the combination does reach it. Every theorem’s core statement is checked in core Lean 4.16, in an idealised symbolic model whose idealisations I spell out as they appear; the steps from bijections to statements about distributions are argued in prose.

The goal

Setting. A finite set of nodes. A contact u→vu \to v at time tt means that uu can hand data to vv at time tt. Contacts are directed and come from a log. No node is a server and no node has an address that others know. For authenticity no node is trusted to relay correctly. For delivery and findability, relays are assumed to follow the forwarding rule and to pass packets on unchanged. A sender aa and a recipient bb share a secret ss, and bb holds aa‘s public verification key. Each node has a local clock, and the clocks of aa and bb may disagree.

Goal. A message mm from aa to bb should satisfy:

  1. Authenticity. If aa‘s key is not corrupted, bb accepts mm as coming from aa only if aa signed exactly mm, whatever the relays did on the way.
  2. Delivery. When relays forward honestly, mm reaches bb whenever the contact history allows any delivery at all within the lifetime (TTL) and the hop limit, and no later than any other forwarding rule would deliver it.
  3. Findability. Knowing only ss and its own clock, bb can tell which packets are for it, as long as the clocks are close enough.
  4. Unlinkability. The labels relays see on packets reveal nothing about ss, and do not show that two packets of different epochs belong to the same pair.

The four requirements pull in different directions. Delivery wants every node to carry every packet. Findability wants a label that bb can recognise. Unlinkability wants a label that nobody else can recognise and that changes over time. Authenticity has to survive relays that are free to drop, copy, reorder and rewrite.

The components

Each component is known, and I credit each to the work that introduced it or made it standard.

  • Digital signatures. Existential unforgeability under adaptive chosen-message attack (EUF-CMA) is from A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks (SIAM Journal on Computing, 1988). The proofs below use the symbolic attacker model of On the Security of Public Key Protocols (IEEE Transactions on Information Theory, 1983), in which a signature is a term that only the key holder can build.
  • Pseudorandom functions. A keyed function that no efficient observer can tell apart from a random function, from How to Construct Random Functions (Journal of the ACM, 1986).
  • Time-stepped values with a tolerance window. Deriving a value from a shared secret and ⌊t/L⌋\lfloor t / L \rfloor, and accepting neighbouring steps to absorb clock drift, is the scheme of TOTP: Time-Based One-Time Password Algorithm (RFC 6238, 2011).
  • Epidemic, store-carry-forward delivery. Passing a copy at every contact is from Epidemic Routing for Partially-Connected Ad Hoc Networks (technical report, 2000). Bundles with a lifetime that are stored and carried between contacts are from A Delay-Tolerant Network Architecture for Challenged Internets (ACM SIGCOMM, 2003).
  • Time-respecting journeys. Journeys whose contacts occur in time order, and the earliest-arrival (“foremost”) journey among them, are from Computing Shortest, Fastest, and Foremost Journeys in Dynamic Networks (International Journal of Foundations of Computer Science, 2003). The general framework is surveyed in Time-Varying Graphs and Dynamic Networks (International Journal of Parallel, Emergent and Distributed Systems, 2012).

The combination

Fix an epoch length L>0L \gt 0 and write epoch(t)=⌊t/L⌋\mathrm{epoch}(t) = \lfloor t / L \rfloor. Let FF be a pseudorandom function, a tolerance d≥0d \ge 0, a lifetime ttl\mathit{ttl} and a hop limit HH.

  1. Send. At local time tst_s the sender computes the mailbox id Fs(epoch(ts))F_s(\mathrm{epoch}(t_s)), signs the body, and emits the packet ⟨Fs(epoch(ts)), m, Signa(m)⟩\langle F_s(\mathrm{epoch}(t_s)),\ m,\ \mathrm{Sign}_a(m) \rangle with creation time t0t_0. Here t0t_0 is the creation time on the time axis of the contact log, and tst_s is the sender’s own clock reading, which may differ from it.
  2. Forward. At every contact u→vu \to v whose time lies in [t0,t0+ttl][t_0, t_0 + \mathit{ttl}], uu passes a copy of each packet it holds to vv. A node keeps the copy that has travelled the fewest hops.
  3. Poll. At local time trt_r the recipient computes the 2d+12d+1 ids Fs(e)F_s(e) for e∈[epoch(tr)−d, epoch(tr)+d]e \in [\mathrm{epoch}(t_r) - d,\ \mathrm{epoch}(t_r) + d], collects the packets it holds that carry one of them, and accepts those that verify under aa‘s key.

Each component answers one requirement. The signature gives authenticity, flooding gives delivery, the window gives findability, and the pseudorandom function gives unlinkability. The theorems below show that the answers do not interfere. Authenticity holds however the packet travelled. Delivery holds whatever label the packet carries. The label the sender writes is among those the recipient polls. Rotating the label hides the secret without breaking any of the other three properties.

The rest of the article is one Lean file, split into blocks in reading order. All blocks together compile with core Lean 4.16, with no imports and no sorry, admit or added axioms.

Authenticity over any path

Symbolic signatures and traces. A signature is the term ⟨a,m⟩\langle a, m \rangle, read “agent aa signed body mm”. A packet is ⟨box,body,σ⟩\langle \mathit{box}, \mathit{body}, \sigma \rangle. A packet verifies under aa when σ=⟨a,body⟩\sigma = \langle a, \mathit{body} \rangle. The adversary is described by which signatures it can derive after seeing a list of packets: a signature honestly issued, a replay of a signature already seen, or any signature under a corrupted key. A trace is every packet any relay has ever emitted, newest first, where each emitted signature must be derivable from what came before. Box and body are unconstrained, so a trace allows any dropping, copying, reordering, replaying or relabelling.

Assumption (EUF-CMA, idealised). The computational property is that no efficient adversary produces a valid signature under an honest key on a body the key holder never signed. The model replaces it by the symbolic rule above: the only signatures under an honest key are those issued or replayed. Nothing below is a computational proof.

/-
  Rotating mailboxes over opportunistic forwarding.
  Core Lean 4.16, no imports beyond the prelude.
-/

namespace RM

/-! ## 1. Symbolic signatures: authenticity independent of the path -/

abbrev Agent := Nat
abbrev Body  := Nat

/-- A symbolic signature: the term `⟨a, m⟩` stands for "agent `a` signed body `m`". -/
structure Sig where
  signer : Agent
  body   : Body
deriving DecidableEq

/-- A packet: mailbox id, body, signature. -/
structure Packet where
  box  : Nat
  body : Body
  sig  : Sig
deriving DecidableEq

/-- Verification under the public key of `a`: a function of the packet alone. -/
def Verifies (a : Agent) (p : Packet) : Prop := p.sig = ⟨a, p.body⟩

/-- Signatures a relay can put on a packet, given the packets it has seen:
    those honestly issued, replays of seen ones, and anything signed with a
    corrupted key. This is the symbolic idealisation of EUF-CMA. -/
inductive Derivable (issued : Sig → Prop) (corrupt : Agent → Prop)
    (seen : List Packet) : Sig → Prop
  | issue {σ : Sig} : issued σ → Derivable issued corrupt seen σ
  | replay {p : Packet} : p ∈ seen → Derivable issued corrupt seen p.sig
  | forge (a : Agent) (m : Body) : corrupt a → Derivable issued corrupt seen ⟨a, m⟩

/-- Every packet any relay ever emits, newest first. A relay may choose box and
    body freely and may drop, reorder or duplicate; only the signature is
    constrained. Any forwarding path is a sub-history of some trace. -/
inductive Trace (issued : Sig → Prop) (corrupt : Agent → Prop) : List Packet → Prop
  | nil : Trace issued corrupt []
  | emit {t : List Packet} {p : Packet} :
      Trace issued corrupt t → Derivable issued corrupt t p.sig →
      Trace issued corrupt (p :: t)

Theorem 1 (authenticity, independent of the path). Let tt be a trace, p∈tp \in t, and aa an uncorrupted agent. If pp verifies under aa, then aa issued the signature ⟨a,p.body⟩\langle a, p.\mathit{body} \rangle. Conversely, if aa issued ⟨a,m⟩\langle a, m \rangle, then after any trace a packet with body mm and any mailbox id can be emitted, and it verifies under aa. Any packet in a trace can be re-emitted.

Proof. By induction on the trace, every signature in it is derivable from the empty history, because a replay only points back to an earlier packet whose signature was derivable. A signature derivable from nothing, with an uncorrupted signer, cannot be a replay or a forgery, so it was issued. Verification rewrites p.σp.\sigma to ⟨a,p.body⟩\langle a, p.\mathit{body} \rangle. The converse is one emit step. ∎

Verification is a function of the packet alone, and the theorem quantifies over every trace, which is every possible behaviour of the relays. So it does not matter which path a packet took, how often it was copied, or what mailbox id it now carries. Lean reports that authenticity depends on no axioms at all.

theorem derivable_lift {issued corrupt} {t : List Packet} {σ : Sig}
    (hd : Derivable issued corrupt t σ)
    (ih : ∀ p ∈ t, Derivable issued corrupt [] p.sig) :
    Derivable issued corrupt [] σ := by
  cases hd with
  | issue h => exact .issue h
  | replay h => exact ih _ h
  | forge a m h => exact .forge a m h

theorem derivable_nil {issued corrupt} :
    ∀ {t : List Packet}, Trace issued corrupt t →
      ∀ p ∈ t, Derivable issued corrupt [] p.sig := by
  intro t ht
  induction ht with
  | nil => intro p hp; cases hp
  | @emit t p _ hd ih =>
    intro q hq
    cases hq with
    | head => exact derivable_lift hd ih
    | tail _ h => exact ih q h

theorem derivable_honest {issued corrupt} {σ : Sig} {a : Agent}
    (hd : Derivable issued corrupt [] σ) (hs : σ.signer = a) (ha : ¬ corrupt a) :
    issued σ := by
  cases hd with
  | issue h => exact h
  | replay h => cases h
  | forge b m h => simp at hs; subst hs; exact absurd h ha

/-- Theorem 1 (safety). Whatever path a packet took, if it verifies under an
    honest sender's key then that sender issued exactly this body. -/
theorem authenticity {issued corrupt} {t : List Packet} {p : Packet} {a : Agent}
    (ht : Trace issued corrupt t) (hp : p ∈ t) (ha : ¬ corrupt a)
    (hv : Verifies a p) : issued ⟨a, p.body⟩ := by
  have hd := derivable_nil ht p hp
  unfold Verifies at hv
  rw [hv] at hd
  exact derivable_honest hd rfl ha

/-- Theorem 1 (liveness). An issued signature can be emitted after any history,
    under any mailbox id, and verifies. -/
theorem issued_deliverable {issued corrupt} {t : List Packet} {a : Agent} {m : Body}
    (ht : Trace issued corrupt t) (hi : issued ⟨a, m⟩) (b : Nat) :
    Trace issued corrupt (⟨b, m, ⟨a, m⟩⟩ :: t) ∧ Verifies a ⟨b, m, ⟨a, m⟩⟩ :=
  ⟨.emit ht (.issue hi), rfl⟩

/-- Honest relaying: any packet already in the trace may be re-emitted. -/
theorem relay {issued corrupt} {t : List Packet} {p : Packet}
    (ht : Trace issued corrupt t) (hp : p ∈ t) : Trace issued corrupt (p :: t) :=
  .emit ht (.replay hp)

The signature covers the body and not the mailbox id, so a relay can move a signed body to another mailbox. If the recipient or the epoch must be bound to the message, the sender puts them in the body. Theorem 1 then says that aa issued exactly that body, including those fields.

Delivery and earliest arrival

Contact log and journeys. A log is a list of contacts, most recent first, sorted by time, with ties among simultaneous contacts broken by their position in the list. A journey from src\mathit{src} to ww with kk hops in a log hh is defined inductively: src\mathit{src} is reached with 00 hops in any log; a journey in hh is still one in c::hc :: h (waiting); and if c=u→vc = u \to v is usable and uu is reached with kk hops in hh, then vv is reached with k+1k+1 hops in c::hc :: h. A hop can only extend a journey through the older part of the log, so every journey is time-respecting.

The order of a journey comes from the log order. The timestamps on contacts are used only by the usability predicate ok, which is where the lifetime enters.

/-! ## 2. Contacts, journeys and flooding -/

/-- A directed contact `u → v` at time `t`. -/
structure Contact where
  u : Nat
  v : Nat
  t : Nat

/-- A contact log, most recent contact first (the reverse of time order). -/
abbrev Log := List Contact

/-- `Journey ok src h w k`: a journey from `src` to `w` using exactly `k`
    contacts, all usable (`ok`), taken in log order. -/
inductive Journey (ok : Contact → Bool) (src : Nat) : Log → Nat → Nat → Prop
  | here (h : Log) : Journey ok src h src 0
  | wait {h : Log} {w k : Nat} (c : Contact) :
      Journey ok src h w k → Journey ok src (c :: h) w k
  | hop {h : Log} {k : Nat} (c : Contact) :
      ok c = true → Journey ok src h c.u k → Journey ok src (c :: h) c.v (k + 1)

Flooding. The state after log hh maps each node to none or to some k, the fewest hops of any copy it holds. Initially only src\mathit{src} holds a copy, with 00 hops. At a usable contact u→vu \to v, vv keeps the minimum of its own count and uu‘s count plus one.

def merge : Option Nat → Option Nat → Option Nat
  | none,   b      => b
  | some a, none   => some a
  | some a, some b => some (min a b)

/-- One flooding step: at a usable contact, `v` keeps the fewest-hop copy. -/
def step (ok : Contact → Bool) (c : Contact) (s : Nat → Option Nat) : Nat → Option Nat :=
  fun w => if ok c = true ∧ w = c.v then merge (s w) ((s c.u).map (· + 1)) else s w

/-- Flooding state: `some k` = holds a copy that travelled `k` hops. -/
def flood (ok : Contact → Bool) (src : Nat) : Log → Nat → Option Nat
  | []     => fun w => if w = src then some 0 else none
  | c :: h => step ok c (flood ok src h)

Theorem 2a (delivery). For every usable predicate ok, source, destination, hop limit HH and log hh: flooding holds a copy at dst\mathit{dst} with at most HH hops if and only if a journey from src\mathit{src} to dst\mathit{dst} with at most HH hops exists in hh.

Theorem 2b (fewest hops). If flooding records kk hops at ww, then a kk-hop journey to ww exists and every journey to ww has at least kk hops.

Proof. Soundness is induction on the log: a recorded count either was already there (a wait) or came from uu‘s count plus one (a hop). Completeness is induction on the journey, using that counts never grow once set (persist) and that the source always holds a copy with 00 hops. Minimality combines the two. ∎

theorem merge_some {a b : Option Nat} {k : Nat} (h : merge a b = some k) :
    a = some k ∨ b = some k := by
  match a, b with
  | none, b => exact Or.inr h
  | some x, none => exact Or.inl h
  | some x, some y =>
    simp [merge] at h
    rw [← h]
    by_cases hxy : x ≤ y
    · left; simp [Nat.min_eq_left hxy]
    · right; simp [Nat.min_eq_right (Nat.le_of_lt (Nat.lt_of_not_le hxy))]

theorem merge_left {a b : Option Nat} {x : Nat} (h : a = some x) :
    ∃ y, merge a b = some y ∧ y ≤ x := by
  subst h
  cases b with
  | none => exact ⟨x, rfl, Nat.le_refl _⟩
  | some z => exact ⟨min x z, rfl, Nat.min_le_left _ _⟩

theorem merge_right {a b : Option Nat} {x : Nat} (h : b = some x) :
    ∃ y, merge a b = some y ∧ y ≤ x := by
  subst h
  cases a with
  | none => exact ⟨x, rfl, Nat.le_refl _⟩
  | some z => exact ⟨min z x, rfl, Nat.min_le_right _ _⟩

/-- Copies persist and hop counts never grow. -/
theorem persist {ok src} {h : Log} (c : Contact) {w x : Nat}
    (hx : flood ok src h w = some x) :
    ∃ y, flood ok src (c :: h) w = some y ∧ y ≤ x := by
  show ∃ y, step ok c (flood ok src h) w = some y ∧ y ≤ x
  unfold step
  by_cases hc : ok c = true ∧ w = c.v
  · rw [if_pos hc]; exact merge_left hx
  · rw [if_neg hc]; exact ⟨x, hx, Nat.le_refl _⟩

theorem flood_src (ok src) : ∀ h : Log, ∃ k, flood ok src h src = some k ∧ k ≤ 0
  | [] => ⟨0, by simp [flood], Nat.le_refl _⟩
  | c :: h => by
    obtain ⟨k, hk, hk0⟩ := flood_src ok src h
    obtain ⟨y, hy, hyk⟩ := persist (ok := ok) (src := src) c hk
    exact ⟨y, hy, Nat.le_trans hyk hk0⟩

/-- Soundness: every copy flooding produces arrived along a journey with that hop count. -/
theorem flood_sound {ok src} : ∀ {h : Log} {w k : Nat},
    flood ok src h w = some k → Journey ok src h w k
  | [], w, k, hw => by
    simp [flood] at hw
    obtain ⟨rfl, rfl⟩ := hw
    exact .here []
  | c :: h, w, k, hw => by
    change step ok c (flood ok src h) w = some k at hw
    unfold step at hw
    by_cases hc : ok c = true ∧ w = c.v
    · rw [if_pos hc] at hw
      obtain ⟨hok, rfl⟩ := hc
      rcases merge_some hw with h1 | h2
      · exact .wait c (flood_sound h1)
      · cases hu : flood ok src h c.u with
        | none => rw [hu] at h2; cases h2
        | some j =>
          rw [hu] at h2
          simp at h2
          subst h2
          exact .hop c hok (flood_sound hu)
    · rw [if_neg hc] at hw
      exact .wait c (flood_sound hw)

/-- Completeness: every journey is matched by flooding with no more hops. -/
theorem flood_complete {ok src} {h : Log} {w j : Nat} (hj : Journey ok src h w j) :
    ∃ k, flood ok src h w = some k ∧ k ≤ j := by
  induction hj with
  | here h =>
    obtain ⟨k, hk, hk0⟩ := flood_src ok src h
    exact ⟨k, hk, hk0⟩
  | wait c _ ih =>
    obtain ⟨x, hx, hxj⟩ := ih
    obtain ⟨y, hy, hyx⟩ := persist c hx
    exact ⟨y, hy, Nat.le_trans hyx hxj⟩
  | @hop h k c hok _ ih =>
    obtain ⟨x, hx, hxk⟩ := ih
    show ∃ y, step ok c (flood ok src h) c.v = some y ∧ y ≤ k + 1
    unfold step
    rw [if_pos ⟨hok, rfl⟩, hx]
    obtain ⟨y, hy, hyx⟩ := merge_right (a := flood ok src h c.v) (b := some (x + 1)) rfl
    exact ⟨y, hy, by omega⟩

/-- Theorem 2a (delivery). With hop limit `H` and usable contacts `ok`
    (e.g. inside the TTL window), flooding delivers iff a journey exists. -/
theorem delivery_iff (ok : Contact → Bool) (src dst H : Nat) (h : Log) :
    (∃ k, flood ok src h dst = some k ∧ k ≤ H) ↔ (∃ j, j ≤ H ∧ Journey ok src h dst j) := by
  constructor
  · intro ⟨k, hk, hkH⟩; exact ⟨k, hkH, flood_sound hk⟩
  · intro ⟨j, hjH, hj⟩
    obtain ⟨k, hk, hkj⟩ := flood_complete hj
    exact ⟨k, hk, Nat.le_trans hkj hjH⟩

/-- Theorem 2b (fewest hops). The hop count flooding records is minimal. -/
theorem flood_min_hops {ok src} {h : Log} {w k : Nat} (hk : flood ok src h w = some k) :
    Journey ok src h w k ∧ ∀ j, Journey ok src h w j → k ≤ j := by
  refine ⟨flood_sound hk, fun j hj => ?_⟩
  obtain ⟨k', hk', hle⟩ := flood_complete hj
  rw [hk] at hk'
  cases hk'
  exact hle

To compare flooding with other strategies, a general forwarding rule is a function fwd that sees the whole past log and the current contact, and decides whether the holder passes a copy on. It can only pass a copy it holds. Single-copy, limited-copy, probabilistic and history-based rules are all instances.

Theorem 2c (earliest arrival). For every forwarding rule and every log: if the rule has delivered to ww, then flooding has delivered to ww, with a hop count no larger than that of any journey to ww.

Proof. Any copy a rule delivers travelled along a journey (induction on the log), flooding is complete for journeys (Theorem 2a), and its hop count is minimal (Theorem 2b). ∎

The theorem holds for every log, so in particular for every time prefix hτh_\tau: the contacts up to time τ\tau, which form a tail of the newest-first list. The arrival time of flooding is the least τ\tau at which it holds a copy, so no rule arrives earlier. By Theorem 2a that time is also the arrival time of the earliest journey. With ok=ttlOk(t0,ttl)\mathit{ok} = \mathrm{ttlOk}(t_0, \mathit{ttl}), every statement holds within the lifetime. The rule model carry does not count hops, so Theorem 2c compares flooding with journeys, not with the hop count of the rule’s own copy; the hop limit enters through Theorems 2a and 2b.

/-- An arbitrary single-copy-or-more forwarding rule: at a usable contact the
    holder `u` passes a copy to `v` when `fwd` (which may see the whole past) says so. -/
def carry (ok : Contact → Bool) (fwd : Log → Contact → Bool) (src : Nat) : Log → Nat → Bool
  | []     => fun w => w == src
  | c :: h => fun w =>
      (ok c && fwd h c && w == c.v && carry ok fwd src h c.u) || carry ok fwd src h w

theorem carry_journey {ok fwd src} : ∀ {h : Log} {w : Nat},
    carry ok fwd src h w = true → ∃ k, Journey ok src h w k
  | [], w, hw => by
    simp [carry] at hw
    subst hw
    exact ⟨0, .here []⟩
  | c :: h, w, hw => by
    simp only [carry, Bool.or_eq_true, Bool.and_eq_true, beq_iff_eq] at hw
    rcases hw with ⟨⟨⟨hok, _⟩, rfl⟩, hu⟩ | hw
    · obtain ⟨k, hk⟩ := carry_journey hu
      exact ⟨k + 1, .hop c hok hk⟩
    · obtain ⟨k, hk⟩ := carry_journey hw
      exact ⟨k, .wait c hk⟩

/-- Theorem 2c (earliest arrival). For every log, and so for every time prefix, if any
    forwarding rule has delivered to `w`, flooding has delivered too, with
    no more hops than any journey. -/
theorem flood_earliest (ok : Contact → Bool) (fwd : Log → Contact → Bool) (src : Nat)
    {h : Log} {w : Nat} (hc : carry ok fwd src h w = true) :
    ∃ k, flood ok src h w = some k ∧ ∀ j, Journey ok src h w j → k ≤ j := by
  obtain ⟨j, hj⟩ := carry_journey hc
  obtain ⟨k, hk, _⟩ := flood_complete hj
  exact ⟨k, hk, (flood_min_hops hk).2⟩

/-- TTL window: a message created at `t0` with lifetime `ttl` may use a contact
    only inside `[t0, t0 + ttl]`. -/
def ttlOk (t0 ttl : Nat) (c : Contact) : Bool := t0 ≤ c.t && c.t ≤ t0 + ttl

-- A concrete log (newest first): 1→2 at time 5, then 0→1 at time 3.
-- Relay order matters: the reversed order gives no journey.
example : flood (ttlOk 0 10) 0 [⟨1, 2, 5⟩, ⟨0, 1, 3⟩] 2 = some 2 := by decide
example : flood (ttlOk 0 10) 0 [⟨0, 1, 5⟩, ⟨1, 2, 3⟩] 2 = none := by decide
example : flood (ttlOk 0 4) 0 [⟨1, 2, 5⟩, ⟨0, 1, 3⟩] 2 = none := by decide

The three concrete checks show that order matters. The contact 0→10 \to 1 at time 3 followed by 1→21 \to 2 at time 5 delivers in 2 hops. The same two links in the opposite time order do not deliver. A lifetime of 4 excludes the contact at time 5.

Skew-tolerant polling

Epochs and windows. epoch(t)=⌊t/L⌋\mathrm{epoch}(t) = \lfloor t / L \rfloor. The polled window at epoch ee with tolerance dd is the list e−d,…,e−d+2de - d, \dots, e - d + 2d, with truncated subtraction at 00. It has length 2d+12d + 1. The polled ids are FsF_s applied to each epoch in the window.

/-! ## 3. Epochs and skew-tolerant polling -/

def epoch (L t : Nat) : Nat := t / L

/-- Epochs polled by a receiver at epoch `e` with tolerance `d`. -/
def window (e d : Nat) : List Nat := (List.range (2 * d + 1)).map (fun i => e - d + i)

theorem mem_window {e d x : Nat} (h1 : e - d ≤ x) (h2 : x ≤ e + d) : x ∈ window e d := by
  unfold window
  rw [List.mem_map]
  exact ⟨x - (e - d), List.mem_range.mpr (by omega), by omega⟩

theorem window_exact {e d x : Nat} (hd : d ≤ e) (hx : x ∈ window e d) :
    e - d ≤ x ∧ x ≤ e + d := by
  unfold window at hx
  rw [List.mem_map] at hx
  obtain ⟨i, hi, rfl⟩ := hx
  have := List.mem_range.mp hi
  omega

theorem window_length (e d : Nat) : (window e d).length = 2 * d + 1 := by
  simp [window]

Here tst_s is the sender’s clock reading when it stamps the packet, and trt_r is the recipient’s clock reading when it polls. Their gap is the clock offset plus the time the packet spent in transit. The hypothesis below bounds that whole gap.

Theorem 3 (skew tolerance). If L>0L \gt 0, ts≤tr+dLt_s \le t_r + dL and tr≤ts+dLt_r \le t_s + dL, then epoch(ts)\mathrm{epoch}(t_s) lies in the window around epoch(tr)\mathrm{epoch}(t_r) with tolerance dd. So for any id function FF and secret ss, the sender’s mailbox id Fs(epoch(ts))F_s(\mathrm{epoch}(t_s)) is among the ids the recipient polls.

Proof. Division by LL is monotone and ⌊(x+dL)/L⌋=⌊x/L⌋+d\lfloor (x + dL)/L \rfloor = \lfloor x/L \rfloor + d. Then ∣epoch(ts)−epoch(tr)∣≤d|\mathrm{epoch}(t_s) - \mathrm{epoch}(t_r)| \le d, and every such epoch is in the window. ∎

theorem div_mono {a b c : Nat} (hc : 0 < c) (h : a ≤ b) : a / c ≤ b / c :=
  (Nat.le_div_iff_mul_le hc).mpr (Nat.le_trans (Nat.div_mul_le_self a c) h)

/-- Clock skew of at most `d` epoch lengths moves the epoch by at most `d`. -/
theorem epoch_close {L d ts tr : Nat} (hL : 0 < L)
    (h1 : ts ≤ tr + d * L) (h2 : tr ≤ ts + d * L) :
    epoch L tr - d ≤ epoch L ts ∧ epoch L ts ≤ epoch L tr + d := by
  unfold epoch
  have a : ts / L ≤ tr / L + d := by
    have := div_mono hL h1
    rwa [Nat.add_mul_div_right _ _ hL] at this
  have b : tr / L ≤ ts / L + d := by
    have := div_mono hL h2
    rwa [Nat.add_mul_div_right _ _ hL] at this
  generalize ts / L = x at a b ⊢
  generalize tr / L = y at a b ⊢
  omega

/-- Theorem 3 (skew tolerance). -/
theorem skew_found {L d ts tr : Nat} (hL : 0 < L)
    (h1 : ts ≤ tr + d * L) (h2 : tr ≤ ts + d * L) :
    epoch L ts ∈ window (epoch L tr) d := by
  obtain ⟨a, b⟩ := epoch_close hL h1 h2
  exact mem_window a b

/-- The polled mailbox ids for secret `s` (any id function `F`). -/
def polled (F : Nat → Nat → Nat) (s e d : Nat) : List Nat := (window e d).map (F s)

theorem box_polled (F : Nat → Nat → Nat) {s L d ts tr : Nat} (hL : 0 < L)
    (h1 : ts ≤ tr + d * L) (h2 : tr ≤ ts + d * L) :
    F s (epoch L ts) ∈ polled F s (epoch L tr) d :=
  List.mem_map_of_mem _ (skew_found hL h1 h2)

/-- A gap of exactly `d * L` moves the epoch by exactly `d`. -/
theorem epoch_shift {L : Nat} (t d : Nat) (hL : 0 < L) :
    epoch L (t + d * L) = epoch L t + d := by
  unfold epoch; exact Nat.add_mul_div_right _ _ hL

/-- Tightness, lower end: the sender's clock is `d * L` behind; tolerance `d - 1` misses. -/
theorem tight_low {L d t : Nat} (hL : 0 < L) (hd : 0 < d) :
    epoch L t ∉ window (epoch L (t + d * L)) (d - 1) := by
  rw [epoch_shift t d hL]
  intro hx
  unfold window at hx
  rw [List.mem_map] at hx
  obtain ⟨i, _, hi⟩ := hx
  omega

/-- Tightness, upper end: the sender's clock is `d * L` ahead; tolerance `d - 1` misses
    (away from the truncation at epoch 0). -/
theorem tight_high {L d t : Nat} (hL : 0 < L) (hd : 0 < d) (he : d - 1 ≤ epoch L t) :
    epoch L (t + d * L) ∉ window (epoch L t) (d - 1) := by
  rw [epoch_shift t d hL]
  intro hx
  unfold window at hx
  rw [List.mem_map] at hx
  obtain ⟨i, hi, heq⟩ := hx
  have := List.mem_range.mp hi
  omega

-- A concrete instance: skew exactly `L` with `d = 1` is caught by width 1, missed by width 0.
example : epoch 10 10 ∈ window (epoch 10 0) 1 := by decide
example : epoch 10 10 ∉ window (epoch 10 0) 0 := by decide

The window is tight in both directions. A gap of exactly dLdL moves the epoch by exactly dd (epoch_shift), so a sender clock dLdL behind lands on the lowest polled epoch e−de - d and one dLdL ahead lands on the highest e+de + d. With tolerance d−1d - 1 the first is always missed (tight_low) and the second is missed whenever d−1≤ed - 1 \le e, that is, away from the truncation at epoch 0 (tight_high). So neither end of the 2d+12d+1 ids can be dropped. For example, with L=10L = 10 and a gap of exactly 1010, the stamp is found with tolerance 1 and missed with tolerance 0. The theorem uses nothing about FF, so findability does not depend on the pseudorandom function at all. Conversely, when d≤ed \le e the window contains only epochs within dd of ee (window_exact), so polling never looks further than the tolerance requires.

Unlinkability in the ideal-PRF model

Assumption (PRF security, idealised). The computational property is that FsF_s cannot be told apart from a uniformly random function by an efficient observer who does not know ss. The model replaces FF by a table T:S→E→IT : S \to E \to I drawn uniformly at random, where the sets of secrets SS, epochs EE (a finite horizon) and ids II are finite. Nothing below is a computational proof.

Views and relabellings. The view of a list of points (si,ei)(s_i, e_i) is the list of ids T(si,ei)T(s_i, e_i), which is what an observer of those mailboxes sees. A map π\pi on S×ES \times E relabels a table by (π⋅T)(s,e)=T(π(s,e))(\pi \cdot T)(s, e) = T(\pi(s, e)).

The Lean statements are about bijections of tables. The step from a bijection to a statement about distributions is the standard fact that a bijection of a finite set maps the uniform distribution to itself. That step is in the prose, not in Lean.

/-! ## 4. Ideal PRF: a uniformly random table -/

/-- In the ideal-PRF model the keyed function is replaced by a table
    `T : secret → epoch → id` drawn uniformly at random. -/
abbrev Table (S E I : Type) := S → E → I

def view {S E I : Type} (T : Table S E I) (qs : List (S × E)) : List I :=
  qs.map (fun q => T q.1 q.2)

/-- Relabelling the table through a permutation `π` of its domain. -/
def relabel {S E I : Type} (π : S × E → S × E) (T : Table S E I) : Table S E I :=
  fun s e => T (π (s, e)).1 (π (s, e)).2

theorem relabel_invol {S E I : Type} {π : S × E → S × E} (hπ : ∀ q, π (π q) = q)
    (T : Table S E I) : relabel π (relabel π T) = T := by
  funext s e
  simp only [relabel, hπ]

theorem view_relabel {S E I : Type} (π : S × E → S × E) (T : Table S E I) :
    ∀ qs : List (S × E), view (relabel π T) qs = view T (qs.map π)
  | [] => rfl
  | q :: qs => by
    simp only [view, List.map_cons] at *
    exact congrArg _ (view_relabel π T qs)

Theorem 4a (secret hiding). For secrets s,s′s, s' and any list of epochs, swapping ss and s′s' in the domain is an involution on tables, and it turns the view of ss on those epochs into the view of s′s'. So for uniform TT, the ids of ss on any list of epochs have the same distribution as the ids of s′s'. The observed ids carry no information about which secret produced them.

Theorem 4b (unlinkability across epochs). For s≠s′s \ne s' and e≠e′e \ne e', swapping the two points (s,e′)(s, e') and (s′,e′)(s', e') is an involution on tables, and it turns the view of [(s,e),(s,e′)][(s,e), (s,e')] into the view of [(s,e),(s′,e′)][(s,e), (s',e')]. So for uniform TT, the two ids seen for the same secret at ee and e′e' have the same distribution as the two ids seen for two different secrets at ee and e′e'.

Proof. An involution is a bijection. Relabelling commutes with views, view(π⋅T,q)=view(T,π(q))\mathrm{view}(\pi \cdot T, q) = \mathrm{view}(T, \pi(q)), and the swaps fix or exchange exactly the points involved. Since T↦π⋅TT \mapsto \pi \cdot T is a bijection, π⋅T\pi \cdot T is uniform when TT is, so the two views have the same distribution. ∎

/-- Swap two domain points. -/
def swapPt {S E : Type} [DecidableEq S] [DecidableEq E] (p q : S × E) (x : S × E) : S × E :=
  if x = p then q else if x = q then p else x

theorem swapPt_invol {S E : Type} [DecidableEq S] [DecidableEq E] (p q : S × E) :
    ∀ x, swapPt p q (swapPt p q x) = x := by
  intro x
  unfold swapPt
  by_cases hp : x = p
  · subst hp; by_cases hq : q = x <;> simp [hq]
  · by_cases hq : x = q
    · subst hq; simp
    · simp [hp, hq]

/-- Swap two secrets, keeping the epoch. -/
def swapKey {S E : Type} [DecidableEq S] (s s' : S) (x : S × E) : S × E :=
  (if x.1 = s then s' else if x.1 = s' then s else x.1, x.2)

theorem swapKey_invol {S E : Type} [DecidableEq S] (s s' : S) :
    ∀ x : S × E, swapKey s s' (swapKey s s' x) = x := by
  intro ⟨a, e⟩
  unfold swapKey
  by_cases h1 : a = s
  · subst h1; by_cases h2 : s' = a <;> simp [h2]
  · by_cases h2 : a = s'
    · subst h2; simp
    · simp [h1, h2]

/-- Theorem 4a (secret hiding). Relabelling by the key swap is an involution on
    tables and turns the view of secret `s` on any epoch list into the view of `s'`. -/
theorem secret_hiding {S E I : Type} [DecidableEq S] (s s' : S) (es : List E)
    (T : Table S E I) :
    relabel (swapKey s s') (relabel (swapKey s s') T) = T ∧
    view (relabel (swapKey s s') T) (es.map (fun e => (s, e))) =
      view T (es.map (fun e => (s', e))) := by
  refine ⟨relabel_invol (swapKey_invol s s') T, ?_⟩
  rw [view_relabel, List.map_map]
  congr 1
  apply List.map_congr_left
  intro e _
  simp [swapKey]

/-- Theorem 4b (unlinkability across epochs). For `e ≠ e'`, `s ≠ s'`, the pair of
    ids "same secret at e, e'" is carried by a table involution to "different
    secrets at e, e'". -/
theorem unlinkable {S E I : Type} [DecidableEq S] [DecidableEq E]
    {s s' : S} {e e' : E} (hs : s ≠ s') (he : e ≠ e') (T : Table S E I) :
    relabel (swapPt (s, e') (s', e')) (relabel (swapPt (s, e') (s', e')) T) = T ∧
    view (relabel (swapPt (s, e') (s', e')) T) [(s, e), (s, e')] =
      view T [(s, e), (s', e')] := by
  refine ⟨relabel_invol (swapPt_invol _ _) T, ?_⟩
  rw [view_relabel]
  have h1 : swapPt (s, e') (s', e') (s, e) = (s, e) := by
    unfold swapPt
    have a : (s, e) ≠ (s, e') := fun h => he (Prod.mk.inj h).2
    have b : (s, e) ≠ (s', e') := fun h => hs (Prod.mk.inj h).1
    simp [a, b]
  have h2 : swapPt (s, e') (s', e') (s, e') = (s', e') := by simp [swapPt]
  simp [h1, h2]

Theorem 4c (fresh epochs). Let pp be a point not in the list qq. Overwriting T(p)T(p) with y′y' leaves the view of qq unchanged, and overwriting it back with the old value restores TT. So for every observed view oo, overwriting at pp is a bijection between {T:view(T,q)=o, T(p)=y}\lbrace T : \mathrm{view}(T, q) = o,\ T(p) = y \rbrace and the same set with y′y'. All these sets have the same size, so given any view of other points, T(p)T(p) is uniform on II. The id of an epoch not yet observed is independent of all ids observed so far.

Proof. The overwrite does not touch any point of qq, and the two overwrites are mutually inverse. The step from equal fibre sizes to conditional uniformity, and so to the ids being independent, is counting. ∎

/-- Point update of a table. -/
def update {S E I : Type} [DecidableEq S] [DecidableEq E]
    (T : Table S E I) (p : S × E) (y : I) : Table S E I :=
  fun s e => if (s, e) = p then y else T s e

/-- Theorem 4c (fresh epochs). For an unqueried point `p`, rewriting `T p` to any
    `y'` keeps the view, and is undone by rewriting back: a bijection between the
    fibres `{T | view T qs = o ∧ T p = y}` for different `y`. -/
theorem fresh_epoch {S E I : Type} [DecidableEq S] [DecidableEq E]
    (T : Table S E I) (p : S × E) (qs : List (S × E)) (hp : p ∉ qs) (y' : I) :
    view (update T p y') qs = view T qs ∧
    update T p y' p.1 p.2 = y' ∧
    update (update T p y') p (T p.1 p.2) = T := by
  refine ⟨?_, by simp [update], ?_⟩
  · unfold view
    apply List.map_congr_left
    intro q hq
    have : (q.1, q.2) ≠ p := fun h => hp (by rw [← h]; exact hq)
    simp [update, this]
  · funext s e
    unfold update
    by_cases h : (s, e) = p
    · subst h; simp
    · simp [h]

A uniformly random table can map two points to the same id. Distinct ids are therefore a separate idealisation. When it holds, ids of different pairs or different epochs differ. For a truly random table, the probability that qq distinct given points have two equal ids is at most q(q−1)/(2∣I∣)q(q-1)/(2|I|) by the union bound over pairs. That standard bound is not proved here.

The two idealisations fit together only partly. Theorems 4a and 4b also hold for a uniform injective table, because relabelling by a permutation of the domain preserves injectivity, so it is a bijection on injective tables too. Theorem 4c does not carry over unchanged: a point update can create a collision, and under the injective idealisation T(p)T(p) is uniform only on the ids not yet observed, not on all of II. Theorem 4c as stated is for the uniform model.

/-- Idealisation of collision-freeness: an injective ideal PRF. -/
def CollisionFree {S E I : Type} (T : Table S E I) : Prop :=
  ∀ s e s' e', T s e = T s' e' → s = s' ∧ e = e'

theorem ids_distinct {S E I : Type} {T : Table S E I} (hT : CollisionFree T)
    {s s' : S} {e e' : E} (h : s ≠ s' ∨ e ≠ e') : T s e ≠ T s' e' := by
  intro heq
  obtain ⟨a, b⟩ := hT _ _ _ _ heq
  rcases h with h | h
  · exact h a
  · exact h b

End to end

Theorem 5 (the guarantees for one set of parameters). Assume the sender aa issued ⟨a,m⟩\langle a, m \rangle, the history so far is a trace, L>0L \gt 0, the gap between tst_s and trt_r is at most dLdL in both directions, and a journey from src\mathit{src} to dst\mathit{dst} with at most HH hops, using only contacts in [t0,t0+ttl][t_0, t_0 + \mathit{ttl}], exists in the log. Let p=⟨Fs(epoch(ts)), m, ⟨a,m⟩⟩p = \langle F_s(\mathrm{epoch}(t_s)),\ m,\ \langle a, m \rangle \rangle. Then flooding within the lifetime delivers to dst\mathit{dst} within HH hops, the mailbox id of pp is among the ids the recipient polls at trt_r, emitting pp extends the trace, and pp verifies under aa.

Proof. Theorem 1 (converse) for pp, Theorem 2a for the spread of its copies, Theorem 3 for its mailbox id. ∎

Here src\mathit{src} is the node where aa emits pp and dst\mathit{dst} is bb‘s node. The flooding model tracks hop counts, not packets: it models the spread of copies of pp, which honest relays re-emit unchanged (the relay step of Theorem 1), so each copy keeps the box Fs(epoch(ts))F_s(\mathrm{epoch}(t_s)). Theorem 5 collects the three guarantees for the same parameters. It does not relate the poll instant trt_r to the time the copy arrives, so it does not by itself say that bb finds pp at trt_r: that also needs the poll to happen after arrival, with the gap still within dLdL.

Together with Theorem 1 this gives both directions of the goal. Whatever is delivered and verifies under an honest aa was issued by aa, whatever the relays did. When relays forward honestly, whatever aa issues reaches bb‘s node whenever the contacts allow, under a mailbox id bb polls whenever the clocks allow. Theorem 4 says that rotating the id, which Theorem 5 allows with any FF, does not reveal the secret or link epochs, in the ideal model.

/-! ## 5. End to end -/

/-- Theorem 5. If the sender issued `m`, a journey of at most `H` hops inside the
    lifetime exists, and the clocks differ by at most `d` epoch lengths, then
    flooding within the lifetime reaches `dst`, the packet's mailbox id is among
    those the receiver polls, and it verifies. Conversely (Theorem 1) anything that verifies under
    an honest sender's key was issued by that sender, whatever path it took. -/
theorem end_to_end {issued : Sig → Prop} {corrupt : Agent → Prop}
    (F : Nat → Nat → Nat) (log : Log) (t : List Packet)
    {a m s L d ts tr src dst H j t0 ttl : Nat}
    (ht : Trace issued corrupt t) (hi : issued ⟨a, m⟩)
    (hL : 0 < L) (h1 : ts ≤ tr + d * L) (h2 : tr ≤ ts + d * L)
    (hj : Journey (ttlOk t0 ttl) src log dst j) (hjH : j ≤ H) :
    let p : Packet := ⟨F s (epoch L ts), m, ⟨a, m⟩⟩
    (∃ k, flood (ttlOk t0 ttl) src log dst = some k ∧ k ≤ H) ∧
    p.box ∈ polled F s (epoch L tr) d ∧
    Trace issued corrupt (p :: t) ∧ Verifies a p := by
  intro p
  obtain ⟨ht', hv⟩ := issued_deliverable ht hi (F s (epoch L ts))
  exact ⟨(delivery_iff (ttlOk t0 ttl) src dst H log).mpr ⟨j, hjH, hj⟩,
         box_polled F hL h1 h2, ht', hv⟩

end RM

Limits and assumptions

The theorems are exactly as strong as the model. What they do not give:

  • No computational proofs. EUF-CMA and PRF security are assumptions. The Lean works with symbolic signatures and a uniformly random table. How the symbolic results carry over to a real signature scheme and a real pseudorandom function is a computational question that this article does not address.
  • Distributions are argued in prose. Lean proves the bijections and the identities between views. The steps from there to equal distributions, conditional uniformity and the ids being independent are counting arguments outside Lean.
  • Collision-freeness is assumed. It is a separate idealisation, and the birthday bound above is stated, not proved.
  • Unlinkability is shown for specific patterns. The key swap over any list of epochs, the two-point pattern of Theorem 4b, and the fresh-epoch statement. A general statement for any two query lists of equal length with distinct points is not proved.
  • Only the ids are covered. The signature in the clear identifies the signer to anyone who holds the public key, so the body and signature must be sealed under a key derived from the shared secret. That sealing is not modelled. Timing, packet sizes, contact patterns and the act of polling are also outside the model.
  • Time order is taken from the log. A journey is time-respecting because the log is assumed sorted by time. Simultaneous contacts are ordered by the log, so two contacts at the same instant can form a two-hop journey. The lifetime is a window on contact times, and the hop limit is a bound on the hop count of the delivered copy.
  • Copies are free. Buffers are unbounded, contacts have unlimited capacity, nothing is lost, and delivery leaves the copy in place. Theorem 2c says flooding is never later than any rule. It says nothing about the storage and bandwidth flooding uses.
  • No replay protection. A replayed packet verifies. Rejecting stale messages needs an epoch or a counter in the signed body together with state at the recipient.
  • Delivery assumes honest relays. Theorems 2 and 5 assume every relay follows the forwarding rule and passes the packet on unchanged. A relay that drops packets can stop delivery, for instance when it lies on every usable journey, and a relay that moves the body to another mailbox id can make the arriving copy unfindable. Neither can break authenticity, which Theorem 1 proves against arbitrary relays.
  • Corrupted senders. Nothing is claimed for messages from a corrupted key, and nothing about relays beyond the derivation rules.
  • One polling instant. Theorem 3 is about one poll. A packet whose transit time pushes the gap beyond dLdL is found only if the recipient keeps polling older epochs.

Prior work

  • A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks, SIAM Journal on Computing, 1988. Defines EUF-CMA, the computational property idealised in Theorem 1.
  • On the Security of Public Key Protocols, IEEE Transactions on Information Theory, 1983. The symbolic attacker model used for Derivable.
  • How to Construct Random Functions, Journal of the ACM, 1986. Defines pseudorandom functions, whose ideal counterpart is the random table of Theorem 4.
  • TOTP: Time-Based One-Time Password Algorithm, RFC 6238, 2011. Values derived from a shared secret and a time step, with neighbouring steps accepted to absorb clock drift, as in Theorem 3.
  • Epidemic Routing for Partially-Connected Ad Hoc Networks, technical report, 2000. Flooding at every contact.
  • A Delay-Tolerant Network Architecture for Challenged Internets, ACM SIGCOMM, 2003. Store-carry-forward with bundle lifetimes.
  • Computing Shortest, Fastest, and Foremost Journeys in Dynamic Networks, International Journal of Foundations of Computer Science, 2003. Time-respecting journeys and earliest-arrival journeys, the yardstick of Theorem 2c.
  • Time-Varying Graphs and Dynamic Networks, International Journal of Parallel, Emergent and Distributed Systems, 2012. Journeys in time-varying graphs.

The contribution here is only the combination and its proofs: that these components, put together as above, reach all four requirements at once.