tp_trie/
storage_proof.rs

1// This file is part of Tetcore.
2
3// Copyright (C) 2020-2021 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 tetcore_std::vec::Vec;
19use codec::{Encode, Decode};
20use tetsy_hash_db::{Hasher, HashDB};
21
22/// A proof that some set of key-value pairs are included in the storage trie. The proof contains
23/// the storage values so that the partial storage backend can be reconstructed by a verifier that
24/// does not already have access to the key-value pairs.
25///
26/// The proof consists of the set of serialized nodes in the storage trie accessed when looking up
27/// the keys covered by the proof. Verifying the proof requires constructing the partial trie from
28/// the serialized nodes and performing the key lookups.
29#[derive(Debug, PartialEq, Eq, Clone, Encode, Decode)]
30pub struct StorageProof {
31	trie_nodes: Vec<Vec<u8>>,
32}
33
34impl StorageProof {
35	/// Constructs a storage proof from a subset of encoded trie nodes in a storage backend.
36	pub fn new(trie_nodes: Vec<Vec<u8>>) -> Self {
37		StorageProof { trie_nodes }
38	}
39
40	/// Returns a new empty proof.
41	///
42	/// An empty proof is capable of only proving trivial statements (ie. that an empty set of
43	/// key-value pairs exist in storage).
44	pub fn empty() -> Self {
45		StorageProof {
46			trie_nodes: Vec::new(),
47		}
48	}
49
50	/// Returns whether this is an empty proof.
51	pub fn is_empty(&self) -> bool {
52		self.trie_nodes.is_empty()
53	}
54
55	/// Create an iterator over trie nodes constructed from the proof. The nodes are not guaranteed
56	/// to be traversed in any particular order.
57	pub fn iter_nodes(self) -> StorageProofNodeIterator {
58		StorageProofNodeIterator::new(self)
59	}
60
61	/// Creates a `MemoryDB` from `Self`.
62	pub fn into_memory_db<H: Hasher>(self) -> crate::MemoryDB<H> {
63		self.into()
64	}
65
66	/// Merges multiple storage proofs covering potentially different sets of keys into one proof
67	/// covering all keys. The merged proof output may be smaller than the aggregate size of the input
68	/// proofs due to deduplication of trie nodes.
69	pub fn merge<I>(proofs: I) -> Self where I: IntoIterator<Item=Self> {
70		let trie_nodes = proofs.into_iter()
71			.flat_map(|proof| proof.iter_nodes())
72			.collect::<tetcore_std::collections::btree_set::BTreeSet<_>>()
73			.into_iter()
74			.collect();
75
76		Self { trie_nodes }
77	}
78}
79
80/// An iterator over trie nodes constructed from a storage proof. The nodes are not guaranteed to
81/// be traversed in any particular order.
82pub struct StorageProofNodeIterator {
83	inner: <Vec<Vec<u8>> as IntoIterator>::IntoIter,
84}
85
86impl StorageProofNodeIterator {
87	fn new(proof: StorageProof) -> Self {
88		StorageProofNodeIterator {
89			inner: proof.trie_nodes.into_iter(),
90		}
91	}
92}
93
94impl Iterator for StorageProofNodeIterator {
95	type Item = Vec<u8>;
96
97	fn next(&mut self) -> Option<Self::Item> {
98		self.inner.next()
99	}
100}
101
102impl<H: Hasher> From<StorageProof> for crate::MemoryDB<H> {
103	fn from(proof: StorageProof) -> Self {
104		let mut db = crate::MemoryDB::default();
105		for item in proof.iter_nodes() {
106			db.insert(crate::EMPTY_PREFIX, &item);
107		}
108		db
109	}
110}
tp_trie/storage_proof.rs

tp_trie/
storage_proof.rs
