#!/usr/bin/env python3
# SPDX-License-Identifier: Apache-2.0
"""verify_bundle.py — verify a DeepSweep Agent Evidence bundle OFFLINE with the Python standard library only.

    python3 verify_bundle.py evidence-bundle.json ledger.pub.pem
    python3 verify_bundle.py --self-test contracts/vectors/evidence-vectors.v1.json   (golden vectors + RFC 8032 KAT)

Exit 0 = VERIFIED (attributed to the pinned key; root reproduced from the records; every inclusion and
consistency proof re-verified). Exit 4 = a check FAILED (the reason is printed). Exit 2 = could not read input.

This is an independent implementation of the format described in `evidence-format.md` (v1):
  canonicalize = RFC 8785 (JCS) · leaf = SHA-256(0x00 || canonicalize(record)) · node = SHA-256(0x01 || L || R)
  (RFC 6962) · tree head signed as Ed25519(canonicalize(treeHead)) (RFC 8032) · keyId = "dsk_" +
  sha256hex(base64(SPKI DER))[:16]. No network, no third-party packages, no secret material anywhere.
"""
import base64, hashlib, json, re, sys

# ----------------------------------------------------------------------------- JCS (RFC 8785, subset used by v1)
def canonicalize(v):
    if v is None: return "null"
    if v is True: return "true"
    if v is False: return "false"
    if isinstance(v, int): return str(v)
    if isinstance(v, float):
        if v != v or v in (float("inf"), float("-inf")): raise TypeError("non-finite number")
        if v == int(v) and abs(v) < 1e21: return str(int(v))
        return repr(v)
    if isinstance(v, str): return json.dumps(v, ensure_ascii=False, separators=(",", ":"))
    if isinstance(v, list): return "[" + ",".join(canonicalize(x) for x in v) + "]"
    if isinstance(v, dict):
        # RFC 8785 sorts by UTF-16 code units; for BMP-only keys this equals code-point order.
        keys = sorted(v.keys(), key=lambda k: k.encode("utf-16-be"))
        return "{" + ",".join(json.dumps(k, ensure_ascii=False, separators=(",", ":")) + ":" + canonicalize(v[k]) for k in keys) + "}"
    raise TypeError("cannot canonicalize %r" % type(v))

def sha256_hex(b): return hashlib.sha256(b).hexdigest()

# ----------------------------------------------------------------------------- RFC 6962 Merkle
HEX = re.compile(r"^[0-9a-f]{64}$")
def hash_leaf(data_bytes): return sha256_hex(b"\x00" + data_bytes)
def hash_node(l_hex, r_hex): return sha256_hex(b"\x01" + bytes.fromhex(l_hex) + bytes.fromhex(r_hex))
def merkle_root(leaves):
    n = len(leaves)
    if n == 0: return sha256_hex(b"")
    if n == 1: return leaves[0]
    k = 1
    while k * 2 < n: k *= 2
    return hash_node(merkle_root(leaves[:k]), merkle_root(leaves[k:]))
def verify_inclusion(leaf_hash, index, tree_size, proof, root):
    # RFC 6962 §2.1.1 (as in RFC 9162 §2.1.3.2)
    if index < 0 or index >= tree_size or not HEX.match(leaf_hash): return False
    fn, sn, r = index, tree_size - 1, leaf_hash
    for p in proof:
        if not HEX.match(p): return False
        if sn == 0: return False
        if fn % 2 == 1 or fn == sn:
            r = hash_node(p, r)
            while not (fn % 2 == 1 or fn == 0):
                fn //= 2; sn //= 2
        else:
            r = hash_node(r, p)
        fn //= 2; sn //= 2
    return sn == 0 and r == root
def verify_consistency(m, n, old_root, new_root, proof):
    # RFC 9162 §2.1.4.2 — consistency between tree sizes m < n
    if m < 1 or m > n or not HEX.match(old_root) or not HEX.match(new_root): return False
    if m == n: return len(proof) == 0 and old_root == new_root
    if any(not HEX.match(p) for p in proof): return False
    fn, sn = m - 1, n - 1
    while fn % 2 == 1:
        fn //= 2; sn //= 2
    proof = list(proof)
    if fn == 0:
        fr = sr = old_root
    else:
        if not proof: return False
        fr = sr = proof.pop(0)
    for c in proof:
        if sn == 0: return False
        if fn % 2 == 1 or fn == sn:
            fr = hash_node(c, fr); sr = hash_node(c, sr)
            while not (fn % 2 == 1 or fn == 0):
                fn //= 2; sn //= 2
        else:
            sr = hash_node(sr, c)
        fn //= 2; sn //= 2
    return sn == 0 and fr == old_root and sr == new_root

# ----------------------------------------------------------------------------- Ed25519 verify (RFC 8032 §5.1, reference arithmetic)
_P = 2**255 - 19
_Q = 2**252 + 27742317777372353535851937790883648493
def _inv(x): return pow(x, _P - 2, _P)
_D = (-121665 * _inv(121666)) % _P
_I = pow(2, (_P - 1) // 4, _P)
def _recover_x(y, sign):
    if y >= _P: return None
    x2 = (y * y - 1) * _inv(_D * y * y + 1) % _P
    if x2 == 0:
        return None if sign else 0
    x = pow(x2, (_P + 3) // 8, _P)
    if (x * x - x2) % _P != 0: x = x * _I % _P
    if (x * x - x2) % _P != 0: return None
    if (x & 1) != sign: x = _P - x
    return x
_GY = 4 * _inv(5) % _P
_GX = _recover_x(_GY, 0)
_G = (_GX, _GY, 1, _GX * _GY % _P)
def _add(P1, P2):
    X1, Y1, Z1, T1 = P1; X2, Y2, Z2, T2 = P2
    A = (Y1 - X1) * (Y2 - X2) % _P; B = (Y1 + X1) * (Y2 + X2) % _P
    C = 2 * T1 * T2 * _D % _P; Dd = 2 * Z1 * Z2 % _P
    E, F, G, H = B - A, Dd - C, Dd + C, B + A
    return (E * F % _P, G * H % _P, F * G % _P, E * H % _P)
def _mul(s, P1):
    Q = (0, 1, 1, 0)
    while s > 0:
        if s & 1: Q = _add(Q, P1)
        P1 = _add(P1, P1); s >>= 1
    return Q
def _eq(P1, P2):
    X1, Y1, Z1, _ = P1; X2, Y2, Z2, _ = P2
    return (X1 * Z2 - X2 * Z1) % _P == 0 and (Y1 * Z2 - Y2 * Z1) % _P == 0
def _decode_point(s):
    if len(s) != 32: return None
    y = int.from_bytes(s, "little"); sign = y >> 255; y &= (1 << 255) - 1
    x = _recover_x(y, sign)
    if x is None: return None
    return (x, y, 1, x * y % _P)
def ed25519_verify(public_key_32, msg, sig_64):
    try:
        if len(public_key_32) != 32 or len(sig_64) != 64: return False
        A = _decode_point(public_key_32)
        if A is None: return False
        Rs, Ss = sig_64[:32], sig_64[32:]
        R = _decode_point(Rs)
        if R is None: return False
        s = int.from_bytes(Ss, "little")
        if s >= _Q: return False
        h = int.from_bytes(hashlib.sha512(Rs + public_key_32 + msg).digest(), "little") % _Q
        sB = _mul(s, _G); hA = _mul(h, A)
        return _eq(sB, _add(R, hA))
    except Exception:
        return False

# ----------------------------------------------------------------------------- key handling
def load_pinned_key(path):
    txt = open(path, "r", encoding="utf-8").read().strip()
    if "BEGIN PUBLIC KEY" in txt:
        b64 = "".join(l.strip() for l in txt.splitlines() if l and not l.startswith("-----"))
    else:
        b64 = txt
    der = base64.b64decode(b64)
    if len(der) != 44 or der[:12] != bytes.fromhex("302a300506032b6570032100"):
        raise ValueError("not an Ed25519 SPKI public key")
    key_id = "dsk_" + sha256_hex(base64.b64encode(der).decode("ascii").encode("utf-8"))[:16]
    return der[-32:], key_id

# ----------------------------------------------------------------------------- the checks
def verify_bundle(bundle, pinned_raw, pinned_key_id):
    findings = []
    ok_all = True
    def f(check, ok, detail):
        nonlocal ok_all
        findings.append((check, ok, detail)); ok_all = ok_all and ok
    if not isinstance(bundle, dict) or bundle.get("status") != "ok" or not isinstance(bundle.get("root"), str) \
       or not isinstance(bundle.get("records"), list) or not isinstance(bundle.get("inclusion"), list):
        return False, [("envelope", False, "bundle must be a status:ok export with root, records, inclusion")]
    records, root = bundle["records"], bundle["root"]
    # 0. chain attestation — the exporter refuses to emit a bundle over a
    # broken hash chain (TEAM-ADR-046); anything but an explicit true is a
    # tampered-before-export or hand-assembled bundle. Fail closed.
    chain_ok = bundle.get("chainIntact") is True
    f("chain", chain_ok, "bundle attests an intact ledger hash chain at export time" if chain_ok
      else "bundle does not attest an intact hash chain (chainIntact is not true)")
    # 3. root recomputed from the records
    leaves = [hash_leaf(canonicalize(r).encode("utf-8")) for r in records]
    root_ok = merkle_root(leaves) == root
    f("root-recomputation", root_ok, "root reproduced from %d records" % len(records) if root_ok
      else "records do not reproduce the bundle's root — a record was altered")
    # 1+2. attribution
    sth = bundle.get("signedTreeHead")
    if sth is None:
        f("attribution", False, "no signed tree head — internally consistent but UNATTRIBUTED")
    else:
        head, sig, kid = sth.get("treeHead"), sth.get("signature"), sth.get("keyId")
        if not isinstance(head, dict) or head.get("schemaVersion") != 1 or not isinstance(head.get("treeSize"), int) \
           or not HEX.match(str(head.get("rootHash"))) or not isinstance(head.get("signedAt"), str) \
           or not isinstance(head.get("logId"), str) or not isinstance(sig, str) or not isinstance(kid, str):
            f("attribution", False, "malformed signed tree head envelope")
        elif kid != pinned_key_id:
            f("attribution", False, "tree-head keyId %s is not the pinned key (%s)" % (kid, pinned_key_id))
        elif head["logId"] != kid:
            f("attribution", False, "treeHead.logId does not match the signing keyId")
        elif not ed25519_verify(pinned_raw, canonicalize(head).encode("utf-8"), base64.b64decode(sig)):
            f("attribution", False, "tree head signature does not verify under %s" % kid)
        elif head["rootHash"] != root or head["treeSize"] != len(records):
            f("attribution", False, "signed tree head does not bind this bundle's (treeSize, root)")
        else:
            f("attribution", True, "signed by log %s, binding size %d" % (kid, head["treeSize"]))
    # 4. inclusion proofs
    bad = [i for i, inc in enumerate(bundle["inclusion"])
           if not (isinstance(inc, dict) and isinstance(inc.get("leafHash"), str) and isinstance(inc.get("leafIndex"), int)
                   and isinstance(inc.get("treeSize"), int) and isinstance(inc.get("proof"), list)
                   and verify_inclusion(inc["leafHash"], inc["leafIndex"], inc["treeSize"], inc["proof"], root))]
    f("inclusion", not bad, "%d inclusion proof(s) verified against the root" % len(bundle["inclusion"]) if not bad
      else "inclusion proof(s) %s do not verify" % bad)
    unbound = [i for i, inc in enumerate(bundle["inclusion"])
               if isinstance(inc, dict) and isinstance(inc.get("leafIndex"), int) and 0 <= inc["leafIndex"] < len(leaves)
               and inc.get("leafHash") != leaves[inc["leafIndex"]]]
    f("inclusion-binding", not unbound, "every inclusion proof names the hash of its own record" if not unbound
      else "inclusion proof(s) %s name a leaf hash that is not the hash of records[leafIndex]" % unbound)
    f("inclusion-coverage", len(bundle["inclusion"]) == len(records),
      "every record carries an inclusion proof" if len(bundle["inclusion"]) == len(records)
      else "%d records but %d inclusion proofs" % (len(records), len(bundle["inclusion"])))
    # 5. consistency proofs
    cons = bundle.get("consistency") or []
    # Field names are the exporter's contract (src/evidence/export.ts
    # ConsistencyProofExport): firstSize/firstRoot/secondSize/secondRoot.
    # This block previously read oldSize/newSize/oldRoot/newRoot — names no
    # exporter ever emitted — so any bundle CARRYING a consistency proof was
    # refused as tampered (TEAM-ADR-046 found it; the round-trip guard only
    # ever fed this verifier an empty consistency array).
    badc = [i for i, c in enumerate(cons)
            if not (isinstance(c, dict) and isinstance(c.get("firstSize"), int) and isinstance(c.get("secondSize"), int)
                    and isinstance(c.get("firstRoot"), str) and isinstance(c.get("secondRoot"), str) and isinstance(c.get("proof"), list)
                    and c["secondRoot"] == root
                    and verify_consistency(c["firstSize"], c["secondSize"], c["firstRoot"], c["secondRoot"], c["proof"]))]
    f("consistency", not badc, "%d consistency proof(s) verified" % len(cons) if not badc else "consistency proof(s) %s do not verify" % badc)
    return ok_all, findings

def self_test(vectors_path):
    """Run the repository's golden vectors (contracts/vectors/evidence-vectors.v1.json) with negative controls."""
    vec = json.load(open(vectors_path, "r", encoding="utf-8"))
    fails = 0
    def check(name, cond):
        nonlocal fails
        print(("PASS  " if cond else "FAIL  ") + name)
        if not cond: fails += 1
    check("empty tree root", merkle_root([]) == vec["knownAnswer"]["emptyTreeRoot"])
    leaves = [hash_leaf(canonicalize(lv["record"]).encode("utf-8")) for lv in vec["leafVectors"]]
    check("leaf hashes (JCS + RFC 6962 leaf) match %d vectors" % len(leaves), all(l == lv["leafHash"] for l, lv in zip(leaves, vec["leafVectors"])))
    check("tree roots match %d vectors" % len(vec["trees"]), all(merkle_root(leaves[:t["treeSize"]]) == t["rootHash"] for t in vec["trees"]))
    inc_ok = all(verify_inclusion(leaves[i["leafIndex"]], i["leafIndex"], t["treeSize"], i["path"], t["rootHash"]) for t in vec["trees"] for i in t["inclusion"])
    inc_neg = all(not verify_inclusion(leaves[i["leafIndex"]], (i["leafIndex"] + 1) % t["treeSize"], t["treeSize"], i["path"], t["rootHash"]) for t in vec["trees"] if t["treeSize"] > 1 for i in t["inclusion"])
    check("inclusion proofs verify, and a shifted index is refused", inc_ok and inc_neg)
    c_ok = all(verify_consistency(c["firstTreeSize"], c["secondTreeSize"], c["firstRoot"], c["secondRoot"], c["path"]) for c in vec["consistency"])
    c_neg = all(not verify_consistency(c["firstTreeSize"], c["secondTreeSize"], c["secondRoot"], c["firstRoot"], c["path"]) for c in vec["consistency"])
    check("consistency proofs verify (%d), and swapped roots are refused" % len(vec["consistency"]), c_ok and c_neg)
    # RFC 8032 §7.1 test vector 1 (public key, empty message, signature)
    pk = bytes.fromhex("d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a")
    sig = bytes.fromhex("e5564300c360ac729086e2cc806e828a84877f1eb8e5d974d873e065224901555fb8821590a33bacc61e39701cf9b46bd25bf5f0595bbe24655141438e7a100b")
    check("Ed25519 RFC 8032 test vector 1 verifies, and a flipped bit is refused",
          ed25519_verify(pk, b"", sig) and not ed25519_verify(pk, b"", bytes([sig[0] ^ 1]) + sig[1:]))
    print("self-test: all checks passed" if not fails else "self-test: %d FAILED" % fails)
    return 0 if not fails else 4

def main(argv):
    if len(argv) == 2 and argv[0] == "--self-test":
        return self_test(argv[1])
    if len(argv) != 2:
        print(__doc__); return 2
    try:
        bundle = json.load(open(argv[0], "r", encoding="utf-8"))
        raw, kid = load_pinned_key(argv[1])
    except Exception as e:
        print("could not read input: %s" % e); return 2
    ok, findings = verify_bundle(bundle, raw, kid)
    for check, good, detail in findings:
        print("%s  %-20s %s" % ("PASS" if good else "FAIL", check, detail))
    print("VERIFIED — attributed to %s, %d record(s)" % (kid, len(bundle.get("records", []))) if ok else "NOT VERIFIED")
    return 0 if ok else 4

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