CommitmentTreeInsert under-costed in estimated-cost paths: keyless ops skipped, and average-case constants used as upper bounds

[QuantumExplorer]

Summary

CommitmentTreeInsert is under-costed in the estimated-cost paths, in two independent ways. Downstream this is an admission-control bypass: Dash Platform uses the estimated cost as the bound that decides whether a transaction is adequately funded, then re-meters with the real cost during execution. When actual exceeds estimated, the transaction is admitted and then fails mid-execution.

This caused two ~2-hour mainnet chain stalls on 2026-08-14/15 (Dash Platform evo1, heights 415652 and 415661). The platform-side handling of that failure is a separate bug being fixed in dashpay/platform, but the trigger originates here: an average-case estimator is being used as an upper bound.

Defect 1 — keyless ops are dropped before cost dispatch

grovedb/src/batch/batch_structure.rs:126-132:

// Keyless ops (append-only tree ops) are handled by preprocessing.
// In estimated-cost paths they have no cost model yet — skip.
let key = match op_key {
    Some(k) => k,
    None => continue,
};

CommitmentTreeInsert is constructed keyless (op_key: None — see batch/mod.rs:775, "None for append-only tree ops"). In the apply path, preprocess_commitment_tree_ops (batch/mod.rs:5424, :5821) rewrites it into a keyed ReplaceNonMerkTreeRoot, so it arrives with a key and is costed. That preprocessing takes tx and storage_batch and reads the existing frontier, so it cannot run when there is no real tree — i.e. in the estimated-cost path the op stays keyless and hits the continue.

The consequence is that the cost arms that do exist for this op are unreachable during estimation:

• grovedb/src/batch/estimated_costs/average_case_costs.rs:210
• grovedb/src/batch/estimated_costs/worst_case_costs.rs:195

So the note-commitment append contributes zero to the estimate. Measured downstream on Dash Platform (2-action shield, 494 pre-seeded notes): estimated 158,296,560 vs actual 177,215,760 — a shortfall of 18,919,200 credits, 10.7% of the fee, attributable to the skipped append (Sinsemilla + blake3 + note storage).

Worth noting the comment says these ops "have no cost model yet", which is now stale — models were added at the two sites above, but the continue above them means they never run.

Defect 2 — the model is average-case where an upper bound is required

Even once reachable, the constants at average_case_costs.rs:225-246 are averages, not bounds:

// Average frontier size with ~16 ommers:
// 1 (flag) + 8 (position) + 32 (leaf) + 1 (count) + 16*32 = 554
const AVG_FRONTIER_SIZE: u32 = 554;
// Average Sinsemilla hashes per append:
// 32 (root computation) + 1 (avg ommer updates) = 33
const AVG_SINSEMILLA_HASHES: u32 = 33;
// Average blake3 hashes: 1 for running buffer hash
const AVG_BLAKE3_HASHES: u32 = 1;

The real cost is position-dependent (grovedb-commitment-tree/src/commitment_frontier/mod.rs:59-66):

// Count Sinsemilla hashes: 32 levels for the leaf path + trailing_ones
// for ommer merges
let ommer_hashes = self
    .frontier
    .value()
    .map(|f| u64::from(f.position()).trailing_ones())
    .unwrap_or(0);
cost.sinsemilla_hash_calls += 32 + ommer_hashes;

With FRONTIER_DEPTH = NOTE_COMMITMENT_TREE_DEPTH (32), the bounds are:

quantity	real range	estimate	worst case
sinsemilla_hash_calls	32 ..= 64	33	64
ommer count in frontier	0 ..= 32	~16	32
frontier size (bytes)	42 ..= 1066	554	1066 (1 + 8 + 32 + 1 + 32*32)

trailing_ones(position) is maximal exactly at positions 2^k - 1, so the expensive appends are deterministic and cheaply reachable by an adversary choosing when to append — not a rare tail.

The existing tests already encode the position dependence (grovedb-commitment-tree/src/commitment_frontier/tests.rs:268-295): positions yielding 32, 32, 33, 32, 34 for the first five appends.

Proposed fix

1. Make keyless ops reachable in estimation. Either give batch_structure.rs a synthetic key for append-only ops so they flow to the existing cost arms, or dispatch their cost before the continue. Silently dropping an op from a cost model should not be possible — a continue that discards cost is indistinguishable from an op that is genuinely free.
2. Replace the averages with depth-bounded upper bounds in worst_case_costs.rs at minimum: MAX_SINSEMILLA_HASHES = 32 + FRONTIER_DEPTH (64), MAX_FRONTIER_SIZE = 1 + 8 + 32 + 1 + FRONTIER_DEPTH * 32 (1066). Derive them from FRONTIER_DEPTH rather than hardcoding, so a depth change cannot silently reintroduce the gap.
3. Add a property test asserting estimated >= actual for CommitmentTreeInsert across a range of tree positions, specifically covering 2^k - 1 positions. This is the invariant consumers rely on and it is currently unstated and unenforced.

Whether average_case_costs.rs should also become an upper bound is a judgement call for maintainers — if any consumer legitimately wants average-case numbers, the fix is for admission-control consumers to call the worst-case path instead. Either way the two should not be silently interchangeable, since the difference is a consensus fault for the caller.

Notes for whoever picks this up

• Dash Platform pins a2791bbdca756d6a6113024aec48f09f7a33faa9; all line numbers above are against that rev and reproduce on current master.
• This changes fee amounts for consumers, so the platform-side pin bump needs a protocol-version gate and a fee-table regeneration. Please land and merge here before the pin moves.
• A previous pin bump on the platform side was blocked for days by an orphaned rev, so merging to master first (rather than bumping to a branch commit) matters.

---

September 2026 audit addendum — C012

Audit group: C012. Classification: correctness. Provisional severity: low.

The audited snapshot passes keyless typed append operations to BatchStructure, where they are skipped before cost dispatch. Append-only batches can return successful zero estimates and mixed batches omit that work. This confirms #812 Defect 1 on the audited snapshot. The existing issue reports downstream incidents and #813 describes a fix, but this audit did not independently reproduce those incidents or verify current develop/deployment remediation.

Expected contract and correction: Use the existing #812/#813 tracking for complete typed-append estimate dispatch or explicit unsupported errors. Verify repeated appends do not collapse in the estimator and preserve the intended average/worst-case and historical-version contracts. This addendum does not add an independent finding for #812 Defect 2.

Validation to complete

• Exercise all public typed constructors through both estimate modes.
• Assert each repeated append contributes its modeled cost or produces an explicit unsupported error.
• Verify fix: CommitmentTreeInsert under-costed in estimated-cost paths (issue #812) #813 and any subsequent models against the intended deployment pin before interpreting this historical result as current.

Limits and existing work

• Downstream admission-control and incident claims belong to the existing issue and are not independently validated by this audit.

Related tracking: issue #812 (closed), PR #813 (merged), PR #826 (merged), PR #829 (merged).

Scope: saved GroveDB worktree with revision context 2fa0f133877420a0d9c91ba7bc51b1775ab8c783. This report does not establish that current develop or any deployed application is affected. Focused runtime validation remains outstanding.

Audit source and canonical finding identifiers

Source status: snapshot-backed (git_worktree); plain source locations are used because this is not a sealed commit-only scan.

Audited revision context: 2fa0f133877420a0d9c91ba7bc51b1775ab8c783.

The findings were manually reconciled from a preserved scan bundle. The native scan ended before final completion; these are provisional source-review findings, not a completed native scan certification.

Canonical finding ID: csf_68c96e9f714a1dd08c94e6dd

Primary fingerprint: codex-security/v1:sha256:a3064c7db6356e27d9a2bca699a58f08493ab6c8d49be694aa2f7fb1677207a2

Source locations:

• Location (entrypoint): grovedb/src/batch/mod.rs:6261-6310
• Location (root_control): grovedb/src/batch/batch_structure.rs:127-132
• Location (sink): grovedb/src/batch/mod.rs:3882-3898
• Location (entrypoint): grovedb/src/batch/mod.rs:1194-1256