2018-08-03 02:18:06 -07:00
|
|
|
//! # Collaborative Threshold Decryption
|
|
|
|
//!
|
|
|
|
//! Each node inputs the same encrypted data, and after at least _f + 1_ correct validators have
|
2018-08-07 09:25:50 -07:00
|
|
|
//! done so, each node outputs the decrypted data.
|
2018-08-03 02:18:06 -07:00
|
|
|
//!
|
|
|
|
//! ## How it works
|
|
|
|
//!
|
|
|
|
//! The algorithm uses a threshold encryption scheme: A message encrypted to the network's public
|
|
|
|
//! key can be collaboratively decrypted by combining at least _f + 1_ decryption shares. Each
|
2018-11-06 08:26:48 -08:00
|
|
|
//! validator holds a secret key share, and uses it to produce and multicast a decryption share once
|
|
|
|
//! a ciphertext is provided. The algorithm outputs as soon as it receives a ciphertext and _f + 1_
|
|
|
|
//! threshold shares.
|
2018-08-03 02:18:06 -07:00
|
|
|
|
|
|
|
use std::collections::BTreeMap;
|
|
|
|
use std::sync::Arc;
|
|
|
|
|
2018-12-11 05:44:36 -08:00
|
|
|
use crate::crypto::{self, Ciphertext, DecryptionShare};
|
2018-10-29 07:36:56 -07:00
|
|
|
use failure::Fail;
|
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
|
|
|
use rand::Rng;
|
2018-10-29 07:36:56 -07:00
|
|
|
use rand_derive::Rand;
|
|
|
|
use serde_derive::{Deserialize, Serialize};
|
|
|
|
|
2018-12-18 07:17:46 -08:00
|
|
|
use crate::fault_log::{self, Fault};
|
2018-12-11 05:44:36 -08:00
|
|
|
use crate::{DistAlgorithm, NetworkInfo, NodeIdT, Target};
|
2018-08-03 02:18:06 -07:00
|
|
|
|
|
|
|
/// A threshold decryption error.
|
|
|
|
#[derive(Clone, Eq, PartialEq, Debug, Fail)]
|
|
|
|
pub enum Error {
|
2018-11-26 06:35:24 -08:00
|
|
|
/// Redundant input provided.
|
2018-08-03 02:18:06 -07:00
|
|
|
#[fail(display = "Redundant input provided: {:?}", _0)]
|
|
|
|
MultipleInputs(Box<Ciphertext>),
|
2018-11-27 03:13:42 -08:00
|
|
|
/// Invalid ciphertext.
|
2018-08-03 02:18:06 -07:00
|
|
|
#[fail(display = "Invalid ciphertext: {:?}", _0)]
|
|
|
|
InvalidCiphertext(Box<Ciphertext>),
|
2018-11-27 03:13:42 -08:00
|
|
|
/// Unknown sender.
|
2018-08-03 02:18:06 -07:00
|
|
|
#[fail(display = "Unknown sender")]
|
|
|
|
UnknownSender,
|
2018-11-27 03:13:42 -08:00
|
|
|
/// Decryption failed.
|
2018-08-03 02:18:06 -07:00
|
|
|
#[fail(display = "Decryption failed: {:?}", _0)]
|
2018-10-10 07:11:27 -07:00
|
|
|
Decryption(crypto::error::Error),
|
2018-11-26 06:35:24 -08:00
|
|
|
/// Tried to decrypt before setting a cipherext.
|
|
|
|
#[fail(display = "Tried to decrypt before setting ciphertext")]
|
2018-11-06 08:26:48 -08:00
|
|
|
CiphertextIsNone,
|
2018-08-03 02:18:06 -07:00
|
|
|
}
|
|
|
|
|
|
|
|
/// A threshold decryption result.
|
|
|
|
pub type Result<T> = ::std::result::Result<T, Error>;
|
|
|
|
|
2018-12-18 07:17:46 -08:00
|
|
|
/// A threshold decryption message fault
|
|
|
|
#[derive(Clone, Debug, Fail, PartialEq)]
|
|
|
|
pub enum FaultKind {
|
|
|
|
/// `ThresholdDecrypt` received multiple shares from the same sender.
|
|
|
|
#[fail(display = "`ThresholdDecrypt` received multiple shares from the same sender.")]
|
|
|
|
MultipleDecryptionShares,
|
|
|
|
/// `HoneyBadger` received a decryption share from an unverified sender.
|
|
|
|
#[fail(display = "`HoneyBadger` received a decryption share from an unverified sender.")]
|
|
|
|
UnverifiedDecryptionShareSender,
|
|
|
|
}
|
|
|
|
|
|
|
|
/// The type of fault log whose entries are `ThresholdDecrypt` faults.
|
|
|
|
pub type FaultLog<N> = fault_log::FaultLog<N, FaultKind>;
|
|
|
|
|
2018-08-03 02:18:06 -07:00
|
|
|
/// A Threshold Decryption message.
|
|
|
|
#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Rand)]
|
|
|
|
pub struct Message(pub DecryptionShare);
|
|
|
|
|
2018-11-07 08:13:10 -08:00
|
|
|
/// A Threshold Decrypt algorithm instance. If every node inputs the same data, encrypted to the
|
2018-08-03 02:18:06 -07:00
|
|
|
/// network's public key, every node will output the decrypted data.
|
|
|
|
#[derive(Debug)]
|
2018-11-07 08:13:10 -08:00
|
|
|
pub struct ThresholdDecrypt<N> {
|
2018-08-03 02:18:06 -07:00
|
|
|
netinfo: Arc<NetworkInfo<N>>,
|
|
|
|
/// The encrypted data.
|
|
|
|
ciphertext: Option<Ciphertext>,
|
|
|
|
/// All received threshold decryption shares.
|
2018-12-10 08:08:01 -08:00
|
|
|
shares: BTreeMap<N, (usize, DecryptionShare)>,
|
2018-11-06 08:26:48 -08:00
|
|
|
/// Whether we already sent our shares.
|
|
|
|
had_input: bool,
|
2018-08-03 02:18:06 -07:00
|
|
|
/// Whether we have already returned the output.
|
|
|
|
terminated: bool,
|
|
|
|
}
|
|
|
|
|
2018-11-26 06:35:24 -08:00
|
|
|
/// A `ThresholdDecrypt` step. It will contain at most one output.
|
2018-12-11 05:44:36 -08:00
|
|
|
pub type Step<N> = crate::DaStep<ThresholdDecrypt<N>>;
|
2018-08-03 02:18:06 -07:00
|
|
|
|
2018-11-07 08:13:10 -08:00
|
|
|
impl<N: NodeIdT> DistAlgorithm for ThresholdDecrypt<N> {
|
2018-08-29 09:08:35 -07:00
|
|
|
type NodeId = N;
|
2018-11-06 08:26:48 -08:00
|
|
|
type Input = ();
|
2018-08-03 02:18:06 -07:00
|
|
|
type Output = Vec<u8>;
|
|
|
|
type Message = Message;
|
|
|
|
type Error = Error;
|
2018-12-18 07:17:46 -08:00
|
|
|
type FaultKind = FaultKind;
|
2018-08-03 02:18:06 -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: (), _rng: &mut R) -> Result<Step<N>> {
|
2018-11-06 08:26:48 -08:00
|
|
|
self.start_decryption()
|
2018-08-03 02:18:06 -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_message<R: Rng>(
|
|
|
|
&mut self,
|
|
|
|
sender_id: &Self::NodeId,
|
|
|
|
message: Message,
|
|
|
|
_rng: &mut R,
|
|
|
|
) -> Result<Step<N>> {
|
2018-08-03 02:18:06 -07:00
|
|
|
self.handle_message(sender_id, message)
|
|
|
|
}
|
|
|
|
|
|
|
|
fn terminated(&self) -> bool {
|
|
|
|
self.terminated
|
|
|
|
}
|
|
|
|
|
|
|
|
fn our_id(&self) -> &N {
|
2018-08-29 09:08:35 -07:00
|
|
|
self.netinfo.our_id()
|
2018-08-03 02:18:06 -07:00
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2018-11-07 08:13:10 -08:00
|
|
|
impl<N: NodeIdT> ThresholdDecrypt<N> {
|
|
|
|
/// Creates a new Threshold Decrypt instance.
|
2018-08-03 02:18:06 -07:00
|
|
|
pub fn new(netinfo: Arc<NetworkInfo<N>>) -> Self {
|
2018-11-07 08:13:10 -08:00
|
|
|
ThresholdDecrypt {
|
2018-08-03 02:18:06 -07:00
|
|
|
netinfo,
|
|
|
|
ciphertext: None,
|
|
|
|
shares: BTreeMap::new(),
|
2018-11-06 08:26:48 -08:00
|
|
|
had_input: false,
|
2018-08-03 02:18:06 -07:00
|
|
|
terminated: false,
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2018-11-07 08:13:10 -08:00
|
|
|
/// Creates a new instance of `ThresholdDecrypt`, including setting the ciphertext to
|
2018-11-06 08:26:48 -08:00
|
|
|
/// decrypt.
|
|
|
|
pub fn new_with_ciphertext(netinfo: Arc<NetworkInfo<N>>, ct: Ciphertext) -> Result<Self> {
|
2018-11-07 08:13:10 -08:00
|
|
|
let mut td = ThresholdDecrypt::new(netinfo);
|
2018-11-06 08:26:48 -08:00
|
|
|
td.set_ciphertext(ct)?;
|
|
|
|
Ok(td)
|
|
|
|
}
|
|
|
|
|
2018-08-03 02:18:06 -07:00
|
|
|
/// Sets the ciphertext, sends the decryption share, and tries to decrypt it.
|
|
|
|
/// This must be called exactly once, with the same ciphertext in all participating nodes.
|
2018-10-23 06:38:42 -07:00
|
|
|
/// If we have enough shares, outputs the plaintext.
|
2018-11-06 08:26:48 -08:00
|
|
|
pub fn set_ciphertext(&mut self, ct: Ciphertext) -> Result<()> {
|
2018-08-03 02:18:06 -07:00
|
|
|
if self.ciphertext.is_some() {
|
|
|
|
return Err(Error::MultipleInputs(Box::new(ct)));
|
|
|
|
}
|
2018-11-06 08:26:48 -08:00
|
|
|
if !ct.verify() {
|
|
|
|
return Err(Error::InvalidCiphertext(Box::new(ct.clone())));
|
2018-10-28 07:55:07 -07:00
|
|
|
}
|
2018-08-03 02:18:06 -07:00
|
|
|
self.ciphertext = Some(ct);
|
2018-11-06 08:26:48 -08:00
|
|
|
Ok(())
|
|
|
|
}
|
|
|
|
|
|
|
|
/// Sends our decryption shares to peers, and if we have collected enough, returns the decrypted
|
|
|
|
/// message. Returns an error if the ciphertext hasn't been received yet.
|
|
|
|
pub fn start_decryption(&mut self) -> Result<Step<N>> {
|
|
|
|
if self.had_input {
|
|
|
|
return Ok(Step::default()); // Don't waste time on redundant shares.
|
|
|
|
}
|
|
|
|
let ct = self.ciphertext.clone().ok_or(Error::CiphertextIsNone)?;
|
2018-08-03 02:18:06 -07:00
|
|
|
let mut step = Step::default();
|
|
|
|
step.fault_log.extend(self.remove_invalid_shares());
|
2018-11-06 08:26:48 -08:00
|
|
|
self.had_input = true;
|
2018-12-10 08:08:01 -08:00
|
|
|
let opt_idx = self.netinfo.node_index(self.our_id());
|
|
|
|
let (idx, share) = match (opt_idx, self.netinfo.secret_key_share()) {
|
|
|
|
(Some(idx), Some(sks)) => (idx, sks.decrypt_share_no_verify(&ct)),
|
|
|
|
(_, _) => return Ok(step.join(self.try_output()?)), // Not a validator.
|
2018-11-22 04:00:02 -08:00
|
|
|
};
|
2018-11-06 08:26:48 -08:00
|
|
|
let our_id = self.our_id().clone();
|
2018-10-28 07:55:07 -07:00
|
|
|
let msg = Target::All.message(Message(share.clone()));
|
|
|
|
step.messages.push(msg);
|
2018-12-10 08:08:01 -08:00
|
|
|
self.shares.insert(our_id, (idx, share));
|
2018-08-03 02:18:06 -07:00
|
|
|
step.extend(self.try_output()?);
|
|
|
|
Ok(step)
|
|
|
|
}
|
|
|
|
|
2018-08-03 06:24:49 -07:00
|
|
|
/// Returns an iterator over the IDs of all nodes who sent a share.
|
|
|
|
pub fn sender_ids(&self) -> impl Iterator<Item = &N> {
|
|
|
|
self.shares.keys()
|
|
|
|
}
|
|
|
|
|
2018-10-24 03:26:43 -07:00
|
|
|
/// Handles a message with a decryption share received from `sender_id`.
|
|
|
|
///
|
|
|
|
/// This must be called with every message we receive from another node.
|
|
|
|
///
|
|
|
|
/// If we have collected enough, returns the decrypted message.
|
2018-10-23 06:38:42 -07:00
|
|
|
pub fn handle_message(&mut self, sender_id: &N, message: Message) -> Result<Step<N>> {
|
2018-08-03 02:18:06 -07:00
|
|
|
if self.terminated {
|
|
|
|
return Ok(Step::default()); // Don't waste time on redundant shares.
|
|
|
|
}
|
2018-11-06 08:26:48 -08:00
|
|
|
// Before checking the share, ensure the sender is a known validator
|
2018-12-10 08:08:01 -08:00
|
|
|
let idx = self
|
|
|
|
.netinfo
|
|
|
|
.node_index(sender_id)
|
2018-11-06 08:26:48 -08:00
|
|
|
.ok_or(Error::UnknownSender)?;
|
2018-08-03 02:18:06 -07:00
|
|
|
let Message(share) = message;
|
|
|
|
if !self.is_share_valid(sender_id, &share) {
|
|
|
|
let fault_kind = FaultKind::UnverifiedDecryptionShareSender;
|
|
|
|
return Ok(Fault::new(sender_id.clone(), fault_kind).into());
|
|
|
|
}
|
2018-12-10 08:08:01 -08:00
|
|
|
let entry = (idx, share);
|
|
|
|
if self.shares.insert(sender_id.clone(), entry).is_some() {
|
2018-08-03 02:18:06 -07:00
|
|
|
return Ok(Fault::new(sender_id.clone(), FaultKind::MultipleDecryptionShares).into());
|
|
|
|
}
|
|
|
|
self.try_output()
|
|
|
|
}
|
|
|
|
|
|
|
|
/// Removes all shares that are invalid, and returns faults for their senders.
|
|
|
|
fn remove_invalid_shares(&mut self) -> FaultLog<N> {
|
|
|
|
let faulty_senders: Vec<N> = self
|
|
|
|
.shares
|
|
|
|
.iter()
|
2018-12-10 08:08:01 -08:00
|
|
|
.filter(|(id, (_, share))| !self.is_share_valid(id, share))
|
2018-08-03 02:18:06 -07:00
|
|
|
.map(|(id, _)| id.clone())
|
|
|
|
.collect();
|
|
|
|
let mut fault_log = FaultLog::default();
|
|
|
|
for id in faulty_senders {
|
|
|
|
self.shares.remove(&id);
|
|
|
|
fault_log.append(id, FaultKind::UnverifiedDecryptionShareSender);
|
|
|
|
}
|
|
|
|
fault_log
|
|
|
|
}
|
|
|
|
|
|
|
|
/// Returns `true` if the share is valid, or if we don't have the ciphertext yet.
|
|
|
|
fn is_share_valid(&self, id: &N, share: &DecryptionShare) -> bool {
|
|
|
|
let ct = match self.ciphertext {
|
|
|
|
None => return true, // No ciphertext yet. Verification postponed.
|
|
|
|
Some(ref ct) => ct,
|
|
|
|
};
|
|
|
|
match self.netinfo.public_key_share(id) {
|
|
|
|
None => false, // Unknown sender.
|
|
|
|
Some(pk) => pk.verify_decryption_share(share, ct),
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
/// Outputs the decrypted message, if we have the ciphertext and enough shares.
|
|
|
|
fn try_output(&mut self) -> Result<Step<N>> {
|
|
|
|
if self.terminated || self.shares.len() <= self.netinfo.num_faulty() {
|
|
|
|
return Ok(Step::default()); // Not enough shares yet, or already terminated.
|
|
|
|
}
|
|
|
|
let ct = match self.ciphertext {
|
|
|
|
None => return Ok(Step::default()), // Still waiting for the ciphertext.
|
2018-11-06 08:26:48 -08:00
|
|
|
Some(ref ct) => ct.clone(),
|
2018-08-03 02:18:06 -07:00
|
|
|
};
|
|
|
|
self.terminated = true;
|
2018-11-06 08:26:48 -08:00
|
|
|
let step = self.start_decryption()?; // Before terminating, make sure we sent our share.
|
2018-12-10 08:08:01 -08:00
|
|
|
let share_itr = self
|
|
|
|
.shares
|
|
|
|
.values()
|
|
|
|
.map(|&(ref idx, ref share)| (idx, share));
|
|
|
|
let plaintext = self
|
|
|
|
.netinfo
|
|
|
|
.public_key_set()
|
|
|
|
.decrypt(share_itr, &ct)
|
|
|
|
.map_err(Error::Decryption)?;
|
2018-11-06 08:26:48 -08:00
|
|
|
Ok(step.with_output(plaintext))
|
2018-08-03 02:18:06 -07:00
|
|
|
}
|
|
|
|
}
|