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