verifier_core.py

"""
verifier_core.py — Deterministic computational-verification engine.

This module is intentionally CAP-agnostic: no network, no SDK, no side effects.
It takes a request dict and returns a deterministic, hashable result dict.
Same input -> same output -> same content hash. That determinism is what makes
the delivery verifiable by anyone (re-run and compare the hash).

This is where YOUR edge plugs in. The reference implementations below are
pure-stdlib (Miller-Rabin + Pollard rho-Brent) so the skeleton runs anywhere,
but the FACTOR_ENGINE / PRIME_ENGINE hooks let you swap in your GPU factoring,
factordb cross-checks, ECM, etc. without touching the CAP layer.

Input is normalized before dispatch (see normalize_request): real requesters
wrap payloads in {"text": "..."}, use field synonyms (task/number/value), or
phrase the request in prose ("is 97 prime?"). The normalizer maps those onto
the canonical {op, n, factors} schema WITHOUT touching the math or the output
format, so canonical requests are byte-identical to before and only loose
inputs gain tolerance. Genuinely empty/garbage input still hits the error path.
"""

from __future__ import annotations

import hashlib
import json
import math
import random
import time
from typing import Any

# ---------------------------------------------------------------------------
# Primality (Miller-Rabin). Deterministic for n < 3.317e24 with these witnesses.
# ---------------------------------------------------------------------------

_DETERMINISTIC_WITNESSES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)


def is_probable_prime(n: int, rounds: int = 40) -> bool:
    if n < 2:
        return False
    for p in _DETERMINISTIC_WITNESSES:
        if n % p == 0:
            return n == p
    d = n - 1
    r = 0
    while d % 2 == 0:
        d //= 2
        r += 1

    def _witness(a: int) -> bool:
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            return False
        for _ in range(r - 1):
            x = (x * x) % n
            if x == n - 1:
                return False
        return True  # composite

    # Deterministic band
    if n < 3_317_044_064_679_887_385_961_981:
        return not any(_witness(a) for a in _DETERMINISTIC_WITNESSES)
    # Probabilistic fallback for very large n
    for _ in range(rounds):
        a = random.randrange(2, n - 1)
        if _witness(a):
            return False
    return True


# ---------------------------------------------------------------------------
# Factorization (Pollard rho-Brent + trial division). Reference engine.
# ---------------------------------------------------------------------------

def _pollard_rho_brent(n: int) -> int:
    if n % 2 == 0:
        return 2
    if n % 3 == 0:
        return 3
    while True:
        y, c, m = random.randrange(1, n), random.randrange(1, n), random.randrange(1, n)
        g = q = r = 1
        x = ys = y
        while g == 1:
            x = y
            for _ in range(r):
                y = (y * y + c) % n
            k = 0
            while k < r and g == 1:
                ys = y
                for _ in range(min(m, r - k)):
                    y = (y * y + c) % n
                    q = (q * abs(x - y)) % n
                g = math.gcd(q, n)
                k += m
            r *= 2
        if g == n:
            g = 1
            while g == 1:
                ys = (ys * ys + c) % n
                g = math.gcd(abs(x - ys), n)
        if g != n:
            return g


def factorize(n: int) -> list[int]:
    """Return sorted prime factors with multiplicity. Reference engine.

    >>> SWAP POINT <<<  Replace the body with a call to your GPU/ECM/factordb
    engine for large inputs. The contract is: return a list whose product == n
    and every element passes is_probable_prime.
    """
    if n <= 1:
        return []
    factors: list[int] = []
    stack = [n]
    while stack:
        m = stack.pop()
        if m == 1:
            continue
        if is_probable_prime(m):
            factors.append(m)
            continue
        d = _pollard_rho_brent(m)
        stack.append(d)
        stack.append(m // d)
    factors.sort()
    return factors


# ---------------------------------------------------------------------------
# Canonical serialization + content hash (the verifiable attestation).
# ---------------------------------------------------------------------------

def canonical_json(obj: Any) -> str:
    """Deterministic JSON: sorted keys, no insignificant whitespace."""
    return json.dumps(obj, sort_keys=True, separators=(",", ":"), default=str)


def _content_hash(payload: dict[str, Any]) -> str:
    return "sha256:" + hashlib.sha256(canonical_json(payload).encode()).hexdigest()


# ---------------------------------------------------------------------------
# Input normalization. Maps loose/real-world requests onto the canonical schema
# {op, n, factors} without touching the math engine or the output format.
# Unresolvable input is returned untouched so existing error paths still fire.
# ---------------------------------------------------------------------------

_OP_ALIASES = {
    "verify_prime": "verify_prime", "is_prime": "verify_prime", "isprime": "verify_prime",
    "prime": "verify_prime", "primality": "verify_prime",
    "primality_verification": "verify_prime", "prime_proof": "verify_prime",
    "factor": "factor", "factorize": "factor", "factorization": "factor",
    "full_factorization": "factor",
    "verify_factorization": "verify_factorization", "audit": "verify_factorization",
    "factor_audit": "verify_factorization", "audit_factorization": "verify_factorization",
}
_OP_KEYS = ("op", "operation", "task", "mode", "type", "action")
_N_KEYS = ("n", "number", "value", "integer", "input", "num")
_FACTORS_KEYS = ("factors", "claimed_factors", "claim")


def _coerce_op(raw: str) -> str:
    """Map a free-form op/task string onto a canonical op, else ''."""
    s = str(raw or "").strip().lower().replace(" ", "_")
    if s in _OP_ALIASES:
        return _OP_ALIASES[s]
    if "factoriz" in s or "factorise" in s:
        return "verify_factorization" if "audit" in s else "factor"
    if "prime" in s or "primality" in s:
        return "verify_prime"
    if "audit" in s:
        return "verify_factorization"
    return ""


def _first_int_in(text: str) -> str:
    """Extract the longest contiguous integer run from arbitrary text."""
    cur = best = ""
    for ch in str(text):
        if ch.isdigit():
            cur += ch
        else:
            if len(cur) > len(best):
                best = cur
            cur = ""
    if len(cur) > len(best):
        best = cur
    return best


def normalize_request(request: dict[str, Any]) -> dict[str, Any]:
    """Best-effort mapping of a loose request dict onto the canonical schema.

    Handles: {"text": "<json or prose>"} envelopes, field synonyms
    (task/number/value/...), prose intent ("is 97 prime?"), and bare numbers.
    Never raises; returns the original request if nothing is resolvable, so the
    downstream unsupported_op / bad_request handling stays intact.
    """
    if not isinstance(request, dict):
        return request
    req = dict(request)

    # 1) Unwrap {"text": "..."} envelopes (inner may be JSON or prose).
    if {k.lower() for k in req.keys()} == {"text"}:
        inner = next(iter(req.values()))
        if isinstance(inner, str):
            stripped = inner.strip()
            parsed = None
            if stripped.startswith("{"):
                try:
                    parsed = json.loads(stripped)
                except (ValueError, TypeError):
                    parsed = None
            if isinstance(parsed, dict):
                req = parsed
            else:
                op = _coerce_op(stripped)
                num = _first_int_in(stripped)
                req = {}
                if op:
                    req["op"] = op
                if num:
                    req["n"] = num

    # 2) Resolve op from any synonym key, else sniff prose across all values.
    op_val = ""
    for k in _OP_KEYS:
        if k in req and str(req[k]).strip():
            op_val = _coerce_op(req[k])
            if op_val:
                break
    if not op_val:
        op_val = _coerce_op(" ".join(str(v) for v in req.values()))

    # 3) Resolve n from any synonym key, else first integer found anywhere.
    n_val = ""
    for k in _N_KEYS:
        if k in req and str(req[k]).strip():
            n_val = str(req[k]).strip()
            break
    if not n_val:
        n_val = _first_int_in(" ".join(str(v) for v in req.values()))

    # 4) Resolve factors (for audits) from any synonym key.
    factors_val = None
    for k in _FACTORS_KEYS:
        if k in req and isinstance(req[k], (list, tuple)):
            factors_val = list(req[k])
            break

    # 5) Default op: a number with no clear op -> factor (most informative),
    #    or verify_factorization when factors are also present.
    if not op_val and n_val:
        op_val = "verify_factorization" if factors_val else "factor"

    out: dict[str, Any] = {}
    if op_val:
        out["op"] = op_val
    if n_val:
        out["n"] = n_val
    if factors_val is not None:
        out["factors"] = factors_val
    return out or request


# ---------------------------------------------------------------------------
# Request dispatch. This is the agent's public "skill" surface.
# ---------------------------------------------------------------------------

SUPPORTED_OPS = ("verify_prime", "factor", "verify_factorization")


def compute_result(request: dict[str, Any]) -> dict[str, Any]:
    """Pure function: request dict -> deterministic result dict (with hash + log).

    Accepts the canonical schema directly, or any loose form that
    normalize_request can map onto it:
      {"op": "verify_prime",         "n": "<int as string>"}
      {"op": "factor",               "n": "<int as string>"}
      {"op": "verify_factorization", "n": "<int>", "factors": ["<int>", ...]}
    """
    log: list[str] = []
    t0 = time.perf_counter()

    # Normalize loose/real-world input onto the canonical schema first.
    raw_keys = sorted(request.keys()) if isinstance(request, dict) else []
    request = normalize_request(request)
    op = str(request.get("op", "")).strip()
    if op:
        log.append(f"normalized(keys={raw_keys} -> op={op})")

    try:
        if op == "verify_prime":
            n = int(str(request["n"]))
            log.append(f"miller_rabin(n={n}, digits={len(str(n))})")
            verdict = is_probable_prime(n)
            payload = {
                "op": op,
                "n": str(n),
                "is_prime": verdict,
                "method": "miller-rabin",
                "deterministic_band": n < 3_317_044_064_679_887_385_961_981,
            }

        elif op == "factor":
            n = int(str(request["n"]))
            log.append(f"factorize(n={n}, digits={len(str(n))})")
            factors = factorize(n)
            product_ok = (math.prod(factors) == n) if factors else (n == 1)
            all_prime = all(is_probable_prime(f) for f in factors)
            payload = {
                "op": op,
                "n": str(n),
                "factors": [str(f) for f in factors],
                "product_check": product_ok,
                "all_factors_prime": all_prime,
                "verified": bool(product_ok and all_prime),
                "method": "pollard-rho-brent + miller-rabin",
            }

        elif op == "verify_factorization":
            n = int(str(request["n"]))
            claimed = [int(str(f)) for f in request.get("factors", [])]
            log.append(f"verify_factorization(n={n}, k={len(claimed)} factors)")
            product = math.prod(claimed) if claimed else 0
            product_ok = product == n
            primality = {str(f): is_probable_prime(f) for f in claimed}
            all_prime = all(primality.values())
            payload = {
                "op": op,
                "n": str(n),
                "claimed_factors": [str(f) for f in claimed],
                "product": str(product),
                "product_check": product_ok,
                "factor_primality": primality,
                "all_factors_prime": all_prime,
                "verified": bool(product_ok and all_prime),
                "method": "exact-product + miller-rabin",
            }

        else:
            payload = {
                "op": op or "(missing)",
                "error": "unsupported_op",
                "supported_ops": list(SUPPORTED_OPS),
                "hint": 'send {"op":"factor","n":"600851475143"} or '
                        '{"op":"verify_prime","n":"97"}',
            }
    except (KeyError, ValueError, TypeError) as e:
        payload = {"op": op or "(missing)", "error": "bad_request", "detail": str(e)}

    elapsed_ms = round((time.perf_counter() - t0) * 1000, 3)
    log.append(f"elapsed_ms={elapsed_ms}")

    # The attestation: hash is computed over the payload only, so any verifier
    # can re-run compute_result, strip {hash, execution_log}, and compare.
    result = dict(payload)
    result["execution_log"] = log
    result["content_hash"] = _content_hash(payload)
    return result


if __name__ == "__main__":
    # Tiny self-test / demo
    import pprint
    for req in [
        {"op": "verify_prime", "n": "1000000000000000000000000000057"},  # large prime
        {"op": "factor", "n": "600851475143"},                          # Project Euler #3
        {"op": "verify_factorization", "n": "13195", "factors": ["5", "7", "13", "29"]},
        {"op": "factor", "n": "9999999900000001"},
        {"op": "bogus"},
        # loose / real-world forms now handled by normalize_request:
        {"text": '{"task":"primality_verification","number":"32416190071"}'},
        {"text": "is 7919 prime?"},
        {"text": "600851475143"},
        {"operation": "factorize", "number": "13195"},
    ]:
        print("REQUEST:", req)
        pprint.pp(compute_result(req))
        print("-" * 70)