//! Order opaque messages in a Byzantine environment. //! //! # Status //! //! Stability varies by primitive. See [README](https://github.com/commonwarexyz/monorepo#stability) for details. #![doc( html_logo_url = "https://commonware.xyz/imgs/rustdoc_logo.svg", html_favicon_url = "https://commonware.xyz/favicon.ico" )] use commonware_macros::stability_scope; stability_scope!(BETA { use commonware_codec::{Encode, Read}; use commonware_cryptography::{Digestible, Digested}; use std::sync::Arc; pub mod simplex; pub mod types; use types::{Epoch, Height, Round, View}; /// Epochable is a trait that provides access to the epoch number. /// Any consensus message or object that is associated with a specific epoch should implement this. pub trait Epochable { /// Returns the epoch associated with this object. fn epoch(&self) -> Epoch; } /// Heightable is a trait that provides access to the height. /// Any consensus message or object that is associated with a specific height should implement this. pub trait Heightable { /// Returns the height associated with this object. fn height(&self) -> Height; } impl Heightable for Arc { fn height(&self) -> Height { self.as_ref().height() } } /// Viewable is a trait that provides access to the view (round) number. /// Any consensus message or object that is associated with a specific view should implement this. pub trait Viewable { /// Returns the view associated with this object. fn view(&self) -> View; } /// Roundable is a trait that provides access to the [`Round`] number. /// Any consensus message or object that implements [`Epochable`] and [`Viewable`] automatically /// implements this trait. pub trait Roundable: Epochable + Viewable { /// Returns the round associated with this object, derived from its epoch and view. fn round(&self) -> Round { Round::new(self.epoch(), self.view()) } } impl Roundable for T {} /// Block is the interface for a block in the blockchain. /// /// A block type that is also decoded, such as an application block received over the wire or /// read from storage, must use a canonical encoding. Every byte sequence `bytes` accepted by /// the decoder must satisfy `encode(decode(bytes)) == bytes`, and decoders must reject /// alternate encodings of the same block. pub trait Block: Heightable + Digestible + Encode { /// Get the parent block's digest. fn parent(&self) -> Self::Digest; } impl Block for Arc { fn parent(&self) -> Self::Digest { self.as_ref().parent() } } impl Heightable for Digested { fn height(&self) -> Height { self.inner().height() } } impl Block for Digested { fn parent(&self) -> Self::Digest { self.inner().parent() } } /// CertifiableBlock extends [Block] with consensus context information. /// /// This trait is required for blocks used with deferred verification in [CertifiableAutomaton]. /// It allows the verification context to be derived directly from the block when a validator /// needs to participate in certification but never verified the block locally (necessary for liveness). /// /// The [`Digestible`] implementation for a [`CertifiableBlock`] must commit to the block's /// embedded consensus context. In other words, changing [`CertifiableBlock::context`] for a /// block must also change [`Digestible::digest`]. pub trait CertifiableBlock: Block { /// The consensus context type stored in this block. type Context: Clone + Encode; /// Get the consensus context that was used when this block was proposed. fn context(&self) -> Self::Context; } impl CertifiableBlock for Digested { type Context = B::Context; fn context(&self) -> Self::Context { self.inner().context() } } /// A block that bounds its encoded size under a codec configuration. pub trait BoundedBlock: Block + Read { /// Returns an upper bound on the encoded size of any block [`Read::read_cfg`] admits under /// `cfg`, using each encoded type's maximum width. fn max_encode_size(cfg: &Self::Cfg) -> usize; } }); stability_scope!(BETA, cfg(not(target_arch = "wasm32")) { use commonware_actor::Feedback; use commonware_cryptography::{Digest, PublicKey}; use commonware_utils::channel::{fallible::OneshotExt, oneshot, ring}; use std::future::Future; pub mod marshal; mod reporter; pub use reporter::*; /// Histogram buckets for measuring consensus latency. const LATENCY: [f64; 36] = [ 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, 0.36, 0.37, 0.38, 0.39, 0.4, 0.45, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0, ]; /// Automaton is the interface responsible for driving the consensus forward by proposing new payloads /// and verifying payloads proposed by other participants. pub trait Automaton: Clone + Send + 'static { /// Context is metadata provided by the consensus engine associated with a given payload. /// /// This often includes things like the proposer, view number, the height, or the epoch. type Context; /// Hash of an arbitrary payload. type Digest: Digest; /// Generate a new payload for the given context. /// /// If it is possible to generate a payload, the Digest should be returned over the provided /// channel. If it is not possible to generate a payload, the channel can be dropped. If construction /// takes too long, the consensus engine may drop the provided proposal. /// /// Returning a payload from `propose` commits the local proposer to verifying /// the same `(context, payload)`. /// /// For [`CertifiableAutomaton`] implementations, returning a payload from /// `propose` also commits the local proposer to certifying that same /// `(round, payload)` if it later becomes notarized. /// /// Consensus may request a payload for a future context before earlier /// contexts complete. Honor any dependencies supplied in the context /// rather than rebuilding them from current local state. If consensus /// later abandons a dependency, it also abandons the proposal. /// /// Closing the response declines this request, which consensus may /// treat as final for the context. Keep the response pending when /// temporary unavailability should not abandon the context. fn propose( &mut self, context: Self::Context, ) -> impl Future> + Send; /// Verify the payload is valid. /// /// Honest participants must agree on validity for the same `(context, payload)`. /// /// This request is single-shot for the given `(context, payload)`. Once the returned /// channel resolves or closes, consensus treats verification as concluded and will not /// retry the same request. After a restart, however, consensus may request verification /// for the same `(context, payload)` again if the result was not durably recorded before /// shutdown. /// /// Implementations should therefore keep the request pending while the verdict may still /// change. Return `false` only when the payload is permanently invalid for this context. /// For example, temporary conditions such as time skew, missing dependencies, or data /// that may arrive later should not conclude verification with `false`. /// /// Closing the channel is also terminal for this request and should be reserved for cases /// where verification cannot ever produce a verdict anymore (for example, shutdown), not /// for temporary inability to decide. /// /// The future-context requirement on [`Self::propose`] applies here /// too: the context's dependencies may not be resolvable locally yet. fn verify( &mut self, context: Self::Context, payload: Self::Digest, ) -> impl Future> + Send; } /// An application's response to a handoff proposal request. /// /// `Handoff<()>` is the same decision without a payload, and [`map`](Self::map) attaches one. #[derive(Clone, Copy, Debug, Eq, PartialEq)] pub enum Handoff { /// Relay the candidate and cast the proposer's notarize vote without waiting for the /// parent to certify. /// /// This trusts the outgoing leader not to equivocate and to complete its term, since /// the proposal is usable only if every uncertified view it builds on certifies. /// /// Validators buffer the early vote only once it is inside their admission window, which /// always includes the next term start from the parent's term (see /// [Optimistic Validation](crate::simplex#optimistic-validation)), and consensus does not /// resend it. If the quorum needs a validator whose window does not reach the vote yet, the /// incoming term times out. Vote(D), /// Relay the candidate and withhold the proposer's notarize vote until its parent /// certifies or finalizes. /// /// The relay commits to nothing: only the vote names a proposal. If the parent is /// replaced before it certifies, the proposer can relay another candidate for the same /// view. /// /// A relay may defer sending the candidate until consensus requests the broadcast that /// precedes the proposer's vote. Stage(D), /// Request an ordinary proposal after the parent certifies. Wait, } impl Handoff { /// Returns whether this response declines to build. pub const fn is_wait(&self) -> bool { matches!(self, Self::Wait) } /// Applies `f` to the payload, keeping the decision. pub fn map(self, f: impl FnOnce(D) -> T) -> Handoff { match self { Self::Vote(payload) => Handoff::Vote(f(payload)), Self::Stage(payload) => Handoff::Stage(f(payload)), Self::Wait => Handoff::Wait, } } } /// CertifiableAutomaton extends [Automaton] with the ability to certify payloads before finalization. /// /// This trait is required by consensus implementations (like Simplex) that support a certification /// phase between notarization and finalization. Applications that do not need custom certification /// logic can use the default implementation which always certifies. pub trait CertifiableAutomaton: Automaton { /// Prepare a payload for a term-start proposal whose parent is not yet certified. /// /// Returning [`Handoff::Vote`] or [`Handoff::Stage`] commits the application to /// the same verification and certification obligations as returning a payload from /// [`Automaton::propose`]. /// /// With [`Handoff::Wait`], consensus issues an ordinary [`Automaton::propose`] for the same /// context once the parent certifies, unless it has already voted to nullify this view or /// has left it. /// /// Consensus requests the relay of a [`Handoff::Stage`] candidate as soon as it arrives. /// /// Closing the response forfeits the local proposal opportunity for this view once the /// parent certifies or finalizes, and the view then times out as a missing proposal. /// /// A replacement parent can supersede the request's parent before it certifies. Consensus /// then drops the request and can request a proposal on the replacement, unless it has /// voted to nullify this view or has left it. /// /// Return the receiver promptly and do any work behind it. Parent certification does not /// cancel this request, and while the response is pending, consensus requests no other /// proposal for this view. /// /// Consensus drops the receiver when it abandons the context, so stop pending work when /// the receiver closes. /// /// Consensus also drops the receiver once the parent can no longer be built on before it /// certifies, as after a nullification in the parent's term, or once it votes to nullify /// the view it is waiting in, at or below the parent. An application that verifies other /// blocks only after this build completes could otherwise keep that parent or view from /// certifying. The request then waits as if the application had returned /// [`Handoff::Wait`]. /// /// # Request Contract /// /// Per view and per process, with at most `f` faulty validators, consensus calls this /// method at most twice and [`Automaton::propose`] at most once. It skips this method when /// the parent is already certified. A second call follows only when the outgoing leader /// equivocated at the parent view and its other block there was notarized, replacing the /// parent this node voted for. A restart resets these counts. fn prepare( &mut self, _context: Self::Context, ) -> impl Future>> + Send { #[allow(clippy::async_yields_async)] async move { let (sender, receiver) = oneshot::channel(); sender.send_lossy(Handoff::Wait); receiver } } /// Determine whether a verified payload is safe to commit. /// /// The round parameter identifies which consensus round is being certified, allowing /// applications to associate certification with the correct verification context. The /// same payload may appear in multiple rounds, so implementations must key any state /// on `(round, payload)` rather than `payload` alone. /// /// Like [`Automaton::verify`], payloads produced by [`Automaton::propose`] are certifiable-by-construction. /// Also like [`Automaton::verify`], certification is single-shot for the given /// `(round, payload)`. Once the returned channel resolves or closes, consensus treats /// certification as concluded and will not retry the same request. After a restart, /// however, consensus may request certification for the same `(round, payload)` again /// if the result was not durably recorded before shutdown. Until that repeated request /// resolves, the proposal is pending again, exactly as before the first request /// completed, so consensus may still verify or build upon proposals that build upon /// it. A `false` result takes effect once consensus records it. /// /// Implementations should therefore keep the request pending while the verdict may still /// change. Return `false` only when the payload is permanently uncertifiable for that /// round. Temporary conditions such as waiting for more data should not conclude /// certification with `false`. /// /// Closing the channel is also terminal for this request and should be reserved for cases /// where certification can no longer produce a verdict (for example, shutdown), not for temporary /// inability to decide. /// /// # Determinism Requirement /// /// The decision returned by `certify` must be deterministic and consistent across /// all honest participants to ensure liveness. /// /// # Finality /// /// A certified payload may never be finalized. A competing payload can also certify in /// another round, even when every participant is honest. Only treat a payload as final /// once the [`Reporter`] receives a finalization for it or one of its descendants. fn certify( &mut self, _round: Round, _payload: Self::Digest, ) -> impl Future> + Send { #[allow(clippy::async_yields_async)] async move { let (sender, receiver) = oneshot::channel(); sender.send_lossy(true); receiver } } } /// Relay is the interface responsible for broadcasting payloads to the network. /// /// The consensus engine is only aware of a payload's digest, not its contents. It is up /// to the relay to efficiently broadcast the full payload to other participants. pub trait Relay: Clone + Send + 'static { /// Hash of an arbitrary payload. type Digest: Digest; /// Identity key of a network participant. type PublicKey: PublicKey; /// Directive for how a payload should be broadcast. /// /// Consensus mechanisms that need broadcast control (e.g. distinguishing /// initial broadcast from rebroadcasts) define a custom enum here. Mechanisms that /// treat every broadcast identically can set this to `()`. type Plan: Send; /// Broadcast a payload according to the given plan. fn broadcast(&mut self, payload: Self::Digest, plan: Self::Plan) -> Feedback; } /// Reporter is the interface responsible for reporting activity to some external actor. pub trait Reporter: Clone + Send + 'static { /// Activity is specified by the underlying consensus implementation and can be interpreted if desired. /// /// Examples of activity would be "vote", "finalize", or "fault". Various consensus implementations may /// want to reward (or penalize) participation in different ways and in different places. For example, /// validators could be required to send multiple types of messages (i.e. vote and finalize) and rewarding /// both equally may better align incentives with desired behavior. type Activity; /// Report some activity observed by the consensus implementation. fn report(&mut self, activity: Self::Activity) -> Feedback; } /// Alias for the subscription type returned by [`Monitor::subscribe`]. /// /// Each value is the latest index, so a subscriber that falls behind skips intermediate indices. pub type IndexSubscription = ring::Receiver; /// Monitor is the interface an external actor can use to observe the progress of a consensus implementation. /// /// Monitor is used to implement mechanisms that share the same set of active participants as consensus and/or /// perform some activity that requires some synchronization with the progress of consensus. /// /// Monitor can be implemented using [crate::Reporter] to avoid introducing complexity /// into any particular consensus implementation. pub trait Monitor: Clone + Send + 'static { /// Index is the type used to indicate the in-progress consensus decision. type Index; /// Returns the latest index and a subscription that yields the newest index whenever it /// has changed. fn subscribe( &mut self, ) -> impl Future)> + Send; } }); stability_scope!(ALPHA { pub mod aggregation; }); stability_scope!(ALPHA, cfg(not(target_arch = "wasm32")) { use crate::marshal::ancestry::Ancestry; use commonware_cryptography::certificate::Scheme; /// Application is a minimal interface for standard implementations that operate over a stream /// of epoched blocks. pub trait Application: Clone + Send + 'static { /// The signing scheme used by the application. type SigningScheme: Scheme; /// Context is metadata provided by the consensus engine associated with a given payload. /// /// This often includes things like the proposer, view number, the height, or the epoch. type Context: Epochable; /// The block type produced by the application's builder. /// /// The builder hands marshal a [`Digested`] block, so the application computes the digest /// of a block it built exactly once, on its own strategy, before returning it. type Block: Block; /// Per-proposal input handed to [`prepare`](Self::prepare) and /// [`propose`](Self::propose). Applications that need no input set this to `()`. type Input: Send; /// Build a block on a parent that has not yet certified, or decline with /// [`Handoff::Wait`]. /// /// The marshal calls this in place of [`Self::propose`] for a term-start proposal whose /// parent is uncertified, with the same `ancestry` and after the same checks. It /// re-proposes the epoch boundary block and declines a parent it cannot build on with /// [`Handoff::Wait`], in both cases without calling this method. The default declines. /// /// With [`Handoff::Vote`] or [`Handoff::Stage`], the marshal keeps the returned block for /// relay as it would a proposal. With [`Handoff::Wait`], consensus waits for parent /// certification before requesting [`Self::propose`] for the same context, unless it has /// voted to nullify the context's view or has left it. The decision is final for the /// request. /// /// With deferred or coded verification, a prepared build can start before this node /// has verified the parent's contents. The parent may later fail certification, /// which discards the candidate. /// /// Parent certification does not cancel a prepared build. Consensus cancels it once the /// parent can no longer be built on before it certifies, as after a nullification in the /// parent's term, or once it votes to nullify the view it is waiting in, at or below the /// parent. Unless it has voted to nullify the proposal's view or has left it, it then /// requests an ordinary proposal for the same context if the parent certifies, or can /// request a proposal on a replacement parent once one is selectable. /// /// [`Handoff::Vote`] trusts the outgoing consensus leader not to equivocate and to /// complete its term (see [`Handoff::Vote`]). The context names the parent by view and /// digest, and its leader field names the incoming leader, not the outgoing one. Identify /// the outgoing leader from the elector's schedule or authenticated metadata for the /// parent's consensus round. A verified parent block can name an earlier proposer in its /// embedded context, as with an epoch-boundary reproposal. If that identity or trust is /// uncertain, return [`Handoff::Stage`], which can relay the block before the parent /// certifies but withholds the vote. /// /// This future may be cancelled before it completes. Implementations must be /// cancellation-safe. /// /// If readiness is uncertain, return [`Handoff::Wait`]. /// /// A wrapper around another application must forward this method, since the default /// would otherwise replace the inner application's choice with [`Handoff::Wait`]. fn prepare( &mut self, _context: (E, Self::Context), _ancestry: impl Ancestry, _input: Self::Input, ) -> impl Future>> + Send { async { Handoff::Wait } } /// Build a new block on top of the provided parent ancestry. If the build job fails, /// or the proposer's slot should be skipped, the implementor should return [None]. /// /// `input` is the per-proposal input for this build. /// /// This future may be cancelled before it completes. Implementations must be /// cancellation-safe. fn propose( &mut self, context: (E, Self::Context), ancestry: impl Ancestry, input: Self::Input, ) -> impl Future>> + Send; /// Verify a block produced by the application's proposer, relative to its ancestry. /// /// This future should not resolve until the implementation can produce a stable verdict. /// Return `false` only when the block is permanently invalid for the supplied context and /// ancestry. If validity may still change as additional information becomes available, /// continue waiting instead of returning `false`. /// /// In other words, to abstain from voting, do not resolve this future yet. Keep it /// pending until the implementation can either prove the block valid, prove it invalid, /// or the consensus engine cancels the request. Abstaining is not represented by a /// special return value. /// /// This future may be cancelled before it completes. Implementations must be /// cancellation-safe. fn verify( &mut self, context: (E, Self::Context), ancestry: impl Ancestry, ) -> impl Future + Send; } });