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 to , 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 to the claimed .
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 . The kind is one of Pre, Read, Write or Post. The key is . The pair is the version. The values and 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 write , , and for its components.
Version. The transactions of a batch are numbered , and the accesses inside a transaction are numbered from 0. For an access, is the number of its transaction and is the number of the access inside that transaction. The value is reserved for Pre rows and for Post rows. Versions are ordered lexicographically: if , or and . Rows are ordered lexicographically by .
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 from keys to values. One access acts on a single value by if is a Write and otherwise. Applying to a state changes only key . For an access list , applies the rows from left to right, and folds over a list starting from the value .
/-! ## 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 for the subsequence of made of the rows with key , in their original order. For lists, is with prepended, is concatenation, and is the one-element list.
Key independence. For every access list , state and key ,
Proof. Induction on . A row with key updates key exactly as does and stays in . A row with another key leaves key alone and is dropped from . ∎
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 , 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 on rows, holds if every pair of consecutive elements of satisfies .
The first lemma is what makes “consecutive in sorted order” useful. If is sorted by key, the rows of one key form a contiguous block, so two rows that are consecutive in were already consecutive in . A constraint that satisfies on consecutive rows of the same key therefore holds on every consecutive pair of .
Contiguity. If is sorted by key and every consecutive pair of with equal keys satisfies , then holds for every key .
Proof. Induction on . If the head has key and the next row also does, the pair is consecutive in both lists. If has a different key, sortedness puts every later row at a key above , so nothing after 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 satisfy if: when , is not a Post and is not a Pre; when , is a Post and is a Pre.
First and last rows. Suppose satisfies , its first row is a Pre and its last row is a Post. Then for every key , the first row of is a Pre and the last row of is a Post.
Proof. The first row of key is either the first row of 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 is sorted by key, starts with a Pre, ends with a Post and satisfies . Then for every key that occurs in ,
with a Pre, a Post and every row of a Read or a Write. In particular each key has exactly one Pre row and one Post row.
Proof. By contiguity, consecutive rows of satisfy the same-key half of : 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 with the same key satisfy flow if : each row starts from the value the previous row of its key left. A Read row (and a Post row) is consistent if : it does not change the value.
Segment soundness. Let every row of be a Read or a Write, every Read in be consistent, and let flow hold on every consecutive pair of . Then
Proof. Induction on . For the first interior row , flow gives . If is a Write, by definition. If is a Read, by consistency. Either way the segment continues from , and the induction hypothesis applies with in place of . ∎
/-! ## 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 . It does not yet say that they are the rows of in the order of . That is the next step.
Recovering the order
The permutation argument guarantees that the interior rows of are a rearrangement of the committed list , nothing more. Two facts close the gap. Filtering commutes with permutation, so the interior rows of key in are a rearrangement of . And two lists that are rearrangements of each other and are both sorted, in compatible orders, are equal.
Sorted permutations are equal. Let be a permutation of , with sorted by and sorted by (each pair in list order satisfies the relation). If no satisfy both and , then .
Proof. Induction on . Let and be the heads. If , then occurs later in and occurs later in , so and , which is excluded. So ; cancel it from both sides and apply the induction hypothesis to the tails. ∎
Here is the non-strict version order (from sorting ) and is the strict version order (from the executor’s order on ). and would mean , 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 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 is sorted by , the interior rows of are a permutation of , and the versions in strictly increase. Then for every key , the interior rows of are exactly , as lists.
Proof. Filtering the permutation by key gives that the interior of is a permutation of . Inside one key, the order on reduces to the version order, so the interior of is sorted by non-strict version; is sorted by strict version because 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 is transitive and every consecutive pair of satisfies , then every pair of in list order satisfies . This applies to the order on for and to the strict version order for .
/-! ## 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 , a committed access list and a sorted log , the verifier accepts if:
- is sorted by ;
- the first row of is a Pre, the last is a Post, and holds;
- the interior rows of are a permutation of ;
- the versions of strictly increase;
- flow holds on consecutive rows of with the same key, and every Read and Post row is consistent;
- every Pre row carries the pre-state: .
The claimed post-state maps a key to the value of its Post row if it has one, and to 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 satisfies .
Proof. Let . By the per-key shape, (the Post row of a key is unique, so it is ). Contiguity carries flow to ; this per-key summary is the lemma key_segment below, reused in the next section. Segment soundness gives . Order recovery gives , condition 6 gives , and consistency of gives . So , which is 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:
Proof. Pointwise in . If has a Post row of key , use the previous theorem. If has some row of key but no Post row, the per-key shape is contradicted. If has no row of key at all, order recovery gives , so by key independence , 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 is consistent with a state if every row of records as its value-before the value of its key just before it in sequential order: whenever , .
Reads are correct. If the verifier accepts, then:
- for every key and every split , ;
- is consistent with . In particular every Read in returned , the value of its key just before it.
Proof. For 1: lies in , so by the permutation it lies in and key occurs in . The per-key summary used for Post rows gives with flow, and , so . Induction on , exactly as in segment soundness: the first interior row starts at by flow, and each row ends at the value gives it, so . For 2: if , then ; apply 1 and key independence. A Read of is an interior row of , so read consistency gives . ∎
/-! ## 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:
| kind | key | |||
|---|---|---|---|---|
| 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 sorted log adds a Pre and a Post row per key:
| kind | key | |||
|---|---|---|---|---|
| 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 |
Here . Pre rows take version , below every access because accesses have . Post rows take , 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 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 is the one hypothesis that is not about . The checks constrain the value-before fields of only through flow in , and they constrain the order of ‘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 , there are , and such that all acceptance conditions hold except that the versions of are only non-decreasing, is not consistent with , and .
Proof. Let and let consist of the two rows and , in this order, in the format (kind, key, version, , ). Sequential execution ends with 2. The first row records although the state is 1, so is not consistent with . The sorted log may list the two writes in the opposite order, since equal versions are sorted either way: Pre with value 1, then , then , then Post with value 1. Flow holds along this order, every other check on 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 to record a value-before that sequential execution never produces. If were known in advance to be consistent with , a tie could not change the post-state. Fix a key and read each interior row as an edge of a directed multigraph. Both and the interior of are then trails from 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 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 , and such that all acceptance conditions hold except that the versions of are only non-decreasing, is consistent with , and the interior of differs from .
Proof. Let and , which is consistent with . 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 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 ; 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.
- Binding commitments. The commitment to and the openings of (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.
- Post-state binding. The circuit checks that the opened new state equals : on every key with a Post row in it holds that row’s value , and on every other key it holds .
- Knowledge soundness. From any prover that produces accepting proofs, an extractor obtains a witness satisfying conditions 1, 2, 5 and 6, and the circuit checks condition 4 on consecutive rows of (local sortedness for the strict version order). Each of these is a constraint on one row or on two consecutive rows.
- Sound permutation argument. Rows are encoded injectively as tuples of field elements over a field . The grand-product argument compresses each row with a random challenge and compares over the interior of and over at a random . The challenges and are sampled, or derived by Fiat–Shamir, after the commitments to and are fixed, and the witness the extractor returns is the one committed before the challenges.
If the two multisets differ, the two products are different polynomials in : 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 for rows, so, because is chosen independently of the committed rows, by the Schwartz–Zippel lemma the products agree at a random point with probability at most . A logarithmic-derivative argument, as in “Multivariate lookups based on logarithmic derivatives” (IACR ePrint 2022), sums instead of multiplying; provided the characteristic of exceeds , 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 when the challenges are sampled interactively, or for a prover making hash queries when they are derived by Fiat–Shamir, an accepted proof yields a witness that satisfies all six acceptance conditions against the committed and the opened . By the theorems above, every access in recorded the value of its key just before it, and, by batch soundness and assumption 2, the attested post-state is .
Costs
Let the batch have accesses on distinct keys, so and has rows.
- Witness construction. Building means sorting rows by : 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 such checks. Let be the largest bit width of a key or of a version component. Each order comparison on then costs constraints with a bit decomposition, so the checks total constraints. With lookups, split each compared quantity into limbs of bits: a comparison costs lookups into a range table of size , so lookups in total. A single lookup per comparison corresponds to and is meaningful only when a table of size is feasible. The width is not bounded by : keys are arbitrary, and a 256-bit key gives for any . In the other direction, strictly increasing versions are distinct pairs , so the version pair needs at least bits in total and ; the version part cannot be made smaller. The total is constraints exactly when keys and version components are encoded in bits. The permutation argument adds 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
omegafor 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 for Pre and for Post works for a batch of transactions. This is part of how is built, not something the proofs derive.
- Whether a tie can change the post-state when 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.