Skip to content

Ungrouped range count/sum with proof over a never-written prefix fails verification instead of proving 0 #5272

Open

Description

@PastaPastaPasta

An ungrouped range count or sum with proof (prefix properties fixed with ==, a range on the last index property, no groupBy) fails proof verification when no document has ever been written under the == prefix value. The node generates a proof, but the client cannot verify it. It should prove 0. The grouped "carrier" form of the same query (in [value] plus groupBy) proves the empty result correctly.

We hit this building Dash Forge, a git forge that runs on Platform. A new repository has no check runs and no releases, so its counts hit this case on day one.

Expected Behavior

count and sum with proof over a prefix that holds no documents verify and return 0, as the carrier form and the point-lookup (== only) forms already do.

Current Behavior

The prover returns proof bytes without error. Verification fails:

  • count: grovedb: invalid proof: non-leaf proof did not contain the expected key <prefix value>
  • sum: grovedb: invalid proof: aggregate-sum proof has 0 lower-layer entries at depth 5 (expected exactly one entry for path key <prefix value>)

The key in both messages is the serialized == value that has no subtree.

Where it comes from (our reading).

On a devnet. We run a read-only probe of 40 aggregate shapes against a repository, a target and an identity that have no documents. On a 5.0.0-beta.1 devnet, through the JS SDK's countWithProof / sumWithProof, 36 of 40 passed. Two of the four failures are this bug (the other two were our own shapes with no summable index):

FAIL check outcomes per head, ungrouped range outcome >= 0:
  grovedb: invalid proof: non-leaf proof did not contain the expected key 262d2cfd4b73c716f8c34f0177dbc93891debbd01355dfc415e11e1410a90cda
FAIL release count, ungrouped range repoId == tagName > "":
  grovedb: invalid proof: aggregate-sum proof has 0 lower-layer entries at depth 5 (expected exactly one entry for path key 262d2cfd4b73c716f8c34f0177dbc93891debbd01355dfc415e11e1410a90cda)
PASS check outcomes per head, range outcome >= 0 groupBy outcome
PASS release count, carrier repoId in [R] tagName > "" groupBy repoId

The key 262d2c… is the random repository id R the probe used. The queries were repoId == R AND headOid == H AND outcome >= 0 on a rangeCountable index [repoId, headOid, outcome], and repoId == R AND tagName > "" summing delta on a summable: "delta", rangeSummable: true index [repoId, tagName]. The same two shapes failed the same way on an earlier devnet running 4.2.0-beta.7.

Possible Solution

Two options:

  1. Let the leaf-chain walkers in GroveDB accept a verified absence proof for the next path key at a non-leaf layer, and return 0 with the root hash of the chain above it, as the carrier walkers do for absent outer keys. This looks like the same family as fix: answer a single-path axis read over an absent path with the empty result grovedb#965, which made a single-path axis read over an absent path prove an empty result (taken into Platform by fix(drive): bump grovedb so a ranking over an unwritten pinned prefix proves an empty page #4753 for Proved ranked read on a never-populated timeRange bucket fails proof generation instead of proving empty #4592).
  2. Failing that, have Drive refuse the shape with a clear error, or serve it through the carrier form internally, so clients don't receive a proof they can't verify.

Steps to Reproduce (for bugs)

This rs-drive integration test reproduces it at v5.0.0-beta.1 (we dropped it into packages/rs-drive/tests/ and ran cargo test -p drive --test empty_aggregate_probe):

  1. Register a contract with a document type crow with index [a, b] ("countable": "countable", "rangeCountable": true), and a type srow with index [a, b] ("summable": "amount", "rangeSummable": true). a, b, amount are integers.
  2. Insert three documents of each type, all with a = 1.
  3. Build a DriveDocumentCountQuery / DriveDocumentSumQuery on those indexes with a == X AND b > 0. Call execute_aggregate_count_with_proof / execute_aggregate_sum_with_proof, then verify_aggregate_count_proof / verify_aggregate_sum_proof.

Output:

PROBE count a == 1 AND b > 0: Ok(3)
PROBE sum(amount) a == 1 AND b > 0: Ok(30)
PROBE count a == 2 AND b > 0: Err("verify: grovedb: invalid proof: non-leaf proof did not contain the expected key 8000000000000002")
PROBE sum(amount) a == 2 AND b > 0: Err("verify: grovedb: invalid proof: aggregate-sum proof has 0 lower-layer entries at depth 5 (expected exactly one entry for path key 8000000000000002)")
Test source (empty_aggregate_probe.rs)
//! Ungrouped range count / sum whose `==` prefix value was never written.
//! Expected: a proof of 0.

#![cfg(all(feature = "server", feature = "verify"))]

use dpp::block::block_info::BlockInfo;
use dpp::data_contract::accessors::v0::DataContractV0Getters;
use dpp::data_contract::conversion::value::v0::DataContractValueConversionMethodsV0;
use dpp::data_contract::document_type::accessors::DocumentTypeV0Getters;
use dpp::data_contract::document_type::methods::DocumentTypeV0Methods;
use dpp::document::DocumentV0Setters;
use dpp::platform_value::{platform_value, Identifier, Value};
use dpp::prelude::DataContract;
use dpp::version::PlatformVersion;
use drive::query::drive_document_sum_query::DriveDocumentSumQuery;
use drive::query::{DriveDocumentCountQuery, WhereClause, WhereOperator};
use drive::util::object_size_info::{DocumentAndContractInfo, DocumentInfo, OwnedDocumentInfo};
use drive::util::test_helpers::setup::setup_drive_with_initial_state_structure;

fn setup() -> (drive::drive::Drive, DataContract) {
    let platform_version = PlatformVersion::latest();
    let drive = setup_drive_with_initial_state_structure(None);
    let contract = DataContract::from_value(
        platform_value!({
            "$formatVersion": "0",
            "id": "BZUodcFoFL6KvnonehrnMVggTvCe8W5MiRnZuqLb6M54",
            "version": 1,
            "ownerId": "GZVdTnLFAN2yE9rLeCHBDBCr7YQgmXJuoExkY347j7Z5",
            "documentSchemas": {
                "crow": {
                    "type": "object",
                    "indices": [
                        {"name": "byAB", "properties": [{"a": "asc"}, {"b": "asc"}],
                         "countable": "countable", "rangeCountable": true}
                    ],
                    "properties": {
                        "a": {"type": "integer", "position": 0},
                        "b": {"type": "integer", "position": 1},
                        "amount": {"type": "integer", "position": 2, "minimum": 0, "maximum": 1000}
                    },
                    "required": ["a", "b", "amount"],
                    "additionalProperties": false
                },
                "srow": {
                    "type": "object",
                    "indices": [
                        {"name": "sumAB", "properties": [{"a": "asc"}, {"b": "asc"}],
                         "summable": "amount", "rangeSummable": true}
                    ],
                    "properties": {
                        "a": {"type": "integer", "position": 0},
                        "b": {"type": "integer", "position": 1},
                        "amount": {"type": "integer", "position": 2, "minimum": 0, "maximum": 1000}
                    },
                    "required": ["a", "b", "amount"],
                    "additionalProperties": false
                }
            }
        }),
        false,
        platform_version,
    )
    .expect("contract");
    drive
        .apply_contract(
            &contract,
            BlockInfo::default(),
            true,
            None,
            None,
            platform_version,
        )
        .expect("apply contract");
    // Documents exist only under a = 1.
    for (type_index, type_name) in ["crow", "srow"].iter().enumerate() {
        let document_type = contract.document_type_for_name(type_name).expect("type");
        for (i, b) in [3i64, 5, 7].iter().enumerate() {
            let seed = (type_index * 10 + i) as u8 + 1;
            let mut document = document_type
                .create_document_from_data(
                    platform_value!({"a": 1i64, "b": *b, "amount": 10i64}),
                    Identifier::from([100; 32]),
                    1,
                    1,
                    [seed; 32],
                    platform_version,
                )
                .expect("doc");
            document.set_id(Identifier::from([seed; 32]));
            drive
                .add_document_for_contract(
                    DocumentAndContractInfo {
                        owned_document_info: OwnedDocumentInfo {
                            document_info: DocumentInfo::DocumentRefInfo((&document, None)),
                            owner_id: None,
                        },
                        contract: &contract,
                        document_type,
                    },
                    true,
                    BlockInfo::default(),
                    true,
                    None,
                    platform_version,
                    None,
                )
                .expect("insert");
        }
    }
    (drive, contract)
}

fn clauses(a: i64) -> Vec<WhereClause> {
    vec![
        WhereClause {
            field: "a".to_string(),
            operator: WhereOperator::Equal,
            value: Value::I64(a),
        },
        WhereClause {
            field: "b".to_string(),
            operator: WhereOperator::GreaterThan,
            value: Value::I64(0),
        },
    ]
}

#[test]
fn probe_empty_prefix_ungrouped_range_count_and_sum() {
    let platform_version = PlatformVersion::latest();
    let (drive, contract) = setup();
    let count_type = contract.document_type_for_name("crow").expect("crow");
    let sum_type = contract.document_type_for_name("srow").expect("srow");
    let count_index = count_type.indexes().get("byAB").expect("byAB");
    let sum_index = sum_type.indexes().get("sumAB").expect("sumAB");
    let mut failures = 0;
    for a in [1i64, 2] {
        let count_query = DriveDocumentCountQuery {
            document_type: count_type,
            contract_id: contract.id().to_buffer(),
            document_type_name: "crow".to_string(),
            index: count_index,
            where_clauses: clauses(a),
        };
        let proved = count_query
            .execute_aggregate_count_with_proof(&drive, None, platform_version)
            .map_err(|e| format!("prove: {e}"))
            .and_then(|proof| {
                count_query
                    .verify_aggregate_count_proof(&proof, platform_version)
                    .map_err(|e| format!("verify: {e}"))
            });
        eprintln!(
            "PROBE count a == {a} AND b > 0: {:?}",
            proved.as_ref().map(|r| r.1)
        );
        if proved.is_err() {
            failures += 1;
        }

        let sum_query = DriveDocumentSumQuery {
            document_type: sum_type,
            contract_id: contract.id().to_buffer(),
            document_type_name: "srow".to_string(),
            index: sum_index,
            where_clauses: clauses(a),
            sum_property: "amount".to_string(),
        };
        let proved = sum_query
            .execute_aggregate_sum_with_proof(&drive, None, platform_version)
            .map_err(|e| format!("prove: {e}"))
            .and_then(|proof| {
                sum_query
                    .verify_aggregate_sum_proof(&proof, platform_version)
                    .map_err(|e| format!("verify: {e}"))
            });
        eprintln!(
            "PROBE sum(amount) a == {a} AND b > 0: {:?}",
            proved.as_ref().map(|r| r.1)
        );
        if proved.is_err() {
            failures += 1;
        }
    }
    assert_eq!(failures, 0);
}

Context

  • Any app that shows a count or total over a range (items since a date, releases of a repository, check outcomes of a commit) gets a verification error instead of 0 for a new user, a new object, or a new network.
  • Our workaround: the web client refuses ungrouped range aggregates and rewrites them as the carrier form, the leading == as in [value] plus groupBy (query.ts L307-L321). That works, but every SDK user has to know to do it.

Your Environment

  • Version used: Platform 5.0.0-beta.1 (GroveDB dce8252f), on a devnet (sakura) and in a local rs-drive test at tag v5.0.0-beta.1.
  • Environment name and version: @dashevo/evo-sdk (JS SDK) in Node.js for the devnet probe; Rust 1.98.1 for the rs-drive test.
  • Operating System and version: macOS.
  • Link to your project: https://github.com/PastaPastaPasta/dash-forge

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions