openmls/group/public_group/
mod.rs

1//! # Public Groups
2//!
3//! There are a few use-cases that require the tracking of an MLS group based on
4//! [`PublicMessage`]s, e.g. for group membership tracking by a delivery
5//! service.
6//!
7//! This module and its submodules contain the [`PublicGroup`] struct, as well
8//! as associated helper structs the goal of which is to enable this
9//! functionality.
10//!
11//! To avoid duplication of code and functionality, [`MlsGroup`] internally
12//! relies on a [`PublicGroup`] as well.
13
14use std::{collections::HashSet, iter};
15
16use openmls_traits::{crypto::OpenMlsCrypto, types::Ciphersuite};
17use serde::{Deserialize, Serialize};
18
19use self::{
20    diff::{PublicGroupDiff, StagedPublicGroupDiff},
21    errors::CreationFromExternalError,
22};
23use super::{
24    proposal_store::{ProposalStore, QueuedProposal},
25    GroupContext, GroupId, Member, StagedCommit,
26};
27#[cfg(test)]
28use crate::treesync::{node::parent_node::PlainUpdatePathNode, treekem::UpdatePathNode};
29use crate::{
30    binary_tree::{
31        array_representation::{direct_path, TreeSize},
32        LeafNodeIndex,
33    },
34    ciphersuite::{hash_ref::ProposalRef, signable::Verifiable},
35    error::LibraryError,
36    extensions::RequiredCapabilitiesExtension,
37    framing::{InterimTranscriptHashInput, Sender},
38    messages::{
39        group_info::{GroupInfo, VerifiableGroupInfo},
40        proposals::Proposal,
41        ConfirmationTag, PathSecret,
42    },
43    schedule::CommitSecret,
44    storage::PublicStorageProvider,
45    treesync::{
46        errors::{DerivePathError, TreeSyncFromNodesError},
47        node::{
48            encryption_keys::{EncryptionKey, EncryptionKeyPair},
49            leaf_node::LeafNode,
50        },
51        RatchetTree, RatchetTreeIn, TreeSync,
52    },
53    versions::ProtocolVersion,
54};
55#[cfg(doc)]
56use crate::{framing::PublicMessage, group::MlsGroup};
57
58pub(crate) mod builder;
59pub(crate) mod diff;
60pub mod errors;
61pub mod process;
62pub(crate) mod staged_commit;
63#[cfg(test)]
64mod tests;
65mod validation;
66
67/// This struct holds all public values of an MLS group.
68#[derive(Debug)]
69#[cfg_attr(any(test, feature = "test-utils"), derive(PartialEq, Clone))]
70pub struct PublicGroup {
71    treesync: TreeSync,
72    proposal_store: ProposalStore,
73    group_context: GroupContext,
74    interim_transcript_hash: Vec<u8>,
75    // Most recent confirmation tag. Kept here for verification purposes.
76    confirmation_tag: ConfirmationTag,
77}
78
79/// This is a wrapper type, because we can't implement the storage traits on `Vec<u8>`.
80#[derive(Debug, Serialize, Deserialize)]
81pub struct InterimTranscriptHash(pub Vec<u8>);
82
83impl PublicGroup {
84    /// Create a new PublicGroup from a [`TreeSync`] instance and a
85    /// [`GroupInfo`].
86    pub(crate) fn new(
87        crypto: &impl OpenMlsCrypto,
88        treesync: TreeSync,
89        group_context: GroupContext,
90        initial_confirmation_tag: ConfirmationTag,
91    ) -> Result<Self, LibraryError> {
92        let interim_transcript_hash = {
93            let input = InterimTranscriptHashInput::from(&initial_confirmation_tag);
94
95            input.calculate_interim_transcript_hash(
96                crypto,
97                group_context.ciphersuite(),
98                group_context.confirmed_transcript_hash(),
99            )?
100        };
101
102        Ok(PublicGroup {
103            treesync,
104            proposal_store: ProposalStore::new(),
105            group_context,
106            interim_transcript_hash,
107            confirmation_tag: initial_confirmation_tag,
108        })
109    }
110
111    /// Create a [`PublicGroup`] instance to start tracking an existing MLS group.
112    ///
113    /// This function performs basic validation checks and returns an error if
114    /// one of the checks fails. See [`CreationFromExternalError`] for more
115    /// details.
116    pub fn from_external<StorageProvider, StorageError>(
117        crypto: &impl OpenMlsCrypto,
118        storage: &StorageProvider,
119        ratchet_tree: RatchetTreeIn,
120        verifiable_group_info: VerifiableGroupInfo,
121        proposal_store: ProposalStore,
122    ) -> Result<(Self, GroupInfo), CreationFromExternalError<StorageError>>
123    where
124        StorageProvider: PublicStorageProvider<Error = StorageError>,
125    {
126        let (public_group, group_info) = PublicGroup::from_external_internal(
127            crypto,
128            ratchet_tree,
129            verifiable_group_info,
130            proposal_store,
131        )?;
132
133        public_group
134            .store(storage)
135            .map_err(CreationFromExternalError::WriteToStorageError)?;
136
137        Ok((public_group, group_info))
138    }
139    pub(crate) fn from_external_internal<StorageError>(
140        crypto: &impl OpenMlsCrypto,
141        ratchet_tree: RatchetTreeIn,
142        verifiable_group_info: VerifiableGroupInfo,
143        proposal_store: ProposalStore,
144    ) -> Result<(Self, GroupInfo), CreationFromExternalError<StorageError>> {
145        let ciphersuite = verifiable_group_info.ciphersuite();
146
147        let group_id = verifiable_group_info.group_id();
148        let ratchet_tree = ratchet_tree
149            .into_verified(ciphersuite, crypto, group_id)
150            .map_err(|e| {
151                CreationFromExternalError::TreeSyncError(TreeSyncFromNodesError::RatchetTreeError(
152                    e,
153                ))
154            })?;
155
156        // Create a RatchetTree from the given nodes. We have to do this before
157        // verifying the group info, since we need to find the Credential to verify the
158        // signature against.
159        let treesync = TreeSync::from_ratchet_tree(crypto, ciphersuite, ratchet_tree)?;
160
161        let mut encryption_keys = HashSet::new();
162
163        // Perform basic checks that the leaf nodes in the ratchet tree are valid
164        // These checks only do those that don't need group context. We do the full
165        // checks later, but do these here to fail early in case of funny business
166        treesync.full_leaves().try_for_each(|leaf_node| {
167            leaf_node.validate_locally()?;
168
169            // Check that no two nodes share an encryption key.
170            // This is a bit stronger than what the spec requires: It requires that the encryption keys
171            // in parent nodes and unmerged leaves must be unique. Here, we check that all encryption
172            // keys (all leaf nodes, incl. unmerged and all parent nodes) are unique.
173            //
174            // https://validation.openmls.tech/#valn1410
175            if !encryption_keys.insert(leaf_node.encryption_key()) {
176                return Err(CreationFromExternalError::DuplicateEncryptionKey);
177            }
178
179            Ok(())
180        })?;
181
182        // For each non-empty parent node and each entry in the node's unmerged_leaves field:
183        treesync
184            .full_parents()
185            .try_for_each(|(parent_index, parent_node)| {
186                // Check that no two nodes share an encryption key.
187                // This is a bit stronger than what the spec requires: It requires that the encryption keys
188                // in parent nodes and unmerged leaves must be unique. Here, we check that all encryption
189                // keys (all leaf nodes, incl. unmerged and all parent nodes) are unique.
190                //
191                // https://validation.openmls.tech/#valn1410
192                if !encryption_keys.insert(parent_node.encryption_key()) {
193                    return Err(CreationFromExternalError::DuplicateEncryptionKey);
194                }
195
196                parent_node
197                    .unmerged_leaves()
198                    .iter()
199                    .try_for_each(|leaf_index| {
200                        let path = direct_path(*leaf_index, treesync.tree_size());
201
202                        // https://validation.openmls.tech/#valn1408
203                        // Verify that the entry represents a non-blank leaf node that is a descendant of the
204                        // parent node.
205                        let this_parent_offset = path
206                            .iter()
207                            .position(|x| x == &parent_index)
208                            .ok_or(
209                            CreationFromExternalError::<StorageError>::UnmergedLeafNotADescendant,
210                        )?;
211                        let path_leaf_to_this = &path[..this_parent_offset];
212
213
214                        // https://validation.openmls.tech/#valn1409
215                        // Verify that every non-blank intermediate node between the leaf node and the parent
216                        // node also has an entry for the leaf node in its unmerged_leaves.
217                        path_leaf_to_this
218                            .iter()
219                            .try_for_each(|intermediate_index| {
220                                // None would be blank, and we don't care about those
221                                if let Some(intermediate_node) = treesync
222                                    .parent(*intermediate_index) {
223                                    if !intermediate_node.unmerged_leaves().contains(leaf_index) {
224                                        return Err(CreationFromExternalError::<StorageError>::IntermediateNodeMissingUnmergedLeaf);
225                                    }
226                                }
227
228                                Ok(())
229                            })
230                    })
231            })?;
232
233        // https://validation.openmls.tech/#valn1402
234        let group_info: GroupInfo = {
235            let signer_signature_key = treesync
236                .leaf(verifiable_group_info.signer())
237                .ok_or(CreationFromExternalError::UnknownSender)?
238                .signature_key()
239                .clone()
240                .into_signature_public_key_enriched(ciphersuite.signature_algorithm());
241
242            verifiable_group_info
243                .verify(crypto, &signer_signature_key)
244                .map_err(|_| CreationFromExternalError::InvalidGroupInfoSignature)?
245        };
246
247        // https://validation.openmls.tech/#valn1405
248        if treesync.tree_hash() != group_info.group_context().tree_hash() {
249            return Err(CreationFromExternalError::TreeHashMismatch);
250        }
251
252        if group_info.group_context().protocol_version() != ProtocolVersion::Mls10 {
253            return Err(CreationFromExternalError::UnsupportedMlsVersion);
254        }
255
256        let group_context = group_info.group_context().clone();
257
258        let interim_transcript_hash = {
259            let input = InterimTranscriptHashInput::from(group_info.confirmation_tag());
260
261            input.calculate_interim_transcript_hash(
262                crypto,
263                group_context.ciphersuite(),
264                group_context.confirmed_transcript_hash(),
265            )?
266        };
267
268        let public_group = Self {
269            treesync,
270            group_context,
271            interim_transcript_hash,
272            confirmation_tag: group_info.confirmation_tag().clone(),
273            proposal_store,
274        };
275
276        // Fully check that the leaf nodes in the ratchet tree are valid
277        // https://validation.openmls.tech/#valn1407
278        public_group
279            .treesync
280            .full_leaves()
281            .try_for_each(|leaf_node| public_group.validate_leaf_node(leaf_node))?;
282
283        Ok((public_group, group_info))
284    }
285
286    /// Returns the index of the sender of a staged, external commit.
287    pub fn ext_commit_sender_index(
288        &self,
289        commit: &StagedCommit,
290    ) -> Result<LeafNodeIndex, LibraryError> {
291        self.leftmost_free_index(iter::empty(), commit.queued_proposals())
292    }
293
294    /// Returns the leftmost free leaf index.
295    ///
296    /// For External Commits of the "resync" type, this returns the index
297    /// of the sender.
298    ///
299    /// The proposals must be validated before calling this function.
300    pub(crate) fn leftmost_free_index<'a>(
301        &self,
302        inline_proposals: impl Iterator<Item = &'a Proposal>,
303        queued_proposals: impl Iterator<Item = &'a QueuedProposal>,
304    ) -> Result<LeafNodeIndex, LibraryError> {
305        // Leftmost free leaf in the tree
306        let free_leaf_index = self.treesync().free_leaf_index();
307        // Indices that are freed due to queued self-remove proposals or remove
308        // proposals.
309        let removed_indices = queued_proposals.filter_map(|proposal| {
310            match (proposal.proposal(), proposal.sender()) {
311                (Proposal::Remove(r), _) => Some(r.removed),
312                (Proposal::SelfRemove, Sender::Member(sender)) => Some(*sender),
313                _ => None, // SelfRemove proposals must come from group members
314            }
315        });
316        let more_removed_indices = inline_proposals.filter_map(|proposal| match proposal {
317            Proposal::Remove(r) => Some(r.removed),
318            _ => None,
319        });
320        // Find the leftmost free leaf index, which is either the free leaf index
321        // or the leftmost index of a self-remove proposal or remove proposal.
322        removed_indices
323            .into_iter()
324            .chain(more_removed_indices)
325            .chain(std::iter::once(free_leaf_index))
326            .min()
327            .ok_or_else(|| LibraryError::custom("No free leaf index found"))
328    }
329
330    /// Create an empty  [`PublicGroupDiff`] based on this [`PublicGroup`].
331    pub(crate) fn empty_diff(&self) -> PublicGroupDiff {
332        PublicGroupDiff::new(self)
333    }
334
335    /// Merge the changes performed on the [`PublicGroupDiff`] into this
336    /// [`PublicGroup`].
337    ///
338    /// **NOTE:** The caller must ensure that the group context in the `diff` is
339    ///           updated before calling this function with `update_group_context`.
340    pub(crate) fn merge_diff(&mut self, diff: StagedPublicGroupDiff) {
341        self.treesync.merge_diff(diff.staged_diff);
342        self.group_context = diff.group_context;
343        self.interim_transcript_hash = diff.interim_transcript_hash;
344        self.confirmation_tag = diff.confirmation_tag;
345    }
346
347    /// Derives [`EncryptionKeyPair`]s for the nodes in the shared direct path
348    /// of the leaves with index `leaf_index` and `sender_index`.  This function
349    /// also checks that the derived public keys match the existing public keys.
350    ///
351    /// Returns the [`CommitSecret`] derived from the path secret of the root
352    /// node, as well as the derived [`EncryptionKeyPair`]s. Returns an error if
353    /// the target leaf is outside of the tree.
354    ///
355    /// Returns [`DerivePathError::PublicKeyMismatch`] if the derived keys don't
356    /// match with the existing ones.
357    ///
358    /// Returns [`DerivePathError::LibraryError`] if the sender_index is not
359    /// in the tree.
360    pub(crate) fn derive_path_secrets(
361        &self,
362        crypto: &impl OpenMlsCrypto,
363        ciphersuite: Ciphersuite,
364        path_secret: PathSecret,
365        sender_index: LeafNodeIndex,
366        leaf_index: LeafNodeIndex,
367    ) -> Result<(Vec<EncryptionKeyPair>, CommitSecret), DerivePathError> {
368        self.treesync.derive_path_secrets(
369            crypto,
370            ciphersuite,
371            path_secret,
372            sender_index,
373            leaf_index,
374        )
375    }
376
377    /// Get an iterator over all [`Member`]s of this [`PublicGroup`].
378    pub fn members(&self) -> impl Iterator<Item = Member> + '_ {
379        self.treesync().full_leave_members()
380    }
381
382    /// Export the nodes of the public tree.
383    pub fn export_ratchet_tree(&self) -> RatchetTree {
384        self.treesync().export_ratchet_tree()
385    }
386
387    /// Add the [`QueuedProposal`] to the [`PublicGroup`]s internal [`ProposalStore`].
388    pub fn add_proposal<Storage: PublicStorageProvider>(
389        &mut self,
390        storage: &Storage,
391        proposal: QueuedProposal,
392    ) -> Result<(), Storage::Error> {
393        storage.queue_proposal(self.group_id(), &proposal.proposal_reference(), &proposal)?;
394        self.proposal_store.add(proposal);
395        Ok(())
396    }
397
398    /// Remove the Proposal with the given [`ProposalRef`] from the [`PublicGroup`]s internal [`ProposalStore`].
399    pub fn remove_proposal<Storage: PublicStorageProvider>(
400        &mut self,
401        storage: &Storage,
402        proposal_ref: &ProposalRef,
403    ) -> Result<(), Storage::Error> {
404        storage.remove_proposal(self.group_id(), proposal_ref)?;
405        self.proposal_store.remove(proposal_ref);
406        Ok(())
407    }
408
409    /// Return all queued proposals
410    pub fn queued_proposals<Storage: PublicStorageProvider>(
411        &self,
412        storage: &Storage,
413    ) -> Result<Vec<(ProposalRef, QueuedProposal)>, Storage::Error> {
414        storage.queued_proposals(self.group_id())
415    }
416}
417
418// Getters
419impl PublicGroup {
420    /// Get the ciphersuite.
421    pub fn ciphersuite(&self) -> Ciphersuite {
422        self.group_context.ciphersuite()
423    }
424
425    /// Get the version.
426    pub fn version(&self) -> ProtocolVersion {
427        self.group_context.protocol_version()
428    }
429
430    /// Get the group id.
431    pub fn group_id(&self) -> &GroupId {
432        self.group_context.group_id()
433    }
434
435    /// Get the group context.
436    pub fn group_context(&self) -> &GroupContext {
437        &self.group_context
438    }
439
440    /// Get the required capabilities.
441    pub fn required_capabilities(&self) -> Option<&RequiredCapabilitiesExtension> {
442        self.group_context.required_capabilities()
443    }
444
445    /// Get treesync.
446    fn treesync(&self) -> &TreeSync {
447        &self.treesync
448    }
449
450    /// Get confirmation tag.
451    pub fn confirmation_tag(&self) -> &ConfirmationTag {
452        &self.confirmation_tag
453    }
454
455    /// Return a reference to the leaf at the given `LeafNodeIndex` or `None` if the
456    /// leaf is blank.
457    pub fn leaf(&self, leaf_index: LeafNodeIndex) -> Option<&LeafNode> {
458        self.treesync().leaf(leaf_index)
459    }
460
461    /// Returns the tree size
462    pub(crate) fn tree_size(&self) -> TreeSize {
463        self.treesync().tree_size()
464    }
465
466    fn interim_transcript_hash(&self) -> &[u8] {
467        &self.interim_transcript_hash
468    }
469
470    /// Return a vector containing all [`EncryptionKey`]s for which the owner of
471    /// the given `leaf_index` should have private key material.
472    pub(crate) fn owned_encryption_keys(&self, leaf_index: LeafNodeIndex) -> Vec<EncryptionKey> {
473        self.treesync().owned_encryption_keys(leaf_index)
474    }
475
476    /// Stores the [`PublicGroup`] to storage. Called from methods creating a new group and mutating an
477    /// existing group, both inside [`PublicGroup`] and in [`MlsGroup`].
478    ///
479    /// [`MlsGroup`]: crate::group::MlsGroup
480    pub(crate) fn store<Storage: PublicStorageProvider>(
481        &self,
482        storage: &Storage,
483    ) -> Result<(), Storage::Error> {
484        let group_id = self.group_context.group_id();
485        storage.write_tree(group_id, self.treesync())?;
486        storage.write_confirmation_tag(group_id, self.confirmation_tag())?;
487        storage.write_context(group_id, self.group_context())?;
488        storage.write_interim_transcript_hash(
489            group_id,
490            &InterimTranscriptHash(self.interim_transcript_hash.clone()),
491        )?;
492        Ok(())
493    }
494
495    /// Deletes the [`PublicGroup`] from storage.
496    pub fn delete<Storage: PublicStorageProvider>(
497        storage: &Storage,
498        group_id: &GroupId,
499    ) -> Result<(), Storage::Error> {
500        storage.delete_tree(group_id)?;
501        storage.delete_confirmation_tag(group_id)?;
502        storage.delete_context(group_id)?;
503        storage.delete_interim_transcript_hash(group_id)?;
504
505        Ok(())
506    }
507
508    /// Loads the [`PublicGroup`] corresponding to a [`GroupId`] from storage.
509    pub fn load<Storage: PublicStorageProvider>(
510        storage: &Storage,
511        group_id: &GroupId,
512    ) -> Result<Option<Self>, Storage::Error> {
513        let treesync = storage.tree(group_id)?;
514        let proposals: Vec<(ProposalRef, QueuedProposal)> = storage.queued_proposals(group_id)?;
515        let group_context = storage.group_context(group_id)?;
516        let interim_transcript_hash: Option<InterimTranscriptHash> =
517            storage.interim_transcript_hash(group_id)?;
518        let confirmation_tag = storage.confirmation_tag(group_id)?;
519        let mut proposal_store = ProposalStore::new();
520
521        for (_ref, proposal) in proposals {
522            proposal_store.add(proposal);
523        }
524
525        let build = || -> Option<Self> {
526            Some(Self {
527                treesync: treesync?,
528                proposal_store,
529                group_context: group_context?,
530                interim_transcript_hash: interim_transcript_hash?.0,
531                confirmation_tag: confirmation_tag?,
532            })
533        };
534
535        Ok(build())
536    }
537
538    /// Returns a reference to the [`ProposalStore`].
539    pub(crate) fn proposal_store(&self) -> &ProposalStore {
540        &self.proposal_store
541    }
542
543    /// Returns a mutable reference to the [`ProposalStore`].
544    pub(crate) fn proposal_store_mut(&mut self) -> &mut ProposalStore {
545        &mut self.proposal_store
546    }
547}
548
549// Test functions
550#[cfg(any(feature = "test-utils", test))]
551impl PublicGroup {
552    pub(crate) fn context_mut(&mut self) -> &mut GroupContext {
553        &mut self.group_context
554    }
555
556    #[cfg(test)]
557    pub(crate) fn set_group_context(&mut self, group_context: GroupContext) {
558        self.group_context = group_context;
559    }
560
561    #[cfg(test)]
562    pub(crate) fn encrypt_path(
563        &self,
564        provider: &impl crate::storage::OpenMlsProvider,
565        ciphersuite: Ciphersuite,
566        path: &[PlainUpdatePathNode],
567        group_context: &[u8],
568        exclusion_list: &HashSet<&LeafNodeIndex>,
569        own_leaf_index: LeafNodeIndex,
570    ) -> Result<Vec<UpdatePathNode>, LibraryError> {
571        self.treesync().empty_diff().encrypt_path(
572            provider.crypto(),
573            ciphersuite,
574            path,
575            group_context,
576            exclusion_list,
577            own_leaf_index,
578        )
579    }
580}