//! BEEF format (BRC-62/95/96) for SPV transaction proofs.
//!
//! BEEF (Background Evaluation Extended Format) is the standard format for
//! exchanging SPV (Simplified Payment Verification) transaction proofs.
//!
//! # Supported Standards
//!
//! - **BRC-62**: BEEF V1 format
//! - **BRC-74**: BUMP (BSV Unified Merkle Path) format for merkle proofs
//! - **BRC-95**: Atomic BEEF for single-transaction proofs
//! - **BRC-96**: BEEF V2 with TXID-only extension
//!
//! # Example
//!
//! ```rust,ignore
//! use bsv_rs::transaction::Beef;
//!
//! // Parse from hex
//! let beef = Beef::from_hex("...")?;
//!
//! // Validate structure
//! assert!(beef.is_valid(false));
//!
//! // Find a transaction
//! if let Some(tx) = beef.find_txid("abc123...") {
//! println!("Found transaction");
//! }
//!
//! // Serialize back
//! let hex = beef.to_hex();
//! ```
use std::collections::{HashMap, HashSet};
use crate::primitives::encoding::bounded_capacity;
use crate::primitives::{from_hex, to_hex, Reader, Writer};
use crate::Result;
use super::beef_stream::{display_hex, merkle_path_root, Kind, Reason, Refusal};
use super::beef_tx::{BeefTx, ATOMIC_BEEF, BEEF_V1, BEEF_V2};
use super::merkle_path::MerklePath;
use super::transaction::Transaction;
/// Result of sorting transactions in a BEEF.
#[derive(Debug, Clone, Default)]
pub struct SortResult {
/// TXIDs of inputs that are missing from the BEEF.
pub missing_inputs: Vec<String>,
/// TXIDs of transactions that are not valid (no proof and don't chain to proofs).
pub not_valid: Vec<String>,
/// TXIDs of valid transactions.
pub valid: Vec<String>,
/// TXIDs of transactions that have missing inputs.
pub with_missing_inputs: Vec<String>,
/// TXIDs of txid-only transactions.
pub txid_only: Vec<String>,
}
/// Result of BEEF validation.
#[derive(Debug, Clone)]
pub struct BeefValidationResult {
/// Whether the BEEF is structurally valid.
pub valid: bool,
/// Merkle roots keyed by block height (to be verified by chain tracker).
pub roots: HashMap<u32, String>,
}
/// Memory hints for [`Beef::from_binary_with_limits`]: how many entries of
/// each kind the in-memory parse may reserve room for ahead of reading them.
///
/// These are not limits on what is accepted. Since 0.4.0 a valid BEEF is
/// never refused for its size or its counts: a BEEF with more transactions
/// or BUMPs than the hints is read all the same, and the vectors grow as the
/// entries arrive. A door that reads a stranger's BEEF reads it with
/// [`verify_stream`](super::beef_stream::verify_stream), which holds one
/// element at a time and ignores these hints.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct BeefLimits {
/// The most transactions (full or txid-only) to reserve room for.
pub max_txs: usize,
/// The most BUMPs (merkle paths) to reserve room for.
pub max_bumps: usize,
}
/// BEEF (Background Evaluation Extended Format) for SPV proofs.
///
/// A BEEF contains:
/// - A list of BUMPs (merkle paths) proving transactions are in blocks
/// - A list of transactions (full or txid-only)
///
/// Transactions must be sorted in dependency order (oldest first).
#[derive(Debug, Clone)]
pub struct Beef {
/// Merkle paths (BUMPs) for proving transactions.
pub bumps: Vec<MerklePath>,
/// Transactions in the BEEF.
pub txs: Vec<BeefTx>,
/// BEEF format version (V1 or V2).
pub version: u32,
/// For Atomic BEEF, the target transaction ID.
pub atomic_txid: Option<String>,
/// Index of txids to BeefTx for fast lookup.
txid_index: HashMap<String, usize>,
/// Whether the transactions need sorting.
needs_sort: bool,
}
impl Beef {
/// Creates a new empty BEEF with V2 format.
pub fn new() -> Self {
Self::with_version(BEEF_V2)
}
/// Creates a new empty BEEF with the specified version.
pub fn with_version(version: u32) -> Self {
Self {
bumps: Vec::new(),
txs: Vec::new(),
version,
atomic_txid: None,
txid_index: HashMap::new(),
needs_sort: true,
}
}
/// Marks the BEEF as needing re-sort.
fn mark_mutated(&mut self) {
self.needs_sort = true;
}
/// Rebuilds the txid index.
fn rebuild_index(&mut self) {
self.txid_index.clear();
for (i, tx) in self.txs.iter().enumerate() {
self.txid_index.insert(tx.txid(), i);
}
}
/// Finds a BeefTx by txid.
pub fn find_txid(&self, txid: &str) -> Option<&BeefTx> {
self.txid_index.get(txid).map(|&i| &self.txs[i])
}
/// Finds a BeefTx by txid (mutable).
pub fn find_txid_mut(&mut self, txid: &str) -> Option<&mut BeefTx> {
self.txid_index.get(txid).map(|&i| &mut self.txs[i])
}
/// Finds a MerklePath that contains the given txid.
pub fn find_bump(&self, txid: &str) -> Option<&MerklePath> {
self.bumps.iter().find(|b| b.contains(txid))
}
/// Finds a transaction and populates its input source transactions from this BEEF.
pub fn find_transaction_for_signing(&self, txid: &str) -> Option<Transaction> {
let beef_tx = self.find_txid(txid)?;
let tx = beef_tx.tx()?.clone();
// Would need to populate source transactions - simplified for now
Some(tx)
}
/// Builds the proof tree rooted at a specific transaction.
pub fn find_atomic_transaction(&self, txid: &str) -> Option<Transaction> {
let beef_tx = self.find_txid(txid)?;
let mut tx = beef_tx.tx().cloned()?;
self.add_input_proof(&mut tx);
Some(tx)
}
/// Attach merkle paths and source transactions to `tx` and its whole
/// input ancestry, LINEARLY: every distinct unproven parent is linked in
/// full exactly once (memoized by txid), and every later input that
/// sources the same txid gets a BARE STUB of it: the parent transaction
/// itself (its outputs are what the input spends), carrying its BUMP when
/// this BEEF proves it, with every one of ITS inputs' `source_transaction`
/// left `None`.
///
/// Port of the TypeScript `Beef.addInputProof` (`@bsv/sdk`
/// `transaction/Beef.ts`): a transaction with a BUMP in this BEEF gets it
/// as its `merkle_path` and is not descended (a proven transaction needs
/// no ancestry); an unproven one has each input's `source_transaction`
/// linked from this BEEF and is descended in turn.
///
/// The TS walk keeps one `Transaction` object per txid and assigns it to
/// every input by reference, so linking it once links it everywhere.
/// Rust stores `source_transaction` as an owned `Box`, one copy per input,
/// so the reference structure cannot be reproduced exactly and the two
/// naive answers are both wrong:
///
/// - link only the first occurrence and hand later inputs a bare clone
/// (0.3.20): the structure stays linear, but the old object-graph
/// `Transaction::verify` reached the bare clone and refused a complete
/// BEEF with "Input N has no source transaction", and two inputs
/// sourcing the same unproven parent (a covenant output plus that
/// transaction's own change) is the ordinary shape of a wallet's
/// second spend;
/// - link every input in full by cloning the memoized parent (0.3.21):
/// correct for that walk, but EXPONENTIAL. On a diamond chain, where
/// each level spends both outputs of the previous unproven level (a
/// wallet's ordinary change chain), every level then carries two full
/// copies of the level below it: 24 levels = 2^24 subtrees, and
/// `from_beef` died on memory before verification even started.
///
/// So the structure stays linear as in 0.3.20 (one full link per txid plus
/// one cheap stub per repeat), and [`Transaction::verify`] no longer cares
/// which copy it reaches: it gathers the reachable transactions by txid and
/// looks every input's source up in that map.
///
/// The walk is ITERATIVE (0.3.35, bsv-stack-lean #57): an explicit stack of
/// frames replaces the call that recursed once per unproven link, so a
/// stranger's chain of unproven transactions costs heap, not stack (a
/// 1 MiB stack, the order of a WASM stack in a Worker, overflowed at a few
/// hundred links and the abort took every request in flight with it). The
/// frames are visited in the recursion's order (depth first, inputs in
/// order), so which input gets the full link and which a stub, and the
/// resulting `source_transaction` shape, are exactly the recursive walk's.
/// The reference walks iteratively too (`@bsv/sdk` `Beef.#addInputProof`).
/// Bumps are looked up through an index built once, so the walk is linear
/// in the BEEF rather than in transactions times bumps.
fn add_input_proof(&self, tx: &mut Transaction) {
/// One transaction being linked, and the next input to link.
struct Frame {
tx: Transaction,
next_input: usize,
}
// `find_bump`'s answer for every hash at level 0: the FIRST bump whose
// leaf level carries it, as `find_bump`'s scan returns.
let mut bump_by_txid: HashMap<&str, &MerklePath> = HashMap::new();
for bump in &self.bumps {
for leaf in bump.path.first().into_iter().flatten() {
if let Some(hash) = leaf.hash.as_deref() {
bump_by_txid.entry(hash).or_insert(bump);
}
}
}
let find_bump = |txid: &str| bump_by_txid.get(txid).copied();
// Attach a transaction's own proof; a proven transaction is not
// descended (its frame starts with no input left to link).
let enter = |mut tx: Transaction| -> Frame {
if tx.merkle_path.is_none() {
if let Some(mp) = find_bump(&tx.id()) {
tx.merkle_path = Some(mp.clone());
}
}
let next_input = if tx.merkle_path.is_some() {
tx.inputs.len()
} else {
0
};
Frame { tx, next_input }
};
// Keyed by txid, the value being the stub handed to later inputs.
// Presence also means "this txid has been linked in full once".
let mut stubs: HashMap<String, Transaction> = HashMap::new();
let mut stack: Vec<Frame> = vec![enter(std::mem::take(tx))];
while let Some(top) = stack.last_mut() {
if top.next_input == top.tx.inputs.len() {
// Every input of this transaction is linked: hand it to the
// input of its parent that it sources, or back to the caller.
let done = stack.pop().expect("the stack is not empty").tx;
match stack.last_mut() {
Some(parent) => {
parent.tx.inputs[parent.next_input - 1].source_transaction =
Some(Box::new(done));
}
None => *tx = done,
}
continue;
}
let input = &mut top.tx.inputs[top.next_input];
top.next_input += 1;
let Some(src_txid) = input.source_txid.clone() else {
continue;
};
if let Some(stub) = stubs.get(&src_txid) {
// Already linked in full once: this input gets the stub, which
// carries the output being spent (and the proof when there is
// one) without repeating the ancestry underneath it.
input.source_transaction = Some(Box::new(stub.clone()));
continue;
}
// Take the caller's own source when it carries one, else this BEEF's.
let mut src = match input.source_transaction.take() {
Some(own) => *own,
None => match self.find_txid(&src_txid).and_then(|b| b.tx().cloned()) {
Some(found) => found,
None => continue, // not in this BEEF: left unlinked, as before
},
};
// Memoize the stub BEFORE descending: a BEEF whose source links
// form a cycle then terminates instead of walking forever, and for
// the honest DAG case the order makes no difference (a transaction
// is never reachable from inside its own ancestry).
let stub = Self::bare_stub(&mut src, find_bump(&src_txid));
stubs.insert(src_txid, stub);
stack.push(enter(src));
}
}
/// A bare copy of `tx`: the transaction with its BUMP when the BEEF proves
/// it, and with every input's `source_transaction` dropped, so no ancestry
/// is duplicated. The ancestry is lifted out before the clone and put back
/// after, so building a stub never copies a subtree.
fn bare_stub(tx: &mut Transaction, bump: Option<&MerklePath>) -> Transaction {
let ancestry: Vec<Option<Box<Transaction>>> = tx
.inputs
.iter_mut()
.map(|input| input.source_transaction.take())
.collect();
let mut stub = tx.clone();
for (input, source) in tx.inputs.iter_mut().zip(ancestry) {
input.source_transaction = source;
}
if stub.merkle_path.is_none() {
if let Some(mp) = bump {
stub.merkle_path = Some(mp.clone());
}
}
stub
}
/// Merges a MerklePath into this BEEF.
///
/// If a path with the same block height and root already exists, combines them.
///
/// # Returns
///
/// The index of the merged bump.
pub fn merge_bump(&mut self, bump: MerklePath) -> usize {
// Check for existing bump with same block height and root
for (i, existing) in self.bumps.iter_mut().enumerate() {
if existing.block_height == bump.block_height {
if let (Ok(root1), Ok(root2)) =
(existing.compute_root(None), bump.compute_root(None))
{
if root1 == root2 {
// Combine the bumps
let _ = existing.combine(&bump);
self.update_bump_indices(i);
return i;
}
}
}
}
// Add as new bump
let index = self.bumps.len();
self.bumps.push(bump);
self.update_bump_indices(index);
index
}
/// Updates bump indices for transactions proven by a bump.
/// Only assigns the bump if the txid appears as a flagged leaf (txid=true).
/// This prevents a tx from being claimed by a bump where it appears only
/// as a sibling hash. Matches TS SDK behavior where the txid flag is
/// checked/set during bump index assignment.
fn update_bump_indices(&mut self, bump_index: usize) {
let bump = &self.bumps[bump_index];
for tx in &mut self.txs {
if tx.bump_index().is_none() {
let txid = tx.txid();
// Only assign if the leaf has txid=true (a proper proven tx,
// not just a sibling hash used for proof computation)
let is_txid_leaf = bump.path[0]
.iter()
.any(|l| l.txid && l.hash.as_deref() == Some(&txid));
if is_txid_leaf {
tx.set_bump_index(Some(bump_index));
}
}
}
}
/// Merges a transaction into this BEEF.
///
/// If the transaction has a merkle path, it's also merged.
/// Replaces any existing transaction with the same txid.
pub fn merge_transaction(&mut self, tx: Transaction) -> &BeefTx {
let txid = tx.id();
self.remove_existing_txid(&txid);
let bump_index = None; // Could be set if tx has merklePath
let new_tx = BeefTx::from_tx(tx, bump_index);
self.txs.push(new_tx);
let idx = self.txs.len() - 1;
self.txid_index.insert(txid.clone(), idx);
self.try_to_validate_bump_index(idx);
self.mark_mutated();
&self.txs[idx]
}
/// Merges raw transaction bytes into this BEEF.
pub fn merge_raw_tx(&mut self, raw_tx: Vec<u8>, bump_index: Option<usize>) -> &BeefTx {
let new_tx = BeefTx::from_raw_tx(raw_tx, bump_index);
let txid = new_tx.txid();
self.remove_existing_txid(&txid);
self.txs.push(new_tx);
let idx = self.txs.len() - 1;
self.txid_index.insert(txid, idx);
self.try_to_validate_bump_index(idx);
self.mark_mutated();
&self.txs[idx]
}
/// Merges a txid-only entry into this BEEF.
pub fn merge_txid_only(&mut self, txid: String) -> &BeefTx {
if let Some(&idx) = self.txid_index.get(&txid) {
return &self.txs[idx];
}
let new_tx = BeefTx::from_txid(txid.clone());
self.txs.push(new_tx);
let idx = self.txs.len() - 1;
self.txid_index.insert(txid, idx);
self.try_to_validate_bump_index(idx);
self.mark_mutated();
&self.txs[idx]
}
/// Converts an existing transaction to txid-only format.
///
/// This is used to trim known transactions from BEEF before returning to caller,
/// reducing the BEEF size when the recipient already has the full transaction.
///
/// Returns the modified BeefTx if found, None if txid not in BEEF.
pub fn make_txid_only(&mut self, txid: &str) -> Option<&BeefTx> {
let idx = *self.txid_index.get(txid)?;
// If already txid-only, just return it
if self.txs[idx].is_txid_only() {
return Some(&self.txs[idx]);
}
// Replace with txid-only version
let new_tx = BeefTx::from_txid(txid.to_string());
self.txs[idx] = new_tx;
self.mark_mutated();
Some(&self.txs[idx])
}
/// Removes an existing transaction by txid.
fn remove_existing_txid(&mut self, txid: &str) {
if let Some(&idx) = self.txid_index.get(txid) {
self.txs.remove(idx);
self.rebuild_index();
self.mark_mutated();
}
}
/// Tries to validate a bump index for a new transaction.
///
/// STRICT MATCHING ONLY: assigns `bump_index` if-and-only-if some bump's
/// level-0 leaf has `txid=true` AND `hash == tx.txid()`. If no such leaf
/// exists, `bump_index` remains `None`.
///
/// A previous iteration of this function included a permissive second
/// pass that matched ANY leaf hash at level 0 (including sibling hashes
/// used only for merkle computation) and mutated the leaf's `txid` flag
/// to `true`. That was incorrect: a tx's txid can legitimately appear as
/// a sibling hash in an unrelated bump, and marking it as a txid-leaf
/// there would claim a proof that does not belong to it.
///
/// The Go SDK (`go-sdk/transaction/beef.go:tryToValidateBumpIndex`) only
/// validates/discards already-assigned paths and does not auto-discover
/// from siblings. This matches that strict semantics. The TS SDK still
/// has the permissive variant; fixing it there is a separate effort.
fn try_to_validate_bump_index(&mut self, tx_idx: usize) {
if self.txs[tx_idx].bump_index().is_some() {
return;
}
let txid = self.txs[tx_idx].txid();
// Strict match: leaf has txid=true AND hash == tx.txid().
for (i, bump) in self.bumps.iter().enumerate() {
let is_txid_leaf = bump
.path
.first()
.map(|level0| {
level0
.iter()
.any(|l| l.txid && l.hash.as_deref() == Some(&txid))
})
.unwrap_or(false);
if is_txid_leaf {
self.txs[tx_idx].set_bump_index(Some(i));
return;
}
}
}
/// Merges another BEEF into this one.
///
/// Bumps are merged first and may receive new indices in self. Transactions
/// are then merged WITHOUT passing bump indices from the source — instead,
/// `try_to_validate_bump_index` discovers the correct index by scanning
/// self.bumps. This matches the TypeScript SDK's `mergeBeefTx` behavior.
pub fn merge_beef(&mut self, other: &Beef) {
for bump in &other.bumps {
self.merge_bump(bump.clone());
}
for tx in &other.txs {
if tx.is_txid_only() {
self.merge_txid_only(tx.txid());
} else if let Some(raw) = tx.raw_tx() {
// Do NOT pass tx.bump_index() — it's the old index from
// `other` which is invalid after bumps were re-indexed.
// merge_raw_tx calls try_to_validate_bump_index to discover
// the correct index by scanning self.bumps.
self.merge_raw_tx(raw.to_vec(), None);
} else if let Some(t) = tx.tx() {
self.merge_transaction(t.clone());
}
}
}
/// Trims ancestor transactions that are no longer needed because their
/// dependents now have merkle proofs (BUMPs).
///
/// In BEEF, a transaction with a BUMP is self-proving via its merkle path
/// and does not require its ancestor transactions to also be present.
/// This method walks the dependency graph from tip transactions (those not
/// spent by any other tx in the BEEF) and removes any transaction that is
/// only reachable through proven (bumped) transactions.
///
/// This is useful after upgrading previously-unproven transactions with
/// newly-available merkle proofs, allowing their deep ancestor chains to
/// be removed.
pub fn trim_known_proven(&mut self) {
use std::collections::{HashSet, VecDeque};
let all_txids: HashSet<String> = self.txs.iter().map(|tx| tx.txid()).collect();
// Find which txids are referenced as inputs by other txs in the BEEF.
// Note: proven txs have empty input_txids (cleared by set_bump_index),
// so we also parse their raw tx bytes to recover the full reference graph.
let mut referenced_as_input: HashSet<String> = HashSet::new();
for tx in &mut self.txs {
let input_refs: Vec<String> = if !tx.input_txids.is_empty() {
tx.input_txids.clone()
} else if let Some(parsed) = tx.tx_mut() {
parsed
.inputs
.iter()
.filter_map(|inp| inp.get_source_txid().ok())
.collect::<Vec<String>>()
} else {
Vec::new()
};
for input_txid in &input_refs {
if all_txids.contains(input_txid) {
referenced_as_input.insert(input_txid.clone());
}
}
}
// Tip transactions: not referenced as an input by any other tx in the BEEF
let tips: Vec<String> = all_txids
.iter()
.filter(|txid| !referenced_as_input.contains(*txid))
.cloned()
.collect();
// BFS from tips: mark needed txids, stop at proven txs
let mut needed: HashSet<String> = HashSet::new();
let mut queue: VecDeque<String> = VecDeque::from(tips);
while let Some(txid) = queue.pop_front() {
if needed.contains(&txid) {
continue;
}
needed.insert(txid.clone());
if let Some(tx) = self.find_txid(&txid) {
// Proven tx is self-sufficient — don't need its ancestors
if tx.bump_index().is_some() {
continue;
}
// Unproven — need its input txids too
for input_txid in tx.input_txids.clone() {
if all_txids.contains(&input_txid) && !needed.contains(&input_txid) {
queue.push_back(input_txid);
}
}
}
}
// Nothing to trim
if needed.len() == self.txs.len() {
return;
}
// Remove unneeded transactions
self.txs.retain(|tx| needed.contains(&tx.txid()));
self.rebuild_index();
// Clean up unused BUMPs and remap indices
let used_bump_indices: HashSet<usize> =
self.txs.iter().filter_map(|tx| tx.bump_index()).collect();
if used_bump_indices.len() < self.bumps.len() {
let mut new_bumps = Vec::new();
let mut index_map: HashMap<usize, usize> = HashMap::new();
for (old_idx, bump) in self.bumps.iter().enumerate() {
if used_bump_indices.contains(&old_idx) {
let new_idx = new_bumps.len();
index_map.insert(old_idx, new_idx);
new_bumps.push(bump.clone());
}
}
self.bumps = new_bumps;
for tx in &mut self.txs {
if let Some(old_idx) = tx.bump_index() {
if let Some(&new_idx) = index_map.get(&old_idx) {
tx.set_bump_index(Some(new_idx));
}
}
}
}
self.mark_mutated();
}
/// Checks if this BEEF is structurally valid: [`verify_valid`](Self::verify_valid)`.valid`.
///
/// Does NOT verify merkle roots against a chain tracker.
///
/// # Arguments
///
/// * `allow_txid_only` - Decides nothing since 0.4.2: a txid-only entry
/// is valid when a BUMP of this BEEF proves its txid, and not otherwise
/// (see [`verify_structure`](Self::verify_structure)).
pub fn is_valid(&mut self, allow_txid_only: bool) -> bool {
self.verify_valid(allow_txid_only).valid
}
/// Validates the BEEF structure and returns roots to verify:
/// [`verify_structure`](Self::verify_structure) without the kind.
///
/// `allow_txid_only` decides nothing since 0.4.2. Through 0.4.1 it
/// accepted every txid-only entry when true and refused every one when
/// false; the streaming reader, and this, read each entry: valid when a
/// BUMP of this BEEF proves its txid, [`Kind::StubNotProven`] otherwise
/// (bsv-stack-lean NL-8 W5).
pub fn verify_valid(&mut self, allow_txid_only: bool) -> BeefValidationResult {
let _ = allow_txid_only;
match self.verify_structure() {
Ok(roots) => BeefValidationResult { valid: true, roots },
Err(_) => BeefValidationResult {
valid: false,
roots: HashMap::new(),
},
}
}
/// The whole BEEF's structure on the streaming reader's rules: the roots
/// to check against the headers by height, or the reader's [`Kind`] for
/// what is wrong (the in-memory BEEF has no offsets to name).
///
/// - Each BUMP's root is the reader's walk (`beef_stream`'s `bump_root`), once per BUMP
/// and linear in its leaves (0.4.2; at 0.4.1 the walk ran once per leaf,
/// NL-8 W1). A lone leaf is the block of one transaction only at offset
/// 0; at any other offset it is [`Kind::MissingSibling`] (NL-8 W2). Two
/// BUMPs at one height with different roots: [`Kind::RootNotCarried`]
/// (the headers carry one root per height).
/// - A raw transaction with no input: [`Kind::NoInputs`] (0.4.1); one with
/// an input and no output: [`Kind::NoOutputs`] (0.4.3). The first such
/// transaction in the order held when this is called, as the reader
/// meets the first on the wire.
/// - A txid-only entry no BUMP of this BEEF proves: [`Kind::StubNotProven`]
/// (NL-8 W5).
/// - A BUMP index that names no BUMP, or a BUMP that does not carry the
/// txid: [`Kind::BumpIndexNamesNoBump`], [`Kind::TxidNotInBump`].
/// - An input of an unproven transaction that names no transaction of
/// this BEEF, or one that never becomes valid: [`Kind::InputNamesNoElement`].
/// The transactions are sorted first ([`sort_txs`](Self::sort_txs)), as
/// the reference sorts them; the stream reads its order as written.
/// - Atomic (NL-8 W4): the subject is the last raw transaction, else
/// [`Kind::SubjectMissing`]; every other transaction or txid-only entry
/// is spent by a later raw transaction, else
/// [`Kind::UnrelatedTransaction`]. "Last" and "later" are the order the
/// transactions hold when this is called, before its sort: the wire's
/// for a BEEF just read, the writer's for one built here.
///
/// A byte after the frame (NL-8 W3) is refused by [`from_binary`](Self::from_binary)
/// before this runs.
pub fn verify_structure(&mut self) -> std::result::Result<HashMap<u32, String>, Kind> {
// The atomic rule reads the order as held, so it is judged before
// the sort and answered after the rest, where the reader's `finish`
// answers it.
let atomic = match self.atomic_txid.clone() {
Some(subject) => self.atomic_rule(&subject),
None => Ok(()),
};
// The first transaction that is no transaction, in the order held
// (the reader's), before the sort moves it.
let no_transaction = self.txs.iter().find_map(|tx| {
if tx.has_no_inputs() {
Some(Kind::NoInputs)
} else if tx.has_no_outputs() {
Some(Kind::NoOutputs)
} else {
None
}
});
let sr = self.sort_txs();
// Each BUMP's root, by the streaming reader's walk: once per BUMP,
// linear in its leaves (0.4.2). At 0.4.1 each flagged leaf computed
// the root afresh, rebuilding every node it needed from level 0: a
// BUMP of 8,192 leaves gave no answer in 120 s (bsv-stack-lean NL-8
// W1, #61).
let mut roots: HashMap<u32, String> = HashMap::new();
for bump in &self.bumps {
let root = display_hex(&merkle_path_root(bump).map_err(|r| r.kind())?);
match roots.get(&bump.block_height) {
Some(existing) if *existing != root => return Err(Kind::RootNotCarried),
Some(_) => {}
None => {
roots.insert(bump.block_height, root);
}
}
}
// Every hash of each BUMP's level 0 is a txid that BUMP proves,
// indexed once.
let carried: HashSet<(usize, &str)> = self
.bumps
.iter()
.enumerate()
.flat_map(|(i, bump)| {
bump.path
.first()
.into_iter()
.flatten()
.filter_map(move |l| l.hash.as_deref().map(|h| (i, h)))
})
.collect();
let proven: HashSet<&str> = carried.iter().map(|(_, h)| *h).collect();
if let Some(kind) = no_transaction {
return Err(kind);
}
let mut valid_txids: HashSet<String> = HashSet::new();
for tx in &self.txs {
if tx.is_txid_only() {
let txid = tx.txid();
if !proven.contains(txid.as_str()) {
return Err(Kind::StubNotProven);
}
valid_txids.insert(txid);
}
}
for tx in &self.txs {
if let Some(bump_idx) = tx.bump_index() {
if bump_idx >= self.bumps.len() {
return Err(Kind::BumpIndexNamesNoBump);
}
let txid = tx.txid();
if !carried.contains(&(bump_idx, txid.as_str())) {
return Err(Kind::TxidNotInBump);
}
valid_txids.insert(txid);
}
}
if !sr.missing_inputs.is_empty()
|| !sr.not_valid.is_empty()
|| !sr.with_missing_inputs.is_empty()
{
return Err(Kind::InputNamesNoElement);
}
// Verify dependency order
for tx in &self.txs {
for input_txid in &tx.input_txids {
if !valid_txids.contains(input_txid) {
return Err(Kind::InputNamesNoElement);
}
}
valid_txids.insert(tx.txid());
}
atomic?;
Ok(roots)
}
/// The atomic rule on the transactions in the order they hold (the
/// streaming reader's `BeefIndex::finish`): `subject` is the last raw
/// transaction, and every other entry is spent by a later raw
/// transaction.
fn atomic_rule(&self, subject: &str) -> std::result::Result<(), Kind> {
let mut last_raw: Option<String> = None;
let mut referenced: HashMap<String, bool> = HashMap::new();
for tx in &self.txs {
let txid = tx.txid();
if !tx.is_txid_only() {
for prev in spent_txids(tx) {
if let Some(r) = referenced.get_mut(&prev) {
*r = true;
}
}
last_raw = Some(txid.clone());
}
referenced.entry(txid).or_insert(false);
}
if last_raw.as_deref() != Some(subject) {
return Err(Kind::SubjectMissing);
}
if referenced.iter().any(|(txid, r)| !r && txid != subject) {
return Err(Kind::UnrelatedTransaction);
}
Ok(())
}
/// Sorts transactions by dependency order.
///
/// The order is the one a repeated scan of the pending transactions
/// produces (each scan accepts, in BEEF order, every transaction whose
/// inputs are valid by then), but it is computed in one pass with a
/// work list keyed by (scan, position) instead of rescanning: a chain
/// written newest first made the rescan quadratic, 767.8 s for 128,000
/// links (0.3.35, bsv-stack-lean #57). The reference sorts the same way
/// (`@bsv/sdk` `Beef.#topoSort`, "preserve the legacy repeated-scan
/// ordering without repeating scans").
pub fn sort_txs(&mut self) -> SortResult {
use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashSet};
let mut result = SortResult::default();
let mut valid_txids: HashMap<String, bool> = HashMap::new();
let txids: Vec<String> = self.txs.iter().map(|tx| tx.txid()).collect();
let known: HashSet<&str> = txids.iter().map(String::as_str).collect();
// Separate transactions by type
let mut with_proof: Vec<usize> = Vec::new();
let mut txid_only: Vec<usize> = Vec::new();
let mut queue: Vec<usize> = Vec::new();
for (i, tx) in self.txs.iter_mut().enumerate() {
tx.is_valid = Some(tx.has_proof());
if tx.has_proof() {
valid_txids.insert(txids[i].clone(), true);
with_proof.push(i);
} else if tx.is_txid_only() && tx.input_txids.is_empty() {
valid_txids.insert(txids[i].clone(), true);
txid_only.push(i);
result.txid_only.push(txids[i].clone());
} else {
queue.push(i);
}
}
// Check for missing inputs
let mut with_missing: Vec<usize> = Vec::new();
let mut pending: Vec<usize> = Vec::new();
for &i in &queue {
let mut has_missing = false;
for input_txid in &self.txs[i].input_txids {
if !known.contains(input_txid.as_str()) {
result.missing_inputs.push(input_txid.clone());
has_missing = true;
}
}
if has_missing {
with_missing.push(i);
result.with_missing_inputs.push(txids[i].clone());
} else {
pending.push(i);
}
}
// Each pending transaction waits on its inputs that are not valid
// yet; `dependents` lists the waiters of each such txid.
let n = self.txs.len();
let mut waiting_on = vec![0usize; n];
let mut dependents: HashMap<&str, Vec<usize>> = HashMap::new();
for &i in &pending {
for input_txid in &self.txs[i].input_txids {
if !valid_txids.contains_key(input_txid) {
waiting_on[i] += 1;
dependents.entry(input_txid.as_str()).or_default().push(i);
}
}
}
// Accept in (scan, position) order. A transaction's scan is the first
// in which every input it waits on was valid before its position: an
// input made valid at (scan s, position p) counts from scan s for a
// waiter after p, and from scan s + 1 for a waiter before p. A txid is
// valid from its first accepted entry.
let mut scan = vec![0usize; n];
let mut accepted = vec![false; n];
let mut ready: BinaryHeap<Reverse<(usize, usize)>> = pending
.iter()
.filter(|&&i| waiting_on[i] == 0)
.map(|&i| Reverse((0, i)))
.collect();
let mut sorted_pending: Vec<usize> = Vec::new();
while let Some(Reverse((s, i))) = ready.pop() {
accepted[i] = true;
sorted_pending.push(i);
if valid_txids.insert(txids[i].clone(), true).is_some() {
continue; // a repeated txid: its waiters were released already
}
for j in dependents.remove(txids[i].as_str()).unwrap_or_default() {
let from = if i < j { s } else { s + 1 };
scan[j] = scan[j].max(from);
waiting_on[j] -= 1;
if waiting_on[j] == 0 {
ready.push(Reverse((scan[j], j)));
}
}
}
// Remaining are not valid
let not_valid: Vec<usize> = pending.into_iter().filter(|&i| !accepted[i]).collect();
for &i in ¬_valid {
result.not_valid.push(txids[i].clone());
}
// Collect valid txids
result.valid = valid_txids.keys().cloned().collect();
// Reorder transactions - build new order indices
let mut new_order: Vec<usize> = Vec::with_capacity(n);
new_order.extend(&with_missing);
new_order.extend(¬_valid);
new_order.extend(&txid_only);
new_order.extend(&with_proof);
new_order.extend(&sorted_pending);
// Move the transactions into the new order (every index is in exactly
// one of the five lists; anything left over keeps its relative order
// at the end, as before).
let mut old: Vec<Option<BeefTx>> = std::mem::take(&mut self.txs)
.into_iter()
.map(Some)
.collect();
self.txs = new_order.iter().filter_map(|&i| old[i].take()).collect();
self.txs.extend(old.into_iter().flatten());
self.needs_sort = false;
self.rebuild_index();
result
}
/// Parses a BEEF from binary data.
///
/// No count is bounded beyond what the bytes hold. The whole BEEF is
/// held in memory: this is the reader for small bodies and for building.
/// A door that reads a stranger's BEEF reads it with
/// [`verify_stream`](super::beef_stream::verify_stream), one element at a
/// time.
///
/// Since 0.4.2 a byte after the frame is refused, as the streaming reader
/// refuses it: the error names its offset and `TrailingBytes`
/// (bsv-stack-lean NL-8 W3). [`from_reader`](Self::from_reader) reads a
/// BEEF out of a longer stream and leaves what follows to its caller.
pub fn from_binary(bin: &[u8]) -> Result<Self> {
let mut reader = Reader::new(bin);
let beef = Self::from_reader(&mut reader)?;
no_trailing_bytes(&reader)?;
Ok(beef)
}
/// Parses a BEEF from binary data, reserving room for at most
/// `limits.max_bumps` BUMPs and `limits.max_txs` transactions ahead of
/// reading them.
///
/// Deprecated in 0.4.0. Through 0.3 this refused a BEEF over a byte
/// length, a BUMP count or a transaction count; it refuses none of them
/// now and reads exactly what [`Beef::from_binary`] reads. A valid BEEF
/// is never refused for its size or its counts, and a count the bytes
/// cannot honor is refused where the bytes run out. The streaming reader
/// is [`verify_stream`](super::beef_stream::verify_stream).
#[deprecated(
since = "0.4.0",
note = "the limits no longer refuse anything; use `Beef::from_binary` for a small body \
and `beef_stream::verify_stream` for a stranger's"
)]
pub fn from_binary_with_limits(bin: &[u8], limits: &BeefLimits) -> Result<Self> {
let mut reader = Reader::new(bin);
let beef = Self::read(&mut reader, Some(limits))?;
no_trailing_bytes(&reader)?;
Ok(beef)
}
/// Parses a BEEF from a hex string.
pub fn from_hex(hex: &str) -> Result<Self> {
let bin = from_hex(hex)?;
Self::from_binary(&bin)
}
/// Parses a BEEF from a Reader.
pub fn from_reader(reader: &mut Reader) -> Result<Self> {
Self::read(reader, None)
}
/// The parse, with the memory hints when a caller gave them. A hint
/// reserves room, never more than the bytes left could fill (a BUMP is at
/// least 3 bytes, a transaction entry at least 10); it refuses nothing.
fn read(reader: &mut Reader, hints: Option<&BeefLimits>) -> Result<Self> {
let mut version = reader.read_u32_le()?;
let mut atomic_txid = None;
// Check for Atomic BEEF prefix
if version == ATOMIC_BEEF {
let txid_slice = reader.read_bytes(32)?;
let mut txid_bytes = txid_slice.to_vec();
txid_bytes.reverse();
atomic_txid = Some(to_hex(&txid_bytes));
version = reader.read_u32_le()?;
}
if version != BEEF_V1 && version != BEEF_V2 {
return Err(crate::Error::BeefError(format!(
"Invalid BEEF version: 0x{:08X}",
version
)));
}
let mut beef = Self::with_version(version);
beef.atomic_txid = atomic_txid;
// Read bumps
let bump_count = reader.read_var_int_num()?;
if let Some(hints) = hints {
beef.bumps.reserve(bounded_capacity(
bump_count.min(hints.max_bumps),
reader.remaining(),
3,
));
}
for _ in 0..bump_count {
let bump = MerklePath::from_reader(reader)?;
beef.bumps.push(bump);
}
// Read transactions
let tx_count = reader.read_var_int_num()?;
if let Some(hints) = hints {
beef.txs.reserve(bounded_capacity(
tx_count.min(hints.max_txs),
reader.remaining(),
10,
));
}
for _ in 0..tx_count {
let tx = BeefTx::from_reader(reader, version)?;
let txid = tx.txid();
beef.txs.push(tx);
let idx = beef.txs.len() - 1;
beef.txid_index.insert(txid, idx);
}
beef.needs_sort = true;
Ok(beef)
}
/// Serializes this BEEF to binary.
pub fn to_binary(&mut self) -> Vec<u8> {
if self.needs_sort {
self.sort_txs();
}
let mut writer = Writer::new();
self.to_writer(&mut writer);
writer.into_bytes()
}
/// Serializes this BEEF to a hex string.
pub fn to_hex(&mut self) -> String {
to_hex(&self.to_binary())
}
/// Writes this BEEF to a Writer.
pub fn to_writer(&self, writer: &mut Writer) {
writer.write_u32_le(self.version);
writer.write_var_int(self.bumps.len() as u64);
for bump in &self.bumps {
bump.to_writer(writer);
}
writer.write_var_int(self.txs.len() as u64);
for tx in &self.txs {
tx.to_writer(writer, self.version);
}
}
/// Serializes this BEEF as Atomic BEEF for a specific transaction.
pub fn to_binary_atomic(&mut self, txid: &str) -> Result<Vec<u8>> {
if self.needs_sort {
self.sort_txs();
}
if self.find_txid(txid).is_none() {
return Err(crate::Error::BeefError(format!(
"{} does not exist in this Beef",
txid
)));
}
let mut writer = Writer::new();
writer.write_u32_le(ATOMIC_BEEF);
// Write txid (reversed)
let txid_bytes = from_hex(txid)?;
let mut reversed = txid_bytes;
reversed.reverse();
writer.write_bytes(&reversed);
self.to_writer(&mut writer);
Ok(writer.into_bytes())
}
/// Returns true if this is an Atomic BEEF.
pub fn is_atomic(&self) -> bool {
self.atomic_txid.is_some()
}
/// Returns a shallow clone of this BEEF.
pub fn clone_shallow(&self) -> Self {
Self {
bumps: self.bumps.clone(),
txs: self.txs.clone(),
version: self.version,
atomic_txid: self.atomic_txid.clone(),
txid_index: self.txid_index.clone(),
needs_sort: self.needs_sort,
}
}
/// Returns a summary string of this BEEF.
pub fn to_log_string(&mut self) -> String {
let mut log = format!(
"BEEF with {} BUMPs and {} Transactions, isValid {}\n",
self.bumps.len(),
self.txs.len(),
self.is_valid(false)
);
for (i, bump) in self.bumps.iter().enumerate() {
log.push_str(&format!(" BUMP {}\n", i));
log.push_str(&format!(" block: {}\n", bump.block_height));
let txids: Vec<String> = bump.txids();
if !txids.is_empty() {
log.push_str(" txids: [\n");
for txid in txids {
log.push_str(&format!(" '{}'\n", txid));
}
log.push_str(" ]\n");
}
}
for (i, tx) in self.txs.iter().enumerate() {
log.push_str(&format!(" TX {}\n", i));
log.push_str(&format!(" txid: {}\n", tx.txid()));
if let Some(bump_idx) = tx.bump_index() {
log.push_str(&format!(" bumpIndex: {}\n", bump_idx));
}
if tx.is_txid_only() {
log.push_str(" txidOnly\n");
} else {
log.push_str(&format!(
" rawTx length={}\n",
tx.raw_tx().map(|r| r.len()).unwrap_or(0)
));
}
if !tx.input_txids.is_empty() {
log.push_str(" inputs: [\n");
for input_txid in &tx.input_txids {
log.push_str(&format!(" '{}'\n", input_txid));
}
log.push_str(" ]\n");
}
}
log
}
}
impl Default for Beef {
fn default() -> Self {
Self::new()
}
}
/// A byte after the frame's end: the streaming reader's refusal, in its words.
fn no_trailing_bytes(reader: &Reader) -> Result<()> {
if reader.remaining() == 0 {
return Ok(());
}
let refusal = Refusal {
offset: reader.position() as u64,
reason: Reason::TrailingBytes,
};
Err(crate::Error::BeefError(refusal.to_string()))
}
/// The txids a raw transaction's inputs spend (display hex), proven or not.
fn spent_txids(tx: &BeefTx) -> Vec<String> {
let parsed;
let t = match tx.tx() {
Some(t) => t,
None => match tx.raw_tx().map(Transaction::from_binary) {
Some(Ok(t)) => {
parsed = t;
&parsed
}
_ => return Vec::new(),
},
};
t.inputs
.iter()
.filter_map(|i| i.get_source_txid().ok())
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::transaction::MerklePathLeaf;
#[test]
fn test_new_beef() {
let beef = Beef::new();
assert_eq!(beef.version, BEEF_V2);
assert!(beef.bumps.is_empty());
assert!(beef.txs.is_empty());
}
#[test]
fn test_beef_v1_version() {
let beef = Beef::with_version(BEEF_V1);
assert_eq!(beef.version, BEEF_V1);
}
#[test]
fn test_merge_txid_only() {
let mut beef = Beef::new();
let txid = "a".repeat(64);
beef.merge_txid_only(txid.clone());
assert_eq!(beef.txs.len(), 1);
assert!(beef.txs[0].is_txid_only());
assert!(beef.find_txid(&txid).is_some());
}
#[test]
fn test_make_txid_only() {
let mut beef = Beef::new();
// Create a simple raw transaction (minimal valid tx)
// Version (4) + input count (1) + input (41) + output count (1) + output (9) + locktime (4)
let raw_tx = vec![
0x01, 0x00, 0x00, 0x00, // version
0x01, // input count
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // prev txid (32 bytes)
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, // vout
0x00, // script length
0xff, 0xff, 0xff, 0xff, // sequence
0x01, // output count
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // satoshis
0x00, // script length
0x00, 0x00, 0x00, 0x00, // locktime
];
let beef_tx = beef.merge_raw_tx(raw_tx, None);
let txid = beef_tx.txid();
// Verify it's not txid-only
assert!(!beef.txs[0].is_txid_only());
// Convert to txid-only
let result = beef.make_txid_only(&txid);
assert!(result.is_some());
assert!(beef.txs[0].is_txid_only());
// Verify the txid is still findable
assert!(beef.find_txid(&txid).is_some());
// Converting again should succeed (already txid-only)
let result2 = beef.make_txid_only(&txid);
assert!(result2.is_some());
// Non-existent txid should return None
let fake_txid = "b".repeat(64);
assert!(beef.make_txid_only(&fake_txid).is_none());
}
#[test]
fn test_merge_bump() {
let mut beef = Beef::new();
let bump = MerklePath::from_coinbase_txid(&"a".repeat(64), 100);
let idx = beef.merge_bump(bump);
assert_eq!(idx, 0);
assert_eq!(beef.bumps.len(), 1);
}
#[test]
fn test_is_valid_empty() {
let mut beef = Beef::new();
// Empty BEEF should be valid
assert!(beef.is_valid(false));
}
#[test]
fn test_default() {
let beef = Beef::default();
assert_eq!(beef.version, BEEF_V2);
}
#[test]
fn test_trim_known_proven_removes_deep_ancestors() {
// Build a BEEF with chain: TX_A (proven) <- TX_B (unproven) <- TX_C (unproven, tip)
// Then prove TX_B. After trim, TX_A should be removed since TX_B is now self-sufficient.
let mut beef = Beef::new();
// TX_A: a "coinbase-like" tx (no real inputs for our purposes)
let tx_a_raw = vec![
0x01, 0x00, 0x00, 0x00, // version
0x01, // input count
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, // prev txid (all zeros = coinbase)
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff,
0x00, // script length
0xff, 0xff, 0xff, 0xff, // sequence
0x01, // output count
0xe8, 0x03, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // 1000 satoshis
0x00, // script length
0x00, 0x00, 0x00, 0x00, // locktime
];
let tx_a_id = {
let btx = beef.merge_raw_tx(tx_a_raw.clone(), None);
btx.txid()
};
// Give TX_A a proof (BUMP)
let bump_a = MerklePath::from_coinbase_txid(&tx_a_id, 100);
let bump_idx_a = beef.merge_bump(bump_a);
beef.find_txid_mut(&tx_a_id)
.unwrap()
.set_bump_index(Some(bump_idx_a));
// TX_B: spends TX_A (input references tx_a_id)
let tx_a_id_bytes = from_hex(&tx_a_id).unwrap();
let mut tx_b_raw = vec![0x01, 0x00, 0x00, 0x00, 0x01]; // version + 1 input
// prev txid (reversed tx_a_id)
let mut prev_txid = tx_a_id_bytes.clone();
prev_txid.reverse();
tx_b_raw.extend_from_slice(&prev_txid);
tx_b_raw.extend_from_slice(&[0x00, 0x00, 0x00, 0x00]); // vout
tx_b_raw.push(0x00); // script length
tx_b_raw.extend_from_slice(&[0xff, 0xff, 0xff, 0xff]); // sequence
tx_b_raw.push(0x01); // output count
tx_b_raw.extend_from_slice(&[0xd0, 0x07, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00]); // 2000 sats
tx_b_raw.push(0x00); // script length
tx_b_raw.extend_from_slice(&[0x00, 0x00, 0x00, 0x00]); // locktime
let tx_b_id = {
let btx = beef.merge_raw_tx(tx_b_raw, None);
btx.txid()
};
// TX_C: spends TX_B (tip, unproven)
let tx_b_id_bytes = from_hex(&tx_b_id).unwrap();
let mut tx_c_raw = vec![0x01, 0x00, 0x00, 0x00, 0x01];
let mut prev_txid_b = tx_b_id_bytes.clone();
prev_txid_b.reverse();
tx_c_raw.extend_from_slice(&prev_txid_b);
tx_c_raw.extend_from_slice(&[0x00, 0x00, 0x00, 0x00]);
tx_c_raw.push(0x00);
tx_c_raw.extend_from_slice(&[0xff, 0xff, 0xff, 0xff]);
tx_c_raw.push(0x01);
tx_c_raw.extend_from_slice(&[0xb8, 0x0b, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00]);
tx_c_raw.push(0x00);
tx_c_raw.extend_from_slice(&[0x00, 0x00, 0x00, 0x00]);
let _tx_c_id = {
let btx = beef.merge_raw_tx(tx_c_raw, None);
btx.txid()
};
// Before trim: 3 txs (A proven, B unproven, C unproven)
assert_eq!(beef.txs.len(), 3);
// Now "prove" TX_B
let bump_b = MerklePath::from_coinbase_txid(&tx_b_id, 101);
let bump_idx_b = beef.merge_bump(bump_b);
beef.find_txid_mut(&tx_b_id)
.unwrap()
.set_bump_index(Some(bump_idx_b));
// Trim: TX_A should be removed (only ancestor of now-proven TX_B)
beef.trim_known_proven();
assert_eq!(beef.txs.len(), 2); // TX_B and TX_C remain
assert!(beef.find_txid(&tx_b_id).is_some()); // TX_B kept (proven, needed by TX_C)
assert!(beef.find_txid(&_tx_c_id).is_some()); // TX_C kept (tip)
assert!(beef.find_txid(&tx_a_id).is_none()); // TX_A removed (unnecessary)
// BUMP for TX_A's block should be removed, BUMP for TX_B's block kept
assert_eq!(beef.bumps.len(), 1);
assert_eq!(beef.bumps[0].block_height, 101);
}
#[test]
fn test_beef_v1_binary_roundtrip_preserves_bytes() {
// Simple P2PKH transaction
let tx_hex = "0100000001c997a5e56e104102fa209c6a852dd90660a20b2d9c352423edce25857fcd3704000000004847304402204e45e16932b8af514961a1d3a1a25fdf3f4f7732e9d624c6c61548ab5fb8cd410220181522ec8eca07de4860a4acdd12909d831cc56cbbac4622082221a8768d1d0901ffffffff0200ca9a3b00000000434104ae1a62fe09c5f51b13905f07f06b99a2f7159b2225f374cd378d71302fa28414e7aab37397f554a7df5f142c21c1b7303b8a0626f1baded5c72a704f7e6cd84cac00286bee0000000043410411db93e1dcdb8a016b49840f8c53bc1eb68a382e97b1482ecad7b148a6909a5cb2e0eaddfb84ccf9744464f82e160bfa9b8b64f9d4c03f999b8643f656b412a3ac00000000";
let tx = Transaction::from_hex(tx_hex).unwrap();
let tx_bytes = tx.to_binary();
// Build BEEF V1 manually
let mut writer = Writer::new();
writer.write_u32_le(BEEF_V1);
writer.write_var_int(0); // 0 bumps
writer.write_var_int(1); // 1 tx
writer.write_bytes(&tx_bytes); // raw tx
writer.write_u8(0); // no bump
let original = writer.into_bytes();
// Round-trip
let mut beef = Beef::from_binary(&original).unwrap();
let reserialized = beef.to_binary();
assert_eq!(
original, reserialized,
"BEEF V1 round-trip must preserve exact bytes"
);
}
#[test]
fn test_beef_v2_binary_roundtrip_preserves_bytes() {
// Simple P2PKH transaction
let tx_hex = "0100000001c997a5e56e104102fa209c6a852dd90660a20b2d9c352423edce25857fcd3704000000004847304402204e45e16932b8af514961a1d3a1a25fdf3f4f7732e9d624c6c61548ab5fb8cd410220181522ec8eca07de4860a4acdd12909d831cc56cbbac4622082221a8768d1d0901ffffffff0200ca9a3b00000000434104ae1a62fe09c5f51b13905f07f06b99a2f7159b2225f374cd378d71302fa28414e7aab37397f554a7df5f142c21c1b7303b8a0626f1baded5c72a704f7e6cd84cac00286bee0000000043410411db93e1dcdb8a016b49840f8c53bc1eb68a382e97b1482ecad7b148a6909a5cb2e0eaddfb84ccf9744464f82e160bfa9b8b64f9d4c03f999b8643f656b412a3ac00000000";
let tx = Transaction::from_hex(tx_hex).unwrap();
let tx_bytes = tx.to_binary();
// Build BEEF V2 manually
let mut writer = Writer::new();
writer.write_u32_le(BEEF_V2);
writer.write_var_int(0); // 0 bumps
writer.write_var_int(1); // 1 tx
writer.write_u8(0); // RawTx format
writer.write_bytes(&tx_bytes);
let original = writer.into_bytes();
let mut beef = Beef::from_binary(&original).unwrap();
let reserialized = beef.to_binary();
assert_eq!(
original, reserialized,
"BEEF V2 round-trip must preserve exact bytes"
);
}
/// Helper: builds a raw transaction that spends a given previous txid at vout 0.
/// If `prev_txid` is None, creates a coinbase-like tx (all-zero prev hash).
/// `satoshis` controls the output value.
/// `extra_script_bytes` can be provided to inflate the locking script.
fn make_raw_tx(
prev_txid: Option<&str>,
satoshis: u64,
extra_script_bytes: Option<&[u8]>,
) -> Vec<u8> {
let mut raw = vec![0x01, 0x00, 0x00, 0x00]; // version
raw.push(0x01); // 1 input
// prev txid (reversed for wire format) or all zeros
match prev_txid {
Some(txid_hex) => {
let mut txid_bytes = from_hex(txid_hex).unwrap();
txid_bytes.reverse();
raw.extend_from_slice(&txid_bytes);
}
None => {
raw.extend_from_slice(&[0u8; 32]);
}
}
raw.extend_from_slice(&[0x00, 0x00, 0x00, 0x00]); // vout=0
raw.push(0x00); // empty unlocking script
raw.extend_from_slice(&[0xff, 0xff, 0xff, 0xff]); // sequence
raw.push(0x01); // 1 output
raw.extend_from_slice(&satoshis.to_le_bytes()); // satoshis
// locking script
match extra_script_bytes {
Some(script) => {
// write script length as varint
let len = script.len() as u64;
if len < 0xFD {
raw.push(len as u8);
} else if len <= 0xFFFF {
raw.push(0xFD);
raw.extend_from_slice(&(len as u16).to_le_bytes());
} else {
raw.push(0xFE);
raw.extend_from_slice(&(len as u32).to_le_bytes());
}
raw.extend_from_slice(script);
}
None => {
raw.push(0x00); // empty script
}
}
raw.extend_from_slice(&[0x00, 0x00, 0x00, 0x00]); // locktime
raw
}
/// Helper: adds a raw tx to a beef and returns its txid.
fn add_raw_tx(beef: &mut Beef, raw: Vec<u8>, bump_index: Option<usize>) -> String {
beef.merge_raw_tx(raw, bump_index).txid()
}
/// Helper: adds a raw tx to a beef, creates a coinbase-style BUMP for it, and
/// sets the bump index. Returns the txid.
fn add_proven_tx(beef: &mut Beef, raw: Vec<u8>, block_height: u32) -> String {
let txid = add_raw_tx(beef, raw, None);
let bump = MerklePath::from_coinbase_txid(&txid, block_height);
let bi = beef.merge_bump(bump);
beef.find_txid_mut(&txid).unwrap().set_bump_index(Some(bi));
txid
}
// ── Test 1: merge_beef preserves raw tx bytes ────────────────────────
#[test]
fn test_merge_beef_preserves_raw_tx_bytes() {
// Create BEEF A with a large-script tx (simulating PushDrop-style data).
let mut beef_a = Beef::new();
let big_script: Vec<u8> = (0..512).map(|i| (i % 256) as u8).collect();
let raw_a = make_raw_tx(None, 5000, Some(&big_script));
let txid_a = add_proven_tx(&mut beef_a, raw_a.clone(), 100);
// Create BEEF B with a different tx.
let mut beef_b = Beef::new();
let raw_b = make_raw_tx(None, 3000, None);
let txid_b = add_proven_tx(&mut beef_b, raw_b.clone(), 101);
// Merge B into A.
beef_a.merge_beef(&beef_b);
// Serialize, parse back.
let bin = beef_a.to_binary();
let parsed = Beef::from_binary(&bin).unwrap();
// Verify raw bytes of both txs survived the round-trip.
let found_a = parsed.find_txid(&txid_a).unwrap();
assert_eq!(
found_a.raw_tx().unwrap(),
&raw_a,
"TX A raw bytes differ after merge round-trip"
);
let found_b = parsed.find_txid(&txid_b).unwrap();
assert_eq!(
found_b.raw_tx().unwrap(),
&raw_b,
"TX B raw bytes differ after merge round-trip"
);
}
// ── Test 2: trim with 5 txs, 2 deep ancestors removed ───────────────
#[test]
fn test_trim_known_proven_removes_deep_ancestors_5tx() {
// Chain: A0 (proven) <- A1 (unproven) <- B (unproven) <- C (unproven) <- D (tip, unproven)
// Then prove B. After trim, A0 and A1 (deep ancestors of proven B) should be removed.
// Remaining: B, C, D (3 txs).
let mut beef = Beef::new();
let raw_a0 = make_raw_tx(None, 10_000, None);
let txid_a0 = add_proven_tx(&mut beef, raw_a0, 100);
let raw_a1 = make_raw_tx(Some(&txid_a0), 9000, None);
let txid_a1 = add_raw_tx(&mut beef, raw_a1, None);
let raw_b = make_raw_tx(Some(&txid_a1), 8000, None);
let txid_b = add_raw_tx(&mut beef, raw_b, None);
let raw_c = make_raw_tx(Some(&txid_b), 7000, None);
let txid_c = add_raw_tx(&mut beef, raw_c, None);
let raw_d = make_raw_tx(Some(&txid_c), 6000, None);
let txid_d = add_raw_tx(&mut beef, raw_d, None);
assert_eq!(beef.txs.len(), 5);
// Now prove B.
let bump_b = MerklePath::from_coinbase_txid(&txid_b, 200);
let bi = beef.merge_bump(bump_b);
beef.find_txid_mut(&txid_b)
.unwrap()
.set_bump_index(Some(bi));
beef.trim_known_proven();
assert_eq!(beef.txs.len(), 3, "Should keep B, C, D only");
assert!(beef.find_txid(&txid_a0).is_none(), "A0 should be trimmed");
assert!(beef.find_txid(&txid_a1).is_none(), "A1 should be trimmed");
assert!(
beef.find_txid(&txid_b).is_some(),
"B should remain (proven)"
);
assert!(beef.find_txid(&txid_c).is_some(), "C should remain");
assert!(beef.find_txid(&txid_d).is_some(), "D should remain (tip)");
}
// ── Test 3: V1 <-> V2 round-trip preserving data ────────────────────
#[test]
fn test_beef_v1_v2_roundtrip() {
// Build a V2 BEEF with 2 txs.
let mut beef_v2 = Beef::with_version(BEEF_V2);
let raw_1 = make_raw_tx(None, 1000, None);
let txid_1 = add_proven_tx(&mut beef_v2, raw_1.clone(), 50);
let raw_2 = make_raw_tx(Some(&txid_1), 500, None);
let txid_2 = add_raw_tx(&mut beef_v2, raw_2.clone(), None);
// Serialize as V2, parse back.
let v2_bin = beef_v2.to_binary();
let mut parsed_v2 = Beef::from_binary(&v2_bin).unwrap();
assert_eq!(parsed_v2.version, BEEF_V2);
assert_eq!(parsed_v2.txs.len(), 2);
// Switch to V1, serialize, parse back.
parsed_v2.version = BEEF_V1;
let v1_bin = parsed_v2.to_binary();
let parsed_v1 = Beef::from_binary(&v1_bin).unwrap();
assert_eq!(parsed_v1.version, BEEF_V1);
assert_eq!(parsed_v1.txs.len(), 2);
// Verify both txids present and raw bytes preserved.
let found_1 = parsed_v1.find_txid(&txid_1).unwrap();
assert_eq!(found_1.raw_tx().unwrap(), &raw_1);
let found_2 = parsed_v1.find_txid(&txid_2).unwrap();
assert_eq!(found_2.raw_tx().unwrap(), &raw_2);
// Verify bump is preserved.
assert_eq!(parsed_v1.bumps.len(), 1);
assert!(parsed_v1.bumps[0].contains(&txid_1));
}
// ── Test 4: V1 serialization format (raw_tx BEFORE has_bump) ────────
#[test]
fn test_beef_v1_serialization_format() {
let mut beef = Beef::with_version(BEEF_V1);
let raw_tx = make_raw_tx(None, 2000, None);
let txid = add_proven_tx(&mut beef, raw_tx.clone(), 300);
let _ = txid; // used indirectly via the bump
let bin = beef.to_binary();
// V1 format:
// 4 bytes: version (0x0100BEEF LE -> 01 00 BE EF)
// varint: bump count
// bumps...
// varint: tx count
// For each tx:
// raw_tx bytes
// 1 byte: has_bump (0 or 1)
// [varint bump_index if has_bump == 1]
//
// Verify the version marker.
assert_eq!(&bin[0..4], &[0x01, 0x00, 0xBE, 0xEF]);
// After version + bumps + tx-count varint, we should find raw_tx bytes
// followed by has_bump=1 and bump_index=0.
// Find the raw_tx inside the serialized BEEF.
let tx_start = bin
.windows(raw_tx.len())
.position(|w| w == raw_tx.as_slice())
.expect("raw tx bytes not found in BEEF binary");
let after_tx = tx_start + raw_tx.len();
// has_bump byte should be 1 (proven).
assert_eq!(bin[after_tx], 0x01, "has_bump should be 1 for proven tx");
// bump index should be 0 (varint encoding of 0).
assert_eq!(bin[after_tx + 1], 0x00, "bump index should be 0");
}
// ── Test 5: Large OP_PUSHDATA2 script round-trip ────────────────────
#[test]
fn test_beef_large_pushdata_scripts() {
// Create a transaction with a locking script > 256 bytes (needs OP_PUSHDATA2).
let mut beef = Beef::new();
// 400-byte script filled with a recognizable pattern.
let script: Vec<u8> = (0..400).map(|i| ((i * 7 + 3) % 256) as u8).collect();
let raw_tx = make_raw_tx(None, 10_000, Some(&script));
let txid = add_raw_tx(&mut beef, raw_tx.clone(), None);
// Round-trip through serialization.
let bin = beef.to_binary();
let parsed = Beef::from_binary(&bin).unwrap();
let found = parsed.find_txid(&txid).unwrap();
let recovered_raw = found.raw_tx().unwrap();
assert_eq!(
recovered_raw, &raw_tx,
"raw tx with large script should survive round-trip"
);
// Verify the script bytes are embedded in the raw tx.
let script_pos = recovered_raw
.windows(script.len())
.position(|w| w == script.as_slice())
.expect("script bytes not found in recovered raw tx");
assert!(
script_pos > 0,
"script should be at a nonzero offset in the tx"
);
}
// ── Test 6: merge_beef remaps bump indices correctly ────────────────
#[test]
fn test_merge_beef_bump_indices_remapped() {
// BEEF A: tx_a proven at block 100 (bump index 0 in A).
let mut beef_a = Beef::new();
let raw_a = make_raw_tx(None, 1000, None);
let txid_a = add_proven_tx(&mut beef_a, raw_a, 100);
// BEEF B: tx_b proven at block 200 (bump index 0 in B — different from A).
let mut beef_b = Beef::new();
let raw_b = make_raw_tx(None, 2000, None);
let txid_b = add_proven_tx(&mut beef_b, raw_b, 200);
// Before merge, both have bump index 0 in their respective BEEFs.
assert_eq!(beef_a.find_txid(&txid_a).unwrap().bump_index(), Some(0));
assert_eq!(beef_b.find_txid(&txid_b).unwrap().bump_index(), Some(0));
// Merge B into A.
beef_a.merge_beef(&beef_b);
// After merge, A should have 2 bumps.
assert_eq!(beef_a.bumps.len(), 2);
// tx_a should still reference the bump at block 100.
let btx_a = beef_a.find_txid(&txid_a).unwrap();
let bump_a = btx_a.bump_index().unwrap();
assert_eq!(beef_a.bumps[bump_a].block_height, 100);
assert!(beef_a.bumps[bump_a].contains(&txid_a));
// tx_b should reference the bump at block 200 (remapped index).
let btx_b = beef_a.find_txid(&txid_b).unwrap();
let bump_b = btx_b.bump_index().unwrap();
assert_eq!(beef_a.bumps[bump_b].block_height, 200);
assert!(beef_a.bumps[bump_b].contains(&txid_b));
// The bump indices should be different.
assert_ne!(bump_a, bump_b, "Bump indices should differ after merge");
}
// ── Test 7: trim reduces size for ARC compatibility ─────────────────
#[test]
fn test_trim_reduces_size_for_arc_compatibility() {
// Build a BEEF:
// A0 (proven, block 10) <- A1 (proven, block 11) <- B (unproven)
// <- C (unproven, tip)
// Also add an unrelated proven tx D at block 12.
// Total: 4 txs. After trim, A0 should be removed (deep ancestor of
// proven A1). Remaining: A1, B, C, D => but A1 is proven, B depends on
// A1 (unproven), C depends on B.
// Actually let's build a cleaner chain:
// A0 (proven) <- A1 (unproven) <- A2 (unproven) <- tip
// Then prove A1. After trim, A0 removed. Remaining: A1, A2, tip (3 txs).
let mut beef = Beef::new();
let raw_a0 = make_raw_tx(None, 50_000, None);
let txid_a0 = add_proven_tx(&mut beef, raw_a0, 10);
let raw_a1 = make_raw_tx(Some(&txid_a0), 40_000, None);
let txid_a1 = add_raw_tx(&mut beef, raw_a1, None);
let raw_a2 = make_raw_tx(Some(&txid_a1), 30_000, None);
let txid_a2 = add_raw_tx(&mut beef, raw_a2, None);
// Add two more unrelated proven txs to bulk up.
let raw_d = make_raw_tx(None, 20_000, None);
let txid_d = add_proven_tx(&mut beef, raw_d, 12);
let raw_e = make_raw_tx(None, 15_000, None);
let txid_e = add_proven_tx(&mut beef, raw_e, 13);
assert_eq!(beef.txs.len(), 5);
let size_before = beef.to_binary().len();
// Prove A1.
let bump_a1 = MerklePath::from_coinbase_txid(&txid_a1, 11);
let bi = beef.merge_bump(bump_a1);
beef.find_txid_mut(&txid_a1)
.unwrap()
.set_bump_index(Some(bi));
beef.trim_known_proven();
let size_after = beef.to_binary().len();
// A0 removed, bump for block 10 removed.
assert!(beef.find_txid(&txid_a0).is_none(), "A0 should be trimmed");
assert!(beef.find_txid(&txid_a1).is_some());
assert!(beef.find_txid(&txid_a2).is_some());
assert!(beef.find_txid(&txid_d).is_some());
assert!(beef.find_txid(&txid_e).is_some());
assert_eq!(beef.txs.len(), 4);
assert!(
size_after < size_before,
"Trimmed BEEF ({} bytes) should be smaller than original ({} bytes)",
size_after,
size_before
);
}
// ── BEEF-to-EF extraction tests ────────────────────────────────────
/// Helper: builds a raw transaction with 2 inputs spending two different
/// previous txids at vout 0. Both use empty unlocking scripts.
fn make_raw_tx_2_inputs(prev_txid_a: &str, prev_txid_b: &str, satoshis: u64) -> Vec<u8> {
let mut raw = vec![0x01, 0x00, 0x00, 0x00]; // version
raw.push(0x02); // 2 inputs
// Input 0: prev_txid_a
let mut txid_a = from_hex(prev_txid_a).unwrap();
txid_a.reverse();
raw.extend_from_slice(&txid_a);
raw.extend_from_slice(&[0x00, 0x00, 0x00, 0x00]); // vout=0
raw.push(0x00); // empty unlocking script
raw.extend_from_slice(&[0xff, 0xff, 0xff, 0xff]); // sequence
// Input 1: prev_txid_b
let mut txid_b = from_hex(prev_txid_b).unwrap();
txid_b.reverse();
raw.extend_from_slice(&txid_b);
raw.extend_from_slice(&[0x00, 0x00, 0x00, 0x00]); // vout=0
raw.push(0x00); // empty unlocking script
raw.extend_from_slice(&[0xff, 0xff, 0xff, 0xff]); // sequence
raw.push(0x01); // 1 output
raw.extend_from_slice(&satoshis.to_le_bytes());
raw.push(0x00); // empty locking script
raw.extend_from_slice(&[0x00, 0x00, 0x00, 0x00]); // locktime
raw
}
#[test]
fn test_beef_to_ef_basic() {
use crate::script::UnlockingScript;
// Create a BEEF with 1 proven parent + 1 new (unproven) tx
let mut beef = Beef::new();
// Parent tx: coinbase-like, output of 10000 sats
let parent_raw = make_raw_tx(None, 10_000, None);
let parent_txid = add_proven_tx(&mut beef, parent_raw.clone(), 100);
// New tx: spends parent's output
let new_raw = make_raw_tx(Some(&parent_txid), 9000, None);
let new_txid = add_raw_tx(&mut beef, new_raw.clone(), None);
// Parse the new tx from raw bytes
let mut new_tx = Transaction::from_binary(&new_raw).unwrap();
assert_eq!(new_tx.id(), new_txid);
// Parse the parent from raw bytes and attach as source_transaction
let parent_tx = Transaction::from_binary(&parent_raw).unwrap();
new_tx.inputs[0].source_transaction = Some(Box::new(parent_tx));
// Set an empty unlocking script (required by to_ef)
new_tx.inputs[0].unlocking_script = Some(UnlockingScript::new());
// Call to_ef()
let ef_bytes = new_tx.to_ef().unwrap();
// Verify EF bytes start with version (4 bytes) then EF marker
assert_eq!(
&ef_bytes[0..4],
&[0x01, 0x00, 0x00, 0x00],
"version should be 1"
);
assert_eq!(
&ef_bytes[4..10],
&[0x00, 0x00, 0x00, 0x00, 0x00, 0xEF],
"EF marker should follow version"
);
// Round-trip: parse with from_ef(), verify txid matches
let parsed = Transaction::from_ef(&ef_bytes).unwrap();
assert_eq!(parsed.id(), new_txid, "EF round-trip should preserve txid");
// Verify the source satoshis are embedded
let source_sats = parsed.inputs[0].source_satoshis().unwrap();
assert_eq!(
source_sats, 10_000,
"source satoshis should be from parent output"
);
}
#[test]
fn test_beef_to_ef_multiple_inputs() {
use crate::script::UnlockingScript;
// Create a BEEF with 2 proven parents + 1 new tx with 2 inputs
let mut beef = Beef::new();
let parent_a_raw = make_raw_tx(None, 5000, None);
let parent_a_txid = add_proven_tx(&mut beef, parent_a_raw.clone(), 100);
let parent_b_raw = make_raw_tx(None, 7000, None);
let parent_b_txid = add_proven_tx(&mut beef, parent_b_raw.clone(), 101);
// New tx spends both parents
let new_raw = make_raw_tx_2_inputs(&parent_a_txid, &parent_b_txid, 11_000);
let new_txid = add_raw_tx(&mut beef, new_raw.clone(), None);
// Parse and attach source_transactions
let mut new_tx = Transaction::from_binary(&new_raw).unwrap();
assert_eq!(new_tx.inputs.len(), 2);
let parent_a_tx = Transaction::from_binary(&parent_a_raw).unwrap();
let parent_b_tx = Transaction::from_binary(&parent_b_raw).unwrap();
new_tx.inputs[0].source_transaction = Some(Box::new(parent_a_tx));
new_tx.inputs[0].unlocking_script = Some(UnlockingScript::new());
new_tx.inputs[1].source_transaction = Some(Box::new(parent_b_tx));
new_tx.inputs[1].unlocking_script = Some(UnlockingScript::new());
// Call to_ef() — should succeed with both inputs
let ef_bytes = new_tx.to_ef().unwrap();
// Verify EF marker
assert_eq!(&ef_bytes[4..10], &[0x00, 0x00, 0x00, 0x00, 0x00, 0xEF]);
// Round-trip through from_ef()
let parsed = Transaction::from_ef(&ef_bytes).unwrap();
assert_eq!(parsed.id(), new_txid, "EF round-trip txid mismatch");
assert_eq!(parsed.inputs.len(), 2, "should have 2 inputs");
// Verify both parent outputs are embedded
assert_eq!(
parsed.inputs[0].source_satoshis().unwrap(),
5000,
"input 0 should embed parent A's 5000 sats"
);
assert_eq!(
parsed.inputs[1].source_satoshis().unwrap(),
7000,
"input 1 should embed parent B's 7000 sats"
);
}
#[test]
fn test_beef_to_ef_large_pushdata_script() {
use crate::script::UnlockingScript;
// Parent has a PushDrop-style locking script > 256 bytes
let mut beef = Beef::new();
let big_script: Vec<u8> = (0..400).map(|i| ((i * 13 + 7) % 256) as u8).collect();
let parent_raw = make_raw_tx(None, 20_000, Some(&big_script));
let parent_txid = add_proven_tx(&mut beef, parent_raw.clone(), 200);
// New tx spends the parent
let new_raw = make_raw_tx(Some(&parent_txid), 19_000, None);
let _new_txid = add_raw_tx(&mut beef, new_raw.clone(), None);
let mut new_tx = Transaction::from_binary(&new_raw).unwrap();
let parent_tx = Transaction::from_binary(&parent_raw).unwrap();
// Verify parent has the big script in its output
let parent_script_bytes = parent_tx.outputs[0].locking_script.to_binary();
assert_eq!(parent_script_bytes.len(), big_script.len());
new_tx.inputs[0].source_transaction = Some(Box::new(parent_tx));
new_tx.inputs[0].unlocking_script = Some(UnlockingScript::new());
let ef_bytes = new_tx.to_ef().unwrap();
// Round-trip and verify the full script is preserved
let parsed = Transaction::from_ef(&ef_bytes).unwrap();
let embedded_script = parsed.inputs[0]
.source_locking_script()
.unwrap()
.to_binary();
assert_eq!(
embedded_script, big_script,
"EF should preserve the full >256-byte locking script"
);
}
#[test]
fn test_beef_to_ef_missing_parent_fails() {
// Create a new tx that spends a parent, but DON'T attach source_transaction
let mut beef = Beef::new();
let parent_raw = make_raw_tx(None, 10_000, None);
let parent_txid = add_proven_tx(&mut beef, parent_raw.clone(), 100);
let new_raw = make_raw_tx(Some(&parent_txid), 9000, None);
let _new_txid = add_raw_tx(&mut beef, new_raw.clone(), None);
// Parse the new tx but do NOT attach source_transaction
let mut new_tx = Transaction::from_binary(&new_raw).unwrap();
// Set unlocking script so we get past that check
new_tx.inputs[0].unlocking_script = Some(crate::script::UnlockingScript::new());
// to_ef() should fail because source_transaction is missing
let result = new_tx.to_ef();
assert!(
result.is_err(),
"to_ef() should fail without source_transaction"
);
let err_msg = result.unwrap_err().to_string();
assert!(
err_msg.contains("source transactions"),
"Error should mention source transactions, got: {}",
err_msg
);
}
#[test]
fn test_trim_known_proven_noop_when_nothing_to_trim() {
let mut beef = Beef::new();
// Single proven tx — nothing to trim
let raw = vec![
0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0x00,
0xff, 0xff, 0xff, 0xff, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00,
];
let txid = beef.merge_raw_tx(raw, None).txid();
let bump = MerklePath::from_coinbase_txid(&txid, 100);
let bi = beef.merge_bump(bump);
beef.find_txid_mut(&txid).unwrap().set_bump_index(Some(bi));
beef.trim_known_proven();
assert_eq!(beef.txs.len(), 1); // Still there
}
#[test]
fn test_merge_beef_bump_index_not_assigned_from_sibling() {
// Reproduces the production bug where tx[1] gets assigned bump[0]
// because tx[1]'s txid appears as a SIBLING hash in bump[0]'s path.
//
// Setup: Two independent proven txs (TX_A and TX_B) in separate BEEFs.
// TX_B's txid appears as a sibling in TX_A's merkle path.
// After merge_beef, TX_B must reference its OWN bump, not TX_A's.
let tx_a_raw = make_raw_tx(None, 1000, None);
let tx_b_raw = make_raw_tx(None, 2000, Some(&[0x01])); // different script → different txid
let tx_a_id = BeefTx::from_raw_tx(tx_a_raw.clone(), None).txid();
let tx_b_id = BeefTx::from_raw_tx(tx_b_raw.clone(), None).txid();
// Build BEEF 1 with TX_A proven. Its merkle path has TX_B's txid as a sibling.
let mut beef1 = Beef::new();
add_raw_tx(&mut beef1, tx_a_raw, None);
let bump_a = MerklePath {
block_height: 100,
path: vec![vec![
MerklePathLeaf {
offset: 0,
hash: Some(tx_a_id.clone()),
txid: true,
duplicate: false,
},
MerklePathLeaf {
offset: 1,
hash: Some(tx_b_id.clone()), // TX_B appears as sibling!
txid: false, // NOT a txid — just a sibling hash
duplicate: false,
},
]],
};
let bi_a = beef1.merge_bump(bump_a);
beef1
.find_txid_mut(&tx_a_id)
.unwrap()
.set_bump_index(Some(bi_a));
// Build BEEF 2 with TX_B proven in a different block.
let mut beef2 = Beef::new();
add_raw_tx(&mut beef2, tx_b_raw, None);
let bump_b = MerklePath::from_coinbase_txid(&tx_b_id, 200);
let bi_b = beef2.merge_bump(bump_b);
beef2
.find_txid_mut(&tx_b_id)
.unwrap()
.set_bump_index(Some(bi_b));
// Merge BEEF 2 into BEEF 1.
beef1.merge_beef(&beef2);
// TX_A should still point to bump[0] (height=100)
let tx_a = beef1.find_txid(&tx_a_id).unwrap();
assert_eq!(tx_a.bump_index(), Some(0), "TX_A should keep bump[0]");
// TX_B must point to its OWN bump (height=200), NOT bump[0].
let tx_b = beef1.find_txid(&tx_b_id).unwrap();
let tx_b_bump_idx = tx_b.bump_index().expect("TX_B should have a bump index");
assert_eq!(
beef1.bumps[tx_b_bump_idx].block_height, 200,
"TX_B's bump must be at height 200 (its own proof), not height 100 (where it's a sibling)"
);
// The BEEF should be valid
assert!(beef1.is_valid(false), "Merged BEEF should be valid");
}
#[test]
fn test_try_to_validate_bump_index_strict_no_sibling_fallback() {
// When a tx's txid only appears as a SIBLING hash (txid=false) in an
// unrelated bump, `try_to_validate_bump_index` must leave the tx's
// bump_index as None — not fall back to the sibling match.
//
// Regression test for: consolidation failing with "BEEF structure is
// invalid" because a tx's bump_index was being set to a bump that
// contained its hash only as a sibling (used only for merkle
// computation of some OTHER tx's proof). Go SDK reference:
// `go-sdk/transaction/beef.go:tryToValidateBumpIndex` — strict only.
let mut beef = Beef::new();
// Build a bump that proves SOME OTHER tx (txid=true for it) and
// happens to include `tx_id` as a sibling hash (txid=false).
let tx_raw = make_raw_tx(None, 1234, None);
let tx_id = BeefTx::from_raw_tx(tx_raw.clone(), None).txid();
let other_txid = "d".repeat(64);
let bump = MerklePath {
block_height: 500,
path: vec![vec![
MerklePathLeaf {
offset: 0,
hash: Some(other_txid),
txid: true,
duplicate: false,
},
MerklePathLeaf {
offset: 1,
hash: Some(tx_id.clone()), // our tx appears here as SIBLING
txid: false,
duplicate: false,
},
]],
};
beef.merge_bump(bump);
// Now add our tx via merge_raw_tx (bump_index=None, forcing
// try_to_validate_bump_index to run). Before the fix this would
// fall back to the sibling match and set bump_index=Some(0).
beef.merge_raw_tx(tx_raw, None);
let tx = beef.find_txid(&tx_id).unwrap();
assert_eq!(
tx.bump_index(),
None,
"tx must not be assigned to a bump where it appears only as a sibling hash"
);
}
#[test]
fn test_update_bump_indices_ignores_siblings() {
// Verify that update_bump_indices (called by merge_bump) does not
// assign bump indices based on sibling hashes.
let mut beef = Beef::new();
let tx_raw = make_raw_tx(None, 1000, None);
let tx_id = add_raw_tx(&mut beef, tx_raw, None);
// Create a bump where tx_id is a SIBLING (txid=false), not a leaf
let other_txid = "c".repeat(64);
let bump = MerklePath {
block_height: 100,
path: vec![vec![
MerklePathLeaf {
offset: 0,
hash: Some(other_txid),
txid: true,
duplicate: false,
},
MerklePathLeaf {
offset: 1,
hash: Some(tx_id.clone()),
txid: false, // Our tx appears as sibling only
duplicate: false,
},
]],
};
beef.merge_bump(bump);
// The tx should NOT have been assigned this bump
let tx = beef.find_txid(&tx_id).unwrap();
assert_eq!(
tx.bump_index(),
None,
"Transaction must not be assigned a bump where it appears only as a sibling"
);
}
}
#[cfg(test)]
mod merkle_path_reattach_tests {
//! `from_beef` / `from_atomic_beef` must return a transaction that carries
//! its BUMP, matching the TypeScript `@bsv/sdk` reference
//! (`Beef.findAtomicTransaction` -> `addInputProof`, which sets
//! `current.merklePath = mp`).
//!
//! Before this fix both Rust entry points cloned the parsed transaction
//! and dropped the proof, because bumps live in `Beef::bumps` and are
//! referenced by `BeefTx::bump_index` rather than being stored inside the
//! transaction. Every caller asking "is this mined?" got "no" forever.
use crate::transaction::Transaction;
/// A BEEF carrying one proven transaction, produced by this crate's own
/// writer so the test cannot drift from the wire format.
fn proven_beef() -> (Vec<u8>, String) {
// A minimal mined transaction with a merkle path attached.
let raw = hex::decode(
"0100000001b7994a0db2f373a29227e1d90da883c6ce1cb0dd2d6812e4558041ebbbcfa54\
80000000000ffffffff0101000000000000001976a914000000000000000000000000000\
000000000000088ac00000000",
)
.unwrap_or_default();
let mut tx = Transaction::from_binary(&raw).expect("fixture tx must parse");
let txid = tx.id();
// Attach a real single-leaf merkle path for this txid.
let mp = crate::transaction::MerklePath {
block_height: 800_000,
path: vec![vec![crate::transaction::merkle_path::MerklePathLeaf {
offset: 0,
hash: Some(txid.clone()),
txid: true,
duplicate: false,
}]],
};
tx.merkle_path = Some(mp);
let beef = tx.to_beef(true).expect("fixture must serialize to BEEF");
assert!(!beef.is_empty(), "fixture BEEF must be non-empty");
(beef, txid)
}
#[test]
fn from_beef_reattaches_the_merkle_path() {
let (beef, txid) = proven_beef();
let parsed = match Transaction::from_beef(&beef, Some(&txid)) {
Ok(t) => t,
Err(e) => panic!("from_beef failed: {e}"),
};
assert!(
parsed.merkle_path.is_some(),
"from_beef must reattach the BUMP (ts-sdk addInputProof parity); \
without it every caller reads 'unmined' forever"
);
assert_eq!(parsed.id(), txid);
}
#[test]
fn from_beef_without_a_txid_also_reattaches() {
let (beef, txid) = proven_beef();
let parsed = match Transaction::from_beef(&beef, None) {
Ok(t) => t,
Err(e) => panic!("from_beef(None) failed: {e}"),
};
assert_eq!(parsed.id(), txid);
assert!(
parsed.merkle_path.is_some(),
"the last-transaction path must attach the BUMP too"
);
}
/// Two inputs of one spend sourcing the SAME unproven parent (a covenant
/// head output plus that transaction's own change): the walk must link
/// BOTH inputs fully, and `Transaction::verify` must then execute every
/// script instead of failing on a bare clone. Found live on zanaadu beta
/// (2026-09-08); the TS SDK never sees it because its inputs share one
/// object by reference.
#[tokio::test]
async fn two_inputs_from_one_unproven_parent_are_both_linked() {
use crate::primitives::PrivateKey;
use crate::script::template::SignOutputs;
use crate::script::templates::P2PKH;
use crate::script::ScriptTemplate;
use crate::transaction::{TransactionInput, TransactionOutput};
let key = PrivateKey::random();
let lock = P2PKH::new().lock(&key.public_key().hash160()).unwrap();
// F (proven) -> M (unproven, two outputs) -> R spending M:0 AND M:1.
let mut funding = Transaction::new();
funding.inputs.push(TransactionInput {
source_txid: Some("aa".repeat(32)),
source_output_index: 0,
unlocking_script: Some(crate::script::UnlockingScript::from_script(
crate::script::Script::new(),
)),
..Default::default()
});
funding
.outputs
.push(TransactionOutput::new(100_000, lock.clone()));
let funding_txid = funding.id();
funding.merkle_path = Some(crate::transaction::MerklePath {
block_height: 800_000,
path: vec![vec![crate::transaction::merkle_path::MerklePathLeaf {
offset: 0,
hash: Some(funding_txid.clone()),
txid: true,
duplicate: false,
}]],
});
let mut middle = Transaction::new();
middle
.add_input_from_tx(funding, 0, P2PKH::unlock(&key, SignOutputs::All, false))
.unwrap();
middle
.outputs
.push(TransactionOutput::new(40_000, lock.clone()));
middle
.outputs
.push(TransactionOutput::new(50_000, lock.clone()));
middle.sign().await.unwrap();
let mut subject = Transaction::new();
subject
.add_input_from_tx(
middle.clone(),
0,
P2PKH::unlock(&key, SignOutputs::All, false),
)
.unwrap();
subject
.add_input_from_tx(
middle.clone(),
1,
P2PKH::unlock(&key, SignOutputs::All, false),
)
.unwrap();
subject.outputs.push(TransactionOutput::new(80_000, lock));
subject.sign().await.unwrap();
let beef = subject.to_beef(false).unwrap();
let subject_txid = subject.id();
let parsed = Transaction::from_beef(&beef, Some(&subject_txid)).unwrap();
// Every input carries the parent it spends, so its output (satoshis and
// locking script) is right there...
for (vin, input) in parsed.inputs.iter().enumerate() {
let src = input
.source_transaction
.as_ref()
.unwrap_or_else(|| panic!("input {vin} must carry its source"));
assert_eq!(
src.id(),
middle.id(),
"input {vin} must carry the parent it names"
);
assert!(
src.outputs.len() > input.source_output_index as usize,
"input {vin}: the parent must carry the output being spent"
);
}
// ...but the ancestry BELOW that parent is linked exactly once: input 0
// gets the fully linked copy, input 1 a bare stub. Linking both in full
// is what made 0.3.21 exponential on a chain of such spends.
let first = parsed.inputs[0].source_transaction.as_ref().unwrap();
let grand = first.inputs[0]
.source_transaction
.as_ref()
.expect("input 0: the first copy of the unproven parent is linked in full");
assert!(
grand.merkle_path.is_some(),
"input 0: the proven grandparent must carry its merkle path"
);
let second = parsed.inputs[1].source_transaction.as_ref().unwrap();
assert!(
second.inputs[0].source_transaction.is_none(),
"input 1 must get a BARE STUB of the parent, not a second full copy"
);
// Neither `verify` nor anything else may care which copy it reaches.
assert!(
matches!(
parsed
.verify(
&crate::transaction::MockChainTracker::always_valid(800_010),
None
)
.await,
Ok(true)
),
"every input's script executes with its source found by txid"
);
}
/// A DIAMOND CHAIN: every level spends both outputs of the previous
/// unproven level, which is what an ordinary wallet change chain looks
/// like. 0.3.21 linked every input by cloning the memoized parent, so each
/// level carried two full copies of the level below it and 24 levels meant
/// 2^24 subtrees: `from_beef` died on memory before verification started
/// (found by the zanaadu overlay engine's regression suite, 2026-09-08).
/// The linking must be linear in the BEEF and `verify` must still pass.
///
/// The test itself builds the BEEF by hand and signs each level against a
/// SHALLOW copy of its parent, so the fixture stays linear too.
#[tokio::test]
async fn a_deep_diamond_chain_links_and_verifies_in_linear_time() {
const LEVELS: u32 = 24;
let (beef, subject_txid) = diamond_chain_beef(LEVELS, None).await;
let started = std::time::Instant::now();
let parsed = Transaction::from_beef(&beef, Some(&subject_txid))
.expect("a 24-deep diamond of unproven spends must parse and link");
let verified = parsed
.verify(
&crate::transaction::MockChainTracker::always_valid(800_010),
None,
)
.await;
let elapsed = started.elapsed();
assert!(
matches!(verified, Ok(true)),
"a 24-deep diamond of valid unproven spends verifies: {verified:?}"
);
assert!(
elapsed.as_secs() < 5,
"linking plus verification must be linear in the chain, took {elapsed:?}"
);
// The linked structure itself must stay small: one full link per
// distinct parent plus one bare stub per repeat input, so a couple of
// source objects per level, never 2^level.
let sources = count_linked_sources(&parsed);
assert!(
sources <= 4 * (LEVELS as usize + 1),
"the linked ancestry must be linear: {sources} source objects for {LEVELS} levels"
);
assert!(
sources >= LEVELS as usize,
"every level must still be reachable: {sources} source objects"
);
println!("24-deep diamond: {sources} source objects, linked+verified in {elapsed:?}");
}
/// The same chain with one byte of the signature flipped in a MIDDLE
/// level: the by-txid walk must still reach that level and refuse it. A
/// walk that stopped at the first bare stub, or that trusted a proof-less
/// copy it could not descend, would let this through.
#[tokio::test]
async fn a_corrupted_signature_in_the_middle_of_the_chain_is_refused() {
let (beef, subject_txid) = diamond_chain_beef(12, Some(6)).await;
let parsed = Transaction::from_beef(&beef, Some(&subject_txid))
.expect("the corrupted chain still parses and links");
match parsed
.verify(
&crate::transaction::MockChainTracker::always_valid(800_010),
None,
)
.await
{
Err(e) => assert!(
e.to_string()
.contains("Script validation failed for input "),
"the interpreter's own refusal must surface, got: {e}"
),
Ok(v) => {
panic!("a corrupted signature in the middle level must be refused, got Ok({v})")
}
}
}
/// The value rule the by-txid walk now carries: an unproven spend whose
/// outputs pay out more than its inputs bring in is refused, even though
/// every one of its scripts passes (TS `Transaction.verify`,
/// `outputTotal > inputTotal`). Nothing else in the SDK checked it.
#[tokio::test]
async fn an_unproven_spend_creating_satoshis_is_refused() {
use crate::primitives::PrivateKey;
use crate::script::template::SignOutputs;
use crate::script::templates::P2PKH;
use crate::script::{Script, ScriptTemplate, UnlockingScript};
use crate::transaction::{MerklePath, TransactionInput, TransactionOutput};
let key = PrivateKey::random();
let lock = P2PKH::new().lock(&key.public_key().hash160()).unwrap();
let mut funding = Transaction::new();
funding.inputs.push(TransactionInput {
source_txid: Some("aa".repeat(32)),
source_output_index: 0,
unlocking_script: Some(UnlockingScript::from_script(Script::new())),
..Default::default()
});
funding
.outputs
.push(TransactionOutput::new(10_000, lock.clone()));
let funding_txid = funding.id();
funding.merkle_path = Some(MerklePath::from_coinbase_txid(&funding_txid, 800_000));
let mut spend = Transaction::new();
spend
.add_input_from_tx(funding, 0, P2PKH::unlock(&key, SignOutputs::All, false))
.unwrap();
// 10,000 sats in, 11,000 out: the signature is valid over exactly this.
spend.outputs.push(TransactionOutput::new(11_000, lock));
spend.sign().await.unwrap();
let beef = spend.to_beef(false).unwrap();
let subject_txid = spend.id();
let parsed = Transaction::from_beef(&beef, Some(&subject_txid)).unwrap();
let verified = parsed
.verify(
&crate::transaction::MockChainTracker::always_valid(800_010),
None,
)
.await;
assert!(
matches!(verified, Ok(false)),
"a spend that creates satoshis must be refused, got {verified:?}"
);
}
/// Number of `source_transaction` objects reachable from `tx`.
fn count_linked_sources(tx: &Transaction) -> usize {
tx.inputs
.iter()
.filter_map(|input| input.source_transaction.as_deref())
.map(|src| 1 + count_linked_sources(src))
.sum()
}
/// A `levels`-deep chain of unproven spends over one proven funding
/// transaction, every level after the first spending BOTH outputs of the
/// level below it, returned as `(beef, subject_txid)`.
///
/// `corrupt_level`, when given, flips one byte inside the signature of
/// that level's first input after signing it; the levels above it are
/// then built over the corrupted transaction, so the chain stays
/// structurally sound and only that one script fails.
async fn diamond_chain_beef(levels: u32, corrupt_level: Option<u32>) -> (Vec<u8>, String) {
use crate::primitives::PrivateKey;
use crate::script::template::SignOutputs;
use crate::script::templates::P2PKH;
use crate::script::{Script, ScriptTemplate, UnlockingScript};
use crate::transaction::{Beef, MerklePath, TransactionInput, TransactionOutput};
/// A copy carrying no ancestry, so the fixture never materializes one.
fn shallow(tx: &Transaction) -> Transaction {
let mut copy = tx.clone();
for input in copy.inputs.iter_mut() {
input.source_transaction = None;
}
copy
}
let key = PrivateKey::random();
let lock = P2PKH::new().lock(&key.public_key().hash160()).unwrap();
let mut funding = Transaction::new();
funding.inputs.push(TransactionInput {
source_txid: Some("aa".repeat(32)),
source_output_index: 0,
unlocking_script: Some(UnlockingScript::from_script(Script::new())),
..Default::default()
});
let mut sats: u64 = 4_000_000;
funding
.outputs
.push(TransactionOutput::new(sats, lock.clone()));
let funding_txid = funding.id();
funding.merkle_path = Some(MerklePath::from_coinbase_txid(&funding_txid, 800_000));
let mut beef = Beef::new();
let bump_index = beef.merge_bump(funding.merkle_path.clone().unwrap());
beef.merge_raw_tx(funding.to_binary(), Some(bump_index));
let mut prev = shallow(&funding);
for level in 0..levels {
let mut tx = Transaction::new();
tx.add_input_from_tx(
prev.clone(),
0,
P2PKH::unlock(&key, SignOutputs::All, false),
)
.unwrap();
if level > 0 {
tx.add_input_from_tx(
prev.clone(),
1,
P2PKH::unlock(&key, SignOutputs::All, false),
)
.unwrap();
}
sats -= 1_000; // a little less out than in: the value rule
tx.outputs
.push(TransactionOutput::new(sats / 2, lock.clone()));
tx.outputs
.push(TransactionOutput::new(sats - sats / 2, lock.clone()));
tx.sign().await.unwrap();
if corrupt_level == Some(level) {
// [0x47/0x48 push][0x30 len][0x02 rlen][r...]: byte 10 is in r.
let mut raw = tx.inputs[0].unlocking_script.as_ref().unwrap().to_binary();
raw[10] ^= 0x01;
tx.inputs[0].unlocking_script = Some(UnlockingScript::from_script(
Script::from_binary(&raw).unwrap(),
));
}
beef.merge_raw_tx(tx.to_binary(), None);
prev = shallow(&tx);
}
let subject_txid = prev.id();
assert_eq!(
beef.txs.len(),
levels as usize + 1,
"the fixture BEEF holds the funding plus every level, each once"
);
(beef.to_binary(), subject_txid)
}
}
/// The walks made iterative in 0.3.35 (bsv-stack-lean #57) against their
/// 0.3.34 recursive and rescanning forms, kept here verbatim as the
/// reference, on seeded random BEEFs: a DAG of spends with proven roots,
/// inputs missing from the BEEF, txid-only entries, repeated entries and a
/// shuffled wire order. Same link shape, same sort, same bytes.
#[cfg(test)]
mod iterative_equivalence_tests {
use super::*;
use crate::script::{LockingScript, UnlockingScript};
use crate::transaction::{TransactionInput, TransactionOutput};
use rand::rngs::StdRng;
use rand::seq::SliceRandom;
use rand::{Rng, SeedableRng};
use std::collections::HashSet;
// ---- the 0.3.34 forms, verbatim but for being free functions ----
fn legacy_attach_proof_memoized(
beef: &Beef,
tx: &mut Transaction,
stubs: &mut HashMap<String, Transaction>,
) {
let txid = tx.id();
if tx.merkle_path.is_none() {
if let Some(mp) = beef.find_bump(&txid) {
tx.merkle_path = Some(mp.clone());
}
}
if tx.merkle_path.is_some() {
return; // proven: no ancestry needed
}
for input in tx.inputs.iter_mut() {
let Some(src_txid) = input.source_txid.clone() else {
continue;
};
if let Some(stub) = stubs.get(&src_txid) {
input.source_transaction = Some(Box::new(stub.clone()));
continue;
}
let mut src = match input.source_transaction.take() {
Some(own) => *own,
None => match beef.find_txid(&src_txid).and_then(|b| b.tx().cloned()) {
Some(found) => found,
None => continue,
},
};
let stub = Beef::bare_stub(&mut src, beef.find_bump(&src_txid));
stubs.insert(src_txid, stub);
legacy_attach_proof_memoized(beef, &mut src, stubs);
input.source_transaction = Some(Box::new(src));
}
}
fn legacy_find_atomic_transaction(beef: &Beef, txid: &str) -> Option<Transaction> {
let mut tx = beef.find_txid(txid)?.tx().cloned()?;
let mut stubs: HashMap<String, Transaction> = HashMap::new();
legacy_attach_proof_memoized(beef, &mut tx, &mut stubs);
Some(tx)
}
fn legacy_sort_txs(beef: &mut Beef) -> SortResult {
let mut result = SortResult::default();
let mut valid_txids: HashMap<String, bool> = HashMap::new();
let mut txid_to_idx: HashMap<String, usize> = HashMap::new();
for (i, tx) in beef.txs.iter().enumerate() {
txid_to_idx.insert(tx.txid(), i);
}
let mut with_proof: Vec<usize> = Vec::new();
let mut txid_only: Vec<usize> = Vec::new();
let mut queue: Vec<usize> = Vec::new();
for (i, tx) in beef.txs.iter_mut().enumerate() {
tx.is_valid = Some(tx.has_proof());
if tx.has_proof() {
valid_txids.insert(tx.txid(), true);
with_proof.push(i);
} else if tx.is_txid_only() && tx.input_txids.is_empty() {
valid_txids.insert(tx.txid(), true);
txid_only.push(i);
result.txid_only.push(tx.txid());
} else {
queue.push(i);
}
}
let mut with_missing: Vec<usize> = Vec::new();
let mut pending: Vec<usize> = Vec::new();
for &i in &queue {
let mut has_missing = false;
for input_txid in &beef.txs[i].input_txids {
if !txid_to_idx.contains_key(input_txid) {
result.missing_inputs.push(input_txid.clone());
has_missing = true;
}
}
if has_missing {
with_missing.push(i);
result.with_missing_inputs.push(beef.txs[i].txid());
} else {
pending.push(i);
}
}
let mut sorted_pending: Vec<usize> = Vec::new();
while !pending.is_empty() {
let old_len = pending.len();
pending.retain(|&i| {
let all_inputs_valid = beef.txs[i]
.input_txids
.iter()
.all(|txid| valid_txids.contains_key(txid));
if all_inputs_valid {
valid_txids.insert(beef.txs[i].txid(), true);
sorted_pending.push(i);
false
} else {
true
}
});
if pending.len() == old_len {
break;
}
}
for &i in &pending {
result.not_valid.push(beef.txs[i].txid());
}
result.valid = valid_txids.keys().cloned().collect();
let mut new_order: Vec<usize> = Vec::new();
new_order.extend(&with_missing);
new_order.extend(&pending);
new_order.extend(&txid_only);
new_order.extend(&with_proof);
new_order.extend(&sorted_pending);
let old_txs = std::mem::take(&mut beef.txs);
let old_len = old_txs.len();
let old_vec: Vec<BeefTx> = old_txs;
for &i in &new_order {
if i < old_len {
beef.txs.push(old_vec[i].clone());
}
}
if beef.txs.len() < old_len {
for (i, tx) in old_vec.into_iter().enumerate() {
if !new_order.contains(&i) {
beef.txs.push(tx);
}
}
}
beef.needs_sort = false;
beef.rebuild_index();
result
}
fn legacy_collect_ancestors(
tx: &Transaction,
allow_partial: bool,
seen_txids: &mut HashSet<String>,
ancestors: &mut Vec<Transaction>,
bumps: &mut Vec<MerklePath>,
bump_index_by_root: &mut HashMap<String, usize>,
) -> Result<()> {
let txid = tx.id();
if seen_txids.contains(&txid) {
return Ok(());
}
if let Some(ref merkle_path) = tx.merkle_path {
let root = merkle_path.compute_root(Some(&txid)).unwrap_or_default();
let key = format!("{}:{}", merkle_path.block_height, root);
if let Some(&existing_idx) = bump_index_by_root.get(&key) {
if bumps[existing_idx].combine(merkle_path).is_err() {
let new_idx = bumps.len();
bumps.push(merkle_path.clone());
bump_index_by_root.insert(key, new_idx);
}
} else {
let new_idx = bumps.len();
bumps.push(merkle_path.clone());
bump_index_by_root.insert(key, new_idx);
}
seen_txids.insert(txid);
ancestors.push(tx.clone());
return Ok(());
}
for i in (0..tx.inputs.len()).rev() {
let input = &tx.inputs[i];
if let Some(ref source_tx) = input.source_transaction {
legacy_collect_ancestors(
source_tx,
allow_partial,
seen_txids,
ancestors,
bumps,
bump_index_by_root,
)?;
} else if !allow_partial {
let source_txid = input.source_txid.as_deref().unwrap_or("unknown");
return Err(crate::Error::TransactionError(format!(
"Missing source transaction for input {} (txid: {}). \
Set allow_partial=true to skip missing source transactions.",
i, source_txid
)));
}
}
seen_txids.insert(txid);
ancestors.push(tx.clone());
Ok(())
}
/// 0.3.34's `to_beef` (V2) and `to_atomic_beef`, over the recursive walk.
fn legacy_to_beef(tx: &Transaction, allow_partial: bool, atomic: bool) -> Result<Vec<u8>> {
let mut beef = Beef::with_version(BEEF_V2);
let mut seen_txids: HashSet<String> = HashSet::new();
let mut ancestors: Vec<Transaction> = Vec::new();
let mut bumps: Vec<MerklePath> = Vec::new();
let mut bump_index_by_root: HashMap<String, usize> = HashMap::new();
legacy_collect_ancestors(
tx,
allow_partial,
&mut seen_txids,
&mut ancestors,
&mut bumps,
&mut bump_index_by_root,
)?;
for bump in bumps {
beef.merge_bump(bump);
}
for ancestor in ancestors {
beef.merge_transaction(ancestor);
}
if atomic {
beef.to_binary_atomic(&tx.id())
} else {
Ok(beef.to_binary())
}
}
// ---- the random BEEFs ----
fn random_txid(rng: &mut StdRng) -> String {
let bytes: [u8; 32] = rng.gen();
to_hex(&bytes)
}
/// A random BEEF of `n` transactions: each spends one to three outputs
/// of earlier ones (or, one time in ten, a txid not in the BEEF); one in
/// five is proven; one in twenty is a txid-only entry; then a few entries
/// are repeated and the wire order is shuffled.
fn random_beef(rng: &mut StdRng, n: usize) -> Beef {
let lock = LockingScript::from_binary(&[0x51]).unwrap();
let mut beef = Beef::new();
let mut made: Vec<(String, u32)> = Vec::new();
for _ in 0..n {
let mut tx = Transaction::new();
let inputs = rng.gen_range(1..=3);
for _ in 0..inputs {
let (txid, vout) = if made.is_empty() || rng.gen_bool(0.1) {
(random_txid(rng), 0)
} else {
let (txid, outputs) = &made[rng.gen_range(0..made.len())];
(txid.clone(), rng.gen_range(0..*outputs))
};
let mut input = TransactionInput::new(txid, vout);
input.unlocking_script = Some(UnlockingScript::new());
tx.inputs.push(input);
}
let outputs = rng.gen_range(1..=3);
for _ in 0..outputs {
tx.outputs.push(TransactionOutput::new(
rng.gen_range(1..10_000),
lock.clone(),
));
}
let txid = tx.id();
if rng.gen_bool(0.05) {
beef.merge_txid_only(txid.clone());
} else if rng.gen_bool(0.2) {
let height = rng.gen_range(800_000..800_003);
let bump = beef.merge_bump(MerklePath::from_coinbase_txid(&txid, height));
beef.merge_raw_tx(tx.to_binary(), Some(bump));
} else {
beef.merge_raw_tx(tx.to_binary(), None);
}
made.push((txid, outputs as u32));
}
for _ in 0..rng.gen_range(0..3) {
let repeat = beef.txs[rng.gen_range(0..beef.txs.len())].clone();
beef.txs.push(repeat);
}
beef.txs.shuffle(rng);
beef.rebuild_index();
beef
}
/// The linked shape, node by node in preorder: txid, proven or not, and
/// for each input whether it carries a source.
fn shape(tx: &Transaction) -> Vec<(String, bool, Vec<bool>)> {
let mut out = Vec::new();
let mut stack = vec![tx];
while let Some(t) = stack.pop() {
out.push((
t.id(),
t.merkle_path.is_some(),
t.inputs
.iter()
.map(|i| i.source_transaction.is_some())
.collect(),
));
for input in t.inputs.iter().rev() {
if let Some(src) = input.source_transaction.as_deref() {
stack.push(src);
}
}
}
out
}
fn txids(beef: &Beef) -> Vec<String> {
beef.txs.iter().map(|t| t.txid()).collect()
}
fn sorted(mut v: Vec<String>) -> Vec<String> {
v.sort();
v
}
/// Strips every `source_txid` that has a linked source: the shape
/// `add_input_from_tx` builds.
fn strip_source_txids(tx: &mut Transaction) {
tx.invalidate_caches();
for input in tx.inputs.iter_mut() {
if let Some(src) = input.source_transaction.as_deref_mut() {
strip_source_txids(src);
input.source_txid = None;
}
}
}
#[test]
fn the_iterative_sort_orders_exactly_as_the_rescan_did() {
let mut rng = StdRng::seed_from_u64(57);
for round in 0..300 {
let n = rng.gen_range(1..40);
let beef = random_beef(&mut rng, n);
let mut new = beef.clone();
let mut old = beef.clone();
let a = new.sort_txs();
let b = legacy_sort_txs(&mut old);
assert_eq!(txids(&new), txids(&old), "round {round}: the order");
assert_eq!(a.missing_inputs, b.missing_inputs, "round {round}");
assert_eq!(a.not_valid, b.not_valid, "round {round}");
assert_eq!(
a.with_missing_inputs, b.with_missing_inputs,
"round {round}"
);
assert_eq!(a.txid_only, b.txid_only, "round {round}");
assert_eq!(sorted(a.valid), sorted(b.valid), "round {round}");
assert_eq!(new.to_binary(), old.to_binary(), "round {round}: the bytes");
}
}
#[test]
fn the_iterative_link_has_exactly_the_recursive_shape() {
let mut rng = StdRng::seed_from_u64(35);
let mut linked = 0;
for round in 0..300 {
let n = rng.gen_range(1..40);
let mut beef = random_beef(&mut rng, n);
if rng.gen_bool(0.5) {
beef.sort_txs();
}
for txid in txids(&beef) {
let new = beef.find_atomic_transaction(&txid);
let old = legacy_find_atomic_transaction(&beef, &txid);
assert_eq!(
new.as_ref().map(shape),
old.as_ref().map(shape),
"round {round}, subject {txid}"
);
linked += usize::from(new.is_some());
}
}
assert!(linked > 1_000, "the rounds exercised {linked} subjects");
}
#[test]
fn the_iterative_serializers_write_exactly_the_recursive_bytes() {
let mut rng = StdRng::seed_from_u64(2026);
let mut compared = 0;
for round in 0..200 {
let n = rng.gen_range(1..30);
let beef = random_beef(&mut rng, n);
for txid in txids(&beef) {
let Some(mut tx) = beef.find_atomic_transaction(&txid) else {
continue;
};
if rng.gen_bool(0.3) {
strip_source_txids(&mut tx);
}
for allow_partial in [false, true] {
for atomic in [false, true] {
let new = if atomic {
tx.to_atomic_beef(allow_partial)
} else {
tx.to_beef(allow_partial)
};
let old = legacy_to_beef(&tx, allow_partial, atomic);
assert_eq!(
new.map_err(|e| e.to_string()),
old.map_err(|e| e.to_string()),
"round {round}, subject {txid}, partial {allow_partial}, atomic {atomic}"
);
compared += 1;
}
}
}
}
assert!(
compared > 1_000,
"the rounds compared {compared} serializations"
);
}
#[test]
fn the_iterative_clone_copies_exactly_what_the_derived_clone_did() {
let mut rng = StdRng::seed_from_u64(5);
for _ in 0..100 {
let n = rng.gen_range(1..30);
let beef = random_beef(&mut rng, n);
for txid in txids(&beef) {
let Some(tx) = beef.find_atomic_transaction(&txid) else {
continue;
};
let copy = tx.clone();
assert_eq!(shape(©), shape(&tx));
assert_eq!(copy.to_beef(true).ok(), tx.to_beef(true).ok());
}
}
}
}