Skip to content

Plan, apply and roll back changes to a production ontology, with a blast radius report and a proof an auditor can re-check.

17.3 KB
Raw Blame
//! **RDFC-1.0, the W3C RDF Dataset Canonicalization algorithm.**
//!
//! A certified run needs to say WHICH graph it was about, and a graph is only
//! nameable by its content if two serialisations of the same dataset hash to
//! the same value. Blank nodes are what make that hard: their labels are
//! process-local, so hashing them directly gives the same dataset a different
//! address after a reload, and a content-addressed certificate whose address
//! moves for no semantic reason is worse than no address at all.
//!
//! Decision 0010 records the three options and shipped the most conservative,
//! which is to REFUSE blank nodes in certified input. That is not viable:
//! 168 of the 288 tracked `.ttl` files in this repository use blank-node
//! syntax, and a SHACL property shape is a blank node almost by construction.
//! Refusing them would refuse most of the corpus.
//!
//! ## Why this is written here rather than taken from a crate
//!
//! `rdf-canon` 0.15.3 implements RDFC-1.0 and is pinned to `oxrdf ^0.2.4`.
//! This tree is on `oxrdf 0.3`, and there has been no release in fifteen
//! months, so adopting it means a SECOND copy of oxrdf plus a conversion layer
//! that is itself untrusted. `sophia_c14n` means an entire second RDF stack.
//!
//! A canonicaliser is a trusted component: if it gives two different datasets
//! one address, a certificate vouches for an input nobody supplied. Paying
//! thousands of unverified lines for that is the trade decision 0014 declined
//! for Dafny. This module is a few hundred lines measured against the W3C
//! suite in `tests/w3c-rdfc10/`, which is the standard this repository holds
//! its own gates to.
//!
//! ## The poison budget is part of the algorithm, not a safety valve
//!
//! Section 4.4 of the Recommendation documents dataset poisoning: blank-node
//! symmetry drives `hash_n_degree_quads` superlinear, and the specification
//! tells implementers to bound the work. The bound here is a call budget, and
//! exceeding it is a REFUSAL with a named reason rather than a truncated
//! answer, because a canonical form computed under a cut-off is not canonical.
//! The W3C suite carries a negative test for exactly this and it is run.

use oxigraph::model::{BlankNode, GraphName, NamedOrBlankNode, Quad, Term};
use sha2::{Digest, Sha256, Sha384};
use std::collections::BTreeMap;

/// How many times `hash_n_degree_quads` may be entered for one dataset.
///
/// 4000 is what the reference implementations use. It is high enough that no
/// test in the W3C suite marked `low` or `medium` complexity comes near it,
/// and low enough that a poisoned dataset is refused in well under a second.
pub const DEFAULT_CALL_BUDGET: usize = 4000;

#[derive(Debug)]
pub enum CanonError {
    /// The work budget was exhausted. Named separately from every other error
    /// because it is not a statement about the dataset being malformed: it is
    /// a refusal to spend unbounded time on a dataset shaped to cost it.
    BudgetExhausted { budget: usize },
}

impl std::fmt::Display for CanonError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::BudgetExhausted { budget } => write!(
                f,
                "canonicalisation exceeded its budget of {budget} hash_n_degree_quads calls. \
                 RDFC-1.0 section 4.4 documents this as dataset poisoning: blank-node symmetry \
                 can drive the algorithm superlinear, and a canonical form computed under a \
                 cut-off is not canonical, so this is refused rather than answered"
            ),
        }
    }
}

impl std::error::Error for CanonError {}

/// Assigns `<prefix>0`, `<prefix>1`, ... in the order identifiers are first
/// seen.
///
/// The PREFIX is not cosmetic. RDFC-1.0 uses `c14n` for the canonical issuer
/// and `b` for the temporary issuers that explore permutations, and the
/// issued identifier is concatenated into the path string that
/// `hash_n_degree_quads` compares to pick a permutation. Issuing `c14n0`
/// where the algorithm says `b0` changes those comparisons and therefore the
/// labels, which is exactly how this implementation first failed W3C tests
/// 044, 045, 046 and 075 while passing the other sixty.
#[derive(Clone, Debug)]
struct Issuer {
    prefix: &'static str,
    issued: BTreeMap<String, String>,
    order: Vec<String>,
}

impl Issuer {
    fn new(prefix: &'static str) -> Self {
        Self { prefix, issued: BTreeMap::new(), order: Vec::new() }
    }

    fn issue(&mut self, existing: &str) -> String {
        if let Some(id) = self.issued.get(existing) {
            return id.clone();
        }
        let id = format!("{}{}", self.prefix, self.order.len());
        self.issued.insert(existing.to_string(), id.clone());
        self.order.push(existing.to_string());
        id
    }

    fn get(&self, existing: &str) -> Option<&String> {
        self.issued.get(existing)
    }
}

/// The hash RDFC-1.0 is parameterised over.
///
/// The Recommendation fixes SHA-256 as the default and permits others; the
/// W3C suite carries a SHA-384 variant of the diamond test, which is how this
/// parameter earns its place rather than being generality for its own sake.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub enum HashAlgorithm {
    #[default]
    Sha256,
    Sha384,
}

impl HashAlgorithm {
    fn hex(self, bytes: impl AsRef<[u8]>) -> String {
        match self {
            Self::Sha256 => format!("{:x}", Sha256::digest(bytes.as_ref())),
            Self::Sha384 => format!("{:x}", Sha384::digest(bytes.as_ref())),
        }
    }
}

/// One quad as canonical N-Quads, terminated. `Display` gives everything but
/// the full stop.
fn nquad(q: &Quad) -> String {
    format!("{q} .\n")
}

fn blank_of_subject(s: &NamedOrBlankNode) -> Option<&str> {
    match s {
        NamedOrBlankNode::BlankNode(b) => Some(b.as_str()),
        _ => None,
    }
}

fn blank_of_term(t: &Term) -> Option<&str> {
    match t {
        Term::BlankNode(b) => Some(b.as_str()),
        _ => None,
    }
}

fn blank_of_graph(g: &GraphName) -> Option<&str> {
    match g {
        GraphName::BlankNode(b) => Some(b.as_str()),
        _ => None,
    }
}

/// Every blank node mentioned by a quad, by position.
fn blanks(q: &Quad) -> Vec<&str> {
    let mut out = Vec::new();
    if let Some(b) = blank_of_subject(&q.subject) {
        out.push(b);
    }
    if let Some(b) = blank_of_term(&q.object) {
        out.push(b);
    }
    if let Some(b) = blank_of_graph(&q.graph_name) {
        out.push(b);
    }
    out
}

/// Rewrite a quad's blank nodes through `f`.
fn relabel(q: &Quad, f: &mut impl FnMut(&str) -> String) -> Quad {
    let subject = match &q.subject {
        NamedOrBlankNode::BlankNode(b) => {
            NamedOrBlankNode::BlankNode(BlankNode::new_unchecked(f(b.as_str())))
        }
        other => other.clone(),
    };
    let object = match &q.object {
        Term::BlankNode(b) => Term::BlankNode(BlankNode::new_unchecked(f(b.as_str()))),
        other => other.clone(),
    };
    let graph_name = match &q.graph_name {
        GraphName::BlankNode(b) => GraphName::BlankNode(BlankNode::new_unchecked(f(b.as_str()))),
        other => other.clone(),
    };
    Quad {
        subject,
        predicate: q.predicate.clone(),
        object,
        graph_name,
    }
}

struct State<'a> {
    /// Blank node identifier to the quads mentioning it.
    to_quads: BTreeMap<&'a str, Vec<&'a Quad>>,
    canonical: Issuer,
    budget: usize,
    spent: usize,
    hash: HashAlgorithm,
}

impl<'a> State<'a> {
    /// RDFC-1.0 section 4.6, Hash First Degree Quads.
    ///
    /// The reference blank node becomes `_:a` and every other blank node
    /// becomes `_:z`, so the hash describes the node's immediate shape without
    /// depending on any label.
    fn hash_first_degree(&self, reference: &str) -> String {
        let mut lines: Vec<String> = self
            .to_quads
            .get(reference)
            .map(|qs| {
                qs.iter()
                    .map(|q| {
                        nquad(&relabel(q, &mut |b| {
                            if b == reference { "a".to_string() } else { "z".to_string() }
                        }))
                    })
                    .collect()
            })
            .unwrap_or_default();
        lines.sort();
        self.hash.hex(lines.concat())
    }

    /// RDFC-1.0 section 4.7, Hash Related Blank Node.
    fn hash_related(
        &self,
        related: &str,
        quad: &Quad,
        issuer: &Issuer,
        position: char,
    ) -> String {
        let identifier = if let Some(id) = self.canonical.get(related) {
            format!("_:{id}")
        } else if let Some(id) = issuer.get(related) {
            format!("_:{id}")
        } else {
            self.hash_first_degree(related)
        };
        let mut input = String::new();
        input.push(position);
        if position != 'g' {
            input.push('<');
            input.push_str(quad.predicate.as_str());
            input.push('>');
        }
        input.push_str(&identifier);
        self.hash.hex(input)
    }

    /// RDFC-1.0 section 4.8, Hash N-Degree Quads.
    fn hash_n_degree(&mut self, identifier: &str, issuer: &Issuer) -> Result<(String, Issuer), CanonError> {
        self.spent += 1;
        if self.spent > self.budget {
            return Err(CanonError::BudgetExhausted { budget: self.budget });
        }

        // Hash to the related blank nodes that produced it.
        let mut hn: BTreeMap<String, Vec<String>> = BTreeMap::new();
        let quads: Vec<&Quad> = self.to_quads.get(identifier).cloned().unwrap_or_default();
        for q in &quads {
            for (position, related) in [
                ('s', blank_of_subject(&q.subject)),
                ('o', blank_of_term(&q.object)),
                ('g', blank_of_graph(&q.graph_name)),
            ] {
                let Some(related) = related else { continue };
                if related == identifier {
                    continue;
                }
                let h = self.hash_related(related, q, issuer, position);
                hn.entry(h).or_default().push(related.to_string());
            }
        }

        let mut data_to_hash = String::new();
        let mut issuer = issuer.clone();
        for (related_hash, mut nodes) in hn {
            data_to_hash.push_str(&related_hash);
            let mut chosen_path = String::new();
            let mut chosen_issuer: Option<Issuer> = None;

            nodes.sort();
            nodes.dedup_by(|a, b| a == b && false); // keep duplicates: they are distinct positions
            for permutation in Permutations::new(&nodes) {
                let mut issuer_copy = issuer.clone();
                let mut path = String::new();
                let mut recursion: Vec<String> = Vec::new();
                let mut abandoned = false;

                for related in &permutation {
                    if let Some(id) = self.canonical.get(related) {
                        path.push_str("_:");
                        path.push_str(id);
                    } else {
                        if issuer_copy.get(related).is_none() {
                            recursion.push(related.clone());
                        }
                        path.push_str("_:");
                        path.push_str(&issuer_copy.issue(related));
                    }
                    if !chosen_path.is_empty() && path.len() >= chosen_path.len() && path > chosen_path {
                        abandoned = true;
                        break;
                    }
                }
                if abandoned {
                    continue;
                }

                for related in &recursion {
                    let (hash, next) = self.hash_n_degree(related, &issuer_copy)?;
                    path.push_str("_:");
                    path.push_str(&issuer_copy.issue(related));
                    path.push('<');
                    path.push_str(&hash);
                    path.push('>');
                    issuer_copy = next;
                    if !chosen_path.is_empty() && path.len() >= chosen_path.len() && path > chosen_path {
                        abandoned = true;
                        break;
                    }
                }
                if abandoned {
                    continue;
                }

                if chosen_path.is_empty() || path < chosen_path {
                    chosen_path = path;
                    chosen_issuer = Some(issuer_copy);
                }
            }

            data_to_hash.push_str(&chosen_path);
            if let Some(c) = chosen_issuer {
                issuer = c;
            }
        }
        Ok((self.hash.hex(&data_to_hash), issuer))
    }
}

/// Every permutation of `items`, in lexicographic order of position, one at a
/// time.
///
/// Lazy because the budget is checked per `hash_n_degree` call and a list of
/// all k! permutations is built before the first of them. Built eagerly, two
/// identical blank-node stars of 11 leaves took 10 s of CPU and 1.78 GB of
/// resident memory to reach the budget (issue #293), and each further leaf
/// multiplies that. The order is the one the eager recursion produced, so
/// which path wins a tie, and therefore every label, is unchanged.
struct Permutations<'a> {
    items: &'a [String],
    indices: Vec<usize>,
    started: bool,
}

impl<'a> Permutations<'a> {
    fn new(items: &'a [String]) -> Self {
        Self { items, indices: (0..items.len()).collect(), started: false }
    }
}

impl Iterator for Permutations<'_> {
    type Item = Vec<String>;

    fn next(&mut self) -> Option<Vec<String>> {
        if self.started {
            // Next index sequence in lexicographic order, or the end.
            let i = self.indices.windows(2).rposition(|w| w[0] < w[1])?;
            let j = self.indices.iter().rposition(|&x| x > self.indices[i])?;
            self.indices.swap(i, j);
            self.indices[i + 1..].reverse();
        }
        self.started = true;
        Some(self.indices.iter().map(|&k| self.items[k].clone()).collect())
    }
}

/// Canonical blank-node labels for a dataset, as a map from the input label.
pub fn canonical_labels(
    quads: &[Quad],
    budget: usize,
    hash: HashAlgorithm,
) -> Result<BTreeMap<String, String>, CanonError> {
    let mut to_quads: BTreeMap<&str, Vec<&Quad>> = BTreeMap::new();
    for q in quads {
        for b in blanks(q) {
            to_quads.entry(b).or_default().push(q);
        }
    }
    let mut state = State {
        to_quads,
        canonical: Issuer::new("c14n"),
        budget,
        spent: 0,
        hash,
    };

    // 4.4.3 step 3: first-degree hashes, and anything uniquely hashed is
    // settled without recursion.
    let mut by_hash: BTreeMap<String, Vec<String>> = BTreeMap::new();
    let ids: Vec<String> = state.to_quads.keys().map(|s| (*s).to_string()).collect();
    for id in &ids {
        by_hash.entry(state.hash_first_degree(id)).or_default().push(id.to_string());
    }

    let mut ambiguous: Vec<(String, Vec<String>)> = Vec::new();
    for (hash, mut nodes) in by_hash {
        if nodes.len() == 1 {
            state.canonical.issue(&nodes[0]);
        } else {
            nodes.sort();
            ambiguous.push((hash, nodes));
        }
    }

    // 4.4.3 step 5: the rest, in hash order, each explored with a temporary
    // issuer so the choice of label cannot depend on input order.
    for (_, nodes) in ambiguous {
        let mut hash_path: Vec<(String, Issuer)> = Vec::new();
        for n in &nodes {
            if state.canonical.get(n).is_some() {
                continue;
            }
            let mut temp = Issuer::new("b");
            temp.issue(n);
            hash_path.push(state.hash_n_degree(n, &temp)?);
        }
        hash_path.sort_by(|a, b| a.0.cmp(&b.0));
        for (_, issuer) in hash_path {
            for existing in &issuer.order {
                state.canonical.issue(existing);
            }
        }
    }

    Ok(state
        .canonical
        .issued
        .iter()
        .map(|(k, v)| (k.clone(), v.clone()))
        .collect())
}

/// The dataset with its blank nodes relabelled `c14n0`, `c14n1`, ..., in
/// input order. The quads themselves are what `GraphStore` loads back into a
/// store; [`canonical_nquads`] is the same relabelling serialised for hashing.
pub fn canonical_quads(
    quads: &[Quad],
    budget: usize,
    hash: HashAlgorithm,
) -> Result<Vec<Quad>, CanonError> {
    let labels = canonical_labels(quads, budget, hash)?;
    Ok(quads
        .iter()
        .map(|q| relabel(q, &mut |b| labels.get(b).cloned().unwrap_or_else(|| b.to_string())))
        .collect())
}

/// The dataset in canonical N-Quads: blank nodes relabelled `c14n0`, `c14n1`,
/// ..., every quad serialised, sorted, and concatenated.
///
/// This is the form to hash. Two serialisations of the same dataset produce
/// the same string whatever their blank-node labels were.
pub fn canonical_nquads(
    quads: &[Quad],
    budget: usize,
    hash: HashAlgorithm,
) -> Result<String, CanonError> {
    let mut lines: Vec<String> =
        canonical_quads(quads, budget, hash)?.iter().map(nquad).collect();
    lines.sort();
    lines.dedup();
    Ok(lines.concat())
}

/// SHA-256 of the canonical form. This is the address of a dataset.
pub fn digest(
    quads: &[Quad],
    budget: usize,
    hash: HashAlgorithm,
) -> Result<String, CanonError> {
    Ok(hash.hex(canonical_nquads(quads, budget, hash)?))
}