#!/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 a counterparty co-signature over the PROPOSITION it re-derives
                       ({proposition, value, challenge}). k = 1 + (valid independent co-signatures): one
                       counterparty → k=2, a t-of-n beacon → k=t. The verifier checks each signature.
  - k = 1  TESTIMONY   the attester's word alone; no independent mechanism left a durable byproduct.
                       Displayed, never counted as verified.

Two things the thread this came from (anp2network / colonist-one, 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.
  • k counts the SIZE of the required conspiracy, not its LIKELIHOOD. A co-signer with a stake in the
    answer still makes k=2 structurally, but doesn't buy independence — so we report an
    independence-adjusted k that discounts conflicted co-signers back toward k=1.

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 _cosigs(col):
    """Valid counterparty signatures over the PROPOSITION. Returns [(sub, independent_bool), ...]."""
    prop = col.get("proposition")
    val = col.get("value")
    witnesses = col.get("witnesses")
    if witnesses is None and isinstance(col.get("witness"), dict):
        witnesses = [col["witness"]]
    out = []
    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, not just the value — so a narrow witness cannot be
        # reused under a wider claim (change the proposition and the signature no longer verifies).
        msg = jcs({"proposition": prop, "value": val, "challenge": w.get("challenge")}).encode("utf-8")
        if ed_verify(w["pubkey"], msg, w["sig"]):
            independent = w.get("independence", "independent") in (None, "independent")
            out.append((w.get("sub") or "witness", independent))
    return out


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:
        cs = _cosigs(col)
        if cs:
            k = 1 + len(cs)
            k_indep = 1 + sum(1 for _, ind in cs if ind)
            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 counterparty co-signature(s) over the proposition" % (k - 1)
        if k_indep < k:
            note += "; %d have a stake in the answer → independence-adjusted k=%d" % (k - k_indep, k_indep)
    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
        adj = "" if (min_k_indep == min_k) else " (independence-adjusted k=%s)" % min_k_indep
        print("RESULT: RECEIPT COHERENT ✓ — every column carries the strength it claims. Cheapest "
              "falsehood path: min k=%s%s — the fewest parties who must collude to make any load-bearing "
              "column false." % (min_k, adj))
        if min_k_indep is not None and min_k_indep <= 1:
            print("        NOTE: a min k of 1 means at least one load-bearing column is testimony or a "
                  "conflicted witness — 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))