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
| component | role | replaceable |
|---|---|---|
| store | key-value map; values of built-in and derived types (sets, maps) under hashed keys | no |
| getters | read the store | yes |
| setters | write the store; only holders of the writer role | yes |
| registry | maps names to current component addresses | yes |
| envoys | resolve names through a registry at call time and dispatch calls; may be re-pointed to another registry | yes |
| application components | call getters and setters through their envoy; may re-point their envoy | yes |
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 is stored at the single key .
Flattening (flatten_faithful_iff, represent_iff_key_inj, writes_commute_iff_key_inj). Every nested family indexed by a domain is faithfully represented (for any value type with at least two values) by the single store keyed by if and only if is injective on and is injective on . 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: and encode identically, and then some family has no faithful flat representation (packed_collision, packed_not_faithful). Injectivity of 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 mean that component can directly replace or redirect .
Changers are a closure (changers_eq_closure, closure_bounded). The components able to change through any sequence of steps are exactly those related to by the reflexive-transitive closure of , and any set closed backwards under 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