openmls/group/public_group/

mod.rs

//! # Public Groups
//!
//! There are a few use-cases that require the tracking of an MLS group based on
//! [`PublicMessage`]s, e.g. for group membership tracking by a delivery
//! service.
//!
//! This module and its submodules contain the [`PublicGroup`] struct, as well
//! as associated helper structs the goal of which is to enable this
//! functionality.
//!
//! To avoid duplication of code and functionality, [`MlsGroup`] internally
//! relies on a [`PublicGroup`] as well.

use std::collections::HashSet;

use openmls_traits::{crypto::OpenMlsCrypto, types::Ciphersuite};
use serde::{Deserialize, Serialize};

use self::{
    diff::{PublicGroupDiff, StagedPublicGroupDiff},
    errors::CreationFromExternalError,
};
use super::{
    proposal_store::{ProposalStore, QueuedProposal},
    GroupContext, GroupId, Member, StagedCommit,
};
#[cfg(test)]
use crate::treesync::{node::parent_node::PlainUpdatePathNode, treekem::UpdatePathNode};
use crate::{
    binary_tree::{
        array_representation::{direct_path, TreeSize},
        LeafNodeIndex,
    },
    ciphersuite::{hash_ref::ProposalRef, signable::Verifiable},
    error::LibraryError,
    extensions::RequiredCapabilitiesExtension,
    framing::{InterimTranscriptHashInput, Sender},
    group::mls_group::creation::LeafNodeLifetimePolicy,
    messages::{
        group_info::{GroupInfo, VerifiableGroupInfo},
        proposals::Proposal,
        ConfirmationTag, PathSecret,
    },
    schedule::CommitSecret,
    storage::PublicStorageProvider,
    treesync::{
        errors::{DerivePathError, TreeSyncFromNodesError},
        node::{
            encryption_keys::{EncryptionKey, EncryptionKeyPair},
            leaf_node::LeafNode,
        },
        RatchetTree, RatchetTreeIn, TreeSync,
    },
    versions::ProtocolVersion,
};
#[cfg(doc)]
use crate::{framing::PublicMessage, group::MlsGroup};

pub(crate) mod builder;
pub(crate) mod diff;
pub mod errors;
pub mod process;
pub(crate) mod staged_commit;
#[cfg(test)]
mod tests;
mod validation;

#[cfg(feature = "migration-import")]
mod migration_import;

/// This struct holds all public values of an MLS group.
#[derive(Debug)]
#[cfg_attr(feature = "migration-import", derive(serde::Deserialize))]
#[cfg_attr(
    all(feature = "test-utils", feature = "migration-import"),
    derive(serde::Serialize)
)]
#[cfg_attr(any(test, feature = "test-utils"), derive(PartialEq, Clone))]
pub struct PublicGroup {
    treesync: TreeSync,
    proposal_store: ProposalStore,
    group_context: GroupContext,
    interim_transcript_hash: Vec<u8>,
    // Most recent confirmation tag. Kept here for verification purposes.
    confirmation_tag: ConfirmationTag,
}

/// This is a wrapper type, because we can't implement the storage traits on `Vec<u8>`.
#[derive(Debug, Serialize, Deserialize)]
pub struct InterimTranscriptHash(pub Vec<u8>);

impl PublicGroup {
    /// Create a new PublicGroup from a [`TreeSync`] instance and a
    /// [`GroupInfo`].
    pub(crate) fn new(
        crypto: &impl OpenMlsCrypto,
        treesync: TreeSync,
        group_context: GroupContext,
        initial_confirmation_tag: ConfirmationTag,
    ) -> Result<Self, LibraryError> {
        let interim_transcript_hash = {
            let input = InterimTranscriptHashInput::from(&initial_confirmation_tag);

            input.calculate_interim_transcript_hash(
                crypto,
                group_context.ciphersuite(),
                group_context.confirmed_transcript_hash(),
            )?
        };

        Ok(PublicGroup {
            treesync,
            proposal_store: ProposalStore::new(),
            group_context,
            interim_transcript_hash,
            confirmation_tag: initial_confirmation_tag,
        })
    }

    /// Create a [`PublicGroup`] instance to start tracking an existing MLS group.
    ///
    /// This function performs basic validation checks and returns an error if
    /// one of the checks fails. See [`CreationFromExternalError`] for more
    /// details.
    #[openmls_traits::maybe_async]
    pub async fn from_external<StorageProvider, StorageError>(
        crypto: &impl OpenMlsCrypto,
        storage: &StorageProvider,
        ratchet_tree: RatchetTreeIn,
        verifiable_group_info: VerifiableGroupInfo,
        proposal_store: ProposalStore,
    ) -> Result<(Self, GroupInfo), CreationFromExternalError<StorageError>>
    where
        StorageProvider: PublicStorageProvider<Error = StorageError>,
    {
        Self::from_external_with_lifetime_policy(
            crypto,
            storage,
            ratchet_tree,
            verifiable_group_info,
            proposal_store,
            LeafNodeLifetimePolicy::Verify,
        )
        .await
    }

    /// Like [`Self::from_external`], but checks the lifetimes of the leaf nodes
    /// in the ratchet tree under `lifetime_policy`.
    #[openmls_traits::maybe_async]
    pub async fn from_external_with_lifetime_policy<StorageProvider, StorageError>(
        crypto: &impl OpenMlsCrypto,
        storage: &StorageProvider,
        ratchet_tree: RatchetTreeIn,
        verifiable_group_info: VerifiableGroupInfo,
        proposal_store: ProposalStore,
        lifetime_policy: LeafNodeLifetimePolicy,
    ) -> Result<(Self, GroupInfo), CreationFromExternalError<StorageError>>
    where
        StorageProvider: PublicStorageProvider<Error = StorageError>,
    {
        let (public_group, group_info) = PublicGroup::from_ratchet_tree(
            crypto,
            ratchet_tree,
            verifiable_group_info,
            proposal_store,
            lifetime_policy,
        )?;

        public_group
            .store(storage)
            .await
            .map_err(CreationFromExternalError::WriteToStorageError)?;

        Ok((public_group, group_info))
    }

    pub(crate) fn from_ratchet_tree<StorageError>(
        crypto: &impl OpenMlsCrypto,
        ratchet_tree: RatchetTreeIn,
        verifiable_group_info: VerifiableGroupInfo,
        proposal_store: ProposalStore,
        validate_lifetimes: LeafNodeLifetimePolicy,
    ) -> Result<(Self, GroupInfo), CreationFromExternalError<StorageError>> {
        let ciphersuite = verifiable_group_info.ciphersuite();
        crypto
            .supports(ciphersuite)
            .map_err(|_| CreationFromExternalError::UnsupportedCiphersuite(ciphersuite))?;

        let group_id = verifiable_group_info.group_id();
        let ratchet_tree = ratchet_tree
            .into_verified(ciphersuite, crypto, group_id)
            .map_err(|e| {
                CreationFromExternalError::TreeSyncError(TreeSyncFromNodesError::RatchetTreeError(
                    e,
                ))
            })?;

        // Create a RatchetTree from the given nodes. We have to do this before
        // verifying the group info, since we need to find the Credential to verify the
        // signature against.
        let treesync = TreeSync::from_ratchet_tree(crypto, ciphersuite, ratchet_tree)?;

        let mut encryption_keys = HashSet::new();
        let mut signature_keys = HashSet::new();

        // Perform basic checks that the leaf nodes in the ratchet tree are valid
        // These checks only do those that don't need group context. We do the full
        // checks later, but do these here to fail early in case of funny business
        // https://validation.openmls.tech/#valn1407
        treesync.full_leaves().try_for_each(|(_, leaf_node)| {
            leaf_node.validate_locally()?;

            // Check that no two nodes share a signature key.
            // https://validation.openmls.tech/#valn0111
            if !signature_keys.insert(leaf_node.signature_key()) {
                return Err(CreationFromExternalError::DuplicateSignatureKey);
            }

            // Check that no two nodes share an encryption key.
            // https://validation.openmls.tech/#valn0112
            if !encryption_keys.insert(leaf_node.encryption_key()) {
                return Err(CreationFromExternalError::DuplicateEncryptionKey);
            }

            Ok(())
        })?;

        // For each non-empty parent node and each entry in the node's unmerged_leaves field:
        treesync
            .full_parents()
            .try_for_each(|(parent_index, parent_node)| {
                // Check that no two nodes share an encryption key.
                // This is a bit stronger than what the spec requires: It requires that the encryption keys
                // in parent nodes and unmerged leaves must be unique. Here, we check that all encryption
                // keys (all leaf nodes, incl. unmerged and all parent nodes) are unique.
                //
                // https://validation.openmls.tech/#valn1410
                if !encryption_keys.insert(parent_node.encryption_key()) {
                    return Err(CreationFromExternalError::DuplicateEncryptionKey);
                }

                parent_node
                    .unmerged_leaves()
                    .iter()
                    .try_for_each(|leaf_index| {
                        let path = direct_path(*leaf_index, treesync.tree_size());

                        // https://validation.openmls.tech/#valn1408
                        // Verify that the entry represents a non-blank leaf node that is a descendant of the
                        // parent node.
                        let this_parent_offset = path
                            .iter()
                            .position(|x| x == &parent_index)
                            .ok_or(
                            CreationFromExternalError::<StorageError>::UnmergedLeafNotADescendant,
                        )?;
                        let path_leaf_to_this = &path[..this_parent_offset];


                        // https://validation.openmls.tech/#valn1409
                        // Verify that every non-blank intermediate node between the leaf node and the parent
                        // node also has an entry for the leaf node in its unmerged_leaves.
                        path_leaf_to_this
                            .iter()
                            .try_for_each(|intermediate_index| {
                                // None would be blank, and we don't care about those
                                if let Some(intermediate_node) = treesync
                                    .parent(*intermediate_index) {
                                    // The list of unmerged leaves is sorted,
                                    // which UnmergedLeaves enforces when it is
                                    // deserialized from the wire.
                                    if intermediate_node
                                        .unmerged_leaves()
                                        .binary_search(leaf_index)
                                        .is_err()
                                    {
                                        return Err(CreationFromExternalError::<StorageError>::IntermediateNodeMissingUnmergedLeaf);
                                    }
                                }

                                Ok(())
                            })
                    })
            })?;

        // https://validation.openmls.tech/#valn1402
        let group_info: GroupInfo = {
            let signer_signature_key = treesync
                .leaf(verifiable_group_info.signer())
                .ok_or(CreationFromExternalError::UnknownSender)?
                .signature_key()
                .clone()
                .into_signature_public_key_enriched(ciphersuite.signature_algorithm());

            verifiable_group_info
                .verify(crypto, &signer_signature_key)
                .map_err(|_| CreationFromExternalError::InvalidGroupInfoSignature)?
        };

        // https://validation.openmls.tech/#valn1405
        if treesync.tree_hash() != group_info.group_context().tree_hash() {
            return Err(CreationFromExternalError::TreeHashMismatch);
        }

        if group_info.group_context().protocol_version() != ProtocolVersion::Mls10 {
            return Err(CreationFromExternalError::UnsupportedMlsVersion);
        }

        let group_context = group_info.group_context().clone();

        let interim_transcript_hash = {
            let input = InterimTranscriptHashInput::from(group_info.confirmation_tag());

            input.calculate_interim_transcript_hash(
                crypto,
                group_context.ciphersuite(),
                group_context.confirmed_transcript_hash(),
            )?
        };

        let public_group = Self {
            treesync,
            group_context,
            interim_transcript_hash,
            confirmation_tag: group_info.confirmation_tag().clone(),
            proposal_store,
        };

        // Fully check that the leaf nodes in the ratchet tree are valid
        // https://validation.openmls.tech/#valn1407
        public_group
            .treesync
            .full_leaves()
            .try_for_each(|(_, leaf_node)| {
                public_group.validate_leaf_node(leaf_node, validate_lifetimes)
            })?;

        Ok((public_group, group_info))
    }

    /// Returns the index of the sender of a staged, external commit.
    pub fn ext_commit_sender_index(
        &self,
        commit: &StagedCommit,
    ) -> Result<LeafNodeIndex, LibraryError> {
        self.leftmost_free_index(commit.queued_proposals())
    }

    /// Returns the leftmost free leaf index.
    ///
    /// For External Commits of the "resync" type, this returns the index
    /// of the sender.
    ///
    /// The proposals must be validated before calling this function.
    pub(crate) fn leftmost_free_index<'a>(
        &self,
        queued_proposals: impl Iterator<Item = &'a QueuedProposal>,
    ) -> Result<LeafNodeIndex, LibraryError> {
        // Leftmost free leaf in the tree
        let free_leaf_index = self.treesync().free_leaf_index();
        // Indices that are freed due to queued self-remove proposals or remove
        // proposals.
        let removed_indices = queued_proposals.filter_map(|proposal| {
            match (proposal.proposal(), proposal.sender()) {
                (Proposal::Remove(r), _) => Some(r.removed),
                (Proposal::SelfRemove, Sender::Member(sender)) => Some(*sender),
                _ => None, // SelfRemove proposals must come from group members
            }
        });
        // Find the leftmost free leaf index, which is either the free leaf index
        // or the leftmost index of a self-remove proposal or remove proposal.
        removed_indices
            .into_iter()
            .chain(std::iter::once(free_leaf_index))
            .min()
            .ok_or_else(|| LibraryError::custom("No free leaf index found"))
    }

    /// Create an empty  [`PublicGroupDiff`] based on this [`PublicGroup`].
    pub(crate) fn empty_diff(&self) -> PublicGroupDiff<'_> {
        PublicGroupDiff::new(self)
    }

    /// Merge the changes performed on the [`PublicGroupDiff`] into this
    /// [`PublicGroup`].
    ///
    /// **NOTE:** The caller must ensure that the group context in the `diff` is
    ///           updated before calling this function with `update_group_context`.
    pub(crate) fn merge_diff(&mut self, diff: StagedPublicGroupDiff) {
        self.treesync.merge_diff(diff.staged_diff);
        self.group_context = diff.group_context;
        self.interim_transcript_hash = diff.interim_transcript_hash;
        self.confirmation_tag = diff.confirmation_tag;
    }

    /// Derives [`EncryptionKeyPair`]s for the nodes in the shared direct path
    /// of the leaves with index `leaf_index` and `sender_index`.  This function
    /// also checks that the derived public keys match the existing public keys.
    ///
    /// Returns the [`CommitSecret`] derived from the path secret of the root
    /// node, as well as the derived [`EncryptionKeyPair`]s. Returns an error if
    /// the target leaf is outside of the tree.
    ///
    /// Returns [`DerivePathError::PublicKeyMismatch`] if the derived keys don't
    /// match with the existing ones.
    ///
    /// Returns [`DerivePathError::LibraryError`] if the sender_index is not
    /// in the tree.
    pub(crate) fn derive_path_secrets(
        &self,
        crypto: &impl OpenMlsCrypto,
        ciphersuite: Ciphersuite,
        path_secret: PathSecret,
        sender_index: LeafNodeIndex,
        leaf_index: LeafNodeIndex,
    ) -> Result<(Vec<EncryptionKeyPair>, CommitSecret), DerivePathError> {
        self.treesync.derive_path_secrets(
            crypto,
            ciphersuite,
            path_secret,
            sender_index,
            leaf_index,
        )
    }

    /// Get an iterator over all [`Member`]s of this [`PublicGroup`].
    pub fn members(&self) -> impl Iterator<Item = Member> + '_ {
        self.treesync().full_leaf_members()
    }

    /// Export the nodes of the public tree.
    pub fn export_ratchet_tree(&self) -> RatchetTree {
        self.treesync().export_ratchet_tree()
    }

    /// Add the [`QueuedProposal`] to the [`PublicGroup`]s internal [`ProposalStore`].
    #[openmls_traits::maybe_async]
    pub async fn add_proposal<Storage: PublicStorageProvider>(
        &mut self,
        storage: &Storage,
        proposal: QueuedProposal,
    ) -> Result<(), Storage::Error> {
        storage
            .queue_proposal(self.group_id(), &proposal.proposal_reference(), &proposal)
            .await?;
        self.proposal_store.add(proposal);
        Ok(())
    }

    /// Remove the Proposal with the given [`ProposalRef`] from the [`PublicGroup`]s internal [`ProposalStore`].
    #[openmls_traits::maybe_async]
    pub async fn remove_proposal<Storage: PublicStorageProvider>(
        &mut self,
        storage: &Storage,
        proposal_ref: &ProposalRef,
    ) -> Result<(), Storage::Error> {
        storage
            .remove_proposal(self.group_id(), proposal_ref)
            .await?;
        self.proposal_store.remove(proposal_ref);
        Ok(())
    }

    /// Return all queued proposals
    #[openmls_traits::maybe_async]
    pub async fn queued_proposals<Storage: PublicStorageProvider>(
        &self,
        storage: &Storage,
    ) -> Result<Vec<(ProposalRef, QueuedProposal)>, Storage::Error> {
        storage.queued_proposals(self.group_id()).await
    }
}

// Getters
impl PublicGroup {
    /// Get the ciphersuite.
    pub fn ciphersuite(&self) -> Ciphersuite {
        self.group_context.ciphersuite()
    }

    /// Get the version.
    pub fn version(&self) -> ProtocolVersion {
        self.group_context.protocol_version()
    }

    /// Get the group id.
    pub fn group_id(&self) -> &GroupId {
        self.group_context.group_id()
    }

    /// Get the group context.
    pub fn group_context(&self) -> &GroupContext {
        &self.group_context
    }

    /// Get the required capabilities.
    pub fn required_capabilities(&self) -> Option<&RequiredCapabilitiesExtension> {
        self.group_context.required_capabilities()
    }

    /// Returns the current tree state of the group, in the form of a [`TreeSync`].
    pub fn treesync(&self) -> &TreeSync {
        &self.treesync
    }

    /// Get confirmation tag.
    pub fn confirmation_tag(&self) -> &ConfirmationTag {
        &self.confirmation_tag
    }

    /// Return a reference to the leaf at the given `LeafNodeIndex` or `None` if the
    /// leaf is blank.
    pub fn leaf(&self, leaf_index: LeafNodeIndex) -> Option<&LeafNode> {
        self.treesync().leaf(leaf_index)
    }

    /// Returns the tree size
    pub(crate) fn tree_size(&self) -> TreeSize {
        self.treesync().tree_size()
    }

    fn interim_transcript_hash(&self) -> &[u8] {
        &self.interim_transcript_hash
    }

    /// Return a vector containing all [`EncryptionKey`]s for which the owner of
    /// the given `leaf_index` should have private key material.
    pub(crate) fn owned_encryption_keys(&self, leaf_index: LeafNodeIndex) -> Vec<EncryptionKey> {
        self.treesync().owned_encryption_keys(leaf_index)
    }

    /// Stores the [`PublicGroup`] to storage. Called from methods creating a new group and mutating an
    /// existing group, both inside [`PublicGroup`] and in [`MlsGroup`].
    ///
    /// [`MlsGroup`]: crate::group::MlsGroup
    #[openmls_traits::maybe_async]
    pub(crate) async fn store<Storage: PublicStorageProvider>(
        &self,
        storage: &Storage,
    ) -> Result<(), Storage::Error> {
        let group_id = self.group_context.group_id();
        storage.write_tree(group_id, self.treesync()).await?;
        storage
            .write_confirmation_tag(group_id, self.confirmation_tag())
            .await?;
        storage
            .write_context(group_id, self.group_context())
            .await?;
        storage
            .write_interim_transcript_hash(
                group_id,
                &InterimTranscriptHash(self.interim_transcript_hash.clone()),
            )
            .await?;
        Ok(())
    }

    /// Deletes the [`PublicGroup`] from storage.
    #[openmls_traits::maybe_async]
    pub async fn delete<Storage: PublicStorageProvider>(
        storage: &Storage,
        group_id: &GroupId,
    ) -> Result<(), Storage::Error> {
        storage.delete_tree(group_id).await?;
        storage.delete_confirmation_tag(group_id).await?;
        storage.delete_context(group_id).await?;
        storage.delete_interim_transcript_hash(group_id).await?;

        Ok(())
    }

    /// Loads the [`PublicGroup`] corresponding to a [`GroupId`] from storage.
    #[openmls_traits::maybe_async]
    pub async fn load<Storage: PublicStorageProvider>(
        storage: &Storage,
        group_id: &GroupId,
    ) -> Result<Option<Self>, Storage::Error> {
        let treesync = storage.tree(group_id).await?;
        let proposals: Vec<(ProposalRef, QueuedProposal)> =
            storage.queued_proposals(group_id).await?;
        let group_context = storage.group_context(group_id).await?;
        let interim_transcript_hash: Option<InterimTranscriptHash> =
            storage.interim_transcript_hash(group_id).await?;
        let confirmation_tag = storage.confirmation_tag(group_id).await?;
        let mut proposal_store = ProposalStore::new();

        for (_ref, proposal) in proposals {
            proposal_store.add(proposal);
        }

        let build = || -> Option<Self> {
            Some(Self {
                treesync: treesync?,
                proposal_store,
                group_context: group_context?,
                interim_transcript_hash: interim_transcript_hash?.0,
                confirmation_tag: confirmation_tag?,
            })
        };

        Ok(build())
    }

    /// Returns a reference to the [`ProposalStore`].
    pub(crate) fn proposal_store(&self) -> &ProposalStore {
        &self.proposal_store
    }

    /// Returns a mutable reference to the [`ProposalStore`].
    pub(crate) fn proposal_store_mut(&mut self) -> &mut ProposalStore {
        &mut self.proposal_store
    }
}

// Test functions
#[cfg(any(feature = "test-utils", test))]
impl PublicGroup {
    pub(crate) fn context_mut(&mut self) -> &mut GroupContext {
        &mut self.group_context
    }

    #[cfg(test)]
    pub(crate) fn set_group_context(&mut self, group_context: GroupContext) {
        self.group_context = group_context;
    }

    #[cfg(test)]
    pub(crate) fn encrypt_path(
        &self,
        provider: &impl crate::storage::OpenMlsProvider,
        ciphersuite: Ciphersuite,
        path: &[PlainUpdatePathNode],
        group_context: &[u8],
        exclusion_list: &HashSet<&LeafNodeIndex>,
        own_leaf_index: LeafNodeIndex,
    ) -> Result<Vec<UpdatePathNode>, LibraryError> {
        self.treesync().empty_diff().encrypt_path(
            provider.crypto(),
            ciphersuite,
            path,
            group_context,
            exclusion_list,
            own_leaf_index,
        )
    }
}