warg_transparency/map/
proof.rs

1use alloc::vec::Vec;
2use core::marker::PhantomData;
3use std::iter::repeat;
4
5use warg_crypto::{
6    hash::{Hash, SupportedDigest},
7    VisitBytes,
8};
9
10use super::{
11    map::{hash_branch, hash_leaf},
12    path::{ReversePath, Side},
13};
14
15/// An inclusion proof of the specified value in a map
16///
17/// # Compression
18///
19/// Since the depth of a tree is always `n` and a proof needs to contain all
20/// branch node peers from the leaf to the root, a proof should contain `n`
21/// hashes. However, several strategies can be used to compress a proof;
22/// saving both memory and bytes on the wire.
23///
24/// First, the hash of the item and the root are known by both sides and can
25/// be omitted.
26///
27/// Second, sparse peers can be represented by `None`. Since we take references
28/// to the hashes, Rust null-optimization is used.
29///
30/// Third, since sparse peers are more likely at the bottom of the tree, we
31/// can omit all leading sparse peers. The verifier can dynamically reconstruct
32pub struct Proof<D, K, V>
33where
34    D: SupportedDigest,
35    K: VisitBytes,
36    V: VisitBytes,
37{
38    key: PhantomData<K>,
39    value: PhantomData<V>,
40    /// Sibling node hashes needed to construct a proof
41    pub peers: Vec<Option<Hash<D>>>,
42}
43
44impl<D, K, V> Proof<D, K, V>
45where
46    D: SupportedDigest,
47    K: VisitBytes,
48    V: VisitBytes,
49{
50    pub(crate) fn new(peers: Vec<Option<Hash<D>>>) -> Self {
51        Self {
52            key: PhantomData,
53            value: PhantomData,
54            peers,
55        }
56    }
57
58    pub(crate) fn push(&mut self, peer: Option<Hash<D>>) {
59        self.peers.push(peer);
60    }
61
62    /// Computes the root obtained by evaluating this inclusion proof with the given leaf
63    pub fn evaluate(&self, key: &K, value: &V) -> Hash<D> {
64        // Get the path from bottom to top.
65        let path = ReversePath::<D>::new(Hash::of(key));
66
67        let fill = repeat(None).take(256 - self.peers.len());
68        // Calculate the leaf hash.
69        let mut hash = hash_leaf(value);
70
71        // Loop over each side and peer.
72        let peers = fill.chain(self.peers.iter().cloned());
73        for (i, (side, peer)) in path.zip(peers).enumerate() {
74            match &peer {
75                Some(_) => {
76                    hash = match side {
77                        Side::Left => hash_branch(&hash, &peer.unwrap()),
78                        Side::Right => hash_branch(&peer.unwrap(), &hash),
79                    };
80                }
81                None => match side {
82                    Side::Left => hash = hash_branch(&hash, D::empty_tree_hash(i)),
83                    Side::Right => {
84                        hash = hash_branch(D::empty_tree_hash(i), &hash);
85                    }
86                },
87            }
88        }
89
90        hash
91    }
92}
93
94impl<D, K, V> From<Proof<D, K, V>> for Vec<Option<Hash<D>>>
95where
96    D: SupportedDigest,
97    K: VisitBytes,
98    V: VisitBytes,
99{
100    fn from(value: Proof<D, K, V>) -> Self {
101        value.peers
102    }
103}
104
105#[cfg(test)]
106mod tests {
107    #[test]
108    fn test_proof_evaluate() {
109        use warg_crypto::hash::Sha256;
110
111        let a = crate::map::Map::<Sha256, &str, &[u8]>::default();
112        let b = a.insert("foo", b"bar");
113        let c = b.insert("baz", b"bat");
114
115        let root = c.root().clone();
116
117        let p = c.prove("baz").unwrap();
118
119        assert_eq!(root, p.evaluate(&"baz", &b"bat".as_slice()));
120        assert_ne!(root, p.evaluate(&"other", &b"bar".as_slice()));
121    }
122}
warg_transparency/map/proof.rs

warg_transparency/map/
proof.rs
