#!/usr/bin/env python3
"""Independent verifier for the ntp.alastyr.com time log.

    python3 verify.py                                   verify the whole log up to the latest checkpoint
    python3 verify.py --at 2026-09-24T12:43:00Z         show the entry in force at that moment and its proof
    python3 verify.py --bundle 2026-09-24T12:43:00Z -o evidence.json
                                                        write a self-contained evidence bundle for that moment
    python3 verify.py --verify-bundle evidence.json     verify a bundle OFFLINE (no network access)
    python3 verify.py --dir ./timelog ...               work on a downloaded copy / mirror instead of the web

Requirements: Python 3.8+, the "cryptography" package (pip install cryptography).
To also check the external Roughtime anchors install roughtime-stamp (Go 1.27+):
    go install github.com/tannerryan/roughtime/cmd/roughtime-stamp@latest

What is checked
  whole log   every entry is canonical JSON, sequence numbers are gapless, every entry carries the
              SHA-256 of the previous one, the RFC 6962 Merkle root of all entries equals the root in
              the latest signed checkpoint, every anchor checkpoint is signed and matches the tree at
              its size (the log was not rewritten), every Roughtime proof is valid.
  bundle      the entry hashes to a leaf that is included (RFC 6962 inclusion proof) in a checkpoint
              signed by the log key, and that checkpoint was timestamped by independent Roughtime
              servers no later than the stated upper bound.

CONFIRM THE VERIFIER KEY independently (https://ntp.alastyr.com/en/time-evidence.html, other channels);
a verifier that takes the key from the server it is verifying trusts that server.
"""
import argparse, base64, datetime as dt, gzip, hashlib, json, os, pathlib, shutil, subprocess, sys, tempfile, urllib.error, urllib.request

BASE = 'https://ntp.alastyr.com/timelog/'
VERIFIER_KEY = 'ntp.alastyr.com/timelog+cb0bb9d1+AVE7wZiELg0QMVE6AplpKfH8Jl/UAftuIIq9ch2dnyYA'
BUNDLE_FORMAT = 'https://ntp.alastyr.com/timelog/bundle/v1'
TILE = 256


def sha(b):
    return hashlib.sha256(b).digest()


def leaf_hash(b):
    return sha(b'\x00' + b)


def node(l, r):
    return sha(b'\x01' + l + r)


# ------------------------------------------------------------------ source
class Source:
    def __init__(self, directory):
        self.dir = pathlib.Path(directory) if directory else None
        self.cache = {}

    def get(self, path, required=True):
        if path in self.cache:
            return self.cache[path]
        try:
            if self.dir:
                data = (self.dir / path).read_bytes()
            else:
                with urllib.request.urlopen(BASE + path, timeout=30) as r:
                    data = r.read()
        except (OSError, urllib.error.URLError):
            if required:
                raise SystemExit(f'cannot read {path}')
            data = None
        self.cache[path] = data
        return data


# ------------------------------------------------------------------ signed notes
def open_checkpoint(note, vkey):
    """Verify a C2SP signed note with the Ed25519 verifier key; return (origin, size, root)."""
    from cryptography.hazmat.primitives.asymmetric.ed25519 import Ed25519PublicKey
    # C2SP: the name cannot contain '+', but the base64 key can -> split from the LEFT
    name, kid, key = vkey.split('+', 2)
    raw = base64.b64decode(key)
    if raw[0] != 1:
        raise SystemExit('only Ed25519 verifier keys are supported')
    pub = Ed25519PublicKey.from_public_bytes(raw[1:])
    text = note.decode() if isinstance(note, bytes) else note
    body, sigs = text.split('\n\n', 1)
    body = (body + '\n').encode()
    for line in sigs.splitlines():
        if not line.startswith('— '):
            continue
        _, sname, sb64 = line.split(' ')
        s = base64.b64decode(sb64)
        if sname == name and s[:4].hex() == kid:
            pub.verify(s[4:], body)                      # raises if invalid
            origin, size, root = body.decode().split('\n')[:3]
            if origin != name:
                raise SystemExit('checkpoint origin does not match the key name')
            return origin, int(size), base64.b64decode(root)
    raise SystemExit('no signature by the expected key')


# ------------------------------------------------------------------ tiles
def index_path(n):
    s = f'{n:03d}'
    s = '0' * (-len(s) % 3) + s
    p = [s[i:i + 3] for i in range(0, len(s), 3)]
    return '/'.join(['x' + x for x in p[:-1]] + [p[-1]])


def read_tile(src, kind, n, width):
    """Full tile, or the partial tile of `width`; fall back to the full tile (whose
    first `width` items are identical) when the partial has been retired."""
    base = f'tile/{kind}/{index_path(n)}'
    data = None
    if width < TILE:
        data = src.get(f'{base}.p/{width}', required=False)
    if data is None:
        data = src.get(base)
    return data


def tile_hashes(src, level, n, size):
    count = size // (TILE ** level)
    width = min(TILE, count - n * TILE)
    raw = read_tile(src, level, n, width)
    return [raw[i:i + 32] for i in range(0, width * 32, 32)]


def level_hashes(src, level, start, end, size):
    out = []
    i = start
    while i < end:
        n = i // TILE
        hs = tile_hashes(src, level, n, size)
        take = min(end, (n + 1) * TILE) - i
        out += hs[i - n * TILE:i - n * TILE + take]
        i += take
    return out


def mth(src, a, b, size):
    """Merkle tree hash of leaves [a, b) using published tiles."""
    n = b - a
    if n & (n - 1) == 0 and a % n == 0:                  # aligned complete subtree
        h = n.bit_length() - 1
        level, rest = h // 8, h % 8
        hs = level_hashes(src, level, a >> (8 * level), (a >> (8 * level)) + (1 << rest), size)
        while len(hs) > 1:
            hs = [node(hs[i], hs[i + 1]) for i in range(0, len(hs), 2)]
        return hs[0]
    k = 1 << ((n - 1).bit_length() - 1)
    return node(mth(src, a, a + k, size), mth(src, a + k, b, size))


def inclusion_proof(src, i, a, b, size):
    """RFC 6962 PATH(i, D[a:b])."""
    n = b - a
    if n == 1:
        return []
    k = 1 << ((n - 1).bit_length() - 1)
    if i < a + k:
        return inclusion_proof(src, i, a, a + k, size) + [mth(src, a + k, b, size)]
    return inclusion_proof(src, i, a + k, b, size) + [mth(src, a, a + k, size)]


def root_from_inclusion(leaf, index, size, proof):
    """RFC 9162 section 2.1.3.2 verification algorithm."""
    if index >= size:
        raise ValueError('index out of range')
    fn, sn, r = index, size - 1, leaf
    for p in proof:
        if sn == 0:
            raise ValueError('proof too long')
        if fn & 1 or fn == sn:
            r = node(p, r)
            if not fn & 1:
                while fn & 1 == 0 and fn != 0:
                    fn >>= 1; sn >>= 1
        else:
            r = node(r, p)
        fn >>= 1; sn >>= 1
    if sn != 0:
        raise ValueError('proof too short')
    return r


def entry_at(src, i, size):
    n = i // TILE
    width = min(TILE, size - n * TILE)
    raw = read_tile(src, 'entries', n, width)
    j, pos = 0, 0
    while pos < len(raw):
        ln = int.from_bytes(raw[pos:pos + 2], 'big')
        if j == i - n * TILE:
            return raw[pos + 2:pos + 2 + ln]
        pos += 2 + ln; j += 1
    raise SystemExit(f'entry {i} not found in bundle {n}')


# ------------------------------------------------------------------ roughtime
def roughtime_check(checkpoint_bytes, proof_bytes, witnesses_bytes):
    tool = shutil.which('roughtime-stamp')
    if not tool:
        return None, 'roughtime-stamp not installed; Roughtime proof not checked'
    with tempfile.TemporaryDirectory() as d:
        d = pathlib.Path(d)
        (d / 'cp').write_bytes(checkpoint_bytes); (d / 'proof').write_bytes(proof_bytes)
        (d / 'w.json').write_bytes(witnesses_bytes)
        r = subprocess.run([tool, '-mode', 'verify', '-doc', str(d / 'cp'), '-in', str(d / 'proof'),
                            '-servers', str(d / 'w.json')], capture_output=True, text=True)
    if r.returncode != 0:
        raise SystemExit(f'Roughtime proof INVALID:\n{r.stderr or r.stdout}')
    upper = next((l.split(':', 1)[1].strip() for l in r.stdout.splitlines() if l.startswith('Upper bound')), None)
    return upper, 'Roughtime proof valid'


# ------------------------------------------------------------------ lookups
def parse_time(s):
    return dt.datetime.fromisoformat(s.replace('Z', '+00:00'))


def seq_at(src, idx, when):
    """Sequence number of the last SAMPLE entry at or before `when`."""
    days = [d for d in idx['days'] if d <= when.strftime('%Y-%m-%d')]
    for day in reversed(days):
        rows = json.loads(src.get(f'index/{day}.json', required=False) or b'[]')
        best = None
        for hms, seq in rows:
            if parse_time(f'{day}T{hms}Z') <= when:
                best = seq
        if best is not None:
            return best
    raise SystemExit('no entry at or before that moment')


def covering_anchor(src, idx, seq):
    """First anchor whose checkpoint includes entry `seq`."""
    for day in idx['days']:
        rows = json.loads(src.get(f'anchors/{day}/index.json', required=False) or b'[]')
        for a in rows:
            if a['size'] > seq:
                return day, a
    return None, None


# ------------------------------------------------------------------ commands
def cmd_bundle(src, idx, vkey, when, out):
    seq = seq_at(src, idx, when)
    day, anc = covering_anchor(src, idx, seq)
    if not anc:
        raise SystemExit('this entry is not covered by an external anchor yet (anchors are taken every 10 minutes)')
    cp = src.get(f'anchors/{day}/{anc["name"]}.checkpoint')
    _, size, root = open_checkpoint(cp, vkey)
    entry = entry_at(src, seq, size)
    proof = inclusion_proof(src, seq, 0, size, size)
    if root_from_inclusion(leaf_hash(entry), seq, size, proof) != root:
        raise SystemExit('inclusion proof does not reach the checkpoint root')
    bundle = {
        'format': BUNDLE_FORMAT,
        'origin': vkey.split('+', 2)[0], 'verifier_key': vkey,
        'requested_time': when.strftime('%Y-%m-%dT%H:%M:%SZ'),
        'entry_index': seq,
        'entry': json.loads(entry),
        'entry_b64': base64.b64encode(entry).decode(),
        'checkpoint': cp.decode(),
        'tree_size': size,
        'inclusion_proof': [base64.b64encode(h).decode() for h in proof],
        'anchor': {'name': f'{day}/{anc["name"]}', 'upper_bound': anc.get('upper_bound'),
                   'roughtime_proof_b64': base64.b64encode(src.get(f'anchors/{day}/{anc["name"]}.proof')).decode(),
                   'witnesses_b64': base64.b64encode(src.get('witnesses.json')).decode()},
        'how_to_verify': 'python3 verify.py --verify-bundle THIS_FILE  (https://ntp.alastyr.com/timelog/verify.py)',
    }
    pathlib.Path(out).write_text(json.dumps(bundle, ensure_ascii=False, indent=1))
    print(f'bundle   : {out}  (entry {seq}, tree size {size}, {len(proof)} proof hashes)')
    cmd_verify_bundle(out, vkey)


def cmd_verify_bundle(path, vkey):
    b = json.loads(pathlib.Path(path).read_text())
    if b.get('format') != BUNDLE_FORMAT:
        raise SystemExit('unknown bundle format')
    if b['verifier_key'] != vkey:
        raise SystemExit(f'bundle key differs from the expected key:\n  {b["verifier_key"]}')
    entry = base64.b64decode(b['entry_b64'])
    if json.loads(entry) != b['entry']:
        raise SystemExit('readable entry does not match entry_b64')
    _, size, root = open_checkpoint(b['checkpoint'], vkey)
    if size != b['tree_size']:
        raise SystemExit('tree size mismatch')
    proof = [base64.b64decode(h) for h in b['inclusion_proof']]
    if root_from_inclusion(leaf_hash(entry), b['entry_index'], size, proof) != root:
        raise SystemExit('INVALID: inclusion proof does not reach the signed checkpoint root')
    print(f'entry    : #{b["entry_index"]} at {b["entry"]["time"]}  clock_state={b["entry"].get("clock_state")}')
    print(f'inclusion: VALID -- included in checkpoint of size {size}, signature by {b["origin"]} VALID')
    upper, msg = roughtime_check(b['checkpoint'].encode(), base64.b64decode(b['anchor']['roughtime_proof_b64']),
                                 base64.b64decode(b['anchor']['witnesses_b64']))
    print(f'anchor   : {msg}' + (f'; independent witnesses signed that this checkpoint existed no later than {upper}' if upper else
                                  f' (claimed upper bound {b["anchor"].get("upper_bound")})'))


def cmd_full(src, idx, vkey, skip_anchors):
    anchors = []
    for day in idx['days']:
        rows = json.loads(src.get(f'anchors/{day}/index.json', required=False) or b'[]')
        anchors += [(day, a) for a in rows]
    _, last_size, last_root = open_checkpoint(src.get('checkpoint'), vkey)
    need = {a['size'] for _, a in anchors} | {last_size}
    stack, roots, prev, seq = [], {}, None, 0
    for day in idx['days']:
        raw = src.get(f'records/{day}.jsonl', required=False)
        raw = raw if raw is not None else gzip.decompress(src.get(f'records/{day}.jsonl.gz'))
        for line in raw.split(b'\n'):
            if not line or seq >= last_size:
                continue
            e = json.loads(line)
            if json.dumps(e, sort_keys=True, separators=(',', ':'), ensure_ascii=False).encode() != line:
                raise SystemExit(f'entry {seq} is not canonical')
            if e['seq'] != seq or e['prev'] != prev:
                raise SystemExit(f'chain broken at entry {seq}')
            prev = sha(line).hex()
            stack.append((0, leaf_hash(line)))
            while len(stack) >= 2 and stack[-1][0] == stack[-2][0]:
                (y, r), (_, l) = stack.pop(), stack.pop()
                stack.append((y + 1, node(l, r)))
            seq += 1
            if seq in need:
                r = stack[-1][1]
                for _, h in reversed(stack[:-1]):
                    r = node(h, r)
                roots[seq] = r
    if seq != last_size or roots.get(last_size) != last_root:
        raise SystemExit('records do not match the latest signed checkpoint')
    print(f'records  : {seq} entries; chain, canonical form and Merkle root match the signed checkpoint')
    witnesses = src.get('witnesses.json') if not skip_anchors else None
    ok, checked = 0, 0
    for day, a in anchors:
        if a['size'] > last_size:
            continue
        cp = src.get(f'anchors/{day}/{a["name"]}.checkpoint')
        _, size, root = open_checkpoint(cp, vkey)
        if size != a['size'] or roots.get(size) != root:
            raise SystemExit(f'anchor {day}/{a["name"]} does not match the records -- the log was rewritten')
        ok += 1
        if not skip_anchors:
            upper, msg = roughtime_check(cp, src.get(f'anchors/{day}/{a["name"]}.proof'), witnesses)
            checked += upper is not None
    note = '' if checked == ok else (' (Roughtime proofs skipped: --skip-roughtime)' if skip_anchors
                                     else ' (Roughtime proofs not checked: roughtime-stamp not installed)')
    print(f'anchors  : {ok} anchor checkpoints signed and consistent with the records; {checked} Roughtime proofs valid{note}')


def main():
    ap = argparse.ArgumentParser(description='Verify the ntp.alastyr.com time log')
    ap.add_argument('--dir', help='local copy or mirror of the log (offline)')
    ap.add_argument('--key', default=VERIFIER_KEY, help='verifier key (C2SP vkey)')
    ap.add_argument('--at', help='show the entry in force at this UTC moment, e.g. 2026-09-24T12:43:00Z')
    ap.add_argument('--bundle', help='write an evidence bundle for this UTC moment')
    ap.add_argument('-o', '--out', default='evidence.json')
    ap.add_argument('--verify-bundle', help='verify an evidence bundle offline')
    ap.add_argument('--skip-roughtime', action='store_true')
    g = ap.parse_args()
    if g.verify_bundle:
        return cmd_verify_bundle(g.verify_bundle, g.key)
    src = Source(g.dir)
    idx = json.loads(src.get('index.json'))
    if idx['verifier_key'] != g.key:
        raise SystemExit(f'the server publishes a different key than expected:\n  {idx["verifier_key"]}')
    print(f'log      : {idx["origin"]}  (started {idx["started"]}, {idx["size"]} entries)')
    if g.bundle:
        return cmd_bundle(src, idx, g.key, parse_time(g.bundle), g.out)
    if g.at:
        when = parse_time(g.at)
        seq = seq_at(src, idx, when)
        _, size, root = open_checkpoint(src.get('checkpoint'), g.key)
        entry = entry_at(src, seq, size)
        proof = inclusion_proof(src, seq, 0, size, size)
        assert root_from_inclusion(leaf_hash(entry), seq, size, proof) == root
        print(json.dumps(json.loads(entry), ensure_ascii=False, indent=1))
        day, a = covering_anchor(src, idx, seq)
        print(f'\ninclusion: entry #{seq} is included in the latest signed checkpoint (size {size})')
        print(f'anchor   : ' + (f'first external anchor {day}/{a["name"]}, upper bound {a.get("upper_bound")}'
                                if a else 'not anchored yet (every 10 minutes)'))
        return
    cmd_full(src, idx, g.key, g.skip_roughtime)


if __name__ == '__main__':
    main()