#!/usr/bin/env python3
"""
independence-verify — the honest quorum number: how independent a corroboration REALLY is.

A quorum of N sources corroborating a claim is only as independent as the number of distinct derivation
ROOTS it rests on. Five "independent" sensors that all read one upstream feed are k=1, not k=5 — one
corrupted feed falsifies the whole quorum. exori's line (thecolony.cc): "the honest quorum number isn't
your signer count, it's your distinct-root count, and nobody publishes that one." This makes it
publishable AND checkable: a quorum receipt commits, per input, the derivation roots it reduces to; this
walks them and reports the number a naive signer count hides.

A quorum receipt's body is
  {kind:"touchstone.quorum", claim, inputs:[{source, roots:[<root-ref>...]}, ...]}
where a root-ref is any stable identifier for a leaf source (a feed name, a sensor id, another receipt's
recorder:seq:entry_hash). Two inputs COLLAPSE onto each other wherever their root sets intersect.

Given the quorum receipt (recorder + seq), this checks, trusting no server:
  1. the body re-derives its digest and the receipt folds to a Bitcoin-anchored checkpoint (so the
     declared roots are COMMITTED — a quorum can't quietly revise its lineage after the fact);
  2. the independence floor: k = the minimum number of roots whose corruption falsifies EVERY input (a
     minimum hitting set over the inputs' root sets). k=1 means one source can break the whole quorum.
     signer_count > k is a quorum "dressed" as more independent than it is. UPPER BOUND: an UNDECLARED
     shared root can only LOWER k, so honesty is the claimant's — hidden correlation is owned by them,
     exactly as in the collusion floor.

Reuses standing-verify.py (jcs / recompute_entry_hash / fold_proof / get_json) — fetch it alongside. Dep-free.

    python3 independence-verify.py --recorder=<quorum-recorder> --seq=<n> [--base=https://touchstone.cv]
    python3 independence-verify.py --selftest
Exit: 0 = anchored + independence graded · 1 = INFLATED nothing / malformed quorum · 2 = unanchored /
      missing sibling / unreachable. (An INFLATED quorum still exits 0 — it's a graded fact, not a failure.)
"""
import os
import sys
import hashlib
import importlib.util
import itertools
import urllib.error

_HERE = os.path.dirname(os.path.abspath(__file__))


def _load_sibling(filename):
    path = os.path.join(_HERE, filename)
    if not os.path.exists(path):
        raise FileNotFoundError(filename)
    spec = importlib.util.spec_from_file_location(filename.replace("-", "_").replace(".py", ""), path)
    mod = importlib.util.module_from_spec(spec)
    spec.loader.exec_module(mod)
    return mod


def _min_hitting_set(root_sets):
    """Smallest set of roots that intersects EVERY input's root set — the min sources to corrupt to
    falsify the whole quorum. Exact by increasing size (quorums are small); greedy + flagged if huge."""
    if not root_sets:
        return 0, False
    universe = sorted(set().union(*root_sets))
    if len(universe) > 18:
        # Exact is exponential here. The OLD fallback was a greedy hitting set — and that was UNSOUND
        # in the dangerous direction: greedy returns a set >= the true minimum, and a HIGHER floor means
        # "more sources must be corrupted", i.e. MORE claimed independence. So the verifier OVERSTATED
        # safety (witnessed: true k=2 reported as k=3), and the >18 trigger is set by however many roots
        # the EMITTER declares — so an emitter could pad their root list to force the flattering mode.
        # That is the k=1-dressed-as-k=n inflation this tool exists to refuse, committed by the verifier.
        #
        # Replaced with a SOUND LOWER bound: any collection of pairwise-DISJOINT input root-sets forces
        # one corruption each, so k >= |packing|. Under-claiming is safe (it can only make the quorum
        # look weaker than it is); over-claiming is not. Same asymmetry as the lineage floor: hidden or
        # uncomputable structure must cost you, never credit you.
        packing, used = 0, set()
        for rs in sorted((set(r) for r in root_sets), key=len):   # smallest first — packs more sets
            if not (rs & used):
                packing += 1
                used |= rs
        return max(packing, 1), True
    for size in range(1, len(universe) + 1):
        for combo in itertools.combinations(universe, size):
            s = set(combo)
            if all(rs & s for rs in root_sets):
                return size, False
    return len(universe), False


def independence(inputs):
    """Pure grader over a quorum's inputs. Returns the honest independence numbers + a per-root collapse."""
    root_sets, synthetic = [], 0
    for i, inp in enumerate(inputs if isinstance(inputs, list) else []):
        roots = inp.get("roots") if isinstance(inp, dict) else None
        rs = {str(r) for r in roots} if isinstance(roots, list) and roots else set()
        if not rs:                              # an input with NO declared lineage is its own k=1 source
            synthetic += 1
            rs = {"self:%d" % i}
        root_sets.append(rs)
    signer_count = len(root_sets)
    universe = set().union(*root_sets) if root_sets else set()
    distinct_roots = len(universe)
    floor, approx = _min_hitting_set(root_sets)
    # which roots are SHARED across >1 input (where the inflation comes from)
    shared = {}
    for rs in root_sets:
        for r in rs:
            shared[r] = shared.get(r, 0) + 1
    shared = sorted([(r, n) for r, n in shared.items() if n > 1 and not r.startswith("self:")],
                    key=lambda x: -x[1])
    return {
        "signer_count": signer_count, "distinct_roots": distinct_roots, "floor": floor,
        "inflated": floor < signer_count, "approx": approx, "shared_roots": shared,
        "self_rooted": synthetic,
    }


def _verify_anchored(sv, base, recorder, seq):
    try:
        d = sv.get_json("%s/.well-known/touchstone/checkpoints/%s/entry/%d" % (base, recorder, seq))
    except Exception:
        return False, None
    entry, cp = d.get("entry") or {}, d.get("checkpoint") or {}
    if sv.recompute_entry_hash(entry) != entry.get("entry_hash"):
        return False, entry
    ok = d.get("inclusion_proof") is not None and cp.get("merkle_root") \
        and sv.fold_proof(entry.get("entry_hash"), d.get("inclusion_proof")) == cp.get("merkle_root")
    return bool(ok), entry


def verify(recorder, seq, base):
    lines = ["quorum — %s seq %d" % (recorder, seq)]
    try:
        sv = _load_sibling("standing-verify.py")
    except FileNotFoundError:
        return 2, lines + ["fetch standing-verify.py alongside this file."]
    try:
        doc = sv.get_json("%s/quorum/%s/%d" % (base, recorder, seq))
    except urllib.error.HTTPError as e:
        return 2, lines + ["no quorum receipt at %s seq %d (HTTP %d)" % (recorder, seq, e.code)]
    except Exception as e:  # noqa: BLE001
        return 2, lines + ["could not fetch the quorum (%s)" % e]

    body = doc.get("quorum") or {}
    digest = hashlib.sha256(sv.jcs(body).encode("utf-8")).hexdigest()
    dig_ok = digest == doc.get("quorum_sha256")
    ok, entry = _verify_anchored(sv, base, recorder, seq)
    anchored = bool(ok and entry and entry.get("payload_hash") == doc.get("quorum_sha256"))
    lines.append("  %s quorum body → digest %s… %s committed" % ("✓" if dig_ok else "✗", digest[:12], "==" if dig_ok else "!="))
    lines.append("  %s quorum anchored to Bitcoin (declared roots can't be revised after the fact)"
                 % ("✓" if anchored else "·"))

    r = independence(body.get("inputs"))
    lines.append("")
    lines.append("  claim      : %s" % (body.get("claim") or "—"))
    lines.append("  signer_count   : %d   (what a naive quorum advertises)" % r["signer_count"])
    lines.append("  distinct_roots : %d   (upper bound on independence)" % r["distinct_roots"])
    lines.append("  independence k : %d   (min roots to corrupt to falsify the WHOLE quorum%s)"
                 % (r["floor"], " — a LOWER bound: exact is infeasible over this many roots, so k is "
                                "under-claimed, never over-claimed" if r["approx"] else ""))
    if r["approx"]:
        lines.append("      · the exact minimum is >= this number. It is reported DOWNWARD on purpose: an "
                     "over-stated k claims more sources must be corrupted than really must, which is the "
                     "inflation this tool exists to refuse — and the fallback is triggered by how many "
                     "roots the EMITTER declares, so an over-claiming fallback would be theirs to trigger.")
    for rr, n in r["shared_roots"][:6]:
        lines.append("      · root %s carries %d of the %d inputs" % (rr, n, r["signer_count"]))
    if r["self_rooted"]:
        lines.append("      · %d input(s) declared NO lineage — counted as their own k=1 source" % r["self_rooted"])
    lines.append("")
    if r["inflated"]:
        lines.append("RESULT: INFLATED — %d signatures, but the quorum rests on k=%d root(s). k=%d dressed as k=%d. "
                     "Corrupt %d source(s) and every input falls. (UPPER bound: an undeclared shared root only lowers it.)"
                     % (r["signer_count"], r["floor"], r["floor"], r["signer_count"], r["floor"]))
    else:
        lines.append("RESULT: INDEPENDENT — %d inputs over %d disjoint derivation roots; the signer count is honest. "
                     "(UPPER bound: an undeclared shared root would lower it — which is why the roots are committed.)"
                     % (r["signer_count"], r["floor"]))
    return 0, lines


def _kv(argv, key, default=None):
    for a in argv:
        if a.startswith(key + "="):
            return a.split("=", 1)[1]
    return default


def _selftest():
    ok = []
    # 5 sources, all reading one feed → k=1 dressed as k=5.
    q1 = [{"source": "s%d" % i, "roots": ["feed:noaa-gfs"]} for i in range(5)]
    r1 = independence(q1)
    ok.append(("5-of-1 feed → floor 1", r1["floor"] == 1 and r1["signer_count"] == 5 and r1["inflated"]))
    # 5 sources, 5 distinct feeds → honest k=5.
    q2 = [{"source": "s%d" % i, "roots": ["feed:%d" % i]} for i in range(5)]
    r2 = independence(q2)
    ok.append(("5-of-5 distinct → floor 5", r2["floor"] == 5 and not r2["inflated"]))
    # multi-root: A{r1,r2} B{r2,r3} C{r1,r3} → corrupt {r1,r2} hits all → floor 2 < distinct 3.
    q3 = [{"roots": ["r1", "r2"]}, {"roots": ["r2", "r3"]}, {"roots": ["r1", "r3"]}]
    r3 = independence(q3)
    ok.append(("multi-root hitting set → floor 2", r3["floor"] == 2 and r3["distinct_roots"] == 3))
    # an input with NO declared roots is its own source (not free independence, not un-hittable).
    q4 = [{"roots": ["feed:x"]}, {"roots": []}]
    r4 = independence(q4)
    ok.append(("no-lineage input → own root", r4["floor"] == 2 and r4["self_rooted"] == 1))
    # two confirmations reading one scoreboard = k=1 (exori's motivating case).
    q5 = [{"source": "confirmer-a", "roots": ["scoreboard:composite"]},
          {"source": "confirmer-b", "roots": ["scoreboard:composite"]}]
    ok.append(("two readers, one scoreboard → k=1", independence(q5)["floor"] == 1))

    # ── THE FALLBACK MUST NEVER OVER-CLAIM (found 2026-07-13 auditing the self-narrowing class) ─────
    # The old >18-root fallback was a GREEDY hitting set, which returns >= the true minimum. A HIGHER
    # floor means "more sources must be corrupted" = MORE claimed independence, so the verifier
    # OVERSTATED safety — and the trigger is how many roots the EMITTER declares, so padding the root
    # list forced the flattering mode. Same k=1-as-k=n inflation the tool exists to refuse, committed
    # by the verifier. Now a DISJOINT-PACKING LOWER bound: under-claims, never over-claims.
    # Witnessed: on this construction the true minimum is 2; greedy reported 3.
    adv = [{"a", "c"}, {"a", "c"}, {"a", "c"}, {"a"}, {"b", "c"}, {"b", "c"}, {"b", "c"}, {"b"}]
    for i in range(16):                                  # pad the universe past 18 → fallback fires
        adv[i % 8] = adv[i % 8] | {"pad%d" % i}
    k_rep, approx = _min_hitting_set(adv)
    k_true = 2                                            # {a, b} hits every set
    ok.append(("fallback actually fires (not vacuous)", approx is True))
    ok.append(("fallback NEVER over-claims k", k_rep <= k_true))
    ok.append(("…and is tight here (k=2, greedy said 3)", k_rep == k_true))
    # a bound that always returned 1 would trivially satisfy "never over-claims" — pin that it is not
    # degenerate: a genuinely 3-independent quorum over a big universe must still report 3.
    wide = [{"x1", "q%d" % i} for i in range(1)] + [{"x2"}, {"x3"}]
    for i in range(20):
        wide[i % 3] = wide[i % 3] | {"w%d" % i}
    k_wide, approx_w = _min_hitting_set(wide)
    ok.append(("bound is not degenerate (disjoint sets → 3)", (not approx_w) or k_wide == 3))
    for n, g in ok:
        print("  %-34s %s" % (n, "ok" if g else "FAIL"))
    bad = [n for n, g in ok if not g]
    print("\n" + ("SELFTEST FAILED: " + ", ".join(bad) if bad
                  else "SELFTEST OK — the honest quorum number is the distinct-root floor, not the signer count."))
    return 1 if bad else 0


def main(argv):
    if "--selftest" in argv[1:]:
        return _selftest()
    recorder, seq = _kv(argv[1:], "--recorder"), _kv(argv[1:], "--seq")
    base = _kv(argv[1:], "--base", "https://touchstone.cv").rstrip("/")
    if not recorder or seq is None:
        print(__doc__)
        return 2
    code, lines = verify(recorder, int(seq), base)
    for ln in lines:
        print(ln)
    return code


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