brk_mempool/snapshot/
cpfp.rs

1//! CPFP (Child Pays For Parent) walk over a `Snapshot`'s adjacency.
2//!
3//! Three independent walks:
4//! - `ancestors`: capped DFS up `parents` only.
5//! - `descendants`: capped DFS down `children` only.
6//! - cluster: connected component over `parents ∪ children`,
7//!   linearized for wire shape and seed chunk feerate.
8
9use brk_types::{
10    CPFP_CHAIN_LIMIT, CpfpCluster, CpfpClusterTx, CpfpClusterTxIndex, CpfpEntry, CpfpInfo, FeeRate,
11    SigOps, TxidPrefix, VSize, find_seed_chunk,
12};
13use rustc_hash::{FxBuildHasher, FxHashSet};
14
15use crate::Mempool;
16
17use super::{Cluster, SnapTx, Snapshot, TxIndex};
18
19impl Mempool {
20    /// CPFP info for a live mempool tx. Returns `None` when the tx
21    /// isn't in the live pool, so callers can fall through to the
22    /// confirmed path. The snapshot can lag `state.txs` by up to one
23    /// cycle: if the seed is in the snapshot but no longer in live
24    /// state we return `None` rather than a half-stale report.
25    pub fn cpfp_info(&self, prefix: &TxidPrefix) -> Option<CpfpInfo> {
26        let snapshot = self.snapshot();
27        let seed_idx = snapshot.idx_of(prefix)?;
28        let seed = snapshot.tx(seed_idx)?;
29
30        let sigops = self.read().txs.get(&seed.txid)?.total_sigop_cost;
31
32        Some(snapshot.cpfp_info_at(seed_idx, seed, sigops))
33    }
34}
35
36impl Snapshot {
37    fn cpfp_info_at(&self, seed_idx: TxIndex, seed: &SnapTx, sigops: SigOps) -> CpfpInfo {
38        let ancestors = Self::collect_cpfp_entries(&self.txs, seed_idx, |t| &t.parents);
39        let descendants = Self::collect_cpfp_entries(&self.txs, seed_idx, |t| &t.children);
40        let best_descendant = descendants
41            .iter()
42            .max_by_key(|e| FeeRate::from((e.fee, e.weight)))
43            .cloned();
44
45        let (cluster, effective_fee_per_vsize) = Self::build_cpfp_cluster(&self.txs, seed_idx, seed);
46        let vsize = VSize::from(seed.weight);
47
48        CpfpInfo {
49            ancestors,
50            best_descendant,
51            descendants,
52            effective_fee_per_vsize,
53            sigops,
54            fee: seed.fee,
55            vsize,
56            adjusted_vsize: sigops.adjust_vsize(vsize),
57            cluster,
58        }
59    }
60
61    /// Capped DFS from `seed` (exclusive) along `next`, lifted directly
62    /// to wire-shape `CpfpEntry`s. Used for both ancestor and descendant
63    /// walks.
64    fn collect_cpfp_entries(
65        txs: &[SnapTx],
66        seed: TxIndex,
67        next: impl Fn(&SnapTx) -> &[TxIndex],
68    ) -> Vec<CpfpEntry> {
69        let Some(seed_node) = txs.get(seed.as_usize()) else {
70            return Vec::new();
71        };
72        let mut visited: FxHashSet<TxIndex> =
73            FxHashSet::with_capacity_and_hasher(CPFP_CHAIN_LIMIT + 1, FxBuildHasher);
74        visited.insert(seed);
75        let mut out: Vec<CpfpEntry> = Vec::with_capacity(CPFP_CHAIN_LIMIT);
76        let mut stack: Vec<TxIndex> = next(seed_node).to_vec();
77        while let Some(idx) = stack.pop() {
78            if out.len() >= CPFP_CHAIN_LIMIT {
79                break;
80            }
81            if !visited.insert(idx) {
82                continue;
83            }
84            if let Some(t) = txs.get(idx.as_usize()) {
85                out.push(CpfpEntry::from(t));
86                stack.extend(next(t).iter().copied());
87            }
88        }
89        out
90    }
91
92    /// Wire-shape `CpfpCluster` plus the seed's chunk feerate. Members
93    /// are the connected component of the seed in the dependency graph,
94    /// topologically ordered (parents before children) so wire indices
95    /// and chunk-internal ordering are valid for client-side
96    /// reconstruction. Returns `(None, seed_per_tx_rate)` for singletons
97    /// (matches mempool.space, which omits `cluster` when no relations
98    /// exist).
99    fn build_cpfp_cluster(
100        txs: &[SnapTx],
101        seed_idx: TxIndex,
102        seed: &SnapTx,
103    ) -> (Option<CpfpCluster>, FeeRate) {
104        let seed_per_tx_rate = FeeRate::from((seed.fee, seed.vsize));
105        let component = Cluster::walk(txs, seed_idx);
106        if component.len() <= 1 {
107            return (None, seed_per_tx_rate);
108        }
109
110        let (members, chunks) = Cluster::linearize(txs, &component);
111        let cluster_txs = Self::wire_cluster_members(txs, &members);
112        let seed_local = CpfpClusterTxIndex::from(
113            members
114                .iter()
115                .position(|&i| i == seed_idx)
116                .map_or(0, |p| p as u32),
117        );
118        let (chunk_index, seed_chunk_rate) = find_seed_chunk(&chunks, seed_local, seed_per_tx_rate);
119
120        (
121            Some(CpfpCluster {
122                txs: cluster_txs,
123                chunks,
124                chunk_index,
125            }),
126            seed_chunk_rate,
127        )
128    }
129
130    /// Materialize wire-shape `CpfpClusterTx`s for every topo-ordered
131    /// member with parent edges remapped to local indices.
132    fn wire_cluster_members(txs: &[SnapTx], members: &[TxIndex]) -> Vec<CpfpClusterTx> {
133        let local_of = Cluster::local_index(members);
134        members
135            .iter()
136            .map(|&idx| {
137                let t = &txs[idx.as_usize()];
138                CpfpClusterTx {
139                    txid: t.txid,
140                    weight: t.weight,
141                    fee: t.fee,
142                    parents: t
143                        .parents
144                        .iter()
145                        .filter_map(|p| local_of.get(p).copied())
146                        .collect(),
147                }
148            })
149            .collect()
150    }
151}
152
153#[cfg(test)]
154mod tests {
155    use brk_types::{FeeRate, Txid};
156
157    use super::*;
158    use crate::{
159        state::TxEntry,
160        test_support::{fake_entry_info, fake_tx, p2wpkh_script},
161    };
162
163    /// Insert a tx, optionally declaring parent dependencies for the
164    /// snapshot builder's adjacency wire-up.
165    fn insert_with_depends(
166        mempool: &Mempool,
167        seed: u8,
168        fee: u64,
169        vsize: u64,
170        parents: &[Txid],
171    ) -> Txid {
172        let tx = fake_tx(seed, &[None], &[(p2wpkh_script(seed + 1), 1_234)]);
173        let txid = tx.txid;
174        let mut info = fake_entry_info(txid, fee, vsize);
175        info.depends = parents.to_vec();
176        let entry = TxEntry::new(&info, vsize, false);
177        let mut state = mempool.test_state_lock().write();
178        state.txs.insert(tx, entry);
179        txid
180    }
181
182    #[test]
183    fn singleton_cpfp_info_has_no_cluster() {
184        let mempool = Mempool::for_test();
185        let txid = insert_with_depends(&mempool, 0xB0, 10_000, 100, &[]);
186        mempool.test_tick(&[txid], FeeRate::new(1.0));
187
188        let info = mempool
189            .cpfp_info(&TxidPrefix::from(&txid))
190            .expect("tx is in mempool");
191        assert!(info.cluster.is_none(), "singletons emit no cluster");
192        assert!(info.ancestors.is_empty());
193        assert!(info.descendants.is_empty());
194        // Effective rate equals isolated rate when there's no package lift.
195        let isolated = FeeRate::from((info.fee, info.vsize));
196        assert_eq!(info.effective_fee_per_vsize, isolated);
197    }
198
199    #[test]
200    fn two_tx_cpfp_cluster_has_both_members_and_lifted_rate() {
201        let mempool = Mempool::for_test();
202        let parent = insert_with_depends(&mempool, 0xB1, 100, 100, &[]);
203        let child = insert_with_depends(&mempool, 0xB2, 1_900, 100, &[parent]);
204        mempool.test_tick(&[parent, child], FeeRate::new(1.0));
205
206        let parent_info = mempool.cpfp_info(&TxidPrefix::from(&parent)).unwrap();
207        let cluster = parent_info.cluster.expect("two-tx cluster present");
208        assert_eq!(cluster.txs.len(), 2);
209        // Topological order: parent first.
210        assert_eq!(cluster.txs[0].txid, parent);
211        assert_eq!(cluster.txs[1].txid, child);
212        // Child reports the parent as its only local parent.
213        assert_eq!(cluster.txs[1].parents.len(), 1);
214        // CPFP lift: parent's effective rate exceeds its isolated rate.
215        let parent_isolated = FeeRate::from((parent_info.fee, parent_info.vsize));
216        assert!(parent_info.effective_fee_per_vsize > parent_isolated);
217        // Same package -> child's reported chunk rate matches parent's.
218        let child_info = mempool.cpfp_info(&TxidPrefix::from(&child)).unwrap();
219        assert_eq!(parent_info.effective_fee_per_vsize, child_info.effective_fee_per_vsize);
220    }
221
222    #[test]
223    fn cpfp_ancestor_and_descendant_walks_are_directional() {
224        // chain: A -> B -> C
225        let mempool = Mempool::for_test();
226        let a = insert_with_depends(&mempool, 0xB3, 100, 100, &[]);
227        let b = insert_with_depends(&mempool, 0xB4, 100, 100, &[a]);
228        let c = insert_with_depends(&mempool, 0xB5, 5_800, 100, &[b]);
229        mempool.test_tick(&[a, b, c], FeeRate::new(1.0));
230
231        // B sees A as an ancestor and C as a descendant.
232        let info_b = mempool.cpfp_info(&TxidPrefix::from(&b)).unwrap();
233        let ancestor_ids: Vec<_> = info_b.ancestors.iter().map(|e| e.txid).collect();
234        let descendant_ids: Vec<_> = info_b.descendants.iter().map(|e| e.txid).collect();
235        assert_eq!(ancestor_ids, vec![a]);
236        assert_eq!(descendant_ids, vec![c]);
237        // best_descendant picks the highest-rate descendant.
238        assert_eq!(info_b.best_descendant.as_ref().map(|e| e.txid), Some(c));
239    }
240
241    #[test]
242    fn cpfp_info_returns_none_for_unknown_txid() {
243        let mempool = Mempool::for_test();
244        mempool.test_tick(&[], FeeRate::new(1.0));
245        let bogus = TxidPrefix::from(&Txid::COINBASE);
246        assert!(mempool.cpfp_info(&bogus).is_none());
247    }
248}
brk_mempool/snapshot/cpfp.rs

brk_mempool/snapshot/
cpfp.rs
