Research / 2026

Checking a log from its signed head

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

An outsider who holds only a public key and a signed tree head can check that an entry is in a log, that a row is in a state, and that a later head extends an earlier one. Merkle tree hashing with leaf and node domain separation, inclusion and consistency proofs, a row proof and signed heads are combined, and every soundness theorem is proved in the form "the claim holds, or this computable extractor returns a collision of the hash". Unforgeability is a hypothesis, never an axiom. Everything is checked in Lean.

Merkle treesTransparency logsInclusion proofsConsistency proofsSigned tree heads
1 key
all the outsider holds: a signed head is judged against it, and every proof is checked against the head
claim ∨ collision
the form of every soundness theorem: the claim holds, or a computable extractor returns a collision of the hash
0 axioms
added to Lean: collision resistance and unforgeability appear only as hypotheses or as the collision alternative

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 pkpk; 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 pkpk, the signed heads and the proof, with these properties.

  1. 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.
  2. Head soundness. A signed head is accepted only if a valid signature under pkpk 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.
  3. Proof soundness. If a head and an inclusion proof for entry dd at index mm are accepted, then dd really is entry mm 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 hh 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 hh 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 nn is split at the largest power of two strictly below nn. 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

  1. trusted
    public key pk
  2. judge
    signed head
    key = pk ∧ verify(pk, encode(head), sig)
  3. read
    head fields
    (size, logRoot, stateSize, stateRoot)
  4. check
    inclusion, row or consistency proof
    recompute a root, compare
  5. conclude
    claim, or a collision
Fig. 1What the outsider does. The head is judged against the trusted key first; every proof is then checked against a digest taken from the accepted head, never from the prover.

The pieces are wired as follows.

  • The log is a list of entries ll. Its digest is the RFC 6962 tree hash MTH(l)\mathrm{MTH}(l).
  • The table is a list of rows ss. Each row (k,v)(k, v) becomes the leaf h(k)∥h(v)h(k) \Vert h(v), 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 (∣l∣,MTH(l),∣s∣,MTH(rows of s))(|l|, \mathrm{MTH}(l), |s|, \mathrm{MTH}(\text{rows of } s)). 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 pkpk and the signature verifies under pkpk 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 N\mathbb{N} (bytes in practice). A hash function is any function hh from words to words whose outputs all have the same length ww. Fixed width is a functional property, like a 256-bit output, not a security assumption.

Collision. A pair (a,b)(a, b) with a≠ba \ne b and h(a)=h(b)h(a) = h(b).

Extractor. For a finite list PP of candidate pairs, FCh(P)\mathsf{FC}_h(P) returns the first pair in PP that is a collision of hh, or nothing.

Every soundness proof below follows one pattern. It names a list PP of candidate pairs, built from the honest data and the proof, and shows that the claim follows if no pair in PP collides. Lemma 1 turns that into “claim, or FCh(P)\mathsf{FC}_h(P) returns a collision”.

Lemma 1 (extraction). If FCh(P)\mathsf{FC}_h(P) returns cc, then cc is a collision and c∈Pc \in P. If it returns nothing, no pair in PP collides. Hence, for every proposition QQ: if QQ follows from “no pair in PP collides”, then QQ holds or FCh(P)\mathsf{FC}_h(P) 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. leaf(d)=0∥d\mathrm{leaf}(d) = 0 \Vert d and node(a,b)=1∥a∥b\mathrm{node}(a, b) = 1 \Vert a \Vert b. The leaf hash is h(leaf(d))h(\mathrm{leaf}(d)) and the node hash is h(node(a,b))h(\mathrm{node}(a, b)).

Lemma 2 (domain separation). For all d,a,bd, a, b: leaf(d)≠node(a,b)\mathrm{leaf}(d) \ne \mathrm{node}(a, b). Consequently, a leaf hash that equals a node hash is itself a collision, namely (leaf(d),node(a,b))(\mathrm{leaf}(d), \mathrm{node}(a, b)).

Proof. The first symbols differ. ∎

Without the prefixes, an interior node a∥ba \Vert b could be presented as a leaf whose data is a∥ba \Vert b, 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 ww 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 n≥2n \ge 2, let k(n)=2⌊log⁡2(n−1)⌋k(n) = 2^{\lfloor \log_2 (n - 1) \rfloor}, the largest power of two strictly below nn. This is the split of RFC 6962.

Lemma 3 (split). For n≥2n \ge 2: 1≤k(n)<n≤2k(n)1 \le k(n) \lt n \le 2k(n). Moreover, if k(n)<m≤nk(n) \lt m \le n, then k(m)=k(n)k(m) = k(n).

The second part is what makes consistency proofs work. A prefix of length mm that reaches past the split of nn 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 D=(d0,…,dn−1)D = (d_0, \ldots, d_{n-1}):

MTH(D)={h(ε)n=0h(leaf(d0))n=1h(node(MTH(D[0:k]), MTH(D[k:n])))n≥2, k=k(n).\mathrm{MTH}(D) = \begin{cases} h(\varepsilon) & n = 0 \\ h(\mathrm{leaf}(d_0)) & n = 1 \\ h\big(\mathrm{node}(\mathrm{MTH}(D[0{:}k]),\ \mathrm{MTH}(D[k{:}n]))\big) & n \ge 2,\ k = k(n). \end{cases}

Every tree hash has width ww, because the last step is always a call to hh. The lemma mth_take_split is Lemma 3 applied to the tree: for k(n)<m≤nk(n) \lt m \le n, the tree hash of the first mm 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 mm in a tree of size nn 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 mm and that m<nm \lt n. The climb recomputes a root from the leaf hash of the claimed entry and the siblings.

Inclusion verifier. VerIncl(m,n,d,p,r)\mathsf{VerIncl}(m, n, d, p, r) accepts if pp has the shape of the path to leaf mm in a tree of size nn, and the root recomputed from h(leaf(d))h(\mathrm{leaf}(d)) and pp equals rr.

Honest proof. Path(l,m)\mathsf{Path}(l, m): at each split, the tree hash of the subtree not containing mm, 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 dd, 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 ll be a log.

  1. Completeness. If lm=dl_m = d, then VerIncl(m,∣l∣,d,Path(l,m),MTH(l))\mathsf{VerIncl}(m, |l|, d, \mathsf{Path}(l, m), \mathrm{MTH}(l)) accepts.
  2. Soundness. If VerIncl(m,∣l∣,d,p,MTH(l))\mathsf{VerIncl}(m, |l|, d, p, \mathrm{MTH}(l)) accepts for any pp, then lm=dl_m = d, or FCh(InclPairs(l,m,d,p))\mathsf{FC}_h(\mathsf{InclPairs}(l, m, d, p)) returns a collision of hh.

Proof sketch. Completeness is by strong induction on ∣l∣|l|: the honest sibling at each level is exactly the other child in the definition of MTH\mathrm{MTH}. For soundness, assume no candidate pair collides and induct on pp. At the top, the recomputed root equals MTH(l)\mathrm{MTH}(l), 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 ww, so the node message splits uniquely, and the child on mm‘s side of the claimed message equals the honest subtree hash. Recurse into that subtree. At the bottom, the leaf messages are equal, so dd 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 mm with old root r1r_1 to a new size nn with new root r2r_2. 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 r1r_1 and r2r_2. It follows the recursion of RFC 6962’s SUBPROOF: while mm fits in the left subtree, only the new root gains a right sibling; once mm reaches past the split, the left subtree is complete and shared, and both roots gain it as a left sibling. The flag bb records whether the old subtree reached at the bottom is the whole old tree. If so, its root is r1r_1, which the verifier already holds, and the proof stops there. If not, the proof supplies it.

Consistency verifier. VerCons(m,n,r1,r2,p)\mathsf{VerCons}(m, n, r_1, r_2, p) accepts if 0<m≤n0 \lt m \le n, every digest in pp has width ww, and the pair of roots recomputed from pp is (r1,r2)(r_1, r_2).

Honest proof. Sub(l,m)\mathsf{Sub}(l, m), 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 ll be a log and 0<m≤∣l∣0 \lt m \le |l|.

  1. Completeness. VerCons(m,∣l∣,MTH(l[0:m]),MTH(l),Sub(l,m))\mathsf{VerCons}(m, |l|, \mathrm{MTH}(l[0{:}m]), \mathrm{MTH}(l), \mathsf{Sub}(l, m)) accepts.
  2. Soundness. If VerCons(m,∣l∣,r1,MTH(l),p)\mathsf{VerCons}(m, |l|, r_1, \mathrm{MTH}(l), p) accepts for any r1r_1 and pp, then r1=MTH(l[0:m])r_1 = \mathrm{MTH}(l[0{:}m]), or FCh(ConsPairs(r1,l,m,p))\mathsf{FC}_h(\mathsf{ConsPairs}(r_1, l, m, p)) returns a collision.

Proof sketch. Induction on pp, as for Theorem 1, but tracking both roots. When m≤k(n)m \le k(n), 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 m>k(n)m \gt k(n), 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 r1r_1, 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 ∣l1∣=∣l2∣|l_1| = |l_2| and MTH(l1)=MTH(l2)\mathrm{MTH}(l_1) = \mathrm{MTH}(l_2), then l1=l2l_1 = l_2, or FCh(BindPairs(l1,l2))\mathsf{FC}_h(\mathsf{BindPairs}(l_1, l_2)) returns a collision.

Corollary 4 (append-only). If VerCons(m,∣l∣,r1,MTH(l),p)\mathsf{VerCons}(m, |l|, r_1, \mathrm{MTH}(l), p) accepts and l0l_0 is any log with ∣l0∣=m|l_0| = m and MTH(l0)=r1\mathrm{MTH}(l_0) = r_1, then l0=l[0:m]l_0 = l[0{:}m], or the extractor returns a collision from ConsPairs+ ⁣ ⁣+BindPairs(l0,l[0:m])\mathsf{ConsPairs} \mathbin{+\!\!+} \mathsf{BindPairs}(l_0, l[0{:}m]).

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 (k,v)(k, v) is committed as the leaf h(k)∥h(v)h(k) \Vert h(v), which has width 2w2w 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 ss be a table.

  1. Completeness. If si=(k,v)s_i = (k, v), the honest proof is accepted against the table root.
  2. Soundness. If a row proof for (k,v)(k, v) at index ii is accepted against the root of ss with size ∣s∣|s|, then si=(k,v)s_i = (k, v), or FCh(RowPairs(s,i,(k,v),p))\mathsf{FC}_h(\mathsf{RowPairs}(s, i, (k, v), p)) returns a collision.

Proof. Theorem 1 gives that the leaf at ii is h(k)∥h(v)h(k) \Vert h(v), up to a collision. Equal fixed-width concatenations give h(k)=h(k′)h(k) = h(k') and h(v)=h(v′)h(v) = h(v') for the honest row (k′,v′)(k', v'), and the two added pairs turn these into k=k′k = k' and v=v′v = v', 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

msg(hd)=2∥size∥stateSize∥∣logRoot∣∥logRoot∥stateRoot.\mathrm{msg}(\mathit{hd}) = 2 \Vert \mathit{size} \Vert \mathit{stateSize} \Vert |\mathit{logRoot}| \Vert \mathit{logRoot} \Vert \mathit{stateRoot}.

Judgement. Given the trusted key pkpk, a signed head (hd,key,σ)(\mathit{hd}, \mathit{key}, \sigma) is accepted iff key=pk\mathit{key} = pk and Verify(pk,msg(hd),σ)\mathrm{Verify}(pk, \mathrm{msg}(\mathit{hd}), \sigma).

Hypotheses. (U) Unforgeability: every message that verifies under pkpk 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 (∣l∣,MTH(l),∣s∣,root(s))(|l|, \mathrm{MTH}(l), |s|, \mathrm{root}(s)) for some log ll and table ss.

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). msg\mathrm{msg} is injective, and msg(hd)\mathrm{msg}(\mathit{hd}) is neither a leaf message nor a node message.

Theorem 7 (signed-head judgement). A signed head is accepted iff its key is pkpk 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 msg(hd)\mathrm{msg}(\mathit{hd}) was signed. (S) gives an issued hd′\mathit{hd}' with msg(hd′)=msg(hd)\mathrm{msg}(\mathit{hd}') = \mathrm{msg}(\mathit{hd}). Lemma 6 gives hd′=hd\mathit{hd}' = \mathit{hd}. ∎

/-! ## 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).

  1. Inclusion. If a signed head is accepted and VerIncl(m,size,d,p,logRoot)\mathsf{VerIncl}(m, \mathit{size}, d, p, \mathit{logRoot}) accepts on its fields, then the head was issued for some log ll and table ss, and lm=dl_m = d or the extractor returns a collision from InclPairs(l,m,d,p)\mathsf{InclPairs}(l, m, d, p).
  2. Rows. If a signed head is accepted and the row check for (k,v)(k, v) at ii accepts against its table size and root, then the head was issued for some l,sl, s, and si=(k,v)s_i = (k, v) or the extractor returns a collision from RowPairs\mathsf{RowPairs}.
  3. Consistency. If two signed heads are accepted and VerCons\mathsf{VerCons} accepts from the first head’s size and root to the second’s, then they were issued for (l1,s1)(l_1, s_1) and (l2,s2)(l_2, s_2), and l1=l2[0:∣l1∣]l_1 = l_2[0{:}|l_1|] or the extractor returns a collision from ConsPairs+ ⁣ ⁣+BindPairs\mathsf{ConsPairs} \mathbin{+\!\!+} \mathsf{BindPairs}.

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 N\mathbb{N}, 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 0<m≤n0 \lt m \le n. The case m=0m = 0 is rejected rather than handled.
  • Rows by position. A row proof shows that row ii of the table is (k,v)(k, v). 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 simp and omega, which bring in Lean’s built-in propext, Classical.choice and Quot.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.