fbas_analyzer/analysis/
assume_faulty.rs

1use super::*;
2
3impl Fbas {
4    /// Assume in the following that `nodes` can exhibit crash failures with the "goal" of
5    /// blocking individual nodes or the whole FBAS. For keeping node IDs unchanged, this method
6    /// doesn't delete the node entirely but only makes it unsatisfiable.
7    pub fn assume_crash_faulty(&mut self, nodes: &NodeIdSet) {
8        for node_id in nodes.iter() {
9            self.nodes[node_id].quorum_set = QuorumSet::new_unsatisfiable();
10        }
11    }
12    /// Assume in the following that `nodes` can exhibit Byzantine failures with the "goal" of
13    /// provoking splits. This corresponds to the *delete* operation from Mazières's original
14    /// FBAS/SCP paper. For keeping node IDs unchanged, this method doesn't delete the node
15    /// entirely but only makes it unsatisfiable and redacts it from all quorum sets.
16    pub fn assume_split_faulty(&mut self, nodes: &NodeIdSet) {
17        for node_id in nodes.iter() {
18            self.nodes[node_id].quorum_set = QuorumSet::new_unsatisfiable();
19        }
20        for node in self.nodes.iter_mut() {
21            node.assume_split_faulty(nodes);
22        }
23    }
24}
25impl Node {
26    /// This corresponds to the *delete* operation from Mazières's original FBAS/SCP paper.
27    pub fn assume_split_faulty(&mut self, nodes: &NodeIdSet) {
28        self.quorum_set.assume_split_faulty(nodes);
29    }
30}
31impl QuorumSet {
32    /// This corresponds to the *delete* operation from Mazières's original FBAS/SCP paper.
33    pub fn assume_split_faulty(&mut self, nodes: &NodeIdSet) {
34        let n_validators_before = self.validators.len();
35        self.validators = self
36            .validators
37            .iter()
38            .copied()
39            .filter(|&x| !nodes.contains(x))
40            .collect();
41        let n_validator_deletions = n_validators_before - self.validators.len();
42
43        for iqs in self.inner_quorum_sets.iter_mut() {
44            iqs.assume_split_faulty(nodes);
45        }
46        self.threshold = self.threshold.saturating_sub(n_validator_deletions);
47    }
48}
49
50#[cfg(test)]
51mod tests {
52    use super::*;
53
54    #[test]
55    fn assume_crash_faulty_makes_nodes_unsatisfiable() {
56        let mut fbas = Fbas::from_json_str(
57            r#"[
58            {
59                "publicKey": "n0",
60                "quorumSet": { "threshold": 2, "validators": ["n0", "n1"], "innerQuorumSets": [] }
61            },
62            {
63                "publicKey": "n1",
64                "quorumSet": { "threshold": 2, "validators": ["n0", "n1"], "innerQuorumSets": [] }
65            }
66        ]"#,
67        );
68        fbas.assume_crash_faulty(&bitset! {1});
69        let actual = fbas;
70        let expected = Fbas::from_json_str(
71            r#"[
72            {
73                "publicKey": "n0",
74                "quorumSet": { "threshold": 2, "validators": ["n0", "n1"], "innerQuorumSets": [] }
75            },
76            {
77                "publicKey": "n1",
78                "quorumSet": { "threshold": 1, "validators": [], "innerQuorumSets": [] }
79            }
80        ]"#,
81        );
82        assert_eq!(expected, actual);
83    }
84
85    #[test]
86    fn assume_split_faulty_makes_nodes_unsatisfiable() {
87        let mut fbas = Fbas::from_json_str(
88            r#"[
89            {
90                "publicKey": "n0",
91                "quorumSet": { "threshold": 2, "validators": ["n0", "n1"], "innerQuorumSets": [] }
92            },
93            {
94                "publicKey": "n1",
95                "quorumSet": { "threshold": 2, "validators": ["n0", "n1"], "innerQuorumSets": [] }
96            }
97        ]"#,
98        );
99        fbas.assume_split_faulty(&bitset! {0, 1});
100        assert!(!fbas.nodes[0].quorum_set.is_satisfiable());
101        assert!(!fbas.nodes[1].quorum_set.is_satisfiable());
102    }
103
104    #[test]
105    fn assume_split_faulty_removes_from_quorum_sets() {
106        let mut fbas = Fbas::from_json_str(
107            r#"[
108            {
109                "publicKey": "n0",
110                "quorumSet": { "threshold": 2, "validators": ["n0", "n1"], "innerQuorumSets": [] }
111            },
112            {
113                "publicKey": "n1",
114                "quorumSet": { "threshold": 2, "validators": ["n0", "n1"], "innerQuorumSets": [] }
115            }
116        ]"#,
117        );
118        fbas.assume_split_faulty(&bitset! {1});
119        let actual = fbas.nodes[0].quorum_set.clone();
120        let expected = QuorumSet::new(vec![0], vec![], 1);
121        assert_eq!(expected, actual);
122    }
123
124    #[test]
125    fn assume_split_faulty_works_on_a_more_complex_fbas() {
126        let mut fbas = Fbas::from_json_str(
127            r#"[
128            {
129                "publicKey": "n0",
130                "quorumSet": { "threshold": 3, "validators": ["n0", "n1", "n2"], "innerQuorumSets": [] }
131            },
132            {
133                "publicKey": "n1",
134                "quorumSet": { "threshold": 3, "validators": ["n0", "n1"], "innerQuorumSets": [
135                    { "threshold": 2, "validators": ["n2", "n3"] }
136                ]}
137            },
138            {
139                "publicKey": "n2",
140                "quorumSet": { "threshold": 4, "validators": ["n0", "n1", "n2", "n3"], "innerQuorumSets": [] }
141            },
142            {
143                "publicKey": "n3",
144                "quorumSet": { "threshold": 4, "validators": ["n1", "n2", "n3", "n4"], "innerQuorumSets": [] }
145            }
146        ]"#,
147        );
148        fbas.assume_split_faulty(&bitset! {0, 2});
149        let actual = fbas;
150        let expected = Fbas::from_json_str(
151            r#"[
152            {
153                "publicKey": "n0"
154            },
155            {
156                "publicKey": "n1",
157                "quorumSet": { "threshold": 2, "validators": ["n1"], "innerQuorumSets": [
158                    { "threshold": 1, "validators": ["n3"] }
159                ]}
160            },
161            {
162                "publicKey": "n2"
163            },
164            {
165                "publicKey": "n3",
166                "quorumSet": { "threshold": 3, "validators": ["n1", "n3", "n4"], "innerQuorumSets": [] }
167            }
168        ]"#,
169        );
170        assert_eq!(expected, actual);
171    }
172}
fbas_analyzer/analysis/assume_faulty.rs

fbas_analyzer/analysis/
assume_faulty.rs
