boundgraph-check 0.1.0

//! Signing a verdict, and verifying one without asking anybody.
//!
//! # Why a verdict has to be signed at all
//!
//! An unsigned verdict is a row in a log file. Anyone who can write the log can
//! write "the tests passed", and nobody reading it later can tell the
//! difference between a checker that ran and a line someone typed. That is the
//! whole gap between logging and evidence, and Law III sits on the far side of
//! it: a state change commits on [`Evidence`], so evidence has to be worth
//! something.
//!
//! ed25519 over the canonical CBOR encoding closes it. The signature covers the
//! verdict, the checker's identity and version, the digests of exactly what was
//! checked, the key identity, and how the verdict was reached — everything
//! except the signature itself, which is what
//! [`Evidence::signing_payload`](boundgraph_core::Evidence::signing_payload) returns.
//! Change any of it and the signature stops verifying.
//!
//! # Deterministic signatures, deliberately
//!
//! ed25519 derives its per-signature nonce from the private key and the message
//! (RFC 8032 §5.1.6) rather than sampling one. Signing the same evidence twice
//! therefore produces the same 64 bytes. That is load-bearing here rather than
//! incidental: US-0801 requires a checker to be a pure function of its inputs,
//! and replay (US-1006) re-runs a recorded check and compares. A randomised
//! signature scheme would make every replayed run differ in a field that says
//! nothing about whether the check agreed.
//!
//! # Verification is a free function
//!
//! [`verify`] takes evidence and a public key and returns an answer. No
//! runtime, no registry, no async, no I/O. A compliance reviewer with a ledger
//! file and a published key can check every verdict in it without running BoundGraph
//! at all — which is the only version of "auditable" that means anything.
//!
//! # There is no path to unsigned evidence
//!
//! [`sign_evidence`] is the only constructor in this crate, and it returns
//! `Result`. There is no `unsigned()`, no feature flag, and no fallback that
//! degrades to an empty signature when a key is unavailable. A signing failure
//! propagates and the step does not commit. That asymmetry is deliberate: a
//! blocked commit is an outage, an unsigned commit is a lie in the audit trail,
//! and only one of those can be fixed after the fact.
//!
//! # Key management
//!
//! Which keys exist, and who holds them, is unresolved — `ARCHITECTURE.md` §17
//! lists it as the one open question blocking M3. `docs/evidence-keys.md`
//! records the three candidate strategies and what each costs. This module is
//! written so that the decision can be made later without changing any caller:
//!
//! - [`Sign`] is a trait, so an external KMS or an HSM is an implementation of
//!   it rather than a rewrite. [`LocalKey`] is the in-process one, which is
//!   what M3 runs on.
//! - The key *identity* travels in the evidence, not the key material, so a
//!   verifier looks the key up rather than trusting what it was handed.
//! - [`KeyRing`] is the smallest possible resolver of identity to public key.
//!   A KMS-backed one satisfies the same call.

use std::collections::BTreeMap;
use std::fmt;

use boundgraph_core::{
    CanonicalError, CheckerId, Digest, Evidence, EvidenceKind, Signature, SigningKeyId, Verdict,
};
use ed25519_dalek::{Signer as _, Verifier as _};

/// How many bytes an ed25519 public key is.
pub const PUBLIC_KEY_LEN: usize = 32;

/// How many bytes a private seed is.
pub const SEED_LEN: usize = 32;

/// Signing failed, so nothing commits.
///
/// Every variant is terminal for the check that produced it. See the module
/// documentation on why there is no degraded path.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
#[non_exhaustive]
pub enum SignError {
    /// The evidence could not be canonically encoded, so there is nothing to
    /// sign over.
    #[error("the evidence could not be encoded for signing: {0}")]
    Encode(String),

    /// The signer could not produce a signature — an unreachable KMS, a
    /// revoked key, a hardware token that is not present.
    #[error("the signer {key} is unavailable: {detail}")]
    Unavailable {
        /// Which key could not be used.
        key: SigningKeyId,
        /// Why.
        detail: String,
    },
}

impl From<CanonicalError> for SignError {
    fn from(e: CanonicalError) -> Self {
        Self::Encode(e.to_string())
    }
}

/// Verification failed, so the evidence proves nothing.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
#[non_exhaustive]
pub enum VerifyError {
    /// The signature does not match the evidence under the given key.
    ///
    /// Says nothing about *which* field was altered, and cannot: a signature is
    /// over the whole pre-image. What it does say is that this evidence is not
    /// what the key signed.
    #[error("the signature over evidence from {checker} does not verify under {key}")]
    Invalid {
        /// The checker the evidence claims to come from.
        checker: CheckerId,
        /// The key it claims to be signed by.
        key: SigningKeyId,
    },

    /// The evidence names a key the verifier does not have.
    ///
    /// Not a failure of the evidence. An auditor missing a public key has an
    /// incomplete key ring, and treating that as tampering would be wrong —
    /// which is why it is its own variant.
    #[error("no public key is known for {0}")]
    UnknownKey(SigningKeyId),

    /// The public key bytes are not a valid ed25519 point.
    #[error("the public key for {key} is malformed: {detail}")]
    MalformedKey {
        /// Which key.
        key: SigningKeyId,
        /// Why it could not be used.
        detail: String,
    },

    /// The evidence could not be canonically encoded, so the pre-image the
    /// signature covers cannot be reconstructed.
    #[error("the evidence could not be encoded for verification: {0}")]
    Encode(String),
}

/// An ed25519 public key, as bytes.
///
/// Deliberately a plain 32-byte value rather than a re-exported curve type: a
/// key ring, a ledger, and a config file all want to carry one, and none of
/// them should have to name this crate's ed25519 implementation to do it.
/// Point validity is checked at [`verify`] time, where the error can be
/// reported, rather than at construction where it would only panic.
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct PublicKey([u8; PUBLIC_KEY_LEN]);

impl PublicKey {
    /// Wrap raw public key bytes.
    pub const fn from_bytes(bytes: [u8; PUBLIC_KEY_LEN]) -> Self {
        Self(bytes)
    }

    /// The raw bytes.
    pub const fn as_bytes(&self) -> &[u8; PUBLIC_KEY_LEN] {
        &self.0
    }

    /// The key as lowercase hex, which is how it appears in configuration.
    pub fn to_hex(&self) -> String {
        use fmt::Write as _;
        self.0.iter().fold(String::new(), |mut s, b| {
            let _ = write!(s, "{b:02x}");
            s
        })
    }

    fn to_dalek(self, id: &SigningKeyId) -> Result<ed25519_dalek::VerifyingKey, VerifyError> {
        ed25519_dalek::VerifyingKey::from_bytes(&self.0).map_err(|e| VerifyError::MalformedKey {
            key: id.clone(),
            detail: e.to_string(),
        })
    }
}

impl fmt::Debug for PublicKey {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "PublicKey({})", self.to_hex())
    }
}

/// Whatever can produce a signature for a key it holds.
///
/// The seam the open key-management question lives behind. An in-process key,
/// an agent socket, a cloud KMS, and a hardware token differ in where the
/// private bytes are and how a signature is requested; none of that is visible
/// to a checker, which asks for a signature and gets one or does not commit.
pub trait Sign: Send + Sync + fmt::Debug {
    /// Which key this signs with.
    ///
    /// Recorded in every piece of evidence, so a verifier knows what to check
    /// against without being handed the key material.
    fn key_id(&self) -> SigningKeyId;

    /// Sign a pre-image.
    ///
    /// # Errors
    ///
    /// [`SignError::Unavailable`] if the key could not be used. There is no
    /// success value that means "unsigned".
    fn sign(&self, payload: &[u8]) -> Result<Signature, SignError>;
}

/// An ed25519 key held in this process.
///
/// What M3 runs on, and the reference implementation of [`Sign`]. The private
/// bytes are zeroized on drop by `ed25519-dalek`, and neither [`Debug`] nor any
/// accessor exposes them — a key that has been printed into a log is a key that
/// has been published.
///
/// # Example
///
/// ```
/// use boundgraph_check::{LocalKey, Sign, sign_evidence, verify};
/// use boundgraph_core::{CheckerId, Digest, EvidenceKind, Verdict};
///
/// let key = LocalKey::from_seed("host-key-1", [7u8; 32]);
///
/// let evidence = sign_evidence(
///     Verdict::Pass,
///     CheckerId::new("json-schema", 1),
///     [Digest::of(b"the payload that was checked")],
///     EvidenceKind::Deterministic,
///     &key,
/// )?;
///
/// // Anyone holding the public key can check it, with no runtime at all.
/// verify(&evidence, &key.public_key())?;
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub struct LocalKey {
    id: SigningKeyId,
    key: ed25519_dalek::SigningKey,
}

impl LocalKey {
    /// Build a key from a 32-byte seed.
    ///
    /// Deterministic: the same seed always gives the same key. That is what
    /// makes a cassette test (US-1008) able to assert on exact signature bytes,
    /// and it is why this takes a seed rather than sampling one.
    ///
    /// The seed *is* the private key. Treat it as such.
    pub fn from_seed(id: impl Into<String>, seed: [u8; SEED_LEN]) -> Self {
        Self {
            id: SigningKeyId(id.into()),
            key: ed25519_dalek::SigningKey::from_bytes(&seed),
        }
    }

    /// Build a key from freshly sampled entropy.
    ///
    /// For a per-run key, which is one of the strategies
    /// `docs/evidence-keys.md` weighs. Not deterministic, and so not for use in
    /// a test that asserts on signature bytes.
    pub fn generate(id: impl Into<String>) -> Self {
        use rand::RngCore as _;
        let mut seed = [0u8; SEED_LEN];
        rand::rng().fill_bytes(&mut seed);
        Self::from_seed(id, seed)
    }

    /// The public half, to be published so verdicts can be checked.
    pub fn public_key(&self) -> PublicKey {
        PublicKey(self.key.verifying_key().to_bytes())
    }
}

impl fmt::Debug for LocalKey {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        // The public half only. A private key in a debug log is a leaked key.
        f.debug_struct("LocalKey")
            .field("id", &self.id)
            .field("public_key", &self.public_key())
            .finish()
    }
}

impl Sign for LocalKey {
    fn key_id(&self) -> SigningKeyId {
        self.id.clone()
    }

    fn sign(&self, payload: &[u8]) -> Result<Signature, SignError> {
        Ok(Signature::from_bytes(self.key.sign(payload).to_bytes()))
    }
}

/// Build evidence and sign it, in that order, as one operation.
///
/// The only way to make an [`Evidence`] in this crate. Splitting it into
/// "construct" and "sign later" would create a window in which an unsigned
/// value exists and could be stored, and there is no reason to want one.
///
/// Inputs are sorted and deduplicated by [`Evidence::new`] *before* the
/// pre-image is computed, so a checker that happened to list the same digests
/// in a different order produces byte-identical evidence.
///
/// # Errors
///
/// [`SignError::Encode`] if the evidence cannot be canonically encoded, or
/// [`SignError::Unavailable`] if the signer refused. Either way the caller has
/// no evidence, and so cannot commit.
pub fn sign_evidence(
    verdict: Verdict,
    checker: CheckerId,
    inputs: impl IntoIterator<Item = Digest>,
    kind: EvidenceKind,
    signer: &dyn Sign,
) -> Result<Evidence, SignError> {
    // A placeholder purely so the pre-image can be computed from the finished
    // value. It is overwritten below and never leaves this function: every exit
    // path from here either carries a real signature or is an error.
    let mut evidence = Evidence::new(
        verdict,
        checker,
        inputs,
        Signature::from_bytes([0u8; 64]),
        signer.key_id(),
        kind,
    );

    let payload = evidence.signing_payload()?;
    evidence.signature = signer.sign(&payload)?;
    Ok(evidence)
}

/// Check evidence against a public key.
///
/// Standalone by design: no runtime, no registry, no async, no I/O. Given a
/// ledger file and a published key, this is the whole of what an external
/// auditor needs.
///
/// # Errors
///
/// [`VerifyError::Invalid`] if the signature does not match — which is what a
/// tampered value produces, whichever field was altered.
/// [`VerifyError::MalformedKey`] if the key is not a valid ed25519 point, and
/// [`VerifyError::Encode`] if the pre-image could not be rebuilt.
pub fn verify(evidence: &Evidence, key: &PublicKey) -> Result<(), VerifyError> {
    let verifying = key.to_dalek(&evidence.key)?;

    let payload = evidence
        .signing_payload()
        .map_err(|e| VerifyError::Encode(e.to_string()))?;

    let signature = ed25519_dalek::Signature::from_bytes(evidence.signature.as_bytes());

    // `verify` on `VerifyingKey` is already the strict, cofactorless check that
    // rejects small-order keys and non-canonical encodings. The malleable
    // variant is not used, so two distinct signatures can never both verify
    // over one piece of evidence.
    verifying
        .verify(&payload, &signature)
        .map_err(|_| VerifyError::Invalid {
            checker: evidence.checker.clone(),
            key: evidence.key.clone(),
        })
}

/// Public keys, by the identity the evidence names.
///
/// The smallest thing that resolves a [`SigningKeyId`] to a [`PublicKey`], and
/// deliberately no more: whether keys arrive from a config file, a KMS, or a
/// transparency log is a deployment question, and this type is what all three
/// end up producing.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct KeyRing {
    keys: BTreeMap<SigningKeyId, PublicKey>,
}

impl KeyRing {
    /// An empty ring, which trusts nothing.
    pub fn new() -> Self {
        Self::default()
    }

    /// Trust `key` under the identity `id`.
    #[must_use]
    pub fn with(mut self, id: impl Into<String>, key: PublicKey) -> Self {
        self.keys.insert(SigningKeyId(id.into()), key);
        self
    }

    /// Trust the public half of a local key under its own identity.
    #[must_use]
    pub fn trusting(self, key: &LocalKey) -> Self {
        let id = key.key_id();
        self.with(id.0, key.public_key())
    }

    /// The public key for an identity, if the ring holds one.
    pub fn get(&self, id: &SigningKeyId) -> Option<&PublicKey> {
        self.keys.get(id)
    }

    /// How many keys are trusted.
    pub fn len(&self) -> usize {
        self.keys.len()
    }

    /// Whether the ring trusts nothing.
    pub fn is_empty(&self) -> bool {
        self.keys.is_empty()
    }

    /// Check evidence against whichever key it names.
    ///
    /// # Errors
    ///
    /// [`VerifyError::UnknownKey`] if the ring does not hold the named key —
    /// distinct from [`VerifyError::Invalid`], because an incomplete key ring
    /// is the auditor's problem and a bad signature is the evidence's.
    pub fn verify(&self, evidence: &Evidence) -> Result<(), VerifyError> {
        let key = self
            .get(&evidence.key)
            .ok_or_else(|| VerifyError::UnknownKey(evidence.key.clone()))?;
        verify(evidence, key)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn key() -> LocalKey {
        LocalKey::from_seed("host-key-1", [7u8; SEED_LEN])
    }

    fn evidence(signer: &dyn Sign) -> Evidence {
        sign_evidence(
            Verdict::Pass,
            CheckerId::new("json-schema", 1),
            [Digest::of(b"payload"), Digest::of(b"schema")],
            EvidenceKind::Deterministic,
            signer,
        )
        .expect("signing should succeed")
    }

    // ── signing ─────────────────────────────────────────────────────────────

    /// The criterion: evidence is signed over its canonical encoding, and the
    /// result verifies.
    #[test]
    fn signed_evidence_verifies_under_the_signing_key() {
        let key = key();
        assert!(verify(&evidence(&key), &key.public_key()).is_ok());
    }

    #[test]
    fn the_signing_key_identity_is_recorded_in_the_evidence() {
        let key = key();
        assert_eq!(evidence(&key).key, SigningKeyId("host-key-1".into()));
    }

    /// A verifier that only had the key material would have to trust whatever
    /// it was handed. It looks the key up by the recorded identity instead.
    #[test]
    fn a_key_ring_resolves_the_recorded_identity() {
        let key = key();
        let ring = KeyRing::new().trusting(&key);

        assert_eq!(ring.len(), 1);
        assert!(ring.verify(&evidence(&key)).is_ok());
    }

    #[test]
    fn a_key_the_ring_does_not_hold_is_not_a_tampering_report() {
        let key = key();
        let err = KeyRing::new().verify(&evidence(&key)).unwrap_err();

        assert_eq!(
            err,
            VerifyError::UnknownKey(SigningKeyId("host-key-1".into()))
        );
    }

    /// ed25519 derives its nonce from the key and the message, so the same
    /// evidence signs to the same bytes. Replay compares evidence.
    #[test]
    fn signing_the_same_evidence_twice_gives_the_same_bytes() {
        let key = key();
        let first = evidence(&key);
        for _ in 0..8 {
            assert_eq!(evidence(&key), first);
        }
    }

    #[test]
    fn input_order_does_not_change_the_signature() {
        let key = key();
        let forwards = sign_evidence(
            Verdict::Pass,
            CheckerId::new("c", 1),
            [Digest::of(b"a"), Digest::of(b"b")],
            EvidenceKind::Deterministic,
            &key,
        )
        .unwrap();
        let backwards = sign_evidence(
            Verdict::Pass,
            CheckerId::new("c", 1),
            [Digest::of(b"b"), Digest::of(b"a")],
            EvidenceKind::Deterministic,
            &key,
        )
        .unwrap();

        assert_eq!(forwards, backwards);
    }

    /// The placeholder used to compute the pre-image must never survive.
    #[test]
    fn the_placeholder_signature_never_escapes() {
        let key = key();
        assert_ne!(evidence(&key).signature, Signature::from_bytes([0u8; 64]));
    }

    // ── tampering ───────────────────────────────────────────────────────────

    /// The criterion: every field the signature covers, checked one at a time.
    #[test]
    fn a_tampered_evidence_value_fails_verification() {
        let key = key();
        let public = key.public_key();
        let good = evidence(&key);

        let mut flipped_verdict = good.clone();
        flipped_verdict.verdict = Verdict::Fail("actually it failed".into());

        let mut flipped_checker = good.clone();
        flipped_checker.checker = CheckerId::new("json-schema", 2);

        let mut flipped_inputs = good.clone();
        flipped_inputs.inputs = vec![Digest::of(b"a different payload")];

        let mut flipped_key_id = good.clone();
        flipped_key_id.key = SigningKeyId("some-other-key".into());

        let mut flipped_kind = good.clone();
        flipped_kind.kind = EvidenceKind::Quorum { n: 3, k: 2 };

        let mut flipped_signature = good.clone();
        flipped_signature.signature = Signature::from_bytes([9u8; 64]);

        for (what, tampered) in [
            ("verdict", flipped_verdict),
            ("checker", flipped_checker),
            ("inputs", flipped_inputs),
            ("key identity", flipped_key_id),
            ("kind", flipped_kind),
            ("signature", flipped_signature),
        ] {
            assert!(
                verify(&tampered, &public).is_err(),
                "altering the {what} must break verification"
            );
        }
    }

    /// The most valuable forgery there is: taking a passing verdict and
    /// pointing it at a patch that never passed.
    #[test]
    fn a_pass_cannot_be_moved_onto_another_artefact() {
        let key = key();
        let mut harvested = evidence(&key);
        harvested.inputs = vec![Digest::of(b"a failing patch")];

        assert!(verify(&harvested, &key.public_key()).is_err());
    }

    #[test]
    fn evidence_does_not_verify_under_the_wrong_key() {
        let key = key();
        let other = LocalKey::from_seed("host-key-2", [9u8; SEED_LEN]);

        let err = verify(&evidence(&key), &other.public_key()).unwrap_err();
        assert!(matches!(err, VerifyError::Invalid { .. }));
    }

    #[test]
    fn an_all_zero_signature_does_not_verify() {
        let key = key();
        let mut unsigned = evidence(&key);
        unsigned.signature = Signature::from_bytes([0u8; 64]);

        assert!(verify(&unsigned, &key.public_key()).is_err());
    }

    #[test]
    fn a_malformed_public_key_is_its_own_error() {
        let key = key();
        // `y = 2` does not decompress: no `x` on the curve has it.
        let mut bytes = [0u8; PUBLIC_KEY_LEN];
        bytes[0] = 2;
        let broken = PublicKey::from_bytes(bytes);

        let err = verify(&evidence(&key), &broken).unwrap_err();
        assert!(matches!(err, VerifyError::MalformedKey { .. }));
    }

    // ── signing failure ─────────────────────────────────────────────────────

    /// The criterion: a signer that cannot sign yields no evidence at all,
    /// rather than evidence with an empty signature.
    #[test]
    fn a_signing_failure_produces_no_evidence() {
        #[derive(Debug)]
        struct Broken;

        impl Sign for Broken {
            fn key_id(&self) -> SigningKeyId {
                SigningKeyId("kms-key-1".into())
            }
            fn sign(&self, _payload: &[u8]) -> Result<Signature, SignError> {
                Err(SignError::Unavailable {
                    key: self.key_id(),
                    detail: "the KMS did not answer".into(),
                })
            }
        }

        let err = sign_evidence(
            Verdict::Pass,
            CheckerId::new("json-schema", 1),
            [Digest::of(b"payload")],
            EvidenceKind::Deterministic,
            &Broken,
        )
        .unwrap_err();

        assert!(matches!(err, SignError::Unavailable { .. }));
    }

    // ── keys ────────────────────────────────────────────────────────────────

    #[test]
    fn the_same_seed_always_gives_the_same_key() {
        let a = LocalKey::from_seed("k", [3u8; SEED_LEN]);
        let b = LocalKey::from_seed("k", [3u8; SEED_LEN]);
        assert_eq!(a.public_key(), b.public_key());
    }

    #[test]
    fn generated_keys_differ() {
        assert_ne!(
            LocalKey::generate("k").public_key(),
            LocalKey::generate("k").public_key()
        );
    }

    /// A private key that has been printed is a private key that has been
    /// published.
    #[test]
    fn debug_output_does_not_contain_the_private_seed() {
        let seed = [0xab; SEED_LEN];
        let rendered = format!("{:?}", LocalKey::from_seed("k", seed));

        let seed_hex = PublicKey::from_bytes(seed).to_hex();
        assert!(!rendered.contains(&seed_hex), "the seed leaked: {rendered}");
        assert!(rendered.contains("host") || rendered.contains('k'));
    }

    #[test]
    fn a_public_key_renders_as_hex() {
        let key = PublicKey::from_bytes([0u8; PUBLIC_KEY_LEN]);
        assert_eq!(key.to_hex().len(), PUBLIC_KEY_LEN * 2);
        assert!(format!("{key:?}").contains(&key.to_hex()));
    }

    #[test]
    fn an_empty_ring_trusts_nothing() {
        let ring = KeyRing::new();
        assert!(ring.is_empty());
        assert!(ring.get(&SigningKeyId("anything".into())).is_none());
    }
}