mithril_common/entities/
mk_set_proof.rs

1use crate::StdResult;
2use crate::crypto_helper::{MKMapProof, MKTreeNode, ProtocolMkProof};
3use crate::entities::{
4    BlockHash, BlockRange, CardanoBlock, CardanoBlockTransactionMkTreeNode, CardanoTransaction,
5    TransactionHash,
6};
7
8/// Trait to convert a type into a [MKTreeNode]
9///
10/// Note: this trait exists only to allow `CardanoTransaction` to have a second, different, conversion
11/// to [MKTreeNode] without changing its `Into<MKTreeNode>` implementation.
12/// The `Into<MKTreeNode>` implementation cover proof generation and certification for `CardanoTransactions`
13/// signed entity, this trait implementation cover the same operation for `CardanoBlocksTransactions`
14/// signed entity.
15///
16/// Todo: after `CardanoTransactions` signed entity removal, remove this trait and use `Into<MKTreeNode>` instead.
17pub trait IntoMKTreeNode {
18    /// Converts the item into a [MKTreeNode]
19    fn into_mk_tree_node(self) -> MKTreeNode;
20}
21
22/// A cryptographic proof of that a set of items is included in a Merkle tree
23#[derive(Clone, Debug, PartialEq)]
24pub struct MkSetProof<T: IntoMKTreeNode + Clone> {
25    /// Certified items list
26    pub(crate) items: Vec<T>,
27
28    /// Proof of inclusion of the certified items
29    pub(crate) proof: ProtocolMkProof,
30}
31
32impl<T: IntoMKTreeNode + Clone> MkSetProof<T> {
33    /// MkSetProof factory
34    pub fn new<P: Into<MKMapProof<BlockRange>>>(items: Vec<T>, proof: P) -> Self {
35        Self {
36            items,
37            proof: ProtocolMkProof::new(proof.into()),
38        }
39    }
40
41    /// Return the hex encoded merkle root of this proof
42    pub fn merkle_root(&self) -> String {
43        self.proof.compute_root().to_hex()
44    }
45
46    /// Verify that proof includes all items of the set
47    pub fn verify(&self) -> StdResult<()> {
48        self.proof.verify()?;
49        for node in self.items.iter().cloned().map(IntoMKTreeNode::into_mk_tree_node) {
50            self.proof.contains(&node)?;
51        }
52
53        Ok(())
54    }
55}
56
57impl IntoMKTreeNode for CardanoBlock {
58    fn into_mk_tree_node(self) -> MKTreeNode {
59        let node: CardanoBlockTransactionMkTreeNode = self.into();
60        node.into()
61    }
62}
63
64impl MkSetProof<CardanoBlock> {
65    /// Get the blocks certified by this proof
66    pub fn blocks(&self) -> &[CardanoBlock] {
67        &self.items
68    }
69
70    /// Get the hashes of the blocks certified by this proof
71    pub fn blocks_hashes(&self) -> impl Iterator<Item = &BlockHash> + '_ {
72        self.items.iter().map(|b| &b.block_hash)
73    }
74}
75
76impl IntoMKTreeNode for CardanoTransaction {
77    fn into_mk_tree_node(self) -> MKTreeNode {
78        let node: CardanoBlockTransactionMkTreeNode = self.into();
79        node.into()
80    }
81}
82
83impl MkSetProof<CardanoTransaction> {
84    /// Get the transactions certified by this proof
85    pub fn transactions(&self) -> &[CardanoTransaction] {
86        &self.items
87    }
88
89    /// Get the hashes of the transactions certified by this proof
90    pub fn transactions_hashes(&self) -> impl Iterator<Item = &TransactionHash> + '_ {
91        self.items.iter().map(|t| &t.transaction_hash)
92    }
93}
94
95#[cfg(test)]
96mod tests {
97    use crate::crypto_helper::{MKMap, MKMapNode, MKTree, MKTreeStoreInMemory};
98    use crate::test::entities_extensions::BlockRangeTestExtension;
99
100    use super::*;
101
102    impl IntoMKTreeNode for &str {
103        fn into_mk_tree_node(self) -> MKTreeNode {
104            MKTreeNode::new(self.as_bytes().to_vec())
105        }
106    }
107
108    fn tamper<T: Clone>(item: &T, f: fn(&mut T)) -> T {
109        let mut item = item.clone();
110        f(&mut item);
111        item
112    }
113
114    fn mk_proof_for(items: &[&str]) -> MKMapProof<BlockRange> {
115        let mk_map: MKMap<_, MKMapNode<BlockRange, MKTreeStoreInMemory>, MKTreeStoreInMemory> =
116            MKMap::new(&[(BlockRange::new(0, 100), MKTree::new(items).unwrap().into())]).unwrap();
117        mk_map.compute_proof(items).unwrap()
118    }
119
120    #[test]
121    fn should_verify_where_all_items_are_contained_in_the_proof() {
122        let leaves = vec!["leaf-1", "leaf-2", "leaf-3", "leaf-4", "leaf-5", "leaf-6"];
123        let mk_map_proof = mk_proof_for(&leaves);
124
125        let proof = MkSetProof::new(leaves, mk_map_proof);
126
127        proof.verify().expect("The proof should be valid");
128    }
129
130    #[test]
131    fn should_not_verify_where_at_least_one_item_is_not_contained_in_the_proof() {
132        let proved_leaves = vec!["leaf-1", "leaf-2", "leaf-3", "leaf-4", "leaf-5", "leaf-6"];
133        let mk_map_proof = mk_proof_for(&proved_leaves);
134        let tampered_leaves = tamper(&proved_leaves, |l| l.push("tampered-leaf"));
135
136        let proof = MkSetProof::new(tampered_leaves, mk_map_proof);
137
138        proof.verify().expect_err("The proof should be invalid");
139    }
140}
mithril_common/entities/mk_set_proof.rs

mithril_common/entities/
mk_set_proof.rs
