verifying-crypto-with-lean/check-book.py

#!/usr/bin/env python3
"""check-book.py — the measured half of the book's button (see check-book.sh).

Every check compares a claim PRINTED IN THE BOOK against a value MEASURED
from the sources, the built PDF, or the sibling repositories at the moment
it runs. No expected value is carried in this file when it can be derived;
where the book's prose states a number, the number is parsed OUT OF THE
PROSE and compared against the measurement — so editing either side alone
turns the button red.

Populations are derived by property, never by glob or label (the log's
entries/ directory contains convenience copies; leaves are the files whose
names are six digits AND whose index field matches their position).

Exit 0 only if every applicable check passed. A check that could not
measure (missing sibling repo without BOOK_LOCAL_ONLY=1) is a FAILURE,
not a skip: a gate that read nothing must not look like a clean gate.
"""

import json
import os
import re
import subprocess
import sys

FAILS = []
PASSES = []


def ok(label, detail=""):
    PASSES.append(label)
    print(f"  ok    {label}" + (f"  [{detail}]" if detail else ""))


def fail(label, detail=""):
    FAILS.append(label)
    print(f"  FAIL  {label}" + (f"  [{detail}]" if detail else ""))


def check(cond, label, detail=""):
    (ok if cond else fail)(label, detail)


def read(path):
    with open(path, "r", errors="replace") as fh:
        return fh.read()


WORDS = {
    "one": 1, "two": 2, "three": 3, "four": 4, "five": 5, "six": 6,
    "seven": 7, "eight": 8, "nine": 9, "ten": 10, "eleven": 11,
    "twelve": 12, "thirteen": 13, "fourteen": 14, "fifteen": 15,
    "sixteen": 16, "seventeen": 17, "eighteen": 18, "nineteen": 19,
    "twenty": 20, "forty-four": 44, "sixty-one": 61,
}


def main():
    book = os.path.abspath(sys.argv[1] if len(sys.argv) > 1 else ".")
    no_pdf = os.environ.get("SKIP_BUILD") == "1"
    local_only = os.environ.get("BOOK_LOCAL_ONLY") == "1"
    estate = os.environ.get("ESTATE_ROOT", os.path.dirname(book))
    ltl = os.environ.get("LTL_DIR", os.path.join(estate, "lean-transparency-log"))
    fips = os.environ.get("FIPS205_DIR", os.path.join(estate, "fips205-slhdsa-verified"))
    p25519 = os.environ.get("P25519_FILE", os.path.join(
        estate, "dalek-ed25519-verified", "verification", "Proofs", "P25519.lean"))

    main_tex = read(os.path.join(book, "main.tex"))
    readme = read(os.path.join(book, "README.md"))
    chdir = os.path.join(book, "chapters")

    # the publication-history block: its CURRENT-edition line is bound to
    # measurements below; its historical lines are frozen and exempt from
    # the whole-book claim scans, so strip the span for scanning purposes
    mhist = re.search(r"% BEGIN PUBHIST.*?% END PUBHIST", main_tex, re.S)
    pubhist = mhist.group(0) if mhist else ""
    main_scan = main_tex.replace(pubhist, "")

    # ── Phase 0: source hygiene ────────────────────────────────────────────
    print("=== Phase 0: source hygiene ===")

    inputs = re.findall(r"\\input\{(chapters/[^}]+)\}", main_tex)
    missing = [i for i in inputs if not os.path.exists(os.path.join(book, i + ".tex"))]
    check(not missing, "every \\input'd chapter file exists",
          ",".join(missing) or f"{len(inputs)} inputs")
    on_disk = {f"chapters/{f[:-4]}" for f in os.listdir(chdir) if f.endswith(".tex")}
    orphans = sorted(on_disk - set(inputs))
    check(not orphans, "no orphan .tex under chapters/", ",".join(orphans) or "none")

    chapter_files = [i for i in inputs if re.search(r"chapters/ch\d\d-", i)]
    nums = [int(re.search(r"ch(\d\d)-", c).group(1)) for c in chapter_files]
    n_ch = len(chapter_files)
    check(nums == list(range(1, n_ch + 1)) and n_ch > 0,
          "chapter files contiguous ch01..chNN in input order", f"N={n_ch}")

    for cf in chapter_files + ["chapters/interlude-by-hand"]:
        src = read(os.path.join(book, cf + ".tex"))
        envs = re.findall(r"\\end\{([a-z]+)\}", src)
        check(envs and envs[-1] == "checkpoint",
              f"{cf.split('/')[-1]}: last environment is checkpoint",
              envs[-1] if envs else "no environments")

    for cf in chapter_files:
        num = int(re.search(r"ch(\d\d)-", cf).group(1))
        src = read(os.path.join(book, cf + ".tex"))
        n_ex = len(re.findall(r"\\exercise\{", src))
        sols = re.findall(r"\\solhead\{(\d+)\.(\d+)\}", src)
        n_sol = len(sols)
        label = f"ch{num:02d}: exercises == solutions"
        if n_ex == 0 and n_sol == 0:
            ok(label, "none (allowed)")
            continue
        good = (n_ex == n_sol
                and all(int(a) == num for a, _ in sols)
                and [int(b) for _, b in sols] == list(range(1, n_sol + 1)))
        check(good, label, f"{n_ex} exercises, solheads {[a+'.'+b for a, b in sols]}")

    isrc = read(os.path.join(book, "chapters/interlude-by-hand.tex"))
    i_ex = len(re.findall(r"Exercise I\.\d", isrc))
    i_sol = re.findall(r"\\solhead\{I\.(\d+)\}", isrc)
    check(i_ex == len(i_sol) and [int(x) for x in i_sol] == list(range(1, len(i_sol) + 1)),
          "interlude: exercises == solutions", f"{i_ex} vs {len(i_sol)}")

    # ── Phase 1 leftovers: claims about the built PDF ──────────────────────
    print("=== Phase 1b: built-PDF claims ===")
    if no_pdf:
        print("  (skipped: SKIP_BUILD=1 — build phase runs in check-book.sh)")
    else:
        pdf = os.path.join(book, "main.pdf")
        info = subprocess.run(["pdfinfo", pdf], capture_output=True, text=True).stdout
        pages = int(re.search(r"Pages:\s+(\d+)", info).group(1))
        check(pages >= 100, "PDF built and non-trivial", f"{pages} pages")
        txt = subprocess.run(["pdftotext", pdf, "-"],
                             capture_output=True, text=True).stdout
        bad = [l for l in txt.splitlines() if "??" in l]
        check(not bad, "no unresolved references ('??') in rendered PDF",
              bad[0][:60] if bad else "clean")
        page_claims = re.findall(r"(\d{2,4}) pages", readme + main_scan)
        if page_claims:
            for pc in page_claims:
                check(int(pc) == pages, f"page-count claim {pc} == built {pages}")
        else:
            ok("no page-count claim outside the history block (nothing to bind)")

        # publication history: the current-edition line is a live claim
        med = re.search(r"\\textbf\{(\w+) edition\} --- published "
                        r"([A-Za-z]+ \d+, \d{4}): (\w+)\s*\n?chapters, "
                        r"(\d+) pages", pubhist)
        if not (pubhist and med):
            fail("publication-history block with parseable current-edition line",
                 "missing" if not pubhist else "line not parseable")
        else:
            check(WORDS.get(med.group(3)) == n_ch,
                  "current edition's chapter count == measured",
                  f"{med.group(3)} vs {n_ch}")
            check(int(med.group(4)) == pages,
                  "current edition's page count == built PDF",
                  f"{med.group(4)} vs {pages}")
            # committed PDF must carry the current-edition line: this is what
            # a GitHub visitor downloads, and it must not lag the sources
            if os.path.isdir(os.path.join(book, ".git")):
                blob = subprocess.run(["git", "-C", book, "show", "HEAD:main.pdf"],
                                      capture_output=True)
                tmp = os.path.join(book, ".committed-main.pdf.tmp")
                with open(tmp, "wb") as fh:
                    fh.write(blob.stdout)
                ctxt = subprocess.run(["pdftotext", tmp, "-"],
                                      capture_output=True, text=True).stdout
                os.unlink(tmp)
                check(f"published {med.group(2)}" in ctxt,
                      "COMMITTED main.pdf carries the current-edition line "
                      "(the PDF a visitor downloads is not stale)",
                      med.group(2))
            else:
                ok("committed-PDF binding skipped (no git repo here)")

    # ── Phase 2: internal countable claims ─────────────────────────────────
    print("=== Phase 2: internal countable claims ===")

    m = re.search(r"(\w+(?:-\w+)?) chapters", readme)
    check(m and WORDS.get(m.group(1)) == n_ch,
          f"README chapter count == {n_ch}", m.group(0) if m else "no claim found")

    ch01 = read(os.path.join(book, "chapters/ch01-why-verify.tex"))
    m = re.search(r"the next (\w+)\s*\nchapters|the next (\w+) chapters", ch01)
    word = (m.group(1) or m.group(2)) if m else None
    check(word is not None and WORDS.get(word) == n_ch - 1,
          f"ch01 'the next N chapters' == {n_ch - 1}", word or "claim not found")

    # stale-total scan is scoped to the front matter, where whole-book totals
    # live; inside a chapter, "N chapters" is a positional count checked next
    for stale in ("twelve chapters", "thirteen chapters"):
        hits = [name for name, txt in (("main.tex", main_scan), ("README.md", readme))
                if stale in txt]
        check(not hits, f"no stale '{stale}' in front matter (history block exempt)",
              ",".join(hits) or "clean")
    # any "spent N chapters" phrase inside chapter chNN counts its predecessors
    for cf in chapter_files:
        num = int(re.search(r"ch(\d\d)-", cf).group(1))
        for word in re.findall(r"spent (\w+) chapters",
                               read(os.path.join(book, cf + ".tex"))):
            check(WORDS.get(word) == num - 1,
                  f"ch{num:02d} 'spent {word} chapters' == its {num - 1} predecessors")

    m = re.search(r"A (\w+)-week plan", main_tex)
    plan_word = WORDS.get(m.group(1)) if m else None
    weeks = [int(x) for x in re.findall(r"^(\d+)\s+&", main_tex, re.M)]
    ranges = [int(b) for _, b in re.findall(r"^(\d+)--(\d+)\s+&", main_tex, re.M)]
    max_week = max(weeks + ranges) if (weeks or ranges) else 0
    check(plan_word == max_week and plan_word is not None,
          "week-plan heading == max week row", f"{plan_word} vs {max_week}")
    check(f"{m.group(1)}-week" in main_tex.replace("A " + m.group(1), "", 1),
          "instructors paragraph agrees with plan heading")

    m = re.search(r"Chapters ([\d, ]+ and \d+) carry one", main_tex)
    if not m:
        fail("discussion-exercise roster claim parseable", "pattern not found")
    else:
        claimed = set(int(x) for x in re.findall(r"\d+", m.group(1)))
        measured = set()
        for cf in chapter_files:
            num = int(re.search(r"ch(\d\d)-", cf).group(1))
            src = read(os.path.join(book, cf + ".tex"))
            if re.search(r"\\exercise\{\(Discussion\)", src):
                measured.add(num)
        check(claimed == measured, "discussion-exercise roster == measured",
              f"claimed {sorted(claimed)}, measured {sorted(measured)}")

    ch13 = read(os.path.join(book, "chapters/ch13-second-summit.tex"))
    n, h, d, hp, a, k, w, ln2, m_dig = 16, 63, 7, 9, 12, 14, 16, 3, 30
    length = 2 * n + ln2
    split = ((k * a + 7) // 8, (h - h // d + 7) // 8, (h + 8 * d - 1) // (8 * d))
    check(sum(split) == m_dig and split == (21, 7, 2), "digest split recomputes",
          str(split))
    sig_bytes = n * (1 + k * (1 + a) + d * (length + hp))
    check(sig_bytes == 7856, "signature size recomputes", str(sig_bytes))
    fixed = k * a + d * hp + d + 1 + 1 + k          # H paths + T's + Hmsg + FORS leaves
    best = 0
    for csum in range(0, 32 * (w - 1) + 1):
        sh = csum << 4
        digs = [(sh >> 12) & 0xF, (sh >> 8) & 0xF, (sh >> 4) & 0xF]
        best = max(best, csum + sum((w - 1) - x for x in digs))
    worst = fixed + d * best
    check(fixed == 254 and best == 510 and worst == 3824,
          "oracle pricing recomputes (fixed/per-layer-max/worst)",
          f"{fixed}/{best}/{worst}")

    def see_saw(csum):
        sh = csum << 4
        return ((sh >> 12) & 0xF, (sh >> 8) & 0xF, (sh >> 4) & 0xF)
    check(see_saw(480) == (1, 14, 0) and see_saw(479) == (1, 13, 15)
          and see_saw(256) == (1, 0, 0), "checksum worked examples recompute")

    for token, why in [("7{,}856", "signature size"), ("254", "fixed oracle calls"),
                       ("510", "per-layer max"), ("3{,}824", "worst total"),
                       ("(1, 14, 0)", "csum 480 digits"),
                       ("(1, 13, 15)", "csum 479 digits"),
                       ("57{,}344", "FORS forest"), ("231", "H count"),
                       ("$21 + 7 + 2 = 30$", "digest split")]:
        check(token in ch13, f"ch13 prints {why}", token)
    check(len(str(2**255 - 19)) == 77, "'77-digit prime' recomputes")

    # ── Phase 3: cross-repo congruence ─────────────────────────────────────
    print("=== Phase 3: cross-repo congruence ===")
    if local_only:
        print("  (SKIPPED: BOOK_LOCAL_ONLY=1 — cross-repo claims NOT verified)")
    else:
        # the log: leaves by property, not by glob
        entdir = os.path.join(ltl, "entries")
        if not os.path.isdir(entdir):
            fail("lean-transparency-log present", entdir)
        else:
            leaf_files = sorted(f for f in os.listdir(entdir)
                                if re.fullmatch(r"\d{6}\.json", f))
            leaves = [json.load(open(os.path.join(entdir, f))) for f in leaf_files]
            idx_ok = all(lf["index"] == i for i, lf in enumerate(leaves))
            n_leaves = len(leaves)
            check(idx_ok, "leaf indexes contiguous and match filenames",
                  f"{n_leaves} leaves")

            for where, src, pat in [
                    ("title page '19 entries'", main_tex, r"(\d+) entries and counting"),
                    ("preface 'nineteen pieces'", main_tex, r"lists (\w+)\s*\npieces|lists (\w+) pieces"),
                    ("ch01 tryit '19 entries'", ch01, r"(\d+) entries, each one"),
                    ("ch14 'nineteen leaves'",
                     read(os.path.join(book, "chapters/ch14-attestation-protocol.tex")),
                     r"log's (\w+) leaves")]:
                mm = re.search(pat, src)
                val = None
                if mm:
                    g = next(g for g in mm.groups() if g)
                    val = int(g) if g.isdigit() else WORDS.get(g)
                check(val == n_leaves, f"{where} == measured {n_leaves}", str(val))

            def certs(i):
                return leaves[i]["leaf"]["attestation"]["certificates"]

            def comp(i):
                return leaves[i]["leaf"]["attestation"]["subject"]["component"]

            ed = {"dalek-ed25519-verified", "anza-ed25519-verified",
                  "risc0-ed25519-verified", "betrusted-ed25519-verified"}
            check({comp(i) for i in (13, 14, 15, 16)} == ed,
                  "leaves 13-16 subjects are the four ed25519 forks")
            check(all(len(certs(i)) == 44 for i in (13, 14, 15, 16)),
                  "'forty-four certificates each' == measured",
                  str([len(certs(i)) for i in (13, 14, 15, 16)]))
            check(27 + 13 + 4 == 44, "27 main + 13 scalar + 4 apex == 44")
            check(comp(17) == "ltl-accumulator-verified"
                  and len(certs(17)) == 61 and len(certs(12)) == 61,
                  "'sixty-one' accumulator certificates == measured (leaves 12, 17)")
            check(all(len(certs(i)) == 16 for i in range(0, 12)),
                  "'sixteen' early-leaf certificates == measured (leaves 0-11)")

            s18 = leaves[18]["leaf"]["attestation"]
            check(s18["subject"]["component"] == "fips205-slhdsa-verified"
                  and s18["subject"]["kind"] == "slh_dsa",
                  "leaf 18 subject is fips205-slhdsa-verified / slh_dsa")
            check(len(certs(18)) == 11 and "eleven certificates" in ch13,
                  "'eleven certificates' == measured", str(len(certs(18))))
            by_name = {c["name"]: c for c in certs(18)}
            for want in ("fips205.chain_free_loop_eq", "fips205.xmss_loop_eq",
                         "fips205.ht_loop_eq", "fips205.wots_csum_loop_eq",
                         "fips205.slh_verify_128s_accepts_iff"):
                check(want in by_name, f"leaf 18 carries {want}")
            kernel3 = {"propext", "Classical.choice", "Quot.sound"}
            apex = set(by_name["fips205.slh_verify_128s_accepts_iff"]["observed_axioms"])
            oracles = {f"verify_mono.oracle.{x}"
                       for x in ("f", "h", "h_msg", "t_l", "t_len")}
            check(apex == kernel3 | oracles, "apex cone == kernel-3 + five oracles")
            ht = set(by_name["fips205.ht_loop_eq"]["observed_axioms"])
            check(ht == kernel3 | {"verify_mono.oracle.f", "verify_mono.oracle.h",
                                   "verify_mono.oracle.t_l"},
                  "ht cone is f,h,t_l (the book's table row, by property not name)")
            plumb = sum(1 for c in certs(18) if set(c["observed_axioms"]) == kernel3)
            check(plumb == 4, "four kernel-3-only plumbing certificates", str(plumb))
            check(all(c["status"] == "proven" and c["axiom_status"] == "clean"
                      and set(c["observed_axioms"]) == set(c["expected_axioms"])
                      for c in certs(18)), "leaf 18: all proven, clean, cones exact")

            heads = [json.loads(l) for l in
                     open(os.path.join(ltl, "sth-history.jsonl")) if l.strip()]
            dual = [hd["tree_size"] for hd in heads
                    if hd["signatures"].get("slh_dsa", {}).get("status") == "signed"]
            check(dual and min(dual) == 14,
                  "'since tree 14' dual-signed heads == measured",
                  f"first dual head size {min(dual) if dual else None}")
            check(heads[-1]["tree_size"] == n_leaves,
                  "final head size == leaf count")

        # fips205 parameter card
        funs = os.path.join(fips, "verification", "gen", "SlhVerify", "Funs.lean")
        if not os.path.exists(funs):
            fail("fips205-slhdsa-verified present", funs)
        else:
            fsrc = read(funs)
            mm = re.search(
                r"def verify_mono\.slh_verify_128s.*?types\.SlhDsaSig "
                r"(\d+)#usize (\d+)#usize (\d+)#usize (\d+)#usize (\d+)#usize "
                r"(\d+)#usize.*?slh_verify_internal_free (\d+)#usize (\d+)#usize",
                fsrc, re.S)
            if not mm:
                fail("fips205 entry-point parameters parseable")
            else:
                A, D, HP, K, LEN, N = (int(mm.group(i)) for i in range(1, 7))
                H, M = int(mm.group(7)), int(mm.group(8))
                W = int(re.search(r"def W : Std\.U32 := (\d+)#u32", fsrc).group(1))
                repo = {"a": A, "d": D, "h'": HP, "k": K, "len": LEN,
                        "n": N, "h": H, "m": M, "w": W}
                card = {"a": a, "d": d, "h'": hp, "k": k, "len": length,
                        "n": n, "h": h, "m": m_dig, "w": w}
                check(repo == card, "ch13 parameter card == extracted entry point",
                      str(repo))
                for sym, val in card.items():
                    tok = f"{sym} = {val}"
                    check(tok in ch13 or f"= {val}" in ch13,
                          f"ch13 prints {sym} = {val}")

        # the 71-digit Q, digit for digit
        if not os.path.exists(p25519):
            fail("P25519.lean present for Q comparison", p25519)
        else:
            psrc = read(p25519)
            mq = re.search(r"theorem prime_(\d{60,})", psrc)
            ch07 = read(os.path.join(book, "chapters/ch07-primality-certificates.tex"))
            mb = re.search(r"Q = ([0-9\\a-z{} ]+?),\s*\n?\\\]", ch07, re.S)
            q_repo = mq.group(1) if mq else None
            q_book = re.sub(r"\D", "", mb.group(1)) if mb else None
            check(q_repo is not None and q_book == q_repo,
                  "ch07's printed Q == repository's Q, digit for digit",
                  f"book {len(q_book or '')} digits, repo {len(q_repo or '')} digits")
            check(q_repo is not None and len(q_repo) == 71 and "71-digit" in ch07,
                  "'71-digit' claim recomputes")

    # ── verdict ────────────────────────────────────────────────────────────
    print()
    total = len(PASSES) + len(FAILS)
    if FAILS:
        print(f"RED: {len(FAILS)} of {total} claims diverge from measured reality:")
        for f in FAILS:
            print(f"  - {f}")
        sys.exit(1)
    if local_only:
        print(f"LOCAL CHECKS GREEN ({total} checks) — cross-repo claims NOT "
              f"verified (BOOK_LOCAL_ONLY=1). This is not ALL GREEN.")
        sys.exit(0)
    print(f"ALL CLAIM CHECKS GREEN ({total} checks)")
    sys.exit(0)


if __name__ == "__main__":
    main()