warg_transparency/map/
mod.rs

1//! Immutable Map w/ Inclusion Proofs
2//!
3//! The main type in this module is [`Map`]. It implements an immutable map
4//! backed by a sparse [Merkle tree][0], which provides the ability to generate
5//! inclusion proofs for its items. This data structure is inspired by
6//! the [Revocation Transparency][1] effort.
7//!
8//! [0]: https://en.wikipedia.org/wiki/Merkle_tree
9//! [1]: https://www.links.org/files/RevocationTransparency.pdf
10
11#![allow(clippy::module_inception)]
12
13mod fork;
14mod link;
15mod map;
16mod node;
17mod path;
18mod proof;
19mod proof_bundle;
20mod singleton;
21
22pub use map::Map;
23pub use proof::Proof;
24pub use proof_bundle::ProofBundle as MapProofBundle;
25
26#[cfg(test)]
27mod test {
28    use warg_crypto::{
29        hash::{Sha256, SupportedDigest},
30        VisitBytes,
31    };
32
33    use super::Map;
34
35    #[test]
36    fn insert() {
37        // Prepare three trees.
38        let first = Map::<Sha256, &'static str, &'static str>::default();
39        let second = first.insert("foo", "bar");
40        let third = second.insert("baz", "bat");
41
42        // Ensure the digests don't match.
43        assert_ne!(first.root(), second.root());
44        assert_ne!(first.root(), third.root());
45        assert_ne!(second.root(), third.root());
46
47        // Ensure the empty tree has the known root.
48        assert_eq!(&first.root().clone(), Sha256::empty_tree_hash(256));
49    }
50
51    #[test]
52    fn len() {
53        let first = Map::<Sha256, &'static str, &'static str>::default();
54        assert_eq!(first.len(), 0);
55
56        let second = first.insert("foo", "bar");
57        assert_eq!(second.len(), 1);
58
59        let third = second.insert("bar", "bat");
60        assert_eq!(third.len(), 2);
61
62        let fourth = third.insert("foo", "qux");
63        assert_eq!(fourth.len(), 2);
64    }
65
66    #[test]
67    fn is_empty() {
68        let first = Map::<Sha256, &'static str, &'static str>::default();
69        assert!(first.is_empty());
70
71        let second = first.insert("foo", "bar");
72        assert!(!second.is_empty());
73
74        let third = second.insert("bar", "bat");
75        assert!(!third.is_empty());
76    }
77
78    #[test]
79    fn extend() {
80        let first = Map::<Sha256, &'static str, &'static str>::default();
81        let second = first.insert("foo", "bar");
82        let third = second.insert("baz", "bat");
83
84        let extended = first.extend([("foo", "bar"), ("baz", "bat")]);
85        assert!(!extended.is_empty());
86        assert_eq!(extended.len(), 2);
87        assert_eq!(extended, third);
88
89        let extended = first.extend([("baz", "bat"), ("foo", "bar")]);
90        assert!(!extended.is_empty());
91        assert_eq!(extended.len(), 2);
92        assert_eq!(extended, third);
93    }
94
95    #[test]
96    fn replace() {
97        let first = Map::<Sha256, &'static str, &'static str>::default();
98        let second = first.insert("foo", "bar");
99        assert_eq!(second.len(), 1);
100
101        let third = second.insert("foo", "baz");
102        assert_eq!(third.len(), 1);
103
104        // Ensure the digests don't match.
105        assert_ne!(first.root(), second.root());
106        assert_ne!(first.root(), third.root());
107        assert_ne!(second.root(), third.root());
108    }
109
110    #[test]
111    fn prove() {
112        fn check<D: SupportedDigest, K: VisitBytes + PartialEq + Clone, V: VisitBytes + Clone>(
113            tree: &Map<D, K, V>,
114            key: K,
115            value: V,
116        ) {
117            let proof = tree.prove(key.clone()).unwrap();
118            assert_eq!(tree.root().clone(), proof.evaluate(&key, &value));
119        }
120
121        let first = Map::<Sha256, &'static str, &'static str>::default();
122        assert!(first.prove("foo").is_none());
123        assert!(first.prove("baz").is_none());
124        assert!(first.prove("qux").is_none());
125
126        let second = first.insert("foo", "bar");
127        check(&second, "foo", "bar");
128        assert!(second.prove("baz").is_none());
129        assert!(second.prove("qux").is_none());
130        let third = second.insert("bar", "bat");
131        check(&third, "foo", "bar");
132        check(&third, "bar", "bat");
133        assert!(third.prove("qux").is_none());
134
135        let fourth = third.insert("foo", "qux");
136        check(&fourth, "foo", "qux");
137    }
138}
warg_transparency/map/mod.rs

warg_transparency/map/
mod.rs
