mithril_common/entities/
cardano_transactions_set_proof.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
use crate::crypto_helper::{MKMapProof, ProtocolMkProof};
use crate::entities::TransactionHash;
use crate::StdResult;

use super::BlockRange;

cfg_test_tools! {
    use crate::crypto_helper::{MKMap, MKTree, MKTreeNode, MKMapNode, MKTreeStorer, MKTreeStoreInMemory};
    use crate::entities::BlockNumber;
    use std::collections::HashMap;
}

/// A cryptographic proof of a set of Cardano transactions is included in the global Cardano transactions set
#[derive(Clone, Debug, PartialEq)]
pub struct CardanoTransactionsSetProof {
    /// Hashes of the certified transactions
    pub(crate) transactions_hashes: Vec<TransactionHash>,

    /// Proof of the transactions
    pub(crate) transactions_proof: ProtocolMkProof,
}

impl CardanoTransactionsSetProof {
    /// CardanoTransactionsSetProof factory
    pub fn new<T: Into<MKMapProof<BlockRange>>>(
        transactions_hashes: Vec<TransactionHash>,
        transactions_proof: T,
    ) -> Self {
        Self {
            transactions_hashes,
            transactions_proof: ProtocolMkProof::new(transactions_proof.into()),
        }
    }

    /// Return the hex encoded merkle root of this proof
    pub fn merkle_root(&self) -> String {
        self.transactions_proof.compute_root().to_hex()
    }

    /// Get the hashes of the transactions certified by this proof
    pub fn transactions_hashes(&self) -> &[TransactionHash] {
        &self.transactions_hashes
    }

    /// Verify that transactions set proof is valid
    pub fn verify(&self) -> StdResult<()> {
        self.transactions_proof.verify()?;
        for hash in &self.transactions_hashes {
            self.transactions_proof.contains(&hash.to_owned().into())?;
        }

        Ok(())
    }

    cfg_test_tools! {
        /// Retrieve a dummy proof (for test only)
        pub fn dummy() -> Self {
            let leaves = vec![
                (BlockNumber(0), "tx-1".to_string()),
                (BlockNumber(1), "tx-2".to_string()),
                (BlockNumber(1), "tx-3".to_string()),
                (BlockNumber(10), "tx-4".to_string()),
                (BlockNumber(20), "tx-5".to_string()),
                (BlockNumber(22), "tx-6".to_string()),
            ];

            Self::from_leaves::<MKTreeStoreInMemory>(&leaves).unwrap()
        }

        /// Helper to create a proof from a list of leaves
        pub fn from_leaves<S: MKTreeStorer>(leaves: &[(BlockNumber, TransactionHash)]) -> StdResult<Self> {
            let transactions_hashes: Vec<TransactionHash> =
                leaves.iter().map(|(_, t)| t.into()).collect();
            let mut transactions_by_block_ranges: HashMap<BlockRange, Vec<TransactionHash>> =
                HashMap::new();
            for (block_number, transaction_hash) in leaves {
                let block_range = BlockRange::from_block_number(*block_number);
                transactions_by_block_ranges
                    .entry(block_range)
                    .or_default()
                    .push(transaction_hash.to_owned());
            }
            let mk_map = MKMap::<_, _, MKTreeStoreInMemory>::new(
                transactions_by_block_ranges
                    .into_iter()
                    .try_fold(
                        vec![],
                        |mut acc, (block_range, transactions)| -> StdResult<Vec<(_, MKMapNode<_,S>)>> {
                            acc.push((block_range, MKTree::<S>::new(&transactions)?.into()));
                            Ok(acc)
                        },
                    )?
                    .as_slice(),
            )?;
            let mk_leaves: Vec<MKTreeNode> = transactions_hashes
                .iter()
                .map(|h| h.to_owned().into())
                .collect();
            let mk_proof = mk_map.compute_proof(&mk_leaves)?;
            Ok(Self::new(transactions_hashes, mk_proof))
        }

    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn should_verify_where_all_hashes_are_contained_in_the_proof() {
        let leaves = vec![
            (BlockNumber(0), "tx-1".to_string()),
            (BlockNumber(1), "tx-2".to_string()),
            (BlockNumber(1), "tx-3".to_string()),
            (BlockNumber(10), "tx-4".to_string()),
            (BlockNumber(20), "tx-5".to_string()),
            (BlockNumber(22), "tx-6".to_string()),
        ];
        let proof =
            CardanoTransactionsSetProof::from_leaves::<MKTreeStoreInMemory>(&leaves).unwrap();

        proof.verify().expect("The proof should be valid");
    }

    #[test]
    fn shouldnt_verify_where_at_least_one_hash_is_not_contained_in_the_proof() {
        let leaves = vec![
            (BlockNumber(0), "tx-1".to_string()),
            (BlockNumber(1), "tx-2".to_string()),
            (BlockNumber(1), "tx-3".to_string()),
            (BlockNumber(10), "tx-4".to_string()),
            (BlockNumber(20), "tx-5".to_string()),
            (BlockNumber(22), "tx-6".to_string()),
        ];
        let proof =
            CardanoTransactionsSetProof::from_leaves::<MKTreeStoreInMemory>(&leaves).unwrap();
        let mut transactions_hashes_tampered = proof.transactions_hashes().to_vec();
        transactions_hashes_tampered.push("tx-123".to_string());
        let proof = CardanoTransactionsSetProof {
            transactions_hashes: transactions_hashes_tampered,
            ..proof
        };

        proof.verify().expect_err("The proof should be invalid");
    }
}