core_crypto/mls/conversation/
commit_delay.rs

1use log::{debug, trace};
2use openmls::prelude::LeafNodeIndex;
3
4use super::MlsConversation;
5use crate::MlsError;
6
7/// These constants intend to ramp up the delay and flatten the curve for later positions
8const DELAY_RAMP_UP_MULTIPLIER: f32 = 120.0;
9const DELAY_RAMP_UP_SUB: u64 = 106;
10const DELAY_POS_LINEAR_INCR: u64 = 15;
11const DELAY_POS_LINEAR_RANGE: std::ops::RangeInclusive<u64> = 1..=3;
12
13impl MlsConversation {
14    /// Helps consumer by providing a deterministic delay in seconds for him to commit its pending proposal.
15    /// It depends on the index of the client in the ratchet tree
16    /// * `self_index` - ratchet tree index of self client
17    /// * `epoch` - current group epoch
18    /// * `nb_members` - number of clients in the group
19    pub fn compute_next_commit_delay(&self) -> Option<u64> {
20        use openmls::messages::proposals::Proposal;
21
22        if self.group.pending_proposals().next().is_none() {
23            trace!("No pending proposals, no delay needed");
24            return None;
25        }
26
27        let removed_index = self
28            .group
29            .pending_proposals()
30            .filter_map(|proposal| {
31                if let Proposal::Remove(remove_proposal) = proposal.proposal() {
32                    Some(remove_proposal.removed())
33                } else {
34                    None
35                }
36            })
37            .collect::<Vec<LeafNodeIndex>>();
38
39        let self_index = self.group.own_leaf_index();
40        debug!(removed_index:? = removed_index, self_index:? = self_index; "Indexes");
41        // Find a remove proposal that concerns us
42        let is_self_removed = removed_index.contains(&self_index);
43
44        // If our own client has been removed, don't commit
45        if is_self_removed {
46            debug!("Self removed from group, no delay needed");
47            return None;
48        }
49
50        let epoch = self.group.epoch().as_u64();
51        let mut own_index = self.group.own_leaf_index().u32() as u64;
52
53        // Look for members that were removed at the left of our tree in order to shift our own leaf index (post-commit tree visualization)
54        let left_tree_diff = self
55            .group
56            .members()
57            .take(own_index as usize)
58            .try_fold(0u32, |mut acc, kp| {
59                if removed_index.contains(&kp.index) {
60                    acc += 1;
61                }
62
63                Result::<_, MlsError>::Ok(acc)
64            })
65            .unwrap_or_default();
66
67        // Post-commit visualization of the number of members after remove proposals
68        let nb_members = (self.group.members().count() as u64).saturating_sub(removed_index.len() as u64);
69        // This shifts our own leaf index to the left (tree-wise) from as many as there was removed members that have a smaller leaf index than us (older members)
70        own_index = own_index.saturating_sub(left_tree_diff as u64);
71
72        Some(Self::calculate_delay(own_index, epoch, nb_members))
73    }
74
75    fn calculate_delay(self_index: u64, epoch: u64, nb_members: u64) -> u64 {
76        let position = if nb_members > 0 {
77            ((epoch % nb_members) + (self_index % nb_members)) % nb_members + 1
78        } else {
79            1
80        };
81
82        if DELAY_POS_LINEAR_RANGE.contains(&position) {
83            position.saturating_sub(1) * DELAY_POS_LINEAR_INCR
84        } else {
85            (((position as f32).ln() * DELAY_RAMP_UP_MULTIPLIER) as u64).saturating_sub(DELAY_RAMP_UP_SUB)
86        }
87    }
88}
89
90#[cfg(test)]
91mod tests {
92    use super::*;
93    use crate::test_utils::*;
94
95    #[test]
96    fn calculate_delay_single() {
97        let (self_index, epoch, nb_members) = (0, 0, 1);
98        let delay = MlsConversation::calculate_delay(self_index, epoch, nb_members);
99        assert_eq!(delay, 0);
100    }
101
102    #[test]
103    fn calculate_delay_max() {
104        let (self_index, epoch, nb_members) = (u64::MAX, u64::MAX, u64::MAX);
105        let delay = MlsConversation::calculate_delay(self_index, epoch, nb_members);
106        assert_eq!(delay, 0);
107    }
108
109    #[test]
110    fn calculate_delay_min() {
111        let (self_index, epoch, nb_members) = (u64::MIN, u64::MIN, u64::MAX);
112        let delay = MlsConversation::calculate_delay(self_index, epoch, nb_members);
113        assert_eq!(delay, 0);
114    }
115
116    #[test]
117    fn calculate_delay_zero_members() {
118        let (self_index, epoch, nb_members) = (0, 0, u64::MIN);
119        let delay = MlsConversation::calculate_delay(self_index, epoch, nb_members);
120        assert_eq!(delay, 0);
121    }
122
123    #[test]
124    fn calculate_delay_min_max() {
125        let (self_index, epoch, nb_members) = (u64::MIN, u64::MAX, u64::MAX);
126        let delay = MlsConversation::calculate_delay(self_index, epoch, nb_members);
127        assert_eq!(delay, 0);
128    }
129
130    #[test]
131    fn calculate_delay_n() {
132        let epoch = 1;
133        let nb_members = 10;
134
135        let indexes_delays = [
136            (0, 15),
137            (1, 30),
138            (2, 60),
139            (3, 87),
140            (4, 109),
141            (5, 127),
142            (6, 143),
143            (7, 157),
144            (8, 170),
145            (9, 0),
146            // wrong but it shouldn't cause problems
147            (10, 15),
148        ];
149
150        for (self_index, expected_delay) in indexes_delays {
151            let delay = MlsConversation::calculate_delay(self_index, epoch, nb_members);
152            assert_eq!(delay, expected_delay);
153        }
154    }
155
156    #[apply(all_cred_cipher)]
157    async fn calculate_delay_creator_removed(case: TestContext) {
158        let [alice, bob, charlie] = case.sessions().await;
159        Box::pin(async move {
160            let conversation = case
161                .create_conversation([&alice, &bob])
162                .await
163                .invite_notify([&charlie])
164                .await;
165            assert_eq!(conversation.member_count().await, 3);
166
167            let proposal_guard = conversation.remove_proposal(&alice).await;
168            let (proposal_guard, result) = proposal_guard.notify_member_fallible(&bob).await;
169            let bob_decrypted_message = result.unwrap();
170            let (_, result) = proposal_guard.notify_member_fallible(&charlie).await;
171            let charlie_decrypted_message = result.unwrap();
172
173            let bob_hypothetical_position = 0;
174            let charlie_hypothetical_position = 1;
175
176            assert_eq!(
177                bob_decrypted_message.delay,
178                Some(DELAY_POS_LINEAR_INCR * bob_hypothetical_position)
179            );
180
181            assert_eq!(
182                charlie_decrypted_message.delay,
183                Some(DELAY_POS_LINEAR_INCR * charlie_hypothetical_position)
184            );
185        })
186        .await;
187    }
188}