contextgraph-types 2.0.0

//! Provenance attestation — turning "we have a trace" into "we have evidence"
//! (`SPEC.md` §6.5, [ADR 0010](../../docs/adr/0010-provenance-attestation.md)).
//!
//! A [`Provenance`] link carries a `digest`. A digest is **tamper-evident only
//! to a party that already trusts whoever recorded it**: it proves the bytes
//! did not change *since someone wrote that number down*, and says nothing
//! about who wrote it or whether they were entitled to. For a host reading its
//! own cache that is enough. For the auditor asking "prove this citation is
//! what the provider actually served," it is not — the digest and the frame it
//! describes were produced by the same unauthenticated party, so a provider
//! that fabricates a frame simply fabricates a matching digest.
//!
//! A signature closes that gap, and it is the only thing that does. This module
//! defines the three constructions that make a frame's provenance verifiable
//! **offline**, by a third party, with no network and no trust in the host that
//! stored it:
//!
//! 1. A **provenance chain hash** ([`provenance_chain_head`]) — a hash chain
//!    over a frame's ordered [`Provenance`] links, folded source-first, so no
//!    link can be inserted, removed, reordered, or edited without changing the
//!    head.
//! 2. A **frame commitment** ([`frame_commitment`]) — the chain head bound to
//!    the frame's full [`FrameId`] identity.
//! 3. A **Merkle root** ([`merkle_root`]) over a whole result set, with
//!    [`InclusionProof`]s, so one frame can be proven a member of a signed
//!    answer without disclosing its siblings.
//!
//! [`ProvenanceAttestation`] is the detached Ed25519 signature over (1)–(3).
//! It reaches a host on the `frames` envelope, in
//! [`ContextQueryResult::frame_attestations`](crate::ContextQueryResult::frame_attestations)
//! and
//! [`ContextQueryResult::result_attestation`](crate::ContextQueryResult::result_attestation)
//! — *beside* the frames, never inside one (`SPEC.md` §6.5.5, F6/F11).
//!
//! # Why the frame identity is inside the signed preimage
//!
//! Signing a bare chain head would be a forgery primitive, not a defense. Two
//! frames citing the same source share a chain head, so a signature over the
//! head alone can be lifted from an innocuous frame and stapled onto a
//! fabricated one: the signature verifies, the evidence is invented. The signed
//! preimage therefore commits to `(provider_id, frame_id, content_digest)` —
//! the whole [`FrameId`] triple — *and* the chain head. A signature binds to one
//! frame served by one provider, or it binds to nothing.
//!
//! # Why the encoding is length-prefixed rather than canonical JSON
//!
//! The lifecycle profile's `record_hash` canonicalizes with RFC 8785 (JCS),
//! which is the right choice there: a record's hash covers a whole open-ended
//! JSON document. A provenance chain is a fixed list of six optional strings,
//! and for that shape JCS is a liability — it makes every implementation depend
//! on a conforming JSON canonicalizer, whose number formatting and Unicode
//! escaping rules are exactly where cross-language implementations silently
//! disagree.
//!
//! This module encodes the typed fields directly, each length-prefixed
//! (`SPEC.md` §6.5.1). Length prefixing is not decoration:
//! naive concatenation is ambiguous, and a chain with `uri: "ab", range: "c"`
//! would otherwise hash identically to one with `uri: "a", range: "bc"` — a
//! collision an adversary chooses, not one they have to find. A four-byte
//! big-endian length in front of every field makes the encoding injective, and
//! any language can produce it from the typed fields with no library at all.
//!
//! # Cryptography is optional; the preimage rule is not
//!
//! Hashing and signature verification live behind the off-by-default
//! `attestation` feature, so `contextgraph-types` keeps its "zero dependencies
//! beyond serde" promise for the pure wire consumer. [`ProvenanceAttestation`]
//! itself is a **wire type and always compiles** — a host must be able to parse,
//! relay, and store an attestation it has not been built to check, exactly as it
//! relays a frame kind it does not recognize.
//!
//! The protocol defines the *preimage*; it does not define your signing
//! backend. [`frame_commitment`] and [`merkle_root`] are public so a provider
//! holding keys in an HSM, a KMS, or a hardware token signs the bytes itself
//! and never hands this crate a secret. [`sign_frame_attestation`] exists for
//! providers and tests that are content to sign in-process.

use serde::{Deserialize, Serialize};

use crate::frame::Provenance;
use crate::identity::FrameId;

/// The signature algorithm this revision defines. `algorithm` is a string, not
/// an enum, precisely so a post-quantum successor is an additive change rather
/// than a new major family — see [`ProvenanceAttestation::algorithm`].
pub const ALGORITHM_ED25519: &str = "ed25519";

/// The domain-separation tags and Merkle prefixes the hashing rules use
/// (`SPEC.md` §6.5.1). Only referenced by the gated hashing code, but normative:
/// a reimplementation in another language must use these exact byte strings or
/// it will compute different commitments and interoperate with nothing.
#[cfg(feature = "attestation")]
mod domain {
    /// Domain-separation tag for the hash-chain genesis.
    pub(super) const GENESIS: &[u8] = b"contextgraph/attest/1/genesis";
    /// Domain-separation tag for one provenance link.
    pub(super) const LINK: &[u8] = b"contextgraph/attest/1/link";
    /// Domain-separation tag for a frame commitment.
    pub(super) const FRAME: &[u8] = b"contextgraph/attest/1/frame";
    /// Domain-separation tag for an empty Merkle tree.
    pub(super) const MERKLE_EMPTY: &[u8] = b"contextgraph/attest/1/merkle-empty";
    /// RFC 6962 leaf prefix. Distinct from [`MERKLE_NODE`] so a leaf hash can
    /// never be reinterpreted as an interior node — the second-preimage defense
    /// that makes a Merkle proof mean what it claims.
    pub(super) const MERKLE_LEAF: &[u8] = &[0x00];
    /// RFC 6962 interior-node prefix.
    pub(super) const MERKLE_NODE: &[u8] = &[0x01];
}

/// A detached attestation binding one frame's provenance to a signing identity
/// (`SPEC.md` §6.5).
///
/// **Detached, always.** Like the lifecycle profile's
/// [`RecordAttestation`](crate::RecordAttestation), this never travels inside
/// the preimage it signs. Re-signing after a key rotation, or a second attester
/// countersigning the same frame, must not perturb the frame's content-addressed
/// identity — and it cannot, because the attestation is metadata beside the
/// frame rather than a field within it.
///
/// It is a **distinct type** from `RecordAttestation` even though five of six
/// fields match. The two sign different preimages under different domain tags,
/// and a shared type would invite the one mistake the domain separation exists
/// to prevent: presenting a record attestation as a frame attestation. The
/// cryptography already refuses that; the type system should make it unsayable.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct ProvenanceAttestation {
    /// The `sha256:<hex>` commitment this attestation signs — a
    /// [`frame_commitment`] for a single frame, or a [`merkle_root`] for a
    /// result set.
    pub signed_commitment: String,
    /// The signing key's id. Rotation is expressed by a new `key_id`, never by
    /// reusing one, so an archived attestation always names the exact key that
    /// produced it.
    pub key_id: String,
    /// The signature scheme, e.g. [`ALGORITHM_ED25519`].
    ///
    /// A string rather than an enum: a verifier that does not recognize the
    /// value returns [`AttestationVerdict::UnknownAlgorithm`] and declines,
    /// which is a *safe* failure. Freezing the set into an enum would make
    /// adopting a post-quantum scheme a breaking wire change, and this protocol
    /// promises no flag day inside a major family.
    pub algorithm: String,
    /// The attesting authority — who is accountable for the claim, as distinct
    /// from which key mechanically produced it.
    pub attester_id: String,
    /// The detached signature, lowercase hex.
    ///
    /// Hex rather than base64 to match the `sha256:<hex>` convention every other
    /// digest in this protocol already uses; one encoding across the wire
    /// surface is worth more than the 40 bytes base64 would save.
    pub signature: String,
    /// When the attestation was issued (a `SPEC.md` §F4 protocol timestamp).
    pub issued_at: String,
}

impl ProvenanceAttestation {
    /// Build an attestation from its parts.
    pub fn new(
        signed_commitment: impl Into<String>,
        key_id: impl Into<String>,
        algorithm: impl Into<String>,
        attester_id: impl Into<String>,
        signature: impl Into<String>,
        issued_at: impl Into<String>,
    ) -> Self {
        Self {
            signed_commitment: signed_commitment.into(),
            key_id: key_id.into(),
            algorithm: algorithm.into(),
            attester_id: attester_id.into(),
            signature: signature.into(),
            issued_at: issued_at.into(),
        }
    }

    /// Whether this attestation names a scheme this revision defines.
    ///
    /// Advisory: a verifier reports [`AttestationVerdict::UnknownAlgorithm`]
    /// rather than treating an unrecognized scheme as a failure to *validate*.
    /// The distinction matters to an auditor — "I cannot check this" is a
    /// different finding from "this is forged."
    pub fn uses_known_algorithm(&self) -> bool {
        self.algorithm == ALGORITHM_ED25519
    }

    /// Whether `issued_at` is a well-formed protocol timestamp (`SPEC.md` §F4).
    pub fn has_well_formed_issued_at(&self) -> bool {
        crate::validate::is_protocol_timestamp(&self.issued_at)
    }
}

/// One step of a Merkle [`InclusionProof`]: the sibling hash, and which side it
/// sits on.
///
/// RFC 6962 lets a verifier recover the side from index arithmetic. This carries
/// it explicitly instead. The redundancy costs one bool per step and removes an
/// entire class of verifier bug — an off-by-one in the index recursion produces
/// a *wrong root* rather than a silently-accepted proof, and a hand-written
/// verifier in another language is far likelier to get a stated side right than
/// to re-derive the split correctly.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct InclusionStep {
    /// The sibling subtree hash, `sha256:<hex>`.
    pub sibling: String,
    /// Whether the sibling is the **left** operand at this level.
    pub sibling_is_left: bool,
}

/// The longest inclusion path this crate will walk (`SPEC.md` §6.5.3).
///
/// A path of *n* steps describes a Merkle tree over up to 2ⁿ leaves, so 64
/// steps covers every answer that could exist and then some. The cap is not
/// about correctness — a wrong path yields a wrong root and fails the
/// comparison — it is about work: each step costs a hash, the path arrives from
/// the provider, and a verifier that walked an arbitrary one would hash for as
/// long as a peer cared to make it.
pub const MAX_INCLUSION_PATH_STEPS: usize = 64;

/// A proof that one frame commitment is a leaf of a signed [`merkle_root`]
/// (`SPEC.md` §6.5.3).
///
/// This is what makes a signed answer *selectively* disclosable. A host that
/// served twelve frames can prove to an auditor that one specific frame was in
/// the signed set — and prove the provider committed to it before knowing which
/// one would be questioned — while disclosing nothing about the other eleven
/// beyond their hashes.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct InclusionProof {
    /// The leaf's index in canonical order.
    pub leaf_index: usize,
    /// How many leaves the tree held. Part of the proof because a root alone
    /// does not pin the tree's size, and a verifier that ignores it can be shown
    /// a proof from a differently-shaped tree.
    pub leaf_count: usize,
    /// Sibling hashes from the leaf upward.
    pub path: Vec<InclusionStep>,
}

/// What a result set says about one frame's attestation — the wire carrier that
/// keeps a [`ProvenanceAttestation`] *beside* the frame it covers
/// (`SPEC.md` §6.5.5, F11).
///
/// # Why the identity is echoed in full
///
/// A parallel array indexed by position would be smaller and unusable as
/// evidence: a provider that reorders, omits, or duplicates a frame would shift
/// an attestation onto the wrong one, and a host filtering the set — which is
/// the normal case — would have to re-derive the mapping from an order nobody
/// wrote down. Carrying the whole
/// [`FrameId`] triple makes an entry self-describing, which is the same
/// reasoning [`FrameVerdict`](crate::FrameVerdict) already applies to
/// `context/verify`. It is also exactly what a verifier needs: `provider_id`
/// and `content_digest` are two of the three inputs to
/// [`frame_commitment`], and neither is recoverable from the frame body alone.
///
/// # Why both members are optional
///
/// The cheapest honest way to sign an answer is **one** signature over the
/// result-set Merkle root, with a per-frame inclusion proof and no per-frame
/// signature at all. Requiring `attestation` would make that shape
/// unrepresentable and force a provider into *n* signatures to say what one
/// says. Requiring `inclusion_proof` would tax a provider that signs frames
/// individually and publishes no root. An entry carrying neither is noise, and
/// [`carries_evidence`](Self::carries_evidence) is how a host says so.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct FrameAttestation {
    /// The frame this entry attests, named in full rather than by position.
    pub frame: FrameId,
    /// A detached signature over this frame's own [`frame_commitment`].
    ///
    /// Absent when the provider signed only the result-set root: the frame is
    /// then attested *through* `inclusion_proof`, not on its own.
    #[serde(default, skip_serializing_if = "Option::is_none")]
    pub attestation: Option<ProvenanceAttestation>,
    /// A proof that this frame's commitment is a leaf of the signed
    /// `result_attestation` root (`SPEC.md` §6.5.3).
    ///
    /// Optional on the wire, and the reason is a host that keeps a *subset*:
    /// once frames are dropped their sibling commitments are gone, and the root
    /// can never be recomputed again. See
    /// [ADR 0014](https://github.com/macanderson/context-graph-protocol/blob/main/docs/adr/0014-attestations-on-the-wire.md).
    #[serde(default, skip_serializing_if = "Option::is_none")]
    pub inclusion_proof: Option<InclusionProof>,
}

impl FrameAttestation {
    /// A per-frame signature with no inclusion proof.
    pub fn signed(frame: FrameId, attestation: ProvenanceAttestation) -> Self {
        Self {
            frame,
            attestation: Some(attestation),
            inclusion_proof: None,
        }
    }

    /// Membership of a signed result set, with no per-frame signature.
    pub fn proven(frame: FrameId, inclusion_proof: InclusionProof) -> Self {
        Self {
            frame,
            attestation: None,
            inclusion_proof: Some(inclusion_proof),
        }
    }

    /// Whether this entry carries anything a verifier can act on.
    ///
    /// An entry with neither a signature nor a proof names a frame and asserts
    /// nothing about it. A host **MUST NOT** read that as attested — it is
    /// wire noise, and F9's "unverifiable degrades to unattested" covers it.
    pub fn carries_evidence(&self) -> bool {
        self.attestation.is_some() || self.inclusion_proof.is_some()
    }

    /// Attach an inclusion proof, so a per-frame signature and result-set
    /// membership travel together.
    pub fn with_inclusion_proof(mut self, proof: InclusionProof) -> Self {
        self.inclusion_proof = Some(proof);
        self
    }
}

/// The outcome of checking a [`ProvenanceAttestation`] (`SPEC.md` §6.5.4).
///
/// Every failure is *named*. A boolean would collapse "this signature is
/// forged" into "I was handed a truncated key," and those call for opposite
/// responses: the first is an incident, the second is a configuration bug.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum AttestationVerdict {
    /// The signature verifies against the recomputed commitment, and that
    /// commitment binds the frame's content.
    Valid,
    /// The signature verifies, but over a preimage that does not bind the
    /// frame's content: the frame declared no `content_digest`, so
    /// [`frame_commitment`] hashed the *absence* of one (`SPEC.md` §6.5.2).
    ///
    /// What this does and does not prove is the whole reason the variant
    /// exists. It proves the named provider issued a frame with this id and
    /// this provenance chain. It does not prove the bytes served under that id
    /// are the bytes that were signed — the provider can serve one document
    /// today and a different one tomorrow, and this same signature keeps
    /// verifying, because the content was never in the preimage.
    ///
    /// Before this variant existed, that case returned [`Valid`](Self::Valid)
    /// and a verifier had no way to tell the two apart (#128). A host that
    /// rendered such a frame as "signed" was making a claim the signature did
    /// not support.
    ///
    /// [`is_valid`](Self::is_valid) is **false** here, so the default answer is
    /// the safe one. A host that has its own reason to accept an identity-only
    /// attestation must say so by matching this variant or calling
    /// [`signature_verifies`](Self::signature_verifies) — which is the point:
    /// the decision becomes visible in the code that makes it.
    ///
    /// A conformant attester does not produce this. `SPEC.md` §6.5.2 requires a
    /// provider that signs a frame to populate `content_digest`; encountering
    /// this verdict means the frame was signed by a non-conformant attester, or
    /// predates that requirement.
    ValidIdentityOnly,
    /// The signature is well-formed and verifies, but over a *different*
    /// commitment than this frame produces — the frame or its provenance was
    /// altered after signing. The loudest possible finding.
    CommitmentMismatch {
        /// The commitment recomputed from the frame in hand.
        expected: String,
        /// The commitment the attestation claims to sign.
        signed: String,
    },
    /// The commitment matches but the signature does not verify under the
    /// supplied key: a forgery, or the wrong key.
    BadSignature,
    /// The named algorithm is not one this build can check. Not a failure to
    /// validate — a refusal to guess.
    UnknownAlgorithm(String),
    /// The public key was not a well-formed key for the named algorithm.
    MalformedKey,
    /// The signature field was not well-formed for the named algorithm.
    MalformedSignature,
    /// `signed_commitment` was not a well-formed `sha256:<hex>` digest.
    MalformedCommitment,
}

impl AttestationVerdict {
    /// Whether this verdict is [`Valid`](Self::Valid) — the signature checks
    /// out *and* it binds the frame's content.
    ///
    /// A host **MUST NOT** treat any other verdict as provisionally acceptable:
    /// the point of an attestation is that "I could not check it" and "it is
    /// good" are never the same answer.
    ///
    /// That includes [`ValidIdentityOnly`](Self::ValidIdentityOnly), which is
    /// deliberately not valid here. Its signature does verify, but over a
    /// preimage that says nothing about the bytes in hand, and a host asking
    /// "is this good?" is asking about the bytes. Use
    /// [`signature_verifies`](Self::signature_verifies) to ask the narrower
    /// question on purpose.
    pub fn is_valid(&self) -> bool {
        matches!(self, Self::Valid)
    }

    /// Whether the signature itself checked out, whatever it covers.
    ///
    /// True for [`Valid`](Self::Valid) and
    /// [`ValidIdentityOnly`](Self::ValidIdentityOnly). This is the question to
    /// ask when the caller genuinely wants provider identity and provenance
    /// without a claim about content — an audit trail of who answered, say,
    /// rather than a check that an answer is unaltered.
    ///
    /// It is a separate method rather than a looser `is_valid` because the
    /// difference between them is the whole of #128: one accepts a frame whose
    /// content can be swapped without disturbing the signature, and the other
    /// does not. Whichever a caller wants, it should be legible at the call
    /// site which one they asked for.
    pub fn signature_verifies(&self) -> bool {
        matches!(self, Self::Valid | Self::ValidIdentityOnly)
    }

    /// Whether the verified commitment binds the frame's content bytes.
    ///
    /// Only [`Valid`](Self::Valid) does. A verdict that did not verify at all
    /// binds nothing, so this is false for every failure too.
    pub fn binds_content(&self) -> bool {
        matches!(self, Self::Valid)
    }
}

// ---------------------------------------------------------------------------
// Canonical encoding (`SPEC.md` §6.5.1) — dependency-free, so the rule is
// readable and reimplementable even in a build with `attestation` disabled.
// ---------------------------------------------------------------------------

/// Append a length-prefixed string: `u32be(len) || utf8`.
fn enc_str(out: &mut Vec<u8>, s: &str) {
    out.extend_from_slice(&(s.len() as u32).to_be_bytes());
    out.extend_from_slice(s.as_bytes());
}

/// Append a length-prefixed optional string: `0x00` for absent, `0x01 ||
/// enc_str` for present.
///
/// The presence byte is what keeps absent distinct from empty. Without it
/// `uri: None` and `uri: Some("")` would encode identically, and a provider
/// could drop a URI from a signed chain without disturbing the hash.
fn enc_opt(out: &mut Vec<u8>, s: Option<&str>) {
    match s {
        None => out.push(0x00),
        Some(s) => {
            out.push(0x01);
            enc_str(out, s);
        }
    }
}

/// The canonical encoding of one provenance link (`SPEC.md` §6.5.1).
///
/// Field order is fixed by the struct's declaration order and pinned by the
/// spec — it is part of the normative rule, not an implementation detail, and
/// changing it is a breaking wire change.
pub fn encode_provenance_link(link: &Provenance) -> Vec<u8> {
    let mut out = Vec::new();
    enc_str(&mut out, &link.kind);
    enc_opt(&mut out, link.uri.as_deref());
    enc_opt(&mut out, link.range.as_deref());
    enc_opt(&mut out, link.digest.as_deref());
    enc_opt(&mut out, link.method.as_deref());
    enc_opt(&mut out, link.by.as_deref());
    out
}

/// Render 32 raw bytes as this protocol's `sha256:<hex>` digest string.
pub fn digest_string(bytes: &[u8; 32]) -> String {
    let mut s = String::with_capacity(7 + 64);
    s.push_str("sha256:");
    for b in bytes {
        // Lowercase hex, two chars per byte — the form `is_well_formed_digest`
        // accepts and every other digest in the protocol already uses.
        s.push(char::from_digit((b >> 4) as u32, 16).expect("nibble is < 16"));
        s.push(char::from_digit((b & 0x0f) as u32, 16).expect("nibble is < 16"));
    }
    s
}

/// Parse **lowercase** hex into bytes. `None` on any byte outside `0-9a-f`, or
/// on an odd length.
///
/// Lowercase-only is the protocol's grammar, not a preference. `SPEC.md` spells
/// a digest as 64 lowercase hex characters and
/// [`is_well_formed_digest`](crate::is_well_formed_digest) enforces exactly
/// that — its own doctest asserts the uppercase form is rejected.
///
/// This function did not, and the divergence it created is the kind §6.5 exists
/// to eliminate (#145). `to_digit(16)` accepts `A`-`F`, and both `parse_digest`
/// and the signature branch of [`verify_commitment`] decode through here — so an
/// attestation carrying an uppercase `signed_commitment` or signature verified
/// against the Rust reference while every SDK port rejected it as malformed.
/// The same bytes, read by two conforming implementations, produced opposite
/// verdicts. An auditor's answer must not depend on which language opened the
/// file.
///
/// Nothing emits uppercase — `digest_string` and `sign_commitment` both write
/// lowercase — so this narrows what is *accepted*, never what is produced.
#[cfg(feature = "attestation")]
fn from_hex(s: &str) -> Option<Vec<u8>> {
    if !s.len().is_multiple_of(2) {
        return None;
    }
    let mut out = Vec::with_capacity(s.len() / 2);
    // `as_chunks::<2>()` over `chunks_exact(2)`: the length check above already
    // rules out a remainder, and the fixed-size chunk lets the compiler see both
    // indexes are in bounds.
    let (pairs, _) = s.as_bytes().as_chunks::<2>();
    for pair in pairs {
        let hi = lowercase_hex_digit(pair[0])?;
        let lo = lowercase_hex_digit(pair[1])?;
        out.push(hi * 16 + lo);
    }
    Some(out)
}

/// One lowercase hex digit's value, or `None` for anything else — uppercase
/// `A`-`F` included.
///
/// Spelled out rather than reached through `char::to_digit(16)`, which accepts
/// both cases and is what let the uppercase form through. Matching on the byte
/// makes the accepted set visible at the point it is decided.
#[cfg(feature = "attestation")]
fn lowercase_hex_digit(byte: u8) -> Option<u8> {
    match byte {
        b'0'..=b'9' => Some(byte - b'0'),
        b'a'..=b'f' => Some(byte - b'a' + 10),
        _ => None,
    }
}

/// Parse a `sha256:<hex>` digest string into its 32 raw bytes.
#[cfg(feature = "attestation")]
fn parse_digest(digest: &str) -> Option<[u8; 32]> {
    let hex = digest.strip_prefix("sha256:")?;
    let bytes = from_hex(hex)?;
    bytes.try_into().ok()
}

// ---------------------------------------------------------------------------
// Hashing and signing — gated, because they need real cryptography.
// ---------------------------------------------------------------------------

#[cfg(feature = "attestation")]
mod crypto {
    use super::*;
    use crate::frame::ContextFrame;
    use ed25519_dalek::{Signature, Signer, SigningKey, VerifyingKey};
    use sha2::{Digest, Sha256};

    /// SHA-256 over a sequence of parts, hashed in order without any separator
    /// beyond the parts' own length prefixes.
    fn sha256(parts: &[&[u8]]) -> [u8; 32] {
        let mut hasher = Sha256::new();
        for part in parts {
            hasher.update(part);
        }
        hasher.finalize().into()
    }

    /// The head of a frame's provenance hash chain (`SPEC.md` §6.5.2).
    ///
    /// Links fold **source-first**, matching the order [`Provenance`] is
    /// documented to carry (closest-to-source first), so each link commits to
    /// everything nearer the source than itself:
    ///
    /// ```text
    /// h₋₁ = SHA256(domain::GENESIS)
    /// hᵢ  = SHA256(domain::LINK ‖ hᵢ₋₁ ‖ encode(linkᵢ))
    /// head = hₙ₋₁          (or h₋₁ for an empty chain)
    /// ```
    ///
    /// Because every step consumes the previous head, no link can be inserted,
    /// dropped, reordered, or edited without changing the result — which is the
    /// property a bare per-link digest never had. An empty chain hashes to the
    /// genesis value rather than to zero or to a sentinel, so "no provenance" is
    /// a *stated* claim a signature can cover, not a gap.
    pub fn provenance_chain_head(links: &[Provenance]) -> [u8; 32] {
        let mut head = sha256(&[domain::GENESIS]);
        for link in links {
            let encoded = encode_provenance_link(link);
            head = sha256(&[domain::LINK, &head, &encoded]);
        }
        head
    }

    /// The commitment binding one frame's identity to its provenance chain
    /// (`SPEC.md` §6.5.2) — the preimage a single-frame attestation signs.
    ///
    /// ```text
    /// SHA256(
    ///   domain::FRAME ‖ enc(provider_id) ‖ enc(frame.id)
    ///                ‖ enc_opt(frame.content_digest) ‖ chain_head
    /// )
    /// ```
    ///
    /// `content_digest` is included so that, **when the frame declares one**,
    /// the signature covers the frame's *bytes* and not merely its name.
    ///
    /// When the frame declares none, it does not. `enc_opt` writes a single
    /// `0x00` presence byte, so the preimage records the absence honestly
    /// rather than substituting a placeholder — but what gets signed is then
    /// identity and provenance alone, and a provider can re-serve entirely
    /// different content under the same frame id with that signature still
    /// checking out. The encoding is doing its job; the guarantee is simply
    /// narrower than the presence of a signature suggests.
    ///
    /// Two things follow, and both are load-bearing (#128):
    ///
    /// - `SPEC.md` §6.5.2 requires a provider that *signs* a frame to populate
    ///   `content_digest`. A digest-less frame remains conformant; signing one
    ///   is not. This function still computes the commitment for such a frame,
    ///   because a verifier has to be able to check signatures produced before
    ///   that rule, or by an implementation that ignores it.
    /// - [`verify_frame_attestation`] returns
    ///   [`AttestationVerdict::ValidIdentityOnly`] rather than
    ///   [`AttestationVerdict::Valid`] for exactly that case, so no caller can
    ///   mistake the narrower guarantee for the wider one.
    ///
    /// A frame that declares no digest and carries no attestation is a
    /// different thing again: unverifiable by design
    /// (`docs/context-reuse.md` §4), and no rule here applies to it.
    pub fn frame_commitment(provider_id: &str, frame: &ContextFrame) -> [u8; 32] {
        let chain_head = provenance_chain_head(&frame.provenance);
        let mut preimage = Vec::new();
        enc_str(&mut preimage, provider_id);
        enc_str(&mut preimage, &frame.id);
        enc_opt(&mut preimage, frame.content_digest.as_deref());
        sha256(&[domain::FRAME, &preimage, &chain_head])
    }

    /// Every frame of a result set paired with its commitment, in the
    /// protocol's canonical [`FrameId`] order (`SPEC.md` §6.3, §6.5.3).
    ///
    /// The order is the whole point: a Merkle root is a function of leaf
    /// *sequence*, so a provider and a verifier that sort differently compute
    /// different roots from identical frames. Sorting by the identity triple —
    /// the order deterministic composition already uses — means neither side
    /// has to preserve, transmit, or agree on the order the frames happened to
    /// arrive in.
    pub fn result_set_commitments(
        provider_id: &str,
        frames: &[ContextFrame],
    ) -> Vec<(FrameId, [u8; 32])> {
        let mut ordered: Vec<(FrameId, &ContextFrame)> = frames
            .iter()
            .map(|frame| (frame.identity(provider_id), frame))
            .collect();
        ordered.sort_by(|(a, _), (b, _)| a.cmp(b));
        ordered
            .into_iter()
            .map(|(id, frame)| {
                let commitment = frame_commitment(provider_id, frame);
                (id, commitment)
            })
            .collect()
    }

    /// The Merkle root a provider signs to attest a whole answer
    /// (`SPEC.md` §6.5.3, F12).
    ///
    /// The leaves are exactly the frames carried in the result — never a larger
    /// candidate set the provider truncated away. A root over frames the host
    /// never received is unverifiable by construction, and an unverifiable root
    /// is worse than none: it looks like evidence.
    pub fn result_set_root(provider_id: &str, frames: &[ContextFrame]) -> [u8; 32] {
        let commitments: Vec<[u8; 32]> = result_set_commitments(provider_id, frames)
            .into_iter()
            .map(|(_, commitment)| commitment)
            .collect();
        merkle_root(&commitments)
    }

    /// A Merkle leaf hash, RFC 6962 style: `SHA256(0x00 ‖ commitment)`.
    fn leaf_hash(commitment: &[u8; 32]) -> [u8; 32] {
        sha256(&[domain::MERKLE_LEAF, commitment])
    }

    /// A Merkle interior node, RFC 6962 style: `SHA256(0x01 ‖ left ‖ right)`.
    fn node_hash(left: &[u8; 32], right: &[u8; 32]) -> [u8; 32] {
        sha256(&[domain::MERKLE_NODE, left, right])
    }

    /// The largest power of two strictly less than `n` (RFC 6962's split point).
    /// Only meaningful for `n >= 2`.
    fn split_point(n: usize) -> usize {
        let mut k = 1;
        while k * 2 < n {
            k *= 2;
        }
        k
    }

    /// The Merkle root over a set of frame commitments (`SPEC.md` §6.5.3).
    ///
    /// RFC 6962's tree shape, chosen over "duplicate the last leaf on an odd
    /// level" because that shortcut admits two distinct leaf sets with the same
    /// root — an ambiguity that is fine for a checksum and disqualifying for
    /// evidence. Callers pass commitments in the protocol's canonical
    /// [`FrameId`](crate::FrameId) order so the root is reproducible.
    pub fn merkle_root(commitments: &[[u8; 32]]) -> [u8; 32] {
        match commitments.len() {
            0 => sha256(&[domain::MERKLE_EMPTY]),
            1 => leaf_hash(&commitments[0]),
            n => {
                let k = split_point(n);
                node_hash(
                    &merkle_root(&commitments[..k]),
                    &merkle_root(&commitments[k..]),
                )
            }
        }
    }

    /// Build an [`InclusionProof`] for `leaf_index` within `commitments`.
    /// `None` if the index is out of range.
    pub fn inclusion_proof(commitments: &[[u8; 32]], leaf_index: usize) -> Option<InclusionProof> {
        if leaf_index >= commitments.len() {
            return None;
        }
        let mut path = Vec::new();
        collect_path(commitments, leaf_index, &mut path);
        Some(InclusionProof {
            leaf_index,
            leaf_count: commitments.len(),
            path,
        })
    }

    /// Walk down the tree accumulating sibling hashes, leaf-upward.
    fn collect_path(commitments: &[[u8; 32]], index: usize, path: &mut Vec<InclusionStep>) {
        if commitments.len() <= 1 {
            return;
        }
        let k = split_point(commitments.len());
        if index < k {
            collect_path(&commitments[..k], index, path);
            path.push(InclusionStep {
                sibling: digest_string(&merkle_root(&commitments[k..])),
                sibling_is_left: false,
            });
        } else {
            collect_path(&commitments[k..], index - k, path);
            path.push(InclusionStep {
                sibling: digest_string(&merkle_root(&commitments[..k])),
                sibling_is_left: true,
            });
        }
    }

    /// Recompute a Merkle root from a leaf commitment and its proof.
    ///
    /// This is the whole offline story: an auditor holding one frame, its proof,
    /// and a signed root needs nothing else — no network, no host, no provider.
    /// `None` if any sibling in the path is malformed.
    pub fn root_from_proof(commitment: &[u8; 32], proof: &InclusionProof) -> Option<[u8; 32]> {
        if proof.leaf_index >= proof.leaf_count {
            return None;
        }
        let mut acc = leaf_hash(commitment);
        for step in &proof.path {
            let sibling = parse_digest(&step.sibling)?;
            acc = if step.sibling_is_left {
                node_hash(&sibling, &acc)
            } else {
                node_hash(&acc, &sibling)
            };
        }
        Some(acc)
    }

    /// Verify a detached attestation over a single frame (`SPEC.md` §6.5.4).
    ///
    /// Pure and offline. `public_key` is raw bytes rather than an
    /// `ed25519_dalek` type on purpose: the public API of this crate names no
    /// cryptography library, so the backend can be replaced — or a
    /// post-quantum scheme added — without a breaking change to callers.
    pub fn verify_frame_attestation(
        provider_id: &str,
        frame: &ContextFrame,
        attestation: &ProvenanceAttestation,
        public_key: &[u8],
    ) -> AttestationVerdict {
        let expected = frame_commitment(provider_id, frame);
        let verdict = verify_commitment(&expected, attestation, public_key);
        // A frame with no `content_digest` was committed to by id and
        // provenance alone, so a passing signature says nothing about the bytes
        // (#128). Downgrade the verdict rather than let `Valid` carry a
        // guarantee this preimage never made. Every failing verdict is left
        // exactly as it is — it is already the more specific answer.
        match verdict {
            AttestationVerdict::Valid if frame.content_digest.is_none() => {
                AttestationVerdict::ValidIdentityOnly
            }
            other => other,
        }
    }

    /// Verify that a frame was a leaf of a signed result-set root
    /// (`SPEC.md` §6.5.3, F13).
    ///
    /// This is the other half of §6.5. A provider that signs **one** root and
    /// ships a per-frame [`InclusionProof`] has attested every frame it served
    /// with a single signature, and the `attestation` member of the matching
    /// [`FrameAttestation`] entry is then absent. A verifier that only knew how
    /// to check per-frame signatures would report every such frame as
    /// unattested — the cheapest honest signing shape would be the one nothing
    /// could check — which is why this lives beside
    /// [`verify_frame_attestation`] rather than inside one host.
    ///
    /// `result_attestation` is the answer-level attestation, whose
    /// `signed_commitment` must equal the root this proof recomputes from the
    /// frame's own commitment.
    ///
    /// The content-binding rule is [`verify_frame_attestation`]'s, unchanged
    /// and for the same reason (#128): the leaf is a [`frame_commitment`], so a
    /// frame that declares no `content_digest` is committed to by identity and
    /// provenance alone however many hashes sit between it and the signature.
    ///
    /// # Bounded work
    ///
    /// Every field of `proof` comes from the provider, and each step of the
    /// path costs a hash. [`MAX_INCLUSION_PATH_STEPS`] caps that before any
    /// hashing starts: a longer path describes a tree with more leaves than any
    /// answer can hold, and is rejected on its length rather than walked.
    pub fn verify_frame_inclusion(
        provider_id: &str,
        frame: &ContextFrame,
        proof: &InclusionProof,
        result_attestation: &ProvenanceAttestation,
        public_key: &[u8],
    ) -> AttestationVerdict {
        if proof.path.len() > MAX_INCLUSION_PATH_STEPS {
            return AttestationVerdict::MalformedCommitment;
        }
        let commitment = frame_commitment(provider_id, frame);
        let Some(root) = root_from_proof(&commitment, proof) else {
            // A malformed sibling, or a leaf index outside the tree the proof
            // describes. Either way there is no root to compare against, and
            // that is a malformed commitment rather than a bad signature.
            return AttestationVerdict::MalformedCommitment;
        };
        match verify_commitment(&root, result_attestation, public_key) {
            AttestationVerdict::Valid if frame.content_digest.is_none() => {
                AttestationVerdict::ValidIdentityOnly
            }
            other => other,
        }
    }

    /// Verify a detached attestation over an already-computed commitment — a
    /// [`merkle_root`] for a result set, or a [`frame_commitment`].
    pub fn verify_commitment(
        expected: &[u8; 32],
        attestation: &ProvenanceAttestation,
        public_key: &[u8],
    ) -> AttestationVerdict {
        if attestation.algorithm != ALGORITHM_ED25519 {
            return AttestationVerdict::UnknownAlgorithm(attestation.algorithm.clone());
        }
        let Some(signed) = parse_digest(&attestation.signed_commitment) else {
            return AttestationVerdict::MalformedCommitment;
        };
        // Compare commitments *before* touching the signature. A mismatch means
        // the frame changed after signing, and saying so is far more useful to
        // an operator than the "bad signature" a naive order would report.
        if signed != *expected {
            return AttestationVerdict::CommitmentMismatch {
                expected: digest_string(expected),
                signed: attestation.signed_commitment.clone(),
            };
        }
        let Ok(key_bytes) = <[u8; 32]>::try_from(public_key) else {
            return AttestationVerdict::MalformedKey;
        };
        let Ok(verifying_key) = VerifyingKey::from_bytes(&key_bytes) else {
            return AttestationVerdict::MalformedKey;
        };
        let Some(sig_bytes) = from_hex(&attestation.signature) else {
            return AttestationVerdict::MalformedSignature;
        };
        let Ok(sig_bytes) = <[u8; 64]>::try_from(sig_bytes.as_slice()) else {
            return AttestationVerdict::MalformedSignature;
        };
        let signature = Signature::from_bytes(&sig_bytes);
        // `verify_strict` rejects small-order public keys and the malleable
        // signature forms `verify` tolerates. For evidence, the strict variant
        // is the only defensible choice: a signature that two verifiers can
        // disagree about is not evidence.
        match verifying_key.verify_strict(&signed, &signature) {
            Ok(()) => AttestationVerdict::Valid,
            Err(_) => AttestationVerdict::BadSignature,
        }
    }

    /// Sign a frame's commitment in-process, for providers content to hold key
    /// material in memory.
    ///
    /// A provider using an HSM or KMS instead calls [`frame_commitment`],
    /// signs the 32 bytes with its own backend, and assembles the
    /// [`ProvenanceAttestation`] by hand — the protocol specifies the preimage,
    /// never the custody of the key.
    pub fn sign_frame_attestation(
        provider_id: &str,
        frame: &ContextFrame,
        signing_key_seed: &[u8; 32],
        key_id: impl Into<String>,
        attester_id: impl Into<String>,
        issued_at: impl Into<String>,
    ) -> ProvenanceAttestation {
        let commitment = frame_commitment(provider_id, frame);
        sign_commitment(
            &commitment,
            signing_key_seed,
            key_id,
            attester_id,
            issued_at,
        )
    }

    /// Sign an arbitrary commitment (a frame commitment or a Merkle root).
    pub fn sign_commitment(
        commitment: &[u8; 32],
        signing_key_seed: &[u8; 32],
        key_id: impl Into<String>,
        attester_id: impl Into<String>,
        issued_at: impl Into<String>,
    ) -> ProvenanceAttestation {
        let signing_key = SigningKey::from_bytes(signing_key_seed);
        let signature = signing_key.sign(commitment);
        let mut hex = String::with_capacity(128);
        for b in signature.to_bytes() {
            hex.push(char::from_digit((b >> 4) as u32, 16).expect("nibble is < 16"));
            hex.push(char::from_digit((b & 0x0f) as u32, 16).expect("nibble is < 16"));
        }
        ProvenanceAttestation::new(
            digest_string(commitment),
            key_id,
            ALGORITHM_ED25519,
            attester_id,
            hex,
            issued_at,
        )
    }

    /// The public key matching a signing seed, as raw bytes — the form
    /// [`verify_frame_attestation`] accepts.
    pub fn public_key_for(signing_key_seed: &[u8; 32]) -> [u8; 32] {
        SigningKey::from_bytes(signing_key_seed)
            .verifying_key()
            .to_bytes()
    }
}

#[cfg(feature = "attestation")]
pub use crypto::{
    frame_commitment, inclusion_proof, merkle_root, provenance_chain_head, public_key_for,
    result_set_commitments, result_set_root, root_from_proof, sign_commitment,
    sign_frame_attestation, verify_commitment, verify_frame_attestation, verify_frame_inclusion,
};

#[cfg(all(test, feature = "attestation"))]
mod tests {
    use super::*;
    use crate::frame::{ContextFrame, FrameKind};

    /// A deterministic seed — tests need reproducible signatures, and this key
    /// signs nothing outside this file.
    const SEED: [u8; 32] = [7u8; 32];

    fn link(kind: &str, uri: Option<&str>, digest: Option<&str>) -> Provenance {
        Provenance {
            kind: kind.into(),
            uri: uri.map(Into::into),
            range: None,
            digest: digest.map(Into::into),
            method: None,
            by: None,
        }
    }

    fn frame_with(id: &str, provenance: Vec<Provenance>) -> ContextFrame {
        let mut frame = ContextFrame::full(id, FrameKind::Doc, "Retry policy", "body", 0.9, 1);
        frame.content_digest = Some("sha256:abcd".into());
        frame.provenance = provenance;
        frame
    }

    #[test]
    fn the_encoding_is_injective_across_field_boundaries() {
        // The attack length-prefixing exists to stop: without it, ("ab", "c")
        // and ("a", "bc") concatenate to the same bytes and an adversary picks
        // the collision rather than searching for one.
        let a = link("file", Some("ab"), Some("c"));
        let b = link("file", Some("a"), Some("bc"));
        assert_ne!(encode_provenance_link(&a), encode_provenance_link(&b));
    }

    #[test]
    fn an_absent_field_never_encodes_like_an_empty_one() {
        let absent = link("file", None, None);
        let empty = link("file", Some(""), None);
        assert_ne!(
            encode_provenance_link(&absent),
            encode_provenance_link(&empty),
            "the presence byte must keep None distinct from Some(\"\")"
        );
    }

    #[test]
    fn an_empty_chain_has_a_stated_head_not_a_zero() {
        let head = provenance_chain_head(&[]);
        assert_ne!(head, [0u8; 32], "\"no provenance\" is a claim, not a gap");
        // Stable across calls — the genesis is a constant, not a nonce.
        assert_eq!(head, provenance_chain_head(&[]));
    }

    #[test]
    fn reordering_the_chain_changes_the_head() {
        let a = link("file", Some("src/a.rs"), Some("sha256:aa"));
        let b = link("derivation", Some("summary"), Some("sha256:bb"));
        let forward = provenance_chain_head(&[a.clone(), b.clone()]);
        let reversed = provenance_chain_head(&[b, a]);
        assert_ne!(
            forward, reversed,
            "a hash chain must bind order; per-link digests never did"
        );
    }

    #[test]
    fn dropping_a_link_changes_the_head() {
        let a = link("file", Some("src/a.rs"), Some("sha256:aa"));
        let b = link("derivation", None, None);
        assert_ne!(
            provenance_chain_head(&[a.clone(), b]),
            provenance_chain_head(&[a]),
            "truncating provenance must be detectable"
        );
    }

    #[test]
    fn a_signed_frame_verifies_against_its_own_key() {
        let frame = frame_with(
            "f1",
            vec![link("file", Some("src/a.rs"), Some("sha256:aa"))],
        );
        let attestation = sign_frame_attestation(
            "repo-graph",
            &frame,
            &SEED,
            "key-1",
            "oxagen",
            "2026-08-27T00:00:00Z",
        );
        let key = public_key_for(&SEED);
        assert_eq!(
            verify_frame_attestation("repo-graph", &frame, &attestation, &key),
            AttestationVerdict::Valid
        );
        assert!(attestation.uses_known_algorithm());
        assert!(attestation.has_well_formed_issued_at());
    }

    #[test]
    fn editing_provenance_after_signing_is_caught_as_a_mismatch() {
        let frame = frame_with(
            "f1",
            vec![link("file", Some("src/a.rs"), Some("sha256:aa"))],
        );
        let attestation = sign_frame_attestation(
            "repo-graph",
            &frame,
            &SEED,
            "key-1",
            "oxagen",
            "2026-08-27T00:00:00Z",
        );
        // Rewrite the source URI — the exact tamper a bare digest cannot see,
        // because the tamperer simply rewrites the digest too.
        let mut tampered = frame.clone();
        tampered.provenance[0].uri = Some("src/evil.rs".into());
        tampered.provenance[0].digest = Some("sha256:ff".into());

        let key = public_key_for(&SEED);
        let verdict = verify_frame_attestation("repo-graph", &tampered, &attestation, &key);
        assert!(
            matches!(verdict, AttestationVerdict::CommitmentMismatch { .. }),
            "expected a commitment mismatch, got {verdict:?}"
        );
        assert!(!verdict.is_valid());
    }

    #[test]
    fn a_signature_cannot_be_lifted_onto_another_frame() {
        // The forgery the FrameId binding exists to prevent. Both frames cite
        // exactly the same source, so they share a chain head; only the identity
        // binding distinguishes them.
        let shared = vec![link("file", Some("src/a.rs"), Some("sha256:aa"))];
        let honest = frame_with("f1", shared.clone());
        let forged = frame_with("f2", shared);
        assert_eq!(
            provenance_chain_head(&honest.provenance),
            provenance_chain_head(&forged.provenance),
            "precondition: identical provenance means an identical chain head"
        );

        let attestation = sign_frame_attestation(
            "repo-graph",
            &honest,
            &SEED,
            "key-1",
            "oxagen",
            "2026-08-27T00:00:00Z",
        );
        let key = public_key_for(&SEED);
        assert!(
            matches!(
                verify_frame_attestation("repo-graph", &forged, &attestation, &key),
                AttestationVerdict::CommitmentMismatch { .. }
            ),
            "a stolen signature must not validate a different frame"
        );
    }

    #[test]
    fn the_same_frame_from_another_provider_does_not_verify() {
        let frame = frame_with("f1", vec![link("file", Some("src/a.rs"), None)]);
        let attestation = sign_frame_attestation(
            "repo-graph",
            &frame,
            &SEED,
            "key-1",
            "oxagen",
            "2026-08-27T00:00:00Z",
        );
        let key = public_key_for(&SEED);
        assert!(
            matches!(
                verify_frame_attestation("impostor", &frame, &attestation, &key),
                AttestationVerdict::CommitmentMismatch { .. }
            ),
            "the provider id is part of the signed identity"
        );
    }

    #[test]
    fn re_serving_different_bytes_under_the_same_id_is_caught() {
        let frame = frame_with("f1", vec![link("file", Some("src/a.rs"), None)]);
        let attestation = sign_frame_attestation(
            "repo-graph",
            &frame,
            &SEED,
            "key-1",
            "oxagen",
            "2026-08-27T00:00:00Z",
        );
        let mut swapped = frame.clone();
        swapped.content_digest = Some("sha256:0000".into());
        let key = public_key_for(&SEED);
        assert!(
            matches!(
                verify_frame_attestation("repo-graph", &swapped, &attestation, &key),
                AttestationVerdict::CommitmentMismatch { .. }
            ),
            "the signature covers the frame's bytes, not just its name"
        );
    }

    #[test]
    fn a_wrong_key_is_a_bad_signature_not_a_mismatch() {
        let frame = frame_with("f1", vec![]);
        let attestation = sign_frame_attestation(
            "repo-graph",
            &frame,
            &SEED,
            "key-1",
            "oxagen",
            "2026-08-27T00:00:00Z",
        );
        let other = public_key_for(&[9u8; 32]);
        assert_eq!(
            verify_frame_attestation("repo-graph", &frame, &attestation, &other),
            AttestationVerdict::BadSignature,
            "the commitment is intact; only the key is wrong"
        );
    }

    #[test]
    fn an_unknown_algorithm_is_declined_rather_than_failed() {
        let frame = frame_with("f1", vec![]);
        let mut attestation = sign_frame_attestation(
            "repo-graph",
            &frame,
            &SEED,
            "key-1",
            "oxagen",
            "2026-08-27T00:00:00Z",
        );
        attestation.algorithm = "dilithium3".into();
        let key = public_key_for(&SEED);
        let verdict = verify_frame_attestation("repo-graph", &frame, &attestation, &key);
        assert_eq!(
            verdict,
            AttestationVerdict::UnknownAlgorithm("dilithium3".into())
        );
        assert!(!verdict.is_valid(), "declining is still not accepting");
        assert!(!attestation.uses_known_algorithm());
    }

    #[test]
    fn malformed_keys_and_signatures_are_named_distinctly() {
        let frame = frame_with("f1", vec![]);
        let attestation = sign_frame_attestation(
            "repo-graph",
            &frame,
            &SEED,
            "key-1",
            "oxagen",
            "2026-08-27T00:00:00Z",
        );
        assert_eq!(
            verify_frame_attestation("repo-graph", &frame, &attestation, &[0u8; 5]),
            AttestationVerdict::MalformedKey
        );

        let mut truncated = attestation.clone();
        truncated.signature = "abcd".into();
        assert_eq!(
            verify_frame_attestation("repo-graph", &frame, &truncated, &public_key_for(&SEED)),
            AttestationVerdict::MalformedSignature
        );

        let mut bad_commitment = attestation;
        bad_commitment.signed_commitment = "not-a-digest".into();
        assert_eq!(
            verify_frame_attestation(
                "repo-graph",
                &frame,
                &bad_commitment,
                &public_key_for(&SEED)
            ),
            AttestationVerdict::MalformedCommitment
        );
    }

    #[test]
    fn an_attestation_round_trips_through_json() {
        let frame = frame_with("f1", vec![link("file", Some("a"), None)]);
        let attestation = sign_frame_attestation(
            "repo-graph",
            &frame,
            &SEED,
            "key-1",
            "oxagen",
            "2026-08-27T00:00:00Z",
        );
        let json = serde_json::to_string(&attestation).unwrap();
        let back: ProvenanceAttestation = serde_json::from_str(&json).unwrap();
        assert_eq!(back, attestation);
    }

    #[test]
    fn every_leaf_of_a_signed_set_proves_its_own_membership() {
        let commitments: Vec<[u8; 32]> = (0..7)
            .map(|i| frame_commitment("repo-graph", &frame_with(&format!("f{i}"), vec![])))
            .collect();
        let root = merkle_root(&commitments);

        for (index, commitment) in commitments.iter().enumerate() {
            let proof = inclusion_proof(&commitments, index).expect("index is in range");
            assert_eq!(proof.leaf_index, index);
            assert_eq!(proof.leaf_count, 7);
            assert_eq!(
                root_from_proof(commitment, &proof),
                Some(root),
                "leaf {index} must recompute the signed root"
            );
        }
    }

    #[test]
    fn a_proof_does_not_validate_a_commitment_that_was_not_in_the_set() {
        let commitments: Vec<[u8; 32]> = (0..4)
            .map(|i| frame_commitment("repo-graph", &frame_with(&format!("f{i}"), vec![])))
            .collect();
        let root = merkle_root(&commitments);
        let proof = inclusion_proof(&commitments, 1).unwrap();

        let outsider = frame_commitment("repo-graph", &frame_with("intruder", vec![]));
        assert_ne!(
            root_from_proof(&outsider, &proof),
            Some(root),
            "an unsigned frame must not ride someone else's proof"
        );
    }

    #[test]
    fn a_single_frame_set_still_produces_a_usable_proof() {
        let commitments = vec![frame_commitment("repo-graph", &frame_with("only", vec![]))];
        let root = merkle_root(&commitments);
        let proof = inclusion_proof(&commitments, 0).unwrap();
        assert!(proof.path.is_empty(), "a lone leaf needs no siblings");
        assert_eq!(root_from_proof(&commitments[0], &proof), Some(root));
    }

    #[test]
    fn an_empty_set_has_a_distinct_root() {
        let empty = merkle_root(&[]);
        let lone = merkle_root(&[frame_commitment("repo-graph", &frame_with("only", vec![]))]);
        assert_ne!(empty, lone);
        assert!(inclusion_proof(&[], 0).is_none());
    }

    /// The whole cheap-signing path in one helper: sign the root over `frames`
    /// and hand back the root attestation plus each frame's inclusion proof, in
    /// canonical order.
    fn root_signed(
        provider_id: &str,
        frames: &[ContextFrame],
    ) -> (ProvenanceAttestation, Vec<InclusionProof>) {
        let commitments: Vec<[u8; 32]> = result_set_commitments(provider_id, frames)
            .into_iter()
            .map(|(_, commitment)| commitment)
            .collect();
        let root = merkle_root(&commitments);
        let proofs = (0..commitments.len())
            .map(|index| inclusion_proof(&commitments, index).expect("index is in range"))
            .collect();
        let attestation = sign_commitment(
            &root,
            &SEED,
            "repo-graph-2026-08",
            "repo-graph",
            "2026-08-29T00:00:00Z",
        );
        (attestation, proofs)
    }

    #[test]
    fn one_root_signature_attests_every_frame_it_covers() {
        // The point of §6.5.3: a provider signs once, and every frame in the
        // answer is verifiable from its own proof. A verifier that only knew
        // how to check per-frame signatures would call all of these unattested.
        let frames = vec![
            frame_with("a", vec![link("file", Some("src/a.rs"), Some("sha256:aa"))]),
            frame_with("b", vec![]),
            frame_with("c", vec![]),
        ];
        // Canonical order is by `FrameId`, which is what the proofs index into.
        let ordered: Vec<ContextFrame> = {
            let mut sorted = frames.clone();
            sorted.sort_by_key(|frame| frame.identity("repo-graph"));
            sorted
        };
        let (root, proofs) = root_signed("repo-graph", &frames);
        let public_key = public_key_for(&SEED);

        for (frame, proof) in ordered.iter().zip(&proofs) {
            assert_eq!(
                verify_frame_inclusion("repo-graph", frame, proof, &root, &public_key),
                AttestationVerdict::Valid,
                "frame `{}` is a leaf of the signed root",
                frame.id
            );
        }
    }

    #[test]
    fn a_frame_edited_after_the_root_was_signed_recomputes_a_different_root() {
        let frames = vec![frame_with("a", vec![]), frame_with("b", vec![])];
        let (root, proofs) = root_signed("repo-graph", &frames);
        let mut ordered = frames.clone();
        ordered.sort_by_key(|frame| frame.identity("repo-graph"));
        ordered[0].provenance.push(link("derivation", None, None));

        assert!(
            matches!(
                verify_frame_inclusion(
                    "repo-graph",
                    &ordered[0],
                    &proofs[0],
                    &root,
                    &public_key_for(&SEED),
                ),
                AttestationVerdict::CommitmentMismatch { .. }
            ),
            "a proof must not launder an edit the root never covered"
        );
    }

    #[test]
    fn a_digest_less_frame_proven_through_a_root_binds_no_content() {
        // #128's rule survives the tree: the leaf is a frame commitment, so a
        // frame declaring no `content_digest` is committed to by identity and
        // provenance alone however many hashes sit above it.
        let mut frame = frame_with("a", vec![]);
        frame.content_digest = None;
        let frames = vec![frame.clone()];
        let (root, proofs) = root_signed("repo-graph", &frames);

        let verdict = verify_frame_inclusion(
            "repo-graph",
            &frame,
            &proofs[0],
            &root,
            &public_key_for(&SEED),
        );
        assert_eq!(verdict, AttestationVerdict::ValidIdentityOnly);
        assert!(verdict.signature_verifies());
        assert!(!verdict.binds_content());
    }

    #[test]
    fn a_root_signed_by_the_wrong_key_is_a_bad_signature_not_a_mismatch() {
        let frames = vec![frame_with("a", vec![])];
        let (root, proofs) = root_signed("repo-graph", &frames);
        let impostor = public_key_for(&[8u8; 32]);
        assert_eq!(
            verify_frame_inclusion("repo-graph", &frames[0], &proofs[0], &root, &impostor),
            AttestationVerdict::BadSignature
        );
    }

    #[test]
    fn an_inclusion_path_longer_than_the_cap_is_rejected_before_it_is_walked() {
        // Every step costs a hash and the path comes from the provider, so the
        // length is checked before any hashing starts.
        let frames = vec![frame_with("a", vec![])];
        let (root, _) = root_signed("repo-graph", &frames);
        let oversized = InclusionProof {
            leaf_index: 0,
            leaf_count: usize::MAX,
            path: vec![
                InclusionStep {
                    sibling: digest_string(&[1u8; 32]),
                    sibling_is_left: false,
                };
                MAX_INCLUSION_PATH_STEPS + 1
            ],
        };
        assert_eq!(
            verify_frame_inclusion(
                "repo-graph",
                &frames[0],
                &oversized,
                &root,
                &public_key_for(&SEED)
            ),
            AttestationVerdict::MalformedCommitment
        );
    }

    #[test]
    fn leaf_and_node_hashing_are_domain_separated() {
        // Without the RFC 6962 prefixes, an interior node's hash could be
        // presented as a leaf, letting a subtree masquerade as a single frame.
        let a = frame_commitment("repo-graph", &frame_with("a", vec![]));
        let b = frame_commitment("repo-graph", &frame_with("b", vec![]));
        let pair_root = merkle_root(&[a, b]);
        // The two-leaf root must not equal the one-leaf root of any commitment.
        assert_ne!(pair_root, merkle_root(&[a]));
        assert_ne!(pair_root, merkle_root(&[b]));
    }

    #[test]
    fn a_signed_merkle_root_verifies_for_the_whole_result_set() {
        let commitments: Vec<[u8; 32]> = (0..3)
            .map(|i| frame_commitment("repo-graph", &frame_with(&format!("f{i}"), vec![])))
            .collect();
        let root = merkle_root(&commitments);
        let attestation = sign_commitment(&root, &SEED, "key-1", "oxagen", "2026-08-27T00:00:00Z");
        let key = public_key_for(&SEED);
        assert_eq!(
            verify_commitment(&root, &attestation, &key),
            AttestationVerdict::Valid
        );
    }

    #[test]
    fn digest_strings_are_well_formed_protocol_digests() {
        let head = provenance_chain_head(&[link("file", Some("a"), None)]);
        let rendered = digest_string(&head);
        assert!(
            crate::validate::is_well_formed_digest(&rendered),
            "{rendered} must satisfy the protocol digest grammar"
        );
    }
}

#[cfg(all(test, feature = "attestation"))]
mod content_binding_tests {
    use super::*;
    use crate::frame::{ContextFrame, FrameKind};

    const SEED: [u8; 32] = [7u8; 32];
    const PROVIDER: &str = "acme.docs";

    fn frame(id: &str, content: &str, digest: Option<&str>) -> ContextFrame {
        let mut f = ContextFrame::full(id, FrameKind::Doc, "Retry policy", content, 0.9, 1);
        f.content_digest = digest.map(Into::into);
        f
    }

    fn attest(frame: &ContextFrame) -> ProvenanceAttestation {
        sign_frame_attestation(PROVIDER, frame, &SEED, "k1", "acme", "2026-09-10T00:00:00Z")
    }

    /// The demonstration from #128, kept as a test so the guarantee cannot
    /// quietly revert: sign a frame that declares no `content_digest`, rewrite
    /// its content, and check that the verdict does not claim the signature
    /// still covers it.
    ///
    /// Before the fix this asserted `Valid` — twice, for two different sets of
    /// bytes — and a host had no way to tell that the second answer was not the
    /// one that had been signed.
    #[test]
    fn a_signed_frame_with_no_content_digest_is_attested_over_nothing_it_says() {
        let signed = frame("f1", "retry three times", None);
        let attestation = attest(&signed);
        let key = public_key_for(&SEED);

        let before = verify_frame_attestation(PROVIDER, &signed, &attestation, &key);
        assert_eq!(before, AttestationVerdict::ValidIdentityOnly);

        // The same provider re-serves entirely different content under the same
        // frame id. The signature is untouched and still verifies, because the
        // content was never in the preimage — that is the defect. What must not
        // happen is a verdict that calls it `Valid`.
        let mut rewritten = signed.clone();
        rewritten.content = Some("retry zero times, drop the request".into());

        let after = verify_frame_attestation(PROVIDER, &rewritten, &attestation, &key);
        assert_eq!(
            after,
            AttestationVerdict::ValidIdentityOnly,
            "rewriting the content of a digest-less frame does not disturb the signature"
        );

        assert!(
            !after.is_valid(),
            "an identity-only attestation is not `is_valid`"
        );
        assert!(!after.binds_content(), "it binds nothing about the content");
        assert!(
            after.signature_verifies(),
            "the signature itself is genuine — that is why this is subtle"
        );
    }

    /// The contrasting case: a frame that declares a digest *is* bound, and
    /// altering it is caught as the loud failure it should be.
    #[test]
    fn a_frame_that_declares_a_digest_is_bound_to_it() {
        let signed = frame("f2", "retry three times", Some("sha256:aaaa"));
        let attestation = attest(&signed);
        let key = public_key_for(&SEED);

        let verdict = verify_frame_attestation(PROVIDER, &signed, &attestation, &key);
        assert_eq!(verdict, AttestationVerdict::Valid);
        assert!(verdict.is_valid() && verdict.binds_content());

        // Changing the declared digest changes the preimage, so the recomputed
        // commitment no longer matches the signed one.
        let mut altered = signed.clone();
        altered.content_digest = Some("sha256:bbbb".into());
        let verdict = verify_frame_attestation(PROVIDER, &altered, &attestation, &key);
        assert!(
            matches!(verdict, AttestationVerdict::CommitmentMismatch { .. }),
            "got {verdict:?}"
        );
    }

    /// Dropping the digest from a frame that was signed *with* one is a
    /// mismatch, not a downgrade. The downgrade path must not become a way to
    /// launder a tampered frame into a passing verdict.
    #[test]
    fn stripping_a_digest_after_signing_is_a_mismatch_not_a_downgrade() {
        let signed = frame("f3", "retry three times", Some("sha256:aaaa"));
        let attestation = attest(&signed);
        let key = public_key_for(&SEED);

        let mut stripped = signed.clone();
        stripped.content_digest = None;

        let verdict = verify_frame_attestation(PROVIDER, &stripped, &attestation, &key);
        assert!(
            matches!(verdict, AttestationVerdict::CommitmentMismatch { .. }),
            "stripping the digest must not downgrade to ValidIdentityOnly; got {verdict:?}"
        );
    }
}

#[cfg(all(test, feature = "attestation"))]
mod lowercase_hex_tests {
    use super::*;

    const SEED: [u8; 32] = [9u8; 32];
    const PROVIDER: &str = "acme.docs";

    fn frame() -> crate::frame::ContextFrame {
        let mut f = crate::frame::ContextFrame::full(
            "f1",
            crate::frame::FrameKind::Doc,
            "Retry policy",
            "body",
            0.9,
            1,
        );
        f.content_digest = Some("sha256:aaaa".into());
        f
    }

    /// The divergence #145 reported: the same attestation, read by the Rust
    /// reference and by any SDK port, must reach the same verdict. Uppercase is
    /// outside `SPEC.md`'s grammar, every SDK rejects it, and the reference
    /// accepted it.
    #[test]
    fn an_uppercase_commitment_is_malformed_not_valid() {
        let f = frame();
        let mut att =
            sign_frame_attestation(PROVIDER, &f, &SEED, "k1", "acme", "2026-09-10T00:00:00Z");
        let key = public_key_for(&SEED);

        // Baseline: as emitted, it verifies.
        assert_eq!(
            verify_frame_attestation(PROVIDER, &f, &att, &key),
            AttestationVerdict::Valid
        );

        // Upper-casing only the hex body leaves the same bytes, spelled the way
        // the grammar forbids.
        let (scheme, hex) = att.signed_commitment.split_once(':').expect("scheme");
        att.signed_commitment = format!("{scheme}:{}", hex.to_uppercase());

        assert_eq!(
            verify_frame_attestation(PROVIDER, &f, &att, &key),
            AttestationVerdict::MalformedCommitment,
            "uppercase hex is outside SPEC.md's digest grammar and every SDK rejects it"
        );
    }

    #[test]
    fn an_uppercase_signature_is_malformed_not_valid() {
        let f = frame();
        let mut att =
            sign_frame_attestation(PROVIDER, &f, &SEED, "k1", "acme", "2026-09-10T00:00:00Z");
        let key = public_key_for(&SEED);

        att.signature = att.signature.to_uppercase();

        assert_eq!(
            verify_frame_attestation(PROVIDER, &f, &att, &key),
            AttestationVerdict::MalformedSignature
        );
    }

    /// The narrowing must not touch what the reference *emits*, only what it
    /// accepts — otherwise it would break every attestation already written.
    #[test]
    fn everything_this_module_emits_is_still_lowercase() {
        let f = frame();
        let att = sign_frame_attestation(PROVIDER, &f, &SEED, "k1", "acme", "2026-09-10T00:00:00Z");
        assert_eq!(att.signed_commitment, att.signed_commitment.to_lowercase());
        assert_eq!(att.signature, att.signature.to_lowercase());
        assert_eq!(
            digest_string(&frame_commitment(PROVIDER, &f)),
            digest_string(&frame_commitment(PROVIDER, &f)).to_lowercase()
        );
    }

    #[test]
    fn lowercase_digits_decode_and_uppercase_ones_do_not() {
        assert_eq!(lowercase_hex_digit(b'0'), Some(0));
        assert_eq!(lowercase_hex_digit(b'9'), Some(9));
        assert_eq!(lowercase_hex_digit(b'a'), Some(10));
        assert_eq!(lowercase_hex_digit(b'f'), Some(15));
        for byte in *b"AFgG :" {
            assert_eq!(
                lowercase_hex_digit(byte),
                None,
                "byte {byte:?} must not decode"
            );
        }
    }
}