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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170

use crate::crypto_helper::{MKMapProof, ProtocolMkProof};
use crate::entities::TransactionHash;
use crate::messages::CardanoTransactionsSetProofMessagePart;
use crate::{StdError, 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
    transactions_hashes: Vec<TransactionHash>,

    /// Proof of the transactions
    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))
        }

    }
}

impl TryFrom<CardanoTransactionsSetProof> for CardanoTransactionsSetProofMessagePart {
    type Error = StdError;

    fn try_from(proof: CardanoTransactionsSetProof) -> Result<Self, Self::Error> {
        Ok(Self {
            transactions_hashes: proof.transactions_hashes,
            proof: proof.transactions_proof.to_json_hex()?,
        })
    }
}

impl TryFrom<CardanoTransactionsSetProofMessagePart> for CardanoTransactionsSetProof {
    type Error = StdError;

    fn try_from(proof: CardanoTransactionsSetProofMessagePart) -> Result<Self, Self::Error> {
        Ok(Self {
            transactions_hashes: proof.transactions_hashes,
            transactions_proof: ProtocolMkProof::from_json_hex(&proof.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");
    }
}