Summary

CheckBlockSubtrees validates a block's subtrees in three phases:

1. Phase 1 — processTransactionsInLevels processes each batch of subtrees' transactions in dependency-level order, populating the UTXO store and validator cache.
2. Phase 2 — all subtrees are validated in parallel (CheckBlockSubtreesConcurrency). Failures are collected for phase 3.
3. Phase 3 — failed subtrees are re-validated sequentially.

Phase 2's parallelism is justified at scale (e.g. on dev-scale-1, ~600 subtrees × ~1M txs per block) because each subtree's validation is largely independent I/O + cache lookups. But concurrency races on cross-subtree parent dependencies: when subtree B spends an output created by a tx in subtree A and they run at the same time, B may observe the cache before A has populated it and fail with TX_MISSING_PARENT.

When this code path runs

This is the catch-up / sync path, not steady-state. A well-connected teranode processes each subtree via the subtree-notify flow and builds its local copy ahead of the block announcement; the missingSubtrees list at the top of CheckBlockSubtrees is empty and the function returns immediately. Only when a teranode falls behind (or missed a subtree notification) does it arrive here with subtrees that need to be fetched from a peer and validated — meaning this code primarily affects sync throughput, not block-time latency.

The bug

Phase 2 collected failures into a shared slice via a mutex-guarded append from inside the per-subtree goroutine:

revalidateSubtrees := make([]chainhash.Hash, 0, len(missingSubtrees))

for _, subtreeHash := range missingSubtrees {
    g.Go(func() error {
        ...
        if err != nil {
            revalidateSubtreesMutex.Lock()
            revalidateSubtrees = append(revalidateSubtrees, subtreeHash) // arrival order, not block order
            revalidateSubtreesMutex.Unlock()
            return nil
        }
        ...
    })
}

Goroutines run concurrently and append as they finish failing, so the order of revalidateSubtrees reflects goroutine-completion order, which is non-deterministic. Phase 3's for _, subtreeHash := range revalidateSubtrees does iterate sequentially, but it iterates the wrong list — a child subtree can sit ahead of its parent and fail re-validation for the same TX_MISSING_PARENT reason it failed in phase 2.

On top of that, phase 1 failed the whole block with a processing error as soon as any missing-parent tx appeared, so phase 3 often never ran at all.

Observed on teratestnet: block 15,631 (9,216 txs, 1,305 with cross-subtree parents) consistently failed and stalled sync at height 15,630.

Fix

Two small changes:

1. Phase 2 collects failures positionally (block order)

Instead of a mutex-guarded slice of failures in arrival order, phase 2 writes into a failedParallel []bool indexed by the subtree's position in missingSubtrees (the canonical block order).

2. Phase 3 becomes a single ordered pass

Iterate missingSubtrees and re-validate any entry where failedParallel[i] is set. Because block subtrees are in a dependency-respecting order and each earlier subtree is re-validated first, one pass suffices — no convergence loop, no retry limits, no error bookkeeping.

3. Phase 1 defers when all errors are missing-parent

processTransactionsInLevels still counts missing-parent errors separately. When every error is a missing-parent error, it returns nil instead of failing — letting later batches run and phase 3 resolve the dependencies. Non-recoverable errors (invalid txs, processing errors) still fail fatally.

Why this is simpler than a convergence loop

A convergence loop (retry until every subtree succeeds or no progress is made) also works, but its complexity exists only to compensate for unordered failure collection. Once phase 3 walks failures in block order, each subtree's predecessors have always been validated before it, so one pass is always sufficient. If a subtree fails in that pass, the failure is real — a retry wouldn't help, and surfacing it immediately is the correct behavior.

Net change: ~26 source lines added, half of which are explanatory comments.

Performance note: dense vs sparse dependency chains

Phase 2's parallelism value scales inversely with cross-subtree dependency density:

• Sparse-dep sync (mixed real-world traffic) — most subtrees are independent, parallel validation is a genuine win, phase 3 cleans up a small residual.
• Dense-dep sync (dev-scale-1 tx-blaster chains) — every subtree has many (1–10K) txs whose parent is in the previous subtree. Only subtree 0 succeeds in parallel; the other ~599 race on deps they can't satisfy, fail fast on cache misses, and phase 3 does essentially the entire block's work sequentially.

The fix is correct in both cases: phase 3's ordered single-pass converges in one sweep regardless of density, so worst-case wall time is bounded by the sequential cost of cross-subtree dep resolution (which is inescapable — chains this tight must serialize). The convergence loop was O(n) passes in the worst case; this is O(1).

Whether phase 2 is worth keeping for dense-chain sync is a separate perf question (a future tunable or density heuristic could skip it). For now it's cheap to leave in because failed attempts fail fast on cache misses, and removing it would regress sparse sync.

Test plan

• go test -tags testtxmetacache ./services/subtreevalidation/... — 281 / 281 pass
• go build ./... clean
• Integration verification: deploy to teratestnet and observe sync past 15,631
• Optional perf measurement on dev-scale-1 to confirm phase 2's overhead is negligible in the dense case

The change is additive on the happy path: blocks where every subtree succeeds in phase 2 skip phase 3 entirely, byte-for-byte identical to before.

Relationship to #715 / #646

This supersedes the earlier convergence-loop version of this PR (and the unrelated gate-logic work in #646, handled by #715).

🤖 Generated with Claude Code