p2panda_encryption/traits/ordering.rs
1// SPDX-License-Identifier: MIT OR Apache-2.0
2
3//! Peers need to make sure that messages arrive "in order" to be processed correctly.
4//!
5//! We require three things:
6//!
7//! 1. Define a way to partially order our messages (for example through a vector clock), like this
8//! we can sort events "after" or "before" each other, or identify messages which arrived "at
9//! the same time".
10//! 2. Define a way to declare "dependencies", that is, messages which are required to be processed
11//! _before_ we can process this message. This is slightly different from a vector clock as we
12//! do not only declare which message we've observed "before" to help with partial ordering, but
13//! also point at additional requirements to fullfil the protocol.
14//! 3. Define a set of rules, the "protocol", peers need to follow whenever they publish new
15//! messages: What information do they need to mention for other peers to correctly order and
16//! process messages from us?
17//!
18//! An "ordering" interface allows us to implement these requirements for our custom application
19//! data types.
20#[cfg(any(test, feature = "data_scheme"))]
21use crate::crypto::xchacha20::XAeadNonce;
22#[cfg(any(test, feature = "data_scheme"))]
23use crate::data_scheme::{self, GroupSecretId};
24#[cfg(any(test, feature = "message_scheme"))]
25use crate::message_scheme::{self, Generation};
26#[cfg(any(test, feature = "message_scheme"))]
27use crate::traits::{AckedGroupMembership, ForwardSecureGroupMessage};
28#[cfg(any(test, feature = "data_scheme"))]
29use crate::traits::{GroupMembership, GroupMessage};
30
31/// Ordering protocol for p2panda's "data encryption" scheme.
32///
33/// When publishing a message peers need to make sure to provide the following informations:
34///
35/// 1. "create" control messages do not have any dependencies as they are the first messages in a
36/// group.
37/// 2. When an "add", "update" or "remove" control message gets published, that message needs to
38/// point at all the last known, previously processed control messages (by us and others).
39/// 3. Every application message needs to point at the control message which generated the used
40/// secret. Usually applications always use the "latest" group secret. In this case it's enough
41/// to point at the last known control messages (similar to point 2).
42///
43/// When a peer processes a "welcome" message (they got added to a group) then all previously seen
44/// control and application messages can be re-processed.
45///
46/// Applications can choose to remove secrets from their group bundles for forward secrecy. In this
47/// case additional logic is required to "jump" over these "outdated" application messages.
48/// Ignoring these messages can take place when processing the "welcome" message.
49#[cfg(any(test, feature = "data_scheme"))]
50pub trait Ordering<ID, OP, DGM>
51where
52 DGM: GroupMembership<ID, OP>,
53{
54 type State;
55
56 type Error: std::error::Error;
57
58 type Message: GroupMessage<ID, OP, DGM>;
59
60 fn next_control_message(
61 y: Self::State,
62 control_message: &data_scheme::ControlMessage<ID>,
63 direct_messages: &[data_scheme::DirectMessage<ID, OP, DGM>],
64 ) -> Result<(Self::State, Self::Message), Self::Error>;
65
66 fn next_application_message(
67 y: Self::State,
68 group_secret_id: GroupSecretId,
69 nonce: XAeadNonce,
70 ciphertext: Vec<u8>,
71 ) -> Result<(Self::State, Self::Message), Self::Error>;
72
73 fn queue(y: Self::State, message: &Self::Message) -> Result<Self::State, Self::Error>;
74
75 fn set_welcome(y: Self::State, message: &Self::Message) -> Result<Self::State, Self::Error>;
76
77 #[allow(clippy::type_complexity)]
78 fn next_ready_message(
79 y: Self::State,
80 ) -> Result<(Self::State, Option<Self::Message>), Self::Error>;
81}
82
83/// Ordering protocol for p2panda's "message encryption" scheme. Extra care is required here, since
84/// the strong forward secrecy guarantees makes ordering more strict.
85///
86/// When publishing a message peers need to make sure to provide the following information:
87///
88/// 1. "create" control messages do not have any dependencies as they are the first messages in a
89/// group.
90/// 2. When an "add", "update" or "remove" control message gets published, that message needs to
91/// point at a) the last known, previously processed control messages (by us and others), b) if
92/// any application messages were sent by us, the last sent message. The latter helps with peers
93/// understanding that they might miss a message when they switch to a new ratchet, they can
94/// decide to ignore this message "dependency", but will also then potentially lose it. This
95/// can be useful to do if messages get lost and peers otherwise get "stuck".
96/// 3. "ack" control messages need to point at the regarding "create", "add", "update" or "remove"
97/// control message they are acknowledging.
98/// 4. The first application message written during a new "ratchet epoch" needs to point at the
99/// "ack" or "create", "add", "update" or "remove" message which initiated that epoch.
100/// 5. Every subsequent application message needs to point at the previous application message.
101///
102/// In this example a user "Alice" creates a group with Bob. Both of them send messages into the
103/// group ("Message 1", "Messsage 2" etc.) based on the established ratchet secrets. At some point
104/// Alice decides to renew the group's seed with an "update", and at the same time (concurrently)
105/// Bob "adds" Charlie. After processing all messages in the correct order and meeting all
106/// dependencies Alice and Bob will be able to read all sent messages by each other.
107///
108/// ```text
109/// Alice
110/// ────────
111/// ┌──────┐
112/// │CREATE│
113/// └──────┘ Bob
114/// ▲ ▲ ▲ ─────
115/// │ │ │ ┌───┐
116/// │ │ └───────────────────┤ACK│
117/// │ │ ┌►└───┘
118/// │ │ │ ▲ ▲
119/// │ │ │ │
120/// Message 1 │ ┌─────────────────┘ │
121/// ▲ │ │ │ Message 1
122/// │ │ │ │ ▲
123/// │ │ │ │
124/// Message 2 │ │ │
125/// ▲ │ │ │ Message 2
126/// │ │ │ │ ▲
127/// │ │ │ │ │
128/// ┌┴─┴─┴─┐ ┌┴─┴┐
129/// │UPDATE│ Concurrent! │ADD│
130/// └──────┘ ┌►└───┘
131/// ▲ ▲ ▲ │ ▲ ▲ Charlie
132/// │ │ │ │ │ │ ─────────
133/// │ ├─┼─────────────────┘ │ ├──────────────────────┐
134/// │ │ │ │ │
135/// Message 3 │ └────────────────────┤ │ │
136/// ▲ │ │ │
137/// │ │ │ Message 3 │
138/// │ │ ▲ │
139/// Message 4 │ │ │ │
140/// │ │ │ │
141/// ┌─┴─┐ ┌┴─┴┐ ┌─┴─┐
142/// │ACK│ │ACK│ │ACK│
143/// └───┘ └───┘ └───┘
144/// ```
145///
146/// When a peer processes a "welcome" message (they got added to a group, like "Charlie" in our
147/// example), then the following steps take place:
148///
149/// 1. Control and application messages before the "welcome" message (the "add" which added us) can
150/// be ignored.
151/// 2. Control messages after or concurrent to the "welcome" message need to be processed
152/// regularly like all other messages.
153/// 3. Application messages concurrent to the "welcome" message can be ignored (as they can not be
154/// decrypted).
155///
156/// All of this "welcome" processing needs to be done before we can move on processing future
157/// messages.
158///
159/// In the previously given example "Charlie" would be added to the group by Bob's "add" control
160/// message. Charlie would process their "welcome", acknowledge it and look at all other messages
161/// now. They identified that Alice's "update" happened concurrently to the "add", so they also
162/// process this message. They ignore the "create" as it took place before the "add". They ignore
163/// "Message 1", "Message 2", "Message 3" and "Message 4" of Alice and "Message 1" and "Message 2"
164/// of Bob, as they would not be able to decrypt them. Afterwards they would be able to decrypt
165/// "Message 3" of Bob as this message was created with Charlie in mind.
166///
167/// Note that Charlie will _not_ be able to decrypt older messages of Alice and Bob as they have
168/// been encrypted by Alice prior to their knowledge that Charlie was already in the group then. As
169/// soon as Alice will learn that Charlie was added they will "forward" their ratchet state to
170/// Charlie, but this will only be used for future messages.
171#[cfg(any(test, feature = "message_scheme"))]
172pub trait ForwardSecureOrdering<ID, OP, DGM>
173where
174 DGM: AckedGroupMembership<ID, OP>,
175{
176 type State: Clone + std::fmt::Debug + serde::Serialize + for<'a> serde::Deserialize<'a>;
177
178 type Error: std::error::Error;
179
180 type Message: Clone
181 + ForwardSecureGroupMessage<ID, OP, DGM>
182 + serde::Serialize
183 + for<'a> serde::Deserialize<'a>;
184
185 fn next_control_message(
186 y: Self::State,
187 control_message: &message_scheme::ControlMessage<ID, OP>,
188 direct_messages: &[message_scheme::DirectMessage<ID, OP, DGM>],
189 ) -> Result<(Self::State, Self::Message), Self::Error>;
190
191 fn next_application_message(
192 y: Self::State,
193 generation: Generation,
194 ciphertext: Vec<u8>,
195 ) -> Result<(Self::State, Self::Message), Self::Error>;
196
197 fn queue(y: Self::State, message: &Self::Message) -> Result<Self::State, Self::Error>;
198
199 fn set_welcome(y: Self::State, message: &Self::Message) -> Result<Self::State, Self::Error>;
200
201 #[allow(clippy::type_complexity)]
202 fn next_ready_message(
203 y: Self::State,
204 ) -> Result<(Self::State, Option<Self::Message>), Self::Error>;
205}