#!/usr/bin/env python3
"""Reproduce the cells the revised document reads off `kstar_dfs.py` (return #1144).
Job #2987 adds one ladder row, 19#→43#, whose numbers are not this document's own: they
come from the pruned covering search that return #1144 serves. This script is how a
reviewer re-reads that row, and how the document's other rows stay anchored, without
trusting anything this run wrote down.
Two modes:
reproduce-row.py --instrument ./kstar_dfs.py [--full]
run the served instrument fresh. The frozen cells (13#→29#, 13#→31#, 17#→31#) are
the committed ones the document's earlier rows rest on; `--full` adds the new
19#→43# row's K* plus its two certificate cells (N_20, N_21). `--full` costs about
three minutes; the frozen cells are seconds.
reproduce-row.py --from-dir
canonicalise JSON outputs already recorded in (out-*.json, counts-*.json).
This is how the uploaded evidence file was built from the observed runs.
Both modes print exactly the same canonical text: wall time (`seconds`) is dropped and
progress lines (which carry elapsed seconds and go to stderr anyway) are not read, so the
output is byte-identical across machines -- the property the assignment asks for. Exit 0
only when every cell printed was observed and matches the value the document states.
"""
import argparse
import hashlib
import json
import os
import subprocess
import sys
FROZEN = [((13, 29), 10), ((13, 31), 17), ((17, 31), 13)] # #1144 §2, committed cells
NEW_ROW = ((19, 43), 20) # #1144: the added row
CERTS = [((19, 43, 20), 4), ((19, 43, 21), 0)] # #1144: N_20 = 4, N_21 = 0
WITNESS = {"P": 19, "PP": 43, "D": 378675, "witness_start": 22352, "windows_tested": 378695}
def load_json(path):
"""One instrument record per file. A captured run may carry its progress lines in the
same stream, so take the last brace-delimited line -- never the first, which may be a
progress record."""
with open(path, encoding="utf-8", errors="replace") as fh:
for ln in reversed(fh.read().splitlines()):
ln = ln.strip()
if ln.startswith("{") and ln.endswith("}"):
return json.loads(ln)
raise SystemExit("no JSON record in %s" % path)
def canonical(rec):
"""The machine-independent projection of one instrument record."""
keep = ("P", "PP", "D", "Q", "kstar", "witness_start", "windows_tested", "lo", "hi", "k", "N_k")
return {k: rec[k] for k in keep if k in rec}
def line(rec):
return "python kstar_dfs.py %d %d -> %s" % (
rec["P"], rec["PP"], json.dumps(canonical(rec), sort_keys=True, separators=(",", ":")))
def observe(instrument, P, PP, extra=None):
args = [sys.executable, instrument, str(P), str(PP)] + (extra or [])
p = subprocess.run(args, capture_output=True, text=True)
if p.returncode != 0:
raise SystemExit("instrument failed: %s\n%s" % (" ".join(args), p.stderr[-800:]))
body = [ln for ln in p.stdout.splitlines() if ln.strip().startswith("{")]
return json.loads(body[-1])
def main() -> int:
ap = argparse.ArgumentParser()
ap.add_argument("--instrument", default=None)
ap.add_argument("--from-dir", default=None)
ap.add_argument("--hash", default=None, help="sha256 of the instrument (printed as provenance)")
ap.add_argument("--full", action="store_true")
a = ap.parse_args()
sys.stdout.reconfigure(newline="\n", encoding="utf-8")
rows, ok = [], True
def add(rec, expect_kstar=None, expect_nk=None, label=""):
nonlocal ok
got = rec.get("kstar") if expect_kstar is not None else rec.get("N_k")
want = expect_kstar if expect_kstar is not None else expect_nk
good = (got == want)
ok = ok and good
rows.append("%s%s %s" % (line(rec), " [%s]" % label if label else "",
"match" if good else "MISMATCH (document says %s)" % want))
if a.from_dir:
for (P, PP), want in FROZEN:
add(load_json(os.path.join(a.from_dir, "out-%d%d.json" % (P, PP))),
expect_kstar=want, label="frozen")
rec = load_json(os.path.join(a.from_dir, "out-%d%d.json" % NEW_ROW[0]))
add(rec, expect_kstar=NEW_ROW[1], label="19#->43# K*")
for key, want in (("D", WITNESS["D"]), ("witness_start", WITNESS["witness_start"]),
("windows_tested", WITNESS["windows_tested"])):
good = (rec.get(key) == want)
ok = ok and good
rows.append(" witness field %-15s = %s (%s)" % (key, rec.get(key),
"match" if good else "MISMATCH"))
for (P, PP, k), want in CERTS:
add(load_json(os.path.join(a.from_dir, "counts-%d.json" % k)),
expect_nk=want, label="certificate cell N_%d" % k)
else:
if not a.instrument:
raise SystemExit("need --instrument or --from-dir")
for (P, PP), want in FROZEN:
add(observe(a.instrument, P, PP), expect_kstar=want, label="frozen")
if a.full:
add(observe(a.instrument, *NEW_ROW[0]), expect_kstar=NEW_ROW[1], label="19#->43# K*")
for (P, PP, k), want in CERTS:
add(observe(a.instrument, P, PP, ["--count", str(k)]), expect_nk=want,
label="certificate cell N_%d" % k)
if a.hash:
with open(a.instrument, "rb") as fh:
digest = hashlib.sha256(fh.read()).hexdigest()
rows.append(" instrument sha256 %s (declared %s: %s)" % (
digest, a.hash, "match" if digest == a.hash else "MISMATCH"))
ok = ok and digest == a.hash
print("kstar_dfs.py cells read by research/history/staging/attack-kstar-01.md (job #2987)")
print("source: kstar_dfs.py, served by return #1144; wall time and progress lines excluded")
for r in rows:
print(r)
print("verdict: %s" % ("PASS" if ok else "FAIL"))
return 0 if ok else 1
if __name__ == "__main__":
sys.exit(main())