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

sp_transaction_storage_proof/
lib.rs
