Assessment reports>Grug>Discussion>Property testing of ics23_prove

Property testing of ics23_prove

The following property test consists of multiple batches of insertions and deletions in a pattern that covers every case of applying operations to a tree, except for those explicitly marked as unreachable. We recommend its inclusion in the test suite to mitigate potential future bugs as the code evolves.

proptest! {
    #[test]
    fn proptest_apply_ics23prove(
        (batch1, removals_batch1) in prop::collection::hash_map("[a-z]{1,10}", "[a-z]{1,10}", 1..100).prop_flat_map(|batch1| {
            let len = batch1.len();
            (Just(batch1), prop::collection::vec(any::<prop::sample::Selector>(), 0..len))
        }),
        batch2 in prop::collection::hash_map("[a-z]{1,10}", "[a-z]{1,10}", 1..100),
        removals_batch2 in prop::collection::vec(any::<prop::sample::Selector>(), 0..50)
    ) {
        let path = TempDataDir::new("_grug_disk_db_apply_ics23prove");
        let db = DiskDb::open(&path).unwrap();
        use std::collections::BTreeMap;
        let mut state = BTreeMap::new();
        let (_, maybe_root) = db.flush_and_commit(Batch::from(batch1.clone().into_iter().map(|(k, v)| (k.into_bytes(), Op::Insert(v.into_bytes()))).collect::<BTreeMap<_,_>>())).unwrap();
        let root0 = maybe_root.unwrap().to_vec();
        for (k, v) in batch1.iter() {
            state.insert(k.clone().into_bytes(), v.clone().into_bytes());
        }
        for (k, v) in state.iter() {
            let proof = db.ics23_prove(k.clone(), None).unwrap();
            assert!(matches!(proof, ics23::CommitmentProof { proof: Some(ics23::commitment_proof::Proof::Exist(_)) }));
            assert!(ics23::verify_membership::<HostFunctionsManager>(&proof, &ICS23_PROOF_SPEC, &root0, &k, &v));
        }
        let (_, maybe_root) = db.flush_and_commit(Batch::from(removals_batch1.iter().map(|r| (r.select(&batch1).0.clone().into_bytes(), Op::Delete)).collect::<BTreeMap<_,_>>())).unwrap();
        let root1 = maybe_root.unwrap().to_vec();
        for r in removals_batch1.iter() {
            let pre_k = r.select(&batch1).0;
            let k = pre_k.clone().into_bytes();
            state.remove(&k);
            let proof = db.ics23_prove(k.clone(), Some(0)).unwrap();
            assert!(matches!(proof, ics23::CommitmentProof { proof: Some(ics23::commitment_proof::Proof::Exist(_)) }), "proof: {:?}, k: {:?}", proof, pre_k);
            assert!(ics23::verify_membership::<HostFunctionsManager>(&proof, &ICS23_PROOF_SPEC, &root0, &k, &batch1[pre_k].clone().into_bytes()));
            let proof = db.ics23_prove(k.clone(), None).unwrap();
            assert!(matches!(proof, ics23::CommitmentProof { proof: Some(ics23::commitment_proof::Proof::Nonexist(_)) }));
            assert!(ics23::verify_non_membership::<HostFunctionsManager>(&proof, &ICS23_PROOF_SPEC, &root1, &k));
        }
        let batch_batch2 = Batch::from(
            removals_batch2.iter().map(|r| (r.select(&batch1).0.clone().into_bytes(), Op::Delete))
            .chain(batch2.clone().into_iter().map(|(k, v)| (k.into_bytes(), Op::Insert(v.into_bytes()))))
            .collect::<BTreeMap<_,_>>()
        );
        let (_, maybe_root) = db.flush_and_commit(batch_batch2).unwrap();
        let root2 = maybe_root.unwrap().to_vec();
        for r in removals_batch2.iter() {
            let pre_k = r.select(&batch1).0;
            let k = pre_k.clone().into_bytes();
            state.remove(&k);
            if !batch2.contains_key(pre_k) {
                let proof = db.ics23_prove(k.clone(), None).unwrap();
                assert!(matches!(proof, ics23::CommitmentProof { proof: Some(ics23::commitment_proof::Proof::Nonexist(_)) }));
                assert!(ics23::verify_non_membership::<HostFunctionsManager>(&proof, &ICS23_PROOF_SPEC, &root2, &k));
            }
        }
        for (k, v) in batch2.iter() {
            state.insert(k.clone().into_bytes(), v.clone().into_bytes());
        }
        for (k, v) in state.iter() {
            let proof = db.ics23_prove(k.clone(), None).unwrap();
            assert!(matches!(proof, ics23::CommitmentProof { proof: Some(ics23::commitment_proof::Proof::Exist(_)) }));
            assert!(ics23::verify_membership::<HostFunctionsManager>(&proof, &ICS23_PROOF_SPEC, &root2, &k, &v));
        }
    }
}

This recommendation has been acknowledged by Left Curve Software Ltd., and a similar test was incorporated in commit .

Zellic © 2025Back to top ↑