cs_mwc_bch/messages/
merkle_block.rs

1use byteorder::{LittleEndian, ReadBytesExt, WriteBytesExt};
2use hex;
3use messages::block_header::BlockHeader;
4use messages::message::Payload;
5use std::fmt;
6use std::io;
7use std::io::{Read, Write};
8use util::{sha256d, var_int, Error, Hash256, Result, Serializable};
9
10/// A block header and partial merkle tree for SPV nodes to validate transactions
11#[derive(Default, PartialEq, Eq, Hash, Clone)]
12pub struct MerkleBlock {
13    /// Block header
14    pub header: BlockHeader,
15    /// Number of transactions in the block
16    pub total_transactions: u32,
17    /// Hashes in depth-first order
18    pub hashes: Vec<Hash256>,
19    /// Bit vector used to assign hashes to nodes in the partial merkle tree
20    pub flags: Vec<u8>,
21}
22
23impl MerkleBlock {
24    /// Validates the merkle block and partial merkle tree and returns the set of matched transactions
25    pub fn validate(&self) -> Result<Vec<Hash256>> {
26        if self.total_transactions == 0 {
27            return Err(Error::BadData("No transactions".to_string()));
28        }
29
30        let mut preorder_node = 0;
31        let mut flag_bits_used = 0;
32        let mut hashes_used = 0;
33        let mut matches = Vec::new();
34        let tree_depth = (self.total_transactions as f32).log(2.).ceil() as usize;
35        let mut row_len = self.total_transactions as usize;
36        let mut total_nodes = row_len as usize;
37        while row_len > 1 {
38            row_len = (row_len + 1) / 2;
39            total_nodes += row_len;
40        }
41
42        let merkle_root = self.traverse(
43            &mut preorder_node,
44            &mut flag_bits_used,
45            &mut hashes_used,
46            0,
47            tree_depth,
48            total_nodes,
49            &mut matches,
50        )?;
51
52        if merkle_root != self.header.merkle_root {
53            return Err(Error::BadData("Merkle root doesn't match".to_string()));
54        }
55
56        if hashes_used < self.hashes.len() {
57            return Err(Error::BadData("Not all hashes consumed".to_string()));
58        }
59
60        if preorder_node < total_nodes {
61            return Err(Error::BadData("Not all nodes consumed".to_string()));
62        }
63
64        if (flag_bits_used + 7) / 8 < self.flags.len() {
65            return Err(Error::BadData("Not all flag bits consumed".to_string()));
66        }
67
68        Ok(matches)
69    }
70
71    fn traverse(
72        &self,
73        preorder_node: &mut usize,
74        flag_bits_used: &mut usize,
75        hashes_used: &mut usize,
76        depth: usize,
77        tree_depth: usize,
78        total_nodes: usize,
79        matches: &mut Vec<Hash256>,
80    ) -> Result<Hash256> {
81        let flag = self.consume_flag(flag_bits_used)?;
82        if flag == 0 {
83            *preorder_node += (1 << (tree_depth - depth + 1)) - 1;
84            let hash = self.consume_hash(hashes_used)?;
85            Ok(hash)
86        } else if depth == tree_depth {
87            *preorder_node += 1;
88            let hash = self.consume_hash(hashes_used)?;
89            matches.push(hash.clone());
90            Ok(hash)
91        } else {
92            *preorder_node += 1;
93            let left = self.traverse(
94                preorder_node,
95                flag_bits_used,
96                hashes_used,
97                depth + 1,
98                tree_depth,
99                total_nodes,
100                matches,
101            )?;
102            if *preorder_node >= total_nodes {
103                let mut concat = Vec::with_capacity(64);
104                concat.extend_from_slice(&left.0);
105                concat.extend_from_slice(&left.0);
106                Ok(sha256d(&concat))
107            } else {
108                let right = self.traverse(
109                    preorder_node,
110                    flag_bits_used,
111                    hashes_used,
112                    depth + 1,
113                    tree_depth,
114                    total_nodes,
115                    matches,
116                )?;
117                if left == right {
118                    return Err(Error::BadData("Duplicate transactions".to_string()));
119                } else {
120                    let mut concat = Vec::with_capacity(64);
121                    concat.extend_from_slice(&left.0);
122                    concat.extend_from_slice(&right.0);
123                    Ok(sha256d(&concat))
124                }
125            }
126        }
127    }
128
129    fn consume_flag(&self, flag_bits_used: &mut usize) -> Result<u8> {
130        if *flag_bits_used / 8 >= self.flags.len() {
131            return Err(Error::BadData("Not enough flag bits".to_string()));
132        }
133        let flag = (self.flags[*flag_bits_used / 8] >> *flag_bits_used % 8) & 1;
134        *flag_bits_used += 1;
135        Ok(flag)
136    }
137
138    fn consume_hash(&self, hashes_used: &mut usize) -> Result<Hash256> {
139        if *hashes_used >= self.hashes.len() {
140            return Err(Error::BadData("Not enough hashes".to_string()));
141        }
142        let hash = self.hashes[*hashes_used];
143        *hashes_used += 1;
144        Ok(hash)
145    }
146}
147
148impl Serializable<MerkleBlock> for MerkleBlock {
149    fn read(reader: &mut dyn Read) -> Result<MerkleBlock> {
150        let header = BlockHeader::read(reader)?;
151        let total_transactions = reader.read_u32::<LittleEndian>()?;
152        let num_hashes = var_int::read(reader)?;
153        let mut hashes = Vec::with_capacity(num_hashes as usize);
154        for _i in 0..num_hashes {
155            hashes.push(Hash256::read(reader)?);
156        }
157        let flags_len = var_int::read(reader)?;
158        let mut flags = vec![0; flags_len as usize];
159        reader.read(&mut flags)?;
160        Ok(MerkleBlock {
161            header,
162            total_transactions,
163            hashes,
164            flags,
165        })
166    }
167
168    fn write(&self, writer: &mut dyn Write) -> io::Result<()> {
169        self.header.write(writer)?;
170        writer.write_u32::<LittleEndian>(self.total_transactions)?;
171        var_int::write(self.hashes.len() as u64, writer)?;
172        for hash in self.hashes.iter() {
173            hash.write(writer)?;
174        }
175        var_int::write(self.flags.len() as u64, writer)?;
176        writer.write(&self.flags)?;
177        Ok(())
178    }
179}
180
181impl Payload<MerkleBlock> for MerkleBlock {
182    fn size(&self) -> usize {
183        self.header.size()
184            + 4
185            + var_int::size(self.hashes.len() as u64)
186            + self.hashes.len() * 32
187            + var_int::size(self.flags.len() as u64)
188            + self.flags.len()
189    }
190}
191
192impl fmt::Debug for MerkleBlock {
193    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
194        f.debug_struct("MerkleBlock")
195            .field("header", &self.header)
196            .field("total_transactions", &self.total_transactions)
197            .field("hashes", &self.hashes)
198            .field("flags", &hex::encode(&self.flags))
199            .finish()
200    }
201}
202
203#[cfg(test)]
204mod tests {
205    use super::*;
206    use hex;
207    use std::io::Cursor;
208
209    #[test]
210    fn read_bytes() {
211        let b = hex::decode("0100000082bb869cf3a793432a66e826e05a6fc37469f8efb7421dc880670100000000007f16c5962e8bd963659c793ce370d95f093bc7e367117b3c30c1f8fdd0d9728776381b4d4c86041b554b852907000000043612262624047ee87660be1a707519a443b1c1ce3d248cbfc6c15870f6c5daa2019f5b01d4195ecbc9398fbf3c3b1fa9bb3183301d7a1fb3bd174fcfa40a2b6541ed70551dd7e841883ab8f0b16bf04176b7d1480e4f0af9f3d4c3595768d06820d2a7bc994987302e5b1ac80fc425fe25f8b63169ea78e68fbaaefa59379bbf011d".as_bytes()).unwrap();
212        let p = MerkleBlock::read(&mut Cursor::new(&b)).unwrap();
213        assert!(p.header.version == 1);
214        let prev_hash = "82bb869cf3a793432a66e826e05a6fc37469f8efb7421dc88067010000000000";
215        assert!(p.header.prev_hash.0.to_vec() == hex::decode(prev_hash).unwrap());
216        let merkle_root = "7f16c5962e8bd963659c793ce370d95f093bc7e367117b3c30c1f8fdd0d97287";
217        assert!(p.header.merkle_root.0.to_vec() == hex::decode(merkle_root).unwrap());
218        assert!(p.header.timestamp == 1293629558);
219        assert!(p.total_transactions == 7);
220        assert!(p.hashes.len() == 4);
221        let hash1 = "3612262624047ee87660be1a707519a443b1c1ce3d248cbfc6c15870f6c5daa2";
222        assert!(p.hashes[0].0.to_vec() == hex::decode(hash1).unwrap());
223        let hash2 = "019f5b01d4195ecbc9398fbf3c3b1fa9bb3183301d7a1fb3bd174fcfa40a2b65";
224        assert!(p.hashes[1].0.to_vec() == hex::decode(hash2).unwrap());
225        let hash3 = "41ed70551dd7e841883ab8f0b16bf04176b7d1480e4f0af9f3d4c3595768d068";
226        assert!(p.hashes[2].0.to_vec() == hex::decode(hash3).unwrap());
227        let hash4 = "20d2a7bc994987302e5b1ac80fc425fe25f8b63169ea78e68fbaaefa59379bbf";
228        assert!(p.hashes[3].0.to_vec() == hex::decode(hash4).unwrap());
229        assert!(p.flags.len() == 1 && p.flags[0] == 29);
230    }
231
232    #[test]
233    fn write_read() {
234        let mut v = Vec::new();
235        let p = MerkleBlock {
236            header: BlockHeader {
237                version: 12345,
238                prev_hash: Hash256::decode(
239                    "7766009988776600998877660099887766009988776600998877660099887766",
240                ).unwrap(),
241                merkle_root: Hash256::decode(
242                    "2211554433221155443322115544332211554433221155443322115544332211",
243                ).unwrap(),
244                timestamp: 66,
245                bits: 4488,
246                nonce: 9999,
247            },
248            total_transactions: 14,
249            hashes: vec![Hash256([1; 32]), Hash256([3; 32]), Hash256([5; 32])],
250            flags: vec![24, 125, 199],
251        };
252        p.write(&mut v).unwrap();
253        assert!(v.len() == p.size());
254        assert!(MerkleBlock::read(&mut Cursor::new(&v)).unwrap() == p);
255    }
256
257    #[test]
258    fn validate() {
259        // Valid merkle block with 7 transactions
260        let b = hex::decode("0100000082bb869cf3a793432a66e826e05a6fc37469f8efb7421dc880670100000000007f16c5962e8bd963659c793ce370d95f093bc7e367117b3c30c1f8fdd0d9728776381b4d4c86041b554b852907000000043612262624047ee87660be1a707519a443b1c1ce3d248cbfc6c15870f6c5daa2019f5b01d4195ecbc9398fbf3c3b1fa9bb3183301d7a1fb3bd174fcfa40a2b6541ed70551dd7e841883ab8f0b16bf04176b7d1480e4f0af9f3d4c3595768d06820d2a7bc994987302e5b1ac80fc425fe25f8b63169ea78e68fbaaefa59379bbf011d".as_bytes()).unwrap();
261        let p = MerkleBlock::read(&mut Cursor::new(&b)).unwrap();
262        assert!(p.validate().unwrap().len() == 1);
263
264        // Not enough hashes
265        let mut p2 = p.clone();
266        p2.hashes.truncate(p.hashes.len() - 1);
267        assert!(p2.validate().is_err());
268
269        // Too many hashes
270        let mut p2 = p.clone();
271        p2.hashes.push(Hash256([0; 32]));
272        assert!(p2.validate().is_err());
273
274        // Not enough flags
275        let mut p2 = p.clone();
276        p2.flags = vec![];
277        assert!(p2.validate().is_err());
278
279        // Too many flags
280        let mut p2 = p.clone();
281        p2.flags.push(0);
282        assert!(p2.validate().is_err());
283
284        // Merkle root doesn't match
285        let mut p2 = p.clone();
286        p2.hashes[0] = Hash256([1; 32]);
287        assert!(p2.validate().is_err());
288    }
289
290    #[test]
291    fn incomplete_tree() {
292        let hash1 = Hash256([1; 32]);
293        let hash2 = Hash256([2; 32]);
294        let hash3 = Hash256([3; 32]);
295        let hash4 = Hash256([4; 32]);
296        let right = hash(&hash(&hash2, &hash3), &hash4);
297        let merkle_root = hash(&hash1, &hash(&right, &right));
298        let header = BlockHeader {
299            version: 12345,
300            prev_hash: Hash256([0; 32]),
301            merkle_root,
302            timestamp: 66,
303            bits: 4488,
304            nonce: 9999,
305        };
306        let merkle_block = MerkleBlock {
307            header,
308            total_transactions: 11,
309            hashes: vec![hash1, hash2, hash3, hash4],
310            flags: vec![0x5d],
311        };
312        assert!(merkle_block.validate().is_ok());
313    }
314
315    fn hash(a: &Hash256, b: &Hash256) -> Hash256 {
316        let mut v = Vec::with_capacity(64);
317        v.write(&a.0).unwrap();
318        v.write(&b.0).unwrap();
319        sha256d(&v)
320    }
321}
cs_mwc_bch/messages/merkle_block.rs

cs_mwc_bch/messages/
merkle_block.rs
