# CAIN-42 Evolution 03 — Byzantine Autonomous State Fabric — Report

Date: 2026-10-05. Code: `cain/acp/` (ledger, replica, stateroot, objects, fixtures, evidence),
`cain/govkernel/` (state, recovery, memory, reality — corrections), `verification/acp/verify_state_root.py`,
`tools/acp/{e03_evidence,bench_state}.py`, `docs/formal/StateCertification.tla`.
Evidence: `artifacts/acp/` (E03_STATE_BUNDLE.json, E03_STATE_RESULTS.json, E03_BENCH_*.json, TLC_*.txt).

Evidence categories are kept separate throughout:
**MODEL-VERIFIED** (TLC, bounded), **IMPLEMENTATION-TESTED** (pytest / scenario on real code, one host),
**LIVE-OBSERVED** (production clusters), **INDEPENDENTLY-VERIFIED** (by a third party).
Nothing in this evolution is LIVE-OBSERVED or INDEPENDENTLY-VERIFIED.

## Scope of the forensics (what was and was not inspected)

Inspected end to end: `cain/acp` (Authority Continuity Protocol: ledger, replicas on the production PBFT
engine, receipts, checkpoints, boundary, graph, counterfactual), `cain/govkernel` (E01/E02 kernel and the
E03S "state fabric" committed as 64888b0 during this session), the live E03 route
(`/frontier/e03/authority/*` uses `cain.govkernel.authority`, not `cain.acp`), the evidence publishers, and
the public-IP guard. **Not** re-inspected: every repository/service/package of the ecosystem, the live
clusters, CI/CD, infrastructure. The full-ecosystem capability matrix requested by the prompt was not
rebuilt; the matrix below covers the governance-state path only.

| Capability | Implemented | Tested | Formally modelled | Live | Enforced | Byzantine-tested | Indep. verified |
|---|---|---|---|---|---|---|---|
| Authority objects, attenuation, continuity (ACP E02) | yes | yes | AuthorityContinuity.tla (E02) | no | in ACP ledger | 25-attack suite, N=4 | no |
| Quorum-certified Merkle state root (E03) | yes | yes | StateCertification.tla | no | receipts + checkpoints | N=4/5/7, f forgers | clean-room verifier (ours) |
| Single-use transitions (E03) | yes | yes | no | no | ledger | fuzz + replay tests | no |
| Behaviour consistency + auto-containment (E03) | yes | yes | lifecycle in TLA | no | ledger | scenario N=4/5/7 | no |
| Probation / re-verification (E03) | yes | yes | yes (NoExecWithoutReverify) | no | ledger | — | no |
| Governed memory (E03) | yes | yes | no | no | ledger | scenario | no |
| govkernel state layer (E03S) | yes (corrected) | yes | GovernanceState.tla (no adversary) | no | library only | forged-cert tests | clean-room (ours) |

## A. Current CAIN architecture (governance path)

Two parallel stacks existed: `cain/govkernel` (single-process libraries: canonical ABI, authority,
revocation, causal graph, counterfactual, and since 64888b0 a state machine) and `cain/acp` (a replicated
deterministic ledger whose transitions are ordered by the production PBFT engine, applied by replicas that
verify commit certificates, and whose results are certified by 2f+1 node-signed receipts). Only
`govkernel.authority` is reachable from a live route (feature-flagged, EVALUATE by default).

## B. Evolution 03 architecture

Evolution 03 is built **on ACP**, not as a third layer. The ledger is the CAIN Governance State Machine;
Evolution 03 adds (1) the Merkle state root bound into every receipt, head and checkpoint, (2) single-use
transitions, (3) behaviour consistency with deterministic containment, probation and re-verification,
(4) governed memory, (5) a clean-room verifier, a TLA+ model, an evidence generator with a tamper suite,
and a benchmark. The govkernel E03S layer was corrected (F-E03-1, F-E03-2) and documented as a
single-process library superseded by ACP for replicated state.

## C. Byzantine state model

State = `AuthorityLedger.snapshot()`, 11 dimensions (spec §1). Lifecycle PROPOSE → VALIDATE → PREPARE →
QUORUM → COMMIT → STATE_ROOT → EVIDENCE (spec §3). Every transition records previous head, transition,
reason/outcome, signer(s) (actor/authority), policy/epoch/trust/risk (in the state it is applied to),
sequence, PBFT decision hash (causal parent in the total order), commitment (transition hash), quorum
(commit QC + receipts), evidence (log entry) and resulting state root.
Deterministic serialization: identical inputs → identical roots (test S1; N=4/5/7 replicas produce
identical root histories). A single Byzantine node cannot create an authoritative state: honest replicas
sign only the root they computed and a certificate needs q ≥ f+1 non-equivocating signers (MODEL-VERIFIED
`CertifiedIsTruth`, `NoFork`; IMPLEMENTATION-TESTED Q1 a–e).

**Conflicting realities.** FACT = certified state (root + inclusion proof). OBSERVATION = boundary-signed
OBSERVE / MEMORY_OBSERVE. CLAIM = agent-signed REPORT / MEMORY_WRITE. PROPOSAL = a signed transition not
yet ordered. DECISION = the ledger outcome at its seq. COMMITMENT = ≥ q matching receipts. Conflicting
agent report vs boundary observation → containment; conflicting verified memories → recorded conflict,
adoption blocked; conflicting replicas → equivocation discarded / no quorum; conflicting policy versions,
authority states, trust versions → rejected by epoch/policy/version rules (E02). An unverified
observation never becomes authoritative: memory needs boundary → oracle → governor quorum; reports never
change trust.

## D. Authority-state integration

Authority objects, delegation lineage, revocations and executions are dimensions of the same root, so an
inclusion proof of the `authority` or `revocation` dimension at a certified seq proves the exact authority
state an action was evaluated against. Containment composes with lineage: anything delegated through a
contained agent or authority is denied.

## E. Cryptographic design

Domain-separated SHA-256 and Ed25519 (`cain.acp.canon`), RFC 6962 Merkle tree over dimensions (per-dimension
disclosure without revealing other tenants' data), hash-chained heads that now commit to the state root,
node-signed receipts and checkpoints, PBFT commit QCs. No new primitive was added; the root exists so a
verifier can check one dimension and so receipts/checkpoints commit to state, not only to outcomes.

## F. Causal graph

The existing ACP graph (`cain/acp/graph.py`) and evidence log already answer why/who/where-from. E03 adds
the state root to every log entry and head, and the observation/report/containment records to the
execution and containment dimensions, so the chain AUTHORIZED → EXECUTED → REPORTED → CONTAINED →
RELEASED → RE-VERIFIED is reconstructable from the log and provable against certified roots.

## G. Byzantine-agent model

Covered by ledger rules + tests: lying about execution (REPORT vs OBSERVE → contain), altered parameters
(EFFECT_MISMATCH → contain), replay (request guard + single-use transitions), escalation/delegation beyond
authority (E02 attenuation), stale state (epoch/policy/version), tenant escape (tenant checks; memory
views), privilege laundering via a new identity (KEY_CONTAINED), extending authority while contained
(DELEGATE refused), framing another agent (only the executing agent can REPORT). Model/tool substitution
is E02 (scope binds model/tool/environment; revocation targets MODEL/TOOL). **Not covered:** omitted actions
(an agent that never asks for authority is invisible to the ledger) and effects a boundary cannot observe.

## H. Byzantine-memory model

Four layers, each promoted by a different trust root, strictly ordered, tenant-bound, append-only, with
conflicts surfaced. Tested: poisoning conflict (M2), cross-tenant view and supersede (M3), identical and
re-timed replay (M3), contained writer (M3), memory never changes any `evaluate()` verdict even when an
AUTHORITATIVE memory says "mallory holds ROOT" (M4). **Not covered:** stale memory expiry (records carry
`at_ms`, no TTL rule), vector/embedding memory, deletion requests (no erasure path by design).

## I. Trust transition system

Increase: only oracle-signed TRUST with a higher version; refused while contained. Decrease: oracle, or
automatic to 0 on evidence of a lie. Suspension/containment: CONTAIN or automatic. Probation: RELEASE
(governor threshold). Re-verification: fresh oracle attestation required before any ALLOW. Reinstatement:
the ALLOW path after re-verification. Permanent revocation: REVOKE AGENT/KEY (E02). Agent claims never move
trust (B4). Note: the oracle is a single trust root (one key); trust *increases* are not quorum-certified
beyond PBFT ordering.

## J. Incident containment

DETECT (ledger comparison) → CLASSIFY (reason code) → ISOLATE/REVOKE (agent, key, authority, descendants;
plus E02 tenant halt, global halt, tool/model/environment revocation) → PRESERVE EVIDENCE (history,
receipts, roots) → RELEASE (quorum) → REVERIFY (oracle) → RESTORE. Emergency fail-closed: GLOBAL_HALT /
TENANT_HALT (one governor). Supported scopes: agent, agent key, authority chain, tenant, global, tool,
model, environment, capability. **Not implemented:** agent-group and resource-class containment as single
operations; replica containment is the PBFT membership's job (not done by the ledger).

## K. Recovery architecture

A recovering replica restores only a snapshot whose digest **and state root** match a checkpoint signed by
≥ q replicas, never behind its own watermark (Q3, plus E02 restore tests). Replay from genesis re-derives
identical roots. Corrected govkernel `recover()` requires pinned-quorum certificates and the trusted
genesis root. **Not measured here:** disk loss, view change, membership change and partitions with the
state root (the E02/E26 suites cover the PBFT side; the multi-host clusters were not upgraded).

## L. Formal verification (MODEL-VERIFIED, bounded)

`docs/formal/StateCertification.tla`:
* N=4, f=1, Q=3, 2 seqs, 2 roots: **No error**, 6,019,073 states generated, 358,176 distinct, depth 19.
* N=7, f=2, Q=5, 1 seq: **No error**, 586,913 generated, 37,440 distinct, depth 16.
* Negative control N=4, f=1, Q=1: **CertifiedIsTruth violated** in 3 steps (model is not vacuous).
Invariants: CertifiedIsTruth, NoFork, HonestNeverEquivocate, NoExecWhileContained,
NoExecWithoutReverify, ReleaseOnlyWithQuorum, HonestCanCertify. This checks the design under these bounds;
it is not a proof of the Python code. Not modelled: view change, recovery, memory, tenant isolation.

## M. Adversarial testing (IMPLEMENTATION-TESTED)

* `tests/acp/test_acp_e03_state.py` — 37 tests (state root, dimension proofs, containment, memory,
  N=4/5/7 with f Byzantine receipt forgers, replay, laundering).
* Existing ACP suites (142) and govkernel (93, incl. new forged-certificate regressions) pass.
* Mutation fuzz: 5,760 mutated transitions across 12 kinds, **0** cases where a rejected transition changed
  governed state.
* Clean-room tamper suite: 14 cases on the published bundle, all as expected (13 FAILED, 1 VERIFIED with
  the equivocator excluded).
* Red-team findings (second audit): see R.

## N. Performance (IMPLEMENTATION-TESTED, one host, in-process network)

Fair comparison = HEAD code (no state root) vs this evolution, both on the same host
(`E03_BENCH_BEFORE_RERUN.json` vs `E03_BENCH_AFTER.json`; the first `E03_BENCH_BEFORE.json` ran while a
TLC job occupied 2 cores and is kept only for honesty):

| Submit → quorum receipts, p50 / p95 / p99 ms | before | after |
|---|---|---|
| N=4 | 246 / 335 / 571 | 243 / 294 / 370 |
| N=5 | 346 / 518 / 816 | 342 / 393 / 403 |
| N=7 | 525 / 731 / 841 | 603 / 812 / 1010 |

Ledger EXECUTE apply p50 ≈ 1.2 ms before and after (the root is computed by the replica, not the ledger).
State-root computation: p50 1.6 ms with ~100 executions in state, **p50 37.6 ms / p99 86 ms with ~2,000**
— it is O(state) and runs on every apply on every replica. Dimension-proof verification p50 0.05–0.11 ms.
Failures 0; replicas agreed in every run. Peak traced memory per run 3.1 / 4.2 / 6.7 MB (N=4/5/7).
Not measured: network traffic, revocation propagation across hosts, multi-host latency.

## O. Independent verification

`verification/acp/verify_state_root.py`: zero CAIN imports; re-implements canonical JSON, domain-separated
hashing, Ed25519, RFC 6962, the dimension table and the head chain from the spec. On the published bundle:
**VERIFIED, 27 checks**. It is written by us — not third-party verification.

## P. IP Candidate Register (for counsel review; no legal conclusions)

| # | Candidate | Mechanism / evidence | Prior-art risk (honest) | Suggested treatment |
|---|---|---|---|---|
| 1 | Receipt-certified per-dimension governance state root | 11-dimension RFC 6962 root in every node-signed apply receipt; per-dimension inclusion proofs; tests Q1–Q3, TLA | **High.** Tendermint/CometBFT AppHash signed by ≥2/3 validators; Ethereum state roots; CT logs; SCITT receipts | Defensive publication; claim value only in combination with 2–4 |
| 2 | Evidence-triggered deterministic containment inside the replicated authority ledger (authorized vs boundary-observed vs agent-reported) | `_t_observe`/`_t_report` → contain agent+key+authority, trust→0, descendants denied | Medium. Runtime verification / EDR auto-quarantine exist; replicated ledger-ordered containment of AI-agent authority chains less common | Attorney review candidate; keep parameters as trade secret |
| 3 | Probation with version-gated re-verification after quorum release | release records trust version; ALLOW requires a strictly newer oracle attestation | Medium–high (probation/re-certification patterns in IAM) | Defensive publication |
| 4 | Four-layer governed memory with distinct trust roots per promotion and adoption blocked on conflict | MEMORY_* transitions, M1–M4 | Medium (provenance-tracked memory, data lineage) | Attorney review candidate |
| 5 | Key-level containment against identity laundering | KEY_CONTAINED | High (key revocation lists) | Open / defensive |
| 6 | Single-use governance transitions with a deterministic, clock-bounded replay window | seen_transitions + TRANSITION_STALE | High (nonce windows, Tendermint tx cache) | Open |

Trade-secret candidates: the exact attenuation lattice and scope rules (E02), containment thresholds,
operational runbooks. Open-source candidates: the clean-room verifiers and the TLA models (they create
trust; they reveal no implementation). Patentability, novelty and freedom-to-operate are **not assessed**.

## Q. Reproduction-cost analysis (realistic)

For a competent team that already has a BFT library and Ed25519/Merkle tooling, from public documents:
E03 alone ≈ 3–6 engineer-weeks (state root + receipts 1–2, containment/memory rules 1–2, verifier + TLA +
tests 1–2). The whole ACP stack it depends on (deterministic authority ledger with attenuation, PBFT
integration with certificate binding, receipts, checkpoints, boundary, test corpus) ≈ 6–12 engineer-months
for a senior team with BFT and security experience (distributed systems 30%, security/policy 25%,
testing/adversarial 20%, crypto/formal 10%, integration/ops 15%). The moat is the integrated, tested
combination and the evidence trail, not any single mechanism; a team using CometBFT would get item P1
largely for free.

## R. Security findings (this evolution)

| ID | Severity | Finding | Status |
|---|---|---|---|
| F-E03-1 | **Critical** (published) | govkernel E03S state machine, `recover()` and clean-room `state_verifier.py` accepted a caller-written `{"valid":true,"signers":[...],"threshold":k}` as a quorum: one node could commit any state (demonstrated: `authority = {agent-evil: ROOT}`), and choose threshold 1. S-04 reported PASS. | **Fixed**: pinned membership, Ed25519 certificates, verifier takes pinned members out of band; 6 regression tests + extended clean-room test |
| F-E03-2 | Medium | govkernel state roots admitted floats (no single cross-language encoding) | **Fixed** (`NON_CANONICAL`) |
| F-E03-3 | **High** (library) | ACP ledger had no general transition replay protection: an old quorum-signed GLOBAL_RESUME / RELEASE could lift a *new* halt / containment; an old SET_POLICY could roll policy back; an old halt/contain could be re-applied | **Fixed**: single-use transitions + stale window; 6 regression tests. Not live (ACP is not on a live route) |
| F-E03-4 | Medium | EFFECT_MISMATCH was recorded but had no consequence | **Fixed** (auto-containment) |
| F-E03-5 | Medium | Containment per agent id could be laundered by re-registering the key | **Fixed** (KEY_CONTAINED) |
| F-E03-6 | Low | govkernel `GovernedMemory.write` overwrote records; `reconcile` counted reports not distinct sources | **Fixed** |
| F-E03-7 | Policy | 10 implementation source files served on the public sites (E26 + govkernel bundles), against the owner's code-secrecy directive; the govkernel publisher would re-publish them | **Fixed**: moved by `check_public_ip_exposure.py --move`; publisher now emits sha256 commitments |
| F-E03-8 | Medium (design) | A compromised boundary or a single governor can contain any agent (denial of service) | Accepted by design (stop cheap, release by quorum); documented |
| F-E03-9 | Medium (perf) | State root is O(state) per apply | Open — E04 |

## S. Known limitations

One process, one host, in-process network (no independent failure domains). The live clusters
(cain-mr-01/02) run neither ACP nor the state root. PBFT QCs are not re-verified by the clean-room verifier.
The oracle and boundary are single keys. Execution and replay tables grow without pruning except
`seen_transitions`. Memory has no expiry. The govkernel trust/memory/containment libraries still take
caller-asserted `quorum=`/`verified=` flags (documented, not replicated). No third-party review.

## T. Production readiness by component

| Component | Readiness |
|---|---|
| ACP ledger + E03 rules | PRE-PRODUCTION: tested, not deployed |
| State root + receipts + checkpoints | PRE-PRODUCTION: tested; needs incremental Merkle before large state |
| Clean-room verifier | Usable now on published bundles |
| TLA model | Bounded design check only |
| govkernel E03S libraries | Library/demo only; not a replicated control |

## U. Claims that are demonstrably true (with the evidence)

1. Identical transition sequences yield identical state roots on N=4, 5 and 7 replicas (tests; RESULTS.json).
2. With f Byzantine replicas signing a forged root, the forged root is never certified and the honest root
   is (Q1 a–e; tamper suite; TLA N=4, N=7).
3. A rejected transition does not change governed state (5,760-case fuzz, 0 violations).
4. An agent whose observed effect or report contradicts its authorization is contained on every replica at
   the same seq, and cannot act, delegate, write memory, or regain trust until a quorum release and a fresh
   oracle attestation (B1–B5, C1–C3, scenario seqs 18–36).
5. Memory never changes an authorization verdict (M4).
6. The published bundle verifies with a verifier that imports no CAIN code; 13 tampering cases fail it.

## V. Claims that remain unverified

Multi-host / cross-region behaviour of the state root; behaviour under view change, disk loss and
membership change *with* the root; performance at production state sizes and over a network; third-party
review; any notion of novelty or legal protection; the "200 invariants / 120 vectors" figures in
AGENTS.md (not re-run here).

## W. Recommended Evolution 04

1. Incremental state commitment (per-dimension sparse Merkle maps updated per transition) to remove F-E03-9.
2. Deploy ACP + state root to cain-mr-02 behind a flag; run the E26 multi-host fault matrix against roots.
3. Re-verify PBFT commit QCs in the clean-room verifier.
4. Quorum (or threshold-oracle) trust increases; multi-key boundaries.
5. Pruning/checkpoint-based compaction for executions and replay tables.
6. Extend the TLA model with view change and recovery.
