Skip to main content

tributary_framework/
lib.rs

1#![cfg_attr(docsrs, feature(doc_cfg))]
2#![doc = include_str!("../README.md")]
3#![deny(missing_docs)]
4#![no_std]
5
6use core::{
7  pin::Pin,
8  task::{Poll, Context},
9  num::NonZero,
10  time::Duration,
11};
12extern crate alloc;
13use alloc::boxed::Box;
14extern crate std;
15use std::collections::HashMap;
16
17use futures_core::stream::{Stream as _, FusedStream as _};
18
19use zeroize::Zeroizing;
20use ciphersuite::Ciphersuite;
21use dalek_ff_group::Ristretto;
22
23use serai_db::{Transaction as _, Db};
24
25use ::tendermint::{Signer as _, Network};
26
27mod read_write;
28pub use read_write::*;
29
30/// The specification and implementation of a Merkle tree.
31pub mod merkle;
32use merkle::*;
33
34/// The functionality for transactions.
35pub mod transaction;
36use transaction::{Signed, TransactionKind};
37pub use transaction::Transaction;
38
39/// The functionality for blocks.
40pub mod block;
41pub use block::Block;
42
43pub mod mempool;
44use mempool::{MempoolError, MempoolNetwork, Mempool, MempoolConsumer};
45
46mod blockchain;
47use blockchain::{Reader, Blockchain};
48
49mod tendermint;
50use tendermint::{SignatureScheme, Tendermint};
51pub use tendermint::{AggregateSignature, Commit, Slash};
52
53mod or;
54
55/// A Tendermint consensus message for a Tributary.
56pub type Message<T> =
57  ::tendermint::Message<[u8; 32], [u8; 64], AggregateSignature, ReadWriteAsBorsh<Block<T>>>;
58
59struct AsyncAddToMempool<T> {
60  transaction: T,
61  bypass_rate_limit: bool,
62  response: async_channel::Sender<Result<(), MempoolError>>,
63}
64
65pin_project_lite::pin_project! {
66  struct MempoolFuture<D: Db, T: Transaction, MN: MempoolNetwork<T>> {
67    db: D,
68    #[pin]
69    mempool: Mempool<D, T, MN>,
70    #[pin]
71    mempool_recv: async_channel::Receiver<AsyncAddToMempool<T>>,
72  }
73}
74
75impl<D: Db, T: Transaction, MN: MempoolNetwork<T>> Future for MempoolFuture<D, T, MN> {
76  type Output = ();
77  fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> {
78    let mut projection = self.project();
79
80    let _: Poll<()> = projection.mempool.as_mut().poll(cx);
81    if (!projection.mempool_recv.is_terminated()) &&
82      let Poll::Ready(Some(AsyncAddToMempool { transaction, bypass_rate_limit, response })) =
83        projection.mempool_recv.poll_next(cx)
84    {
85      let mut txn = projection.db.txn();
86      let result = projection.mempool.add(&mut txn, transaction, bypass_rate_limit);
87      txn.commit();
88
89      let _ = response.try_send(result);
90    }
91
92    Poll::Pending
93  }
94}
95
96pin_project_lite::pin_project! {
97  /// An instanced Tributary.
98  ///
99  /// This is a collection of futures which MUST be polled in order for the Tributary to make
100  /// progress. It may be directly polled, acting as a single-threaded sequential executor for each
101  /// of the contained futures, or unrolled via its `IntoIterator` implementation, allowing the
102  /// futures to be individually spawned on an executor.
103  pub struct Tributary<
104    D: Db,
105    T: Transaction,
106    MN: MempoolNetwork<T>,
107    Tendermint = (),
108    Loop = (),
109  > {
110    #[pin]
111    tendermint: Tendermint,
112    #[pin]
113    mempool: MempoolFuture<D, T, MN>,
114    #[pin]
115    inner_loop: Loop,
116  }
117}
118
119impl<
120  D: Db,
121  T: Transaction,
122  MN: MempoolNetwork<T>,
123  Tendermint: Future<Output = ()>,
124  Loop: Future<Output = ()>,
125> Future for Tributary<D, T, MN, Tendermint, Loop>
126{
127  type Output = ();
128  fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> {
129    let projection = self.project();
130
131    let _: Poll<()> = projection.tendermint.poll(cx);
132    let _: Poll<()> = projection.mempool.poll(cx);
133    let _: Poll<()> = projection.inner_loop.poll(cx);
134
135    Poll::Pending
136  }
137}
138
139impl<
140  D: 'static + Send + for<'db> Db<Transaction<'db>: Send>,
141  T: 'static + Send + Transaction,
142  MN: 'static + Send + MempoolNetwork<T>,
143  Tendermint: 'static + Send + Future<Output = ()>,
144  Loop: 'static + Send + Future<Output = ()>,
145> IntoIterator for Tributary<D, T, MN, Tendermint, Loop>
146{
147  type Item = Pin<Box<dyn Send + Future<Output = ()>>>;
148  type IntoIter = <[Self::Item; 3] as IntoIterator>::IntoIter;
149  fn into_iter(self) -> Self::IntoIter {
150    let Self { tendermint, mempool, inner_loop } = self;
151    let tendermint: Self::Item = Box::pin(tendermint);
152    let mempool = Box::pin(mempool);
153    let inner_loop = Box::pin(inner_loop);
154    [tendermint, mempool, inner_loop].into_iter()
155  }
156}
157
158/// An error when instantiating the Tributary.
159#[derive(Debug)]
160pub enum TributaryError {
161  /// The (target) block time wasn't representable.
162  UnrepresentableBlockTime,
163  /// The provided key didn't correspond to a validator.
164  NotValidator,
165}
166
167/// An error when syncing a block.
168pub enum SyncError {
169  /// The block was syntactically invalid.
170  InvalidBlock(block::SyntacticError),
171  /// The commit was invalid.
172  InvalidCommit,
173}
174
175/// A handle to an instanced Tributary.
176#[derive(Clone)]
177pub struct TributaryHandle<D: Db, T: Transaction> {
178  db: D,
179
180  genesis: [u8; 32],
181  block_time: Duration,
182  validator_set: crate::tendermint::ValidatorSet,
183  signature_scheme: SignatureScheme,
184
185  validator: [u8; 32],
186
187  blocks_behind: async_channel::Sender<async_channel::Sender<u64>>,
188
189  sync: async_channel::Sender<(Block<T>, crate::tendermint::Commit)>,
190  message: async_channel::Sender<Message<T>>,
191  mempool: async_channel::Sender<AsyncAddToMempool<T>>,
192  censure: async_channel::Sender<([u8; 32], async_channel::Sender<()>)>,
193
194  next_block_notification: async_channel::Sender<async_channel::Sender<()>>,
195}
196
197impl<
198  D: Send + Sync + for<'db> Db<Transaction<'db>: Send>,
199  T: Send + Sync + Transaction,
200  MN: MempoolNetwork<T>,
201> Tributary<D, T, MN>
202{
203  /// Instance a Tributary.
204  ///
205  /// This MUST be the only Tributary instanced with this `genesis` value. It will be reloaded from
206  /// the database if prior instanced. For further context on the limitations of this, please refer
207  /// to the limitations placed upon [`::tendermint::Tendermint`].
208  ///
209  /// The `genesis` argument will be expanded to a 32-byte genesis by prefixing 16 `0`s.
210  ///
211  /// `genesis_time` is expressed in milliseconds since the epoch and used to limit the minimum
212  /// time blocks may be published with. This prevents a malicious supermajority from backdating
213  /// blocks, allowing flooding the honest minority with valid blocks which still respect the
214  /// minimum spacing between blocks. It is optional as it is not strictly required, but it is
215  /// practically required for resilience against a dishonest supermajority (who can compromise the
216  /// integrity of the Tributary in general). Whatever value is set, it MUST be consistent across
217  /// participants AND reboots.
218  ///
219  /// `validators` represents the validators present in the Tributary (keyed by their Ristretto
220  /// public keys, valued by their weight in the consensus process). It MUST be a valid value for
221  /// the [`::tendermint::ValidatorSet`] trait.
222  ///
223  /// `key` is the validator's Ristretto private key. It MUST be consistent across reboots.
224  ///
225  /// `mempool_rate_limit` is the maximum amount of transactions each validator may have pending
226  /// within the mempool. It MAY be locally configured independently of other validators. It does
227  /// not apply to provided nor unsigned transactions which are privileged within the Tributary.
228  #[expect(clippy::too_many_arguments)]
229  pub async fn new<
230    N: Send
231      + Sync
232      + Network<[u8; 32], [u8; 64], AggregateSignature, ReadWriteAsBorsh<Block<T>>, Sleep: Send>,
233  >(
234    db: D,
235    genesis: [u8; 16],
236    genesis_time: Option<u64>,
237    validators: HashMap<[u8; 32], NonZero<u16>>,
238    tendermint_network: N,
239    mempool_network: MN,
240    key: Zeroizing<<Ristretto as Ciphersuite>::F>,
241    mempool_rate_limit: usize,
242  ) -> Result<
243    (
244      Tributary<D, T, MN, impl Send + Future<Output = ()>, impl Send + Future<Output = ()>>,
245      TributaryHandle<D, T>,
246    ),
247    TributaryError,
248  > {
249    /*
250      Expand the 16-byte genesis DST into a 32-byte 'hash'.
251
252      This isn't considered a hash, solely an element in the same 32-byte domain as a hash
253      (allowing it to be specified as the 'parent' for the first actual block on the blockchain).
254
255      Tendermint allows the genesis to be an arbitrary DST value but the Tributary requires it not
256      collide with an actual block's hash. The following expansion sets the first 16 bytes to `0`,
257      meaning a collision would require 128 bits of effort (as the security of the rest of the
258      cryptography in the Tributary requires).
259    */
260    let genesis = {
261      let mut genesis_32 = [0; 32];
262      genesis_32[16 ..].copy_from_slice(&genesis);
263      genesis_32
264    };
265
266    let genesis_time = genesis_time.unwrap_or(0);
267
268    let target_block_time =
269      N::target_block_time().ok_or(TributaryError::UnrepresentableBlockTime)?;
270
271    // TODO: This is the maximum of the bound internal to the `tendermint-consensus` library
272    let (sync_send, sync_recv) =
273      async_channel::bounded::<(Block<T>, crate::tendermint::Commit)>(64);
274    let (message_send, message_recv) = async_channel::bounded::<
275      ::tendermint::MessageFor<Tendermint<D, T, MempoolConsumer<T>, N>>,
276    >(2 * validators.len());
277
278    let (mempool_send, mempool_recv) =
279      async_channel::bounded::<AsyncAddToMempool<T>>(mempool_rate_limit.max(8));
280
281    let (censure_send, censure_recv) =
282      async_channel::bounded::<([u8; 32], async_channel::Sender<()>)>(validators.len());
283
284    let (mempool, mempool_consumer) = Mempool::new(
285      db.clone(),
286      genesis,
287      validators.keys().copied(),
288      mempool_network,
289      censure_recv,
290      mempool_rate_limit,
291    );
292
293    let (blocks_behind_send, blocks_behind_recv) =
294      async_channel::bounded::<async_channel::Sender<u64>>(1);
295
296    let signature_scheme = SignatureScheme::new(genesis, validators.len());
297    let signer = signature_scheme.signer(key);
298    let validator = signer.validator();
299    if !validators.contains_key(&validator) {
300      Err(TributaryError::NotValidator)?;
301    }
302
303    let (validator_set, next_block_notification, (mut tendermint_handle, tendermint)) = {
304      let blockchain =
305        Blockchain::new(&db, genesis, genesis_time, validators, signature_scheme.clone());
306
307      let (tip, minimum_next_block_time) = {
308        let tip = blockchain.tip(&db);
309        let target_block_time = u64::try_from(target_block_time.as_millis())
310          .map_err(|_| TributaryError::UnrepresentableBlockTime)?;
311        let minimum_next_block_time = tip
312          .as_ref()
313          .map(|tip| tip.time().checked_add(target_block_time))
314          .unwrap_or(Some(genesis_time));
315        let tip = tip.map(|block| block.hash()).unwrap_or(genesis);
316        (tip, minimum_next_block_time)
317      };
318
319      /*
320        In practice, this is bounded by the amount of handles which simultaneously exist,
321        preventing concerns with its memory usage. If the caller did cause this channel to be an
322        effective DoS, it'd be because they've already created an amount of handles which are an
323        effective DoS.
324      */
325      let (next_block_notification_send, next_block_notification_recv) =
326        async_channel::unbounded::<async_channel::Sender<()>>();
327
328      let mut tendermint = Tendermint::<_, _, _, N>::new(
329        db.clone(),
330        genesis,
331        blockchain,
332        next_block_notification_recv,
333        mempool_consumer,
334      );
335      let validator_set = {
336        use ::tendermint::Blockchain as _;
337        tendermint.validator_set().clone()
338      };
339      let proposal = tendermint.block_proposal(tip, minimum_next_block_time, 0);
340
341      (
342        validator_set,
343        next_block_notification_send,
344        ::tendermint::Tendermint::process(
345          tendermint,
346          signer,
347          db.clone(),
348          tendermint_network,
349          proposal,
350        )
351        .await,
352      )
353    };
354
355    let inner_loop = async move {
356      loop {
357        if let Err(::tendermint::ProcessTerminated) = match (or::Or {
358          f1: or::Or { f1: sync_recv.recv(), f2: message_recv.recv() },
359          f2: blocks_behind_recv.recv(),
360        })
361        .await
362        {
363          or::Either::L(or::Either::L(Ok((block, commit)))) => {
364            tendermint_handle.sync(ReadWriteAsBorsh(block), commit).await
365          }
366          or::Either::L(or::Either::R(Ok(message))) => tendermint_handle.message(message).await,
367
368          or::Either::R(Ok(blocks_behind)) => {
369            // Ignore the error in case the future was cancelled
370            let _ = blocks_behind.try_send({
371              let observed_block_number = u64::from(tendermint_handle.observed_block_number());
372              let block_number = u64::from(tendermint_handle.block_number());
373              observed_block_number.saturating_sub(block_number)
374            });
375            Ok(())
376          }
377
378          // If all of the handles were dropped, we consider the process terminated
379          or::Either::L(or::Either::L(Err(_)) | or::Either::R(Err(_))) | or::Either::R(Err(_)) => {
380            Err(::tendermint::ProcessTerminated)
381          }
382        } {
383          // TODO: Never
384          core::future::pending::<()>().await;
385        }
386      }
387    };
388
389    Ok((
390      Tributary {
391        tendermint,
392        mempool: MempoolFuture { db: db.clone(), mempool, mempool_recv },
393        inner_loop,
394      },
395      TributaryHandle {
396        db,
397
398        genesis,
399        block_time: target_block_time,
400        validator_set,
401        signature_scheme,
402
403        validator,
404
405        blocks_behind: blocks_behind_send,
406
407        sync: sync_send,
408        message: message_send,
409        mempool: mempool_send,
410        censure: censure_send,
411
412        next_block_notification,
413      },
414    ))
415  }
416}
417
418impl<D: Db, T: Transaction> TributaryHandle<D, T> {
419  /// The Tributary's genesis.
420  pub fn genesis(&self) -> [u8; 32] {
421    self.genesis
422  }
423
424  /// The Tributary's target block time.
425  pub fn block_time(&self) -> Duration {
426    self.block_time
427  }
428
429  /// The Tributary's tip block.
430  ///
431  /// This is read from the database and is accordingly the last _committed_ block.
432  pub fn tip(&self) -> Option<[u8; 32]> {
433    Reader::<T>::tip(&self.db, self.genesis)
434  }
435
436  /// The amount of blocks the local Tributary is missing in comparison to the current consensus
437  /// efforts.
438  ///
439  /// This is derivative of [`::tendermint::TendermintHandle::observed_block_number`], a method
440  /// which allows the local process to observe the block validators are obtaining consensus over.
441  /// It is not intended to be an explicit counter of the amount of blocks to explicitly sync,
442  /// solely a hint.
443  pub async fn blocks_behind(&self) -> u64 {
444    let (send, recv) = async_channel::bounded(1);
445    let _ = self.blocks_behind.send(send).await;
446    match recv.recv().await {
447      Ok(blocks_behind) => blocks_behind,
448      Err(_) => core::future::pending().await,
449    }
450  }
451
452  /// A block on the Tributary, identified by its hash.
453  ///
454  /// This returns `None` if the block wasn't committed on this Tributary.
455  pub fn block(&self, hash: [u8; 32]) -> Option<Block<T>> {
456    Reader::<T>::block(&self.db, self.genesis, hash)
457  }
458  /// The commit for a block on the Tributary.
459  ///
460  /// This returns `None` if no commit was saved for this block.
461  pub fn commit(&self, block: [u8; 32]) -> Option<crate::tendermint::Commit> {
462    crate::tendermint::db_commit(&self.db, self.genesis, block)
463  }
464  /// The block after a block on the Tributary.
465  ///
466  /// This returns `None` if either:
467  /// - The parent block (identified by its hash) wasn't committed on this Tributary
468  /// - It has no child block committed on the Tributary
469  pub fn block_after(&self, parent: [u8; 32]) -> Option<[u8; 32]> {
470    Reader::<T>::block_after(&self.db, self.genesis, parent)
471  }
472
473  /// The hashes of locally provided transactions.
474  pub fn locally_provided_transactions(
475    &self,
476    scope: &'static str,
477    start: u64,
478  ) -> impl Iterator<Item = [u8; 32]> {
479    mempool::ProvidedReader::<T>::locally_provided(&self.db, self.genesis, scope, start)
480  }
481
482  /// Handle a consensus message.
483  ///
484  /// This will return once the message has been queued to be handled, offering no inspection
485  /// into when that queue is consumed or if the queued message was valid.
486  pub async fn message(&self, message: Message<T>) {
487    /*
488      Queueing into an open channel (with no observability into when the queue is consumed from) is
489      considered equivalent to not queueing into a closed channel (a queue which will never be
490      consumed from). All values are still handled in order, without omission, whenever (or if
491      ever) handled. This lets us igore any error here.
492    */
493    let _ = self.message.send(message).await;
494  }
495
496  /// Explicitly sync a block.
497  ///
498  /// This is intended to be used when a Tributary is behind, unable to simply observe blocks as
499  /// they're produced by the consensus process.
500  ///
501  /// The block's _syntax_ and the commit is immediately validated. Therefore, this block is either
502  /// valid, semantically invalid, or ephemerally invalid. Assuming honest behavior, this block
503  /// will be semantically valid (due to the commit by a supermajority of validators finalizing
504  /// it) though. This assumption allows simplifying that this function either returns an error or:
505  /// 1) The block was already added
506  /// 2) The block is not ready to be added (due to missing parent blocks)
507  /// 3) The block will be added
508  ///
509  /// This function only queues the block to be added (if verified to be syntactically valid, with
510  /// a valid commit). This function offers no inspection into when that queue is consumed or if
511  /// the queued block was entirely valid.
512  pub async fn sync(
513    &self,
514    block: Block<T>,
515    commit: crate::tendermint::Commit,
516  ) -> Result<(), SyncError> {
517    if !commit.verify(&self.validator_set, &self.signature_scheme, &self.genesis, block.hash()) {
518      Err(SyncError::InvalidCommit)?;
519    }
520    let () = block.verify_syntax(self.genesis).map_err(SyncError::InvalidBlock)?;
521
522    /*
523      Queueing into an open channel (with no observability into when the queue is consumed from) is
524      considered equivalent to not queueing into a closed channel (a queue which will never be
525      consumed from). All values are still handled in order, without omission, whenever (or if
526      ever) handled. This lets us igore any error here.
527    */
528    let _ = self.sync.send((block, commit)).await;
529
530    Ok(())
531  }
532
533  /// Publish a transaction into the Tributary's mempool.
534  ///
535  /// This is used to publish a transaction, regardless of its kind. `Provided` transactions are
536  /// intended to only be provided by the local node however, meaning the caller MUST check the
537  /// kind of a transaction and its origin _before_ calling this method.
538  ///
539  /// The mempool's rate limit will be bypassed if the transaction's signer is the Tributary's
540  /// validator, ensuring the local validator can publish their own transactions without needing to
541  /// implement an additional buffer.
542  pub async fn transaction(&self, transaction: T) -> Result<(), MempoolError> {
543    let bypass_rate_limit =
544      if let TransactionKind::Signed { signed: Signed { signer, .. }, .. } = transaction.kind() {
545        signer == self.validator
546      } else {
547        true
548      };
549
550    let (response_send, response_recv) = async_channel::bounded(1);
551    let _ = self
552      .mempool
553      .send(AsyncAddToMempool { transaction, bypass_rate_limit, response: response_send })
554      .await;
555    match response_recv.recv().await {
556      Ok(result) => result,
557      /*
558        If the channel was closed, the mempool was dropped, and this publication won't occur.
559
560        We yield `Pending` infinitely to reflect how this publication will never be ready. While
561        the alternative would to be return an error, we presume that applications won't drop the
562        mempool, letting us simplify the API a bit.
563      */
564      Err(_) => core::future::pending().await,
565    }
566  }
567
568  /// Censure a validator.
569  ///
570  /// This will prevent voting for block proposals from this validator and not populate their
571  /// transactions within the mempool. It only applies to the local view and doesn't have to
572  /// performed in any synchrony with other validators.
573  pub async fn censure(&self, validator: [u8; 32]) {
574    let (censured_send, censured_recv) = async_channel::bounded::<()>(1);
575    let _ = self.censure.send((validator, censured_send)).await;
576    match censured_recv.recv().await {
577      Ok(()) => {}
578      /*
579        If the channel was closed, this validator won't have the censure applied, so this function
580        should never return (signifying the censure was applied).
581
582        We _could_ also propagate an error to signify the Tributary is no longer running, but it
583        isn't worth the API complexity.
584      */
585      Err(_) => core::future::pending().await,
586    }
587  }
588
589  /// A future which resolves when the next block is added to the Tributary.
590  pub fn next_block_notification(&self) -> impl Send + Future<Output = ()> {
591    let (next_block_notification_send, next_block_notification_recv) =
592      async_channel::bounded::<()>(1);
593    let _ = self.next_block_notification.try_send(next_block_notification_send);
594    async move {
595      match next_block_notification_recv.recv().await {
596        Ok(()) => {}
597        /*
598          If the channel was closed, there won't be any more blocks added, so this notification
599          should never resolve.
600
601          We _could_ also propagate an error to signify the Tributary is no longer running, but it
602          isn't worth the API complexity.
603        */
604        Err(_) => core::future::pending().await,
605      }
606    }
607  }
608}