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

sp_state_machine/
trie_backend.rs
