sp_runtime/proving_trie/
mod.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//! Types for merkle tries compatible with the runtime.
19
20pub mod base16;
21pub mod base2;
22
23use crate::{Decode, DispatchError, Encode, MaxEncodedLen, TypeInfo};
24#[cfg(feature = "serde")]
25use crate::{Deserialize, Serialize};
26use sp_std::vec::Vec;
27use sp_trie::{trie_types::TrieError as SpTrieError, VerifyError};
28
29/// A runtime friendly error type for tries.
30#[derive(Eq, PartialEq, Clone, Copy, Encode, Decode, Debug, TypeInfo, MaxEncodedLen)]
31#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
32pub enum TrieError {
33	/* From TrieError */
34	/// Attempted to create a trie with a state root not in the DB.
35	InvalidStateRoot,
36	/// Trie item not found in the database,
37	IncompleteDatabase,
38	/// A value was found in the trie with a nibble key that was not byte-aligned.
39	ValueAtIncompleteKey,
40	/// Corrupt Trie item.
41	DecoderError,
42	/// Hash is not value.
43	InvalidHash,
44	/* From VerifyError */
45	/// The statement being verified contains multiple key-value pairs with the same key.
46	DuplicateKey,
47	/// The proof contains at least one extraneous node.
48	ExtraneousNode,
49	/// The proof contains at least one extraneous value which should have been omitted from the
50	/// proof.
51	ExtraneousValue,
52	/// The proof contains at least one extraneous hash reference the should have been omitted.
53	ExtraneousHashReference,
54	/// The proof contains an invalid child reference that exceeds the hash length.
55	InvalidChildReference,
56	/// The proof indicates that an expected value was not found in the trie.
57	ValueMismatch,
58	/// The proof is missing trie nodes required to verify.
59	IncompleteProof,
60	/// The root hash computed from the proof is incorrect.
61	RootMismatch,
62	/// One of the proof nodes could not be decoded.
63	DecodeError,
64}
65
66impl<T> From<SpTrieError<T>> for TrieError {
67	fn from(error: SpTrieError<T>) -> Self {
68		match error {
69			SpTrieError::InvalidStateRoot(..) => Self::InvalidStateRoot,
70			SpTrieError::IncompleteDatabase(..) => Self::IncompleteDatabase,
71			SpTrieError::ValueAtIncompleteKey(..) => Self::ValueAtIncompleteKey,
72			SpTrieError::DecoderError(..) => Self::DecoderError,
73			SpTrieError::InvalidHash(..) => Self::InvalidHash,
74		}
75	}
76}
77
78impl<T, U> From<VerifyError<T, U>> for TrieError {
79	fn from(error: VerifyError<T, U>) -> Self {
80		match error {
81			VerifyError::DuplicateKey(..) => Self::DuplicateKey,
82			VerifyError::ExtraneousNode => Self::ExtraneousNode,
83			VerifyError::ExtraneousValue(..) => Self::ExtraneousValue,
84			VerifyError::ExtraneousHashReference(..) => Self::ExtraneousHashReference,
85			VerifyError::InvalidChildReference(..) => Self::InvalidChildReference,
86			VerifyError::ValueMismatch(..) => Self::ValueMismatch,
87			VerifyError::IncompleteProof => Self::IncompleteProof,
88			VerifyError::RootMismatch(..) => Self::RootMismatch,
89			VerifyError::DecodeError(..) => Self::DecodeError,
90		}
91	}
92}
93
94impl From<TrieError> for &'static str {
95	fn from(e: TrieError) -> &'static str {
96		match e {
97			TrieError::InvalidStateRoot => "The state root is not in the database.",
98			TrieError::IncompleteDatabase => "A trie item was not found in the database.",
99			TrieError::ValueAtIncompleteKey =>
100				"A value was found with a key that is not byte-aligned.",
101			TrieError::DecoderError => "A corrupt trie item was encountered.",
102			TrieError::InvalidHash => "The hash does not match the expected value.",
103			TrieError::DuplicateKey => "The proof contains duplicate keys.",
104			TrieError::ExtraneousNode => "The proof contains extraneous nodes.",
105			TrieError::ExtraneousValue => "The proof contains extraneous values.",
106			TrieError::ExtraneousHashReference => "The proof contains extraneous hash references.",
107			TrieError::InvalidChildReference => "The proof contains an invalid child reference.",
108			TrieError::ValueMismatch => "The proof indicates a value mismatch.",
109			TrieError::IncompleteProof => "The proof is incomplete.",
110			TrieError::RootMismatch => "The root hash computed from the proof is incorrect.",
111			TrieError::DecodeError => "One of the proof nodes could not be decoded.",
112		}
113	}
114}
115
116/// An interface for creating, interacting with, and creating proofs in a merkle trie.
117pub trait ProvingTrie<Hashing, Key, Value>
118where
119	Self: Sized,
120	Hashing: sp_core::Hasher,
121{
122	/// Create a new instance of a `ProvingTrie` using an iterator of key/value pairs.
123	fn generate_for<I>(items: I) -> Result<Self, DispatchError>
124	where
125		I: IntoIterator<Item = (Key, Value)>;
126	/// Access the underlying trie root.
127	fn root(&self) -> &Hashing::Out;
128	/// Query a value contained within the current trie. Returns `None` if the
129	/// the value does not exist in the trie.
130	fn query(&self, key: &Key) -> Option<Value>;
131	/// Create a proof that can be used to verify a key and its value are in the trie.
132	fn create_proof(&self, key: &Key) -> Result<Vec<u8>, DispatchError>;
133	/// Verify the existence of `key` and `value` in a given trie root and proof.
134	fn verify_proof(
135		root: &Hashing::Out,
136		proof: &[u8],
137		key: &Key,
138		value: &Value,
139	) -> Result<(), DispatchError>;
140}
141
142/// This trait is one strategy that can be used to benchmark a trie proof verification for the
143/// runtime. This strategy assumes that the majority complexity of verifying a merkle proof comes
144/// from computing hashes to recreate the merkle root. This trait converts the the proof, some
145/// bytes, to the number of hashes we expect to execute to verify that proof.
146pub trait ProofToHashes {
147	/// The Proof type we will use to determine the number of hashes.
148	type Proof: ?Sized;
149	/// This function returns the number of hashes we expect to calculate based on the
150	/// size of the proof. This is used for benchmarking, so for worst case scenario, we should
151	/// round up.
152	///
153	/// The major complexity of doing a `verify_proof` is computing the hashes needed
154	/// to calculate the merkle root. For tries, it should be easy to predict the depth
155	/// of the trie (which is equivalent to the hashes), by looking at the length of the proof.
156	fn proof_to_hashes(proof: &Self::Proof) -> Result<u32, DispatchError>;
157}
158
159#[cfg(test)]
160mod tests {
161	use super::*;
162	use crate::traits::BlakeTwo256;
163
164	// A trie which simulates a trie of accounts (u32) and balances (u128).
165	type BalanceTrie2 = base2::BasicProvingTrie<BlakeTwo256, u32, u128>;
166	type BalanceTrie16 = base16::BasicProvingTrie<BlakeTwo256, u32, u128>;
167
168	#[test]
169	fn basic_api_usage_base_2() {
170		let balance_trie = BalanceTrie2::generate_for((0..100u32).map(|i| (i, i.into()))).unwrap();
171		let root = *balance_trie.root();
172		assert_eq!(balance_trie.query(&69), Some(69));
173		assert_eq!(balance_trie.query(&6969), None);
174		let proof = balance_trie.create_proof(&69u32).unwrap();
175		assert_eq!(BalanceTrie2::verify_proof(&root, &proof, &69u32, &69u128), Ok(()));
176	}
177
178	#[test]
179	fn basic_api_usage_base_16() {
180		let balance_trie = BalanceTrie16::generate_for((0..100u32).map(|i| (i, i.into()))).unwrap();
181		let root = *balance_trie.root();
182		assert_eq!(balance_trie.query(&69), Some(69));
183		assert_eq!(balance_trie.query(&6969), None);
184		let proof = balance_trie.create_proof(&69u32).unwrap();
185		assert_eq!(BalanceTrie16::verify_proof(&root, &proof, &69u32, &69u128), Ok(()));
186	}
187}
sp_runtime/proving_trie/mod.rs

sp_runtime/proving_trie/
mod.rs
