java-topology/defects/zebra-0001/TICKET.md

zebra-0001: ZIP-317 block template has_direct_dependencies O(T×S) Vec scan

MOAD: MOAD-0001 (CWE-407) Severity: LOW-MEDIUM Speedup: ~500x at T=1000 (pathological chain dependency topology) Language: Rust File: zebra-rpc/src/methods/types/get_block_template/zip317.rs:228

Description

has_direct_dependencies() is called for each dependent transaction during block template construction (ZIP-317). It checks whether all of a candidate transaction's dependencies are already in selected_txs by iterating the entire Vec<SelectedMempoolTx> and counting how many entries appear in a HashSet<transaction::Hash>.

fn has_direct_dependencies(
    candidate_tx_deps: Option<&HashSet<transaction::Hash>>,
    selected_txs: &Vec<SelectedMempoolTx>,
) -> bool {
    // ...
    let mut num_available_deps = 0;
    for tx in selected_txs {           // O(S) per call
        if deps.contains(&tx.transaction.id.mined_id()) {  // O(1) HashSet lookup
            num_available_deps += 1;
        }
        if num_available_deps == deps.len() {
            return true;
        }
    }
    false
}

In checked_add_transaction_weighted_random, each time a transaction is selected and its dependents are evaluated, has_direct_dependencies iterates all S already-selected transactions. As S grows with each selected tx, the total work across a block template build is O(T×S_avg) = O(T²) for T transactions in a deep dependency chain.

A more efficient approach: maintain a HashSet<transaction::Hash> of selected tx IDs alongside the Vec. Then has_direct_dependencies reduces to O(D) per check (D = number of direct dependencies, typically 1-3), giving O(T×D) total.

Complexity

• Current: O(T²) worst case for T txs in chain dependency topology
• Fixed: O(T×D) where D = average direct dependency count (typically 1-3)
• Speedup: ~T/D ≈ 333x at T=1000, D=3

Context

Block template construction runs once per block (~75 seconds on Zcash mainnet). Zcash block size limits bound T to around 1000 transactions in practice. This is not a hot path, so impact is LOW in typical operation, but a miner constructing blocks from a deep-chained mempool would observe the worst case.

Fix

Pass a HashSet<transaction::Hash> of already-selected tx IDs alongside selected_txs, built incrementally as transactions are added. Replace the Vec scan in has_direct_dependencies with a single HashSet intersection check: all deps must be present in selected_tx_ids.