#!/usr/bin/env python3
"""Rightshold Ledger — independent second verifier.

A second, separate implementation of the Rightshold Ledger verification
rules, written in Python from the rules the ledger states in its own first
entry. It shares no code with the Rightshold service and never asks the
service whether the chain is valid (it never calls /v1/ledger/verify):
given a daily snapshot and its signed manifest, it recomputes everything
itself — the SHA-256 of the snapshot body, the manifest's Ed25519
signature, every entry payload hash and leaf hash, every block's Merkle
root, block hash and Ed25519 signature, and the chain link from the first
block to the head — against the issuer keys published in the JSON Web Key
Set (/.well-known/jwks.json), including retired keys, which still verify
the blocks they signed.

Needs: Python 3 and the openssl command-line tool (for Ed25519). Nothing
else; the standard library does the rest.

Usage:
  python3 verify-ledger.py                      Verify the latest daily snapshot (fetched).
  python3 verify-ledger.py --day 2026-10-23     Verify one day's snapshot (fetched).
  python3 verify-ledger.py --snapshot body.json --manifest manifest.json [--jwks jwks.json]
                                                Verify local files (fully offline when
                                                --jwks names a saved key set).
  python3 verify-ledger.py --conformance [source]
                                                Run the published verifier conformance
                                                vectors (a URL or a local file; default the
                                                published document) and report per vector.

Exit code is 0 only when every check passes. The Bitcoin anchor state is
reported exactly as the snapshot carries it; this program does not fetch
anchor proofs.
"""

import base64
import hashlib
import json
import os
import subprocess
import sys
import tempfile
import urllib.request
import urllib.parse
import http.client

DEFAULT_BASE = "https://www.rightshold.com"
GENESIS_PREV = "0" * 64
# DER prefix of an Ed25519 SubjectPublicKeyInfo: SEQUENCE { SEQUENCE { OID 1.3.101.112 }, BIT STRING }.
SPKI_PREFIX = bytes.fromhex("302a300506032b6570032100")

CHECKS = [
    "manifest.consistency",
    "manifest.body_sha256",
    "manifest.signature",
    "snapshot.head",
    "chain.height_sequence",
    "chain.prev_link",
    "entry.payload_hash",
    "entry.leaf_hash",
    "block.entry_count",
    "block.merkle_root",
    "block.hash",
    "block.key_published",
    "block.signature",
]


# ---------- canonical JSON (the ledger's stated rule: keys sorted, no whitespace, UTF-8) ----------

def _js_number(x: float) -> str:
    """Format a float the way JSON.stringify does (ECMAScript Number::toString)."""
    if x != x:
        return "NaN"
    if x in (float("inf"), float("-inf")):
        return "Infinity" if x > 0 else "-Infinity"
    if x == 0:
        return "0"
    sign = "-" if x < 0 else ""
    ax = abs(x)
    if ax == int(ax) and ax < 1e21:
        return sign + str(int(ax))
    r = repr(ax)
    if "e" in r or "E" in r:
        mant, _, e = r.replace("E", "e").partition("e")
        exp = int(e)
        ip, _, fp = mant.partition(".")
        digits = ip + fp
        k = exp - len(fp)
    else:
        ip, _, fp = r.partition(".")
        if ip != "0":
            digits = ip + fp
            k = -len(fp)
        else:
            zeros = len(fp) - len(fp.lstrip("0"))
            digits = fp.lstrip("0")
            k = -(zeros + len(digits))
    digits = digits.lstrip("0")
    while digits.endswith("0"):
        digits = digits[:-1]
        k += 1
    n = k + len(digits)  # value = 0.<digits> * 10**n
    if 0 < n <= 21:
        if n >= len(digits):
            return sign + digits + "0" * (n - len(digits))
        return sign + digits[:n] + "." + digits[n:]
    if -6 < n <= 0:
        return sign + "0." + "0" * (-n) + digits
    mant = digits[0] + ("." + digits[1:] if len(digits) > 1 else "")
    e = n - 1
    return sign + mant + "e" + ("+" if e >= 0 else "-") + str(abs(e))


def canonical(v) -> str:
    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):
        return _js_number(v)
    if isinstance(v, str):
        return json.dumps(v, ensure_ascii=False)
    if isinstance(v, list):
        return "[" + ",".join(canonical(i) for i in v) + "]"
    if isinstance(v, dict):
        return "{" + ",".join(
            json.dumps(k, ensure_ascii=False) + ":" + canonical(v[k]) for k in sorted(v.keys())
        ) + "}"
    raise TypeError(f"cannot canonicalize {type(v)}")


def sha256_hex(data) -> str:
    if isinstance(data, str):
        data = data.encode("utf-8")
    return hashlib.sha256(data).hexdigest()


# ---------- Ed25519 via openssl ----------

def _b64url_decode(s: str) -> bytes:
    return base64.urlsafe_b64decode(s + "=" * (-len(s) % 4))


def _pem_raw_key(pem: str) -> bytes:
    body = "".join(line.strip() for line in pem.splitlines() if line.strip() and "-----" not in line)
    der = base64.b64decode(body)
    return der[-32:]


def ed25519_verify(raw_key: bytes, message: bytes, signature: bytes) -> bool:
    der = SPKI_PREFIX + raw_key
    with tempfile.TemporaryDirectory(prefix="rh-verify-") as td:
        key_f = os.path.join(td, "key.der")
        msg_f = os.path.join(td, "msg.bin")
        sig_f = os.path.join(td, "sig.bin")
        with open(key_f, "wb") as f:
            f.write(der)
        with open(msg_f, "wb") as f:
            f.write(message)
        with open(sig_f, "wb") as f:
            f.write(signature)
        r = subprocess.run(
            ["openssl", "pkeyutl", "-verify", "-pubin", "-keyform", "DER",
             "-inkey", key_f, "-rawin", "-in", msg_f, "-sigfile", sig_f],
            capture_output=True, timeout=30,
        )
    return r.returncode == 0


# ---------- key set ----------

class KeySet:
    """The published issuer keys, by key id, with their status. Retired keys still verify
    the blocks they signed; a revoked or unknown key verifies nothing."""

    def __init__(self, jwks: dict):
        self.keys = {}
        for k in jwks.get("keys", []):
            if k.get("kty") == "OKP" and k.get("crv") == "Ed25519" and "x" in k:
                self.keys[k["kid"]] = {"raw": _b64url_decode(k["x"]), "status": k.get("status", "?")}

    def raw(self, kid):
        e = self.keys.get(kid)
        return e["raw"] if e else None

    def status(self, kid):
        e = self.keys.get(kid)
        return e["status"] if e else None


# ---------- chain verification ----------

def header_of(b: dict) -> dict:
    return {
        "v": b["v"], "height": b["height"], "prev_hash": b["prev_hash"],
        "merkle_root": b["merkle_root"], "first_seq": b["first_seq"],
        "last_seq": b["last_seq"], "entry_count": b["entry_count"],
        "at": b["at"], "key_id": b["key_id"],
    }


def leaf_hash(e: dict) -> str:
    return sha256_hex("leaf:" + canonical({
        "seq": e["seq"], "at": e["at"], "type": e["type"],
        "subject": e["subject"], "payload_hash": e["payload_hash"],
    }))


def merkle_root(leaves) -> str:
    if not leaves:
        return sha256_hex("empty")
    level = list(leaves)
    while len(level) > 1:
        nxt = []
        for i in range(0, len(level), 2):
            nxt.append(sha256_hex("node:" + level[i] + level[i + 1]) if i + 1 < len(level) else level[i])
        level = nxt
    return level[0]


class Report:
    def __init__(self):
        self.results = {}  # check -> (ok, detail)
        self.notes = []

    def fail(self, check, detail):
        if check not in self.results:
            self.results[check] = (False, detail)

    def passed(self, check, detail):
        if check not in self.results:
            self.results[check] = (True, detail)

    def ok(self):
        return all(self.results.get(c, (False, "not run"))[0] for c in CHECKS)


def verify_snapshot(manifest: dict, body_bytes: bytes, body: dict, keys: KeySet) -> Report:
    rep = Report()

    # manifest.consistency — the signed statement must match the manifest around it,
    # and the body must be the day the manifest names.
    signed = None
    try:
        signed = json.loads(manifest.get("signed_bytes", ""))
    except Exception:
        pass
    fields = ["day", "head_hash", "head_height", "issuer", "key_id", "sha256"]
    if signed is None:
        rep.fail("manifest.consistency", "signed_bytes does not parse as JSON")
    elif any(signed.get(f) != manifest.get(f) for f in fields):
        bad = [f for f in fields if signed.get(f) != manifest.get(f)]
        rep.fail("manifest.consistency", "signed statement disagrees with the manifest on: " + ", ".join(bad))
    elif body.get("day") != manifest.get("day") or body.get("cutoff") != manifest.get("cutoff"):
        rep.fail("manifest.consistency", "snapshot body day/cutoff do not match the manifest")
    else:
        rep.passed("manifest.consistency", "signed statement, manifest and snapshot body agree")

    # manifest.body_sha256 — over the body bytes exactly as received.
    digest = sha256_hex(body_bytes)
    if digest == manifest.get("sha256"):
        rep.passed("manifest.body_sha256", "sha256 of the snapshot body matches the manifest")
    else:
        rep.fail("manifest.body_sha256", f"sha256 of the snapshot body is {digest}, the manifest says {manifest.get('sha256')}")

    # manifest.signature — Ed25519 over signed_bytes under the manifest's key.
    mkid = manifest.get("key_id")
    mraw = keys.raw(mkid) if mkid else None
    if mraw is None:
        rep.fail("manifest.signature", f"manifest key {mkid} is not in the published key set")
    elif keys.status(mkid) == "revoked":
        rep.fail("manifest.signature", f"manifest key {mkid} is revoked")
    else:
        try:
            sig = base64.b64decode(manifest.get("signature", ""))
            ok = ed25519_verify(mraw, str(manifest.get("signed_bytes", "")).encode("utf-8"), sig)
        except Exception:
            ok = False
        if ok:
            rep.passed("manifest.signature", f"Ed25519 signature verifies under {mkid} ({keys.status(mkid)})")
        else:
            rep.fail("manifest.signature", "Ed25519 signature over signed_bytes does not verify")

    blocks = body.get("blocks")
    if not isinstance(blocks, list) or not blocks:
        for c in CHECKS[3:]:
            rep.fail(c, "snapshot body carries no blocks")
        return rep

    # snapshot.head — the body's last block must be the head the manifest names.
    head = blocks[-1].get("block", {})
    if head.get("height") == manifest.get("head_height") and head.get("block_hash") == manifest.get("head_hash") \
            and (manifest.get("blocks") is None or len(blocks) == manifest.get("blocks")):
        rep.passed("snapshot.head", f"body head is block {head.get('height')}, the head the manifest names")
    else:
        rep.fail("snapshot.head",
                 f"body head is height {head.get('height')} hash {head.get('block_hash')}, "
                 f"the manifest names height {manifest.get('head_height')} hash {manifest.get('head_hash')} "
                 f"across {manifest.get('blocks')} block(s); the body carries {len(blocks)}")

    prev = GENESIS_PREV
    total_entries = 0
    for i, item in enumerate(blocks):
        b = item.get("block", {})
        es = item.get("entries", [])
        h = b.get("height")
        if h != i:
            rep.fail("chain.height_sequence", f"block at position {i} carries height {h}")
        if b.get("prev_hash") != prev:
            rep.fail("chain.prev_link", f"block {h}: prev_hash does not name block {i - 1}'s hash")
        leaves = []
        for e in es:
            if sha256_hex(canonical(e.get("payload"))) != e.get("payload_hash"):
                rep.fail("entry.payload_hash", f"entry {e.get('seq')}: payload hash does not recompute")
            lh = leaf_hash(e)
            if lh != e.get("leaf_hash"):
                rep.fail("entry.leaf_hash", f"entry {e.get('seq')}: leaf hash does not recompute")
            leaves.append(lh)
        total_entries += len(es)
        if len(es) != b.get("entry_count") or (es and (es[0].get("seq") != b.get("first_seq") or es[-1].get("seq") != b.get("last_seq"))):
            rep.fail("block.entry_count", f"block {h}: entry_count/first_seq/last_seq disagree with the entries carried")
        if merkle_root(leaves) != b.get("merkle_root"):
            rep.fail("block.merkle_root", f"block {h}: Merkle root does not recompute from the entry leaf hashes")
        hdr = header_of(b)
        if sha256_hex("block:" + canonical(hdr)) != b.get("block_hash"):
            rep.fail("block.hash", f"block {h}: block hash does not recompute from the header")
        raw = keys.raw(b.get("key_id"))
        if raw is None:
            rep.fail("block.key_published", f"block {h}: key {b.get('key_id')} is not in the published key set")
        elif keys.status(b.get("key_id")) == "revoked":
            rep.fail("block.key_published", f"block {h}: key {b.get('key_id')} is revoked")
        else:
            try:
                pem_raw = _pem_raw_key(str(b.get("public_key_pem", "")))
            except Exception:
                pem_raw = None
            if pem_raw != raw:
                rep.fail("block.key_published", f"block {h}: the public key inside the block differs from the published key {b.get('key_id')}")
            else:
                rep.passed("block.key_published", "every block's key is the published key for its id")
                try:
                    sig = base64.b64decode(b.get("signature", ""))
                    ok = ed25519_verify(raw, canonical(hdr).encode("utf-8"), sig)
                except Exception:
                    ok = False
                if not ok:
                    rep.fail("block.signature", f"block {h}: Ed25519 signature over the header does not verify")
        prev = b.get("block_hash")

    rep.passed("chain.height_sequence", f"{len(blocks)} blocks at heights 0..{len(blocks) - 1}")
    rep.passed("chain.prev_link", "every block names the hash of the block before it, back to the genesis prev-hash")
    rep.passed("entry.payload_hash", f"all {total_entries} entry payload hashes recompute")
    rep.passed("entry.leaf_hash", f"all {total_entries} entry leaf hashes recompute")
    rep.passed("block.entry_count", "entry counts and sequence ranges match the entries carried")
    rep.passed("block.merkle_root", "every block's Merkle root recomputes")
    rep.passed("block.hash", "every block hash recomputes from its header")
    rep.passed("block.signature", "every block signature verifies under its published key")

    rep.notes.append(
        "Anchors: " + (
            "the manifest carries Bitcoin anchor state: " + json.dumps(manifest["anchors"])
            if "anchors" in manifest else
            "the snapshot manifest carries no Bitcoin anchor state; per-block anchor proofs are "
            "published separately by the service and are not part of what a snapshot attests."
        )
    )
    rep.notes.append(f"Counts: {len(blocks)} blocks, {total_entries} entries, head height {head.get('height')}.")
    return rep


def print_report(rep: Report, title: str) -> bool:
    print(title)
    for c in CHECKS:
        ok, detail = rep.results.get(c, (False, "not run"))
        print(f"[{'PASS' if ok else 'FAIL'}] {c} — {detail}")
    for n in rep.notes:
        print("  " + n)
    ok = rep.ok()
    print("VERDICT: " + ("PASS" if ok else "FAIL"))
    return ok


# ---------- fetching ----------

class _Redirect(Exception):
    def __init__(self, url):
        super().__init__(url)
        self.url = url


def _fetch_once(url: str) -> bytes:
    """One GET via http.client: a plain HTTP/1.1 request with no
    `Connection: close` header, honouring http_proxy/https_proxy
    environment variables the way urllib does (CONNECT tunnel for
    https). Raises on any non-200 status or short read."""
    parts = urllib.parse.urlsplit(url)
    if parts.scheme not in ("http", "https"):
        raise RuntimeError(f"unsupported URL scheme: {parts.scheme}")
    host = parts.hostname
    port = parts.port or (443 if parts.scheme == "https" else 80)
    path = parts.path or "/"
    if parts.query:
        path += "?" + parts.query
    headers = {"user-agent": "rightshold-second-verifier/1", "accept-encoding": "identity"}
    proxies = urllib.request.getproxies()
    proxy = None if urllib.request.proxy_bypass(host) else (proxies.get(parts.scheme) or proxies.get("all"))
    conn = None
    try:
        if proxy:
            p = urllib.parse.urlsplit(proxy if "//" in proxy else "//" + proxy)
            auth = None
            if p.username:
                auth = "Basic " + base64.b64encode(
                    (urllib.parse.unquote(p.username) + ":" + urllib.parse.unquote(p.password or "")).encode()
                ).decode()
            if parts.scheme == "https":
                conn = http.client.HTTPSConnection(p.hostname, p.port or 8080, timeout=60)
                conn.set_tunnel(host, port, headers={"proxy-authorization": auth} if auth else None)
            else:
                conn = http.client.HTTPConnection(p.hostname, p.port or 8080, timeout=60)
                if auth:
                    headers["proxy-authorization"] = auth
                path = url  # absolute-form for a plain-http proxy request
        elif parts.scheme == "https":
            conn = http.client.HTTPSConnection(host, port, timeout=60)
        else:
            conn = http.client.HTTPConnection(host, port, timeout=60)
        conn.request("GET", path, headers=headers)
        resp = conn.getresponse()
        if resp.status in (301, 302, 303, 307, 308):
            location = resp.getheader("location")
            resp.read()
            if location:
                raise _Redirect(urllib.parse.urljoin(url, location))
            raise RuntimeError(f"GET {url} -> HTTP {resp.status} (redirect without a location)")
        if resp.status != 200:
            raise RuntimeError(f"GET {url} -> HTTP {resp.status}")
        return resp.read()
    finally:
        if conn is not None:
            try:
                conn.close()
            except Exception:
                pass


def fetch(url: str) -> bytes:
    """Fetch a URL with the standard library only.

    Deliberately not urllib.request.urlopen: urllib always sends a
    `Connection: close` request header, and some serving paths cut
    large chunked responses short for such clients (seen in production
    as IncompleteRead on the ~295 KB ledger snapshot and intermittent
    failures on the conformance vectors and /v1/status).
    http.client sends no such header and reads the framed body to
    its end. A truncated or dropped read is retried on a fresh
    connection, and the last error is raised if every attempt fails,
    so a short read can never be mistaken for a complete body.
    """
    last = None
    redirects = 0
    for _attempt in range(5):
        try:
            return _fetch_once(url)
        except _Redirect as r:
            redirects += 1
            if redirects > 3:
                raise RuntimeError(f"too many redirects fetching {url}")
            url = r.url
        except Exception as e:
            last = e
    raise RuntimeError(f"fetch failed for {url}: {last}")


def fetch_json(url: str):
    return json.loads(fetch(url).decode("utf-8"))


# ---------- modes ----------

def run_snapshot_mode(args) -> int:
    base = args.base.rstrip("/")
    if args.snapshot:
        body_bytes = open(args.snapshot, "rb").read()
        manifest = json.loads(open(args.manifest, encoding="utf-8").read())
        body = json.loads(body_bytes.decode("utf-8"))
        if args.jwks:
            jwks = json.loads(open(args.jwks, encoding="utf-8").read())
            src = "local files"
        else:
            jwks = fetch_json(base + "/.well-known/jwks.json")
            src = "local snapshot, published key set"
    else:
        q = f"?day={args.day}" if args.day else ""
        manifest = fetch_json(base + "/v1/ledger/snapshot" + q)
        body_bytes = fetch(base + "/v1/ledger/snapshot.json" + q)
        body = json.loads(body_bytes.decode("utf-8"))
        jwks = fetch_json(base + "/.well-known/jwks.json")
        src = base
    rep = verify_snapshot(manifest, body_bytes, body, KeySet(jwks))
    ok = print_report(rep, f"Rightshold Ledger — independent second verifier\nSnapshot day {manifest.get('day')} (source: {src})")
    return 0 if ok else 1


def run_conformance_mode(args) -> int:
    base = args.base.rstrip("/")
    src = args.conformance
    if src is True or src is None:
        doc = fetch_json(base + "/v1/conformance/vectors")
        label = base + "/v1/conformance/vectors"
    elif os.path.exists(src):
        doc = json.loads(open(src, encoding="utf-8").read())
        label = src
    else:
        doc = fetch_json(src)
        label = src
    print(f"Verifier conformance vectors — {label}")
    print(f"Document version {doc.get('version')}; {1 + len(doc.get('tampered', []))} vectors.")
    all_ok = True

    def one(name, vec):
        nonlocal all_ok
        snap = vec["snapshot"]
        body = snap["body"]
        body_bytes = canonical(body).encode("utf-8")
        rep = verify_snapshot(snap["manifest"], body_bytes, body, KeySet(vec["jwks"]))
        failed = [c for c in CHECKS if not rep.results.get(c, (False, ""))[0]]
        expect = vec["expect"]
        if expect == "pass":
            good = rep.ok()
            exp = vec.get("expected", {})
            head = body["blocks"][-1]["block"] if body.get("blocks") else {}
            n_entries = sum(len(x.get("entries", [])) for x in body.get("blocks", []))
            if exp:
                good = good and exp.get("head_height") == head.get("height") and exp.get("head_hash") == head.get("block_hash") \
                    and exp.get("blocks") == len(body.get("blocks", [])) and exp.get("entries") == n_entries
            print(f"[{'PASS' if good else 'FAIL'}] {name} — expected a fully verifying chain"
                  + ("" if good else f"; failing checks: {', '.join(failed) or 'expected outcomes differ'}"))
            all_ok = all_ok and good
        else:
            want = vec.get("expect_failing_checks", [])
            missing = [c for c in want if c not in failed]
            good = bool(failed) and not missing
            print(f"[{'PASS' if good else 'FAIL'}] {name} — expected rejection at {', '.join(want) or 'any check'}"
                  f"; the verifier failed: {', '.join(failed) or 'nothing'}"
                  + ("" if good else " — expected failures missing"))
            all_ok = all_ok and good

    one("known-good", doc["known_good"])
    for vec in doc.get("tampered", []):
        one(vec["id"], vec)
    print("VERDICT: " + ("PASS — the verifier accepts the good chain and rejects every altered one at the named check"
                         if all_ok else "FAIL"))
    return 0 if all_ok else 1


def main(argv) -> int:
    class Args:
        base = DEFAULT_BASE
        day = None
        snapshot = None
        manifest = None
        jwks = None
        conformance = None

    args = Args()
    i = 0
    while i < len(argv):
        a = argv[i]
        if a == "--base":
            i += 1; args.base = argv[i]
        elif a == "--day":
            i += 1; args.day = argv[i]
        elif a == "--snapshot":
            i += 1; args.snapshot = argv[i]
        elif a == "--manifest":
            i += 1; args.manifest = argv[i]
        elif a == "--jwks":
            i += 1; args.jwks = argv[i]
        elif a == "--conformance":
            if i + 1 < len(argv) and not argv[i + 1].startswith("--"):
                i += 1; args.conformance = argv[i]
            else:
                args.conformance = True
        elif a in ("-h", "--help"):
            print(__doc__)
            return 0
        else:
            print(f"unknown argument: {a}\n\n{__doc__}", file=sys.stderr)
            return 2
        i += 1
    try:
        if args.conformance is not None:
            return run_conformance_mode(args)
        if args.snapshot and not args.manifest:
            print("--snapshot needs --manifest", file=sys.stderr)
            return 2
        return run_snapshot_mode(args)
    except FileNotFoundError as e:
        print(f"file not found: {e.filename}", file=sys.stderr)
        return 2
    except Exception as e:
        print(f"could not run: {e}", file=sys.stderr)
        return 2


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