sp_trie/
storage_proof.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
18use alloc::{collections::btree_set::BTreeSet, vec::Vec};
19use codec::{Decode, DecodeWithMemTracking, Encode};
20use core::iter::{DoubleEndedIterator, IntoIterator};
21use hash_db::{HashDB, Hasher};
22use scale_info::TypeInfo;
23
24// Note that `LayoutV1` usage here (proof compaction) is compatible
25// with `LayoutV0`.
26use crate::LayoutV1 as Layout;
27
28/// Error associated with the `storage_proof` module.
29#[derive(Encode, Decode, Clone, Eq, PartialEq, Debug, TypeInfo)]
30pub enum StorageProofError {
31	/// The proof contains duplicate nodes.
32	DuplicateNodes,
33}
34
35/// A proof that some set of key-value pairs are included in the storage trie. The proof contains
36/// the storage values so that the partial storage backend can be reconstructed by a verifier that
37/// does not already have access to the key-value pairs.
38///
39/// The proof consists of the set of serialized nodes in the storage trie accessed when looking up
40/// the keys covered by the proof. Verifying the proof requires constructing the partial trie from
41/// the serialized nodes and performing the key lookups.
42#[derive(Debug, PartialEq, Eq, Clone, Encode, Decode, DecodeWithMemTracking, TypeInfo)]
43pub struct StorageProof {
44	trie_nodes: BTreeSet<Vec<u8>>,
45}
46
47impl StorageProof {
48	/// Constructs a storage proof from a subset of encoded trie nodes in a storage backend.
49	pub fn new(trie_nodes: impl IntoIterator<Item = Vec<u8>>) -> Self {
50		StorageProof { trie_nodes: BTreeSet::from_iter(trie_nodes) }
51	}
52
53	/// Constructs a storage proof from a subset of encoded trie nodes in a storage backend.
54	///
55	/// Returns an error if the provided subset of encoded trie nodes contains duplicates.
56	pub fn new_with_duplicate_nodes_check(
57		trie_nodes: impl IntoIterator<Item = Vec<u8>>,
58	) -> Result<Self, StorageProofError> {
59		let mut trie_nodes_set = BTreeSet::new();
60		for node in trie_nodes {
61			if !trie_nodes_set.insert(node) {
62				return Err(StorageProofError::DuplicateNodes);
63			}
64		}
65
66		Ok(StorageProof { trie_nodes: trie_nodes_set })
67	}
68
69	/// Returns a new empty proof.
70	///
71	/// An empty proof is capable of only proving trivial statements (ie. that an empty set of
72	/// key-value pairs exist in storage).
73	pub fn empty() -> Self {
74		StorageProof { trie_nodes: BTreeSet::new() }
75	}
76
77	/// Returns whether this is an empty proof.
78	pub fn is_empty(&self) -> bool {
79		self.trie_nodes.is_empty()
80	}
81
82	/// Returns the number of nodes in the proof.
83	pub fn len(&self) -> usize {
84		self.trie_nodes.len()
85	}
86
87	/// Convert into an iterator over encoded trie nodes in lexicographical order constructed
88	/// from the proof.
89	pub fn into_iter_nodes(self) -> impl Sized + DoubleEndedIterator<Item = Vec<u8>> {
90		self.trie_nodes.into_iter()
91	}
92
93	/// Create an iterator over encoded trie nodes in lexicographical order constructed
94	/// from the proof.
95	pub fn iter_nodes(&self) -> impl Sized + DoubleEndedIterator<Item = &Vec<u8>> {
96		self.trie_nodes.iter()
97	}
98
99	/// Convert into plain node vector.
100	pub fn into_nodes(self) -> BTreeSet<Vec<u8>> {
101		self.trie_nodes
102	}
103
104	/// Creates a [`MemoryDB`](crate::MemoryDB) from `Self`.
105	pub fn into_memory_db<H: Hasher>(self) -> crate::MemoryDB<H> {
106		self.into()
107	}
108
109	/// Creates a [`MemoryDB`](crate::MemoryDB) from `Self` reference.
110	pub fn to_memory_db<H: Hasher>(&self) -> crate::MemoryDB<H> {
111		self.into()
112	}
113
114	/// Merges multiple storage proofs covering potentially different sets of keys into one proof
115	/// covering all keys. The merged proof output may be smaller than the aggregate size of the
116	/// input proofs due to deduplication of trie nodes.
117	pub fn merge(proofs: impl IntoIterator<Item = Self>) -> Self {
118		let trie_nodes = proofs
119			.into_iter()
120			.flat_map(|proof| proof.into_iter_nodes())
121			.collect::<BTreeSet<_>>()
122			.into_iter()
123			.collect();
124
125		Self { trie_nodes }
126	}
127
128	/// Encode as a compact proof with default trie layout.
129	pub fn into_compact_proof<H: Hasher>(
130		self,
131		root: H::Out,
132	) -> Result<CompactProof, crate::CompactProofError<H::Out, crate::Error<H::Out>>> {
133		let db = self.into_memory_db();
134		crate::encode_compact::<Layout<H>, crate::MemoryDB<H>>(&db, &root)
135	}
136
137	/// Encode as a compact proof with default trie layout.
138	pub fn to_compact_proof<H: Hasher>(
139		&self,
140		root: H::Out,
141	) -> Result<CompactProof, crate::CompactProofError<H::Out, crate::Error<H::Out>>> {
142		let db = self.to_memory_db();
143		crate::encode_compact::<Layout<H>, crate::MemoryDB<H>>(&db, &root)
144	}
145
146	/// Returns the estimated encoded size of the compact proof.
147	///
148	/// Running this operation is a slow operation (build the whole compact proof) and should only
149	/// be in non sensitive path.
150	///
151	/// Return `None` on error.
152	pub fn encoded_compact_size<H: Hasher>(self, root: H::Out) -> Option<usize> {
153		let compact_proof = self.into_compact_proof::<H>(root);
154		compact_proof.ok().map(|p| p.encoded_size())
155	}
156}
157
158impl<H: Hasher> From<StorageProof> for crate::MemoryDB<H> {
159	fn from(proof: StorageProof) -> Self {
160		From::from(&proof)
161	}
162}
163
164impl<H: Hasher> From<&StorageProof> for crate::MemoryDB<H> {
165	fn from(proof: &StorageProof) -> Self {
166		let mut db = crate::MemoryDB::with_hasher(crate::RandomState::default());
167		proof.iter_nodes().for_each(|n| {
168			db.insert(crate::EMPTY_PREFIX, &n);
169		});
170		db
171	}
172}
173
174/// Storage proof in compact form.
175#[derive(Debug, PartialEq, Eq, Clone, Encode, Decode, DecodeWithMemTracking, TypeInfo)]
176pub struct CompactProof {
177	pub encoded_nodes: Vec<Vec<u8>>,
178}
179
180impl CompactProof {
181	/// Return an iterator on the compact encoded nodes.
182	pub fn iter_compact_encoded_nodes(&self) -> impl Iterator<Item = &[u8]> {
183		self.encoded_nodes.iter().map(Vec::as_slice)
184	}
185
186	/// Decode to a full storage_proof.
187	///
188	/// The decoded root is always checked against `expected_root`.
189	pub fn to_storage_proof<H: Hasher>(
190		&self,
191		expected_root: &H::Out,
192	) -> Result<(StorageProof, H::Out), crate::CompactProofError<H::Out, crate::Error<H::Out>>> {
193		let mut db = crate::MemoryDB::<H>::new(&[]);
194		let root = crate::decode_compact::<Layout<H>, _, _>(
195			&mut db,
196			self.iter_compact_encoded_nodes(),
197			expected_root,
198		)?;
199		Ok((
200			StorageProof::new(db.drain().into_iter().filter_map(|kv| {
201				if (kv.1).1 > 0 {
202					Some((kv.1).0)
203				} else {
204					None
205				}
206			})),
207			root,
208		))
209	}
210
211	/// Convert self into a [`MemoryDB`](crate::MemoryDB).
212	///
213	/// `expected_root` is the expected root of this compact proof. The decoded root is always
214	/// checked against it.
215	///
216	/// Returns the memory db and the root of the trie.
217	pub fn to_memory_db<H: Hasher>(
218		&self,
219		expected_root: &H::Out,
220	) -> Result<(crate::MemoryDB<H>, H::Out), crate::CompactProofError<H::Out, crate::Error<H::Out>>>
221	{
222		let mut db = crate::MemoryDB::<H>::new(&[]);
223		let root = crate::decode_compact::<Layout<H>, _, _>(
224			&mut db,
225			self.iter_compact_encoded_nodes(),
226			expected_root,
227		)?;
228
229		Ok((db, root))
230	}
231}
232
233#[cfg(test)]
234pub mod tests {
235	use super::*;
236	use crate::{tests::create_storage_proof, StorageProof};
237
238	type Hasher = sp_core::Blake2Hasher;
239	type Layout = crate::LayoutV1<Hasher>;
240
241	const TEST_DATA: &[(&[u8], &[u8])] =
242		&[(b"key1", &[1; 64]), (b"key2", &[2; 64]), (b"key3", &[3; 64]), (b"key11", &[4; 64])];
243
244	#[test]
245	fn proof_with_duplicate_nodes_is_rejected() {
246		let (raw_proof, _root) = create_storage_proof::<Layout>(TEST_DATA);
247		assert!(matches!(
248			StorageProof::new_with_duplicate_nodes_check(raw_proof),
249			Err(StorageProofError::DuplicateNodes)
250		));
251	}
252
253	#[test]
254	fn invalid_compact_proof_does_not_panic_when_decoding() {
255		let invalid_proof = CompactProof { encoded_nodes: vec![vec![135]] };
256		// Decoding fails before the root is ever compared, so any expected root will do.
257		let result = invalid_proof.to_memory_db::<Hasher>(&Default::default());
258		assert!(result.is_err());
259	}
260}
sp_trie/storage_proof.rs

sp_trie/
storage_proof.rs
