Change proof over a key-empty range is rejected with UnexpectedValue

[bernard-avalabs]

Affected area(s)

proofs

Describe the bug

Summary

db.change_proof(...) can produce a proof that its own verifier then rejects with ProofError(UnexpectedValue). This happens when the proven range [start_key, end_key] is empty in both the start and end tries and a key above end_key was changed. A proof that honestly attests "nothing changed in this range" must verify.

This is a completeness bug: a valid, honestly-generated proof is rejected. Reproduces in both merkledb and ethhash.

Reproduction

Save as firewood/tests/change_proof_empty_range.rs, run cargo test -p firewood --test change_proof_empty_range (with or without --features ethhash):

use firewood::api::{BatchOp, Db as _, Proposal as _};
use firewood::db::{Db, DbConfig};
use firewood::{NodeHashAlgorithm, verify_change_proof_root_hash, verify_change_proof_structure};

// start trie:  { 0x20: 0x01 }
// end trie:    { 0xe0: 0x01 }        (0x20 deleted; 0xe0 added)
// proof range: [0x60, 0xb0]          (0x20 < 0x60, 0xe0 > 0xb0: range holds no keys)
#[test]
fn change_proof_over_empty_range_verifies() {
    let dir = tempfile::tempdir().unwrap();
    let config = DbConfig::builder()
        .node_hash_algorithm(NodeHashAlgorithm::compile_option())
        .build();
    let db = Db::new(dir.path(), config).unwrap();

    db.propose(vec![BatchOp::Put { key: b"\x20".as_slice(), value: b"\x01".as_slice() }])
        .unwrap().commit().unwrap();
    let start_root = db.root_hash().unwrap();

    let end_batch: Vec<BatchOp<&[u8], &[u8]>> = vec![
        BatchOp::Delete { key: b"\x20" },
        BatchOp::Put { key: b"\xe0", value: b"\x01" },
    ];
    db.propose(end_batch).unwrap().commit().unwrap();
    let end_root = db.root_hash().unwrap();

    // Honest change proof over the key-empty range [0x60, 0xb0].
    let start = b"\x60".as_slice();
    let end = b"\xb0".as_slice();
    let proof = db
        .change_proof(start_root.clone(), end_root.clone(), Some(start), Some(end), None)
        .expect("change_proof should succeed");

    let ctx = verify_change_proof_structure(&proof, end_root.clone(), Some(start), Some(end), None)
        .expect("structural verification should pass");
    let parent = db.revision(start_root).unwrap();
    let proposal = db.apply_change_proof_to_parent(&proof, &*parent).unwrap();
    verify_change_proof_root_hash(&proof, &ctx, &proposal)
        .expect("BUG: honest change proof over an empty range was rejected");
}

Output:

BUG: honest change proof over an empty range was rejected: ProofError(UnexpectedValue)

Root cause

Both boundary proofs of a change proof are generated against the end trie (change_proof in firewood/src/merkle/mod.rs: start_proof = self.prove(start_key) where self is the end trie). So the "start proof" for start_key is an exclusion proof whose terminal is the nearest end-trie key greater than or equal to start_key.

For the fixture above, the end trie is {0xe0}, so the start proof for start_key = 0x60 is the node 0xe0 (the nearest key at or above 0x60). Verification then reconciles that node in the start-proof loop of verify_change_proof_root_hash, which classifies a node as in-range using only the lower bound:

if node_nibbles >= start_key_nibbles {
    Err(ProofError::UnexpectedValue)   // treated as an in-range value conflict
} else { ... }

Here 0xe0 is greater than start_key (0x60), so the check treats it as in-range and rejects it. But 0xe0 is also greater than end_key (0xb0), so it is really outside the range. Its value should be taken from the proof, not rejected as tampering. The check only compares the node against start_key, never against end_key, so a node past the upper bound looks in-range.

The same failure happens whenever the range holds no keys and a changed key sits above end_key. It does not depend on the specific keys used, and changes below the range verify fine.

Notes

Found via debugging of the change-proof verifier for a different issue. The change-proof fuzzer does not currently generate this shape (it draws range bounds from existing keys, so ranges are never key-empty); extending the fuzzer to cover key-empty ranges is planned as a follow-up.

To reproduce

See above

Expected behavior

The proof verifies: verify_change_proof_root_hash returns Ok.

Additional context

No response