/__w/smoldot/smoldot/repo/lib/src/trie/proof_encode.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 | | use super::{nibble, trie_node, trie_structure}; |
19 | | |
20 | | use alloc::{borrow::ToOwned as _, vec::Vec}; |
21 | | use core::{array, iter}; |
22 | | |
23 | | pub use super::nibble::Nibble; |
24 | | |
25 | | /// Prototype for a Merkle proof whose building is in progress. |
26 | | pub struct ProofBuilder { |
27 | | /// Contains a subset of the trie. Each node is associated with its node value if it is known, |
28 | | /// or `None` if it isn't known. |
29 | | /// |
30 | | /// The `TrieStructure` data structure is very explicit in its usage. Nodes such as branch |
31 | | /// nodes are not implicitly but explicitly created. However, the trie structure is normally |
32 | | /// not meant to contain branch nodes without any children. In order to bypass this |
33 | | /// restriction, we pretend that nodes have a storage value when necessary even if this is |
34 | | /// not the case. |
35 | | trie_structure: trie_structure::TrieStructure<Option<Node>>, |
36 | | |
37 | | /// List of keys of the nodes in [`ProofBuilder::trie_structure`] whose user data is `None`. |
38 | | missing_node_values: hashbrown::HashSet<Vec<Nibble>, fnv::FnvBuildHasher>, |
39 | | } |
40 | | |
41 | | #[derive(Debug, Clone)] |
42 | | struct Node { |
43 | | /// Value passed as `node_value` by the API user. |
44 | | node_value: Vec<u8>, |
45 | | /// Node containing the storage value associated with this node. |
46 | | storage_value_node: Option<Vec<u8>>, |
47 | | } |
48 | | |
49 | | impl ProofBuilder { |
50 | | /// Initializes a new empty proof builder. |
51 | | /// |
52 | | /// This is equivalent to calling [`ProofBuilder::with_nodes_capacity`] with a value of 0. |
53 | 1.50k | pub fn new() -> Self { |
54 | 1.50k | Self::with_nodes_capacity(0) |
55 | 1.50k | } _RNvMNtNtCsN16ciHI6Qf_7smoldot4trie12proof_encodeNtB2_12ProofBuilder3new Line | Count | Source | 53 | 1.50k | pub fn new() -> Self { | 54 | 1.50k | Self::with_nodes_capacity(0) | 55 | 1.50k | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot4trie12proof_encodeNtB2_12ProofBuilder3new |
56 | | |
57 | | /// Initializes a new empty proof builder. |
58 | | /// |
59 | | /// Memory is allocated to store `capacity` nodes, in other words the number of nodes added |
60 | | /// using [`ProofBuilder::set_node_value`]. |
61 | 1.50k | pub fn with_nodes_capacity(capacity: usize) -> Self { |
62 | 1.50k | ProofBuilder { |
63 | 1.50k | trie_structure: trie_structure::TrieStructure::with_capacity(capacity), |
64 | 1.50k | missing_node_values: hashbrown::HashSet::with_capacity_and_hasher( |
65 | 1.50k | capacity, |
66 | 1.50k | Default::default(), |
67 | 1.50k | ), |
68 | 1.50k | } |
69 | 1.50k | } _RNvMNtNtCsN16ciHI6Qf_7smoldot4trie12proof_encodeNtB2_12ProofBuilder19with_nodes_capacity Line | Count | Source | 61 | 1.50k | pub fn with_nodes_capacity(capacity: usize) -> Self { | 62 | 1.50k | ProofBuilder { | 63 | 1.50k | trie_structure: trie_structure::TrieStructure::with_capacity(capacity), | 64 | 1.50k | missing_node_values: hashbrown::HashSet::with_capacity_and_hasher( | 65 | 1.50k | capacity, | 66 | 1.50k | Default::default(), | 67 | 1.50k | ), | 68 | 1.50k | } | 69 | 1.50k | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot4trie12proof_encodeNtB2_12ProofBuilder19with_nodes_capacity |
70 | | |
71 | | /// Inserts the node value of a given trie node into the builder. |
72 | | /// |
73 | | /// Overwrites any previously-set value for this key. |
74 | | /// |
75 | | /// The `node_value` is decoded in order for the proof builder to determine the hierarchy of |
76 | | /// the trie and know which node values are missing. If the `node_value` is invalid, this |
77 | | /// function panics. In order to avoid difficult-to-debug corner cases, this function also |
78 | | /// panics if it is no possible for `node_value` to be found at the given `key` due to a |
79 | | /// mismatch. |
80 | | /// |
81 | | /// If the `node_value` contains a storage value as a hash, then a `unhashed_storage_value` |
82 | | /// can optionally be provided in order to provide the unhashed version of this value. |
83 | | /// |
84 | | /// The validity of the `node_value` in the context of the other node values that have been |
85 | | /// stored in this proof builder isn't verified. For example, a node value can indicate no |
86 | | /// children while the node value of a child has been added, or a node value can indicate a |
87 | | /// child with a specific hash, while the child in question has a different hash. This will |
88 | | /// lead to an invalid proof being generated. |
89 | | /// |
90 | | /// # Panic |
91 | | /// |
92 | | /// Panics if `node_value` is not a valid node value. |
93 | | /// Panics if the partial key found in `node_value` doesn't match the last elements of `key`. |
94 | | /// Panics in case `node_value` indicates no storage value, but `unhashed_storage_value` |
95 | | /// is `Some`. |
96 | | /// |
97 | 28.8k | pub fn set_node_value( |
98 | 28.8k | &mut self, |
99 | 28.8k | key: &[Nibble], |
100 | 28.8k | node_value: &[u8], |
101 | 28.8k | unhashed_storage_value: Option<&[u8]>, |
102 | 28.8k | ) { |
103 | | // The first thing to do is decode the node value, in order to detect invalid node values |
104 | | // first things first. |
105 | 28.8k | let decoded_node_value28.8k = match trie_node::decode(node_value) { |
106 | 28.8k | Ok(d) => d, |
107 | 1 | Err(err) => panic!("failed to decode node value: {err:?}; value: {node_value:?}"), |
108 | | }; |
109 | | |
110 | | // Check consistency between `node_value` and `unhashed_storage_value` and determine |
111 | | // whether a separate storage node should be included in the proof. |
112 | 28.8k | let storage_value_node = match (&decoded_node_value.storage_value, &unhashed_storage_value) |
113 | | { |
114 | 0 | (trie_node::StorageValue::Unhashed(ref in_node_value), Some(ref user_provided)) => { |
115 | 0 | assert_eq!(in_node_value, user_provided); |
116 | 0 | None |
117 | | } |
118 | 0 | (trie_node::StorageValue::Hashed(_), Some(value)) => Some(value.to_vec()), |
119 | 0 | (trie_node::StorageValue::None, Some(_)) => panic!(), |
120 | 28.8k | (_, None) => None, |
121 | | }; |
122 | | |
123 | | // Value that is going to be inserted in the trie. |
124 | 28.8k | let trie_structure_value = Node { |
125 | 28.8k | node_value: node_value.to_owned(), |
126 | 28.8k | storage_value_node, |
127 | 28.8k | }; |
128 | 28.8k | |
129 | 28.8k | match self.trie_structure.node(key.iter().copied()) { |
130 | 6.40k | trie_structure::Entry::Occupied(mut entry) => { |
131 | 6.40k | let _was_in = self.missing_node_values.remove(key); |
132 | 6.40k | debug_assert_eq!(_was_in, entry.user_data().is_none()); |
133 | 6.40k | *entry.user_data() = Some(trie_structure_value); |
134 | | } |
135 | 22.4k | trie_structure::Entry::Vacant(entry) => { |
136 | 22.4k | // We insert a storage value for the given node, even though the node might be |
137 | 22.4k | // a branch node. This is necessary in order for the trie structure to store our |
138 | 22.4k | // node, as otherwise the node possibly wouldn't exist. |
139 | 22.4k | match entry.insert_storage_value() { |
140 | 22.4k | trie_structure::PrepareInsert::One(insert) => { |
141 | 22.4k | insert.insert(Some(trie_structure_value)); |
142 | 22.4k | } |
143 | 0 | trie_structure::PrepareInsert::Two(insert) => { |
144 | 0 | let _was_inserted = self |
145 | 0 | .missing_node_values |
146 | 0 | .insert(insert.branch_node_key().collect()); |
147 | 0 | debug_assert!(_was_inserted); |
148 | 0 | insert.insert(Some(trie_structure_value), None); |
149 | | } |
150 | | } |
151 | | } |
152 | | } |
153 | | |
154 | | // We must also make sure that the parent of the node is in the proof. Insert the parent |
155 | | // in the trie structure as well. |
156 | | // This shouldn't be done if the node is the root node of the trie. |
157 | 28.8k | let partial_key_len = decoded_node_value.partial_key.len(); |
158 | 28.8k | assert!( |
159 | 28.8k | key.len() >= partial_key_len, |
160 | 0 | "mismatch between node value partial key and provided key" |
161 | | ); |
162 | 28.8k | assert!( |
163 | 28.8k | itertools::equal( |
164 | 28.8k | key[(key.len() - partial_key_len)..].iter().copied(), |
165 | 28.8k | decoded_node_value.partial_key.clone() |
166 | 28.8k | ), |
167 | 0 | "mismatch between node value partial key and provided key" |
168 | | ); |
169 | 28.8k | if key.len() != partial_key_len { |
170 | 27.3k | let parent_key = &key[..(key.len() - partial_key_len - 1)]; |
171 | 27.3k | match self.trie_structure.node(parent_key.iter().copied()) { |
172 | 20.9k | trie_structure::Entry::Occupied(_) => { |
173 | 20.9k | // The parent is already in the structure. Nothing to do. |
174 | 20.9k | } |
175 | 6.40k | trie_structure::Entry::Vacant(entry) => match entry.insert_storage_value() { |
176 | 6.40k | trie_structure::PrepareInsert::One(insert) => { |
177 | 6.40k | let _was_inserted = self.missing_node_values.insert(parent_key.to_owned()); |
178 | 6.40k | debug_assert!(_was_inserted); |
179 | 6.40k | insert.insert(None); |
180 | | } |
181 | 0 | trie_structure::PrepareInsert::Two(insert) => { |
182 | 0 | let _was_inserted = self.missing_node_values.insert(parent_key.to_owned()); |
183 | 0 | debug_assert!(_was_inserted); |
184 | | |
185 | 0 | let _was_inserted = self |
186 | 0 | .missing_node_values |
187 | 0 | .insert(insert.branch_node_key().collect()); |
188 | 0 | debug_assert!(_was_inserted); |
189 | | |
190 | 0 | insert.insert(None, None); |
191 | | } |
192 | | }, |
193 | | } |
194 | 1.50k | } |
195 | 28.8k | } _RNvMNtNtCsN16ciHI6Qf_7smoldot4trie12proof_encodeNtB2_12ProofBuilder14set_node_value Line | Count | Source | 97 | 28.8k | pub fn set_node_value( | 98 | 28.8k | &mut self, | 99 | 28.8k | key: &[Nibble], | 100 | 28.8k | node_value: &[u8], | 101 | 28.8k | unhashed_storage_value: Option<&[u8]>, | 102 | 28.8k | ) { | 103 | | // The first thing to do is decode the node value, in order to detect invalid node values | 104 | | // first things first. | 105 | 28.8k | let decoded_node_value28.8k = match trie_node::decode(node_value) { | 106 | 28.8k | Ok(d) => d, | 107 | 1 | Err(err) => panic!("failed to decode node value: {err:?}; value: {node_value:?}"), | 108 | | }; | 109 | | | 110 | | // Check consistency between `node_value` and `unhashed_storage_value` and determine | 111 | | // whether a separate storage node should be included in the proof. | 112 | 28.8k | let storage_value_node = match (&decoded_node_value.storage_value, &unhashed_storage_value) | 113 | | { | 114 | 0 | (trie_node::StorageValue::Unhashed(ref in_node_value), Some(ref user_provided)) => { | 115 | 0 | assert_eq!(in_node_value, user_provided); | 116 | 0 | None | 117 | | } | 118 | 0 | (trie_node::StorageValue::Hashed(_), Some(value)) => Some(value.to_vec()), | 119 | 0 | (trie_node::StorageValue::None, Some(_)) => panic!(), | 120 | 28.8k | (_, None) => None, | 121 | | }; | 122 | | | 123 | | // Value that is going to be inserted in the trie. | 124 | 28.8k | let trie_structure_value = Node { | 125 | 28.8k | node_value: node_value.to_owned(), | 126 | 28.8k | storage_value_node, | 127 | 28.8k | }; | 128 | 28.8k | | 129 | 28.8k | match self.trie_structure.node(key.iter().copied()) { | 130 | 6.40k | trie_structure::Entry::Occupied(mut entry) => { | 131 | 6.40k | let _was_in = self.missing_node_values.remove(key); | 132 | 6.40k | debug_assert_eq!(_was_in, entry.user_data().is_none()); | 133 | 6.40k | *entry.user_data() = Some(trie_structure_value); | 134 | | } | 135 | 22.4k | trie_structure::Entry::Vacant(entry) => { | 136 | 22.4k | // We insert a storage value for the given node, even though the node might be | 137 | 22.4k | // a branch node. This is necessary in order for the trie structure to store our | 138 | 22.4k | // node, as otherwise the node possibly wouldn't exist. | 139 | 22.4k | match entry.insert_storage_value() { | 140 | 22.4k | trie_structure::PrepareInsert::One(insert) => { | 141 | 22.4k | insert.insert(Some(trie_structure_value)); | 142 | 22.4k | } | 143 | 0 | trie_structure::PrepareInsert::Two(insert) => { | 144 | 0 | let _was_inserted = self | 145 | 0 | .missing_node_values | 146 | 0 | .insert(insert.branch_node_key().collect()); | 147 | 0 | debug_assert!(_was_inserted); | 148 | 0 | insert.insert(Some(trie_structure_value), None); | 149 | | } | 150 | | } | 151 | | } | 152 | | } | 153 | | | 154 | | // We must also make sure that the parent of the node is in the proof. Insert the parent | 155 | | // in the trie structure as well. | 156 | | // This shouldn't be done if the node is the root node of the trie. | 157 | 28.8k | let partial_key_len = decoded_node_value.partial_key.len(); | 158 | 28.8k | assert!( | 159 | 28.8k | key.len() >= partial_key_len, | 160 | 0 | "mismatch between node value partial key and provided key" | 161 | | ); | 162 | 28.8k | assert!( | 163 | 28.8k | itertools::equal( | 164 | 28.8k | key[(key.len() - partial_key_len)..].iter().copied(), | 165 | 28.8k | decoded_node_value.partial_key.clone() | 166 | 28.8k | ), | 167 | 0 | "mismatch between node value partial key and provided key" | 168 | | ); | 169 | 28.8k | if key.len() != partial_key_len { | 170 | 27.3k | let parent_key = &key[..(key.len() - partial_key_len - 1)]; | 171 | 27.3k | match self.trie_structure.node(parent_key.iter().copied()) { | 172 | 20.9k | trie_structure::Entry::Occupied(_) => { | 173 | 20.9k | // The parent is already in the structure. Nothing to do. | 174 | 20.9k | } | 175 | 6.40k | trie_structure::Entry::Vacant(entry) => match entry.insert_storage_value() { | 176 | 6.40k | trie_structure::PrepareInsert::One(insert) => { | 177 | 6.40k | let _was_inserted = self.missing_node_values.insert(parent_key.to_owned()); | 178 | 6.40k | debug_assert!(_was_inserted); | 179 | 6.40k | insert.insert(None); | 180 | | } | 181 | 0 | trie_structure::PrepareInsert::Two(insert) => { | 182 | 0 | let _was_inserted = self.missing_node_values.insert(parent_key.to_owned()); | 183 | 0 | debug_assert!(_was_inserted); | 184 | | | 185 | 0 | let _was_inserted = self | 186 | 0 | .missing_node_values | 187 | 0 | .insert(insert.branch_node_key().collect()); | 188 | 0 | debug_assert!(_was_inserted); | 189 | | | 190 | 0 | insert.insert(None, None); | 191 | | } | 192 | | }, | 193 | | } | 194 | 1.50k | } | 195 | 28.8k | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot4trie12proof_encodeNtB2_12ProofBuilder14set_node_value |
196 | | |
197 | | /// Returns a list of keys for which the node value must be known in order to be able to build |
198 | | /// the proof. |
199 | | /// |
200 | | /// For each entry returned by this iterator, [`ProofBuilder::set_node_value`] must be called. |
201 | | /// |
202 | | /// This function has a complexity of `O(1)` and thus can be called repeatedly. |
203 | 1.50k | pub fn missing_node_values(&self) -> impl Iterator<Item = &[Nibble]> { |
204 | 1.50k | self.missing_node_values.iter().map(|v| &v[..]1 ) _RNCNvMNtNtCsN16ciHI6Qf_7smoldot4trie12proof_encodeNtB4_12ProofBuilder19missing_node_values0B8_ Line | Count | Source | 204 | 1 | self.missing_node_values.iter().map(|v| &v[..]) |
Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot4trie12proof_encodeNtB4_12ProofBuilder19missing_node_values0B8_ |
205 | 1.50k | } _RNvMNtNtCsN16ciHI6Qf_7smoldot4trie12proof_encodeNtB2_12ProofBuilder19missing_node_values Line | Count | Source | 203 | 1.50k | pub fn missing_node_values(&self) -> impl Iterator<Item = &[Nibble]> { | 204 | 1.50k | self.missing_node_values.iter().map(|v| &v[..]) | 205 | 1.50k | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot4trie12proof_encodeNtB2_12ProofBuilder19missing_node_values |
206 | | |
207 | | /// Returns the hash of the trie root node. |
208 | | /// |
209 | | /// This function returns `None` if the proof is empty or if the trie root node is missing |
210 | | /// from the proof, in which case [`ProofBuilder::missing_node_values`] will return it. |
211 | | /// |
212 | | /// In other words, if the proof is not empty and if [`ProofBuilder::missing_node_values`] |
213 | | /// returns an empty iterator, then you are guaranteed that this function returns `Some`. |
214 | | /// |
215 | | /// This function has a complexity of `O(1)`. |
216 | 1.50k | pub fn trie_root_hash(&self) -> Option<[u8; 32]> { |
217 | 1.50k | let node_value = &self.trie_structure.root_user_data()?0 .as_ref()?0 .node_value; |
218 | 1.50k | Some(blake2_hash(node_value)) |
219 | 1.50k | } _RNvMNtNtCsN16ciHI6Qf_7smoldot4trie12proof_encodeNtB2_12ProofBuilder14trie_root_hash Line | Count | Source | 216 | 1.50k | pub fn trie_root_hash(&self) -> Option<[u8; 32]> { | 217 | 1.50k | let node_value = &self.trie_structure.root_user_data()?0 .as_ref()?0 .node_value; | 218 | 1.50k | Some(blake2_hash(node_value)) | 219 | 1.50k | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot4trie12proof_encodeNtB2_12ProofBuilder14trie_root_hash |
220 | | |
221 | | /// Modifies the node values that have been inserted in the proof builder in order to make the |
222 | | /// proof coherent, if necessary. |
223 | | /// |
224 | | /// If all the node values that have been added through [`ProofBuilder::set_node_value`] come |
225 | | /// from a valid trie, then the proof is already coherent and there is no need to call this |
226 | | /// function. This function is necessary only in situations where the node values have been |
227 | | /// manually modified. |
228 | | /// |
229 | | /// Calling this function when the node values aren't coherent will modify the hash of the trie |
230 | | /// root that is found in the proof. Most of the time, the verification of a trie proof checks |
231 | | /// whether the hash of the trie root in the proof matches an expected value. When that is the |
232 | | /// case, then calling this function would produce a proof that is no longer accepted. |
233 | | /// |
234 | | /// This function only updates the hashes of storage values and children. Storage values |
235 | | /// themselves are always left untouched. |
236 | | /// This function also updates the presence of children. If a node has been added using |
237 | | /// [`ProofBuilder::set_node_value`] but its parent indicates a lack of child, then calling |
238 | | /// this function will modify the parent in order to indicate the presence of a child. |
239 | | /// However, this function never removes children. If a node indicates that it has a child, but |
240 | | /// the child has not been added using [`ProofBuilder::set_node_value`], it simply indicates |
241 | | /// that the child in question is (intentionally) not part of the proof, and the proof is still |
242 | | /// valid. |
243 | | /// |
244 | | /// This function works even if [`ProofBuilder::missing_node_values`] returns a non-empty |
245 | | /// iterator, but will not be able to update everything. You are encouraged to call this |
246 | | /// function only after having added all missing node values; |
247 | 1.50k | pub fn make_coherent(&mut self) { |
248 | | // The implementation of this function iterates over the nodes of the trie in a specific |
249 | | // order: we start with the deepest child possible of the root node, then we jump from each |
250 | | // node to the deepest child possible of its next sibling. If a node is the last sibling, |
251 | | // jump to its parent. |
252 | | // This order of iteration guarantees that we traverse all the nodes of the trie, and that |
253 | | // we don't traverse a parent before having traversed of all its children. |
254 | | // When traversing a node, we calculate the hash of its children and update the node value |
255 | | // of that node. |
256 | | |
257 | | // Node currently being iterated. |
258 | 1.50k | let mut iter: trie_structure::NodeAccess<_> = { |
259 | 1.50k | let mut node = match self.trie_structure.root_node() { |
260 | 1.50k | Some(c) => c, |
261 | | None => { |
262 | | // Trie is empty. |
263 | 0 | return; |
264 | | } |
265 | | }; |
266 | | |
267 | 3.50k | loop { |
268 | 3.50k | match node.into_first_child() { |
269 | 2.00k | Ok(c) => node = c, |
270 | 1.50k | Err(c) => break c, |
271 | | } |
272 | | } |
273 | | }; |
274 | | |
275 | 28.8k | loop { |
276 | 28.8k | // Due to borrowing issues, we calculate ahead of time the values of the children of |
277 | 28.8k | // the node. |
278 | 28.8k | let children_values: [Option<Option<arrayvec::ArrayVec<u8, 32>>>; 16] = |
279 | 461k | array::from_fn(|nibble| { |
280 | 461k | let nibble = nibble::Nibble::try_from(u8::try_from(nibble).unwrap()).unwrap(); |
281 | | |
282 | 461k | if let Some(child_node_info27.3k ) = iter.child_user_data(nibble) { |
283 | 27.3k | if let Some(child_node_info) = child_node_info { |
284 | | // Node values of length < 32 are inlined. |
285 | 27.3k | if child_node_info.node_value.len() < 32 { |
286 | 8.87k | Some(Some(child_node_info.node_value.iter().copied().collect())) |
287 | | } else { |
288 | 18.4k | Some(Some(blake2_hash(&child_node_info.node_value).into())) |
289 | | } |
290 | | } else { |
291 | | // Missing node value. Don't update anything. |
292 | 0 | None |
293 | | } |
294 | | } else { |
295 | 433k | Some(None) |
296 | | } |
297 | 461k | })28.8k ; _RNCNvMNtNtCsN16ciHI6Qf_7smoldot4trie12proof_encodeNtB4_12ProofBuilder13make_coherent0B8_ Line | Count | Source | 279 | 461k | array::from_fn(|nibble| { | 280 | 461k | let nibble = nibble::Nibble::try_from(u8::try_from(nibble).unwrap()).unwrap(); | 281 | | | 282 | 461k | if let Some(child_node_info27.3k ) = iter.child_user_data(nibble) { | 283 | 27.3k | if let Some(child_node_info) = child_node_info { | 284 | | // Node values of length < 32 are inlined. | 285 | 27.3k | if child_node_info.node_value.len() < 32 { | 286 | 8.87k | Some(Some(child_node_info.node_value.iter().copied().collect())) | 287 | | } else { | 288 | 18.4k | Some(Some(blake2_hash(&child_node_info.node_value).into())) | 289 | | } | 290 | | } else { | 291 | | // Missing node value. Don't update anything. | 292 | 0 | None | 293 | | } | 294 | | } else { | 295 | 433k | Some(None) | 296 | | } | 297 | 461k | }); |
Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot4trie12proof_encodeNtB4_12ProofBuilder13make_coherent0B8_ |
298 | | |
299 | | // We only update the current node if its node value has been inserted by the user. |
300 | 28.8k | if let Some(node_info) = iter.user_data().as_mut() { |
301 | | // We already make sure that node values are valid when inserting them. As such, |
302 | | // it is ok to `unwrap()` here. |
303 | 28.8k | let mut decoded_node_value = trie_node::decode(&node_info.node_value).unwrap(); |
304 | 28.8k | |
305 | 28.8k | // Update the hash of the storage value contained in `decoded_node_value`. |
306 | 28.8k | // This is done in a slightly weird way due to borrowing issues. |
307 | 28.8k | let storage_value_hash = node_info |
308 | 28.8k | .storage_value_node |
309 | 28.8k | .as_ref() |
310 | 28.8k | .map(|v| blake2_hash(v)0 ); Unexecuted instantiation: _RNCNvMNtNtCsN16ciHI6Qf_7smoldot4trie12proof_encodeNtB4_12ProofBuilder13make_coherents_0B8_ Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot4trie12proof_encodeNtB4_12ProofBuilder13make_coherents_0B8_ |
311 | 28.8k | debug_assert_eq!( |
312 | 28.8k | storage_value_hash.is_some(), |
313 | 28.8k | matches!( |
314 | 28.8k | decoded_node_value.storage_value, |
315 | | trie_node::StorageValue::Hashed(_) |
316 | | ) |
317 | | ); |
318 | 28.8k | if let Some(storage_value_hash0 ) = storage_value_hash.as_ref() { |
319 | 0 | decoded_node_value.storage_value = |
320 | 0 | trie_node::StorageValue::Hashed(storage_value_hash); |
321 | 28.8k | } |
322 | | |
323 | | // Update the children. |
324 | 461k | for (nibble, child_value) in children_values.iter().enumerate()28.8k { |
325 | 461k | if let Some(child_value) = child_value { |
326 | 461k | decoded_node_value.children[nibble] = child_value.as_deref(); |
327 | 461k | }0 |
328 | | // As documented, children are never removed. If `child_value` is `None`, we |
329 | | // intentionally keep the existing value in `decoded_node_value.children`. |
330 | | } |
331 | | |
332 | | // Re-encode the node value after its updates, and store it. |
333 | | // `encode` can return an error only if there's no children and no storage value. |
334 | | // Because we are guaranteed that the node was valid when we decoded it, and that |
335 | | // we only ever add a storage value or add children, we are sure that encoding |
336 | | // can't reach this situation. |
337 | 28.8k | let updated_node_value = |
338 | 28.8k | trie_node::encode(decoded_node_value) |
339 | 28.8k | .unwrap() |
340 | 112k | .fold(Vec::new(), |mut a, b| { |
341 | 112k | a.extend_from_slice(b.as_ref()); |
342 | 112k | a |
343 | 112k | }); _RNCNvMNtNtCsN16ciHI6Qf_7smoldot4trie12proof_encodeNtB4_12ProofBuilder13make_coherents0_0B8_ Line | Count | Source | 340 | 112k | .fold(Vec::new(), |mut a, b| { | 341 | 112k | a.extend_from_slice(b.as_ref()); | 342 | 112k | a | 343 | 112k | }); |
Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot4trie12proof_encodeNtB4_12ProofBuilder13make_coherents0_0B8_ |
344 | 28.8k | node_info.node_value = updated_node_value; |
345 | 0 | } |
346 | | |
347 | | // Jump to the next node in the order of iteration described at the top of this |
348 | | // function. |
349 | 28.8k | match iter.into_next_sibling() { |
350 | 9.26k | Err(n) => match n.into_parent() { |
351 | 7.76k | Some(p) => iter = p, |
352 | 1.50k | None => break, // Finished. |
353 | | }, |
354 | 19.5k | Ok(mut node) => { |
355 | 25.3k | iter = loop { |
356 | 25.3k | match node.into_first_child() { |
357 | 5.75k | Ok(c) => node = c, |
358 | 19.5k | Err(c) => break c, |
359 | | } |
360 | | }; |
361 | | } |
362 | | } |
363 | | } |
364 | 1.50k | } _RNvMNtNtCsN16ciHI6Qf_7smoldot4trie12proof_encodeNtB2_12ProofBuilder13make_coherent Line | Count | Source | 247 | 1.50k | pub fn make_coherent(&mut self) { | 248 | | // The implementation of this function iterates over the nodes of the trie in a specific | 249 | | // order: we start with the deepest child possible of the root node, then we jump from each | 250 | | // node to the deepest child possible of its next sibling. If a node is the last sibling, | 251 | | // jump to its parent. | 252 | | // This order of iteration guarantees that we traverse all the nodes of the trie, and that | 253 | | // we don't traverse a parent before having traversed of all its children. | 254 | | // When traversing a node, we calculate the hash of its children and update the node value | 255 | | // of that node. | 256 | | | 257 | | // Node currently being iterated. | 258 | 1.50k | let mut iter: trie_structure::NodeAccess<_> = { | 259 | 1.50k | let mut node = match self.trie_structure.root_node() { | 260 | 1.50k | Some(c) => c, | 261 | | None => { | 262 | | // Trie is empty. | 263 | 0 | return; | 264 | | } | 265 | | }; | 266 | | | 267 | 3.50k | loop { | 268 | 3.50k | match node.into_first_child() { | 269 | 2.00k | Ok(c) => node = c, | 270 | 1.50k | Err(c) => break c, | 271 | | } | 272 | | } | 273 | | }; | 274 | | | 275 | 28.8k | loop { | 276 | 28.8k | // Due to borrowing issues, we calculate ahead of time the values of the children of | 277 | 28.8k | // the node. | 278 | 28.8k | let children_values: [Option<Option<arrayvec::ArrayVec<u8, 32>>>; 16] = | 279 | 28.8k | array::from_fn(|nibble| { | 280 | | let nibble = nibble::Nibble::try_from(u8::try_from(nibble).unwrap()).unwrap(); | 281 | | | 282 | | if let Some(child_node_info) = iter.child_user_data(nibble) { | 283 | | if let Some(child_node_info) = child_node_info { | 284 | | // Node values of length < 32 are inlined. | 285 | | if child_node_info.node_value.len() < 32 { | 286 | | Some(Some(child_node_info.node_value.iter().copied().collect())) | 287 | | } else { | 288 | | Some(Some(blake2_hash(&child_node_info.node_value).into())) | 289 | | } | 290 | | } else { | 291 | | // Missing node value. Don't update anything. | 292 | | None | 293 | | } | 294 | | } else { | 295 | | Some(None) | 296 | | } | 297 | 28.8k | }); | 298 | | | 299 | | // We only update the current node if its node value has been inserted by the user. | 300 | 28.8k | if let Some(node_info) = iter.user_data().as_mut() { | 301 | | // We already make sure that node values are valid when inserting them. As such, | 302 | | // it is ok to `unwrap()` here. | 303 | 28.8k | let mut decoded_node_value = trie_node::decode(&node_info.node_value).unwrap(); | 304 | 28.8k | | 305 | 28.8k | // Update the hash of the storage value contained in `decoded_node_value`. | 306 | 28.8k | // This is done in a slightly weird way due to borrowing issues. | 307 | 28.8k | let storage_value_hash = node_info | 308 | 28.8k | .storage_value_node | 309 | 28.8k | .as_ref() | 310 | 28.8k | .map(|v| blake2_hash(v)); | 311 | 28.8k | debug_assert_eq!( | 312 | 28.8k | storage_value_hash.is_some(), | 313 | 28.8k | matches!( | 314 | 28.8k | decoded_node_value.storage_value, | 315 | | trie_node::StorageValue::Hashed(_) | 316 | | ) | 317 | | ); | 318 | 28.8k | if let Some(storage_value_hash0 ) = storage_value_hash.as_ref() { | 319 | 0 | decoded_node_value.storage_value = | 320 | 0 | trie_node::StorageValue::Hashed(storage_value_hash); | 321 | 28.8k | } | 322 | | | 323 | | // Update the children. | 324 | 461k | for (nibble, child_value) in children_values.iter().enumerate()28.8k { | 325 | 461k | if let Some(child_value) = child_value { | 326 | 461k | decoded_node_value.children[nibble] = child_value.as_deref(); | 327 | 461k | }0 | 328 | | // As documented, children are never removed. If `child_value` is `None`, we | 329 | | // intentionally keep the existing value in `decoded_node_value.children`. | 330 | | } | 331 | | | 332 | | // Re-encode the node value after its updates, and store it. | 333 | | // `encode` can return an error only if there's no children and no storage value. | 334 | | // Because we are guaranteed that the node was valid when we decoded it, and that | 335 | | // we only ever add a storage value or add children, we are sure that encoding | 336 | | // can't reach this situation. | 337 | 28.8k | let updated_node_value = | 338 | 28.8k | trie_node::encode(decoded_node_value) | 339 | 28.8k | .unwrap() | 340 | 28.8k | .fold(Vec::new(), |mut a, b| { | 341 | | a.extend_from_slice(b.as_ref()); | 342 | | a | 343 | 28.8k | }); | 344 | 28.8k | node_info.node_value = updated_node_value; | 345 | 0 | } | 346 | | | 347 | | // Jump to the next node in the order of iteration described at the top of this | 348 | | // function. | 349 | 28.8k | match iter.into_next_sibling() { | 350 | 9.26k | Err(n) => match n.into_parent() { | 351 | 7.76k | Some(p) => iter = p, | 352 | 1.50k | None => break, // Finished. | 353 | | }, | 354 | 19.5k | Ok(mut node) => { | 355 | 25.3k | iter = loop { | 356 | 25.3k | match node.into_first_child() { | 357 | 5.75k | Ok(c) => node = c, | 358 | 19.5k | Err(c) => break c, | 359 | | } | 360 | | }; | 361 | | } | 362 | | } | 363 | | } | 364 | 1.50k | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot4trie12proof_encodeNtB2_12ProofBuilder13make_coherent |
365 | | |
366 | | /// Builds the Merkle proof. |
367 | | /// |
368 | | /// This function returns an iterator of buffers. The actual Merkle proof consists in the |
369 | | /// concatenation of all the buffers. |
370 | | /// |
371 | | /// This function will succeed if no entry at all has been inserted in the [`ProofBuilder`]. |
372 | | /// |
373 | | /// This function will succeed even if [`ProofBuilder::missing_node_values`] returns a |
374 | | /// non-zero number of elements. However, the proof produced will then be invalid. |
375 | 1.50k | pub fn build(mut self) -> impl Iterator<Item = impl AsRef<[u8]> + Clone> { |
376 | 1.50k | // Index of the root node in the trie, if any. |
377 | 1.50k | let root_node_index = self.trie_structure.root_node().map(|n| n.node_index()1.50k ); _RNCNvMNtNtCsN16ciHI6Qf_7smoldot4trie12proof_encodeNtB4_12ProofBuilder5build0B8_ Line | Count | Source | 377 | 1.50k | let root_node_index = self.trie_structure.root_node().map(|n| n.node_index()); |
Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot4trie12proof_encodeNtB4_12ProofBuilder5build0B8_ |
378 | 1.50k | |
379 | 1.50k | // Collect the entries in the proof into a `HashSet` in order to de-duplicate them. |
380 | 1.50k | // TODO: we need to collect the indices into a Vec due to the API of trie_structure not allowing non-mutable access to nodes |
381 | 1.50k | let entries = self |
382 | 1.50k | .trie_structure |
383 | 1.50k | .iter_unordered() |
384 | 1.50k | .collect::<Vec<_>>() |
385 | 1.50k | .into_iter() |
386 | 28.8k | .flat_map(move |node_index| { |
387 | 28.8k | let Some(trie_structure_value28.8k ) = self |
388 | 28.8k | .trie_structure |
389 | 28.8k | .node_by_index(node_index) |
390 | 28.8k | .unwrap() |
391 | 28.8k | .user_data() |
392 | 28.8k | .take() |
393 | | // Ignore nodes whose value is missing. |
394 | | else { |
395 | 1 | return either::Right(iter::empty()); |
396 | | }; |
397 | | |
398 | | // Nodes of length < 32 should have been inlined within their parent or ancestor. |
399 | | // We thus skip them, unless they're the root node. |
400 | 28.8k | if root_node_index != Some(node_index) && trie_structure_value.node_value.len() < 3227.3k |
401 | | { |
402 | 8.88k | debug_assert!(trie_structure_value.storage_value_node.is_none()); |
403 | 8.88k | return either::Right(iter::empty()); |
404 | 19.9k | } |
405 | 19.9k | |
406 | 19.9k | // For each node, there are either one or two things to output: the node value, |
407 | 19.9k | // and the storage value. |
408 | 19.9k | either::Left( |
409 | 19.9k | iter::once(trie_structure_value.node_value) |
410 | 19.9k | .chain(trie_structure_value.storage_value_node), |
411 | 19.9k | ) |
412 | 28.8k | }) _RNCNvMNtNtCsN16ciHI6Qf_7smoldot4trie12proof_encodeNtB4_12ProofBuilder5builds_0B8_ Line | Count | Source | 386 | 28.8k | .flat_map(move |node_index| { | 387 | 28.8k | let Some(trie_structure_value28.8k ) = self | 388 | 28.8k | .trie_structure | 389 | 28.8k | .node_by_index(node_index) | 390 | 28.8k | .unwrap() | 391 | 28.8k | .user_data() | 392 | 28.8k | .take() | 393 | | // Ignore nodes whose value is missing. | 394 | | else { | 395 | 1 | return either::Right(iter::empty()); | 396 | | }; | 397 | | | 398 | | // Nodes of length < 32 should have been inlined within their parent or ancestor. | 399 | | // We thus skip them, unless they're the root node. | 400 | 28.8k | if root_node_index != Some(node_index) && trie_structure_value.node_value.len() < 3227.3k | 401 | | { | 402 | 8.88k | debug_assert!(trie_structure_value.storage_value_node.is_none()); | 403 | 8.88k | return either::Right(iter::empty()); | 404 | 19.9k | } | 405 | 19.9k | | 406 | 19.9k | // For each node, there are either one or two things to output: the node value, | 407 | 19.9k | // and the storage value. | 408 | 19.9k | either::Left( | 409 | 19.9k | iter::once(trie_structure_value.node_value) | 410 | 19.9k | .chain(trie_structure_value.storage_value_node), | 411 | 19.9k | ) | 412 | 28.8k | }) |
Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot4trie12proof_encodeNtB4_12ProofBuilder5builds_0B8_ |
413 | 1.50k | .collect::<hashbrown::HashSet<_, fnv::FnvBuildHasher>>(); |
414 | 1.50k | |
415 | 1.50k | // The first bytes of the proof contain the number of entries in the proof. |
416 | 1.50k | let num_entries_encoded = crate::util::encode_scale_compact_usize(entries.len()); |
417 | 1.50k | |
418 | 1.50k | // Add the size of each entry before each entry. |
419 | 19.9k | let entries = entries.into_iter().flat_map(|entry| { |
420 | 19.9k | let len = crate::util::encode_scale_compact_usize(entry.len()); |
421 | 19.9k | [either::Left(len), either::Right(entry)].into_iter() |
422 | 19.9k | }); _RNCNvMNtNtCsN16ciHI6Qf_7smoldot4trie12proof_encodeNtB4_12ProofBuilder5builds0_0B8_ Line | Count | Source | 419 | 19.9k | let entries = entries.into_iter().flat_map(|entry| { | 420 | 19.9k | let len = crate::util::encode_scale_compact_usize(entry.len()); | 421 | 19.9k | [either::Left(len), either::Right(entry)].into_iter() | 422 | 19.9k | }); |
Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot4trie12proof_encodeNtB4_12ProofBuilder5builds0_0B8_ |
423 | 1.50k | |
424 | 1.50k | iter::once(either::Left(num_entries_encoded)).chain(entries.into_iter().map(either::Right)) |
425 | 1.50k | } _RNvMNtNtCsN16ciHI6Qf_7smoldot4trie12proof_encodeNtB2_12ProofBuilder5build Line | Count | Source | 375 | 1.50k | pub fn build(mut self) -> impl Iterator<Item = impl AsRef<[u8]> + Clone> { | 376 | 1.50k | // Index of the root node in the trie, if any. | 377 | 1.50k | let root_node_index = self.trie_structure.root_node().map(|n| n.node_index()); | 378 | 1.50k | | 379 | 1.50k | // Collect the entries in the proof into a `HashSet` in order to de-duplicate them. | 380 | 1.50k | // TODO: we need to collect the indices into a Vec due to the API of trie_structure not allowing non-mutable access to nodes | 381 | 1.50k | let entries = self | 382 | 1.50k | .trie_structure | 383 | 1.50k | .iter_unordered() | 384 | 1.50k | .collect::<Vec<_>>() | 385 | 1.50k | .into_iter() | 386 | 1.50k | .flat_map(move |node_index| { | 387 | | let Some(trie_structure_value) = self | 388 | | .trie_structure | 389 | | .node_by_index(node_index) | 390 | | .unwrap() | 391 | | .user_data() | 392 | | .take() | 393 | | // Ignore nodes whose value is missing. | 394 | | else { | 395 | | return either::Right(iter::empty()); | 396 | | }; | 397 | | | 398 | | // Nodes of length < 32 should have been inlined within their parent or ancestor. | 399 | | // We thus skip them, unless they're the root node. | 400 | | if root_node_index != Some(node_index) && trie_structure_value.node_value.len() < 32 | 401 | | { | 402 | | debug_assert!(trie_structure_value.storage_value_node.is_none()); | 403 | | return either::Right(iter::empty()); | 404 | | } | 405 | | | 406 | | // For each node, there are either one or two things to output: the node value, | 407 | | // and the storage value. | 408 | | either::Left( | 409 | | iter::once(trie_structure_value.node_value) | 410 | | .chain(trie_structure_value.storage_value_node), | 411 | | ) | 412 | 1.50k | }) | 413 | 1.50k | .collect::<hashbrown::HashSet<_, fnv::FnvBuildHasher>>(); | 414 | 1.50k | | 415 | 1.50k | // The first bytes of the proof contain the number of entries in the proof. | 416 | 1.50k | let num_entries_encoded = crate::util::encode_scale_compact_usize(entries.len()); | 417 | 1.50k | | 418 | 1.50k | // Add the size of each entry before each entry. | 419 | 1.50k | let entries = entries.into_iter().flat_map(|entry| { | 420 | | let len = crate::util::encode_scale_compact_usize(entry.len()); | 421 | | [either::Left(len), either::Right(entry)].into_iter() | 422 | 1.50k | }); | 423 | 1.50k | | 424 | 1.50k | iter::once(either::Left(num_entries_encoded)).chain(entries.into_iter().map(either::Right)) | 425 | 1.50k | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot4trie12proof_encodeNtB2_12ProofBuilder5build |
426 | | |
427 | | /// Similar to [`ProofBuilder::build`], but returns a `Vec`. |
428 | | /// |
429 | | /// This is a convenience wrapper around [`ProofBuilder::build`]. |
430 | 1.50k | pub fn build_to_vec(self) -> Vec<u8> { |
431 | 41.3k | self.build().fold(Vec::new(), |mut a, b| { |
432 | 41.3k | a.extend_from_slice(b.as_ref()); |
433 | 41.3k | a |
434 | 41.3k | }) _RNCNvMNtNtCsN16ciHI6Qf_7smoldot4trie12proof_encodeNtB4_12ProofBuilder12build_to_vec0B8_ Line | Count | Source | 431 | 41.3k | self.build().fold(Vec::new(), |mut a, b| { | 432 | 41.3k | a.extend_from_slice(b.as_ref()); | 433 | 41.3k | a | 434 | 41.3k | }) |
Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot4trie12proof_encodeNtB4_12ProofBuilder12build_to_vec0B8_ |
435 | 1.50k | } _RNvMNtNtCsN16ciHI6Qf_7smoldot4trie12proof_encodeNtB2_12ProofBuilder12build_to_vec Line | Count | Source | 430 | 1.50k | pub fn build_to_vec(self) -> Vec<u8> { | 431 | 1.50k | self.build().fold(Vec::new(), |mut a, b| { | 432 | | a.extend_from_slice(b.as_ref()); | 433 | | a | 434 | 1.50k | }) | 435 | 1.50k | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot4trie12proof_encodeNtB2_12ProofBuilder12build_to_vec |
436 | | } |
437 | | |
438 | | impl Default for ProofBuilder { |
439 | 0 | fn default() -> Self { |
440 | 0 | Self::new() |
441 | 0 | } Unexecuted instantiation: _RNvXs_NtNtCsN16ciHI6Qf_7smoldot4trie12proof_encodeNtB4_12ProofBuilderNtNtCsaYZPK01V26L_4core7default7Default7default Unexecuted instantiation: _RNvXs_NtNtCseuYC0Zibziv_7smoldot4trie12proof_encodeNtB4_12ProofBuilderNtNtCsaYZPK01V26L_4core7default7Default7default |
442 | | } |
443 | | |
444 | 19.9k | fn blake2_hash(data: &[u8]) -> [u8; 32] { |
445 | 19.9k | <[u8; 32]>::try_from(blake2_rfc::blake2b::blake2b(32, &[], data).as_bytes()).unwrap() |
446 | 19.9k | } _RNvNtNtCsN16ciHI6Qf_7smoldot4trie12proof_encode11blake2_hash Line | Count | Source | 444 | 19.9k | fn blake2_hash(data: &[u8]) -> [u8; 32] { | 445 | 19.9k | <[u8; 32]>::try_from(blake2_rfc::blake2b::blake2b(32, &[], data).as_bytes()).unwrap() | 446 | 19.9k | } |
Unexecuted instantiation: _RNvNtNtCseuYC0Zibziv_7smoldot4trie12proof_encode11blake2_hash |
447 | | |
448 | | #[cfg(test)] |
449 | | mod tests { |
450 | | use super::super::{nibble, proof_decode, trie_node, trie_structure}; |
451 | | use core::{array, iter}; |
452 | | use rand::distributions::{Distribution as _, Uniform}; |
453 | | |
454 | | #[test] |
455 | 1 | fn empty_works() { |
456 | 1 | let proof_builder = super::ProofBuilder::new(); |
457 | 1 | assert_eq!(proof_builder.missing_node_values().count(), 0); |
458 | 1 | assert_eq!(proof_builder.build_to_vec(), &[0]); |
459 | 1 | } |
460 | | |
461 | | #[test] |
462 | | #[should_panic] |
463 | 1 | fn invalid_node_value_detected() { |
464 | 1 | let mut proof_builder = super::ProofBuilder::new(); |
465 | 1 | proof_builder.set_node_value( |
466 | 1 | &nibble::bytes_to_nibbles([1, 2, 3, 4].into_iter()).collect::<Vec<_>>(), |
467 | 1 | b"foobar", |
468 | 1 | None, |
469 | 1 | ); |
470 | 1 | } |
471 | | |
472 | | #[test] |
473 | 1 | fn one_root_node_works() { |
474 | 1 | let mut proof_builder = super::ProofBuilder::new(); |
475 | 1 | |
476 | 1 | proof_builder.set_node_value( |
477 | 1 | &nibble::bytes_to_nibbles([1, 2, 3, 4].into_iter()).collect::<Vec<_>>(), |
478 | 1 | &[72, 1, 2, 3, 4, 20, 104, 101, 108, 108, 111], |
479 | 1 | None, |
480 | 1 | ); |
481 | 1 | |
482 | 1 | assert_eq!(proof_builder.missing_node_values().count(), 0); |
483 | 1 | assert_eq!( |
484 | 1 | proof_builder.build_to_vec(), |
485 | 1 | &[4, 44, 72, 1, 2, 3, 4, 20, 104, 101, 108, 108, 111] |
486 | 1 | ); |
487 | 1 | } |
488 | | |
489 | | #[test] |
490 | 1 | fn one_node_non_root_detects_root_node() { |
491 | 1 | let mut proof_builder = super::ProofBuilder::new(); |
492 | 1 | |
493 | 1 | proof_builder.set_node_value( |
494 | 1 | &nibble::bytes_to_nibbles([1, 2, 3, 4].into_iter()).collect::<Vec<_>>(), |
495 | 1 | &[68, 3, 4, 20, 104, 101, 108, 108, 111], |
496 | 1 | None, |
497 | 1 | ); |
498 | 1 | |
499 | 1 | assert_eq!( |
500 | 1 | proof_builder.missing_node_values().collect::<Vec<_>>(), |
501 | 1 | vec![&[ |
502 | 1 | nibble::Nibble::try_from(0).unwrap(), |
503 | 1 | nibble::Nibble::try_from(1).unwrap(), |
504 | 1 | nibble::Nibble::try_from(0).unwrap() |
505 | 1 | ]] |
506 | 1 | ); |
507 | 1 | } |
508 | | |
509 | | #[test] |
510 | 1 | fn build_doesnt_panic_if_missing_node() { |
511 | 1 | let mut proof_builder = super::ProofBuilder::new(); |
512 | 1 | proof_builder.set_node_value( |
513 | 1 | &nibble::bytes_to_nibbles([1, 2, 3, 4].into_iter()).collect::<Vec<_>>(), |
514 | 1 | &[68, 3, 4, 20, 104, 101, 108, 108, 111], |
515 | 1 | None, |
516 | 1 | ); |
517 | 1 | let _ = proof_builder.build(); |
518 | 1 | } |
519 | | |
520 | | #[test] |
521 | 1 | fn build_random_proof() { |
522 | | // This test builds a proof of a randomly-generated trie, then fixes it, then checks |
523 | | // whether the decoder considers the proof as valid. |
524 | | |
525 | | // We repeat the test many times due to its random factor. |
526 | 1.50k | for _ in 0..1500 { |
527 | | // Build a trie with entries with randomly generated keys. |
528 | 1.50k | let mut trie = trie_structure::TrieStructure::new(); |
529 | 1.50k | // Generate at least one node, as otherwise the test panics. Empty proofs are however |
530 | 1.50k | // valid. |
531 | 1.50k | for _ in 0..Uniform::new_inclusive(1, 32).sample(&mut rand::thread_rng()) { |
532 | 24.2k | let mut key = Vec::new(); |
533 | 145k | for _ in 0..Uniform::new_inclusive(0, 12).sample(&mut rand::thread_rng()) { |
534 | 145k | key.push( |
535 | 145k | nibble::Nibble::try_from( |
536 | 145k | Uniform::new_inclusive(0, 15).sample(&mut rand::thread_rng()), |
537 | 145k | ) |
538 | 145k | .unwrap(), |
539 | 145k | ); |
540 | 145k | } |
541 | | |
542 | 24.2k | match trie.node(key.into_iter()) { |
543 | 22.3k | trie_structure::Entry::Vacant(e) => { |
544 | 22.3k | e.insert_storage_value().insert((), ()); |
545 | 22.3k | } |
546 | 921 | trie_structure::Entry::Occupied(trie_structure::NodeAccess::Branch(e)) => { |
547 | 921 | e.insert_storage_value(); |
548 | 921 | } |
549 | 969 | trie_structure::Entry::Occupied(trie_structure::NodeAccess::Storage(_)) => {} |
550 | | } |
551 | | } |
552 | | |
553 | | // Put the content of the trie into the proof builder. |
554 | 1.50k | let mut proof_builder = super::ProofBuilder::new(); |
555 | 28.8k | for node_index in trie.iter_unordered().collect::<Vec<_>>()1.50k { |
556 | 28.8k | let key = trie |
557 | 28.8k | .node_full_key_by_index(node_index) |
558 | 28.8k | .unwrap() |
559 | 28.8k | .collect::<Vec<_>>(); |
560 | 28.8k | |
561 | 28.8k | // This randomly-generated storage might end up not being used, but that's not |
562 | 28.8k | // problematic. |
563 | 28.8k | let mut storage_value = Vec::new(); |
564 | 926k | for _ in 0..Uniform::new_inclusive(0, 64).sample(&mut rand::thread_rng()) { |
565 | 926k | storage_value |
566 | 926k | .push(Uniform::new_inclusive(0, 255).sample(&mut rand::thread_rng())); |
567 | 926k | } |
568 | | |
569 | 28.8k | let node_value = trie_node::encode_to_vec(trie_node::Decoded { |
570 | 461k | children: array::from_fn(28.8k |nibble| { |
571 | 461k | let nibble = |
572 | 461k | nibble::Nibble::try_from(u8::try_from(nibble).unwrap()).unwrap(); |
573 | 461k | if trie |
574 | 461k | .node_by_index(node_index) |
575 | 461k | .unwrap() |
576 | 461k | .child_user_data(nibble) |
577 | 461k | .is_some() |
578 | | { |
579 | 27.3k | Some(&[][..]) |
580 | | } else { |
581 | 433k | None |
582 | | } |
583 | 461k | }), |
584 | 28.8k | partial_key: trie |
585 | 28.8k | .node_by_index(node_index) |
586 | 28.8k | .unwrap() |
587 | 28.8k | .partial_key() |
588 | 28.8k | .collect::<Vec<_>>() |
589 | 28.8k | .into_iter(), |
590 | 28.8k | storage_value: if trie.node_by_index(node_index).unwrap().has_storage_value() { |
591 | 23.2k | trie_node::StorageValue::Unhashed(&storage_value) |
592 | | } else { |
593 | 5.58k | trie_node::StorageValue::None |
594 | | }, |
595 | | }) |
596 | 28.8k | .unwrap(); |
597 | 28.8k | |
598 | 28.8k | proof_builder.set_node_value(&key, &node_value, None); |
599 | | } |
600 | | |
601 | | // Generate the proof. |
602 | 1.50k | assert!(proof_builder.missing_node_values().next().is_none()); |
603 | 1.50k | proof_builder.make_coherent(); |
604 | 1.50k | let trie_root_hash = proof_builder.trie_root_hash().unwrap(); |
605 | 1.50k | let proof = proof_builder.build_to_vec(); |
606 | 1.50k | |
607 | 1.50k | // Verify the correctness of the proof. |
608 | 1.50k | let proof = |
609 | 1.50k | proof_decode::decode_and_verify_proof(proof_decode::Config { proof }).unwrap(); |
610 | 1.50k | assert!(proof |
611 | 1.50k | .closest_descendant_merkle_value(&trie_root_hash, iter::empty()) |
612 | 1.50k | .is_ok()); |
613 | | } |
614 | 1 | } |
615 | | |
616 | | #[test] |
617 | 1 | fn identical_nodes_deduplicated() { |
618 | 1 | let mut proof_builder = super::ProofBuilder::new(); |
619 | 1 | |
620 | 1 | // One root node containing two children with an identical hash. |
621 | 1 | proof_builder.set_node_value( |
622 | 1 | &nibble::bytes_to_nibbles([].into_iter()).collect::<Vec<_>>(), |
623 | 1 | &[ |
624 | 1 | 128, 3, 0, 128, 205, 154, 249, 23, 88, 152, 61, 75, 170, 87, 182, 7, 127, 171, 174, |
625 | 1 | 60, 2, 124, 79, 166, 31, 155, 155, 185, 182, 155, 250, 63, 139, 166, 222, 184, 128, |
626 | 1 | 205, 154, 249, 23, 88, 152, 61, 75, 170, 87, 182, 7, 127, 171, 174, 60, 2, 124, 79, |
627 | 1 | 166, 31, 155, 155, 185, 182, 155, 250, 63, 139, 166, 222, 184, |
628 | 1 | ], |
629 | 1 | None, |
630 | 1 | ); |
631 | 1 | |
632 | 1 | // Two identical nodes but at a different key. |
633 | 1 | // Importantly, the node values are more than 32 bytes long to ensure that they're |
634 | 1 | // separate node and should not be inlined. |
635 | 1 | proof_builder.set_node_value( |
636 | 1 | &nibble::bytes_to_nibbles([0].into_iter()).collect::<Vec<_>>(), |
637 | 1 | &[ |
638 | 1 | 65, 0, 81, 1, 108, 111, 110, 103, 32, 115, 116, 111, 114, 97, 103, 101, 32, 118, |
639 | 1 | 97, 108, 117, 101, 32, 105, 110, 32, 111, 114, 100, 101, 114, 32, 116, 111, 32, |
640 | 1 | 101, 110, 115, 117, 114, 101, 32, 116, 104, 97, 116, 32, 116, 104, 101, 32, 110, |
641 | 1 | 111, 100, 101, 32, 118, 97, 108, 117, 101, 32, 105, 115, 32, 109, 111, 114, 101, |
642 | 1 | 32, 116, 104, 97, 110, 32, 51, 50, 32, 98, 121, 116, 101, 115, 32, 108, 111, 110, |
643 | 1 | 103, |
644 | 1 | ], |
645 | 1 | None, |
646 | 1 | ); |
647 | 1 | proof_builder.set_node_value( |
648 | 1 | &nibble::bytes_to_nibbles([0x10].into_iter()).collect::<Vec<_>>(), |
649 | 1 | &[ |
650 | 1 | 65, 0, 81, 1, 108, 111, 110, 103, 32, 115, 116, 111, 114, 97, 103, 101, 32, 118, |
651 | 1 | 97, 108, 117, 101, 32, 105, 110, 32, 111, 114, 100, 101, 114, 32, 116, 111, 32, |
652 | 1 | 101, 110, 115, 117, 114, 101, 32, 116, 104, 97, 116, 32, 116, 104, 101, 32, 110, |
653 | 1 | 111, 100, 101, 32, 118, 97, 108, 117, 101, 32, 105, 115, 32, 109, 111, 114, 101, |
654 | 1 | 32, 116, 104, 97, 110, 32, 51, 50, 32, 98, 121, 116, 101, 115, 32, 108, 111, 110, |
655 | 1 | 103, |
656 | 1 | ], |
657 | 1 | None, |
658 | 1 | ); |
659 | 1 | |
660 | 1 | // The proof builder should de-duplicate the two children, otherwise the proof is invalid. |
661 | 1 | proof_decode::decode_and_verify_proof(proof_decode::Config { |
662 | 1 | proof: proof_builder.build_to_vec(), |
663 | 1 | }) |
664 | 1 | .unwrap(); |
665 | 1 | } |
666 | | } |