wot_network/

search.rs

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

use std::fmt::Display;

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

/// Error type for [`ResidualNetworkTrait::reduce`]
#[derive(Debug)]
pub struct ReduceError(pub String);

impl Display for ReduceError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.0)
    }
}

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

/// The interface of a residual network, which can (optionally) be used in a [`WotSearchTrait`].
pub trait ResidualNetworkTrait {
    /// Set up a new residual network based on `network`, and with the given set of `anchors`.
    ///
    /// TODO: allow implementations to keep a reference to `&Network`, with appropriate lifetimes?
    fn new(network: &Network, anchors: &[TrustAnchor]) -> Self;

    /// Find the "best" path from the anchors to `target`, given the remaining capacities in this
    /// residual network.
    ///
    /// Returns a [`Path`] and the effective trust amount for this path, given the flow constraints
    /// of this residual network.
    ///
    /// Note that the effective trust amount (which is limited by the current limitations of the
    /// residual network state) can be lower than the "standalone" trust amount of that path.
    /// (This limitation can be caused by a capacity limit of the anchor, an edge or a node along
    /// the path).
    fn search(&self, target: &Binding) -> Option<(Path, u8)>;

    /// Reduce the remaining capacities in this residual network by `reduce_amount` for `path`.
    ///
    /// Returns a `ReduceError` if the reduce operation was invalid.
    ///
    /// In the error case, the residual network's state should not be changed.
    /// Using flow with this function should be an atomic operation!
    fn reduce(&mut self, path: &Path, reduce_amount: u8) -> Result<(), ReduceError>;

    /// Get the remaining flow capacity of a trust anchor, specifically in its role as an anchor.
    ///
    /// `None`, if `anchor` is not a trust anchor,
    fn anchor_capacity(&self, anchor: &Certificate) -> Option<u8>;

    /// The amount of remaining available outgoing flow capacity from `cert`,
    /// in any context (including as an anchor): along a delegation edge, or along certification
    /// edges.
    ///
    /// By default, all certificates start with an outbound capacity of `120`
    /// (but a certificate may be initialized differently, in a residual network).
    fn outbound_capacity(&self, cert: &Certificate) -> u8;

    /// The amount of flow that has been used between `issuer` and `target` (along delegation
    /// edges), in this residual network.
    ///
    /// `issuer` and `target` may not be the same certificate in calls to this function.
    fn used_flow_between(&self, issuer: &Certificate, target: &Certificate) -> u8;
}

/// An interface for searching paths that authenticate identity bindings in a Web of Trust network.
pub trait WotSearchTrait {
    fn new(network: Network, anchors: Vec<TrustAnchor>, target: Binding) -> Self;

    /// Authenticate the link between the certificate and the identity in the `target` Binding
    /// with an OpenPGP "Web of Trust" lookup.
    ///
    /// Searches for enough paths to satisfy `target_trust_amount`, if possible.
    fn search(&mut self, 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 anchors, edges or nodes 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 new_with_paths(paths: Vec<(Path, u8)>) -> Self {
        Self { paths }
    }

    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 path's
    /// standalone amount: The flow capacity can be limited (by other paths in this `Paths`)
    /// by the remaining capacity of the anchor, edges or nodes along the path.
    pub fn add(&mut self, path: Path, effective_amount: u8) {
        assert!(
            effective_amount <= path.standalone_amount(),
            "Effective amount cannot exceed the standalone 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 (independent) evidence that the [Network] offers for an
    /// identity binding, based on the configured [TrustAnchor]s.
    ///
    /// Note that the sum of total effective trust amounts of multiple paths can exceed the
    /// value 120 (which is a limit of trust amount values in all other contexts).
    pub fn total_effective_amount(&self) -> usize {
        self.paths
            .iter()
            .map(|(_, effective)| *effective 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 {
    pub start: Certificate,
    pub delegations: Vec<Delegation>,
    pub certification: Certification,
}

impl Path {
    pub fn new(
        start: Certificate,
        delegations: Vec<Delegation>,
        certification: Certification,
    ) -> Self {
        Self {
            start,
            delegations,
            certification,
        }
    }

    /// 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) -> &Certification {
        &self.certification
    }

    /// The "standalone trust amount" of this path.
    ///
    /// The amount is 120 for paths without a delegation edge,
    /// or the minimum trust amount of any delegation edge.
    pub(crate) fn standalone_amount(&self) -> u8 {
        self.delegations
            .iter()
            .map(|d| d.trust_amount)
            .min()
            .unwrap_or(120) // paths without delegations have trust amount "120"
    }

    /// 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 intended for informal uses, such as comparing test results with
    /// expected paths.
    pub fn certificates(&self) -> Vec<&Certificate> {
        let mut certs = vec![self.first()];
        for edge in self.delegations() {
            certs.push(edge.target())
        }

        certs.push(&self.certification.target.cert);

        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
    }

    /// An iterator over all edges in this path.
    ///
    /// This always returns a series of zero or more [`Edge::Delegation`]s,
    /// followed by exactly one [`Edge::Certification`].
    pub fn edges(&self) -> impl Iterator<Item = Edge> + '_ {
        self.delegations()
            .iter()
            .map(|d| Edge::Delegation(d.clone()))
            .chain([Edge::Certification(self.binding().clone())])
    }
}

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

impl TrustAnchor {
    /// A `trust_amount` over 120 is illegal
    pub fn new(cert: Certificate, trust_amount: u8) -> Self {
        assert!(trust_amount <= 120);

        Self { cert, trust_amount }
    }

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

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