V1 proofs under a per-instance cap emit subquery-bearing layers in full, so merged ordered-page proofs grow with the range

[QuantumExplorer]

Summary

Under a per-instance cap (Query::limit), the V1 prover emits a layer that has subquery branches in full, and only the descents below it stop once the instance budget is spent. For a merged proof whose limited branch is an ordered range over a secondary index, the proof therefore carries every key of the range at the index level, so its size grows with the size of the range rather than with the requested page.

This is the shape Platform's composite document queries produce for a feed page (dashpay/platform#4728, fixed on the Drive side by dashpay/platform#4729; the incorrect "prover/verifier mismatch" framing in #961 is closed). Correctness is not affected: prover and verifier agree, and the proof verifies. The cost is proof size and bandwidth.

Where the rule lives

• Merge lift: an input's global SizedQuery::limit becomes its branch root's per-instance cap, grovedb/src/query/merge/v1.rs#L102-L119.
• Prover per-layer budget: a pure terminal layer runs under min(global, instance), a layer with subquery branches under the global budget only, grovedb/src/operations/proof/generate.rs#L1947-L1963.
• Verifier mirror, grovedb/src/operations/proof/verify.rs#L1633-L1651.

The rationale in the comments is sound as far as it goes: the instance chain budgets descendant rows, not children, and an empty child consumes no budget, so a later populated child may still owe rows. Truncating the merk walk by child count would be wrong. But once the merged query has no global limit (the normal case after lifting), the layer's merk walk is proven with limit = None, i.e. unbounded.

Concrete shape and magnitude

Page: [documents, <contract>, 1, post, byLanguageCreated, "en", $createdAt] with RangeAfter(0), descending, SizedQuery.limit = 20, each $createdAt key holding a 0 subtree of document references. Merged with a disjoint count branch on another document type, the page's limit is lifted, the merged root has no global limit, and the $createdAt layer is proven with every key in range. Twenty descents follow, then descents stop.

Each emitted key costs roughly a KV node with an 8-byte key, the serialized tree element and a 32-byte hash, on the order of 70 to 100 bytes. A feed with 10,000 posts under one language prefix pays about 0.7 to 1 MB per 20-post page proof; the same page as a plain (non-merged) query proves in a few kilobytes because the global limit truncates that layer to 20 keys.

Why the plain query is smaller and the merged one is not

With a global limit the prover truncates the subquery-bearing layer to limit children and relies on the empty-layer charge (charge_empty_layer) to keep the global budget aligned with truncation. Instance caps have no such charge, so the only sound choice today is to emit the layer whole.

Possible directions

1. Descend first, then prove the layer. For a layer with subquery branches under an instance cap, execute the descents against the merk (they are needed anyway) until the budget is spent, note the last key that produced a row, and prove the layer as a range truncated at that key with a proven right/left bound. The verifier already tolerates a layer whose later children carry no lower-layer proof once the budget is exhausted; it would additionally need to accept an abridged tail after the exhaustion point, which it can decide because it knows the budget when it finishes the descents. That means restructuring the verifier so the layer's merk proof is executed with the post-descent knowledge, or executing it twice.
2. Charge empty children against the instance budget. Mirror the global limit's empty-layer charge for instance caps, so a layer with subquery branches can be truncated at instance children. This changes the meaning of an instance cap from "N rows" to "N rows or empty children", which is a semantic change callers (Drive's composite lookups over IN sets, where absent keys are common) would need to accept and re-validate against.
3. Emit a bound-only tail. Keep the full range at the layer but downgrade every key past the exhaustion point to hash-only nodes. The verifier needs no budget change since those nodes carry no value, and range completeness stays provable. This bounds the per-key cost (about 40 bytes) rather than the count, so it halves the problem instead of removing it.

Option 1 is the one that makes proof size proportional to the page. Whichever is chosen needs the same rule on both sides and a regression test that proves an ordered range page merged with a disjoint branch and asserts the proof size does not grow with the number of keys past the limit.

Regression test to add

• Insert N (say 200) keys under an index level, each with a populated child subtree.
• Build a PathQuery over the range with SizedQuery.limit = 5, merge it with a disjoint limit-free branch, prove, verify.
• Assert the proof verifies, returns exactly 5 rows, and its length is within a constant of the same proof over N = 10.