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