Skip to main content

tributary_framework/mempool/
mod.rs

1//! The mempool for a Tributary.
2//!
3//! This is distinguished into the mempool for provided transactions and the mempool for (un)signed
4//! transactions due to the difference in semantics between them.
5//!
6//! Both mempools are implemented with the same pattern.
7//! - Transactions may be added into the mempool by a mutable reference.
8//! - The mempool may be polled to respond to requests for block proposals and handle the addition
9//!   of new blocks.
10//!
11//! This avoids requiring any locks over the mempool's state between the application layer and the
12//! blockchain.
13
14use core::{
15  pin::Pin,
16  task::{Poll, Context},
17};
18use alloc::{boxed::Box, collections::BTreeSet};
19
20use futures_core::stream::{Stream as _, FusedStream as _};
21
22use serai_db::{Db, Get, Transaction as DbTxn};
23
24use crate::transaction::{TransactionError, TransactionKind, Transaction};
25
26serai_db::schema!(TributaryMempool {
27  // The last block this mempool has handled.
28  LastBlock: (genesis: [u8; 32]) -> [u8; 32],
29});
30
31serai_db::channel!(TributaryMempool {
32  // Validators to censure.
33  Censure: (genesis: [u8; 32]) -> [u8; 32],
34});
35
36/// An error within the mempool.
37#[derive(Clone, Debug)]
38pub enum MempoolError {
39  /// The transaction was invalid.
40  Invalid(TransactionError),
41  /// The transaction was already present within the mempool or on-chain.
42  AlreadyPresent,
43  /// The transaction conflicts with a transaction already present within the mempool or on-chain.
44  Conflict,
45  /// The signer has too many pre-existing transactions in the mempool.
46  RateLimit,
47}
48
49impl From<TransactionError> for MempoolError {
50  fn from(error: TransactionError) -> MempoolError {
51    MempoolError::Invalid(error)
52  }
53}
54
55/// The mempool for provided transactions.
56mod provided;
57use provided::*;
58pub(crate) use provided::ProvidedReader;
59
60/// The mempool for (un)signed transactions.
61mod un_signed;
62use un_signed::*;
63
64/// The network for the mempool.
65pub trait MempoolNetwork<T: Transaction> {
66  /// Gossip an (un)signed transaction.
67  ///
68  /// The mempool will automatically re-gossip transactions which have yet to be included on-chain.
69  /// Accordingly, this gossip layer SHOULD have some layer of intelligence, being able to
70  /// de-duplicate and rate-limit gossiped transactions (in case the mempool is over-eager).
71  fn gossip(&mut self, genesis: [u8; 32], transaction: T);
72}
73
74/// A stub implementation which does not implement any gossip functionality.
75///
76/// This likely SHOULD NOT be used.
77impl<T: Transaction> MempoolNetwork<T> for () {
78  fn gossip(&mut self, _genesis: [u8; 32], _transaction: T) {}
79}
80
81pin_project_lite::pin_project! {
82  /// The mempool for a Tributary.
83  ///
84  /// This MUST be polled to respond to requests for block proposals.
85  pub(crate) struct Mempool<D: Db, T: Transaction, N: MempoolNetwork<T>> {
86    db: D,
87    genesis: [u8; 32],
88
89    last_block: [u8; 32],
90    provided: Provided<T>,
91    un_signed: UnSigned<T>,
92
93    network: N,
94    regossip: usize,
95
96    // Asynchronous censures.
97    #[pin]
98    censure: async_channel::Receiver<([u8; 32], async_channel::Sender<()>)>,
99    // The requests for block proposals.
100    #[pin]
101    request: async_channel::Receiver<([u8; 32], async_channel::Sender<Box<[T]>>)>,
102    // A way to re-send requests for block proposals.
103    //
104    // `async_channel::Receiver` doesn't offer a `peek` function. If we aren't available to
105    // service a request, we simply re-send the request message to handle it later, using the
106    // channel itself as the buffer.
107    #[pin]
108    resend_request: async_channel::WeakSender<([u8; 32], async_channel::Sender<Box<[T]>>)>,
109  }
110}
111
112impl<D: Db, T: Transaction, N: MempoolNetwork<T>> Future for Mempool<D, T, N> {
113  type Output = ();
114  fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> {
115    let mut projection = self.project();
116
117    // Index the blocks added on-chain
118    if let Some(block) =
119      crate::Reader::<T>::block_after(projection.db, *projection.genesis, *projection.last_block)
120    {
121      let block = crate::Reader::<T>::block(projection.db, *projection.genesis, block)
122        .expect("block after last block wasn't saved to database");
123
124      let mut txn = projection.db.txn();
125      LastBlock::set(&mut txn, *projection.genesis, &block.hash());
126      projection.provided.block(&mut txn, &block);
127      projection.un_signed.block(&mut txn, &block);
128      txn.commit();
129
130      *projection.last_block = block.hash();
131
132      /*
133        If we have transactions which weren't included in this block, pick some to gossip again.
134
135        TODO: This is fine as a naïve solution, technically increasing the odds transactions only
136        in this mempool are eventually included in a block (without requiring this mempool itself
137        provide a block proposal). It's still an incredibly naïve solution which practically
138        requires the gossip layer de-duplicate and rate limit transactions. That leaves the
139        question of if it would be better to defer this out of the mempool entirely, leaving it to
140        the application.
141
142        The Tendermint module does have a `Mempool` trait intended to allow such modularity. That
143        design isn't exposed at this time however.
144      */
145      {
146        let outstanding_un_signed_transactions = projection.un_signed.block_proposal().count();
147        let transactions_to_regossip = outstanding_un_signed_transactions.isqrt().isqrt().max(1);
148        if let Some(start) = projection.regossip.checked_rem(outstanding_un_signed_transactions) {
149          let end = start.saturating_add(transactions_to_regossip);
150          let range = start .. end;
151          for (i, transaction) in projection.un_signed.block_proposal().enumerate() {
152            if range.contains(&i) ||
153              i.checked_add(outstanding_un_signed_transactions)
154                .is_some_and(|i| range.contains(&i))
155            {
156              projection.network.gossip(*projection.genesis, transaction.clone());
157            }
158          }
159          *projection.regossip = projection.regossip.wrapping_add(transactions_to_regossip);
160        }
161      }
162
163      /*
164        Yield after indexing a block.
165
166        In order to ensure this future is polled again, this task is immediately woken back up.
167        [`core::task::Waker::wake`] guarantees this call happens _before_ the following
168        [`Future::poll`] invocation, allowing a task to wake itself to implement a yield.
169      */
170      cx.waker().wake_by_ref();
171      return Poll::Pending;
172    }
173
174    // Handle asynchronous censures
175    while (!projection.censure.is_terminated()) &&
176      let Poll::Ready(Some((validator, response))) = projection.censure.as_mut().poll_next(cx)
177    {
178      let mut txn = projection.db.txn();
179      projection.un_signed.censure(&mut txn, validator);
180      txn.commit();
181      let _ = response.try_send(());
182    }
183    // Handle synchronous censures
184    {
185      let mut txn = projection.db.txn();
186      while let Some(validator) = Censure::try_recv(&mut txn, *projection.genesis) {
187        projection.un_signed.censure(&mut txn, validator);
188      }
189      txn.commit();
190    }
191
192    // Receive requests for block proposals
193    if (!projection.request.is_terminated()) &&
194      let Poll::Ready(Some((parent, response))) = projection.request.poll_next(cx)
195    {
196      if parent == *projection.last_block {
197        // Respond to a request for a block proposal with all transactions in our mempool
198        let _ = response.try_send(
199          projection
200            .provided
201            .block_proposal()
202            .chain(projection.un_signed.block_proposal())
203            .cloned()
204            .collect::<Box<[_]>>(),
205        );
206      } else if let Some(resend_request) = projection.resend_request.upgrade() {
207        // If this proposal isn't building on our latest indexed block, try to re-queue the request
208        let _ = resend_request.try_send((parent, response));
209      }
210    }
211
212    Poll::Pending
213  }
214}
215
216pub(crate) struct MempoolConsumer<T> {
217  genesis: [u8; 32],
218  censured: BTreeSet<[u8; 32]>,
219  #[expect(clippy::type_complexity)]
220  request: async_channel::Sender<([u8; 32], async_channel::Sender<Box<[T]>>)>,
221}
222
223pin_project_lite::pin_project! {
224  pub(crate) struct MempoolRecv<T> {
225    #[pin]
226    receiver: Option<async_channel::Receiver<T>>
227  }
228}
229
230impl<T> Future for MempoolRecv<Box<[T]>> {
231  type Output = Box<[T]>;
232  fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> {
233    let message = if let Some(receiver) = self.project().receiver.as_pin_mut() {
234      let Poll::Ready(message) = receiver.poll_next(cx) else {
235        return Poll::Pending;
236      };
237      message
238    } else {
239      // If we don't have a receiver, it's because we couldn't send the request to the mempool
240      None
241    };
242
243    /*
244      Fallback to an empty list of transactions.
245
246      This uses [`Box::default`] which for `[T]`, creates a box to an empty slice
247      _without further bounds on `T`_. `Box::from([].as_slice())` would require `T: Clone`.
248      Unfortunately, it isn't available as `Box::new_empty_slice`
249      (or with any more descriptive name).
250    */
251    Poll::Ready(message.unwrap_or_else(Box::default))
252  }
253}
254
255impl<T: Transaction> crate::tendermint::Mempool<T> for MempoolConsumer<T> {
256  type Transactions = Box<[T]>;
257  type Future = MempoolRecv<Self::Transactions>;
258  fn transactions(&mut self, parent_block: [u8; 32]) -> Self::Future {
259    let (sender, receiver) = async_channel::bounded(1);
260    /*
261      We use `force_send`, replacing the existing message if there is one, as we only care for the
262      next block's proposal.
263    */
264    let sent_request = self.request.force_send((parent_block, sender));
265    MempoolRecv { receiver: sent_request.is_ok().then_some(receiver) }
266  }
267  fn censured(&self, getter: &impl Get, validator: [u8; 32]) -> bool {
268    self.censured.contains(&validator) || UnSigned::<T>::censured(getter, self.genesis, validator)
269  }
270  fn censure(&mut self, txn: &mut impl DbTxn, validator: [u8; 32]) {
271    if self.censured.insert(validator) {
272      Censure::send(txn, self.genesis, &validator);
273    }
274  }
275}
276
277impl<D: Db, T: Transaction, N: MempoolNetwork<T>> Mempool<D, T, N> {
278  pub(super) fn new(
279    mut db: D,
280    genesis: [u8; 32],
281    validators: impl IntoIterator<Item = [u8; 32]>,
282    network: N,
283    censure: async_channel::Receiver<([u8; 32], async_channel::Sender<()>)>,
284    rate_limit: usize,
285  ) -> (Self, MempoolConsumer<T>) {
286    let last_block = LastBlock::get(&db, genesis).unwrap_or(genesis);
287
288    let provided = Provided::new(&db, genesis);
289
290    let un_signed = {
291      let mut txn = db.txn();
292      let mut un_signed = UnSigned::new(&mut txn, genesis, validators, rate_limit);
293      while let Some(validator) = Censure::try_recv(&mut txn, genesis) {
294        un_signed.censure(&mut txn, validator);
295      }
296      txn.commit();
297      un_signed
298    };
299
300    let (request_send, request_recv) = async_channel::bounded(1);
301    let resend_request = request_send.clone().downgrade();
302
303    (
304      Self {
305        db,
306        genesis,
307
308        last_block,
309        provided,
310        un_signed,
311
312        network,
313        regossip: 0,
314
315        censure,
316        request: request_recv,
317        resend_request,
318      },
319      MempoolConsumer {
320        genesis,
321
322        /*
323          This is a cache of validators which have been censured, yet this hasn't been reflected
324          in the signed mempool's database yet. As we drained the `Censure` channel, ensuring all
325          censures _have_ been incorporated into the `signed` mempool, we can initialize this cache
326          as empty.
327        */
328        censured: BTreeSet::new(),
329
330        request: request_send,
331      },
332    )
333  }
334
335  pub(crate) fn add(
336    self: Pin<&mut Self>,
337    txn: &mut impl DbTxn,
338    transaction: T,
339    bypass_rate_limit: bool,
340  ) -> Result<(), MempoolError> {
341    let projection = self.project();
342    match transaction.kind() {
343      TransactionKind::Provided { .. } => projection.provided.provide(txn, transaction),
344      TransactionKind::Unsigned | TransactionKind::Signed { .. } => {
345        let result = projection.un_signed.add(txn, transaction.clone(), bypass_rate_limit);
346        if result.is_ok() {
347          projection.network.gossip(*projection.genesis, transaction);
348        }
349        result
350      }
351    }
352  }
353}