MemForest::prove returns invalid proofs for the sibling of a deleted leaf

[USCMig]

MemForest::prove returns Ok(proof) for a leaf whose sibling has been
deleted, but the resulting proof fails Stump::verify. The forest's state is
correct — its roots match the Stump's exactly — so this is specifically proof
generation, not the deletion itself.

The same happens through Pollard, and there it is worse: after a deletion it
cannot produce a valid proof for an unaffected leaf either, failing with
"Could not upgrade node, this is probably a bug".

Reproduced against rustreexo = "0.6.0" with stock BitcoinNodeHash.

Why it matters

Spending one of two adjacent outputs is routine, so any node serving inclusion
proofs from a MemForest hits this immediately in normal operation. Because
prove() returns Ok, the caller has no signal that anything is wrong until a
verifier rejects the proof — the failure surfaces at the wrong end of the wire.

Minimal reproduction

use rustreexo::mem_forest::MemForest;
use rustreexo::node_hash::BitcoinNodeHash;
use rustreexo::proof::Proof;
use rustreexo::stump::Stump;

fn leaf(n: u32) -> BitcoinNodeHash {
    let mut bytes = [0u8; 32];
    bytes[..4].copy_from_slice(&n.to_le_bytes());
    BitcoinNodeHash::new(bytes)
}

#[test]
fn sibling_of_deleted_leaf_cannot_be_proven() {
    let leaves: Vec<BitcoinNodeHash> = (1..=8u32).map(leaf).collect();

    let mut forest: MemForest<BitcoinNodeHash> = MemForest::new();
    let stump: Stump<BitcoinNodeHash> = Stump::new();

    forest.modify(&leaves, &[]).unwrap();
    let (stump, _) = stump.modify(&leaves, &[], &Proof::default()).unwrap();

    // Before any deletion every leaf proves correctly.
    for target in &leaves {
        let proof = forest.prove(&[*target]).unwrap();
        assert_eq!(stump.verify(&proof, &[*target]), Ok(true));
    }

    // Delete leaf 0. Leaf 1 is its sibling.
    let deletion_proof = forest.prove(&[leaves[0]]).unwrap();
    forest.modify(&[], &[leaves[0]]).unwrap();
    let (stump, _) = stump.modify(&[], &[leaves[0]], &deletion_proof).unwrap();

    // State is fine: forest and stump agree on the roots.
    let forest_roots: Vec<_> = forest.get_roots().iter().map(|n| n.get_data()).collect();
    assert_eq!(forest_roots, stump.roots);

    // A leaf whose sibling is untouched still proves correctly.
    let ok = forest.prove(&[leaves[3]]).unwrap();
    assert_eq!(stump.verify(&ok, &[leaves[3]]), Ok(true));

    // The sibling of the deleted leaf does not. prove() returns Ok...
    let broken = forest.prove(&[leaves[1]]).unwrap();
    // ...but the proof does not verify.
    assert_eq!(stump.verify(&broken, &[leaves[1]]), Ok(true)); // <-- FAILS
}

Suspected cause

Not verified — offered only as a starting point, and it may be wrong.

In canonical Utreexo the surviving sibling is promoted one row when its partner
is deleted, so its proof should become one node shorter. MemForest::prove
appears to still report the leaf's pre-deletion position, so verification then
walks a path that includes a sibling no longer on it.

Pollard variant

use rustreexo::pollard::{Pollard, PollardAddition};

#[test]
fn pollard_proof_generation_breaks_after_a_deletion() {
    let leaves: Vec<BitcoinNodeHash> = (1..=8u32).map(leaf).collect();
    let mut pollard: Pollard<BitcoinNodeHash> = Pollard::new();
    let stump: Stump<BitcoinNodeHash> = Stump::new();

    let additions: Vec<_> = leaves
        .iter()
        .map(|hash| PollardAddition { hash: *hash, remember: true })
        .collect();
    pollard.modify(&additions, &[], Proof::default()).unwrap();
    let (stump, _) = stump.modify(&leaves, &[], &Proof::default()).unwrap();
    assert_eq!(pollard.roots(), stump.roots);

    let deletion_proof = pollard.batch_proof(&[leaves[0]]).unwrap();
    pollard.modify(&[], &[leaves[0]], deletion_proof.clone()).unwrap();
    let (stump, _) = stump.modify(&[], &[leaves[0]], &deletion_proof).unwrap();
    assert_eq!(pollard.roots(), stump.roots);

    // Both of these fail — including leaf 3, which the deletion did not touch.
    let sibling = pollard.batch_proof(&[leaves[1]]).unwrap();
    assert_eq!(stump.verify(&sibling, &[leaves[1]]), Ok(true)); // <-- FAILS

    let unaffected = pollard.batch_proof(&[leaves[3]]).unwrap();
    assert_eq!(stump.verify(&unaffected, &[leaves[3]]), Ok(true)); // <-- FAILS
}

Environment

• rustreexo 0.6.0 from crates.io
• Found while building a Zcash transparent-UTXO accumulator; the tests above
  are reduced from that project's differential suite and use only stock
  rustreexo types, so custom hash implementations are not involved.