Skip to main content

drive_proof_verifier/block_proof/
merkle.rs

1//! Tenderdash's Merkle tree (RFC 6962), the tree behind a block's hash, its `data_hash`
2//! and its `results_hash`.
3
4use super::BlockProofError;
5use sha2::{Digest, Sha256};
6
7const LEAF_PREFIX: [u8; 1] = [0];
8const INNER_PREFIX: [u8; 1] = [1];
9const HASH_SIZE: usize = 32;
10
11fn leaf_hash(leaf: &[u8]) -> [u8; 32] {
12    Sha256::new()
13        .chain_update(LEAF_PREFIX)
14        .chain_update(leaf)
15        .finalize()
16        .into()
17}
18
19fn inner_hash(left: &[u8], right: &[u8]) -> [u8; 32] {
20    Sha256::new()
21        .chain_update(INNER_PREFIX)
22        .chain_update(left)
23        .chain_update(right)
24        .finalize()
25        .into()
26}
27
28/// The largest power of two below `length`, which must be at least 2.
29fn split_point(length: usize) -> usize {
30    1 << (usize::BITS - 1 - (length - 1).leading_zeros())
31}
32
33/// The root of the tree over `leaves`.
34pub fn merkle_root<T: AsRef<[u8]>>(leaves: &[T]) -> [u8; 32] {
35    match leaves {
36        [] => Sha256::digest([]).into(),
37        [leaf] => leaf_hash(leaf.as_ref()),
38        _ => {
39            let (left, right) = leaves.split_at(split_point(leaves.len()));
40            inner_hash(&merkle_root(left), &merkle_root(right))
41        }
42    }
43}
44
45/// The tree over some leaves, with the paths of the selected ones: what a node needs to
46/// prove those leaves are under the root.
47#[derive(Debug)]
48pub struct MerkleTree {
49    /// The root of the tree.
50    pub root: [u8; 32],
51    /// For each selected leaf, the hashes from its sibling up to a child of the root.
52    pub paths: Vec<Vec<Vec<u8>>>,
53}
54
55impl MerkleTree {
56    /// Build the tree over `leaves`, keeping paths only for the positions in `selected`,
57    /// which must be ascending and within `leaves`.
58    pub fn new<T: AsRef<[u8]>>(leaves: &[T], selected: &[usize]) -> Self {
59        Self::build(leaves, 0, selected)
60    }
61
62    fn build<T: AsRef<[u8]>>(leaves: &[T], first: usize, selected: &[usize]) -> Self {
63        if selected.is_empty() {
64            return Self {
65                root: merkle_root(leaves),
66                paths: Vec::new(),
67            };
68        }
69        if leaves.len() < 2 {
70            return Self {
71                root: merkle_root(leaves),
72                paths: vec![Vec::new(); selected.len()],
73            };
74        }
75
76        let split = split_point(leaves.len());
77        let (left_leaves, right_leaves) = leaves.split_at(split);
78        let (left_selected, right_selected) =
79            selected.split_at(selected.partition_point(|&position| position < first + split));
80        let left = Self::build(left_leaves, first, left_selected);
81        let right = Self::build(right_leaves, first + split, right_selected);
82
83        let root = inner_hash(&left.root, &right.root);
84        let paths = left
85            .paths
86            .into_iter()
87            .map(|mut path| {
88                path.push(right.root.to_vec());
89                path
90            })
91            .chain(right.paths.into_iter().map(|mut path| {
92                path.push(left.root.to_vec());
93                path
94            }))
95            .collect();
96        Self { root, paths }
97    }
98}
99
100/// Follow `path` up from the leaf at `index` of a tree of `total` leaves, returning the
101/// root it leads to. `path` runs from the leaf's sibling up to a child of the root.
102///
103/// The position decides the order each pair is hashed in, so a path leads to the tree's
104/// root only from the position it was built for. `total` is the caller's claim: a path
105/// can also fit a tree of another size, at another position.
106pub fn root_from_path(
107    index: u32,
108    total: u32,
109    leaf: &[u8],
110    path: &[Vec<u8>],
111) -> Result<[u8; 32], BlockProofError> {
112    if index >= total {
113        return Err(BlockProofError::IndexOutOfRange { index, total });
114    }
115
116    // Walk down from the root to the leaf, noting at each level which side the leaf is on
117    let (mut position, mut size) = (index as usize, total as usize);
118    let mut leaf_is_on_the_left = Vec::new();
119    while size > 1 {
120        let split = split_point(size);
121        if position < split {
122            leaf_is_on_the_left.push(true);
123            size = split;
124        } else {
125            leaf_is_on_the_left.push(false);
126            position -= split;
127            size -= split;
128        }
129    }
130    let malformed = path.len() != leaf_is_on_the_left.len()
131        || path.iter().any(|sibling| sibling.len() != HASH_SIZE);
132    if malformed {
133        return Err(BlockProofError::MalformedPath { index, total });
134    }
135
136    // Then hash back up, the path giving the other side at each level
137    let root = path.iter().zip(leaf_is_on_the_left.iter().rev()).fold(
138        leaf_hash(leaf),
139        |hash, (sibling, &on_the_left)| {
140            if on_the_left {
141                inner_hash(&hash, sibling)
142            } else {
143                inner_hash(sibling, &hash)
144            }
145        },
146    );
147    Ok(root)
148}
149
150#[cfg(test)]
151mod tests {
152    use super::*;
153
154    /// `merkle.ProofsFromByteSlices` of Tenderdash's `crypto/merkle` over `leaf-0`..`leaf-6`.
155    const TENDERDASH_ROOT: &str =
156        "0b007fb915eb9b2a146f54b1c86ec53b664f8e455b7660b0b6ee13edc0d921c0";
157    const TENDERDASH_PATHS: [&[&str]; 7] = [
158        &[
159            "3145c409f259b7c53e32036090ff76751025a2498ba9823ef718cac50b4e616f",
160            "bd45ff28796704d88bdac51b1df553fda59837b616d6d1cb2114dbc3b087ff69",
161            "8eae6bd3b3a07f1f75ee72a531629e6eb31e42e62f760e47de52a53c3641ef23",
162        ],
163        &[
164            "305df59f9590c3c9ac63d2b2743c388e3792449078cebf7fb3dbe6471643b2b7",
165            "bd45ff28796704d88bdac51b1df553fda59837b616d6d1cb2114dbc3b087ff69",
166            "8eae6bd3b3a07f1f75ee72a531629e6eb31e42e62f760e47de52a53c3641ef23",
167        ],
168        &[
169            "f76836325aec5699d8d71f8e42e9d47c5c29b08059ba296384f7ca40ad3a40ae",
170            "60a53eed0de87a90c8e59427c59c46253c33a76a09502a51801300927b7e6bdc",
171            "8eae6bd3b3a07f1f75ee72a531629e6eb31e42e62f760e47de52a53c3641ef23",
172        ],
173        &[
174            "fca89f57c9f8c8eb4047a7ff9d333acf9e0f3384b20b255bceab0f216dcca267",
175            "60a53eed0de87a90c8e59427c59c46253c33a76a09502a51801300927b7e6bdc",
176            "8eae6bd3b3a07f1f75ee72a531629e6eb31e42e62f760e47de52a53c3641ef23",
177        ],
178        &[
179            "8f1593cb92f429d9340b9bbc1f0bb122adf8026c42a4a42142e2168931727236",
180            "676f3782f5b3a5fb4370ed49572cedc523f4a66322269c85f2af0509d17b0a4d",
181            "bdd1c5ff55b19cb6b0e7c761bf9a6ccaa27fbbfc07b74f1fabb6e911a0bd2ab3",
182        ],
183        &[
184            "ea9fc1a1b6e191b460d0d6306e3e870c173f39330f13cda1b70cfc72bdc398ba",
185            "676f3782f5b3a5fb4370ed49572cedc523f4a66322269c85f2af0509d17b0a4d",
186            "bdd1c5ff55b19cb6b0e7c761bf9a6ccaa27fbbfc07b74f1fabb6e911a0bd2ab3",
187        ],
188        &[
189            "985bb5d36b927800876871da925a7e82abe83a9ddba5882920a007a55ea2b376",
190            "bdd1c5ff55b19cb6b0e7c761bf9a6ccaa27fbbfc07b74f1fabb6e911a0bd2ab3",
191        ],
192    ];
193
194    fn tenderdash_leaves() -> Vec<Vec<u8>> {
195        (0..7)
196            .map(|index| format!("leaf-{index}").into_bytes())
197            .collect()
198    }
199
200    fn numbered_leaves(total: usize) -> Vec<Vec<u8>> {
201        (0..total)
202            .map(|index| index.to_be_bytes().to_vec())
203            .collect()
204    }
205
206    fn hex_path(path: &[Vec<u8>]) -> Vec<String> {
207        path.iter().map(hex::encode).collect()
208    }
209
210    #[test]
211    fn should_build_the_same_tree_as_tenderdash() {
212        let leaves = tenderdash_leaves();
213
214        let tree = MerkleTree::new(&leaves, &(0..leaves.len()).collect::<Vec<_>>());
215
216        assert_eq!(hex::encode(tree.root), TENDERDASH_ROOT);
217        for (path, expected) in tree.paths.iter().zip(TENDERDASH_PATHS) {
218            assert_eq!(hex_path(path), expected);
219        }
220    }
221
222    #[test]
223    fn should_follow_the_paths_tenderdash_builds_to_its_root() {
224        let leaves = tenderdash_leaves();
225
226        for (index, (leaf, path)) in leaves.iter().zip(TENDERDASH_PATHS).enumerate() {
227            let path = path
228                .iter()
229                .map(|hash| hex::decode(hash).unwrap())
230                .collect::<Vec<_>>();
231
232            let root = root_from_path(index as u32, 7, leaf, &path).unwrap();
233
234            assert_eq!(hex::encode(root), TENDERDASH_ROOT, "leaf {index}");
235        }
236    }
237
238    #[test]
239    fn should_hash_edge_trees_like_rfc_6962() {
240        assert_eq!(
241            hex::encode(merkle_root::<Vec<u8>>(&[])),
242            "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"
243        );
244        assert_eq!(
245            hex::encode(merkle_root(&[Vec::new()])),
246            "6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d"
247        );
248        assert_eq!(
249            hex::encode(merkle_root(&[b"L123456".to_vec()])),
250            "395aa064aa4c29f7010acfe3f25db9485bbd4b91897b6ad7ad547639252b4d56"
251        );
252        assert_eq!(
253            hex::encode(inner_hash(b"N123", b"N456")),
254            "aa217fe888e47007fa15edab33c2b492a722cb106c64667fc2b044444de66bbb"
255        );
256    }
257
258    #[test]
259    fn should_compute_the_same_root_without_building_paths() {
260        for total in 0..=33usize {
261            let leaves = numbered_leaves(total);
262            let all = (0..total).collect::<Vec<_>>();
263
264            assert_eq!(merkle_root(&leaves), MerkleTree::new(&leaves, &all).root);
265        }
266    }
267
268    #[test]
269    fn should_build_only_the_selected_paths() {
270        let leaves = tenderdash_leaves();
271
272        for selected in [vec![], vec![0], vec![6], vec![1, 4], vec![2, 3, 5]] {
273            let tree = MerkleTree::new(&leaves, &selected);
274
275            assert_eq!(hex::encode(tree.root), TENDERDASH_ROOT);
276            assert_eq!(tree.paths.len(), selected.len());
277            for (path, position) in tree.paths.iter().zip(&selected) {
278                assert_eq!(hex_path(path), TENDERDASH_PATHS[*position]);
279            }
280        }
281    }
282
283    #[test]
284    fn should_give_every_leaf_a_path_to_the_root() {
285        for total in 1..=33usize {
286            let leaves = numbered_leaves(total);
287            let tree = MerkleTree::new(&leaves, &(0..total).collect::<Vec<_>>());
288
289            for (index, leaf) in leaves.iter().enumerate() {
290                let root =
291                    root_from_path(index as u32, total as u32, leaf, &tree.paths[index]).unwrap();
292                assert_eq!(root, tree.root, "leaf {index} of {total}");
293            }
294        }
295    }
296
297    #[test]
298    fn should_not_reach_the_root_from_another_position() {
299        for total in 2..=33usize {
300            let leaves = numbered_leaves(total);
301            let tree = MerkleTree::new(&leaves, &(0..total).collect::<Vec<_>>());
302
303            for (index, leaf) in leaves.iter().enumerate() {
304                for claimed in (0..total).filter(|&claimed| claimed != index) {
305                    let root =
306                        root_from_path(claimed as u32, total as u32, leaf, &tree.paths[index]);
307                    assert_ne!(root.ok(), Some(tree.root), "leaf {index} as {claimed}");
308                }
309            }
310        }
311    }
312
313    #[test]
314    fn should_not_reach_the_root_from_another_leaf() {
315        let leaves = tenderdash_leaves();
316        let tree = MerkleTree::new(&leaves, &[3]);
317
318        let root = root_from_path(3, 7, b"leaf-4", &tree.paths[0]).unwrap();
319
320        assert_ne!(root, tree.root);
321    }
322
323    #[test]
324    fn should_refuse_a_position_outside_the_tree() {
325        assert_eq!(
326            root_from_path(7, 7, b"leaf", &[]),
327            Err(BlockProofError::IndexOutOfRange { index: 7, total: 7 })
328        );
329        assert_eq!(
330            root_from_path(0, 0, b"leaf", &[]),
331            Err(BlockProofError::IndexOutOfRange { index: 0, total: 0 })
332        );
333    }
334
335    #[test]
336    fn should_refuse_a_path_of_the_wrong_shape() {
337        let leaves = tenderdash_leaves();
338        let tree = MerkleTree::new(&leaves, &[2]);
339        let path = &tree.paths[0];
340        let malformed = Err(BlockProofError::MalformedPath { index: 2, total: 7 });
341
342        // too short, too long, and a sibling that is not a hash
343        assert_eq!(root_from_path(2, 7, b"leaf-2", &path[1..]), malformed);
344        let mut longer = path.clone();
345        longer.push(vec![0; 32]);
346        assert_eq!(root_from_path(2, 7, b"leaf-2", &longer), malformed);
347        let mut truncated = path.clone();
348        truncated[0].pop();
349        assert_eq!(root_from_path(2, 7, b"leaf-2", &truncated), malformed);
350
351        // a single leaf is its own root and has no path
352        assert_eq!(
353            root_from_path(0, 1, b"leaf", &[vec![0; 32]]),
354            Err(BlockProofError::MalformedPath { index: 0, total: 1 })
355        );
356        assert_eq!(root_from_path(0, 1, b"leaf", &[]), Ok(leaf_hash(b"leaf")));
357    }
358}