From 98a7d5b88e975d529a4c8e6446ef8c3a4314281e Mon Sep 17 00:00:00 2001 From: Dmenec Date: Wed, 22 Jul 2026 17:30:35 +0200 Subject: [PATCH] feat(chain): classify outpoints by chain-level spend eligibility MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Adds classify_outpoints, which decides per-output whether it's settled, immature, or pending (trusted, untrusted, or unknown) based on its unsettled ancestry. Trust is resolved with a memoized ancestry walk: a tainting ancestor makes it untrusted, one missing from the view makes it unknown, and ancestors shared by several outputs are only walked once. Co-authored-by: 志宇 Co-Authored-By: Claude Opus 4.8 (1M context) --- crates/chain/src/canonical.rs | 172 +++++++++++++++++++++++++++++++++- 1 file changed, 171 insertions(+), 1 deletion(-) diff --git a/crates/chain/src/canonical.rs b/crates/chain/src/canonical.rs index c2aecb75..fc1db415 100644 --- a/crates/chain/src/canonical.rs +++ b/crates/chain/src/canonical.rs @@ -22,7 +22,7 @@ //! } //! ``` -use crate::collections::HashMap; +use crate::collections::{HashMap, HashSet}; use alloc::sync::Arc; use alloc::vec::Vec; use core::{fmt, ops::RangeBounds}; @@ -34,6 +34,32 @@ use bitcoin::{ use crate::{spk_txout::SpkTxOutIndex, Anchor, Balance, CanonicalViewTask, ChainPosition, TxGraph}; +/// The spend-eligibility classification of a canonical output, produced by +/// [`CanonicalView::classify_outpoints`]. +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +pub enum Eligibility { + /// An output the caller considers settled, per the `is_settled` predicate given to + /// [`classify_outpoints`](CanonicalView::classify_outpoints). Typically confirmed deeply + /// enough to be unlikely to be replaced, but the caller decides. + Settled, + /// A coinbase output that has not yet matured and is not spendable. + Immature, + /// An output not yet settled. + Unsettled(Trust), +} + +/// Describes whether an [`Unsettled`](Eligibility::Unsettled) output is trusted, untrusted, or of +/// unknown trust because the `CanonicalView` doesn't have its full ancestry. +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +pub enum Trust { + /// Ancestors spend owned outputs. + Trusted, + /// Ancestors spend foreign outputs. + Untrusted, + /// Some ancestor is not in Canonical set. + Unknown, +} + /// A single canonical transaction with its position. /// /// This struct represents a transaction that has been determined to be canonical (not @@ -394,6 +420,150 @@ impl Canonical { } impl CanonicalView { + /// Classify each of the given `outpoints` by its [spend eligibility](Eligibility). + /// This is the primitive behind [`balance`](Self::balance). + /// + /// Callers that need richer handling (coin selection, coin control, or + /// wallet-specific categories like "locked") can fold over this instead of `balance`. + /// + /// Outpoints that are already spent, or that aren't part of this canonical view, are skipped. + /// + /// # Arguments + /// + /// * `outpoints` - The outpoints to classify. + /// * `does_taint` - Returns `true` for a transaction that pulls in untrusted funds (e.g. it + /// spends an output the wallet doesn't own). It drives the [`Trust`] of an unsettled output: + /// a tainting transaction in its ancestry makes it [`Untrusted`](Trust::Untrusted). Outputs + /// with missing ancestry stay [`Unknown`](Trust::Unknown) regardless of this predicate. + /// * `is_settled` - Returns `true` for the [position](ChainPosition) of a transaction we + /// consider settled (unlikely to be replaced), for example one with enough confirmations. + pub fn classify_outpoints<'a>( + &'a self, + outpoints: impl IntoIterator + 'a, + mut does_taint: impl FnMut(&CanonicalTx>) -> bool + 'a, + is_settled: impl Fn(&ChainPosition) -> bool + 'a, + ) -> impl Iterator>, Eligibility)> + 'a { + let tip = self.tip.height; + // Shared across outpoints so an ancestor reached by several of them is only walked once. + let mut cache = HashMap::::new(); + outpoints + .into_iter() + .filter_map(move |op| self.txout(op)) + .filter(|txo| txo.spent_by.is_none()) + .map(move |txout| { + let eligibility = if !txout.is_mature(tip) { + Eligibility::Immature + } else if is_settled(&txout.pos) { + Eligibility::Settled + } else { + Eligibility::Unsettled(self.ancestry_trust( + txout.outpoint.txid, + &mut does_taint, + &is_settled, + &mut cache, + )) + }; + (txout, eligibility) + }) + } + + /// Returns the [`Trust`] of `seed_txid` based on its unsettled ancestry. + /// + /// Walks backwards from `seed_txid`, stopping at settled ancestors. + /// An ancestor missing from the [`CanonicalView`] set is [`Unknown`](Trust::Unknown). + /// Each visited transaction is cached, so an ancestor shared by several outpoints only gets + /// walked once across the calls to this method that share the same `cache`. + /// The walk stops at [`Settled`](Eligibility::Settled) transactions and at + /// [`Unknown`](Trust::Unknown) ones, and performs a short-circuit as soon as a tainting + /// transaction is found. + fn ancestry_trust( + &self, + seed_txid: Txid, + does_taint: &mut F, + is_settled: &S, + cache: &mut HashMap, + ) -> Trust + where + F: FnMut(&CanonicalTx>) -> bool, + S: Fn(&ChainPosition) -> bool, + { + if let Some(&trust) = cache.get(&seed_txid) { + return trust; + } + + // `Enter`: if tx is unsettled and not directly tainted, queue its parents. + // `Exit`: by now every parent is resolved, so the tx is tainted if any parent is. + enum Frame { + Enter(Txid), + Exit(CanonicalTx>), + } + + let mut stack = alloc::vec![Frame::Enter(seed_txid)]; + // Txids currently on the stack between their `Enter` and `Exit`, so we don't queue the + // same parent twice while it's still being processed. + let mut pending = HashSet::::new(); + + while let Some(frame) = stack.pop() { + match frame { + Frame::Enter(txid) => { + if cache.contains_key(&txid) || pending.contains(&txid) { + continue; + } + let Some(c_tx) = self.tx(txid) else { + // Missing from the `CanonicalView`. + cache.insert(txid, Trust::Unknown); + continue; + }; + if is_settled(&c_tx.pos) { + cache.insert(txid, Trust::Trusted); + continue; + } + if does_taint(&c_tx) { + // Directly tainted + cache.insert(txid, Trust::Untrusted); + continue; + } + pending.insert(txid); + stack.push(Frame::Exit(c_tx.clone())); + for txin in &c_tx.tx.input { + // Previous output is coinbase + if txin.previous_output.is_null() { + continue; + } + let parent_txid = txin.previous_output.txid; + if !cache.contains_key(&parent_txid) && !pending.contains(&parent_txid) { + stack.push(Frame::Enter(parent_txid)); + } + } + } + Frame::Exit(c_tx) => { + let mut trust = Trust::Trusted; + for txin in &c_tx.tx.input { + if txin.previous_output.is_null() { + continue; + } + let parent_trust = cache + .get(&txin.previous_output.txid) + .copied() + .unwrap_or(Trust::Trusted); + trust = match (trust, parent_trust) { + (Trust::Untrusted, _) | (_, Trust::Untrusted) => Trust::Untrusted, + (Trust::Unknown, _) | (_, Trust::Unknown) => Trust::Unknown, + _ => Trust::Trusted, + }; + if trust == Trust::Untrusted { + break; + } + } + cache.insert(c_tx.txid, trust); + pending.remove(&c_tx.txid); + } + } + } + + cache[&seed_txid] + } + /// Calculate the total balance of the given outpoints. /// /// This method computes a detailed balance breakdown for a set of outpoints, categorizing -- 2.49.0