pezsp_runtime/proving_trie/
mod.rs

1// This file is part of Bizinikiwi.
2
3// Copyright (C) Parity Technologies (UK) Ltd. and Dijital Kurdistan Tech Institute
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 pezsp_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			},
113			TrieError::DecoderError => "A corrupt trie item was encountered.",
114			TrieError::InvalidHash => "The hash does not match the expected value.",
115			TrieError::DuplicateKey => "The proof contains duplicate keys.",
116			TrieError::ExtraneousNode => "The proof contains extraneous nodes.",
117			TrieError::ExtraneousValue => "The proof contains extraneous values.",
118			TrieError::ExtraneousHashReference => "The proof contains extraneous hash references.",
119			TrieError::InvalidChildReference => "The proof contains an invalid child reference.",
120			TrieError::ValueMismatch => "The proof indicates a value mismatch.",
121			TrieError::IncompleteProof => "The proof is incomplete.",
122			TrieError::RootMismatch => "The root hash computed from the proof is incorrect.",
123			TrieError::DecodeError => "One of the proof nodes could not be decoded.",
124		}
125	}
126}
127
128/// An interface for creating, interacting with, and creating proofs in a merkle trie.
129pub trait ProvingTrie<Hashing, Key, Value>
130where
131	Self: Sized,
132	Hashing: pezsp_core::Hasher,
133{
134	/// Create a new instance of a `ProvingTrie` using an iterator of key/value pairs.
135	fn generate_for<I>(items: I) -> Result<Self, DispatchError>
136	where
137		I: IntoIterator<Item = (Key, Value)>;
138	/// Access the underlying trie root.
139	fn root(&self) -> &Hashing::Out;
140	/// Query a value contained within the current trie. Returns `None` if the
141	/// the value does not exist in the trie.
142	fn query(&self, key: &Key) -> Option<Value>;
143	/// Create a proof that can be used to verify a key and its value are in the trie.
144	fn create_proof(&self, key: &Key) -> Result<Vec<u8>, DispatchError>;
145	/// Verify the existence of `key` and `value` in a given trie root and proof.
146	fn verify_proof(
147		root: &Hashing::Out,
148		proof: &[u8],
149		key: &Key,
150		value: &Value,
151	) -> Result<(), DispatchError>;
152}
153
154/// This trait is one strategy that can be used to benchmark a trie proof verification for the
155/// runtime. This strategy assumes that the majority complexity of verifying a merkle proof comes
156/// from computing hashes to recreate the merkle root. This trait converts the the proof, some
157/// bytes, to the number of hashes we expect to execute to verify that proof.
158pub trait ProofToHashes {
159	/// The Proof type we will use to determine the number of hashes.
160	type Proof: ?Sized;
161	/// This function returns the number of hashes we expect to calculate based on the
162	/// size of the proof. This is used for benchmarking, so for worst case scenario, we should
163	/// round up.
164	///
165	/// The major complexity of doing a `verify_proof` is computing the hashes needed
166	/// to calculate the merkle root. For tries, it should be easy to predict the depth
167	/// of the trie (which is equivalent to the hashes), by looking at the length of the proof.
168	fn proof_to_hashes(proof: &Self::Proof) -> Result<u32, DispatchError>;
169}
170
171#[cfg(test)]
172mod tests {
173	use super::*;
174	use crate::traits::BlakeTwo256;
175
176	// A trie which simulates a trie of accounts (u32) and balances (u128).
177	type BalanceTrie2 = base2::BasicProvingTrie<BlakeTwo256, u32, u128>;
178	type BalanceTrie16 = base16::BasicProvingTrie<BlakeTwo256, u32, u128>;
179
180	#[test]
181	fn basic_api_usage_base_2() {
182		let balance_trie = BalanceTrie2::generate_for((0..100u32).map(|i| (i, i.into()))).unwrap();
183		let root = *balance_trie.root();
184		assert_eq!(balance_trie.query(&69), Some(69));
185		assert_eq!(balance_trie.query(&6969), None);
186		let proof = balance_trie.create_proof(&69u32).unwrap();
187		assert_eq!(BalanceTrie2::verify_proof(&root, &proof, &69u32, &69u128), Ok(()));
188	}
189
190	#[test]
191	fn basic_api_usage_base_16() {
192		let balance_trie = BalanceTrie16::generate_for((0..100u32).map(|i| (i, i.into()))).unwrap();
193		let root = *balance_trie.root();
194		assert_eq!(balance_trie.query(&69), Some(69));
195		assert_eq!(balance_trie.query(&6969), None);
196		let proof = balance_trie.create_proof(&69u32).unwrap();
197		assert_eq!(BalanceTrie16::verify_proof(&root, &proof, &69u32, &69u128), Ok(()));
198	}
199}
pezsp_runtime/proving_trie/mod.rs

pezsp_runtime/proving_trie/
mod.rs
