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

sp_transaction_storage_proof/
lib.rs
