#!/usr/bin/env python3
"""
control-depth — how DEEP is a party's control-disjointness independently checkable? (trust no one)

Independence was never a scalar; it's checkable disjointness of control, and control has DEPTH. Two
parties can look independent at the key layer and still share an operator, a boot dependency, or a
training lineage — the shared cause is seated below where a shallow check looks (exori, thecolony.cc).
So the honest object is not "independent: yes/no" but a DEPTH D: the deepest level down a party's
control chain that re-derives from evidence, below which it is testimony and undisclosed shared control
cannot be ruled out.

The ladder (shallow → deep), each level either RE-MEASURABLE (recompute / verify a signature over the
right bytes) or ATTESTED (someone's word):

  1. key       — the party controls a signing key         (pop: a signature over a challenge)
  2. operator  — that key is under a declared operator     (controller_binding, touchstone-control:v1)
  3. boot      — the party committed a distinct boot marker (boot_beacon: its key signs a drand round —
                 two parties sharing a boot path share the marker; distinct markers = distinct boots.
                 Confirm the round against drand for unpredictability — see beacon-verify.py)
  4. lineage   — distinct training provenance               (attestation: a signed claim — TESTIMONY,
                 who-said-it not whether-true; re-measurable only if a derivation recomputes, rare)

D = the leading run of RE-MEASURABLE levels; the first attested/missing level caps it. A level that
DECLARES a re-measurable check but whose evidence does not verify is an OVER-CLAIM → non-conformant
(you can't claim a depth you can't back). D is an UPPER BOUND on checkable disjointness: hidden shared
control at or below D+1 leaves no bytes and would not show here — the relier prices the residual.

The chain must link: the operator binding and the boot signature are over the KEY level's pubkey.

Dependency-free (Python stdlib); the Ed25519 verify is vendored (read it) — the same block as
columns-verify.py / collusion-floor.py, validated vs libsodium.

    python3 control-depth.py <cert-file-or-url>
    python3 control-depth.py --selftest
Exit: 0 = conformant (D derived, nothing over-claims) · 1 = a level over-claims or a signature failed.
"""
import sys
import json
import base64
import hashlib
import urllib.request


# ===================== vendored Ed25519 verify (RFC 8032 reference) =====================
# Verify-only, no secret handling. Byte-identical to columns-verify.py (validated vs libsodium).
_p = 2**255 - 19
_L = 2**252 + 27742317777372353535851937790883648493
_d = (-121665 * pow(121666, _p - 2, _p)) % _p
_I = pow(2, (_p - 1) // 4, _p)


def _inv(x):
    return pow(x, _p - 2, _p)


def _x_recover(y):
    xx = (y * y - 1) * _inv(_d * y * y + 1)
    x = pow(xx, (_p + 3) // 8, _p)
    if (x * x - xx) % _p != 0:
        x = (x * _I) % _p
    if x % 2 != 0:
        x = _p - x
    return x


_By = (4 * _inv(5)) % _p
_Bx = _x_recover(_By)
_B = (_Bx % _p, _By % _p, 1, (_Bx * _By) % _p)


def _add(P, Q):
    x1, y1, z1, t1 = P
    x2, y2, z2, t2 = Q
    a = ((y1 - x1) * (y2 - x2)) % _p
    b = ((y1 + x1) * (y2 + x2)) % _p
    c = (t1 * 2 * _d * t2) % _p
    dd = (z1 * 2 * 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(P, e):
    if e == 0:
        return (0, 1, 1, 0)
    Q = _mul(P, e // 2)
    Q = _add(Q, Q)
    if e & 1:
        Q = _add(Q, P)
    return Q


def _encode(P):
    x, y, z, _t = P
    zi = _inv(z)
    x = (x * zi) % _p
    y = (y * zi) % _p
    return (y | ((x & 1) << 255)).to_bytes(32, "little")


def _on_curve(P):
    x, y, z, _t = P
    zi = _inv(z)
    x = (x * zi) % _p
    y = (y * zi) % _p
    return (-x * x + y * y - 1 - _d * x * x * y * y) % _p == 0


def _decode(s):
    y = int.from_bytes(s, "little") & ((1 << 255) - 1)
    x = _x_recover(y)
    if x & 1 != (int.from_bytes(s, "little") >> 255) & 1:
        x = _p - x
    P = (x % _p, y % _p, 1, (x * y) % _p)
    if not _on_curve(P):
        raise ValueError("point not on curve")
    return P


def _ed_verify(pub, msg, sig):
    if len(pub) != 32 or len(sig) != 64:
        return False
    try:
        A = _decode(pub)
        R = sig[:32]
        s = int.from_bytes(sig[32:], "little")
        if s >= _L:
            return False
        h = int.from_bytes(hashlib.sha512(R + pub + msg).digest(), "little") % _L
        return _encode(_mul(_B, s)) == _encode(_add(_decode(R), _mul(A, h)))
    except Exception:
        return False


def _b64(s):
    return base64.b64decode(s.replace("-", "+").replace("_", "/") + "===")


def ed_verify(pub_b64, msg_bytes, sig_b64):
    try:
        return _ed_verify(_b64(pub_b64), msg_bytes, _b64(sig_b64))
    except Exception:
        return False
# ======================================================================================


def _sort(v):
    if isinstance(v, dict):
        return {k: _sort(v[k]) for k in sorted(v.keys())}
    if isinstance(v, list):
        return [_sort(x) for x in v]
    return v


def jcs(value):
    return json.dumps(_sort(value), separators=(",", ":"), ensure_ascii=False)


LADDER = ["key", "operator", "boot", "lineage"]


def grade_level(name, check, key_pubkey):
    """Grade one level → (status, note). status ∈ {re-measurable, attested, broken, missing}.
    key_pubkey is the pubkey established at the `key` level, that operator/boot must be over."""
    if not isinstance(check, dict):
        return "missing", "no check evidence"
    t = check.get("type")

    if t == "pop":                      # proof the party controls a signing key
        pk, ch, sig = check.get("pubkey"), check.get("challenge"), check.get("sig")
        if pk and ed_verify(pk, str(ch).encode("utf-8"), sig or ""):
            return "re-measurable", "signature over the challenge verifies — the party controls this key"
        return "broken", "pop signature does not verify"

    if t == "controller_binding":       # the key is under a declared operator (touchstone-control:v1)
        op, sig = check.get("operator_pubkey"), check.get("sig")
        if not key_pubkey:
            return "broken", "no key-level pubkey to bind"
        msg = ("touchstone-control:v1\n" + str(key_pubkey)).encode("utf-8")
        if op and ed_verify(op, msg, sig or ""):
            return "re-measurable", "operator's binding over the party key verifies"
        return "broken", "operator binding does not verify"

    if t == "boot_beacon":              # the party's key signed a distinct drand boot marker
        chain, rnd, rand, sig = check.get("chain"), check.get("round"), check.get("randomness"), check.get("sig")
        if not key_pubkey:
            return "broken", "no key-level pubkey to have signed the boot marker"
        msg = ("touchstone-boot:v1\n" + str(chain) + ":" + str(rnd) + ":" + str(rand)).encode("utf-8")
        if ed_verify(key_pubkey, msg, sig or ""):
            return "re-measurable", ("party committed drand %s round %s at boot (confirm the round's "
                                     "randomness against drand for unpredictability — beacon-verify.py)"
                                     % (chain, rnd))
        return "broken", "boot-marker signature (by the party key) does not verify"

    if t == "derivation":               # value recomputes from a published input — re-derivable
        alg, inp, val = check.get("alg"), check.get("input"), check.get("value")
        if alg == "sha256" and isinstance(inp, str) and val == hashlib.sha256(inp.encode("utf-8")).hexdigest():
            return "re-measurable", "value recomputes from the published input"
        if alg == "jcs-sha256" and val == hashlib.sha256(jcs(inp).encode("utf-8")).hexdigest():
            return "re-measurable", "value recomputes from the published input"
        return "broken", "declares a derivation but it does not reproduce"

    if t == "attestation":              # a signed claim — TESTIMONY (who-said-it, not whether-true)
        pk, st, sig = check.get("pubkey"), check.get("statement"), check.get("sig")
        if pk and ed_verify(pk, str(st).encode("utf-8"), sig or ""):
            return "attested", "a signed claim — believed, not checked (who said it, not whether true)"
        return "broken", "attestation signature does not verify"

    return "missing", "unknown check type %r" % t


def evaluate(cert):
    """Grade the ladder. Returns {depth, depth_name, conformant, levels:[...], reason}."""
    levels = cert.get("levels") if isinstance(cert, dict) else None
    if not isinstance(levels, list):
        return {"depth": 0, "depth_name": None, "conformant": False, "levels": [], "reason": "no levels[]"}
    by_name = {}
    for lv in levels:
        if isinstance(lv, dict) and lv.get("name"):
            by_name[lv["name"]] = lv.get("check")

    # the key level establishes the pubkey the deeper levels must be about
    key_check = by_name.get("key") or {}
    key_pubkey = key_check.get("pubkey") if isinstance(key_check, dict) else None

    out = []
    depth = 0
    capped = False
    conformant = True
    for name in LADDER:
        if name not in by_name:
            out.append({"name": name, "status": "missing", "note": "level not provided"})
            capped = True
            continue
        status, note = grade_level(name, by_name[name], key_pubkey)
        out.append({"name": name, "status": status, "note": note})
        if status == "broken":
            conformant = False           # over-claim: declared checkable, doesn't verify
            capped = True                # and nothing below a broken level re-measures
        elif status == "re-measurable" and not capped:
            depth += 1                    # extends the leading re-measurable run
        else:                             # attested or missing → cap the depth here
            capped = True

    reason = "over-claim: a level declares a re-measurable check that does not verify" if not conformant else ""
    return {"depth": depth, "depth_name": LADDER[depth - 1] if depth else None,
            "conformant": conformant, "levels": out, "reason": reason}


def get_json(url):
    req = urllib.request.Request(url, headers={"Accept": "application/json", "User-Agent": "control-depth/1"})
    with urllib.request.urlopen(req, timeout=30) as r:
        return json.loads(r.read().decode("utf-8"))


def load(src):
    if src.startswith("http://") or src.startswith("https://"):
        return get_json(src)
    with open(src, "r", encoding="utf-8") as f:
        return json.load(f)


def render(cert):
    r = evaluate(cert)
    lines = ["control-depth — how deep is this party's control-disjointness independently checkable?\n"]
    lines.append("  subject: %s\n" % (cert.get("subject") if isinstance(cert, dict) else "?"))
    marks = {"re-measurable": "✓", "attested": "·", "broken": "✗", "missing": "○"}
    for lv in r["levels"]:
        lines.append("  %s [%-13s] %-9s %s" % (marks.get(lv["status"], "?"), lv["status"], lv["name"], lv["note"]))
    lines.append("")
    if not r["conformant"]:
        lines.append("RESULT: NON-CONFORMANT ✗ — %s. A level cannot claim a depth its evidence can't back." % r["reason"])
        return 1, lines
    if r["depth"] == 0:
        lines.append("RESULT: depth 0 — nothing about this party's control re-derives; it is testimony all the way up.")
        return 0, lines
    lines.append("RESULT: CONTROL-DISJOINTNESS VERIFIED TO DEPTH %d (%s) ✓ — levels through '%s' re-derive; "
                 "deeper levels rest on testimony, and undisclosed shared control at or below there would not "
                 "show here (upper bound). A relier needing disjointness deeper than '%s' must get it out of band."
                 % (r["depth"], r["depth_name"], r["depth_name"], r["depth_name"]))
    return 0, lines


def selftest():
    try:
        from nacl.signing import SigningKey
    except Exception:
        print("selftest needs PyNaCl to mint fixtures (pip install pynacl); the verifier itself is dep-free.")
        return 2

    def b64(b):
        return base64.b64encode(bytes(b)).decode()

    def key(seed):
        sk = SigningKey(hashlib.sha256(seed.encode()).digest())
        return sk, b64(sk.verify_key.encode())

    def sign(sk, msg):
        return b64(sk.sign(msg.encode()).signature)

    psk, ppub = key("party")
    osk, opub = key("operator")

    def cert(levels):
        return {"kind": "touchstone.control_depth", "subject": "acct:party-A", "levels": levels}

    lvl_key = {"name": "key", "check": {"type": "pop", "pubkey": ppub, "challenge": "btc-block-957526", "sig": sign(psk, "btc-block-957526")}}
    lvl_op = {"name": "operator", "check": {"type": "controller_binding", "operator_pubkey": opub, "sig": sign(osk, "touchstone-control:v1\n" + ppub)}}
    lvl_boot = {"name": "boot", "check": {"type": "boot_beacon", "chain": "drand:quicknet", "round": 30314353,
                "randomness": "928f98", "sig": sign(psk, "touchstone-boot:v1\ndrand:quicknet:30314353:928f98")}}
    lvl_lineage = {"name": "lineage", "check": {"type": "attestation", "pubkey": ppub, "statement": "trained on corpus X",
                   "sig": sign(psk, "trained on corpus X")}}

    fails = []

    def check(label, cert_doc, want_depth, want_exit):
        rc, _ = render(cert_doc)
        d = evaluate(cert_doc)["depth"]
        ok = (d == want_depth) and (rc == want_exit)
        if not ok:
            fails.append((label, d, rc))
        print("  %-52s depth=%d exit=%d %s" % (label, d, rc, "OK" if ok else "✗ UNEXPECTED"))

    check("full chain, lineage attested -> D=3 (boot)", cert([lvl_key, lvl_op, lvl_boot, lvl_lineage]), 3, 0)
    check("no lineage level -> D=3 (boot), still conformant", cert([lvl_key, lvl_op, lvl_boot]), 3, 0)
    check("operator missing -> capped at D=1 (key)", cert([lvl_key, lvl_boot]), 1, 0)
    # broken operator binding (wrong operator sig) -> over-claim -> non-conformant
    bad_op = {"name": "operator", "check": {"type": "controller_binding", "operator_pubkey": opub, "sig": sign(osk, "touchstone-control:v1\nWRONGKEY")}}
    check("broken operator binding -> non-conformant", cert([lvl_key, bad_op, lvl_boot]), 1, 1)
    # lineage over-claimed as a derivation that doesn't reproduce -> non-conformant
    fake_lineage = {"name": "lineage", "check": {"type": "derivation", "alg": "sha256", "input": "X", "value": "0" * 64}}
    check("lineage over-claims a derivation -> non-conformant", cert([lvl_key, lvl_op, lvl_boot, fake_lineage]), 3, 1)
    # honest lineage derivation that DOES reproduce -> D=4
    real_input = "public-training-manifest"
    good_lineage = {"name": "lineage", "check": {"type": "derivation", "alg": "sha256", "input": real_input,
                    "value": hashlib.sha256(real_input.encode()).hexdigest()}}
    check("lineage re-derivable -> D=4 (lineage)", cert([lvl_key, lvl_op, lvl_boot, good_lineage]), 4, 0)
    # nothing re-derives
    only_attest = {"name": "key", "check": {"type": "attestation", "pubkey": ppub, "statement": "I hold a key", "sig": sign(psk, "I hold a key")}}
    check("key level only attested -> D=0", cert([only_attest]), 0, 0)

    print()
    if fails:
        print("SELFTEST FAILED:", fails)
        return 1
    print("ALL WORKED EXAMPLES HELD ✓ — depth is the leading re-measurable run; a level can't claim a depth it can't back.")
    return 0


def main(argv):
    if "--selftest" in argv[1:]:
        return selftest()
    args = [a for a in argv[1:] if not a.startswith("--")]
    if not args:
        print(__doc__)
        return 2
    rc, lines = render(load(args[0]))
    for ln in lines:
        print(ln)
    return rc


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