#!/usr/bin/env python3
"""Clean-room verifier for CAIN ACP Evolution 03 state-root evidence.

ZERO CAIN imports. Depends only on the Python standard library and `cryptography` (Ed25519). Every
encoding is re-implemented here from the published specification (docs/evolution03/STATE_FABRIC.md):

  canonical(x)      = json.dumps(x, sort_keys=True, separators=(",",":"), ensure_ascii=False), UTF-8;
                      floats rejected, integers within +-(2^53-1), ASCII object keys
  H(domain, x)      = SHA-256("CAIN-ACP-H/<domain>\\0" || canonical(x))           (hex)
  sig input         = "CAIN-ACP-SIG/<domain>\\0" || bytes.fromhex(digest)          (Ed25519)
  dimension digest  = H("statedim.v1", {"dimension": name, "value": {field: snapshot[field], ...}})
  leaf              = canonical({"dimension": name, "value_digest": digest})
  state root        = RFC 6962 MTH(leaves in the fixed dimension order below)
  receipt digest    = H("receipt.v1", receipt minus "signature")
  head_k            = H("head.v1", {prev, seq, decision_hash, transition_hash, outcome, reason, result,
                                    state_root})

What it decides, from published evidence only (it never reads CAIN's database):
  * which state roots were certified, at which seq, by which >= quorum pinned replicas;
  * that certified seqs strictly increase (no rollback) and no seq has two certified roots (no fork);
  * equivocating replicas (two different signed receipts for one seq) -- their votes are discarded;
  * that a published snapshot recomputes to the certified root (it does not trust CAIN's arithmetic);
  * that each published dimension proof includes its value under the certified root;
  * that the evidence log's head chain recomputes, that each log transition hashes to its
    transition_hash, and that the certified receipts are exactly log entries (binds log to quorum).

What it does NOT do: re-verify the PBFT commit certificates (it relies on 2f+1 replica signatures over
the result and state root instead), check membership/key provenance (keys are pinned as input), or
judge whether the ledger's rules were right (it checks that the claimed history is the certified one).

Usage: verify_state_root.py BUNDLE.json   -> prints a JSON verdict; exit 0 iff VERIFIED.
"""
from __future__ import annotations

import base64
import hashlib
import json
import sys

from cryptography.exceptions import InvalidSignature
from cryptography.hazmat.primitives.asymmetric.ed25519 import Ed25519PublicKey

SAFE = 2 ** 53 - 1
DIMENSIONS = (
    ("governance", ("genesis", "epoch", "min_authority_epoch", "clock_ms", "applied")),
    ("policy", ("policy_hash", "compatible_policies")),
    ("identity", ("principals", "agents")),
    ("authority", ("authorities",)),
    ("revocation", ("revoked", "halted_tenants", "global_halt")),
    ("trust", ("trust",)),
    ("risk", ("risk",)),
    ("replay", ("consumed_requests", "consumed_nonces", "seen_transitions")),
    ("execution", ("executions",)),
    ("containment", ("contained",)),
    ("memory", ("memory",)),
)
NAMES = [n for n, _ in DIMENSIONS]
RECEIPT_FIELDS = {"cluster_id", "replica", "seq", "decision_hash", "transition_hash", "outcome", "reason",
                  "result_digest", "head", "state_root", "signature"}


class Bad(Exception):
    pass


def _chk(x):
    if x is None or isinstance(x, (str, bool)):
        return
    if isinstance(x, int):
        if abs(x) > SAFE:
            raise Bad("unsafe integer")
        return
    if isinstance(x, float):
        raise Bad("float in canonical data")
    if isinstance(x, list):
        for v in x:
            _chk(v)
        return
    if isinstance(x, dict):
        for k, v in x.items():
            if not isinstance(k, str) or not k.isascii():
                raise Bad("non-ASCII/non-string key")
            _chk(v)
        return
    raise Bad(f"type {type(x).__name__}")


def canon(x) -> bytes:
    _chk(x)
    return json.dumps(x, ensure_ascii=False, sort_keys=True, separators=(",", ":"), allow_nan=False).encode()


def H(domain: str, x) -> str:
    return hashlib.sha256(f"CAIN-ACP-H/{domain}\0".encode() + canon(x)).hexdigest()


def ed_ok(pub_b64: str, domain: str, digest: str, sig_b64: str) -> bool:
    try:
        sig = base64.b64decode(sig_b64, validate=True)
        if base64.b64encode(sig).decode() != sig_b64 or len(sig) != 64:
            return False
        key = base64.b64decode(pub_b64, validate=True)
        Ed25519PublicKey.from_public_bytes(key).verify(sig, f"CAIN-ACP-SIG/{domain}\0".encode() + bytes.fromhex(digest))
        return True
    except (InvalidSignature, ValueError, TypeError):
        return False


# --- RFC 6962 -------------------------------------------------------------------------------------
def _leaf(b):
    return hashlib.sha256(b"\x00" + b).digest()


def _node(a, b):
    return hashlib.sha256(b"\x01" + a + b).digest()


def mth(leaves):
    if len(leaves) == 1:
        return _leaf(leaves[0])
    k = 1
    while k * 2 < len(leaves):
        k *= 2
    return _node(mth(leaves[:k]), mth(leaves[k:]))


def inclusion_ok(leaf, index, size, path, root) -> bool:
    if index >= size:
        return False
    fn, sn, r = index, size - 1, _leaf(leaf)
    for p in path:
        if sn == 0:
            return False
        if fn % 2 == 1 or fn == sn:
            r = _node(p, r)
            if fn % 2 == 0:
                while fn % 2 == 0 and fn != 0:
                    fn >>= 1
                    sn >>= 1
        else:
            r = _node(r, p)
        fn >>= 1
        sn >>= 1
    return sn == 0 and r == root


def dim_leaf(name, value) -> bytes:
    return canon({"dimension": name, "value_digest": H("statedim.v1", {"dimension": name, "value": value})})


def root_of_snapshot(snap) -> str:
    covered = [k for _, ks in DIMENSIONS for k in ks]
    if sorted(covered) != sorted(snap):
        raise Bad(f"snapshot fields != committed dimensions: {sorted(set(snap) ^ set(covered))}")
    return mth([dim_leaf(n, {k: snap[k] for k in ks}) for n, ks in DIMENSIONS]).hex()


def head(prev, e) -> str:
    return H("head.v1", {"prev": prev, "seq": e["seq"], "decision_hash": e["decision_hash"],
                         "transition_hash": e["transition_hash"], "outcome": e["outcome"], "reason": e["reason"],
                         "result": e["result"], "state_root": e["state_root"]})


# --- quorum -----------------------------------------------------------------------------------------
def certify(receipts, keys, quorum, cluster_id):
    """Group validly-signed receipts by everything except the signer; drop equivocators."""
    valid, groups, equiv, problems = {}, {}, set(), []
    for r in receipts:
        if set(r) != RECEIPT_FIELDS:
            problems.append("malformed receipt")
            continue
        body = {k: r[k] for k in RECEIPT_FIELDS - {"signature"}}
        pub = keys.get(r["replica"])
        if not pub or not ed_ok(pub, "receipt.v1", H("receipt.v1", body), r["signature"]):
            problems.append(f"bad signature/unknown replica {r['replica']!r}")
            continue
        if r["cluster_id"] != cluster_id:
            problems.append("foreign cluster receipt")
            continue
        key = tuple(body[k] for k in sorted(body) if k != "replica")
        if r["replica"] in valid:
            if valid[r["replica"]] != key:
                equiv.add(r["replica"])
            continue
        valid[r["replica"]] = key
        groups.setdefault(key, set()).add(r["replica"])
    for k in groups:
        groups[k] -= equiv
    best = max(groups.items(), key=lambda kv: len(kv[1]), default=(None, set()))
    if best[0] is None or len(best[1]) < quorum:
        return None, sorted(equiv), problems
    fields = sorted(RECEIPT_FIELDS - {"signature", "replica"})
    return dict(zip(fields, best[0]), signers=sorted(best[1])), sorted(equiv), problems


def verify(bundle) -> dict:
    out = {"verifier": "cain-acp-e03-cleanroom/1", "checks": [], "certified": []}

    def check(name, ok, detail=""):
        out["checks"].append({"check": name, "ok": bool(ok), "detail": detail})
        return ok

    cl = bundle["cluster"]
    keys, q, n, f = cl["replica_public_keys"], cl["quorum"], len(cl["replica_public_keys"]), cl["f"]
    check("quorum_intersection", 2 * q - n >= f + 1 and q <= n - f, f"n={n} f={f} q={q}")
    seen_seq = {}
    last = 0
    for i, cs in enumerate(bundle["certified_states"]):
        cert, equiv, problems = certify(cs["receipts"], keys, q, cl["cluster_id"])
        if not check(f"state[{i}].quorum", cert is not None, f"equivocators={equiv} problems={problems}"):
            continue
        if equiv:
            check(f"state[{i}].equivocation_excluded", not (set(equiv) & set(cert["signers"])), str(equiv))
        s = cert["seq"]
        check(f"state[{i}].no_fork", seen_seq.get(s, cert["state_root"]) == cert["state_root"], f"seq {s}")
        check(f"state[{i}].monotonic_seq", s > last, f"{s} after {last}")
        seen_seq[s], last = cert["state_root"], max(last, s)
        if "snapshot" in cs:
            try:
                check(f"state[{i}].snapshot_recomputes_root", root_of_snapshot(cs["snapshot"]) == cert["state_root"])
            except Bad as e:
                check(f"state[{i}].snapshot_recomputes_root", False, str(e))
        for p in cs.get("dimension_proofs", []):
            try:
                ok = (p["dimension"] in NAMES and NAMES.index(p["dimension"]) == p["index"]
                      and p["size"] == len(NAMES)
                      and inclusion_ok(dim_leaf(p["dimension"], p["value"]), p["index"], p["size"],
                                       [base64.b64decode(x, validate=True) for x in p["proof"]],
                                       bytes.fromhex(cert["state_root"])))
            except (Bad, KeyError, ValueError, TypeError):
                ok = False
            check(f"state[{i}].dimension[{p.get('dimension')}]", ok)
        out["certified"].append({"seq": s, "state_root": cert["state_root"], "transition_hash": cert["transition_hash"],
                                 "outcome": cert["outcome"], "reason": cert["reason"], "signers": cert["signers"]})
    log = bundle.get("evidence_log")
    if log is not None:
        prev, ok, why = bundle["genesis_head"], True, ""
        by_seq = {}
        for e in log:
            if e["prev_head"] != prev or head(prev, e) != e["head"]:
                ok, why = False, f"head chain breaks at seq {e['seq']}"
                break
            t = e["transition"]
            if t is not None:
                th = H("transition.v1", {"schema": t["schema"], "kind": t["kind"], "body": t["body"], "at_ms": t["at_ms"]})
                if th != e["transition_hash"]:
                    ok, why = False, f"transition does not hash to transition_hash at seq {e['seq']}"
                    break
            prev = e["head"]
            by_seq[e["seq"]] = e
        check("evidence_log.head_chain_and_transition_binding", ok, why)
        for c in out["certified"]:
            e = by_seq.get(c["seq"])
            check(f"evidence_log.contains_certified_seq_{c['seq']}",
                  e is not None and (e["state_root"], e["transition_hash"]) == (c["state_root"], c["transition_hash"]))
    out["verdict"] = "VERIFIED" if out["checks"] and all(c["ok"] for c in out["checks"]) else "FAILED"
    return out


def main(argv):
    with open(argv[1]) as fh:
        res = verify(json.load(fh))
    print(json.dumps(res, indent=2, sort_keys=True))
    return 0 if res["verdict"] == "VERIFIED" else 1


if __name__ == "__main__":
    sys.exit(main(sys.argv))
