sp_transaction_storage_proof/
lib.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//! Storage proof primitives. Contains types and basic code to extract storage
19//! proofs for indexed transactions.
20
21#![cfg_attr(not(feature = "std"), no_std)]
22
23pub mod runtime_api;
24
25extern crate alloc;
26
27use core::result::Result;
28
29use alloc::vec::Vec;
30use codec::{Decode, DecodeWithMemTracking, Encode};
31use sp_inherents::{InherentData, InherentIdentifier, IsFatalError};
32use sp_runtime::traits::{Block as BlockT, NumberFor};
33
34pub use sp_inherents::Error;
35
36/// The identifier for the proof inherent.
37pub const INHERENT_IDENTIFIER: InherentIdentifier = *b"tx_proof";
38/// Proof trie value size.
39pub const CHUNK_SIZE: usize = 256;
40
41/// Type used for counting/tracking chunks.
42pub type ChunkIndex = u32;
43
44/// Errors that can occur while checking the storage proof.
45#[derive(Encode, Debug)]
46#[cfg_attr(feature = "std", derive(Decode))]
47pub enum InherentError {
48	InvalidProof,
49	TrieError,
50}
51
52impl IsFatalError for InherentError {
53	fn is_fatal_error(&self) -> bool {
54		true
55	}
56}
57
58/// Holds a chunk of data retrieved from storage along with
59/// a proof that the data was stored at that location in the trie.
60#[derive(Encode, Decode, DecodeWithMemTracking, Clone, PartialEq, Debug, scale_info::TypeInfo)]
61pub struct TransactionStorageProof {
62	/// Data chunk that is proved to exist.
63	pub chunk: Vec<u8>,
64	/// Trie nodes that compose the proof.
65	pub proof: Vec<Vec<u8>>,
66}
67
68/// Auxiliary trait to extract storage proof.
69pub trait TransactionStorageProofInherentData {
70	/// Get the proof.
71	fn storage_proof(&self) -> Result<Option<TransactionStorageProof>, Error>;
72}
73
74impl TransactionStorageProofInherentData for InherentData {
75	fn storage_proof(&self) -> Result<Option<TransactionStorageProof>, Error> {
76		self.get_data(&INHERENT_IDENTIFIER)
77	}
78}
79
80/// Provider for inherent data.
81#[cfg(feature = "std")]
82pub struct InherentDataProvider {
83	proof: Option<TransactionStorageProof>,
84}
85
86#[cfg(feature = "std")]
87impl InherentDataProvider {
88	pub fn new(proof: Option<TransactionStorageProof>) -> Self {
89		InherentDataProvider { proof }
90	}
91}
92
93#[cfg(feature = "std")]
94#[async_trait::async_trait]
95impl sp_inherents::InherentDataProvider for InherentDataProvider {
96	async fn provide_inherent_data(&self, inherent_data: &mut InherentData) -> Result<(), Error> {
97		if let Some(proof) = &self.proof {
98			inherent_data.put_data(INHERENT_IDENTIFIER, proof)
99		} else {
100			Ok(())
101		}
102	}
103
104	async fn try_handle_error(
105		&self,
106		identifier: &InherentIdentifier,
107		mut error: &[u8],
108	) -> Option<Result<(), Error>> {
109		if *identifier != INHERENT_IDENTIFIER {
110			return None;
111		}
112
113		let error = InherentError::decode(&mut error).ok()?;
114
115		Some(Err(Error::Application(Box::from(format!("{:?}", error)))))
116	}
117}
118
119/// A utility function to extract a chunk index from the source of randomness.
120///
121/// # Panics
122///
123/// This function panics if `total_chunks` is `0`.
124pub fn random_chunk(random_hash: &[u8], total_chunks: ChunkIndex) -> ChunkIndex {
125	let mut buf = [0u8; 8];
126	buf.copy_from_slice(&random_hash[0..8]);
127	let random_u64 = u64::from_be_bytes(buf);
128	(random_u64 % total_chunks as u64) as u32
129}
130
131/// A utility function to calculate the number of chunks.
132///
133/// * `bytes` - number of bytes
134pub fn num_chunks(bytes: u32) -> ChunkIndex {
135	(bytes as u64).div_ceil(CHUNK_SIZE as u64) as u32
136}
137
138/// A utility function to encode the transaction index as a trie key.
139///
140/// * `index` - chunk index.
141pub fn encode_index(index: ChunkIndex) -> Vec<u8> {
142	codec::Encode::encode(&codec::Compact(index))
143}
144
145/// An interface to request indexed data from the client.
146pub trait IndexedBody<B: BlockT> {
147	/// Get all indexed transactions for a block,
148	/// including renewed transactions.
149	///
150	/// Note that this will only fetch transactions
151	/// that are indexed by the runtime with `storage_index_transaction`.
152	fn block_indexed_body(&self, number: NumberFor<B>) -> Result<Option<Vec<Vec<u8>>>, Error>;
153
154	/// Get a block number for a block hash.
155	fn number(&self, hash: B::Hash) -> Result<Option<NumberFor<B>>, Error>;
156}
157
158#[cfg(feature = "std")]
159pub mod registration {
160	use super::*;
161	use sp_runtime::traits::{Block as BlockT, One, Saturating, Zero};
162	use sp_trie::TrieMut;
163
164	type Hasher = sp_core::Blake2Hasher;
165	type TrieLayout = sp_trie::LayoutV1<Hasher>;
166
167	/// Create a new inherent data provider instance for a given parent block hash.
168	pub fn new_data_provider<B, C>(
169		client: &C,
170		parent: &B::Hash,
171		retention_period: NumberFor<B>,
172	) -> Result<InherentDataProvider, Error>
173	where
174		B: BlockT,
175		C: IndexedBody<B>,
176	{
177		let parent_number = client.number(*parent)?.unwrap_or(Zero::zero());
178		let number = parent_number.saturating_add(One::one()).saturating_sub(retention_period);
179		if number.is_zero() {
180			// Too early to collect proofs.
181			return Ok(InherentDataProvider::new(None));
182		}
183
184		let proof = match client.block_indexed_body(number)? {
185			Some(transactions) => build_proof(parent.as_ref(), transactions)?,
186			None => {
187				// Nothing was indexed in that block.
188				None
189			},
190		};
191		Ok(InherentDataProvider::new(proof))
192	}
193
194	/// Build a proof for a given source of randomness and indexed transactions.
195	pub fn build_proof(
196		random_hash: &[u8],
197		transactions: Vec<Vec<u8>>,
198	) -> Result<Option<TransactionStorageProof>, Error> {
199		// Get total chunks, we will need it to generate a random chunk index.
200		let total_chunks: ChunkIndex =
201			transactions.iter().map(|t| num_chunks(t.len() as u32)).sum();
202		if total_chunks.is_zero() {
203			return Ok(None);
204		}
205		let selected_chunk_index = random_chunk(random_hash, total_chunks);
206
207		// Generate tries for each transaction.
208		let mut chunk_index = 0;
209		for transaction in transactions {
210			let mut selected_chunk_and_key = None;
211			let mut db = sp_trie::MemoryDB::<Hasher>::default();
212			let mut transaction_root = sp_trie::empty_trie_root::<TrieLayout>();
213			{
214				let mut trie =
215					sp_trie::TrieDBMutBuilder::<TrieLayout>::new(&mut db, &mut transaction_root)
216						.build();
217				let chunks = transaction.chunks(CHUNK_SIZE).map(|c| c.to_vec());
218				for (index, chunk) in chunks.enumerate() {
219					let index = encode_index(index as u32);
220					trie.insert(&index, &chunk).map_err(|e| Error::Application(Box::new(e)))?;
221					if chunk_index == selected_chunk_index {
222						selected_chunk_and_key = Some((chunk, index));
223					}
224					chunk_index += 1;
225				}
226				trie.commit();
227			}
228			if let Some((target_chunk, target_chunk_key)) = selected_chunk_and_key {
229				let chunk_proof = sp_trie::generate_trie_proof::<TrieLayout, _, _, _>(
230					&db,
231					transaction_root,
232					&[target_chunk_key],
233				)
234				.map_err(|e| Error::Application(Box::new(e)))?;
235
236				// We found the chunk and computed the proof root for the entire transaction,
237				// so there is no need to waste time calculating the subsequent transactions.
238				return Ok(Some(TransactionStorageProof {
239					proof: chunk_proof,
240					chunk: target_chunk,
241				}));
242			}
243		}
244
245		Err(Error::Application(Box::from(format!("No chunk (total_chunks: {total_chunks}) matched the selected_chunk_index: {selected_chunk_index}; logic error!"))))
246	}
247
248	#[test]
249	fn build_proof_check() {
250		use std::str::FromStr;
251		let random = [0u8; 32];
252		let proof = build_proof(&random, vec![vec![42]]).unwrap().unwrap();
253		let root = sp_core::H256::from_str(
254			"0xff8611a4d212fc161dae19dd57f0f1ba9309f45d6207da13f2d3eab4c6839e91",
255		)
256		.unwrap();
257		sp_trie::verify_trie_proof::<TrieLayout, _, _, _>(
258			&root,
259			&proof.proof,
260			&[(encode_index(0), Some(proof.chunk))],
261		)
262		.unwrap();
263
264		// Fail for empty transactions/chunks.
265		assert!(build_proof(&random, vec![]).unwrap().is_none());
266		assert!(build_proof(&random, vec![vec![]]).unwrap().is_none());
267	}
268}
sp_transaction_storage_proof/lib.rs

sp_transaction_storage_proof/
lib.rs
