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 at time means that can hand data to at time . 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 and a recipient share a secret , and holds ‘s public verification key. Each node has a local clock, and the clocks of and may disagree.
Goal. A message from to should satisfy:
- Authenticity. If ‘s key is not corrupted, accepts as coming from only if signed exactly , whatever the relays did on the way.
- Delivery. When relays forward honestly, reaches 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.
- Findability. Knowing only and its own clock, can tell which packets are for it, as long as the clocks are close enough.
- Unlinkability. The labels relays see on packets reveal nothing about , 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 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 , 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 and write . Let be a pseudorandom function, a tolerance , a lifetime and a hop limit .
- Send. At local time the sender computes the mailbox id , signs the body, and emits the packet with creation time . Here is the creation time on the time axis of the contact log, and is the sender’s own clock reading, which may differ from it.
- Forward. At every contact whose time lies in , passes a copy of each packet it holds to . A node keeps the copy that has travelled the fewest hops.
- Poll. At local time the recipient computes the ids for , collects the packets it holds that carry one of them, and accepts those that verify under ‘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 , read “agent signed body ”. A packet is . A packet verifies under when . 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 be a trace, , and an uncorrupted agent. If verifies under , then issued the signature . Conversely, if issued , then after any trace a packet with body and any mailbox id can be emitted, and it verifies under . 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 to . 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 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 to with hops in a log is defined inductively: is reached with hops in any log; a journey in is still one in (waiting); and if is usable and is reached with hops in , then is reached with hops in . 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 maps each node to none or to some k, the fewest hops of any copy it holds. Initially only holds a copy, with hops. At a usable contact , keeps the minimum of its own count and ‘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 and log : flooding holds a copy at with at most hops if and only if a journey from to with at most hops exists in .
Theorem 2b (fewest hops). If flooding records hops at , then a -hop journey to exists and every journey to has at least hops.
Proof. Soundness is induction on the log: a recorded count either was already there (a wait) or came from ‘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 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 , then flooding has delivered to , with a hop count no larger than that of any journey to .
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 : the contacts up to time , which form a tail of the newest-first list. The arrival time of flooding is the least 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 , 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 at time 3 followed by 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. . The polled window at epoch with tolerance is the list , with truncated subtraction at . It has length . The polled ids are 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 is the sender’s clock reading when it stamps the packet, and 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 , and , then lies in the window around with tolerance . So for any id function and secret , the sender’s mailbox id is among the ids the recipient polls.
Proof. Division by is monotone and . Then , 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 moves the epoch by exactly (epoch_shift), so a sender clock behind lands on the lowest polled epoch and one ahead lands on the highest . With tolerance the first is always missed (tight_low) and the second is missed whenever , that is, away from the truncation at epoch 0 (tight_high). So neither end of the ids can be dropped. For example, with and a gap of exactly , the stamp is found with tolerance 1 and missed with tolerance 0. The theorem uses nothing about , so findability does not depend on the pseudorandom function at all. Conversely, when the window contains only epochs within of (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 cannot be told apart from a uniformly random function by an efficient observer who does not know . The model replaces by a table drawn uniformly at random, where the sets of secrets , epochs (a finite horizon) and ids are finite. Nothing below is a computational proof.
Views and relabellings. The view of a list of points is the list of ids , which is what an observer of those mailboxes sees. A map on relabels a table by .
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 and any list of epochs, swapping and in the domain is an involution on tables, and it turns the view of on those epochs into the view of . So for uniform , the ids of on any list of epochs have the same distribution as the ids of . The observed ids carry no information about which secret produced them.
Theorem 4b (unlinkability across epochs). For and , swapping the two points and is an involution on tables, and it turns the view of into the view of . So for uniform , the two ids seen for the same secret at and have the same distribution as the two ids seen for two different secrets at and .
Proof. An involution is a bijection. Relabelling commutes with views, , and the swaps fix or exchange exactly the points involved. Since is a bijection, is uniform when 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 be a point not in the list . Overwriting with leaves the view of unchanged, and overwriting it back with the old value restores . So for every observed view , overwriting at is a bijection between and the same set with . All these sets have the same size, so given any view of other points, is uniform on . 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 , 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 distinct given points have two equal ids is at most 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 is uniform only on the ids not yet observed, not on all of . 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 issued , the history so far is a trace, , the gap between and is at most in both directions, and a journey from to with at most hops, using only contacts in , exists in the log. Let . Then flooding within the lifetime delivers to within hops, the mailbox id of is among the ids the recipient polls at , emitting extends the trace, and verifies under .
Proof. Theorem 1 (converse) for , Theorem 2a for the spread of its copies, Theorem 3 for its mailbox id. ∎
Here is the node where emits and is ‘s node. The flooding model tracks hop counts, not packets: it models the spread of copies of , which honest relays re-emit unchanged (the relay step of Theorem 1), so each copy keeps the box . Theorem 5 collects the three guarantees for the same parameters. It does not relate the poll instant to the time the copy arrives, so it does not by itself say that finds at : that also needs the poll to happen after arrival, with the gap still within .
Together with Theorem 1 this gives both directions of the goal. Whatever is delivered and verifies under an honest was issued by , whatever the relays did. When relays forward honestly, whatever issues reaches ‘s node whenever the contacts allow, under a mailbox id polls whenever the clocks allow. Theorem 4 says that rotating the id, which Theorem 5 allows with any , 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 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.