Expand description
A library and tool for analyzing the quorum structure of federated byzantine agreement systems (FBASs) like Stellar. Related research paper here.
We recommend using the Analysis struct for doing analyses.
§Example analysis
use fbas_analyzer::{Fbas, Analysis, bitset, bitsetvec};
let fbas = Fbas::from_json_file(std::path::Path::new("test_data/correct_trivial.json"));
let mut analysis = Analysis::new(&fbas);
assert!(analysis.has_quorum_intersection());
// "Unwrapping" analysis results gives us their internal representation, with node IDs
// corresponding to node indices in the input JSON.
assert_eq!(bitsetvec![{0,1},{0,2},{1,2}], analysis.minimal_blocking_sets().unwrap());
// You can directly transform results into vectors of public keys or organization names...
let mss_pretty = analysis.minimal_splitting_sets().into_pretty_vec_vec(&fbas, None);
assert_eq!(vec!["GCGB2S2KGYARPVIA37HYZXVRM2YZUEXA6S33ZU5BUDC6THSB62LZSTYH"], mss_pretty[0]);
// ...or serialize them using serde.
assert_eq!("[0,1,2]", serde_json::to_string(&analysis.top_tier()).unwrap());
// You can also post-process results. Let's say we believe that node 0 has crashed...
let remaining_mbs = analysis.minimal_blocking_sets().without_nodes(&[0]).minimal_sets();
assert_eq!(bitsetvec![{1},{2}], remaining_mbs.unwrap()); // Yikes!§More examples…
…can be found in the src/bin and examples folders…
Modules§
Macros§
- bitset
- Create a
BitSetfrom a list of elements. - bitsetvec
- Create a
Vec<BitSet>from a list of sets. - timed
- Measure the time it takes for an operation to complete (as
Duration). - timed_
secs - Measure the time it takes for an operation to complete (in seconds, as
f64).
Structs§
- Analysis
- Front end for many interesting FBAS analyses. Among other things, it does ID space shrinking (which improves memory and performance when using bit sets) and caches the results of long-running computations.
- Fbas
- Representation of an FBAS.
- Filtered
Nodes - The result of filtering nodes by a predicate. Transform
into_pretty_vecfor usage in one of severalwithout_nodesfunctions. - Groupings
- Defines one concrete way to group the nodes of an
Fbas, for example by organization, ISP or country. Used for merging nodes belonging to the same group into one. - Node
IdSet Result - Wraps a node ID set.
- Node
IdSet VecResult - Wraps a vector of node ID sets. Node ID sets are stored in shrunken form to preserve memory.
- Pretty
Quorum Set - Quorum
Set
Traits§
Functions§
- all_
intersect - contains_
quorum - Returns
trueif any subset ofnode_setforms a quorum forfbas. - find_
minimal_ blocking_ sets - Find all minimal blocking sets in the FBAS.
- find_
minimal_ quorums - Find all minimal quorums in the FBAS.
- find_
minimal_ splitting_ sets - If the FBAS doesn’t enjoy quorum intersection, this will just return
bitsetvec![{}]… - find_
nonintersecting_ quorums - Find at least two non-intersecting quorums. Use this function if you don’t want to enumerate all minimal quorums and/or it is likely that the FBAS lacks quorum intersection and you want to stop early in such cases.
- find_
symmetric_ clusters - Finds groups of nodes (represented as quorum sets) such that all members of the same group have (logically) the same quorum set and the common quorum set is comprised of exactly the group of nodes (a symmetric cluster). This function implicitly patches quorum sets so that each node is always included in its own quorum set. Getting a result with more than 1 entry implies that we don’t have quorum intersection.
- find_
symmetric_ top_ tier - If the top tier is symmetric, i.e., each two top-tier nodes have the same quorum set,
return the top tier’s common quorum set. Else return
None. This function implicitly patches quorum sets so that each node is always included in its own quorum set. - involved_
nodes - Returns the union of all sets in
node_sets. - is_
set_ of_ minimal_ node_ sets - remove_
non_ minimal_ node_ sets - Reduce to minimal node sets, i.e. to a set of node sets so that no member set is a superset of another.
- to_
grouping_ names - Resolve the grouping names for a collection of node IDs. Resolves to node names (public keys) if no matching grouping is found.
- to_
public_ keys - Resolve the pretty names for a collection of node IDs.