An operator keeps an append-only log of entries, and alongside it a table of rows (key, value pairs) that the log produces. From time to time the operator publishes a short signed message, a signed tree head: the size of the log, a digest of the log, the size of the table and a digest of the table. Someone outside, who has never seen the log, holds only the operator’s public key. They are handed a signed head and a short proof. From these alone they want to conclude that an entry is in the log, that a row is in the table, or that the log behind a newer head extends the log behind an older one.
This article states that goal precisely, puts together standard components that reach it, and proves that the combination does reach it. None of the components is new. What is shown is that, wired together this way, they give the outsider exactly the guarantees claimed, under assumptions that are written down as hypotheses.
The goal
There are three parties: an operator, who holds a signing key and the data; an outsider, who holds only the operator’s public key ; and a prover, who may be anyone and is not trusted. The prover hands the outsider a signed head and a proof. The outsider runs a deterministic check and accepts or rejects.
Goal. Give a judgement on signed heads and three proof checkers, all computable by the outsider from , the signed heads and the proof, with these properties.
- Completeness. For every log and every entry in it, the honest proof is accepted against the honest head. The same holds for every row of the table, and for every pair of an older and a newer size of the same log.
- Head soundness. A signed head is accepted only if a valid signature under covers every field of the head. If the signature scheme is unforgeable and the operator signs only heads of real (log, table) pairs, an accepted head is the head of some real pair.
- Proof soundness. If a head and an inclusion proof for entry at index are accepted, then really is entry of the log behind the head. The same holds for rows, and for consistency: if two heads and a consistency proof between them are accepted, the older log is a prefix of the newer one.
Soundness is stated relative to the hash function. Each proof-soundness theorem (item 3) has the form “the claim holds, or a collision of is exhibited”, and the collision is computed by an explicit function from the honest data and the proof.
The last sentence is how collision resistance enters. No assumption that is injective is made anywhere, since no real hash function is injective. Instead, each theorem says that a false accepted proof can be turned into a concrete collision. Anyone who believes collisions are infeasible to find then believes the claim. This way of stating security for a keyless hash follows the treatment of collision resistance as explicit reduction cited in the prior work.
The components
Each part is standard. They are listed with the work they come from (full list under Prior work).
- Merkle tree hashing (A Digital Signature Based on a Conventional Encryption Function, CRYPTO 1987). A list of entries is committed to by one digest, computed bottom-up through a binary tree.
- The RFC 6962 tree shape and domain separation (Certificate Transparency, IETF RFC 6962, 2013). A list of any length is split at the largest power of two strictly below . Leaves are hashed with a prefix 0 and interior nodes with a prefix 1. The same document gives the honest inclusion proof (PATH) and consistency proof (SUBPROOF).
- Append-only logs with proofs between versions (Efficient Data Structures for Tamper-Evident Logging, USENIX Security 2009). A history tree whose commitments at different sizes can be linked by short proofs.
- Unforgeable signatures (A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks, SIAM Journal on Computing 1988). Used here only through an idealised hypothesis, stated below.
- Security of a keyless hash as collision extraction (Formalizing Human Ignorance: Collision-Resistant Hashing without the Keys, VIETCRYPT 2006). A fixed hash function has collisions, so the security statement is a reduction that exhibits one.
The combination
- judgesigned head
key = pk ∧ verify(pk, encode(head), sig) - readhead fields
(size, logRoot, stateSize, stateRoot) - checkinclusion, row or consistency proof
recompute a root, compare - concludeclaim, or a collision
The pieces are wired as follows.
- The log is a list of entries . Its digest is the RFC 6962 tree hash .
- The table is a list of rows . Each row becomes the leaf , and the table’s digest is the tree hash of the list of these leaves. A row proof is an inclusion proof for that leaf.
- A head is the tuple . The signed message is an injective encoding of all four fields, with its own domain tag 2, so it can never be read as a leaf (tag 0) or a node (tag 1).
- The outsider accepts a signed head if its stated key is and the signature verifies under on the encoding. Every proof is then checked against the size and digest read from the accepted head.
The rest of the article defines these pieces in Lean and proves the three goal properties. The Lean blocks below, read in order, form one file for Lean 4 with no libraries beyond the core. It compiles with no sorry, no admit and no added axiom.
Definitions
Words, hash functions and collisions
Messages and digests are finite words over (bytes in practice). A hash function is any function from words to words whose outputs all have the same length . Fixed width is a functional property, like a 256-bit output, not a security assumption.
Collision. A pair with and .
Extractor. For a finite list of candidate pairs, returns the first pair in that is a collision of , or nothing.
Every soundness proof below follows one pattern. It names a list of candidate pairs, built from the honest data and the proof, and shows that the claim follows if no pair in collides. Lemma 1 turns that into “claim, or returns a collision”.
Lemma 1 (extraction). If returns , then is a collision and . If it returns nothing, no pair in collides. Hence, for every proposition : if follows from “no pair in collides”, then holds or returns a collision.
/-
Verifiable logs from a signed tree head.
Self-contained core Lean 4 (no libraries). Cryptographic assumptions are
hypotheses, never axioms: every soundness theorem either reaches its
conclusion or hands back an explicit collision of the hash function.
-/
set_option linter.unusedVariables false
/-! ## 1. Words, hash functions, collisions -/
/-- Messages and digests are finite words over ℕ (bytes, in practice). -/
abbrev Word := List Nat
/-- An abstract hash function with a fixed output width. The width is a
functional property of the function (like 32 bytes for a 256-bit hash),
not a security assumption. -/
structure Hash where
h : Word → Word
w : Nat
width : ∀ m, (h m).length = w
/-- A collision: two distinct messages with the same digest. -/
def Hash.IsCollision (H : Hash) (c : Word × Word) : Prop :=
c.1 ≠ c.2 ∧ H.h c.1 = H.h c.2
/-- `H` has no collision among the listed candidate pairs. -/
def NoCollIn (H : Hash) (ps : List (Word × Word)) : Prop :=
∀ a b, (a, b) ∈ ps → H.h a = H.h b → a = b
/-- The extractor: scan candidate pairs and return the first collision. -/
def firstCollision (H : Hash) : List (Word × Word) → Option (Word × Word)
| [] => none
| (a, b) :: rest =>
if a ≠ b ∧ H.h a = H.h b then some (a, b) else firstCollision H rest
theorem firstCollision_some (H : Hash) :
∀ {ps : List (Word × Word)} {c : Word × Word},
firstCollision H ps = some c → H.IsCollision c ∧ c ∈ ps
| [], c, h => by simp [firstCollision] at h
| (a, b) :: rest, c, h => by
simp only [firstCollision] at h
split at h
· rename_i hc
cases h
exact ⟨hc, List.mem_cons_self _ _⟩
· have := firstCollision_some H h
exact ⟨this.1, List.mem_cons_of_mem _ this.2⟩
theorem firstCollision_none (H : Hash) :
∀ {ps : List (Word × Word)}, firstCollision H ps = none → NoCollIn H ps
| [], _ => by intro a b hm; simp at hm
| (a, b) :: rest, h => by
simp only [firstCollision] at h
split at h
· cases h
· rename_i hc
intro x y hm hxy
rcases List.mem_cons.mp hm with he | hm
· cases he
exact Decidable.byContradiction (fun hne => hc ⟨hne, hxy⟩)
· exact firstCollision_none H h x y hm hxy
/-- Reduction pattern: if `P` follows from collision-freeness on `ps`, then
either `P` holds or the extractor returns a genuine collision. -/
theorem extract (H : Hash) (ps : List (Word × Word)) {P : Prop}
(hP : NoCollIn H ps → P) :
P ∨ ∃ c, firstCollision H ps = some c ∧ H.IsCollision c := by
cases hfc : firstCollision H ps with
| none => exact Or.inl (hP (firstCollision_none H hfc))
| some c => exact Or.inr ⟨c, rfl, (firstCollision_some H hfc).1⟩
theorem NoCollIn.tail {H : Hash} {p : Word × Word} {ps : List (Word × Word)}
(h : NoCollIn H (p :: ps)) : NoCollIn H ps :=
fun a b hm => h a b (List.mem_cons_of_mem _ hm)
theorem NoCollIn.left {H : Hash} {ps qs : List (Word × Word)}
(h : NoCollIn H (ps ++ qs)) : NoCollIn H ps :=
fun a b hm => h a b (List.mem_append_left _ hm)
theorem NoCollIn.right {H : Hash} {ps qs : List (Word × Word)}
(h : NoCollIn H (ps ++ qs)) : NoCollIn H qs :=
fun a b hm => h a b (List.mem_append_right _ hm)
Domain separation
Leaf and node messages. and . The leaf hash is and the node hash is .
Lemma 2 (domain separation). For all : . Consequently, a leaf hash that equals a node hash is itself a collision, namely .
Proof. The first symbols differ. ∎
Without the prefixes, an interior node could be presented as a leaf whose data is , and a proof could stop one level early. With them, any such confusion is a collision. The two injectivity lemmas for node messages need the length of one side to be known; that is where the fixed width is used.
/-! ## 2. Domain-separated tree hashing -/
def leafMsg (d : Word) : Word := 0 :: d
def nodeMsg (a b : Word) : Word := 1 :: (a ++ b)
def leafH (H : Hash) (d : Word) : Word := H.h (leafMsg d)
def nodeH (H : Hash) (a b : Word) : Word := H.h (nodeMsg a b)
/-- Domain separation: no leaf message is a node message. -/
theorem domain_separation (d a b : Word) : leafMsg d ≠ nodeMsg a b := by
simp [leafMsg, nodeMsg]
/-- Hence a leaf hash equal to a node hash is itself a collision. -/
theorem leaf_node_confusion (H : Hash) (d a b : Word)
(h : leafH H d = nodeH H a b) : H.IsCollision (leafMsg d, nodeMsg a b) :=
⟨domain_separation d a b, h⟩
theorem leafMsg_inj {a b : Word} (h : leafMsg a = leafMsg b) : a = b := by
simpa [leafMsg] using h
theorem nodeMsg_inj_left {a b c d : Word} (h : nodeMsg a b = nodeMsg c d)
(hl : a.length = c.length) : a = c ∧ b = d := by
simp only [nodeMsg, List.cons.injEq, true_and] at h
exact List.append_inj h hl
theorem nodeMsg_inj_right {a b c d : Word} (h : nodeMsg a b = nodeMsg c d)
(hl : b.length = d.length) : a = c ∧ b = d := by
simp only [nodeMsg, List.cons.injEq, true_and] at h
exact List.append_inj' h hl
The split point
For , let , the largest power of two strictly below . This is the split of RFC 6962.
Lemma 3 (split). For : . Moreover, if , then .
The second part is what makes consistency proofs work. A prefix of length that reaches past the split of is split at the same place, so its left subtree is the same complete subtree as in the larger tree.
/-! ## 3. The split point: largest power of two strictly below `n` -/
def cut (n : Nat) : Nat := 2 ^ Nat.log2 (n - 1)
theorem cut_bounds {n : Nat} (hn : 2 ≤ n) :
1 ≤ cut n ∧ cut n < n ∧ n ≤ 2 * cut n := by
have h1 := @Nat.log2_self_le (n - 1) (by omega)
have h2 := @Nat.lt_log2_self (n - 1)
have h3 := Nat.two_pow_pos (Nat.log2 (n - 1))
rw [Nat.pow_succ] at h2
unfold cut
omega
/-- If `cut n < m ≤ n` then `m` splits at the same point as `n`. -/
theorem cut_eq {n m : Nat} (hn : 2 ≤ n) (hk : cut n < m) (hm : m ≤ n) :
cut m = cut n := by
unfold cut at *
have a1 := @Nat.log2_self_le (n - 1) (by omega)
have a2 := @Nat.lt_log2_self (n - 1)
have a3 := Nat.two_pow_pos (Nat.log2 (n - 1))
have hm1 : m - 1 ≠ 0 := by omega
have b1 := Nat.log2_self_le hm1
have b2 := @Nat.lt_log2_self (m - 1)
rcases Nat.lt_trichotomy (Nat.log2 (m - 1)) (Nat.log2 (n - 1)) with h | h | h
· have := Nat.pow_le_pow_right (show 2 > 0 by decide)
(show Nat.log2 (m - 1) + 1 ≤ Nat.log2 (n - 1) by omega)
omega
· rw [h]
· have := Nat.pow_le_pow_right (show 2 > 0 by decide)
(show Nat.log2 (n - 1) + 1 ≤ Nat.log2 (m - 1) by omega)
omega
The tree hash
Merkle tree hash (RFC 6962). For a list :
Every tree hash has width , because the last step is always a call to . The lemma mth_take_split is Lemma 3 applied to the tree: for , the tree hash of the first entries is a node whose left child is the left subtree of the full tree.
/-! ## 4. The Merkle tree hash -/
def mth (H : Hash) (l : List Word) : Word :=
if h2 : 2 ≤ l.length then
nodeH H (mth H (l.take (cut l.length))) (mth H (l.drop (cut l.length)))
else
match l with
| [d] => leafH H d
| _ => H.h []
termination_by l.length
decreasing_by
all_goals simp_wf
all_goals have := cut_bounds h2
all_goals omega
theorem mth_node (H : Hash) {l : List Word} (h2 : 2 ≤ l.length) :
mth H l = nodeH H (mth H (l.take (cut l.length))) (mth H (l.drop (cut l.length))) := by
rw [mth, dif_pos h2]
theorem mth_single (H : Hash) (d : Word) : mth H [d] = leafH H d := by
rw [mth]; simp
theorem mth_len (H : Hash) (l : List Word) : (mth H l).length = H.w := by
rw [mth]
split
· exact H.width _
· split
· exact H.width _
· exact H.width _
theorem len_take_cut {l : List Word} (h2 : 2 ≤ l.length) :
(l.take (cut l.length)).length = cut l.length := by
have := cut_bounds h2
rw [List.length_take]; omega
/-- Splitting a prefix of length `m > cut n` uses the same split point. -/
theorem mth_take_split (H : Hash) {l : List Word} {m : Nat} (h2 : 2 ≤ l.length)
(hk : cut l.length < m) (hm : m ≤ l.length) :
mth H (l.take m) =
nodeH H (mth H (l.take (cut l.length)))
(mth H ((l.drop (cut l.length)).take (m - cut l.length))) := by
have hb := cut_bounds h2
have hlen : (l.take m).length = m := by rw [List.length_take]; omega
have hm2 : 2 ≤ (l.take m).length := by omega
rw [mth_node H hm2, hlen, cut_eq h2 hk hm, List.take_take,
Nat.min_eq_left (by omega), List.drop_take]
Theorems: the combination achieves the goal
Inclusion
A proof is a list of sibling digests, listed from the root side down (RFC 6962 sends them leaf side first; only the order differs). The verifier for index in a tree of size walks down the same splits as the tree hash. The shape check confirms that the proof has exactly one digest per level of the path to leaf and that . The climb recomputes a root from the leaf hash of the claimed entry and the siblings.
Inclusion verifier. accepts if has the shape of the path to leaf in a tree of size , and the root recomputed from and equals .
Honest proof. : at each split, the tree hash of the subtree not containing , then recurse into the one that does.
Candidate pairs. At each level, the pair (node message the verifier hashed, node message the honest tree hashed there); at the bottom, (leaf of , leaf of the honest entry).
/-! ## 5. Inclusion proofs
A proof is listed root side first (RFC 6962 transmits the reverse order). -/
/-- Recompute a root from a leaf digest `x` at index `m` in a tree of size `n`. -/
def climb (H : Hash) : Nat → Nat → Word → List Word → Word
| _, _, x, [] => x
| m, n, x, s :: p =>
if m < cut n then nodeH H (climb H m (cut n) x p) s
else nodeH H s (climb H (m - cut n) (n - cut n) x p)
/-- The proof has exactly the shape of the path to leaf `m` of a size-`n` tree. -/
def shapeOK : Nat → Nat → List Word → Bool
| m, n, [] => n == 1 && m == 0
| m, n, _ :: p =>
decide (2 ≤ n) &&
(if m < cut n then shapeOK m (cut n) p else shapeOK (m - cut n) (n - cut n) p)
def verifyIncl (H : Hash) (m n : Nat) (d : Word) (p : List Word) (root : Word) : Bool :=
shapeOK m n p && climb H m n (leafH H d) p == root
/-- The honest proof. -/
def inclPath (H : Hash) (l : List Word) (m : Nat) : List Word :=
if h2 : 2 ≤ l.length then
if m < cut l.length then
mth H (l.drop (cut l.length)) :: inclPath H (l.take (cut l.length)) m
else
mth H (l.take (cut l.length)) :: inclPath H (l.drop (cut l.length)) (m - cut l.length)
else []
termination_by l.length
decreasing_by
all_goals simp_wf
all_goals have := cut_bounds h2
all_goals omega
/-- Candidate pairs: claimed versus honest preimage at every level. -/
def inclPairs (H : Hash) : List Word → Nat → Word → List Word → List (Word × Word)
| l, _, d, [] => [(leafMsg d, leafMsg (l.headD []))]
| l, m, d, s :: p =>
if m < cut l.length then
(nodeMsg (climb H m (cut l.length) (leafH H d) p) s,
nodeMsg (mth H (l.take (cut l.length))) (mth H (l.drop (cut l.length)))) ::
inclPairs H (l.take (cut l.length)) m d p
else
(nodeMsg s (climb H (m - cut l.length) (l.length - cut l.length) (leafH H d) p),
nodeMsg (mth H (l.take (cut l.length))) (mth H (l.drop (cut l.length)))) ::
inclPairs H (l.drop (cut l.length)) (m - cut l.length) d p
Theorem 1 (inclusion). Let be a log.
- Completeness. If , then accepts.
- Soundness. If accepts for any , then , or returns a collision of .
Proof sketch. Completeness is by strong induction on : the honest sibling at each level is exactly the other child in the definition of . For soundness, assume no candidate pair collides and induct on . At the top, the recomputed root equals , which is the hash of the honest node message. The candidate pair at this level is (claimed node message, honest node message), with equal hashes, so the two messages are equal. Both children have width , so the node message splits uniquely, and the child on ‘s side of the claimed message equals the honest subtree hash. Recurse into that subtree. At the bottom, the leaf messages are equal, so is the honest entry. Lemma 1 turns this into the stated disjunction. ∎
theorem climb_len (H : Hash) : ∀ (p : List Word) (m n : Nat) (x : Word),
x.length = H.w → (climb H m n x p).length = H.w
| [], _, _, _, hx => hx
| s :: p, m, n, x, _ => by
simp only [climb]; split
· exact H.width _
· exact H.width _
theorem incl_core (H : Hash) : ∀ (p l : List Word) (m : Nat) (d : Word),
shapeOK m l.length p = true → climb H m l.length (leafH H d) p = mth H l →
NoCollIn H (inclPairs H l m d p) → l[m]? = some d
| [], l, m, d, hs, hc, hn => by
simp only [shapeOK, Bool.and_eq_true, beq_iff_eq] at hs
obtain ⟨h1, rfl⟩ := hs
match l, h1 with
| [y], _ =>
simp only [climb, mth_single] at hc
have hd := leafMsg_inj (hn _ _ (by simp [inclPairs]) hc)
subst hd; rfl
| s :: p, l, m, d, hs, hc, hn => by
simp only [shapeOK, Bool.and_eq_true, decide_eq_true_eq] at hs
obtain ⟨h2, hs⟩ := hs
have hb := cut_bounds h2
have ht := len_take_cut h2
rw [mth_node H h2] at hc
simp only [climb] at hc
simp only [inclPairs] at hn
split at hs
· rename_i hlt
rw [if_pos hlt] at hc hn
have hpair := hn _ _ (List.mem_cons_self _ _) hc
have he := nodeMsg_inj_left hpair
(by rw [climb_len H p _ _ (leafH H d) (H.width _), mth_len])
have ih := incl_core H p (l.take (cut l.length)) m d
(by rw [ht]; exact hs) (by rw [ht]; exact he.1) hn.tail
rw [List.getElem?_take_of_lt hlt] at ih
exact ih
· rename_i hlt
rw [if_neg hlt] at hc hn
have hpair := hn _ _ (List.mem_cons_self _ _) hc
have he := nodeMsg_inj_right hpair
(by rw [climb_len H p _ _ (leafH H d) (H.width _), mth_len])
have ih := incl_core H p (l.drop (cut l.length)) (m - cut l.length) d
(by rw [List.length_drop]; exact hs) (by rw [List.length_drop]; exact he.2) hn.tail
rw [List.getElem?_drop, show cut l.length + (m - cut l.length) = m by omega] at ih
exact ih
theorem incl_complete_core (H : Hash) : ∀ (n : Nat) (l : List Word) (m : Nat) (d : Word),
l.length = n → l[m]? = some d →
shapeOK m n (inclPath H l m) = true ∧ climb H m n (leafH H d) (inclPath H l m) = mth H l := by
intro n
induction n using Nat.strongRecOn with
| ind n ih =>
intro l m d hl hm
subst hl
by_cases h2 : 2 ≤ l.length
· have hb := cut_bounds h2
have ht := len_take_cut h2
rw [inclPath, dif_pos h2]
split
· rename_i hlt
obtain ⟨hs, hc⟩ := ih (cut l.length) hb.2.1 (l.take (cut l.length)) m d ht
(by rw [List.getElem?_take_of_lt hlt]; exact hm)
simp only [shapeOK, climb, if_pos hlt]
rw [mth_node H h2, hc]
simp [h2, hs]
· rename_i hlt
obtain ⟨hs, hc⟩ := ih (l.length - cut l.length) (by omega) (l.drop (cut l.length))
(m - cut l.length) d (List.length_drop _ _)
(by rw [List.getElem?_drop, show cut l.length + (m - cut l.length) = m by omega]; exact hm)
simp only [shapeOK, climb, if_neg hlt]
rw [mth_node H h2, hc]
simp [h2, hs]
· rw [inclPath, dif_neg h2]
rcases l with _ | ⟨y, _ | ⟨z, t⟩⟩
· simp at hm
· cases m with
| zero =>
simp at hm; subst hm
simp [shapeOK, climb, mth_single]
| succ k => simp at hm
· simp at h2
/-- **Inclusion, completeness.** The honest proof is always accepted. -/
theorem inclusion_complete (H : Hash) (l : List Word) (m : Nat) (d : Word)
(hm : l[m]? = some d) :
verifyIncl H m l.length d (inclPath H l m) (mth H l) = true := by
obtain ⟨hs, hc⟩ := incl_complete_core H l.length l m d rfl hm
simp [verifyIncl, hs, hc]
/-- **Inclusion, soundness.** An accepted proof places `d` at index `m`,
unless the extractor returns a collision of `H`. -/
theorem inclusion_sound (H : Hash) (l p : List Word) (m : Nat) (d : Word)
(hv : verifyIncl H m l.length d p (mth H l) = true) :
l[m]? = some d ∨
∃ c, firstCollision H (inclPairs H l m d p) = some c ∧ H.IsCollision c := by
simp only [verifyIncl, Bool.and_eq_true, beq_iff_eq] at hv
exact extract H _ (incl_core H p l m d hv.1 hv.2)
Consistency
A consistency proof links an old size with old root to a new size with new root . The verifier recomputes two roots from the same proof, one for the old tree and one for the new tree, and accepts if they are and . It follows the recursion of RFC 6962’s SUBPROOF: while fits in the left subtree, only the new root gains a right sibling; once reaches past the split, the left subtree is complete and shared, and both roots gain it as a left sibling. The flag records whether the old subtree reached at the bottom is the whole old tree. If so, its root is , which the verifier already holds, and the proof stops there. If not, the proof supplies it.
Consistency verifier. accepts if , every digest in has width , and the pair of roots recomputed from is .
Honest proof. , RFC 6962 SUBPROOF, root side first.
/-! ## 6. Consistency proofs -/
/-- From a proof, recompute the pair (old subtree root, new subtree root).
`b` records that the old subtree is the whole old tree, whose root `r1`
the verifier already holds. -/
def consRoots (H : Hash) (r1 : Word) : Nat → Nat → Bool → List Word → Option (Word × Word)
| m, n, b, [] => if m = n ∧ b = true then some (r1, r1) else none
| m, n, b, s :: p =>
if m = n then (if b = false ∧ p = [] then some (s, s) else none)
else if m < n then
if m ≤ cut n then
(consRoots H r1 m (cut n) b p).map (fun r => (r.1, nodeH H r.2 s))
else
(consRoots H r1 (m - cut n) (n - cut n) false p).map
(fun r => (nodeH H s r.1, nodeH H s r.2))
else none
def verifyCons (H : Hash) (m n : Nat) (r1 r2 : Word) (p : List Word) : Bool :=
decide (0 < m) && decide (m ≤ n) && p.all (fun s => s.length == H.w) &&
consRoots H r1 m n true p == some (r1, r2)
/-- The honest proof (RFC 6962 `SUBPROOF`, root side first). -/
def subproof (H : Hash) (l : List Word) (m : Nat) (b : Bool) : List Word :=
if m = l.length then (if b then [] else [mth H l])
else if h2 : 2 ≤ l.length then
if m ≤ cut l.length then
mth H (l.drop (cut l.length)) :: subproof H (l.take (cut l.length)) m b
else
mth H (l.take (cut l.length)) :: subproof H (l.drop (cut l.length)) (m - cut l.length) false
else []
termination_by l.length
decreasing_by
all_goals simp_wf
all_goals have := cut_bounds h2
all_goals omega
/-- Second component of an optional pair (default: empty word). -/
def sndD (o : Option (Word × Word)) : Word := (o.map Prod.snd).getD []
def consPairs (H : Hash) (r1 : Word) : List Word → Nat → Bool → List Word → List (Word × Word)
| _, _, _, [] => []
| l, m, b, s :: p =>
if m ≤ cut l.length then
(nodeMsg (sndD (consRoots H r1 m (cut l.length) b p)) s,
nodeMsg (mth H (l.take (cut l.length))) (mth H (l.drop (cut l.length)))) ::
consPairs H r1 (l.take (cut l.length)) m b p
else
(nodeMsg s (sndD (consRoots H r1 (m - cut l.length) (l.length - cut l.length) false p)),
nodeMsg (mth H (l.take (cut l.length))) (mth H (l.drop (cut l.length)))) ::
consPairs H r1 (l.drop (cut l.length)) (m - cut l.length) false p
Theorem 2 (consistency). Let be a log and .
- Completeness. accepts.
- Soundness. If accepts for any and , then , or returns a collision.
Proof sketch. Induction on , as for Theorem 1, but tracking both roots. When , matching the new root against the honest node pins the right sibling to the honest right subtree hash and the recomputed new root of the left part to the honest left subtree hash; recurse left. When , it pins the left sibling to the honest left subtree hash; by Lemma 3 the old prefix splits at the same point, so its root is a node over that same left subtree, and recurse right. At the bottom, either the flag says the old subtree is the whole old tree, whose root is , or the proof’s single remaining digest is both old and new subtree root. The width check on proof digests is what lets each node message split uniquely, since the sibling is taken from the proof rather than recomputed. ∎
theorem cons_core (H : Hash) (r1 : Word) : ∀ (p l : List Word) (m : Nat) (b : Bool) (o nw : Word),
0 < m → m ≤ l.length → (∀ s ∈ p, s.length = H.w) →
consRoots H r1 m l.length b p = some (o, nw) → nw = mth H l →
NoCollIn H (consPairs H r1 l m b p) → o = mth H (l.take m)
| [], l, m, b, o, nw, _, _, _, hc, hnw, _ => by
simp only [consRoots] at hc
split at hc
· rename_i h
obtain ⟨rfl, _⟩ := h
simp only [Option.some.injEq, Prod.mk.injEq] at hc
obtain ⟨rfl, rfl⟩ := hc
rw [List.take_of_length_le (Nat.le_refl _)]; exact hnw
· cases hc
| s :: p, l, m, b, o, nw, hm0, hmn, hw, hc, hnw, hn => by
simp only [consRoots] at hc
by_cases heq : m = l.length
· rw [if_pos heq] at hc
split at hc
· simp only [Option.some.injEq, Prod.mk.injEq] at hc
obtain ⟨rfl, rfl⟩ := hc
rw [heq, List.take_of_length_le (Nat.le_refl _)]; exact hnw
· cases hc
· rw [if_neg heq, if_pos (by omega : m < l.length)] at hc
have h2 : 2 ≤ l.length := by omega
have hb := cut_bounds h2
have ht := len_take_cut h2
rw [mth_node H h2] at hnw
simp only [consPairs] at hn
have hs : s.length = H.w := hw s (List.mem_cons_self _ _)
have hw' : ∀ x ∈ p, x.length = H.w := fun x hx => hw x (List.mem_cons_of_mem _ hx)
split at hc
· rename_i hle
rw [if_pos hle] at hn
cases hr : consRoots H r1 m (cut l.length) b p with
| none => rw [hr] at hc; cases hc
| some r =>
obtain ⟨o', nw'⟩ := r
rw [hr] at hc hn
simp only [Option.map_some', Option.some.injEq, Prod.mk.injEq] at hc
obtain ⟨rfl, rfl⟩ := hc
have hpair := hn _ _ (List.mem_cons_self _ _) hnw
simp only [sndD, Option.map_some', Option.getD_some] at hpair
have he := nodeMsg_inj_right hpair (by rw [hs, mth_len])
have ih := cons_core H r1 p (l.take (cut l.length)) m b o' nw' hm0
(by rw [ht]; exact hle) hw' (by rw [ht]; exact hr) he.1 hn.tail
rw [ih, List.take_take, Nat.min_eq_left hle]
· rename_i hle
rw [if_neg hle] at hn
cases hr : consRoots H r1 (m - cut l.length) (l.length - cut l.length) false p with
| none => rw [hr] at hc; cases hc
| some r =>
obtain ⟨o', nw'⟩ := r
rw [hr] at hc hn
simp only [Option.map_some', Option.some.injEq, Prod.mk.injEq] at hc
obtain ⟨rfl, rfl⟩ := hc
have hpair := hn _ _ (List.mem_cons_self _ _) hnw
simp only [sndD, Option.map_some', Option.getD_some] at hpair
have he := nodeMsg_inj_left hpair (by rw [hs, mth_len])
have ih := cons_core H r1 p (l.drop (cut l.length)) (m - cut l.length) false o' nw'
(by omega) (by rw [List.length_drop]; omega) hw'
(by rw [List.length_drop]; exact hr) he.2 hn.tail
rw [ih, he.1, mth_take_split H h2 (by omega) hmn]
theorem cons_complete_core (H : Hash) (r1 : Word) : ∀ (n : Nat) (l : List Word) (m : Nat) (b : Bool),
l.length = n → 0 < m → m ≤ n → (b = true → r1 = mth H (l.take m)) →
consRoots H r1 m n b (subproof H l m b) = some (mth H (l.take m), mth H l) ∧
∀ s ∈ subproof H l m b, s.length = H.w := by
intro n
induction n using Nat.strongRecOn with
| ind n ih =>
intro l m b hl hm0 hmn hr1
subst hl
by_cases heq : m = l.length
· rw [subproof, if_pos heq]
have htk : l.take m = l := List.take_of_length_le (by omega)
cases b
· simp only [Bool.false_eq_true, if_false]
refine ⟨?_, ?_⟩
· simp [consRoots, heq, htk]
· intro s hs; simp at hs; subst hs; exact mth_len H l
· simp only [if_true]
refine ⟨?_, ?_⟩
· simp only [consRoots, heq, and_self, if_true]
rw [hr1 rfl, htk, ← heq, htk]
· intro s hs; simp at hs
· have h2 : 2 ≤ l.length := by omega
have hb := cut_bounds h2
have ht := len_take_cut h2
rw [subproof, if_neg heq, dif_pos h2]
split
· rename_i hle
obtain ⟨hc, hw⟩ := ih (cut l.length) hb.2.1 (l.take (cut l.length)) m b ht hm0 hle
(fun hb' => by rw [hr1 hb', List.take_take, Nat.min_eq_left hle])
refine ⟨?_, ?_⟩
· simp only [consRoots, if_neg heq, if_pos (show m < l.length by omega), if_pos hle]
rw [hc, Option.map_some', mth_node H h2, List.take_take, Nat.min_eq_left hle]
· intro s hs
rcases List.mem_cons.mp hs with rfl | hs
· exact mth_len H _
· exact hw s hs
· rename_i hle
obtain ⟨hc, hw⟩ := ih (l.length - cut l.length) (by omega) (l.drop (cut l.length))
(m - cut l.length) false (List.length_drop _ _) (by omega)
(by omega) (fun h => by cases h)
refine ⟨?_, ?_⟩
· simp only [consRoots, if_neg heq, if_pos (show m < l.length by omega), if_neg hle]
rw [hc, Option.map_some', mth_node H h2, mth_take_split H h2 (by omega) hmn]
· intro s hs
rcases List.mem_cons.mp hs with rfl | hs
· exact mth_len H _
· exact hw s hs
/-- **Consistency, completeness.** The honest proof between sizes
`0 < m ≤ n` is always accepted. -/
theorem consistency_complete (H : Hash) (l : List Word) (m : Nat)
(hm0 : 0 < m) (hmn : m ≤ l.length) :
verifyCons H m l.length (mth H (l.take m)) (mth H l) (subproof H l m true) = true := by
obtain ⟨hc, hw⟩ := cons_complete_core H (mth H (l.take m)) l.length l m true rfl hm0 hmn
(fun _ => rfl)
simp only [verifyCons, Bool.and_eq_true, decide_eq_true_eq, beq_iff_eq, List.all_eq_true]
exact ⟨⟨⟨hm0, hmn⟩, fun s hs => by simp [hw s hs]⟩, hc⟩
/-- **Consistency, soundness.** If a proof is accepted against the new root
`mth l`, the old root is the root of the first `m` entries of `l`, unless
the extractor returns a collision. -/
theorem consistency_sound (H : Hash) (l p : List Word) (m : Nat) (r1 : Word)
(hv : verifyCons H m l.length r1 (mth H l) p = true) :
r1 = mth H (l.take m) ∨
∃ c, firstCollision H (consPairs H r1 l m true p) = some c ∧ H.IsCollision c := by
simp only [verifyCons, Bool.and_eq_true, decide_eq_true_eq, beq_iff_eq,
List.all_eq_true] at hv
obtain ⟨⟨⟨hm0, hmn⟩, hw⟩, hc⟩ := hv
exact extract H _ (cons_core H r1 p l m true r1 (mth H l) hm0 hmn
(fun s hs => by simpa using hw s hs) hc rfl)
Theorem 2 says the old root is the root of the prefix. To say the old log is the prefix, one more step is needed: two logs of the same size with the same root are equal, unless a collision is found.
Theorem 3 (root binding). If and , then , or returns a collision.
Corollary 4 (append-only). If accepts and is any log with and , then , or the extractor returns a collision from .
Proof. Theorem 3 by strong induction on the size, splitting both logs at the same point. Corollary 4 combines Theorem 2 with Theorem 3 under one extraction, so a single list of candidates covers both steps. ∎
/-! ## 7. Root binding: equal roots of equal size force equal logs -/
def bindPairs (H : Hash) (l1 l2 : List Word) : List (Word × Word) :=
if h2 : 2 ≤ l1.length then
(nodeMsg (mth H (l1.take (cut l1.length))) (mth H (l1.drop (cut l1.length))),
nodeMsg (mth H (l2.take (cut l1.length))) (mth H (l2.drop (cut l1.length)))) ::
(bindPairs H (l1.take (cut l1.length)) (l2.take (cut l1.length)) ++
bindPairs H (l1.drop (cut l1.length)) (l2.drop (cut l1.length)))
else [(leafMsg (l1.headD []), leafMsg (l2.headD []))]
termination_by l1.length
decreasing_by
all_goals simp_wf
all_goals have := cut_bounds h2
all_goals omega
theorem bind_core (H : Hash) : ∀ (n : Nat) (l1 l2 : List Word),
l1.length = n → l2.length = n → mth H l1 = mth H l2 →
NoCollIn H (bindPairs H l1 l2) → l1 = l2 := by
intro n
induction n using Nat.strongRecOn with
| ind n ih =>
intro l1 l2 h1 h2' he hn
rw [bindPairs] at hn
by_cases h2 : 2 ≤ l1.length
· rw [dif_pos h2] at hn
have hb := cut_bounds h2
have h22 : 2 ≤ l2.length := by omega
rw [mth_node H h2, mth_node H h22, show l2.length = l1.length by omega] at he
have hp := nodeMsg_inj_left (hn _ _ (List.mem_cons_self _ _) he) (by rw [mth_len, mth_len])
have t1 : (l1.take (cut l1.length)).length = cut l1.length := len_take_cut h2
have t2 : (l2.take (cut l1.length)).length = cut l1.length := by
rw [List.length_take]; omega
have ht := ih (cut l1.length) (by omega) _ _ t1 t2 hp.1 hn.tail.left
have hd := ih (l1.length - cut l1.length) (by omega) (l1.drop (cut l1.length))
(l2.drop (cut l1.length)) (List.length_drop _ _) (by rw [List.length_drop]; omega)
hp.2 hn.tail.right
rw [← List.take_append_drop (cut l1.length) l1, ← List.take_append_drop (cut l1.length) l2,
ht, hd]
· rw [dif_neg h2] at hn
rcases l1 with _ | ⟨x, _ | ⟨z, t⟩⟩
· rcases l2 with _ | ⟨y, t⟩
· rfl
· simp at h1 h2'; omega
· rcases l2 with _ | ⟨y, _ | ⟨z, t⟩⟩
· simp at h1 h2'; omega
· rw [mth_single, mth_single] at he
have := leafMsg_inj (hn _ _ (List.mem_cons_self _ _) he)
simp only [List.headD] at this
rw [this]
· simp at h1 h2'; omega
· simp at h2
/-- **Root binding.** Two logs of the same size with the same root are equal,
unless the extractor returns a collision. -/
theorem root_binding (H : Hash) (l1 l2 : List Word) (hl : l1.length = l2.length)
(he : mth H l1 = mth H l2) :
l1 = l2 ∨ ∃ c, firstCollision H (bindPairs H l1 l2) = some c ∧ H.IsCollision c :=
extract H _ (bind_core H l1.length l1 l2 rfl hl.symm he)
/-- **Append-only.** An accepted consistency proof from `(m, r1)` to the
root of `l` makes every log `l0` with `|l0| = m` and root `r1` a prefix of
`l`, unless the extractor returns a collision. -/
theorem consistency_prefix (H : Hash) (l l0 p : List Word) (m : Nat) (r1 : Word)
(hv : verifyCons H m l.length r1 (mth H l) p = true)
(h0 : l0.length = m) (hr : mth H l0 = r1) :
l0 = l.take m ∨
∃ c, firstCollision H (consPairs H r1 l m true p ++ bindPairs H l0 (l.take m)) = some c ∧
H.IsCollision c := by
have hv' := hv
simp only [verifyCons, Bool.and_eq_true, decide_eq_true_eq, beq_iff_eq,
List.all_eq_true] at hv'
obtain ⟨⟨⟨hm0, hmn⟩, hw⟩, hc⟩ := hv'
refine extract H _ (fun hn => ?_)
have hr1 := cons_core H r1 p l m true r1 (mth H l) hm0 hmn
(fun s hs => by simpa using hw s hs) hc rfl hn.left
exact bind_core H m l0 (l.take m) h0 (by rw [List.length_take]; omega)
(by rw [hr, hr1]) hn.right
Rows
A row is committed as the leaf , which has width and so splits uniquely. The table root is the tree hash of these leaves, and a row proof is an inclusion proof for the leaf. The candidate pairs add, to those of Theorem 1, the pairs (claimed key, honest key) and (claimed value, honest value).
Theorem 5 (rows). Let be a table.
- Completeness. If , the honest proof is accepted against the table root.
- Soundness. If a row proof for at index is accepted against the root of with size , then , or returns a collision.
Proof. Theorem 1 gives that the leaf at is , up to a collision. Equal fixed-width concatenations give and for the honest row , and the two added pairs turn these into and , up to a collision. ∎
/-! ## 8. State rows -/
/-- A row is a key and a value. -/
abbrev Row := Word × Word
/-- Row leaf: the digests of key and value, concatenated (fixed width). -/
def rowEnc (H : Hash) (r : Row) : Word := H.h r.1 ++ H.h r.2
def stateRoot (H : Hash) (s : List Row) : Word := mth H (s.map (rowEnc H))
def verifyRow (H : Hash) (i n : Nat) (r : Row) (p : List Word) (root : Word) : Bool :=
verifyIncl H i n (rowEnc H r) p root
def rowPairs (H : Hash) (s : List Row) (i : Nat) (r : Row) (p : List Word) :
List (Word × Word) :=
inclPairs H (s.map (rowEnc H)) i (rowEnc H r) p ++
((s[i]?).map (fun r' => [(r.1, r'.1), (r.2, r'.2)])).getD []
/-- **Row proof, completeness.** -/
theorem row_complete (H : Hash) (s : List Row) (i : Nat) (r : Row) (hs : s[i]? = some r) :
verifyRow H i s.length r (inclPath H (s.map (rowEnc H)) i) (stateRoot H s) = true := by
have := inclusion_complete H (s.map (rowEnc H)) i (rowEnc H r)
(by rw [List.getElem?_map, hs]; rfl)
rw [List.length_map] at this
exact this
/-- **Row proof, soundness.** An accepted row proof against the state root
of `s` means row `i` of `s` is exactly `(key, value)`, unless the extractor
returns a collision. -/
theorem row_sound (H : Hash) (s : List Row) (i : Nat) (r : Row) (p : List Word)
(hv : verifyRow H i s.length r p (stateRoot H s) = true) :
s[i]? = some r ∨
∃ c, firstCollision H (rowPairs H s i r p) = some c ∧ H.IsCollision c := by
simp only [verifyRow, verifyIncl, stateRoot, Bool.and_eq_true, beq_iff_eq] at hv
rw [← List.length_map s (rowEnc H)] at hv
refine extract H _ (fun hn => ?_)
have hi := incl_core H p (s.map (rowEnc H)) i (rowEnc H r) hv.1 hv.2 hn.left
rw [List.getElem?_map] at hi
cases hsi : s[i]? with
| none => rw [hsi] at hi; cases hi
| some r' =>
rw [hsi] at hi
simp only [Option.map_some', Option.some.injEq] at hi
have hr : NoCollIn H (((s[i]?).map (fun r' => [(r.1, r'.1), (r.2, r'.2)])).getD []) :=
hn.right
rw [hsi] at hr
simp only [Option.map_some', Option.getD_some] at hr
simp only [rowEnc] at hi
have he := List.append_inj hi (by rw [H.width, H.width])
have k := hr _ _ (List.mem_cons_self _ _) he.1.symm
have v := hr _ _ (List.mem_cons_of_mem _ (List.mem_cons_self _ _)) he.2.symm
rw [Prod.ext k v]
Signed heads
Head and its encoding. A head has four fields: log size, log root, table size, table root. Its signed message is
Judgement. Given the trusted key , a signed head is accepted iff and .
Hypotheses. (U) Unforgeability: every message that verifies under with some signature is one the key holder signed. (S) Signing discipline: every message the key holder signed is the encoding of a head it issued. (HI) Honest issuer: every issued head is for some log and table .
The length prefix makes the encoding injective, so a signature covers every field. A change to any field, including either size, changes the signed message. The tag 2 keeps signed heads apart from leaf and node messages.
Lemma 6 (head encoding). is injective, and is neither a leaf message nor a node message.
Theorem 7 (signed-head judgement). A signed head is accepted iff its key is and the signature verifies on the encoding of all four fields. Under (U) and (S), every accepted head is, field for field, a head the key holder issued.
Proof. (U) gives that was signed. (S) gives an issued with . Lemma 6 gives . ∎
/-! ## 9. Signed tree heads -/
structure Head where
size : Nat
logRoot : Word
stateSize : Nat
stateRoot : Word
deriving DecidableEq, Repr
/-- The signed message: a domain tag `2`, then every field. The length
prefix makes the encoding injective. -/
def Head.encode (hd : Head) : Word :=
2 :: hd.size :: hd.stateSize :: hd.logRoot.length :: (hd.logRoot ++ hd.stateRoot)
theorem Head.encode_inj {a b : Head} (h : a.encode = b.encode) : a = b := by
cases a; cases b
simp only [Head.encode, List.cons.injEq, true_and] at h
obtain ⟨h1, h2, h3, h4⟩ := h
obtain ⟨h5, h6⟩ := List.append_inj h4 h3
subst h1 h2 h5 h6; rfl
/-- The head encoding is separated from leaf and node messages. -/
theorem Head.encode_ne (hd : Head) (d a b : Word) :
hd.encode ≠ leafMsg d ∧ hd.encode ≠ nodeMsg a b := by
simp [Head.encode, leafMsg, nodeMsg]
/-- A signature scheme, seen through its verification algorithm
`verify key message signature`. -/
structure SigScheme where
verify : Word → Word → Word → Bool
structure SignedHead where
head : Head
key : Word
sig : Word
/-- The outsider's judgement, holding only the trusted key `pk`. -/
def judge (S : SigScheme) (pk : Word) (sh : SignedHead) : Bool :=
sh.key == pk && S.verify pk sh.head.encode sh.sig
/-- Unforgeability as a hypothesis: every message that verifies under `pk`
is one the key holder signed. -/
def Unforgeable (S : SigScheme) (pk : Word) (Signed : Word → Prop) : Prop :=
∀ m σ, S.verify pk m σ = true → Signed m
theorem judge_iff (S : SigScheme) (pk : Word) (sh : SignedHead) :
judge S pk sh = true ↔ sh.key = pk ∧ S.verify pk sh.head.encode sh.sig = true := by
simp [judge]
/-- **Signed-head judgement.** Under unforgeability, and if the key holder
signs only encodings of heads it issued, every accepted head is, field for
field, an issued head. -/
theorem judge_issued (S : SigScheme) (pk : Word) (Signed : Word → Prop) (Issued : Head → Prop)
(hU : Unforgeable S pk Signed) (hS : ∀ m, Signed m → ∃ hd, Issued hd ∧ hd.encode = m)
(sh : SignedHead) (hj : judge S pk sh = true) : Issued sh.head := by
obtain ⟨_, hv⟩ := (judge_iff S pk sh).mp hj
obtain ⟨hd, hi, he⟩ := hS _ (hU _ _ hv)
rw [← Head.encode_inj he]; exact hi
/-- Changing any field changes the signed message. -/
theorem judge_field_change (S : SigScheme) (pk : Word) (sh sh' : SignedHead)
(hne : sh.head ≠ sh'.head) : sh.head.encode ≠ sh'.head.encode :=
fun h => hne (Head.encode_inj h)
The goal theorems
The outsider’s three checks now combine. The checks read their size and root from the accepted head, so none of the inputs comes from the prover except the proof itself.
Theorem 8 (outsider guarantees). Assume (U), (S) and (HI).
- Inclusion. If a signed head is accepted and accepts on its fields, then the head was issued for some log and table , and or the extractor returns a collision from .
- Rows. If a signed head is accepted and the row check for at accepts against its table size and root, then the head was issued for some , and or the extractor returns a collision from .
- Consistency. If two signed heads are accepted and accepts from the first head’s size and root to the second’s, then they were issued for and , and or the extractor returns a collision from .
Proof. Theorem 7 makes each accepted head an issued head, and (HI) gives the log and table behind it. Rewriting the verifier’s inputs with the head’s fields reduces 1 to Theorem 1, 2 to Theorem 5 and 3 to Corollary 4. ∎
Together with the completeness parts of Theorems 1, 2 and 5 and with Theorem 7, this is the goal of the first section. Completeness holds unconditionally. Soundness holds unless a collision is exhibited, and the collision is computed by a fixed function from the operator’s data and the proof the outsider accepted.
/-! ## 10. The goal: verification by an outsider holding only `pk` -/
/-- The head an honest operator signs for log `l` and state `s`. -/
def headOf (H : Hash) (l : List Word) (s : List Row) : Head :=
⟨l.length, mth H l, s.length, stateRoot H s⟩
/-- Honest issuance: the operator only issues heads of actual (log, state) pairs. -/
def HonestIssuer (H : Hash) (Issued : Head → Prop) : Prop :=
∀ hd, Issued hd → ∃ l s, hd = headOf H l s
section Outsider
variable (H : Hash) (S : SigScheme) (pk : Word) (Signed : Word → Prop) (Issued : Head → Prop)
(hU : Unforgeable S pk Signed) (hS : ∀ m, Signed m → ∃ hd, Issued hd ∧ hd.encode = m)
(hH : HonestIssuer H Issued)
include hU hS hH
/-- **Outsider inclusion.** An accepted head and an accepted inclusion proof
against it: the head was issued for some log `l` and `d` is entry `m` of
`l`, unless the extractor returns a collision. -/
theorem outsider_inclusion (sh : SignedHead) (hj : judge S pk sh = true)
(m : Nat) (d : Word) (p : List Word)
(hv : verifyIncl H m sh.head.size d p sh.head.logRoot = true) :
∃ l s, Issued (headOf H l s) ∧ sh.head = headOf H l s ∧
(l[m]? = some d ∨
∃ c, firstCollision H (inclPairs H l m d p) = some c ∧ H.IsCollision c) := by
have hi := judge_issued S pk Signed Issued hU hS sh hj
obtain ⟨l, s, he⟩ := hH _ hi
refine ⟨l, s, he ▸ hi, he, ?_⟩
rw [he] at hv
exact inclusion_sound H l p m d hv
/-- **Outsider row lookup.** -/
theorem outsider_row (sh : SignedHead) (hj : judge S pk sh = true)
(i : Nat) (r : Row) (p : List Word)
(hv : verifyRow H i sh.head.stateSize r p sh.head.stateRoot = true) :
∃ l s, Issued (headOf H l s) ∧ sh.head = headOf H l s ∧
(s[i]? = some r ∨
∃ c, firstCollision H (rowPairs H s i r p) = some c ∧ H.IsCollision c) := by
have hi := judge_issued S pk Signed Issued hU hS sh hj
obtain ⟨l, s, he⟩ := hH _ hi
refine ⟨l, s, he ▸ hi, he, ?_⟩
rw [he] at hv
exact row_sound H s i r p hv
/-- **Outsider consistency.** Two accepted heads and an accepted consistency
proof between them: the earlier issued log is a prefix of the later one,
unless the extractor returns a collision. -/
theorem outsider_consistency (sh1 sh2 : SignedHead)
(hj1 : judge S pk sh1 = true) (hj2 : judge S pk sh2 = true) (p : List Word)
(hv : verifyCons H sh1.head.size sh2.head.size sh1.head.logRoot sh2.head.logRoot p = true) :
∃ l1 s1 l2 s2, sh1.head = headOf H l1 s1 ∧ sh2.head = headOf H l2 s2 ∧
Issued (headOf H l1 s1) ∧ Issued (headOf H l2 s2) ∧
(l1 = l2.take l1.length ∨
∃ c, firstCollision H (consPairs H (mth H l1) l2 l1.length true p ++
bindPairs H l1 (l2.take l1.length)) = some c ∧ H.IsCollision c) := by
have hi1 := judge_issued S pk Signed Issued hU hS sh1 hj1
have hi2 := judge_issued S pk Signed Issued hU hS sh2 hj2
obtain ⟨l1, s1, he1⟩ := hH _ hi1
obtain ⟨l2, s2, he2⟩ := hH _ hi2
refine ⟨l1, s1, l2, s2, he1, he2, he1 ▸ hi1, he2 ▸ hi2, ?_⟩
rw [he1, he2] at hv
exact consistency_prefix H l2 l1 p l1.length (mth H l1) hv rfl rfl
end Outsider
A toy check
The last block runs the verifiers on a five-entry log with a toy hash: a two-symbol checksum that is trivially not collision resistant and is used only so that the evaluation is small and readable. The theorems above hold for every hash function; the toy only illustrates the verifiers’ behaviour. The five evaluations print true, false, false, true, false: the honest inclusion proof for entry 2 is accepted; the same proof with one sibling digest changed is rejected; the honest proof presented with a different entry value is rejected; the honest consistency proof from size 3 to size 5 is accepted; and a consistency proof against a rewritten history (entry 1 replaced) is rejected.
/-! ## 11. A toy check (TOY HASH: not collision resistant, illustration only) -/
def toyHash : Hash where
h m := [m.foldl (fun a x => (a * 31 + x + 1) % 251) 7, m.length % 251]
w := 2
width _ := rfl
def toyLog : List Word := [[10], [11], [12], [13], [14]]
-- inclusion of entry 2 in the 5-entry log: honest proof accepted
#eval verifyIncl toyHash 2 5 [12] (inclPath toyHash toyLog 2) (mth toyHash toyLog)
-- the same proof with one sibling digest tampered: rejected
#eval verifyIncl toyHash 2 5 [12]
((inclPath toyHash toyLog 2).modifyHead (fun s => s.map (· + 1))) (mth toyHash toyLog)
-- the honest proof for a different entry value: rejected
#eval verifyIncl toyHash 2 5 [99] (inclPath toyHash toyLog 2) (mth toyHash toyLog)
-- consistency from size 3 to size 5: honest proof accepted
#eval verifyCons toyHash 3 5 (mth toyHash (toyLog.take 3)) (mth toyHash toyLog)
(subproof toyHash toyLog 3 true)
-- consistency against a rewritten history (entry 1 changed): rejected
#eval verifyCons toyHash 3 5 (mth toyHash [[10], [77], [12]]) (mth toyHash toyLog)
(subproof toyHash toyLog 3 true)
Limits and assumptions
What is proved is proved in the model above. The following are outside it.
- Who can run the extractor. The candidate pairs are built from the honest log or table. This is the usual form of a reduction: whoever holds the data and a false accepted proof obtains a collision. The outsider cannot run it and does not need to. The theorem says that a false proof that passes is as hard to produce as a collision.
- Unforgeability is idealised. (U) is a deterministic statement, “every message that verifies was signed”, not a probabilistic game with an adversary’s advantage. (S) and (HI) are hypotheses about the operator’s conduct. Nothing here bounds any probability.
- Alphabet. Words are over , so a size fits in one symbol of the head encoding. An injective fixed-width byte encoding of sizes is not proved.
- Proof order and verifier form. Proofs are listed root side first, the reverse of RFC 6962’s order, and the verifiers are recursive, mirroring PATH and SUBPROOF. Equivalence with the RFC’s iterative verification algorithms, which work with bit operations on indices, is not proved.
- Consistency from the empty tree. The consistency verifier requires . The case is rejected rather than handled.
- Rows by position. A row proof shows that row of the table is . It does not show that keys are unique, it does not support lookup by key, and it cannot show that a key is absent.
- Split views. Theorem 8 says what two heads with an accepted consistency proof mean. It does not address an operator who signs two heads that no consistency proof links. Detecting that requires outsiders to compare the heads they have seen, which is not modelled.
- Kernel axioms. The proofs use the tactics
simpandomega, which bring in Lean’s built-inpropext,Classical.choiceandQuot.sound. No other axiom is used, and the extractor itself is an ordinary computable function.
Prior work
The parts are standard; the sources below are the ones the components above are taken from.
- A Digital Signature Based on a Conventional Encryption Function, CRYPTO, 1987: hash trees that commit to many values with one digest.
- Certificate Transparency, IETF RFC 6962, 2013: the tree hash with its split at the largest power of two, leaf and node prefixes, signed tree heads, and the PATH and SUBPROOF algorithms for inclusion and consistency proofs.
- Efficient Data Structures for Tamper-Evident Logging, USENIX Security Symposium, 2009: history trees with commitments at every size and proofs that a later commitment extends an earlier one.
- A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks, SIAM Journal on Computing, 1988: the unforgeability notion idealised as (U).
- Formalizing Human Ignorance: Collision-Resistant Hashing without the Keys, VIETCRYPT, 2006: stating the security of a fixed, keyless hash function as an explicit reduction that produces a collision, the form of every soundness theorem here.