Research / 2025 –

Checking a batch of state accesses offline

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

Offline memory checking for a key–value state: a batch of transactions is verified from a log sorted by key and version, using only checks on single rows, checks on consecutive rows and one permutation argument. A Lean proof shows that the checks force every access to have seen the value of its key just before it and the claimed post-state to equal sequential execution, and that distinct versions cannot be dropped.

Memory checkingPermutation argumentsVerifiable computation
2 rows
the most any check reads, apart from the single permutation argument
O(n log n)
witness construction for n accesses, dominated by sorting the log
1 tie
two accesses sharing a version break order recovery, and with it soundness when the committed values are unchecked

A batch of transactions reads and writes a key–value state. Executing the batch produces a list of accesses: each one names a key, says whether it reads or writes, and records the value it saw and the value it left. To prove that the batch moves the state from ss to s′s', the straightforward route is to replay this list against a memory, checking every read against the current contents. In an arithmetic circuit that means a random-access memory, which is the expensive part.

Offline memory checking avoids it. Instead of checking each access when it happens, the prover writes all accesses into a log, sorts the log by key and then by time, and the verifier checks the sorted log. In sorted order, every access to a key sits next to the previous access to the same key, so “this read returns the last value written” becomes a comparison between two consecutive rows. One global check remains: the sorted log must contain exactly the accesses that were executed, which is a permutation argument. If all of this passes, every access saw the value of its key just before it in sequential order, and the batch moves the state from ss to the claimed s′s'.

Offline memory checking goes back to “Checking the correctness of memories” (FOCS 1991), whose checker compares timestamped multisets of reads and writes without sorting. The sorted variant used here, which sorts the memory trace by address and time, checks adjacent entries and links the sorted trace to the execution trace by a permutation, appears in earlier reductions from RAM computations to circuits and PCPs, for example “Short PCPs verifiable in polylogarithmic time” (CCC 2005), is developed in “Fast reductions from RAMs to delegatable succinct constraint satisfaction problems” (ITCS 2013), and is the standard memory check in proof systems for RAM programs, for example “SNARKs for C: Verifying program executions succinctly and in zero knowledge” (CRYPTO 2013). This article states the checks for a key–value batch precisely and proves, in Lean, that they are sound: if they pass, every access recorded the value of its key just before it, and the post-state they claim equals sequential execution of the batch. The proof includes the step that is easy to skip informally, namely that a permutation plus sorting gives back each key’s accesses in their original order. That step needs distinct versions, and I show by counterexamples what fails without them.

All Lean below is core Lean 4 (checked with 4.16.0). The code blocks, joined in order, form one file that compiles with no errors, no warnings and no sorry.

Rows and versions

Row. A row is a tuple (κ,k,t,j,vb,va)(\kappa, k, t, j, v_b, v_a). The kind κ\kappa is one of Pre, Read, Write or Post. The key is k∈Nk \in \mathbb{N}. The pair (t,j)∈N2(t, j) \in \mathbb{N}^2 is the version. The values vbv_b and vav_a are the value before and the value after the row. Read and Write rows are interior rows. Pre and Post rows are boundary rows: they carry a key’s value before and after the whole batch. For a row rr write k(r)k(r), ver(r)=(t,j)\mathrm{ver}(r) = (t, j), vb(r)v_b(r) and va(r)v_a(r) for its components.

Version. The transactions of a batch are numbered 1,…,T1, \dots, T, and the accesses inside a transaction are numbered from 0. For an access, tt is the number of its transaction and jj is the number of the access inside that transaction. The value t=0t = 0 is reserved for Pre rows and t=T+1t = T + 1 for Post rows. Versions are ordered lexicographically: (t,j)<(t′,j′)(t, j) \lt (t', j') if t<t′t \lt t', or t=t′t = t' and j<j′j \lt j'. Rows are ordered lexicographically by (k,(t,j))(k, (t, j)).

A version is assigned by the executor while it runs the batch in order, so the committed access list has strictly increasing versions. Two different accesses therefore never share a version, and in particular two accesses to the same key never do. This is the property the order-recovery step below needs.

/-
  Offline memory checking for a key–value state over a sorted,
  versioned access log.  Core Lean 4 only.
-/

namespace MemCheck

/-! ## 1. Rows, versions, and the order on rows -/

inductive Kind where
  | pre | read | write | post
  deriving DecidableEq, Repr

/-- A row: kind, key, version `(t, j)`, value before, value after. -/
structure Row (V : Type) where
  kind : Kind
  key  : Nat
  t    : Nat
  j    : Nat
  vb   : V
  va   : V
  deriving DecidableEq

variable {V : Type}

/-- Lexicographic order on versions `(t, j)`: non-strict and strict. -/
def verLe (x y : Row V) : Prop := x.t < y.t ∨ (x.t = y.t ∧ x.j ≤ y.j)
def verLt (x y : Row V) : Prop := x.t < y.t ∨ (x.t = y.t ∧ x.j < y.j)

/-- Lexicographic order on `(key, version)`. -/
def rowLe (x y : Row V) : Prop := x.key < y.key ∨ (x.key = y.key ∧ verLe x y)

def Kind.interior : Kind → Bool
  | .read => true | .write => true | _ => false

def interior (r : Row V) : Bool := r.kind.interior
def onKey (k : Nat) (r : Row V) : Bool := r.key == k

theorem onKey_iff (k : Nat) (r : Row V) : onKey k r = true ↔ r.key = k := by
  simp [onKey]

theorem filter_pos {k : Nat} {r : Row V} (l : List (Row V)) (h : r.key = k) :
    (r :: l).filter (onKey k) = r :: l.filter (onKey k) :=
  List.filter_cons_of_pos ((onKey_iff k r).mpr h)

theorem filter_neg {k : Nat} {r : Row V} (l : List (Row V)) (h : ¬ r.key = k) :
    (r :: l).filter (onKey k) = l.filter (onKey k) :=
  List.filter_cons_of_neg (fun e => h ((onKey_iff k r).mp e))

Sequential semantics and key independence

State and execution. A state is a total map s:N→Vs : \mathbb{N} \to V from keys to values. One access acts on a single value by step(v,r)=va(r)\mathrm{step}(v, r) = v_a(r) if rr is a Write and step(v,r)=v\mathrm{step}(v, r) = v otherwise. Applying rr to a state changes only key k(r)k(r). For an access list AA, apply(s,A)\mathrm{apply}(s, A) applies the rows from left to right, and exec(v,L)\mathrm{exec}(v, L) folds step\mathrm{step} over a list LL starting from the value vv.

/-! ## 2. Sequential semantics -/

/-- State: a total map from keys to values. -/
def State (V : Type) := Nat → V

/-- One access on a single cell: a write overwrites, anything else keeps. -/
def stepVal (v : V) (r : Row V) : V :=
  match r.kind with
  | .write => r.va
  | _      => v

/-- Apply one access to a state. -/
def applyRow (s : State V) (r : Row V) : State V :=
  fun k => if r.key = k then stepVal (s k) r else s k

/-- Sequential execution of an access list. -/
def applyAll (s : State V) : List (Row V) → State V
  | []      => s
  | r :: rs => applyAll (applyRow s r) rs

/-- Sequential execution of a list of accesses on one cell. -/
def execVal (v : V) : List (Row V) → V
  | []      => v
  | r :: rs => execVal (stepVal v r) rs

The sequential semantics is the specification. The verifier never runs it; the theorem at the end says that what the verifier does check implies the same result.

Write A∣kA|_k for the subsequence of AA made of the rows with key kk, in their original order. For lists, x::Lx :: L is LL with xx prepended, L1+ ⁣ ⁣+L2L_1 \mathbin{+\!\!+} L_2 is concatenation, and [q][q] is the one-element list.

Key independence. For every access list AA, state ss and key kk,

apply(s,A)(k)=exec(s(k), A∣k).\mathrm{apply}(s, A)(k) = \mathrm{exec}\big(s(k),\, A|_k\big).

Proof. Induction on AA. A row with key kk updates key kk exactly as step\mathrm{step} does and stays in A∣kA|_k. A row with another key leaves key kk alone and is dropped from A∣kA|_k. ∎

So each key can be checked on its own: its final value depends only on its pre-state value and its own accesses, in order. The rest of the argument is about recovering A∣kA|_k, in order, from the sorted log.

/-! ## 3. Key independence -/

theorem key_independence (k : Nat) :
    ∀ (A : List (Row V)) (s : State V),
      applyAll s A k = execVal (s k) (A.filter (onKey k)) := by
  intro A
  induction A with
  | nil => intro s; rfl
  | cons r rs ih =>
    intro s
    show applyAll (applyRow s r) rs k = _
    rw [ih]
    by_cases h : r.key = k
    · have hf : (r :: rs).filter (onKey k) = r :: rs.filter (onKey k) := by
        first | exact filter_pos _ h | exact filter_neg _ h
      rw [hf]
      show execVal (applyRow s r k) _ = execVal (stepVal (s k) r) _
      simp [applyRow, h]
    · have hf : (r :: rs).filter (onKey k) = rs.filter (onKey k) := by
        first | exact filter_pos _ h | exact filter_neg _ h
      rw [hf]
      simp [applyRow, h]

Local constraints

A circuit checks constraints row by row. The constraints here are of two kinds: on one row, or on two consecutive rows.

Consecutive-pair predicates. For a relation PP on rows, AdjP(L)\mathrm{Adj}_P(L) holds if every pair of consecutive elements (x,y)(x, y) of LL satisfies P(x,y)P(x, y).

The first lemma is what makes “consecutive in sorted order” useful. If BB is sorted by key, the rows of one key form a contiguous block, so two rows that are consecutive in B∣kB|_k were already consecutive in BB. A constraint that BB satisfies on consecutive rows of the same key therefore holds on every consecutive pair of B∣kB|_k.

Contiguity. If BB is sorted by key and every consecutive pair of BB with equal keys satisfies QQ, then AdjQ(B∣k)\mathrm{Adj}_Q(B|_k) holds for every key kk.

Proof. Induction on BB. If the head xx has key kk and the next row yy also does, the pair (x,y)(x, y) is consecutive in both lists. If yy has a different key, sortedness puts every later row at a key above kk, so nothing after xx survives the filter. ∎

/-! ## 4. Adjacent-pair constraints -/

/-- `Adj P L`: every pair of consecutive elements of `L` satisfies `P`. -/
def Adj (P : Row V → Row V → Prop) : List (Row V) → Prop
  | x :: y :: rs => P x y ∧ Adj P (y :: rs)
  | _ => True

/-- `LastP P L`: the last element of `L` (if any) satisfies `P`. -/
def LastP (P : Row V → Prop) : List (Row V) → Prop
  | []           => True
  | [x]          => P x
  | _ :: y :: rs => LastP P (y :: rs)

theorem adj_tail {P : Row V → Row V → Prop} (x : Row V) :
    ∀ rs, Adj P (x :: rs) → Adj P rs
  | [], _ => trivial
  | _ :: _, h => h.2

theorem adj_imp {P Q : Row V → Row V → Prop} (hpq : ∀ x y, P x y → Q x y) :
    ∀ L : List (Row V), Adj P L → Adj Q L
  | [], _ => trivial
  | [_], _ => trivial
  | x :: y :: rs, h => ⟨hpq x y h.1, adj_imp hpq (y :: rs) h.2⟩

/-- Filtering a key-sorted list by one key yields a contiguous block:
    consecutive survivors were consecutive in the original list. -/
theorem adj_filter {Q : Row V → Row V → Prop} (k : Nat) :
    ∀ B : List (Row V),
      List.Pairwise (fun x y => x.key ≤ y.key) B →
      Adj (fun x y => x.key = y.key → Q x y) B →
      Adj Q (B.filter (onKey k)) := by
  intro B
  induction B with
  | nil => intro _ _; trivial
  | cons x rest ih =>
    intro hs ha
    have hs' := List.pairwise_cons.mp hs
    have ih' := ih hs'.2 (adj_tail x rest ha)
    by_cases hx : x.key = k
    · have hf : (x :: rest).filter (onKey k) = x :: rest.filter (onKey k) := by
        first | exact filter_pos _ hx | exact filter_neg _ hx
      rw [hf]
      cases rest with
      | nil => simp [List.filter]; trivial
      | cons y rest' =>
        by_cases hy : y.key = k
        · have hf2 : (y :: rest').filter (onKey k) = y :: rest'.filter (onKey k) := by
            first | exact filter_pos _ hy | exact filter_neg _ hy
          rw [hf2] at ih' ⊢
          exact ⟨ha.1 (hx.trans hy.symm), ih'⟩
        · have hxy : x.key ≤ y.key := hs'.1 y (List.mem_cons_self _ _)
          have hys := List.pairwise_cons.mp hs'.2
          have hnil : (y :: rest').filter (onKey k) = [] := by
            apply List.filter_eq_nil_iff.mpr
            intro z hz hzk
            have hzk' := (onKey_iff k z).mp hzk
            cases List.mem_cons.mp hz with
            | inl h => exact hy (h ▸ hzk')
            | inr h =>
              have := hys.1 z h
              omega
          rw [hnil]; trivial
    · have hf : (x :: rest).filter (onKey k) = rest.filter (onKey k) := by
        first | exact filter_pos _ hx | exact filter_neg _ hx
      rw [hf]; exact ih'

The boundary rows mark where each key’s block starts and ends. One local rule fixes their positions.

Boundary rule. Consecutive rows x,yx, y satisfy Bnd(x,y)\mathrm{Bnd}(x, y) if: when k(x)=k(y)k(x) = k(y), xx is not a Post and yy is not a Pre; when k(x)≠k(y)k(x) \ne k(y), xx is a Post and yy is a Pre.

First and last rows. Suppose BB satisfies AdjBnd\mathrm{Adj}_{\mathrm{Bnd}}, its first row is a Pre and its last row is a Post. Then for every key kk, the first row of B∣kB|_k is a Pre and the last row of B∣kB|_k is a Post.

Proof. The first row of key kk is either the first row of BB or follows a row of a different key; in both cases it is a Pre. Symmetrically for the last row. Neither part uses sortedness. ∎

/-! ## 5. Local boundary constraints and the per-key shape -/

/-- The local boundary rule on consecutive rows `x, y`:
    same key ⇒ `x` is not a Post and `y` is not a Pre;
    key change ⇒ `x` is a Post and `y` is a Pre. -/
def Bnd (x y : Row V) : Prop :=
  (x.key = y.key → x.kind ≠ .post ∧ y.kind ≠ .pre) ∧
  (x.key ≠ y.key → x.kind = .post ∧ y.kind = .pre)

/-- The first surviving row of a key is a Pre row. -/
theorem filter_head_pre (k : Nat) :
    ∀ B : List (Row V),
      (∀ y, B.head? = some y → y.kind = .pre ∨ y.key ≠ k) →
      Adj Bnd B →
      ∀ y, (B.filter (onKey k)).head? = some y → y.kind = .pre := by
  intro B
  induction B with
  | nil => intro _ _ y h; simp [List.filter] at h
  | cons x rest ih =>
    intro hh ha y hy
    by_cases hx : x.key = k
    · have hf : (x :: rest).filter (onKey k) = x :: rest.filter (onKey k) := by
        first | exact filter_pos _ hx | exact filter_neg _ hx
      rw [hf] at hy
      have hxy : x = y := by simpa using hy
      rw [← hxy]
      cases hh x rfl with
      | inl h => exact h
      | inr h => exact absurd hx h
    · have hf : (x :: rest).filter (onKey k) = rest.filter (onKey k) := by
        first | exact filter_pos _ hx | exact filter_neg _ hx
      rw [hf] at hy
      apply ih _ (adj_tail x rest ha) y hy
      intro z hz
      cases rest with
      | nil => simp at hz
      | cons z' rest' =>
        have hz' : z' = z := by simpa using hz
        rw [← hz']
        by_cases hxz : x.key = z'.key
        · exact Or.inr (fun h => hx (hxz.trans h))
        · exact Or.inl (ha.1.2 hxz).2

theorem lastP_cons {P : Row V → Prop} (x y : Row V) (rs : List (Row V)) :
    LastP P (x :: y :: rs) = LastP P (y :: rs) := rfl

/-- The last surviving row of a key is a Post row. -/
theorem filter_last_post (k : Nat) :
    ∀ B : List (Row V),
      LastP (fun r => r.kind = .post) B →
      Adj Bnd B →
      LastP (fun r => r.kind = .post) (B.filter (onKey k)) := by
  intro B
  induction B with
  | nil => intro _ _; trivial
  | cons x rest ih =>
    intro hl ha
    cases rest with
    | nil =>
      by_cases hx : x.key = k
      · rw [filter_pos _ hx]; exact hl
      · rw [filter_neg _ hx]; trivial
    | cons y rest' =>
      have ih' := ih hl (adj_tail x _ ha)
      by_cases hx : x.key = k
      · have hf : (x :: y :: rest').filter (onKey k)
            = x :: (y :: rest').filter (onKey k) := by
          first | exact filter_pos _ hx | exact filter_neg _ hx
        rw [hf]
        cases hfr : (y :: rest').filter (onKey k) with
        | nil =>
          show x.kind = .post
          have hyk : y.key ≠ k := by
            intro hyk
            have : y ∈ (y :: rest').filter (onKey k) :=
              List.mem_filter.mpr ⟨List.mem_cons_self _ _, (onKey_iff k y).mpr hyk⟩
            rw [hfr] at this; simp at this
          exact (ha.1.2 (fun h => hyk (h ▸ hx))).1
        | cons z zs =>
          rw [lastP_cons]; rw [hfr] at ih'; exact ih'
      · have hf : (x :: y :: rest').filter (onKey k) = (y :: rest').filter (onKey k) := by
          first | exact filter_pos _ hx | exact filter_neg _ hx
        rw [hf]; exact ih'

Combined with contiguity, this gives each key’s block its full shape.

Per-key shape. Suppose BB is sorted by key, starts with a Pre, ends with a Post and satisfies AdjBnd\mathrm{Adj}_{\mathrm{Bnd}}. Then for every key kk that occurs in BB,

B∣k=p::I+ ⁣ ⁣+[q]B|_k = p :: I \mathbin{+\!\!+} [q]

with pp a Pre, qq a Post and every row of II a Read or a Write. In particular each key has exactly one Pre row and one Post row.

Proof. By contiguity, consecutive rows of B∣kB|_k satisfy the same-key half of Bnd\mathrm{Bnd}: no Post is followed by anything and no Pre is preceded by anything. The first row is a Pre and the last a Post by the previous theorem. Everything in between is neither, so it is a Read or a Write. ∎

/-- A list that starts after a non-Post row, has no Post-then-anything and no
    anything-then-Pre adjacency, and ends in a Post, is `I ++ [q]` with `q`
    a Post and every row of `I` neither Pre nor Post. -/
theorem tail_shape (x : Row V) :
    ∀ L : List (Row V),
      x.kind ≠ .post →
      Adj (fun a b => a.kind ≠ .post ∧ b.kind ≠ .pre) (x :: L) →
      LastP (fun r => r.kind = .post) (x :: L) →
      ∃ I q, L = I ++ [q] ∧ q.kind = .post ∧
        ∀ r ∈ I, r.kind ≠ .pre ∧ r.kind ≠ .post := by
  intro L
  induction L generalizing x with
  | nil => intro hx _ hl; exact absurd hl hx
  | cons y L' ih =>
    intro _ ha hl
    cases L' with
    | nil => exact ⟨[], y, rfl, hl, by simp⟩
    | cons z zs =>
      have hy_pre : y.kind ≠ .pre := ha.1.2
      have hy_post : y.kind ≠ .post := ha.2.1.1
      obtain ⟨I, q, hI, hq, hr⟩ := ih y hy_post ha.2 hl
      refine ⟨y :: I, q, by rw [hI]; rfl, hq, ?_⟩
      intro r hr'
      cases List.mem_cons.mp hr' with
      | inl h => subst h; exact ⟨hy_pre, hy_post⟩
      | inr h => exact hr r h

theorem kind_interior_of {k : Kind} (h1 : k ≠ .pre) (h2 : k ≠ .post) :
    k = .read ∨ k = .write := by
  cases k <;> simp_all

/-- **Per-key shape.**  If `B` is sorted by key, starts with a Pre row, ends
    with a Post row, and satisfies the local boundary rule, then for every key
    `k` the rows of key `k` form `Pre :: I ++ [Post]` with `I` all READ/WRITE. -/
theorem segment_shape (k : Nat) (B : List (Row V))
    (hsort : List.Pairwise (fun x y => x.key ≤ y.key) B)
    (hfirst : ∀ y, B.head? = some y → y.kind = .pre)
    (hlast : LastP (fun r => r.kind = .post) B)
    (hbnd : Adj Bnd B)
    (hne : B.filter (onKey k) ≠ []) :
    ∃ p I q, B.filter (onKey k) = p :: (I ++ [q]) ∧
      p.kind = .pre ∧ q.kind = .post ∧
      ∀ r ∈ I, r.kind = .read ∨ r.kind = .write := by
  have hhead := filter_head_pre k B (fun y h => Or.inl (hfirst y h)) hbnd
  have hl := filter_last_post k B hlast hbnd
  have ha : Adj (fun a b => a.kind ≠ .post ∧ b.kind ≠ .pre) (B.filter (onKey k)) :=
    adj_filter k B hsort (adj_imp (fun x y h e => h.1 e) B hbnd)
  cases hf : B.filter (onKey k) with
  | nil => exact absurd hf hne
  | cons p rest =>
    rw [hf] at hl ha
    have hp : p.kind = .pre := hhead p (by rw [hf]; rfl)
    have hpp : p.kind ≠ .post := by rw [hp]; decide
    obtain ⟨I, q, hI, hq, hr⟩ := tail_shape p rest hpp ha hl
    exact ⟨p, I, q, by rw [hI], hp, hq,
      fun r h => kind_interior_of (hr r h).1 (hr r h).2⟩

Segment soundness

Local flow and read consistency. Consecutive rows x,yx, y with the same key satisfy flow if vb(y)=va(x)v_b(y) = v_a(x): each row starts from the value the previous row of its key left. A Read row (and a Post row) is consistent if vb=vav_b = v_a: it does not change the value.

Segment soundness. Let every row of II be a Read or a Write, every Read in II be consistent, and let flow hold on every consecutive pair of p::I+ ⁣ ⁣+[q]p :: I \mathbin{+\!\!+} [q]. Then

vb(q)=exec(va(p), I).v_b(q) = \mathrm{exec}\big(v_a(p),\, I\big).

Proof. Induction on II. For the first interior row rr, flow gives vb(r)=va(p)v_b(r) = v_a(p). If rr is a Write, step(va(p),r)=va(r)\mathrm{step}(v_a(p), r) = v_a(r) by definition. If rr is a Read, step(va(p),r)=va(p)=vb(r)=va(r)\mathrm{step}(v_a(p), r) = v_a(p) = v_b(r) = v_a(r) by consistency. Either way the segment continues from va(r)v_a(r), and the induction hypothesis applies with rr in place of pp. ∎

/-! ## 6. Segment soundness: local flow executes the segment -/

/-- Local memory flow: the next row's value-before is the previous
    row's value-after. -/
def Flow (x y : Row V) : Prop := y.vb = x.va

/-- One interior row that starts where `p` left off ends at its own
    value-after under the sequential step. -/
theorem step_of_flow (p r : Row V) (hk : r.kind = .read ∨ r.kind = .write)
    (hc : r.kind = .read → r.vb = r.va) (hf : r.vb = p.va) :
    stepVal p.va r = r.va := by
  cases hk with
  | inl hk => simp [stepVal, hk]; rw [← hf]; exact hc hk
  | inr hk => simp [stepVal, hk]

theorem segment_sound :
    ∀ (I : List (Row V)) (p q : Row V),
      (∀ r ∈ I, r.kind = .read ∨ r.kind = .write) →
      (∀ r ∈ I, r.kind = .read → r.vb = r.va) →
      Adj Flow (p :: (I ++ [q])) →
      q.vb = execVal p.va I := by
  intro I
  induction I with
  | nil => intro p q _ _ ha; exact ha.1
  | cons r I' ih =>
    intro p q hrw hrc ha
    show q.vb = execVal (stepVal p.va r) I'
    rw [step_of_flow p r (hrw r (List.mem_cons_self _ _))
      (hrc r (List.mem_cons_self _ _)) ha.1]
    exact ih r q (fun x h => hrw x (List.mem_cons_of_mem _ h))
      (fun x h => hrc x (List.mem_cons_of_mem _ h)) ha.2

/-- Every interior row of the segment starts from the value obtained by
    executing the interior rows before it. -/
theorem segment_reads :
    ∀ (I : List (Row V)) (p q : Row V),
      (∀ r ∈ I, r.kind = .read ∨ r.kind = .write) →
      (∀ r ∈ I, r.kind = .read → r.vb = r.va) →
      Adj Flow (p :: (I ++ [q])) →
      ∀ (P S : List (Row V)) (r : Row V), I = P ++ r :: S →
        r.vb = execVal p.va P := by
  intro I
  induction I with
  | nil => intro _ _ _ _ _ P S r he; cases P <;> simp at he
  | cons x I' ih =>
    intro p q hrw hrc ha P S r he
    cases P with
    | nil =>
      simp at he
      rw [← he.1]; exact ha.1
    | cons y P' =>
      simp at he
      obtain ⟨hxy, hI'⟩ := he
      subst hxy
      show r.vb = execVal (stepVal p.va x) P'
      rw [step_of_flow p x (hrw x (List.mem_cons_self _ _))
        (hrc x (List.mem_cons_self _ _)) ha.1]
      exact ih x q (fun z h => hrw z (List.mem_cons_of_mem _ h))
        (fun z h => hrc z (List.mem_cons_of_mem _ h)) ha.2 P' S r hI'

Segment soundness says that the sorted block of one key is a correct execution of its own interior rows, in the order they appear in BB. It does not yet say that they are the rows of A∣kA|_k in the order of AA. That is the next step.

Recovering the order

The permutation argument guarantees that the interior rows of BB are a rearrangement of the committed list AA, nothing more. Two facts close the gap. Filtering commutes with permutation, so the interior rows of key kk in BB are a rearrangement of A∣kA|_k. And two lists that are rearrangements of each other and are both sorted, in compatible orders, are equal.

Sorted permutations are equal. Let l1l_1 be a permutation of l2l_2, with l1l_1 sorted by R1R_1 and l2l_2 sorted by R2R_2 (each pair in list order satisfies the relation). If no a,ba, b satisfy both R1(a,b)R_1(a, b) and R2(b,a)R_2(b, a), then l1=l2l_1 = l_2.

Proof. Induction on l1l_1. Let aa and bb be the heads. If a≠ba \ne b, then bb occurs later in l1l_1 and aa occurs later in l2l_2, so R1(a,b)R_1(a, b) and R2(b,a)R_2(b, a), which is excluded. So a=ba = b; cancel it from both sides and apply the induction hypothesis to the tails. ∎

Here R1R_1 is the non-strict version order (from sorting BB) and R2R_2 is the strict version order (from the executor’s order on AA). R1(a,b)R_1(a, b) and R2(b,a)R_2(b, a) would mean ver(a)≤ver(b)<ver(a)\mathrm{ver}(a) \le \mathrm{ver}(b) \lt \mathrm{ver}(a), which is impossible. The theorem needs a strict order on one side: with a tie, two rows with equal versions can be listed in either order in BB and still count as sorted.

/-! ## 7. Sorted permutations are equal -/

/-- If `l₁ ~ l₂`, `l₁` is sorted by `R₁`, `l₂` by `R₂`, and no pair satisfies
    `R₁ a b` together with `R₂ b a`, then `l₁ = l₂`. -/
theorem perm_sorted_eq {α : Type} {R₁ R₂ : α → α → Prop}
    (hanti : ∀ a b, R₁ a b → R₂ b a → False) :
    ∀ l₁ l₂ : List α, l₁.Perm l₂ →
      List.Pairwise R₁ l₁ → List.Pairwise R₂ l₂ → l₁ = l₂ := by
  intro l₁
  induction l₁ with
  | nil => intro l₂ hp _ _; exact hp.nil_eq
  | cons a t₁ ih =>
    intro l₂ hp h₁ h₂
    cases l₂ with
    | nil => exact absurd hp.eq_nil (by simp)
    | cons b t₂ =>
      have hs₁ := List.pairwise_cons.mp h₁
      have hs₂ := List.pairwise_cons.mp h₂
      have hab : a = b := by
        have ha : a ∈ b :: t₂ := hp.mem_iff.mp (List.mem_cons_self _ _)
        have hb : b ∈ a :: t₁ := hp.mem_iff.mpr (List.mem_cons_self _ _)
        cases List.mem_cons.mp ha with
        | inl h => exact h
        | inr ha' =>
          cases List.mem_cons.mp hb with
          | inl h => exact h.symm
          | inr hb' => exact (hanti a b (hs₁.1 b hb') (hs₂.1 a ha')).elim
      subst hab
      rw [ih t₂ hp.cons_inv hs₁.2 hs₂.2]

theorem verLe_verLt_false (a b : Row V) : verLe a b → verLt b a → False := by
  unfold verLe verLt; omega

/-- Pairwise restricted to a predicate that holds on every element. -/
theorem pairwise_imp_mem {α : Type} {R S : α → α → Prop} {P : α → Prop}
    (h : ∀ x y, P x → P y → R x y → S x y) :
    ∀ L : List α, (∀ x ∈ L, P x) → List.Pairwise R L → List.Pairwise S L := by
  intro L
  induction L with
  | nil => intro _ _; exact List.Pairwise.nil
  | cons a t ih =>
    intro hP hR
    have hR' := List.pairwise_cons.mp hR
    refine List.pairwise_cons.mpr ⟨?_, ih (fun x hx => hP x (List.mem_cons_of_mem _ hx)) hR'.2⟩
    intro b hb
    exact h a b (hP a (List.mem_cons_self _ _)) (hP b (List.mem_cons_of_mem _ hb)) (hR'.1 b hb)

Order recovery. Suppose BB is sorted by (k,(t,j))(k, (t, j)), the interior rows of BB are a permutation of AA, and the versions in AA strictly increase. Then for every key kk, the interior rows of B∣kB|_k are exactly A∣kA|_k, as lists.

Proof. Filtering the permutation by key gives that the interior of B∣kB|_k is a permutation of A∣kA|_k. Inside one key, the order on (k,(t,j))(k, (t, j)) reduces to the version order, so the interior of B∣kB|_k is sorted by non-strict version; A∣kA|_k is sorted by strict version because AA is. Apply the previous theorem. ∎

/-- **Order recovery.**  Within one key, the sorted log's interior equals the
    committed log's subsequence for that key. -/
theorem interior_eq_committed (k : Nat) (B A : List (Row V))
    (hsort : List.Pairwise rowLe B)
    (hperm : (B.filter interior).Perm A)
    (hA : List.Pairwise verLt A) :
    (B.filter (onKey k)).filter interior = A.filter (onKey k) := by
  apply perm_sorted_eq verLe_verLt_false
  · have h := hperm.filter (onKey k)
    rw [List.filter_filter] at h
    rw [List.filter_filter]
    have e : (fun a : Row V => interior a && onKey k a) = (fun a => onKey k a && interior a) := by
      funext a; cases interior a <;> cases onKey k a <;> rfl
    rw [e]; exact h
  · have hL : List.Pairwise rowLe (B.filter (onKey k)) := hsort.filter _
    have hL' : List.Pairwise verLe (B.filter (onKey k)) := by
      apply pairwise_imp_mem (P := fun r => r.key = k) _ _ _ hL
      · intro x y hx hy hxy
        cases hxy with
        | inl h => omega
        | inr h => exact h.2
      · intro x hx; exact (onKey_iff k x).mp (List.mem_filter.mp hx).2
    exact hL'.filter _
  · exact hA.filter _

Sortedness is a local check

A verifier cannot check a pairwise condition over all pairs of rows directly. It does not need to: for a transitive relation, the consecutive pairs are enough.

Local sortedness. If RR is transitive and every consecutive pair of LL satisfies RR, then every pair of LL in list order satisfies RR. This applies to the order on (k,(t,j))(k, (t, j)) for BB and to the strict version order for AA.

/-! ## 8. Sortedness is a local check -/

theorem pairwise_of_adj {R : Row V → Row V → Prop}
    (htrans : ∀ a b c, R a b → R b c → R a c) :
    ∀ (L : List (Row V)) (x : Row V), Adj R (x :: L) → List.Pairwise R (x :: L) := by
  intro L
  induction L with
  | nil => intro x _; exact List.pairwise_singleton _ _
  | cons y L' ih =>
    intro x ha
    have hy := ih y ha.2
    refine List.pairwise_cons.mpr ⟨?_, hy⟩
    intro z hz
    cases List.mem_cons.mp hz with
    | inl h => rw [h]; exact ha.1
    | inr h => exact htrans x y z ha.1 ((List.pairwise_cons.mp hy).1 z h)

theorem rowLe_trans (a b c : Row V) : rowLe a b → rowLe b c → rowLe a c := by
  unfold rowLe verLe; omega

theorem verLt_trans (a b c : Row V) : verLt a b → verLt b c → verLt a c := by
  unfold verLt; omega

/-- Adjacent-pair sortedness implies global sortedness. -/
theorem sorted_of_adj (B : List (Row V)) (h : Adj rowLe B) : List.Pairwise rowLe B := by
  cases B with
  | nil => exact List.Pairwise.nil
  | cons x L => exact pairwise_of_adj rowLe_trans L x h

theorem ordered_of_adj (A : List (Row V)) (h : Adj verLt A) : List.Pairwise verLt A := by
  cases A with
  | nil => exact List.Pairwise.nil
  | cons x L => exact pairwise_of_adj verLt_trans L x h

Together with contiguity and the first-and-last lemma, this means every check except the permutation reads at most two consecutive rows.

The soundness theorem

Acceptance. Given a pre-state ss, a committed access list AA and a sorted log BB, the verifier accepts if:

  1. BB is sorted by (k,(t,j))(k, (t, j));
  2. the first row of BB is a Pre, the last is a Post, and AdjBnd(B)\mathrm{Adj}_{\mathrm{Bnd}}(B) holds;
  3. the interior rows of BB are a permutation of AA;
  4. the versions of AA strictly increase;
  5. flow holds on consecutive rows of BB with the same key, and every Read and Post row is consistent;
  6. every Pre row carries the pre-state: va(p)=s(k(p))v_a(p) = s(k(p)).

The claimed post-state claimed(s,B)\mathrm{claimed}(s, B) maps a key to the value vav_a of its Post row if it has one, and to s(k)s(k) otherwise.

Conditions 1 and 4 are stated over all pairs. By local sortedness, a verifier checks them on consecutive pairs.

/-! ## 9. The soundness theorem -/

/-- The hypotheses a verifier checks on the sorted log `B`, given the
    committed access list `A` and the pre-state `s`. -/
structure Accepts (s : State V) (A B : List (Row V)) : Prop where
  /-- (1) sorted by `(key, (t, j))` lexicographically -/
  sorted   : List.Pairwise rowLe B
  /-- (2) boundary shape: first row Pre, last row Post, local boundary rule -/
  first    : ∀ y, B.head? = some y → y.kind = .pre
  last     : LastP (fun r => r.kind = .post) B
  bnd      : Adj Bnd B
  /-- (3) interior rows are a permutation of the committed list -/
  perm     : (B.filter interior).Perm A
  /-- (4) the committed list is in execution order: versions strictly increase -/
  ordered  : List.Pairwise verLt A
  /-- (5) local flow between consecutive rows of the same key -/
  flow     : Adj (fun x y => x.key = y.key → Flow x y) B
  /-- (5) read consistency (also for Post rows) -/
  readc    : ∀ r ∈ B, r.kind = .read ∨ r.kind = .post → r.vb = r.va
  /-- (6) Pre rows carry the pre-state -/
  preVal   : ∀ r ∈ B, r.kind = .pre → r.va = s r.key

theorem keyLe_of_rowLe (B : List (Row V)) (h : List.Pairwise rowLe B) :
    List.Pairwise (fun x y => x.key ≤ y.key) B :=
  h.imp (fun hxy => by cases hxy with
    | inl h => omega
    | inr h => omega)

Post rows are correct. If the verifier accepts, every Post row qq satisfies va(q)=apply(s,A)(k(q))v_a(q) = \mathrm{apply}(s, A)(k(q)).

Proof. Let k=k(q)k = k(q). By the per-key shape, B∣k=p::I+ ⁣ ⁣+[q]B|_k = p :: I \mathbin{+\!\!+} [q] (the Post row of a key is unique, so it is qq). Contiguity carries flow to B∣kB|_k; this per-key summary is the lemma key_segment below, reused in the next section. Segment soundness gives vb(q)=exec(va(p),I)v_b(q) = \mathrm{exec}(v_a(p), I). Order recovery gives I=A∣kI = A|_k, condition 6 gives va(p)=s(k)v_a(p) = s(k), and consistency of qq gives va(q)=vb(q)v_a(q) = v_b(q). So va(q)=exec(s(k),A∣k)v_a(q) = \mathrm{exec}(s(k), A|_k), which is apply(s,A)(k)\mathrm{apply}(s, A)(k) by key independence. ∎

/-- **Per-key summary.**  For a key with rows in `B`, the checks give its
    segment `p :: I ++ [q]`, flow on it, the pre-state at `p`, and
    `I = A|ₖ` as lists. -/
theorem key_segment (s : State V) (A B : List (Row V)) (h : Accepts s A B)
    (k : Nat) (hne : B.filter (onKey k) ≠ []) :
    ∃ p I q, B.filter (onKey k) = p :: (I ++ [q]) ∧
      p.kind = .pre ∧ q.kind = .post ∧
      (∀ r ∈ I, r.kind = .read ∨ r.kind = .write) ∧
      (∀ r ∈ I, r.kind = .read → r.vb = r.va) ∧
      Adj Flow (p :: (I ++ [q])) ∧
      p.va = s k ∧ q.vb = q.va ∧
      I = A.filter (onKey k) := by
  have hksort := keyLe_of_rowLe B h.sorted
  obtain ⟨p, I, q, hL, hp, hq, hI⟩ :=
    segment_shape k B hksort h.first h.last h.bnd hne
  have memL : ∀ r, r ∈ B.filter (onKey k) → r ∈ B ∧ r.key = k := fun r hr =>
    ⟨(List.mem_filter.mp hr).1, (onKey_iff k r).mp (List.mem_filter.mp hr).2⟩
  have hpB := memL p (by rw [hL]; exact List.mem_cons_self _ _)
  have hqB := memL q (by rw [hL]; simp)
  have hIB : ∀ r ∈ I, r ∈ B := fun r hr =>
    (memL r (by rw [hL]; exact List.mem_cons_of_mem _ (List.mem_append_left _ hr))).1
  -- interior of key `k` is the committed subsequence of key `k`
  have hIeq : I = A.filter (onKey k) := by
    rw [← interior_eq_committed k B A h.sorted h.perm h.ordered, hL]
    have hi : ∀ r ∈ I, interior r = true := fun r hr => by
      cases hI r hr with
      | inl e => simp [interior, e, Kind.interior]
      | inr e => simp [interior, e, Kind.interior]
    have hp' : interior p = false := by simp [interior, hp, Kind.interior]
    have hq'' : interior q = false := by simp [interior, hq, Kind.interior]
    rw [List.filter_cons, hp', List.filter_append, List.filter_eq_self.mpr hi]
    simp [List.filter, hq'']
  refine ⟨p, I, q, hL, hp, hq, hI,
    fun r hr hk => h.readc r (hIB r hr) (Or.inl hk), ?_, ?_,
    h.readc q hqB.1 (Or.inr hq), hIeq⟩
  · rw [← hL]; exact adj_filter k B hksort h.flow
  · rw [h.preVal p hpB.1 hp, hpB.2]

/-- **Main theorem (Post rows).**  Every Post row of key `k` carries the value
    of key `k` after sequential execution of the committed list. -/
theorem post_correct (s : State V) (A B : List (Row V)) (h : Accepts s A B)
    (q : Row V) (hq : q ∈ B) (hqk : q.kind = .post) :
    q.va = applyAll s A q.key := by
  let k := q.key
  have hqL : q ∈ B.filter (onKey k) :=
    List.mem_filter.mpr ⟨hq, (onKey_iff k q).mpr rfl⟩
  have hne : B.filter (onKey k) ≠ [] := by
    intro he; rw [he] at hqL; simp at hqL
  obtain ⟨p, I, q', hL, hp, _, hI, hrc, hflow, hpv, hqc, hIeq⟩ :=
    key_segment s A B h k hne
  -- the Post row of key `k` is unique
  have hqq : q = q' := by
    rw [hL] at hqL
    cases List.mem_cons.mp hqL with
    | inl h' => rw [h'] at hqk; rw [hp] at hqk; cases hqk
    | inr h' =>
      cases List.mem_append.mp h' with
      | inl hi => cases hI q hi with
        | inl h'' => rw [hqk] at h''; cases h''
        | inr h'' => rw [hqk] at h''; cases h''
      | inr hi => simp at hi; exact hi
  subst hqq
  rw [key_independence k A s, ← hIeq, ← hpv, ← segment_sound I p q hI hrc hflow]
  exact hqc.symm

Batch soundness. If the verifier accepts, the claimed post-state equals sequential execution:

claimed(s,B)=apply(s,A).\mathrm{claimed}(s, B) = \mathrm{apply}(s, A).

Proof. Pointwise in kk. If BB has a Post row of key kk, use the previous theorem. If BB has some row of key kk but no Post row, the per-key shape is contradicted. If BB has no row of key kk at all, order recovery gives A∣k=[]A|_k = [], so by key independence apply(s,A)(k)=s(k)\mathrm{apply}(s, A)(k) = s(k), which is what the claimed post-state says. ∎

/-- **Main theorem (untouched keys).**  A key with no row in `B` keeps its
    pre-state value under sequential execution. -/
theorem untouched_correct (s : State V) (A B : List (Row V)) (h : Accepts s A B)
    (k : Nat) (hk : ∀ r ∈ B, r.key ≠ k) :
    applyAll s A k = s k := by
  have hB : B.filter (onKey k) = [] :=
    List.filter_eq_nil_iff.mpr (fun r hr e => hk r hr ((onKey_iff k r).mp e))
  have hA : A.filter (onKey k) = [] := by
    have := interior_eq_committed k B A h.sorted h.perm h.ordered
    rw [hB] at this; exact this.symm
  rw [key_independence k A s, hA]; rfl

/-- The post-state claimed by `B`: the Post row's value where one exists,
    the pre-state value elsewhere. -/
def claimedPost (s : State V) (B : List (Row V)) : State V := fun k =>
  match B.find? (fun r => r.kind == .post && r.key == k) with
  | some r => r.va
  | none   => s k

/-- **Soundness.**  If the verifier's checks pass, the claimed post-state is
    exactly the result of executing the committed access list sequentially. -/
theorem batch_sound (s : State V) (A B : List (Row V)) (h : Accepts s A B) :
    claimedPost s B = applyAll s A := by
  funext k
  unfold claimedPost
  cases hf : B.find? (fun r => r.kind == .post && r.key == k) with
  | some r =>
    have hm := List.mem_of_find?_eq_some hf
    have hp := List.find?_some hf
    simp at hp
    show r.va = _
    rw [← hp.2]; exact post_correct s A B h r hm hp.1
  | none =>
    show s k = _
    have hn := List.find?_eq_none.mp hf
    by_cases hex : ∃ r ∈ B, r.key = k
    · -- a key with rows has a Post row, contradicting `none`
      obtain ⟨r, hr, hrk⟩ := hex
      have hne : B.filter (onKey k) ≠ [] := by
        intro he
        have : r ∈ B.filter (onKey k) := List.mem_filter.mpr ⟨hr, (onKey_iff k r).mpr hrk⟩
        rw [he] at this; simp at this
      obtain ⟨p, I, q, hL, _, hq, _⟩ :=
        segment_shape k B (keyLe_of_rowLe B h.sorted) h.first h.last h.bnd hne
      have hqL : q ∈ B.filter (onKey k) := by rw [hL]; simp
      have hqB := List.mem_filter.mp hqL
      exfalso
      apply hn q hqB.1
      have : q.key = k := (onKey_iff k q).mp hqB.2
      simp [hq, this]
    · exact (untouched_correct s A B h k (fun r hr e => hex ⟨r, hr, e⟩)).symm

Every access sees the right value

The post-state is not the whole story. A transaction computes what it writes from what it reads, so the property memory checking exists to give is that every Read returned the current value of its key. Sequential execution ignores the value-before fields, so batch soundness alone says nothing about them. The same ingredients prove it.

Consistency of an access list. An access list AA is consistent with a state ss if every row rr of AA records as its value-before the value of its key just before it in sequential order: whenever A=A1+ ⁣ ⁣+r::A2A = A_1 \mathbin{+\!\!+} r :: A_2, vb(r)=apply(s,A1)(k(r))v_b(r) = \mathrm{apply}(s, A_1)(k(r)).

Reads are correct. If the verifier accepts, then:

  1. for every key kk and every split A∣k=P+ ⁣ ⁣+r::SA|_k = P \mathbin{+\!\!+} r :: S, vb(r)=exec(s(k),P)v_b(r) = \mathrm{exec}(s(k), P);
  2. AA is consistent with ss. In particular every Read rr in AA returned vb(r)=va(r)=apply(s,A1)(k(r))v_b(r) = v_a(r) = \mathrm{apply}(s, A_1)(k(r)), the value of its key just before it.

Proof. For 1: rr lies in AA, so by the permutation it lies in BB and key kk occurs in BB. The per-key summary used for Post rows gives B∣k=p::I+ ⁣ ⁣+[q]B|_k = p :: I \mathbin{+\!\!+} [q] with flow, va(p)=s(k)v_a(p) = s(k) and I=A∣kI = A|_k, so I=P+ ⁣ ⁣+r::SI = P \mathbin{+\!\!+} r :: S. Induction on PP, exactly as in segment soundness: the first interior row starts at va(p)v_a(p) by flow, and each row ends at the value step\mathrm{step} gives it, so vb(r)=exec(va(p),P)v_b(r) = \mathrm{exec}(v_a(p), P). For 2: if A=A1+ ⁣ ⁣+r::A2A = A_1 \mathbin{+\!\!+} r :: A_2, then A∣k(r)=A1∣k(r)+ ⁣ ⁣+r::A2∣k(r)A|_{k(r)} = A_1|_{k(r)} \mathbin{+\!\!+} r :: A_2|_{k(r)}; apply 1 and key independence. A Read of AA is an interior row of BB, so read consistency gives vb(r)=va(r)v_b(r) = v_a(r). ∎

/-! ## 10. Every access sees the right value -/

/-- Each row records, as its value-before, the value of its key just before
    it in sequential execution. -/
def Consistent : State V → List (Row V) → Prop
  | _, []      => True
  | s, r :: rs => r.vb = s r.key ∧ Consistent (applyRow s r) rs

theorem applyAll_append (l₁ l₂ : List (Row V)) :
    ∀ s : State V, applyAll s (l₁ ++ l₂) = applyAll (applyAll s l₁) l₂ := by
  induction l₁ with
  | nil => intro s; rfl
  | cons r rs ih => intro s; exact ih (applyRow s r)

/-- **Per-key read correctness.**  Every access of key `k` saw the value
    obtained by executing the earlier accesses of key `k` from `s k`. -/
theorem read_correct (s : State V) (A B : List (Row V)) (h : Accepts s A B)
    (k : Nat) (P S : List (Row V)) (r : Row V)
    (hsplit : A.filter (onKey k) = P ++ r :: S) :
    r.vb = execVal (s k) P := by
  have hrA : r ∈ A.filter (onKey k) := by rw [hsplit]; simp
  have hrk : r.key = k := (onKey_iff k r).mp (List.mem_filter.mp hrA).2
  have hrB : r ∈ B :=
    (List.mem_filter.mp (h.perm.mem_iff.mpr (List.mem_filter.mp hrA).1)).1
  have hne : B.filter (onKey k) ≠ [] := by
    intro he
    have : r ∈ B.filter (onKey k) := List.mem_filter.mpr ⟨hrB, (onKey_iff k r).mpr hrk⟩
    rw [he] at this; simp at this
  obtain ⟨p, I, q, _, _, _, hI, hrc, hflow, hpv, _, hIeq⟩ := key_segment s A B h k hne
  rw [← hpv]
  exact segment_reads I p q hI hrc hflow P S r (hIeq.trans hsplit)

/-- Every access of the committed list saw the value of its key just before
    it in sequential order. -/
theorem access_correct (s : State V) (A B : List (Row V)) (h : Accepts s A B)
    (A₁ A₂ : List (Row V)) (r : Row V) (hA : A = A₁ ++ r :: A₂) :
    r.vb = applyAll s A₁ r.key := by
  rw [key_independence r.key A₁ s]
  apply read_correct s A B h r.key _ (A₂.filter (onKey r.key)) r
  rw [hA, List.filter_append, filter_pos _ rfl]

/-- **Read soundness.**  If the checks pass, the committed list is
    consistent with the pre-state. -/
theorem consistent_of_accepts (s : State V) (A B : List (Row V))
    (h : Accepts s A B) : Consistent s A := by
  have key : ∀ (rest A₁ : List (Row V)), A = A₁ ++ rest →
      Consistent (applyAll s A₁) rest := by
    intro rest
    induction rest with
    | nil => intro _ _; trivial
    | cons r rs ih =>
      intro A₁ he
      refine ⟨access_correct s A B h A₁ rs r he, ?_⟩
      have := ih (A₁ ++ [r]) (by rw [he]; simp)
      rwa [applyAll_append] at this
  exact key A [] (by simp)

/-- A Read of the committed list returns the value of its key just before
    it in sequential order. -/
theorem read_returns (s : State V) (A B : List (Row V)) (h : Accepts s A B)
    (A₁ A₂ : List (Row V)) (r : Row V) (hA : A = A₁ ++ r :: A₂)
    (hr : r.kind = .read) :
    r.va = applyAll s A₁ r.key := by
  have hrA : r ∈ A := by rw [hA]; simp
  have hrB : r ∈ B := (List.mem_filter.mp (h.perm.mem_iff.mpr hrA)).1
  rw [← h.readc r hrB (Or.inl hr)]
  exact access_correct s A B h A₁ A₂ r hA

A worked example

Two transactions over keys 1 and 2, every value initially 0. Transaction 1 writes 5 to key 2 and reads key 1. Transaction 2 reads key 2 and writes 7 to it. The committed list, in execution order:

kindkey(t,j)(t, j)vbv_bvav_a
Write2(1, 0)05
Read1(1, 1)00
Read2(2, 0)55
Write2(2, 1)57

The sorted log adds a Pre and a Post row per key:

kindkey(t,j)(t, j)vbv_bvav_a
Pre1(0, 0)00
Read1(1, 1)00
Post1(3, 0)00
Pre2(0, 0)00
Write2(1, 0)05
Read2(2, 0)55
Write2(2, 1)57
Post2(3, 0)77

Here T=2T = 2. Pre rows take version (0,0)(0, 0), below every access because accesses have t≥1t \ge 1. Post rows take (T+1,0)=(3,0)(T + 1, 0) = (3, 0), above every access. Lean checks that this pair is accepted, so the hypotheses of the soundness theorems can be met, that both the claimed and the sequential post-state are [0,0,7,0][0, 0, 7, 0] on keys 0 to 3, and that the committed list is consistent with the pre-state, as read soundness predicts.

/-! ## 11. A concrete check -/

def ex_s : State Nat := fun _ => 0

/-- Committed log in execution order: tx 1 writes key 2 := 5 and reads key 1;
    tx 2 reads key 2 and writes key 2 := 7. -/
def ex_A : List (Row Nat) :=
  [⟨.write, 2, 1, 0, 0, 5⟩, ⟨.read, 1, 1, 1, 0, 0⟩,
   ⟨.read, 2, 2, 0, 5, 5⟩, ⟨.write, 2, 2, 1, 5, 7⟩]

/-- The same accesses sorted by `(key, version)` with boundary rows. -/
def ex_B : List (Row Nat) :=
  [⟨.pre, 1, 0, 0, 0, 0⟩, ⟨.read, 1, 1, 1, 0, 0⟩, ⟨.post, 1, 3, 0, 0, 0⟩,
   ⟨.pre, 2, 0, 0, 0, 0⟩, ⟨.write, 2, 1, 0, 0, 5⟩, ⟨.read, 2, 2, 0, 5, 5⟩,
   ⟨.write, 2, 2, 1, 5, 7⟩, ⟨.post, 2, 3, 0, 7, 7⟩]

example : (List.range 4).map (applyAll ex_s ex_A) = [0, 0, 7, 0] := by decide
example : (List.range 4).map (claimedPost ex_s ex_B) = [0, 0, 7, 0] := by decide

/-- The hypotheses are satisfiable: the example log is accepted. -/
example : Accepts ex_s ex_A ex_B where
  sorted  := by unfold rowLe verLe; decide
  first   := by intro y h; simp [ex_B] at h; rw [← h]
  last    := by simp [ex_B, LastP]
  bnd     := by simp [ex_B, Adj, Bnd]
  perm    := by decide
  ordered := by unfold verLt; decide
  flow    := by simp [ex_B, Adj, Flow]
  readc   := by decide
  preVal  := by decide

example : Consistent ex_s ex_A := by simp [Consistent, ex_A, ex_s, applyRow, stepVal]

Distinct versions are necessary

Strictly increasing versions in AA is the one hypothesis that is not about BB. The checks constrain the value-before fields of AA only through flow in BB, and they constrain the order of AA‘s rows only through the versions. With a tie, the order is no longer fixed, and that is enough to break soundness.

A tie breaks soundness. For these checks, which place no direct constraint on the value-before fields of AA, there are ss, AA and BB such that all acceptance conditions hold except that the versions of AA are only non-decreasing, AA is not consistent with ss, and claimed(s,B)≠apply(s,A)\mathrm{claimed}(s, B) \ne \mathrm{apply}(s, A).

Proof. Let s(0)=1s(0) = 1 and let AA consist of the two rows (Write,0,(1,0),2,1)(\text{Write}, 0, (1,0), 2, 1) and (Write,0,(1,0),1,2)(\text{Write}, 0, (1,0), 1, 2), in this order, in the format (kind, key, version, vbv_b, vav_a). Sequential execution ends with 2. The first row records vb=2v_b = 2 although the state is 1, so AA is not consistent with ss. The sorted log may list the two writes in the opposite order, since equal versions are sorted either way: Pre with value 1, then (Write,0,(1,0),1,2)(\text{Write}, 0, (1,0), 1, 2), then (Write,0,(1,0),2,1)(\text{Write}, 0, (1,0), 2, 1), then Post with value 1. Flow holds along this order, every other check on BB passes, and the claimed value is 1. ∎

The flow check is not the problem: the reordered log is a correct execution, just of a different order. Only the versions say which order is the real one, so they must determine it.

The counterexample needs AA to record a value-before that sequential execution never produces. If AA were known in advance to be consistent with ss, a tie could not change the post-state. Fix a key and read each interior row as an edge vb→vav_b \to v_a of a directed multigraph. Both A∣kA|_k and the interior of B∣kB|_k are then trails from s(k)s(k) through the same multiset of edges, and the end of such a trail is fixed by the degrees: it is the unique vertex with one more incoming than outgoing edge, or s(k)s(k) if every vertex is balanced. (This remark is not formalised in Lean.) Order recovery still fails, though: the sorted log no longer certifies which access came where, as the next theorem shows.

A tie breaks order recovery. There are ss, AA and BB such that all acceptance conditions hold except that the versions of AA are only non-decreasing, AA is consistent with ss, and the interior of B∣0B|_0 differs from A∣0A|_0.

Proof. Let s(0)=1s(0) = 1 and A=[(Write,0,(1,0),1,2),(Write,0,(1,0),2,1),(Read,0,(1,0),1,1)]A = [(\text{Write}, 0, (1,0), 1, 2), (\text{Write}, 0, (1,0), 2, 1), (\text{Read}, 0, (1,0), 1, 1)], which is consistent with ss. The sorted log may put the Read first: Pre with value 1, the Read, the two Writes, Post with value 1. Flow holds, and every check on BB passes. ∎

/-! ## 12. Distinct versions are necessary -/

/-- Two writes to key `0` sharing version `(1, 0)`.  The sorted log may list
    them in either order; every other check still passes, yet the claimed
    post-state differs from sequential execution. -/
theorem distinct_versions_needed :
    ∃ (s : State Nat) (A B : List (Row Nat)),
      List.Pairwise rowLe B ∧
      (∀ y, B.head? = some y → y.kind = .pre) ∧
      LastP (fun r => r.kind = .post) B ∧
      Adj Bnd B ∧
      (B.filter interior).Perm A ∧
      List.Pairwise verLe A ∧
      Adj (fun x y => x.key = y.key → Flow x y) B ∧
      (∀ r ∈ B, r.kind = .read ∨ r.kind = .post → r.vb = r.va) ∧
      (∀ r ∈ B, r.kind = .pre → r.va = s r.key) ∧
      ¬ Consistent s A ∧
      claimedPost s B ≠ applyAll s A := by
  refine ⟨fun _ => 1,
    [⟨.write, 0, 1, 0, 2, 1⟩, ⟨.write, 0, 1, 0, 1, 2⟩],
    [⟨.pre, 0, 0, 0, 1, 1⟩, ⟨.write, 0, 1, 0, 1, 2⟩, ⟨.write, 0, 1, 0, 2, 1⟩,
     ⟨.post, 0, 2, 0, 1, 1⟩], ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩
  · unfold rowLe verLe; decide
  · intro y h; simp at h; rw [← h]
  · simp [LastP]
  · simp [Adj, Bnd]
  · decide
  · unfold verLe; decide
  · simp [Adj, Flow]
  · decide
  · decide
  · intro hc; exact absurd hc.1 (by decide)
  · intro h; exact absurd (congrFun h 0) (by decide)

/-- With a consistent committed list, a tie still breaks order recovery:
    every check passes, yet the interior of the sorted log for key `0` is
    not `A|₀`.  Here the post-state happens to agree. -/
theorem tie_breaks_order :
    ∃ (s : State Nat) (A B : List (Row Nat)),
      List.Pairwise rowLe B ∧
      (∀ y, B.head? = some y → y.kind = .pre) ∧
      LastP (fun r => r.kind = .post) B ∧
      Adj Bnd B ∧
      (B.filter interior).Perm A ∧
      List.Pairwise verLe A ∧
      Adj (fun x y => x.key = y.key → Flow x y) B ∧
      (∀ r ∈ B, r.kind = .read ∨ r.kind = .post → r.vb = r.va) ∧
      (∀ r ∈ B, r.kind = .pre → r.va = s r.key) ∧
      Consistent s A ∧
      (B.filter (onKey 0)).filter interior ≠ A.filter (onKey 0) ∧
      claimedPost s B 0 = applyAll s A 0 := by
  refine ⟨fun _ => 1,
    [⟨.write, 0, 1, 0, 1, 2⟩, ⟨.write, 0, 1, 0, 2, 1⟩, ⟨.read, 0, 1, 0, 1, 1⟩],
    [⟨.pre, 0, 0, 0, 1, 1⟩, ⟨.read, 0, 1, 0, 1, 1⟩, ⟨.write, 0, 1, 0, 1, 2⟩,
     ⟨.write, 0, 1, 0, 2, 1⟩, ⟨.post, 0, 2, 0, 1, 1⟩],
    ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩
  · unfold rowLe verLe; decide
  · intro y h; simp at h; rw [← h]
  · simp [LastP]
  · simp [Adj, Bnd]
  · decide
  · unfold verLe; decide
  · simp [Adj, Flow]
  · decide
  · decide
  · simp [Consistent, applyRow, stepVal]
  · decide
  · decide

end MemCheck

#print axioms MemCheck.key_independence
#print axioms MemCheck.segment_shape
#print axioms MemCheck.segment_sound
#print axioms MemCheck.interior_eq_committed
#print axioms MemCheck.post_correct
#print axioms MemCheck.untouched_correct
#print axioms MemCheck.batch_sound
#print axioms MemCheck.read_correct
#print axioms MemCheck.consistent_of_accepts
#print axioms MemCheck.read_returns
#print axioms MemCheck.distinct_versions_needed
#print axioms MemCheck.tie_breaks_order

Each #print axioms line reports a subset of propext, Quot.sound and Classical.choice, Lean’s standard axioms; no others are used.

From checks to a proof system

The theorems above are combinatorial. A verifier does not see BB; it sees a commitment and a proof. This section sketches the reduction that links the two. It is a remark, not a theorem: it is not checked in Lean, and it holds only to the extent that the following assumptions do.

  1. Binding commitments. The commitment to AA and the openings of ss (the values carried by Pre rows) and of the new state are binding. For hash-based commitments this follows from collision resistance of the hash.
  2. Post-state binding. The circuit checks that the opened new state equals claimed(s,B)\mathrm{claimed}(s, B): on every key with a Post row in BB it holds that row’s value vav_a, and on every other key it holds s(k)s(k).
  3. Knowledge soundness. From any prover that produces accepting proofs, an extractor obtains a witness BB satisfying conditions 1, 2, 5 and 6, and the circuit checks condition 4 on consecutive rows of AA (local sortedness for the strict version order). Each of these is a constraint on one row or on two consecutive rows.
  4. Sound permutation argument. Rows are encoded injectively as tuples of cc field elements over a field F\mathbb{F}. The grand-product argument compresses each row with a random challenge α\alpha and compares ∏i(γ−∑lαlxi,l)\prod_i (\gamma - \sum_l \alpha^l x_{i,l}) over the interior of BB and over AA at a random γ\gamma. The challenges α\alpha and γ\gamma are sampled, or derived by Fiat–Shamir, after the commitments to AA and BB are fixed, and the witness BB the extractor returns is the one committed before the challenges.

If the two multisets differ, the two products are different polynomials in (α,γ)(\alpha, \gamma): each factor is irreducible and determined by its row, and polynomial rings over a field have unique factorisation. Each product has total degree at most ncnc for nn rows, so, because (α,γ)(\alpha, \gamma) is chosen independently of the committed rows, by the Schwartz–Zippel lemma the products agree at a random point with probability at most nc/∣F∣nc/|\mathbb{F}|. A logarithmic-derivative argument, as in “Multivariate lookups based on logarithmic derivatives” (IACR ePrint 2022), sums 1/(γ−xi)1/(\gamma - x_i) instead of multiplying; provided the characteristic of F\mathbb{F} exceeds nn, it has an error bound of the same order. Grand-product permutation checks of this kind are the ones used in “PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge” (IACR ePrint 2019) and in lookup arguments such as “plookup: A simplified polynomial protocol for lookup tables” (IACR ePrint 2020).

Under assumptions 1–4, except with probability negligible in the security parameter plus nc/∣F∣nc/|\mathbb{F}| when the challenges are sampled interactively, or Q⋅nc/∣F∣Q \cdot nc/|\mathbb{F}| for a prover making QQ hash queries when they are derived by Fiat–Shamir, an accepted proof yields a witness BB that satisfies all six acceptance conditions against the committed AA and the opened ss. By the theorems above, every access in AA recorded the value of its key just before it, and, by batch soundness and assumption 2, the attested post-state claimed(s,B)\mathrm{claimed}(s, B) is apply(s,A)\mathrm{apply}(s, A).

Costs

Let the batch have nn accesses on mm distinct keys, so m≤nm \le n and BB has n+2mn + 2m rows.

  • Witness construction. Building BB means sorting n+2mn + 2m rows by (k,(t,j))(k, (t, j)): O((n+m)log⁡(n+m))=O(nlog⁡n)O((n + m)\log(n + m)) = O(n \log n) comparisons. Filling in the boundary rows and the flow values is one linear pass. Sorting dominates this step. Proving the resulting circuit is a separate cost, set by the proof system and not counted here; for the polynomial-commitment systems cited above it is quasi-linear in the circuit size and in practice usually larger than the cost of sorting.
  • Constraints. By contiguity, the first-and-last lemma and local sortedness, every check except the permutation reads one row or two consecutive rows, so there are O(n+m)O(n + m) such checks. Let ww be the largest bit width of a key or of a version component. Each order comparison on (k,(t,j))(k, (t, j)) then costs O(w)O(w) constraints with a bit decomposition, so the checks total O((n+m)w)=O(nw)O((n + m) w) = O(n w) constraints. With lookups, split each compared quantity into limbs of bb bits: a comparison costs O(⌈w/b⌉)O(\lceil w/b \rceil) lookups into a range table of size 2b2^b, so O(n⌈w/b⌉)O(n \lceil w/b \rceil) lookups in total. A single lookup per comparison corresponds to b=wb = w and is meaningful only when a table of size 2w2^w is feasible. The width ww is not bounded by nn: keys are arbitrary, and a 256-bit key gives w=256w = 256 for any nn. In the other direction, nn strictly increasing versions are nn distinct pairs (t,j)(t, j), so the version pair needs at least ⌈log⁡2n⌉\lceil \log_2 n \rceil bits in total and w≥⌈log⁡2n⌉/2w \ge \lceil \log_2 n \rceil / 2; the version part cannot be made smaller. The total is O(nlog⁡n)O(n \log n) constraints exactly when keys and version components are encoded in O(log⁡n)O(\log n) bits. The permutation argument adds O(c)O(c) constraints per row.
  • Verifier. It never sorts and never replays the batch. Its work is whatever the proof system charges for verifying a circuit of that size.

These bounds follow from the shape of the constraints; they are not Lean theorems.

Limitations and open questions

  • Keys and version components are natural numbers. The proofs use omega for the orders; they are not stated for an arbitrary linearly ordered key type.
  • Boundary versions are a convention: Pre rows need a version at or below every access to the key, and Post rows one at or above. With transactions numbered from 1, the choice (0,0)(0, 0) for Pre and (T+1,0)(T + 1, 0) for Post works for a batch of TT transactions. This is part of how BB is built, not something the proofs derive.
  • Whether a tie can change the post-state when AA is known to be consistent is settled above only by an informal trail argument; formalising it needs multigraph degree counting that the file does not develop.
  • The link to a proof system is a reduction sketched in prose. Formalising it would need a model of the proof system and of the random challenges, which core Lean does not provide.
  • Whether the Pre and Post rows can be removed, by letting the first and last access of each key carry the boundary values, without losing the local character of every check, is the question I would like to settle next.