[−][src]Module hbbft::binary_agreement
Binary Agreement
The Binary Agreement protocol allows each node to input one binary (bool
) value, and will
output a binary value. The output is guaranteed to have been input by at least one correct
node, and all correct nodes will have the same output.
How it works
The algorithm proceeds in epochs, and the number of epochs it takes until it terminates is
unbounded in theory but has a finite expected value. Each node keeps track of an estimate
value e
, which is initialized to the node's own input. Let's call a value v
that has been input by at least one correct node and such that !v
hasn't been output by any
correct node yet, a viable output. The estimate will always be a viable output.
All messages are annotated with the epoch they belong to, but we omit that here for brevity.
-
At the beginning of each epoch, we multicast
BVal(e)
. It translates to: "I know thate
is a viable output." -
Once we receive
BVal(v)
with the same value from f + 1 different validators, we know that at least one of them must be correct. So we know thatv
is a viable output. If we haven't done so already we multicastBVal(v)
. (Even if we already multicastBVal(!v)
). -
Let's say a node believes in
v
if it receivedBVal(v)
from 2 f + 1 validators. For the first valuev
we believe in, we multicastAux(v)
. It translates to: "I know that all correct nodes will eventually know thatv
is a viable output. I'm not sure about!v
yet."-
Since every node will receive at least 2 f + 1
BVal
messages from correct validators, there is at least one valuev
, such that every node receives f + 1BVal(v)
messages. As a consequence, every correct validator will multicastBVal(v)
itself. Hence we are guaranteed to receive 2 f + 1BVal(v)
messages. In short: If any correct node believes inv
, every correct node will. -
Every correct node will eventually send exactly one
Aux
, so we will receive at least N - fAux
messages with values we believe in. At that point, we define the setvals
of candidate values: the set of values we believe in and have received in anAux
.
-
-
Once we have the set of candidate values, we obtain a coin value
s
(see below).-
If there is only a single candidate value
b
, we set our estimatee = b
. Ifs == b
, we output and send aTerm(b)
message which is interpreted asBVal(b)
andAux(b)
for all future epochs. Ifs != b
, we just proceed to the next epoch. -
If both values are candidates, we set
e = s
and proceed to the next epoch.
-
In epochs that are 0 modulo 3, the value s
is true
. In 1 modulo 3, it is false
. In the
case 2 modulo 3, we flip a coin to determine a pseudorandom s
.
An adversary that knows each coin value, controls a few validators and controls network
scheduling can delay the delivery of Aux
and BVal
messages to influence which candidate
values the nodes will end up with. In some circumstances that allows them to stall the network.
This is even true if the coin is flipped too early: the adversary must not learn about the coin
value early enough to delay enough Aux
messages. That's why in the third case, the value s
is determined as follows:
-
We multicast a
Conf
message containing our candidate values. -
Since every good node believes in all values it puts into its
Conf
message, we will eventually receive N - fConf
messages containing only values we believe in. Then we trigger the coin. -
After f + 1 nodes have sent us their coin shares, we receive the coin output and assign it to
s
.
Modules
bool_set | A single-byte representation of a set of boolean values. |
Structs
BinaryAgreement | Binary Agreement instance |
Message | Messages sent during the Binary Agreement stage. |
Enums
Error | A |
FaultKind | A faulty Binary Agreement message received from a peer. |
MessageContent | The content of a message belonging to a particular |
SbvMessage | A message belonging to the Synchronized Binary Value Broadcast phase of a |
Type Definitions
Result | A |
Step | A |