15698235808

Committed 17 Jun 2025 04:33AM UTC coverage: 78.333% (+0.04%) from 78.291%

Build # 15698235808

Build Type

Pull #804

github

Committed by

web-flow

Commit Message

Merge ed47dd2dd into 6f12ef8f2

Pull Request Pull Request #804: Add autolykos 2 validation for custom message

Run Details

49 of 62 new or added lines in 5 files covered. (79.03%)

5 existing lines in 2 files now uncovered.

11764 of 15018 relevant lines covered (78.33%)

2.89 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

95.76

/ergo-merkle-tree/src/merkletree.rs

use crate::batchmerkleproof::{BatchMerkleProof, BatchMerkleProofIndex};
use crate::{prefixed_hash, prefixed_hash2, INTERNAL_PREFIX, LEAF_PREFIX};
use ergo_chain_types::Digest32;
use sigma_util::hash::blake2b256_hash;
use std::collections::{BTreeSet, HashMap};

/// Node for a Merkle Tree
#[derive(Debug, Clone, Eq, PartialEq)]
#[cfg_attr(feature = "json", derive(serde::Serialize))]
pub enum MerkleNode {
    #[doc(hidden)]
    Node { hash: Digest32 },
    /// Leaf Node in MerkleTree. Can be created using [`Self::from_bytes`]
    Leaf {
        /// 32 byte Blake2b256 hash for data
        hash: Digest32,
        /// Leaf Data
        data: Vec<u8>,
    },
    #[doc(hidden)]
    EmptyNode,
}

impl MerkleNode {
    /// Creates a new Leaf Node from bytes. The hash is prefixed with a leaf node prefix.
    pub fn from_bytes<T: Into<Vec<u8>>>(bytes: T) -> Self {
        let bytes = bytes.into();
        let hash = prefixed_hash(LEAF_PREFIX, &bytes);
        MerkleNode::Leaf { hash, data: bytes }
    }
    /// Gets hash for the node, returns None if it's an Empty Node
    pub fn get_hash(&self) -> Option<&Digest32> {
        match self {
            MerkleNode::Node { hash } => Some(hash),
            MerkleNode::Leaf { hash, .. } => Some(hash),
            _ => None,
        }
    }
    /// Gets data for the node if it's a leaf node
    pub fn get_leaf_data(&self) -> Option<&Vec<u8>> {
        match self {
            MerkleNode::Leaf { data, .. } => Some(data),
            _ => None,
        }
    }
    pub(crate) fn empty() -> Self {
        Self::EmptyNode
    }
}

// utillity functions for indexing a binary tree
fn get_left(node_index: usize) -> usize {
    2 * node_index + 1
}
fn get_right(node_index: usize) -> usize {
    2 * node_index + 2
}

fn get_parent(index: usize) -> Option<usize> {
    index.checked_sub(1).map(|v| v / 2)
}

fn get_sibling(index: usize) -> Option<usize> {
    let parent_index = get_parent(index)?;
    if get_left(parent_index) != index {
        Some(get_left(parent_index))
    } else {
        Some(get_right(parent_index))
    }
}

// builds a new MerkleProof from tree nodes
fn build_proof(
    nodes: &[MerkleNode],
    mut leaf_index: usize,
    internal_nodes: usize,
) -> Option<crate::MerkleProof> {
    leaf_index += internal_nodes;
    let mut proof_nodes: Vec<crate::LevelNode> = vec![];
    let leaf_data = match nodes.get(leaf_index) {
        Some(MerkleNode::Leaf { data, .. }) => data,
        _ => return None,
    };
    while let Some(sibling) = get_sibling(leaf_index) {
        let side = if sibling == leaf_index + 1 {
            crate::NodeSide::Left // side information is encoded relative to the node we're trying to prove is in the tree. The leaf is on the left of the current node
        } else {
            crate::NodeSide::Right
        };
        match nodes[sibling].get_hash() {
            Some(hash) => proof_nodes.push(crate::LevelNode::new(*hash, side)),
            _ => proof_nodes.push(crate::LevelNode::empty_node(side)),
        }
        leaf_index = get_parent(leaf_index)?;
    }

    Some(crate::MerkleProof::new(leaf_data, &proof_nodes))
}

fn build_multiproof(
    nodes: &[MerkleNode],
    leaf_indices: &[usize],
    internal_nodes: usize,
) -> Option<BatchMerkleProof> {
    let mut multiproof: Vec<crate::LevelNode> = vec![];

    let mut a: BTreeSet<usize> = leaf_indices
        .iter()
        .map(|idx| idx + internal_nodes)
        .collect();
    // while a does not contain the root index (0)
    while !a.contains(&0) {
        let mut b_pruned = BTreeSet::new();
        for node in &a {
            // for each leaf node, insert it and it's neighbor into the set. Since we're inserting into a set, we don't need any deduplication or sorting
            b_pruned.insert(*node);
            b_pruned.insert(get_sibling(*node)?);
        }

        let diff = &b_pruned - &a;
        for node in diff {
            let side = match get_sibling(node) {
                Some(s) if s == node - 1 => crate::NodeSide::Right,
                Some(_) => crate::NodeSide::Left,
                None => unreachable!(),
            };
            let levelnode = match nodes[node].get_hash() {
                Some(hash) => crate::LevelNode::new(*hash, side),
                None => crate::LevelNode::empty_node(side),
            };
            multiproof.push(levelnode);
        }
        a = b_pruned.into_iter().flat_map(get_parent).collect();
    }

    Some(BatchMerkleProof::new(
        leaf_indices
            .iter()
            .flat_map(|idx| {
                Some(BatchMerkleProofIndex {
                    index: *idx,
                    hash: nodes[idx + internal_nodes].get_hash().cloned()?,
                })
            })
            .collect(),
        multiproof,
    ))
}

/// Merkle Tree
#[derive(Debug)]
#[cfg_attr(feature = "json", derive(serde::Serialize))]
pub struct MerkleTree {
    nodes: Vec<MerkleNode>,
    elements_hash_index: HashMap<Digest32, usize>,
    internal_nodes: usize,
}

impl MerkleTree {
    /// Creates a new MerkleTree from leaf nodes
    pub fn new(nodes: impl Into<Vec<MerkleNode>>) -> Self {
        #[allow(clippy::unwrap_used)]
        fn build_nodes(nodes: &mut [MerkleNode]) {
            for pair in (1..nodes.len()).step_by(2).rev() {
                let node = match (
                    nodes[pair].get_hash(),
                    nodes[get_sibling(pair).unwrap()].get_hash(), // since we pad nodes with no sibling with an empty node, get_sibling should always return Some
                ) {
                    (Some(left_hash), Some(right_hash)) => MerkleNode::Node {
                        hash: prefixed_hash2(
                            INTERNAL_PREFIX,
                            left_hash.as_ref(),
                            right_hash.as_ref(),
                        ),
                    },
                    (Some(hash), None) => MerkleNode::Node {
                        hash: prefixed_hash(INTERNAL_PREFIX, hash.as_ref()),
                    },
                    (None, None) => MerkleNode::EmptyNode,
                    _ => unreachable!(),
                };
                nodes[get_parent(pair).unwrap()] = node;
            }
        }
        let mut tree_nodes = nodes.into();
        if tree_nodes.len() % 2 == 1 {
            tree_nodes.push(MerkleNode::EmptyNode);
        }
        let elements_hash_index = tree_nodes
            .iter()
            .flat_map(MerkleNode::get_hash)
            .enumerate()
            .map(|(i, node)| (*node, i))
            .collect();
        let leaf_nodes = tree_nodes.len();
        // prepend leaf nodes with empty nodes to build the full tree
        tree_nodes.splice(
            0..0,
            std::iter::repeat_n(
                MerkleNode::empty(),
                tree_nodes.len().next_power_of_two() - 1,
            ),
        );
        build_nodes(&mut tree_nodes);
        let nodes_len = tree_nodes.len();
        Self {
            nodes: tree_nodes,
            elements_hash_index,
            internal_nodes: nodes_len - leaf_nodes,
        }
    }

    /// Returns the root hash for MerkleTree. If the tree is empty, then returns [0; 32]
    pub fn root_hash(&self) -> Digest32 {
        self.nodes
            .first()
            .and_then(MerkleNode::get_hash)
            .cloned()
            .unwrap_or_else(Digest32::zero)
    }
    /// Returns the root hash for MerkleTree. If the tree is empty, then returns a special hash '0e5751c026e543b2e8ab2eb06099daa1d1e5df47778f7787faab45cdf12fe3a8', which is extension/transaction root hash for genesis block
    /// See: <https://github.com/ergoplatform/ergo/issues/1077>
    pub fn root_hash_special(&self) -> Digest32 {
        self.nodes
            .first()
            .and_then(MerkleNode::get_hash)
            .cloned()
            .unwrap_or_else(|| {
                let hash = blake2b256_hash(&[]);
                Digest32::from(hash)
            })
    }

    /// Returns HashMap of hashes and their index in the tree
    pub fn get_elements_hash_index(&self) -> &HashMap<Digest32, usize> {
        &self.elements_hash_index
    }

    /// Builds a [`crate::MerkleProof`] for leaf_index. Returns None if index does not exist
    pub fn proof_by_index(&self, leaf_index: usize) -> Option<crate::MerkleProof> {
        build_proof(&self.nodes, leaf_index, self.internal_nodes)
    }
    /// Builds a [`crate::MerkleProof`] for given hash. Returns None if hash is not a leaf of tree
    pub fn proof_by_element_hash(&self, hash: &Digest32) -> Option<crate::MerkleProof> {
        let index = *self.elements_hash_index.get(hash)?;
        self.proof_by_index(index)
    }
    /// Builds a [`crate::MerkleProof`] for element, by searching for its hash in the tree
    pub fn proof_by_element(&self, data: &[u8]) -> Option<crate::MerkleProof> {
        let hash = prefixed_hash(LEAF_PREFIX, data);
        self.proof_by_element_hash(&hash)
    }

    /// Builds a [`crate::BatchMerkleProof`] for given indices
    pub fn proof_by_indices(
        &self,
        leaf_indices: &[usize],
    ) -> Option<crate::batchmerkleproof::BatchMerkleProof> {
        let mut leaf_indices = leaf_indices.to_owned();
        leaf_indices.sort_unstable();
        leaf_indices.dedup();
        // check that node index is in bounds, a leaf node, and not an empty node
        if leaf_indices.is_empty()
            || leaf_indices.iter().any(|i| {
                self.nodes
                    .get(self.internal_nodes + *i)
                    .and_then(MerkleNode::get_leaf_data)
                    .is_none()
            })
        {
            return None;
        }

        build_multiproof(&self.nodes, &leaf_indices, self.internal_nodes)
    }
}

#[cfg(test)]
#[allow(clippy::unwrap_used, clippy::panic)]
mod test {
    use crate::{prefixed_hash, prefixed_hash2, MerkleNode, MerkleTree};

    #[test]
    fn merkle_tree_zero_elements() {
        let tree = MerkleTree::new(&[][..]);
        assert!(tree.root_hash().as_ref() == [0; 32]);
    }
    #[test]
    fn merkle_tree_test_one_element() {
        // Here the merkle tree looks as follows:
        //      I
        //     / \
        //    L   E
        // Where `I`, `L`, and `E` denote the root internal node, leaf node, and empty node,
        // respectively.

        let data = [1; 32];
        let node = MerkleNode::from_bytes(data);
        let tree = MerkleTree::new(&[node][..]);
        assert_eq!(
            tree.root_hash(),
            prefixed_hash(1, prefixed_hash(0, &data).as_ref())
        );
    }
    #[test]
    fn merkle_tree_test_five_elements() {
        let bytes = [1u8; 32];
        let nodes = vec![MerkleNode::from_bytes(bytes); 5];
        let tree = MerkleTree::new(&*nodes);
        let h0x = prefixed_hash(0, &bytes);
        let h10 = prefixed_hash2(1, h0x.as_ref(), h0x.as_ref());
        let h11 = &h10;
        let h12 = prefixed_hash(1, h0x.0.as_ref());
        let h20 = prefixed_hash2(1, h10.as_ref(), h11.as_ref());
        let h21 = prefixed_hash(1, h12.as_ref());
        let h30 = prefixed_hash2(1, h20.as_ref(), h21.as_ref());
        assert_eq!(tree.root_hash(), h30);
    }

    #[test]
    fn merkle_tree_test_merkleproof() {
        let nodes = [
            MerkleNode::from_bytes([1; 32]),
            MerkleNode::from_bytes([2; 32]),
            MerkleNode::from_bytes([3; 32]),
            MerkleNode::from_bytes([4; 32]),
            MerkleNode::from_bytes([5; 32]),
        ];
        let tree = MerkleTree::new(&nodes[..]);
        let tree_root = tree.root_hash();
        for (i, node) in nodes.iter().enumerate() {
            assert_eq!(
                tree.proof_by_index(i).unwrap().get_leaf_data(),
                node.get_leaf_data().unwrap()
            );
            assert!(tree.proof_by_index(i).unwrap().valid(tree_root.as_ref()));
            assert!(tree
                .proof_by_element(node.get_leaf_data().unwrap())
                .unwrap()
                .valid(tree_root.as_ref()));
            assert!(tree
                .proof_by_element_hash(node.get_hash().unwrap())
                .unwrap()
                .valid(tree_root.as_ref()));
        }
    }
}

#[cfg(feature = "arbitrary")]
#[cfg(test)]
#[allow(clippy::unwrap_used)]
mod arbitrary {
    use crate::{MerkleNode, MerkleTree};
    use proptest::array::uniform32;
    use proptest::collection::vec;
    use proptest::prelude::*;
    proptest! {
        #[test]
        fn merkle_tree_test_arbitrary_proof(data in vec(uniform32(0u8..), 0..100)) {
            let nodes: Vec<MerkleNode> = data.into_iter().map(MerkleNode::from_bytes).collect();
            let tree = MerkleTree::new(&*nodes);
            for (i, node) in nodes.iter().enumerate() {
                let proof = tree.proof_by_index(i).unwrap();
                assert_eq!(
                    proof.get_leaf_data(),
                    node.get_leaf_data().unwrap()
                );
                assert!(proof.valid(tree.root_hash().as_ref()));
            }
        }
        #[test]
        fn merkle_tree_test_arbitrary_batch_proof(data in vec(uniform32(0u8..), 0..1000), indices in vec(0..1000usize, 0..1000)) {
            let valid = indices.iter().all(|i| *i < data.len()) && !indices.is_empty(); // TODO, is there any better strategy for proptest that doesn't require us to filter out invalid indices
            let nodes: Vec<MerkleNode> = data.into_iter().map(MerkleNode::from_bytes).collect();
            let tree = MerkleTree::new(&*nodes);
            if valid {
                assert!(tree.proof_by_indices(&indices).unwrap().valid(tree.root_hash().as_ref()));
            }
            else {
                assert!(tree.proof_by_indices(&indices).is_none());
            }
        }
    }
}

1	use crate::batchmerkleproof::{BatchMerkleProof, BatchMerkleProofIndex};
2	use crate::{prefixed_hash, prefixed_hash2, INTERNAL_PREFIX, LEAF_PREFIX};
3	use ergo_chain_types::Digest32;
4	use sigma_util::hash::blake2b256_hash;
5	use std::collections::{BTreeSet, HashMap};
6
7	/// Node for a Merkle Tree
8	#[derive(Debug, Clone, Eq, PartialEq)]
9	#[cfg_attr(feature = "json", derive(serde::Serialize))]
10	pub enum MerkleNode {
11	#[doc(hidden)]
12	Node { hash: Digest32 },
13	/// Leaf Node in MerkleTree. Can be created using [`Self::from_bytes`]
14	Leaf {
15	/// 32 byte Blake2b256 hash for data
16	hash: Digest32,
17	/// Leaf Data
18	data: Vec<u8>,
19	},
20	#[doc(hidden)]
21	EmptyNode,
22	}
23
24	impl MerkleNode {
25	/// Creates a new Leaf Node from bytes. The hash is prefixed with a leaf node prefix.
26	pub fn from_bytes<T: Into<Vec<u8>>>(bytes: T) -> Self {	4✔
27	let bytes = bytes.into();	2✔
28	let hash = prefixed_hash(LEAF_PREFIX, &bytes);	5✔
29	MerkleNode::Leaf { hash, data: bytes }
30	}
31	/// Gets hash for the node, returns None if it's an Empty Node
32	pub fn get_hash(&self) -> Option<&Digest32> {	3✔
33	match self {	5✔
34	MerkleNode::Node { hash } => Some(hash),	3✔
35	MerkleNode::Leaf { hash, .. } => Some(hash),	3✔
36	_ => None,	5✔
37	}
38	}
39	/// Gets data for the node if it's a leaf node
40	pub fn get_leaf_data(&self) -> Option<&Vec<u8>> {	4✔
41	match self {	2✔
42	MerkleNode::Leaf { data, .. } => Some(data),	3✔
43	_ => None,	1✔
44	}
45	}
46	pub(crate) fn empty() -> Self {	4✔
47	Self::EmptyNode	2✔
48	}
49	}
50
51	// utillity functions for indexing a binary tree
52	fn get_left(node_index: usize) -> usize {	2✔
53	2 * node_index + 1	4✔
54	}
55	fn get_right(node_index: usize) -> usize {	4✔
56	2 * node_index + 2	2✔
57	}
58
59	fn get_parent(index: usize) -> Option<usize> {	4✔
60	index.checked_sub(1).map(\|v\| v / 2)	8✔
61	}
62
63	fn get_sibling(index: usize) -> Option<usize> {	4✔
64	let parent_index = get_parent(index)?;	2✔
65	if get_left(parent_index) != index {	8✔
66	Some(get_left(parent_index))	2✔
67	} else {
68	Some(get_right(parent_index))	2✔
69	}
70	}
71
72	// builds a new MerkleProof from tree nodes
73	fn build_proof(	1✔
74	nodes: &[MerkleNode],
75	mut leaf_index: usize,
76	internal_nodes: usize,
77	) -> Option<crate::MerkleProof> {
78	leaf_index += internal_nodes;	1✔
79	let mut proof_nodes: Vec<crate::LevelNode> = vec![];	1✔
80	let leaf_data = match nodes.get(leaf_index) {	2✔
81	Some(MerkleNode::Leaf { data, .. }) => data,	1✔
82	_ => return None,	×
83	};
84	while let Some(sibling) = get_sibling(leaf_index) {	2✔
85	let side = if sibling == leaf_index + 1 {	3✔
86	crate::NodeSide::Left // side information is encoded relative to the node we're trying to prove is in the tree. The leaf is on the left of the current node	1✔
87	} else {
88	crate::NodeSide::Right	1✔
89	};
90	match nodes[sibling].get_hash() {	1✔
91	Some(hash) => proof_nodes.push(crate::LevelNode::new(*hash, side)),	2✔
92	_ => proof_nodes.push(crate::LevelNode::empty_node(side)),	2✔
93	}
94	leaf_index = get_parent(leaf_index)?;	2✔
95	}
96
97	Some(crate::MerkleProof::new(leaf_data, &proof_nodes))	2✔
98	}
99
100	fn build_multiproof(	2✔
101	nodes: &[MerkleNode],
102	leaf_indices: &[usize],
103	internal_nodes: usize,
104	) -> Option<BatchMerkleProof> {
105	let mut multiproof: Vec<crate::LevelNode> = vec![];	1✔
106
107	let mut a: BTreeSet<usize> = leaf_indices	3✔
108	.iter()
109	.map(\|idx\| idx + internal_nodes)	6✔
110	.collect();
111	// while a does not contain the root index (0)
112	while !a.contains(&0) {	5✔
113	let mut b_pruned = BTreeSet::new();	1✔
114	for node in &a {	3✔
115	// for each leaf node, insert it and it's neighbor into the set. Since we're inserting into a set, we don't need any deduplication or sorting
116	b_pruned.insert(*node);	1✔
117	b_pruned.insert(get_sibling(*node)?);	2✔
118	}
119
120	let diff = &b_pruned - &a;	1✔
121	for node in diff {	3✔
122	let side = match get_sibling(node) {	4✔
123	Some(s) if s == node - 1 => crate::NodeSide::Right,	4✔
UNCOV 124	Some(_) => crate::NodeSide::Left,	×
125	None => unreachable!(),
126	};
127	let levelnode = match nodes[node].get_hash() {	1✔
UNCOV 128	Some(hash) => crate::LevelNode::new(*hash, side),	×
129	None => crate::LevelNode::empty_node(side),	2✔
130	};
131	multiproof.push(levelnode);	3✔
132	}
133	a = b_pruned.into_iter().flat_map(get_parent).collect();	1✔
134	}
135
136	Some(BatchMerkleProof::new(	1✔
137	leaf_indices	2✔
138	.iter()
139	.flat_map(\|idx\| {	4✔
140	Some(BatchMerkleProofIndex {	1✔
141	index: *idx,	2✔
142	hash: nodes[idx + internal_nodes].get_hash().cloned()?,	1✔
143	})
144	})
145	.collect(),
146	multiproof,	2✔
147	))
148	}
149
150	/// Merkle Tree
151	#[derive(Debug)]
152	#[cfg_attr(feature = "json", derive(serde::Serialize))]
153	pub struct MerkleTree {
154	nodes: Vec<MerkleNode>,
155	elements_hash_index: HashMap<Digest32, usize>,
156	internal_nodes: usize,
157	}
158
159	impl MerkleTree {
160	/// Creates a new MerkleTree from leaf nodes
161	pub fn new(nodes: impl Into<Vec<MerkleNode>>) -> Self {	3✔
162	#[allow(clippy::unwrap_used)]
163	fn build_nodes(nodes: &mut [MerkleNode]) {	2✔
164	for pair in (1..nodes.len()).step_by(2).rev() {	7✔
165	let node = match (	6✔
166	nodes[pair].get_hash(),	6✔
167	nodes[get_sibling(pair).unwrap()].get_hash(), // since we pad nodes with no sibling with an empty node, get_sibling should always return Some	4✔
168	) {
169	(Some(left_hash), Some(right_hash)) => MerkleNode::Node {
170	hash: prefixed_hash2(	2✔
171	INTERNAL_PREFIX,
172	left_hash.as_ref(),
173	right_hash.as_ref(),
174	),
175	},
176	(Some(hash), None) => MerkleNode::Node {
177	hash: prefixed_hash(INTERNAL_PREFIX, hash.as_ref()),	3✔
178	},
179	(None, None) => MerkleNode::EmptyNode,	1✔
180	_ => unreachable!(),
181	};
182	nodes[get_parent(pair).unwrap()] = node;	3✔
183	}
184	}
185	let mut tree_nodes = nodes.into();	5✔
186	if tree_nodes.len() % 2 == 1 {	8✔
187	tree_nodes.push(MerkleNode::EmptyNode);	8✔
188	}
189	let elements_hash_index = tree_nodes	8✔
190	.iter()
191	.flat_map(MerkleNode::get_hash)	×
192	.enumerate()
193	.map(\|(i, node)\| (*node, i))	8✔
194	.collect();
195	let leaf_nodes = tree_nodes.len();	8✔
196	// prepend leaf nodes with empty nodes to build the full tree
197	tree_nodes.splice(	2✔
198	0..0,	×
199	std::iter::repeat_n(	4✔
200	MerkleNode::empty(),	2✔
201	tree_nodes.len().next_power_of_two() - 1,	6✔
202	),
203	);
204	build_nodes(&mut tree_nodes);	4✔
205	let nodes_len = tree_nodes.len();	3✔
206	Self {
207	nodes: tree_nodes,
208	elements_hash_index,
209	internal_nodes: nodes_len - leaf_nodes,	3✔
210	}
211	}
212
213	/// Returns the root hash for MerkleTree. If the tree is empty, then returns [0; 32]
214	pub fn root_hash(&self) -> Digest32 {	2✔
215	self.nodes	2✔
216	.first()
217	.and_then(MerkleNode::get_hash)
218	.cloned()
219	.unwrap_or_else(Digest32::zero)
220	}
221	/// Returns the root hash for MerkleTree. If the tree is empty, then returns a special hash '0e5751c026e543b2e8ab2eb06099daa1d1e5df47778f7787faab45cdf12fe3a8', which is extension/transaction root hash for genesis block
222	/// See: <https://github.com/ergoplatform/ergo/issues/1077>
223	pub fn root_hash_special(&self) -> Digest32 {	2✔
224	self.nodes	2✔
225	.first()
226	.and_then(MerkleNode::get_hash)
227	.cloned()
228	.unwrap_or_else(\|\| {	2✔
229	let hash = blake2b256_hash(&[]);	2✔
230	Digest32::from(hash)	2✔
231	})
232	}
233
234	/// Returns HashMap of hashes and their index in the tree
235	pub fn get_elements_hash_index(&self) -> &HashMap<Digest32, usize> {	1✔
236	&self.elements_hash_index	1✔
237	}
238
239	/// Builds a [`crate::MerkleProof`] for leaf_index. Returns None if index does not exist
240	pub fn proof_by_index(&self, leaf_index: usize) -> Option<crate::MerkleProof> {	1✔
241	build_proof(&self.nodes, leaf_index, self.internal_nodes)	1✔
242	}
243	/// Builds a [`crate::MerkleProof`] for given hash. Returns None if hash is not a leaf of tree
244	pub fn proof_by_element_hash(&self, hash: &Digest32) -> Option<crate::MerkleProof> {	1✔
245	let index = *self.elements_hash_index.get(hash)?;	1✔
246	self.proof_by_index(index)	1✔
247	}
248	/// Builds a [`crate::MerkleProof`] for element, by searching for its hash in the tree
249	pub fn proof_by_element(&self, data: &[u8]) -> Option<crate::MerkleProof> {	1✔
250	let hash = prefixed_hash(LEAF_PREFIX, data);	1✔
251	self.proof_by_element_hash(&hash)	1✔
252	}
253
254	/// Builds a [`crate::BatchMerkleProof`] for given indices
255	pub fn proof_by_indices(	2✔
256	&self,
257	leaf_indices: &[usize],
258	) -> Option<crate::batchmerkleproof::BatchMerkleProof> {
259	let mut leaf_indices = leaf_indices.to_owned();	3✔
260	leaf_indices.sort_unstable();	4✔
261	leaf_indices.dedup();	2✔
262	// check that node index is in bounds, a leaf node, and not an empty node
263	if leaf_indices.is_empty()	3✔
264	\|\| leaf_indices.iter().any(\|i\| {	7✔
265	self.nodes	6✔
266	.get(self.internal_nodes + *i)	4✔
267	.and_then(MerkleNode::get_leaf_data)
268	.is_none()
269	})
270	{
271	return None;	1✔
272	}
273
274	build_multiproof(&self.nodes, &leaf_indices, self.internal_nodes)	1✔
275	}
276	}
277
278	#[cfg(test)]
279	#[allow(clippy::unwrap_used, clippy::panic)]
280	mod test {
281	use crate::{prefixed_hash, prefixed_hash2, MerkleNode, MerkleTree};
282
283	#[test]
284	fn merkle_tree_zero_elements() {
285	let tree = MerkleTree::new(&[][..]);
286	assert!(tree.root_hash().as_ref() == [0; 32]);
287	}
288	#[test]
289	fn merkle_tree_test_one_element() {
290	// Here the merkle tree looks as follows:
291	// I
292	// / \
293	// L E
294	// Where `I`, `L`, and `E` denote the root internal node, leaf node, and empty node,
295	// respectively.
296
297	let data = [1; 32];
298	let node = MerkleNode::from_bytes(data);
299	let tree = MerkleTree::new(&[node][..]);
300	assert_eq!(
301	tree.root_hash(),
302	prefixed_hash(1, prefixed_hash(0, &data).as_ref())
303	);
304	}
305	#[test]
306	fn merkle_tree_test_five_elements() {
307	let bytes = [1u8; 32];
308	let nodes = vec![MerkleNode::from_bytes(bytes); 5];
309	let tree = MerkleTree::new(&*nodes);
310	let h0x = prefixed_hash(0, &bytes);
311	let h10 = prefixed_hash2(1, h0x.as_ref(), h0x.as_ref());
312	let h11 = &h10;
313	let h12 = prefixed_hash(1, h0x.0.as_ref());
314	let h20 = prefixed_hash2(1, h10.as_ref(), h11.as_ref());
315	let h21 = prefixed_hash(1, h12.as_ref());
316	let h30 = prefixed_hash2(1, h20.as_ref(), h21.as_ref());
317	assert_eq!(tree.root_hash(), h30);
318	}
319
320	#[test]
321	fn merkle_tree_test_merkleproof() {
322	let nodes = [
323	MerkleNode::from_bytes([1; 32]),
324	MerkleNode::from_bytes([2; 32]),
325	MerkleNode::from_bytes([3; 32]),
326	MerkleNode::from_bytes([4; 32]),
327	MerkleNode::from_bytes([5; 32]),
328	];
329	let tree = MerkleTree::new(&nodes[..]);
330	let tree_root = tree.root_hash();
331	for (i, node) in nodes.iter().enumerate() {
332	assert_eq!(
333	tree.proof_by_index(i).unwrap().get_leaf_data(),
334	node.get_leaf_data().unwrap()
335	);
336	assert!(tree.proof_by_index(i).unwrap().valid(tree_root.as_ref()));
337	assert!(tree
338	.proof_by_element(node.get_leaf_data().unwrap())
339	.unwrap()
340	.valid(tree_root.as_ref()));
341	assert!(tree
342	.proof_by_element_hash(node.get_hash().unwrap())
343	.unwrap()
344	.valid(tree_root.as_ref()));
345	}
346	}
347	}
348
349	#[cfg(feature = "arbitrary")]
350	#[cfg(test)]
351	#[allow(clippy::unwrap_used)]
352	mod arbitrary {
353	use crate::{MerkleNode, MerkleTree};
354	use proptest::array::uniform32;
355	use proptest::collection::vec;
356	use proptest::prelude::*;
357	proptest! {
358	#[test]
359	fn merkle_tree_test_arbitrary_proof(data in vec(uniform32(0u8..), 0..100)) {
360	let nodes: Vec<MerkleNode> = data.into_iter().map(MerkleNode::from_bytes).collect();
361	let tree = MerkleTree::new(&*nodes);
362	for (i, node) in nodes.iter().enumerate() {
363	let proof = tree.proof_by_index(i).unwrap();
364	assert_eq!(
365	proof.get_leaf_data(),
366	node.get_leaf_data().unwrap()
367	);
368	assert!(proof.valid(tree.root_hash().as_ref()));
369	}
370	}
371	#[test]
372	fn merkle_tree_test_arbitrary_batch_proof(data in vec(uniform32(0u8..), 0..1000), indices in vec(0..1000usize, 0..1000)) {
373	let valid = indices.iter().all(\|i\| *i < data.len()) && !indices.is_empty(); // TODO, is there any better strategy for proptest that doesn't require us to filter out invalid indices
374	let nodes: Vec<MerkleNode> = data.into_iter().map(MerkleNode::from_bytes).collect();
375	let tree = MerkleTree::new(&*nodes);
376	if valid {
377	assert!(tree.proof_by_indices(&indices).unwrap().valid(tree.root_hash().as_ref()));
378	}
379	else {
380	assert!(tree.proof_by_indices(&indices).is_none());
381	}
382	}
383	}
384	}

ergoplatform / sigma-rust / 15698235808

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous