boundgraph_core/

canonical.rs

//! Canonical CBOR encoding.
//!
//! Every BoundGraph primitive is content-addressed by the digest of its canonical
//! encoding, so the encoding must be a *function* of the value: the same
//! logical value must always produce byte-identical output, on any platform,
//! in any process.
//!
//! `serde` alone does not give that. It emits struct fields in declaration
//! order and emits map entries in iteration order, so two equal values can
//! encode differently. We therefore serialise to a [`ciborium::Value`] tree,
//! rewrite it into deterministic form, and only then emit bytes.
//!
//! Deterministic form follows RFC 8949 §4.2.1: map keys are sorted bytewise
//! and lexicographically **by their own encoded representation**, not by their
//! logical value. Sorting by logical value would order `1` before `"a"` in one
//! encoder and after it in another; sorting by encoded bytes is unambiguous.

use ciborium::Value;
use serde::Serialize;
use serde::de::DeserializeOwned;

use crate::digest::Digest;

/// Something went wrong turning a value into (or back out of) canonical bytes.
#[derive(Debug, thiserror::Error)]
pub enum CanonicalError {
    /// The value could not be represented as CBOR.
    #[error("could not encode value as canonical CBOR: {0}")]
    Encode(String),

    /// The bytes were not valid CBOR, or did not match the target type.
    #[error("could not decode canonical CBOR: {0}")]
    Decode(String),
}

/// Encode `value` as canonical CBOR.
///
/// The output is deterministic: equal values always produce equal bytes.
pub fn to_canonical_cbor<T: Serialize + ?Sized>(value: &T) -> Result<Vec<u8>, CanonicalError> {
    let tree = Value::serialized(value).map_err(|e| CanonicalError::Encode(e.to_string()))?;
    let tree = canonicalize(tree)?;
    write(&tree)
}

/// Decode canonical CBOR produced by [`to_canonical_cbor`].
pub fn from_canonical_cbor<T: DeserializeOwned>(bytes: &[u8]) -> Result<T, CanonicalError> {
    let tree: Value =
        ciborium::from_reader(bytes).map_err(|e| CanonicalError::Decode(e.to_string()))?;
    tree.deserialized()
        .map_err(|e| CanonicalError::Decode(e.to_string()))
}

/// Blanket helper: the content address of any serialisable value.
///
/// This is the single definition of identity in BoundGraph. Two values share a
/// digest if and only if they encode to the same canonical bytes.
pub trait Canonical: Serialize {
    /// The canonical CBOR encoding of this value.
    fn canonical_bytes(&self) -> Result<Vec<u8>, CanonicalError> {
        to_canonical_cbor(self)
    }

    /// The `blake3` digest of this value's canonical encoding.
    fn digest(&self) -> Result<Digest, CanonicalError> {
        Ok(Digest::of(&self.canonical_bytes()?))
    }
}

impl<T: Serialize + ?Sized> Canonical for T {}

// ── internals ───────────────────────────────────────────────────────────────

fn write(tree: &Value) -> Result<Vec<u8>, CanonicalError> {
    let mut out = Vec::new();
    ciborium::into_writer(tree, &mut out).map_err(|e| CanonicalError::Encode(e.to_string()))?;
    Ok(out)
}

/// Rewrite a CBOR tree into deterministic form, depth first.
fn canonicalize(value: Value) -> Result<Value, CanonicalError> {
    Ok(match value {
        Value::Array(items) => Value::Array(
            items
                .into_iter()
                .map(canonicalize)
                .collect::<Result<Vec<_>, _>>()?,
        ),

        Value::Map(entries) => {
            // Canonicalise children first so nested keys are themselves in
            // deterministic form before we encode them for sorting.
            let mut prepared = Vec::with_capacity(entries.len());
            for (k, v) in entries {
                let k = canonicalize(k)?;
                let v = canonicalize(v)?;
                let sort_key = write(&k)?;
                prepared.push((sort_key, k, v));
            }
            prepared.sort_by(|a, b| a.0.cmp(&b.0));
            Value::Map(prepared.into_iter().map(|(_, k, v)| (k, v)).collect())
        }

        Value::Tag(tag, inner) => Value::Tag(tag, Box::new(canonicalize(*inner)?)),

        other => other,
    })
}

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

    #[test]
    fn map_keys_are_sorted_by_encoded_bytes() {
        // Insertion order here is deliberately not sorted order.
        let mut a: BTreeMap<String, u32> = BTreeMap::new();
        a.insert("zebra".into(), 1);
        a.insert("alpha".into(), 2);

        let mut b: BTreeMap<String, u32> = BTreeMap::new();
        b.insert("alpha".into(), 2);
        b.insert("zebra".into(), 1);

        assert_eq!(
            to_canonical_cbor(&a).unwrap(),
            to_canonical_cbor(&b).unwrap()
        );
    }

    #[test]
    fn encoding_is_stable_across_calls() {
        let v = vec![("k", 1u8), ("j", 2u8)];
        let first = to_canonical_cbor(&v).unwrap();
        for _ in 0..16 {
            assert_eq!(first, to_canonical_cbor(&v).unwrap());
        }
    }

    #[test]
    fn round_trip_preserves_value() {
        let v: Vec<(String, u64)> = vec![("a".into(), 1), ("b".into(), 2)];
        let bytes = to_canonical_cbor(&v).unwrap();
        let back: Vec<(String, u64)> = from_canonical_cbor(&bytes).unwrap();
        assert_eq!(v, back);
    }

    #[test]
    fn nested_maps_are_canonicalised_too() {
        let mut inner_a: BTreeMap<String, u8> = BTreeMap::new();
        inner_a.insert("y".into(), 1);
        inner_a.insert("x".into(), 2);
        let mut outer_a: BTreeMap<String, BTreeMap<String, u8>> = BTreeMap::new();
        outer_a.insert("outer".into(), inner_a);

        let mut inner_b: BTreeMap<String, u8> = BTreeMap::new();
        inner_b.insert("x".into(), 2);
        inner_b.insert("y".into(), 1);
        let mut outer_b: BTreeMap<String, BTreeMap<String, u8>> = BTreeMap::new();
        outer_b.insert("outer".into(), inner_b);

        assert_eq!(
            to_canonical_cbor(&outer_a).unwrap(),
            to_canonical_cbor(&outer_b).unwrap()
        );
    }
}