commonware_consensus/simplex/
types.rs

1//! Types used in [crate::simplex].
2
3use crate::Viewable;
4use bytes::{Buf, BufMut};
5use commonware_codec::{
6    varint::UInt, Encode, EncodeSize, Error, Read, ReadExt, ReadRangeExt, Write,
7};
8use commonware_cryptography::{Digest, Signature as CSignature, Signer, Verifier};
9use commonware_utils::{quorum, union};
10
11/// View is a monotonically increasing counter that represents the current focus of consensus.
12pub type View = u64;
13
14/// Context is a collection of metadata from consensus about a given payload.
15/// It provides information about the current view and the parent payload that new proposals are built on.
16#[derive(Clone)]
17pub struct Context<D: Digest> {
18    /// Current view (round) of consensus.
19    pub view: View,
20
21    /// Parent the payload is built on.
22    ///
23    /// If there is a gap between the current view and the parent view, the participant
24    /// must possess a nullification for each discarded view to safely vote on the proposed
25    /// payload (any view without a nullification may eventually be finalized and skipping
26    /// it would result in a fork).
27    pub parent: (View, D),
28}
29
30/// Attributable is a trait that provides access to the signer index.
31/// This is used to identify which participant signed a given message.
32pub trait Attributable {
33    /// Returns the index of the signer (validator) who produced this message.
34    fn signer(&self) -> u32;
35}
36
37// Constants for domain separation in signature verification
38// These are used to prevent cross-protocol attacks and message-type confusion
39pub const NOTARIZE_SUFFIX: &[u8] = b"_NOTARIZE";
40pub const NULLIFY_SUFFIX: &[u8] = b"_NULLIFY";
41pub const FINALIZE_SUFFIX: &[u8] = b"_FINALIZE";
42
43/// Creates a message to be signed containing just the view number
44#[inline]
45pub fn view_message(view: View) -> Vec<u8> {
46    View::encode(&view).into()
47}
48
49/// Creates a namespace for notarize messages by appending the NOTARIZE_SUFFIX
50#[inline]
51pub fn notarize_namespace(namespace: &[u8]) -> Vec<u8> {
52    union(namespace, NOTARIZE_SUFFIX)
53}
54
55/// Creates a namespace for nullify messages by appending the NULLIFY_SUFFIX
56#[inline]
57pub fn nullify_namespace(namespace: &[u8]) -> Vec<u8> {
58    union(namespace, NULLIFY_SUFFIX)
59}
60
61/// Creates a namespace for finalize messages by appending the FINALIZE_SUFFIX
62#[inline]
63pub fn finalize_namespace(namespace: &[u8]) -> Vec<u8> {
64    union(namespace, FINALIZE_SUFFIX)
65}
66
67/// Calculates the quorum threshold for a set of validators
68/// Returns (threshold, len) where threshold is the minimum number of validators
69/// required for a quorum, and len is the total number of validators
70#[inline]
71pub fn threshold<P>(validators: &[P]) -> (u32, u32) {
72    let len = validators.len() as u32;
73    let threshold = quorum(len);
74    (threshold, len)
75}
76
77/// Voter represents all possible message types that can be sent by validators
78/// in the consensus protocol.
79#[derive(Clone, Debug, PartialEq)]
80pub enum Voter<S: CSignature, D: Digest> {
81    /// A single validator notarize over a proposal
82    Notarize(Notarize<S, D>),
83    /// An aggregated set of validator notarizes that meets quorum
84    Notarization(Notarization<S, D>),
85    /// A single validator nullify to skip the current view (usually when leader is unresponsive)
86    Nullify(Nullify<S>),
87    /// An aggregated set of validator nullifies that meets quorum
88    Nullification(Nullification<S>),
89    /// A single validator finalize over a proposal
90    Finalize(Finalize<S, D>),
91    /// An aggregated set of validator finalizes that meets quorum
92    Finalization(Finalization<S, D>),
93}
94
95impl<S: CSignature, D: Digest> Write for Voter<S, D> {
96    fn write(&self, writer: &mut impl BufMut) {
97        match self {
98            Voter::Notarize(notarize) => {
99                0u8.write(writer);
100                notarize.write(writer);
101            }
102            Voter::Notarization(notarization) => {
103                1u8.write(writer);
104                notarization.write(writer);
105            }
106            Voter::Nullify(nullify) => {
107                2u8.write(writer);
108                nullify.write(writer);
109            }
110            Voter::Nullification(nullification) => {
111                3u8.write(writer);
112                nullification.write(writer);
113            }
114            Voter::Finalize(finalize) => {
115                4u8.write(writer);
116                finalize.write(writer);
117            }
118            Voter::Finalization(finalization) => {
119                5u8.write(writer);
120                finalization.write(writer);
121            }
122        }
123    }
124}
125
126impl<S: CSignature, D: Digest> Read for Voter<S, D> {
127    type Cfg = usize;
128
129    fn read_cfg(reader: &mut impl Buf, max_len: &usize) -> Result<Self, Error> {
130        let tag = u8::read(reader)?;
131        match tag {
132            0 => Ok(Voter::Notarize(Notarize::<S, D>::read(reader)?)),
133            1 => Ok(Voter::Notarization(Notarization::<S, D>::read_cfg(
134                reader, max_len,
135            )?)),
136            2 => Ok(Voter::Nullify(Nullify::<S>::read(reader)?)),
137            3 => Ok(Voter::Nullification(Nullification::<S>::read_cfg(
138                reader, max_len,
139            )?)),
140            4 => Ok(Voter::Finalize(Finalize::<S, D>::read(reader)?)),
141            5 => Ok(Voter::Finalization(Finalization::<S, D>::read_cfg(
142                reader, max_len,
143            )?)),
144            _ => Err(Error::Invalid("consensus::simplex::Voter", "Invalid type")),
145        }
146    }
147}
148
149impl<S: CSignature, D: Digest> EncodeSize for Voter<S, D> {
150    fn encode_size(&self) -> usize {
151        1 + match self {
152            Voter::Notarize(notarize) => notarize.encode_size(),
153            Voter::Notarization(notarization) => notarization.encode_size(),
154            Voter::Nullify(nullify) => nullify.encode_size(),
155            Voter::Nullification(nullification) => nullification.encode_size(),
156            Voter::Finalize(finalize) => finalize.encode_size(),
157            Voter::Finalization(finalization) => finalization.encode_size(),
158        }
159    }
160}
161
162impl<S: CSignature, D: Digest> Viewable for Voter<S, D> {
163    type View = View;
164
165    fn view(&self) -> View {
166        match self {
167            Voter::Notarize(notarize) => notarize.view(),
168            Voter::Notarization(notarization) => notarization.view(),
169            Voter::Nullify(nullify) => nullify.view(),
170            Voter::Nullification(nullification) => nullification.view(),
171            Voter::Finalize(finalize) => finalize.view(),
172            Voter::Finalization(finalization) => finalization.view(),
173        }
174    }
175}
176
177/// Proposal represents a proposed block in the protocol.
178/// It includes the view number, the parent view, and the actual payload.
179#[derive(Clone, Debug, PartialEq, Eq, Hash)]
180pub struct Proposal<D: Digest> {
181    /// The view (round) in which this proposal is made
182    pub view: View,
183    /// The view of the parent proposal that this one builds upon
184    pub parent: View,
185    /// The actual payload/content of the proposal (typically a digest of the block data)
186    pub payload: D,
187}
188
189impl<D: Digest> Proposal<D> {
190    /// Creates a new proposal with the specified view, parent view, and payload.
191    pub fn new(view: View, parent: View, payload: D) -> Self {
192        Self {
193            view,
194            parent,
195            payload,
196        }
197    }
198}
199
200impl<D: Digest> Write for Proposal<D> {
201    fn write(&self, writer: &mut impl BufMut) {
202        UInt(self.view).write(writer);
203        UInt(self.parent).write(writer);
204        self.payload.write(writer);
205    }
206}
207
208impl<D: Digest> Read for Proposal<D> {
209    type Cfg = ();
210
211    fn read_cfg(reader: &mut impl Buf, _: &()) -> Result<Self, Error> {
212        let view = UInt::read_cfg(reader, &())?.into();
213        let parent = UInt::read_cfg(reader, &())?.into();
214        let payload = D::read_cfg(reader, &())?;
215        Ok(Self {
216            view,
217            parent,
218            payload,
219        })
220    }
221}
222
223impl<D: Digest> EncodeSize for Proposal<D> {
224    fn encode_size(&self) -> usize {
225        UInt(self.view).encode_size() + UInt(self.parent).encode_size() + self.payload.encode_size()
226    }
227}
228
229impl<D: Digest> Viewable for Proposal<D> {
230    type View = View;
231
232    fn view(&self) -> View {
233        self.view
234    }
235}
236
237/// Signature represents a validator's cryptographic signature with their identifier.
238/// This combines the validator's public key index with their actual signature.
239#[derive(Clone, Debug, PartialEq, Eq, Hash)]
240pub struct Signature<S: CSignature> {
241    /// Index of the validator's public key in the validator set
242    pub public_key: u32,
243    /// The cryptographic signature produced by the validator
244    pub signature: S,
245}
246
247impl<S: CSignature> Signature<S> {
248    /// Creates a new signature with the given public key index and signature data.
249    pub fn new(public_key: u32, signature: S) -> Self {
250        Self {
251            public_key,
252            signature,
253        }
254    }
255}
256
257impl<S: CSignature> Write for Signature<S> {
258    fn write(&self, writer: &mut impl BufMut) {
259        UInt(self.public_key).write(writer);
260        self.signature.write(writer);
261    }
262}
263
264impl<S: CSignature> Read for Signature<S> {
265    type Cfg = ();
266
267    fn read_cfg(reader: &mut impl Buf, _: &()) -> Result<Self, Error> {
268        let public_key = UInt::read(reader)?.into();
269        let signature = S::read(reader)?;
270        Ok(Self {
271            public_key,
272            signature,
273        })
274    }
275}
276
277impl<S: CSignature> EncodeSize for Signature<S> {
278    fn encode_size(&self) -> usize {
279        UInt(self.public_key).encode_size() + self.signature.encode_size()
280    }
281}
282
283impl<S: CSignature> Attributable for Signature<S> {
284    fn signer(&self) -> u32 {
285        self.public_key
286    }
287}
288
289/// Notarize represents a validator's notarize over a proposal.
290#[derive(Clone, Debug, PartialEq, Eq, Hash)]
291pub struct Notarize<S: CSignature, D: Digest> {
292    /// The proposal that is being notarized
293    pub proposal: Proposal<D>,
294    /// The validator's signature
295    pub signature: Signature<S>,
296}
297
298impl<S: CSignature, D: Digest> Notarize<S, D> {
299    /// Creates a new notarize with the given proposal and signature.
300    pub fn new(proposal: Proposal<D>, signature: Signature<S>) -> Self {
301        Self {
302            proposal,
303            signature,
304        }
305    }
306
307    /// Verifies the signature on this notarize using the provided verifier.
308    ///
309    /// This ensures that the notarize was actually produced by the claimed validator.
310    pub fn verify<K: Verifier<Signature = S>>(&self, namespace: &[u8], public_key: &K) -> bool {
311        let notarize_namespace = notarize_namespace(namespace);
312        let message = self.proposal.encode();
313        public_key.verify(
314            Some(notarize_namespace.as_ref()),
315            &message,
316            &self.signature.signature,
317        )
318    }
319
320    /// Creates a new signed notarize using the provided cryptographic scheme.
321    pub fn sign<C: Signer<Signature = S>>(
322        namespace: &[u8],
323        signer: &mut C,
324        public_key_index: u32,
325        proposal: Proposal<D>,
326    ) -> Self {
327        let notarize_namespace = notarize_namespace(namespace);
328        let message = proposal.encode();
329        let signature = signer.sign(Some(notarize_namespace.as_ref()), &message);
330        Self {
331            proposal,
332            signature: Signature::new(public_key_index, signature),
333        }
334    }
335}
336
337impl<S: CSignature, D: Digest> Write for Notarize<S, D> {
338    fn write(&self, writer: &mut impl BufMut) {
339        self.proposal.write(writer);
340        self.signature.write(writer);
341    }
342}
343
344impl<S: CSignature, D: Digest> Read for Notarize<S, D> {
345    type Cfg = ();
346
347    fn read_cfg(reader: &mut impl Buf, _: &()) -> Result<Self, Error> {
348        let proposal = Proposal::<D>::read_cfg(reader, &())?;
349        let signature = Signature::<S>::read_cfg(reader, &())?;
350        Ok(Self {
351            proposal,
352            signature,
353        })
354    }
355}
356
357impl<S: CSignature, D: Digest> EncodeSize for Notarize<S, D> {
358    fn encode_size(&self) -> usize {
359        self.proposal.encode_size() + self.signature.encode_size()
360    }
361}
362
363impl<S: CSignature, D: Digest> Viewable for Notarize<S, D> {
364    type View = View;
365
366    fn view(&self) -> View {
367        self.proposal.view()
368    }
369}
370
371impl<S: CSignature, D: Digest> Attributable for Notarize<S, D> {
372    fn signer(&self) -> u32 {
373        self.signature.signer()
374    }
375}
376
377/// Notarization represents an aggregated set of notarizes that meets the quorum threshold.
378/// It includes the proposal and the set of signatures from validators.
379#[derive(Clone, Debug, PartialEq, Eq, Hash)]
380pub struct Notarization<S: CSignature, D: Digest> {
381    /// The proposal that has been notarized
382    pub proposal: Proposal<D>,
383    /// The set of signatures from validators (must meet quorum threshold)
384    pub signatures: Vec<Signature<S>>,
385}
386
387impl<S: CSignature, D: Digest> Notarization<S, D> {
388    /// Creates a new notarization with the given proposal and set of signatures.
389    ///
390    /// # Warning
391    ///
392    /// The signatures must be sorted by the public key index.
393    pub fn new(proposal: Proposal<D>, signatures: Vec<Signature<S>>) -> Self {
394        Self {
395            proposal,
396            signatures,
397        }
398    }
399
400    /// Verifies all signatures in this notarization using the provided verifier.
401    ///
402    /// This ensures that:
403    /// 1. There are at least threshold valid signatures
404    /// 2. All signatures are valid
405    /// 3. All signers are in the validator set
406    ///
407    /// In `read_cfg`, we ensure that the signatures are sorted by public key index and are unique.
408    pub fn verify<K: Verifier<Signature = S>>(&self, namespace: &[u8], participants: &[K]) -> bool {
409        // Get allowed signers
410        let (threshold, count) = threshold(participants);
411        if self.signatures.len() < threshold as usize {
412            return false;
413        }
414        if self.signatures.len() > count as usize {
415            return false;
416        }
417
418        // Verify signatures
419        let notarize_namespace = notarize_namespace(namespace);
420        let message = self.proposal.encode();
421        for signature in &self.signatures {
422            // Get public key
423            let Some(public_key) = participants.get(signature.public_key as usize) else {
424                return false;
425            };
426
427            // Verify signature
428            if !public_key.verify(
429                Some(notarize_namespace.as_ref()),
430                &message,
431                &signature.signature,
432            ) {
433                return false;
434            }
435        }
436        true
437    }
438}
439
440impl<S: CSignature, D: Digest> Write for Notarization<S, D> {
441    fn write(&self, writer: &mut impl BufMut) {
442        self.proposal.write(writer);
443        self.signatures.write(writer);
444    }
445}
446
447impl<S: CSignature, D: Digest> Read for Notarization<S, D> {
448    type Cfg = usize;
449
450    fn read_cfg(reader: &mut impl Buf, max_len: &usize) -> Result<Self, Error> {
451        let proposal = Proposal::<D>::read(reader)?;
452        let signatures = Vec::<Signature<S>>::read_range(reader, ..=*max_len)?;
453
454        // Ensure the signatures are sorted by public key index and are unique
455        for i in 1..signatures.len() {
456            if signatures[i - 1].public_key >= signatures[i].public_key {
457                return Err(Error::Invalid(
458                    "consensus::simplex::Notarization",
459                    "Signatures are not sorted by public key index",
460                ));
461            }
462        }
463        Ok(Self {
464            proposal,
465            signatures,
466        })
467    }
468}
469
470impl<S: CSignature, D: Digest> EncodeSize for Notarization<S, D> {
471    fn encode_size(&self) -> usize {
472        self.proposal.encode_size() + self.signatures.encode_size()
473    }
474}
475
476impl<S: CSignature, D: Digest> Viewable for Notarization<S, D> {
477    type View = View;
478
479    fn view(&self) -> View {
480        self.proposal.view()
481    }
482}
483
484/// Nullify represents a validator's nullify to skip the current view.
485/// This is typically used when the leader is unresponsive or fails to propose a valid block.
486#[derive(Clone, Debug, PartialEq, Eq, Hash)]
487pub struct Nullify<S: CSignature> {
488    /// The view to be nullified (skipped)
489    pub view: View,
490    /// The validator's signature on the view
491    pub signature: Signature<S>,
492}
493
494impl<S: CSignature> Nullify<S> {
495    /// Creates a new nullify with the given view and signature.
496    pub fn new(view: View, signature: Signature<S>) -> Self {
497        Self { view, signature }
498    }
499
500    /// Verifies the signature on this nullify using the provided verifier.
501    pub fn verify<K: Verifier<Signature = S>>(&self, namespace: &[u8], public_key: &K) -> bool {
502        let nullify_namespace = nullify_namespace(namespace);
503        let message = view_message(self.view);
504        public_key.verify(
505            Some(nullify_namespace.as_ref()),
506            &message,
507            &self.signature.signature,
508        )
509    }
510
511    /// Creates a new signed nullify using the provided cryptographic scheme.
512    pub fn sign<C: Signer<Signature = S>>(
513        namespace: &[u8],
514        signer: &mut C,
515        public_key_index: u32,
516        view: View,
517    ) -> Self {
518        let nullify_namespace = nullify_namespace(namespace);
519        let message = view_message(view);
520        let signature = signer.sign(Some(nullify_namespace.as_ref()), &message);
521        Self {
522            view,
523            signature: Signature::new(public_key_index, signature),
524        }
525    }
526}
527
528impl<S: CSignature> Write for Nullify<S> {
529    fn write(&self, writer: &mut impl BufMut) {
530        UInt(self.view).write(writer);
531        self.signature.write(writer);
532    }
533}
534
535impl<S: CSignature> Read for Nullify<S> {
536    type Cfg = ();
537
538    fn read_cfg(reader: &mut impl Buf, _: &()) -> Result<Self, Error> {
539        let view = UInt::read(reader)?.into();
540        let signature = Signature::<S>::read(reader)?;
541        Ok(Self { view, signature })
542    }
543}
544
545impl<S: CSignature> EncodeSize for Nullify<S> {
546    fn encode_size(&self) -> usize {
547        UInt(self.view).encode_size() + self.signature.encode_size()
548    }
549}
550
551impl<S: CSignature> Viewable for Nullify<S> {
552    type View = View;
553
554    fn view(&self) -> View {
555        self.view
556    }
557}
558
559impl<S: CSignature> Attributable for Nullify<S> {
560    fn signer(&self) -> u32 {
561        self.signature.signer()
562    }
563}
564
565/// Nullification represents an aggregated set of nullifies that meets the quorum threshold.
566/// When a view is nullified, the consensus moves to the next view.
567#[derive(Clone, Debug, PartialEq, Eq, Hash)]
568pub struct Nullification<S: CSignature> {
569    /// The view that has been nullified
570    pub view: View,
571    /// The set of signatures from validators (must meet quorum threshold)
572    pub signatures: Vec<Signature<S>>,
573}
574
575impl<S: CSignature> Nullification<S> {
576    /// Creates a new nullification with the given view and set of signatures.
577    ///
578    /// # Warning
579    ///
580    /// The signatures must be sorted by the public key index.
581    pub fn new(view: View, signatures: Vec<Signature<S>>) -> Self {
582        Self { view, signatures }
583    }
584
585    /// Verifies all signatures in this nullification using the provided verifier.
586    ///
587    /// Similar to Notarization::verify, ensures quorum of valid signatures from validators.
588    pub fn verify<K: Verifier<Signature = S>>(&self, namespace: &[u8], participants: &[K]) -> bool {
589        // Get allowed signers
590        let (threshold, count) = threshold(participants);
591        if self.signatures.len() < threshold as usize {
592            return false;
593        }
594        if self.signatures.len() > count as usize {
595            return false;
596        }
597
598        // Verify signatures
599        let nullify_namespace = nullify_namespace(namespace);
600        let message = view_message(self.view);
601        for signature in &self.signatures {
602            // Get public key
603            let Some(public_key) = participants.get(signature.public_key as usize) else {
604                return false;
605            };
606
607            // Verify signature
608            if !public_key.verify(
609                Some(nullify_namespace.as_ref()),
610                &message,
611                &signature.signature,
612            ) {
613                return false;
614            }
615        }
616        true
617    }
618}
619
620impl<S: CSignature> Write for Nullification<S> {
621    fn write(&self, writer: &mut impl BufMut) {
622        UInt(self.view).write(writer);
623        self.signatures.write(writer);
624    }
625}
626
627impl<S: CSignature> Read for Nullification<S> {
628    type Cfg = usize;
629
630    fn read_cfg(reader: &mut impl Buf, max_len: &usize) -> Result<Self, Error> {
631        let view = UInt::read(reader)?.into();
632        let signatures = Vec::<Signature<S>>::read_range(reader, ..=*max_len)?;
633
634        // Ensure the signatures are sorted by public key index and are unique
635        for i in 1..signatures.len() {
636            if signatures[i - 1].public_key >= signatures[i].public_key {
637                return Err(Error::Invalid(
638                    "consensus::simplex::Nullification",
639                    "Signatures are not sorted by public key index",
640                ));
641            }
642        }
643        Ok(Self { view, signatures })
644    }
645}
646
647impl<S: CSignature> EncodeSize for Nullification<S> {
648    fn encode_size(&self) -> usize {
649        UInt(self.view).encode_size() + self.signatures.encode_size()
650    }
651}
652
653impl<S: CSignature> Viewable for Nullification<S> {
654    type View = View;
655
656    fn view(&self) -> View {
657        self.view
658    }
659}
660
661/// Finalize represents a validator's finalize over a proposal.
662/// This happens after a proposal has been notarized, confirming it as the canonical block
663/// for this view.
664#[derive(Clone, Debug, PartialEq, Eq, Hash)]
665pub struct Finalize<S: CSignature, D: Digest> {
666    /// The proposal to be finalized
667    pub proposal: Proposal<D>,
668    /// The validator's signature on the proposal
669    pub signature: Signature<S>,
670}
671
672impl<S: CSignature, D: Digest> Finalize<S, D> {
673    /// Creates a new finalize with the given proposal and signature.
674    pub fn new(proposal: Proposal<D>, signature: Signature<S>) -> Self {
675        Self {
676            proposal,
677            signature,
678        }
679    }
680
681    /// Verifies the signature on this finalize using the provided verifier.
682    pub fn verify<K: Verifier<Signature = S>>(&self, namespace: &[u8], public_key: &K) -> bool {
683        let finalize_namespace = finalize_namespace(namespace);
684        let message = self.proposal.encode();
685        public_key.verify(
686            Some(finalize_namespace.as_ref()),
687            &message,
688            &self.signature.signature,
689        )
690    }
691
692    /// Creates a new signed finalize using the provided cryptographic scheme.
693    pub fn sign<C: Signer<Signature = S>>(
694        namespace: &[u8],
695        signer: &mut C,
696        public_key_index: u32,
697        proposal: Proposal<D>,
698    ) -> Self {
699        let finalize_namespace = finalize_namespace(namespace);
700        let message = proposal.encode();
701        let signature = signer.sign(Some(finalize_namespace.as_ref()), &message);
702        Self {
703            proposal,
704            signature: Signature::new(public_key_index, signature),
705        }
706    }
707}
708
709impl<S: CSignature, D: Digest> Write for Finalize<S, D> {
710    fn write(&self, writer: &mut impl BufMut) {
711        self.proposal.write(writer);
712        self.signature.write(writer);
713    }
714}
715
716impl<S: CSignature, D: Digest> Read for Finalize<S, D> {
717    type Cfg = ();
718
719    fn read_cfg(reader: &mut impl Buf, _: &()) -> Result<Self, Error> {
720        let proposal = Proposal::<D>::read(reader)?;
721        let signature = Signature::<S>::read(reader)?;
722        Ok(Self {
723            proposal,
724            signature,
725        })
726    }
727}
728
729impl<S: CSignature, D: Digest> EncodeSize for Finalize<S, D> {
730    fn encode_size(&self) -> usize {
731        self.proposal.encode_size() + self.signature.encode_size()
732    }
733}
734
735impl<S: CSignature, D: Digest> Viewable for Finalize<S, D> {
736    type View = View;
737
738    fn view(&self) -> View {
739        self.proposal.view()
740    }
741}
742
743impl<S: CSignature, D: Digest> Attributable for Finalize<S, D> {
744    fn signer(&self) -> u32 {
745        self.signature.signer()
746    }
747}
748
749/// Finalization represents an aggregated set of finalizes that meets the quorum threshold.
750/// When a proposal is finalized, it becomes the canonical block for its view.
751#[derive(Clone, Debug, PartialEq, Eq, Hash)]
752pub struct Finalization<S: CSignature, D: Digest> {
753    /// The proposal that has been finalized
754    pub proposal: Proposal<D>,
755    /// The set of signatures from validators (must meet quorum threshold)
756    pub signatures: Vec<Signature<S>>,
757}
758
759impl<S: CSignature, D: Digest> Finalization<S, D> {
760    /// Creates a new finalization with the given proposal and set of signatures.
761    ///
762    /// # Warning
763    ///
764    /// The signatures must be sorted by the public key index.
765    pub fn new(proposal: Proposal<D>, signatures: Vec<Signature<S>>) -> Self {
766        Self {
767            proposal,
768            signatures,
769        }
770    }
771
772    /// Verifies all signatures in this finalization using the provided verifier.
773    ///
774    /// Similar to Notarization::verify, ensures quorum of valid signatures from validators.
775    pub fn verify<V: Verifier<Signature = S>>(&self, namespace: &[u8], participants: &[V]) -> bool {
776        // Get allowed signers
777        let (threshold, count) = threshold(participants);
778        if self.signatures.len() < threshold as usize {
779            return false;
780        }
781        if self.signatures.len() > count as usize {
782            return false;
783        }
784
785        // Verify signatures
786        let finalize_namespace = finalize_namespace(namespace);
787        let message = self.proposal.encode();
788        for signature in &self.signatures {
789            // Get public key
790            let Some(public_key) = participants.get(signature.public_key as usize) else {
791                return false;
792            };
793
794            // Verify signature
795            if !public_key.verify(
796                Some(finalize_namespace.as_ref()),
797                &message,
798                &signature.signature,
799            ) {
800                return false;
801            }
802        }
803        true
804    }
805}
806
807impl<S: CSignature, D: Digest> Write for Finalization<S, D> {
808    fn write(&self, writer: &mut impl BufMut) {
809        self.proposal.write(writer);
810        self.signatures.write(writer);
811    }
812}
813
814impl<S: CSignature, D: Digest> Read for Finalization<S, D> {
815    type Cfg = usize;
816
817    fn read_cfg(reader: &mut impl Buf, max_len: &usize) -> Result<Self, Error> {
818        let proposal = Proposal::<D>::read(reader)?;
819        let signatures = Vec::<Signature<S>>::read_range(reader, ..=*max_len)?;
820
821        // Ensure the signatures are sorted by public key index and are unique
822        for i in 1..signatures.len() {
823            if signatures[i - 1].public_key >= signatures[i].public_key {
824                return Err(Error::Invalid(
825                    "consensus::simplex::Finalization",
826                    "Signatures are not sorted by public key index",
827                ));
828            }
829        }
830        Ok(Self {
831            proposal,
832            signatures,
833        })
834    }
835}
836
837impl<S: CSignature, D: Digest> EncodeSize for Finalization<S, D> {
838    fn encode_size(&self) -> usize {
839        self.proposal.encode_size() + self.signatures.encode_size()
840    }
841}
842
843impl<S: CSignature, D: Digest> Viewable for Finalization<S, D> {
844    type View = View;
845
846    fn view(&self) -> View {
847        self.proposal.view()
848    }
849}
850
851/// Backfiller is a message type for requesting and receiving missing consensus artifacts.
852/// This is used to synchronize validators that have fallen behind or just joined the network.
853#[derive(Clone, Debug, PartialEq)]
854pub enum Backfiller<S: CSignature, D: Digest> {
855    /// Request for missing notarizations and nullifications
856    Request(Request),
857    /// Response containing requested notarizations and nullifications
858    Response(Response<S, D>),
859}
860
861impl<S: CSignature, D: Digest> Write for Backfiller<S, D> {
862    fn write(&self, writer: &mut impl BufMut) {
863        match self {
864            Backfiller::Request(request) => {
865                0u8.write(writer);
866                request.write(writer);
867            }
868            Backfiller::Response(response) => {
869                1u8.write(writer);
870                response.write(writer);
871            }
872        }
873    }
874}
875
876impl<S: CSignature, D: Digest> Read for Backfiller<S, D> {
877    type Cfg = (usize, usize);
878
879    fn read_cfg(reader: &mut impl Buf, cfg: &(usize, usize)) -> Result<Self, Error> {
880        let tag = u8::read(reader)?;
881        match tag {
882            0 => Ok(Backfiller::Request(Request::read_cfg(reader, &cfg.0)?)),
883            1 => Ok(Backfiller::Response(Response::<S, D>::read_cfg(
884                reader, cfg,
885            )?)),
886            _ => Err(Error::Invalid(
887                "consensus::simplex::Backfiller",
888                "Invalid type",
889            )),
890        }
891    }
892}
893
894impl<S: CSignature, D: Digest> EncodeSize for Backfiller<S, D> {
895    fn encode_size(&self) -> usize {
896        1 + match self {
897            Backfiller::Request(request) => request.encode_size(),
898            Backfiller::Response(response) => response.encode_size(),
899        }
900    }
901}
902
903/// Request is a message to request missing notarizations and nullifications.
904/// This is used by validators who need to catch up with the consensus state.
905#[derive(Clone, Debug, PartialEq)]
906pub struct Request {
907    /// Unique identifier for this request (used to match responses)
908    pub id: u64,
909    /// Views for which notarizations are requested
910    pub notarizations: Vec<View>,
911    /// Views for which nullifications are requested
912    pub nullifications: Vec<View>,
913}
914
915impl Request {
916    /// Creates a new request for missing notarizations and nullifications.
917    pub fn new(id: u64, notarizations: Vec<View>, nullifications: Vec<View>) -> Self {
918        Self {
919            id,
920            notarizations,
921            nullifications,
922        }
923    }
924}
925
926impl Write for Request {
927    fn write(&self, writer: &mut impl BufMut) {
928        UInt(self.id).write(writer);
929        self.notarizations.write(writer);
930        self.nullifications.write(writer);
931    }
932}
933
934impl Read for Request {
935    type Cfg = usize;
936
937    fn read_cfg(reader: &mut impl Buf, max_len: &usize) -> Result<Self, Error> {
938        let id = UInt::read(reader)?.into();
939        let notarizations = Vec::<View>::read_range(reader, ..=*max_len)?;
940        let remaining = max_len - notarizations.len();
941        let nullifications = Vec::<View>::read_range(reader, ..=remaining)?;
942        Ok(Self {
943            id,
944            notarizations,
945            nullifications,
946        })
947    }
948}
949
950impl EncodeSize for Request {
951    fn encode_size(&self) -> usize {
952        UInt(self.id).encode_size()
953            + self.notarizations.encode_size()
954            + self.nullifications.encode_size()
955    }
956}
957
958/// Response is a message containing the requested notarizations and nullifications.
959/// This is sent in response to a Request message.
960#[derive(Clone, Debug, PartialEq)]
961pub struct Response<S: CSignature, D: Digest> {
962    /// Identifier matching the original request
963    pub id: u64,
964    /// Notarizations for the requested views
965    pub notarizations: Vec<Notarization<S, D>>,
966    /// Nullifications for the requested views
967    pub nullifications: Vec<Nullification<S>>,
968}
969
970impl<S: CSignature, D: Digest> Response<S, D> {
971    /// Creates a new response with the given id, notarizations, and nullifications.
972    pub fn new(
973        id: u64,
974        notarizations: Vec<Notarization<S, D>>,
975        nullifications: Vec<Nullification<S>>,
976    ) -> Self {
977        Self {
978            id,
979            notarizations,
980            nullifications,
981        }
982    }
983}
984
985impl<S: CSignature, D: Digest> Write for Response<S, D> {
986    fn write(&self, writer: &mut impl BufMut) {
987        UInt(self.id).write(writer);
988        self.notarizations.write(writer);
989        self.nullifications.write(writer);
990    }
991}
992
993impl<S: CSignature, D: Digest> Read for Response<S, D> {
994    type Cfg = (usize, usize);
995
996    fn read_cfg(reader: &mut impl Buf, (total, max_sigs): &(usize, usize)) -> Result<Self, Error> {
997        let id = UInt::read(reader)?.into();
998        let notarizations =
999            Vec::<Notarization<S, D>>::read_cfg(reader, &((..=total).into(), *max_sigs))?;
1000        let rem = total - notarizations.len();
1001        let nullifications =
1002            Vec::<Nullification<S>>::read_cfg(reader, &((..=rem).into(), *max_sigs))?;
1003        Ok(Self {
1004            id,
1005            notarizations,
1006            nullifications,
1007        })
1008    }
1009}
1010
1011impl<S: CSignature, D: Digest> EncodeSize for Response<S, D> {
1012    fn encode_size(&self) -> usize {
1013        UInt(self.id).encode_size()
1014            + self.notarizations.encode_size()
1015            + self.nullifications.encode_size()
1016    }
1017}
1018
1019/// Activity represents all possible activities that can occur in the consensus protocol.
1020/// This includes both regular consensus messages and fault evidence.
1021#[derive(Clone, Debug, PartialEq, Hash, Eq)]
1022pub enum Activity<S: CSignature, D: Digest> {
1023    /// A single notarize over a proposal
1024    Notarize(Notarize<S, D>),
1025    /// An aggregated set of validator notarizes that meets quorum
1026    Notarization(Notarization<S, D>),
1027    /// A single validator nullify to skip the current view
1028    Nullify(Nullify<S>),
1029    /// An aggregated set of validator nullifies that meets quorum
1030    Nullification(Nullification<S>),
1031    /// A single validator finalize over a proposal
1032    Finalize(Finalize<S, D>),
1033    /// An aggregated set of validator finalizes that meets quorum
1034    Finalization(Finalization<S, D>),
1035    /// Evidence of a validator sending conflicting notarizes (Byzantine behavior)
1036    ConflictingNotarize(ConflictingNotarize<S, D>),
1037    /// Evidence of a validator sending conflicting finalizes (Byzantine behavior)
1038    ConflictingFinalize(ConflictingFinalize<S, D>),
1039    /// Evidence of a validator sending both nullify and finalize for the same view (Byzantine behavior)
1040    NullifyFinalize(NullifyFinalize<S, D>),
1041}
1042
1043impl<S: CSignature, D: Digest> Write for Activity<S, D> {
1044    fn write(&self, writer: &mut impl BufMut) {
1045        match self {
1046            Activity::Notarize(notarize) => {
1047                0u8.write(writer);
1048                notarize.write(writer);
1049            }
1050            Activity::Notarization(notarization) => {
1051                1u8.write(writer);
1052                notarization.write(writer);
1053            }
1054            Activity::Nullify(nullify) => {
1055                2u8.write(writer);
1056                nullify.write(writer);
1057            }
1058            Activity::Nullification(nullification) => {
1059                3u8.write(writer);
1060                nullification.write(writer);
1061            }
1062            Activity::Finalize(finalize) => {
1063                4u8.write(writer);
1064                finalize.write(writer);
1065            }
1066            Activity::Finalization(finalization) => {
1067                5u8.write(writer);
1068                finalization.write(writer);
1069            }
1070            Activity::ConflictingNotarize(conflicting_notarize) => {
1071                6u8.write(writer);
1072                conflicting_notarize.write(writer);
1073            }
1074            Activity::ConflictingFinalize(conflicting_finalize) => {
1075                7u8.write(writer);
1076                conflicting_finalize.write(writer);
1077            }
1078            Activity::NullifyFinalize(nullify_finalize) => {
1079                8u8.write(writer);
1080                nullify_finalize.write(writer);
1081            }
1082        }
1083    }
1084}
1085
1086impl<S: CSignature, D: Digest> Read for Activity<S, D> {
1087    type Cfg = usize;
1088
1089    fn read_cfg(reader: &mut impl Buf, max_len: &usize) -> Result<Self, Error> {
1090        let tag = u8::read(reader)?;
1091        match tag {
1092            0 => Ok(Activity::Notarize(Notarize::<S, D>::read(reader)?)),
1093            1 => Ok(Activity::Notarization(Notarization::<S, D>::read_cfg(
1094                reader, max_len,
1095            )?)),
1096            2 => Ok(Activity::Nullify(Nullify::<S>::read(reader)?)),
1097            3 => Ok(Activity::Nullification(Nullification::<S>::read_cfg(
1098                reader, max_len,
1099            )?)),
1100            4 => Ok(Activity::Finalize(Finalize::<S, D>::read(reader)?)),
1101            5 => Ok(Activity::Finalization(Finalization::<S, D>::read_cfg(
1102                reader, max_len,
1103            )?)),
1104            6 => Ok(Activity::ConflictingNotarize(
1105                ConflictingNotarize::<S, D>::read(reader)?,
1106            )),
1107            7 => Ok(Activity::ConflictingFinalize(
1108                ConflictingFinalize::<S, D>::read(reader)?,
1109            )),
1110            8 => Ok(Activity::NullifyFinalize(NullifyFinalize::<S, D>::read(
1111                reader,
1112            )?)),
1113            _ => Err(Error::Invalid(
1114                "consensus::simplex::Activity",
1115                "Invalid type",
1116            )),
1117        }
1118    }
1119}
1120
1121impl<S: CSignature, D: Digest> EncodeSize for Activity<S, D> {
1122    fn encode_size(&self) -> usize {
1123        1 + match self {
1124            Activity::Notarize(notarize) => notarize.encode_size(),
1125            Activity::Notarization(notarization) => notarization.encode_size(),
1126            Activity::Nullify(nullify) => nullify.encode_size(),
1127            Activity::Nullification(nullification) => nullification.encode_size(),
1128            Activity::Finalize(finalize) => finalize.encode_size(),
1129            Activity::Finalization(finalization) => finalization.encode_size(),
1130            Activity::ConflictingNotarize(conflicting_notarize) => {
1131                conflicting_notarize.encode_size()
1132            }
1133            Activity::ConflictingFinalize(conflicting_finalize) => {
1134                conflicting_finalize.encode_size()
1135            }
1136            Activity::NullifyFinalize(nullify_finalize) => nullify_finalize.encode_size(),
1137        }
1138    }
1139}
1140
1141impl<S: CSignature, D: Digest> Viewable for Activity<S, D> {
1142    type View = View;
1143
1144    fn view(&self) -> View {
1145        match self {
1146            Activity::Notarize(notarize) => notarize.view(),
1147            Activity::Notarization(notarization) => notarization.view(),
1148            Activity::Nullify(nullify) => nullify.view(),
1149            Activity::Nullification(nullification) => nullification.view(),
1150            Activity::Finalize(finalize) => finalize.view(),
1151            Activity::Finalization(finalization) => finalization.view(),
1152            Activity::ConflictingNotarize(conflicting_notarize) => conflicting_notarize.view(),
1153            Activity::ConflictingFinalize(conflicting_finalize) => conflicting_finalize.view(),
1154            Activity::NullifyFinalize(nullify_finalize) => nullify_finalize.view(),
1155        }
1156    }
1157}
1158
1159/// ConflictingNotarize represents evidence of a Byzantine validator sending conflicting notarizes.
1160/// This is used to prove that a validator has equivocated (voted for different proposals in the same view).
1161#[derive(Clone, Debug, PartialEq, Hash, Eq)]
1162pub struct ConflictingNotarize<S: CSignature, D: Digest> {
1163    /// The view in which the conflict occurred
1164    pub view: View,
1165    /// The parent view of the first conflicting proposal
1166    pub parent_1: View,
1167    /// The payload of the first conflicting proposal
1168    pub payload_1: D,
1169    /// The signature on the first conflicting proposal
1170    pub signature_1: Signature<S>,
1171    /// The parent view of the second conflicting proposal
1172    pub parent_2: View,
1173    /// The payload of the second conflicting proposal
1174    pub payload_2: D,
1175    /// The signature on the second conflicting proposal
1176    pub signature_2: Signature<S>,
1177}
1178
1179impl<S: CSignature, D: Digest> ConflictingNotarize<S, D> {
1180    /// Creates a new conflicting notarize evidence from two conflicting notarizes.
1181    pub fn new(notarize_1: Notarize<S, D>, notarize_2: Notarize<S, D>) -> Self {
1182        assert_eq!(notarize_1.view(), notarize_2.view());
1183        assert_eq!(notarize_1.signer(), notarize_2.signer());
1184        Self {
1185            view: notarize_1.view(),
1186            parent_1: notarize_1.proposal.parent,
1187            payload_1: notarize_1.proposal.payload,
1188            signature_1: notarize_1.signature,
1189            parent_2: notarize_2.proposal.parent,
1190            payload_2: notarize_2.proposal.payload,
1191            signature_2: notarize_2.signature,
1192        }
1193    }
1194
1195    /// Reconstructs the original notarizes from this evidence.
1196    pub fn notarizes(&self) -> (Notarize<S, D>, Notarize<S, D>) {
1197        (
1198            Notarize::new(
1199                Proposal::new(self.view, self.parent_1, self.payload_1),
1200                self.signature_1.clone(),
1201            ),
1202            Notarize::new(
1203                Proposal::new(self.view, self.parent_2, self.payload_2),
1204                self.signature_2.clone(),
1205            ),
1206        )
1207    }
1208
1209    /// Verifies that both conflicting signatures are valid, proving Byzantine behavior.
1210    pub fn verify<V: Verifier<Signature = S>>(&self, namespace: &[u8], public_key: &V) -> bool {
1211        let (notarize_1, notarize_2) = self.notarizes();
1212        notarize_1.verify(namespace, public_key) && notarize_2.verify(namespace, public_key)
1213    }
1214}
1215
1216impl<S: CSignature, D: Digest> Write for ConflictingNotarize<S, D> {
1217    fn write(&self, writer: &mut impl BufMut) {
1218        UInt(self.view).write(writer);
1219        UInt(self.parent_1).write(writer);
1220        self.payload_1.write(writer);
1221        self.signature_1.write(writer);
1222        UInt(self.parent_2).write(writer);
1223        self.payload_2.write(writer);
1224        self.signature_2.write(writer);
1225    }
1226}
1227
1228impl<S: CSignature, D: Digest> Read for ConflictingNotarize<S, D> {
1229    type Cfg = ();
1230
1231    fn read_cfg(reader: &mut impl Buf, _: &()) -> Result<Self, Error> {
1232        let view = UInt::read(reader)?.into();
1233        let parent_1 = UInt::read(reader)?.into();
1234        let payload_1 = D::read_cfg(reader, &())?;
1235        let signature_1 = Signature::<S>::read(reader)?;
1236        let parent_2 = UInt::read(reader)?.into();
1237        let payload_2 = D::read_cfg(reader, &())?;
1238        let signature_2 = Signature::<S>::read(reader)?;
1239        if signature_1.signer() != signature_2.signer() {
1240            return Err(Error::Invalid(
1241                "consensus::simplex::ConflictingNotarize",
1242                "notarizes must have the same public key",
1243            ));
1244        }
1245        Ok(Self {
1246            view,
1247            parent_1,
1248            payload_1,
1249            signature_1,
1250            parent_2,
1251            payload_2,
1252            signature_2,
1253        })
1254    }
1255}
1256
1257impl<S: CSignature, D: Digest> EncodeSize for ConflictingNotarize<S, D> {
1258    fn encode_size(&self) -> usize {
1259        UInt(self.view).encode_size()
1260            + UInt(self.parent_1).encode_size()
1261            + self.payload_1.encode_size()
1262            + self.signature_1.encode_size()
1263            + UInt(self.parent_2).encode_size()
1264            + self.payload_2.encode_size()
1265            + self.signature_2.encode_size()
1266    }
1267}
1268
1269impl<S: CSignature, D: Digest> Viewable for ConflictingNotarize<S, D> {
1270    type View = View;
1271
1272    fn view(&self) -> View {
1273        self.view
1274    }
1275}
1276
1277impl<S: CSignature, D: Digest> Attributable for ConflictingNotarize<S, D> {
1278    fn signer(&self) -> u32 {
1279        self.signature_1.signer()
1280    }
1281}
1282
1283/// ConflictingFinalize represents evidence of a Byzantine validator sending conflicting finalizes.
1284/// Similar to ConflictingNotarize, but for finalizes.
1285#[derive(Clone, Debug, PartialEq, Hash, Eq)]
1286pub struct ConflictingFinalize<S: CSignature, D: Digest> {
1287    /// The view in which the conflict occurred
1288    pub view: View,
1289    /// The parent view of the first conflicting proposal
1290    pub parent_1: View,
1291    /// The payload of the first conflicting proposal
1292    pub payload_1: D,
1293    /// The signature on the first conflicting proposal
1294    pub signature_1: Signature<S>,
1295    /// The parent view of the second conflicting proposal
1296    pub parent_2: View,
1297    /// The payload of the second conflicting proposal
1298    pub payload_2: D,
1299    /// The signature on the second conflicting proposal
1300    pub signature_2: Signature<S>,
1301}
1302
1303impl<S: CSignature, D: Digest> ConflictingFinalize<S, D> {
1304    /// Creates a new conflicting finalize evidence from two conflicting finalizes.
1305    pub fn new(finalize_1: Finalize<S, D>, finalize_2: Finalize<S, D>) -> Self {
1306        assert_eq!(finalize_1.view(), finalize_2.view());
1307        assert_eq!(finalize_1.signer(), finalize_2.signer());
1308        Self {
1309            view: finalize_1.view(),
1310            parent_1: finalize_1.proposal.parent,
1311            payload_1: finalize_1.proposal.payload,
1312            signature_1: finalize_1.signature,
1313            parent_2: finalize_2.proposal.parent,
1314            payload_2: finalize_2.proposal.payload,
1315            signature_2: finalize_2.signature,
1316        }
1317    }
1318
1319    /// Reconstructs the original finalize from this evidence.
1320    pub fn finalizes(&self) -> (Finalize<S, D>, Finalize<S, D>) {
1321        (
1322            Finalize::new(
1323                Proposal::new(self.view, self.parent_1, self.payload_1),
1324                self.signature_1.clone(),
1325            ),
1326            Finalize::new(
1327                Proposal::new(self.view, self.parent_2, self.payload_2),
1328                self.signature_2.clone(),
1329            ),
1330        )
1331    }
1332
1333    /// Verifies that both conflicting signatures are valid, proving Byzantine behavior.
1334    pub fn verify<V: Verifier<Signature = S>>(&self, namespace: &[u8], public_key: &V) -> bool {
1335        let (finalize_1, finalize_2) = self.finalizes();
1336        finalize_1.verify(namespace, public_key) && finalize_2.verify(namespace, public_key)
1337    }
1338}
1339
1340impl<S: CSignature, D: Digest> Write for ConflictingFinalize<S, D> {
1341    fn write(&self, writer: &mut impl BufMut) {
1342        UInt(self.view).write(writer);
1343        UInt(self.parent_1).write(writer);
1344        self.payload_1.write(writer);
1345        self.signature_1.write(writer);
1346        UInt(self.parent_2).write(writer);
1347        self.payload_2.write(writer);
1348        self.signature_2.write(writer);
1349    }
1350}
1351
1352impl<S: CSignature, D: Digest> Read for ConflictingFinalize<S, D> {
1353    type Cfg = ();
1354
1355    fn read_cfg(reader: &mut impl Buf, _: &()) -> Result<Self, Error> {
1356        let view = UInt::read(reader)?.into();
1357        let parent_1 = UInt::read(reader)?.into();
1358        let payload_1 = D::read_cfg(reader, &())?;
1359        let signature_1 = Signature::<S>::read(reader)?;
1360        let parent_2 = UInt::read(reader)?.into();
1361        let payload_2 = D::read_cfg(reader, &())?;
1362        let signature_2 = Signature::<S>::read(reader)?;
1363        if signature_1.signer() != signature_2.signer() {
1364            return Err(Error::Invalid(
1365                "consensus::simplex::ConflictingFinalize",
1366                "finalizes must have the same public key",
1367            ));
1368        }
1369        Ok(Self {
1370            view,
1371            parent_1,
1372            payload_1,
1373            signature_1,
1374            parent_2,
1375            payload_2,
1376            signature_2,
1377        })
1378    }
1379}
1380
1381impl<S: CSignature, D: Digest> EncodeSize for ConflictingFinalize<S, D> {
1382    fn encode_size(&self) -> usize {
1383        UInt(self.view).encode_size()
1384            + UInt(self.parent_1).encode_size()
1385            + self.payload_1.encode_size()
1386            + self.signature_1.encode_size()
1387            + UInt(self.parent_2).encode_size()
1388            + self.payload_2.encode_size()
1389            + self.signature_2.encode_size()
1390    }
1391}
1392
1393impl<S: CSignature, D: Digest> Viewable for ConflictingFinalize<S, D> {
1394    type View = View;
1395
1396    fn view(&self) -> View {
1397        self.view
1398    }
1399}
1400
1401impl<S: CSignature, D: Digest> Attributable for ConflictingFinalize<S, D> {
1402    fn signer(&self) -> u32 {
1403        self.signature_1.signer()
1404    }
1405}
1406
1407/// NullifyFinalize represents evidence of a Byzantine validator sending both a nullify and finalize
1408/// for the same view, which is contradictory behavior (a validator should either try to skip a view OR
1409/// finalize a proposal, not both).
1410#[derive(Clone, Debug, PartialEq, Hash, Eq)]
1411pub struct NullifyFinalize<S: CSignature, D: Digest> {
1412    /// The proposal that the validator tried to finalize
1413    pub proposal: Proposal<D>,
1414    /// The signature on the nullify
1415    pub view_signature: Signature<S>,
1416    /// The signature on the finalize
1417    pub finalize_signature: Signature<S>,
1418}
1419
1420impl<S: CSignature, D: Digest> NullifyFinalize<S, D> {
1421    /// Creates a new nullify-finalize evidence from a nullify and a finalize.
1422    pub fn new(nullify: Nullify<S>, finalize: Finalize<S, D>) -> Self {
1423        assert_eq!(nullify.view(), finalize.view());
1424        assert_eq!(nullify.signer(), finalize.signer());
1425        Self {
1426            proposal: finalize.proposal,
1427            view_signature: nullify.signature,
1428            finalize_signature: finalize.signature,
1429        }
1430    }
1431
1432    /// Verifies that both the nullify and finalize signatures are valid, proving Byzantine behavior.
1433    pub fn verify<V: Verifier<Signature = S>>(&self, namespace: &[u8], public_key: &V) -> bool {
1434        let nullify = Nullify::new(self.proposal.view(), self.view_signature.clone());
1435        let finalize = Finalize::new(self.proposal.clone(), self.finalize_signature.clone());
1436        nullify.verify(namespace, public_key) && finalize.verify(namespace, public_key)
1437    }
1438}
1439
1440impl<S: CSignature, D: Digest> Write for NullifyFinalize<S, D> {
1441    fn write(&self, writer: &mut impl BufMut) {
1442        self.proposal.write(writer);
1443        self.view_signature.write(writer);
1444        self.finalize_signature.write(writer);
1445    }
1446}
1447
1448impl<S: CSignature, D: Digest> Read for NullifyFinalize<S, D> {
1449    type Cfg = ();
1450
1451    fn read_cfg(reader: &mut impl Buf, _: &()) -> Result<Self, Error> {
1452        let proposal = Proposal::<D>::read(reader)?;
1453        let view_signature = Signature::<S>::read(reader)?;
1454        let finalize_signature = Signature::<S>::read(reader)?;
1455        if view_signature.signer() != finalize_signature.signer() {
1456            return Err(Error::Invalid(
1457                "consensus::simplex::NullifyFinalize",
1458                "nullification and finalization must have the same public key",
1459            ));
1460        }
1461        Ok(Self {
1462            proposal,
1463            view_signature,
1464            finalize_signature,
1465        })
1466    }
1467}
1468
1469impl<S: CSignature, D: Digest> EncodeSize for NullifyFinalize<S, D> {
1470    fn encode_size(&self) -> usize {
1471        self.proposal.encode_size()
1472            + self.view_signature.encode_size()
1473            + self.finalize_signature.encode_size()
1474    }
1475}
1476
1477impl<S: CSignature, D: Digest> Viewable for NullifyFinalize<S, D> {
1478    type View = View;
1479
1480    fn view(&self) -> View {
1481        self.proposal.view()
1482    }
1483}
1484
1485impl<S: CSignature, D: Digest> Attributable for NullifyFinalize<S, D> {
1486    fn signer(&self) -> u32 {
1487        self.view_signature.signer()
1488    }
1489}
1490
1491#[cfg(test)]
1492mod tests {
1493    use super::*;
1494    use commonware_codec::{Decode, DecodeExt, Encode};
1495    use commonware_cryptography::{
1496        ed25519::{PrivateKey, PublicKey, Signature},
1497        sha256::Digest as Sha256Digest,
1498        PrivateKeyExt as _,
1499    };
1500
1501    const NAMESPACE: &[u8] = b"test";
1502
1503    // Helper function to create a sample digest
1504    fn sample_digest(v: u8) -> Sha256Digest {
1505        Sha256Digest::from([v; 32]) // Simple fixed digest for testing
1506    }
1507
1508    fn sample_scheme(v: u64) -> PrivateKey {
1509        PrivateKey::from_seed(v)
1510    }
1511
1512    #[test]
1513    fn test_proposal_encode_decode() {
1514        let proposal = Proposal::new(10, 5, sample_digest(1));
1515        let encoded = proposal.encode();
1516        let decoded = Proposal::<Sha256Digest>::decode(encoded).unwrap();
1517        assert_eq!(proposal, decoded);
1518    }
1519
1520    #[test]
1521    fn test_notarize_encode_decode() {
1522        let mut scheme = sample_scheme(0);
1523        let proposal = Proposal::new(10, 5, sample_digest(1));
1524        let notarize = Notarize::sign(NAMESPACE, &mut scheme, 0, proposal);
1525        let encoded = notarize.encode();
1526        let decoded = Notarize::<Signature, Sha256Digest>::decode(encoded).unwrap();
1527        assert_eq!(notarize, decoded);
1528        assert!(decoded.verify::<PublicKey>(NAMESPACE, &scheme.public_key()));
1529    }
1530
1531    #[test]
1532    fn test_notarization_encode_decode() {
1533        let mut scheme_1 = sample_scheme(0);
1534        let mut scheme_2 = sample_scheme(1);
1535        let proposal = Proposal::new(10, 5, sample_digest(1));
1536        let notarize_1 = Notarize::sign(NAMESPACE, &mut scheme_1, 0, proposal.clone());
1537        let notarize_2 = Notarize::sign(NAMESPACE, &mut scheme_2, 1, proposal.clone());
1538        let signatures = vec![notarize_1.signature.clone(), notarize_2.signature.clone()];
1539        let notarization = Notarization::new(proposal.clone(), signatures.clone());
1540        let encoded = notarization.encode();
1541        let decoded =
1542            Notarization::<Signature, Sha256Digest>::decode_cfg(encoded, &usize::MAX).unwrap();
1543        assert_eq!(notarization, decoded);
1544        assert!(
1545            decoded.verify::<PublicKey>(NAMESPACE, &[scheme_1.public_key(), scheme_2.public_key()])
1546        );
1547    }
1548
1549    #[test]
1550    fn test_nullify_encode_decode() {
1551        let mut scheme = sample_scheme(0);
1552        let nullify = Nullify::sign(NAMESPACE, &mut scheme, 0, 10);
1553        let encoded = nullify.encode();
1554        let decoded = Nullify::<Signature>::decode(encoded).unwrap();
1555        assert_eq!(nullify, decoded);
1556        assert!(decoded.verify::<PublicKey>(NAMESPACE, &scheme.public_key()));
1557    }
1558
1559    #[test]
1560    fn test_nullification_encode_decode() {
1561        let mut scheme_1 = sample_scheme(0);
1562        let mut scheme_2 = sample_scheme(1);
1563        let nullify_1 = Nullify::sign(NAMESPACE, &mut scheme_1, 0, 10);
1564        let nullify_2 = Nullify::sign(NAMESPACE, &mut scheme_2, 1, 10);
1565        let signatures = vec![nullify_1.signature.clone(), nullify_2.signature.clone()];
1566        let nullification = Nullification::new(10, signatures.clone());
1567        let encoded = nullification.encode();
1568        let decoded = Nullification::<Signature>::decode_cfg(encoded, &usize::MAX).unwrap();
1569        assert_eq!(nullification, decoded);
1570        assert!(
1571            decoded.verify::<PublicKey>(NAMESPACE, &[scheme_1.public_key(), scheme_2.public_key()])
1572        );
1573    }
1574
1575    #[test]
1576    fn test_finalize_encode_decode() {
1577        let mut scheme = sample_scheme(0);
1578        let proposal = Proposal::new(10, 5, sample_digest(1));
1579        let finalize = Finalize::sign(NAMESPACE, &mut scheme, 0, proposal);
1580        let encoded = finalize.encode();
1581        let decoded = Finalize::<Signature, Sha256Digest>::decode(encoded).unwrap();
1582        assert_eq!(finalize, decoded);
1583    }
1584
1585    #[test]
1586    fn test_finalization_encode_decode() {
1587        let mut scheme_1 = sample_scheme(0);
1588        let mut scheme_2 = sample_scheme(1);
1589        let proposal = Proposal::new(10, 5, sample_digest(1));
1590        let finalize_1 = Finalize::sign(NAMESPACE, &mut scheme_1, 0, proposal.clone());
1591        let finalize_2 = Finalize::sign(NAMESPACE, &mut scheme_2, 1, proposal.clone());
1592        let signatures = vec![finalize_1.signature.clone(), finalize_2.signature.clone()];
1593        let finalization = Finalization::new(proposal.clone(), signatures.clone());
1594        let encoded = finalization.encode();
1595        let decoded =
1596            Finalization::<Signature, Sha256Digest>::decode_cfg(encoded, &usize::MAX).unwrap();
1597        assert_eq!(finalization, decoded);
1598        assert!(
1599            decoded.verify::<PublicKey>(NAMESPACE, &[scheme_1.public_key(), scheme_2.public_key()])
1600        );
1601    }
1602
1603    #[test]
1604    fn test_backfiller_encode_decode() {
1605        let request = Request::new(1, vec![10, 11], vec![12, 13]);
1606        let backfiller = Backfiller::Request::<Signature, Sha256Digest>(request.clone());
1607        let encoded = backfiller.encode();
1608        let decoded =
1609            Backfiller::<Signature, Sha256Digest>::decode_cfg(encoded, &(usize::MAX, usize::MAX))
1610                .unwrap();
1611        assert!(matches!(decoded, Backfiller::Request(r) if r == request));
1612    }
1613
1614    #[test]
1615    fn test_request_encode_decode() {
1616        let request = Request::new(1, vec![10, 11], vec![12, 13]);
1617        let encoded = request.encode();
1618        let decoded = Request::decode_cfg(encoded, &usize::MAX).unwrap();
1619        assert_eq!(request, decoded);
1620    }
1621
1622    #[test]
1623    fn test_response_encode_decode() {
1624        let mut scheme = sample_scheme(0);
1625        let proposal = Proposal::new(10, 5, sample_digest(1));
1626        let notarize = Notarize::sign(NAMESPACE, &mut scheme, 0, proposal.clone());
1627        let notarization = Notarization::new(proposal.clone(), vec![notarize.signature.clone()]);
1628        let response = Response::new(1, vec![notarization], vec![]);
1629        let encoded = response.encode();
1630        let decoded =
1631            Response::<Signature, Sha256Digest>::decode_cfg(encoded, &(usize::MAX, usize::MAX))
1632                .unwrap();
1633        assert_eq!(response, decoded);
1634    }
1635
1636    #[test]
1637    fn test_conflicting_notarize_encode_decode() {
1638        let mut scheme = sample_scheme(0);
1639        let proposal1 = Proposal::new(10, 5, sample_digest(1));
1640        let proposal2 = Proposal::new(10, 6, sample_digest(2));
1641        let notarize1 = Notarize::sign(NAMESPACE, &mut scheme, 0, proposal1.clone());
1642        let notarize2 = Notarize::sign(NAMESPACE, &mut scheme, 0, proposal2.clone());
1643        let conflicting = ConflictingNotarize::new(notarize1, notarize2);
1644        let encoded = conflicting.encode();
1645        let decoded = ConflictingNotarize::<Signature, Sha256Digest>::decode(encoded).unwrap();
1646        assert_eq!(conflicting, decoded);
1647        assert!(conflicting.verify::<PublicKey>(NAMESPACE, &scheme.public_key()));
1648    }
1649
1650    #[test]
1651    fn test_conflicting_finalize_encode_decode() {
1652        let mut scheme = sample_scheme(0);
1653        let proposal1 = Proposal::new(10, 5, sample_digest(1));
1654        let proposal2 = Proposal::new(10, 6, sample_digest(2));
1655        let finalize1 = Finalize::sign(NAMESPACE, &mut scheme, 0, proposal1.clone());
1656        let finalize2 = Finalize::sign(NAMESPACE, &mut scheme, 0, proposal2.clone());
1657        let conflicting = ConflictingFinalize::new(finalize1, finalize2);
1658        let encoded = conflicting.encode();
1659        let decoded = ConflictingFinalize::<Signature, Sha256Digest>::decode(encoded).unwrap();
1660        assert_eq!(conflicting, decoded);
1661        assert!(conflicting.verify::<PublicKey>(NAMESPACE, &scheme.public_key()));
1662    }
1663
1664    #[test]
1665    fn test_nullify_finalize_encode_decode() {
1666        let mut scheme = sample_scheme(0);
1667        let proposal = Proposal::new(10, 5, sample_digest(1));
1668        let nullify = Nullify::sign(NAMESPACE, &mut scheme, 1, 10);
1669        let finalize = Finalize::sign(NAMESPACE, &mut scheme, 1, proposal.clone());
1670        let nullify_finalize = NullifyFinalize::new(nullify, finalize);
1671        let encoded = nullify_finalize.encode();
1672        let decoded = NullifyFinalize::<Signature, Sha256Digest>::decode(encoded).unwrap();
1673        assert_eq!(nullify_finalize, decoded);
1674        assert!(nullify_finalize.verify::<PublicKey>(NAMESPACE, &scheme.public_key()));
1675    }
1676
1677    #[test]
1678    fn test_notarize_verify_wrong_namespace() {
1679        let mut scheme = sample_scheme(0);
1680        let proposal = Proposal::new(10, 5, sample_digest(1));
1681        let notarize = Notarize::sign(NAMESPACE, &mut scheme, 0, proposal);
1682
1683        // Verify with wrong namespace - should fail
1684        assert!(!notarize.verify::<PublicKey>(b"wrong_namespace", &scheme.public_key()));
1685    }
1686
1687    #[test]
1688    fn test_notarize_verify_wrong_public_key() {
1689        let mut scheme1 = sample_scheme(0);
1690        let scheme2 = sample_scheme(1); // Different key
1691        let proposal = Proposal::new(10, 5, sample_digest(1));
1692        let notarize = Notarize::sign(NAMESPACE, &mut scheme1, 0, proposal);
1693
1694        // Verify with wrong public key - should fail
1695        assert!(!notarize.verify::<PublicKey>(NAMESPACE, &scheme2.public_key()));
1696    }
1697
1698    #[test]
1699    fn test_notarization_verify_insufficient_signatures() {
1700        let mut scheme_1 = sample_scheme(0);
1701        let mut scheme_2 = sample_scheme(1);
1702        let proposal = Proposal::new(10, 5, sample_digest(1));
1703        let notarize_1 = Notarize::sign(NAMESPACE, &mut scheme_1, 0, proposal.clone());
1704        let notarize_2 = Notarize::sign(NAMESPACE, &mut scheme_2, 1, proposal.clone());
1705
1706        // Create a notarization with only 2 signatures
1707        let signatures = vec![notarize_1.signature.clone(), notarize_2.signature.clone()];
1708        let notarization = Notarization::new(proposal.clone(), signatures);
1709
1710        // Create a validator set of 4, which needs 3 signatures for quorum
1711        let validators = vec![
1712            scheme_1.public_key(),
1713            scheme_2.public_key(),
1714            sample_scheme(2).public_key(),
1715            sample_scheme(3).public_key(),
1716        ];
1717
1718        // Should fail because we only have 2 signatures but need 3 for quorum
1719        assert!(!notarization.verify::<PublicKey>(NAMESPACE, &validators));
1720    }
1721
1722    #[test]
1723    fn test_notarization_verify_invalid_validator_index() {
1724        let mut scheme_1 = sample_scheme(0);
1725        let scheme_2 = sample_scheme(1);
1726        let proposal = Proposal::new(10, 5, sample_digest(1));
1727
1728        // Create notarize with invalid public key index (3, which is out of bounds)
1729        let notarize_1 = Notarize::sign(NAMESPACE, &mut scheme_1, 0, proposal.clone());
1730        let invalid_sig =
1731            super::Signature::new(3, scheme_2.sign(Some(NAMESPACE), &proposal.encode()));
1732
1733        // Create a notarization with an invalid signature (refers to index 3, but there are only 2 validators)
1734        let signatures = vec![notarize_1.signature.clone(), invalid_sig];
1735        let notarization = Notarization::new(proposal.clone(), signatures);
1736
1737        // Create a validator set of 2
1738        let validators = vec![scheme_1.public_key(), scheme_2.public_key()];
1739
1740        // Should fail because the second signature refers to an invalid validator index
1741        assert!(!notarization.verify::<PublicKey>(NAMESPACE, &validators));
1742    }
1743
1744    #[test]
1745    fn test_conflicting_notarize_detection() {
1746        let mut scheme = sample_scheme(0);
1747
1748        // Create two different proposals for the same view
1749        let proposal1 = Proposal::new(10, 5, sample_digest(1));
1750        let proposal2 = Proposal::new(10, 6, sample_digest(2)); // Different parent
1751
1752        // Create notarizes for both proposals from the same validator
1753        let notarize1 = Notarize::sign(NAMESPACE, &mut scheme, 0, proposal1.clone());
1754        let notarize2 = Notarize::sign(NAMESPACE, &mut scheme, 0, proposal2.clone());
1755
1756        // Create conflict evidence
1757        let conflict = ConflictingNotarize::new(notarize1, notarize2);
1758
1759        // Verify the evidence is valid - both signatures should be valid
1760        assert!(conflict.verify::<PublicKey>(NAMESPACE, &scheme.public_key()));
1761
1762        // Now create invalid evidence
1763        let mut scheme2 = sample_scheme(1);
1764        let invalid_notarize = Notarize::sign(NAMESPACE, &mut scheme2, 1, proposal1.clone());
1765
1766        // This will compile but should fail verification since the signatures are from different validators
1767        let (_, n2) = conflict.notarizes();
1768        let invalid_conflict = ConflictingNotarize {
1769            view: n2.view(),
1770            parent_1: n2.proposal.parent,
1771            payload_1: n2.proposal.payload,
1772            signature_1: n2.signature,
1773            parent_2: invalid_notarize.proposal.parent,
1774            payload_2: invalid_notarize.proposal.payload,
1775            signature_2: invalid_notarize.signature,
1776        };
1777
1778        // Verify should fail with either key because the signatures are from different validators
1779        assert!(!invalid_conflict.verify::<PublicKey>(NAMESPACE, &scheme.public_key()));
1780        assert!(!invalid_conflict.verify::<PublicKey>(NAMESPACE, &scheme2.public_key()));
1781    }
1782
1783    #[test]
1784    fn test_nullify_finalize_detection() {
1785        let mut scheme = sample_scheme(0);
1786        let view = 10;
1787
1788        // Create a nullify for view 10
1789        let nullify = Nullify::sign(NAMESPACE, &mut scheme, 0, view);
1790
1791        // Create a finalize for the same view
1792        let proposal = Proposal::new(view, 5, sample_digest(1));
1793        let finalize = Finalize::sign(NAMESPACE, &mut scheme, 0, proposal.clone());
1794
1795        // Create nullify+finalize evidence
1796        let conflict = NullifyFinalize::new(nullify, finalize);
1797
1798        // Verify the evidence is valid
1799        assert!(conflict.verify::<PublicKey>(NAMESPACE, &scheme.public_key()));
1800
1801        // Now create invalid evidence with different validators
1802        let mut scheme2 = sample_scheme(1);
1803        let nullify2 = Nullify::sign(NAMESPACE, &mut scheme2, 1, view);
1804        let finalize2 = Finalize::sign(NAMESPACE, &mut scheme2, 1, proposal);
1805
1806        // This will compile but verification with wrong key should fail
1807        let conflict2 = NullifyFinalize::new(nullify2, finalize2);
1808        assert!(!conflict2.verify::<PublicKey>(NAMESPACE, &scheme.public_key()));
1809        // Wrong key
1810    }
1811
1812    #[test]
1813    fn test_nullification_invalid_signatures() {
1814        let mut scheme_1 = sample_scheme(0);
1815        let mut scheme_2 = sample_scheme(1);
1816
1817        // Create nullify for view 10
1818        let nullify_1 = Nullify::sign(NAMESPACE, &mut scheme_1, 0, 10);
1819        let nullify_2 = Nullify::sign(NAMESPACE, &mut scheme_2, 1, 10);
1820
1821        // Create a nullification with valid signatures
1822        let signatures = vec![nullify_1.signature.clone(), nullify_2.signature.clone()];
1823        let nullification = Nullification::new(10, signatures);
1824
1825        // Create a validator set of 2
1826        let validators = vec![scheme_1.public_key(), scheme_2.public_key()];
1827
1828        // Valid verification
1829        assert!(nullification.verify::<PublicKey>(NAMESPACE, &validators));
1830
1831        // Create a nullification with tampered signature
1832        let tampered_sig =
1833            super::Signature::new(2, scheme_1.sign(Some(NAMESPACE), &nullify_1.encode()));
1834
1835        let invalid_signatures = vec![nullify_1.signature.clone(), tampered_sig];
1836        let invalid_nullification = Nullification::new(10, invalid_signatures);
1837
1838        // Verification should fail with tampered signature
1839        assert!(!invalid_nullification.verify::<PublicKey>(NAMESPACE, &validators));
1840    }
1841}
commonware_consensus/simplex/types.rs

commonware_consensus/simplex/
types.rs
