use alloc::{
boxed::Box,
vec::Vec,
collections::{VecDeque, BTreeMap},
};
use serai_db::{Get, Transaction as DbTxn};
use crate::{
transaction::{TransactionError, Signed, TransactionKind, Transaction},
Block,
};
use super::MempoolError;
mod db {
use crate::{ReadWrite, ReadWriteAsBorsh};
use super::*;
serai_db::schema!(TributaryUnSigned {
Censured: (genesis: [u8; 32], validator: [u8; 32]) -> (),
Transaction: <T: ReadWrite>(genesis: [u8; 32], hash: [u8; 32]) -> ReadWriteAsBorsh<T>,
Transactions: (genesis: [u8; 32]) -> Vec<[u8; 32]>,
UnsignedOnChain: (genesis: [u8; 32], hash: [u8; 32]) -> (),
SignedOnChain: (genesis: [u8; 32], signer: [u8; 32], scope: &[u8], nonce: u64) -> [u8; 32],
});
}
struct ScopeMempool<T> {
have_prior_on_chain: bool,
transactions: VecDeque<T>,
}
impl<T: Transaction> ScopeMempool<T> {
fn iter_with_prior(&self) -> impl Iterator<Item = &T> {
let mut last_nonce: Option<u64> = None;
self.transactions.iter().filter(move |transaction| {
let TransactionKind::Signed { scope: _, signed: Signed { nonce, .. } } = transaction.kind()
else {
panic!("non-signed transaction in signer's mempool")
};
if self.have_prior_on_chain &&
last_nonce.is_none_or(|last_nonce| last_nonce.checked_add(1) == Some(nonce))
{
last_nonce = Some(nonce);
true
} else {
false
}
})
}
}
#[test]
fn iter_with_prior() {
use crate::transaction::TestTransaction;
let transaction = |nonce| TestTransaction {
valid: true,
kind: TransactionKind::Signed {
scope: Box::default(),
signed: Signed { signer: [0; 32], nonce, signature: [0; 64] },
},
salt: 0,
};
let transactions = (0 .. 5).map(transaction).collect::<Vec<_>>();
assert_eq!(
(ScopeMempool::<TestTransaction> {
have_prior_on_chain: true,
transactions: VecDeque::from([transactions[0].clone()])
})
.iter_with_prior()
.map(Transaction::hash)
.collect::<Vec<_>>(),
[transactions[0].hash()]
);
assert_eq!(
(ScopeMempool::<TestTransaction> {
have_prior_on_chain: false,
transactions: VecDeque::from([transactions[1].clone(), transactions[2].clone()])
})
.iter_with_prior()
.map(Transaction::hash)
.collect::<Vec<_>>(),
<[[u8; 32]; 0]>::default()
);
assert_eq!(
(ScopeMempool::<TestTransaction> {
have_prior_on_chain: true,
transactions: VecDeque::from([transactions[1].clone(), transactions[2].clone()])
})
.iter_with_prior()
.map(Transaction::hash)
.collect::<Vec<_>>(),
[transactions[1].hash(), transactions[2].hash()]
);
assert_eq!(
(ScopeMempool::<TestTransaction> {
have_prior_on_chain: true,
transactions: VecDeque::from([
transactions[1].clone(),
transactions[3].clone(),
transactions[4].clone()
])
})
.iter_with_prior()
.map(Transaction::hash)
.collect::<Vec<_>>(),
[transactions[1].hash()]
);
}
struct PopUntil<'map, T> {
scope_mempool_entry:
alloc::collections::btree_map::OccupiedEntry<'map, Box<[u8]>, ScopeMempool<T>>,
on_chain_nonce: u64,
}
impl<'map, T: Transaction> PopUntil<'map, T> {
fn new(
scope_mempool_entry: alloc::collections::btree_map::OccupiedEntry<
'map,
Box<[u8]>,
ScopeMempool<T>,
>,
on_chain_nonce: u64,
) -> Self {
Self { scope_mempool_entry, on_chain_nonce }
}
fn next(mut self) -> Option<(Self, T)> {
let scope_mempool = self.scope_mempool_entry.get_mut();
if let Some(transaction) =
scope_mempool.transactions.pop_front_if(|transaction| match transaction.kind() {
TransactionKind::Signed {
scope: _,
signed: Signed { signer: _, nonce: nonce_in_scope, signature: _ },
} => nonce_in_scope <= self.on_chain_nonce,
TransactionKind::Provided { .. } | TransactionKind::Unsigned => {
panic!("non-signed transaction added to signed transactions in mempool")
}
})
{
return Some((self, transaction));
}
if let Some(first) = scope_mempool.transactions.front() {
let TransactionKind::Signed { scope: _, signed: Signed { signer: _, nonce, signature: _ } } =
first.kind()
else {
panic!("non-signed transaction added to signed transactions in mempool")
};
scope_mempool.have_prior_on_chain =
nonce.checked_sub(1).is_none_or(|prior_nonce| prior_nonce == self.on_chain_nonce);
} else {
self.scope_mempool_entry.remove_entry();
}
None
}
}
#[test]
fn pop_until() {
use crate::transaction::TestTransaction;
let transaction = |nonce| TestTransaction {
valid: true,
kind: TransactionKind::Signed {
scope: Box::default(),
signed: Signed { signer: [0; 32], nonce, signature: [0; 64] },
},
salt: 0,
};
let mut parent = BTreeMap::new();
let two = transaction(2);
let three = transaction(3);
let five = transaction(5);
for on_chain_nonce in [3, 4] {
let scope_mempool_entry =
parent.entry(Box::default()).insert_entry(ScopeMempool::<TestTransaction> {
have_prior_on_chain: true,
transactions: VecDeque::from([two.clone(), three.clone(), five.clone()]),
});
{
let mut iter = PopUntil { scope_mempool_entry, on_chain_nonce };
let mut removed = [two.clone(), three.clone()].into_iter();
while let Some((returned_iter, transaction)) = iter.next() {
iter = returned_iter;
assert_eq!(transaction.hash(), removed.next().unwrap().hash());
}
}
let scope_mempool = &parent[[].as_slice()];
assert_eq!(
scope_mempool.transactions.iter().map(Transaction::hash).collect::<Vec<_>>(),
alloc::vec![five.hash()]
);
assert_eq!(scope_mempool.have_prior_on_chain, on_chain_nonce == 4);
}
}
struct SignerMempool<T>(BTreeMap<Box<[u8]>, ScopeMempool<T>>);
impl<T: Transaction> SignerMempool<T> {
fn new() -> Self {
Self(BTreeMap::new())
}
fn rate(&self) -> Option<usize> {
self
.0
.values()
.map(|scope_mempool| scope_mempool.transactions.len())
.try_fold(0usize, usize::checked_add)
}
#[expect(clippy::borrowed_box)]
fn find_unpublishable_transaction(&mut self) -> Option<(&Box<[u8]>, &mut ScopeMempool<T>)> {
for (scope, scope_mempool) in &mut self.0 {
if !scope_mempool.have_prior_on_chain {
return Some((scope, scope_mempool));
}
let transactions = &scope_mempool.transactions;
if transactions.len() > 1 {
let TransactionKind::Signed { scope: _, signed: Signed { nonce: first, .. } } =
transactions.front().unwrap().kind()
else {
panic!("non-signed transaction in signer's mempool");
};
let TransactionKind::Signed { scope: _, signed: Signed { nonce: last, .. } } =
transactions.back().unwrap().kind()
else {
panic!("non-signed transaction in signer's mempool");
};
if if let Ok(expected_len_minus_one) = usize::try_from(last - first) {
expected_len_minus_one != (transactions.len() - 1)
} else {
true
} {
return Some((scope, scope_mempool));
}
}
}
None
}
#[expect(clippy::too_many_arguments)]
fn add(
&mut self,
getter: &impl Get,
genesis: [u8; 32],
signer: [u8; 32],
scope: Box<[u8]>,
nonce: u64,
hash: [u8; 32],
transaction: T,
) -> Result<&T, MempoolError> {
if let Some(on_chain) = db::SignedOnChain::get(getter, genesis, signer, &scope, nonce) {
if on_chain == hash {
Err(MempoolError::AlreadyPresent)?;
} else {
Err(MempoolError::Conflict)?;
}
}
let scope_mempool_entry = match self.0.entry(scope) {
alloc::collections::btree_map::Entry::Occupied(entry) => entry,
alloc::collections::btree_map::Entry::Vacant(entry) => entry
.insert_entry(ScopeMempool { have_prior_on_chain: false, transactions: VecDeque::new() }),
};
let scope_mempool = scope_mempool_entry.get();
match scope_mempool.transactions.binary_search_by_key(&nonce, |transaction_in_mempool| {
match transaction_in_mempool.kind() {
TransactionKind::Signed { scope: _, signed: Signed { nonce, .. } } => nonce,
TransactionKind::Provided { .. } | TransactionKind::Unsigned => {
panic!("non-signed transaction in mempool's signed transactions")
}
}
}) {
Ok(i) => {
if scope_mempool.transactions[i].hash() == hash {
Err(MempoolError::AlreadyPresent)?;
}
Err(MempoolError::Conflict)?
}
Err(i) => {
let have_prior_on_chain = if i == 0 {
nonce.checked_sub(1).is_none_or(|prior_nonce| {
db::SignedOnChain::get(getter, genesis, signer, scope_mempool_entry.key(), prior_nonce)
.is_some()
})
} else {
scope_mempool.have_prior_on_chain
};
let scope_mempool = scope_mempool_entry.into_mut();
scope_mempool.have_prior_on_chain = have_prior_on_chain;
Ok(&*scope_mempool.transactions.insert_mut(i, transaction))
}
}
}
}
#[test]
fn find_unpublishable_transaction() {
use crate::transaction::TestTransaction;
let genesis = [0xfe; 32];
let signer = [0xaa; 32];
let transaction = |nonce| TestTransaction {
valid: true,
kind: TransactionKind::Signed {
scope: Box::default(),
signed: Signed { signer, nonce, signature: [0; 64] },
},
salt: 0,
};
let mut signer_mempool = SignerMempool::new();
let three = transaction(3);
let four = transaction(4);
let five = transaction(5);
signer_mempool.0.insert(
Box::default(),
ScopeMempool::<TestTransaction> {
have_prior_on_chain: true,
transactions: VecDeque::from([three, five]),
},
);
assert!(signer_mempool.find_unpublishable_transaction().is_some());
signer_mempool
.add(&serai_db::MemDb::new(), genesis, signer, Box::default(), 4, four.hash(), four)
.unwrap();
assert!(signer_mempool.find_unpublishable_transaction().is_none());
signer_mempool.0.get_mut(&Box::default()).unwrap().have_prior_on_chain = false;
assert!(signer_mempool.find_unpublishable_transaction().is_some());
}
pub(super) struct UnSigned<T> {
genesis: [u8; 32],
rate_limit: usize,
unsigned: BTreeMap<[u8; 32], T>,
signed: BTreeMap<[u8; 32], SignerMempool<T>>,
}
impl<T: Transaction> UnSigned<T> {
#[must_use]
pub(super) fn censured(getter: &impl Get, genesis: [u8; 32], validator: [u8; 32]) -> bool {
db::Censured::get(getter, genesis, validator).is_some()
}
fn save(&mut self, txn: &mut impl DbTxn) {
let mempool = self
.unsigned
.values()
.chain(self.signed.values().flat_map(|signer_mempool| {
signer_mempool.0.values().flat_map(|scope_mempool| &scope_mempool.transactions)
}))
.map(Transaction::hash)
.collect();
db::Transactions::set(txn, self.genesis, &mempool);
}
pub(super) fn new(
txn: &mut impl DbTxn,
genesis: [u8; 32],
validators: impl IntoIterator<Item = [u8; 32]>,
rate_limit: usize,
) -> Self {
let mut unsigned = BTreeMap::new();
let mut signed = validators
.into_iter()
.filter(|signer| db::Censured::get(txn, genesis, *signer).is_none())
.map(|signer| (signer, SignerMempool::new()))
.collect::<BTreeMap<[u8; 32], SignerMempool<T>>>();
for hash in db::Transactions::get(txn, genesis).into_iter().flatten() {
let transaction = db::Transaction::<T>::get(txn, genesis, hash)
.expect("transaction in mempool wasn't saved to disk")
.0;
match transaction.kind() {
TransactionKind::Provided { .. } => panic!("provided transaction added to the mempool"),
TransactionKind::Unsigned => {
unsigned.insert(transaction.hash(), transaction);
}
TransactionKind::Signed { scope, signed: Signed { signer, nonce, signature: _ } } => {
let Some(signer_mempool) = signed.get_mut(&signer) else {
db::Transaction::<T>::del(txn, genesis, transaction.hash());
continue;
};
signer_mempool
.add(txn, genesis, signer, scope, nonce, hash, transaction)
.expect("transaction saved into mempool couldn't be reloaded into signer's mempool");
}
}
}
let mut result = UnSigned { genesis, rate_limit, unsigned, signed };
result.save(txn);
result
}
pub(super) fn censure(&mut self, txn: &mut impl DbTxn, validator: [u8; 32]) {
db::Censured::set(txn, self.genesis, validator, &());
for transaction in self
.signed
.remove(&validator)
.into_iter()
.flat_map(|signer_mempool| signer_mempool.0)
.flat_map(|(_scope, scope_mempool)| scope_mempool.transactions)
{
db::Transaction::<T>::del(txn, self.genesis, transaction.hash());
}
self.save(txn);
}
pub(super) fn add(
&mut self,
txn: &mut impl DbTxn,
transaction: T,
bypass_rate_limit: bool,
) -> Result<(), MempoolError> {
crate::transaction::verify_syntax(&transaction, self.genesis)?;
let hash = transaction.hash();
let mut prune = None;
let transaction: &T = match transaction.kind() {
TransactionKind::Provided { .. } => panic!("provided transaction being added to the mempool"),
TransactionKind::Unsigned => {
if db::UnsignedOnChain::get(txn, self.genesis, hash).is_some() {
Err(MempoolError::AlreadyPresent)?;
}
let entry = self.unsigned.entry(hash);
if matches!(entry, alloc::collections::btree_map::Entry::Occupied(_)) {
Err(MempoolError::AlreadyPresent)?;
}
&*entry.insert_entry(transaction).into_mut()
}
TransactionKind::Signed { scope, signed: Signed { signer, nonce, signature: _ } } => {
let signer_mempool = self
.signed
.get_mut(&signer)
.ok_or(MempoolError::Invalid(TransactionError::InvalidSigner))?;
if !bypass_rate_limit {
let Some(rate) = signer_mempool.rate() else { Err(MempoolError::RateLimit)? };
if rate > self.rate_limit {
Err(MempoolError::RateLimit)?;
}
prune = (rate == self.rate_limit).then_some(signer);
}
signer_mempool.add(txn, self.genesis, signer, scope, nonce, hash, transaction)?
}
};
db::Transaction::<T>::set(txn, self.genesis, hash, transaction.into());
if let Some(signer) = prune {
let scope_of_added_transaction = {
let TransactionKind::Signed { scope, signed: _ } = transaction.kind() else {
panic!("pruning a signer's mempool but not adding a signed transaction")
};
scope
};
let signer_mempool =
self.signed.get_mut(&signer).expect("pruning a signer's mempool we don't have");
let (scope, scope_mempool) = match signer_mempool.find_unpublishable_transaction() {
Some((scope, scope_mempool)) => (scope, scope_mempool),
None => (
&scope_of_added_transaction,
signer_mempool
.0
.get_mut(&scope_of_added_transaction)
.expect("added a transaction but its scope doesn't exist within the signer's mempool"),
),
};
let pruned = scope_mempool
.transactions
.pop_back()
.expect("pruning from a scope in a signer's mempool which is empty");
let pruned_hash = pruned.hash();
db::Transaction::<T>::del(txn, self.genesis, pruned_hash);
if scope_mempool.transactions.is_empty() {
let scope = scope.clone();
signer_mempool.0.remove(&scope);
}
if hash == pruned_hash {
Err(MempoolError::RateLimit)?;
}
}
self.save(txn);
Ok(())
}
pub(super) fn block(&mut self, txn: &mut impl DbTxn, block: &Block<T>) {
for slash in block.slashes() {
self.censure(txn, *slash.validator());
}
for transaction in block.transactions() {
match transaction.kind() {
TransactionKind::Provided { .. } => continue,
TransactionKind::Unsigned => {
let hash = transaction.hash();
db::UnsignedOnChain::set(txn, self.genesis, hash, &());
if self.unsigned.remove(&hash).is_some() {
db::Transaction::<T>::del(txn, self.genesis, hash);
}
}
TransactionKind::Signed { scope, signed: Signed { signer, nonce, signature: _ } } => {
db::SignedOnChain::set(txn, self.genesis, signer, &scope, nonce, &transaction.hash());
if let Some(signer_mempool) = self.signed.get_mut(&signer) &&
let alloc::collections::btree_map::Entry::Occupied(scope_mempool_entry) =
signer_mempool.0.entry(scope)
{
let mut iter = PopUntil::new(scope_mempool_entry, nonce);
while let Some((returned_iter, transaction)) = iter.next() {
iter = returned_iter;
db::Transaction::<T>::del(txn, self.genesis, transaction.hash());
}
}
}
}
}
self.save(txn);
}
}
struct BlockProposal<'mempool, T: 'mempool, I: Iterator<Item = &'mempool T>> {
last_signer: Option<[u8; 32]>,
signer_size: Option<usize>,
iter: I,
}
impl<'mempool, T: 'mempool + Transaction, I: Iterator<Item = &'mempool T>> Iterator
for BlockProposal<'mempool, T, I>
{
type Item = &'mempool T;
fn next(&mut self) -> Option<Self::Item> {
loop {
let next_transaction = self.iter.next()?;
match next_transaction.kind() {
TransactionKind::Provided { .. } | TransactionKind::Unsigned => {}
TransactionKind::Signed { scope: _, signed: Signed { signer, nonce: _, signature: _ } } => {
if self.last_signer.as_ref().is_none_or(|last_signer| last_signer != &signer) {
self.signer_size = Some(0);
}
self.last_signer = Some(signer);
self.signer_size = self.signer_size.and_then(|signer_size| {
crate::serialized_len(next_transaction)
.ok()
.and_then(|transaction_size| signer_size.checked_add(transaction_size))
});
if let Some(block_size_limit) = T::BLOCK_SIZE_LIMIT &&
self.signer_size.is_none_or(|signer_size| signer_size >= block_size_limit)
{
continue;
}
}
}
break Some(next_transaction);
}
}
}
impl<T: Transaction> UnSigned<T> {
pub(super) fn block_proposal(&self) -> impl Iterator<Item = &T> {
BlockProposal {
last_signer: None,
signer_size: Some(0),
iter: self.unsigned.values().chain(self.signed.values().flat_map(|signer_mempool| {
signer_mempool.0.values().flat_map(ScopeMempool::iter_with_prior)
})),
}
}
}