"""
Solution: an audit log with a hash chain and anchors. Lab 16's audit.py and script 03
(Exercise 1), standard library only.
"""
import hashlib
import hmac
import json
import random

GENESIS = "0" * 64


def canonical(body):
    """The bytes a fingerprint is computed from: keys sorted, no spaces, UTF-8."""
    return json.dumps(body, sort_keys=True, separators=(",", ":"), ensure_ascii=False).encode()


def entry_hash(prev, seq, body):
    """sha256 of the previous fingerprint, the sequence number and the body, as hex."""
    return hashlib.sha256(prev.encode() + str(seq).encode() + canonical(body)).hexdigest()


class Anchors:
    """Copies of the latest fingerprint, kept where whoever writes the log can't write. Each copy
    carries an HMAC from a key the application doesn't hold."""

    def __init__(self, every=50, key=b"held by another team"):
        self.every = every
        self.key = key
        self.marks = []

    def sign(self, seq, h):
        return hmac.new(self.key, f"{seq}:{h}".encode(), hashlib.sha256).hexdigest()

    def add(self, seq, h):
        self.marks.append({"seq": seq, "hash": h, "mac": self.sign(seq, h)})


def append(entries, body, anchors=None):
    """Add one entry to the end of the log (a list), and anchor every `anchors.every` entries."""
    seq = len(entries)
    prev = entries[-1]["hash"] if entries else GENESIS
    e = {"seq": seq, "prev": prev, "body": body, "hash": entry_hash(prev, seq, body)}
    entries.append(e)
    if anchors and (seq + 1) % anchors.every == 0:
        anchors.add(seq, e["hash"])
    return e


def verify_plain(entries):
    """A log without fingerprints can only check its sequence numbers."""
    for i, e in enumerate(entries):
        if e["seq"] != i:
            return f"entry {i}: sequence number {e['seq']}"
    return None


def verify(entries, anchors=None):
    """None if the log is intact; otherwise the first problem found, as a message."""
    prev = GENESIS
    for i, e in enumerate(entries):
        if e["seq"] != i:
            return f"entry {i}: sequence number {e['seq']}"
        if e["prev"] != prev:
            return f"entry {i}: doesn't follow the entry before it"
        if entry_hash(e["prev"], e["seq"], e["body"]) != e["hash"]:
            return f"entry {i}: content doesn't match its hash"
        prev = e["hash"]
    if anchors:
        for m in anchors.marks:
            if not hmac.compare_digest(m["mac"], anchors.sign(m["seq"], m["hash"])):
                return f"anchor at {m['seq']}: bad signature"
            if m["seq"] >= len(entries):
                return f"anchor at {m['seq']}: the log ends at {len(entries) - 1} (entries were cut off)"
            if entries[m["seq"]]["hash"] != m["hash"]:
                return f"anchor at {m['seq']}: the log's hash differs from the anchored one"
    return None


def rehash(entries, start):
    """The cover-up: renumber and recompute every fingerprint from `start` on. Returns a new list."""
    out = [dict(e) for e in entries]
    prev = out[start - 1]["hash"] if start else GENESIS
    for i in range(start, len(out)):
        out[i]["seq"], out[i]["prev"] = i, prev
        out[i]["hash"] = entry_hash(prev, i, out[i]["body"])
        prev = out[i]["hash"]
    return out


# ---- The lab's tamper test (given) --------------------------------------------------------------

KINDS = ["edit an answer", "swap two entries", "delete an entry", "delete, then renumber + rehash",
         "edit, then rehash", "insert a fake entry, rehash", "cut off the end"]


def tamper(kind, entries, rng, new_user="mallory"):
    """One change, made by someone who can write the log, at a random position."""
    e = [dict(x, body=dict(x["body"])) for x in entries]   # a copy (bodies here are flat)
    n = len(e)
    i = rng.randrange(n - 1)
    if kind == "edit an answer":
        e[i]["body"]["answer"] = "I don't have that information."
    elif kind == "edit, then rehash":
        e[i]["body"]["user"] = new_user
        e = rehash(e, i)
    elif kind == "delete an entry":
        del e[i]
    elif kind == "delete, then renumber + rehash":
        del e[i]
        e = rehash(e, i)
    elif kind == "swap two entries":
        e[i], e[i + 1] = e[i + 1], e[i]
    elif kind == "cut off the end":
        e = e[:rng.randrange(n - 30, n)]
    elif kind == "insert a fake entry, rehash":
        fake = dict(e[i], body=dict(e[i]["body"], answer="(inserted)"))
        e.insert(i + 1, fake)
        e = rehash(e, i + 1)
    return e


def tamper_test(entries, anchors, trials=200, seed=16, new_user="mallory", kinds=KINDS):
    """Each kind of change `trials` times, in the lab's order and with its seed, so the positions are
    the lab's. How many each check caught: {kind: (plain, chain, anchored)}. Pass `kinds` to report
    only some (the others still draw their random positions, so the positions stay the lab's)."""
    rng = random.Random(seed)
    out = {}
    for kind in KINDS:
        if kind not in kinds:
            for _ in range(trials):
                rng.randrange(len(entries) - 1)
                if kind == "cut off the end":
                    rng.randrange(len(entries) - 30, len(entries))
            continue
        c = [0, 0, 0]
        for _ in range(trials):
            t = tamper(kind, entries, rng, new_user)
            chain = verify(t)
            c[0] += verify_plain(t) is not None
            c[1] += chain is not None
            # verify(t, anchors) checks the chain first, so whatever the chain caught, it catches too.
            c[2] += chain is not None or verify(t, anchors) is not None
        out[kind] = tuple(c)
    return out