cfx_storage/impls/merkle_patricia_trie/
merkle.rs

1// Copyright 2019 Conflux Foundation. All rights reserved.
2// Conflux is free software and distributed under GNU General Public License.
3// See http://www.gnu.org/licenses/
4
5pub type ChildrenMerkleTable = [MerkleHash; CHILDREN_COUNT];
6pub type MaybeMerkleTable = Option<ChildrenMerkleTable>;
7pub type MaybeMerkleTableRef<'a> = Option<&'a ChildrenMerkleTable>;
8
9const LEAF_CHILDREN_MERKLE: [MerkleHash; CHILDREN_COUNT] =
10    [MERKLE_NULL_NODE; CHILDREN_COUNT];
11
12/// Node merkle for a subtree is defined as keccak(buffer), where buffer
13/// contains the relevant trie node representation.
14///
15/// buffer := 'n' children_merkles maybe_value;
16/// children_merkles := path_merkle_of_child_0 ... path_merkle_of_child_15;
17/// maybe_value :=   ""     (empty bytes) when maybe_value is None,
18///                | 'v' value            when maybe_value is Some(value).
19///
20/// value can be empty string (to represent TOMBSTONE), therefore we use
21/// 'v' to prefix the value.
22pub fn compute_node_merkle(
23    children_merkles: MaybeMerkleTableRef, maybe_value: Option<&[u8]>,
24) -> MerkleHash {
25    let mut buffer = Vec::with_capacity(
26        1 + std::mem::size_of::<ChildrenMerkleTable>()
27            + maybe_value.map_or(0, |v| 1 + v.len()),
28    );
29    buffer.push('n' as u8);
30    let merkles = match children_merkles {
31        Some(merkles) => merkles,
32        _ => &LEAF_CHILDREN_MERKLE,
33    };
34    for i in 0..CHILDREN_COUNT {
35        buffer.extend_from_slice(merkles[i].as_bytes())
36    }
37
38    match maybe_value {
39        Some(value) => {
40            buffer.push('v' as u8);
41            buffer.extend_from_slice(value);
42        }
43        _ => {}
44    }
45
46    keccak(&buffer)
47}
48
49/// Path merkle is stored as one of a children merkles in its parent node.
50/// It is the merkle of the compressed path combined with a child node.
51///
52/// path_merkle :=   keccak(buffer) when compressed_path has at least one nibble
53///                | node_merkle;
54/// buffer := compressed_path_info_byte compressed_path node_merkle;
55///
56/// compressed_path may exclude half-byte at the beginning or at the end. In
57/// these cases, excluded half-byte will be cleared for the merkle computation.
58///
59/// compressed_path_info_byte := 128 + 64 * (no_first_nibble as bool as int) +
60/// compressed_path.path_steps() % 63
61///
62/// % 63 as we try to avoid power of two which are commonly used in block
63/// cipher.
64///
65/// It's impossible for compressed_path_info_byte to be 'n' used in node merkle
66/// calculation.
67fn compute_path_merkle(
68    compressed_path: CompressedPathRef, without_first_nibble: bool,
69    node_merkle: &MerkleHash,
70) -> MerkleHash {
71    assert_eq!(
72        without_first_nibble,
73        CompressedPathRaw::second_nibble(compressed_path.path_mask())
74            != CompressedPathRaw::NO_MISSING_NIBBLE,
75        "without_first_nibble: {}, path_mask: {}",
76        without_first_nibble,
77        compressed_path.path_mask(),
78    );
79
80    // compressed_path is non-empty.
81    if compressed_path.path_steps() > 0 {
82        let mut buffer = Vec::with_capacity(
83            1 + compressed_path.path_size() as usize
84                + std::mem::size_of::<MerkleHash>(),
85        );
86        // The path_info_byte is defined as:
87        // Most significant bit = 1
88        // 2nd most significant bit = if the first nibble of the first byte
89        // does not belong to the compressed path;
90        // least significant 6 bits = number of nibbles in the compressed path %
91        // 64.
92        let path_info_byte = 128u8
93            + 64u8 * (without_first_nibble as u8)
94            + (compressed_path.path_steps() as u8) % 63u8;
95        buffer.push(path_info_byte);
96
97        buffer.extend_from_slice(compressed_path.path_slice());
98        if without_first_nibble {
99            // Clear out the first nibble.
100            buffer[1] = CompressedPathRaw::second_nibble(buffer[1]);
101        }
102        buffer.extend_from_slice(node_merkle.as_bytes());
103
104        keccak(buffer)
105    } else {
106        *node_merkle
107    }
108}
109
110pub fn compute_merkle(
111    compressed_path: CompressedPathRef, path_without_first_nibble: bool,
112    children_merkles: MaybeMerkleTableRef, maybe_value: Option<&[u8]>,
113) -> MerkleHash {
114    let node_merkle = compute_node_merkle(children_merkles, maybe_value);
115    let path_merkle = compute_path_merkle(
116        compressed_path,
117        path_without_first_nibble,
118        &node_merkle,
119    );
120
121    path_merkle
122}
123
124use super::*;
125use keccak_hash::keccak;
126use primitives::{MerkleHash, MERKLE_NULL_NODE};
cfx_storage/impls/merkle_patricia_trie/merkle.rs

cfx_storage/impls/merkle_patricia_trie/
merkle.rs
