Proof for a startAfter/startAt continuation on a [equality, timestamp] index in descending order is unverifiable — merged-query limit starves the anchor layer ("V1 proof is missing lower layer for non-empty tree at key 00")

[PastaPastaPasta]

Summary

On protocol v14 (v4.2.0-dev.5), a documents query that combines a cursor (startAfter or startAt), a range clause on the terminal index property, and descending order returns a proof the client cannot verify:

grovedb: invalid proof: V1 proof is missing lower layer for non-empty tree at key 00

The rejection is correct — the proof is genuinely incomplete. The prover proves the merged (anchor + main) path query with the merged root traversed descending, so the index branch is visited before the anchor branch and consumes the entire limit + 1 budget; the anchor document's [0x00] subtree layer is then skipped, and verify_start_at_document_in_proof cannot extract the anchor. 100% reproducible; not client-fixable (the anchor is cryptographically absent from the proof).

This is the standard shape of every "timeline" query (newest-first feed, page 2+), so any client paginating a [equality, $createdAt] index newest-first breaks on every continuation page. An aggravation: each failed verification also causes the SDK to ban the responding address, so a UI that retries quickly exhausts its address pool ("no available addresses to use").

Environment

• Platform v4.2.0-dev.5 (protocol v14, GROVE_V4), grovedb pinned rev 6c882c3ee7d2c331f1feda2eb4223add9a6f0e45
• Observed on a devnet; verifying client @dashevo/evo-sdk@4.2.0-dev.5 (wasm)
• Not reproducible on protocol ≤ v13 (see "Why this is new" below)

Reproduction

Any document type with a non-unique compound index [someProperty, $createdAt] and > limit documents under one someProperty value. Live example: doctype post, index languageTimeline: [language, $createdAt], ~450 documents with language == "en".

import { EvoSDK } from '@dashevo/evo-sdk';
// connect to a v14 network, run one proved warm-up query (e.g. epoch), then:

const base = {
  dataContractId: CONTRACT_ID,
  documentTypeName: 'post',
  where:   [['language', '==', 'en'], ['$createdAt', '>', 0]],
  orderBy: [['language', 'asc'], ['$createdAt', 'desc']],
  limit: 100,
};

const page1 = await sdk.documents.query(base);          // OK, verifies (100 docs)
const lastId = [...page1.keys()].pop();

await sdk.documents.query({ ...base, startAfter: lastId });
// -> grovedb: invalid proof: V1 proof is missing lower layer for non-empty tree at key 00

Discriminators (all probed live, each 100% deterministic):

shape	continuation page
equality + range, desc, startAfter	FAILS
equality + range, desc, startAt (inclusive)	FAILS
equality + range, asc, startAfter	verifies
equality only (no range clause), desc, startAfter	verifies
equality + range, desc, no cursor (any limit)	verifies
equality + range, desc, cursor replaced by ['$createdAt', '<', lastTs] value clause	verifies

Same failure on a second index of the same shape ([hashtag, $createdAt]), so it is shape-generic.

Root cause (traced on the pinned revs)

1. Drive merges the anchor fetch into the proof. DriveDocumentQuery::construct_path_query_operations (packages/rs-drive/src/query/mod.rs @ v4.2.0-dev.5, ~1771–1864) builds start_at_path_query = PathQuery::new_single_key([...doctype, [0]], anchor_id), merges it with the main index query via PathQuery::merge, and sets merged.query.limit = limit + 1 — one reserved result slot for the anchor document.

2. The merged root's traversal direction now follows the main query. Since fix(drive): skip the ranked offset by counting instead of walking #4382 (a5fe2ee096), the anchor query's root direction is aligned to the main query before merging (start_at_path_query.query.query.left_to_right = main_path_query.query.query.left_to_right). The main query's root is descending exactly when the terminal where clause is a range (get_non_primary_key_single_in_path_query_v0: a non-range last clause forces left_to_right = true) — which is why equality-only desc cursors still verify.

3. Descending traversal starves the anchor branch of the limit. In the merged query, the doctype level has two branches: [0x00] (primary-key tree, anchor) and the index property key (e.g. "language"). In grovedb prove_subqueries_v1 (grovedb/src/operations/proof/generate.rs, ~1780–2130 @ 6c882c3e), ops stream in the layer's traversal order and done_with_results |= overall_limit == Some(0) is checked per op. Descending, the index branch ("language" = 0x6c…) sorts before [0x00]; mid-timeline it always holds ≥ limit + 1 matching documents, so it consumes the whole budget. When the [0x00] op is reached, the subtree-descent guard (!done_with_results && …, ~2917–2950) fails and no lower layer is emitted for the anchor subtree.

4. The verifier necessarily rejects. Verification runs two subset queries against the one proof: verify_start_at_document_in_proof (extract the anchor), then the rebuilt main query. The anchor subset query finds a non-empty tree at key [0x00] with no lower layer → verify_layer_proof_v1 (grovedb/src/operations/proof/verify.rs, ~2244–2253) raises the error. Ascending, [0x00] is visited first, spends the reserved +1, and everything works — the limit + 1 trick silently depends on anchor-first traversal.

Why this is new at v14

Grovedb's direction-aware PathQuery::merge (grovedb#801, 61904123; enabled as path_query_methods.merge: 1 in GROVE_V4) started propagating input direction onto the merged root — previously the synthesized merged root was always ascending, which protected the anchor-first invariant. Platform #4382 then aligned the anchor query's direction so desc merges stop erroring, completing the chain. Protocol ≤ v13 runs GROVE_V3 merge semantics, so mainnet/testnet never see it — but every v14 client paginating a timeline will.

Suggested fix

In construct_path_query_operations, pin the merged root back to ascending (set both inputs' root left_to_right = true before PathQuery::merge, or overwrite it on the merged query). Branch-internal directions live inside the SubqueryBranches, so newest-first result ordering within the index branch is preserved; the anchor branch is simply traversed first again and consumes its reserved +1. The verifier never reconstructs the merged query (it only runs the two subset queries, which synthesize that level), so no client change is needed and proof bytes change only for the currently-unverifiable shape. A verify-side fix is not possible: the anchor document is genuinely absent from the proof.

Grovedb unit-test shape that reproduces it directly: merge a single-key PathQuery with a large range PathQuery, descending, limit < range-branch results; prove; verify_subset_query the single-key query → "missing lower layer" at the single key. Falsifiable prediction: the same desc+cursor query on the final partial page (fewer than limit remaining documents) verifies today, because the limit never exhausts before the anchor op.

Related but separate

While tracing this, we noticed the cursor lowering excludes the anchor's entire $createdAt key (RangeAfterTo(0..anchor_ts) desc / RangeAfter(anchor_ts..) asc), so documents tying the anchor's timestamp are silently skipped across page boundaries even when proofs verify. Pre-existing, independent of this regression — can file separately if useful.

Workaround for clients

Replace the cursor with a value clause on the range property (['$createdAt', '<', lastSeenTs], drop startAfter). No merge happens, proofs verify. (Same page-boundary tie caveat as above.)