Skip to content

MemForest::clone() shares nodes rather than snapshotting, due to Rc + interior mutability #151

Description

@USCMig

MemForest derives Clone. Its fields are Vec<Rc<Node<Hash>>> and
HashMap<Hash, Weak<Node<Hash>>>, and Node stores its hash in a Cell. The
derived clone therefore copies Rc handles rather than nodes, so mutating
either forest is visible through the other.

This is standard Rc behaviour, but combined with interior mutability it makes
clone() look like a snapshot while not being one. Anyone reaching for it to
save state before a speculative modification, reorg handling,
gets silently corrupted state rather than a compile error.

use rustreexo::mem_forest::MemForest;
use rustreexo::node_hash::BitcoinNodeHash;

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

#[test]
fn clone_should_be_an_independent_snapshot() {
    let leaves: Vec<BitcoinNodeHash> = (1..=8u32).map(leaf).collect();
    let mut forest: MemForest<BitcoinNodeHash> = MemForest::new();
    forest.modify(&leaves, &[]).unwrap();

    let snapshot = forest.clone();
    let before: Vec<_> = snapshot.get_roots().iter().map(|n| n.get_data()).collect();

    forest.modify(&[], &[leaves[0]]).unwrap();          // mutate the original
    let after: Vec<_> = snapshot.get_roots().iter().map(|n| n.get_data()).collect();

    assert_eq!(before, after);   // <-- FAILS: the snapshot changed too
}

serialize / deserialize does round-trip to an independent forest, at roughly
79 bytes per leaf, and is currently the only safe way to snapshot.

Possible resolutions, in rough order of preference:

  1. Implement Clone manually as a deep copy.
  2. Remove the derive, so the mistake becomes a compile error and callers are
    pushed to serialize/deserialize.
  3. Document it on the type, noting serialize/deserialize as the snapshot
    mechanism. Cheapest, but leaves the footgun in place.

Found while designing reorg rollback for a Zcash accumulator, where restoring
pre-block state is the whole operation. Related: there is no API to reinsert a
leaf at a specific position, so a deletion cannot be undone from a delta and a
snapshot is the only route, which is what led to clone() in the first
place.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions