2018-11-03 04:31:36 -07:00
|
|
|
use std::collections::BTreeMap;
|
|
|
|
use std::sync::Arc;
|
|
|
|
use std::{fmt, result};
|
|
|
|
|
|
|
|
use derivative::Derivative;
|
|
|
|
use hex_fmt::HexFmt;
|
|
|
|
use log::debug;
|
2019-04-01 05:37:14 -07:00
|
|
|
use serde::Serialize;
|
2018-11-03 04:31:36 -07:00
|
|
|
|
|
|
|
use super::proposal_state::{ProposalState, Step as ProposalStep};
|
2018-12-18 07:17:46 -08:00
|
|
|
use super::{Error, FaultKind, Message, MessageContent, Result};
|
2019-01-08 00:30:37 -08:00
|
|
|
use crate::{util, ConsensusProtocol, NetworkInfo, NodeIdT, SessionIdT};
|
2018-12-27 01:34:34 -08:00
|
|
|
use rand::Rng;
|
2018-11-03 04:31:36 -07:00
|
|
|
|
2018-11-26 06:35:24 -08:00
|
|
|
/// A `Subset` step, possibly containing several outputs.
|
2018-12-18 07:17:46 -08:00
|
|
|
pub type Step<N> = crate::Step<Message<N>, SubsetOutput<N>, N, FaultKind>;
|
2018-11-03 04:31:36 -07:00
|
|
|
|
2018-11-26 06:35:24 -08:00
|
|
|
/// An output with an accepted contribution or the end of the set.
|
2018-11-03 04:31:36 -07:00
|
|
|
#[derive(Derivative, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
|
|
|
|
#[derivative(Debug)]
|
|
|
|
pub enum SubsetOutput<N> {
|
2018-11-26 06:35:24 -08:00
|
|
|
/// A contribution was accepted into the set.
|
2018-11-03 04:31:36 -07:00
|
|
|
Contribution(
|
|
|
|
N,
|
|
|
|
#[derivative(Debug(format_with = "util::fmt_hex"))] Vec<u8>,
|
|
|
|
),
|
2018-11-26 06:35:24 -08:00
|
|
|
/// The set is complete.
|
2018-11-03 04:31:36 -07:00
|
|
|
Done,
|
|
|
|
}
|
|
|
|
|
|
|
|
/// Subset algorithm instance
|
|
|
|
#[derive(Debug)]
|
2018-12-27 01:34:34 -08:00
|
|
|
pub struct Subset<N, S> {
|
2018-11-03 04:31:36 -07:00
|
|
|
/// Shared network information.
|
|
|
|
netinfo: Arc<NetworkInfo<N>>,
|
|
|
|
/// The session identifier.
|
|
|
|
session_id: S,
|
|
|
|
/// A map that assigns to each validator the progress of their contribution.
|
|
|
|
proposal_states: BTreeMap<N, ProposalState<N, S>>,
|
|
|
|
/// Whether the instance has decided on a value.
|
|
|
|
decided: bool,
|
|
|
|
}
|
|
|
|
|
2019-01-08 00:30:37 -08:00
|
|
|
impl<N: NodeIdT, S: SessionIdT> ConsensusProtocol for Subset<N, S> {
|
2018-11-03 04:31:36 -07:00
|
|
|
type NodeId = N;
|
|
|
|
type Input = Vec<u8>;
|
|
|
|
type Output = SubsetOutput<N>;
|
|
|
|
type Message = Message<N>;
|
|
|
|
type Error = Error;
|
2018-12-18 07:17:46 -08:00
|
|
|
type FaultKind = FaultKind;
|
2018-11-03 04:31:36 -07:00
|
|
|
|
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
|
|
|
fn handle_input<R: Rng>(&mut self, input: Self::Input, _rng: &mut R) -> Result<Step<N>> {
|
2018-11-03 04:31:36 -07:00
|
|
|
self.propose(input)
|
|
|
|
}
|
|
|
|
|
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
|
|
|
fn handle_message<R: Rng>(
|
|
|
|
&mut self,
|
|
|
|
sender_id: &N,
|
|
|
|
message: Message<N>,
|
|
|
|
_rng: &mut R,
|
|
|
|
) -> Result<Step<N>> {
|
2018-11-03 04:31:36 -07:00
|
|
|
self.handle_message(sender_id, message)
|
|
|
|
}
|
|
|
|
|
|
|
|
fn terminated(&self) -> bool {
|
|
|
|
self.decided
|
|
|
|
}
|
|
|
|
|
|
|
|
fn our_id(&self) -> &Self::NodeId {
|
|
|
|
self.netinfo.our_id()
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2018-12-27 01:34:34 -08:00
|
|
|
impl<N: NodeIdT, S: SessionIdT> Subset<N, S> {
|
2018-11-03 04:31:36 -07:00
|
|
|
/// Creates a new `Subset` instance with the given session identifier.
|
|
|
|
///
|
|
|
|
/// If multiple `Subset`s are instantiated within a single network, they must use different
|
|
|
|
/// session identifiers to foil replay attacks.
|
|
|
|
pub fn new(netinfo: Arc<NetworkInfo<N>>, session_id: S) -> Result<Self> {
|
|
|
|
let mut proposal_states = BTreeMap::new();
|
|
|
|
for (proposer_idx, proposer_id) in netinfo.all_ids().enumerate() {
|
|
|
|
let ba_id = BaSessionId {
|
|
|
|
subset_id: session_id.clone(),
|
|
|
|
proposer_idx: proposer_idx as u32,
|
|
|
|
};
|
|
|
|
proposal_states.insert(
|
|
|
|
proposer_id.clone(),
|
|
|
|
ProposalState::new(netinfo.clone(), ba_id, proposer_id.clone())?,
|
|
|
|
);
|
|
|
|
}
|
|
|
|
|
|
|
|
Ok(Subset {
|
|
|
|
netinfo,
|
|
|
|
session_id,
|
|
|
|
proposal_states,
|
|
|
|
decided: false,
|
|
|
|
})
|
|
|
|
}
|
|
|
|
|
|
|
|
/// Proposes a value for the subset.
|
|
|
|
///
|
|
|
|
/// Returns an error if we already made a proposal.
|
2018-11-07 05:26:14 -08:00
|
|
|
pub fn propose(&mut self, value: Vec<u8>) -> Result<Step<N>> {
|
2018-11-03 04:31:36 -07:00
|
|
|
if !self.netinfo.is_validator() {
|
|
|
|
return Ok(Step::default());
|
|
|
|
}
|
|
|
|
debug!("{} proposing {:0.10}", self, HexFmt(&value));
|
|
|
|
let prop_step = self
|
|
|
|
.proposal_states
|
|
|
|
.get_mut(self.netinfo.our_id())
|
|
|
|
.ok_or(Error::UnknownProposer)?
|
|
|
|
.propose(value)?;
|
|
|
|
let step = Self::convert_step(self.netinfo.our_id(), prop_step);
|
|
|
|
Ok(step.join(self.try_output()?))
|
|
|
|
}
|
|
|
|
|
|
|
|
/// Handles a message received from `sender_id`.
|
|
|
|
///
|
|
|
|
/// This must be called with every message we receive from another node.
|
2018-11-07 05:26:14 -08:00
|
|
|
pub fn handle_message(&mut self, sender_id: &N, msg: Message<N>) -> Result<Step<N>> {
|
2018-11-03 04:31:36 -07:00
|
|
|
let prop_step = self
|
|
|
|
.proposal_states
|
|
|
|
.get_mut(&msg.proposer_id)
|
|
|
|
.ok_or(Error::UnknownProposer)?
|
|
|
|
.handle_message(sender_id, msg.content)?;
|
|
|
|
let step = Self::convert_step(&msg.proposer_id, prop_step);
|
|
|
|
Ok(step.join(self.try_output()?))
|
|
|
|
}
|
|
|
|
|
|
|
|
/// Returns the number of validators from which we have already received a proposal.
|
|
|
|
pub fn received_proposals(&self) -> usize {
|
|
|
|
let received = |state: &&ProposalState<N, S>| state.received();
|
|
|
|
self.proposal_states.values().filter(received).count()
|
|
|
|
}
|
|
|
|
|
2018-11-07 05:26:14 -08:00
|
|
|
fn convert_step(proposer_id: &N, prop_step: ProposalStep<N>) -> Step<N> {
|
2018-11-03 04:31:36 -07:00
|
|
|
let from_p_msg = |p_msg: MessageContent| p_msg.with(proposer_id.clone());
|
|
|
|
let mut step = Step::default();
|
2018-12-18 07:17:46 -08:00
|
|
|
if let Some(value) = step.extend_with(prop_step, |fault| fault, from_p_msg).pop() {
|
2018-11-03 04:31:36 -07:00
|
|
|
let contribution = SubsetOutput::Contribution(proposer_id.clone(), value);
|
|
|
|
step.output.push(contribution);
|
|
|
|
}
|
|
|
|
step
|
|
|
|
}
|
|
|
|
|
|
|
|
/// Returns the number of Binary Agreement instances that have decided "yes".
|
|
|
|
fn count_accepted(&self) -> usize {
|
|
|
|
let accepted = |state: &&ProposalState<N, S>| state.accepted();
|
|
|
|
self.proposal_states.values().filter(accepted).count()
|
|
|
|
}
|
|
|
|
|
|
|
|
/// Checks the voting and termination conditions: If enough proposals have been accepted, votes
|
|
|
|
/// "no" for the remaining ones. If all proposals have been decided, outputs `Done`.
|
2018-11-07 05:26:14 -08:00
|
|
|
fn try_output(&mut self) -> Result<Step<N>> {
|
2018-11-03 04:31:36 -07:00
|
|
|
if self.decided || self.count_accepted() < self.netinfo.num_correct() {
|
|
|
|
return Ok(Step::default());
|
|
|
|
}
|
|
|
|
let mut step = Step::default();
|
|
|
|
if self.count_accepted() == self.netinfo.num_correct() {
|
|
|
|
for (proposer_id, state) in &mut self.proposal_states {
|
|
|
|
step.extend(Self::convert_step(proposer_id, state.vote_false()?));
|
|
|
|
}
|
|
|
|
}
|
|
|
|
if self.proposal_states.values().all(ProposalState::complete) {
|
|
|
|
self.decided = true;
|
|
|
|
step.output.push(SubsetOutput::Done);
|
|
|
|
}
|
|
|
|
Ok(step)
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2018-12-27 01:34:34 -08:00
|
|
|
impl<N: NodeIdT, S: SessionIdT> fmt::Display for Subset<N, S> {
|
2019-01-09 02:56:40 -08:00
|
|
|
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> result::Result<(), fmt::Error> {
|
2018-11-03 04:31:36 -07:00
|
|
|
write!(f, "{:?} Subset({})", self.our_id(), self.session_id)
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
/// A session identifier for a `BinaryAgreement` instance run as a `Subset` sub-algorithm. It
|
|
|
|
/// consists of the `Subset` instance's own session ID, and the index of the proposer whose
|
|
|
|
/// contribution this `BinaryAgreement` is about.
|
|
|
|
#[derive(Clone, Debug, Serialize)]
|
|
|
|
pub struct BaSessionId<S> {
|
|
|
|
subset_id: S,
|
|
|
|
proposer_idx: u32,
|
|
|
|
}
|
|
|
|
|
|
|
|
impl<S: fmt::Display> fmt::Display for BaSessionId<S> {
|
2019-01-09 02:56:40 -08:00
|
|
|
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> result::Result<(), fmt::Error> {
|
2018-11-03 04:31:36 -07:00
|
|
|
write!(
|
|
|
|
f,
|
|
|
|
"subset {}, proposer #{}",
|
|
|
|
self.subset_id, self.proposer_idx
|
|
|
|
)
|
|
|
|
}
|
|
|
|
}
|