Append-only tree family charges write churn as new storage: compaction blob, epoch≥2 buffer writes and frontier rewrites are all reported as added_bytes

[QuantumExplorer]

Summary

For CommitmentTree / BulkAppendTree (and by construction PrivateDocumentStore), every data-storage write is reported to the fee layer as added_bytes, and nothing is ever reported as replaced or removed. Three writes that are physically replacement churn are therefore billed as permanent new storage:

1. Epoch compaction writes the chunk blob (2048 × ~328 B at chunk_power 11) as ~630 KB of added_bytes — but the blob supersedes the dense-buffer entries it was built from. The buffer's 2-byte position keys are simply reused by the next epoch (DenseFixedSizedMerkleTree::reset() only zeroes count and the cache), so net growth at the boundary is the blob minus the buffer it replaces ≈ a few KB, not 630 KB.
2. Dense-buffer writes from epoch 2 onward overwrite last epoch's stale value at the same position key, yet are charged as new bytes every epoch. Each note's bytes are effectively charged twice over its life (buffer write + blob copy).
3. The frontier (__ct_data__) is one value rewritten in place on every append, sized ~42 + 32 × popcount(position) (74 B → 1,066 B); each rewrite is charged in full as added_bytes.

All three come from the same mechanism: the data puts are issued with cost_info: None — DenseFixedSizedMerkleTree::put_value (tree.rs), the MMR storage_adapter.rs:98 put that persists chunk blobs and MMR nodes, and commitment_tree/mod.rs:563 for the frontier — so the commit path, which has no previous-size information for them, charges key+value as added. The previous size is knowable at each site: the frontier and buffer writes are preceded by reads of the same key, and the blob's predecessor bytes are exactly the buffer being compacted.

Measured (Dash Platform, real applies, 1-action ShieldedTransfer, 216-byte note, from an empty pool)

write	charged bytes	physical reality
nullifier insert (Merk)	214 B	genuinely new (32 B key + node framing)
note append	429 → 745 B within an epoch (312 B entry + ~50 B put overhead + frontier rewrite)	entry new once; frontier is in-place replacement
compaction (append #2048)	630,166 B added, NoStorageRemoval	blob replaces the ~640 KB buffer it was built from
average per append incl. boundary	~1,200 B at a mature pool	~550 B actually persists (nullifier node + blob share + MMR crumbs)

So the metered storage per note is ~2.2× the bytes that persist, and the boundary transaction is billed ~17.3B credits (at 27,400 credits/B) for what is ~95% replacement.

Why it matters

• Downstream fees price storage by added_bytes at the permanent-storage rate; charging churn that way over-states shielded storage ~2× and concentrates a ~17B-credit spike on one arbitrary transaction per epoch.
• fix: CommitmentTreeInsert under-costed in estimated-cost paths (issue #812) #813's admission upper bound inherits the same accounting, so it is pessimistic twice: worst position and worst accounting. With corrected reporting the bound itself drops to something sane.
• It blocks honest flat pricing of shielded transitions in Dash Platform (the follow-up to CommitmentTreeInsert under-costed in estimated-cost paths: keyless ops skipped, and average-case constants used as upper bounds #812/fix: CommitmentTreeInsert under-costed in estimated-cost paths (issue #812) #813): the per-action storage constant can only be set to what actually persists once the metering says so.

Proposed accounting

Treat the dense buffer as a rolling, pre-paid area and charge each entry's permanent bytes once:

• Blob share as added_bytes, amortized per append: entry_size + CHUNK_ENTRY_OVERHEAD (and the MMR node bytes amortized) charged on every append. (The estimator for PrivateDocumentStoreInsert already models exactly this — amortized_compaction_bytes = entry_size.)
• Buffer writes: epoch 1 (fresh keys) as added; from epoch 2 on, report replaced_bytes = previous value size at that position key (the read that precedes the write, or the deterministic entry size, gives it).
• Frontier rewrite: replaced_bytes = previous serialized size (it was just read), added_bytes only for growth beyond the previous size (and negative growth simply not credited — no refund semantics for data storage).
• Compaction blob put: report as replacement of the buffer bytes it supersedes (replaced_bytes ≈ Σ buffer entry sizes, added_bytes ≈ blob − buffer when positive), not as ~630 KB new. MMR internal nodes as added (they are).
• Removal accounting stays NoStorageRemoval — "removed" would imply refunding someone for the buffer, which nobody should get; replacement is the honest category for churn.

This is fee-affecting and must be gated: the append-only family is GROVE_V4-only and V4 has not activated, so it can land under the existing V4 gate (or its own slot in V4, mirroring how #813 was gated), with V1..V3 untouched.

Test plan

• Property test: Σ added_bytes over a full epoch ≈ physical DB growth (blob + MMR nodes + epoch-1 buffer), for chunk_power 4 and the deployed 11; the boundary append's added_bytes ≈ (blob − buffer) + MMR nodes, not the whole blob.
• Frontier rewrite at positions with many ommers (2^k−1) reports replaced ≥ previous size and added only for growth.
• Epoch-2 buffer writes report replaced_bytes == entry_size, added_bytes = 0 for the entry.
• Estimator ≥ actual still holds on both V3 (unchanged) and V4 (new model) — the fix: CommitmentTreeInsert under-costed in estimated-cost paths (issue #812) #813 bound tests re-run green.
• Golden-byte: stored bytes, roots and proofs are byte-identical — this is cost reporting only.

Refs: #812, #813 (estimator), dashpay/platform#4382 (pin bump that surfaced it), the Dash Platform shielded fee follow-up.