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.json"));
let 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,10},{1,10}], analysis.minimal_blocking_sets().unwrap());

// You can also 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,10]", serde_json::to_string(&analysis.top_tier()).unwrap());

// You can 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},{10}], remaining_mbs.unwrap()); // Yikes!

More examples…

…can be found in the src/bin and examples folders…

Modules

preprocessing
sets
simulation
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 the most 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.
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

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 returns the minimal splitting sets of all sub-FBASs. As this is probably not what you want then, you should check for quorum intersection before using this function.
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 the same quorum set, and the nodes contained in this quorum set are exactly the group of nodes (a symmetric cluster). 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.

Type Definitions

NodeId
NodeIdSet