core_cbc_casper/
justification.rs

1// Core CBC Casper
2// Copyright (C) 2018 - 2020  Coordination Technology Ltd.
3// Authors: pZ4 <pz4@protonmail.ch>,
4//          Lederstrumpf,
5//          h4sh3d <h4sh3d@truelevel.io>
6//          roflolilolmao <q@truelevel.ch>
7//
8// This file is part of Core CBC Casper.
9//
10// Core CBC Casper is free software: you can redistribute it and/or modify it under the terms
11// of the GNU Affero General Public License as published by the Free Software Foundation, either
12// version 3 of the License, or (at your option) any later version.
13//
14// Core CBC Casper is distributed in the hope that it will be useful, but WITHOUT ANY
15// WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
16// PURPOSE. See the GNU Affero General Public License for more details.
17//
18// You should have received a copy of the GNU Affero General Public License along with the Core CBC
19// Rust Library. If not, see <https://www.gnu.org/licenses/>.
20
21use std::collections::{HashMap, HashSet, VecDeque};
22use std::fmt::{Debug, Formatter};
23
24use rayon::iter::IntoParallelRefIterator;
25
26use crate::estimator::Estimator;
27use crate::message::Message;
28use crate::util::weight::{WeightUnit, Zero};
29use crate::validator;
30
31/// This struct holds the set of the [`Message`] that justify
32/// the current message. It works like a `Vec`.
33///
34/// # Example
35///
36/// Using the [`VoteCount`] type message type for brevity's sake.
37///
38/// ```
39/// use core_cbc_casper::justification::Justification;
40/// use core_cbc_casper::message::Message;
41/// use core_cbc_casper::VoteCount;
42///
43/// let message = VoteCount::create_vote_message(0, true);
44///
45/// let mut justification = Justification::empty();
46///
47/// justification.insert(message.clone());
48///
49/// assert_eq!(
50///     *justification.iter().next().unwrap().estimate(),
51///     VoteCount { yes: 1, no: 0 },
52/// );
53/// ```
54///
55/// [`Message`]: ../message/struct.Message.html
56/// [`VoteCount`]: ../struct.VoteCount.html
57#[derive(Eq, PartialEq, Clone, Hash)]
58pub struct Justification<E: Estimator>(Vec<Message<E>>);
59
60impl<E: Estimator> Justification<E> {
61    /// Creates an empty justification.
62    pub fn empty() -> Self {
63        Justification(Vec::new())
64    }
65
66    /// Creates and returns a new justification from a vector of
67    /// [`Message`] and mutates the given [`validator::State`]
68    /// with the updated state.
69    ///
70    /// [`Message`]: ../message/struct.Message.html
71    /// [`validator::State`]: ../validator/struct.State.html
72    pub fn from_messages<U: WeightUnit>(
73        messages: Vec<Message<E>>,
74        state: &mut validator::State<E, U>,
75    ) -> Self {
76        let mut justification = Justification::empty();
77        let messages: HashSet<_> = messages.iter().collect();
78        justification.faulty_inserts(&messages, state);
79        justification
80    }
81
82    pub fn iter(&self) -> std::slice::Iter<Message<E>> {
83        self.0.iter()
84    }
85
86    pub fn par_iter(&self) -> rayon::slice::Iter<Message<E>> {
87        self.0.par_iter()
88    }
89
90    pub fn contains(&self, message: &Message<E>) -> bool {
91        self.0.contains(message)
92    }
93
94    pub fn len(&self) -> usize {
95        self.0.len()
96    }
97
98    pub fn is_empty(&self) -> bool {
99        self.0.is_empty()
100    }
101
102    /// This function checks if the [`message`] is already contained into the underlying `Vec`. If it
103    /// is, it does nothing and returns false. Else, it will push the message in the `Vec` and
104    /// returns true.
105    ///
106    /// [`message`]: ../message/struct.Message.html
107    pub fn insert(&mut self, message: Message<E>) -> bool {
108        if self.contains(&message) {
109            false
110        } else {
111            self.0.push(message);
112            true
113        }
114    }
115
116    /// Runs the [`estimator`] on the justification given the set of equivocators and [`validators'
117    /// weights`].
118    ///
119    /// [`estimator`]: ../estimator/trait.Estimator.html
120    /// [`validators' weights`]: ../validator/struct.Weights.html
121    pub fn make_estimate<U: WeightUnit>(
122        &self,
123        equivocators: &HashSet<E::ValidatorName>,
124        validators_weights: &validator::Weights<E::ValidatorName, U>,
125    ) -> Result<E, E::Error> {
126        let latest_messages = LatestMessages::from(self);
127        let latest_messages_honest =
128            LatestMessagesHonest::from_latest_messages(&latest_messages, equivocators);
129        Estimator::estimate(&latest_messages_honest, validators_weights)
130    }
131
132    /// Inserts [`messages`] to the justification, accepting up to the threshold faults by weight.
133    /// In ordering to insert as much messages as possible, the input messages are sorted
134    /// ascendingly by their [`validators' weight`].
135    /// Returns a `HashSet` of messages that got successfully included in the justification.
136    ///
137    /// [`messages`]: ../message/struct.Message.html
138    /// [`validators' weight`]: ../validator/struct.Weights.html
139    pub fn faulty_inserts<'a, U: WeightUnit>(
140        &mut self,
141        messages: &HashSet<&'a Message<E>>,
142        state: &mut validator::State<E, U>,
143    ) -> HashSet<&'a Message<E>> {
144        let messages = state.sort_by_faultweight(messages);
145        // do the actual insertions to the state
146        messages
147            .into_iter()
148            .filter(|message| self.faulty_insert(message, state))
149            .collect()
150    }
151
152    /// This function makes no assumption on how to treat the equivocator. It adds the message to
153    /// the justification only if it will not cross the fault tolerance threshold.
154    pub fn faulty_insert<U: WeightUnit>(
155        &mut self,
156        message: &Message<E>,
157        state: &mut validator::State<E, U>,
158    ) -> bool {
159        let is_equivocation = state.latest_messages.equivocate(message);
160
161        let sender = message.sender();
162        let validator_weight = state
163            .validators_weights
164            .weight(sender)
165            .unwrap_or(U::INFINITY);
166
167        let already_in_equivocators = state.equivocators.contains(sender);
168
169        match (is_equivocation, already_in_equivocators) {
170            // if it's already equivocating and listed as such, or not equivocating at all, an
171            // insertion can be done without more checks
172            (false, _) | (true, true) => {
173                let success = self.insert(message.clone());
174                if success {
175                    state.latest_messages.update(message);
176                }
177                success
178            }
179            // in the other case, we have to check that the threshold is not reached
180            (true, false) => {
181                if validator_weight + state.state_fault_weight <= state.thr {
182                    let success = self.insert(message.clone());
183                    if success {
184                        state.latest_messages.update(message);
185                        if state.equivocators.insert(sender.clone()) {
186                            state.state_fault_weight += validator_weight;
187                        }
188                    }
189                    success
190                } else {
191                    false
192                }
193            }
194        }
195    }
196
197    /// This function sets the weight of an equivocator to zero right away (returned in
198    /// [`validator::State`]) and add his message to the state, since his weight is null and doesn't
199    /// count to the state fault weight anymore.
200    ///
201    /// [`validator::State`]: ../validator/struct.State.html
202    pub fn faulty_insert_with_slash<'a, U: WeightUnit>(
203        &mut self,
204        message: &Message<E>,
205        state: &'a mut validator::State<E, U>,
206    ) -> Result<bool, validator::Error<'a, HashMap<E::ValidatorName, U>>> {
207        let is_equivocation = state.latest_messages.equivocate(message);
208        if is_equivocation {
209            let sender = message.sender();
210            state.equivocators.insert(sender.clone());
211            state
212                .validators_weights
213                .insert(sender.clone(), <U as Zero<U>>::ZERO)?;
214        }
215        state.latest_messages.update(message);
216        let success = self.insert(message.clone());
217        Ok(success)
218    }
219}
220
221impl<E: Estimator> From<LatestMessagesHonest<E>> for Justification<E> {
222    fn from(lmh: LatestMessagesHonest<E>) -> Self {
223        let mut justification = Self::empty();
224        for message in lmh.iter() {
225            justification.insert(message.clone());
226        }
227        justification
228    }
229}
230
231impl<E: Estimator> Debug for Justification<E> {
232    fn fmt(&self, f: &mut Formatter) -> ::std::fmt::Result {
233        write!(f, "{:?}", self.0)
234    }
235}
236
237/// LatestMessages is a map between [`validators`] and their latests [`messages`]. Latest messages from a
238/// validator are all their messages that are not in the dependency of another of their messages.
239///
240/// # Example
241///
242/// Using the [`VoteCount`] type message type for brevity's sake.
243///
244/// ```
245/// use core_cbc_casper::justification::{Justification, LatestMessages};
246/// use core_cbc_casper::message::Message;
247/// use core_cbc_casper::VoteCount;
248///
249/// use std::collections::HashSet;
250/// use std::iter::FromIterator;
251///
252/// let mut justification = Justification::empty();
253///
254/// let message_0 = Message::new(0, justification.clone(), VoteCount { yes: 1, no: 0 });
255/// justification.insert(message_0.clone());
256/// assert_eq!(
257///     *LatestMessages::from(&justification).get(&0).unwrap(),
258///     HashSet::from_iter(vec![message_0]),
259/// );
260///
261/// // message_1 will replace message_0 in the LatestMessages.
262/// let message_1 = Message::new(0, justification.clone(), VoteCount { yes: 2, no: 0 });
263/// justification.insert(message_1.clone());
264/// assert_eq!(
265///     *LatestMessages::from(&justification).get(&0).unwrap(),
266///     HashSet::from_iter(vec![message_1]),
267/// );
268///
269/// // Equivocating messages will all be contained in the LatestMessages as they're not contained
270/// // in the justification of other messages.
271/// let message_2 = Message::new(0, justification.clone(), VoteCount { yes: 3, no: 0 });
272/// let message_3 = Message::new(0, justification.clone(), VoteCount { yes: 2, no: 1 });
273/// justification.insert(message_2.clone());
274/// justification.insert(message_3.clone());
275/// assert_eq!(
276///     *LatestMessages::from(&justification).get(&0).unwrap(),
277///     HashSet::from_iter(vec![message_2, message_3]),
278/// );
279/// ```
280///
281/// [`VoteCount`]: ../struct.VoteCount.html
282/// [`validators`]: ../validator/trait.ValidatorName.html
283/// [`messages`]: ../message/struct.Message.html
284#[derive(Eq, PartialEq, Clone, Debug)]
285pub struct LatestMessages<E: Estimator>(HashMap<E::ValidatorName, HashSet<Message<E>>>);
286
287impl<E: Estimator> LatestMessages<E> {
288    /// Create an empty set of latest messages.
289    pub fn empty() -> Self {
290        LatestMessages(HashMap::new())
291    }
292
293    /// Insert a new set of messages for a validator.
294    pub fn insert(
295        &mut self,
296        validator: E::ValidatorName,
297        messages: HashSet<Message<E>>,
298    ) -> Option<HashSet<Message<E>>> {
299        self.0.insert(validator, messages)
300    }
301
302    /// Checks whether a sender is already contained in the map.
303    pub fn contains_key(&self, validator: &E::ValidatorName) -> bool {
304        self.0.contains_key(validator)
305    }
306
307    /// Get a set of messages sent by the validator.
308    pub fn get(&self, validator: &E::ValidatorName) -> Option<&HashSet<Message<E>>> {
309        self.0.get(validator)
310    }
311
312    /// Get a mutable set of messages sent by the validator.
313    pub fn get_mut(
314        &mut self,
315        validator: &<E as Estimator>::ValidatorName,
316    ) -> Option<&mut HashSet<Message<E>>> {
317        self.0.get_mut(validator)
318    }
319
320    /// Get an iterator over the map.
321    pub fn iter(&self) -> std::collections::hash_map::Iter<E::ValidatorName, HashSet<Message<E>>> {
322        self.0.iter()
323    }
324
325    /// Get the map size.
326    pub fn len(&self) -> usize {
327        self.0.len()
328    }
329
330    pub fn is_empty(&self) -> bool {
331        self.0.is_empty()
332    }
333
334    /// Get the map keys, i.e. the validators.
335    pub fn keys(&self) -> std::collections::hash_map::Keys<E::ValidatorName, HashSet<Message<E>>> {
336        self.0.keys()
337    }
338
339    /// Get the map values, i.e. the messages.
340    pub fn values(
341        &self,
342    ) -> std::collections::hash_map::Values<E::ValidatorName, HashSet<Message<E>>> {
343        self.0.values()
344    }
345
346    /// Updates the data structure by adding a new message. Returns true if the new message is a
347    /// valid latest message, i.e. the first message of a validator or a message that is not in the
348    /// [`justification`] of the existing latest messages.
349    ///
350    /// [`justification`]: ../justification/struct.Justification.html
351    pub fn update(&mut self, new_message: &Message<E>) -> bool {
352        let sender = new_message.sender();
353        if let Some(latest_messages_from_sender) = self.get(sender).cloned() {
354            latest_messages_from_sender
355                .iter()
356                .filter(|&old_message| new_message != old_message)
357                .fold(false, |acc, old_message| {
358                    let new_independent_from_old = !new_message.depends(old_message);
359                    // equivocation, old and new do not depend on each other
360                    if new_independent_from_old && !old_message.depends(new_message) {
361                        self.get_mut(sender)
362                            .map(|messages| messages.insert(new_message.clone()))
363                            .unwrap_or(false)
364                            || acc
365                    }
366                    // new actually older than old
367                    else if new_independent_from_old {
368                        acc
369                    }
370                    // new newer than old
371                    else {
372                        self.get_mut(sender)
373                            .map(|messages| {
374                                messages.remove(old_message) && messages.insert(new_message.clone())
375                            })
376                            .unwrap_or(false)
377                            || acc
378                    }
379                })
380        } else {
381            // no message found for this validator, so new_message is the latest
382            self.insert(
383                sender.clone(),
384                [new_message.clone()].iter().cloned().collect(),
385            );
386            true
387        }
388    }
389
390    /// Checks whether the new message equivocates with any of the latest messages.
391    pub(crate) fn equivocate(&self, message_new: &Message<E>) -> bool {
392        self.get(message_new.sender())
393            .map(|latest_messages| {
394                latest_messages
395                    .iter()
396                    .any(|message| message.equivocates(&message_new))
397            })
398            .unwrap_or(false)
399    }
400}
401
402impl<E: Estimator> From<&Justification<E>> for LatestMessages<E> {
403    /// Extracts the latest messages of each validator from a [`justification`].
404    ///
405    /// [`justification`]: ../justification/struct.Justification.html
406    fn from(justification: &Justification<E>) -> Self {
407        let mut latest_messages: LatestMessages<E> = LatestMessages::empty();
408        let mut queue: VecDeque<Message<E>> = justification.iter().cloned().collect();
409        while let Some(message) = queue.pop_front() {
410            if latest_messages.update(&message) {
411                message
412                    .justification()
413                    .iter()
414                    .for_each(|message| queue.push_back(message.clone()));
415            }
416        }
417        latest_messages
418    }
419}
420
421/// Set of latest honest [`messages`] for each [`validator`]. Works like [`LatestMessages`] but ignores
422/// equivocations.
423///
424/// # Example
425///
426/// Using the [`VoteCount`] type message type for brevity's sake.
427///
428/// ```
429/// use core_cbc_casper::justification::{Justification, LatestMessages, LatestMessagesHonest};
430/// use core_cbc_casper::message::Message;
431/// use core_cbc_casper::VoteCount;
432///
433/// use std::collections::HashSet;
434/// use std::iter::FromIterator;
435///
436/// let mut justification = Justification::empty();
437///
438/// let message_0 = Message::new(0, justification.clone(), VoteCount { yes: 1, no: 0 });
439/// justification.insert(message_0.clone());
440/// assert_eq!(
441///     HashSet::<&Message<_>>::from_iter(LatestMessagesHonest::from_latest_messages(
442///         &LatestMessages::from(&justification),
443///         &HashSet::new(),
444///     ).iter()),
445///     HashSet::from_iter(vec![&message_0]),
446/// );
447///
448/// // message_1 will replace message_0 in the LatestMessagesHonest.
449/// let message_1 = Message::new(0, justification.clone(), VoteCount { yes: 2, no: 0 });
450/// justification.insert(message_1.clone());
451/// assert_eq!(
452///     HashSet::<&Message<_>>::from_iter(LatestMessagesHonest::from_latest_messages(
453///         &LatestMessages::from(&justification),
454///         &HashSet::new(),
455///     ).iter()),
456///     HashSet::from_iter(vec![&message_1]),
457/// );
458///
459/// // As the validator is no longer honest, his messages are ignored.
460/// let message_2 = Message::new(0, justification.clone(), VoteCount { yes: 3, no: 0 });
461/// let message_3 = Message::new(0, justification.clone(), VoteCount { yes: 2, no: 1 });
462/// justification.insert(message_2.clone());
463/// justification.insert(message_3.clone());
464/// assert_eq!(
465///     HashSet::<&Message<_>>::from_iter(LatestMessagesHonest::from_latest_messages(
466///         &LatestMessages::from(&justification),
467///         &HashSet::new(),
468///     ).iter()),
469///     HashSet::from_iter(vec![]),
470/// );
471/// ```
472///
473/// [`messages`]: ../message/struct.Message.html
474/// [`validator`]: ../validator/trait.ValidatorName.html
475/// [`LatestMessages`]: struct.LatestMessages.html
476/// [`VoteCount`]: ../struct.VoteCount.html
477#[derive(Clone)]
478pub struct LatestMessagesHonest<E: Estimator>(HashSet<Message<E>>);
479
480impl<E: Estimator> LatestMessagesHonest<E> {
481    /// Create an empty latest honest messages set.
482    fn empty() -> Self {
483        LatestMessagesHonest(HashSet::new())
484    }
485
486    /// Inserts a message in the set.
487    fn insert(&mut self, message: Message<E>) -> bool {
488        self.0.insert(message)
489    }
490
491    /// Removes the messages from a validator.
492    pub fn remove(&mut self, validator: &E::ValidatorName) {
493        self.0.retain(|message| message.sender() != validator);
494    }
495
496    /// Filters the latest messages to retrieve the latest honest messages and remove equivocators.
497    pub fn from_latest_messages(
498        latest_messages: &LatestMessages<E>,
499        equivocators: &HashSet<E::ValidatorName>,
500    ) -> Self {
501        latest_messages
502            .iter()
503            .filter_map(|(validator, messages)| {
504                if equivocators.contains(validator) || messages.len() != 1 {
505                    None
506                } else {
507                    messages.iter().next()
508                }
509            })
510            .fold(LatestMessagesHonest::empty(), |mut acc, message| {
511                acc.insert(message.clone());
512                acc
513            })
514    }
515
516    pub fn iter(&self) -> std::collections::hash_set::Iter<Message<E>> {
517        self.0.iter()
518    }
519
520    pub fn len(&self) -> usize {
521        self.0.len()
522    }
523
524    pub fn is_empty(&self) -> bool {
525        self.0.is_empty()
526    }
527
528    pub fn make_estimate<U: WeightUnit>(
529        &self,
530        validators_weights: &validator::Weights<E::ValidatorName, U>,
531    ) -> Result<E, E::Error> {
532        E::estimate(&self, validators_weights)
533    }
534}
535
536#[cfg(test)]
537mod test {
538    use crate::{IntegerWrapper, VoteCount};
539
540    use std::collections::HashSet;
541    use std::iter::FromIterator;
542
543    use crate::justification::{Justification, LatestMessages};
544    use crate::message::Message;
545    use crate::validator;
546
547    #[test]
548    fn faulty_insert_sorted() {
549        let v0 = VoteCount::create_vote_message(0, false);
550        let v0_prime = VoteCount::create_vote_message(0, true);
551        let v1 = VoteCount::create_vote_message(1, true);
552        let v1_prime = VoteCount::create_vote_message(1, false);
553        let v2 = VoteCount::create_vote_message(2, true);
554        let v2_prime = VoteCount::create_vote_message(2, false);
555
556        let mut latest_messages = LatestMessages::empty();
557        latest_messages.update(&v0);
558        latest_messages.update(&v1);
559        latest_messages.update(&v2);
560
561        let mut validator_state = validator::State::new(
562            validator::Weights::new(vec![(0, 1.0), (1, 2.0), (2, 3.0)].into_iter().collect()),
563            0.0,
564            latest_messages,
565            3.0,
566            HashSet::new(),
567        );
568        let mut justification = Justification::empty();
569        let sorted_messages = validator_state
570            .sort_by_faultweight(&vec![&v2_prime, &v1_prime, &v0_prime].into_iter().collect());
571
572        sorted_messages.iter().for_each(|&message| {
573            justification.faulty_insert(message, &mut validator_state);
574        });
575
576        assert_eq!(
577            HashSet::<&Message<VoteCount>>::from_iter(justification.iter()),
578            HashSet::from_iter(vec![&v0_prime, &v1_prime])
579        );
580        float_eq!(validator_state.fault_weight(), 3.0);
581        assert_eq!(
582            *validator_state.latests_messages().get(&0).unwrap(),
583            HashSet::from_iter(vec![v0, v0_prime]),
584        );
585        assert_eq!(
586            *validator_state.latests_messages().get(&1).unwrap(),
587            HashSet::from_iter(vec![v1, v1_prime]),
588        );
589        assert_eq!(
590            *validator_state.latests_messages().get(&2).unwrap(),
591            HashSet::from_iter(vec![v2]),
592        );
593    }
594
595    #[test]
596    fn faulty_inserts() {
597        let v0 = VoteCount::create_vote_message(0, false);
598        let v0_prime = VoteCount::create_vote_message(0, true);
599        let v1 = VoteCount::create_vote_message(1, true);
600        let v1_prime = VoteCount::create_vote_message(1, false);
601        let v2 = VoteCount::create_vote_message(2, true);
602        let v2_prime = VoteCount::create_vote_message(2, false);
603
604        let mut latest_messages = LatestMessages::empty();
605        latest_messages.update(&v0);
606        latest_messages.update(&v1);
607        latest_messages.update(&v2);
608
609        let mut validator_state = validator::State::new(
610            validator::Weights::new(vec![(0, 1.0), (1, 2.0), (2, 3.0)].into_iter().collect()),
611            0.0,
612            latest_messages,
613            3.0,
614            HashSet::new(),
615        );
616        let mut justification = Justification::empty();
617        justification.faulty_inserts(
618            &vec![&v2_prime, &v1_prime, &v0_prime].into_iter().collect(),
619            &mut validator_state,
620        );
621
622        assert_eq!(
623            HashSet::<&Message<VoteCount>>::from_iter(justification.iter()),
624            HashSet::from_iter(vec![&v0_prime, &v1_prime])
625        );
626        float_eq!(validator_state.fault_weight(), 3.0);
627        assert_eq!(
628            *validator_state.latests_messages().get(&0).unwrap(),
629            HashSet::from_iter(vec![v0, v0_prime]),
630        );
631        assert_eq!(
632            *validator_state.latests_messages().get(&1).unwrap(),
633            HashSet::from_iter(vec![v1, v1_prime]),
634        );
635        assert_eq!(
636            *validator_state.latests_messages().get(&2).unwrap(),
637            HashSet::from_iter(vec![v2]),
638        );
639    }
640
641    fn faulty_insert_setup() -> (Message<VoteCount>, validator::State<VoteCount, f32>) {
642        let mut validator_state = validator::State::new(
643            validator::Weights::new(vec![(0, 1.0), (1, 1.0)].into_iter().collect()),
644            0.0,
645            LatestMessages::empty(),
646            0.0,
647            HashSet::new(),
648        );
649
650        let v0 = VoteCount::create_vote_message(0, false);
651        let v0_prime = VoteCount::create_vote_message(0, true); // equivocating vote
652        let v1 = VoteCount::create_vote_message(1, true);
653
654        let mut validator_state_clone = validator_state.clone();
655        validator_state_clone.update(&[&v0]);
656        let m0 = Message::from_validator_state(0, &validator_state_clone).unwrap();
657
658        validator_state.update(&[&v1, &m0, &v0_prime]);
659
660        (v0_prime, validator_state)
661    }
662
663    #[test]
664    fn faulty_insert_accept_fault() {
665        let (v0_prime, validator_state) = faulty_insert_setup();
666
667        let mut state = validator::State::new_with_default_state(
668            validator_state,
669            None,
670            None,
671            None,
672            Some(1.0),
673            None,
674        );
675        let mut justification = Justification::empty();
676        let success = justification.faulty_insert(&v0_prime, &mut state);
677
678        assert!(
679            success,
680            "$v0_prime$ conflicts with $v0$ through $m0$, but we should accept this fault as it \
681             doesnt cross the fault threshold for the set"
682        );
683        assert_eq!(justification.len(), 1);
684        assert!(justification.contains(&v0_prime));
685        assert!(state
686            .latests_messages()
687            .get(&0)
688            .unwrap()
689            .contains(&v0_prime));
690        assert!(state.equivocators().contains(&0));
691        float_eq!(
692            state.fault_weight(),
693            1.0,
694            "$v0_prime$ conflicts with $v0$ through $m0$, but we should accept this fault as it \
695             doesnt cross the fault threshold for the set, and thus the state_fault_weight should \
696             be incremented to 1.0"
697        );
698    }
699
700    #[test]
701    fn faulty_insert_at_threshold() {
702        let (v0_prime, validator_state) = faulty_insert_setup();
703
704        let mut state = validator::State::new_with_default_state(
705            validator_state,
706            None,
707            Some(0.1),
708            None,
709            Some(1.0),
710            None,
711        );
712        let mut justification = Justification::empty();
713        let success = justification.faulty_insert(&v0_prime, &mut state);
714
715        assert!(
716            !success,
717            "$v0_prime$ conflicts with $v0$ through $m0$, and we should not accept this fault as \
718             the fault threshold gets crossed for the set"
719        );
720        assert!(justification.is_empty());
721        assert!(!justification.contains(&v0_prime));
722        assert!(
723            state
724                .latests_messages()
725                .get(&0)
726                .unwrap()
727                .contains(&v0_prime),
728            "$v0_prime$ should still be contained in $state.latests_messages()$",
729        );
730        assert!(!state.equivocators().contains(&0));
731        float_eq!(
732            state.fault_weight(),
733            0.1,
734            "$v0_prime$ conflicts with $v0$ through $m0$, and we should NOT accept this fault as \
735             the fault threshold gets crossed for the set, and thus the state_fault_weight should \
736             not be incremented"
737        );
738    }
739
740    #[test]
741    fn faulty_insert_accept_with_bigger_numbers() {
742        let (v0_prime, validator_state) = faulty_insert_setup();
743
744        let mut state = validator::State::new_with_default_state(
745            validator_state,
746            None,
747            Some(1.0),
748            None,
749            Some(2.0),
750            None,
751        );
752        let mut justification = Justification::empty();
753        let success = justification.faulty_insert(&v0_prime, &mut state);
754
755        assert!(
756            success,
757            "$v0_prime$ conflict with $v0$ through $m0$, but we should accept this fault as the \
758             threshold doesnt get crossed for the set"
759        );
760        assert!(!justification.is_empty());
761        assert!(justification.contains(&v0_prime));
762        assert!(state
763            .latests_messages()
764            .get(&0)
765            .unwrap()
766            .contains(&v0_prime));
767        assert!(state.equivocators().contains(&0));
768        float_eq!(
769            state.fault_weight(),
770            2.0,
771            "$v0_prime$ conflict with $v0$ through $m0$, but we should NOT accept this fault as \
772             we can't know the weight of the validator, which could be Infinity, and thus the \
773             state_fault_weight should be unchanged"
774        );
775    }
776
777    #[test]
778    fn faulty_insert_unknown_weights() {
779        let (v0_prime, validator_state) = faulty_insert_setup();
780
781        // bug found
782        let mut state = validator::State::new_with_default_state(
783            validator_state,
784            Some(validator::Weights::new(vec![].into_iter().collect())),
785            Some(1.0),
786            None,
787            Some(2.0),
788            None,
789        );
790        let mut justification = Justification::empty();
791        let success = justification.faulty_insert(&v0_prime, &mut state);
792
793        assert!(
794            !success,
795            "$v0_prime$ conflict with $v0$ through $m0$, but we should NOT accept this fault as \
796             we can't know the weight of the validator, which could be Infinity"
797        );
798        assert!(justification.is_empty());
799        assert!(!justification.contains(&v0_prime));
800        assert!(
801            state
802                .latests_messages()
803                .get(&0)
804                .unwrap()
805                .contains(&v0_prime),
806            "$v0_prime$ should still be contained in $state.latests_messages()$",
807        );
808        assert!(!state.equivocators().contains(&0));
809        float_eq!(
810            state.fault_weight(),
811            1.0,
812            "$v0_prime$ conflict with $v0$ through $m0$, but we should NOT accept this fault as \
813             we can't know the weight of the validator, which could be Infinity, and thus the \
814             state_fault_weight should be unchanged"
815        );
816    }
817
818    #[test]
819    fn faulty_insert_double_equivocation() {
820        let mut validator_state = validator::State::new(
821            validator::Weights::new(vec![(0, 1.0)].into_iter().collect()),
822            0.0,
823            LatestMessages::empty(),
824            1.0,
825            HashSet::new(),
826        );
827
828        let v0 = Message::new(0, Justification::empty(), IntegerWrapper::new(0));
829        let v0_prime = Message::new(0, Justification::empty(), IntegerWrapper::new(1));
830        let v0_second = Message::new(0, Justification::empty(), IntegerWrapper::new(2));
831
832        let mut justification = Justification::empty();
833
834        // 0's equivocation can be registered as it would not cross the threshold. Its third
835        // message would not change the fault weight and is also accepted.
836        assert!(justification.faulty_insert(&v0, &mut validator_state));
837        assert!(justification.faulty_insert(&v0_prime, &mut validator_state));
838        assert!(justification.faulty_insert(&v0_second, &mut validator_state));
839
840        assert_eq!(
841            HashSet::<&Message<IntegerWrapper>>::from_iter(justification.iter()),
842            HashSet::from_iter(vec![&v0, &v0_prime, &v0_second])
843        );
844        assert!(validator_state.equivocators().contains(&0));
845        float_eq!(validator_state.fault_weight(), 1.0);
846    }
847
848    #[test]
849    fn faulty_insert_with_slash() {
850        let mut validator_state = validator::State::new(
851            validator::Weights::new(vec![(0, 1.0)].into_iter().collect()),
852            0.0,
853            LatestMessages::empty(),
854            1.0,
855            HashSet::new(),
856        );
857
858        let v0 = Message::new(0, Justification::empty(), IntegerWrapper::new(0));
859        let v0_prime = Message::new(0, Justification::empty(), IntegerWrapper::new(1));
860
861        let mut justification = Justification::empty();
862
863        assert!(justification
864            .faulty_insert_with_slash(&v0, &mut validator_state)
865            .unwrap());
866        assert!(justification
867            .faulty_insert_with_slash(&v0_prime, &mut validator_state)
868            .unwrap());
869
870        assert!(justification.contains(&v0));
871        assert!(justification.contains(&v0_prime));
872        assert_eq!(
873            *validator_state.latests_messages().get(&0).unwrap(),
874            HashSet::from_iter(vec![v0, v0_prime]),
875        );
876        assert_eq!(*validator_state.equivocators(), HashSet::from_iter(vec![0]));
877        float_eq!(
878            validator_state.validators_weights().weight(&0).unwrap(),
879            0.0
880        );
881        float_eq!(validator_state.fault_weight(), 0.0);
882    }
883
884    #[test]
885    fn equivocate() {
886        let mut validator_state = validator::State::new(
887            validator::Weights::new(vec![(0, 1.0)].into_iter().collect()),
888            0.0,
889            LatestMessages::empty(),
890            0.0,
891            HashSet::new(),
892        );
893
894        let v0 = VoteCount::create_vote_message(0, true);
895        let v0_prime = VoteCount::create_vote_message(0, false);
896
897        validator_state.update(&[&v0]);
898        let v0_second = Message::from_validator_state(0, &validator_state).unwrap();
899
900        assert!(validator_state.latests_messages().equivocate(&v0_prime));
901        assert!(!validator_state.latests_messages().equivocate(&v0_second));
902    }
903
904    #[test]
905    fn from_messages() {
906        let mut validator_state = validator::State::new(
907            validator::Weights::new(vec![(0, 1.0), (1, 1.0), (2, 1.0)].into_iter().collect()),
908            0.0,
909            LatestMessages::empty(),
910            0.0,
911            HashSet::new(),
912        );
913
914        let v0 = VoteCount::create_vote_message(0, true);
915        let v1 = VoteCount::create_vote_message(1, true);
916        let v2 = VoteCount::create_vote_message(2, false);
917
918        let initial_messages = vec![v0.clone(), v1.clone(), v2.clone()];
919        let justification = Justification::from_messages(initial_messages, &mut validator_state);
920
921        assert_eq!(
922            HashSet::<&Message<VoteCount>>::from_iter(justification.iter()),
923            HashSet::from_iter(vec![&v0, &v1, &v2]),
924        );
925    }
926
927    #[test]
928    fn from_messages_equivocation() {
929        let mut validator_state = validator::State::new(
930            validator::Weights::new(vec![(0, 1.0), (1, 1.0), (2, 1.0)].into_iter().collect()),
931            0.0,
932            LatestMessages::empty(),
933            0.0,
934            HashSet::new(),
935        );
936
937        let v0 = VoteCount::create_vote_message(0, true);
938        let v1 = VoteCount::create_vote_message(1, true);
939        let v2 = VoteCount::create_vote_message(2, false);
940        let v0_prime = VoteCount::create_vote_message(0, false);
941
942        let initial_messages = vec![v0.clone(), v1.clone(), v2.clone()];
943        let mut justification =
944            Justification::from_messages(initial_messages, &mut validator_state);
945
946        justification.faulty_insert(&v0_prime, &mut validator_state);
947
948        assert_eq!(
949            HashSet::<&Message<VoteCount>>::from_iter(justification.iter()),
950            HashSet::from_iter(vec![&v0, &v1, &v2]),
951        );
952    }
953
954    #[test]
955    fn from_messages_duplicate() {
956        let mut validator_state = validator::State::new(
957            validator::Weights::new(vec![(0, 1.0)].into_iter().collect()),
958            0.0,
959            LatestMessages::empty(),
960            0.0,
961            HashSet::new(),
962        );
963
964        let v0 = VoteCount::create_vote_message(0, true);
965        let v0_prime = VoteCount::create_vote_message(0, true);
966
967        let initial_messages = vec![v0, v0_prime];
968
969        let justification = Justification::from_messages(initial_messages, &mut validator_state);
970        assert_eq!(
971            justification.len(),
972            1,
973            "Justification should deduplicate messages"
974        );
975    }
976
977    #[test]
978    fn justification_make_estimate() {
979        let mut validator_state = validator::State::new(
980            validator::Weights::new(vec![(0, 1.0), (1, 1.0), (2, 1.0)].into_iter().collect()),
981            0.0,
982            LatestMessages::empty(),
983            1.0,
984            HashSet::new(),
985        );
986
987        let v0 = VoteCount::create_vote_message(0, true);
988        let v1 = VoteCount::create_vote_message(1, true);
989        let v2 = VoteCount::create_vote_message(2, false);
990
991        let initial_messages = vec![v0, v1, v2];
992        let justification = Justification::from_messages(initial_messages, &mut validator_state);
993
994        let estimate = justification.make_estimate(
995            validator_state.equivocators(),
996            validator_state.validators_weights(),
997        );
998
999        assert_eq!(
1000            estimate.expect("Estimate failed"),
1001            VoteCount { yes: 2, no: 1 }
1002        );
1003    }
1004
1005    #[test]
1006    fn justification_make_estimate_equivocator_not_at_threshold() {
1007        let mut validator_state = validator::State::new(
1008            validator::Weights::new(vec![(0, 1.0), (1, 1.0), (2, 1.0)].into_iter().collect()),
1009            0.0,
1010            LatestMessages::empty(),
1011            1.0,
1012            HashSet::new(),
1013        );
1014
1015        let v0 = VoteCount::create_vote_message(0, true);
1016        let v0_prime = VoteCount::create_vote_message(0, false);
1017        let v1 = VoteCount::create_vote_message(1, false);
1018        let v2 = VoteCount::create_vote_message(2, false);
1019
1020        let initial_messages = vec![v0, v1, v2];
1021        let mut justification =
1022            Justification::from_messages(initial_messages, &mut validator_state);
1023        justification.faulty_insert(&v0_prime, &mut validator_state);
1024
1025        let estimate = justification.make_estimate(
1026            validator_state.equivocators(),
1027            validator_state.validators_weights(),
1028        );
1029
1030        assert_eq!(
1031            estimate.expect("Estimate failed"),
1032            VoteCount { yes: 0, no: 2 }
1033        );
1034    }
1035
1036    #[test]
1037    fn justification_make_estimate_equivocator_at_threshold() {
1038        let mut validator_state = validator::State::new(
1039            validator::Weights::new(vec![(0, 1.0), (1, 1.0), (2, 1.0)].into_iter().collect()),
1040            0.0,
1041            LatestMessages::empty(),
1042            0.0,
1043            HashSet::new(),
1044        );
1045
1046        let v0 = VoteCount::create_vote_message(0, true);
1047        let v0_prime = VoteCount::create_vote_message(0, false);
1048        let v1 = VoteCount::create_vote_message(1, false);
1049        let v2 = VoteCount::create_vote_message(2, false);
1050
1051        let initial_messages = vec![v0, v1, v2];
1052        let mut justification =
1053            Justification::from_messages(initial_messages, &mut validator_state);
1054        justification.faulty_insert(&v0_prime, &mut validator_state);
1055
1056        let estimate = justification.make_estimate(
1057            validator_state.equivocators(),
1058            validator_state.validators_weights(),
1059        );
1060
1061        assert_eq!(
1062            estimate.expect("Estimate failed"),
1063            VoteCount { yes: 1, no: 2 }
1064        );
1065    }
1066
1067    #[test]
1068    fn latest_messages_update_new_sender() {
1069        let mut latest_messages = LatestMessages::empty();
1070
1071        let v0 = VoteCount::create_vote_message(0, true);
1072
1073        let sender_latest_messages_hashset = vec![v0.clone()].into_iter().collect();
1074        assert!(latest_messages.update(&v0));
1075        assert_eq!(
1076            latest_messages.get(&0),
1077            Some(&sender_latest_messages_hashset)
1078        );
1079    }
1080
1081    #[test]
1082    fn latest_messages_update_duplicate_message() {
1083        let mut latest_messages = LatestMessages::empty();
1084        let v0 = VoteCount::create_vote_message(0, true);
1085
1086        assert!(latest_messages.update(&v0));
1087        assert_eq!(
1088            latest_messages.get(&0),
1089            Some(&vec![v0.clone()].into_iter().collect())
1090        );
1091        assert!(!latest_messages.update(&v0.clone()));
1092        assert_eq!(
1093            latest_messages.get(&0),
1094            Some(&vec![v0].into_iter().collect())
1095        );
1096    }
1097
1098    #[test]
1099    fn latest_messages_update_new_message() {
1100        let v0 = VoteCount::create_vote_message(0, false);
1101        let mut justification = Justification::empty();
1102        justification.insert(v0.clone());
1103        let v0_prime = Message::new(0, justification, VoteCount { yes: 1, no: 0 });
1104
1105        let mut latest_messages = LatestMessages::empty();
1106        assert!(latest_messages.update(&v0));
1107        assert!(latest_messages.update(&v0_prime));
1108
1109        assert_eq!(
1110            latest_messages.get(&0),
1111            Some(&vec![v0_prime].into_iter().collect())
1112        );
1113    }
1114
1115    #[test]
1116    fn latest_messages_update_old_message() {
1117        // update will only return false in this case.
1118        let v0 = VoteCount::create_vote_message(0, false);
1119        let mut justification = Justification::empty();
1120        justification.insert(v0.clone());
1121        let v0_prime = Message::new(0, justification, VoteCount { yes: 1, no: 0 });
1122
1123        let mut latest_messages = LatestMessages::empty();
1124        assert!(latest_messages.update(&v0_prime));
1125        assert!(!latest_messages.update(&v0));
1126
1127        assert_eq!(
1128            latest_messages.get(&0),
1129            Some(&vec![v0_prime].into_iter().collect())
1130        );
1131    }
1132
1133    #[test]
1134    fn latest_messages_update_equivocation() {
1135        let v0 = VoteCount::create_vote_message(0, false);
1136        let v0_prime = VoteCount::create_vote_message(0, true);
1137
1138        let mut latest_messages = LatestMessages::empty();
1139        assert!(latest_messages.update(&v0));
1140        assert!(latest_messages.update(&v0_prime));
1141
1142        assert_eq!(
1143            latest_messages.get(&0),
1144            Some(&vec![v0, v0_prime].into_iter().collect())
1145        );
1146    }
1147}
core_cbc_casper/justification.rs

core_cbc_casper/
justification.rs
