wot_network/

search.rs

//! Data structures and traits for path searches in a Web of Trust

use crate::{Binding, Certificate, Certification, Delegation, Edge, Network};

/// An interface for searching paths that authenticate identity bindings in a Web of Trust network.
pub trait WotSearch<'a> {
    fn new(network: &'a Network, roots: &'a [TrustAnchor]) -> Self;

    /// Authenticate the link between `target_id` and `target_userid` with an OpenPGP "Web of Trust" query.
    ///
    /// Searches for enough paths to satisfy `target_trust_amount`, if possible.
    fn search(&self, binding: &Binding, target_trust_amount: usize) -> Paths;
}

/// A list of [Path]s and their *effective amount* in this search.
///
/// NOTE: The effective amount of a [Path] in the context of a [Paths] may be smaller than the
/// path's standalone amount, because edges shared with other [Path]s may restrict flow capacity.
#[derive(Debug)]
pub struct Paths {
    paths: Vec<(Path, u8)>,
}

impl Paths {
    pub fn new() -> Self {
        Self {
            paths: Default::default(),
        }
    }

    pub fn get(&self) -> &[(Path, u8)] {
        &self.paths
    }

    /// Add a [Path] to this list of paths.
    ///
    /// The `effective_amount` of the path in this set of paths can be smaller than the paths
    /// actual amount (it can be limited by the available remaining flow along one of its edges,
    /// caused by other paths in this `Paths`)
    pub fn add(&mut self, path: Path, effective_amount: u8) {
        assert!(
            effective_amount <= path.amount(),
            "Effective amount cannot exceed actual amount of the path."
        );

        self.paths.push((path, effective_amount));
    }

    /// Sum of the effective amounts of each [Path] in this [Paths] object.
    ///
    /// This is the total amount of evidence that the [Network] offers for an identity binding,
    /// based on the configured [TrustAnchor]s
    pub fn total_amount(&self) -> usize {
        self.paths.iter().map(|(_, amount)| *amount as usize).sum()
    }
}

impl Default for Paths {
    fn default() -> Self {
        Self::new()
    }
}

/// A Path starts from an anchoring [Certificate] and consists of a list of delegation edges which lead
/// to a target identity binding.
#[derive(Debug, Clone, Eq, Hash, PartialEq)]
pub struct Path {
    start: Certificate,
    delegations: Vec<Delegation>,
    binding: Option<Certification>,
}

impl Path {
    pub fn new(start: Certificate) -> Self {
        Self {
            start,
            delegations: vec![],
            binding: None,
        }
    }

    /// First cert of the path.
    pub fn first(&self) -> &Certificate {
        &self.start
    }

    /// The list of delegation edges that lead from the anchor to the target binding
    pub fn delegations(&self) -> &[Delegation] {
        &self.delegations
    }

    /// The target binding of this [Path]
    pub fn binding(&self) -> Option<&Certification> {
        self.binding.as_ref()
    }

    /// The mathematical "amount" of this path.
    ///
    /// This corresponds to the minimum "amount" of any edge in the path.
    pub(crate) fn amount(&self) -> u8 {
        // We start with the trust amount of the final binding edge (always 120) as the ceiling
        let mut min = 120;

        // ... and lower it to the minimal amount on any delegation edge.
        if self.delegations().is_empty() {
            min
        } else {
            for edge in &self.delegations {
                min = u8::min(min, edge.trust_amount());
            }
            min
        }
    }

    /// A list of certificates in this [Path], from the starting [Certificate], followed by all
    /// [Delegation] edge target [Certificate]s, and the target [Certificate] in the final [Certification] edge.
    ///
    /// This list format is mainly mostly for informal uses, such as comparing test results with
    /// expected paths.
    pub fn certificates(&self) -> Vec<Certificate> {
        let mut certs = vec![self.first().clone()];
        for edge in self.delegations() {
            certs.push(edge.target().clone())
        }

        if let Some(b) = &self.binding {
            certs.push(b.target.clone())
        } else {
            panic!("Incomplete path")
        }

        certs
    }

    /// The length of this path, counted in nodes: A path with a single edge from node A to node B
    /// is of length 2.
    pub fn length(&self) -> usize {
        // FIXME: do we need to subtract one if the last edge is a redirection to a different
        // user id in the certificate we're already at?
        self.delegations.len() + 2
    }

    pub fn edges(&self) -> impl Iterator<Item = Edge> + '_ {
        self.delegations()
            .iter()
            .map(|d| Edge::Delegation(d.clone()))
            .chain(self.binding().map(|b| Edge::Certification(b.clone())))
    }

    /// Add a delegation edge
    pub fn push(&mut self, edge: Delegation) {
        assert!(
            self.binding.is_none(),
            "Once the binding is set, no more delegations should be added"
        );

        self.delegations.push(edge)
    }

    pub fn set_binding(&mut self, bind: Certification) {
        assert!(
            self.binding.is_none(),
            "A binding should not normally be replaced"
        );

        self.binding = Some(bind)
    }
}

/// A certificate that acts as a root of trust in a Web of Trust search
#[derive(Debug, Clone, Eq, Hash, PartialEq)]
pub struct TrustAnchor {
    id: Certificate,
    trust_amount: u8,
}

impl TrustAnchor {
    /// FIXME: is a `trust_amount` over 120 illegal?
    pub fn new(cert_id: Certificate, trust_amount: u8) -> Self {
        Self {
            id: cert_id,
            trust_amount,
        }
    }

    pub fn id(&self) -> &Certificate {
        &self.id
    }

    pub fn amount(&self) -> u8 {
        self.trust_amount
    }
}