Description

The MerkleProof::prove function for constructing Diem-style proofs of nonmembership returns an error when attempting to look up the root node in the empty tree. This is demonstrated by the following test:

#[test]
fn test_removal_nonmembership() {
    let mut storage = MockStorage::new();
    TREE.apply_raw(&mut storage, 0, 1, &Batch::from([(b"a".to_vec(), Op::Insert(b"a".to_vec()))])).unwrap();
    TREE.apply_raw(&mut storage, 1, 2, &Batch::from([(b"a".to_vec(), Op::Delete)])).unwrap();
    let proof = TREE.prove(&storage, b"a".hash256(), 2);
    assert!(matches!(proof, Ok(Proof::NonMembership(_))), "{:?}", proof);
}

Impact

As Diem-style proofs are not used for IBC, this does not risk funds being locked by failure to prove an ICS-4 packet time-out. However, Diem-style proofs are constructed through ABCI "/store" queries, which will incorrectly return an error instead of successfully returning a nonexistence proof if the store is empty.

Recommendations

Use an internal node with neither child present to represent the empty tree in proof construction and verification instead of permitting the root to be absent.

Remediation

This issue has been acknowledged by Left Curve Software Ltd., and a fix was implemented in commit 58da8b70↗.