#!/usr/bin/env python3 """Minimal reference implementation of PureRand Wheel algorithms wheel-v1 and shuffle-v1. Written from the specification only. Standard library, no dependencies. python3 spec/reference.py receipt.json verify a downloaded receipt python3 spec/reference.py --online receipt.json also look up each draw via the public api2 /verify endpoint python3 spec/reference.py --vectors > out.json regenerate the test vectors """ import hashlib import json import sys import urllib.request def canonical_json(labels, weights, salt, algorithm="wheel-v1"): """api2 canonical JSON: sorted keys, no whitespace, non-ASCII as lowercase \\uXXXX. For documents of strings and integers this equals Python's json.dumps(sort_keys=True, separators=(",", ":"), ensure_ascii=True), with one difference that cannot occur here: Python escapes U+007F, api2 writes it raw, and canonical labels never contain control characters. """ if len(salt) != 64 or any(c not in "0123456789abcdef" for c in salt): raise ValueError("salt must be 64 lowercase hex characters") if len(labels) != len(weights): raise ValueError("labels and weights differ in length") doc = { "algorithm": algorithm, "entries": [{"label": l, "slot": i + 1, "weight": w} for i, (l, w) in enumerate(zip(labels, weights))], "salt": salt, } return json.dumps(doc, sort_keys=True, separators=(",", ":"), ensure_ascii=True) def commitment(labels, weights, salt, algorithm="wheel-v1"): return hashlib.sha256(canonical_json(labels, weights, salt, algorithm).encode("ascii")).hexdigest() def shuffle(n, bits): """shuffle-v1: Fisher-Yates from the last position down; returns the new order or None.""" samples = [int(bits[k : k + 32], 2) for k in range(0, len(bits) - len(bits) % 32, 32)] order = list(range(1, n + 1)) it = iter(samples) for i in range(n - 1, 0, -1): m = i + 1 limit = 2**32 - (2**32 % m) u = next((x for x in it if x < limit), None) if u is None: return None j = u % m order[i], order[j] = order[j], order[i] return order def draw(weights, value_hex): """Return (winning_slot, accepted_sample_index), or None if every sample is rejected.""" data = bytes.fromhex(value_hex) total = sum(weights) limit = 2**32 - (2**32 % total) for i in range(len(data) // 4): u = int.from_bytes(data[4 * i : 4 * i + 4], "big") if u >= limit: continue r = u % total upper = 0 for k, w in enumerate(weights): upper += w if r < upper: return k + 1, i return None def report(ok, text): print("PASS" if ok else "FAIL", text) return ok def verify(receipt, online=False): if receipt.get("status", "drawn") != "drawn": reason = (receipt.get("draw_failure") or {}).get("reason") return report(False, f"not drawn (status {receipt.get('status')}{', ' + reason if reason else ''}): nothing to verify") ok = True algorithm = receipt["algorithm"] weights = receipt["weights"] rnd = receipt["randomness"] draws = rnd["draws"] ok &= report("".join(d["value"] for d in draws) == rnd["value"], "randomness.value is the concatenation of the draws") if algorithm == "shuffle-v1": order = shuffle(len(weights), rnd["value"]) ok &= report(order == receipt["result"]["order"], f"replayed order {order[:5] if order else None}... matches the receipt") else: result = draw(weights, rnd["value"]) expected = (receipt["result"]["winning_slot"], receipt["result"]["accepted_sample_index"]) ok &= report(result == expected, f"replayed {result}, receipt says {expected}") for n, d in enumerate(draws, 1): # Crypto draws: the chain holds SHA-256(value). Bits draws: the value itself. if d.get("type") == "bits": chain_value = d["value"] else: chain_value = hashlib.sha256(d["value"].encode("ascii")).hexdigest() ok &= report(chain_value == d["value_hash"], f"draw {n}: SHA-256(value) == value_hash") ok &= report(d["timestamp"] >= receipt["committed_at"], f"draw {n}: api2 block {d['timestamp']} is not before commitment {receipt['committed_at']}") url = rnd["api_base"] + d["verify_url"] if online: req = urllib.request.Request(url, headers={"Accept": "application/json"}) with urllib.request.urlopen(req, timeout=15) as resp: block = json.load(resp) ok &= report(block.get("ok") is True and block.get("hash") == d["hash"], f"draw {n}: api2 block {d['hash'][:16]}... is intact") ok &= report(block.get("random_data") == chain_value, f"draw {n}: api2 random_data matches the draw") else: shown = chain_value if len(chain_value) <= 64 else chain_value[:32] + "..." print(f" draw {n}: api2 random_data should be {shown} at {url}") names = receipt.get("names") if names: ok &= report(commitment(names["labels"], weights, names["salt"], algorithm) == receipt["commitment"], "published names and salt match the commitment") return ok def vectors(): import unicodedata commit_cases = [ (["Alice", "Bob", "Carol"], [1, 1, 1], "0f1e2d3c4b5a69788796a5b4c3d2e1f000112233445566778899aabbccddeeff"), ( [unicodedata.normalize("NFC", "Zoë"), 'quote " and \\ backslash', "日本語", "😀 emoji", "tab nbsp / slash"], [1, 2, 3, 4, 1000], "a" * 64, ), ] big = 4294500000 # limit for 500 entries of weight 1000 draw_cases = [ ("uniform, first sample accepted", [1, 1, 1], "00000005" + "00" * 12), ("uniform, first sample rejected at the limit", [1, 1, 1], "ffffffff" + "00000005" + "00" * 8), ("weighted, low value lands in slot 1", [1, 1000], "00000000" + "00" * 12), ("weighted, next value lands in slot 2", [1, 1000], "00000001" + "00" * 12), ("500 x 1000, largest accepted value", [1000] * 500, "%08x" % (big - 1) + "00" * 12), ("500 x 1000, smallest rejected value", [1000] * 500, "%08x" % big + "%08x" % 12345 + "00" * 8), ("all four samples rejected", [1, 1, 1], "ff" * 16), ("two api2 draws concatenated", [1, 1, 1], "ff" * 16 + "00000007" + "00" * 12), ] out = {"algorithms": ["wheel-v1", "shuffle-v1"], "generated_by": "spec/reference.py", "commitment_vectors": [], "draw_vectors": [], "shuffle_vectors": []} for labels, weights, salt in commit_cases: out["commitment_vectors"].append({ "labels": labels, "weights": weights, "salt": salt, "canonical_json": canonical_json(labels, weights, salt), "commitment": commitment(labels, weights, salt), }) s32 = lambda *xs: "".join(format(x, "032b") for x in xs) shuffle_cases = [ ("3 entries, samples 7 and 5", 3, s32(7, 5)), ("3 entries, first sample rejected at the limit", 3, s32(2**32 - 1, 7, 5)), ("4 entries, bits run out", 4, s32(1, 2)), ("500 entries, samples counting up", 500, s32(*range(1000, 1499))), ] for name, n, bits in shuffle_cases: out["shuffle_vectors"].append({"name": name, "n": n, "value": bits, "expected_order": shuffle(n, bits)}) out["commitment_vectors"].append({ "labels": ["Alice", "Bob"], "weights": [1, 1], "salt": "b" * 64, "algorithm": "shuffle-v1", "canonical_json": canonical_json(["Alice", "Bob"], [1, 1], "b" * 64, "shuffle-v1"), "commitment": commitment(["Alice", "Bob"], [1, 1], "b" * 64, "shuffle-v1"), }) for name, weights, hx in draw_cases: r = draw(weights, hx) out["draw_vectors"].append({ "name": name, "weights": {"repeat": 1000, "count": 500} if len(weights) == 500 else weights, "value": hx, "expected": None if r is None else {"winning_slot": r[0], "accepted_sample_index": r[1]}, }) return out if __name__ == "__main__": args = sys.argv[1:] if args == ["--vectors"]: json.dump(vectors(), sys.stdout, ensure_ascii=False, indent=2); print() elif len(args) in (1, 2) and args[-1] != "--online": online = args[0] == "--online" sys.exit(0 if verify(json.load(open(args[-1], encoding="utf-8")), online) else 1) else: print(__doc__); sys.exit(2)