2018-07-16 06:31:21 -07:00
|
|
|
#![deny(unused_must_use)]
|
2018-04-12 09:17:33 -07:00
|
|
|
//! Integration test of the reliable broadcast protocol.
|
|
|
|
|
2018-05-16 05:23:57 -07:00
|
|
|
mod network;
|
2018-05-02 06:34:30 -07:00
|
|
|
|
2018-10-25 08:21:24 -07:00
|
|
|
use std::collections::BTreeMap;
|
2018-05-29 05:17:30 -07:00
|
|
|
use std::iter::once;
|
2018-07-11 12:15:08 -07:00
|
|
|
use std::sync::Arc;
|
2018-05-02 06:34:30 -07:00
|
|
|
|
2018-10-29 07:36:56 -07:00
|
|
|
use log::info;
|
2018-05-16 05:23:57 -07:00
|
|
|
use rand::Rng;
|
2018-05-02 06:34:30 -07:00
|
|
|
|
2018-12-11 05:44:36 -08:00
|
|
|
use crate::network::{
|
2018-08-29 09:08:35 -07:00
|
|
|
Adversary, MessageScheduler, MessageWithSender, NodeId, RandomAdversary, SilentAdversary,
|
2018-07-05 09:20:53 -07:00
|
|
|
TestNetwork, TestNode,
|
|
|
|
};
|
2018-12-11 05:44:36 -08:00
|
|
|
use hbbft::broadcast::{Broadcast, Message};
|
|
|
|
use hbbft::{util, DistAlgorithm, NetworkInfo, Target, TargetedMessage};
|
2018-05-02 06:34:30 -07:00
|
|
|
|
2018-05-14 05:35:06 -07:00
|
|
|
/// An adversary that inputs an alternate value.
|
2018-05-03 01:07:37 -07:00
|
|
|
struct ProposeAdversary {
|
|
|
|
scheduler: MessageScheduler,
|
2018-10-25 08:21:24 -07:00
|
|
|
adv_nodes: BTreeMap<NodeId, Arc<NetworkInfo<NodeId>>>,
|
2018-05-03 01:07:37 -07:00
|
|
|
has_sent: bool,
|
|
|
|
}
|
|
|
|
|
|
|
|
impl ProposeAdversary {
|
|
|
|
/// Creates a new replay adversary with the given message scheduler.
|
|
|
|
fn new(
|
|
|
|
scheduler: MessageScheduler,
|
2018-10-25 08:21:24 -07:00
|
|
|
adv_nodes: BTreeMap<NodeId, Arc<NetworkInfo<NodeId>>>,
|
2018-05-03 01:07:37 -07:00
|
|
|
) -> ProposeAdversary {
|
|
|
|
ProposeAdversary {
|
|
|
|
scheduler,
|
|
|
|
adv_nodes,
|
|
|
|
has_sent: false,
|
|
|
|
}
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2018-08-29 09:08:35 -07:00
|
|
|
impl Adversary<Broadcast<NodeId>> for ProposeAdversary {
|
|
|
|
fn pick_node(&self, nodes: &BTreeMap<NodeId, TestNode<Broadcast<NodeId>>>) -> NodeId {
|
2018-05-03 01:07:37 -07:00
|
|
|
self.scheduler.pick_node(nodes)
|
|
|
|
}
|
|
|
|
|
2018-08-29 09:08:35 -07:00
|
|
|
fn push_message(&mut self, _: NodeId, _: TargetedMessage<Message, NodeId>) {
|
2018-05-03 01:07:37 -07:00
|
|
|
// All messages are ignored.
|
|
|
|
}
|
|
|
|
|
2018-08-29 09:08:35 -07:00
|
|
|
fn step(&mut self) -> Vec<MessageWithSender<Broadcast<NodeId>>> {
|
OsRng / external RNG Refactoring (#357)
* Use `OsRng` in place of `thread_rng`.
This changes the defaults of any builder by instantiating an `OsRng` instead of
a `thread_rng`, the former being much more secure than the latter.
Additionally, all the unit tests that still instantiate RNGs manually used `OsRng`s
as well; while there is no actual need for this level of security in tests, the performance overhead is very small and random number generation complexity has such a small impact on these tests that the convenience of being able to ban `thread_rng` from the codebase altogether, setting a good example and avoid issues when refactoring later greatly outweigh the negatives.
* Instead of storing random number generators in the various consensus algorithm instances, pass them in from the outside whenever they are needed.
This changes a large amount of interfaces (and in this commit is only partially done, since `DistAlgorithm` needs to be fundamentally altered as well.
It also obsoletes parts of the `util` module.
* Added an `R: Rng` type parameter to both methods of `DistAlgorithm`, forcing callers to pass in their own Rngs.
* Fixed documentation grammar and spelling in some of the altered interfaces due to RNG refactoring.
* Move `rng` argument to the end of the argument for most functions.
Also includes a reformatting due to Rust 1.30.
* Updated tests, accomodate `rng`-API changes.
* Fixed remaining compilation issues with new RNG code.
* Fix illegal `self` import outside curly braces.
* Cleaned up comments and fixed broken definition of `broadcast_input`.
* Updated existing test cases to properly work with static dispatch randomness.
* Do not use boxed `Rng`s for key generation in test networks.
* Use the passed-in `Rng` in `ReorderingAdversary`, instead of storing a boxed one.
* Fixed clippy lints after refactoring.
* Removed some no-longer necessary manual `fmt::Debug` implementations in test framework.
* Use `OsRng` even in tests in `binary_agreement_mitm`.
* Use a proper deterministic RNG in tests `binary_agreement_mitm`.
* Refactor `examples/simulation.rs` by not using `ThreadRng`, passing generic `Rng` parameters throughout and using a type alias instead of a newtype as the `Transaction`.
* Remove `thread_rng` use from `examples/node.rs`.
* Explicitly construct `InternalContrib` in `DynamicHoneyBadger::propose`.
* Fixed typo in description of `DistAlgorithm` trait.
2018-12-14 04:51:09 -08:00
|
|
|
let mut rng = rand::thread_rng();
|
2018-05-03 01:07:37 -07:00
|
|
|
if self.has_sent {
|
|
|
|
return vec![];
|
|
|
|
}
|
|
|
|
self.has_sent = true;
|
2018-10-25 08:21:24 -07:00
|
|
|
self.adv_nodes
|
2018-05-03 01:07:37 -07:00
|
|
|
.iter()
|
2018-10-25 08:21:24 -07:00
|
|
|
.flat_map(|(&id, netinfo)| {
|
|
|
|
Broadcast::new(netinfo.clone(), id)
|
|
|
|
.expect("broadcast instance")
|
OsRng / external RNG Refactoring (#357)
* Use `OsRng` in place of `thread_rng`.
This changes the defaults of any builder by instantiating an `OsRng` instead of
a `thread_rng`, the former being much more secure than the latter.
Additionally, all the unit tests that still instantiate RNGs manually used `OsRng`s
as well; while there is no actual need for this level of security in tests, the performance overhead is very small and random number generation complexity has such a small impact on these tests that the convenience of being able to ban `thread_rng` from the codebase altogether, setting a good example and avoid issues when refactoring later greatly outweigh the negatives.
* Instead of storing random number generators in the various consensus algorithm instances, pass them in from the outside whenever they are needed.
This changes a large amount of interfaces (and in this commit is only partially done, since `DistAlgorithm` needs to be fundamentally altered as well.
It also obsoletes parts of the `util` module.
* Added an `R: Rng` type parameter to both methods of `DistAlgorithm`, forcing callers to pass in their own Rngs.
* Fixed documentation grammar and spelling in some of the altered interfaces due to RNG refactoring.
* Move `rng` argument to the end of the argument for most functions.
Also includes a reformatting due to Rust 1.30.
* Updated tests, accomodate `rng`-API changes.
* Fixed remaining compilation issues with new RNG code.
* Fix illegal `self` import outside curly braces.
* Cleaned up comments and fixed broken definition of `broadcast_input`.
* Updated existing test cases to properly work with static dispatch randomness.
* Do not use boxed `Rng`s for key generation in test networks.
* Use the passed-in `Rng` in `ReorderingAdversary`, instead of storing a boxed one.
* Fixed clippy lints after refactoring.
* Removed some no-longer necessary manual `fmt::Debug` implementations in test framework.
* Use `OsRng` even in tests in `binary_agreement_mitm`.
* Use a proper deterministic RNG in tests `binary_agreement_mitm`.
* Refactor `examples/simulation.rs` by not using `ThreadRng`, passing generic `Rng` parameters throughout and using a type alias instead of a newtype as the `Transaction`.
* Remove `thread_rng` use from `examples/node.rs`.
* Explicitly construct `InternalContrib` in `DynamicHoneyBadger::propose`.
* Fixed typo in description of `DistAlgorithm` trait.
2018-12-14 04:51:09 -08:00
|
|
|
.handle_input(b"Fake news".to_vec(), &mut rng)
|
2018-10-25 08:21:24 -07:00
|
|
|
.expect("propose")
|
|
|
|
.messages
|
|
|
|
.into_iter()
|
|
|
|
.map(move |msg| MessageWithSender::new(id, msg))
|
2018-12-11 05:44:36 -08:00
|
|
|
})
|
|
|
|
.collect()
|
2018-05-03 01:07:37 -07:00
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2018-05-02 06:34:30 -07:00
|
|
|
/// Broadcasts a value from node 0 and expects all good nodes to receive it.
|
2018-08-29 09:08:35 -07:00
|
|
|
fn test_broadcast<A: Adversary<Broadcast<NodeId>>>(
|
|
|
|
mut network: TestNetwork<A, Broadcast<NodeId>>,
|
2018-05-14 05:35:06 -07:00
|
|
|
proposed_value: &[u8],
|
|
|
|
) {
|
2018-05-08 07:20:32 -07:00
|
|
|
// This returns an error in all but the first test.
|
|
|
|
let _ = env_logger::try_init();
|
2018-05-01 09:32:01 -07:00
|
|
|
|
2018-05-04 02:14:19 -07:00
|
|
|
// Make node 0 propose the value.
|
2018-08-29 09:08:35 -07:00
|
|
|
network.input(NodeId(0), proposed_value.to_vec());
|
2018-05-01 09:32:01 -07:00
|
|
|
|
|
|
|
// Handle messages in random order until all nodes have output the proposed value.
|
2018-05-19 05:29:31 -07:00
|
|
|
while !network.nodes.values().all(TestNode::terminated) {
|
|
|
|
network.step();
|
|
|
|
}
|
|
|
|
// Verify that all instances output the proposed value.
|
|
|
|
for node in network.nodes.values() {
|
2018-05-29 05:17:30 -07:00
|
|
|
assert!(once(&proposed_value.to_vec()).eq(node.outputs()));
|
2018-05-01 09:32:01 -07:00
|
|
|
}
|
2018-06-25 12:09:45 -07:00
|
|
|
assert!(once(&proposed_value.to_vec()).eq(network.observer.outputs()));
|
2018-04-12 09:17:33 -07:00
|
|
|
}
|
2018-05-02 06:34:30 -07:00
|
|
|
|
2018-08-29 09:08:35 -07:00
|
|
|
fn new_broadcast(netinfo: Arc<NetworkInfo<NodeId>>) -> Broadcast<NodeId> {
|
|
|
|
Broadcast::new(netinfo, NodeId(0)).expect("Instantiate broadcast")
|
2018-05-16 05:23:57 -07:00
|
|
|
}
|
|
|
|
|
2018-05-14 07:16:57 -07:00
|
|
|
fn test_broadcast_different_sizes<A, F>(new_adversary: F, proposed_value: &[u8])
|
|
|
|
where
|
2018-08-29 09:08:35 -07:00
|
|
|
A: Adversary<Broadcast<NodeId>>,
|
2018-10-25 08:21:24 -07:00
|
|
|
F: Fn(BTreeMap<NodeId, Arc<NetworkInfo<NodeId>>>) -> A,
|
2018-05-14 07:16:57 -07:00
|
|
|
{
|
|
|
|
let mut rng = rand::thread_rng();
|
|
|
|
let sizes = (1..6)
|
2018-05-29 05:17:30 -07:00
|
|
|
.chain(once(rng.gen_range(6, 20)))
|
|
|
|
.chain(once(rng.gen_range(30, 50)));
|
2018-05-14 07:16:57 -07:00
|
|
|
for size in sizes {
|
2018-11-22 04:00:02 -08:00
|
|
|
let num_faulty_nodes = util::max_faulty(size);
|
2018-05-14 07:16:57 -07:00
|
|
|
let num_good_nodes = size - num_faulty_nodes;
|
2018-05-17 08:38:45 -07:00
|
|
|
info!(
|
2018-05-14 07:16:57 -07:00
|
|
|
"Network size: {} good nodes, {} faulty nodes",
|
|
|
|
num_good_nodes, num_faulty_nodes
|
|
|
|
);
|
2018-10-25 08:21:24 -07:00
|
|
|
let adversary = |adv_nodes| new_adversary(adv_nodes);
|
2018-05-16 05:23:57 -07:00
|
|
|
let network = TestNetwork::new(num_good_nodes, num_faulty_nodes, adversary, new_broadcast);
|
2018-05-14 07:16:57 -07:00
|
|
|
test_broadcast(network, proposed_value);
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2018-05-04 02:14:19 -07:00
|
|
|
#[test]
|
2018-05-08 07:20:32 -07:00
|
|
|
fn test_8_broadcast_equal_leaves_silent() {
|
2018-06-25 11:22:08 -07:00
|
|
|
let adversary = |_| SilentAdversary::new(MessageScheduler::Random);
|
2018-05-04 02:14:19 -07:00
|
|
|
// Space is ASCII character 32. So 32 spaces will create shards that are all equal, even if the
|
|
|
|
// length of the value is inserted.
|
2018-05-16 05:23:57 -07:00
|
|
|
test_broadcast(
|
|
|
|
TestNetwork::new(8, 0, adversary, new_broadcast),
|
|
|
|
&[b' '; 32],
|
|
|
|
);
|
2018-05-04 02:14:19 -07:00
|
|
|
}
|
|
|
|
|
|
|
|
#[test]
|
2018-05-14 07:16:57 -07:00
|
|
|
fn test_broadcast_random_delivery_silent() {
|
2018-10-25 08:21:24 -07:00
|
|
|
let new_adversary = |_| SilentAdversary::new(MessageScheduler::Random);
|
2018-05-14 07:16:57 -07:00
|
|
|
test_broadcast_different_sizes(new_adversary, b"Foo");
|
2018-05-04 02:14:19 -07:00
|
|
|
}
|
|
|
|
|
2018-05-02 06:34:30 -07:00
|
|
|
#[test]
|
2018-05-16 05:23:57 -07:00
|
|
|
fn test_broadcast_first_delivery_silent() {
|
2018-10-25 08:21:24 -07:00
|
|
|
let new_adversary = |_| SilentAdversary::new(MessageScheduler::First);
|
2018-05-14 07:16:57 -07:00
|
|
|
test_broadcast_different_sizes(new_adversary, b"Foo");
|
2018-05-08 07:20:32 -07:00
|
|
|
}
|
|
|
|
|
|
|
|
#[test]
|
2018-05-16 05:23:57 -07:00
|
|
|
fn test_broadcast_random_delivery_adv_propose() {
|
2018-10-25 08:21:24 -07:00
|
|
|
let new_adversary = |adv_nodes| ProposeAdversary::new(MessageScheduler::Random, adv_nodes);
|
2018-05-14 07:16:57 -07:00
|
|
|
test_broadcast_different_sizes(new_adversary, b"Foo");
|
2018-05-03 01:07:37 -07:00
|
|
|
}
|
|
|
|
|
|
|
|
#[test]
|
2018-05-16 05:23:57 -07:00
|
|
|
fn test_broadcast_first_delivery_adv_propose() {
|
2018-10-25 08:21:24 -07:00
|
|
|
let new_adversary = |adv_nodes| ProposeAdversary::new(MessageScheduler::First, adv_nodes);
|
2018-05-14 07:16:57 -07:00
|
|
|
test_broadcast_different_sizes(new_adversary, b"Foo");
|
2018-05-03 01:07:37 -07:00
|
|
|
}
|
2018-07-05 09:20:53 -07:00
|
|
|
|
|
|
|
#[test]
|
|
|
|
fn test_broadcast_random_adversary() {
|
2018-10-25 08:21:24 -07:00
|
|
|
let new_adversary = |_| {
|
2018-07-05 09:20:53 -07:00
|
|
|
// Note: Set this to 0.8 to watch 30 gigs of RAM disappear.
|
|
|
|
RandomAdversary::new(0.2, 0.2, || TargetedMessage {
|
|
|
|
target: Target::All,
|
|
|
|
message: rand::random(),
|
|
|
|
})
|
|
|
|
};
|
|
|
|
test_broadcast_different_sizes(new_adversary, b"RandomFoo");
|
|
|
|
}
|