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
54        // tree visualization)
55        let left_tree_diff = self
56            .group
57            .members()
58            .take(own_index as usize)
59            .try_fold(0u32, |mut acc, kp| {
60                if removed_index.contains(&kp.index) {
61                    acc += 1;
62                }
63
64                Result::<_, MlsError>::Ok(acc)
65            })
66            .unwrap_or_default();
67
68        // Post-commit visualization of the number of members after remove proposals
69        let nb_members = (self.group.members().count() as u64).saturating_sub(removed_index.len() as u64);
70        // This shifts our own leaf index to the left (tree-wise) from as many as there was removed members that have a
71        // smaller leaf index than us (older members)
72        own_index = own_index.saturating_sub(left_tree_diff as u64);
73
74        Some(Self::calculate_delay(own_index, epoch, nb_members))
75    }
76
77    fn calculate_delay(self_index: u64, epoch: u64, nb_members: u64) -> u64 {
78        let position = if nb_members > 0 {
79            ((epoch % nb_members) + (self_index % nb_members)) % nb_members + 1
80        } else {
81            1
82        };
83
84        if DELAY_POS_LINEAR_RANGE.contains(&position) {
85            position.saturating_sub(1) * DELAY_POS_LINEAR_INCR
86        } else {
87            (((position as f32).ln() * DELAY_RAMP_UP_MULTIPLIER) as u64).saturating_sub(DELAY_RAMP_UP_SUB)
88        }
89    }
90}
91
92#[cfg(test)]
93mod tests {
94    use super::*;
95    use crate::test_utils::*;
96
97    #[test]
98    fn calculate_delay_single() {
99        let (self_index, epoch, nb_members) = (0, 0, 1);
100        let delay = MlsConversation::calculate_delay(self_index, epoch, nb_members);
101        assert_eq!(delay, 0);
102    }
103
104    #[test]
105    fn calculate_delay_max() {
106        let (self_index, epoch, nb_members) = (u64::MAX, u64::MAX, u64::MAX);
107        let delay = MlsConversation::calculate_delay(self_index, epoch, nb_members);
108        assert_eq!(delay, 0);
109    }
110
111    #[test]
112    fn calculate_delay_min() {
113        let (self_index, epoch, nb_members) = (u64::MIN, u64::MIN, u64::MAX);
114        let delay = MlsConversation::calculate_delay(self_index, epoch, nb_members);
115        assert_eq!(delay, 0);
116    }
117
118    #[test]
119    fn calculate_delay_zero_members() {
120        let (self_index, epoch, nb_members) = (0, 0, u64::MIN);
121        let delay = MlsConversation::calculate_delay(self_index, epoch, nb_members);
122        assert_eq!(delay, 0);
123    }
124
125    #[test]
126    fn calculate_delay_min_max() {
127        let (self_index, epoch, nb_members) = (u64::MIN, u64::MAX, u64::MAX);
128        let delay = MlsConversation::calculate_delay(self_index, epoch, nb_members);
129        assert_eq!(delay, 0);
130    }
131
132    #[test]
133    fn calculate_delay_n() {
134        let epoch = 1;
135        let nb_members = 10;
136
137        let indexes_delays = [
138            (0, 15),
139            (1, 30),
140            (2, 60),
141            (3, 87),
142            (4, 109),
143            (5, 127),
144            (6, 143),
145            (7, 157),
146            (8, 170),
147            (9, 0),
148            // wrong but it shouldn't cause problems
149            (10, 15),
150        ];
151
152        for (self_index, expected_delay) in indexes_delays {
153            let delay = MlsConversation::calculate_delay(self_index, epoch, nb_members);
154            assert_eq!(delay, expected_delay);
155        }
156    }
157
158    #[apply(all_cred_cipher)]
159    async fn calculate_delay_creator_removed(case: TestContext) {
160        let [alice, bob, charlie] = case.sessions().await;
161        Box::pin(async move {
162            let conversation = case
163                .create_conversation([&alice, &bob])
164                .await
165                .invite_notify([&charlie])
166                .await;
167            assert_eq!(conversation.member_count().await, 3);
168
169            let proposal_guard = conversation.remove_proposal(&alice).await;
170            let (proposal_guard, result) = proposal_guard.notify_member_fallible(&bob).await;
171            let bob_decrypted_message = result.unwrap();
172            let (_, result) = proposal_guard.notify_member_fallible(&charlie).await;
173            let charlie_decrypted_message = result.unwrap();
174
175            let bob_hypothetical_position = 0;
176            let charlie_hypothetical_position = 1;
177
178            assert_eq!(
179                bob_decrypted_message.delay,
180                Some(DELAY_POS_LINEAR_INCR * bob_hypothetical_position)
181            );
182
183            assert_eq!(
184                charlie_decrypted_message.delay,
185                Some(DELAY_POS_LINEAR_INCR * charlie_hypothetical_position)
186            );
187        })
188        .await;
189    }
190}
core_crypto/mls/conversation/commit_delay.rs

core_crypto/mls/conversation/
commit_delay.rs
