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