frame_support/traits/
proving.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//! Provides functionality for verifying proofs.
19
20use alloc::vec::Vec;
21use codec::{Decode, Encode};
22use sp_core::Hasher;
23use sp_runtime::DispatchError;
24
25// Re-export the `proving_trie` types and traits.
26pub use sp_runtime::proving_trie::*;
27
28/// Something that can verify the existence of some data in a given proof.
29pub trait VerifyExistenceProof {
30	/// The proof type.
31	type Proof;
32	/// The hash type.
33	type Hash;
34
35	/// Verify the given `proof`.
36	///
37	/// Ensures that the `proof` was build for `root` and returns the proved data.
38	fn verify_proof(proof: Self::Proof, root: &Self::Hash) -> Result<Vec<u8>, DispatchError>;
39}
40
41/// Implements [`VerifyExistenceProof`] using a binary merkle tree.
42pub struct BinaryMerkleTreeProver<H>(core::marker::PhantomData<H>);
43
44impl<H: Hasher> VerifyExistenceProof for BinaryMerkleTreeProver<H>
45where
46	H::Out: Decode + Encode,
47{
48	type Proof = binary_merkle_tree::MerkleProof<H::Out, Vec<u8>>;
49	type Hash = H::Out;
50
51	fn verify_proof(proof: Self::Proof, root: &Self::Hash) -> Result<Vec<u8>, DispatchError> {
52		if proof.root != *root {
53			return Err(TrieError::RootMismatch.into());
54		}
55
56		if binary_merkle_tree::verify_proof::<H, _, _>(
57			&proof.root,
58			proof.proof,
59			proof.number_of_leaves,
60			proof.leaf_index,
61			&proof.leaf,
62		) {
63			Ok(proof.leaf)
64		} else {
65			Err(TrieError::IncompleteProof.into())
66		}
67	}
68}
69
70impl<H: Hasher> ProofToHashes for BinaryMerkleTreeProver<H> {
71	type Proof = binary_merkle_tree::MerkleProof<H::Out, Vec<u8>>;
72
73	// This base 2 merkle trie includes a `proof` field which is a `Vec<Hash>`.
74	// The length of this vector tells us the depth of the proof, and how many
75	// hashes we need to calculate.
76	fn proof_to_hashes(proof: &Self::Proof) -> Result<u32, DispatchError> {
77		let depth = proof.proof.len();
78		Ok(depth as u32)
79	}
80}
81
82/// Proof used by [`SixteenPatriciaMerkleTreeProver`] for [`VerifyExistenceProof`].
83#[derive(Encode, Decode, Clone)]
84pub struct SixteenPatriciaMerkleTreeExistenceProof {
85	/// The key of the value to prove.
86	pub key: Vec<u8>,
87	/// The value for that the existence is proved.
88	pub value: Vec<u8>,
89	/// The encoded nodes to prove the existence of the data under `key`.
90	pub proof: Vec<Vec<u8>>,
91}
92
93/// Implements [`VerifyExistenceProof`] using a 16-patricia merkle tree.
94pub struct SixteenPatriciaMerkleTreeProver<H>(core::marker::PhantomData<H>);
95
96impl<H: Hasher> VerifyExistenceProof for SixteenPatriciaMerkleTreeProver<H> {
97	type Proof = SixteenPatriciaMerkleTreeExistenceProof;
98	type Hash = H::Out;
99
100	fn verify_proof(proof: Self::Proof, root: &Self::Hash) -> Result<Vec<u8>, DispatchError> {
101		sp_trie::verify_trie_proof::<sp_trie::LayoutV1<H>, _, _, _>(
102			&root,
103			&proof.proof,
104			[&(&proof.key, Some(&proof.value))],
105		)
106		.map_err(|err| TrieError::from(err).into())
107		.map(|_| proof.value)
108	}
109}
110
111impl<H: Hasher> ProofToHashes for SixteenPatriciaMerkleTreeProver<H> {
112	type Proof = SixteenPatriciaMerkleTreeExistenceProof;
113
114	// This base 16 trie uses a raw proof of `Vec<Vec<u8>`, where the length of the first `Vec`
115	// is the depth of the trie. We can use this to predict the number of hashes.
116	fn proof_to_hashes(proof: &Self::Proof) -> Result<u32, DispatchError> {
117		let depth = proof.proof.len();
118		Ok(depth as u32)
119	}
120}
121
122#[cfg(test)]
123mod tests {
124	use super::*;
125	use sp_runtime::{
126		proving_trie::{base16::BasicProvingTrie, ProvingTrie},
127		traits::BlakeTwo256,
128	};
129
130	#[test]
131	fn verify_binary_merkle_tree_prover_works() {
132		let proof = binary_merkle_tree::merkle_proof::<BlakeTwo256, _, _>(
133			vec![b"hey".encode(), b"yes".encode()],
134			1,
135		);
136		let root = proof.root;
137
138		assert_eq!(
139			BinaryMerkleTreeProver::<BlakeTwo256>::verify_proof(proof, &root).unwrap(),
140			b"yes".encode()
141		);
142	}
143
144	#[test]
145	fn verify_sixteen_patricia_merkle_tree_prover_works() {
146		let trie = BasicProvingTrie::<BlakeTwo256, u32, _>::generate_for(vec![
147			(0u32, String::from("hey")),
148			(1u32, String::from("yes")),
149		])
150		.unwrap();
151		let proof = trie.create_proof(&1u32).unwrap();
152		let structured_proof: Vec<Vec<u8>> = Decode::decode(&mut &proof[..]).unwrap();
153		let root = *trie.root();
154
155		let proof = SixteenPatriciaMerkleTreeExistenceProof {
156			key: 1u32.encode(),
157			value: String::from("yes").encode(),
158			proof: structured_proof,
159		};
160
161		assert_eq!(
162			SixteenPatriciaMerkleTreeProver::<BlakeTwo256>::verify_proof(proof, &root).unwrap(),
163			String::from("yes").encode()
164		);
165	}
166
167	#[test]
168	fn proof_to_hashes_sixteen() {
169		let mut i: u32 = 1;
170
171		// Compute log base 16 and round up
172		let log16 = |x: u32| -> u32 {
173			let x_f64 = x as f64;
174			let log16_x = (x_f64.ln() / 16_f64.ln()).ceil();
175			log16_x as u32
176		};
177
178		while i < 10_000_000 {
179			let trie = BasicProvingTrie::<BlakeTwo256, u32, _>::generate_for(
180				(0..i).map(|i| (i, u128::from(i))),
181			)
182			.unwrap();
183			let proof = trie.create_proof(&0).unwrap();
184			let structured_proof: Vec<Vec<u8>> = Decode::decode(&mut &proof[..]).unwrap();
185			let root = *trie.root();
186
187			let proof = SixteenPatriciaMerkleTreeExistenceProof {
188				key: 0u32.encode(),
189				value: 0u128.encode(),
190				proof: structured_proof,
191			};
192			let hashes =
193				SixteenPatriciaMerkleTreeProver::<BlakeTwo256>::proof_to_hashes(&proof).unwrap();
194			let log16 = log16(i).max(1);
195			assert_eq!(hashes, log16);
196
197			assert_eq!(
198				SixteenPatriciaMerkleTreeProver::<BlakeTwo256>::verify_proof(proof.clone(), &root)
199					.unwrap(),
200				proof.value
201			);
202
203			i = i * 10;
204		}
205	}
206
207	#[test]
208	fn proof_to_hashes_binary() {
209		let mut i: u32 = 1;
210		while i < 10_000_000 {
211			let proof = binary_merkle_tree::merkle_proof::<BlakeTwo256, _, _>(
212				(0..i).map(|i| u128::from(i).encode()),
213				0,
214			);
215			let root = proof.root;
216
217			let hashes = BinaryMerkleTreeProver::<BlakeTwo256>::proof_to_hashes(&proof).unwrap();
218			let log2 = (i as f64).log2().ceil() as u32;
219			assert_eq!(hashes, log2);
220
221			assert_eq!(
222				BinaryMerkleTreeProver::<BlakeTwo256>::verify_proof(proof, &root).unwrap(),
223				0u128.encode()
224			);
225
226			i = i * 10;
227		}
228	}
229}
frame_support/traits/proving.rs

frame_support/traits/
proving.rs
