Skip to main content

tendermint_consensus/
lib.rs

1#![cfg_attr(docsrs, feature(doc_cfg))]
2#![doc = include_str!("../README.md")]
3#![deny(missing_docs)]
4#![no_std]
5
6#[cfg(feature = "alloc")]
7extern crate alloc;
8#[cfg(feature = "std")]
9extern crate std;
10
11use core::{time::Duration, future::Future};
12
13mod or;
14use or::*;
15
16mod timeout;
17use timeout::*;
18
19mod validators;
20pub use validators::*;
21
22mod commit;
23pub use commit::*;
24
25mod blockchain;
26pub use blockchain::*;
27
28mod message;
29pub use message::*;
30
31mod slash_reason;
32pub use slash_reason::*;
33
34#[cfg(feature = "std")]
35mod state;
36#[cfg(feature = "std")]
37use state::*;
38
39/// A view over the network used for consensus.
40pub trait Network<V: Validator, S: Signature, A: AggregateSignature, B: Block> {
41  /// The expected average-case latency of the network.
42  ///
43  /// This should be sufficient for a supermajority of validators to communicate, in the average
44  /// case, as necessary to perform the consensus protocol. If the real-world latency exceeds this
45  /// amount of time, the attempt to finalize a block will fail, and a new round will begin with an
46  /// increased amount of latency. Accordingly, setting this to too optimistic of a value will
47  /// increase the amount of failures.
48  ///
49  /// The derivatives of this MAY be limited to the bounds of the internal representations used for
50  /// time.
51  const LATENCY_TIME: Duration;
52
53  /// The expected maximum amount of time to download a block.
54  ///
55  /// The derivatives of this MAY be limited to the bounds of the internal representations used for
56  /// time.
57  const BLOCK_DOWNLOADING_TIME: Duration;
58
59  /// The expected maximum amount of time to process a block.
60  ///
61  /// This is also used as a timeout for fetching the block proposal, if it isn't ready yet.
62  ///
63  /// The derivatives of this MAY be limited to the bounds of the internal representations used for
64  /// time.
65  const BLOCK_PROCESSING_TIME: Duration;
66
67  /// The target block time.
68  ///
69  /// This MUST NOT be overriden. It is a function of the constants for timings.
70  ///
71  /// This will return `None` if the resulting `Duration` isn't representable.
72  fn target_block_time() -> Option<Duration> {
73    Self::BLOCK_DOWNLOADING_TIME
74      .checked_add(Self::BLOCK_PROCESSING_TIME)?
75      .checked_add(Self::LATENCY_TIME.checked_mul(3)?)
76  }
77
78  /// The future returned by [`Network::sleep`].
79  type Sleep: Future<Output = ()>;
80
81  /// An asynchronous implementation of [`std::thread::sleep`].
82  ///
83  /// This MUST be cancel-safe.
84  fn sleep(duration: Duration) -> Self::Sleep;
85
86  /// Broadcast a message to the other validators.
87  ///
88  /// Examples of broadcast include sending this message via peer-to-peer channels to all other
89  /// validators, or publishing this message to a gossip network where it can be reasonably assumed
90  /// to be delivered to all other validators. It does not have to achieve a formal definition of
91  /// broadcast with any specific security properties, though failure for this message to be
92  /// delivered to a sufficient amount of other validators in a timely fashion will cause consensus
93  /// to stall until the timeout for a round exceeds the latency of this network.
94  ///
95  /// This DOES NOT have to be cancel-safe.
96  fn broadcast(
97    &mut self,
98    genesis: impl AsRef<[u8]>,
99    message: Message<V, S, A, B>,
100  ) -> impl Send + Future<Output = ()>;
101}
102
103#[cfg(feature = "std")]
104mod tendermint {
105  use core::{
106    sync::atomic::{Ordering, AtomicU64},
107    future::Future,
108    num::NonZero,
109  };
110  use alloc::sync::Arc;
111
112  /*
113    We use `async-channel`, not `futures-channel`, as neither document/guarantee cancel safety.
114    However, `async-channel` has [this issue](https://github.com/smol-rs/async-channel/issues/111)
115    for which notgull confirms [`async_channel::Recv`] is cancel-safe:
116
117    https://github.com/smol-rs/async-channel/issues/111#issuecomment-3459124415
118
119    We expect this property, causing us to use `async-channel`.
120  */
121  use async_channel::{Sender, Receiver};
122
123  use borsh::{BorshSerialize, BorshDeserialize};
124  use serai_db::{Transaction as _, Db};
125
126  use crate::{
127    BlockNumber, ValidatorSet as _, SignatureScheme, Block, CommitFor, Blockchain, MessageFor,
128    MessageError, Signer, Network, State, Or,
129  };
130
131  /// The Tendermint process.
132  ///
133  /// This is expected to drive the underlying blockchain, adding blocks to it as produced by
134  /// itself _and as received from an external sync loop_ (which is not implemented here).
135  pub struct Tendermint;
136
137  /// The handle for the Tendermint process.
138  pub struct TendermintHandle<B: Blockchain> {
139    block_number: Arc<AtomicU64>,
140    observed_block_number: Arc<AtomicU64>,
141    sync: Sender<(B::Block, CommitFor<B>)>,
142    message: Sender<MessageFor<B>>,
143  }
144
145  struct TendermintProcess<B: Blockchain, S, D, N> {
146    sync: Receiver<(B::Block, CommitFor<B>)>,
147    message: Receiver<MessageFor<B>>,
148
149    state: State<B>,
150    blockchain: B,
151    signer: S,
152    db: D,
153    network: N,
154  }
155
156  impl<
157    B: Blockchain<
158        Validator: BorshSerialize + BorshDeserialize,
159        SignatureScheme: SignatureScheme<
160          Signature: BorshSerialize + BorshDeserialize,
161          AggregateSignature: BorshSerialize + BorshDeserialize,
162        >,
163        Block: BorshSerialize + BorshDeserialize + Block<Hash: BorshSerialize + BorshDeserialize>,
164      >,
165    S: Signer<
166        Validator = B::Validator,
167        Signature = <B::SignatureScheme as SignatureScheme>::Signature,
168      >,
169    D: Db,
170    N: Network<
171        B::Validator,
172        <B::SignatureScheme as SignatureScheme>::Signature,
173        <B::SignatureScheme as SignatureScheme>::AggregateSignature,
174        B::Block,
175      >,
176  > TendermintProcess<B, S, D, N>
177  {
178    async fn run(mut self) {
179      let mut progress = true;
180      loop {
181        /*
182          Attempt to form a commit.
183
184          We do this first in case the process was interrupted while prior attempting a commit.
185        */
186        if progress {
187          let mut txn = self.db.txn();
188          let messages =
189            self.state.attempt_commit::<N>(&mut self.blockchain, &self.signer, &mut txn).await;
190          txn.commit();
191
192          for message in messages {
193            self.network.broadcast(self.blockchain.genesis(), message).await;
194          }
195        }
196        // Assume we made progress on each iteration of this loop
197        progress = true;
198
199        /*
200          We use our `Or` future to implement a select, where our `Or` is documented to prefer `f1`
201          to `f2`, causing these to be polled in the order they're written.
202
203          Receiving from the channels is cancel-safe, as is our own future to check for timeouts.
204        */
205        let tick = (Or {
206          f1: Or {
207            // Check for a synced block, which makes this entire consensus process immaterial
208            f1: self.sync.recv(),
209            /*
210              Check if any timeouts have expired.
211
212              We give this priority so if we reload from the database, this is consistently handled
213              independent of any messages are available.
214            */
215            f2: self.state.timeout::<N, _>(&mut self.blockchain, &self.signer),
216          },
217          // Check for a received message, which may advance this consensus process
218          f2: self.message.recv(),
219        })
220        .await;
221
222        match tick {
223          crate::or::Either::L(crate::or::Either::L(Ok((block, commit)))) => {
224            if (commit.block_number != self.state.block_number()) ||
225              (!commit.verify(
226                self.blockchain.validator_set(),
227                self.blockchain.signature_scheme(),
228                self.blockchain.genesis(),
229                block.semantic_hash(),
230              ))
231            {
232              progress = false;
233              continue;
234            }
235
236            let mut txn = self.db.txn();
237            let messages = self
238              .state
239              .commit::<N>(&mut self.blockchain, &self.signer, &mut txn, block, commit)
240              .await;
241            txn.commit();
242
243            for message in messages {
244              self.network.broadcast(self.blockchain.genesis(), message).await;
245            }
246          }
247
248          /*
249            We do not have to interact with the database here as, on reboot, these timeouts will
250            immediately expire and cause this behavior to occur once again (as this future has
251            priority over incoming messages).
252          */
253          crate::or::Either::L(crate::or::Either::R(timeout)) => {
254            let mut txn = self.db.txn();
255            let messages = timeout.respond::<N>(&mut txn).await;
256            txn.commit();
257
258            for message in messages {
259              self.network.broadcast(self.blockchain.genesis(), message).await;
260            }
261          }
262
263          crate::or::Either::R(Ok(message)) => {
264            let mut txn = self.db.txn();
265            let validator = message.validator;
266            match self
267              .state
268              .message::<N>(&mut self.blockchain, &self.signer, &mut txn, message)
269              .await
270            {
271              Ok(messages) => {
272                txn.commit();
273                for message in messages {
274                  self.network.broadcast(self.blockchain.genesis(), message).await;
275                }
276              }
277              Err(MessageError::Invalid(slash_reason)) => {
278                self.blockchain.slash(validator, slash_reason);
279                progress = false;
280                continue;
281              }
282              Err(
283                MessageError::Stale |
284                MessageError::Future |
285                MessageError::NotValidator |
286                MessageError::InvalidOuterSignature |
287                MessageError::FatalProposal |
288                MessageError::AlreadyHandled,
289              ) => {
290                progress = false;
291                continue;
292              }
293            }
294          }
295          // If our channels have been closed, terminate the consensus process
296          crate::or::Either::L(crate::or::Either::L(Err(async_channel::RecvError))) |
297          crate::or::Either::R(Err(async_channel::RecvError)) => return,
298        }
299      }
300    }
301  }
302
303  /// The Tendermint process was terminated.
304  ///
305  /// This occurs when the future terminates, either due to being itself dropped or due to its
306  /// handle being dropped.
307  #[derive(Debug)]
308  pub struct ProcessTerminated;
309
310  impl Tendermint {
311    async fn internal<
312      B: Blockchain<
313          Validator: BorshSerialize + BorshDeserialize,
314          SignatureScheme: SignatureScheme<
315            Signature: BorshSerialize + BorshDeserialize,
316            AggregateSignature: BorshSerialize + BorshDeserialize,
317          >,
318          Block: BorshSerialize + BorshDeserialize + Block<Hash: BorshSerialize + BorshDeserialize>,
319        >,
320      S: Signer<
321          Validator = B::Validator,
322          Signature = <B::SignatureScheme as SignatureScheme>::Signature,
323        >,
324      D: Db,
325      N: Network<
326          B::Validator,
327          <B::SignatureScheme as SignatureScheme>::Signature,
328          <B::SignatureScheme as SignatureScheme>::AggregateSignature,
329          B::Block,
330        >,
331    >(
332      mut blockchain: B,
333      signer: S,
334      mut db: D,
335      mut network: N,
336      proposal: B::BlockProposal,
337    ) -> (TendermintHandle<B>, TendermintProcess<B, S, D, N>) {
338      // Sync blocks with a capacity of the amount of blocks per 5 minutes
339      let (sync_send, sync_recv) = async_channel::bounded({
340        use core::time::Duration;
341        let blocks_per_five_minutes = if let Some(target_block_time) = N::target_block_time() {
342          Duration::from_mins(5).as_millis().div_ceil(target_block_time.as_millis().max(1))
343        } else {
344          1
345        };
346        // Limit this to a sane range
347        usize::try_from(blocks_per_five_minutes).unwrap_or(usize::MAX).clamp(1, 64)
348      });
349
350      /*
351        Limit the amount of messages proportionally to the amount of validators.
352
353        So long as validators are honest and only send one message within a period, this bound
354        will only be hit if either:
355        1) Messages aren't drained faster than the network's declared latency time
356        2) This validators is slower than the supermajority of validators
357        where either cases are reasonable to establish the bound regarding.
358
359        We do further scale the capacity by `2` to handle _some_ overages.
360      */
361      let (message_send, message_recv) =
362        async_channel::bounded(2 * blockchain.validator_set().validators().into_iter().count());
363
364      let mut txn = db.txn();
365      let (state, messages) = State::new::<N>(&mut blockchain, &signer, &mut txn, proposal).await;
366      txn.commit();
367
368      for message in messages {
369        network.broadcast(blockchain.genesis(), message).await;
370      }
371
372      (
373        TendermintHandle {
374          block_number: state.block_number_ref(),
375          observed_block_number: state.observed_block_number_ref(),
376          sync: sync_send,
377          message: message_send,
378        },
379        (TendermintProcess {
380          sync: sync_recv,
381          message: message_recv,
382
383          state,
384          blockchain,
385          signer,
386          db,
387          network,
388        }),
389      )
390    }
391
392    /// Initialize the Tendermint process.
393    ///
394    /// The returned future will run until its corresponding channels are closed. The future is NOT
395    /// cancel-safe, and will leave an undefined state in memory if cancelled. It MUST be polled
396    /// until either:
397    /// 1) It is of no further use, and accordingly its state may be undefined
398    /// 2) The process terminates, so that the Tendermint process will be re-initialized from the
399    ///    disk before any further use
400    ///
401    /// This MAY exhibit undefined behavior if the `signer` is not consistent across instances, or
402    /// if multiple instances with the same `genesis` value are spawned at once.
403    pub fn process<
404      B: Send
405        + Sync
406        + Blockchain<
407          Validator: Send + Sync + BorshSerialize + BorshDeserialize,
408          ValidatorSet: Sync,
409          SignatureScheme: SignatureScheme<
410            Signature: Send + BorshSerialize + BorshDeserialize,
411            AggregateSignature: Send + BorshSerialize + BorshDeserialize,
412          >,
413          Genesis: Sync,
414          Block: Send
415                   + Sync
416                   + BorshSerialize
417                   + BorshDeserialize
418                   + Block<Hash: Send + BorshSerialize + BorshDeserialize>,
419          BlockProposal: Send,
420        >,
421      S: Send
422        + Sync
423        + Signer<
424          Validator = B::Validator,
425          Signature = <B::SignatureScheme as SignatureScheme>::Signature,
426          SignFuture: Send,
427        >,
428      D: Send + for<'db> Db<Transaction<'db>: Send>,
429      N: Send
430        + Network<
431          B::Validator,
432          <B::SignatureScheme as SignatureScheme>::Signature,
433          <B::SignatureScheme as SignatureScheme>::AggregateSignature,
434          B::Block,
435          Sleep: Send,
436        >,
437    >(
438      blockchain: B,
439      signer: S,
440      db: D,
441      network: N,
442      proposal: B::BlockProposal,
443    ) -> impl Send + Future<Output = (TendermintHandle<B>, impl Send + Future<Output = ()>)> {
444      async move {
445        let (handle, process) = Self::internal(blockchain, signer, db, network, proposal).await;
446        (handle, process.run())
447      }
448    }
449
450    /// A variant of [`Tendermint::process`] which supports `!Send`, `!Sync` arguments.
451    ///
452    /// This is intended to enable support for single-threaded runtimes which do not require such
453    /// bounds.
454    #[expect(clippy::manual_async_fn)]
455    pub fn process_single_threaded<
456      B: Blockchain<
457          Validator: BorshSerialize + BorshDeserialize,
458          SignatureScheme: SignatureScheme<
459            Signature: BorshSerialize + BorshDeserialize,
460            AggregateSignature: BorshSerialize + BorshDeserialize,
461          >,
462          Block: BorshSerialize + BorshDeserialize + Block<Hash: BorshSerialize + BorshDeserialize>,
463        >,
464      S: Signer<
465          Validator = B::Validator,
466          Signature = <B::SignatureScheme as SignatureScheme>::Signature,
467        >,
468      D: Db,
469      N: Network<
470          B::Validator,
471          <B::SignatureScheme as SignatureScheme>::Signature,
472          <B::SignatureScheme as SignatureScheme>::AggregateSignature,
473          B::Block,
474        >,
475    >(
476      blockchain: B,
477      signer: S,
478      db: D,
479      network: N,
480      proposal: B::BlockProposal,
481    ) -> impl Future<Output = (TendermintHandle<B>, impl Future<Output = ()>)> {
482      async move {
483        let (handle, process) = Self::internal(blockchain, signer, db, network, proposal).await;
484        (handle, process.run())
485      }
486    }
487  }
488
489  impl<B: Blockchain> TendermintHandle<B> {
490    /// The number for the block we're currently attempting to achieve consensus over.
491    ///
492    /// This is implemented in a lock-free manner and MAY momentarily desynchronize from the block
493    /// number internal to the Tendermint process, or the blockchain, accordingly.
494    pub fn block_number(&self) -> BlockNumber {
495      BlockNumber(
496        NonZero::new(self.block_number.load(Ordering::Acquire))
497          .expect("block number was corrupted"),
498      )
499    }
500
501    /// The greatest block number we've observed validators attempting to achieve consensus over.
502    ///
503    /// This is the greatest block number which `f + 1` validators have been observed to be
504    /// attempting to obtain consensus over, meaning there presumably is consensus over all prior
505    /// blocks (or the amount of faulty validators exceeds the fault threshold). This is intended
506    /// to be used to allow the larger application to realize it should explicitly sync up to this
507    /// block (as this library does not implement a block sync loop itself).
508    ///
509    /// This is implemented in a lock-free manner and MAY momentarily desynchronize from other
510    /// representations of the state accordingly. A best-effort attempt is made to ensure this will
511    /// always be greater than or equal to the value yielded by [`TendermintHandle::block_number`]
512    /// but this is not guaranteed.
513    pub fn observed_block_number(&self) -> BlockNumber {
514      BlockNumber(
515        NonZero::new(self.observed_block_number.load(Ordering::Acquire))
516          .expect("observed block number was corrupted"),
517      )
518    }
519
520    /// Sync a block by its commit.
521    ///
522    /// The Tendermint implementation will validate the commit as necessary.
523    ///
524    /// This function returns `Ok(())` if the Tendermint process is still running and `Err(())`
525    /// otherwise. This function implements backpressure and will wait until the process has the
526    /// capacity to receive this.
527    pub async fn sync(
528      &mut self,
529      block: B::Block,
530      commit: CommitFor<B>,
531    ) -> Result<(), ProcessTerminated> {
532      self.sync.send((block, commit)).await.map_err(|_| ProcessTerminated)
533    }
534
535    /// Handle a message received from the network.
536    ///
537    /// The Tendermint implementation will validate the message as necessary.
538    ///
539    /// This function returns `Ok(())` if the Tendermint process is still running and `Err(())`
540    /// otherwise. This function implements backpressure and will wait until the process has the
541    /// capacity to receive this.
542    pub async fn message(&mut self, message: MessageFor<B>) -> Result<(), ProcessTerminated> {
543      self.message.send(message).await.map_err(|_| ProcessTerminated)
544    }
545  }
546}
547#[cfg(feature = "std")]
548pub use tendermint::*;