commonware_consensus/lib.rs
1//! Order opaque messages in a Byzantine environment.
2//!
3//! # Status
4//!
5//! `commonware-consensus` is **ALPHA** software and is not yet recommended for production use. Developers should
6//! expect breaking changes and occasional instability.
7
8pub mod ordered_broadcast;
9pub mod simplex;
10pub mod threshold_simplex;
11
12cfg_if::cfg_if! {
13 if #[cfg(not(target_arch = "wasm32"))] {
14 use commonware_utils::Array;
15 use commonware_cryptography::Digest;
16 use futures::channel::{oneshot, mpsc};
17 use std::future::Future;
18
19 /// Histogram buckets for measuring consensus latency.
20 const LATENCY: [f64; 36] = [
21 0.05, 0.1, 0.125, 0.15, 0.16, 0.17, 0.18, 0.19, 0.2, 0.21, 0.22, 0.23, 0.24, 0.25, 0.26, 0.27, 0.28, 0.29, 0.3, 0.31, 0.32, 0.33, 0.34, 0.35,
22 0.36, 0.37, 0.38, 0.39, 0.4, 0.45, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0,
23 ];
24
25 /// Automaton is the interface responsible for driving the consensus forward by proposing new payloads
26 /// and verifying payloads proposed by other participants.
27 pub trait Automaton: Clone + Send + 'static {
28 /// Context is metadata provided by the consensus engine associated with a given payload.
29 ///
30 /// This often includes things like the proposer, view number, the height, or the epoch.
31 type Context;
32
33 /// Hash of an arbitrary payload.
34 type Digest: Digest;
35
36 /// Payload used to initialize the consensus engine.
37 fn genesis(&mut self) -> impl Future<Output = Self::Digest> + Send;
38
39 /// Generate a new payload for the given context.
40 ///
41 /// If it is possible to generate a payload, the Digest should be returned over the provided
42 /// channel. If it is not possible to generate a payload, the channel can be dropped. If construction
43 /// takes too long, the consensus engine may drop the provided proposal.
44 fn propose(
45 &mut self,
46 context: Self::Context,
47 ) -> impl Future<Output = oneshot::Receiver<Self::Digest>> + Send;
48
49 /// Verify the payload is valid.
50 ///
51 /// If it is possible to verify the payload, a boolean should be returned indicating whether
52 /// the payload is valid. If it is not possible to verify the payload, the channel can be dropped.
53 fn verify(
54 &mut self,
55 context: Self::Context,
56 payload: Self::Digest,
57 ) -> impl Future<Output = oneshot::Receiver<bool>> + Send;
58 }
59
60 /// Relay is the interface responsible for broadcasting payloads to the network.
61 ///
62 /// The consensus engine is only aware of a payload's digest, not its contents. It is up
63 /// to the relay to efficiently broadcast the full payload to other participants.
64 pub trait Relay: Clone + Send + 'static {
65 /// Hash of an arbitrary payload.
66 type Digest: Digest;
67
68 /// Called once consensus begins working towards a proposal provided by `Automaton` (i.e.
69 /// it isn't dropped).
70 ///
71 /// Other participants may not begin voting on a proposal until they have the full contents,
72 /// so timely delivery often yields better performance.
73 fn broadcast(&mut self, payload: Self::Digest) -> impl Future<Output = ()> + Send;
74 }
75
76 /// Reporter is the interface responsible for reporting activity to some external actor.
77 pub trait Reporter: Clone + Send + 'static {
78 /// Activity is specified by the underlying consensus implementation and can be interpreted if desired.
79 ///
80 /// Examples of activity would be "vote", "finalize", or "fault". Various consensus implementations may
81 /// want to reward (or penalize) participation in different ways and in different places. For example,
82 /// validators could be required to send multiple types of messages (i.e. vote and finalize) and rewarding
83 /// both equally may better align incentives with desired behavior.
84 type Activity;
85
86 /// Report some activity observed by the consensus implementation.
87 fn report(&mut self, activity: Self::Activity) -> impl Future<Output = ()> + Send;
88 }
89
90 /// Supervisor is the interface responsible for managing which participants are active at a given time.
91 ///
92 /// ## Synchronization
93 ///
94 /// It is up to the user to ensure changes in this list are synchronized across nodes in the network
95 /// at a given `Index`. If care is not taken to do this, consensus could halt (as different participants
96 /// may have a different view of who is active at a given time).
97 ///
98 /// The simplest way to avoid this complexity is to use a consensus implementation that reaches finalization
99 /// on application data before transitioning to a new `Index` (i.e. [Tendermint](https://arxiv.org/abs/1807.04938)).
100 ///
101 /// Implementations that do not work this way (like `simplex`) must introduce some synchrony bound for changes
102 /// (where it is assumed all participants have finalized some previous set change by some point) or "sync points"
103 /// (i.e. epochs) where participants agree that some finalization occurred at some point in the past.
104 pub trait Supervisor: Clone + Send + Sync + 'static {
105 /// Index is the type used to indicate the in-progress consensus decision.
106 type Index;
107
108 /// Public key used to identify participants.
109 type PublicKey: Array;
110
111 /// Return the leader at a given index for the provided seed.
112 fn leader(&self, index: Self::Index) -> Option<Self::PublicKey>;
113
114 /// Get the **sorted** participants for the given view. This is called when entering a new view before
115 /// listening for proposals or votes. If nothing is returned, the view will not be entered.
116 fn participants(&self, index: Self::Index) -> Option<&Vec<Self::PublicKey>>;
117
118 // Indicate whether some candidate is a participant at the given view.
119 fn is_participant(&self, index: Self::Index, candidate: &Self::PublicKey) -> Option<u32>;
120 }
121
122 /// ThresholdSupervisor is the interface responsible for managing which `polynomial` (typically a polynomial with
123 /// a fixed constant `identity`) and `share` for a participant is active at a given time.
124 ///
125 /// ## Synchronization
126 ///
127 /// The same considerations for [`Supervisor`](crate::Supervisor) apply here.
128 pub trait ThresholdSupervisor: Supervisor {
129 /// Identity is the type against which threshold signatures are verified.
130 type Identity;
131
132 /// Seed is some random value used to bias the leader selection process.
133 type Seed;
134
135 /// Polynomial is the group polynomial over which partial signatures are verified.
136 type Polynomial;
137
138 /// Share is the type used to generate a partial signature that can be verified
139 /// against `Identity`.
140 type Share;
141
142 /// Returns the static identity of the shared secret (typically the constant term
143 /// of a polynomial).
144 fn identity(&self) -> &Self::Identity;
145
146 /// Return the leader at a given index over the provided seed.
147 fn leader(&self, index: Self::Index, seed: Self::Seed) -> Option<Self::PublicKey>;
148
149 /// Returns the polynomial over which partial signatures are verified at a given index.
150 fn polynomial(&self, index: Self::Index) -> Option<&Self::Polynomial>;
151
152 /// Returns share to sign with at a given index. After resharing, the share
153 /// may change (and old shares may be deleted).
154 ///
155 /// This can be used to generate a partial signature that can be verified
156 /// against `polynomial`.
157 fn share(&self, index: Self::Index) -> Option<&Self::Share>;
158 }
159
160 /// Monitor is the interface an external actor can use to observe the progress of a consensus implementation.
161 ///
162 /// Monitor is used to implement mechanisms that share the same set of active participants as consensus and/or
163 /// perform some activity that requires some synchronization with the progress of consensus.
164 ///
165 /// Monitor can be implemented using [`Reporter`](crate::Reporter) to avoid introducing complexity
166 /// into any particular consensus implementation.
167 pub trait Monitor: Clone + Send + 'static {
168 /// Index is the type used to indicate the in-progress consensus decision.
169 type Index;
170
171 /// Create a channel that will receive updates when the latest index (also provided) changes.
172 fn subscribe(&mut self) -> impl Future<Output = (Self::Index, mpsc::Receiver<Self::Index>)> + Send;
173 }
174 }
175}