A group of people exchange messages through a host. The host stores the messages, orders them into one history and hands that history to each member. In doing so it holds a number of powers over the group. It can read what it stores. It can alter it. It can present the messages in a different order, or present different orders to different members. It can drop a message it has acknowledged. It can accept messages the group’s rules forbid. It can refuse service to one member, and it can disappear and take the history with it.
None of the parts used below is new. Each is a known technique with its own literature, credited where it appears. The question here is a different one: which combination of these parts takes away each power, and can that be proved? This article states the goal precisely, puts five components together, and proves in a symbolic model that the combination meets the goal. It also proves exactly where the goal cannot be met. All statements are checked in Lean 4 with the core library only. The code blocks below concatenate, in reading order, into one file that compiles with Lean 4.16 with no sorry, no admit and no declared axioms.
The goal
There are seven powers, listed in the table below. For each one, the combination should do one of three things:
- remove it, so that the host cannot exercise it at all;
- expose it, so that exercising it produces transferable evidence: data that any third party, with only public verification keys, can check and that cannot exist against an honest host;
- escape it, so that the members can move the history to another host without losing anything and without trusting the new host more than the old one.
Goal. Under stated assumptions on hashing, signatures, encryption and the uniqueness of submitted entries, and in a model without time, each of the powers read, alter, reorder, drop, break rules, exclude, disappear is removed, exposed or escaped, under these conditions: a fork or reordering is exposed once the views involved are brought together by exchange of heads; a drop is exposed once a receipt is compared with a signed view at least as long; exclusion and disappearance are escaped by a member who holds a copy and its last signed head. Where a power can be neither removed nor exposed, state the precise limit as a theorem.
The limits are part of the goal, not an afterthought. A host can always receive a message and then never show it to anyone. The last theorem below shows that no sound verdict computed from what the host releases can detect this. A second limit lies outside the model, because the model has no time: a host can serve one member a stale view, a strictly shorter history, for ever. That member’s view is still a prefix of everyone else’s, so it yields no evidence, and the member is not alerted to start a migration. Both limits are listed again under Limits and assumptions.
The components
Each component is known. What this article adds is their combination toward this goal and a machine-checked proof that it meets it.
- End-to-end encryption under keys the host does not hold. The symbolic attacker model is that of “On the Security of Public Key Protocols” (IEEE Transactions on Information Theory, 1983): the attacker can pair, unpair and encrypt freely, and can decrypt only with the key. The computational counterpart for confidentiality together with integrity is authenticated encryption, “Authenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm” (ASIACRYPT 2000).
- Hash-chained histories with signed heads. Linking each entry to the digest of everything before it is from “How to Time-Stamp a Digital Document” (Journal of Cryptology, 1991), and the iterated construction of the digest from a compression function is from “A Design Principle for Hash Functions” (CRYPTO 1989). The signature is assumed existentially unforgeable under chosen-message attack, “A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks” (SIAM Journal on Computing, 1988).
- Fork consistency and exchange of heads among readers. The guarantee that an untrusted server can at worst split its clients into groups with diverging histories, and that the split is exposed once two clients compare, is from “Building Secure File Systems out of Byzantine Storage” (PODC 2002). Spreading small summaries between peers is the epidemic approach of “Epidemic Algorithms for Replicated Database Maintenance” (PODC 1987), and exchanging signed log heads for this purpose is studied in “Efficient Gossip Protocols for Verifying the Consistency of Certificate Logs” (IEEE Conference on Communications and Network Security, 2015).
- Deterministic rule checking. Each entry is judged by a deterministic function of the history before it, so that every party who holds the history reaches the same verdict, as in “Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial” (ACM Computing Surveys, 1990).
- A self-certifying log. A name that is derived from the content it names, so that whoever serves it does not need to be trusted, is the idea of self-certifying pathnames in “Separating Key Management from File System Security” (SOSP 1999). Here the name of the history is its signed head.
The combination
The five components are combined as follows.
- Members encrypt every entry under a key known only to members. The host stores and orders ciphertexts.
- The host keeps one history per group and, after each append, signs the head digest of the whole history. A member who submits an entry receives the signed head of a history that contains it, which serves as a receipt.
- Members accept a history only together with a signed head that matches it, and they exchange the heads they hold with other members, over any channel they like, including a direct short-range link. Two heads whose histories are not prefixes of one another are kept as evidence.
- The group fixes a deterministic rule
valid. Any party that holds a history recomputes the rule on every entry. A signed head of a history that breaks the rule is kept as evidence. - Because a history is identified by its signed head and not by where it is stored, any member who holds a copy can hand it to a new host. Members accept the new host’s history only if it extends the last signed head they hold.
The table states what the theorems below establish for each power.
| power | outcome | theorem |
|---|---|---|
| read | removed | secret_not_derivable, key_not_derivable |
| alter | removed, up to replay of seen ciphertexts, which is exposed under A4 | no_forgery, allValid_noReplay_of_nodup |
| reorder, fork | exposed once views are exchanged | reorder_evidence, fork_no_join, fork_evidence_sound |
| drop after a receipt | exposed against a view at least as long as the receipt | drop_evidence |
| break rules | exposed, with the offending entry | violation_witness, rule_evidence_sound |
| exclude, disappear | escaped by migration | migrate_faithful, migrate_extends, migrate_views, migrate_no_fork |
| withhold from every reader | not exposable | indistinguishable, withholding_undetectable |
| serve a stale view | not covered (no time in the model) | none |
Definitions
Histories
A history is a finite list of entries, written newest first, so the most recent entry is the head of the list.
Extension and comparability. History extends history , written , if for some list of newer entries. Two histories are comparable if one extends the other.
Extension is a preorder that respects length and membership. Two histories that are both extended by a third are comparable, which is the fact that the whole fork argument rests on. Two different histories of the same length are never comparable. Extension is decidable for entries with decidable equality, so a third party can check every piece of evidence below (extension, comparability, fork evidence and rule evidence) by computation, given a decidable signature check. Honesty of a host and the derivability of messages are not checks of this kind; they are properties the theorems reason about.
/-
Host powers: a symbolic model.
Histories are lists written newest-first, so "b extends a" means a is a suffix of b.
Cryptography is idealised:
* hashing: a compression function `c` that is injective and never returns the initial value;
* signatures: the set of digests that verify is exactly the set the host signed (a predicate);
* encryption: a symbolic free-algebra term model, where decryption needs the key.
-/
namespace HostPowers
/-! ## 1. Histories and extension -/
section Hist
variable {E : Type}
/-- `Ext a b`: history `b` extends history `a` (newest-first, so `a` is a suffix). -/
def Ext (a b : List E) : Prop := ∃ d, b = d ++ a
/-- Two histories are comparable when one extends the other. -/
def Comparable (a b : List E) : Prop := Ext a b ∨ Ext b a
theorem ext_refl (a : List E) : Ext a a := ⟨[], rfl⟩
theorem ext_trans {a b c : List E} : Ext a b → Ext b c → Ext a c
| ⟨d₁, h₁⟩, ⟨d₂, h₂⟩ => ⟨d₂ ++ d₁, by rw [h₂, h₁, List.append_assoc]⟩
theorem ext_length {a b : List E} : Ext a b → a.length ≤ b.length
| ⟨d, h⟩ => by rw [h, List.length_append]; omega
theorem ext_eq_of_length {a b : List E} : Ext a b → a.length = b.length → a = b
| ⟨d, h⟩, hl => by
subst h
cases d with
| nil => rfl
| cons x d => simp [List.length_append] at hl; omega
theorem ext_mem {a b : List E} {e : E} : Ext a b → e ∈ a → e ∈ b
| ⟨d, h⟩, he => by rw [h]; exact List.mem_append_right d he
/-- Two suffixes of one history are comparable. -/
theorem comparable_of_common {a b L : List E} : Ext a L → Ext b L → Comparable a b := by
intro ⟨d₁, h₁⟩ ⟨d₂, h₂⟩
rw [h₁] at h₂
clear h₁
induction d₁ generalizing d₂ with
| nil => exact Or.inr ⟨d₂, by simpa using h₂⟩
| cons x d₁ ih =>
cases d₂ with
| nil => exact Or.inl ⟨x :: d₁, by simpa using h₂.symm⟩
| cons y d₂ =>
simp only [List.cons_append, List.cons.injEq] at h₂
exact ih d₂ h₂.2
/-- Distinct histories of equal length are never comparable (covers reordering). -/
theorem not_comparable_of_same_length {a b : List E}
(hne : a ≠ b) (hl : a.length = b.length) : ¬ Comparable a b := by
intro h
cases h with
| inl h => exact hne (ext_eq_of_length h hl)
| inr h => exact hne (ext_eq_of_length h hl.symm).symm
/-- A boolean test for extension. -/
def extB [DecidableEq E] (a b : List E) : Bool :=
decide (a.length ≤ b.length) && decide (b.drop (b.length - a.length) = a)
theorem extB_iff [DecidableEq E] (a b : List E) : extB a b = true ↔ Ext a b := by
constructor
· intro h
simp only [extB, Bool.and_eq_true, decide_eq_true_eq] at h
exact ⟨b.take (b.length - a.length), by
have := List.take_append_drop (b.length - a.length) b
rw [h.2] at this; exact this.symm⟩
· intro ⟨d, h⟩
subst h
simp only [extB, Bool.and_eq_true, decide_eq_true_eq, List.length_append]
refine ⟨by omega, ?_⟩
have : d.length + a.length - a.length = d.length := by omega
rw [this]; exact List.drop_left _ _
instance [DecidableEq E] (a b : List E) : Decidable (Ext a b) :=
decidable_of_iff _ (extB_iff a b)
instance [DecidableEq E] (a b : List E) : Decidable (Comparable a b) :=
inferInstanceAs (Decidable (_ ∨ _))
end Hist
Head digests
Head. For an initial value and a compression function , the head of a history is
Assumption A1 (collision-free hashing, idealised). The function is injective in both arguments, and its value is never .
A real hash function has a fixed output length and therefore cannot be injective. A1 is the symbolic idealisation of collision resistance. A1 has two parts, and both are used. In a computational model, every use of A1 below becomes “or a collision of , or an input that maps to , has been found”. The second case is a preimage of the initial value, not a collision. Strengthening the chain with the length of the history in a final block removes that case, as in “A Design Principle for Hash Functions” (CRYPTO 1989). The chain here has no length block, and the proofs here do not carry out either reduction.
A head determines its history. Under A1, implies .
Proof. Induction on both lists. Two empty lists are equal. An empty and a non-empty list have heads and , which differ by A1. For two non-empty lists, injectivity of gives equal newest entries and equal heads of the rest, and the induction hypothesis gives equal rests. ∎
/-! ## 2. Hash chains -/
section Chain
variable {Hd E : Type} (iv : Hd) (c : Hd → E → Hd)
/-- The head digest of a history: fold the compression function from the oldest entry. -/
def chain : List E → Hd
| [] => iv
| e :: l => c (chain l) e
/-- Idealised collision-freeness of the compression function (an ASSUMPTION). -/
structure CollisionFree : Prop where
inj : ∀ x y e f, c x e = c y f → x = y ∧ e = f
notIv : ∀ x e, c x e ≠ iv
variable {iv c}
/-- A head digest determines its whole history. -/
theorem chain_inj (hc : CollisionFree iv c) :
∀ {a b : List E}, chain iv c a = chain iv c b → a = b
| [], [], _ => rfl
| [], f :: b, h => absurd h.symm (hc.notIv _ f)
| e :: a, [], h => absurd h (hc.notIv _ e)
| e :: a, f :: b, h => by
have ⟨h₁, h₂⟩ := hc.inj _ _ _ _ h
rw [chain_inj hc h₁, h₂]
end Chain
Signed heads, honesty and fork evidence
Assumption A2 (unforgeable signatures, idealised). The set of digests that carry a valid host signature is exactly the set of digests the host chose to sign. In the Lean file this set is a predicate signed.
This is the symbolic reading of existential unforgeability under chosen-message attack. It gives the host full freedom over what it signs and the attacker no freedom at all.
Honest log. A host is honest for history if every digest it signs is the head of some .
Fork evidence. For histories and , fork evidence is the conjunction: is signed, is signed, and and are not comparable.
Fork evidence is transferable. It consists of two histories and two signatures, and checking it means verifying two signatures, recomputing two heads and deciding one comparability. The Lean instance below makes that decision a computation whenever the signature check is one.
/-! ## 3. Signed heads, fork evidence, fork consistency -/
section Fork
variable {Hd E : Type} (iv : Hd) (c : Hd → E → Hd)
/-- `signed d`: digest `d` carries a valid host signature. Unforgeability is idealised:
this predicate IS the set of digests the host chose to sign. -/
abbrev Signed (Hd : Type) := Hd → Prop
/-- An honest host keeps one history `L` and signs only heads of suffixes of it. -/
def HonestLog (signed : Signed Hd) (L : List E) : Prop :=
∀ d, signed d → ∃ l, Ext l L ∧ chain iv c l = d
/-- Transferable fork evidence: two signed histories, neither extending the other. -/
def ForkEvidence (signed : Signed Hd) (a b : List E) : Prop :=
signed (chain iv c a) ∧ signed (chain iv c b) ∧ ¬ Comparable a b
instance [DecidableEq E] (signed : Signed Hd) [DecidablePred signed] (a b : List E) :
Decidable (ForkEvidence iv c signed a b) :=
inferInstanceAs (Decidable (_ ∧ _ ∧ _))
Theorems: the combination meets the goal
Reorder and fork: exposed
Fork evidence is sound. Under A1, if the host is honest for some , then no pair is fork evidence.
Proof. Both signed heads are heads of suffixes of . By the injectivity of heads, and , so both are suffixes of and therefore comparable. ∎
Fork consistency (no join). If two histories and are not comparable, no history extends both. Under A1 a head names exactly one history, so once the host has shown two members incomparable views, no signed head it issues later can be accepted by both of them: from then on they never again see a common history, and any later views they exchange still form fork evidence.
Proof. Two suffixes of one history are comparable, so a common extension of and would make them comparable. A member accepts a new view only if it extends the view it holds, so after the fork every view accepted by the first member extends and every view accepted by the second extends ; by the first sentence no view is both, and any two such views are again incomparable. ∎
Views trichotomy. For any family of views , at least one of the following holds: every two views are comparable; some pair is fork evidence; some view has no signed head.
Proof. If two views are not comparable and both have signed heads, they are fork evidence by definition. Otherwise every incomparable pair contains a view without a signed head. ∎
The views trichotomy is a case split and needs no assumption. Its weight comes from the soundness of fork evidence. Members accept a view only with a signed head, which rules out the third case. Then either all views pooled by exchange of heads lie on one line, or the pool contains evidence that convicts the host, because evidence cannot exist against an honest host. Under an honest host the second case is impossible as well, which is the corollary honest_views_comparable. The no-join property is the fork-consistency guarantee of the components list: a fork, once made, is permanent and is exposed whenever members on the two sides compare heads.
Reordering is a special case. Two signed histories of the same length that differ, for instance by the order of two entries, are fork evidence.
Drop after a receipt. Let be a signed history that contains entry (the receipt), and a signed history with that does not contain . Then is fork evidence.
Proof. If , then , a contradiction. If , then , so the lengths are equal and , again a contradiction. ∎
variable {iv c}
/-- Soundness: fork evidence never exists against an honest host. -/
theorem fork_evidence_sound (hc : CollisionFree iv c) {signed : Signed Hd} {L : List E}
(hon : HonestLog iv c signed L) {a b : List E} : ¬ ForkEvidence iv c signed a b := by
intro ⟨sa, sb, nc⟩
have ⟨la, ha, ea⟩ := hon _ sa
have ⟨lb, hb, eb⟩ := hon _ sb
rw [chain_inj hc ea] at ha
rw [chain_inj hc eb] at hb
exact nc (comparable_of_common ha hb)
/-- Fork consistency (no join): two incomparable histories have no common extension,
so after a fork no later history can be accepted by both sides. -/
theorem fork_no_join {a b : List E} (h : ¬ Comparable a b) (L : List E) :
¬ (Ext a L ∧ Ext b L) :=
fun ⟨ha, hb⟩ => h (comparable_of_common ha hb)
/-- After a fork, views that extend the two sides remain incomparable. -/
theorem fork_persists {a b a' b' : List E} (h : ¬ Comparable a b)
(ha : Ext a a') (hb : Ext b b') : ¬ Comparable a' b' := by
intro hc
cases hc with
| inl x => exact fork_no_join h b' ⟨ext_trans ha x, hb⟩
| inr x => exact fork_no_join h a' ⟨ha, ext_trans hb x⟩
/-- Views trichotomy: accepted views are pairwise comparable, or two of them form
fork evidence (which, by soundness, convicts the host), or one lacks a signed head. -/
theorem views_trichotomy {ι : Type} {signed : Signed Hd} (view : ι → List E) :
(∀ i j, Comparable (view i) (view j)) ∨
(∃ i j, ForkEvidence iv c signed (view i) (view j)) ∨
(∃ i, ¬ signed (chain iv c (view i))) := by
apply Classical.byContradiction
intro h
apply h; left
intro i j
apply Classical.byContradiction
intro hij
apply h; right; left
refine ⟨i, j, ?_, ?_, hij⟩ <;>
exact Classical.byContradiction fun hn => h (Or.inr (Or.inr ⟨_, hn⟩))
/-- Under an honest host all accepted views are pairwise comparable. -/
theorem honest_views_comparable (hc : CollisionFree iv c) {signed : Signed Hd}
{L : List E} (hon : HonestLog iv c signed L) {a b : List E}
(sa : signed (chain iv c a)) (sb : signed (chain iv c b)) : Comparable a b :=
Classical.byContradiction fun nc => fork_evidence_sound hc hon ⟨sa, sb, nc⟩
/-- Reordering: two signed histories of equal length that differ are fork evidence. -/
theorem reorder_evidence {signed : Signed Hd} {a b : List E}
(sa : signed (chain iv c a)) (sb : signed (chain iv c b))
(hne : a ≠ b) (hl : a.length = b.length) : ForkEvidence iv c signed a b :=
⟨sa, sb, not_comparable_of_same_length hne hl⟩
/-- Dropping after a receipt: a signed receipt `r` containing `e`, and a later signed
history `h` at least as long that omits `e`, form fork evidence. -/
theorem drop_evidence {signed : Signed Hd} {r h : List E} {e : E}
(sr : signed (chain iv c r)) (sh : signed (chain iv c h))
(her : e ∈ r) (heh : e ∉ h) (hl : r.length ≤ h.length) :
ForkEvidence iv c signed r h := by
refine ⟨sr, sh, ?_⟩
intro hcmp
cases hcmp with
| inl x => exact heh (ext_mem x her)
| inr x =>
have := ext_eq_of_length x (Nat.le_antisymm (ext_length x) hl)
exact heh (this ▸ her)
end Fork
Rule-breaking: exposed
Rules. A rule is a boolean function valid of the history before an entry and the entry. A history obeys the rules if every entry is valid with respect to the entries older than it. Rule evidence against the host is a signed head of a history that does not obey the rules. A host is rule-abiding if it signs only heads of histories that obey the rules.
Rule evidence is sound and points at one entry. If a history obeys the rules, so does every history it extends. Hence an honest host whose own history obeys the rules is rule-abiding, and under A1 there is no rule evidence against a rule-abiding host. Conversely, a history that breaks the rules has a suffix with .
Proof. The first claim is induction on the newer entries. For soundness, a signed head equals the head of a history that obeys the rules, and by A1 it is that history. The witness is found by scanning from the newest entry: either it is invalid, or the rest of the history breaks the rules and the induction hypothesis applies. ∎
The example rule noReplay forbids an entry that equals an earlier entry. It is used again under alter. Rule evidence is only as sound as the rule is fair to an honest host, so a rule must never be broken by a history that an honest host would build from honest submissions. For noReplay this needs an assumption, because two members could legitimately submit equal entries.
Assumption A4 (unique submissions). No two honestly submitted entries are equal. For example, each entry carries a fresh random nonce, or the sender’s identifier and a per-sender counter, inside the member-key encryption.
Under A4 an honest history has no repeated entry, so it obeys noReplay (the lemma allValid_noReplay_of_nodup), the honest host is rule-abiding for it, and rule evidence under noReplay cannot convict it. Without A4 a host that faithfully stores two equal honest submissions would break noReplay, and the evidence would be unsound.
/-! ## 4. Rules and rule-breaking evidence -/
section Rules
variable {Hd E : Type} (iv : Hd) (c : Hd → E → Hd)
/-- Every entry is permitted by the rule `valid` given the history before it. -/
def allValid (valid : List E → E → Bool) : List E → Bool
| [] => true
| e :: l => valid l e && allValid valid l
/-- Rule evidence: a signed history that breaks the rules. -/
def RuleEvidence (signed : Signed Hd) (valid : List E → E → Bool) (L : List E) : Prop :=
signed (chain iv c L) ∧ allValid valid L = false
/-- A rule-abiding host signs only heads of histories that obey the rules. -/
def RuleAbiding (signed : Signed Hd) (valid : List E → E → Bool) : Prop :=
∀ d, signed d → ∃ l, chain iv c l = d ∧ allValid valid l = true
variable {iv c}
theorem allValid_suffix (valid : List E → E → Bool) :
∀ {a b : List E}, Ext a b → allValid valid b = true → allValid valid a = true := by
intro a b ⟨d, h⟩ hb
subst h
induction d with
| nil => exact hb
| cons x d ih =>
simp only [List.cons_append, allValid, Bool.and_eq_true] at hb
exact ih hb.2
/-- An honest host whose own history obeys the rules is rule-abiding. -/
theorem honest_valid_ruleAbiding {signed : Signed Hd} {valid : List E → E → Bool}
{L : List E} (hon : HonestLog iv c signed L) (hv : allValid valid L = true) :
RuleAbiding iv c signed valid := by
intro d sd
have ⟨l, hl, el⟩ := hon d sd
exact ⟨l, el, allValid_suffix valid hl hv⟩
/-- Soundness: no rule evidence against a rule-abiding host. -/
theorem rule_evidence_sound (hc : CollisionFree iv c) {signed : Signed Hd}
{valid : List E → E → Bool} (hr : RuleAbiding iv c signed valid) {L : List E} :
¬ RuleEvidence iv c signed valid L := by
intro ⟨sL, bad⟩
have ⟨l, el, vl⟩ := hr _ sL
rw [chain_inj hc el] at vl
rw [vl] at bad
exact Bool.noConfusion bad
/-- Localisation: a rule-breaking history contains a specific offending step. -/
theorem violation_witness (valid : List E → E → Bool) :
∀ {L : List E}, allValid valid L = false →
∃ l e, Ext (e :: l) L ∧ valid l e = false
| [], h => Bool.noConfusion h
| e :: l, h => by
cases hv : valid l e with
| false => exact ⟨l, e, ext_refl _, hv⟩
| true =>
simp only [allValid, hv, Bool.true_and] at h
have ⟨l', e', hx, hv'⟩ := violation_witness valid h
exact ⟨l', e', ext_trans hx ⟨[e], rfl⟩, hv'⟩
/-- Example rule: no entry may repeat an earlier entry (forbids replay). -/
def noReplay [BEq E] (l : List E) (e : E) : Bool := !(l.contains e)
/-- Under A4 an honest history has no repeated entry, and then it obeys `noReplay`. -/
theorem allValid_noReplay_of_nodup [DecidableEq E] :
∀ {L : List E}, L.Nodup → allValid noReplay L = true
| [], _ => rfl
| e :: l, h => by
rw [List.nodup_cons] at h
have hc : l.contains e = false := by
cases hx : l.contains e with
| false => rfl
| true => exact absurd (List.mem_of_elem_eq_true hx) h.1
simp only [allValid, noReplay, hc, Bool.not_false, Bool.true_and]
exact allValid_noReplay_of_nodup h.2
example : allValid (noReplay (E := Nat)) [3, 2, 1] = true := by decide
example : allValid (noReplay (E := Nat)) [1, 2, 1] = false := by decide
end Rules
Read and alter: removed
Assumption A3 (symbolic encryption). Messages are atoms, keys, encryptions and pairs. From a set of known messages, an observer derives pairs and their components, encrypts under a key it can derive, and decrypts only with a key it can derive. Some keys are member keys. The host’s knowledge is clean for a secret atom : in every message of , the secret and every member key occur only inside an encryption under a member key.
This is the attacker model of “On the Security of Public Key Protocols” (IEEE Transactions on Information Theory, 1983). It is not a proof of semantic security or of the integrity of any encryption scheme. In particular A3 treats an encryption under a member key as something that cannot be made without the key, which is what authenticated encryption provides computationally.
The host cannot read. If is clean, every message derivable from is clean. In particular neither the secret nor any member key is derivable.
Proof. Induction on the derivation. Pairing and projection preserve cleanness. Encryption of a clean message stays clean. Decryption under key requires to be derivable, hence clean, hence not a member key, and an encryption under a non-member key is clean only if its content is. ∎
The host cannot alter. Let be clean and derivable from . If an encryption under a member key can be reached inside , by unpairing and by opening encryptions under non-member keys, then it can already be reached inside some message of .
Proof. Induction on the derivation of . Pairing and projection move reachability between parts. A new encryption under a member key would need that key, which is not derivable. Decryption needs a derivable key, which is therefore a non-member key, and the reached encryption was reachable inside the ciphertext before decryption. ∎
So the only member-key ciphertexts the host can put into a history are ciphertexts it has already seen. Inserting one a second time is a replay. Under A4 an honest history never repeats an entry, so under the rule noReplay a history with a replayed entry breaks the rules, and that is exposed as above. In the symbolic model encryption is deterministic, which is why A4 places the nonce inside the encryption: equal plaintexts from different submissions then give different ciphertexts.
/-! ## 5. Encryption in a symbolic model -/
section Symbolic
/-- Symbolic messages: atoms, keys, encryptions, pairs. -/
inductive Msg where
| atom (n : Nat)
| key (k : Nat)
| lock (k : Nat) (m : Msg)
| pair (a b : Msg)
/-- What an observer can derive from a set of known messages `S`. -/
inductive Derives (S : Msg → Prop) : Msg → Prop where
| base {m} : S m → Derives S m
| pair {a b} : Derives S a → Derives S b → Derives S (.pair a b)
| fst {a b} : Derives S (.pair a b) → Derives S a
| snd {a b} : Derives S (.pair a b) → Derives S b
| lock {k m} : Derives S (.key k) → Derives S m → Derives S (.lock k m)
| unlock {k m} : Derives S (.lock k m) → Derives S (.key k) → Derives S m
/-- `clean Kh s m`: in `m`, neither the secret atom `s` nor any member key
(`Kh k = true`) appears outside an encryption under a member key. -/
def clean (Kh : Nat → Bool) (s : Nat) : Msg → Bool
| .atom n => n != s
| .key k => !Kh k
| .lock k m => Kh k || clean Kh s m
| .pair a b => clean Kh s a && clean Kh s b
/-- Secrecy invariant: from clean knowledge only clean messages are derivable. -/
theorem derives_clean {Kh : Nat → Bool} {s : Nat} {S : Msg → Prop}
(hS : ∀ m, S m → clean Kh s m = true) {m : Msg} (h : Derives S m) :
clean Kh s m = true := by
induction h with
| base hm => exact hS _ hm
| pair _ _ iha ihb => simp [clean, iha, ihb]
| fst _ ih => simp only [clean, Bool.and_eq_true] at ih; exact ih.1
| snd _ ih => simp only [clean, Bool.and_eq_true] at ih; exact ih.2
| lock _ _ ihk ihm => simp [clean, ihm]
| @unlock k m _ _ ihc ihk =>
simp only [clean, Bool.not_eq_true'] at ihk
simp only [clean, ihk, Bool.false_or] at ihc
exact ihc
/-- The host cannot read: the secret is not derivable. -/
theorem secret_not_derivable {Kh : Nat → Bool} {s : Nat} {S : Msg → Prop}
(hS : ∀ m, S m → clean Kh s m = true) : ¬ Derives S (.atom s) := by
intro h
have := derives_clean hS h
simp [clean] at this
/-- Member keys are not derivable either. -/
theorem key_not_derivable {Kh : Nat → Bool} {s : Nat} {S : Msg → Prop}
(hS : ∀ m, S m → clean Kh s m = true) {k : Nat} (hk : Kh k = true) :
¬ Derives S (.key k) := by
intro h
have := derives_clean hS h
simp [clean, hk] at this
/-- `Reach Kh t x`: `t` can be reached inside `x` by unpairing and by opening
encryptions under non-member keys. -/
inductive Reach (Kh : Nat → Bool) (t : Msg) : Msg → Prop where
| refl : Reach Kh t t
| left {a b} : Reach Kh t a → Reach Kh t (.pair a b)
| right {a b} : Reach Kh t b → Reach Kh t (.pair a b)
| open_ {k m} : Kh k = false → Reach Kh t m → Reach Kh t (.lock k m)
/-- The host cannot alter: every ciphertext under a member key that the host can
produce, or find inside anything it can produce, was already in its knowledge. -/
theorem no_forgery {Kh : Nat → Bool} {s : Nat} {S : Msg → Prop}
(hS : ∀ m, S m → clean Kh s m = true) {x : Msg} (hx : Derives S x) :
∀ k m, Kh k = true → Reach Kh (.lock k m) x → ∃ y, S y ∧ Reach Kh (.lock k m) y := by
induction hx with
| base hy => exact fun _ _ _ r => ⟨_, hy, r⟩
| pair _ _ iha ihb =>
intro k m hk r
cases r with
| left r => exact iha k m hk r
| right r => exact ihb k m hk r
| fst _ ih => exact fun k m hk r => ih k m hk (.left r)
| snd _ ih => exact fun k m hk r => ih k m hk (.right r)
| @lock k' m' hkd _ _ ihm =>
intro k m hk r
cases r with
| refl => exact absurd hkd (key_not_derivable hS hk)
| open_ _ r => exact ihm k m hk r
| @unlock k' m' _ hkd ihc _ =>
intro k m hk r
cases hk' : Kh k' with
| true => exact absurd hkd (key_not_derivable hS hk')
| false => exact ihc k m hk (.open_ hk' r)
end Symbolic
Exclude and disappear: escaped by migration
Migration preserves the history and its verifiability. Under A1:
- a copy whose head equals the last signed head of is itself;
- if a new host’s history has a suffix whose head equals the head of , then ;
- every view satisfies , so no member’s view is invalidated;
- if the old host was honest for and the new host is honest for , then no fork evidence can be formed from signatures of either host.
Proof. (1) and (2) are the injectivity of heads. (3) is transitivity of extension. For (4), every head signed by the old host is the head of a suffix of , hence of . So the union of the two signature sets is honest for , and fork evidence is unsound against it. ∎
A host that refuses one member, or stops answering, therefore takes nothing with it. Any member holding a copy and a signed head can present the history elsewhere, and every other member can check the new host’s history against the head they already hold.
/-! ## 6. Migration -/
section Migration
variable {Hd E : Type} {iv : Hd} {c : Hd → E → Hd}
/-- A copy whose head matches the last signed head is the original history. -/
theorem migrate_faithful (hc : CollisionFree iv c) {L M : List E}
(h : chain iv c M = chain iv c L) : M = L := chain_inj hc h
/-- A new host's history that contains a suffix with the old signed head extends
the old history. -/
theorem migrate_extends (hc : CollisionFree iv c) {L L' l : List E}
(hl : Ext l L') (he : chain iv c l = chain iv c L) : Ext L L' :=
chain_inj hc he ▸ hl
/-- Every view consistent with the old history remains consistent after migration. -/
theorem migrate_views {v L L' : List E} (hv : Ext v L) (hL : Ext L L') : Ext v L' :=
ext_trans hv hL
/-- Combined honesty: if the old host was honest for `L` and the new host is honest for
an extension `L'`, signing under either is honest for `L'`, so no fork evidence
can be built across the migration. -/
theorem migrate_no_fork (hc : CollisionFree iv c) {s₁ s₂ : Signed Hd} {L L' : List E}
(h₁ : HonestLog iv c s₁ L) (h₂ : HonestLog iv c s₂ L') (hL : Ext L L') {a b : List E} :
¬ ForkEvidence iv c (fun d => s₁ d ∨ s₂ d) a b := by
apply fork_evidence_sound hc (L := L')
intro d hd
cases hd with
| inl h =>
have ⟨l, hl, el⟩ := h₁ d h
exact ⟨l, ext_trans hl hL, el⟩
| inr h => exact h₂ d h
end Migration
The limit: withholding from every reader
The general fact behind the limit concerns any verdict that is a function of what can be observed.
Indistinguishability. Let map worlds to observations and be a verdict on observations that is sound: for every honest world . If is honest and , then .
Proof. Rewrite with the equality of observations and apply soundness to . ∎
Host world. A host world consists of the entries received and the list of histories released with signed heads. It is honest if every released history is a suffix of what was received and the full received history has been released. Withholding from world gives the world that received on top of what received and releases exactly what releases.
Total withholding cannot be exposed. If is honest, then withholding any from gives a dishonest world, and every sound verdict on released histories returns false on it.
Proof. The full received history of the new world is one entry longer than anything released, so it was not released, and the world is dishonest. Its releases equal those of the honest world , so indistinguishability applies. ∎
Evidence in the combination above is always made of released signed heads. A host that never signs a head of a history containing , toward anyone, leaves nothing to compare. A receipt is exactly the act that would release such a head. If the host refuses the receipt, the member learns that the entry was not accepted, which is all that can be learnt.
/-! ## 7. The limit: total withholding -/
section Limit
/-- General indistinguishability: a sound verdict, computed only from public
artifacts, cannot convict a world whose artifacts equal those of an honest world. -/
theorem indistinguishable {W A : Type} (obs : W → A) (honest : W → Prop)
(J : A → Bool) (sound : ∀ w, honest w → J (obs w) = false)
{w₁ w₂ : W} (h₂ : honest w₂) (same : obs w₁ = obs w₂) : J (obs w₁) = false := by
rw [same]; exact sound w₂ h₂
variable {E : Type}
/-- A host world: entries received (newest first) and histories released as signed heads. -/
structure HostWorld (E : Type) where
received : List E
released : List (List E)
/-- Honest: every released history is a suffix of what was received, and everything
received has been released. -/
def HostWorld.Honest (w : HostWorld E) : Prop :=
(∀ h ∈ w.released, Ext h w.received) ∧ w.received ∈ w.released
/-- Total withholding of `e` from an honest world `w`: the host received `e` on top
of `w.received` but releases exactly what `w` releases. -/
def withhold (w : HostWorld E) (e : E) : HostWorld E :=
⟨e :: w.received, w.released⟩
theorem withhold_dishonest (w : HostWorld E) (e : E) (hw : w.Honest) :
¬ (withhold w e).Honest := by
intro ⟨_, hmem⟩
have := ext_length (hw.1 _ hmem)
simp [withhold] at this; omega
/-- No sound verdict on released artifacts detects total withholding. -/
theorem withholding_undetectable (J : List (List E) → Bool)
(sound : ∀ w : HostWorld E, w.Honest → J w.released = false)
(w : HostWorld E) (hw : w.Honest) (e : E) :
¬ (withhold w e).Honest ∧ J (withhold w e).released = false :=
⟨withhold_dishonest w e hw,
indistinguishable HostWorld.released HostWorld.Honest J sound hw rfl⟩
end Limit
Coverage
Coverage. Under A1, A2 and A3, for any host, rule and clean host knowledge: the host cannot derive the secret; every member-key ciphertext it can produce can already be reached inside some message of its knowledge; two signed differing histories of equal length are fork evidence, and fork evidence is impossible against an honest host; two incomparable histories have no common extension; a signed receipt containing and a signed history at least as long without are fork evidence; rule evidence localises to one offending entry and is impossible against a rule-abiding host; a migrated copy with matching head is the original and keeps every view consistent; and total withholding of an entry evades every sound verdict on released histories.
Proof. Each conjunct is one of the theorems above. ∎
The concrete checks at the end compute heads with a small compression function on natural numbers, one built from the standard triangular pairing of naturals, . Its injectivity is not proved in the file, and it is used only to evaluate examples, never as an instance of A1.
/-! ## 8. Coverage -/
section Coverage
variable {Hd E : Type} {iv : Hd} {c : Hd → E → Hd}
/-- Coverage: under the idealised assumptions, each host power is impossible,
yields transferable evidence, or is escaped by migration, under the conditions
stated in each conjunct; total withholding provably leaves no evidence. -/
theorem coverage (hc : CollisionFree iv c) (signed : Signed Hd)
(valid : List E → E → Bool) (Kh : Nat → Bool) (s : Nat) (S : Msg → Prop)
(hS : ∀ m, S m → clean Kh s m = true) :
-- read: impossible
(¬ Derives S (.atom s)) ∧
-- alter: impossible (only replay of seen ciphertexts, which a rule can forbid)
(∀ x k m, Derives S x → Kh k = true → Reach Kh (.lock k m) x →
∃ y, S y ∧ Reach Kh (.lock k m) y) ∧
-- reorder / fork: evidence, and evidence is sound
(∀ a b : List E, signed (chain iv c a) → signed (chain iv c b) →
a ≠ b → a.length = b.length → ForkEvidence iv c signed a b) ∧
(∀ L a b : List E, HonestLog iv c signed L → ¬ ForkEvidence iv c signed a b) ∧
(∀ a b L : List E, ¬ Comparable a b → ¬ (Ext a L ∧ Ext b L)) ∧
-- drop after receipt: evidence
(∀ (r h : List E) (e : E), signed (chain iv c r) → signed (chain iv c h) →
e ∈ r → e ∉ h → r.length ≤ h.length → ForkEvidence iv c signed r h) ∧
-- rule-breaking: evidence, localised, and sound
(∀ L : List E, RuleEvidence iv c signed valid L →
∃ l e, Ext (e :: l) L ∧ valid l e = false) ∧
(RuleAbiding iv c signed valid → ∀ L, ¬ RuleEvidence iv c signed valid L) ∧
-- exclude / disappear: a migrated copy is faithful and keeps every view consistent
(∀ L M : List E, chain iv c M = chain iv c L → M = L) ∧
(∀ v L L' : List E, Ext v L → Ext L L' → Ext v L') ∧
-- limit: total withholding from every reader evades every sound verdict
(∀ (J : List (List E) → Bool), (∀ w : HostWorld E, w.Honest → J w.released = false) →
∀ (w : HostWorld E), w.Honest → ∀ e : E,
¬ (withhold w e).Honest ∧ J (withhold w e).released = false) :=
⟨secret_not_derivable hS,
fun _ k m hx hk r => no_forgery hS hx k m hk r,
fun _ _ sa sb hne hl => reorder_evidence sa sb hne hl,
fun _ _ _ hon => fork_evidence_sound hc hon,
fun _ _ L h => fork_no_join h L,
fun _ _ _ sr sh her heh hl => drop_evidence sr sh her heh hl,
fun _ ⟨_, bad⟩ => violation_witness valid bad,
fun hr _ => rule_evidence_sound hc hr,
fun _ _ h => migrate_faithful hc h,
fun _ _ _ hv hL => migrate_views hv hL,
fun J sound w hw e => withholding_undetectable J sound w hw e⟩
end Coverage
/-! ## 9. A concrete check -/
/-- A toy compression on naturals (the triangular pairing of naturals, shifted by one). -/
def toyC (x e : Nat) : Nat := (x + e) * (x + e + 1) / 2 + e + 1
example : chain 0 toyC [2, 1] ≠ chain 0 toyC [1, 2] := by decide
example : ¬ Comparable [2, 1] [1, 2] := by decide
example : Comparable [3, 2, 1] [1] := by decide
end HostPowers
Limits and assumptions
- Symbolic model only. Every theorem holds in the idealised model: an injective compression function (A1), signatures as a predicate (A2), and symbolic free-algebra encryption (A3), together with unique submissions (A4). Nothing here is a computational proof. Collision resistance, unforgeability under chosen-message attack and authenticated encryption are assumptions, and the reductions from them to the statements above are not carried out.
- Separate models. The coverage theorem is a conjunction over shared parameters. The history model and the message model are linked informally, by reading log entries as ciphertexts. There is no single execution semantics in which the host acts and all properties are proved about the same run.
- Evidence needs exchange. Fork evidence exists only once two incomparable views are in one place. Members who never exchange heads can be kept on diverging histories indefinitely. Exchange is modelled only as pooling views, not as a protocol with its own timing.
- Freshness is not covered; this is the second limit. A host can give one member a receipt for and serve another member a strictly shorter, stale prefix without , for ever.
drop_evidencerequires the later history to be at least as long as the receipt, so a stale view gives no evidence, and the stale member is never alerted to migrate. Toward that member this is a drop and an exclusion that the combination does not expose. Bounding staleness needs time, for example signed heads with timestamps, which the model does not have. - Total withholding is the proved limit. The
HostWorldhonesty in that theorem is “every received entry appears in a released head”. It is narrower thanHonestLogand not formally tied to it. The general statement isindistinguishable, which holds for any observation function and any notion of honesty. - Who can check the rules.
validis taken as given. Only parties holding the history, and able to evaluate the rule on it, can produce rule evidence. If the rule needs plaintext, that means members, and whether non-members could check rules over ciphertexts is not modelled. - Replay and delay. The host can still insert a ciphertext it has seen.
noReplayturns a repeated entry into a rule violation, but an entry the host received and held back can be released late. That is delayed delivery, a weaker form of withholding, and it is not exposed. - Migration needs a copy and a new host. Escaping exclusion or disappearance needs at least one member who holds the history and its last signed head, and a new host willing to serve it. Agreement among members on which new host to use is not modelled.
#print axioms reports no axioms for chain_inj, rule_evidence_sound, migrate_faithful and migrate_extends; only propext for no_forgery, fork_evidence_sound, fork_no_join, fork_persists, violation_witness, allValid_noReplay_of_nodup and migrate_no_fork; propext and Quot.sound for withholding_undetectable; and propext, Classical.choice and Quot.sound for views_trichotomy, honest_views_comparable, ext_eq_of_length, not_comparable_of_same_length, reorder_evidence, drop_evidence and coverage. In views_trichotomy and honest_views_comparable the classical axioms come from the explicit case split by contradiction. In coverage they come from the length lemma ext_eq_of_length, whose simp and omega steps introduce them, through not_comparable_of_same_length, reorder_evidence and drop_evidence.
Prior work
Fork consistency for untrusted storage was introduced in “Building Secure File Systems out of Byzantine Storage” (PODC 2002), and its limits and variants are studied in “Fork Sequential Consistency is Blocking” (Information Processing Letters, 2009) and “Fail-Aware Untrusted Storage” (DSN 2009; SIAM Journal on Computing, 2011). Tamper-evident logs and their proofs of extension are in “Efficient Data Structures for Tamper-Evident Logging” (USENIX Security 2009), and exchange of log heads between observers in “Efficient Gossip Protocols for Verifying the Consistency of Certificate Logs” (IEEE Conference on Communications and Network Security, 2015), building on “Epidemic Algorithms for Replicated Database Maintenance” (PODC 1987). Hash chains and signatures: “How to Time-Stamp a Digital Document” (Journal of Cryptology, 1991), “A Design Principle for Hash Functions” (CRYPTO 1989) and “A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks” (SIAM Journal on Computing, 1988). Symbolic analysis of encryption: “On the Security of Public Key Protocols” (IEEE Transactions on Information Theory, 1983), and for its computational soundness “Reconciling Two Views of Cryptography (The Computational Soundness of Formal Encryption)” (Journal of Cryptology, 2002). Authenticated encryption: “Authenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm” (ASIACRYPT 2000). Deterministic replay of rules: “Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial” (ACM Computing Surveys, 1990). Self-certifying names: “Separating Key Management from File System Security” (SOSP 1999).