hypercore/tree/
merkle_tree_changeset.rs

1use ed25519_dalek::{Signature, SigningKey, VerifyingKey};
2use std::convert::TryFrom;
3
4use crate::{
5    crypto::{signable_tree, verify, Hash},
6    sign, HypercoreError, Node,
7};
8
9/// Changeset for a `MerkleTree`. This allows to incrementally change a `MerkleTree` in two steps:
10/// first create the changes to this changeset, get out information from this to put to the oplog,
11/// and the commit the changeset to the tree.
12///
13/// This is called "MerkleTreeBatch" in Javascript, source
14/// [here](https://github.com/holepunchto/hypercore/blob/88a1a2f1ebe6e33102688225516c4e882873f710/lib/merkle-tree.js#L44).
15#[derive(Debug)]
16pub(crate) struct MerkleTreeChangeset {
17    pub(crate) length: u64,
18    pub(crate) ancestors: u64,
19    pub(crate) byte_length: u64,
20    pub(crate) batch_length: u64,
21    pub(crate) fork: u64,
22    pub(crate) roots: Vec<Node>,
23    pub(crate) nodes: Vec<Node>,
24    pub(crate) hash: Option<Box<[u8]>>,
25    pub(crate) signature: Option<Signature>,
26    pub(crate) upgraded: bool,
27
28    // Safeguarding values
29    pub(crate) original_tree_length: u64,
30    pub(crate) original_tree_fork: u64,
31}
32
33impl MerkleTreeChangeset {
34    pub(crate) fn new(
35        length: u64,
36        byte_length: u64,
37        fork: u64,
38        roots: Vec<Node>,
39    ) -> MerkleTreeChangeset {
40        Self {
41            length,
42            ancestors: length,
43            byte_length,
44            batch_length: 0,
45            fork,
46            roots,
47            nodes: vec![],
48            hash: None,
49            signature: None,
50            upgraded: false,
51            original_tree_length: length,
52            original_tree_fork: fork,
53        }
54    }
55
56    pub(crate) fn append(&mut self, data: &[u8]) -> usize {
57        let len = data.len();
58        let head = self.length * 2;
59        let mut iter = flat_tree::Iterator::new(head);
60        let node = Node::new(head, Hash::data(data).as_bytes().to_vec(), len as u64);
61        self.append_root(node, &mut iter);
62        self.batch_length += 1;
63        len
64    }
65
66    pub(crate) fn append_root(&mut self, node: Node, iter: &mut flat_tree::Iterator) {
67        self.upgraded = true;
68        self.length += iter.factor() / 2;
69        self.byte_length += node.length;
70        self.roots.push(node.clone());
71        self.nodes.push(node);
72
73        while self.roots.len() > 1 {
74            let a = &self.roots[self.roots.len() - 1];
75            let b = &self.roots[self.roots.len() - 2];
76            if iter.sibling() != b.index {
77                iter.sibling(); // unset so it always points to last root
78                break;
79            }
80
81            let node = Node::new(
82                iter.parent(),
83                Hash::parent(a, b).as_bytes().into(),
84                a.length + b.length,
85            );
86            let _ = &self.nodes.push(node.clone());
87            let _ = &self.roots.pop();
88            let _ = &self.roots.pop();
89            let _ = &self.roots.push(node);
90        }
91    }
92
93    /// Hashes and signs the changeset
94    pub(crate) fn hash_and_sign(&mut self, signing_key: &SigningKey) {
95        let hash = self.hash();
96        let signable = self.signable(&hash);
97        let signature = sign(signing_key, &signable);
98        self.hash = Some(hash);
99        self.signature = Some(signature);
100    }
101
102    /// Verify and set signature with given public key
103    pub(crate) fn verify_and_set_signature(
104        &mut self,
105        signature: &[u8],
106        public_key: &VerifyingKey,
107    ) -> Result<(), HypercoreError> {
108        // Verify that the received signature matches the public key
109        let signature =
110            Signature::try_from(signature).map_err(|_| HypercoreError::InvalidSignature {
111                context: "Could not parse signature".to_string(),
112            })?;
113        let hash = self.hash();
114        verify(public_key, &self.signable(&hash), Some(&signature))?;
115
116        // Set values to changeset
117        self.hash = Some(hash);
118        self.signature = Some(signature);
119        Ok(())
120    }
121
122    /// Calculates a hash of the current set of roots
123    pub(crate) fn hash(&self) -> Box<[u8]> {
124        Hash::tree(&self.roots).as_bytes().into()
125    }
126
127    /// Creates a signable slice from given hash
128    pub(crate) fn signable(&self, hash: &[u8]) -> Box<[u8]> {
129        signable_tree(hash, self.length, self.fork)
130    }
131}
hypercore/tree/merkle_tree_changeset.rs

hypercore/tree/
merkle_tree_changeset.rs
