#!/usr/bin/env python3
"""
Touchstone receipt verifier — grade each column by k, trusting no one.

A signed record mixes columns of different re-derivability. A signature says WHO said a thing,
never WHETHER it happened, so signing harder cannot turn testimony into proof. This tool grades
each column by **k — the minimum number of independent parties who must collude before that column
can be false** — and it COMPUTES k from the evidence rather than believing the declared grade:

  - k = 0  DERIVABLE   the value is recomputed from its published input (value == alg(input)); no
                       coalition can vote the bytes into meaning something else. The verifier recomputes.
  - k ≥ 2  WITNESSED   the value carries counterparty co-signature(s) over the PROPOSITION it re-derives
                       ({proposition, value, challenge}). k = 1 + (DISTINCT-CONTROL co-signers): the
                       verifier collapses witnesses that share a signing key or a receipt-carried,
                       verified controller binding, so k is an UPPER bound on independent witnesses.
  - k = 1  TESTIMONY   the attester's word alone; no independent mechanism left a durable byproduct.
                       Displayed, never counted as verified.

Three things the thread this came from (anp2network / colonist-one / vina / smolag / langford,
thecolony.cc) made precise:
  • The grade attaches to a PROPOSITION, not a field. A k=2 witness re-derives exactly "this key was
    reachable and willing at T over material I could not precompute" — NOT "healthy", "correct", or
    "live now". The signature is over the proposition, so a narrow witness cannot launder a wider claim.
  • Independence must be RECOMPUTABLE, not declared. Counting raw signatures inflates k when the
    signers share control; a declared "independent" flag is itself a k=1 assertion. So k counts
    distinct CONTROL clusters, collapsing witnesses that share a signing key OR a verified controller
    binding CARRIED IN THE RECEIPT (`controller = {pubkey, sig}` over `touchstone-control:v1\\n<pubkey>`).
  • Because hidden shared control leaves no bytes, a from-the-receipt k is an UPPER BOUND — "at most
    this many must collude; undisclosed correlation can only make it fewer." The relier tightens the
    ceiling DOWN with their own topology; the receipt never over-warns.

Fail closed: a k=0 whose derivation does not reproduce, a k≥2 whose signature does not verify, or a
column DECLARING a lower k than its evidence supports (laundering strength) → hard ✗. The receipt is
only as strong as its cheapest falsehood path, so the rollup reports the MINIMUM k across columns.

Dependency-free (Python stdlib); the Ed25519 verify is vendored (read it). Input is a file or URL;
columns are found at `.columns` / `.payload.columns` / `.document.columns`. Optional
`columns_sha256` (= sha256(JCS(columns))) binds the whole set.

Usage:
    python3 columns-verify.py <file-or-url>
Exit: 0 = every verifiable column checks out and none over-claims k (testimony never fails) · 1 = a
column failed to reproduce, a signature failed, or a column claimed more strength than it can back.
"""
import sys
import json
import hashlib
import base64
import urllib.request


# ===================== vendored Ed25519 verify (RFC 8032 reference) =====================
# Verify-only, no secret handling. Vendored so this tool trusts no compiled crypto library —
# an auditor reads it. (Same implementation as the touchstone-verify package, 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
# ======================================================================================


# --- clean-room JCS canonicalization (RFC 8785 subset) — identical to verify.py ---
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)


# --- k-graded column verification: compute k from the EVIDENCE, never from the declaration ---
def _sha256_hex(b):
    return hashlib.sha256(b).hexdigest()


def _recompute(col):
    """True if a k=0 derivation reproduces the value; False if it is offered but fails; None if absent."""
    d = col.get("derivation")
    if not isinstance(d, dict):
        return None
    alg, inp = d.get("alg"), d.get("input")
    if alg == "sha256":
        if not isinstance(inp, str):
            return False
        return col.get("value") == _sha256_hex(inp.encode("utf-8"))
    if alg == "jcs-sha256":
        return col.get("value") == _sha256_hex(jcs(inp).encode("utf-8"))
    return False   # unknown alg → cannot recompute → fail closed


def _ctrl_key(w):
    """A witness's CONTROL identity: a verified controller (operator) binding if the receipt carries
    one, else its own signing key. Two witnesses collapse to one cluster iff these match. The
    controller binding is `controller = {pubkey, sig}` where the operator key signs the domain-
    separated bytes `touchstone-control:v1\\n<witness_pubkey>` — recomputable, no external lookup."""
    ctrl = w.get("controller")
    if isinstance(ctrl, dict) and ctrl.get("pubkey") and ctrl.get("sig"):
        binding = ("touchstone-control:v1\n" + str(w.get("pubkey"))).encode("utf-8")
        if ed_verify(ctrl["pubkey"], binding, ctrl["sig"]):
            return "ctrl:" + str(ctrl["pubkey"])
    return "key:" + str(w.get("pubkey"))


def _control_clusters(col):
    """Number of DISTINCT-CONTROL clusters among the valid co-signatures over the proposition. Two
    co-sigs collapse when they share a signing key OR a verified controller binding carried in the
    receipt — so five sock-puppet keys under one evidenced operator count as one. Independence the
    receipt does NOT evidence (a hidden shared controller) can only REDUCE the true count, so this is
    an UPPER bound on independent witnesses — never an over-estimate of collusion cost."""
    prop, val = col.get("proposition"), col.get("value")
    witnesses = col.get("witnesses")
    if witnesses is None and isinstance(col.get("witness"), dict):
        witnesses = [col["witness"]]
    clusters = set()
    for w in (witnesses or []):
        if not isinstance(w, dict) or not w.get("pubkey") or not w.get("sig"):
            continue
        # The signature binds the proposition, so a narrow witness cannot be reused under a wider claim.
        msg = jcs({"proposition": prop, "value": val, "challenge": w.get("challenge")}).encode("utf-8")
        if ed_verify(w["pubkey"], msg, w["sig"]):
            clusters.add(_ctrl_key(w))
    return len(clusters)


def evaluate(col):
    """Grade one column. Returns dict with ok (True/False/None), status, k, k_indep, note."""
    declared = col.get("k")
    rec = _recompute(col)
    if rec is True:
        k, k_indep, status = 0, 0, "DERIVABLE"
    elif rec is False:
        return {"ok": False, "status": "RECOMPUTE-FAILS", "k": None, "k_indep": None,
                "note": "declares a derivation but it does NOT reproduce the value"}
    else:
        clusters = _control_clusters(col)
        if clusters:
            k = 1 + clusters               # k = 1 (the attester) + distinct-control witnesses
            k_indep = k                    # no separate declared-independence axis — control IS the axis
            status = "WITNESSED"
        else:
            k, k_indep, status = 1, 1, "TESTIMONY"
    # Over-claim = declaring MORE strength than the evidence earns. Strength is NOT numeric-k:
    # k=1 is weakest (one party lies), higher k is stronger, k=0 is strongest (uncollusible) → rank
    # k=0 as infinity. Declaring k=2 for a k=1 fact, or k=0 for a witnessed one, both over-claim.
    _rank = lambda x: float("inf") if x == 0 else x
    if isinstance(declared, int) and _rank(declared) > _rank(k):
        return {"ok": False, "status": "OVER-CLAIMED", "k": k, "k_indep": k_indep,
                "note": "declares k=%d but the evidence only supports k=%d — cannot launder strength"
                        % (declared, k)}
    ok = None if status == "TESTIMONY" else True
    if status == "DERIVABLE":
        note = "recomputed from published input — no coalition can forge it"
    elif status == "WITNESSED":
        note = ("≤ %d distinct-control witness(es) co-signed the proposition (collapsed on shared "
                "key/controller); hidden shared control can only lower it" % (k - 1))
    else:
        note = "attester's word alone — believed, not checked"
    return {"ok": ok, "status": status, "k": k, "k_indep": k_indep, "note": note,
            "proposition": col.get("proposition")}


def get_json(url):
    req = urllib.request.Request(url, headers={"Accept": "application/json", "User-Agent": "columns-verify/2"})
    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 find_columns(doc):
    for path in (lambda d: d.get("columns"),
                 lambda d: (d.get("payload") or {}).get("columns"),
                 lambda d: (d.get("document") or {}).get("columns")):
        try:
            c = path(doc)
        except Exception:
            c = None
        if isinstance(c, list):
            return c, doc
    return None, doc


def _kfmt(k):
    return "?" if k is None else ("k=%d" % k)


def main(argv):
    args = [a for a in argv[1:] if not a.startswith("--")]
    if not args:
        print(__doc__)
        return 2
    doc = load(args[0])
    columns, holder = find_columns(doc)
    if columns is None:
        print("No `columns` block found (looked at .columns, .payload.columns, .document.columns).")
        return 2

    print("Touchstone receipt verifier — how many parties must collude before each column is false?\n")

    computed_digest = _sha256_hex(jcs(columns).encode("utf-8"))
    published_digest = holder.get("columns_sha256") if isinstance(holder, dict) else None
    digest_fail = bool(published_digest) and published_digest != computed_digest
    if published_digest:
        print("columns_sha256 : %s  (%s)"
              % (computed_digest, "matches published" if not digest_fail else "✗ DOES NOT MATCH published"))
    else:
        print("columns_sha256 : %s  (computed; no published value to compare)" % computed_digest)
    print()

    n_fail = 0
    min_k = None
    min_k_indep = None
    for col in columns:
        r = evaluate(col)
        mark = "·" if r["ok"] is None else ("✓" if r["ok"] else "✗")
        kd = _kfmt(r["k"])
        if r["k_indep"] is not None and r["k_indep"] != r["k"]:
            kd += "→%d" % r["k_indep"]
        print("  %s [%-14s %-6s] %-22s %s" % (mark, r["status"], kd, str(col.get("name"))[:22], r["note"]))
        if r.get("proposition"):
            print("        re-derives: \"%s\"" % str(r["proposition"])[:100])
        if r["ok"] is False:
            n_fail += 1
        # the cheapest falsehood path: min k among LOAD-BEARING columns that CAN be falsified by
        # collusion at all. A k=0 column is recomputable — no coalition can forge it — so it offers
        # no falsehood path and never lowers the minimum.
        if r["ok"] is not False and r["k"] is not None and r["k"] >= 1:
            min_k = r["k"] if min_k is None else min(min_k, r["k"])
            ki = r["k_indep"] if r["k_indep"] is not None else r["k"]
            min_k_indep = ki if min_k_indep is None else min(min_k_indep, ki)
    print()
    if n_fail == 0 and not digest_fail:
        if min_k is None:
            print("RESULT: RECEIPT COHERENT ✓ — every load-bearing column is recomputable (k=0); no "
                  "coalition can make any of them false. The strongest a receipt gets.")
            return 0
        print("RESULT: RECEIPT COHERENT ✓ — every column carries the strength it claims. Cheapest "
              "falsehood path: min k ≤ %s — AT MOST this many independent parties must collude to make "
              "a load-bearing column false; undisclosed shared control can only make it fewer (upper "
              "bound over receipt-evidenced distinct control)." % min_k)
        if min_k <= 1:
            print("        NOTE: a min k of 1 means at least one load-bearing column is testimony — the "
                  "receipt rests on someone's word there. Price it accordingly.")
        return 0
    print("RESULT: RECEIPT INCOHERENT ✗ — %d column(s) failed to back their grade%s. A column cannot "
          "borrow a strength it cannot reproduce; k is fired from the evidence, not declared."
          % (n_fail, " (and the columns digest is wrong)" if digest_fail else ""))
    return 1


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