[−][src]Module hbbft::broadcast
Broadcast
The Broadcast Protocol assumes a network of N validators that send signed messages to each other, with at most f of them faulty, where 3 f < N. It allows one validator, the "proposer", to send a value to the other validators, and guarantees that:
- If the proposer is correct, all correct validators will receive the value.
- If the proposer is faulty, either all correct validators will receive the same value, or none of them receives any value at all.
Handling the networking and signing is the responsibility of this crate's user:
- The proposer needs to be determined beforehand. In all nodes,
Broadcast::new
must be called with the same proposer's ID. - Only in the proposer,
Broadcast::broadcast
is called, with the value they want to send. - All messages contained in
Step
s returned by any of the methods must be securely sent to the other nodes, e.g. by signing, (possibly encrypting) and sending them over the network. - All incoming, verified messages must be passed into
Broadcast::handle_message
. It is the user's responsibility to validate the sender, e.g. by checking the signature. - Eventually, a
Step
will contain the value as its output. At that point, the algorithm has terminated and the instance can be dropped. (The messages in the last step still need to be sent out, though, to allow the other nodes to terminate, too.)
How it works
The proposer uses a Reed-Solomon code to split the value into N chunks, N - 2 f of which
suffice to reconstruct the value. These chunks s[0]
, s[1]
, ..., s[N - 1]
are used as the
leaves of a Merkle tree, a data structure which allows creating small proofs that the chunks
belong together: The tree has a root hash h
, and for each chunk s[i]
, there is a branch
b[i]
connecting that chunk to the root hash. Together, these values are the proof
p[i] = (h, b[i], s[i])
, with which a third party can verify that s[i]
is the i
-th leaf of
the Merkle tree with root hash h
.
The algorithm proceeds as follows:
- The proposer sends
Value(p[i])
to each validator numberi
. - When validator
i
receivesValue(p[i])
from the proposer, it sends it on to everyone else asEcho(p[i])
. - A validator that has received N - f
Echo
s or f + 1Ready
s with root hashh
, sendsReady(h)
to everyone. - A node that has received 2 f + 1
Ready
s and N - 2 fEcho
s with root hashh
decodes and outputs the value, and then terminates.
Only the first valid Value
from the proposer, and the first valid Echo
message from every
validator, is handled as above. Invalid messages (where the proof isn't correct), Values
received from other nodes, and any further Value
s and Echo
s are ignored, and the sender is
reported as faulty.
In the Valid(p[i])
messages, the proposer distributes the chunks of the value equally among
all validators, along with a proof to verify that all chunks are leaves of the same Merkle tree
with root hash h
.
An Echo(p[i])
indicates that validator i
has received its chunk of the value from
the proposer. Since Echo
s contain the chunk, they are also used later on to reconstruct the
value when the algorithm completes: Every node that receives at least N - 2 f valid Echo
s
with root hash h
can decode the value.
A validator sends Ready(h)
as soon as it knows that everyone will eventually be able to
decode the value with root hash h
. Either of the two conditions in the third point above is
sufficient for that:
- If it has received N - f
Echo
s withh
, it knows that at least N - 2 f correct validators have multicast anEcho
withh
, and therefore everyone will eventually receive at least N - 2 f valid ones. So it knows that everyone will be able to decode, and can sendReady(h)
. Moreover, since every correct validator only sends one kind ofEcho
message, there is no danger of receiving N - fEcho
s with two different root hashes, so every correct validator will only send oneReady
message. - Even without enough
Echo
s, if a validator receives f + 1Ready(h)
messages, it knows that at least one correct validator has sentReady(h)
. It therefore also knows that everyone will be able to decode eventually, and multicastsReady(h)
itself.
Finally, if a node has received 2 f + 1 Ready(h)
messages, it knows that at least f + 1
correct validators have sent it. Thus, every remaining correct validator will eventually
receive f + 1, and multicast Ready(h)
itself. Hence every node will receive
N - f ≥ 2 f + 1 Ready(h)
messages.
In addition, we know at this point that every node will eventually be able to decode, i.e.
receive N - 2 f valid Echo
s (since we know that at least one correct validator has sent
Ready(h)
).
In short: Once we satisfy the termination condition in the fourth point (we've received
2 f + 1 Ready
s and N - 2 f Echo
s with root hash h
), we know that
everyone else will eventually satisfy it, too. So at that point, we can output and terminate.
Example
In this example, we manually pass messages between instantiated nodes to simulate a network. The
network is composed of 7 nodes, and node 3 is the proposer. We use u64
as network IDs, and
start by creating a common network info. Then we input a randomly generated payload into the
proposer and process all the resulting messages in a loop. For the purpose of simulation we
annotate each message with the node that produced it. For each output, we perform correctness
checks to verify that every node has output the same payload as we provided to the proposer
node, and that it did so exactly once.
use hbbft::broadcast::{Broadcast, Error, Step}; use hbbft::{NetworkInfo, SourcedMessage, Target, TargetedMessage}; use rand::{OsRng, Rng, RngCore}; use std::collections::{BTreeMap, BTreeSet, VecDeque}; use std::iter::once; use std::sync::Arc; fn main() -> Result<(), Error> { // Our simulated network has seven nodes in total, node 3 is the proposer. const NUM_NODES: u64 = 7; const PROPOSER_ID: u64 = 3; let mut rng = OsRng::new().expect("Could not initialize OS random number generator."); // Create a random set of keys for testing. let netinfos = NetworkInfo::generate_map(0..NUM_NODES, &mut rng) .expect("Failed to create `NetworkInfo` map"); // Create initial nodes by instantiating a `Broadcast` for each. let mut nodes = BTreeMap::new(); for (i, netinfo) in netinfos { let bc = Broadcast::new(Arc::new(netinfo), PROPOSER_ID)?; nodes.insert(i, bc); } // First we generate a random payload. let mut payload: Vec<_> = vec![0; 128]; rng.fill_bytes(&mut payload[..]); // Define a function for handling one step of a `Broadcast` instance. This function appends // new messages onto the message queue and checks whether each node outputs at most once // and the output is correct. let on_step = |id: u64, step: Step<u64>, messages: &mut VecDeque<SourcedMessage<TargetedMessage<_, _>, _>>, finished_nodes: &mut BTreeSet<u64>| { // Annotate messages with the sender ID. messages.extend(step.messages.into_iter().map(|msg| SourcedMessage { source: id, message: msg, })); if !step.output.is_empty() { // The output should be the same as the input we gave to the proposer. assert!(step.output.iter().eq(once(&payload))); // Every node should output exactly once. Here we check the first half of this // statement, namely that every node outputs at most once. assert!(finished_nodes.insert(id)); } }; let mut messages = VecDeque::new(); let mut finished_nodes = BTreeSet::new(); // Now we can start the algorithm, its input is the payload. let initial_step = { let proposer = nodes.get_mut(&PROPOSER_ID).unwrap(); proposer.broadcast(payload.clone()).unwrap() }; on_step( PROPOSER_ID, initial_step, &mut messages, &mut finished_nodes, ); // The message loop: The network is simulated by passing messages around from node to node. while let Some(SourcedMessage { source, message: TargetedMessage { target, message }, }) = messages.pop_front() { match target { Target::All => { for (id, node) in &mut nodes { let step = node.handle_message(&source, message.clone())?; on_step(*id, step, &mut messages, &mut finished_nodes); } } Target::Node(id) => { let step = { let node = nodes.get_mut(&id).unwrap(); node.handle_message(&source, message)? }; on_step(id, step, &mut messages, &mut finished_nodes); } }; } // Every node should output exactly once. Here we check the second half of this statement, // namely that every node outputs. assert_eq!(finished_nodes, nodes.keys().cloned().collect()); Ok(()) }
Structs
Broadcast | Broadcast algorithm instance. |
Enums
Error | A broadcast error. |
FaultKind | Represents each reason why a broadcast message could be faulty. |
Message | The three kinds of message sent during the reliable broadcast stage of the consensus algorithm. |
Type Definitions
Result | A broadcast result. |
Step | A |