# CorpusFetch Method Slice (Zero-Prose Python Stdlib Reference)
# Canonical Residual: https://corpusfetch.com/c/which-invariants-prevent-privilege-amplification-across-attenuated-macaroon-chains-when-caveat-predicates-are-evaluated-out-of-order.md
# Remnant Warrant:    https://corpusfetch.com/c/which-invariants-prevent-privilege-amplification-across-attenuated-macaroon-chains-when-caveat-predicates-are-evaluated-out-of-order.warrant.json
# Markdown SHA-256:   9ac098352e47dabea1a9ef30a6f8cea2b63a9c97d7ae8c8c0b8b9feee09f35c8
# Code AST SHA-256:   b2d330f4e1d9e9d1f98c24bbddefeced0c91982004334589b7f9a3f755b5c10a
# Verified Classes:   ChainIntegrityError, Caveat, Macaroon
# Defensive Guards:   7 fail-closed invariants (zero external deps)

import hmac
import hashlib
from dataclasses import dataclass, field
from typing import Sequence


class ChainIntegrityError(RuntimeError):
    """Raised when a presented macaroon chain fails attenuation invariants."""
    pass


@dataclass(frozen=True)
class Caveat:
    predicate: str


@dataclass(frozen=True)
class Macaroon:
    identifier: bytes
    parent_sig: bytes          # signature of the predecessor token (chain commitment)
    caveats: tuple[Caveat, ...]
    signature: bytes


def _sign(key: bytes, identifier: bytes, parent_sig: bytes, caveats: Sequence[Caveat]) -> bytes:
    msg = identifier + b"|" + parent_sig + b"|" + b";".join(c.predicate.encode() for c in caveats)
    return hmac.new(key, msg, hashlib.sha256).digest()


def attenuate(key: bytes, parent: Macaroon, extra: Sequence[Caveat]) -> Macaroon:
    """Append caveats to a token the caller holds. Monotone by construction."""
    new_caveats = parent.caveats + tuple(extra)
    sig = _sign(key, parent.identifier, parent.signature, new_caveats)
    return Macaroon(parent.identifier, parent.signature, new_caveats, sig)


def verify_chain(key: bytes, chain: Sequence[Macaroon]) -> None:
    """
    Verify a full presented chain root->leaf. Rejects:
      - broken parent linkage (sibling derivation / omission)
      - non-monotone caveat sets (a child must be a prefix-preserving superset)
      - bad signatures
    """
    if not chain:
        raise ChainIntegrityError("empty chain")

    root = chain[0]
    expected_root_sig = _sign(key, root.identifier, b"", root.caveats)
    if not hmac.compare_digest(root.signature, expected_root_sig):
        raise ChainIntegrityError("root signature invalid")

    for prev, cur in zip(chain, chain[1:]):
        if cur.parent_sig != prev.signature:
            raise ChainIntegrityError(
                "child does not descend from presented parent (sibling derivation or omitted ancestor)"
            )
        if cur.caveats[: len(prev.caveats)] != prev.caveats:
            raise ChainIntegrityError("caveat set is not a prefix-preserving superset of parent")
        expected = _sign(key, cur.identifier, cur.parent_sig, cur.caveats)
        if not hmac.compare_digest(cur.signature, expected):
            raise ChainIntegrityError("intermediate signature invalid")


def authorize(key: bytes, chain: Sequence[Macaroon], request: dict) -> bool:
    """
    Conjunctive evaluation over the full chain. Deny-on-exception:
    an unevaluated caveat is an unverified restriction and must fail closed.
    """
    verify_chain(key, chain)
    all_caveats = [c for token in chain for c in token.caveats]
    for caveat in all_caveats:
        try:
            if not _evaluate(caveat.predicate, request):
                return False
        except Exception as exc:
            raise ChainIntegrityError(f"caveat evaluation failed closed: {caveat.predicate!r}") from exc
    return True


def _evaluate(predicate: str, request: dict) -> bool:
    # Simplified predicate engine: "key=value" or "key in {a,b}"
    if " in " in predicate:
        key, _, rest = predicate.partition(" in ")
        allowed = {x.strip() for x in rest.strip("{}").split(",")}
        return request.get(key.strip()) in allowed
    if "=" in predicate:
        key, _, val = predicate.partition("=")
        return request.get(key.strip()) == val.strip()
    raise ChainIntegrityError(f"unrecognized caveat predicate: {predicate!r}")


if __name__ == "__main__":
    SECRET = b"root-secret-held-by-orchestrator-only"

    root = Macaroon(
        identifier=b"root",
        parent_sig=b"",
        caveats=(Caveat("account=acme"),),
        signature=b"",
    )
    root = Macaroon(root.identifier, root.parent_sig, root.caveats,
                    _sign(SECRET, root.identifier, b"", root.caveats))

    # Correct: P attenuates the token it holds.
    p_token = attenuate(SECRET, root, [Caveat("action in {read,list}")])
    w_token = attenuate(SECRET, p_token, [Caveat("path prefix=/reports")])

    print("legit write:", authorize(SECRET, [root, p_token, w_token],
                                   {"account": "acme", "action": "write", "path": "/reports/q3.csv"}))

    # Attack: P derives a sibling from the root, omitting the action caveat.
    forged = attenuate(SECRET, root, [Caveat("path prefix=/reports")])
    try:
        authorize(SECRET, [root, forged], {"account": "acme", "action": "write", "path": "/reports/q3.csv"})
    except ChainIntegrityError as e:
        print("sibling derivation rejected:", e)

    # Attack: omit an ancestor entirely from the presented chain.
    try:
        authorize(SECRET, [root, w_token], {"account": "acme", "action": "read", "path": "/reports/x"})
    except ChainIntegrityError as e:
        print("omitted ancestor rejected:", e)
