sp_state_machine/
trie_backend.rs

1// This file is part of Substrate.
2
3// Copyright (C) Parity Technologies (UK) Ltd.
4// SPDX-License-Identifier: Apache-2.0
5
6// Licensed under the Apache License, Version 2.0 (the "License");
7// you may not use this file except in compliance with the License.
8// You may obtain a copy of the License at
9//
10// 	http://www.apache.org/licenses/LICENSE-2.0
11//
12// Unless required by applicable law or agreed to in writing, software
13// distributed under the License is distributed on an "AS IS" BASIS,
14// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15// See the License for the specific language governing permissions and
16// limitations under the License.
17
18//! Trie-based state machine backend.
19
20#[cfg(feature = "std")]
21use crate::backend::AsTrieBackend;
22use crate::{
23	backend::{IterArgs, StorageIterator},
24	trie_backend_essence::{RawIter, TrieBackendEssence, TrieBackendStorage},
25	Backend, StorageKey, StorageValue,
26};
27
28use codec::Codec;
29#[cfg(feature = "std")]
30use hash_db::HashDB;
31use hash_db::Hasher;
32use sp_core::storage::{ChildInfo, StateVersion};
33#[cfg(feature = "std")]
34use sp_trie::{
35	cache::{LocalTrieCache, TrieCache},
36	MemoryDB,
37};
38#[cfg(not(feature = "std"))]
39use sp_trie::{Error, NodeCodec};
40use sp_trie::{MerkleValue, PrefixedMemoryDB, StorageProof, TrieRecorderProvider};
41
42use trie_db::TrieCache as TrieCacheT;
43#[cfg(not(feature = "std"))]
44use trie_db::{node::NodeOwned, CachedValue};
45
46/// A provider of trie caches that are compatible with [`trie_db::TrieDB`].
47pub trait TrieCacheProvider<H: Hasher> {
48	/// Cache type that implements [`trie_db::TrieCache`].
49	type Cache<'a>: TrieCacheT<sp_trie::NodeCodec<H>> + 'a
50	where
51		Self: 'a;
52
53	/// Return a [`trie_db::TrieDB`] compatible cache.
54	///
55	/// The `storage_root` parameter *must* be the storage root of the trie this cache is used for.
56	///
57	/// NOTE: Implementors should use the `storage_root` to differentiate between storage keys that
58	/// may belong to different tries.
59	fn as_trie_db_cache(&self, storage_root: H::Out) -> Self::Cache<'_>;
60
61	/// Returns a cache that can be used with a [`trie_db::TrieDBMut`].
62	///
63	/// When finished with the operation on the trie, it is required to call [`Self::merge`] to
64	/// merge the cached items for the correct `storage_root`.
65	fn as_trie_db_mut_cache(&self) -> Self::Cache<'_>;
66
67	/// Merge the cached data in `other` into the provider using the given `new_root`.
68	///
69	/// This must be used for the cache returned by [`Self::as_trie_db_mut_cache`] as otherwise the
70	/// cached data is just thrown away.
71	fn merge<'a>(&'a self, other: Self::Cache<'a>, new_root: H::Out);
72}
73
74#[cfg(feature = "std")]
75impl<H: Hasher> TrieCacheProvider<H> for LocalTrieCache<H> {
76	type Cache<'a> = TrieCache<'a, H> where H: 'a;
77
78	fn as_trie_db_cache(&self, storage_root: H::Out) -> Self::Cache<'_> {
79		self.as_trie_db_cache(storage_root)
80	}
81
82	fn as_trie_db_mut_cache(&self) -> Self::Cache<'_> {
83		self.as_trie_db_mut_cache()
84	}
85
86	fn merge<'a>(&'a self, other: Self::Cache<'a>, new_root: H::Out) {
87		other.merge_into(self, new_root)
88	}
89}
90
91#[cfg(feature = "std")]
92impl<H: Hasher> TrieCacheProvider<H> for &LocalTrieCache<H> {
93	type Cache<'a> = TrieCache<'a, H> where Self: 'a;
94
95	fn as_trie_db_cache(&self, storage_root: H::Out) -> Self::Cache<'_> {
96		(*self).as_trie_db_cache(storage_root)
97	}
98
99	fn as_trie_db_mut_cache(&self) -> Self::Cache<'_> {
100		(*self).as_trie_db_mut_cache()
101	}
102
103	fn merge<'a>(&'a self, other: Self::Cache<'a>, new_root: H::Out) {
104		other.merge_into(self, new_root)
105	}
106}
107
108/// Cache provider that allows construction of a [`TrieBackend`] and satisfies the requirements, but
109/// can never be instantiated.
110#[cfg(not(feature = "std"))]
111pub struct UnimplementedCacheProvider<H> {
112	// Not strictly necessary, but the H bound allows to use this as a drop-in
113	// replacement for the `LocalTrieCache` in no-std contexts.
114	_phantom: core::marker::PhantomData<H>,
115}
116
117#[cfg(not(feature = "std"))]
118impl<H: Hasher> trie_db::TrieCache<NodeCodec<H>> for UnimplementedCacheProvider<H> {
119	fn lookup_value_for_key(&mut self, _key: &[u8]) -> Option<&CachedValue<H::Out>> {
120		unimplemented!()
121	}
122
123	fn cache_value_for_key(&mut self, _key: &[u8], _value: CachedValue<H::Out>) {
124		unimplemented!()
125	}
126
127	fn get_or_insert_node(
128		&mut self,
129		_hash: H::Out,
130		_fetch_node: &mut dyn FnMut() -> trie_db::Result<NodeOwned<H::Out>, H::Out, Error<H::Out>>,
131	) -> trie_db::Result<&NodeOwned<H::Out>, H::Out, Error<H::Out>> {
132		unimplemented!()
133	}
134
135	fn get_node(&mut self, _hash: &H::Out) -> Option<&NodeOwned<H::Out>> {
136		unimplemented!()
137	}
138}
139
140#[cfg(not(feature = "std"))]
141impl<H: Hasher> TrieCacheProvider<H> for UnimplementedCacheProvider<H> {
142	type Cache<'a> = UnimplementedCacheProvider<H> where H: 'a;
143
144	fn as_trie_db_cache(&self, _storage_root: <H as Hasher>::Out) -> Self::Cache<'_> {
145		unimplemented!()
146	}
147
148	fn as_trie_db_mut_cache(&self) -> Self::Cache<'_> {
149		unimplemented!()
150	}
151
152	fn merge<'a>(&'a self, _other: Self::Cache<'a>, _new_root: <H as Hasher>::Out) {
153		unimplemented!()
154	}
155}
156
157/// Recorder provider that allows construction of a [`TrieBackend`] and satisfies the requirements,
158/// but can never be instantiated.
159#[cfg(not(feature = "std"))]
160pub struct UnimplementedRecorderProvider<H> {
161	// Not strictly necessary, but the H bound allows to use this as a drop-in
162	// replacement for the [`sp_trie::recorder::Recorder`] in no-std contexts.
163	_phantom: core::marker::PhantomData<H>,
164}
165
166#[cfg(not(feature = "std"))]
167impl<H: Hasher> trie_db::TrieRecorder<H::Out> for UnimplementedRecorderProvider<H> {
168	fn record<'a>(&mut self, _access: trie_db::TrieAccess<'a, H::Out>) {
169		unimplemented!()
170	}
171
172	fn trie_nodes_recorded_for_key(&self, _key: &[u8]) -> trie_db::RecordedForKey {
173		unimplemented!()
174	}
175}
176
177#[cfg(not(feature = "std"))]
178impl<H: Hasher> TrieRecorderProvider<H> for UnimplementedRecorderProvider<H> {
179	type Recorder<'a> = UnimplementedRecorderProvider<H> where H: 'a;
180
181	fn drain_storage_proof(self) -> Option<StorageProof> {
182		unimplemented!()
183	}
184
185	fn as_trie_recorder(&self, _storage_root: H::Out) -> Self::Recorder<'_> {
186		unimplemented!()
187	}
188}
189
190#[cfg(feature = "std")]
191type DefaultCache<H> = LocalTrieCache<H>;
192
193#[cfg(not(feature = "std"))]
194type DefaultCache<H> = UnimplementedCacheProvider<H>;
195
196#[cfg(feature = "std")]
197type DefaultRecorder<H> = sp_trie::recorder::Recorder<H>;
198
199#[cfg(not(feature = "std"))]
200type DefaultRecorder<H> = UnimplementedRecorderProvider<H>;
201
202/// Builder for creating a [`TrieBackend`].
203pub struct TrieBackendBuilder<
204	S: TrieBackendStorage<H>,
205	H: Hasher,
206	C = DefaultCache<H>,
207	R = DefaultRecorder<H>,
208> {
209	storage: S,
210	root: H::Out,
211	recorder: Option<R>,
212	cache: Option<C>,
213}
214
215impl<S, H> TrieBackendBuilder<S, H>
216where
217	S: TrieBackendStorage<H>,
218	H: Hasher,
219{
220	/// Create a new builder instance.
221	pub fn new(storage: S, root: H::Out) -> Self {
222		Self { storage, root, recorder: None, cache: None }
223	}
224}
225
226impl<S, H, C, R> TrieBackendBuilder<S, H, C, R>
227where
228	S: TrieBackendStorage<H>,
229	H: Hasher,
230{
231	/// Create a new builder instance.
232	pub fn new_with_cache(storage: S, root: H::Out, cache: C) -> Self {
233		Self { storage, root, recorder: None, cache: Some(cache) }
234	}
235	/// Wrap the given [`TrieBackend`].
236	///
237	/// This can be used for example if all accesses to the trie should
238	/// be recorded while some other functionality still uses the non-recording
239	/// backend.
240	///
241	/// The backend storage and the cache will be taken from `other`.
242	pub fn wrap(other: &TrieBackend<S, H, C, R>) -> TrieBackendBuilder<&S, H, &C, R> {
243		TrieBackendBuilder {
244			storage: other.essence.backend_storage(),
245			root: *other.essence.root(),
246			recorder: None,
247			cache: other.essence.trie_node_cache.as_ref(),
248		}
249	}
250
251	/// Use the given optional `recorder` for the to be configured [`TrieBackend`].
252	pub fn with_optional_recorder(self, recorder: Option<R>) -> Self {
253		Self { recorder, ..self }
254	}
255
256	/// Use the given `recorder` for the to be configured [`TrieBackend`].
257	pub fn with_recorder(self, recorder: R) -> Self {
258		Self { recorder: Some(recorder), ..self }
259	}
260
261	/// Use the given optional `cache` for the to be configured [`TrieBackend`].
262	pub fn with_optional_cache<LC>(self, cache: Option<LC>) -> TrieBackendBuilder<S, H, LC, R> {
263		TrieBackendBuilder {
264			cache,
265			root: self.root,
266			storage: self.storage,
267			recorder: self.recorder,
268		}
269	}
270
271	/// Use the given `cache` for the to be configured [`TrieBackend`].
272	pub fn with_cache<LC>(self, cache: LC) -> TrieBackendBuilder<S, H, LC, R> {
273		TrieBackendBuilder {
274			cache: Some(cache),
275			root: self.root,
276			storage: self.storage,
277			recorder: self.recorder,
278		}
279	}
280
281	/// Build the configured [`TrieBackend`].
282	pub fn build(self) -> TrieBackend<S, H, C, R> {
283		TrieBackend {
284			essence: TrieBackendEssence::new_with_cache_and_recorder(
285				self.storage,
286				self.root,
287				self.cache,
288				self.recorder,
289			),
290			next_storage_key_cache: Default::default(),
291		}
292	}
293}
294
295/// A cached iterator.
296struct CachedIter<S, H, C, R>
297where
298	H: Hasher,
299{
300	last_key: alloc::vec::Vec<u8>,
301	iter: RawIter<S, H, C, R>,
302}
303
304impl<S, H, C, R> Default for CachedIter<S, H, C, R>
305where
306	H: Hasher,
307{
308	fn default() -> Self {
309		Self { last_key: Default::default(), iter: Default::default() }
310	}
311}
312
313#[cfg(feature = "std")]
314type CacheCell<T> = parking_lot::Mutex<T>;
315
316#[cfg(not(feature = "std"))]
317type CacheCell<T> = core::cell::RefCell<T>;
318
319#[cfg(feature = "std")]
320fn access_cache<T, R>(cell: &CacheCell<T>, callback: impl FnOnce(&mut T) -> R) -> R {
321	callback(&mut *cell.lock())
322}
323
324#[cfg(not(feature = "std"))]
325fn access_cache<T, R>(cell: &CacheCell<T>, callback: impl FnOnce(&mut T) -> R) -> R {
326	callback(&mut *cell.borrow_mut())
327}
328
329/// Patricia trie-based backend. Transaction type is an overlay of changes to commit.
330pub struct TrieBackend<
331	S: TrieBackendStorage<H>,
332	H: Hasher,
333	C = DefaultCache<H>,
334	R = DefaultRecorder<H>,
335> {
336	pub(crate) essence: TrieBackendEssence<S, H, C, R>,
337	next_storage_key_cache: CacheCell<Option<CachedIter<S, H, C, R>>>,
338}
339
340impl<
341		S: TrieBackendStorage<H>,
342		H: Hasher,
343		C: TrieCacheProvider<H> + Send + Sync,
344		R: TrieRecorderProvider<H> + Send + Sync,
345	> TrieBackend<S, H, C, R>
346where
347	H::Out: Codec,
348{
349	#[cfg(test)]
350	pub(crate) fn from_essence(essence: TrieBackendEssence<S, H, C, R>) -> Self {
351		Self { essence, next_storage_key_cache: Default::default() }
352	}
353
354	/// Get backend essence reference.
355	pub fn essence(&self) -> &TrieBackendEssence<S, H, C, R> {
356		&self.essence
357	}
358
359	/// Get backend storage reference.
360	pub fn backend_storage_mut(&mut self) -> &mut S {
361		self.essence.backend_storage_mut()
362	}
363
364	/// Get backend storage reference.
365	pub fn backend_storage(&self) -> &S {
366		self.essence.backend_storage()
367	}
368
369	/// Set trie root.
370	pub fn set_root(&mut self, root: H::Out) {
371		self.essence.set_root(root)
372	}
373
374	/// Get trie root.
375	pub fn root(&self) -> &H::Out {
376		self.essence.root()
377	}
378
379	/// Consumes self and returns underlying storage.
380	pub fn into_storage(self) -> S {
381		self.essence.into_storage()
382	}
383
384	/// Extract the [`StorageProof`].
385	///
386	/// This only returns `Some` when there was a recorder set.
387	pub fn extract_proof(mut self) -> Option<StorageProof> {
388		self.essence.recorder.take().and_then(|r| r.drain_storage_proof())
389	}
390}
391
392impl<S: TrieBackendStorage<H>, H: Hasher, C: TrieCacheProvider<H>, R: TrieRecorderProvider<H>>
393	core::fmt::Debug for TrieBackend<S, H, C, R>
394{
395	fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
396		write!(f, "TrieBackend")
397	}
398}
399
400impl<
401		S: TrieBackendStorage<H>,
402		H: Hasher,
403		C: TrieCacheProvider<H> + Send + Sync,
404		R: TrieRecorderProvider<H> + Send + Sync,
405	> Backend<H> for TrieBackend<S, H, C, R>
406where
407	H::Out: Ord + Codec,
408{
409	type Error = crate::DefaultError;
410	type TrieBackendStorage = S;
411	type RawIter = crate::trie_backend_essence::RawIter<S, H, C, R>;
412
413	fn storage_hash(&self, key: &[u8]) -> Result<Option<H::Out>, Self::Error> {
414		self.essence.storage_hash(key)
415	}
416
417	fn storage(&self, key: &[u8]) -> Result<Option<StorageValue>, Self::Error> {
418		self.essence.storage(key)
419	}
420
421	fn child_storage_hash(
422		&self,
423		child_info: &ChildInfo,
424		key: &[u8],
425	) -> Result<Option<H::Out>, Self::Error> {
426		self.essence.child_storage_hash(child_info, key)
427	}
428
429	fn child_storage(
430		&self,
431		child_info: &ChildInfo,
432		key: &[u8],
433	) -> Result<Option<StorageValue>, Self::Error> {
434		self.essence.child_storage(child_info, key)
435	}
436
437	fn closest_merkle_value(&self, key: &[u8]) -> Result<Option<MerkleValue<H::Out>>, Self::Error> {
438		self.essence.closest_merkle_value(key)
439	}
440
441	fn child_closest_merkle_value(
442		&self,
443		child_info: &ChildInfo,
444		key: &[u8],
445	) -> Result<Option<MerkleValue<H::Out>>, Self::Error> {
446		self.essence.child_closest_merkle_value(child_info, key)
447	}
448
449	fn next_storage_key(&self, key: &[u8]) -> Result<Option<StorageKey>, Self::Error> {
450		let (is_cached, mut cache) = access_cache(&self.next_storage_key_cache, Option::take)
451			.map(|cache| (cache.last_key == key, cache))
452			.unwrap_or_default();
453
454		if !is_cached {
455			cache.iter = self.raw_iter(IterArgs {
456				start_at: Some(key),
457				start_at_exclusive: true,
458				..IterArgs::default()
459			})?
460		};
461
462		let next_key = match cache.iter.next_key(self) {
463			None => return Ok(None),
464			Some(Err(error)) => return Err(error),
465			Some(Ok(next_key)) => next_key,
466		};
467
468		cache.last_key.clear();
469		cache.last_key.extend_from_slice(&next_key);
470		access_cache(&self.next_storage_key_cache, |cache_cell| cache_cell.replace(cache));
471
472		#[cfg(debug_assertions)]
473		debug_assert_eq!(
474			self.essence
475				.next_storage_key_slow(key)
476				.expect(
477					"fetching the next key through iterator didn't fail so this shouldn't either"
478				)
479				.as_ref(),
480			Some(&next_key)
481		);
482
483		Ok(Some(next_key))
484	}
485
486	fn next_child_storage_key(
487		&self,
488		child_info: &ChildInfo,
489		key: &[u8],
490	) -> Result<Option<StorageKey>, Self::Error> {
491		self.essence.next_child_storage_key(child_info, key)
492	}
493
494	fn raw_iter(&self, args: IterArgs) -> Result<Self::RawIter, Self::Error> {
495		self.essence.raw_iter(args)
496	}
497
498	fn storage_root<'a>(
499		&self,
500		delta: impl Iterator<Item = (&'a [u8], Option<&'a [u8]>)>,
501		state_version: StateVersion,
502	) -> (H::Out, PrefixedMemoryDB<H>)
503	where
504		H::Out: Ord,
505	{
506		self.essence.storage_root(delta, state_version)
507	}
508
509	fn child_storage_root<'a>(
510		&self,
511		child_info: &ChildInfo,
512		delta: impl Iterator<Item = (&'a [u8], Option<&'a [u8]>)>,
513		state_version: StateVersion,
514	) -> (H::Out, bool, PrefixedMemoryDB<H>)
515	where
516		H::Out: Ord,
517	{
518		self.essence.child_storage_root(child_info, delta, state_version)
519	}
520
521	fn register_overlay_stats(&self, _stats: &crate::stats::StateMachineStats) {}
522
523	fn usage_info(&self) -> crate::UsageInfo {
524		crate::UsageInfo::empty()
525	}
526
527	fn wipe(&self) -> Result<(), Self::Error> {
528		Ok(())
529	}
530}
531
532#[cfg(feature = "std")]
533impl<S: TrieBackendStorage<H>, H: Hasher, C> AsTrieBackend<H, C> for TrieBackend<S, H, C> {
534	type TrieBackendStorage = S;
535
536	fn as_trie_backend(&self) -> &TrieBackend<S, H, C> {
537		self
538	}
539}
540
541/// Create a backend used for checking the proof, using `H` as hasher.
542///
543/// `proof` and `root` must match, i.e. `root` must be the correct root of `proof` nodes.
544#[cfg(feature = "std")]
545pub fn create_proof_check_backend<H>(
546	root: H::Out,
547	proof: StorageProof,
548) -> Result<TrieBackend<MemoryDB<H>, H>, Box<dyn crate::Error>>
549where
550	H: Hasher,
551	H::Out: Codec,
552{
553	let db = proof.into_memory_db();
554
555	if db.contains(&root, hash_db::EMPTY_PREFIX) {
556		Ok(TrieBackendBuilder::new(db, root).build())
557	} else {
558		Err(Box::new(crate::ExecutionError::InvalidProof))
559	}
560}
561
562#[cfg(test)]
563pub mod tests {
564	use crate::{new_in_mem, InMemoryBackend};
565
566	use super::*;
567	use codec::Encode;
568	use sp_core::H256;
569	use sp_runtime::traits::BlakeTwo256;
570	use sp_trie::{
571		cache::{CacheSize, SharedTrieCache},
572		trie_types::{TrieDBBuilder, TrieDBMutBuilderV0, TrieDBMutBuilderV1},
573		KeySpacedDBMut, PrefixedMemoryDB, Trie, TrieCache, TrieMut,
574	};
575	use std::iter;
576	use trie_db::NodeCodec;
577
578	const CHILD_KEY_1: &[u8] = b"sub1";
579
580	type Recorder = sp_trie::recorder::Recorder<BlakeTwo256>;
581	type Cache = LocalTrieCache<BlakeTwo256>;
582	type SharedCache = SharedTrieCache<BlakeTwo256>;
583
584	macro_rules! parameterized_test {
585		($name:ident, $internal_name:ident) => {
586			#[test]
587			fn $name() {
588				let parameters = vec![
589					(StateVersion::V0, None, None),
590					(StateVersion::V0, Some(SharedCache::new(CacheSize::unlimited())), None),
591					(StateVersion::V0, None, Some(Recorder::default())),
592					(
593						StateVersion::V0,
594						Some(SharedCache::new(CacheSize::unlimited())),
595						Some(Recorder::default()),
596					),
597					(StateVersion::V1, None, None),
598					(StateVersion::V1, Some(SharedCache::new(CacheSize::unlimited())), None),
599					(StateVersion::V1, None, Some(Recorder::default())),
600					(
601						StateVersion::V1,
602						Some(SharedCache::new(CacheSize::unlimited())),
603						Some(Recorder::default()),
604					),
605				];
606
607				for (version, cache, recorder) in parameters {
608					eprintln!(
609						"Running with version {:?}, cache enabled {} and recorder enabled {}",
610						version,
611						cache.is_some(),
612						recorder.is_some()
613					);
614
615					let cache = cache.as_ref().map(|c| c.local_cache());
616
617					$internal_name(version, cache, recorder.clone());
618				}
619			}
620		};
621	}
622
623	pub(crate) fn test_db(state_version: StateVersion) -> (PrefixedMemoryDB<BlakeTwo256>, H256) {
624		let child_info = ChildInfo::new_default(CHILD_KEY_1);
625		let mut root = H256::default();
626		let mut mdb = PrefixedMemoryDB::<BlakeTwo256>::default();
627		{
628			let mut mdb = KeySpacedDBMut::new(&mut mdb, child_info.keyspace());
629			match state_version {
630				StateVersion::V0 => {
631					let mut trie = TrieDBMutBuilderV0::new(&mut mdb, &mut root).build();
632					trie.insert(b"value3", &[142; 33]).expect("insert failed");
633					trie.insert(b"value4", &[124; 33]).expect("insert failed");
634				},
635				StateVersion::V1 => {
636					let mut trie = TrieDBMutBuilderV1::new(&mut mdb, &mut root).build();
637					trie.insert(b"value3", &[142; 33]).expect("insert failed");
638					trie.insert(b"value4", &[124; 33]).expect("insert failed");
639				},
640			};
641		};
642
643		{
644			let mut sub_root = Vec::new();
645			root.encode_to(&mut sub_root);
646
647			fn build<L: sp_trie::TrieLayout>(
648				mut trie: sp_trie::TrieDBMut<L>,
649				child_info: &ChildInfo,
650				sub_root: &[u8],
651			) {
652				trie.insert(child_info.prefixed_storage_key().as_slice(), sub_root)
653					.expect("insert failed");
654				trie.insert(b"key", b"value").expect("insert failed");
655				trie.insert(b"value1", &[42]).expect("insert failed");
656				trie.insert(b"value2", &[24]).expect("insert failed");
657				trie.insert(b":code", b"return 42").expect("insert failed");
658				for i in 128u8..255u8 {
659					trie.insert(&[i], &[i]).unwrap();
660				}
661			}
662
663			match state_version {
664				StateVersion::V0 => {
665					let trie = TrieDBMutBuilderV0::new(&mut mdb, &mut root).build();
666					build(trie, &child_info, &sub_root[..])
667				},
668				StateVersion::V1 => {
669					let trie = TrieDBMutBuilderV1::new(&mut mdb, &mut root).build();
670					build(trie, &child_info, &sub_root[..])
671				},
672			};
673		}
674		(mdb, root)
675	}
676
677	pub(crate) fn test_db_with_hex_keys(
678		state_version: StateVersion,
679		keys: &[&str],
680	) -> (PrefixedMemoryDB<BlakeTwo256>, H256) {
681		let mut root = H256::default();
682		let mut mdb = PrefixedMemoryDB::<BlakeTwo256>::default();
683		match state_version {
684			StateVersion::V0 => {
685				let mut trie = TrieDBMutBuilderV0::new(&mut mdb, &mut root).build();
686				for (index, key) in keys.iter().enumerate() {
687					trie.insert(&array_bytes::hex2bytes(key).unwrap(), &[index as u8]).unwrap();
688				}
689			},
690			StateVersion::V1 => {
691				let mut trie = TrieDBMutBuilderV1::new(&mut mdb, &mut root).build();
692				for (index, key) in keys.iter().enumerate() {
693					trie.insert(&array_bytes::hex2bytes(key).unwrap(), &[index as u8]).unwrap();
694				}
695			},
696		};
697		(mdb, root)
698	}
699
700	pub(crate) fn test_trie(
701		hashed_value: StateVersion,
702		cache: Option<Cache>,
703		recorder: Option<Recorder>,
704	) -> TrieBackend<PrefixedMemoryDB<BlakeTwo256>, BlakeTwo256> {
705		let (mdb, root) = test_db(hashed_value);
706
707		TrieBackendBuilder::new(mdb, root)
708			.with_optional_cache(cache)
709			.with_optional_recorder(recorder)
710			.build()
711	}
712
713	pub(crate) fn test_trie_with_hex_keys(
714		hashed_value: StateVersion,
715		cache: Option<Cache>,
716		recorder: Option<Recorder>,
717		keys: &[&str],
718	) -> TrieBackend<PrefixedMemoryDB<BlakeTwo256>, BlakeTwo256> {
719		let (mdb, root) = test_db_with_hex_keys(hashed_value, keys);
720
721		TrieBackendBuilder::new(mdb, root)
722			.with_optional_cache(cache)
723			.with_optional_recorder(recorder)
724			.build()
725	}
726
727	parameterized_test!(read_from_storage_returns_some, read_from_storage_returns_some_inner);
728	fn read_from_storage_returns_some_inner(
729		state_version: StateVersion,
730		cache: Option<Cache>,
731		recorder: Option<Recorder>,
732	) {
733		assert_eq!(
734			test_trie(state_version, cache, recorder).storage(b"key").unwrap(),
735			Some(b"value".to_vec())
736		);
737	}
738
739	parameterized_test!(
740		read_from_child_storage_returns_some,
741		read_from_child_storage_returns_some_inner
742	);
743	fn read_from_child_storage_returns_some_inner(
744		state_version: StateVersion,
745		cache: Option<Cache>,
746		recorder: Option<Recorder>,
747	) {
748		let test_trie = test_trie(state_version, cache, recorder);
749		assert_eq!(
750			test_trie
751				.child_storage(&ChildInfo::new_default(CHILD_KEY_1), b"value3")
752				.unwrap(),
753			Some(vec![142u8; 33]),
754		);
755		// Change cache entry to check that caching is active.
756		test_trie
757			.essence
758			.cache
759			.write()
760			.child_root
761			.entry(b"sub1".to_vec())
762			.and_modify(|value| {
763				*value = None;
764			});
765		assert_eq!(
766			test_trie
767				.child_storage(&ChildInfo::new_default(CHILD_KEY_1), b"value3")
768				.unwrap(),
769			None,
770		);
771	}
772
773	parameterized_test!(read_from_storage_returns_none, read_from_storage_returns_none_inner);
774	fn read_from_storage_returns_none_inner(
775		state_version: StateVersion,
776		cache: Option<Cache>,
777		recorder: Option<Recorder>,
778	) {
779		assert_eq!(
780			test_trie(state_version, cache, recorder).storage(b"non-existing-key").unwrap(),
781			None
782		);
783	}
784
785	parameterized_test!(
786		pairs_are_not_empty_on_non_empty_storage,
787		pairs_are_not_empty_on_non_empty_storage_inner
788	);
789	fn pairs_are_not_empty_on_non_empty_storage_inner(
790		state_version: StateVersion,
791		cache: Option<Cache>,
792		recorder: Option<Recorder>,
793	) {
794		assert!(!test_trie(state_version, cache, recorder)
795			.pairs(Default::default())
796			.unwrap()
797			.next()
798			.is_none());
799	}
800
801	#[test]
802	fn pairs_are_empty_on_empty_storage() {
803		assert!(TrieBackendBuilder::<PrefixedMemoryDB<BlakeTwo256>, BlakeTwo256>::new(
804			PrefixedMemoryDB::default(),
805			Default::default(),
806		)
807		.build()
808		.pairs(Default::default())
809		.unwrap()
810		.next()
811		.is_none());
812	}
813
814	parameterized_test!(storage_iteration_works, storage_iteration_works_inner);
815	fn storage_iteration_works_inner(
816		state_version: StateVersion,
817		cache: Option<Cache>,
818		recorder: Option<Recorder>,
819	) {
820		let trie = test_trie(state_version, cache, recorder);
821
822		// Fetch everything.
823		assert_eq!(
824			trie.keys(Default::default())
825				.unwrap()
826				.map(|result| result.unwrap())
827				.take(5)
828				.collect::<Vec<_>>(),
829			vec![
830				b":child_storage:default:sub1".to_vec(),
831				b":code".to_vec(),
832				b"key".to_vec(),
833				b"value1".to_vec(),
834				b"value2".to_vec(),
835			]
836		);
837
838		// Fetch starting at a given key (full key).
839		assert_eq!(
840			trie.keys(IterArgs { start_at: Some(b"key"), ..IterArgs::default() })
841				.unwrap()
842				.map(|result| result.unwrap())
843				.take(3)
844				.collect::<Vec<_>>(),
845			vec![b"key".to_vec(), b"value1".to_vec(), b"value2".to_vec(),]
846		);
847
848		// Fetch starting at a given key (partial key).
849		assert_eq!(
850			trie.keys(IterArgs { start_at: Some(b"ke"), ..IterArgs::default() })
851				.unwrap()
852				.map(|result| result.unwrap())
853				.take(3)
854				.collect::<Vec<_>>(),
855			vec![b"key".to_vec(), b"value1".to_vec(), b"value2".to_vec(),]
856		);
857
858		// Fetch starting at a given key (empty key).
859		assert_eq!(
860			trie.keys(IterArgs { start_at: Some(b""), ..IterArgs::default() })
861				.unwrap()
862				.map(|result| result.unwrap())
863				.take(5)
864				.collect::<Vec<_>>(),
865			vec![
866				b":child_storage:default:sub1".to_vec(),
867				b":code".to_vec(),
868				b"key".to_vec(),
869				b"value1".to_vec(),
870				b"value2".to_vec(),
871			]
872		);
873
874		// Fetch starting at a given key and with prefix which doesn't match that key.
875		// (Start *before* the prefix.)
876		assert_eq!(
877			trie.keys(IterArgs {
878				prefix: Some(b"value"),
879				start_at: Some(b"key"),
880				..IterArgs::default()
881			})
882			.unwrap()
883			.map(|result| result.unwrap())
884			.collect::<Vec<_>>(),
885			vec![b"value1".to_vec(), b"value2".to_vec(),]
886		);
887
888		// Fetch starting at a given key and with prefix which doesn't match that key.
889		// (Start *after* the prefix.)
890		assert!(trie
891			.keys(IterArgs {
892				prefix: Some(b"value"),
893				start_at: Some(b"vblue"),
894				..IterArgs::default()
895			})
896			.unwrap()
897			.map(|result| result.unwrap())
898			.next()
899			.is_none());
900
901		// Fetch starting at a given key and with prefix which does match that key.
902		assert_eq!(
903			trie.keys(IterArgs {
904				prefix: Some(b"value"),
905				start_at: Some(b"value"),
906				..IterArgs::default()
907			})
908			.unwrap()
909			.map(|result| result.unwrap())
910			.collect::<Vec<_>>(),
911			vec![b"value1".to_vec(), b"value2".to_vec(),]
912		);
913	}
914
915	// This test reproduces an actual real-world issue: https://github.com/polkadot-js/apps/issues/9103
916	parameterized_test!(
917		storage_iter_does_not_return_out_of_prefix_keys,
918		storage_iter_does_not_return_out_of_prefix_keys_inner
919	);
920	fn storage_iter_does_not_return_out_of_prefix_keys_inner(
921		state_version: StateVersion,
922		cache: Option<Cache>,
923		recorder: Option<Recorder>,
924	) {
925		let trie = test_trie_with_hex_keys(state_version, cache, recorder, &[
926			"6cf4040bbce30824850f1a4823d8c65faeefaa25a5bae16a431719647c1d99da",
927			"6cf4040bbce30824850f1a4823d8c65ff536928ca5ba50039bc2766a48ddbbab",
928			"70f943199f1a2dde80afdaf3f447db834e7b9012096b41c4eb3aaf947f6ea429",
929			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8d007fc7effcb0c044a0c41fd8a77eb55d2133058a86d1f4d6f8e45612cd271eefd77f91caeaacfe011b8f41540e0a793b0fd51b245dae19382b45386570f2b545fab75e3277910f7324b55f47c29f9965e8298371404e50ac",
930			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8d0179c23cd593c770fde9fc7aa8f84b3e401e654b8986c67728844da0080ec9ee222b41a85708a471a511548302870b53f40813d8354b6d2969e1b7ca9e083ecf96f9647e004ecb41c7f26f0110f778bdb3d9da31bef323d9",
931			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8d024de296f88310247001277477f4ace4d0aa5685ea2928d518a807956e4806a656520d6520b8ac259f684aa0d91961d76f697716f04e6c997338d03560ab7d703829fe7b9d0e6d7eff8d8412fc428364c2f474a67b36586d",
932			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8d13dc5d83f2361c14d05933eb3182a92ac14665718569703baf1da25c7d571843b6489f03d8549c87bfa5709836ba729443c319659e83ad5ee133e6f11af51d883e56216e9e1bbb1e2920c7c6120cbb55cd469b1f95b61601",
933			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8d1786d20bbb4b91eb1f5765432d750bd0111a0807c8d04f05110ffaf73f4fa7b360422c13bc97efc3a2324d9fa8f954b424c0bcfce7236a2e8107dd31c2042a9860a964f8472fda49749dec3f146e81470b55aa0f3930d854",
934			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8d18c246484ec5335a40903e7cd05771be7c0b8459333f1ae2925c3669fc3e5accd0f38c4711a15544bfa5709836ba729443c319659e83ad5ee133e6f11af51d883e56216e9e1bbb1e2920c7c6120cbb55cd469b1f95b61601",
935			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8d1aca749033252ce75245528397430d14cb8e8c09248d81ee5de00b6ae93ee880b6d19a595e6dc106bfa5709836ba729443c319659e83ad5ee133e6f11af51d883e56216e9e1bbb1e2920c7c6120cbb55cd469b1f95b61601",
936			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8d1d6bceb91bc07973e7b3296f83af9f1c4300ce9198cc3b44c54dafddb58f4a43aee44a9bef1a2e9dbfa5709836ba729443c319659e83ad5ee133e6f11af51d883e56216e9e1bbb1e2920c7c6120cbb55cd469b1f95b61601",
937			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8d203383772f45721232139e1a8863b0f2f8d480bdc15bcc1f2033cf467e137059558da743838f6b58bfa5709836ba729443c319659e83ad5ee133e6f11af51d883e56216e9e1bbb1e2920c7c6120cbb55cd469b1f95b61601",
938			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8d2197cc5c3eb3a6a67538e0dc3eaaf8c820d71310d377499c4a5d276381789e0a234475e69cddf709d207458083d6146d3a36fce7f1fe05b232702bf154096e5e3a8c378bdc237d7a27909acd663563917f0f70bb0e8e61a3",
939			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8d4f19c117f2ea36100f753c4885aa8d63b4d65a0dc32106f829f89eeabd52c37105c9bdb75f752469729fa3f0e7d907c1d949192c8e264a1a510c32abe3a05ed50be2262d5bfb981673ec80a07fd2ce28c7f27cd0043a788c",
940			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8d547d5aaa651bafa63d077560dfe823ac75665ebf1dcfd96a06e45499f03dda31282977706918d4821b8f41540e0a793b0fd51b245dae19382b45386570f2b545fab75e3277910f7324b55f47c29f9965e8298371404e50ac",
941			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8d6037207d54d69a082ea225ab4a412e4b87d6f5612053b07c405cf05ea25e482a4908c0713be2998abfa5709836ba729443c319659e83ad5ee133e6f11af51d883e56216e9e1bbb1e2920c7c6120cbb55cd469b1f95b61601",
942			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8d63d0920de0c7315ebaed1d639d926961d28af89461c31eca890441e449147d23bb7c9d4fc42d7c16bfa5709836ba729443c319659e83ad5ee133e6f11af51d883e56216e9e1bbb1e2920c7c6120cbb55cd469b1f95b61601",
943			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8d7912c66be82a5972e5bc11c8d10551a296ba9aaff8ca6ab22a8cd1987974b87a97121c871f786d2e17e0a629acf01c38947f170b7e02a9ebb4ee60f83779acb99b71114c01a4f0a60694611a1502c399c77214ffa26e955b",
944			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8d7aa00f217f3a374a2f1ca0f388719f84099e8157a8a83c5ccf54eae1617f93933fa976baa629e6febfa5709836ba729443c319659e83ad5ee133e6f11af51d883e56216e9e1bbb1e2920c7c6120cbb55cd469b1f95b61601",
945			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8d9e1c3c8ab41943cf377b1aa724d7f518a3cfc96a732bdc4658155d09ed2bfc31b5ccbc6d8646b59f1b8f41540e0a793b0fd51b245dae19382b45386570f2b545fab75e3277910f7324b55f47c29f9965e8298371404e50ac",
946			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8d9fb8d6d95d5214a3305a4fa07e344eb99fad4be3565d646c8ac5af85514d9c96702c9c207be234958dbdb9185f467d2be3b84e8b2f529f7ec3844b378a889afd6bd31a9b5ed22ffee2019ad82c6692f1736dd41c8bb85726",
947			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8d9fb8d6d95d5214a3305a4fa07e344eb99fad4be3565d646c8ac5af85514d9c96702c9c207be23495ec1caa509591a36a8403684384ce40838c9bd7fc49d933a10d3b26e979273e2f17ebf0bf41cd90e4287e126a59d5a243",
948			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8da7fc066aae2ffe03b36e9a72f9a39cb2befac7e47f320309f31f1c1676288d9596045807304b3d79bfa5709836ba729443c319659e83ad5ee133e6f11af51d883e56216e9e1bbb1e2920c7c6120cbb55cd469b1f95b61601",
949			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8daf3c377b0fddf7c7ad6d390fab0ab45ac16c21645be880af5cab2fbbeb04820401a4c9f766c17bef9fc14a2e16ade86fe26ee81d4497dc6aab81cc5f5bb0458d6149a763ecb09aefec06950dd61db1ba025401d2a04e3b9d",
950			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8daf3c377b0fddf7c7ad6d390fab0ab45ac16c21645be880af5cab2fbbeb04820401a4c9f766c17befbfa5709836ba729443c319659e83ad5ee133e6f11af51d883e56216e9e1bbb1e2920c7c6120cbb55cd469b1f95b61601",
951			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8db60505ba8b77ef03ed805436d3242f26dc828084b12aaf4bcb96af468816a182b5360149398aad6b1dafe949b0918138ceef924f6393d1818a04842301294604972da17b24b31b155e4409a01273733b8d21a156c2e7eb71",
952			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8dbd27136a6e028656073cc840bfabb48fe935880c4c4c990ee98458b2fed308e9765f7f7f717dd3b2862fa5361d3b55afa6040e582687403c852b2d065b24f253276cc581226991f8e1818a78fc64c39da7f0b383c6726e0f",
953			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8dca40d91320edd326500f9e8b5a0b23a8bdf21549f98f0e014f66b6a18bdd78e337a6c05d670c80c88a55d4c7bb6fbae546e2d03ac9ab16e85fe11dad6adfd6a20618905477b831d7d48ca32d0bfd2bdc8dbeba26ffe2c710",
954			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8dd27478512243ed62c1c1f7066021798a464d4cf9099546d5d9907b3369f1b9d7a5aa5d60ca845619bfa5709836ba729443c319659e83ad5ee133e6f11af51d883e56216e9e1bbb1e2920c7c6120cbb55cd469b1f95b61601",
955			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8de6da5659cbbe1489abbe99c4d3a474f4d1e78edb55a9be68d8f52c6fe730388a298e6f6325db3da7bfa5709836ba729443c319659e83ad5ee133e6f11af51d883e56216e9e1bbb1e2920c7c6120cbb55cd469b1f95b61601",
956			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8de6da5659cbbe1489abbe99c4d3a474f4d1e78edb55a9be68d8f52c6fe730388a298e6f6325db3da7e94ca3e8c297d82f71e232a2892992d1f6480475fb797ce64e58f773d8fafd9fbcee4bdf4b14f2a71b6d3a428cf9f24b",
957			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8decdd1760c61ff7234f2876dbe817af803170233320d778b92043b2359e3de6d16c9e5359f6302da31c84d6f551ad2a831263ef956f0cdb3b4810cefcb2d0b57bcce7b82007016ae4fe752c31d1a01b589a7966cea03ec65c",
958			"7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8df9981ee6b69eb7af2153af34f39ffc06e2daa5272c99798c8849091284dc8905f2a76b65754c2089bfa5709836ba729443c319659e83ad5ee133e6f11af51d883e56216e9e1bbb1e2920c7c6120cbb55cd469b1f95b61601",
959			"7474449cca95dc5d0c00e71735a6d17d4e7b9012096b41c4eb3aaf947f6ea429",
960			"89d139e01a5eb2256f222e5fc5dbe6b33c9c1284130706f5aea0c8b3d4c54d89",
961			"89d139e01a5eb2256f222e5fc5dbe6b36254e9d55588784fa2a62b726696e2b1"
962		]);
963
964		let key = array_bytes::hex2bytes("7474449cca95dc5d0c00e71735a6d17d3cd15a3fd6e04e47bee3922dbfa92c8da7dad55cf08ffe8194efa962146801b0503092b1ed6a3fa6aee9107334aefd7965bbe568c3d24c6d").unwrap();
965
966		assert_eq!(
967			trie.keys(IterArgs {
968				prefix: Some(&key),
969				start_at: Some(&key),
970				start_at_exclusive: true,
971				..IterArgs::default()
972			})
973			.unwrap()
974			.map(|result| result.unwrap())
975			.collect::<Vec<_>>(),
976			Vec::<Vec<u8>>::new()
977		);
978	}
979
980	parameterized_test!(storage_root_is_non_default, storage_root_is_non_default_inner);
981	fn storage_root_is_non_default_inner(
982		state_version: StateVersion,
983		cache: Option<Cache>,
984		recorder: Option<Recorder>,
985	) {
986		assert!(
987			test_trie(state_version, cache, recorder)
988				.storage_root(iter::empty(), state_version)
989				.0 != H256::repeat_byte(0)
990		);
991	}
992
993	parameterized_test!(
994		storage_root_transaction_is_non_empty,
995		storage_root_transaction_is_non_empty_inner
996	);
997	fn storage_root_transaction_is_non_empty_inner(
998		state_version: StateVersion,
999		cache: Option<Cache>,
1000		recorder: Option<Recorder>,
1001	) {
1002		let (new_root, mut tx) = test_trie(state_version, cache, recorder)
1003			.storage_root(iter::once((&b"new-key"[..], Some(&b"new-value"[..]))), state_version);
1004		assert!(!tx.drain().is_empty());
1005		assert!(
1006			new_root !=
1007				test_trie(state_version, None, None)
1008					.storage_root(iter::empty(), state_version)
1009					.0
1010		);
1011	}
1012
1013	parameterized_test!(
1014		keys_with_empty_prefix_returns_all_keys,
1015		keys_with_empty_prefix_returns_all_keys_inner
1016	);
1017	fn keys_with_empty_prefix_returns_all_keys_inner(
1018		state_version: StateVersion,
1019		cache: Option<Cache>,
1020		recorder: Option<Recorder>,
1021	) {
1022		let (test_db, test_root) = test_db(state_version);
1023		let expected = TrieDBBuilder::new(&test_db, &test_root)
1024			.build()
1025			.iter()
1026			.unwrap()
1027			.map(|d| d.unwrap().0.to_vec())
1028			.collect::<Vec<_>>();
1029
1030		let trie = test_trie(state_version, cache, recorder);
1031		let keys: Vec<_> =
1032			trie.keys(Default::default()).unwrap().map(|result| result.unwrap()).collect();
1033
1034		assert_eq!(expected, keys);
1035	}
1036
1037	parameterized_test!(
1038		proof_is_empty_until_value_is_read,
1039		proof_is_empty_until_value_is_read_inner
1040	);
1041	fn proof_is_empty_until_value_is_read_inner(
1042		state_version: StateVersion,
1043		cache: Option<Cache>,
1044		recorder: Option<Recorder>,
1045	) {
1046		let trie_backend = test_trie(state_version, cache, recorder);
1047		assert!(TrieBackendBuilder::wrap(&trie_backend)
1048			.with_recorder(Recorder::default())
1049			.build()
1050			.extract_proof()
1051			.unwrap()
1052			.is_empty());
1053	}
1054
1055	parameterized_test!(
1056		proof_is_non_empty_after_value_is_read,
1057		proof_is_non_empty_after_value_is_read_inner
1058	);
1059	fn proof_is_non_empty_after_value_is_read_inner(
1060		state_version: StateVersion,
1061		cache: Option<Cache>,
1062		recorder: Option<Recorder>,
1063	) {
1064		let trie_backend = test_trie(state_version, cache, recorder);
1065		let backend = TrieBackendBuilder::wrap(&trie_backend)
1066			.with_recorder(Recorder::default())
1067			.build();
1068		assert_eq!(backend.storage(b"key").unwrap(), Some(b"value".to_vec()));
1069		assert!(!backend.extract_proof().unwrap().is_empty());
1070	}
1071
1072	#[test]
1073	fn proof_is_invalid_when_does_not_contains_root() {
1074		let result = create_proof_check_backend::<BlakeTwo256>(
1075			H256::from_low_u64_be(1),
1076			StorageProof::empty(),
1077		);
1078		assert!(result.is_err());
1079	}
1080
1081	parameterized_test!(passes_through_backend_calls, passes_through_backend_calls_inner);
1082	fn passes_through_backend_calls_inner(
1083		state_version: StateVersion,
1084		cache: Option<Cache>,
1085		recorder: Option<Recorder>,
1086	) {
1087		let trie_backend = test_trie(state_version, cache, recorder);
1088		let proving_backend = TrieBackendBuilder::wrap(&trie_backend)
1089			.with_recorder(Recorder::default())
1090			.build();
1091		assert_eq!(trie_backend.storage(b"key").unwrap(), proving_backend.storage(b"key").unwrap());
1092		assert_eq!(
1093			trie_backend
1094				.pairs(Default::default())
1095				.unwrap()
1096				.map(|result| result.unwrap())
1097				.collect::<Vec<_>>(),
1098			proving_backend
1099				.pairs(Default::default())
1100				.unwrap()
1101				.map(|result| result.unwrap())
1102				.collect::<Vec<_>>()
1103		);
1104
1105		let (trie_root, mut trie_mdb) =
1106			trie_backend.storage_root(std::iter::empty(), state_version);
1107		let (proving_root, mut proving_mdb) =
1108			proving_backend.storage_root(std::iter::empty(), state_version);
1109		assert_eq!(trie_root, proving_root);
1110		assert_eq!(trie_mdb.drain(), proving_mdb.drain());
1111	}
1112
1113	#[test]
1114	fn proof_recorded_and_checked_top() {
1115		proof_recorded_and_checked_inner(StateVersion::V0);
1116		proof_recorded_and_checked_inner(StateVersion::V1);
1117	}
1118	fn proof_recorded_and_checked_inner(state_version: StateVersion) {
1119		let size_content = 34; // above hashable value threshold.
1120		let value_range = 0..64;
1121		let contents = value_range
1122			.clone()
1123			.map(|i| (vec![i], Some(vec![i; size_content])))
1124			.collect::<Vec<_>>();
1125		let in_memory = InMemoryBackend::<BlakeTwo256>::default();
1126		let in_memory = in_memory.update(vec![(None, contents)], state_version);
1127		let in_memory_root = in_memory.storage_root(std::iter::empty(), state_version).0;
1128		value_range.clone().for_each(|i| {
1129			assert_eq!(in_memory.storage(&[i]).unwrap().unwrap(), vec![i; size_content])
1130		});
1131
1132		let trie = in_memory.as_trie_backend();
1133		let trie_root = trie.storage_root(std::iter::empty(), state_version).0;
1134		assert_eq!(in_memory_root, trie_root);
1135		value_range
1136			.clone()
1137			.for_each(|i| assert_eq!(trie.storage(&[i]).unwrap().unwrap(), vec![i; size_content]));
1138
1139		for cache in [Some(SharedTrieCache::new(CacheSize::unlimited())), None] {
1140			// Run multiple times to have a different cache conditions.
1141			for i in 0..5 {
1142				if let Some(cache) = &cache {
1143					if i == 2 {
1144						cache.reset_node_cache();
1145					} else if i == 3 {
1146						cache.reset_value_cache();
1147					}
1148				}
1149
1150				let proving = TrieBackendBuilder::wrap(&trie)
1151					.with_recorder(Recorder::default())
1152					.with_optional_cache(cache.as_ref().map(|c| c.local_cache()))
1153					.build();
1154				assert_eq!(proving.storage(&[42]).unwrap().unwrap(), vec![42; size_content]);
1155
1156				let proof = proving.extract_proof().unwrap();
1157
1158				let proof_check =
1159					create_proof_check_backend::<BlakeTwo256>(in_memory_root.into(), proof)
1160						.unwrap();
1161				assert_eq!(proof_check.storage(&[42]).unwrap().unwrap(), vec![42; size_content]);
1162			}
1163		}
1164	}
1165
1166	#[test]
1167	fn proof_record_works_with_iter() {
1168		proof_record_works_with_iter_inner(StateVersion::V0);
1169		proof_record_works_with_iter_inner(StateVersion::V1);
1170	}
1171	fn proof_record_works_with_iter_inner(state_version: StateVersion) {
1172		for cache in [Some(SharedTrieCache::new(CacheSize::unlimited())), None] {
1173			// Run multiple times to have a different cache conditions.
1174			for i in 0..5 {
1175				if let Some(cache) = &cache {
1176					if i == 2 {
1177						cache.reset_node_cache();
1178					} else if i == 3 {
1179						cache.reset_value_cache();
1180					}
1181				}
1182
1183				let contents = (0..64).map(|i| (vec![i], Some(vec![i]))).collect::<Vec<_>>();
1184				let in_memory = InMemoryBackend::<BlakeTwo256>::default();
1185				let in_memory = in_memory.update(vec![(None, contents)], state_version);
1186				let in_memory_root = in_memory.storage_root(std::iter::empty(), state_version).0;
1187				(0..64)
1188					.for_each(|i| assert_eq!(in_memory.storage(&[i]).unwrap().unwrap(), vec![i]));
1189
1190				let trie = in_memory.as_trie_backend();
1191				let trie_root = trie.storage_root(std::iter::empty(), state_version).0;
1192				assert_eq!(in_memory_root, trie_root);
1193				(0..64).for_each(|i| assert_eq!(trie.storage(&[i]).unwrap().unwrap(), vec![i]));
1194
1195				let proving = TrieBackendBuilder::wrap(&trie)
1196					.with_recorder(Recorder::default())
1197					.with_optional_cache(cache.as_ref().map(|c| c.local_cache()))
1198					.build();
1199
1200				(0..63).for_each(|i| {
1201					assert_eq!(proving.next_storage_key(&[i]).unwrap(), Some(vec![i + 1]))
1202				});
1203
1204				let proof = proving.extract_proof().unwrap();
1205
1206				let proof_check =
1207					create_proof_check_backend::<BlakeTwo256>(in_memory_root.into(), proof)
1208						.unwrap();
1209				(0..63).for_each(|i| {
1210					assert_eq!(proof_check.next_storage_key(&[i]).unwrap(), Some(vec![i + 1]))
1211				});
1212			}
1213		}
1214	}
1215
1216	#[test]
1217	fn proof_recorded_and_checked_with_child() {
1218		proof_recorded_and_checked_with_child_inner(StateVersion::V0);
1219		proof_recorded_and_checked_with_child_inner(StateVersion::V1);
1220	}
1221	fn proof_recorded_and_checked_with_child_inner(state_version: StateVersion) {
1222		let child_info_1 = ChildInfo::new_default(b"sub1");
1223		let child_info_2 = ChildInfo::new_default(b"sub2");
1224		let child_info_1 = &child_info_1;
1225		let child_info_2 = &child_info_2;
1226		let contents = vec![
1227			(None, (0..64).map(|i| (vec![i], Some(vec![i]))).collect::<Vec<_>>()),
1228			(Some(child_info_1.clone()), (28..65).map(|i| (vec![i], Some(vec![i]))).collect()),
1229			(Some(child_info_2.clone()), (10..15).map(|i| (vec![i], Some(vec![i]))).collect()),
1230		];
1231		let in_memory = new_in_mem::<BlakeTwo256>();
1232		let in_memory = in_memory.update(contents, state_version);
1233		let child_storage_keys = vec![child_info_1.to_owned(), child_info_2.to_owned()];
1234		let in_memory_root = in_memory
1235			.full_storage_root(
1236				std::iter::empty(),
1237				child_storage_keys.iter().map(|k| (k, std::iter::empty())),
1238				state_version,
1239			)
1240			.0;
1241		(0..64).for_each(|i| assert_eq!(in_memory.storage(&[i]).unwrap().unwrap(), vec![i]));
1242		(28..65).for_each(|i| {
1243			assert_eq!(in_memory.child_storage(child_info_1, &[i]).unwrap().unwrap(), vec![i])
1244		});
1245		(10..15).for_each(|i| {
1246			assert_eq!(in_memory.child_storage(child_info_2, &[i]).unwrap().unwrap(), vec![i])
1247		});
1248
1249		for cache in [Some(SharedTrieCache::new(CacheSize::unlimited())), None] {
1250			// Run multiple times to have a different cache conditions.
1251			for i in 0..5 {
1252				eprintln!("Running with cache {}, iteration {}", cache.is_some(), i);
1253
1254				if let Some(cache) = &cache {
1255					if i == 2 {
1256						cache.reset_node_cache();
1257					} else if i == 3 {
1258						cache.reset_value_cache();
1259					}
1260				}
1261
1262				let trie = in_memory.as_trie_backend();
1263				let trie_root = trie.storage_root(std::iter::empty(), state_version).0;
1264				assert_eq!(in_memory_root, trie_root);
1265				(0..64).for_each(|i| assert_eq!(trie.storage(&[i]).unwrap().unwrap(), vec![i]));
1266
1267				let proving = TrieBackendBuilder::wrap(&trie)
1268					.with_recorder(Recorder::default())
1269					.with_optional_cache(cache.as_ref().map(|c| c.local_cache()))
1270					.build();
1271				assert_eq!(proving.storage(&[42]).unwrap().unwrap(), vec![42]);
1272
1273				let proof = proving.extract_proof().unwrap();
1274
1275				let proof_check =
1276					create_proof_check_backend::<BlakeTwo256>(in_memory_root.into(), proof)
1277						.unwrap();
1278				assert!(proof_check.storage(&[0]).is_err());
1279				assert_eq!(proof_check.storage(&[42]).unwrap().unwrap(), vec![42]);
1280				// note that it is include in root because proof close
1281				assert_eq!(proof_check.storage(&[41]).unwrap().unwrap(), vec![41]);
1282				assert_eq!(proof_check.storage(&[64]).unwrap(), None);
1283
1284				let proving = TrieBackendBuilder::wrap(&trie)
1285					.with_recorder(Recorder::default())
1286					.with_optional_cache(cache.as_ref().map(|c| c.local_cache()))
1287					.build();
1288				assert_eq!(proving.child_storage(child_info_1, &[64]), Ok(Some(vec![64])));
1289				assert_eq!(proving.child_storage(child_info_1, &[25]), Ok(None));
1290				assert_eq!(proving.child_storage(child_info_2, &[14]), Ok(Some(vec![14])));
1291				assert_eq!(proving.child_storage(child_info_2, &[25]), Ok(None));
1292
1293				let proof = proving.extract_proof().unwrap();
1294				let proof_check =
1295					create_proof_check_backend::<BlakeTwo256>(in_memory_root.into(), proof)
1296						.unwrap();
1297				assert_eq!(
1298					proof_check.child_storage(child_info_1, &[64]).unwrap().unwrap(),
1299					vec![64]
1300				);
1301				assert_eq!(proof_check.child_storage(child_info_1, &[25]).unwrap(), None);
1302
1303				assert_eq!(
1304					proof_check.child_storage(child_info_2, &[14]).unwrap().unwrap(),
1305					vec![14]
1306				);
1307				assert_eq!(proof_check.child_storage(child_info_2, &[25]).unwrap(), None);
1308			}
1309		}
1310	}
1311
1312	/// This tests an edge case when recording a child trie access with a cache.
1313	///
1314	/// The accessed value/node is in the cache, but not the nodes to get to this value. So,
1315	/// the recorder will need to traverse the trie to access these nodes from the backend when the
1316	/// storage proof is generated.
1317	#[test]
1318	fn child_proof_recording_with_edge_cases_works() {
1319		child_proof_recording_with_edge_cases_works_inner(StateVersion::V0);
1320		child_proof_recording_with_edge_cases_works_inner(StateVersion::V1);
1321	}
1322	fn child_proof_recording_with_edge_cases_works_inner(state_version: StateVersion) {
1323		let child_info_1 = ChildInfo::new_default(b"sub1");
1324		let child_info_1 = &child_info_1;
1325		let contents = vec![
1326			(None, (0..64).map(|i| (vec![i], Some(vec![i]))).collect::<Vec<_>>()),
1327			(
1328				Some(child_info_1.clone()),
1329				(28..65)
1330					.map(|i| (vec![i], Some(vec![i])))
1331					// Some big value to ensure we get a new node
1332					.chain(std::iter::once((vec![65], Some(vec![65; 128]))))
1333					.collect(),
1334			),
1335		];
1336		let in_memory = new_in_mem::<BlakeTwo256>();
1337		let in_memory = in_memory.update(contents, state_version);
1338		let child_storage_keys = vec![child_info_1.to_owned()];
1339		let in_memory_root = in_memory
1340			.full_storage_root(
1341				std::iter::empty(),
1342				child_storage_keys.iter().map(|k| (k, std::iter::empty())),
1343				state_version,
1344			)
1345			.0;
1346
1347		let child_1_root =
1348			in_memory.child_storage_root(child_info_1, std::iter::empty(), state_version).0;
1349		let trie = in_memory.as_trie_backend();
1350		let nodes = {
1351			let backend = TrieBackendBuilder::wrap(trie).with_recorder(Default::default()).build();
1352			let value = backend.child_storage(child_info_1, &[65]).unwrap().unwrap();
1353			let value_hash = BlakeTwo256::hash(&value);
1354			assert_eq!(value, vec![65; 128]);
1355
1356			let proof = backend.extract_proof().unwrap();
1357
1358			let mut nodes = Vec::new();
1359			for node in proof.into_iter_nodes() {
1360				let hash = BlakeTwo256::hash(&node);
1361				// Only insert the node/value that contains the important data.
1362				if hash != value_hash {
1363					let node = sp_trie::NodeCodec::<BlakeTwo256>::decode(&node)
1364						.unwrap()
1365						.to_owned_node::<sp_trie::LayoutV1<BlakeTwo256>>()
1366						.unwrap();
1367
1368					if let Some(data) = node.data() {
1369						if data == &vec![65; 128] {
1370							nodes.push((hash, node));
1371						}
1372					}
1373				} else if hash == value_hash {
1374					nodes.push((hash, trie_db::node::NodeOwned::Value(node.into(), hash)));
1375				}
1376			}
1377
1378			nodes
1379		};
1380
1381		let cache = SharedTrieCache::<BlakeTwo256>::new(CacheSize::unlimited());
1382		{
1383			let local_cache = cache.local_cache();
1384			let mut trie_cache = local_cache.as_trie_db_cache(child_1_root);
1385
1386			// Put the value/node into the cache.
1387			for (hash, node) in nodes {
1388				trie_cache.get_or_insert_node(hash, &mut || Ok(node.clone())).unwrap();
1389
1390				if let Some(data) = node.data() {
1391					trie_cache.cache_value_for_key(&[65], (data.clone(), hash).into());
1392				}
1393			}
1394		}
1395
1396		{
1397			// Record the access
1398			let proving = TrieBackendBuilder::wrap(&trie)
1399				.with_recorder(Recorder::default())
1400				.with_cache(cache.local_cache())
1401				.build();
1402			assert_eq!(proving.child_storage(child_info_1, &[65]), Ok(Some(vec![65; 128])));
1403
1404			let proof = proving.extract_proof().unwrap();
1405			// And check that we have a correct proof.
1406			let proof_check =
1407				create_proof_check_backend::<BlakeTwo256>(in_memory_root.into(), proof).unwrap();
1408			assert_eq!(
1409				proof_check.child_storage(child_info_1, &[65]).unwrap().unwrap(),
1410				vec![65; 128]
1411			);
1412		}
1413	}
1414
1415	parameterized_test!(
1416		storage_proof_encoded_size_estimation_works,
1417		storage_proof_encoded_size_estimation_works_inner
1418	);
1419	fn storage_proof_encoded_size_estimation_works_inner(
1420		state_version: StateVersion,
1421		cache: Option<Cache>,
1422		recorder: Option<Recorder>,
1423	) {
1424		let has_cache = cache.is_some();
1425		let trie_backend = test_trie(state_version, cache, recorder);
1426		let keys = &[
1427			&b"key"[..],
1428			&b"value1"[..],
1429			&b"value2"[..],
1430			&b"doesnotexist"[..],
1431			&b"doesnotexist2"[..],
1432		];
1433
1434		fn check_estimation(
1435			backend: TrieBackend<
1436				impl TrieBackendStorage<BlakeTwo256>,
1437				BlakeTwo256,
1438				&'_ LocalTrieCache<BlakeTwo256>,
1439			>,
1440			has_cache: bool,
1441		) {
1442			let estimation = backend.essence.recorder.as_ref().unwrap().estimate_encoded_size();
1443			let storage_proof = backend.extract_proof().unwrap();
1444			let storage_proof_size =
1445				storage_proof.into_nodes().into_iter().map(|n| n.encoded_size()).sum::<usize>();
1446
1447			if has_cache {
1448				// Estimation is not entirely correct when we have values already cached.
1449				assert!(estimation >= storage_proof_size)
1450			} else {
1451				assert_eq!(storage_proof_size, estimation);
1452			}
1453		}
1454
1455		for n in 0..keys.len() {
1456			let backend = TrieBackendBuilder::wrap(&trie_backend)
1457				.with_recorder(Recorder::default())
1458				.build();
1459
1460			// Read n keys
1461			(0..n).for_each(|i| {
1462				backend.storage(keys[i]).unwrap();
1463			});
1464
1465			// Check the estimation
1466			check_estimation(backend, has_cache);
1467		}
1468	}
1469
1470	#[test]
1471	fn new_data_is_added_to_the_cache() {
1472		let shared_cache = SharedTrieCache::new(CacheSize::unlimited());
1473		let new_data = vec![
1474			(&b"new_data0"[..], Some(&b"0"[..])),
1475			(&b"new_data1"[..], Some(&b"1"[..])),
1476			(&b"new_data2"[..], Some(&b"2"[..])),
1477			(&b"new_data3"[..], Some(&b"3"[..])),
1478			(&b"new_data4"[..], Some(&b"4"[..])),
1479		];
1480
1481		let new_root = {
1482			let trie = test_trie(StateVersion::V1, Some(shared_cache.local_cache()), None);
1483			trie.storage_root(new_data.clone().into_iter(), StateVersion::V1).0
1484		};
1485
1486		let local_cache = shared_cache.local_cache();
1487		let mut cache = local_cache.as_trie_db_cache(new_root);
1488		// All the data should be cached now
1489		for (key, value) in new_data {
1490			assert_eq!(
1491				value.unwrap(),
1492				cache.lookup_value_for_key(key).unwrap().data().flatten().unwrap().as_ref()
1493			);
1494		}
1495	}
1496
1497	/// Test to ensure that recording the same `key` for different tries works as expected.
1498	///
1499	/// Each trie stores a different value under the same key. The values are big enough to
1500	/// be not inlined with `StateVersion::V1`, this is important to test the expected behavior. The
1501	/// trie recorder is expected to differentiate key access based on the different storage roots
1502	/// of the tries.
1503	#[test]
1504	fn recording_same_key_access_in_different_tries() {
1505		recording_same_key_access_in_different_tries_inner(StateVersion::V0);
1506		recording_same_key_access_in_different_tries_inner(StateVersion::V1);
1507	}
1508	fn recording_same_key_access_in_different_tries_inner(state_version: StateVersion) {
1509		let key = b"test_key".to_vec();
1510		// Use some big values to ensure that we don't keep them inline
1511		let top_trie_val = vec![1; 1024];
1512		let child_trie_1_val = vec![2; 1024];
1513		let child_trie_2_val = vec![3; 1024];
1514
1515		let child_info_1 = ChildInfo::new_default(b"sub1");
1516		let child_info_2 = ChildInfo::new_default(b"sub2");
1517		let child_info_1 = &child_info_1;
1518		let child_info_2 = &child_info_2;
1519		let contents = vec![
1520			(None, vec![(key.clone(), Some(top_trie_val.clone()))]),
1521			(Some(child_info_1.clone()), vec![(key.clone(), Some(child_trie_1_val.clone()))]),
1522			(Some(child_info_2.clone()), vec![(key.clone(), Some(child_trie_2_val.clone()))]),
1523		];
1524		let in_memory = new_in_mem::<BlakeTwo256>();
1525		let in_memory = in_memory.update(contents, state_version);
1526		let child_storage_keys = vec![child_info_1.to_owned(), child_info_2.to_owned()];
1527		let in_memory_root = in_memory
1528			.full_storage_root(
1529				std::iter::empty(),
1530				child_storage_keys.iter().map(|k| (k, std::iter::empty())),
1531				state_version,
1532			)
1533			.0;
1534		assert_eq!(in_memory.storage(&key).unwrap().unwrap(), top_trie_val);
1535		assert_eq!(in_memory.child_storage(child_info_1, &key).unwrap().unwrap(), child_trie_1_val);
1536		assert_eq!(in_memory.child_storage(child_info_2, &key).unwrap().unwrap(), child_trie_2_val);
1537
1538		for cache in [Some(SharedTrieCache::new(CacheSize::unlimited())), None] {
1539			// Run multiple times to have a different cache conditions.
1540			for i in 0..5 {
1541				eprintln!("Running with cache {}, iteration {}", cache.is_some(), i);
1542
1543				if let Some(cache) = &cache {
1544					if i == 2 {
1545						cache.reset_node_cache();
1546					} else if i == 3 {
1547						cache.reset_value_cache();
1548					}
1549				}
1550
1551				let trie = in_memory.as_trie_backend();
1552				let trie_root = trie.storage_root(std::iter::empty(), state_version).0;
1553				assert_eq!(in_memory_root, trie_root);
1554
1555				let proving = TrieBackendBuilder::wrap(&trie)
1556					.with_recorder(Recorder::default())
1557					.with_optional_cache(cache.as_ref().map(|c| c.local_cache()))
1558					.build();
1559				assert_eq!(proving.storage(&key).unwrap().unwrap(), top_trie_val);
1560				assert_eq!(
1561					proving.child_storage(child_info_1, &key).unwrap().unwrap(),
1562					child_trie_1_val
1563				);
1564				assert_eq!(
1565					proving.child_storage(child_info_2, &key).unwrap().unwrap(),
1566					child_trie_2_val
1567				);
1568
1569				let proof = proving.extract_proof().unwrap();
1570
1571				let proof_check =
1572					create_proof_check_backend::<BlakeTwo256>(in_memory_root.into(), proof)
1573						.unwrap();
1574
1575				assert_eq!(proof_check.storage(&key).unwrap().unwrap(), top_trie_val);
1576				assert_eq!(
1577					proof_check.child_storage(child_info_1, &key).unwrap().unwrap(),
1578					child_trie_1_val
1579				);
1580				assert_eq!(
1581					proof_check.child_storage(child_info_2, &key).unwrap().unwrap(),
1582					child_trie_2_val
1583				);
1584			}
1585		}
1586	}
1587}
sp_state_machine/trie_backend.rs

sp_state_machine/
trie_backend.rs
