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

sp_runtime/proving_trie/
mod.rs
