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:
- Implement
Clone manually as a deep copy.
- Remove the derive, so the mistake becomes a compile error and callers are
pushed to serialize/deserialize.
- 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.
MemForestderivesClone. Its fields areVec<Rc<Node<Hash>>>andHashMap<Hash, Weak<Node<Hash>>>, andNodestores its hash in aCell. Thederived clone therefore copies
Rchandles rather than nodes, so mutatingeither forest is visible through the other.
This is standard
Rcbehaviour, but combined with interior mutability it makesclone()look like a snapshot while not being one. Anyone reaching for it tosave state before a speculative modification, reorg handling,
gets silently corrupted state rather than a compile error.
serialize/deserializedoes round-trip to an independent forest, at roughly79 bytes per leaf, and is currently the only safe way to snapshot.
Possible resolutions, in rough order of preference:
Clonemanually as a deep copy.pushed to
serialize/deserialize.serialize/deserializeas the snapshotmechanism. 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 firstplace.