Crate fbas_analyzer

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

• assume_faulty
• preprocessing
• sets
• timing

Macros

• bitset
  Create a BitSet from 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.
• FilteredNodes
  The result of filtering nodes by a predicate. Transform into_pretty_vec for usage in one of several without_nodes functions.
• 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.
• NodeIdSetResult
  Wraps a node ID set.
• NodeIdSetVecResult
  Wraps a vector of node ID sets. Node ID sets are stored in shrunken form to preserve memory.
• PrettyQuorumSet
• QuorumSet

Traits

• AnalysisResult

Functions

• all_intersect
• contains_quorum
  Returns true if any subset of node_set forms a quorum for fbas.
• 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.

Type Aliases

• NodeId
• NodeIdSet