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 scale_info::TypeInfo;
32use sp_inherents::{InherentData, InherentIdentifier, IsFatalError};
33use sp_runtime::traits::{Block as BlockT, NumberFor};
34
35pub use sp_inherents::Error;
36
37/// The identifier for the proof inherent.
38pub const INHERENT_IDENTIFIER: InherentIdentifier = *b"tx_proof";
39/// Proof trie value size.
40pub const CHUNK_SIZE: usize = 256;
41
42/// Type used for counting/tracking chunks.
43pub type ChunkIndex = u32;
44
45/// Hash of indexed data; the algorithm is reported in [`HashingAlgorithm`].
46pub type ContentHash = [u8; 32];
47
48/// IPFS [multicodec](https://github.com/multiformats/multicodec) content-type
49/// identifier for an indexed payload. Full list of values [here](https://github.com/multiformats/multicodec/blob/master/table.csv).
50pub type CidCodec = u64;
51
52/// Hashing algorithm used to compute a [`ContentHash`].
53#[derive(Clone, Copy, Debug, PartialEq, Eq, Encode, Decode, TypeInfo)]
54pub enum HashingAlgorithm {
55	/// BLAKE2b-256.
56	Blake2b256,
57	/// SHA2-256.
58	Sha2_256,
59	/// Keccak-256.
60	Keccak256,
61}
62
63/// Metadata for a single indexed transaction.
64#[derive(Clone, Debug, PartialEq, Eq, Encode, Decode, TypeInfo)]
65pub struct IndexedTransactionInfo {
66	/// Hash of the indexed data.
67	pub content_hash: ContentHash,
68	/// Size of the indexed data, in bytes.
69	pub size: u32,
70	/// Algorithm used to compute `content_hash`.
71	pub hashing: HashingAlgorithm,
72	/// CID codec for constructing the IPFS CID for the indexed data.
73	pub cid_codec: CidCodec,
74	/// Extrinsic index that produced this entry via `store` or `renew`.
75	///
76	/// `u32::MAX` when the producing pallet does not record it.
77	pub extrinsic_index: u32,
78}
79
80/// Errors that can occur while checking the storage proof.
81#[derive(Encode, Debug)]
82#[cfg_attr(feature = "std", derive(Decode))]
83pub enum InherentError {
84	InvalidProof,
85	TrieError,
86}
87
88impl IsFatalError for InherentError {
89	fn is_fatal_error(&self) -> bool {
90		true
91	}
92}
93
94/// Holds a chunk of data retrieved from storage along with
95/// a proof that the data was stored at that location in the trie.
96#[derive(Encode, Decode, DecodeWithMemTracking, Clone, PartialEq, Debug, scale_info::TypeInfo)]
97pub struct TransactionStorageProof {
98	/// Data chunk that is proved to exist.
99	pub chunk: Vec<u8>,
100	/// Trie nodes that compose the proof.
101	pub proof: Vec<Vec<u8>>,
102}
103
104/// Auxiliary trait to extract storage proof.
105pub trait TransactionStorageProofInherentData {
106	/// Get the proof.
107	fn storage_proof(&self) -> Result<Option<TransactionStorageProof>, Error>;
108}
109
110impl TransactionStorageProofInherentData for InherentData {
111	fn storage_proof(&self) -> Result<Option<TransactionStorageProof>, Error> {
112		self.get_data(&INHERENT_IDENTIFIER)
113	}
114}
115
116/// Provider for inherent data.
117#[cfg(feature = "std")]
118pub struct InherentDataProvider {
119	proof: Option<TransactionStorageProof>,
120}
121
122#[cfg(feature = "std")]
123impl InherentDataProvider {
124	pub fn new(proof: Option<TransactionStorageProof>) -> Self {
125		InherentDataProvider { proof }
126	}
127}
128
129#[cfg(feature = "std")]
130#[async_trait::async_trait]
131impl sp_inherents::InherentDataProvider for InherentDataProvider {
132	async fn provide_inherent_data(&self, inherent_data: &mut InherentData) -> Result<(), Error> {
133		if let Some(proof) = &self.proof {
134			inherent_data.put_data(INHERENT_IDENTIFIER, proof)
135		} else {
136			Ok(())
137		}
138	}
139
140	async fn try_handle_error(
141		&self,
142		identifier: &InherentIdentifier,
143		mut error: &[u8],
144	) -> Option<Result<(), Error>> {
145		if *identifier != INHERENT_IDENTIFIER {
146			return None;
147		}
148
149		let error = InherentError::decode(&mut error).ok()?;
150
151		Some(Err(Error::Application(Box::from(format!("{:?}", error)))))
152	}
153}
154
155/// A utility function to extract a chunk index from the source of randomness.
156///
157/// # Panics
158///
159/// This function panics if `total_chunks` is `0`.
160pub fn random_chunk(random_hash: &[u8], total_chunks: ChunkIndex) -> ChunkIndex {
161	let mut buf = [0u8; 8];
162	buf.copy_from_slice(&random_hash[0..8]);
163	let random_u64 = u64::from_be_bytes(buf);
164	(random_u64 % total_chunks as u64) as u32
165}
166
167/// A utility function to calculate the number of chunks.
168///
169/// * `bytes` - number of bytes
170pub fn num_chunks(bytes: u32) -> ChunkIndex {
171	(bytes as u64).div_ceil(CHUNK_SIZE as u64) as u32
172}
173
174/// A utility function to encode the transaction index as a trie key.
175///
176/// * `index` - chunk index.
177pub fn encode_index(index: ChunkIndex) -> Vec<u8> {
178	codec::Encode::encode(&codec::Compact(index))
179}
180
181/// An interface to request indexed data from the client.
182pub trait IndexedBody<B: BlockT> {
183	/// Get all indexed transactions for a block,
184	/// including renewed transactions.
185	///
186	/// Note that this will only fetch transactions
187	/// that are indexed by the runtime with `storage_index_transaction`.
188	fn block_indexed_body(&self, number: NumberFor<B>) -> Result<Option<Vec<Vec<u8>>>, Error>;
189
190	/// Get a block number for a block hash.
191	fn number(&self, hash: B::Hash) -> Result<Option<NumberFor<B>>, Error>;
192}
193
194#[cfg(feature = "std")]
195pub mod registration {
196	use super::*;
197	use sp_runtime::traits::{Block as BlockT, One, Saturating, Zero};
198	use sp_trie::TrieMut;
199
200	type Hasher = sp_core::Blake2Hasher;
201	type TrieLayout = sp_trie::LayoutV1<Hasher>;
202
203	/// Create a new inherent data provider instance for a given parent block hash.
204	pub fn new_data_provider<B, C>(
205		client: &C,
206		parent: &B::Hash,
207		retention_period: NumberFor<B>,
208	) -> Result<InherentDataProvider, Error>
209	where
210		B: BlockT,
211		C: IndexedBody<B>,
212	{
213		let parent_number = client.number(*parent)?.unwrap_or(Zero::zero());
214		let number = parent_number.saturating_add(One::one()).saturating_sub(retention_period);
215		if number.is_zero() {
216			// Too early to collect proofs.
217			return Ok(InherentDataProvider::new(None));
218		}
219
220		let proof = match client.block_indexed_body(number)? {
221			Some(transactions) => build_proof(parent.as_ref(), transactions)?,
222			None => {
223				// Nothing was indexed in that block.
224				None
225			},
226		};
227		Ok(InherentDataProvider::new(proof))
228	}
229
230	/// Build a proof for a given source of randomness and indexed transactions.
231	pub fn build_proof(
232		random_hash: &[u8],
233		transactions: Vec<Vec<u8>>,
234	) -> Result<Option<TransactionStorageProof>, Error> {
235		// Get total chunks, we will need it to generate a random chunk index.
236		let total_chunks: ChunkIndex =
237			transactions.iter().map(|t| num_chunks(t.len() as u32)).sum();
238		if total_chunks.is_zero() {
239			return Ok(None);
240		}
241		let selected_chunk_index = random_chunk(random_hash, total_chunks);
242
243		// Generate tries for each transaction.
244		let mut chunk_index = 0;
245		for transaction in transactions {
246			let mut selected_chunk_and_key = None;
247			let mut db = sp_trie::MemoryDB::<Hasher>::default();
248			let mut transaction_root = sp_trie::empty_trie_root::<TrieLayout>();
249			{
250				let mut trie =
251					sp_trie::TrieDBMutBuilder::<TrieLayout>::new(&mut db, &mut transaction_root)
252						.build();
253				let chunks = transaction.chunks(CHUNK_SIZE).map(|c| c.to_vec());
254				for (index, chunk) in chunks.enumerate() {
255					let index = encode_index(index as u32);
256					trie.insert(&index, &chunk).map_err(|e| Error::Application(Box::new(e)))?;
257					if chunk_index == selected_chunk_index {
258						selected_chunk_and_key = Some((chunk, index));
259					}
260					chunk_index += 1;
261				}
262				trie.commit();
263			}
264			if let Some((target_chunk, target_chunk_key)) = selected_chunk_and_key {
265				let chunk_proof = sp_trie::generate_trie_proof::<TrieLayout, _, _, _>(
266					&db,
267					transaction_root,
268					&[target_chunk_key],
269				)
270				.map_err(|e| Error::Application(Box::new(e)))?;
271
272				// We found the chunk and computed the proof root for the entire transaction,
273				// so there is no need to waste time calculating the subsequent transactions.
274				return Ok(Some(TransactionStorageProof {
275					proof: chunk_proof,
276					chunk: target_chunk,
277				}));
278			}
279		}
280
281		Err(Error::Application(Box::from(format!("No chunk (total_chunks: {total_chunks}) matched the selected_chunk_index: {selected_chunk_index}; logic error!"))))
282	}
283
284	#[test]
285	fn build_proof_check() {
286		use std::str::FromStr;
287		let random = [0u8; 32];
288		let proof = build_proof(&random, vec![vec![42]]).unwrap().unwrap();
289		let root = sp_core::H256::from_str(
290			"0xff8611a4d212fc161dae19dd57f0f1ba9309f45d6207da13f2d3eab4c6839e91",
291		)
292		.unwrap();
293		sp_trie::verify_trie_proof::<TrieLayout, _, _, _>(
294			&root,
295			&proof.proof,
296			&[(encode_index(0), Some(proof.chunk))],
297		)
298		.unwrap();
299
300		// Fail for empty transactions/chunks.
301		assert!(build_proof(&random, vec![]).unwrap().is_none());
302		assert!(build_proof(&random, vec![vec![]]).unwrap().is_none());
303	}
304
305	/// Round-trip: build a proof off-chain, verify it against a runtime-side
306	/// parallel view computed from the same input order. Catches position-mismatch
307	/// bugs where one side reorders the indexed body relative to the other.
308	#[test]
309	fn proof_round_trip_against_parallel_runtime_view() {
310		let payloads: Vec<Vec<u8>> = (0..4)
311			.map(|i: u8| {
312				let mut p = vec![0u8; 2 * CHUNK_SIZE];
313				for (j, byte) in p.iter_mut().enumerate() {
314					*byte = i.wrapping_mul(7).wrapping_add(j as u8);
315				}
316				p
317			})
318			.collect();
319
320		// Non-monotonic submission order so any sort would visibly disturb it.
321		let submission_order = [3usize, 0, 2, 1];
322
323		let from_indexed_body: Vec<Vec<u8>> =
324			submission_order.iter().map(|&i| payloads[i].clone()).collect();
325
326		struct TxInfo {
327			chunk_root: sp_core::H256,
328			size: u32,
329			block_chunks: ChunkIndex,
330		}
331		let mut runtime_view: Vec<TxInfo> = Vec::with_capacity(submission_order.len());
332		let mut cumulative: ChunkIndex = 0;
333		for &i in submission_order.iter() {
334			let payload = &payloads[i];
335			let mut db = sp_trie::MemoryDB::<Hasher>::default();
336			let mut transaction_root = sp_trie::empty_trie_root::<TrieLayout>();
337			{
338				let mut trie =
339					sp_trie::TrieDBMutBuilder::<TrieLayout>::new(&mut db, &mut transaction_root)
340						.build();
341				for (idx, chunk) in payload.chunks(CHUNK_SIZE).enumerate() {
342					trie.insert(&encode_index(idx as u32), chunk).unwrap();
343				}
344				trie.commit();
345			}
346			cumulative += num_chunks(payload.len() as u32);
347			runtime_view.push(TxInfo {
348				chunk_root: transaction_root,
349				size: payload.len() as u32,
350				block_chunks: cumulative,
351			});
352		}
353
354		// Sweep parent_hash so a position bug doesn't pass by chance for some chunks.
355		for seed in 0u8..16 {
356			let parent_hash = [seed; 32];
357
358			let proof = build_proof(&parent_hash, from_indexed_body.clone()).unwrap().unwrap();
359
360			let total_chunks = runtime_view.last().unwrap().block_chunks;
361			let selected_chunk_index = random_chunk(&parent_hash, total_chunks);
362			let tx_index = runtime_view
363				.binary_search_by_key(&selected_chunk_index, |info| {
364					info.block_chunks.saturating_sub(1)
365				})
366				.unwrap_or_else(|i| i);
367			let tx_info = &runtime_view[tx_index];
368			let tx_chunks = num_chunks(tx_info.size);
369			let prev_chunks = tx_info.block_chunks - tx_chunks;
370			let tx_chunk_index = selected_chunk_index - prev_chunks;
371
372			sp_trie::verify_trie_proof::<TrieLayout, _, _, _>(
373				&tx_info.chunk_root,
374				&proof.proof,
375				&[(encode_index(tx_chunk_index), Some(proof.chunk.clone()))],
376			)
377			.unwrap_or_else(|e| panic!("seed={seed}: {e:?}"));
378
379			let expected_chunk = payloads[submission_order[tx_index]]
380				.chunks(CHUNK_SIZE)
381				.nth(tx_chunk_index as usize)
382				.unwrap()
383				.to_vec();
384			assert_eq!(proof.chunk, expected_chunk);
385		}
386	}
387}
sp_transaction_storage_proof/lib.rs

sp_transaction_storage_proof/
lib.rs
