"""Verify packet interoperability, exact data, and generated programs.""" import argparse from base64 import b64decode from concurrent.futures import ThreadPoolExecutor from fractions import Fraction from functools import reduce from hashlib import sha256 from io import BytesIO import json from math import gcd import operator from pathlib import Path import re from shutil import which import sqlite3 from struct import pack, unpack from subprocess import run import sys from tempfile import TemporaryDirectory import tomllib import wave from xml.etree import ElementTree from packet import canonical_bytes, receive, send, write_tree from recipes import Q, RECIPES, SCALE, build, graph_neighbors ROOT = Path(__file__).resolve().parent SEEDS = (0, 1, 2, 3, 15, 16, 17, 31, 32, 127, 128, 255, 256, 398, 399, 400, 1023, 4096, 16384, 32766, 32767) RUN_SEEDS = (0, 399, 32767) PYTHON = [sys.executable, str(ROOT / "packet.py")] NODE = ["node", str(ROOT / "packet.mjs")] def require(condition, message): if not condition: raise RuntimeError(message) def command(args, *, data=None, cwd=ROOT, check=True): result = run(args, input=data, capture_output=True, cwd=cwd, check=check, timeout=90) if check and result.stderr: raise RuntimeError(f"unexpected stderr from {args[0]}: {result.stderr.decode()}") return result def line_bytes(lines): return ("\n".join(lines) + "\n").encode("ascii") def scalar_orbit(seed): states = [seed] for _ in range(23): states.append(Q * states[-1] // SCALE) return states def integer_rows(data, separator=None, skip=1): return [tuple(map(int, line.split(separator))) for line in data.decode("ascii").splitlines()[skip:]] def check_scalar(tree, seed): require(integer_rows(tree["history.csv"], ",") == list(enumerate(scalar_orbit(seed))), "scalar history differs") def check_transducer(tree, seed): table = {(s, a): (t, out) for s, a, t, out in integer_rows(tree["transducer.tsv"], "\t")} require(len(table) == 21, "incomplete transducer") for (state, letter), (successor, output) in table.items(): require(0 <= state < 7 and 0 <= letter < 3 and 0 <= successor < 7, "transducer range") require((successor - 2 * state - letter - seed) % 7 == 0, "transducer successor") require(output == (state + letter + seed) % 2, "transducer output") def check_sat(tree, seed): instance = tree["instance.cnf"].decode("ascii").splitlines() witness = [int(x) for x in tree["witness.txt"].split()] require(instance[0] == "p cnf 15 30" and len(instance) == 31, "CNF header") require([abs(lit) for lit in witness] == list(range(1, 16)), "SAT witness shape") require(sum((lit > 0) << i for i, lit in enumerate(witness)) == seed, "SAT seed witness") true_literals = set(witness) for row in instance[1:]: *clause, end = map(int, row.split()) require(end == 0 and len(clause) == 3 and len({abs(x) for x in clause}) == 3, "invalid CNF clause") require(any(lit in true_literals for lit in clause), "unsatisfied generated clause") def interpolate(samples): matrix = [[Fraction(x**j) for j in range(6)] + [Fraction(y)] for x, y in samples] for j in range(6): pivot = next(i for i in range(j, 6) if matrix[i][j]) matrix[j], matrix[pivot] = matrix[pivot], matrix[j] scale = matrix[j][j] matrix[j] = [x / scale for x in matrix[j]] for i in range(6): if i != j: multiple = matrix[i][j] matrix[i] = [a - multiple * b for a, b in zip(matrix[i], matrix[j])] return [row[-1] for row in matrix] def check_samples(tree, seed): samples = integer_rows(tree["samples.csv"], ",") require(len(samples) == len({x for x, _ in samples}) == 6, "polynomial nodes") expected = [((seed >> (2 * j)) & 7) - 3 for j in range(6)] require(interpolate(samples) == expected, "exact coefficient recovery") def check_srsd(tree, seed): rows = integer_rows(tree["record.tsv"], "\t") require(len(rows) == 8, "SRSD record length") for i, (index, h, quotient, residual) in enumerate(rows): require(index == i and h == 17 + seed % 11 and 0 <= residual < h, "SRSD bounds") require(h * quotient + residual == (-1)**i * (seed + 11 * i * i) - 13 * i, "SRSD exact readout") def check_geometry(tree, seed): data = json.loads(tree["geometry.json"]) require(data["a"] == seed + 1 and data["phi"] == "(1+sqrt(5))/2", "OMEGA scale or phi") require(data["gap"] == "sin(pi/1296000)" and data["c"] == "cos(pi/1296000)", "OMEGA opening") require([label for label, _ in data["marks"]] == ["d2", "d1", "d", "b", "b1", "b2"], "OMEGA mark labels") marks = [z for _, z in data["marks"]] require(all(left == "-" + right or left == "-(" + right + ")" for left, right in zip(marks[:3], reversed(marks[3:]))), "OMEGA symmetry") require(data["position"] == "(a*z,-a*c,0)", "OMEGA placement") def check_network(tree, seed): rows = integer_rows(tree["signals.csv"], ",") require(len(rows) == 11 and all(len(row) == 121 and row[0] == i for i, row in enumerate(rows)), "network shape") require(rows[0][1:] == tuple((seed + 37 * i) % 32768 for i in range(120)), "network seed") require(not any(rows[-1][1:]), "network terminal") edges = graph_neighbors() for current, following in zip(rows, rows[1:]): state = current[1:] for i, successor in enumerate(following[1:]): value = Q * (13 * state[i] + sum(state[j] for j in edges[i])) require(25 * SCALE * successor <= value < 25 * SCALE * (successor + 1), "exact network floor interval") def syndrome(bits): return reduce(operator.xor, (i for i, bit in enumerate(bits, 1) if bit), 0) def check_hamming(tree, seed): rows = tree["codewords.tsv"].decode("ascii").splitlines()[1:] require(len(rows) == 4, "Hamming record length") for i, row in enumerate(rows): index, message, text = row.split("\t") bits = [int(x) for x in text] require(len(bits) == 7 and set(bits) <= {0, 1} and syndrome(bits) == 0, "invalid codeword") decoded = sum(bits[position - 1] << j for j, position in enumerate((3, 5, 6, 7))) require(int(index) == i and decoded == int(message) == (seed >> (4 * i)) & 15, "Hamming data recovery") for bit in range(7): changed = bits[:] changed[bit] ^= 1 require(syndrome(changed) == bit + 1, "Hamming single-bit error location") def check_graph(tree, seed): lines = tree["graph.dot"].decode("ascii").splitlines() require(lines[0] == "digraph Sample {" and lines[-1] == "}", "DOT envelope") require(lines[1:13] == [f" v{i};" for i in range(12)], "DOT vertices") edges = {(int(a), int(b)) for a, b in re.findall(r"^ v(\d+) -> v(\d+);$", "\n".join(lines[13:]), re.M)} expected = {(i, i + 2) for i in range(10)} expected.update((i, i + 1) for i in range(11) if (seed >> i) & 1) require(edges == expected and len(edges) == len(lines[13:-1]), "DOT edges") def check_laplacian(tree, seed): header = tree["matrix.mtx"].splitlines()[:2] require(header == [b"%%MatrixMarket matrix coordinate integer symmetric", b"8 8 16"], "Matrix Market header") rows = integer_rows(tree["matrix.mtx"], skip=2) require(len(rows) == 16 and len({(i, j) for i, j, _ in rows}) == 16, "matrix entries") matrix = [[0] * 8 for _ in range(8)] for i, j, value in rows: require(1 <= j <= i <= 8, "matrix coordinates") matrix[i - 1][j - 1] = matrix[j - 1][i - 1] = value for i, row in enumerate(matrix): require(sum(row) == 0 and row[(i + 1) % 8] == -(1 + (seed + i * i) % 9), "cycle Laplacian") def check_measurements(tree, seed): rows = integer_rows(tree["measurements.csv"], ",") require(len(rows) == 32, "measurement count") for i, (j, left, right) in enumerate(rows): require(j == i and (left - seed - 29 * i) % 1009 == 0 and (right - seed - 11 * i * i) % 2039 == 0 and 0 <= left < 1009 and 0 <= right < 2039, "measurement values") def check_config(tree, seed): expected = {"seed": seed, "sampling": {"period": 1 + seed % 31, "gain": 2 + seed % 13, "exact": True}} require(tomllib.loads(tree["config.toml"].decode("ascii")) == expected, "TOML values") def check_svg(tree, seed): root = ElementTree.fromstring(tree["chart.svg"]) bars = root.findall(".//{http://www.w3.org/2000/svg}rect") require(len(bars) == 8, "SVG bar count") for i, bar in enumerate(bars): h = 1 + (seed + 7 * i * i) % 47 require(bar.attrib == {"x": str(8 + 18 * i), "y": str(55 - h), "width": "12", "height": str(h)}, "SVG bar geometry") def check_ppm(tree, seed): kind, size, maximum, pixels = tree["tile.ppm"].split(b"\n", 3) require((kind, size, maximum) == (b"P6", b"16 12", b"255") and len(pixels) == 576, "PPM header or payload") for i in range(192): y, x = divmod(i, 16) r, g, b = pixels[3 * i : 3 * i + 3] require((r - seed - 17 * x - 31 * y) % 256 == 0 and (g - (seed >> 4) - 13 * x * y) % 256 == 0 and (b - seed - 11 * (x + y)**2) % 256 == 0, "PPM pixels") def check_pbm(tree, seed): kind, size, pixels = tree["grid.pbm"].split(b"\n", 2) require((kind, size) == (b"P4", b"32 16") and len(pixels) == 64, "PBM header or payload") rows = [[(byte >> j) & 1 for byte in pixels[4 * i : 4 * i + 4] for j in range(7, -1, -1)] for i in range(16)] require(sum(bit << i for i, bit in enumerate(rows[0])) == seed | (1 << 16), "PBM seed") for current, following in zip(rows, rows[1:]): require(all(following[i] == (current[(i - 1) % 32] ^ (current[i] | current[(i + 1) % 32])) for i in range(32)), "Rule 30 transition") def check_pcm(tree, seed): with wave.open(BytesIO(tree["tone.wav"]), "rb") as stream: count = 160 + 16 * (seed % 8) require((stream.getnchannels(), stream.getsampwidth(), stream.getframerate(), stream.getnframes()) == (1, 2, 8000, count), "PCM format") samples = unpack(f"<{count}h", stream.readframes(count)) for i, sample in enumerate(samples): phase = i * (3 + seed % 13) % 64 require(sample == (min(phase, 64 - phase) - 16) * 1024, "PCM sample") def check_midi(tree, seed): data = tree["melody.mid"] require(data[:4] == b"MThd" and unpack(">IHHH", data[4:14]) == (6, 0, 1, 96) and data[14:18] == b"MTrk" and int.from_bytes(data[18:22], "big") == len(data) - 22 and len(data) == 90, "MIDI headers") track = data[22:] require(track[-4:] == b"\x00\xff\x2f\x00", "MIDI track end") for i in range(8): note = 48 + (seed + 7 * i + (seed >> (i % 5))) % 24 require(track[8 * i : 8 * i + 8] == bytes((0, 0x90, note, 64, 24 + seed % 16, 0x80, note, 0)), "MIDI note events") def check_mesh(tree, seed): rows = [line.split() for line in tree["mesh.obj"].decode("ascii").splitlines()] require(len(rows) == 41, "OBJ count") for i, (kind, x, y, z) in enumerate(rows[:25]): iy, ix = divmod(i, 5) require(kind == "v" and (int(x), int(y), int(z)) == (ix, iy, (seed + 3 * ix * ix + 5 * iy) % 13), "OBJ vertex") for i, (kind, *vertices) in enumerate(rows[25:]): y, x = divmod(i, 4) a = 1 + 5 * y + x require(kind == "f" and list(map(int, vertices)) == [a, a + 1, a + 6, a + 5], "OBJ face") DATA_CHECKS = dict(zip((1, *range(14, 31)), ( check_scalar, check_transducer, check_sat, check_samples, check_srsd, check_geometry, check_network, check_hamming, check_graph, check_laplacian, check_measurements, check_config, check_svg, check_ppm, check_pbm, check_pcm, check_midi, check_mesh, ), strict=True)) def verify_program(recipe, seed, directory): if recipe == 2: args, expected = [sys.executable, "main.py"], " ".join(map(str, scalar_orbit(seed))) elif recipe == 3: args = ["java", "Main.java"] expected = sum((seed + 17 * i)**2 % 997 for i in range(16)) elif recipe == 4: command(["rustc", "--edition=2021", "main.rs", "-o", "app"], cwd=directory) args, expected = ["./app"], gcd(seed + 100, 12345) elif recipe == 5: args = ["julia", "--startup-file=no", "--history-file=no", "main.jl"] expected = 4 * seed**3 - 3 * seed**2 + 2 * seed - 1 elif recipe == 6: args, expected = ["node", "main.mjs"], sum((seed + i * i) % 997 for i in range(64)) elif recipe == 7: command(["cc", "-std=c17", "-Wall", "-Wextra", "-Werror", "main.c", "-o", "app"], cwd=directory) args, expected = ["./app"], seed * (seed + 1) // 2 elif recipe == 8: t = seed % 257 args, expected = ["sh", "run.sh"], (t + 3) * (t + 1) elif recipe == 9: args, expected = ["lean", "SeedProof.lean"], seed elif recipe == 10: args = ["node", "--input-type=module", "-e", "import {readFileSync} from 'node:fs'; " "const {instance} = await WebAssembly.instantiate(readFileSync('seed.wasm')); " "console.log(instance.exports.run());"] expected = seed elif recipe == 11: with sqlite3.connect(":memory:") as conn: conn.executescript((directory / "load.sql").read_text(encoding="ascii")) values = conn.execute("SELECT id, value FROM samples ORDER BY id").fetchall() expected = [(i, (seed + i * i) % 127) for i in range(1, 7)] require(values == expected, "SQLite sample rows") require(conn.execute("SELECT value FROM total").fetchone()[0] == sum(v for _, v in expected), "SQLite view") return elif recipe == 12: args = [sys.executable, "app/main.py"] expected = sum(i * ((seed + i) % 97) for i in range(1, 13)) else: args = ["node", "--input-type=module", "-e", "const output = {}; globalThis.document = {querySelector(s) {" "if (s !== 'output') throw new Error(s); return output; }}; " "await import('./app.mjs'); console.log(output.textContent);"] expected = sum((seed + i * i) % 61 for i in range(12)) actual = command(args, cwd=directory).stdout.decode("ascii") require(actual == f"{expected}\n", f"program output for recipe {recipe}, seed {seed}: {actual!r}") def cross_runtime(trees): cases = [(recipe, seed, mode) for recipe, seed in trees for mode in (False, True)] params = line_bytes(json.dumps(case, separators=(",", ":")) for case in cases) python_packets = [send(recipe, seed, mode).hex() for recipe, seed, mode in cases] node_packets = command([*NODE, "send-batch"], data=params).stdout.decode("ascii").splitlines() require(node_packets == python_packets, "cross-runtime packet bytes differ") expected = {key: canonical_bytes(tree) for key, tree in trees.items()} for receiver, packets in ((NODE, python_packets), (PYTHON, node_packets)): rebuilt = command([*receiver, "receive-batch"], data=line_bytes(packets)).stdout.splitlines() require(len(rebuilt) == len(cases), "receiver result count") for (recipe, seed, mode), encoded in zip(cases, rebuilt, strict=True): require(b64decode(encoded, validate=True) == expected[recipe, seed], f"tree bytes differ for {receiver[0]}, recipe {recipe}, seed {seed}, witness {mode}") digest = sha256() for (recipe, seed, _), packet in zip(cases, python_packets, strict=True): raw = bytes.fromhex(packet) data = expected[recipe, seed] digest.update(bytes([len(raw)]) + raw + pack(" " "(SeedPacket.rebuild SeedPacket.wasmRecipe p).getD [])))\n" ) with TemporaryDirectory(prefix="seed-packet-lean-") as work: proof = Path(work) / "CheckWasm.lean" proof.write_text(source, encoding="ascii") output = command(["lake", "env", "lean", str(proof)]).stdout actual = [bytes(module) for module in json.loads(output)] expected = [trees[10, seed]["seed.wasm"] for seed in SEEDS] require(actual == expected, "Lean witness receiver produced different WebAssembly bytes") return len(actual) def examples(directory, trees): directory.mkdir() table = ["recipe\tname\tdirect_packet\twitness_packet\tcontent_bytes\tcanonical_tree_sha256"] for recipe, (name, _) in enumerate(RECIPES, 1): tree = trees[recipe, 399] label = name.lower().replace(" ", "-") write_tree(tree, directory / f"{recipe:02d}-{label}") size = sum(map(len, tree.values())) direct = send(recipe, 399).hex() witness = send(recipe, 399, True).hex() digest = sha256(canonical_bytes(tree)).hexdigest() table.append(f"{recipe}\t{name}\t{direct}\t{witness}\t{size}\t{digest}") (directory / "packets.tsv").write_bytes(line_bytes(table)) def main(): parser = argparse.ArgumentParser(description=__doc__) parser.add_argument("--bytes-only", action="store_true", help="skip execution of generated programs") parser.add_argument("--examples", type=Path, help="write all seed-399 examples to a new directory") options = parser.parse_args() require(Q == 339949771344778 and SCALE == 10**15, "coefficient or scale mismatch") trees = {(recipe, seed): build(recipe, seed) for recipe in range(1, len(RECIPES) + 1) for seed in SEEDS} count, digest = cross_runtime(trees) for (recipe, seed), tree in trees.items(): if recipe in DATA_CHECKS: DATA_CHECKS[recipe](tree, seed) controls = control_packets() runs = 0 if options.bytes_only else program_checks(trees) lean_checks = 0 if options.bytes_only else lean_byte_checks(trees) if options.examples: examples(options.examples, trees) print(f"Python {sys.version.split()[0]}") print(f"Node {command(['node', '--version']).stdout.decode().strip()}") print(f"Recipe IDs: {len(RECIPES)}") print(f"Seeds per recipe: {len(SEEDS)}") print(f"Distinct recipe/seed instances: {len(trees)}") print(f"Packet cases in each direction: {count}") print(f"Byte-identical receiver outputs: {2 * count}") print(f"Exact data semantic checks: {len(DATA_CHECKS) * len(SEEDS)}") print(f"Generated program and proof executions: {runs}") print(f"WebAssembly modules matched by the Lean witness receiver: {lean_checks}") print(f"Malformed packets rejected by each receiver: {controls}") print("Quotient collision control: 398, 399, 400 -> 135, three distinct program trees") print(f"Packet and canonical tree corpus SHA-256: {digest}") print("PASS") if __name__ == "__main__": try: main() except Exception as error: if getattr(error, "stderr", None): sys.stderr.buffer.write(error.stderr) sys.exit(str(error))