------------------------- MODULE StateCertification ------------------------- (***************************************************************************) (* Evolution 03 bounded model: (1) certification of ACP state roots by *) (* replica receipts with Byzantine signers, (2) containment / release / *) (* re-verification of an agent. *) (* *) (* Part 1 abstracts PBFT ordering as a single "truth" root per seq (what *) (* every honest replica computes, because the ledger is deterministic). *) (* Honest replicas sign only truth; Byzantine replicas sign anything, at *) (* any seq, any number of times. A root is certified at seq s when >= Q *) (* non-equivocating replicas signed it (cain.acp.replica.verify_receipts). *) (* *) (* Part 2 mirrors cain.acp.ledger containment rules. *) (* *) (* MODEL-VERIFIED only: this checks the design under the bounds in the *) (* .cfg files. It is not a proof of the Python implementation. *) (***************************************************************************) EXTENDS Integers, FiniteSets CONSTANTS Replicas, Byz, Q, MaxSeq, Roots, G, T, MaxVer Honest == Replicas \ Byz VARIABLES truth, signed, \* part 1 status, trustVer, trustOk, releaseVer, \* part 2 executedWhile, releasedWith vars == <> None == "none" Init == /\ truth = [s \in 1..MaxSeq |-> None] /\ signed = {} /\ status = "ACTIVE" /\ trustVer = 1 /\ trustOk = TRUE /\ releaseVer = 0 /\ executedWhile = {} /\ releasedWith = {} \* ---------------- part 1: ordering + receipts -------------------------------- Order(s, x) == /\ truth[s] = None /\ (IF s = 1 THEN TRUE ELSE truth[s-1] # None) /\ truth' = [truth EXCEPT ![s] = x] /\ UNCHANGED <> HonestSign(r, s) == /\ r \in Honest /\ truth[s] # None /\ signed' = signed \cup {<>} /\ UNCHANGED <> ByzSign(b, s, x) == /\ b \in Byz /\ signed' = signed \cup {<>} /\ UNCHANGED <> Equivocators(s) == {r \in Replicas : \E x, y \in Roots : x # y /\ <> \in signed /\ <> \in signed} Signers(s, x) == {r \in Replicas : <> \in signed} \ Equivocators(s) Certified(s, x) == Cardinality(Signers(s, x)) >= Q \* ---------------- part 2: containment lifecycle ----------------------------- \* evidence of a lie (EFFECT_MISMATCH / REPORT_CONTRADICTS_OBSERVATION) or a single-governor CONTAIN Contain == /\ status # "CONTAINED" /\ trustVer < MaxVer /\ status' = "CONTAINED" /\ trustVer' = trustVer + 1 /\ trustOk' = FALSE /\ UNCHANGED <> \* RELEASE carries g valid governor signatures; the ledger accepts only g >= T Release(g) == /\ status = "CONTAINED" /\ g >= T /\ status' = "PROBATION" /\ releaseVer' = trustVer /\ releasedWith' = releasedWith \cup {g} /\ UNCHANGED <> \* oracle attestation: a raise is refused while contained (TRUST_INCREASE_WHILE_CONTAINED) Oracle(ok) == /\ trustVer < MaxVer /\ ~(status = "CONTAINED" /\ ok) /\ trustVer' = trustVer + 1 /\ trustOk' = ok /\ status' = IF status = "PROBATION" /\ ok THEN "ACTIVE" ELSE status /\ UNCHANGED <> \* evaluate(): AGENT_CONTAINED, REVERIFICATION_REQUIRED, trust floor CanExec == /\ status # "CONTAINED" /\ trustOk /\ (releaseVer = 0 \/ trustVer > releaseVer) Execute == /\ CanExec /\ executedWhile' = executedWhile \cup {< releaseVer \/ releaseVer = 0>>} /\ UNCHANGED <> Next == \/ \E s \in 1..MaxSeq, x \in Roots : Order(s, x) \/ \E r \in Replicas, s \in 1..MaxSeq : HonestSign(r, s) \/ \E b \in Byz, s \in 1..MaxSeq, x \in Roots : ByzSign(b, s, x) \/ Contain \/ \E g \in 0..G : Release(g) \/ \E ok \in BOOLEAN : Oracle(ok) \/ Execute Spec == Init /\ [][Next]_vars \* ---------------- invariants ------------------------------------------------- CertifiedIsTruth == \A s \in 1..MaxSeq, x \in Roots : Certified(s, x) => x = truth[s] NoFork == \A s \in 1..MaxSeq, x, y \in Roots : (Certified(s, x) /\ Certified(s, y)) => x = y HonestNeverEquivocate == \A s \in 1..MaxSeq : Equivocators(s) \subseteq Byz NoExecWhileContained == \A e \in executedWhile : e[1] # "CONTAINED" NoExecWithoutReverify == \A e \in executedWhile : e[2] ReleaseOnlyWithQuorum == \A g \in releasedWith : g >= T \* liveness side condition (not temporal): honest replicas alone can reach Q HonestCanCertify == Cardinality(Honest) >= Q =============================================================================