Research / 2021 –

Upgrading everything but the store

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

An architecture in which one persistent key-value store is fixed and every other component, including the registry that names components, can be replaced. Upgrades never touch stored state; only setters write; flattened keys are faithful exactly when the key encoding is injective; positional layouts collide where keyed ones cannot; a two-step role transfer opens a stale-writer window that an atomic or revoke-first transfer closes; registry replacement keeps every name resolvable under a stated ordering; and the set of components that can change a binding is a reachability closure.

Dynamic software updatingAccess controlKey-value storage
iff injective
a nested map family is faithfully stored under flattened keys exactly when the key encoding is injective on its domain
3 changers
when only an admin may replace the registry, exactly the admin, the registry and the binding itself can change a binding
1 window
granting the new writer before revoking the old one admits a state in which both write

A long-lived system wants to replace its logic without moving its data. One way is to fix a single persistent store and make everything else replaceable: the code that reads, the code that writes, the application logic, and even the registry through which components find each other. This page states that architecture abstractly and proves, in Lean 4, what keeps it safe.

Goal. Replace any component except the store, including the registry, without migrating state or changing the names clients use, while the set of parties able to write, and the set able to redirect writes, stays bounded at every moment.

The architecture

componentrolereplaceable
storekey-value map; values of built-in and derived types (sets, maps) under hashed keysno
gettersread the storeyes
setterswrite the store; only holders of the writer roleyes
registrymaps names to current component addressesyes
envoysresolve names through a registry at call time and dispatch calls; may be re-pointed to another registryyes
application componentscall getters and setters through their envoy; may re-point their envoyyes

On a smart-contract platform the store is one contract that is never upgraded, every other component is a separate contract reached by address, names are fixed identifiers, and roles are access-control entries in the store.

The store and its keys

Upgrades never touch state (replacements_preserve_store, upgrades_preserve_store, upgrades_preserve_reads). Any sequence of upgrade steps (deploying code, editing any registry, re-pointing any envoy or application component, changing roles) leaves the store unchanged, and every getter reads exactly what it read before. Names clients hold are unchanged; only pointers move (replace_only_moves_pointer).

Only setters write (only_setters_write, store_change_by_setter, store_change_authorised). If a step changes the store, it is a call that resolves to a setter holding the writer role at that moment; a call to a getter, or to anything else, changes nothing (getter_call_noop, nonsetter_call_noop).

A nested map such as foo[k1][k2]\mathit{foo}[k_1][k_2] is stored at the single key H(enc("foo",k1,k2))H(\mathrm{enc}(\text{"foo"}, k_1, k_2)).

Flattening (flatten_faithful_iff, represent_iff_key_inj, writes_commute_iff_key_inj). Every nested family indexed by a domain DD is faithfully represented (for any value type with at least two values) by the single store keyed by H(enc(⋅))H(\mathrm{enc}(\cdot)) if and only if enc\mathrm{enc} is injective on DD and HH is injective on enc(D)\mathrm{enc}(D). A length-prefixed encoding, with each length written as a single symbol that can hold any length, is injective across all names and arities (encLP_injective); a packed encoding is not: ("ab",["c"])(\text{"ab"}, [\text{"c"}]) and ("a",["bc"])(\text{"a"}, [\text{"bc"}]) encode identically, and then some family has no faithful flat representation (packed_collision, packed_not_faithful). Injectivity of HH is a hypothesis (collision resistance), not a result.

Schema compatibility (schema_compat_iff, module_isolation). For any value type with at least two values, a new version reads every old field exactly as the old version did, in every store, if and only if the two key derivations agree on the old fields; distinct namespaces never interfere given injectivity, and without it they can (collision_without_injectivity).

Layout (positional_insert_collides, kv_no_collision). With positional (offset-based) storage, inserting a field before an existing one makes the new field occupy the old field’s slot, so the new version reads old data under the wrong name (positional_counterexample). With keyed storage every field keeps its key in every version, and, given injectivity of the key hash on the fields in use, no two fields collide.

Who may write

Stale-writer window (stale_writer_window, stale_writer_trace). Upgrading a writer as grant the new writer, then revoke the old one passes through a state in which both can write; the interleaving grant new, write new, write old is executable.

Safe transfers (atomic_transfer_safe, revoke_then_grant_safe, rtg_completes). An atomic transfer, or the order revoke old, re-point, grant new, keeps “only the current logic writes” in every reachable state, including every intermediate one, and does complete the upgrade.

Replacing the registry

Resolvability (resolvable_under_protocol, envoyPoint_iff, registry_replacement). Every step taken under the stated protocol preserves “every name used by every application component resolves to a live component”. Re-pointing an envoy to a registry keeps this, starting from a state where it holds, exactly when that registry binds every name used through the envoy to a live component. Replacing the registry is therefore safe in the order deploy the new registry, bind every needed name, then re-point the envoy; re-pointing first breaks a name (counterexample_repoint_before_populate).

Who can change what

Let can(y,x)\mathit{can}(y, x) mean that component yy can directly replace or redirect xx.

Changers are a closure (changers_eq_closure, closure_bounded). The components able to change XX through any sequence of steps are exactly those related to XX by the reflexive-transitive closure of can\mathit{can}, and any set closed backwards under can\mathit{can} bounds them.

Escalation (escalation). If every application component can re-point its envoy, every envoy can replace the registry, and the registry controls every binding, then every application component can transitively change every getter and setter binding.

Bounded authority (bounded_closure). If replacing the registry is reserved to an admin role, the components able to change a binding are exactly the admin, the registry and the binding itself, whether or not application components may re-point their envoys.

Limits

  • The model is sequential: steps are atomic and totally ordered, as transactions on a single chain are; concurrency inside a step is not modelled.
  • Collision resistance of the key hash is assumed.
  • The correctness of each component’s own logic is outside the model; the results are about state, routing and authority.

Prior work

Dynamic software updating (ACM TOPLAS, 2005; PLDI 2006); separating persistent storage from replaceable logic in smart contracts (the eternal-storage pattern, 2017); proxy contracts with standardised storage slots, beacon proxies and multi-facet proxies; the service-locator pattern; role-based access control.

The Lean development

All definitions and proofs (1525 lines, Lean 4, core library only)
/-!
# Basic definitions

Point updates of functions (a persistent store is a total function from keys to values)
and injectivity on a domain (the collision-resistance hypothesis used for derived keys).
-/
namespace Upgrades

/-- Point update: `upd f a b` agrees with `f` everywhere except at `a`, where it is `b`. -/
def upd {α β : Type} [DecidableEq α] (f : α → β) (a : α) (b : β) : α → β :=
  fun x => if x = a then b else f x

@[simp] theorem upd_same {α β : Type} [DecidableEq α] (f : α → β) (a : α) (b : β) :
    upd f a b a = b := by simp [upd]

theorem upd_ne {α β : Type} [DecidableEq α] (f : α → β) {a x : α} (b : β) (h : x ≠ a) :
    upd f a b x = f x := by simp [upd, h]

/-- `H` is injective on the domain `D`. Used only as a hypothesis (collision resistance of a
key-derivation function on the inputs actually used), never as an axiom. -/
def InjOn {α K : Type} (D : α → Prop) (H : α → K) : Prop :=
  ∀ a b, D a → D b → H a = H b → a = b

end Upgrades

/-!
# Architecture model: persistent store, getters, setters, registries, envoys, middleware

Components live at addresses. The only persistent component is the store `K → V`. Every
other component is code at an address:

* a *getter* is a function of the store (read-only by its type);
* a *setter* computes a list of key/value writes from the store and an argument;
* a *registry* holds a table `name ↦ address` (several named pointers);
* an *envoy* holds a pointer to a registry and dispatches calls by name;
* a *middleware* component uses a list of names and holds a pointer to its envoy.

A call by middleware `m` on name `n` is resolved at call time:
`resolve s m n = table (envReg (mwEnv m)) n`.

Theorems in this file:
* (T2) read/write separation: `getter_call_noop`, `nonsetter_call_noop`, `only_setters_write`,
  `store_change_by_setter` (trace form), `add_or_replace_getter_preserves_store`.
* (T3) state preservation: `upgrades_preserve_store`, `upgrades_preserve_reads`.
-/
namespace Upgrades.Arch

open Upgrades

/-- Code deployed at an address. -/
inductive Comp (K V A Nm : Type) where
  | empty
  | getter (g : (K → V) → A → V)
  | setter (f : (K → V) → A → List (K × V))
  | registry
  | envoy
  | middleware (uses : List Nm)

def Comp.isLive {K V A Nm : Type} : Comp K V A Nm → Bool
  | .empty => false
  | _ => true

structure Sys (Ad K V A Nm : Type) where
  store  : K → V
  kind   : Ad → Comp K V A Nm
  table  : Ad → Nm → Option Ad
  envReg : Ad → Ad
  mwEnv  : Ad → Ad
  writer : Ad → Bool

/-- Every step other than `call` is an upgrade step on non-store components. -/
inductive Step (Ad K V A Nm : Type) where
  | deploy (a : Ad) (c : Comp K V A Nm)
  | regSet (r : Ad) (n : Nm) (a : Ad)
  | regDel (r : Ad) (n : Nm)
  | envoyPoint (e r : Ad)
  | mwPoint (m e : Ad)
  | grant (a : Ad)
  | revoke (a : Ad)
  | call (m : Ad) (n : Nm) (x : A)

variable {Ad K V A Nm : Type} [DecidableEq Ad] [DecidableEq K] [DecidableEq Nm]

def resolve (s : Sys Ad K V A Nm) (m : Ad) (n : Nm) : Option Ad := s.table (s.envReg (s.mwEnv m)) n

/-- Apply a list of writes to the store, left to right. -/
def applyWrites (st : K → V) : List (K × V) → K → V
  | [] => st
  | (k, v) :: ws => applyWrites (upd st k v) ws

/-- Effect of a call: only a resolved setter holding the writer role changes the store. -/
def callEffect (s : Sys Ad K V A Nm) (m : Ad) (n : Nm) (x : A) : Sys Ad K V A Nm :=
  match resolve s m n with
  | none => s
  | some a => match s.kind a with
    | .setter f => if s.writer a then { s with store := applyWrites s.store (f s.store x) } else s
    | _ => s

def step (s : Sys Ad K V A Nm) : Step Ad K V A Nm → Sys Ad K V A Nm
  | .deploy a c => { s with kind := upd s.kind a c }
  | .regSet r n a => { s with table := upd s.table r (upd (s.table r) n (some a)) }
  | .regDel r n => { s with table := upd s.table r (upd (s.table r) n none) }
  | .envoyPoint e r => { s with envReg := upd s.envReg e r }
  | .mwPoint m e => { s with mwEnv := upd s.mwEnv m e }
  | .grant a => { s with writer := upd s.writer a true }
  | .revoke a => { s with writer := upd s.writer a false }
  | .call m n x => callEffect s m n x

def run (s : Sys Ad K V A Nm) (tr : List (Step Ad K V A Nm)) : Sys Ad K V A Nm := tr.foldl step s

theorem run_cons (s : Sys Ad K V A Nm) (e : Step Ad K V A Nm) (tr : List (Step Ad K V A Nm)) :
    run s (e :: tr) = run (step s e) tr := rfl

def Step.isUpgrade : Step Ad K V A Nm → Bool
  | .call _ _ _ => false
  | _ => true

/-- A call is a *setter call* in `s` if it resolves to a setter holding the writer role. -/
def SetterCall (s : Sys Ad K V A Nm) (m : Ad) (n : Nm) : Prop :=
  ∃ a f, resolve s m n = some a ∧ s.kind a = .setter f ∧ s.writer a = true

/-! ### (T2) Read/write separation -/

/-- (T2a) A call that resolves to a getter leaves the entire system state unchanged. -/
theorem getter_call_noop (s : Sys Ad K V A Nm) (m : Ad) (n : Nm) (x : A) (a : Ad)
    (g : (K → V) → A → V) (hr : resolve s m n = some a) (hg : s.kind a = .getter g) :
    step s (.call m n x) = s := by
  simp [step, callEffect, hr, hg]

/-- (T2b) Any call that is not a setter call (unresolved name, getter, non-setter code, or a
setter without the writer role) leaves the entire system state unchanged. -/
theorem nonsetter_call_noop (s : Sys Ad K V A Nm) (m : Ad) (n : Nm) (x : A)
    (h : ¬ SetterCall s m n) : step s (.call m n x) = s := by
  simp only [step, callEffect]
  split
  · rfl
  · rename_i a hr
    split
    · rename_i f hk
      by_cases hw : s.writer a = true
      · exact absurd ⟨a, f, hr, hk, hw⟩ h
      · simp [hw]
    · rfl

/-- (T2c) Only setters write: if a single step changes the store, it is a call that resolves
to a setter holding the writer role. -/
theorem only_setters_write (s : Sys Ad K V A Nm) (e : Step Ad K V A Nm)
    (h : (step s e).store ≠ s.store) : ∃ m n x, e = .call m n x ∧ SetterCall s m n := by
  cases e with
  | call m n x =>
    refine ⟨m, n, x, rfl, ?_⟩
    apply Classical.byContradiction
    intro hn
    exact h (by rw [nonsetter_call_noop s m n x hn])
  | deploy => exact absurd rfl h
  | regSet => exact absurd rfl h
  | regDel => exact absurd rfl h
  | envoyPoint => exact absurd rfl h
  | mwPoint => exact absurd rfl h
  | grant => exact absurd rfl h
  | revoke => exact absurd rfl h

/-- (T2d) Trace form: if the store differs after an arbitrary trace, then some position `i`
of the trace is a call that, in the state reached just before it, resolves to a setter
holding the writer role. -/
theorem store_change_by_setter :
    ∀ (tr : List (Step Ad K V A Nm)) (s : Sys Ad K V A Nm), (run s tr).store ≠ s.store →
      ∃ i m n x, tr[i]? = some (.call m n x) ∧ SetterCall (run s (tr.take i)) m n := by
  intro tr
  induction tr with
  | nil => intro s h; exact absurd rfl h
  | cons e tr ih =>
    intro s h
    by_cases h1 : (step s e).store = s.store
    · have h2 : (run (step s e) tr).store ≠ (step s e).store := by rw [h1]; exact h
      obtain ⟨i, m, n, x, hi, hc⟩ := ih (step s e) h2
      exact ⟨i + 1, m, n, x, by simpa using hi, by simpa [run_cons] using hc⟩
    · obtain ⟨m, n, x, he, hc⟩ := only_setters_write s e h1
      exact ⟨0, m, n, x, by simp [he], by simpa [run] using hc⟩

/-- (T2e) Adding or replacing any getter — deploying getter code `g` at a fresh address `a`
and binding name `n` to it in registry `r` — preserves the store. -/
theorem add_or_replace_getter_preserves_store (s : Sys Ad K V A Nm) (a r : Ad) (n : Nm)
    (g : (K → V) → A → V) :
    (run s [.deploy a (.getter g), .regSet r n a]).store = s.store := rfl

/-! ### (T3) State preservation under upgrades of non-store components -/

/-- (T3a) Any sequence of upgrade steps (deploying code, editing any registry, re-pointing
any envoy to any registry, re-pointing any middleware to any envoy, changing roles) leaves
the store unchanged. -/
theorem upgrades_preserve_store :
    ∀ (tr : List (Step Ad K V A Nm)) (s : Sys Ad K V A Nm),
      (∀ e ∈ tr, e.isUpgrade = true) → (run s tr).store = s.store := by
  intro tr
  induction tr with
  | nil => intro s _; rfl
  | cons e tr ih =>
    intro s h
    rw [run_cons, ih (step s e) (fun b hb => h b (List.mem_cons_of_mem _ hb))]
    have he := h e (List.mem_cons_self _ _)
    cases e with
    | call => simp [Step.isUpgrade] at he
    | _ => rfl

/-- (T3b) Moreover, interleaving calls that are not setter calls changes nothing either:
for any trace in which every call is, at its moment, not a setter call, the store is
preserved. -/
theorem nonwriting_traces_preserve_store :
    ∀ (tr : List (Step Ad K V A Nm)) (s : Sys Ad K V A Nm),
      (∀ i m n x, tr[i]? = some (.call m n x) → ¬ SetterCall (run s (tr.take i)) m n) →
      (run s tr).store = s.store := by
  intro tr s h
  apply Classical.byContradiction
  intro hne
  obtain ⟨i, m, n, x, hi, hc⟩ := store_change_by_setter tr s hne
  exact h i m n x hi hc

/-- (T3c) Reads are preserved: after any upgrade sequence, any getter code reads exactly
what it read before, for every argument, and the names clients use are unchanged values
of type `Nm` (only pointers moved). -/
theorem upgrades_preserve_reads (tr : List (Step Ad K V A Nm)) (s : Sys Ad K V A Nm)
    (h : ∀ e ∈ tr, e.isUpgrade = true) (g : (K → V) → A → V) (x : A) :
    g (run s tr).store x = g s.store x := by
  rw [upgrades_preserve_store tr s h]

end Upgrades.Arch

/-!
# (4) Write authority during an upgrade

State: the current logic `cur` (the registry pointer), the writer-role table, and the phase of
an in-flight upgrade procedure. Writes by any principal may interleave with every step of the
procedure; a write by `p` is enabled iff `p` holds the writer role.

Invariant `OnlyCurrentLogicWrites`: every writer-role holder is the current logic.

* `stale_writer_window`: the two-step procedure `grant(new); revoke(old)` reaches, from any
  state satisfying the invariant, a state where both old and new logic can write; the
  interleaving `grant new; write new; write old; revoke old` is executable
  (`stale_writer_trace`).
* `atomic_transfer_safe`: with an atomic transfer step, every reachable state satisfies
  the invariant.
* `revoke_then_grant_safe`: with the three-step procedure revoke(old); point(new);
  grant(new), every reachable state, including all intermediate ones, satisfies the invariant.
* `atomic_write_only_current`, `rtg_write_only_current`: hence only the current logic writes.
-/
namespace Upgrades.Authority

open Upgrades

inductive Phase (P : Type) where
  | idle
  | granted (new : P)
  | revoked
  | pointed

structure AState (P : Type) where
  cur    : P
  writer : P → Bool
  phase  : Phase P

inductive Ev (P : Type) where
  | write (p : P)
  | grant (p : P)
  | revoke (p : P)
  | point (p : P)
  | transfer (p : P)

variable {P : Type} [DecidableEq P]

def OnlyCurrentLogicWrites (s : AState P) : Prop := ∀ q, s.writer q = true → q = s.cur

/-- Initial state: logic `p` is current and the sole writer. -/
def init (p : P) : AState P := ⟨p, fun q => decide (q = p), .idle⟩

theorem init_inv (p : P) : OnlyCurrentLogicWrites (init p) := by
  intro q h; simpa [init] using h

/-- Execute a trace; `none` if some event is not enabled. -/
def exec (step : AState P → Ev P → Option (AState P)) : AState P → List (Ev P) → Option (AState P)
  | s, [] => some s
  | s, e :: es => match step s e with
    | none => none
    | some s' => exec step s' es

omit [DecidableEq P] in
theorem exec_preserves (step : AState P → Ev P → Option (AState P)) (I : AState P → Prop)
    (h : ∀ s e s', I s → step s e = some s' → I s') :
    ∀ (tr : List (Ev P)) (s s' : AState P), I s → exec step s tr = some s' → I s' := by
  intro tr
  induction tr with
  | nil => intro s s' hs he; simp [exec] at he; exact he ▸ hs
  | cons e es ih =>
    intro s s' hs he
    simp only [exec] at he
    split at he
    · simp at he
    · rename_i s1 hs1
      exact ih s1 s' (h s e s1 hs hs1) he

/-! ### Two-step procedure: grant(new); revoke(old) -/

def stepTwo (s : AState P) : Ev P → Option (AState P)
  | .write p => if s.writer p then some s else none
  | .grant p => match s.phase with
    | .idle => some { s with writer := upd s.writer p true, phase := .granted p }
    | _ => none
  | .revoke p => match s.phase with
    | .granted n => if p = s.cur then some ⟨n, upd s.writer p false, .idle⟩ else none
    | _ => none
  | _ => none

/-- (4a) Stale-writer window, general form: from any idle state where only the current logic
`old` writes, granting `new ≠ old` reaches a state where both can write, violating the
invariant. -/
theorem stale_writer_window (s : AState P) (hs : s.writer s.cur = true) (hidle : s.phase = .idle)
    (new : P) (hne : new ≠ s.cur) :
    ∃ s', stepTwo s (.grant new) = some s' ∧ s'.writer s.cur = true ∧ s'.writer new = true ∧
      ¬ OnlyCurrentLogicWrites s' := by
  refine ⟨{ s with writer := upd s.writer new true, phase := .granted new }, ?_, ?_, ?_, ?_⟩
  · simp [stepTwo, hidle]
  · simp [upd_ne _ _ (Ne.symm hne), hs]
  · simp
  · intro hI
    exact hne (hI new (by simp))

/-- (4a') The concrete interleaving `grant new; write new; write old` is executable from the
initial state: both the old and the new logic perform a write. Completing the procedure with
`revoke old` then restores the invariant with `new` current. -/
theorem stale_writer_trace (old new : P) (hne : old ≠ new) :
    (∃ s, exec stepTwo (init old) [.grant new, .write new, .write old] = some s ∧
      s.writer old = true ∧ s.writer new = true ∧ ¬ OnlyCurrentLogicWrites s) ∧
    (∃ s, exec stepTwo (init old) [.grant new, .write new, .write old, .revoke old] = some s ∧
      s.cur = new ∧ OnlyCurrentLogicWrites s) := by
  have hne' : new ≠ old := Ne.symm hne
  constructor
  · refine ⟨{ init old with writer := upd (init old).writer new true, phase := .granted new },
      ?_, ?_, ?_, ?_⟩
    · simp [exec, stepTwo, init, upd, hne, hne']
    · simp [init, upd, hne]
    · simp [upd]
    · intro hI; exact hne' (hI new (by simp [upd]))
  · refine ⟨⟨new, upd (upd (init old).writer new true) old false, .idle⟩, ?_, rfl, ?_⟩
    · simp [exec, stepTwo, init, upd, hne, hne']
    · intro q hq
      by_cases h1 : q = old
      · subst h1; simp at hq
      · by_cases h2 : q = new
        · exact h2
        · simp [upd, init, h1, h2] at hq

/-! ### Atomic transfer -/

def stepAtomic (s : AState P) : Ev P → Option (AState P)
  | .write p => if s.writer p then some s else none
  | .transfer p => some ⟨p, upd (upd s.writer s.cur false) p true, .idle⟩
  | _ => none

theorem stepAtomic_inv (s : AState P) (e : Ev P) (s' : AState P) (hI : OnlyCurrentLogicWrites s)
    (h : stepAtomic s e = some s') : OnlyCurrentLogicWrites s' := by
  cases e with
  | write p =>
    simp only [stepAtomic] at h
    split at h
    · simp at h; exact h ▸ hI
    · simp at h
  | transfer p =>
    simp only [stepAtomic, Option.some.injEq] at h
    subst h
    intro q hq
    by_cases hqp : q = p
    · exact hqp
    · simp only [upd, hqp, if_false] at hq
      by_cases hqc : q = s.cur
      · simp [hqc] at hq
      · simp [hqc] at hq; exact absurd (hI q hq) hqc
  | grant _ => simp [stepAtomic] at h
  | revoke _ => simp [stepAtomic] at h
  | point _ => simp [stepAtomic] at h

/-- (4b) Atomic transfer: every state reachable by any interleaving of writes and transfers
satisfies `OnlyCurrentLogicWrites`. -/
theorem atomic_transfer_safe (s0 : AState P) (h0 : OnlyCurrentLogicWrites s0)
    (tr : List (Ev P)) (s : AState P) (h : exec stepAtomic s0 tr = some s) :
    OnlyCurrentLogicWrites s :=
  exec_preserves stepAtomic OnlyCurrentLogicWrites stepAtomic_inv tr s0 s h0 h

theorem atomic_write_only_current (s0 : AState P) (h0 : OnlyCurrentLogicWrites s0)
    (tr : List (Ev P)) (s : AState P) (h : exec stepAtomic s0 tr = some s) (p : P)
    (hw : (stepAtomic s (.write p)).isSome) : p = s.cur := by
  have hI := atomic_transfer_safe s0 h0 tr s h
  simp only [stepAtomic] at hw
  split at hw
  · rename_i hp; exact hI p hp
  · simp at hw

/-! ### Revoke-then-grant: revoke(old); point(new); grant(new) -/

def stepRTG (s : AState P) : Ev P → Option (AState P)
  | .write p => if s.writer p then some s else none
  | .revoke p => match s.phase with
    | .idle => if p = s.cur then some { s with writer := upd s.writer p false, phase := .revoked }
      else none
    | _ => none
  | .point p => match s.phase with
    | .revoked => some { s with cur := p, phase := .pointed }
    | _ => none
  | .grant p => match s.phase with
    | .pointed => if p = s.cur then some { s with writer := upd s.writer p true, phase := .idle }
      else none
    | _ => none
  | _ => none

/-- Strengthened invariant: during the revoked/pointed phases nobody holds the writer role. -/
def RTGInv (s : AState P) : Prop :=
  OnlyCurrentLogicWrites s ∧
    (match s.phase with
     | .revoked => ∀ q, s.writer q = false
     | .pointed => ∀ q, s.writer q = false
     | _ => True)

theorem stepRTG_inv (s : AState P) (e : Ev P) (s' : AState P) (hI : RTGInv s)
    (h : stepRTG s e = some s') : RTGInv s' := by
  obtain ⟨hO, hP⟩ := hI
  cases e with
  | write p =>
    simp only [stepRTG] at h
    split at h
    · simp at h; subst h; exact ⟨hO, hP⟩
    · simp at h
  | revoke p =>
    simp only [stepRTG] at h
    split at h
    · rename_i hph
      split at h
      · rename_i hpc
        simp only [Option.some.injEq] at h
        subst h
        have hall : ∀ q, upd s.writer p false q = false := by
          intro q
          by_cases hq : q = p
          · simp [hq]
          · simp only [upd, hq, if_false]
            cases hw : s.writer q
            · rfl
            · exact absurd (hpc ▸ hO q hw) hq
        refine ⟨fun q hq => ?_, hall⟩
        have hq' : upd s.writer p false q = true := hq
        rw [hall q] at hq'; cases hq'
      · simp at h
    · simp at h
  | point p =>
    simp only [stepRTG] at h
    split at h
    · rename_i hph
      simp only [Option.some.injEq] at h
      subst h
      rw [hph] at hP
      have hall : ∀ q, s.writer q = false := hP
      exact ⟨fun q hq => (by rw [hall q] at hq; cases hq), hall⟩
    · simp at h
  | grant p =>
    simp only [stepRTG] at h
    split at h
    · rename_i hph
      split at h
      · rename_i hpc
        simp only [Option.some.injEq] at h
        subst h
        rw [hph] at hP
        have hall : ∀ q, s.writer q = false := hP
        refine ⟨fun q hq => ?_, trivial⟩
        by_cases hqp : q = p
        · exact hqp.trans hpc
        · simp only [upd, hqp, if_false] at hq; rw [hall q] at hq; cases hq
      · simp at h
    · simp at h
  | transfer _ => simp [stepRTG] at h

/-- (4c) Revoke-then-grant: every state reachable by any interleaving of writes with the
three-step procedure (including every intermediate state) satisfies `OnlyCurrentLogicWrites`. -/
theorem revoke_then_grant_safe (s0 : AState P) (h0 : RTGInv s0)
    (tr : List (Ev P)) (s : AState P) (h : exec stepRTG s0 tr = some s) :
    OnlyCurrentLogicWrites s :=
  (exec_preserves stepRTG RTGInv stepRTG_inv tr s0 s h0 h).1

theorem init_rtg_inv (p : P) : RTGInv (init p) := ⟨init_inv p, trivial⟩

theorem rtg_write_only_current (s0 : AState P) (h0 : RTGInv s0)
    (tr : List (Ev P)) (s : AState P) (h : exec stepRTG s0 tr = some s) (p : P)
    (hw : (stepRTG s (.write p)).isSome) : p = s.cur := by
  have hI := revoke_then_grant_safe s0 h0 tr s h
  simp only [stepRTG] at hw
  split at hw
  · rename_i hp; exact hI p hp
  · simp at hw

/-- The safe procedure does complete an upgrade: from `init old`, the trace
`revoke old; point new; grant new` makes `new` the current, sole writer. -/
theorem rtg_completes (old new : P) :
    ∃ s, exec stepRTG (init old) [.revoke old, .point new, .grant new] = some s ∧
      s.cur = new ∧ s.writer new = true := by
  refine ⟨⟨new, upd (upd (init old).writer old false) new true, .idle⟩, ?_, rfl, by simp⟩
  simp [exec, stepRTG, init]

end Upgrades.Authority

/-!
# (T5) Authority closure: who can (transitively) change whom

`can y z` means component `y` may replace component `z` (or re-point the pointer that
designates `z`). A principal that may replace `z` controls `z`'s behaviour, so it acquires
every authority of `z`.

Operational semantics: a *takeover run* is a list of replacement actions `(y, z)`; action
`(y, z)` is enabled iff `y` is already controlled and `can y z`; it adds `z` to the
controlled set.

* `changers_eq_closure`: `y` can transitively change `X` (some enabled run starting from
  `{y}` ends controlling `X`) iff `RTC can y X` (reflexive-transitive closure).
* `escalation`: if every middleware can change its envoy, every envoy can change the
  registry, and the registry controls every binding, then every middleware can transitively
  change every getter/setter binding.
* `closure_bounded`: a backward-closed set bounds the changers of each of its members.
* `bounded_closure`: in the architecture policy where registry replacement is reserved to the
  admin role, the changers of any binding are exactly `{admin, registry, binding}`,
  whatever the middleware/envoy edges are.
-/
namespace Upgrades.Closure

/-- Reflexive-transitive closure. -/
inductive RTC {α : Type} (R : α → α → Prop) : α → α → Prop
  | refl (a : α) : RTC R a a
  | tail {a b c : α} : RTC R a b → R b c → RTC R a c

theorem RTC.single {α : Type} {R : α → α → Prop} {a b : α} (h : R a b) : RTC R a b :=
  .tail (.refl a) h

theorem RTC.trans {α : Type} {R : α → α → Prop} {a b c : α} (h1 : RTC R a b) (h2 : RTC R b c) :
    RTC R a c := by
  induction h2 with
  | refl => exact h1
  | tail _ hbc ih => exact .tail ih hbc

variable {α : Type}

/-- Controlled set after a takeover run. -/
def after (C : α → Prop) : List (α × α) → α → Prop
  | [] => C
  | (_, z) :: r => after (fun x => C x ∨ x = z) r

/-- Every action of the run is enabled when it is taken. -/
def Enabled (can : α → α → Prop) (C : α → Prop) : List (α × α) → Prop
  | [] => True
  | (y, z) :: r => C y ∧ can y z ∧ Enabled can (fun x => C x ∨ x = z) r

/-- `y` can transitively change `X`. -/
def Changes (can : α → α → Prop) (y X : α) : Prop :=
  ∃ r, Enabled can (· = y) r ∧ after (· = y) r X

theorem after_append (C : α → Prop) : ∀ (r1 r2 : List (α × α)),
    after C (r1 ++ r2) = after (after C r1) r2
  | [], _ => rfl
  | (_, _) :: r1, r2 => after_append _ r1 r2

theorem enabled_append (can : α → α → Prop) : ∀ (C : α → Prop) (r1 r2 : List (α × α)),
    Enabled can C r1 → Enabled can (after C r1) r2 → Enabled can C (r1 ++ r2)
  | _, [], _, _, h2 => h2
  | _, (_, _) :: r1, r2, ⟨h1, h2, h3⟩, h4 => ⟨h1, h2, enabled_append can _ r1 r2 h3 h4⟩

theorem after_mono : ∀ (C D : α → Prop) (r : List (α × α)), (∀ x, C x → D x) →
    ∀ x, after C r x → after D r x
  | _, _, [], h, x, hx => h x hx
  | C, D, (_, z) :: r, h, x, hx =>
    after_mono (fun x => C x ∨ x = z) (fun x => D x ∨ x = z) r
      (fun x hx => hx.elim (fun c => .inl (h x c)) .inr) x hx

theorem after_base : ∀ (C : α → Prop) (r : List (α × α)) (x : α), C x → after C r x
  | _, [], _, h => h
  | _, (_, _) :: r, x, h => after_base _ r x (.inl h)

/-- Soundness: everything controlled after an enabled run from a set inside the closure of
`p` is inside the closure of `p`. -/
theorem sound (can : α → α → Prop) (p : α) : ∀ (r : List (α × α)) (C : α → Prop),
    (∀ c, C c → RTC can p c) → Enabled can C r → ∀ x, after C r x → RTC can p x
  | [], _, hC, _, x, hx => hC x hx
  | (y, z) :: r, C, hC, ⟨hy, hyz, hr⟩, x, hx =>
    sound can p r _ (fun c hc => hc.elim (hC c) (fun e => e ▸ .tail (hC y hy) hyz)) hr x hx

/-- (T5a) The components able to transitively change `X` are exactly those related to `X` by
the reflexive-transitive closure of `can`. -/
theorem changers_eq_closure (can : α → α → Prop) (y X : α) :
    Changes can y X ↔ RTC can y X := by
  constructor
  · rintro ⟨r, hen, haf⟩
    exact sound can y r (· = y) (fun c hc => hc ▸ .refl c) hen X haf
  · intro h
    induction h with
    | refl => exact ⟨[], trivial, rfl⟩
    | @tail b c _ hbc ih =>
      obtain ⟨r, hen, haf⟩ := ih
      refine ⟨r ++ [(b, c)], enabled_append can _ r _ hen ⟨haf, hbc, trivial⟩, ?_⟩
      rw [after_append]
      exact .inr rfl

/-- (T5b) Backward-closed sets bound the closure. -/
theorem closure_bounded (can : α → α → Prop) (S : α → Prop)
    (hS : ∀ y z, can y z → S z → S y) {y X : α} (h : RTC can y X) (hX : S X) : S y := by
  induction h with
  | refl => exact hX
  | tail _ hbc ih => exact ih (hS _ _ hbc hX)

/-! ### Architecture authority graph -/

inductive Node (M E Nm : Type) where
  | admin
  | mw (i : M)
  | envoy (j : E)
  | registry
  | binding (n : Nm)

structure Policy (M E : Type) where
  envOf : M → E
  mwMayReplaceEnvoy : Bool
  envoyMayReplaceRegistry : Bool

variable {M E Nm : Type}

/-- Who may change whom. The admin may replace middleware, envoys and the registry; a
middleware may replace its own envoy (if the policy says so); an envoy may replace the
registry (if the policy says so); whoever controls the registry controls every binding. -/
def canArch (π : Policy M E) : Node M E Nm → Node M E Nm → Prop
  | .admin, .registry => True
  | .admin, .envoy _ => True
  | .admin, .mw _ => True
  | .mw i, .envoy j => π.mwMayReplaceEnvoy = true ∧ j = π.envOf i
  | .envoy _, .registry => π.envoyMayReplaceRegistry = true
  | .registry, .binding _ => True
  | _, _ => False

/-- (T5c) Escalation, for any authority relation containing the three edges. -/
theorem escalation (can : Node M E Nm → Node M E Nm → Prop) (envOf : M → E)
    (h1 : ∀ i, can (.mw i) (.envoy (envOf i))) (h2 : ∀ j, can (.envoy j) .registry)
    (h3 : ∀ n, can .registry (.binding n)) (i : M) (n : Nm) :
    RTC can (.mw i) (.binding n) ∧ Changes can (.mw i) (.binding n) := by
  have h : RTC can (.mw i) (.binding n) :=
    .tail (.tail (.single (h1 i)) (h2 _)) (h3 n)
  exact ⟨h, (changers_eq_closure can _ _).2 h⟩

/-- (T5c') Escalation in the architecture policy where middleware may replace its envoy and
envoys may replace the registry: every middleware can transitively change every binding. -/
theorem escalation_policy (π : Policy M E) (hm : π.mwMayReplaceEnvoy = true)
    (he : π.envoyMayReplaceRegistry = true) (i : M) (n : Nm) :
    Changes (canArch π) (.mw i) (.binding n) :=
  (escalation (canArch π) π.envOf (fun _ => ⟨hm, rfl⟩) (fun _ => he) (fun _ => trivial) i n).2

/-- (T5d) Bounded closure: if registry replacement is reserved to the admin role, then for
every binding `n`, the set of components that can transitively change it is exactly
`{admin, registry, binding n}` — independent of the middleware/envoy policy. -/
theorem bounded_closure (π : Policy M E) (he : π.envoyMayReplaceRegistry = false)
    (n : Nm) (y : Node M E Nm) :
    Changes (canArch π) y (.binding n) ↔
      (y = .admin ∨ y = .registry ∨ y = .binding n) := by
  rw [changers_eq_closure]
  constructor
  · intro h
    refine closure_bounded (canArch π) (fun x => x = .admin ∨ x = .registry ∨ x = .binding n)
      ?_ h (.inr (.inr rfl))
    intro a b hab hb
    rcases hb with rfl | rfl | rfl
    · cases a <;> simp [canArch] at hab
    · cases a <;> simp [canArch, he] at hab <;> simp
    · cases a <;> simp [canArch] at hab; simp
  · rintro (rfl | rfl | rfl)
    · exact .tail (.single (show canArch π .admin .registry from trivial))
        (show canArch π .registry (.binding n) from trivial)
    · exact .single (show canArch π .registry (.binding n) from trivial)
    · exact .refl _

/-- Corollary: under the bounded policy no middleware and no envoy can transitively change
any binding. -/
theorem bounded_no_mw_envoy (π : Policy M E) (he : π.envoyMayReplaceRegistry = false)
    (n : Nm) (i : M) (j : E) :
    ¬ Changes (canArch π) (.mw i) (.binding n) ∧ ¬ Changes (canArch π) (.envoy j) (.binding n) := by
  constructor
  · intro h; rcases (bounded_closure π he n _).1 h with h | h | h <;> cases h
  · intro h; rcases (bounded_closure π he n _).1 h with h | h | h <;> cases h

end Upgrades.Closure

/-!
# (T1) Flattening a nested map family into one key-value store

A *nested map family* assigns a value to every name `n` and argument tuple `xs` in a domain
`D` (names may have different arities; `D` is the union of all `(name, argument-tuple)`
domains). A *flat store* is a single map `K → V`. The flattening uses the key
`κ (n, xs) = H (enc (n, xs))`.

* `represent_iff_key_inj`: every nested family is represented by some flat store
  (`s (κ a) = f a` on `D`) iff `κ` is injective on `D`.
* `writes_commute_iff_key_inj`: a flat write at `κ a` acts on the nested view exactly as a
  nested point update at `a`, for all stores and values, iff `κ` is injective on `D`.
* `key_inj_iff`: `κ = H ∘ enc` is injective on `D` iff `enc` is injective on `D` and `H` is
  injective on the image `enc(D)` (the latter is the collision-resistance hypothesis).
* `flatten_faithful_iff`: combination of the two.
* `lp_injective`: a length-prefixed byte encoding is injective on all tuples of all arities.
* `packed_collision`, `packed_not_faithful`: the packed (concatenating) byte encoding has
  collisions, so for *every* `H` some nested family has no flat representation.
-/
namespace Upgrades.Flatten

open Upgrades

variable {α E K V : Type}

/-- Flat store `s` represents nested family `f` on `D` via key map `κ`. -/
def Represents (D : α → Prop) (κ : α → K) (f : α → V) (s : K → V) : Prop :=
  ∀ a, D a → s (κ a) = f a

/-- Nested view of a flat store. -/
def view (κ : α → K) (s : K → V) : α → V := fun a => s (κ a)

/-- (T1a) Representability iff injectivity of the derived key on the domain. -/
theorem represent_iff_key_inj (D : α → Prop) (κ : α → K) (v0 v1 : V) (hv : v0 ≠ v1) :
    (∀ f : α → V, ∃ s : K → V, Represents D κ f s) ↔ InjOn D κ := by
  classical
  constructor
  · intro h a b ha hb hk
    apply Classical.byContradiction
    intro hab
    obtain ⟨s, hs⟩ := h (fun x => if x = a then v1 else v0)
    have e1 : s (κ a) = v1 := by simpa using hs a ha
    have hba : b ≠ a := fun e => hab e.symm
    have e2 : s (κ b) = v0 := by simpa [hba] using hs b hb
    rw [hk] at e1
    exact hv (e2.symm.trans e1)
  · intro hinj f
    refine ⟨fun k => if h : ∃ a, D a ∧ κ a = k then f (Classical.choose h) else v0, ?_⟩
    intro a ha
    have hex : ∃ b, D b ∧ κ b = κ a := ⟨a, ha, rfl⟩
    have hc := Classical.choose_spec hex
    have heq : Classical.choose hex = a := hinj _ _ hc.1 ha hc.2
    show (if h : ∃ b, D b ∧ κ b = κ a then f (Classical.choose h) else v0) = f a
    rw [dif_pos hex, heq]

/-- (T1b) Flat writes commute with nested point updates on `D` iff the derived key is
injective on `D`. -/
theorem writes_commute_iff_key_inj [DecidableEq α] [DecidableEq K] (D : α → Prop) (κ : α → K)
    (v0 v1 : V) (hv : v0 ≠ v1) :
    (∀ (s : K → V) a v b, D a → D b → view κ (upd s (κ a) v) b = upd (view κ s) a v b) ↔
      InjOn D κ := by
  constructor
  · intro h a b ha hb hk
    apply Classical.byContradiction
    intro hab
    have e := h (fun _ => v0) a v1 b ha hb
    have hba : b ≠ a := fun e => hab e.symm
    simp [view, upd, hk, hba] at e
    exact hv e.symm
  · intro hinj s a v b ha hb
    by_cases hab : b = a
    · subst hab; simp [view]
    · have hk : κ b ≠ κ a := fun e => hab (hinj _ _ hb ha e)
      simp [view, upd, hk, hab]

/-- (T1c) Composite injectivity: `H ∘ enc` is injective on `D` iff `enc` is injective on `D`
and `H` is injective on the image of `D` under `enc`. -/
theorem key_inj_iff (D : α → Prop) (enc : α → E) (H : E → K) :
    InjOn D (fun a => H (enc a)) ↔
      InjOn D enc ∧ InjOn (fun e => ∃ a, D a ∧ enc a = e) H := by
  constructor
  · intro h
    refine ⟨fun a b ha hb he => h a b ha hb (by simp [he]), ?_⟩
    rintro _ _ ⟨a, ha, rfl⟩ ⟨b, hb, rfl⟩ hH
    rw [h a b ha hb hH]
  · rintro ⟨he, hH⟩ a b ha hb hk
    exact he a b ha hb (hH _ _ ⟨a, ha, rfl⟩ ⟨b, hb, rfl⟩ hk)

/-- (T1) Flattening theorem: every nested family indexed by `D` is faithfully represented by
the single store keyed by `H (enc ·)` iff `enc` is injective on `D` and `H` is injective on
`enc(D)`. -/
theorem flatten_faithful_iff (D : α → Prop) (enc : α → E) (H : E → K) (v0 v1 : V)
    (hv : v0 ≠ v1) :
    (∀ f : α → V, ∃ s : K → V, Represents D (fun a => H (enc a)) f s) ↔
      InjOn D enc ∧ InjOn (fun e => ∃ a, D a ∧ enc a = e) H :=
  (represent_iff_key_inj D _ v0 v1 hv).trans (key_inj_iff D enc H)

/-! ### Byte-string encodings -/

/-- Bytes are modelled as natural numbers below 256 in a list; the results below do not need
the bound, so `Byte := Nat`. -/
abbrev Byte := Nat
abbrev Bytes := List Byte

/-- Length-prefixed encoding of a tuple of byte strings: each component is preceded by its
length. -/
def lp : List Bytes → Bytes
  | [] => []
  | b :: bs => b.length :: (b ++ lp bs)

theorem lp_injective : ∀ x y : List Bytes, lp x = lp y → x = y
  | [], [], _ => rfl
  | [], _ :: _, h => by simp [lp] at h
  | _ :: _, [], h => by simp [lp] at h
  | b :: bs, c :: cs, h => by
    simp only [lp, List.cons.injEq] at h
    obtain ⟨hl, h2⟩ := h
    have hbc := List.append_inj h2 hl
    rw [hbc.1, lp_injective bs cs hbc.2]

/-- Length-prefixed encoding of `(name, k1, ..., kn)`: injective on the union of all
domains, of every arity. -/
def encLP (a : Bytes × List Bytes) : Bytes := lp (a.1 :: a.2)

theorem encLP_injective (D : Bytes × List Bytes → Prop) : InjOn D encLP := by
  intro a b _ _ h
  have := lp_injective _ _ h
  simp only [List.cons.injEq] at this
  exact Prod.ext this.1 this.2

/-- With the length-prefixed encoding, flattening is faithful for any `H` that is injective
on the encoded image (collision-resistance hypothesis). -/
theorem encLP_faithful (D : Bytes × List Bytes → Prop) (H : Bytes → K)
    (hH : InjOn (fun e => ∃ a, D a ∧ encLP a = e) H) (f : Bytes × List Bytes → V) :
    ∃ s : K → V, Represents D (fun a => H (encLP a)) f s := by
  by_cases hV : ∃ v0 v1 : V, v0 ≠ v1
  · obtain ⟨v0, v1, hv⟩ := hV
    exact (flatten_faithful_iff D encLP H v0 v1 hv).2 ⟨encLP_injective D, hH⟩ f
  · refine ⟨fun _ => f ([], []), fun a _ => ?_⟩
    apply Classical.byContradiction
    intro hne
    exact hV ⟨_, _, hne⟩

/-- Packed encoding: concatenation of the name and all argument bytes, no lengths. -/
def encPacked (a : Bytes × List Bytes) : Bytes := a.1 ++ a.2.flatten

/-- (T1d) Packed encoding collides: `("ab", ["c"])` and `("a", ["bc"])` (as byte strings
`[1,2]`,`[3]` and `[1]`,`[2,3]`) are distinct but encode identically. -/
theorem packed_collision :
    (([1, 2], [[3]]) : Bytes × List Bytes) ≠ ([1], [[2, 3]]) ∧
      encPacked ([1, 2], [[3]]) = encPacked ([1], [[2, 3]]) := by
  refine ⟨by decide, rfl⟩

/-- (T1e) With the packed encoding, for every key function `H` and every value type with two
distinct values, some nested family over a domain containing the two colliding entries has
no faithful flat representation. -/
theorem packed_not_faithful (H : Bytes → K) (v0 v1 : V) (hv : v0 ≠ v1)
    (D : Bytes × List Bytes → Prop) (h1 : D ([1, 2], [[3]])) (h2 : D ([1], [[2, 3]])) :
    ¬ ∀ f : Bytes × List Bytes → V, ∃ s : K → V,
        Represents D (fun a => H (encPacked a)) f s := by
  intro h
  have hinj := (represent_iff_key_inj D _ v0 v1 hv).1 h
  exact packed_collision.1 (hinj _ _ h1 h2 (congrArg H packed_collision.2))

end Upgrades.Flatten

/-!
# (3) Layout safety

*Positional layout*: a version declares an ordered list of fields; field `f` lives at slot
`slot decls f` (its offset). *Typed key-value layout*: field `f` lives at key `H f`,
independent of the declaration list.

Theorems:
* `kv_slot_version_independent`, `kv_insert_preserves`, `kv_no_collision`: in key-value
  storage every field keeps its key in every version, and distinct fields never share a key
  (given `H` injective on the field domain).
* `positional_shift`: inserting a field before an existing one moves that field's slot.
* `positional_insert_collides`: the inserted field takes over the slot of the field that
  previously sat at the insertion point, so the new version reads the old field's data as the
  new field (general statement), with `positional_counterexample` as a concrete instance.
* `positional_append_preserves`: appending at the end is safe for positional layouts.
-/
namespace Upgrades.Layout

open Upgrades

section Positional
variable {F : Type} [DecidableEq F]

/-- Offset of `f` in a positional declaration list (length if absent). -/
def slot : List F → F → Nat
  | [], _ => 0
  | g :: l, f => if f = g then 0 else slot l f + 1

def insertAt (l : List F) (j : Nat) (f : F) : List F := l.take j ++ f :: l.drop j

def readPos {V : Type} (decls : List F) (mem : Nat → V) (f : F) : V := mem (slot decls f)

theorem slot_cons_self (f : F) (l : List F) : slot (f :: l) f = 0 := by simp [slot]

theorem slot_cons_ne {f g : F} (l : List F) (h : f ≠ g) : slot (g :: l) f = slot l f + 1 := by
  simp [slot, h]

theorem slot_append (l1 l2 : List F) (f : F) (h : f ∉ l1) :
    slot (l1 ++ l2) f = l1.length + slot l2 f := by
  induction l1 with
  | nil => simp
  | cons g l1 ih =>
    have hfg : f ≠ g := fun e => h (e ▸ List.mem_cons_self _ _)
    have hf1 : f ∉ l1 := fun m => h (List.mem_cons_of_mem _ m)
    simp only [List.cons_append, slot_cons_ne _ hfg, ih hf1, List.length_cons]
    omega

/-- Appending fields at the end keeps every existing positional slot. -/
theorem positional_append_preserves (l l2 : List F) (g : F) (hg : g ∈ l) :
    slot (l ++ l2) g = slot l g := by
  induction l with
  | nil => simp at hg
  | cons h t ih =>
    by_cases e : g = h
    · subst e; simp [slot]
    · have : g ∈ t := by simpa [e] using hg
      simp [slot, e, ih this]

/-- (3a) Inserting `f` at position `j` shifts every field not in the prefix by one slot. -/
theorem positional_shift (l : List F) (j : Nat) (f g : F) (hg : g ∉ l.take j) (hgf : g ≠ f) :
    slot (insertAt l j f) g = slot l g + 1 := by
  have h := slot_append (l.take j) (l.drop j) g hg
  rw [List.take_append_drop] at h
  rw [insertAt, slot_append _ _ _ hg, slot_cons_ne _ hgf, h]
  omega

/-- (3b) Positional collision: inserting a new field `f` before the existing field `l[j]`
makes the new version's `f` occupy exactly the slot where the old version stored `l[j]`,
while `l[j]` itself moves. Hence the new version reads `l[j]`'s old data as `f`. -/
theorem positional_insert_collides (l : List F) (j : Nat) (hj : j < l.length) (f : F)
    (hf : f ∉ l.take j) (hfirst : l[j] ∉ l.take j) (hfg : f ≠ l[j]) :
    slot (insertAt l j f) f = slot l l[j] ∧
    slot (insertAt l j f) l[j] ≠ slot l l[j] ∧
    ∀ {V : Type} (mem : Nat → V), readPos (insertAt l j f) mem f = readPos l mem l[j] := by
  have hlen : (l.take j).length = j := by simp [List.length_take]; omega
  have hnew : slot (insertAt l j f) f = j := by
    rw [insertAt, slot_append _ _ _ hf, slot_cons_self, hlen, Nat.add_zero]
  have hold : slot l l[j] = j := by
    have h := slot_append (l.take j) (l.drop j) l[j] hfirst
    rw [List.take_append_drop] at h
    rw [h, List.drop_eq_getElem_cons hj, slot_cons_self, hlen, Nat.add_zero]
  refine ⟨by rw [hnew, hold], ?_, fun mem => by simp [readPos, hnew, hold]⟩
  rw [positional_shift l j f l[j] hfirst (Ne.symm hfg)]
  omega

end Positional

inductive Fld where
  | owner | fee | admin
  deriving DecidableEq, Repr

/-- (3c) Concrete counterexample: version 1 declares `[owner, fee]`; version 2 inserts `admin`
first. Version 2 reads `admin` from the slot holding version 1's `owner`, and `owner` from the
slot holding `fee`. -/
theorem positional_counterexample :
    let v1 := [Fld.owner, Fld.fee]
    let v2 := [Fld.admin, Fld.owner, Fld.fee]
    slot v2 Fld.admin = slot v1 Fld.owner ∧ slot v2 Fld.owner = slot v1 Fld.fee ∧
    ∀ {V : Type} (mem : Nat → V),
      readPos v2 mem Fld.admin = readPos v1 mem Fld.owner ∧
      readPos v2 mem Fld.owner = readPos v1 mem Fld.fee := by
  refine ⟨by decide, by decide, fun mem => ⟨rfl, rfl⟩⟩

/-! ### Typed key-value layout -/

section KV
variable {F : Type}

/-- Key of field `f` under a key-value layout: depends only on `f`, never on the declarations. -/
def kvSlot {K : Type} (H : F → K) (_decls : List F) (f : F) : K := H f

def readKV {K V : Type} (H : F → K) (decls : List F) (store : K → V) (f : F) : V :=
  store (kvSlot H decls f)

/-- (3d) Every field keeps its key in every version. -/
theorem kv_slot_version_independent {K : Type} (H : F → K) (l l' : List F) (f : F) :
    kvSlot H l f = kvSlot H l' f := rfl

theorem kv_insert_preserves {K : Type} (H : F → K) (l : List F) (j : Nat) (f g : F) :
    kvSlot H (insertAt l j f) g = kvSlot H l g := rfl

/-- (3e) Data written by any version is read unchanged by any other version. -/
theorem kv_read_version_independent {K V : Type} (H : F → K) (l l' : List F) (s : K → V)
    (f : F) : readKV H l' s f = readKV H l s f := rfl

/-- (3f) No layout collisions across versions: distinct fields in the domain have distinct
keys, in any pair of versions, given `H` injective on that domain. Fields carry their type
tag (e.g. `F = Ty × Name`), so this also excludes type confusion. -/
theorem kv_no_collision {K : Type} (H : F → K) (D : F → Prop) (hH : InjOn D H)
    (l l' : List F) (f g : F) (hf : D f) (hg : D g) (hne : f ≠ g) :
    kvSlot H l f ≠ kvSlot H l' g :=
  fun e => hne (hH f g hf hg e)

/-- The concrete insertion of (3c) is harmless under a key-value layout. -/
theorem kv_counterexample_safe {K : Type} (H : Fld → K) :
    kvSlot H [Fld.admin, Fld.owner, Fld.fee] Fld.owner = kvSlot H [Fld.owner, Fld.fee] Fld.owner :=
  rfl

end KV

end Upgrades.Layout

/-!
# (T4) Resolvability under registry replacement and envoy re-pointing

`AllNamesResolvable s`: every name used by every middleware resolves, through that
middleware's current envoy and that envoy's current registry, to a live component.

The *protocol* `Allowed s e` constrains only routing steps:
* `deploy a c` only at an empty address; a middleware may be deployed only if its envoy's
  registry already binds all its names to live components;
* `regSet r n a` only to a live `a`;
* `regDel r n` only if no middleware routed to `r` uses `n`;
* `envoyPoint e r` only if `r` binds, to live components, every name used by every
  middleware currently pointing to `e` (`Covers`);
* `mwPoint m e` only if the registry of `e` covers `m`;
* `grant`, `revoke`, `call`: always allowed.

Theorems:
* `allowed_preserves`, `resolvable_under_protocol`: protocol traces preserve resolvability.
* `envoyPoint_iff`, `mwPoint_iff`: the covering condition is necessary and sufficient
  (minimal ordering condition: every entry of the new registry used through `e` must be
  written before `e` is re-pointed).
* `registry_replacement`: the complete procedure "deploy new registry; write its entries;
  re-point the envoy" is a protocol trace and ends resolvable with the envoy on the new
  registry.
* `repoint_missing_name_breaks`, `counterexample_repoint_before_populate`.
-/
namespace Upgrades.Resolve

set_option linter.unusedSectionVars false

open Upgrades Upgrades.Arch

variable {Ad K V A Nm : Type} [DecidableEq Ad] [DecidableEq K] [DecidableEq Nm]

def Live (s : Sys Ad K V A Nm) (a : Ad) : Prop := (s.kind a).isLive = true

def UsesName (s : Sys Ad K V A Nm) (m : Ad) (n : Nm) : Prop :=
  ∃ ns, s.kind m = .middleware ns ∧ n ∈ ns

def AllNamesResolvable (s : Sys Ad K V A Nm) : Prop :=
  ∀ m n, UsesName s m n → ∃ a, resolve s m n = some a ∧ Live s a

/-- Registry `r` binds every name used by middleware `m` to a live component. -/
def Covers (s : Sys Ad K V A Nm) (r m : Ad) : Prop :=
  ∀ n, UsesName s m n → ∃ a, s.table r n = some a ∧ Live s a

def Comp.isMw {K V A Nm : Type} : Comp K V A Nm → Bool
  | .middleware _ => true
  | _ => false

def Allowed (s : Sys Ad K V A Nm) : Step Ad K V A Nm → Prop
  | .deploy a c => s.kind a = .empty ∧
      ∀ ns, c = .middleware ns → ∀ n ∈ ns, ∃ b, s.table (s.envReg (s.mwEnv a)) n = some b ∧ Live s b
  | .regSet _ _ a => Live s a
  | .regDel r n => ∀ m, UsesName s m n → s.envReg (s.mwEnv m) ≠ r
  | .envoyPoint e r => ∀ m, s.mwEnv m = e → Covers s r m
  | .mwPoint m e => Covers s (s.envReg e) m
  | .grant _ => True
  | .revoke _ => True
  | .call _ _ _ => True

/-- A protocol trace: every step is allowed in the state where it occurs. -/
def Valid : Sys Ad K V A Nm → List (Step Ad K V A Nm) → Prop
  | _, [] => True
  | s, e :: tr => Allowed s e ∧ Valid (step s e) tr

theorem callEffect_routing (s : Sys Ad K V A Nm) (m : Ad) (n : Nm) (x : A) :
    (callEffect s m n x).kind = s.kind ∧ (callEffect s m n x).table = s.table ∧
    (callEffect s m n x).envReg = s.envReg ∧ (callEffect s m n x).mwEnv = s.mwEnv := by
  unfold callEffect
  split
  · exact ⟨rfl, rfl, rfl, rfl⟩
  · split
    · split <;> exact ⟨rfl, rfl, rfl, rfl⟩
    · exact ⟨rfl, rfl, rfl, rfl⟩

/-- Resolvability depends only on routing (kind, table, envReg, mwEnv). -/
theorem resolvable_congr (s t : Sys Ad K V A Nm) (h1 : t.kind = s.kind) (h2 : t.table = s.table)
    (h3 : t.envReg = s.envReg) (h4 : t.mwEnv = s.mwEnv) :
    AllNamesResolvable s → AllNamesResolvable t := by
  intro h m n hu
  have hu' : UsesName s m n := by simpa [UsesName, h1] using hu
  obtain ⟨a, hr, hl⟩ := h m n hu'
  exact ⟨a, by simpa [resolve, h2, h3, h4] using hr, by simpa [Live, h1] using hl⟩

/-- Every allowed step preserves resolvability. -/
theorem allowed_preserves (s : Sys Ad K V A Nm) (e : Step Ad K V A Nm)
    (hs : AllNamesResolvable s) (ha : Allowed s e) : AllNamesResolvable (step s e) := by
  cases e with
  | deploy a c =>
    obtain ⟨hemp, hmw⟩ := ha
    have hlive : ∀ b, Live s b → Live (step s (.deploy a c)) b ∧ b ≠ a := by
      intro b hb
      have hba : b ≠ a := fun h => by subst h; simp [Live, hemp, Comp.isLive] at hb
      exact ⟨by simpa [Live, step, upd_ne _ _ hba] using hb, hba⟩
    intro m n hu
    by_cases hma : m = a
    · subst hma
      obtain ⟨ns, hk, hn⟩ := hu
      simp [step] at hk
      obtain ⟨b, hb, hl⟩ := hmw ns hk n hn
      exact ⟨b, by simpa [resolve, step] using hb, (hlive b hl).1⟩
    · have hu' : UsesName s m n := by
        obtain ⟨ns, hk, hn⟩ := hu
        exact ⟨ns, by simpa [step, upd_ne _ _ hma] using hk, hn⟩
      obtain ⟨b, hr, hl⟩ := hs m n hu'
      exact ⟨b, by simpa [resolve, step] using hr, (hlive b hl).1⟩
  | regSet r n0 a0 =>
    intro m n hu
    obtain ⟨b, hr, hl⟩ := hs m n hu
    simp only [resolve, step]
    by_cases hreg : s.envReg (s.mwEnv m) = r
    · by_cases hn : n = n0
      · exact ⟨a0, by simp [hreg, hn], ha⟩
      · refine ⟨b, ?_, hl⟩
        simp only [resolve] at hr
        simp [hreg, upd, hn] at hr ⊢
        exact hr
    · exact ⟨b, by simpa [upd, hreg] using hr, hl⟩
  | regDel r n0 =>
    intro m n hu
    obtain ⟨b, hr, hl⟩ := hs m n hu
    refine ⟨b, ?_, hl⟩
    simp only [resolve, step] at hr ⊢
    by_cases hreg : s.envReg (s.mwEnv m) = r
    · have hn : n ≠ n0 := fun h => ha m (h ▸ hu) hreg
      simp [hreg, upd, hn] at hr ⊢
      exact hr
    · simpa [upd, hreg] using hr
  | envoyPoint e r =>
    intro m n hu
    by_cases hme : s.mwEnv m = e
    · obtain ⟨a, ht, hl⟩ := ha m hme n hu
      exact ⟨a, by simp [resolve, step, hme, ht], hl⟩
    · obtain ⟨b, hr, hl⟩ := hs m n hu
      exact ⟨b, by simpa [resolve, step, upd, hme] using hr, hl⟩
  | mwPoint m0 e =>
    intro m n hu
    by_cases hm : m = m0
    · subst hm
      obtain ⟨a, ht, hl⟩ := ha n hu
      exact ⟨a, by simp [resolve, step, ht], hl⟩
    · obtain ⟨b, hr, hl⟩ := hs m n hu
      exact ⟨b, by simpa [resolve, step, upd, hm] using hr, hl⟩
  | grant a => exact resolvable_congr s _ rfl rfl rfl rfl hs
  | revoke a => exact resolvable_congr s _ rfl rfl rfl rfl hs
  | call m n x =>
    obtain ⟨h1, h2, h3, h4⟩ := callEffect_routing s m n x
    exact resolvable_congr s _ h1 h2 h3 h4 hs

/-- (T4a) Every trace executed per the protocol, from a resolvable state, ends (and passes
only through) resolvable states. -/
theorem resolvable_under_protocol :
    ∀ (tr : List (Step Ad K V A Nm)) (s : Sys Ad K V A Nm),
      AllNamesResolvable s → Valid s tr → AllNamesResolvable (run s tr) := by
  intro tr
  induction tr with
  | nil => intro s hs _; exact hs
  | cons e tr ih =>
    intro s hs hv
    exact ih (step s e) (allowed_preserves s e hs hv.1) hv.2

/-- (T4b) Minimal condition for envoy re-pointing: from a resolvable state, re-pointing
envoy `e` to registry `r` yields a resolvable state iff `r` covers every middleware
currently pointing to `e`. -/
theorem envoyPoint_iff (s : Sys Ad K V A Nm) (e r : Ad) (hs : AllNamesResolvable s) :
    AllNamesResolvable (step s (.envoyPoint e r)) ↔ ∀ m, s.mwEnv m = e → Covers s r m := by
  constructor
  · intro h m hme n hu
    obtain ⟨a, hr, hl⟩ := h m n (by simpa [UsesName, step] using hu)
    exact ⟨a, by simpa [resolve, step, hme] using hr, by simpa [Live, step] using hl⟩
  · intro hc
    exact allowed_preserves s _ hs hc

/-- (T4c) Minimal condition for middleware re-pointing. -/
theorem mwPoint_iff (s : Sys Ad K V A Nm) (m e : Ad) (hs : AllNamesResolvable s) :
    AllNamesResolvable (step s (.mwPoint m e)) ↔ Covers s (s.envReg e) m := by
  constructor
  · intro h n hu
    obtain ⟨a, hr, hl⟩ := h m n (by simpa [UsesName, step] using hu)
    exact ⟨a, by simpa [resolve, step] using hr, by simpa [Live, step] using hl⟩
  · intro hc
    exact allowed_preserves s _ hs hc

/-- (T4d) Re-pointing an envoy to a registry missing a name used through it breaks
resolution of that name, in general. -/
theorem repoint_missing_name_breaks (s : Sys Ad K V A Nm) (e r m : Ad) (n : Nm)
    (hme : s.mwEnv m = e) (hu : UsesName s m n) (hmiss : s.table r n = none) :
    resolve (step s (.envoyPoint e r)) m n = none ∧
      ¬ AllNamesResolvable (step s (.envoyPoint e r)) := by
  have hres : resolve (step s (.envoyPoint e r)) m n = none := by
    simp [resolve, step, hme, hmiss]
  refine ⟨hres, fun h => ?_⟩
  obtain ⟨a, hr, _⟩ := h m n (by simpa [UsesName, step] using hu)
  rw [hres] at hr; cases hr

/-! ### The registry replacement procedure is a protocol trace -/

def regSets (r : Ad) (es : List (Nm × Ad)) : List (Step Ad K V A Nm) :=
  es.map fun p => .regSet r p.1 p.2

theorem regSets_routing (r : Ad) :
    ∀ (es : List (Nm × Ad)) (s : Sys Ad K V A Nm),
      (run s (regSets r es)).kind = s.kind ∧ (run s (regSets r es)).envReg = s.envReg ∧
      (run s (regSets r es)).mwEnv = s.mwEnv ∧
      ∀ r', r' ≠ r → (run s (regSets r es)).table r' = s.table r'
  | [], s => ⟨rfl, rfl, rfl, fun _ _ => rfl⟩
  | (n, a) :: es, s => by
    obtain ⟨h1, h2, h3, h4⟩ := regSets_routing r es (step s (.regSet r n a))
    refine ⟨h1, h2, h3, fun r' hr' => ?_⟩
    rw [show regSets r ((n, a) :: es) = Step.regSet r n a :: regSets r es from rfl, run_cons,
      h4 r' hr']
    simp [step, upd, hr']

theorem regSets_frame (r : Ad) (n : Nm) :
    ∀ (es : List (Nm × Ad)) (s : Sys Ad K V A Nm), n ∉ es.map Prod.fst →
      (run s (regSets r es)).table r n = s.table r n
  | [], _, _ => rfl
  | (n0, a0) :: es, s, h => by
    have hn : n ≠ n0 := fun e => h (by simp [e])
    have hes : n ∉ es.map Prod.fst := fun e => h (List.mem_cons_of_mem _ e)
    rw [show regSets r ((n0, a0) :: es) = Step.regSet r n0 a0 :: regSets r es from rfl, run_cons,
      regSets_frame r n es _ hes]
    simp [step, upd, hn]

theorem regSets_table (r : Ad) (n : Nm) :
    ∀ (es : List (Nm × Ad)) (s : Sys Ad K V A Nm), n ∈ es.map Prod.fst →
      ∃ a, (n, a) ∈ es ∧ (run s (regSets r es)).table r n = some a
  | [], _, h => by simp at h
  | (n0, a0) :: es, s, h => by
    rw [show regSets r ((n0, a0) :: es) = Step.regSet r n0 a0 :: regSets r es from rfl, run_cons]
    by_cases hes : n ∈ es.map Prod.fst
    · obtain ⟨a, ha, ht⟩ := regSets_table r n es _ hes
      exact ⟨a, List.mem_cons_of_mem _ ha, ht⟩
    · have hn : n = n0 := by
        simp only [List.map_cons, List.mem_cons] at h
        rcases h with h | h
        · exact h
        · exact absurd h hes
      subst hn
      refine ⟨a0, List.mem_cons_self _ _, ?_⟩
      rw [regSets_frame r n es _ hes]
      simp [step]

theorem regSets_valid (r : Ad) :
    ∀ (es : List (Nm × Ad)) (s : Sys Ad K V A Nm), (∀ p ∈ es, Live s p.2) →
      Valid s (regSets r es)
  | [], _, _ => trivial
  | (n, a) :: es, s, h =>
    ⟨h (n, a) (List.mem_cons_self _ _),
      regSets_valid r es _ (fun p hp => by
        have := h p (List.mem_cons_of_mem _ hp); simpa [Live, step] using this)⟩

theorem valid_append :
    ∀ (t1 t2 : List (Step Ad K V A Nm)) (s : Sys Ad K V A Nm),
      Valid s t1 → Valid (run s t1) t2 → Valid s (t1 ++ t2)
  | [], _, _, _, h2 => h2
  | e :: t1, t2, s, h1, h2 => ⟨h1.1, valid_append t1 t2 (step s e) h1.2 h2⟩

theorem run_append (t1 t2 : List (Step Ad K V A Nm)) (s : Sys Ad K V A Nm) :
    run s (t1 ++ t2) = run (run s t1) t2 := by simp [run, List.foldl_append]

/-- (T4e) Registry replacement procedure. From a resolvable state, with `r'` an empty
address, entries `es` binding only live components, and `es` naming every name used by every
middleware routed through envoy `e`, the trace
`deploy r' registry; regSet r' es…; envoyPoint e r'` is a protocol trace; it ends resolvable,
with `e` pointing to `r'`. -/
theorem registry_replacement (s : Sys Ad K V A Nm) (e r' : Ad) (es : List (Nm × Ad))
    (hs : AllNamesResolvable s) (hfresh : s.kind r' = .empty)
    (hlive : ∀ p ∈ es, Live s p.2)
    (hcov : ∀ m n, s.mwEnv m = e → UsesName s m n → n ∈ es.map Prod.fst) :
    let tr := (Step.deploy r' .registry :: regSets r' es) ++ [Step.envoyPoint e r']
    Valid s tr ∧ AllNamesResolvable (run s tr) ∧ (run s tr).envReg e = r' := by
  intro tr
  let s1 := step s (.deploy r' .registry)
  have hl1 : ∀ b, Live s b → Live s1 b := by
    intro b hb
    have hba : b ≠ r' := fun h => by subst h; simp [Live, hfresh, Comp.isLive] at hb
    simpa [s1, Live, step, upd_ne _ _ hba] using hb
  obtain ⟨hk2, he2, hm2, _⟩ := regSets_routing r' es s1
  have hval : Valid s tr := by
    refine valid_append _ _ s ⟨⟨hfresh, fun ns h => by cases h⟩,
      regSets_valid r' es s1 (fun p hp => hl1 _ (hlive p hp))⟩ ⟨?_, trivial⟩
    intro m hme n hu
    have hu1 : UsesName s m n := by
      obtain ⟨ns, hk, hn⟩ := hu
      refine ⟨ns, ?_, hn⟩
      have hk' : s1.kind m = .middleware ns := by
        rw [← hk2]; exact hk
      by_cases hmr : m = r'
      · subst hmr; simp [s1, step] at hk'
      · simpa [s1, step, upd_ne _ _ hmr] using hk'
    have hme1 : s.mwEnv m = e := by
      have : (run s (Step.deploy r' .registry :: regSets r' es)).mwEnv m = e := hme
      rw [run_cons] at this
      rw [hm2] at this
      simpa [s1, step] using this
    obtain ⟨a, hmem, ht⟩ := regSets_table r' n es s1 (hcov m n hme1 hu1)
    refine ⟨a, by rw [run_cons]; exact ht, ?_⟩
    have := hl1 a (hlive (n, a) hmem)
    show (( run s (Step.deploy r' .registry :: regSets r' es)).kind a).isLive = true
    rw [run_cons, hk2]; exact this
  refine ⟨hval, resolvable_under_protocol tr s hs hval, ?_⟩
  simp [tr, run_append, run, step]

/-! ### Concrete counterexample: re-pointing before populating -/

/-- Addresses: 0 middleware using name 7, 1 envoy, 2 old registry, 3 new (empty) registry,
4 getter bound to name 7 in the old registry. -/
def cex : Sys Nat Nat Nat Nat Nat where
  store := fun _ => 0
  kind := fun a => if a = 0 then .middleware [7] else if a = 1 then .envoy
    else if a = 2 then .registry else if a = 3 then .registry
    else if a = 4 then .getter (fun st _ => st 0) else .empty
  table := fun r n => if r = 2 ∧ n = 7 then some 4 else none
  envReg := fun _ => 2
  mwEnv := fun _ => 1
  writer := fun _ => false

theorem cex_resolvable : AllNamesResolvable cex := by
  intro m n ⟨ns, hk, hn⟩
  by_cases hm : m = 0
  · subst hm
    simp [cex] at hk
    subst hk
    simp at hn
    subst hn
    exact ⟨4, by simp [resolve, cex], by simp [Live, cex, Comp.isLive]⟩
  · exfalso
    simp only [cex, hm, if_false] at hk
    split at hk <;> (try split at hk) <;> (try split at hk) <;> (try split at hk) <;> cases hk

/-- (T4f) Re-pointing envoy 1 to the new registry 3 before it binds name 7 makes the
middleware's name unresolvable (an unsafe ordering). -/
theorem counterexample_repoint_before_populate :
    AllNamesResolvable cex ∧ resolve (step cex (.envoyPoint 1 3)) 0 7 = none ∧
      ¬ AllNamesResolvable (step cex (.envoyPoint 1 3)) := by
  have h := repoint_missing_name_breaks cex 1 3 0 7 rfl ⟨[7], by simp [cex], by simp⟩
    (by simp [cex])
  exact ⟨cex_resolvable, h.1, h.2⟩

end Upgrades.Resolve

/-!
# (2) Schema compatibility

A logic version reads field `f` at storage key `key f`. An upgrade is compatible on the old
data iff its key derivation agrees with the old one on the old field space
(`schema_compat_iff`). With namespaced keys `k = H (ns, name)` and `H` injective on the
domain in use (a collision-resistance *hypothesis*), distinct `(ns, name)` pairs never share
a key (`namespaced_no_collision`), so modules in distinct namespaces are isolated
(`module_isolation`). Without injectivity isolation fails (`collision_without_injectivity`).
-/
namespace Upgrades.Schema

open Upgrades

structure Logic (F K : Type) where
  key : F → K

def Logic.read {F K V : Type} (L : Logic F K) (s : K → V) (f : F) : V := s (L.key f)

/-- (2a) Schema compatibility: for any value type with two distinct values, the upgraded logic
`L'` reads every old field exactly as `L` does, in every store, iff the two key derivations
agree on the old field space `Old`. -/
theorem schema_compat_iff {F K V : Type} [DecidableEq K] (v0 v1 : V) (hv : v0 ≠ v1)
    (Old : F → Prop) (L L' : Logic F K) :
    (∀ (s : K → V) f, Old f → L'.read s f = L.read s f) ↔ (∀ f, Old f → L'.key f = L.key f) := by
  constructor
  · intro h f hf
    apply Decidable.byContradiction
    intro hne
    have := h (fun k => if k = L.key f then v1 else v0) f hf
    simp [Logic.read, hne] at this
    exact hv this
  · intro h s f hf
    simp [Logic.read, h f hf]

/-- Logic of the module with namespace `ns`, deriving keys by `H (ns, name)`. -/
def nsLogic {NS Nm K : Type} (H : NS × Nm → K) (ns : NS) : Logic Nm K := ⟨fun n => H (ns, n)⟩

/-- (2b) Distinct `(namespace, name)` pairs in the domain never collide, given `H` injective
on that domain. -/
theorem namespaced_no_collision {NS Nm K : Type} (H : NS × Nm → K) (D : NS × Nm → Prop)
    (hH : InjOn D H) (a b : NS × Nm) (ha : D a) (hb : D b) (hne : a ≠ b) : H a ≠ H b :=
  fun heq => hne (hH a b ha hb heq)

theorem distinct_namespaces_disjoint {NS Nm K : Type} (H : NS × Nm → K) (D : NS × Nm → Prop)
    (hH : InjOn D H) (ns1 ns2 : NS) (n1 n2 : Nm) (h1 : D (ns1, n1)) (h2 : D (ns2, n2))
    (hns : ns1 ≠ ns2) : H (ns1, n1) ≠ H (ns2, n2) :=
  namespaced_no_collision H D hH _ _ h1 h2 (fun h => hns (congrArg Prod.fst h))

/-- (2c) Module isolation: a write made by the module in namespace `ns1` never changes what the
module in namespace `ns2 ≠ ns1` reads. -/
theorem module_isolation {NS Nm K V : Type} [DecidableEq K] (H : NS × Nm → K)
    (D : NS × Nm → Prop) (hH : InjOn D H) (ns1 ns2 : NS) (n1 n2 : Nm)
    (h1 : D (ns1, n1)) (h2 : D (ns2, n2)) (hns : ns1 ≠ ns2) (s : K → V) (v : V) :
    (nsLogic H ns2).read (upd s (H (ns1, n1)) v) n2 = (nsLogic H ns2).read s n2 := by
  have hne := distinct_namespaces_disjoint H D hH ns1 ns2 n1 n2 h1 h2 hns
  simp [Logic.read, nsLogic, upd_ne _ _ (Ne.symm hne)]

/-- (2d) An upgrade that keeps namespace and derivation, and adds names, is compatible on all
old names (instance of `schema_compat_iff`, right-to-left). -/
theorem same_namespace_upgrade_compatible {NS Nm K V : Type} (H : NS × Nm → K) (ns : NS)
    (Old : Nm → Prop) (L' : Logic Nm K) (hL : ∀ n, Old n → L'.key n = H (ns, n))
    (s : K → V) (n : Nm) (hn : Old n) : L'.read s n = (nsLogic H ns).read s n := by
  simp [Logic.read, nsLogic, hL n hn]

/-- (2e) Injectivity is necessary: with a non-injective derivation, two modules in distinct
namespaces collide, and a write by one changes what the other reads. -/
theorem collision_without_injectivity :
    let H : Nat × Nat → Nat := fun _ => 0
    (nsLogic H 2).read (upd (fun _ => (0 : Nat)) (H (1, 0)) 7) 0 ≠
      (nsLogic H 2).read (fun _ => (0 : Nat)) 0 := by
  simp [Logic.read, nsLogic, upd]

end Upgrades.Schema

/-!
# (1) State preservation

A system separates a persistent key-value store from replaceable logic components.
A registry maps each logic name to the principal currently implementing it; a role table
says which principals may write. Logic replacement only moves a registry pointer.

Theorems:
* `replacements_preserve_store`: any sequence of logic replacements leaves the store unchanged.
* `store_change_authorised`: across *any* trace, if the value at key `k` changed, some write
  to `k` occurred in the trace and its caller held the writer role at that moment.
* `store_frame`: if no write in the trace targets `k`, the value at `k` is unchanged.
-/
namespace Upgrades.Store

open Upgrades

structure Sys (K V P N : Type) where
  store  : K → V
  writer : P → Bool
  impl   : N → P

inductive Act (K V P N : Type) where
  | write   (caller : P) (k : K) (v : V)
  | replace (n : N) (p : P)
  | grant   (p : P)
  | revoke  (p : P)

variable {K V P N : Type} [DecidableEq K] [DecidableEq P] [DecidableEq N]

def step (s : Sys K V P N) : Act K V P N → Sys K V P N
  | .write p k v => if s.writer p then { s with store := upd s.store k v } else s
  | .replace n p => { s with impl := upd s.impl n p }
  | .grant p     => { s with writer := upd s.writer p true }
  | .revoke p    => { s with writer := upd s.writer p false }

def run (s : Sys K V P N) (tr : List (Act K V P N)) : Sys K V P N := tr.foldl step s

theorem run_cons (s : Sys K V P N) (a : Act K V P N) (tr : List (Act K V P N)) :
    run s (a :: tr) = run (step s a) tr := rfl

def Act.isReplace : Act K V P N → Bool
  | .replace _ _ => true
  | _ => false

/-- (1a) Any sequence of logic replacements leaves storage unchanged. -/
theorem replacements_preserve_store :
    ∀ (tr : List (Act K V P N)) (s : Sys K V P N),
      (∀ a ∈ tr, a.isReplace = true) → (run s tr).store = s.store := by
  intro tr
  induction tr with
  | nil => intro s _; rfl
  | cons a tr ih =>
    intro s h
    rw [run_cons, ih (step s a) (fun b hb => h b (List.mem_cons_of_mem _ hb))]
    have ha := h a (List.mem_cons_self _ _)
    cases a with
    | replace n p => rfl
    | write _ _ _ => simp [Act.isReplace] at ha
    | grant _ => simp [Act.isReplace] at ha
    | revoke _ => simp [Act.isReplace] at ha

/-- (1b) Storage changes only through authorised writes: if the value at `k` differs after an
arbitrary trace, then position `i` of the trace is a write to `k` by `p`, and `p` held the
writer role in the state reached just before that position. -/
theorem store_change_authorised :
    ∀ (tr : List (Act K V P N)) (s : Sys K V P N) (k : K),
      (run s tr).store k ≠ s.store k →
      ∃ i p v, tr[i]? = some (Act.write p k v) ∧ (run s (tr.take i)).writer p = true := by
  intro tr
  induction tr with
  | nil => intro s k h; exact absurd rfl h
  | cons a tr ih =>
    intro s k h
    by_cases h1 : (step s a).store k = s.store k
    · have h2 : (run (step s a) tr).store k ≠ (step s a).store k := by
        rw [h1]; exact h
      obtain ⟨i, p, v, hi, hp⟩ := ih (step s a) k h2
      exact ⟨i + 1, p, v, by simpa using hi, by simpa [run_cons] using hp⟩
    · cases a with
      | write p k' v =>
        by_cases hw : s.writer p = true
        · by_cases hk : k = k'
          · subst hk; exact ⟨0, p, v, by simp, by simpa using hw⟩
          · exfalso; apply h1; simp [step, hw, upd, hk]
        · exfalso; apply h1; simp [step, hw]
      | replace _ _ => exact absurd rfl h1
      | grant _ => exact absurd rfl h1
      | revoke _ => exact absurd rfl h1

/-- (1c) Frame: a key no write targets keeps its value across any trace (any mix of
replacements, grants, revocations and writes elsewhere). -/
theorem store_frame (tr : List (Act K V P N)) (s : Sys K V P N) (k : K)
    (h : ∀ p v, Act.write p k v ∉ tr) : (run s tr).store k = s.store k := by
  apply Classical.byContradiction
  intro hne
  obtain ⟨i, p, v, hi, _⟩ := store_change_authorised tr s k hne
  exact h p v (List.mem_of_getElem? hi)

/-- Replacement never changes the names clients hold: only `impl` changes, at one name. -/
theorem replace_only_moves_pointer (s : Sys K V P N) (n : N) (p : P) :
    (step s (.replace n p)).store = s.store ∧ (step s (.replace n p)).writer = s.writer ∧
    (step s (.replace n p)).impl n = p ∧
    ∀ m, m ≠ n → (step s (.replace n p)).impl m = s.impl m := by
  refine ⟨rfl, rfl, by simp [step], fun m hm => by simp [step, upd_ne _ _ hm]⟩

end Upgrades.Store