/__w/smoldot/smoldot/repo/lib/src/trie.rs
Line | Count | Source (jump to first uncovered line) |
1 | | // Smoldot |
2 | | // Copyright (C) 2019-2022 Parity Technologies (UK) Ltd. |
3 | | // SPDX-License-Identifier: GPL-3.0-or-later WITH Classpath-exception-2.0 |
4 | | |
5 | | // This program is free software: you can redistribute it and/or modify |
6 | | // it under the terms of the GNU General Public License as published by |
7 | | // the Free Software Foundation, either version 3 of the License, or |
8 | | // (at your option) any later version. |
9 | | |
10 | | // This program is distributed in the hope that it will be useful, |
11 | | // but WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
13 | | // GNU General Public License for more details. |
14 | | |
15 | | // You should have received a copy of the GNU General Public License |
16 | | // along with this program. If not, see <http://www.gnu.org/licenses/>. |
17 | | |
18 | | //! Radix-16 Merkle-Patricia trie. |
19 | | //! |
20 | | //! This Substrate/Polkadot-specific radix-16 Merkle-Patricia trie is a data structure that |
21 | | //! associates keys with values, and that allows efficient verification of the integrity of the |
22 | | //! data. |
23 | | //! |
24 | | //! # Overview |
25 | | //! |
26 | | //! The key-value storage that the blockchain maintains is represented by |
27 | | //! [a tree](https://en.wikipedia.org/wiki/Tree_data_structure), where each key-value pair in the |
28 | | //! storage corresponds to a node in that tree. |
29 | | //! |
30 | | //! Each node in this tree has what is called a Merkle value associated to it. This Merkle value |
31 | | //! consists, in its essence, in the combination of the storage value associated to that node and |
32 | | //! the Merkle values of all of the node's children. If the resulting Merkle value would be too |
33 | | //! long, it is first hashed. |
34 | | //! |
35 | | //! Since the Merkle values of a node's children depend, in turn, of the Merkle value of their |
36 | | //! own children, we can say that the Merkle value of a node depends on all of the node's |
37 | | //! descendants. |
38 | | //! |
39 | | //! Consequently, the Merkle value of the root node of the tree depends on the storage values of |
40 | | //! all the nodes in the tree. |
41 | | //! |
42 | | //! See also [the Wikipedia page for Merkle tree for a different |
43 | | //! explanation](https://en.wikipedia.org/wiki/Merkle_tree). |
44 | | //! |
45 | | //! ## Efficient updates |
46 | | //! |
47 | | //! When a storage value gets modified, the Merkle value of the root node of the tree also gets |
48 | | //! modified. Thanks to the tree layout, we don't need to recalculate the Merkle value of the |
49 | | //! entire tree, but only of the ancestors of the node which has been modified. |
50 | | //! |
51 | | //! If the storage consists of N entries, recalculating the Merkle value of the trie root requires |
52 | | //! on average only `log16(N)` operations. |
53 | | //! |
54 | | //! ## Proof of storage entry |
55 | | //! |
56 | | //! In the situation where we want to know the storage value associated to a node, but we only |
57 | | //! know the Merkle value of the root of the trie, it is possible to ask a third-party for the |
58 | | //! unhashed Merkle values of the desired node and all its ancestors. This is called a Merkle |
59 | | //! proof. |
60 | | //! |
61 | | //! After having verified that the third-party has provided correct values, and that they match |
62 | | //! the expected root node Merkle value known locally, we can extract the storage value from the |
63 | | //! Merkle value of the desired node. |
64 | | //! |
65 | | //! # Details |
66 | | //! |
67 | | //! This data structure is a tree composed of nodes, each node being identified by a key. A key |
68 | | //! consists in a sequence of 4-bits values called *nibbles*. Example key: `[3, 12, 7, 0]`. |
69 | | //! |
70 | | //! Some of these nodes contain a value. |
71 | | //! |
72 | | //! A node A is an *ancestor* of another node B if the key of A is a prefix of the key of B. For |
73 | | //! example, the node whose key is `[3, 12]` is an ancestor of the node whose key is |
74 | | //! `[3, 12, 8, 9]`. B is a *descendant* of A. |
75 | | //! |
76 | | //! Nodes exist only either if they contain a value, or if their key is the longest shared prefix |
77 | | //! of two or more nodes that contain a value. For example, if nodes `[7, 2, 9, 11]` and |
78 | | //! `[7, 2, 14, 8]` contain a value, then node `[7, 2]` also exist, because it is the longest |
79 | | //! prefix shared between the two. |
80 | | //! |
81 | | //! The *Merkle value* of a node is composed, amongst other things, of its associated value and of |
82 | | //! the Merkle value of its descendants. As such, modifying a node modifies the Merkle value of |
83 | | //! all its ancestors. Note, however, that modifying a node modifies the Merkle value of *only* |
84 | | //! its ancestors. As such, the time spent calculating the Merkle value of the root node of a trie |
85 | | //! mostly depends on the number of modifications that are performed on it, and only a bit on the |
86 | | //! size of the trie. |
87 | | //! |
88 | | //! ## Trie entry version |
89 | | //! |
90 | | //! In the Substrate/Polkadot trie, each trie node that contains a value also has a version |
91 | | //! associated to it. |
92 | | //! |
93 | | //! This version changes the way the hash of the node is calculated and how the Merkle proof is |
94 | | //! generated. Version 1 leads to more succinct Merkle proofs, which is important when these proofs |
95 | | //! are sent over the Internet. |
96 | | //! |
97 | | //! Note that most of the time all the entries of the trie have the same version. However, it is |
98 | | //! possible for the trie to be in a hybrid state where some entries have a certain version and |
99 | | //! other entries a different version. For this reason, most of the trie-related APIs require you |
100 | | //! to provide a trie entry version alongside with the value. |
101 | | //! |
102 | | |
103 | | use crate::util; |
104 | | |
105 | | use alloc::{collections::BTreeMap, vec::Vec}; |
106 | | use core::ops::Bound; |
107 | | |
108 | | mod nibble; |
109 | | |
110 | | pub mod branch_search; |
111 | | pub mod calculate_root; |
112 | | pub mod prefix_proof; |
113 | | pub mod proof_decode; |
114 | | pub mod proof_encode; |
115 | | pub mod trie_node; |
116 | | pub mod trie_structure; |
117 | | |
118 | | use alloc::collections::BTreeSet; |
119 | | |
120 | | pub use nibble::{ |
121 | | all_nibbles, bytes_to_nibbles, nibbles_to_bytes_prefix_extend, nibbles_to_bytes_suffix_extend, |
122 | | nibbles_to_bytes_truncate, BytesToNibbles, Nibble, NibbleFromU8Error, |
123 | | }; |
124 | | |
125 | | /// The format of the nodes of trie has two different versions. |
126 | | /// |
127 | | /// As a summary of the difference between versions, in `V1` the value of the item in the trie is |
128 | | /// hashed if it is too large. This isn't the case in `V0` where the value of the item is always |
129 | | /// unhashed. |
130 | | /// |
131 | | /// An encoded node value can be decoded unambiguously no matter whether it was encoded using `V0` |
132 | | /// or `V1`. |
133 | | #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] |
134 | | pub enum TrieEntryVersion { |
135 | | V0, |
136 | | V1, |
137 | | } |
138 | | |
139 | | impl TryFrom<u8> for TrieEntryVersion { |
140 | | type Error = (); // TODO: better error? |
141 | | |
142 | 42 | fn try_from(value: u8) -> Result<Self, Self::Error> { |
143 | 42 | match value { |
144 | 42 | 0 => Ok(TrieEntryVersion::V0), |
145 | 0 | 1 => Ok(TrieEntryVersion::V1), |
146 | 0 | _ => Err(()), |
147 | | } |
148 | 42 | } Unexecuted instantiation: _RNvXNtCsN16ciHI6Qf_7smoldot4trieNtB2_16TrieEntryVersionINtNtCsaYZPK01V26L_4core7convert7TryFromhE8try_from _RNvXNtCseuYC0Zibziv_7smoldot4trieNtB2_16TrieEntryVersionINtNtCsaYZPK01V26L_4core7convert7TryFromhE8try_from Line | Count | Source | 142 | 42 | fn try_from(value: u8) -> Result<Self, Self::Error> { | 143 | 42 | match value { | 144 | 42 | 0 => Ok(TrieEntryVersion::V0), | 145 | 0 | 1 => Ok(TrieEntryVersion::V1), | 146 | 0 | _ => Err(()), | 147 | | } | 148 | 42 | } |
|
149 | | } |
150 | | |
151 | | impl From<TrieEntryVersion> for u8 { |
152 | 61 | fn from(v: TrieEntryVersion) -> u8 { |
153 | 61 | match v { |
154 | 56 | TrieEntryVersion::V0 => 0, |
155 | 5 | TrieEntryVersion::V1 => 1, |
156 | | } |
157 | 61 | } _RNvXs_NtCsN16ciHI6Qf_7smoldot4triehINtNtCsaYZPK01V26L_4core7convert4FromNtB4_16TrieEntryVersionE4from Line | Count | Source | 152 | 61 | fn from(v: TrieEntryVersion) -> u8 { | 153 | 61 | match v { | 154 | 56 | TrieEntryVersion::V0 => 0, | 155 | 5 | TrieEntryVersion::V1 => 1, | 156 | | } | 157 | 61 | } |
Unexecuted instantiation: _RNvXs_NtCseuYC0Zibziv_7smoldot4triehINtNtCsaYZPK01V26L_4core7convert4FromNtB4_16TrieEntryVersionE4from |
158 | | } |
159 | | |
160 | | /// Hash algorithm used during trie calculations. |
161 | | #[derive(Debug, Copy, Clone, PartialEq, Eq)] |
162 | | pub enum HashFunction { |
163 | | Blake2, |
164 | | Keccak256, |
165 | | } |
166 | | |
167 | | /// Merkle value of the root node of an empty trie using [`HashFunction::Blake2`]. |
168 | | pub const EMPTY_BLAKE2_TRIE_MERKLE_VALUE: [u8; 32] = [ |
169 | | 3, 23, 10, 46, 117, 151, 183, 183, 227, 216, 76, 5, 57, 29, 19, 154, 98, 177, 87, 231, 135, |
170 | | 134, 216, 192, 130, 242, 157, 207, 76, 17, 19, 20, |
171 | | ]; |
172 | | |
173 | | /// Merkle value of the root node of an empty trie using [`HashFunction::Keccak256`]. |
174 | | pub const EMPTY_KECCAK256_TRIE_MERKLE_VALUE: [u8; 32] = [ |
175 | | 188, 54, 120, 158, 122, 30, 40, 20, 54, 70, 66, 41, 130, 143, 129, 125, 102, 18, 247, 180, 119, |
176 | | 214, 101, 145, 255, 150, 169, 224, 100, 188, 201, 138, |
177 | | ]; |
178 | | |
179 | | /// Returns the Merkle value of a trie containing the entries passed as parameter. The entries |
180 | | /// passed as parameter are `(key, value)`. |
181 | | /// |
182 | | /// The entries do not need to be ordered. |
183 | 4 | pub fn trie_root( |
184 | 4 | version: TrieEntryVersion, |
185 | 4 | hash_function: HashFunction, |
186 | 4 | unordered_entries: &[(impl AsRef<[u8]>, impl AsRef<[u8]>)], |
187 | 4 | ) -> [u8; 32] { |
188 | 4 | let ordered_entries = unordered_entries |
189 | 4 | .iter() |
190 | 10 | .map(|(k, v)| (k.as_ref(), v.as_ref())) _RNCINvNtCsN16ciHI6Qf_7smoldot4trie9trie_rootRShBG_E0B6_ Line | Count | Source | 190 | 10 | .map(|(k, v)| (k.as_ref(), v.as_ref())) |
Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie9trie_rootRShBH_E0B6_ |
191 | 4 | .collect::<BTreeMap<_, _>>(); |
192 | 4 | |
193 | 4 | let mut calculation = calculate_root::root_merkle_value(hash_function); |
194 | | |
195 | 224 | loop { |
196 | 224 | match calculation { |
197 | 4 | calculate_root::RootMerkleValueCalculation::Finished { hash } => return hash, |
198 | 10 | calculate_root::RootMerkleValueCalculation::StorageValue(storage_value) => { |
199 | 10 | let val = ordered_entries.get(&storage_value.key().collect::<Vec<_>>()[..]); |
200 | 10 | calculation = storage_value.inject(val.map(|v| (v, version))); _RNCINvNtCsN16ciHI6Qf_7smoldot4trie9trie_rootRShBG_Es_0B6_ Line | Count | Source | 200 | 10 | calculation = storage_value.inject(val.map(|v| (v, version))); |
Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie9trie_rootRShBH_Es_0B6_ |
201 | 10 | } |
202 | 210 | calculate_root::RootMerkleValueCalculation::NextKey(next_key) => { |
203 | 210 | let key = next_key |
204 | 210 | .key_before() |
205 | 210 | .chain(next_key.or_equal().then_some(0)) |
206 | 210 | .collect::<Vec<_>>(); |
207 | 210 | let result = ordered_entries |
208 | 210 | .range(&key[..]..) |
209 | 210 | .next() |
210 | 210 | .filter(|(k, _)| { |
211 | 74 | let mut k = k.iter(); |
212 | 74 | let mut p = next_key.prefix(); |
213 | | loop { |
214 | 162 | match (k.next(), p.next()) { |
215 | 124 | (Some(a), Some(b88 )) if *a == b => {}88 |
216 | 36 | (Some(_), Some(_)) => break false, |
217 | 38 | (Some(_), None) => break true, |
218 | 0 | (None, Some(_)) => break false, |
219 | 0 | (None, None) => break true, |
220 | | } |
221 | | } |
222 | 210 | }74 ) _RNCINvNtCsN16ciHI6Qf_7smoldot4trie9trie_rootRShBG_Es0_0B6_ Line | Count | Source | 210 | 74 | .filter(|(k, _)| { | 211 | 74 | let mut k = k.iter(); | 212 | 74 | let mut p = next_key.prefix(); | 213 | | loop { | 214 | 162 | match (k.next(), p.next()) { | 215 | 124 | (Some(a), Some(b88 )) if *a == b => {}88 | 216 | 36 | (Some(_), Some(_)) => break false, | 217 | 38 | (Some(_), None) => break true, | 218 | 0 | (None, Some(_)) => break false, | 219 | 0 | (None, None) => break true, | 220 | | } | 221 | | } | 222 | 74 | }) |
Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie9trie_rootRShBH_Es0_0B6_ |
223 | 210 | .map(|(k, _)| *k38 ); _RNCINvNtCsN16ciHI6Qf_7smoldot4trie9trie_rootRShBG_Es1_0B6_ Line | Count | Source | 223 | 38 | .map(|(k, _)| *k); |
Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie9trie_rootRShBH_Es1_0B6_ |
224 | 210 | calculation = next_key.inject_key(result.map(|s| s.iter().copied()38 )); _RNCINvNtCsN16ciHI6Qf_7smoldot4trie9trie_rootRShBG_Es2_0B6_ Line | Count | Source | 224 | 38 | calculation = next_key.inject_key(result.map(|s| s.iter().copied())); |
Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie9trie_rootRShBH_Es2_0B6_ |
225 | 210 | } |
226 | | } |
227 | | } |
228 | 4 | } _RINvNtCsN16ciHI6Qf_7smoldot4trie9trie_rootRShBE_EB4_ Line | Count | Source | 183 | 4 | pub fn trie_root( | 184 | 4 | version: TrieEntryVersion, | 185 | 4 | hash_function: HashFunction, | 186 | 4 | unordered_entries: &[(impl AsRef<[u8]>, impl AsRef<[u8]>)], | 187 | 4 | ) -> [u8; 32] { | 188 | 4 | let ordered_entries = unordered_entries | 189 | 4 | .iter() | 190 | 4 | .map(|(k, v)| (k.as_ref(), v.as_ref())) | 191 | 4 | .collect::<BTreeMap<_, _>>(); | 192 | 4 | | 193 | 4 | let mut calculation = calculate_root::root_merkle_value(hash_function); | 194 | | | 195 | 224 | loop { | 196 | 224 | match calculation { | 197 | 4 | calculate_root::RootMerkleValueCalculation::Finished { hash } => return hash, | 198 | 10 | calculate_root::RootMerkleValueCalculation::StorageValue(storage_value) => { | 199 | 10 | let val = ordered_entries.get(&storage_value.key().collect::<Vec<_>>()[..]); | 200 | 10 | calculation = storage_value.inject(val.map(|v| (v, version))); | 201 | 10 | } | 202 | 210 | calculate_root::RootMerkleValueCalculation::NextKey(next_key) => { | 203 | 210 | let key = next_key | 204 | 210 | .key_before() | 205 | 210 | .chain(next_key.or_equal().then_some(0)) | 206 | 210 | .collect::<Vec<_>>(); | 207 | 210 | let result = ordered_entries | 208 | 210 | .range(&key[..]..) | 209 | 210 | .next() | 210 | 210 | .filter(|(k, _)| { | 211 | | let mut k = k.iter(); | 212 | | let mut p = next_key.prefix(); | 213 | | loop { | 214 | | match (k.next(), p.next()) { | 215 | | (Some(a), Some(b)) if *a == b => {} | 216 | | (Some(_), Some(_)) => break false, | 217 | | (Some(_), None) => break true, | 218 | | (None, Some(_)) => break false, | 219 | | (None, None) => break true, | 220 | | } | 221 | | } | 222 | 210 | }) | 223 | 210 | .map(|(k, _)| *k); | 224 | 210 | calculation = next_key.inject_key(result.map(|s| s.iter().copied())); | 225 | 210 | } | 226 | | } | 227 | | } | 228 | 4 | } |
Unexecuted instantiation: _RINvNtCseuYC0Zibziv_7smoldot4trie9trie_rootRShBF_EB4_ |
229 | | |
230 | | /// Returns the Merkle value of a trie containing the entries passed as parameter, where the keys |
231 | | /// are the SCALE-codec-encoded indices of these entries. |
232 | | /// |
233 | | /// > **Note**: In isolation, this function seems highly specific. In practice, it is notably used |
234 | | /// > in order to build the trie root of the list of extrinsics of a block. |
235 | 5 | pub fn ordered_root( |
236 | 5 | version: TrieEntryVersion, |
237 | 5 | hash_function: HashFunction, |
238 | 5 | entries: &[impl AsRef<[u8]>], |
239 | 5 | ) -> [u8; 32] { |
240 | 5 | const USIZE_COMPACT_BYTES: usize = 1 + (usize::BITS as usize) / 8; |
241 | 5 | |
242 | 5 | // Mapping numbers to SCALE-encoded numbers changes the ordering, so we have to sort the keys |
243 | 5 | // beforehand. |
244 | 5 | let trie_keys = (0..entries.len()) |
245 | 10 | .map(|num| util::encode_scale_compact_usize(num).as_ref().to_vec()) _RNCINvNtCsN16ciHI6Qf_7smoldot4trie12ordered_rootRShE0B6_ Line | Count | Source | 245 | 10 | .map(|num| util::encode_scale_compact_usize(num).as_ref().to_vec()) |
Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEE0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootRShE0B6_ Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEE0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEE0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEE0CsibGXYHQB8Ea_25json_rpc_general_requests |
246 | 5 | .collect::<BTreeSet<_>>(); |
247 | 5 | |
248 | 5 | let mut calculation = calculate_root::root_merkle_value(hash_function); |
249 | | |
250 | 262 | loop { |
251 | 262 | match calculation { |
252 | 5 | calculate_root::RootMerkleValueCalculation::Finished { hash, .. } => { |
253 | 5 | return hash; |
254 | | } |
255 | 247 | calculate_root::RootMerkleValueCalculation::NextKey(next_key) => { |
256 | 247 | let key_before = next_key.key_before().collect::<Vec<_>>(); |
257 | 247 | let lower_bound = if next_key.or_equal() { |
258 | 247 | Bound::Included(key_before) |
259 | | } else { |
260 | 0 | Bound::Excluded(key_before) |
261 | | }; |
262 | 247 | let k = trie_keys |
263 | 247 | .range((lower_bound, Bound::Unbounded)) |
264 | 247 | .next() |
265 | 247 | .filter(|k| { |
266 | 118 | k.iter() |
267 | 118 | .copied() |
268 | 118 | .zip(next_key.prefix()) |
269 | 118 | .all(|(a, b)| a == b109 ) _RNCNCINvNtCsN16ciHI6Qf_7smoldot4trie12ordered_rootRShEs_00B8_ Line | Count | Source | 269 | 109 | .all(|(a, b)| a == b) |
Unexecuted instantiation: _RNCNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEEs_00CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootRShEs_00B8_ Unexecuted instantiation: _RNCNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEEs_00CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEEs_00CscDgN54JpMGG_6author Unexecuted instantiation: _RNCNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEEs_00CsibGXYHQB8Ea_25json_rpc_general_requests |
270 | 247 | }); _RNCINvNtCsN16ciHI6Qf_7smoldot4trie12ordered_rootRShEs_0B6_ Line | Count | Source | 265 | 118 | .filter(|k| { | 266 | 118 | k.iter() | 267 | 118 | .copied() | 268 | 118 | .zip(next_key.prefix()) | 269 | 118 | .all(|(a, b)| a == b) | 270 | 118 | }); |
Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEEs_0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootRShEs_0B6_ Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEEs_0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEEs_0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEEs_0CsibGXYHQB8Ea_25json_rpc_general_requests |
271 | 247 | calculation = next_key.inject_key(k.map(|k| k.iter().copied()18 )); _RNCINvNtCsN16ciHI6Qf_7smoldot4trie12ordered_rootRShEs0_0B6_ Line | Count | Source | 271 | 18 | calculation = next_key.inject_key(k.map(|k| k.iter().copied())); |
Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEEs0_0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootRShEs0_0B6_ Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEEs0_0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEEs0_0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEEs0_0CsibGXYHQB8Ea_25json_rpc_general_requests |
272 | | } |
273 | 10 | calculate_root::RootMerkleValueCalculation::StorageValue(value_req) => { |
274 | 10 | let key = value_req |
275 | 10 | .key() |
276 | 10 | .collect::<arrayvec::ArrayVec<u8, USIZE_COMPACT_BYTES>>(); |
277 | 10 | let value = match nom::combinator::all_consuming( |
278 | 10 | util::nom_scale_compact_usize::<nom::error::Error<&[u8]>>, |
279 | 10 | )(&key) |
280 | | { |
281 | 10 | Ok((_, key)) => entries.get(key).map(move |v| (v, version)), _RNCINvNtCsN16ciHI6Qf_7smoldot4trie12ordered_rootRShEs1_0B6_ Line | Count | Source | 281 | 10 | Ok((_, key)) => entries.get(key).map(move |v| (v, version)), |
Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEEs1_0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootRShEs1_0B6_ Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEEs1_0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEEs1_0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEEs1_0CsibGXYHQB8Ea_25json_rpc_general_requests |
282 | 0 | Err(_) => None, |
283 | | }; |
284 | 10 | calculation = value_req.inject(value); |
285 | | } |
286 | | } |
287 | | } |
288 | 5 | } _RINvNtCsN16ciHI6Qf_7smoldot4trie12ordered_rootRShEB4_ Line | Count | Source | 235 | 5 | pub fn ordered_root( | 236 | 5 | version: TrieEntryVersion, | 237 | 5 | hash_function: HashFunction, | 238 | 5 | entries: &[impl AsRef<[u8]>], | 239 | 5 | ) -> [u8; 32] { | 240 | 5 | const USIZE_COMPACT_BYTES: usize = 1 + (usize::BITS as usize) / 8; | 241 | 5 | | 242 | 5 | // Mapping numbers to SCALE-encoded numbers changes the ordering, so we have to sort the keys | 243 | 5 | // beforehand. | 244 | 5 | let trie_keys = (0..entries.len()) | 245 | 5 | .map(|num| util::encode_scale_compact_usize(num).as_ref().to_vec()) | 246 | 5 | .collect::<BTreeSet<_>>(); | 247 | 5 | | 248 | 5 | let mut calculation = calculate_root::root_merkle_value(hash_function); | 249 | | | 250 | 262 | loop { | 251 | 262 | match calculation { | 252 | 5 | calculate_root::RootMerkleValueCalculation::Finished { hash, .. } => { | 253 | 5 | return hash; | 254 | | } | 255 | 247 | calculate_root::RootMerkleValueCalculation::NextKey(next_key) => { | 256 | 247 | let key_before = next_key.key_before().collect::<Vec<_>>(); | 257 | 247 | let lower_bound = if next_key.or_equal() { | 258 | 247 | Bound::Included(key_before) | 259 | | } else { | 260 | 0 | Bound::Excluded(key_before) | 261 | | }; | 262 | 247 | let k = trie_keys | 263 | 247 | .range((lower_bound, Bound::Unbounded)) | 264 | 247 | .next() | 265 | 247 | .filter(|k| { | 266 | | k.iter() | 267 | | .copied() | 268 | | .zip(next_key.prefix()) | 269 | | .all(|(a, b)| a == b) | 270 | 247 | }); | 271 | 247 | calculation = next_key.inject_key(k.map(|k| k.iter().copied())); | 272 | | } | 273 | 10 | calculate_root::RootMerkleValueCalculation::StorageValue(value_req) => { | 274 | 10 | let key = value_req | 275 | 10 | .key() | 276 | 10 | .collect::<arrayvec::ArrayVec<u8, USIZE_COMPACT_BYTES>>(); | 277 | 10 | let value = match nom::combinator::all_consuming( | 278 | 10 | util::nom_scale_compact_usize::<nom::error::Error<&[u8]>>, | 279 | 10 | )(&key) | 280 | | { | 281 | 10 | Ok((_, key)) => entries.get(key).map(move |v| (v, version)), | 282 | 0 | Err(_) => None, | 283 | | }; | 284 | 10 | calculation = value_req.inject(value); | 285 | | } | 286 | | } | 287 | | } | 288 | 5 | } |
Unexecuted instantiation: _RINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEECsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootRShEB4_ Unexecuted instantiation: _RINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEECsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEECscDgN54JpMGG_6author Unexecuted instantiation: _RINvNtCseuYC0Zibziv_7smoldot4trie12ordered_rootINtNtCsdZExvAaxgia_5alloc3vec3VechEECsibGXYHQB8Ea_25json_rpc_general_requests |
289 | | |
290 | | #[cfg(test)] |
291 | | mod tests { |
292 | | use super::{trie_node, HashFunction}; |
293 | | use core::iter; |
294 | | |
295 | | #[test] |
296 | 1 | fn empty_trie_blake2() { |
297 | 1 | let calculated_through_function = *<&[u8; 32]>::try_from( |
298 | 1 | trie_node::calculate_merkle_value( |
299 | 1 | trie_node::Decoded { |
300 | 1 | children: [None::<&'static [u8]>; 16], |
301 | 1 | partial_key: iter::empty(), |
302 | 1 | storage_value: trie_node::StorageValue::None, |
303 | 1 | }, |
304 | 1 | HashFunction::Blake2, |
305 | 1 | true, |
306 | 1 | ) |
307 | 1 | .unwrap() |
308 | 1 | .as_ref(), |
309 | 1 | ) |
310 | 1 | .unwrap(); |
311 | 1 | |
312 | 1 | let calculated_manually = blake2_rfc::blake2b::blake2b(32, &[], &[0x0]); |
313 | 1 | |
314 | 1 | assert_eq!(calculated_through_function, calculated_manually.as_bytes()); |
315 | 1 | assert_eq!( |
316 | 1 | calculated_through_function, |
317 | 1 | super::EMPTY_BLAKE2_TRIE_MERKLE_VALUE |
318 | 1 | ); |
319 | 1 | } |
320 | | |
321 | | #[test] |
322 | 1 | fn empty_trie_keccak256() { |
323 | 1 | let calculated_through_function = *<&[u8; 32]>::try_from( |
324 | 1 | trie_node::calculate_merkle_value( |
325 | 1 | trie_node::Decoded { |
326 | 1 | children: [None::<&'static [u8]>; 16], |
327 | 1 | partial_key: iter::empty(), |
328 | 1 | storage_value: trie_node::StorageValue::None, |
329 | 1 | }, |
330 | 1 | HashFunction::Keccak256, |
331 | 1 | true, |
332 | 1 | ) |
333 | 1 | .unwrap() |
334 | 1 | .as_ref(), |
335 | 1 | ) |
336 | 1 | .unwrap(); |
337 | 1 | |
338 | 1 | let calculated_manually = <sha3::Keccak256 as sha3::Digest>::digest(&[0x0]); |
339 | 1 | |
340 | 1 | assert_eq!(calculated_through_function, calculated_manually.as_ref()); |
341 | 1 | assert_eq!( |
342 | 1 | calculated_through_function, |
343 | 1 | super::EMPTY_KECCAK256_TRIE_MERKLE_VALUE |
344 | 1 | ); |
345 | 1 | } |
346 | | |
347 | | #[test] |
348 | 1 | fn trie_root_example_v0_blake2() { |
349 | 1 | let obtained = super::trie_root( |
350 | 1 | super::TrieEntryVersion::V0, |
351 | 1 | super::HashFunction::Blake2, |
352 | 1 | &[(&b"foo"[..], &b"bar"[..]), (&b"foobar"[..], &b"baz"[..])], |
353 | 1 | ); |
354 | 1 | |
355 | 1 | assert_eq!( |
356 | 1 | obtained, |
357 | 1 | [ |
358 | 1 | 166, 24, 32, 181, 251, 169, 176, 26, 238, 16, 181, 187, 216, 74, 234, 128, 184, 35, |
359 | 1 | 3, 24, 197, 232, 202, 20, 185, 164, 148, 12, 118, 224, 152, 21 |
360 | 1 | ] |
361 | 1 | ); |
362 | 1 | } |
363 | | |
364 | | #[test] |
365 | 1 | fn trie_root_example_v0_keccak() { |
366 | 1 | let obtained = super::trie_root( |
367 | 1 | super::TrieEntryVersion::V0, |
368 | 1 | super::HashFunction::Keccak256, |
369 | 1 | &[(&b"foo"[..], &b"bar"[..]), (&b"foobar"[..], &b"baz"[..])], |
370 | 1 | ); |
371 | 1 | |
372 | 1 | assert_eq!( |
373 | 1 | obtained, |
374 | 1 | [ |
375 | 1 | 109, 13, 46, 4, 44, 192, 37, 121, 213, 230, 248, 34, 108, 36, 86, 23, 164, 52, 162, |
376 | 1 | 165, 248, 111, 236, 65, 142, 71, 118, 196, 44, 205, 139, 145 |
377 | 1 | ] |
378 | 1 | ); |
379 | 1 | } |
380 | | |
381 | | #[test] |
382 | 1 | fn trie_root_example_v1_blake2() { |
383 | 1 | let obtained = super::trie_root( |
384 | 1 | super::TrieEntryVersion::V1, |
385 | 1 | super::HashFunction::Blake2, |
386 | 1 | &[ |
387 | 1 | (&b"bar"[..], &b"foo"[..]), |
388 | 1 | (&b"barfoo"[..], &b"hello"[..]), |
389 | 1 | (&b"anotheritem"[..], &b"anothervalue"[..]), |
390 | 1 | ], |
391 | 1 | ); |
392 | 1 | |
393 | 1 | assert_eq!( |
394 | 1 | obtained, |
395 | 1 | [ |
396 | 1 | 68, 24, 7, 195, 69, 202, 122, 223, 136, 189, 33, 171, 27, 60, 186, 219, 21, 97, |
397 | 1 | 106, 187, 137, 22, 126, 185, 254, 40, 93, 213, 206, 205, 4, 200 |
398 | 1 | ] |
399 | 1 | ); |
400 | 1 | } |
401 | | |
402 | | #[test] |
403 | 1 | fn trie_root_example_v1_keccak() { |
404 | 1 | let obtained = super::trie_root( |
405 | 1 | super::TrieEntryVersion::V1, |
406 | 1 | super::HashFunction::Keccak256, |
407 | 1 | &[ |
408 | 1 | (&b"bar"[..], &b"foo"[..]), |
409 | 1 | (&b"barfoo"[..], &b"hello"[..]), |
410 | 1 | (&b"anotheritem"[..], &b"anothervalue"[..]), |
411 | 1 | ], |
412 | 1 | ); |
413 | 1 | |
414 | 1 | assert_eq!( |
415 | 1 | obtained, |
416 | 1 | [ |
417 | 1 | 163, 182, 101, 58, 113, 93, 97, 19, 25, 39, 58, 170, 167, 225, 212, 187, 157, 3, |
418 | 1 | 230, 21, 92, 129, 196, 38, 212, 190, 49, 103, 242, 0, 4, 65 |
419 | 1 | ] |
420 | 1 | ); |
421 | 1 | } |
422 | | } |