commit 71b0447439d4be589d9f348d1e4182617a7e3084
parent 549ab9f1ff1158318920382e17a4d973816d8b9f
Author: Joris Hartog <jorishartog@hotmail.com>
Date: Wed, 9 Sep 2026 22:20:47 +0200
fix(mempool): evict lower-fee packages under pressure
Diffstat:
3 files changed, 387 insertions(+), 33 deletions(-)
diff --git a/docs/protocol.md b/docs/protocol.md
@@ -337,6 +337,8 @@ signed burn bundles for that height, parent hash, and slot set.
Nodes only keep transactions in their local mempool when they are valid, fee-paying, and unexpired. Pending and orphan transaction pools are bounded by both item count and serialized byte size. A signed burn bundle is limited to `10,000` bytes, and nodes only cache valid bundles for the next height and current parent.
+When the pending count or byte bound is reached, a node admits an independent transaction only if its fee rate is strictly higher than the lowest evictable pending package. Package eviction removes dependent pending transactions and orphan descendants together. This is local relay policy, not a block-consensus rule.
+
## Block Selection
When a node builds a block, the flow is:
diff --git a/docs/security-audit-2026-09-09.md b/docs/security-audit-2026-09-09.md
@@ -21,7 +21,7 @@ found in the reviewed validation paths.
| IUNA-2026-001 | High | Effectively EUR 0 from one public IP | Patched |
| IUNA-2026-002 | High over chain lifetime | A basic host and bandwidth; well below EUR 100/month | Patched |
| IUNA-2026-003 | High during first sync | Below EUR 10,000 when DNS/routing/bootstrap access is available | Patched |
-| IUNA-2026-004 | Medium | 10,000 minimum-fee transactions; protocol value likely far below EUR 10,000 | Open hardening item |
+| IUNA-2026-004 | Medium | 10,000 minimum-fee transactions; protocol value likely far below EUR 10,000 | Patched |
## IUNA-2026-001 — one source could exhaust every Stratum session
@@ -122,12 +122,13 @@ bounds memory, but not admission fairness or repeated validation cost.
Impact: delayed transaction propagation and local CPU load. Consensus remains
valid and directly connected block producers can still include transactions.
-Recommended patch: introduce a minimum relay fee rate and dependency-aware
-replacement of the lowest-fee transaction package. This should be implemented
-as mempool policy, leaving block consensus compatible with already signed
-low-fee transactions. Add tests proving that a full pool accepts a higher-fee
-independent transaction, removes descendants of an evicted parent, and keeps
-byte/count counters exact.
+Patch: once the count or byte bound is reached, the lowest-fee-rate independent
+package becomes the dynamic relay floor. A candidate is admitted only when its
+fee rate is strictly higher; eviction removes the package's pending and orphan
+descendants atomically and recalculates both byte counters. Ordinary low-fee
+admission and block consensus remain compatible. Regression tests prove that a
+full pool accepts a higher-fee independent transaction, descendants are removed
+as one package, and the byte/count counters remain exact.
## Verification evidence
@@ -141,7 +142,7 @@ cargo clippy --locked --all-targets --all-features -- -D warnings: passed
The initial sandboxed run completed 330 tests successfully; its 15 socket-based
P2P tests could not call `bind(2)`. The suite was then repeated locally with
-loopback permission and passed completely: 427 passed, 0 failed, and 36
+loopback permission and passed completely: 432 passed, 0 failed, and 36
long-running tests were ignored by their existing configuration.
`scripts/check-dependencies.sh` could not refresh RustSec because the sandbox
@@ -152,5 +153,4 @@ therefore not claimed by this report.
Do not promote to mainnet until the complete release gate is run on the exact
final revision, the candidate manifest is updated, and the custom VDF plus
-economic finality assumptions receive independent review. IUNA-2026-004 should
-be fixed before exposing a high-value public transaction network.
+economic finality assumptions receive independent review.
diff --git a/src/domain/ledger_mempool.rs b/src/domain/ledger_mempool.rs
@@ -1,3 +1,5 @@
+use std::{cmp::Ordering, collections::BTreeSet};
+
use anyhow::{Context, Result, bail};
use serde::Serialize;
@@ -84,10 +86,6 @@ impl Ledger {
return Ok(TransactionSubmitOutcome::ConflictsWithPending);
}
- if self.pending.len() >= MAX_PENDING_TRANSACTIONS {
- bail!("mempool is full");
- }
-
let mut utxos = self.utxos_after_valid_pending()?;
if transaction_has_missing_inputs(&transaction, &utxos) {
if self.orphans.len() >= MAX_ORPHAN_TRANSACTIONS {
@@ -104,18 +102,86 @@ impl Ledger {
return Ok(TransactionSubmitOutcome::Added);
}
apply_transaction(&transaction, &mut utxos, &signing_domain)?;
- let candidate_bytes = ensure_pending_pool_bytes(
- "mempool",
- self.pending_bytes,
- &transaction,
- MAX_PENDING_POOL_BYTES,
- )?;
+ let candidate_bytes = pending_pool_item_bytes(&transaction)?;
+ let replacement_backup = self.pending_room_required(candidate_bytes).then(|| {
+ (
+ self.pending.clone(),
+ self.orphans.clone(),
+ self.pending_bytes,
+ self.orphan_bytes,
+ )
+ });
+ if let Err(error) = self.make_pending_room(&transaction, candidate_bytes) {
+ self.restore_pending_after_failed_replacement(replacement_backup);
+ return Err(error);
+ }
+
+ // An eviction may remove state the candidate depended on. Components
+ // containing candidate ancestors are protected, but revalidation keeps
+ // this admission step fail-closed if the graph is ever malformed.
+ let mut utxos = match self.utxos_after_valid_pending() {
+ Ok(utxos) => utxos,
+ Err(error) => {
+ self.restore_pending_after_failed_replacement(replacement_backup);
+ return Err(error);
+ }
+ };
+ if transaction_has_missing_inputs(&transaction, &utxos) {
+ self.restore_pending_after_failed_replacement(replacement_backup);
+ bail!("mempool replacement removed a candidate dependency");
+ }
+ if let Err(error) = apply_transaction(&transaction, &mut utxos, &signing_domain) {
+ self.restore_pending_after_failed_replacement(replacement_backup);
+ return Err(error);
+ }
self.pending.push(transaction);
self.pending_bytes = self.pending_bytes.saturating_add(candidate_bytes);
- self.promote_orphan_transactions()?;
+ if let Err(error) = self.promote_orphan_transactions() {
+ if let Some((pending, orphans, pending_bytes, orphan_bytes)) = replacement_backup {
+ self.pending = pending;
+ self.orphans = orphans;
+ self.pending_bytes = pending_bytes;
+ self.orphan_bytes = orphan_bytes;
+ }
+ return Err(error);
+ }
Ok(TransactionSubmitOutcome::Added)
}
+ fn pending_room_required(&self, candidate_bytes: usize) -> bool {
+ self.pending.len() >= MAX_PENDING_TRANSACTIONS
+ || self
+ .pending_bytes
+ .checked_add(candidate_bytes)
+ .is_none_or(|bytes| bytes > MAX_PENDING_POOL_BYTES)
+ }
+
+ fn restore_pending_after_failed_replacement(
+ &mut self,
+ backup: Option<(Vec<Transaction>, Vec<Transaction>, usize, usize)>,
+ ) {
+ if let Some((pending, orphans, pending_bytes, orphan_bytes)) = backup {
+ self.pending = pending;
+ self.orphans = orphans;
+ self.pending_bytes = pending_bytes;
+ self.orphan_bytes = orphan_bytes;
+ }
+ }
+
+ fn make_pending_room(&mut self, candidate: &Transaction, candidate_bytes: usize) -> Result<()> {
+ if !self.pending_room_required(candidate_bytes) {
+ return Ok(());
+ }
+
+ let evicted =
+ pending_eviction_plan(&self.pending, &self.orphans, candidate, candidate_bytes)?;
+ self.pending
+ .retain(|transaction| !evicted.contains(transaction.signature()));
+ self.orphans
+ .retain(|transaction| !evicted.contains(transaction.signature()));
+ self.refresh_pending_pool_byte_counters()
+ }
+
pub(super) fn refresh_pending_pool_byte_counters(&mut self) -> Result<()> {
self.pending_bytes = serialized_pool_len(&self.pending)?;
self.orphan_bytes = serialized_pool_len(&self.orphans)?;
@@ -123,6 +189,162 @@ impl Ledger {
}
}
+#[derive(Debug)]
+struct EvictionPackage {
+ signatures: BTreeSet<String>,
+ fee: u128,
+ economic_bytes: u128,
+ pending_bytes: usize,
+ pending_count: usize,
+ tie_break: String,
+}
+
+fn pending_eviction_plan(
+ pending: &[Transaction],
+ orphans: &[Transaction],
+ candidate: &Transaction,
+ candidate_bytes: usize,
+) -> Result<BTreeSet<String>> {
+ if candidate_bytes > MAX_PENDING_POOL_BYTES {
+ bail!("mempool byte limit exceeded");
+ }
+
+ let by_signature = pending
+ .iter()
+ .enumerate()
+ .map(|(index, transaction)| (transaction.signature().to_string(), index))
+ .collect::<std::collections::BTreeMap<_, _>>();
+ let mut edges = vec![Vec::new(); pending.len()];
+ for (index, transaction) in pending.iter().enumerate() {
+ for input in transaction.inputs() {
+ if let Some(parent) = by_signature.get(&input.outpoint.txid).copied() {
+ edges[index].push(parent);
+ edges[parent].push(index);
+ }
+ }
+ }
+
+ let protected = candidate
+ .inputs()
+ .iter()
+ .filter_map(|input| by_signature.get(&input.outpoint.txid).copied())
+ .collect::<BTreeSet<_>>();
+ let mut visited = vec![false; pending.len()];
+ let mut packages = Vec::new();
+ for start in 0..pending.len() {
+ if visited[start] {
+ continue;
+ }
+ let mut stack = vec![start];
+ let mut indices = Vec::new();
+ let mut protects_candidate = false;
+ visited[start] = true;
+ while let Some(index) = stack.pop() {
+ indices.push(index);
+ protects_candidate |= protected.contains(&index);
+ for adjacent in &edges[index] {
+ if !visited[*adjacent] {
+ visited[*adjacent] = true;
+ stack.push(*adjacent);
+ }
+ }
+ }
+ if protects_candidate {
+ continue;
+ }
+
+ let signatures = indices
+ .iter()
+ .map(|index| pending[*index].signature().to_string())
+ .collect::<BTreeSet<_>>();
+ let fee = indices
+ .iter()
+ .map(|index| u128::from(pending[*index].fee()))
+ .sum();
+ let economic_bytes = indices
+ .iter()
+ .map(|index| pending[*index].economic_size_bytes() as u128)
+ .sum();
+ let pending_bytes = indices.iter().try_fold(0usize, |total, index| {
+ total
+ .checked_add(pending_pool_item_bytes(&pending[*index])?)
+ .context("pending eviction package byte size overflow")
+ })?;
+ let tie_break = signatures.iter().next().cloned().unwrap_or_default();
+ packages.push(EvictionPackage {
+ signatures,
+ fee,
+ economic_bytes,
+ pending_bytes,
+ pending_count: indices.len(),
+ tie_break,
+ });
+ }
+
+ packages.sort_by(compare_package_fee_rate);
+ let candidate_fee = u128::from(candidate.fee());
+ let candidate_economic_bytes = candidate.economic_size_bytes() as u128;
+ let mut remaining_count = pending.len();
+ let mut remaining_bytes = serialized_pool_len(pending)?;
+ let mut evicted = BTreeSet::new();
+ for package in packages {
+ let count_fits = remaining_count < MAX_PENDING_TRANSACTIONS;
+ let bytes_fit = remaining_bytes
+ .checked_add(candidate_bytes)
+ .is_some_and(|bytes| bytes <= MAX_PENDING_POOL_BYTES);
+ if count_fits && bytes_fit {
+ extend_with_orphan_descendants(&mut evicted, orphans);
+ return Ok(evicted);
+ }
+ if candidate_fee.saturating_mul(package.economic_bytes)
+ <= package.fee.saturating_mul(candidate_economic_bytes)
+ {
+ break;
+ }
+ remaining_count = remaining_count.saturating_sub(package.pending_count);
+ remaining_bytes = remaining_bytes.saturating_sub(package.pending_bytes);
+ evicted.extend(package.signatures);
+ }
+
+ let count_fits = remaining_count < MAX_PENDING_TRANSACTIONS;
+ let bytes_fit = remaining_bytes
+ .checked_add(candidate_bytes)
+ .is_some_and(|bytes| bytes <= MAX_PENDING_POOL_BYTES);
+ if count_fits && bytes_fit {
+ extend_with_orphan_descendants(&mut evicted, orphans);
+ Ok(evicted)
+ } else {
+ bail!("mempool is full and candidate fee rate does not exceed an evictable package")
+ }
+}
+
+fn extend_with_orphan_descendants(evicted: &mut BTreeSet<String>, orphans: &[Transaction]) {
+ loop {
+ let mut changed = false;
+ for orphan in orphans {
+ if !evicted.contains(orphan.signature())
+ && orphan
+ .inputs()
+ .iter()
+ .any(|input| evicted.contains(&input.outpoint.txid))
+ {
+ changed |= evicted.insert(orphan.signature().to_string());
+ }
+ }
+ if !changed {
+ return;
+ }
+ }
+}
+
+fn compare_package_fee_rate(left: &EvictionPackage, right: &EvictionPackage) -> Ordering {
+ left.fee
+ .saturating_mul(right.economic_bytes)
+ .cmp(&right.fee.saturating_mul(left.economic_bytes))
+ .then_with(|| left.fee.cmp(&right.fee))
+ .then_with(|| left.tie_break.cmp(&right.tie_break))
+}
+
fn ensure_pending_pool_bytes<T: Serialize>(
label: &str,
existing_bytes: usize,
@@ -165,9 +387,9 @@ mod tests {
use crate::domain::transaction::{UnsignedTxInput, UnsignedUtxoTransaction};
use crate::domain::{OutPoint, TxOutput, Wallet};
- fn dummy_mine(signature_digit: char) -> Transaction {
+ fn dummy_mine(recipient: &str, signature_digit: char) -> Transaction {
Transaction::Mine {
- recipient: "recipient".to_string(),
+ recipient: recipient.to_string(),
anchor: "a".repeat(64),
salt: 1,
nonce: 1,
@@ -206,26 +428,132 @@ mod tests {
}
#[test]
- fn mempool_rejects_transaction_after_ten_thousand_items() {
+ fn full_mempool_accepts_a_higher_fee_independent_transaction() {
let alice = Wallet::from_seed("pending-limit-alice");
let bob = Wallet::from_seed("pending-limit-bob");
let mut ledger = Ledger::new(
BTreeMap::from([
+ (alice.address().to_string(), 10_000_000),
+ (bob.address().to_string(), 10),
+ ]),
+ 1,
+ );
+ let candidate = ledger
+ .build_transfer(&alice, bob.address(), 1, 5_000_000)
+ .unwrap();
+ ledger.pending = (0..MAX_PENDING_TRANSACTIONS)
+ .map(|index| {
+ let digit = char::from_digit((index % 15 + 1) as u32, 16).unwrap();
+ let mut transaction = dummy_mine(bob.address(), digit);
+ if let Transaction::Mine { signature, .. } = &mut transaction {
+ *signature = format!("{index:064x}");
+ }
+ transaction
+ })
+ .collect();
+ ledger.refresh_pending_pool_byte_counters().unwrap();
+
+ assert_eq!(ledger.pending.len(), 10_000);
+ assert!(ledger.submit_transaction(candidate.clone()).unwrap());
+ assert_eq!(ledger.pending.len(), 10_000);
+ assert!(ledger.has_transaction(candidate.signature()));
+ assert_eq!(
+ ledger.pending_bytes,
+ serialized_pool_len(&ledger.pending).unwrap()
+ );
+ assert_eq!(ledger.orphan_bytes, 0);
+ }
+
+ #[test]
+ fn full_mempool_rejects_a_lower_fee_candidate_without_mutation() {
+ let alice = Wallet::from_seed("lower-fee-candidate-alice");
+ let bob = Wallet::from_seed("lower-fee-candidate-bob");
+ let mut ledger = Ledger::new(
+ BTreeMap::from([
(alice.address().to_string(), 10),
(bob.address().to_string(), 10),
]),
1,
);
let candidate = ledger.build_transfer(&alice, bob.address(), 1, 1).unwrap();
- ledger.pending = vec![dummy_mine('f'); MAX_PENDING_TRANSACTIONS];
+ ledger.pending = (0..MAX_PENDING_TRANSACTIONS)
+ .map(|index| {
+ let mut transaction = dummy_mine(bob.address(), 'd');
+ if let Transaction::Mine { signature, .. } = &mut transaction {
+ *signature = format!("{index:064x}");
+ }
+ transaction
+ })
+ .collect();
+ ledger.refresh_pending_pool_byte_counters().unwrap();
+ let before = ledger.pending.clone();
+ let before_bytes = ledger.pending_bytes;
- assert_eq!(ledger.pending.len(), 10_000);
- assert!(
- ledger
- .submit_transaction(candidate)
- .unwrap_err()
- .to_string()
- .contains("mempool is full")
+ let error = ledger.submit_transaction(candidate).unwrap_err();
+
+ assert!(error.to_string().contains("candidate fee rate"));
+ assert_eq!(ledger.pending, before);
+ assert_eq!(ledger.pending_bytes, before_bytes);
+ assert!(ledger.orphans.is_empty());
+ assert_eq!(ledger.orphan_bytes, 0);
+ }
+
+ #[test]
+ fn eviction_package_includes_pending_and_orphan_descendants() {
+ let wallet = Wallet::from_seed("eviction-package-wallet");
+ let parent_signature = "1".repeat(128);
+ let child_signature = "2".repeat(128);
+ let orphan_signature = "3".repeat(128);
+ let parent = synthetic_dependency_transaction(
+ wallet.address(),
+ "a".repeat(64),
+ parent_signature.clone(),
+ 1,
+ );
+ let child = synthetic_dependency_transaction(
+ wallet.address(),
+ parent_signature,
+ child_signature.clone(),
+ 1,
+ );
+ let orphan = synthetic_dependency_transaction(
+ wallet.address(),
+ child_signature,
+ orphan_signature.clone(),
+ u64::MAX,
+ );
+ let candidate = synthetic_dependency_transaction(
+ wallet.address(),
+ "b".repeat(64),
+ "f".repeat(128),
+ 10_000,
+ );
+ let pending = vec![parent, child];
+ let candidate_bytes = pending_pool_item_bytes(&candidate).unwrap();
+ let mut padded = pending.clone();
+ padded.extend(
+ (pending.len()..MAX_PENDING_TRANSACTIONS).map(|_| dummy_mine(wallet.address(), 'e')),
+ );
+
+ let mut ledger = Ledger::new(BTreeMap::new(), 1);
+ ledger.pending = padded;
+ ledger.orphans = vec![orphan];
+ ledger.refresh_pending_pool_byte_counters().unwrap();
+
+ ledger
+ .make_pending_room(&candidate, candidate_bytes)
+ .unwrap();
+
+ assert!(!ledger.has_transaction(&"1".repeat(128)));
+ assert!(!ledger.has_transaction(&"2".repeat(128)));
+ assert!(!ledger.has_transaction(&orphan_signature));
+ assert_eq!(
+ ledger.pending_bytes,
+ serialized_pool_len(&ledger.pending).unwrap()
+ );
+ assert_eq!(
+ ledger.orphan_bytes,
+ serialized_pool_len(&ledger.orphans).unwrap()
);
}
@@ -249,7 +577,7 @@ mod tests {
}
.sign(&wallet, &ledger.transaction_signing_domain())
.unwrap();
- ledger.orphans = vec![dummy_mine('e'); MAX_ORPHAN_TRANSACTIONS];
+ ledger.orphans = vec![dummy_mine(wallet.address(), 'e'); MAX_ORPHAN_TRANSACTIONS];
assert_eq!(ledger.orphans.len(), 1_024);
assert!(
@@ -260,4 +588,28 @@ mod tests {
.contains("orphan transaction pool is full")
);
}
+
+ fn synthetic_dependency_transaction(
+ owner: &str,
+ parent: String,
+ signature: String,
+ fee: u64,
+ ) -> Transaction {
+ Transaction::Transfer {
+ inputs: vec![super::super::TxInput {
+ outpoint: OutPoint {
+ txid: parent,
+ index: 0,
+ },
+ owner: owner.to_string(),
+ signature: signature.clone(),
+ }],
+ outputs: vec![TxOutput {
+ address: owner.to_string(),
+ amount: 1,
+ }],
+ fee,
+ signature,
+ }
+ }
}