/__w/smoldot/smoldot/repo/lib/src/trie/prefix_proof.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 | | //! Scanning, through trie proofs, the list of all keys that share a certain prefix. |
19 | | //! |
20 | | //! This module is a helper whose objective is to find out the list of all keys that start with |
21 | | //! a certain prefix by performing storage proofs. |
22 | | //! |
23 | | //! The total number of storage proofs required is equal to the maximum depth of the tree below |
24 | | //! the requested prefix, plus one. For example, if a tree has the nodes `[1, 5]`, `[1, 5, 8, 9]`, |
25 | | //! and `[1, 5, 8, 9, 2]`, then four queries are necessary to find all the keys whose prefix |
26 | | //! is `[1]`. |
27 | | |
28 | | // TODO: usage example |
29 | | |
30 | | use super::{nibble, proof_decode}; |
31 | | |
32 | | use alloc::{vec, vec::Vec}; |
33 | | use core::{fmt, iter, mem}; |
34 | | |
35 | | mod tests; |
36 | | |
37 | | /// Configuration to pass to [`prefix_scan`]. |
38 | | pub struct Config<'a> { |
39 | | /// Prefix that all the keys must share. |
40 | | pub prefix: &'a [u8], |
41 | | |
42 | | /// Merkle value (or node value) of the root node of the trie. |
43 | | /// |
44 | | /// > **Note**: The Merkle value and node value are always the same for the root node. |
45 | | pub trie_root_hash: [u8; 32], |
46 | | |
47 | | /// If `true`, then the final result will only contain [`StorageValue::Value`] entries and no |
48 | | /// [`StorageValue::Hash`] entry. Proofs that only contain a storage value hash when they are |
49 | | /// expected to contain the full value are considered as invalid. |
50 | | pub full_storage_values_required: bool, |
51 | | } |
52 | | |
53 | | /// Start a new scanning process. |
54 | 1 | pub fn prefix_scan(config: Config<'_>) -> PrefixScan { |
55 | 1 | PrefixScan { |
56 | 1 | trie_root_hash: config.trie_root_hash, |
57 | 1 | full_storage_values_required: config.full_storage_values_required, |
58 | 1 | next_queries: vec![( |
59 | 1 | nibble::bytes_to_nibbles(config.prefix.iter().copied()).collect(), |
60 | 1 | QueryTy::Exact, |
61 | 1 | )], |
62 | 1 | final_result: Vec::with_capacity(32), |
63 | 1 | } |
64 | 1 | } _RNvNtNtCsN16ciHI6Qf_7smoldot4trie12prefix_proof11prefix_scan Line | Count | Source | 54 | 1 | pub fn prefix_scan(config: Config<'_>) -> PrefixScan { | 55 | 1 | PrefixScan { | 56 | 1 | trie_root_hash: config.trie_root_hash, | 57 | 1 | full_storage_values_required: config.full_storage_values_required, | 58 | 1 | next_queries: vec![( | 59 | 1 | nibble::bytes_to_nibbles(config.prefix.iter().copied()).collect(), | 60 | 1 | QueryTy::Exact, | 61 | 1 | )], | 62 | 1 | final_result: Vec::with_capacity(32), | 63 | 1 | } | 64 | 1 | } |
Unexecuted instantiation: _RNvNtNtCseuYC0Zibziv_7smoldot4trie12prefix_proof11prefix_scan |
65 | | |
66 | | /// Scan of a prefix in progress. |
67 | | pub struct PrefixScan { |
68 | | trie_root_hash: [u8; 32], |
69 | | full_storage_values_required: bool, |
70 | | // TODO: we have lots of Vecs here; maybe find a way to optimize |
71 | | next_queries: Vec<(Vec<nibble::Nibble>, QueryTy)>, |
72 | | // TODO: we have lots of Vecs here; maybe find a way to optimize |
73 | | final_result: Vec<(Vec<u8>, StorageValue)>, |
74 | | } |
75 | | |
76 | | #[derive(Copy, Clone, Debug)] |
77 | | enum QueryTy { |
78 | | /// Expect to find a trie node with this exact key. |
79 | | Exact, |
80 | | /// The last nibble of the key is a dummy to force the remote to prove to us either that this |
81 | | /// node exists or that this node doesn't exist, and if it doesn't exist prove it by including |
82 | | /// the "actual" child that we're looking for in the proof. |
83 | | /// It is guaranteed that the trie contains a node whose key is the requested key without its |
84 | | /// last nibble. |
85 | | Direction, |
86 | | } |
87 | | |
88 | | impl PrefixScan { |
89 | | /// Returns the list of keys whose storage proof must be queried. |
90 | 0 | pub fn requested_keys( |
91 | 0 | &'_ self, |
92 | 0 | ) -> impl Iterator<Item = impl Iterator<Item = nibble::Nibble> + '_> + '_ { |
93 | 0 | self.next_queries.iter().map(|(l, _)| l.iter().copied()) Unexecuted instantiation: _RNCNvMNtNtCsN16ciHI6Qf_7smoldot4trie12prefix_proofNtB4_10PrefixScan14requested_keys0B8_ Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot4trie12prefix_proofNtB4_10PrefixScan14requested_keys0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot4trie12prefix_proofNtB4_10PrefixScan14requested_keys0B8_ |
94 | 0 | } Unexecuted instantiation: _RNvMNtNtCsN16ciHI6Qf_7smoldot4trie12prefix_proofNtB2_10PrefixScan14requested_keys Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot4trie12prefix_proofNtB2_10PrefixScan14requested_keys |
95 | | |
96 | | /// Returns whether the storage proof must include the storage values of the requested keys. |
97 | | /// |
98 | | /// > **Note**: This is always equal to [`Config::full_storage_values_required`]. |
99 | 0 | pub fn request_storage_values(&self) -> bool { |
100 | 0 | self.full_storage_values_required |
101 | 0 | } Unexecuted instantiation: _RNvMNtNtCsN16ciHI6Qf_7smoldot4trie12prefix_proofNtB2_10PrefixScan22request_storage_values Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot4trie12prefix_proofNtB2_10PrefixScan22request_storage_values |
102 | | |
103 | | /// Injects the proof presumably containing the keys returned by [`PrefixScan::requested_keys`]. |
104 | | /// |
105 | | /// Returns an error if the proof is invalid. In that case, `self` isn't modified. |
106 | | /// |
107 | | /// Contrary to [`PrefixScan::resume_partial`], a proof is considered valid only if it |
108 | | /// fulfills all the keys found in the list returned by [`PrefixScan::requested_keys`]. |
109 | 6 | pub fn resume_all_keys(self, proof: &[u8]) -> Result<ResumeOutcome, (Self, Error)> { |
110 | 6 | self.resume_inner(false, proof) |
111 | 6 | } _RNvMNtNtCsN16ciHI6Qf_7smoldot4trie12prefix_proofNtB2_10PrefixScan15resume_all_keys Line | Count | Source | 109 | 6 | pub fn resume_all_keys(self, proof: &[u8]) -> Result<ResumeOutcome, (Self, Error)> { | 110 | 6 | self.resume_inner(false, proof) | 111 | 6 | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot4trie12prefix_proofNtB2_10PrefixScan15resume_all_keys |
112 | | |
113 | | /// Injects the proof presumably containing the keys returned by [`PrefixScan::requested_keys`]. |
114 | | /// |
115 | | /// Returns an error if the proof is invalid. In that case, `self` isn't modified. |
116 | | /// |
117 | | /// Contrary to [`PrefixScan::resume_all_keys`], a proof is considered valid if it advances |
118 | | /// the request in any way. |
119 | 0 | pub fn resume_partial(self, proof: &[u8]) -> Result<ResumeOutcome, (Self, Error)> { |
120 | 0 | self.resume_inner(true, proof) |
121 | 0 | } Unexecuted instantiation: _RNvMNtNtCsN16ciHI6Qf_7smoldot4trie12prefix_proofNtB2_10PrefixScan14resume_partial Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot4trie12prefix_proofNtB2_10PrefixScan14resume_partial |
122 | | |
123 | | /// Injects the proof presumably containing the keys returned by [`PrefixScan::requested_keys`]. |
124 | | /// |
125 | | /// Returns an error if the proof is invalid. In that case, `self` isn't modified. |
126 | 6 | fn resume_inner( |
127 | 6 | mut self, |
128 | 6 | allow_incomplete_proof: bool, |
129 | 6 | proof: &[u8], |
130 | 6 | ) -> Result<ResumeOutcome, (Self, Error)> { |
131 | 6 | let decoded_proof = |
132 | 6 | match proof_decode::decode_and_verify_proof(proof_decode::Config { proof }) { |
133 | 6 | Ok(d) => d, |
134 | 0 | Err(err) => return Err((self, Error::InvalidProof(err))), |
135 | | }; |
136 | | |
137 | | // The code below contains an infinite loop. |
138 | | // At each iteration, we update the content of `non_terminal_queries` (by extracting its |
139 | | // value then putting a new value back before the next iteration). |
140 | | // While this is happening, `self.next_queries` is filled with queries that couldn't be |
141 | | // fulfilled with the proof that has been given. |
142 | | |
143 | 6 | let mut non_terminal_queries = mem::take(&mut self.next_queries); |
144 | | |
145 | | // The entire body is executed as long as the processing goes forward. |
146 | 17 | for is_first_iteration in iter::once(true).chain(iter::repeat(false))6 { |
147 | | // Filled with the queries to perform at the next iteration. |
148 | | // Capacity assumes a maximum of 2 children per node on average. This value was chosen |
149 | | // completely arbitrarily. |
150 | 17 | let mut next = Vec::with_capacity(non_terminal_queries.len() * 2); |
151 | 17 | |
152 | 17 | debug_assert!(!non_terminal_queries.is_empty()); |
153 | 3.73k | while let Some((query_key, query_ty3.71k )) = non_terminal_queries.pop() { |
154 | | // If some queries couldn't be fulfilled, and that `allow_incomplete_proof` is |
155 | | // `false`, return an error. This is only done at the first iteration, as otherwise |
156 | | // it is normal for some queries to not be fulfillable. |
157 | 3.71k | if !self.next_queries.is_empty() && is_first_iteration1.25k && !allow_incomplete_proof0 { |
158 | 0 | self.next_queries.extend(next.into_iter()); |
159 | 0 | return Err((self, Error::MissingProofEntry)); |
160 | 3.71k | } |
161 | | |
162 | | // Get the information from the proof about this key. |
163 | | // If the query type is "direction", then instead we look up the parent (that we |
164 | | // know for sure exists in the trie) then find the child. |
165 | 1.25k | let info = { |
166 | 3.71k | let info_of_node = match query_ty { |
167 | 1.25k | QueryTy::Exact => &query_key[..], |
168 | 2.45k | QueryTy::Direction => &query_key[..query_key.len() - 1], |
169 | | }; |
170 | | |
171 | | match ( |
172 | 3.71k | decoded_proof |
173 | 3.71k | .trie_node_info(&self.trie_root_hash, info_of_node.iter().copied()), |
174 | 3.71k | query_ty, |
175 | | ) { |
176 | 1.25k | (Ok(info), QueryTy::Exact) => info, |
177 | 2.45k | (Ok(info), QueryTy::Direction) => { |
178 | 2.45k | match info.children.child(query_key[query_key.len() - 1]) { |
179 | 1.22k | proof_decode::Child::InProof { child_key, .. } => { |
180 | 1.22k | // Rather than complicate this code, we just add the child to |
181 | 1.22k | // `next` (this time an `Exact` query) and process it during |
182 | 1.22k | // the next iteration. |
183 | 1.22k | next.push((child_key.collect::<Vec<_>>(), QueryTy::Exact)); |
184 | 1.22k | continue; |
185 | | } |
186 | | proof_decode::Child::AbsentFromProof { .. } => { |
187 | | // Node not in the proof. There's no point in adding this node |
188 | | // to `next` as we will fail again if we try to verify the |
189 | | // proof again. |
190 | 1.22k | self.next_queries.push((query_key, QueryTy::Direction)); |
191 | 1.22k | continue; |
192 | | } |
193 | | proof_decode::Child::NoChild => { |
194 | | // We know for sure that there is a child in this direction, |
195 | | // otherwise the query wouldn't have been added to this |
196 | | // state machine. |
197 | 0 | unreachable!() |
198 | | } |
199 | | } |
200 | | } |
201 | | (Err(proof_decode::IncompleteProofError { .. }), _) => { |
202 | | // Node not in the proof. There's no point in adding this node to |
203 | | // `next` as we will fail again if we try to verify the proof again. |
204 | 0 | self.next_queries.push((query_key, query_ty)); |
205 | 0 | continue; |
206 | | } |
207 | | } |
208 | | }; |
209 | | |
210 | 335 | if matches!( |
211 | 1.25k | info.storage_value, |
212 | | proof_decode::StorageValue::Known { .. } |
213 | | | proof_decode::StorageValue::HashKnownValueMissing(_) |
214 | | ) { |
215 | | // Fetch the storage value of this node. |
216 | 922 | let value = match info.storage_value0 { |
217 | | proof_decode::StorageValue::HashKnownValueMissing(_) |
218 | 0 | if self.full_storage_values_required => |
219 | 0 | { |
220 | 0 | // Storage values are being explicitly requested, but the proof |
221 | 0 | // doesn't include the desired storage value. |
222 | 0 | self.next_queries.push((query_key, query_ty)); |
223 | 0 | continue; |
224 | | } |
225 | 0 | proof_decode::StorageValue::HashKnownValueMissing(hash) => { |
226 | 0 | debug_assert!(!self.full_storage_values_required); |
227 | 0 | StorageValue::Hash(*hash) |
228 | | } |
229 | 922 | proof_decode::StorageValue::Known { value, .. } => { |
230 | 922 | // TODO: considering storing the storage proofs instead of copying individual storage values? |
231 | 922 | StorageValue::Value(value.to_vec()) |
232 | | } |
233 | 0 | proof_decode::StorageValue::None => unreachable!(), |
234 | | }; |
235 | | |
236 | | // Trie nodes with a value are always aligned to "bytes-keys". In other words, |
237 | | // the number of nibbles is always even. |
238 | 922 | debug_assert_eq!(query_key.len() % 2, 0); |
239 | 922 | let key = query_key |
240 | 922 | .chunks(2) |
241 | 66.3k | .map(|n| (u8::from(n[0]) << 4) | u8::from(n[1])) _RNCNvMNtNtCsN16ciHI6Qf_7smoldot4trie12prefix_proofNtB4_10PrefixScan12resume_inner0B8_ Line | Count | Source | 241 | 66.3k | .map(|n| (u8::from(n[0]) << 4) | u8::from(n[1])) |
Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot4trie12prefix_proofNtB4_10PrefixScan12resume_inner0B8_ |
242 | 922 | .collect::<Vec<_>>(); |
243 | 922 | |
244 | 922 | // Insert in final results, making sure we check for duplicates. |
245 | 424k | debug_assert!(!self.final_result.iter().any(922 |(n, _)| *n == key)922 ); _RNCNvMNtNtCsN16ciHI6Qf_7smoldot4trie12prefix_proofNtB4_10PrefixScan12resume_inners_0B8_ Line | Count | Source | 245 | 424k | debug_assert!(!self.final_result.iter().any(|(n, _)| *n == key)); |
Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot4trie12prefix_proofNtB4_10PrefixScan12resume_inners_0B8_ |
246 | 922 | self.final_result.push((key, value)); |
247 | 335 | } |
248 | | |
249 | | // For each child of the node, put into `next` the key that goes towards this |
250 | | // child. |
251 | 20.1k | for (nibble, child) in info.children.children().enumerate()1.25k { |
252 | 20.1k | match child { |
253 | 18.8k | proof_decode::Child::NoChild => continue, |
254 | 1.22k | proof_decode::Child::AbsentFromProof { .. } => { |
255 | 1.22k | let mut direction = query_key.clone(); |
256 | 1.22k | direction.push( |
257 | 1.22k | nibble::Nibble::try_from(u8::try_from(nibble).unwrap()).unwrap(), |
258 | 1.22k | ); |
259 | 1.22k | next.push((direction, QueryTy::Direction)); |
260 | 1.22k | } |
261 | 28 | proof_decode::Child::InProof { child_key, .. } => { |
262 | 28 | next.push((child_key.collect::<Vec<_>>(), QueryTy::Exact)) |
263 | | } |
264 | | } |
265 | | } |
266 | | } |
267 | | |
268 | | // Finished when nothing more to request. |
269 | 17 | if next.is_empty() && self.next_queries.is_empty()6 { |
270 | 1 | return Ok(ResumeOutcome::Success { |
271 | 1 | entries: self.final_result, |
272 | 1 | full_storage_values_required: self.full_storage_values_required, |
273 | 1 | }); |
274 | 16 | } |
275 | 16 | |
276 | 16 | // If we have failed to make any progress during this iteration, return |
277 | 16 | // either `Ok(InProgress)` or an error depending on whether this is the first |
278 | 16 | // iteration. |
279 | 16 | if next.is_empty() { |
280 | 5 | debug_assert!(!self.next_queries.is_empty()); |
281 | 5 | if is_first_iteration { |
282 | 0 | return Err((self, Error::MissingProofEntry)); |
283 | | } else { |
284 | 5 | break; |
285 | | } |
286 | 11 | } |
287 | 11 | |
288 | 11 | // Update `non_terminal_queries` for the next iteration. |
289 | 11 | non_terminal_queries = next; |
290 | | } |
291 | | |
292 | 5 | Ok(ResumeOutcome::InProgress(self)) |
293 | 6 | } _RNvMNtNtCsN16ciHI6Qf_7smoldot4trie12prefix_proofNtB2_10PrefixScan12resume_inner Line | Count | Source | 126 | 6 | fn resume_inner( | 127 | 6 | mut self, | 128 | 6 | allow_incomplete_proof: bool, | 129 | 6 | proof: &[u8], | 130 | 6 | ) -> Result<ResumeOutcome, (Self, Error)> { | 131 | 6 | let decoded_proof = | 132 | 6 | match proof_decode::decode_and_verify_proof(proof_decode::Config { proof }) { | 133 | 6 | Ok(d) => d, | 134 | 0 | Err(err) => return Err((self, Error::InvalidProof(err))), | 135 | | }; | 136 | | | 137 | | // The code below contains an infinite loop. | 138 | | // At each iteration, we update the content of `non_terminal_queries` (by extracting its | 139 | | // value then putting a new value back before the next iteration). | 140 | | // While this is happening, `self.next_queries` is filled with queries that couldn't be | 141 | | // fulfilled with the proof that has been given. | 142 | | | 143 | 6 | let mut non_terminal_queries = mem::take(&mut self.next_queries); | 144 | | | 145 | | // The entire body is executed as long as the processing goes forward. | 146 | 17 | for is_first_iteration in iter::once(true).chain(iter::repeat(false))6 { | 147 | | // Filled with the queries to perform at the next iteration. | 148 | | // Capacity assumes a maximum of 2 children per node on average. This value was chosen | 149 | | // completely arbitrarily. | 150 | 17 | let mut next = Vec::with_capacity(non_terminal_queries.len() * 2); | 151 | 17 | | 152 | 17 | debug_assert!(!non_terminal_queries.is_empty()); | 153 | 3.73k | while let Some((query_key, query_ty3.71k )) = non_terminal_queries.pop() { | 154 | | // If some queries couldn't be fulfilled, and that `allow_incomplete_proof` is | 155 | | // `false`, return an error. This is only done at the first iteration, as otherwise | 156 | | // it is normal for some queries to not be fulfillable. | 157 | 3.71k | if !self.next_queries.is_empty() && is_first_iteration1.25k && !allow_incomplete_proof0 { | 158 | 0 | self.next_queries.extend(next.into_iter()); | 159 | 0 | return Err((self, Error::MissingProofEntry)); | 160 | 3.71k | } | 161 | | | 162 | | // Get the information from the proof about this key. | 163 | | // If the query type is "direction", then instead we look up the parent (that we | 164 | | // know for sure exists in the trie) then find the child. | 165 | 1.25k | let info = { | 166 | 3.71k | let info_of_node = match query_ty { | 167 | 1.25k | QueryTy::Exact => &query_key[..], | 168 | 2.45k | QueryTy::Direction => &query_key[..query_key.len() - 1], | 169 | | }; | 170 | | | 171 | | match ( | 172 | 3.71k | decoded_proof | 173 | 3.71k | .trie_node_info(&self.trie_root_hash, info_of_node.iter().copied()), | 174 | 3.71k | query_ty, | 175 | | ) { | 176 | 1.25k | (Ok(info), QueryTy::Exact) => info, | 177 | 2.45k | (Ok(info), QueryTy::Direction) => { | 178 | 2.45k | match info.children.child(query_key[query_key.len() - 1]) { | 179 | 1.22k | proof_decode::Child::InProof { child_key, .. } => { | 180 | 1.22k | // Rather than complicate this code, we just add the child to | 181 | 1.22k | // `next` (this time an `Exact` query) and process it during | 182 | 1.22k | // the next iteration. | 183 | 1.22k | next.push((child_key.collect::<Vec<_>>(), QueryTy::Exact)); | 184 | 1.22k | continue; | 185 | | } | 186 | | proof_decode::Child::AbsentFromProof { .. } => { | 187 | | // Node not in the proof. There's no point in adding this node | 188 | | // to `next` as we will fail again if we try to verify the | 189 | | // proof again. | 190 | 1.22k | self.next_queries.push((query_key, QueryTy::Direction)); | 191 | 1.22k | continue; | 192 | | } | 193 | | proof_decode::Child::NoChild => { | 194 | | // We know for sure that there is a child in this direction, | 195 | | // otherwise the query wouldn't have been added to this | 196 | | // state machine. | 197 | 0 | unreachable!() | 198 | | } | 199 | | } | 200 | | } | 201 | | (Err(proof_decode::IncompleteProofError { .. }), _) => { | 202 | | // Node not in the proof. There's no point in adding this node to | 203 | | // `next` as we will fail again if we try to verify the proof again. | 204 | 0 | self.next_queries.push((query_key, query_ty)); | 205 | 0 | continue; | 206 | | } | 207 | | } | 208 | | }; | 209 | | | 210 | 335 | if matches!( | 211 | 1.25k | info.storage_value, | 212 | | proof_decode::StorageValue::Known { .. } | 213 | | | proof_decode::StorageValue::HashKnownValueMissing(_) | 214 | | ) { | 215 | | // Fetch the storage value of this node. | 216 | 922 | let value = match info.storage_value0 { | 217 | | proof_decode::StorageValue::HashKnownValueMissing(_) | 218 | 0 | if self.full_storage_values_required => | 219 | 0 | { | 220 | 0 | // Storage values are being explicitly requested, but the proof | 221 | 0 | // doesn't include the desired storage value. | 222 | 0 | self.next_queries.push((query_key, query_ty)); | 223 | 0 | continue; | 224 | | } | 225 | 0 | proof_decode::StorageValue::HashKnownValueMissing(hash) => { | 226 | 0 | debug_assert!(!self.full_storage_values_required); | 227 | 0 | StorageValue::Hash(*hash) | 228 | | } | 229 | 922 | proof_decode::StorageValue::Known { value, .. } => { | 230 | 922 | // TODO: considering storing the storage proofs instead of copying individual storage values? | 231 | 922 | StorageValue::Value(value.to_vec()) | 232 | | } | 233 | 0 | proof_decode::StorageValue::None => unreachable!(), | 234 | | }; | 235 | | | 236 | | // Trie nodes with a value are always aligned to "bytes-keys". In other words, | 237 | | // the number of nibbles is always even. | 238 | 922 | debug_assert_eq!(query_key.len() % 2, 0); | 239 | 922 | let key = query_key | 240 | 922 | .chunks(2) | 241 | 922 | .map(|n| (u8::from(n[0]) << 4) | u8::from(n[1])) | 242 | 922 | .collect::<Vec<_>>(); | 243 | 922 | | 244 | 922 | // Insert in final results, making sure we check for duplicates. | 245 | 922 | debug_assert!(!self.final_result.iter().any(|(n, _)| *n == key)); | 246 | 922 | self.final_result.push((key, value)); | 247 | 335 | } | 248 | | | 249 | | // For each child of the node, put into `next` the key that goes towards this | 250 | | // child. | 251 | 20.1k | for (nibble, child) in info.children.children().enumerate()1.25k { | 252 | 20.1k | match child { | 253 | 18.8k | proof_decode::Child::NoChild => continue, | 254 | 1.22k | proof_decode::Child::AbsentFromProof { .. } => { | 255 | 1.22k | let mut direction = query_key.clone(); | 256 | 1.22k | direction.push( | 257 | 1.22k | nibble::Nibble::try_from(u8::try_from(nibble).unwrap()).unwrap(), | 258 | 1.22k | ); | 259 | 1.22k | next.push((direction, QueryTy::Direction)); | 260 | 1.22k | } | 261 | 28 | proof_decode::Child::InProof { child_key, .. } => { | 262 | 28 | next.push((child_key.collect::<Vec<_>>(), QueryTy::Exact)) | 263 | | } | 264 | | } | 265 | | } | 266 | | } | 267 | | | 268 | | // Finished when nothing more to request. | 269 | 17 | if next.is_empty() && self.next_queries.is_empty()6 { | 270 | 1 | return Ok(ResumeOutcome::Success { | 271 | 1 | entries: self.final_result, | 272 | 1 | full_storage_values_required: self.full_storage_values_required, | 273 | 1 | }); | 274 | 16 | } | 275 | 16 | | 276 | 16 | // If we have failed to make any progress during this iteration, return | 277 | 16 | // either `Ok(InProgress)` or an error depending on whether this is the first | 278 | 16 | // iteration. | 279 | 16 | if next.is_empty() { | 280 | 5 | debug_assert!(!self.next_queries.is_empty()); | 281 | 5 | if is_first_iteration { | 282 | 0 | return Err((self, Error::MissingProofEntry)); | 283 | | } else { | 284 | 5 | break; | 285 | | } | 286 | 11 | } | 287 | 11 | | 288 | 11 | // Update `non_terminal_queries` for the next iteration. | 289 | 11 | non_terminal_queries = next; | 290 | | } | 291 | | | 292 | 5 | Ok(ResumeOutcome::InProgress(self)) | 293 | 6 | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot4trie12prefix_proofNtB2_10PrefixScan12resume_inner |
294 | | } |
295 | | |
296 | | impl fmt::Debug for PrefixScan { |
297 | 0 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { |
298 | 0 | f.debug_struct("PrefixScan").finish() |
299 | 0 | } Unexecuted instantiation: _RNvXs_NtNtCsN16ciHI6Qf_7smoldot4trie12prefix_proofNtB4_10PrefixScanNtNtCsaYZPK01V26L_4core3fmt5Debug3fmt Unexecuted instantiation: _RNvXs_NtNtCseuYC0Zibziv_7smoldot4trie12prefix_proofNtB4_10PrefixScanNtNtCsaYZPK01V26L_4core3fmt5Debug3fmt |
300 | | } |
301 | | |
302 | | /// Outcome of calling [`PrefixScan::resume_all_keys`] or [`PrefixScan::resume_partial`]. |
303 | | #[derive(Debug)] |
304 | | pub enum ResumeOutcome { |
305 | | /// Scan must continue with the next storage proof query. |
306 | | InProgress(PrefixScan), |
307 | | /// Scan has succeeded. |
308 | | Success { |
309 | | /// List of entries who key starts with the requested prefix. |
310 | | entries: Vec<(Vec<u8>, StorageValue)>, |
311 | | /// Value that was passed as [`Config::full_storage_values_required`]. |
312 | | full_storage_values_required: bool, |
313 | | }, |
314 | | } |
315 | | |
316 | | /// Storage value of a trie entry. See [`ResumeOutcome::Success::entries`]. |
317 | | #[derive(Debug)] |
318 | | pub enum StorageValue { |
319 | | /// Value was found in the proof. |
320 | | Value(Vec<u8>), |
321 | | /// Only the hash of the value was found in the proof. |
322 | | /// |
323 | | /// Never happens if [`Config::full_storage_values_required`] was `true`. |
324 | | Hash([u8; 32]), |
325 | | } |
326 | | |
327 | | /// Possible error returned by [`PrefixScan::resume_all_keys`] or [`PrefixScan::resume_partial`]. |
328 | 0 | #[derive(Debug, Clone, derive_more::Display)] Unexecuted instantiation: _RNvXs7_NtNtCsN16ciHI6Qf_7smoldot4trie12prefix_proofNtB5_5ErrorNtNtCsaYZPK01V26L_4core3fmt7Display3fmt Unexecuted instantiation: _RNvXs7_NtNtCseuYC0Zibziv_7smoldot4trie12prefix_proofNtB5_5ErrorNtNtCsaYZPK01V26L_4core3fmt7Display3fmt |
329 | | pub enum Error { |
330 | | /// The proof has an invalid format. |
331 | | #[display(fmt = "{_0}")] |
332 | | InvalidProof(proof_decode::Error), |
333 | | /// One or more entries in the proof are missing. |
334 | | MissingProofEntry, |
335 | | } |