Implementation of the Agreement on Common Subset (ACS) communication primitive following the key ideas from Ben-Or, Kelmer, and Rabin (BKR)
The Agreement on Common Subset primitive (aka. Agreement on Core Set, aka. Asynchronous Interactive Consistency, aka. Asynchronous Common Subset, aka. Vector Consensus) is a primitive that allows a set of nodes to agree on a set of values formed from inputs specific to each node. The length of the agreed set is at least the number of correct nodes in the system.
This primitive is employed in asynchronous networks and is a common step to achieving atomic/total order broadcast under this network model.
The main idea of BKR is to reduce the ACS problem to several parallel instances of Byzantine Reliable Broadcast (BRB) and Asynchronous Binary Agreement (ABA). Each node in the system will propose a value using BRB and whether this value belongs in the output set is determined by having all nodes participate in a ABA.
This key idea is used in recent asynchronous Byzantine Fault Tolerant (BFT) State Machine Replication (SMR) systems such as HoneyBadgerBFT, BEAT, and PACE.
In the ABA primitive, each node proposes a binary value and the output is a binary value that is proposed by at least one correct node. The implementation of ABA follows the algorithm from Mostéfaoui, Moumen, and Raynal (MMR).
Instead of faithfully following the aforementioned algorithm, we reduce ABA to Binding Crusader Agreement (BCA) and a coin toss. Additionally we use an optimization presented in the BCA paper to reduce the number of communication rounds by reusing information from different ABA rounds (External Validity property).
Efficient ABA algorithms, such as MMR, require a distributed coin tossing primitive. We follow the algorithm of Cachin, Kursawe, and Shoup to implement this primitive. In particular, our implementation uses a 2t-unpredictable strong coin.
The elliptic curves used in the coin tossing algorithm are Ristretto255. The CIRCL library was used compute the group operations and the discrete log equivalence proofs.
During the setup phase, we assume the leader is honest. A more secure implementation would require a distributed key generation protocol for high threshold values.
To try the code, you must run several instances, each of which will be a node in the network. At least one of the nodes must be the contact node, which will be the entry point for the other nodes to join the network.
Messages only start being exchanged after all nodes have joined the network. The number of nodes in the network, as well as the address of the contact are set in the configuration file config.properties.
Additionally, each node must know its own address. This information is not in the configuration file and must instead be passed as an argument when running the node.