Because it takes such a central part in a federated mint we will begin with explaining the properties of Byzantine Fault Tolerant (BFT) consensus algorithms.
A byzantine fault does not only allow a party to go offline, but also to maliciously continue participating in the protocol. In the following we will use
as the total number of participants in a protocol and
as the maximum amount of faulty ones among them.
We define a BFT consensus algorithm as an algorithm that allows all honest parties to agree on a common set of items as long as less or equal than
of the participants are malicious. These items may be contributed by any participant and there should be no risk of targeted censorship of items. One such protocol is Honey Badger BFT (HBBFT). We will mainly use it as a reference for BFT consensus properties but note that similar but more efficient ones exist (most notably Dumbo and hybrids built on top of it).
We generally assume the consensus to run in rounds, producing a common subset of the contributions made by the participants. At the start of each round each participant
is expected to propose a set of items
to the consensus.
After the BFT consensus algorithm has finished (note: this involves a lot of back-and-forth communication which we ignore for now) every honest participant learns the same subset
The consensus set
contains at least
contributions from different participants. Note how this implies that if more than
participants propose the same item said item is guaranteed to be included in the next consensus output.
The consensus protocols we are discussing, asynchronous ones, can only handle about
faulty nodes, so this will also be our assumption when building our protocol on top if not stated otherwise.