manul/session/
evidence.rs

1use alloc::{
2    collections::{BTreeMap, BTreeSet},
3    format,
4    string::{String, ToString},
5};
6use core::fmt::Debug;
7
8use serde::{Deserialize, Serialize};
9
10use super::{
11    echo::{EchoRound, EchoRoundError, EchoRoundMessage},
12    message::{MessageVerificationError, SignedMessageHash, SignedMessagePart},
13    session::{SessionId, SessionParameters},
14    transcript::Transcript,
15    LocalError,
16};
17use crate::{
18    protocol::{
19        BoxedFormat, DirectMessage, DirectMessageError, EchoBroadcast, EchoBroadcastError, MessageValidationError,
20        NormalBroadcast, NormalBroadcastError, Protocol, ProtocolError, ProtocolMessage, ProtocolMessagePart,
21        ProtocolMessagePartHashable, ProtocolValidationError, RoundId,
22    },
23    utils::SerializableMap,
24};
25
26/// Possible errors when verifying [`Evidence`] (evidence of malicious behavior).
27#[derive(Debug, Clone)]
28pub enum EvidenceError {
29    /// Indicates a runtime problem or a bug in the code.
30    Local(LocalError),
31    /// The evidence is improperly constructed
32    ///
33    /// This can indicate many things, such as: messages missing, invalid signatures, invalid messages,
34    /// the messages not actually proving the malicious behavior.
35    /// See the attached description for details.
36    InvalidEvidence(String),
37}
38
39impl From<MessageVerificationError> for EvidenceError {
40    fn from(error: MessageVerificationError) -> Self {
41        match error {
42            MessageVerificationError::Local(error) => Self::Local(error),
43            MessageVerificationError::InvalidSignature => Self::InvalidEvidence("Invalid message signature".into()),
44            MessageVerificationError::SignatureMismatch => {
45                Self::InvalidEvidence("The signature does not match the payload".into())
46            }
47        }
48    }
49}
50
51impl From<NormalBroadcastError> for EvidenceError {
52    fn from(error: NormalBroadcastError) -> Self {
53        Self::InvalidEvidence(format!("Failed to deserialize normal broadcast: {:?}", error))
54    }
55}
56
57impl From<MessageValidationError> for EvidenceError {
58    fn from(error: MessageValidationError) -> Self {
59        match error {
60            MessageValidationError::Local(error) => Self::Local(error),
61            MessageValidationError::InvalidEvidence(error) => Self::InvalidEvidence(error),
62        }
63    }
64}
65
66impl From<ProtocolValidationError> for EvidenceError {
67    fn from(error: ProtocolValidationError) -> Self {
68        match error {
69            ProtocolValidationError::Local(error) => Self::Local(error),
70            ProtocolValidationError::InvalidEvidence(error) => Self::InvalidEvidence(error),
71        }
72    }
73}
74
75/// A self-contained evidence of malicious behavior by a node.
76#[derive_where::derive_where(Debug)]
77#[derive(Clone, Serialize, Deserialize)]
78pub struct Evidence<P: Protocol<SP::Verifier>, SP: SessionParameters> {
79    guilty_party: SP::Verifier,
80    description: String,
81    evidence: EvidenceEnum<P, SP>,
82}
83
84impl<P, SP> Evidence<P, SP>
85where
86    P: Protocol<SP::Verifier>,
87    SP: SessionParameters,
88{
89    pub(crate) fn new_protocol_error(
90        verifier: &SP::Verifier,
91        echo_broadcast: SignedMessagePart<EchoBroadcast>,
92        normal_broadcast: SignedMessagePart<NormalBroadcast>,
93        direct_message: SignedMessagePart<DirectMessage>,
94        error: P::ProtocolError,
95        transcript: &Transcript<P, SP>,
96    ) -> Result<Self, LocalError> {
97        let required_messages = error.required_messages();
98
99        let echo_broadcast = if required_messages.this_round.echo_broadcast {
100            Some(echo_broadcast)
101        } else {
102            None
103        };
104        let normal_broadcast = if required_messages.this_round.normal_broadcast {
105            Some(normal_broadcast)
106        } else {
107            None
108        };
109        let direct_message = if required_messages.this_round.direct_message {
110            Some(direct_message)
111        } else {
112            None
113        };
114
115        let mut echo_broadcasts = BTreeMap::new();
116        let mut normal_broadcasts = BTreeMap::new();
117        let mut direct_messages = BTreeMap::new();
118        if let Some(previous_rounds) = required_messages.previous_rounds {
119            for (round_id, required) in previous_rounds {
120                if required.echo_broadcast {
121                    echo_broadcasts.insert(round_id.clone(), transcript.get_echo_broadcast(&round_id, verifier)?);
122                }
123                if required.normal_broadcast {
124                    normal_broadcasts.insert(round_id.clone(), transcript.get_normal_broadcast(&round_id, verifier)?);
125                }
126                if required.direct_message {
127                    direct_messages.insert(round_id.clone(), transcript.get_direct_message(&round_id, verifier)?);
128                }
129            }
130        }
131
132        let mut echo_hashes = BTreeMap::new();
133        let mut other_echo_broadcasts = BTreeMap::new();
134        if let Some(required_combined_echos) = required_messages.combined_echos {
135            for round_id in required_combined_echos {
136                echo_hashes.insert(
137                    round_id.clone(),
138                    transcript.get_normal_broadcast(&round_id.echo()?, verifier)?,
139                );
140                other_echo_broadcasts.insert(
141                    round_id.clone(),
142                    transcript.get_other_echo_broadcasts(&round_id, verifier)?.into(),
143                );
144            }
145        }
146
147        let description = format!("Protocol error: {error}");
148
149        Ok(Self {
150            guilty_party: verifier.clone(),
151            description,
152            evidence: EvidenceEnum::Protocol(ProtocolEvidence {
153                error,
154                direct_message,
155                echo_broadcast,
156                normal_broadcast,
157                direct_messages: direct_messages.into(),
158                echo_broadcasts: echo_broadcasts.into(),
159                normal_broadcasts: normal_broadcasts.into(),
160                other_echo_broadcasts: other_echo_broadcasts.into(),
161                echo_hashes: echo_hashes.into(),
162            }),
163        })
164    }
165
166    pub(crate) fn new_echo_round_error(
167        verifier: &SP::Verifier,
168        normal_broadcast: SignedMessagePart<NormalBroadcast>,
169        error: EchoRoundError<SP::Verifier>,
170    ) -> Result<Self, LocalError> {
171        let description = format!("Echo round error: {}", error.description());
172        match error {
173            EchoRoundError::InvalidEcho(from) => Ok(Self {
174                guilty_party: verifier.clone(),
175                description,
176                evidence: EvidenceEnum::InvalidEchoPack(InvalidEchoPackEvidence {
177                    normal_broadcast,
178                    invalid_echo_sender: from,
179                }),
180            }),
181            EchoRoundError::MismatchedBroadcasts {
182                guilty_party,
183                we_received,
184                echoed_to_us,
185            } => Ok(Self {
186                guilty_party,
187                description,
188                evidence: EvidenceEnum::MismatchedBroadcasts(MismatchedBroadcastsEvidence {
189                    we_received,
190                    echoed_to_us,
191                }),
192            }),
193        }
194    }
195
196    pub(crate) fn new_invalid_direct_message(
197        verifier: &SP::Verifier,
198        direct_message: SignedMessagePart<DirectMessage>,
199        error: DirectMessageError,
200    ) -> Self {
201        Self {
202            guilty_party: verifier.clone(),
203            description: error.to_string(),
204            evidence: EvidenceEnum::InvalidDirectMessage(InvalidDirectMessageEvidence(direct_message)),
205        }
206    }
207
208    pub(crate) fn new_invalid_echo_broadcast(
209        verifier: &SP::Verifier,
210        echo_broadcast: SignedMessagePart<EchoBroadcast>,
211        error: EchoBroadcastError,
212    ) -> Self {
213        Self {
214            guilty_party: verifier.clone(),
215            description: error.to_string(),
216            evidence: EvidenceEnum::InvalidEchoBroadcast(InvalidEchoBroadcastEvidence(echo_broadcast)),
217        }
218    }
219
220    pub(crate) fn new_invalid_normal_broadcast(
221        verifier: &SP::Verifier,
222        normal_broadcast: SignedMessagePart<NormalBroadcast>,
223        error: NormalBroadcastError,
224    ) -> Self {
225        Self {
226            guilty_party: verifier.clone(),
227            description: error.to_string(),
228            evidence: EvidenceEnum::InvalidNormalBroadcast(InvalidNormalBroadcastEvidence(normal_broadcast)),
229        }
230    }
231
232    /// Returns the verifier of the offending party.
233    pub fn guilty_party(&self) -> &SP::Verifier {
234        &self.guilty_party
235    }
236
237    /// Returns a general description of the offense.
238    pub fn description(&self) -> &str {
239        &self.description
240    }
241
242    /// Attempts to verify that the attached data constitutes enough evidence
243    /// to prove the malicious behavior of [`Self::guilty_party`].
244    ///
245    /// Returns `Ok(())` if it is the case.
246    pub fn verify(
247        &self,
248        associated_data: &<P::ProtocolError as ProtocolError<SP::Verifier>>::AssociatedData,
249    ) -> Result<(), EvidenceError> {
250        let format = BoxedFormat::new::<SP::WireFormat>();
251        match &self.evidence {
252            EvidenceEnum::Protocol(evidence) => evidence.verify::<SP>(&self.guilty_party, &format, associated_data),
253            EvidenceEnum::InvalidDirectMessage(evidence) => evidence.verify::<P, SP>(&self.guilty_party, &format),
254            EvidenceEnum::InvalidEchoBroadcast(evidence) => evidence.verify::<P, SP>(&self.guilty_party, &format),
255            EvidenceEnum::InvalidNormalBroadcast(evidence) => evidence.verify::<P, SP>(&self.guilty_party, &format),
256            EvidenceEnum::InvalidEchoPack(evidence) => evidence.verify(&self.guilty_party, &format),
257            EvidenceEnum::MismatchedBroadcasts(evidence) => evidence.verify::<SP>(&self.guilty_party),
258        }
259    }
260}
261
262#[derive_where::derive_where(Debug)]
263#[derive(Clone, Serialize, Deserialize)]
264enum EvidenceEnum<P: Protocol<SP::Verifier>, SP: SessionParameters> {
265    Protocol(ProtocolEvidence<SP::Verifier, P>),
266    InvalidDirectMessage(InvalidDirectMessageEvidence),
267    InvalidEchoBroadcast(InvalidEchoBroadcastEvidence),
268    InvalidNormalBroadcast(InvalidNormalBroadcastEvidence),
269    InvalidEchoPack(InvalidEchoPackEvidence<SP>),
270    MismatchedBroadcasts(MismatchedBroadcastsEvidence),
271}
272
273#[derive_where::derive_where(Debug)]
274#[derive(Clone, Serialize, Deserialize)]
275pub struct InvalidEchoPackEvidence<SP: SessionParameters> {
276    normal_broadcast: SignedMessagePart<NormalBroadcast>,
277    invalid_echo_sender: SP::Verifier,
278}
279
280impl<SP> InvalidEchoPackEvidence<SP>
281where
282    SP: SessionParameters,
283{
284    fn verify(&self, verifier: &SP::Verifier, format: &BoxedFormat) -> Result<(), EvidenceError> {
285        let verified = self.normal_broadcast.clone().verify::<SP>(verifier)?;
286        let deserialized = verified.payload().deserialize::<EchoRoundMessage<SP>>(format)?;
287        let invalid_echo = deserialized
288            .message_hashes
289            .get(&self.invalid_echo_sender)
290            .ok_or_else(|| {
291                EvidenceError::InvalidEvidence(format!(
292                    "Did not find {:?} in the attached message",
293                    self.invalid_echo_sender
294                ))
295            })?;
296
297        let verified_echo = match invalid_echo.clone().verify::<SP>(&self.invalid_echo_sender) {
298            Ok(echo) => echo,
299            Err(MessageVerificationError::Local(error)) => return Err(EvidenceError::Local(error)),
300            // The message was indeed incorrectly signed - fault proven
301            Err(MessageVerificationError::InvalidSignature) => return Ok(()),
302            Err(MessageVerificationError::SignatureMismatch) => return Ok(()),
303        };
304
305        // `from` sent us a correctly signed message but from another round or another session.
306        // Provable fault of `from`.
307        if verified_echo.metadata() != self.normal_broadcast.metadata() {
308            return Ok(());
309        }
310
311        Err(EvidenceError::InvalidEvidence(
312            "There is nothing wrong with the echoed message".into(),
313        ))
314    }
315}
316
317#[derive(Debug, Clone, Serialize, Deserialize)]
318pub struct MismatchedBroadcastsEvidence {
319    we_received: SignedMessagePart<EchoBroadcast>,
320    echoed_to_us: SignedMessageHash,
321}
322
323impl MismatchedBroadcastsEvidence {
324    fn verify<SP>(&self, verifier: &SP::Verifier) -> Result<(), EvidenceError>
325    where
326        SP: SessionParameters,
327    {
328        let we_received = self.we_received.clone().verify::<SP>(verifier)?;
329        let echoed_to_us = self.echoed_to_us.clone().verify::<SP>(verifier)?;
330
331        if we_received.metadata() == echoed_to_us.metadata() && !echoed_to_us.is_hash_of::<SP, _>(&self.we_received) {
332            Ok(())
333        } else {
334            Err(EvidenceError::InvalidEvidence(
335                "The attached messages don't constitute malicious behavior".into(),
336            ))
337        }
338    }
339}
340
341#[derive(Debug, Clone, Serialize, Deserialize)]
342pub struct InvalidDirectMessageEvidence(SignedMessagePart<DirectMessage>);
343
344impl InvalidDirectMessageEvidence {
345    fn verify<P, SP>(&self, verifier: &SP::Verifier, format: &BoxedFormat) -> Result<(), EvidenceError>
346    where
347        P: Protocol<SP::Verifier>,
348        SP: SessionParameters,
349    {
350        let verified_direct_message = self.0.clone().verify::<SP>(verifier)?;
351        let payload = verified_direct_message.payload();
352
353        if self.0.metadata().round_id().is_echo() {
354            Ok(EchoRound::<P, SP>::verify_direct_message_is_invalid(payload)?)
355        } else {
356            Ok(P::verify_direct_message_is_invalid(
357                format,
358                self.0.metadata().round_id(),
359                payload,
360            )?)
361        }
362    }
363}
364
365#[derive(Debug, Clone, Serialize, Deserialize)]
366pub struct InvalidEchoBroadcastEvidence(SignedMessagePart<EchoBroadcast>);
367
368impl InvalidEchoBroadcastEvidence {
369    fn verify<P, SP>(&self, verifier: &SP::Verifier, format: &BoxedFormat) -> Result<(), EvidenceError>
370    where
371        P: Protocol<SP::Verifier>,
372        SP: SessionParameters,
373    {
374        let verified_echo_broadcast = self.0.clone().verify::<SP>(verifier)?;
375        let payload = verified_echo_broadcast.payload();
376
377        if self.0.metadata().round_id().is_echo() {
378            Ok(EchoRound::<P, SP>::verify_echo_broadcast_is_invalid(payload)?)
379        } else {
380            Ok(P::verify_echo_broadcast_is_invalid(
381                format,
382                self.0.metadata().round_id(),
383                payload,
384            )?)
385        }
386    }
387}
388
389#[derive(Debug, Clone, Serialize, Deserialize)]
390pub struct InvalidNormalBroadcastEvidence(SignedMessagePart<NormalBroadcast>);
391
392impl InvalidNormalBroadcastEvidence {
393    fn verify<P, SP>(&self, verifier: &SP::Verifier, format: &BoxedFormat) -> Result<(), EvidenceError>
394    where
395        P: Protocol<SP::Verifier>,
396        SP: SessionParameters,
397    {
398        let verified_normal_broadcast = self.0.clone().verify::<SP>(verifier)?;
399        let payload = verified_normal_broadcast.payload();
400
401        if self.0.metadata().round_id().is_echo() {
402            Ok(EchoRound::<P, SP>::verify_normal_broadcast_is_invalid(format, payload)?)
403        } else {
404            Ok(P::verify_normal_broadcast_is_invalid(
405                format,
406                self.0.metadata().round_id(),
407                payload,
408            )?)
409        }
410    }
411}
412
413#[derive_where::derive_where(Debug)]
414#[derive(Clone, Serialize, Deserialize)]
415struct ProtocolEvidence<Id: Debug + Clone + Ord, P: Protocol<Id>> {
416    error: P::ProtocolError,
417    direct_message: Option<SignedMessagePart<DirectMessage>>,
418    echo_broadcast: Option<SignedMessagePart<EchoBroadcast>>,
419    normal_broadcast: Option<SignedMessagePart<NormalBroadcast>>,
420    direct_messages: SerializableMap<RoundId, SignedMessagePart<DirectMessage>>,
421    echo_broadcasts: SerializableMap<RoundId, SignedMessagePart<EchoBroadcast>>,
422    normal_broadcasts: SerializableMap<RoundId, SignedMessagePart<NormalBroadcast>>,
423    other_echo_broadcasts: SerializableMap<RoundId, SerializableMap<Id, SignedMessagePart<EchoBroadcast>>>,
424    echo_hashes: SerializableMap<RoundId, SignedMessagePart<NormalBroadcast>>,
425}
426
427fn verify_message_parts<SP, T>(
428    verifier: &SP::Verifier,
429    expected_session_id: &SessionId,
430    message_parts: &SerializableMap<RoundId, SignedMessagePart<T>>,
431) -> Result<BTreeMap<RoundId, T>, EvidenceError>
432where
433    SP: SessionParameters,
434    T: Clone + ProtocolMessagePartHashable,
435{
436    let mut verified_parts = BTreeMap::new();
437    for (round_id, message_part) in message_parts.iter() {
438        let verified = message_part.clone().verify::<SP>(verifier)?;
439        let metadata = verified.metadata();
440        if metadata.session_id() != expected_session_id || metadata.round_id() != round_id {
441            return Err(EvidenceError::InvalidEvidence(
442                "Invalid attached message metadata".into(),
443            ));
444        }
445        verified_parts.insert(round_id.clone(), verified.into_payload());
446    }
447    Ok(verified_parts)
448}
449
450fn verify_message_part<SP, T>(
451    verifier: &SP::Verifier,
452    expected_session_id: &SessionId,
453    expected_round_id: &RoundId,
454    message_part: &Option<SignedMessagePart<T>>,
455) -> Result<T, EvidenceError>
456where
457    SP: SessionParameters,
458    T: Clone + ProtocolMessagePartHashable,
459{
460    let verified_part = if let Some(message_part) = message_part {
461        let metadata = message_part.metadata();
462        if metadata.session_id() != expected_session_id || metadata.round_id() != expected_round_id {
463            return Err(EvidenceError::InvalidEvidence(
464                "Invalid attached message metadata".into(),
465            ));
466        }
467        message_part.clone().verify::<SP>(verifier)?.into_payload()
468    } else {
469        T::none()
470    };
471
472    Ok(verified_part)
473}
474
475impl<Id, P> ProtocolEvidence<Id, P>
476where
477    Id: Debug + Clone + Ord,
478    P: Protocol<Id>,
479{
480    fn verify<SP>(
481        &self,
482        verifier: &SP::Verifier,
483        format: &BoxedFormat,
484        associated_data: &<P::ProtocolError as ProtocolError<Id>>::AssociatedData,
485    ) -> Result<(), EvidenceError>
486    where
487        SP: SessionParameters<Verifier = Id>,
488    {
489        // Find the message part from the message that triggered the error
490        // and use it as a source of RoundID and SessionID.
491        // At least one part of that message will be required, as enforced by `RequiredMessageParts` invariant.
492        let metadata = if let Some(message) = &self.direct_message {
493            message.metadata()
494        } else if let Some(message) = &self.echo_broadcast {
495            message.metadata()
496        } else if let Some(message) = &self.normal_broadcast {
497            message.metadata()
498        } else {
499            return Err(EvidenceError::InvalidEvidence(
500                "At least one part of the trigger message must be present".into(),
501            ));
502        };
503
504        let session_id = metadata.session_id();
505        let round_id = metadata.round_id();
506
507        let direct_message = verify_message_part::<SP, _>(verifier, session_id, round_id, &self.direct_message)?;
508        let echo_broadcast = verify_message_part::<SP, _>(verifier, session_id, round_id, &self.echo_broadcast)?;
509        let normal_broadcast = verify_message_part::<SP, _>(verifier, session_id, round_id, &self.normal_broadcast)?;
510
511        let mut direct_messages = verify_message_parts::<SP, _>(verifier, session_id, &self.direct_messages)?;
512        let mut echo_broadcasts = verify_message_parts::<SP, _>(verifier, session_id, &self.echo_broadcasts)?;
513        let mut normal_broadcasts = verify_message_parts::<SP, _>(verifier, session_id, &self.normal_broadcasts)?;
514
515        let mut combined_echos = BTreeMap::new();
516        for (round_id, echo_hashes) in self.echo_hashes.iter() {
517            let metadata = echo_hashes.metadata();
518            let main_round_id = metadata
519                .round_id()
520                .non_echo()
521                .map_err(|_err| EvidenceError::InvalidEvidence("Invalid echo hash round ID".into()))?;
522            if metadata.session_id() != session_id || &main_round_id != round_id {
523                return Err(EvidenceError::InvalidEvidence(
524                    "Invalid attached message metadata".into(),
525                ));
526            }
527
528            let verified_echo_hashes = echo_hashes.clone().verify::<SP>(verifier)?;
529            let echo_round_payload = verified_echo_hashes
530                .payload()
531                .deserialize::<EchoRoundMessage<SP>>(format)?;
532
533            let signed_echo_broadcasts = self
534                .other_echo_broadcasts
535                .get(round_id)
536                .ok_or_else(|| EvidenceError::InvalidEvidence(format!("Missing {round_id} echo broadcasts")))?;
537
538            let mut echo_messages = BTreeMap::new();
539            for (other_verifier, echo_hash) in echo_round_payload.message_hashes.iter() {
540                let metadata = echo_hash.metadata();
541                if metadata.session_id() != session_id || metadata.round_id() != round_id {
542                    return Err(EvidenceError::InvalidEvidence("Invalid echo hash metadata".into()));
543                }
544
545                let verified_echo_hash = echo_hash.clone().verify::<SP>(other_verifier)?;
546
547                let echo_broadcast = signed_echo_broadcasts.get(other_verifier).ok_or_else(|| {
548                    EvidenceError::InvalidEvidence(format!("Missing {round_id} echo broadcast from {other_verifier:?}"))
549                })?;
550
551                let metadata = echo_broadcast.metadata();
552                if metadata.session_id() != session_id || metadata.round_id() != round_id {
553                    return Err(EvidenceError::InvalidEvidence("Invalid echo broadcast metadata".into()));
554                }
555
556                if !verified_echo_hash.is_hash_of::<SP, _>(echo_broadcast) {
557                    return Err(EvidenceError::InvalidEvidence(
558                        "Mismatch between the echoed hash and the original echo broadcast".into(),
559                    ));
560                }
561
562                let verified_echo_broadcast = echo_broadcast.clone().verify::<SP>(other_verifier)?;
563
564                echo_messages.insert(other_verifier.clone(), verified_echo_broadcast.into_payload());
565            }
566            combined_echos.insert(round_id.clone(), echo_messages);
567        }
568
569        // Merge message parts
570
571        let protocol_message = ProtocolMessage {
572            echo_broadcast,
573            normal_broadcast,
574            direct_message,
575        };
576
577        let all_rounds = echo_broadcasts
578            .keys()
579            .cloned()
580            .chain(normal_broadcasts.keys().cloned())
581            .chain(direct_messages.keys().cloned())
582            .collect::<BTreeSet<_>>();
583
584        let mut previous_messages = BTreeMap::new();
585        for round_id in all_rounds {
586            let echo_broadcast = echo_broadcasts.remove(&round_id).unwrap_or(EchoBroadcast::none());
587            let normal_broadcast = normal_broadcasts.remove(&round_id).unwrap_or(NormalBroadcast::none());
588            let direct_message = direct_messages.remove(&round_id).unwrap_or(DirectMessage::none());
589            let protocol_message = ProtocolMessage {
590                echo_broadcast,
591                normal_broadcast,
592                direct_message,
593            };
594            previous_messages.insert(round_id, protocol_message);
595        }
596
597        Ok(self.error.verify_messages_constitute_error(
598            format,
599            verifier,
600            session_id.as_ref(),
601            associated_data,
602            protocol_message,
603            previous_messages,
604            combined_echos,
605        )?)
606    }
607}
manul/session/evidence.rs

manul/session/
evidence.rs
