Research / 2025 –

A log-structured store across trust tiers

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

A key-value store whose layers sit on tiers of different speed and trust: a volatile tier that answers at once, a durable ordered log, and immutable segments. Reads equal the sequential map, flush and compaction preserve it, tombstones may be dropped exactly at the bottom level, re-encoding with any lossless codec is safe, recovery is exact, finalised state is never rolled back, and a wrong state root has one-step evidence.

Log-structured merge treesWrite-ahead loggingReplay verification
L ≤ i + n
dropping tombstones while merging levels i…i+n−1 of L preserves every read exactly when the window reaches the bottom
prefix
the finalised state is always the replay of a log prefix, and that prefix only grows
1 step
a published root sequence that disagrees with replay has a first index where one record explains the difference

A log-structured merge store answers writes quickly by appending them to a small in-memory table and pushing data into sorted immutable segments in the background. The same shape can be laid across components that differ in speed and in how far they are trusted: a fast volatile tier that answers at once, a durable ordered log, and permanent immutable segments. This page states that architecture abstractly and proves, in Lean 4, the properties that make it correct.

Goal. A store split across tiers answers immediately from a volatile tier, and still (i) every read equals the sequential map semantics, (ii) nothing acknowledged is lost and nothing finalised is rolled back, (iii) anyone can recompute the final state by replaying the durable log, and (iv) flush, compaction and re-encoding never change the abstract state.

The tiers

classic componentrole here
memtablevolatile tier: answers reads and writes at once, may be lost at any moment
write-ahead logdurable ordered log: a record is acknowledged only after it is logged
sorted segments (levels)immutable segments, newest level first
compactionmerging a window of consecutive levels, newest entry wins
re-encodingrewriting segments with a lossless codec
finalisationa prefix of the durable log is declared final; validators replay it

Entries, reads and replay

An entry is a pair (k,x)(k, x) with x∈V∪{⊥}x \in V \cup \lbrace \bot \rbrace; x=⊥x = \bot is a tombstone (a delete). A store is a memtable followed by levels, newest first, each a list of entries. A read of kk returns the first entry for kk found in the memtable and then the levels in order, with a tombstone read as absent. The store’s history is its entries in the order they were written, and replay applies a history to the empty map one entry at a time.

Read correctness (read_correct). For every store and key, the tiered read equals the replay of the store’s history. In run form (read_correct_run): after any interleaving of writes, flushes and compactions of the kinds below, every read equals the sequential map semantics of the writes issued.

Flush (read_flush). Moving the memtable into a new newest level, deduplicated, changes no read.

Compaction (read_compact). Merging any window of consecutive levels, newest entry wins and tombstones kept, changes no read.

Tombstone dropping (tombstone_drop_safe_iff). For a non-empty window of nn levels starting at level ii in a store with LL levels, discarding tombstones during the merge preserves every read of every such store (over a non-empty key and value type) if and only if L≤i+nL \le i + n, that is, if the window reaches the oldest level. When it does not, a tombstone in the window can hide an older value below it, and dropping the tombstone brings that value back (compact_drop_above_bottom_unsafe).

Re-encoding (read_reencode_codec, read_compactReencode). For any codec with decode∘encode=id\mathrm{decode} \circ \mathrm{encode} = \mathrm{id}, re-encoding any selection of levels, or compacting and then encoding the result, preserves every read, with tombstones dropped only under the condition above.

The durable log, acknowledgement and finality

The system state holds the durable log, the number of acknowledged records, a checkpoint (a log position and the levels that cover it), a finalised prefix length with its replayed map, and the volatile store, which may be absent after a crash. Its steps are: append a record to the log and then apply it to the volatile store (write-ahead); acknowledge the oldest unacknowledged logged record; flush; compact; checkpoint; finalise a longer log prefix; crash (lose the volatile tier); recover (rebuild from the checkpoint and the log suffix).

Recovery is exact (recovery_exact). In every reachable state, recovery from the checkpoint plus the log suffix yields exactly the replay of the durable log, whatever was lost. If every logged record has been acknowledged, this is exactly the acknowledged state (recovery_eq_acked).

Acknowledged writes are never lost (acked_never_lost). Along any run, the acknowledged prefix of an earlier state stays a prefix of every later durable log.

Finality only grows (final_prefix_monotone, final_is_prefix_replay, final_never_rolled_back). In every reachable state the final state equals the replay of the finalised log prefix, and along any run every later final state is the earlier one with further records replayed on top: nothing final is undone or reordered.

The write-ahead order matters: if a record is acknowledged before it is logged, a crash in between loses an acknowledged write (early_ack_loses, a concrete three-step run).

Verification by replay

Determinism (replay_deterministic). Two validators replaying the same log from the same state reach the same state, so the final state can be recomputed from the durable log alone (final_verifiable).

One-step evidence (first_divergence, honest_no_divergence). Let a committer publish one state root before the first log record and one after each record, computed by a function HH of the state. If the published sequence has that length, starts at the genesis root but differs from the roots of the replay, there is an index ii whose root agrees with the replay while the next root does not match applying record ii, so record ii alone is the evidence. An honest committer’s roots pass every such check.

Limits

  • Reads answered by the volatile tier before finalisation are only as trustworthy as that tier; the guarantees above concern finalised state and recovery.
  • Roots are compared through HH. If HH maps different states to the same root, a wrong state can go undetected; in practice HH is a collision-resistant hash, which is an assumption, not a result here.
  • The model has one ordered log and one writer of it; consensus on that order and liveness of the log are not modelled.

Prior work

The log-structured merge-tree (Acta Informatica, 1996); write-ahead logging and recovery (ACM Transactions on Database Systems, 1992); a sorted-table storage system with memtables and compactions (OSDI 2006); verified key-value storage (OSDI 2020); optimistic execution with fraud proofs over a public log.

The Lean development

All definitions and proofs (878 lines, Lean 4, core library only)
/-!
# Abstract key-value semantics and log replay

An entry is a key paired with `some v` (a put) or `none` (a delete, i.e. a tombstone).
The abstract semantics of a sequence of entries is the left fold of point updates
over a total map `K → Option V`; this is the sequential map semantics against which
every tier of the store is judged.
-/

namespace TieredLSM

abbrev Entry (K V : Type) := K × Option V
/-- A sorted-string-table style segment, represented as an association list whose
first matching entry wins (newest first). -/
abbrev Seg (K V : Type) := List (Entry K V)
/-- The abstract state: a total map, `none` meaning "absent". -/
abbrev AMap (K V : Type) := K → Option V

variable {K V : Type} [DecidableEq K]

def emptyMap : AMap K V := fun _ => none

/-- Sequential semantics of one entry. -/
def apply (m : AMap K V) (e : Entry K V) : AMap K V :=
  fun k => if k = e.1 then e.2 else m k

/-- Replay of a log (oldest entry first) from a starting state. -/
def replay (m : AMap K V) (es : List (Entry K V)) : AMap K V := es.foldl apply m

@[simp] theorem replay_nil (m : AMap K V) : replay m [] = m := rfl

@[simp] theorem replay_cons (m : AMap K V) (e : Entry K V) (es : List (Entry K V)) :
    replay m (e :: es) = replay (apply m e) es := rfl

theorem replay_append (m : AMap K V) (a b : List (Entry K V)) :
    replay m (a ++ b) = replay (replay m a) b := by
  simp [replay, List.foldl_append]

theorem replay_snoc (m : AMap K V) (a : List (Entry K V)) (e : Entry K V) :
    replay m (a ++ [e]) = apply (replay m a) e := by
  simp [replay_append, replay]

/-- Left-biased choice: the first defined lookup wins (shadowing). -/
def orE {α : Type} : Option α → Option α → Option α
  | some a, _ => some a
  | none, b => b

@[simp] theorem orE_some {α : Type} (a : α) (b : Option α) : orE (some a) b = some a := rfl
@[simp] theorem orE_none {α : Type} (b : Option α) : orE none b = b := rfl
@[simp] theorem orE_none_right {α : Type} (a : Option α) : orE a none = a := by
  cases a <;> rfl
theorem orE_assoc {α : Type} (a b c : Option α) : orE (orE a b) c = orE a (orE b c) := by
  cases a <;> rfl

/-- Segment lookup: `none` = key not present in this segment, `some none` = tombstone,
`some (some v)` = live value. -/
def segGet : Seg K V → K → Option (Option V)
  | [], _ => none
  | (k', e) :: t, k => if k = k' then some e else segGet t k

/-- Lookup across a list of segments, newest first: the first segment that mentions
the key shadows every older one. -/
def levGet : List (Seg K V) → K → Option (Option V)
  | [], _ => none
  | s :: ss, k => orE (segGet s k) (levGet ss k)

/-- Turn a tiered lookup result into a client-visible answer: tombstone and absence
both read as `none`. -/
def resolve : Option (Option V) → Option V
  | some e => e
  | none => none

theorem segGet_append (a b : Seg K V) (k : K) :
    segGet (a ++ b) k = orE (segGet a k) (segGet b k) := by
  induction a with
  | nil => rfl
  | cons hd t ih =>
    obtain ⟨k', e⟩ := hd
    by_cases h : k = k' <;> simp [segGet, h, ih]

theorem levGet_append (A B : List (Seg K V)) (k : K) :
    levGet (A ++ B) k = orE (levGet A k) (levGet B k) := by
  induction A with
  | nil => rfl
  | cons s ss ih => simp [levGet, ih, orE_assoc]

theorem levGet_eq_segGet_flatten (ss : List (Seg K V)) (k : K) :
    levGet ss k = segGet ss.flatten k := by
  induction ss with
  | nil => rfl
  | cons s ss ih => simp [levGet, List.flatten, segGet_append, ih]

/-- Core shadowing lemma: looking a key up newest-first in an association list, falling
back to `m`, equals replaying the list oldest-first over `m`. -/
theorem segGet_fallback_replay (l : Seg K V) (m : AMap K V) (k : K) :
    (match segGet l k with | some e => e | none => m k) = replay m l.reverse k := by
  induction l with
  | nil => rfl
  | cons hd t ih =>
    obtain ⟨k', e⟩ := hd
    rw [List.reverse_cons, replay_snoc]
    by_cases h : k = k'
    · simp [segGet, apply, h]
    · simp only [segGet, apply, h, if_false]
      exact ih

end TieredLSM

/-!
# Theorem 1 (read correctness) and Theorem 2 (flush correctness)

The volatile tier is a memtable (newest entry first, duplicates allowed) above a list
of immutable levels ordered newest to oldest.
-/

namespace TieredLSM

variable {K V : Type} [DecidableEq K]

structure Store (K V : Type) where
  mem : Seg K V
  levels : List (Seg K V)

namespace Store

def empty : Store K V := ⟨[], []⟩

/-- Lookup through the memtable, then the levels newest to oldest; the first entry
found shadows all older ones, and a tombstone reads as absent. -/
def read (st : Store K V) (k : K) : Option V := resolve (levGet (st.mem :: st.levels) k)

/-- The chronological history the store represents: oldest entry first. -/
def chrono (st : Store K V) : List (Entry K V) := (st.mem :: st.levels).flatten.reverse

/-- A write (put or delete) goes to the head of the memtable. -/
def write (st : Store K V) (e : Entry K V) : Store K V := { st with mem := e :: st.mem }

end Store

open Store

/-- **Theorem 1 (read correctness).** For every store, the tiered lookup (memtable,
then levels newest-to-oldest, with shadowing and tombstones) equals the abstract map
obtained by replaying the store's history in order. -/
theorem read_correct (st : Store K V) (k : K) :
    st.read k = replay emptyMap st.chrono k := by
  have h := segGet_fallback_replay (st.mem :: st.levels).flatten (emptyMap) k
  simp only [Store.read, Store.chrono, levGet_eq_segGet_flatten]
  rw [← h]
  cases segGet (st.mem :: st.levels).flatten k <;> rfl

theorem read_eq_replay (st : Store K V) : st.read = replay emptyMap st.chrono :=
  funext (read_correct st)

omit [DecidableEq K] in
theorem chrono_write (st : Store K V) (e : Entry K V) :
    (st.write e).chrono = st.chrono ++ [e] := by
  simp [Store.chrono, Store.write, List.flatten]

/-- A write is the sequential map update. -/
theorem read_write (st : Store K V) (e : Entry K V) :
    (st.write e).read = apply st.read e := by
  rw [read_eq_replay, read_eq_replay, chrono_write, replay_snoc]

theorem read_foldl_write (es : List (Entry K V)) (st : Store K V) :
    (es.foldl Store.write st).read = replay st.read es := by
  induction es generalizing st with
  | nil => rfl
  | cons e es ih => simp [List.foldl, ih, read_write]

/-! ## Deduplicating newest-wins merge (used by flush and compaction) -/

/-- Whether an entry survives a merge; with `drop = true`, tombstones are discarded. -/
def keep (drop : Bool) : Option V → Bool
  | none => !drop
  | some _ => true

/-- Newest-wins merge of a newest-first concatenation of runs: the first occurrence of
each key is kept (and, if `drop`, removed when it is a tombstone), every later
occurrence is discarded. -/
def dd (drop : Bool) : List K → Seg K V → Seg K V
  | _, [] => []
  | seen, (k, e) :: t =>
    if k ∈ seen then dd drop seen t
    else if keep drop e then (k, e) :: dd drop (k :: seen) t
    else dd drop (k :: seen) t

/-- Effect of a merge on one key's lookup result. -/
def adj (drop : Bool) : Option (Option V) → Option (Option V)
  | some none => if drop then none else some none
  | x => x

@[simp] theorem adj_false (x : Option (Option V)) : adj false x = x := by
  rcases x with _ | _ | _ <;> rfl

theorem segGet_dd (drop : Bool) (seen : List K) (l : Seg K V) (k : K) :
    segGet (dd drop seen l) k = if k ∈ seen then none else adj drop (segGet l k) := by
  induction l generalizing seen with
  | nil => by_cases h : k ∈ seen <;> simp [dd, segGet, adj, h]
  | cons hd t ih =>
    obtain ⟨k', e⟩ := hd
    by_cases hs : k' ∈ seen
    · simp only [dd, hs, if_true, ih]
      by_cases hk : k = k'
      · subst hk; simp [hs]
      · simp [segGet, hk]
    · by_cases hk : k = k'
      · subst hk
        cases e <;> cases drop <;> simp [dd, keep, segGet, adj, hs, ih]
      · have hiff : (k ∈ k' :: seen) ↔ (k ∈ seen) := by simp [hk]
        cases hkeep : keep drop e <;>
          simp [dd, hs, hkeep, segGet, hk, ih, hiff]

theorem segGet_merge (l : Seg K V) (k : K) : segGet (dd false [] l) k = segGet l k := by
  simp [segGet_dd]

/-! ## Flush -/

namespace Store
/-- Flush: the memtable becomes a new, deduplicated newest level; the memtable empties. -/
def flush (st : Store K V) : Store K V := ⟨[], dd false [] st.mem :: st.levels⟩
end Store

/-- **Theorem 2 (flush correctness).** Flushing never changes any read. -/
theorem read_flush (st : Store K V) : st.flush.read = st.read := by
  funext k
  simp [Store.read, Store.flush, levGet, segGet, segGet_merge]

end TieredLSM

/-!
# Theorem 3 (compaction)

Compaction replaces the `n` consecutive levels starting at index `i` by their
newest-wins merge. With `drop = true` the merge also discards tombstones.
-/

namespace TieredLSM

variable {K V : Type} [DecidableEq K]

namespace Store
def compact (drop : Bool) (st : Store K V) (i n : Nat) : Store K V :=
  { st with levels :=
      st.levels.take i ++ dd drop [] ((st.levels.drop i).take n).flatten
        :: (st.levels.drop i).drop n }
end Store

omit [DecidableEq K] in
theorem levels_split (L : List (Seg K V)) (i n : Nat) :
    L = L.take i ++ ((L.drop i).take n ++ (L.drop i).drop n) := by
  rw [List.take_append_drop n (L.drop i), List.take_append_drop]

theorem levGet_compact (drop : Bool) (st : Store K V) (i n : Nat) (k : K) :
    levGet (st.compact drop i n).levels k =
      orE (levGet (st.levels.take i) k)
        (orE (adj drop (levGet ((st.levels.drop i).take n) k))
          (levGet ((st.levels.drop i).drop n) k)) := by
  simp only [Store.compact, levGet_append, levGet, segGet_dd, List.not_mem_nil, if_false,
    ← levGet_eq_segGet_flatten]

theorem levGet_levels (st : Store K V) (i n : Nat) (k : K) :
    levGet st.levels k =
      orE (levGet (st.levels.take i) k)
        (orE (levGet ((st.levels.drop i).take n) k) (levGet ((st.levels.drop i).drop n) k)) := by
  conv => lhs; rw [levels_split st.levels i n]
  simp [levGet_append]

/-- **Theorem 3a (compaction preserves the abstract map).** Merging any window of
consecutive levels, newest wins, keeping tombstones, never changes any read. -/
theorem read_compact (st : Store K V) (i n : Nat) :
    (st.compact false i n).read = st.read := by
  funext k
  simp only [Store.read, levGet]
  rw [levGet_compact, levGet_levels st i n, adj_false]
  rfl

theorem resolve_orE_congr (a x y : Option (Option V)) (h : resolve x = resolve y) :
    resolve (orE a x) = resolve (orE a y) := by
  cases a <;> simp [h]

/-- **Theorem 3b, (⇐): dropping tombstones at the bottom is safe.** If the compaction
window reaches the oldest level, discarding tombstones never changes any read. -/
theorem read_compact_drop_bottom (st : Store K V) (i n : Nat)
    (hb : st.levels.length ≤ i + n) : (st.compact true i n).read = st.read := by
  funext k
  have hnil : (st.levels.drop i).drop n = [] := by
    apply List.drop_eq_nil_of_le; simp; omega
  simp only [Store.read, levGet]
  rw [levGet_compact, levGet_levels st i n, hnil]
  apply resolve_orE_congr
  simp only [levGet, orE_none_right]
  apply resolve_orE_congr
  rcases levGet ((st.levels.drop i).take n) k with _ | _ | _ <;> rfl

/-! ## Counterexample: dropping tombstones above the bottom -/

def tombLevels (k0 : K) (v0 : V) (L i n : Nat) : List (Seg K V) :=
  List.replicate i [] ++ (List.replicate n [(k0, none)] ++ List.replicate (L - (i + n)) [(k0, some v0)])

theorem levGet_replicate_nil (m : Nat) (k : K) :
    levGet (List.replicate m ([] : Seg K V)) k = none := by
  induction m with
  | zero => rfl
  | succ m ih => simp [List.replicate_succ, levGet, segGet, ih]

theorem levGet_replicate_one (m : Nat) (hm : 0 < m) (k : K) (e : Option V) :
    levGet (List.replicate m [(k, e)]) k = some e := by
  cases m with
  | zero => omega
  | succ m => simp [List.replicate_succ, levGet, segGet]

/-- A concrete witness: a tombstone in the window shadows an older value below the
window; dropping it resurrects the value. -/
theorem compact_drop_above_bottom_unsafe (k0 : K) (v0 : V) (L i n : Nat)
    (hn : 0 < n) (hab : i + n < L) :
    let st : Store K V := ⟨[], tombLevels k0 v0 L i n⟩
    st.levels.length = L ∧ st.read k0 = none ∧ (st.compact true i n).read k0 = some v0 := by
  intro st
  have hlen : st.levels.length = L := by simp [st, tombLevels]; omega
  have htake : st.levels.take i = List.replicate i [] := by
    simp [st, tombLevels, List.take_append_of_le_length]
  have hdrop : st.levels.drop i =
      List.replicate n [(k0, none)] ++ List.replicate (L - (i + n)) [(k0, some v0)] := by
    simp [st, tombLevels]
  have hwin : (st.levels.drop i).take n = List.replicate n [(k0, none)] := by
    rw [hdrop]; simp [List.take_append_of_le_length]
  have hrest : (st.levels.drop i).drop n = List.replicate (L - (i + n)) [(k0, some v0)] := by
    rw [hdrop]; simp
  refine ⟨hlen, ?_, ?_⟩
  · simp only [Store.read, levGet, segGet]
    rw [levGet_levels st i n, htake, hwin, levGet_replicate_nil, levGet_replicate_one n hn]
    rfl
  · simp only [Store.read, levGet, segGet]
    rw [levGet_compact, htake, hwin, hrest, levGet_replicate_nil,
      levGet_replicate_one n hn, levGet_replicate_one _ (by omega)]
    rfl

/-- **Theorem 3b (tombstone dropping is safe iff it happens at the bottom).** For a
non-empty window `[i, i+n)` over stores with `L` levels, dropping tombstones during
compaction preserves every read of every such store if and only if the window reaches
the bottom level (`L ≤ i + n`). -/
theorem tombstone_drop_safe_iff [Inhabited K] [Inhabited V] (L i n : Nat) (hn : 0 < n) :
    (∀ st : Store K V, st.levels.length = L → (st.compact true i n).read = st.read) ↔
      L ≤ i + n := by
  constructor
  · intro h
    apply Classical.byContradiction
    intro hlt
    have hab : i + n < L := by omega
    obtain ⟨hlen, h1, h2⟩ :=
      compact_drop_above_bottom_unsafe (K := K) (V := V) default default L i n hn hab
    have := congrFun (h _ hlen) default
    rw [h1, h2] at this
    cases this
  · intro hb st hlen
    exact read_compact_drop_bottom st i n (by omega)

/-! ## Theorem 1, run form: reads equal the sequential semantics of all writes -/

/-- Runs of the volatile tier: writes, flushes, compactions (tombstones kept), and
compactions that drop tombstones in a window reaching the bottom level. The list
records the writes in issue order. -/
inductive SRun : Store K V → List (Entry K V) → Prop
  | init : SRun Store.empty []
  | write {st w} (e : Entry K V) : SRun st w → SRun (st.write e) (w ++ [e])
  | flush {st w} : SRun st w → SRun st.flush w
  | compact {st w} (i n : Nat) : SRun st w → SRun (st.compact false i n) w
  | compactBottom {st w} (i n : Nat) :
      st.levels.length ≤ i + n → SRun st w → SRun (st.compact true i n) w

/-- **Theorem 1 (run form).** After any interleaving of writes, flushes and (safe)
compactions, every read equals the sequential map semantics of the writes issued. -/
theorem read_correct_run {st : Store K V} {w : List (Entry K V)} (h : SRun st w) :
    st.read = replay emptyMap w := by
  induction h with
  | init => funext k; rfl
  | write e _ ih => rw [read_write, ih, replay_snoc]
  | flush _ ih => rw [read_flush, ih]
  | compact i n _ ih => rw [read_compact, ih]
  | compactBottom i n hb _ ih => rw [read_compact_drop_bottom _ _ _ hb, ih]

end TieredLSM

/-!
# Theorem 4 (re-encoding compaction)

Durable levels are stored as opaque encoded blobs of type `B`. A decoder `dec` maps a
blob back to a segment. Re-encoding replaces a blob by another one (for instance,
decode and encode under a different codec). Only the semantics of the decoded segment
matters, so the weakest sufficient condition is *semantic losslessness*.
-/

namespace TieredLSM

variable {K V : Type} [DecidableEq K]

/-- A store whose levels are encoded blobs. -/
structure EStore (K V B : Type) where
  mem : Seg K V
  levels : List B

/-- What an encoded store means, given a decoder. -/
def EStore.view {B : Type} (dec : B → Seg K V) (es : EStore K V B) : Store K V :=
  ⟨es.mem, es.levels.map dec⟩

/-- Encode every level of a store. -/
def encodeStore {B : Type} (enc : Seg K V → B) (st : Store K V) : EStore K V B :=
  ⟨st.mem, st.levels.map enc⟩

/-- A blob transformation is semantically lossless under `dec` if it never changes the
answer of any segment lookup. -/
def SemLossless {B : Type} (dec : B → Seg K V) (r : B → B) : Prop :=
  ∀ b k, segGet (dec (r b)) k = segGet (dec b) k

/-- Apply `r` to the levels selected by `sel` (indexed from `j`). -/
def mapSel {α : Type} (r : α → α) (sel : Nat → Bool) : Nat → List α → List α
  | _, [] => []
  | j, x :: xs => (if sel j then r x else x) :: mapSel r sel (j + 1) xs

/-- Re-encode an arbitrary selection of durable levels. -/
def EStore.reencode {B : Type} (r : B → B) (sel : Nat → Bool) (es : EStore K V B) :
    EStore K V B :=
  ⟨es.mem, mapSel r sel 0 es.levels⟩

theorem levGet_mapSel {B : Type} (dec : B → Seg K V) (r : B → B) (hr : SemLossless dec r)
    (sel : Nat → Bool) (j : Nat) (bs : List B) (k : K) :
    levGet ((mapSel r sel j bs).map dec) k = levGet (bs.map dec) k := by
  induction bs generalizing j with
  | nil => rfl
  | cons b bs ih =>
    by_cases hs : sel j = true <;> simp [mapSel, levGet, hs, ih, hr b k]

/-- **Theorem 4 (re-encoding preserves state), general form.** Re-encoding any subset
of durable levels with a semantically lossless transformation preserves every read. -/
theorem read_reencode {B : Type} (dec : B → Seg K V) (r : B → B) (hr : SemLossless dec r)
    (sel : Nat → Bool) (es : EStore K V B) :
    ((es.reencode r sel).view dec).read = (es.view dec).read := by
  funext k
  simp only [Store.read, EStore.view, EStore.reencode, levGet]
  rw [levGet_mapSel dec r hr]

/-- Exact round trip implies semantic losslessness of decode-then-re-encode. -/
theorem semLossless_of_roundtrip {B : Type} (dec : B → Seg K V) (enc : Seg K V → B)
    (h : ∀ s, dec (enc s) = s) : SemLossless dec (enc ∘ dec) := by
  intro b k; simp [h]

/-- **Theorem 4 (codec form).** For any codec with `decode ∘ encode = id`, re-encoding
any selection of durable levels (decode, then encode with that codec) preserves state. -/
theorem read_reencode_codec {B : Type} (dec : B → Seg K V) (enc : Seg K V → B)
    (h : ∀ s, dec (enc s) = s) (sel : Nat → Bool) (es : EStore K V B) :
    ((es.reencode (enc ∘ dec) sel).view dec).read = (es.view dec).read :=
  read_reencode dec _ (semLossless_of_roundtrip dec enc h) sel es

/-- Encoding a whole store with a lossless codec preserves state. -/
theorem read_encodeStore {B : Type} (dec : B → Seg K V) (enc : Seg K V → B)
    (h : ∀ s, dec (enc s) = s) (st : Store K V) :
    ((encodeStore enc st).view dec).read = st.read := by
  have : (st.levels.map enc).map dec = st.levels := by
    rw [List.map_map]
    conv => rhs; rw [← List.map_id st.levels]
    congr 1; funext s; exact h s
  simp [EStore.view, encodeStore, this]

/-- Re-encoding compaction: decode the durable levels, compact (keeping tombstones, or
dropping them when the window reaches the bottom), and encode the result with a
possibly different codec `enc'`. -/
def EStore.compactReencode {B B' : Type} (dec : B → Seg K V) (enc' : Seg K V → B')
    (drop : Bool) (i n : Nat) (es : EStore K V B) : EStore K V B' :=
  encodeStore enc' ((es.view dec).compact drop i n)

/-- **Theorem 4 (re-encoding compaction).** Compaction followed by encoding under any
codec `(enc', dec')` with `dec' ∘ enc' = id` preserves the abstract state; tombstones may
be dropped when the window reaches the bottom level. -/
theorem read_compactReencode {B B' : Type} (dec : B → Seg K V) (enc' : Seg K V → B')
    (dec' : B' → Seg K V) (h : ∀ s, dec' (enc' s) = s) (drop : Bool) (i n : Nat)
    (es : EStore K V B) (hsafe : drop = false ∨ es.levels.length ≤ i + n) :
    ((es.compactReencode dec enc' drop i n).view dec').read = (es.view dec).read := by
  simp only [EStore.compactReencode]
  rw [read_encodeStore dec' enc' h]
  rcases hsafe with hd | hb
  · subst hd; exact read_compact _ i n
  · cases drop
    · exact read_compact _ i n
    · exact read_compact_drop_bottom _ i n (by simpa [EStore.view] using hb)

end TieredLSM

/-!
# Theorem 5 (write-ahead durability) and Theorem 6 (finality monotonicity)

The system has a durable ordered log (append-only), a durable checkpoint (levels
persisted together with the log position they cover), a durable finalised prefix with
its incrementally maintained state, and a volatile tier that may be lost at any time.
Writes are acknowledged only for records already in the durable log (`acked ≤ |log|`).
-/

namespace TieredLSM

variable {K V : Type} [DecidableEq K]

structure Sys (K V : Type) where
  log : List (Entry K V)
  acked : Nat
  ck : Nat
  ckLevels : List (Seg K V)
  fin : Nat
  finMap : AMap K V
  vol : Option (Store K V)

def Sys.init : Sys K V := ⟨[], 0, 0, [], 0, emptyMap, some Store.empty⟩

/-- Recovery: start from the checkpointed levels and replay the log suffix after the
checkpoint into a fresh memtable. -/
def Sys.recoverStore (σ : Sys K V) : Store K V :=
  (σ.log.drop σ.ck).foldl Store.write ⟨[], σ.ckLevels⟩

inductive Step : Sys K V → Sys K V → Prop
  /-- Write-ahead: the record is appended to the durable log, then applied to the
  volatile tier. -/
  | append (σ : Sys K V) (st : Store K V) (e : Entry K V) : σ.vol = some st →
      Step σ { σ with log := σ.log ++ [e], vol := some (st.write e) }
  /-- Acknowledge the oldest unacknowledged record; only logged records can be acked. -/
  | ack (σ : Sys K V) : σ.acked < σ.log.length → Step σ { σ with acked := σ.acked + 1 }
  | flush (σ : Sys K V) (st : Store K V) : σ.vol = some st →
      Step σ { σ with vol := some st.flush }
  | compact (σ : Sys K V) (st : Store K V) (i n : Nat) : σ.vol = some st →
      Step σ { σ with vol := some (st.compact false i n) }
  | compactBottom (σ : Sys K V) (st : Store K V) (i n : Nat) : σ.vol = some st →
      st.levels.length ≤ i + n → Step σ { σ with vol := some (st.compact true i n) }
  /-- Persist the flushed levels together with the log position they cover. -/
  | checkpoint (σ : Sys K V) (st : Store K V) : σ.vol = some st →
      Step σ { σ with ck := σ.log.length, ckLevels := st.flush.levels }
  /-- Asynchronous finalisation of any longer log prefix, incrementally. -/
  | finalise (σ : Sys K V) (n : Nat) : σ.fin ≤ n → n ≤ σ.log.length →
      Step σ { σ with fin := n,
                      finMap := replay σ.finMap ((σ.log.drop σ.fin).take (n - σ.fin)) }
  /-- Loss of the volatile tier, at any moment. -/
  | crash (σ : Sys K V) : Step σ { σ with vol := none }
  | recover (σ : Sys K V) : σ.vol = none → Step σ { σ with vol := some σ.recoverStore }

/-- Reflexive-transitive closure: runs. -/
inductive Steps : Sys K V → Sys K V → Prop
  | refl (σ : Sys K V) : Steps σ σ
  | tail {σ τ υ : Sys K V} : Steps σ τ → Step τ υ → Steps σ υ

def Reach (σ : Sys K V) : Prop := Steps Sys.init σ

/-- The system invariant. -/
structure Inv (σ : Sys K V) : Prop where
  acked_le : σ.acked ≤ σ.log.length
  ck_le : σ.ck ≤ σ.log.length
  fin_le : σ.fin ≤ σ.log.length
  ck_ok : (⟨[], σ.ckLevels⟩ : Store K V).read = replay emptyMap (σ.log.take σ.ck)
  fin_ok : σ.finMap = replay emptyMap (σ.log.take σ.fin)
  vol_ok : ∀ st, σ.vol = some st → st.read = replay emptyMap σ.log

theorem inv_init : Inv (Sys.init : Sys K V) where
  acked_le := Nat.le_refl _
  ck_le := Nat.le_refl _
  fin_le := Nat.le_refl _
  ck_ok := by funext k; rfl
  fin_ok := rfl
  vol_ok := by intro st h; cases h; funext k; rfl

theorem read_recoverStore (σ : Sys K V) (hI : Inv σ) :
    σ.recoverStore.read = replay emptyMap σ.log := by
  rw [Sys.recoverStore, read_foldl_write, hI.ck_ok, ← replay_append, List.take_append_drop]

theorem inv_step {σ τ : Sys K V} (hI : Inv σ) (h : Step σ τ) : Inv τ := by
  cases h with
  | append st e hv =>
    exact {
      acked_le := by simp; have := hI.acked_le; omega
      ck_le := by simp; have := hI.ck_le; omega
      fin_le := by simp; have := hI.fin_le; omega
      ck_ok := by simp only; rw [List.take_append_of_le_length hI.ck_le]; exact hI.ck_ok
      fin_ok := by simp only; rw [List.take_append_of_le_length hI.fin_le]; exact hI.fin_ok
      vol_ok := by
        intro st' h'; cases h'
        rw [read_write, hI.vol_ok st hv, replay_snoc] }
  | ack hlt =>
    exact { hI with acked_le := by simp; omega }
  | flush st hv =>
    refine { hI with vol_ok := ?_ }
    intro st' h'; cases h'; rw [read_flush]; exact hI.vol_ok st hv
  | compact st i n hv =>
    refine { hI with vol_ok := ?_ }
    intro st' h'; cases h'; rw [read_compact]; exact hI.vol_ok st hv
  | compactBottom st i n hv hb =>
    refine { hI with vol_ok := ?_ }
    intro st' h'; cases h'; rw [read_compact_drop_bottom _ _ _ hb]; exact hI.vol_ok st hv
  | checkpoint st hv =>
    exact { hI with
      ck_le := Nat.le_refl _
      ck_ok := by
        simp only [List.take_length]
        have : (⟨[], st.flush.levels⟩ : Store K V) = st.flush := rfl
        rw [this, read_flush]; exact hI.vol_ok st hv }
  | finalise n h1 h2 =>
    exact { hI with
      fin_le := h2
      fin_ok := by
        simp only
        rw [hI.fin_ok, ← replay_append, ← List.take_add, Nat.add_sub_of_le h1] }
  | crash =>
    exact { hI with vol_ok := by intro st h'; cases h' }
  | recover hv =>
    exact { hI with vol_ok := by intro st h'; cases h'; exact read_recoverStore σ hI }

theorem inv_steps {σ τ : Sys K V} (hI : Inv σ) (h : Steps σ τ) : Inv τ := by
  induction h with
  | refl => exact hI
  | tail _ hs ih => exact inv_step ih hs

theorem inv_reach {σ : Sys K V} (h : Reach σ) : Inv σ := inv_steps inv_init h

theorem reach_steps {σ τ : Sys K V} (hσ : Reach σ) (h : Steps σ τ) : Reach τ := by
  induction h with
  | refl => exact hσ
  | tail _ s ih => exact Steps.tail ih s

/-! ## Theorem 5: write-ahead durability -/

/-- **Theorem 5a (recovery is exact).** In every reachable state, whatever was lost,
recovery from the checkpoint plus the durable log suffix yields exactly the
sequential semantics of the durable log. -/
theorem recovery_exact {σ : Sys K V} (h : Reach σ) :
    σ.recoverStore.read = replay emptyMap σ.log :=
  read_recoverStore σ (inv_reach h)

/-- Acknowledged records are a prefix of the durable log, so recovered state extends
the acknowledged state by replaying the (possibly empty) logged-but-unacknowledged
suffix. -/
theorem recovery_extends_acked {σ : Sys K V} (h : Reach σ) :
    σ.recoverStore.read =
      replay (replay emptyMap (σ.log.take σ.acked)) (σ.log.drop σ.acked) := by
  rw [recovery_exact h, ← replay_append, List.take_append_drop]

/-- **Theorem 5b (recovery = acknowledged state).** If every logged record has been
acknowledged, recovery after any loss of the volatile tier yields exactly the
acknowledged state. -/
theorem recovery_eq_acked {σ : Sys K V} (h : Reach σ) (hq : σ.acked = σ.log.length) :
    σ.recoverStore.read = replay emptyMap (σ.log.take σ.acked) := by
  rw [recovery_exact h, hq, List.take_length]

/-! ## Theorem 6: finality monotonicity -/

theorem take_prefix_take {α : Type} {l₁ l₂ : List α} {a b : Nat} (hp : l₁ <+: l₂)
    (ha : a ≤ l₁.length) (hab : a ≤ b) : l₁.take a <+: l₂.take b := by
  obtain ⟨t, rfl⟩ := hp
  have : (l₁ ++ t).take a = l₁.take a := List.take_append_of_le_length ha
  rw [← this]
  have h2 : ((l₁ ++ t).take b).take a = (l₁ ++ t).take a := by
    rw [List.take_take, Nat.min_eq_left hab]
  rw [← h2]
  exact List.take_prefix _ _

/-- One step never truncates the log, never lowers the finalised index or the
acknowledgement counter, and never changes the finalised prefix except by extending it. -/
theorem step_monotone {σ τ : Sys K V} (hI : Inv σ) (h : Step σ τ) :
    σ.log <+: τ.log ∧ σ.fin ≤ τ.fin ∧ σ.acked ≤ τ.acked ∧
      σ.log.take σ.fin <+: τ.log.take τ.fin := by
  have hrefl : ∀ l : List (Entry K V), l <+: l := fun l => List.prefix_refl l
  cases h with
  | append st e hv =>
    refine ⟨List.prefix_append _ _, Nat.le_refl _, Nat.le_refl _, ?_⟩
    simp only; rw [List.take_append_of_le_length hI.fin_le]; exact hrefl _
  | finalise n h1 h2 =>
    exact ⟨hrefl _, h1, Nat.le_refl _, take_prefix_take (hrefl _) hI.fin_le h1⟩
  | ack hlt => exact ⟨hrefl _, Nat.le_refl _, Nat.le_succ _, hrefl _⟩
  | flush => exact ⟨hrefl _, Nat.le_refl _, Nat.le_refl _, hrefl _⟩
  | compact => exact ⟨hrefl _, Nat.le_refl _, Nat.le_refl _, hrefl _⟩
  | compactBottom => exact ⟨hrefl _, Nat.le_refl _, Nat.le_refl _, hrefl _⟩
  | checkpoint => exact ⟨hrefl _, Nat.le_refl _, Nat.le_refl _, hrefl _⟩
  | crash => exact ⟨hrefl _, Nat.le_refl _, Nat.le_refl _, hrefl _⟩
  | recover => exact ⟨hrefl _, Nat.le_refl _, Nat.le_refl _, hrefl _⟩

/-- **Theorem 6 (finality monotonicity), run form.** Along any run from a reachable
state, under any interleaving of writes, acknowledgements, flushes, compactions,
checkpoints, finalisations, crashes and recoveries: the durable log only grows, the
finalised index never decreases, and the finalised prefix is only ever extended. -/
theorem final_prefix_monotone {σ τ : Sys K V} (hσ : Reach σ) (h : Steps σ τ) :
    σ.log <+: τ.log ∧ σ.fin ≤ τ.fin ∧ σ.acked ≤ τ.acked ∧
      σ.log.take σ.fin <+: τ.log.take τ.fin := by
  induction h with
  | refl => exact ⟨List.prefix_refl _, Nat.le_refl _, Nat.le_refl _, List.prefix_refl _⟩
  | @tail τ υ hst hs ih =>
    have hτ : Reach τ := reach_steps hσ hst
    obtain ⟨a, b, c, d⟩ := ih
    obtain ⟨a', b', c', d'⟩ := step_monotone (inv_reach hτ) hs
    exact ⟨a.trans a', Nat.le_trans b b', Nat.le_trans c c', d.trans d'⟩

/-- **Theorem 6 (the final state is a prefix replay).** In every reachable state the
incrementally maintained final state equals the replay of the finalised log prefix. -/
theorem final_is_prefix_replay {σ : Sys K V} (h : Reach σ) :
    σ.finMap = replay emptyMap (σ.log.take σ.fin) :=
  (inv_reach h).fin_ok

/-- **Theorem 6 (nothing final is rolled back).** Any later final state is obtained from
any earlier final state by replaying further log records; the earlier finalised
records are never undone or reordered. -/
theorem final_never_rolled_back {σ τ : Sys K V} (hσ : Reach σ) (h : Steps σ τ) :
    ∃ ext, τ.log.take τ.fin = σ.log.take σ.fin ++ ext ∧ τ.finMap = replay σ.finMap ext := by
  obtain ⟨_, _, _, ⟨ext, hext⟩⟩ := final_prefix_monotone hσ h
  have hτ : Reach τ := reach_steps hσ h
  refine ⟨ext, hext.symm, ?_⟩
  rw [final_is_prefix_replay hτ, final_is_prefix_replay hσ, ← hext, replay_append]

/-- **Acknowledged records are never lost.** Along any run, the acknowledged prefix of
an earlier state remains a prefix of every later durable log, and every later volatile
or recovered state is a replay of a log extending it. -/
theorem acked_never_lost {σ τ : Sys K V} (hσ : Reach σ) (h : Steps σ τ) :
    σ.log.take σ.acked <+: τ.log ∧
      τ.recoverStore.read =
        replay (replay emptyMap (σ.log.take σ.acked)) (τ.log.drop σ.acked) := by
  have hτ : Reach τ := reach_steps hσ h
  obtain ⟨hp, _, _, _⟩ := final_prefix_monotone hσ h
  have hpre : σ.log.take σ.acked <+: τ.log := (List.take_prefix _ _).trans hp
  refine ⟨hpre, ?_⟩
  have hle := (inv_reach hσ).acked_le
  have htk : τ.log.take σ.acked = σ.log.take σ.acked := by
    obtain ⟨t, ht⟩ := hp
    rw [← ht, List.take_append_of_le_length hle]
  rw [recovery_exact hτ, ← htk, ← replay_append, List.take_append_drop]

/-! ## Necessity of write-ahead: acknowledging before logging loses data -/

/-- A variant protocol that acknowledges and applies a write in the volatile tier
before the record reaches the durable log. -/
structure ESys (K V : Type) where
  log : List (Entry K V)
  pending : List (Entry K V)
  acked : List (Entry K V)
  vol : Option (AMap K V)

inductive EStep : ESys K V → ESys K V → Prop
  | writeAck (σ : ESys K V) (m : AMap K V) (e : Entry K V) : σ.vol = some m →
      EStep σ { σ with pending := σ.pending ++ [e], acked := σ.acked ++ [e],
                       vol := some (apply m e) }
  | persist (σ : ESys K V) (e : Entry K V) (rest : List (Entry K V)) :
      σ.pending = e :: rest → EStep σ { σ with log := σ.log ++ [e], pending := rest }
  | crash (σ : ESys K V) : EStep σ { σ with pending := [], vol := none }
  | recover (σ : ESys K V) : σ.vol = none →
      EStep σ { σ with vol := some (replay emptyMap σ.log) }

/-- **Counterexample.** Without write-ahead ordering, a crash between acknowledgement
and logging loses an acknowledged write: the recovered state differs from the
acknowledged state. -/
theorem early_ack_loses (k : K) (v : V) :
    let s0 : ESys K V := ⟨[], [], [], some emptyMap⟩
    let s1 : ESys K V := ⟨[], [(k, some v)], [(k, some v)], some (apply emptyMap (k, some v))⟩
    let s2 : ESys K V := ⟨[], [], [(k, some v)], none⟩
    let s3 : ESys K V := ⟨[], [], [(k, some v)], some emptyMap⟩
    EStep s0 s1 ∧ EStep s1 s2 ∧ EStep s2 s3 ∧
      replay emptyMap s3.acked k = some v ∧ s3.vol = some emptyMap ∧ emptyMap k = (none : Option V) := by
  refine ⟨EStep.writeAck _ _ _ rfl, EStep.crash _, EStep.recover _ rfl, ?_, rfl, rfl⟩
  simp [replay, apply]

end TieredLSM

/-!
# Theorem 7 (verifiability by replay)

A committer publishes a list of state roots, one before the first log record and one
after each record. `H` is an arbitrary state-digest function (e.g. a Merkle root); no
property of `H` is needed for the theorems below. Collision resistance of `H` is what
makes a matching root at index `i` pin down the state at index `i` (not proved here).
-/

namespace TieredLSM

variable {K V : Type} [DecidableEq K]

/-- Relational (big-step) replay semantics. -/
inductive Replays : AMap K V → List (Entry K V) → AMap K V → Prop
  | nil (m : AMap K V) : Replays m [] m
  | cons (m : AMap K V) (e : Entry K V) (es : List (Entry K V)) (m' : AMap K V) :
      Replays (apply m e) es m' → Replays m (e :: es) m'

theorem replays_iff (m : AMap K V) (es : List (Entry K V)) (m' : AMap K V) :
    Replays m es m' ↔ m' = replay m es := by
  constructor
  · intro h
    induction h with
    | nil => rfl
    | cons m e es m' _ ih => simpa using ih
  · intro h; subst h
    induction es generalizing m with
    | nil => exact Replays.nil m
    | cons e es ih => exact Replays.cons m e es _ (ih (apply m e))

/-- **Theorem 7a (replay is deterministic).** Any two validators replaying the same log
from the same state reach the same state. -/
theorem replay_deterministic {m m₁ m₂ : AMap K V} {es : List (Entry K V)}
    (h₁ : Replays m es m₁) (h₂ : Replays m es m₂) : m₁ = m₂ := by
  rw [(replays_iff _ _ _).1 h₁, (replays_iff _ _ _).1 h₂]

/-- The roots an honest committer publishes. -/
def honestRoots {R : Type} (H : AMap K V → R) : AMap K V → List (Entry K V) → List R
  | m, [] => [H m]
  | m, e :: es => H m :: honestRoots H (apply m e) es

theorem honestRoots_length {R : Type} (H : AMap K V → R) (m : AMap K V)
    (es : List (Entry K V)) : (honestRoots H m es).length = es.length + 1 := by
  induction es generalizing m with
  | nil => rfl
  | cons e es ih => simp [honestRoots, ih]

theorem honestRoots_get {R : Type} (H : AMap K V → R) (m : AMap K V)
    (es : List (Entry K V)) (i : Nat) (hi : i ≤ es.length) :
    (honestRoots H m es)[i]? = some (H (replay m (es.take i))) := by
  induction es generalizing m i with
  | nil => cases i with
    | zero => rfl
    | succ i => simp at hi
  | cons e es ih => cases i with
    | zero => simp [honestRoots]
    | succ i =>
      simp only [honestRoots, List.getElem?_cons_succ, List.take_succ_cons, replay_cons]
      exact ih _ i (by simpa using hi)

/-- **Theorem 7c (an honest committer never diverges).** Every one-step check against
the honest roots succeeds. -/
theorem honest_no_divergence {R : Type} (H : AMap K V → R) (m₀ : AMap K V)
    (es : List (Entry K V)) (i : Nat) (e : Entry K V) (he : es[i]? = some e) :
    (honestRoots H m₀ es)[i + 1]? = some (H (apply (replay m₀ (es.take i)) e)) := by
  have hi : i < es.length := by
    rcases Nat.lt_or_ge i es.length with h | h
    · exact h
    · rw [List.getElem?_eq_none h] at he; cases he
  rw [honestRoots_get H m₀ es (i + 1) hi]
  congr 2
  rw [List.take_add, replay_append]
  congr 1
  rw [List.drop_eq_getElem_cons hi] at *
  have : es[i] = e := by
    rw [List.getElem?_eq_getElem hi] at he; exact Option.some.inj he
  simp [this]

/-- **Theorem 7b (first divergence, one-step evidence).** If published roots of the
right length agree on the genesis root but differ from the replay of the durable log,
there is a log index `i` such that the root at `i` is correct, and the root at `i+1`
differs from the digest of applying the single record `i` to the state at `i`. A
challenger therefore needs to exhibit only one record and one state transition. -/
theorem first_divergence {R : Type} (H : AMap K V → R) (m₀ : AMap K V)
    (es : List (Entry K V)) (roots : List R) (hlen : roots.length = es.length + 1)
    (h0 : roots[0]? = some (H m₀)) (hne : roots ≠ honestRoots H m₀ es) :
    ∃ i e, es[i]? = some e ∧
      roots[i]? = some (H (replay m₀ (es.take i))) ∧
      roots[i + 1]? ≠ some (H (apply (replay m₀ (es.take i)) e)) := by
  induction es generalizing m₀ roots with
  | nil =>
    exfalso; apply hne
    match roots, hlen, h0 with
    | [r], _, h0 => simp at h0; simp [honestRoots, h0]
  | cons e es ih =>
    match roots, hlen, h0, hne with
    | r0 :: r1 :: rest, hlen, h0, hne =>
      simp at h0
      by_cases h1 : r1 = H (apply m₀ e)
      · have hne' : r1 :: rest ≠ honestRoots H (apply m₀ e) es := by
          intro hc; apply hne; rw [h0, hc]; rfl
        obtain ⟨i, e', hi, hr, hd⟩ :=
          ih (apply m₀ e) (r1 :: rest) (by simpa using hlen) (by simp [h1]) hne'
        refine ⟨i + 1, e', by simpa using hi, ?_, ?_⟩
        · simpa [List.take_succ_cons] using hr
        · simpa [List.take_succ_cons] using hd
      · refine ⟨0, e, by simp, by simp [h0], ?_⟩
        simp [h1]

/-- Validators can recompute the final state of any reachable system state from the
durable log alone (combining Theorem 6 with Theorem 7a). -/
theorem final_verifiable {σ : Sys K V} (h : Reach σ) (m : AMap K V)
    (hv : Replays emptyMap (σ.log.take σ.fin) m) : m = σ.finMap := by
  rw [final_is_prefix_replay h]; exact (replays_iff _ _ _).1 hv

end TieredLSM