pallet_transaction_storage/
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//! Transaction storage pallet. Indexes transactions and manages storage proofs.
19
20// Ensure we're `no_std` when compiling for Wasm.
21#![cfg_attr(not(feature = "std"), no_std)]
22
23mod benchmarking;
24pub mod weights;
25
26#[cfg(test)]
27mod mock;
28#[cfg(test)]
29mod tests;
30
31extern crate alloc;
32
33use alloc::vec::Vec;
34use codec::{Decode, Encode, MaxEncodedLen};
35use core::fmt::Debug;
36use frame_support::{
37	dispatch::GetDispatchInfo,
38	pallet_prelude::InvalidTransaction,
39	traits::{
40		fungible::{hold::Balanced, Credit, Inspect, Mutate, MutateHold},
41		OnUnbalanced,
42	},
43};
44use frame_system::pallet_prelude::BlockNumberFor;
45use sp_runtime::traits::{BlakeTwo256, Dispatchable, Hash, One, Saturating, Zero};
46use sp_transaction_storage_proof::{
47	encode_index, num_chunks, random_chunk, ChunkIndex, InherentError, TransactionStorageProof,
48	CHUNK_SIZE, INHERENT_IDENTIFIER,
49};
50
51/// A type alias for the balance type from this pallet's point of view.
52type BalanceOf<T> =
53	<<T as Config>::Currency as Inspect<<T as frame_system::Config>::AccountId>>::Balance;
54pub type CreditOf<T> = Credit<<T as frame_system::Config>::AccountId, <T as Config>::Currency>;
55
56// Re-export pallet items so that they can be accessed from the crate namespace.
57pub use pallet::*;
58pub use weights::WeightInfo;
59
60/// Default retention period for data (in blocks).
61pub const DEFAULT_RETENTION_PERIOD: u32 = 100800;
62
63// TODO: https://github.com/paritytech/polkadot-bulletin-chain/issues/139 - Clarify purpose of allocator limits and decide whether to remove or use these constants.
64/// Maximum bytes that can be stored in one transaction.
65// Setting higher limit also requires raising the allocator limit.
66pub const DEFAULT_MAX_TRANSACTION_SIZE: u32 = 8 * 1024 * 1024;
67pub const DEFAULT_MAX_BLOCK_TRANSACTIONS: u32 = 512;
68
69/// Encountered an impossible situation, implies a bug.
70pub const IMPOSSIBLE: InvalidTransaction = InvalidTransaction::Custom(0);
71/// Data size is not in the allowed range.
72pub const BAD_DATA_SIZE: InvalidTransaction = InvalidTransaction::Custom(1);
73/// Renewed extrinsic not found.
74pub const RENEWED_NOT_FOUND: InvalidTransaction = InvalidTransaction::Custom(2);
75/// Authorization was not found.
76pub const AUTHORIZATION_NOT_FOUND: InvalidTransaction = InvalidTransaction::Custom(3);
77/// Authorization has not expired.
78pub const AUTHORIZATION_NOT_EXPIRED: InvalidTransaction = InvalidTransaction::Custom(4);
79
80/// Number of transactions and bytes covered by an authorization.
81#[derive(PartialEq, Eq, Debug, Encode, Decode, scale_info::TypeInfo, MaxEncodedLen)]
82pub struct AuthorizationExtent {
83	/// Number of transactions.
84	pub transactions: u32,
85	/// Number of bytes.
86	pub bytes: u64,
87}
88
89/// Hash of a stored blob of data.
90type ContentHash = [u8; 32];
91
92/// The scope of an authorization.
93#[derive(Encode, Decode, scale_info::TypeInfo, MaxEncodedLen)]
94enum AuthorizationScope<AccountId> {
95	/// Authorization for the given account to store arbitrary data.
96	Account(AccountId),
97	/// Authorization for anyone to store data with a specific hash.
98	Preimage(ContentHash),
99}
100
101type AuthorizationScopeFor<T> = AuthorizationScope<<T as frame_system::Config>::AccountId>;
102
103/// An authorization to store data.
104#[derive(Encode, Decode, scale_info::TypeInfo, MaxEncodedLen)]
105struct Authorization<BlockNumber> {
106	/// Extent of the authorization (number of transactions/bytes).
107	extent: AuthorizationExtent,
108	/// The block at which this authorization expires.
109	expiration: BlockNumber,
110}
111
112type AuthorizationFor<T> = Authorization<BlockNumberFor<T>>;
113
114/// State data for a stored transaction.
115#[derive(Encode, Decode, Clone, Debug, PartialEq, Eq, scale_info::TypeInfo, MaxEncodedLen)]
116pub struct TransactionInfo {
117	/// Chunk trie root.
118	chunk_root: <BlakeTwo256 as Hash>::Output,
119	/// Plain hash of indexed data.
120	content_hash: <BlakeTwo256 as Hash>::Output,
121	/// Size of indexed data in bytes.
122	size: u32,
123	/// Total number of chunks added in the block with this transaction. This
124	/// is used to find transaction info by block chunk index using binary search.
125	///
126	/// Cumulative value of all previous transactions in the block; the last transaction holds the
127	/// total chunks.
128	block_chunks: ChunkIndex,
129}
130
131impl TransactionInfo {
132	/// Get the number of total chunks.
133	///
134	/// See the `block_chunks` field of [`TransactionInfo`] for details.
135	pub fn total_chunks(txs: &[TransactionInfo]) -> ChunkIndex {
136		txs.last().map_or(0, |t| t.block_chunks)
137	}
138}
139
140#[frame_support::pallet]
141pub mod pallet {
142	use super::*;
143	use frame_support::pallet_prelude::*;
144	use frame_system::pallet_prelude::*;
145
146	/// A reason for this pallet placing a hold on funds.
147	#[pallet::composite_enum]
148	pub enum HoldReason {
149		/// The funds are held as deposit for the used storage.
150		StorageFeeHold,
151	}
152
153	#[pallet::config]
154	pub trait Config: frame_system::Config {
155		/// The overarching event type.
156		#[allow(deprecated)]
157		type RuntimeEvent: From<Event<Self>> + IsType<<Self as frame_system::Config>::RuntimeEvent>;
158		/// A dispatchable call.
159		type RuntimeCall: Parameter
160			+ Dispatchable<RuntimeOrigin = Self::RuntimeOrigin>
161			+ GetDispatchInfo
162			+ From<frame_system::Call<Self>>;
163		/// The fungible type for this pallet.
164		type Currency: Mutate<Self::AccountId>
165			+ MutateHold<Self::AccountId, Reason = Self::RuntimeHoldReason>
166			+ Balanced<Self::AccountId>;
167		/// The overarching runtime hold reason.
168		type RuntimeHoldReason: From<HoldReason>;
169		/// Handler for the unbalanced decrease when fees are burned.
170		type FeeDestination: OnUnbalanced<CreditOf<Self>>;
171		/// Weight information for extrinsics in this pallet.
172		type WeightInfo: WeightInfo;
173		/// Maximum number of indexed transactions in the block.
174		#[pallet::constant]
175		type MaxBlockTransactions: Get<u32>;
176		/// Maximum data set in a single transaction in bytes.
177		#[pallet::constant]
178		type MaxTransactionSize: Get<u32>;
179	}
180
181	#[pallet::error]
182	pub enum Error<T> {
183		/// Attempted to call `store`/`renew` outside of block execution.
184		BadContext,
185		/// Data size is not in the allowed range.
186		BadDataSize,
187		/// Too many transactions in the block.
188		TooManyTransactions,
189		/// Invalid configuration.
190		NotConfigured,
191		/// Renewed extrinsic is not found.
192		RenewedNotFound,
193		/// Proof was not expected in this block.
194		UnexpectedProof,
195		/// Proof failed verification.
196		InvalidProof,
197		/// Missing storage proof.
198		MissingProof,
199		/// Unable to verify proof because state data is missing.
200		MissingStateData,
201		/// Double proof check in the block.
202		DoubleCheck,
203		/// Storage proof was not checked in the block.
204		ProofNotChecked,
205		/// Authorization was not found.
206		AuthorizationNotFound,
207		/// Authorization has not expired.
208		AuthorizationNotExpired,
209	}
210
211	#[pallet::pallet]
212	pub struct Pallet<T>(_);
213
214	#[pallet::hooks]
215	impl<T: Config> Hooks<BlockNumberFor<T>> for Pallet<T> {
216		fn on_initialize(n: BlockNumberFor<T>) -> Weight {
217			// TODO: https://github.com/paritytech/polkadot-sdk/issues/10203 - Replace this with benchmarked weights.
218			let mut weight = Weight::zero();
219			let db_weight = T::DbWeight::get();
220
221			// Drop obsolete roots. The proof for `obsolete` will be checked later
222			// in this block, so we drop `obsolete` - 1.
223			weight.saturating_accrue(db_weight.reads(1));
224			let period = Self::retention_period();
225			let obsolete = n.saturating_sub(period.saturating_add(One::one()));
226			if obsolete > Zero::zero() {
227				weight.saturating_accrue(db_weight.writes(1));
228				Transactions::<T>::remove(obsolete);
229			}
230
231			// For `on_finalize`
232			weight.saturating_accrue(db_weight.reads_writes(3, 1));
233			weight
234		}
235
236		fn on_finalize(n: BlockNumberFor<T>) {
237			assert!(
238				ProofChecked::<T>::take() || {
239					// Proof is not required for early or empty blocks.
240					let number = frame_system::Pallet::<T>::block_number();
241					let period = Self::retention_period();
242					let target_number = number.saturating_sub(period);
243
244					target_number.is_zero() || {
245						// An empty block means no transactions were stored, relying on the fact
246						// below that we store transactions only if they contain chunks.
247						!Transactions::<T>::contains_key(target_number)
248					}
249				},
250				"Storage proof must be checked once in the block"
251			);
252
253			// Insert new transactions, iff they have chunks.
254			let transactions = BlockTransactions::<T>::take();
255			let total_chunks = TransactionInfo::total_chunks(&transactions);
256			if total_chunks != 0 {
257				Transactions::<T>::insert(n, transactions);
258			}
259		}
260
261		fn integrity_test() {
262			assert!(
263				!T::MaxBlockTransactions::get().is_zero(),
264				"MaxTransactionSize must be greater than zero"
265			);
266			assert!(
267				!T::MaxTransactionSize::get().is_zero(),
268				"MaxTransactionSize must be greater than zero"
269			);
270			let default_period = DEFAULT_RETENTION_PERIOD.into();
271			let retention_period = GenesisConfig::<T>::default().retention_period;
272			assert_eq!(
273				retention_period, default_period,
274				"GenesisConfig.retention_period must match DEFAULT_RETENTION_PERIOD"
275			);
276		}
277	}
278
279	#[pallet::call]
280	impl<T: Config> Pallet<T> {
281		/// Index and store data off chain. Minimum data size is 1 byte, maximum is
282		/// `MaxTransactionSize`. Data will be removed after `RetentionPeriod` blocks, unless
283		/// `renew` is called.
284		///
285		/// Emits [`Stored`](Event::Stored) when successful.
286		///
287		/// ## Complexity
288		///
289		/// O(n*log(n)) of data size, as all data is pushed to an in-memory trie.
290		#[pallet::call_index(0)]
291		#[pallet::weight(T::WeightInfo::store(data.len() as u32))]
292		pub fn store(origin: OriginFor<T>, data: Vec<u8>) -> DispatchResult {
293			// In the case of a regular unsigned transaction, this should have been checked by
294			// pre_dispatch. In the case of a regular signed transaction, this should have been
295			// checked by pre_dispatch_signed.
296			Self::ensure_data_size_ok(data.len())?;
297			let sender = ensure_signed(origin)?;
298			Self::apply_fee(sender, data.len() as u32)?;
299
300			// Chunk data and compute storage root
301			let chunks: Vec<_> = data.chunks(CHUNK_SIZE).map(|c| c.to_vec()).collect();
302			let chunk_count = chunks.len() as u32;
303			debug_assert_eq!(chunk_count, num_chunks(data.len() as u32));
304			let root = sp_io::trie::blake2_256_ordered_root(chunks, sp_runtime::StateVersion::V1);
305
306			let content_hash = sp_io::hashing::blake2_256(&data);
307			let extrinsic_index =
308				frame_system::Pallet::<T>::extrinsic_index().ok_or(Error::<T>::BadContext)?;
309			sp_io::transaction_index::index(extrinsic_index, data.len() as u32, content_hash);
310
311			let mut index = 0;
312			BlockTransactions::<T>::mutate(|transactions| {
313				if transactions.len() + 1 > T::MaxBlockTransactions::get() as usize {
314					return Err(Error::<T>::TooManyTransactions);
315				}
316				let total_chunks = TransactionInfo::total_chunks(&transactions) + chunk_count;
317				index = transactions.len() as u32;
318				transactions
319					.try_push(TransactionInfo {
320						chunk_root: root,
321						size: data.len() as u32,
322						content_hash: content_hash.into(),
323						block_chunks: total_chunks,
324					})
325					.map_err(|_| Error::<T>::TooManyTransactions)
326			})?;
327			Self::deposit_event(Event::Stored { index, content_hash });
328			Ok(())
329		}
330
331		/// Renew previously stored data. Parameters are the block number that contains previous
332		/// `store` or `renew` call and transaction index within that block. Transaction index is
333		/// emitted in the `Stored` or `Renewed` event. Applies same fees as `store`.
334		///
335		/// Emits [`Renewed`](Event::Renewed) when successful.
336		///
337		/// ## Complexity
338		///
339		/// O(1).
340		#[pallet::call_index(1)]
341		#[pallet::weight(T::WeightInfo::renew())]
342		pub fn renew(
343			origin: OriginFor<T>,
344			block: BlockNumberFor<T>,
345			index: u32,
346		) -> DispatchResultWithPostInfo {
347			let sender = ensure_signed(origin)?;
348			let info = Self::transaction_info(block, index).ok_or(Error::<T>::RenewedNotFound)?;
349
350			// In the case of a regular unsigned transaction, this should have been checked by
351			// pre_dispatch. In the case of a regular signed transaction, this should have been
352			// checked by pre_dispatch_signed.
353			Self::ensure_data_size_ok(info.size as usize)?;
354
355			let extrinsic_index =
356				frame_system::Pallet::<T>::extrinsic_index().ok_or(Error::<T>::BadContext)?;
357			Self::apply_fee(sender, info.size)?;
358			let content_hash = info.content_hash.into();
359			sp_io::transaction_index::renew(extrinsic_index, content_hash);
360
361			let mut index = 0;
362			BlockTransactions::<T>::mutate(|transactions| {
363				if transactions.len() + 1 > T::MaxBlockTransactions::get() as usize {
364					return Err(Error::<T>::TooManyTransactions);
365				}
366				let chunks = num_chunks(info.size);
367				let total_chunks = TransactionInfo::total_chunks(&transactions) + chunks;
368				index = transactions.len() as u32;
369				transactions
370					.try_push(TransactionInfo {
371						chunk_root: info.chunk_root,
372						size: info.size,
373						content_hash: info.content_hash,
374						block_chunks: total_chunks,
375					})
376					.map_err(|_| Error::<T>::TooManyTransactions)
377			})?;
378			Self::deposit_event(Event::Renewed { index, content_hash });
379			Ok(().into())
380		}
381
382		/// Check storage proof for block number `block_number() - RetentionPeriod`. If such a block
383		/// does not exist, the proof is expected to be `None`.
384		///
385		/// ## Complexity
386		///
387		/// Linear w.r.t the number of indexed transactions in the proved block for random probing.
388		/// There's a DB read for each transaction.
389		#[pallet::call_index(2)]
390		#[pallet::weight((T::WeightInfo::check_proof_max(), DispatchClass::Mandatory))]
391		pub fn check_proof(
392			origin: OriginFor<T>,
393			proof: TransactionStorageProof,
394		) -> DispatchResultWithPostInfo {
395			ensure_none(origin)?;
396			ensure!(!ProofChecked::<T>::get(), Error::<T>::DoubleCheck);
397
398			// Get the target block metadata.
399			let number = frame_system::Pallet::<T>::block_number();
400			let period = Self::retention_period();
401			let target_number = number.saturating_sub(period);
402			ensure!(!target_number.is_zero(), Error::<T>::UnexpectedProof);
403			let transactions =
404				Transactions::<T>::get(target_number).ok_or(Error::<T>::MissingStateData)?;
405
406			// Verify the proof with a "random" chunk (randomness is based on the parent hash).
407			let parent_hash = frame_system::Pallet::<T>::parent_hash();
408			Self::verify_chunk_proof(proof, parent_hash.as_ref(), transactions.to_vec())?;
409			ProofChecked::<T>::put(true);
410			Self::deposit_event(Event::ProofChecked);
411			Ok(().into())
412		}
413	}
414
415	#[pallet::event]
416	#[pallet::generate_deposit(pub(super) fn deposit_event)]
417	pub enum Event<T: Config> {
418		/// Stored data under specified index.
419		Stored { index: u32, content_hash: ContentHash },
420		/// Renewed data under specified index.
421		Renewed { index: u32, content_hash: ContentHash },
422		/// Storage proof was successfully checked.
423		ProofChecked,
424		/// An account `who` was authorized to store `bytes` bytes in `transactions` transactions.
425		AccountAuthorized { who: T::AccountId, transactions: u32, bytes: u64 },
426		/// An authorization for account `who` was refreshed.
427		AccountAuthorizationRefreshed { who: T::AccountId },
428		/// Authorization was given for a preimage of `content_hash` (not exceeding `max_size`) to
429		/// be stored by anyone.
430		PreimageAuthorized { content_hash: ContentHash, max_size: u64 },
431		/// An authorization for a preimage of `content_hash` was refreshed.
432		PreimageAuthorizationRefreshed { content_hash: ContentHash },
433		/// An expired account authorization was removed.
434		ExpiredAccountAuthorizationRemoved { who: T::AccountId },
435		/// An expired preimage authorization was removed.
436		ExpiredPreimageAuthorizationRemoved { content_hash: ContentHash },
437	}
438
439	/// Authorizations, keyed by scope.
440	#[pallet::storage]
441	pub(super) type Authorizations<T: Config> =
442		StorageMap<_, Blake2_128Concat, AuthorizationScopeFor<T>, AuthorizationFor<T>, OptionQuery>;
443
444	/// Collection of transaction metadata by block number.
445	#[pallet::storage]
446	pub type Transactions<T: Config> = StorageMap<
447		_,
448		Blake2_128Concat,
449		BlockNumberFor<T>,
450		BoundedVec<TransactionInfo, T::MaxBlockTransactions>,
451		OptionQuery,
452	>;
453
454	#[pallet::storage]
455	/// Storage fee per byte.
456	pub type ByteFee<T: Config> = StorageValue<_, BalanceOf<T>>;
457
458	#[pallet::storage]
459	/// Storage fee per transaction.
460	pub type EntryFee<T: Config> = StorageValue<_, BalanceOf<T>>;
461
462	/// Number of blocks for which stored data must be retained.
463	///
464	/// Data older than `RetentionPeriod` blocks is eligible for removal unless it
465	/// has been explicitly renewed. Validators are required to prove possession of
466	/// data corresponding to block `N - RetentionPeriod` when producing block `N`.
467	#[pallet::storage]
468	pub type RetentionPeriod<T: Config> = StorageValue<_, BlockNumberFor<T>, ValueQuery>;
469
470	// Intermediates
471	#[pallet::storage]
472	pub type BlockTransactions<T: Config> =
473		StorageValue<_, BoundedVec<TransactionInfo, T::MaxBlockTransactions>, ValueQuery>;
474
475	/// Was the proof checked in this block?
476	#[pallet::storage]
477	pub type ProofChecked<T: Config> = StorageValue<_, bool, ValueQuery>;
478
479	#[pallet::genesis_config]
480	pub struct GenesisConfig<T: Config> {
481		pub byte_fee: BalanceOf<T>,
482		pub entry_fee: BalanceOf<T>,
483		pub retention_period: BlockNumberFor<T>,
484	}
485
486	impl<T: Config> Default for GenesisConfig<T> {
487		fn default() -> Self {
488			Self {
489				byte_fee: 10u32.into(),
490				entry_fee: 1000u32.into(),
491				retention_period: DEFAULT_RETENTION_PERIOD.into(),
492			}
493		}
494	}
495
496	#[pallet::genesis_build]
497	impl<T: Config> BuildGenesisConfig for GenesisConfig<T> {
498		fn build(&self) {
499			ByteFee::<T>::put(self.byte_fee);
500			EntryFee::<T>::put(self.entry_fee);
501			RetentionPeriod::<T>::put(self.retention_period);
502		}
503	}
504
505	#[pallet::inherent]
506	impl<T: Config> ProvideInherent for Pallet<T> {
507		type Call = Call<T>;
508		type Error = InherentError;
509		const INHERENT_IDENTIFIER: InherentIdentifier = INHERENT_IDENTIFIER;
510
511		fn create_inherent(data: &InherentData) -> Option<Self::Call> {
512			let proof = data
513				.get_data::<TransactionStorageProof>(&Self::INHERENT_IDENTIFIER)
514				.unwrap_or(None);
515			proof.map(|proof| Call::check_proof { proof })
516		}
517
518		fn check_inherent(_call: &Self::Call, _data: &InherentData) -> Result<(), Self::Error> {
519			Ok(())
520		}
521
522		fn is_inherent(call: &Self::Call) -> bool {
523			matches!(call, Call::check_proof { .. })
524		}
525	}
526
527	impl<T: Config> Pallet<T> {
528		/// Get transaction storage information from outside of this pallet.
529		pub fn transaction_roots(
530			block: BlockNumberFor<T>,
531		) -> Option<BoundedVec<TransactionInfo, T::MaxBlockTransactions>> {
532			Transactions::<T>::get(block)
533		}
534
535		pub fn indexed_transactions(
536			block: BlockNumberFor<T>,
537		) -> alloc::vec::Vec<sp_transaction_storage_proof::IndexedTransactionInfo> {
538			const RAW_CID_CODEC: sp_transaction_storage_proof::CidCodec = 0x55;
539
540			Transactions::<T>::get(block)
541				.map(|txs| {
542					txs.into_iter()
543						.map(|tx| sp_transaction_storage_proof::IndexedTransactionInfo {
544							content_hash: tx.content_hash.into(),
545							size: tx.size,
546							hashing: sp_transaction_storage_proof::HashingAlgorithm::Blake2b256,
547							cid_codec: RAW_CID_CODEC,
548							extrinsic_index: u32::MAX,
549						})
550						.collect()
551				})
552				.unwrap_or_default()
553		}
554
555		/// Get ByteFee storage information from the outside of this pallet.
556		pub fn byte_fee() -> Option<BalanceOf<T>> {
557			ByteFee::<T>::get()
558		}
559		/// Get EntryFee storage information from the outside of this pallet.
560		pub fn entry_fee() -> Option<BalanceOf<T>> {
561			EntryFee::<T>::get()
562		}
563		/// Get RetentionPeriod storage information from the outside of this pallet.
564		pub fn retention_period() -> BlockNumberFor<T> {
565			RetentionPeriod::<T>::get()
566		}
567
568		fn apply_fee(sender: T::AccountId, size: u32) -> DispatchResult {
569			let byte_fee = ByteFee::<T>::get().ok_or(Error::<T>::NotConfigured)?;
570			let entry_fee = EntryFee::<T>::get().ok_or(Error::<T>::NotConfigured)?;
571			let fee = byte_fee.saturating_mul(size.into()).saturating_add(entry_fee);
572			T::Currency::hold(&HoldReason::StorageFeeHold.into(), &sender, fee)?;
573			let (credit, _remainder) =
574				T::Currency::slash(&HoldReason::StorageFeeHold.into(), &sender, fee);
575			debug_assert!(_remainder.is_zero());
576			T::FeeDestination::on_unbalanced(credit);
577			Ok(())
578		}
579
580		/// Returns `true` if a blob of the given size can be stored.
581		fn data_size_ok(size: usize) -> bool {
582			(size > 0) && (size <= T::MaxTransactionSize::get() as usize)
583		}
584
585		/// Ensures that the given data size is valid for storage.
586		fn ensure_data_size_ok(size: usize) -> Result<(), Error<T>> {
587			ensure!(Self::data_size_ok(size), Error::<T>::BadDataSize);
588			Ok(())
589		}
590
591		/// Returns the [`TransactionInfo`] for the specified store/renew transaction.
592		fn transaction_info(
593			block_number: BlockNumberFor<T>,
594			index: u32,
595		) -> Option<TransactionInfo> {
596			let transactions = Transactions::<T>::get(block_number)?;
597			transactions.into_iter().nth(index as usize)
598		}
599
600		/// Verifies that the provided proof corresponds to a randomly selected chunk from a list of
601		/// transactions.
602		pub(crate) fn verify_chunk_proof(
603			proof: TransactionStorageProof,
604			random_hash: &[u8],
605			infos: Vec<TransactionInfo>,
606		) -> Result<(), Error<T>> {
607			// Get the random chunk index - from all transactions in the block = [0..total_chunks).
608			let total_chunks: ChunkIndex = TransactionInfo::total_chunks(&infos);
609			ensure!(total_chunks != 0, Error::<T>::UnexpectedProof);
610			let selected_block_chunk_index = random_chunk(random_hash, total_chunks);
611
612			// Let's find the corresponding transaction and its "local" chunk index for "global"
613			// `selected_block_chunk_index`.
614			let (tx_info, tx_chunk_index) = {
615				// Binary search for the transaction that owns this `selected_block_chunk_index`
616				// chunk.
617				let tx_index = infos
618					.binary_search_by_key(&selected_block_chunk_index, |info| {
619						// Each `info.block_chunks` is cumulative count,
620						// so last chunk index = count - 1.
621						info.block_chunks.saturating_sub(1)
622					})
623					.unwrap_or_else(|tx_index| tx_index);
624
625				// Get the transaction and its local chunk index.
626				let tx_info = infos.get(tx_index).ok_or(Error::<T>::MissingStateData)?;
627				// We shouldn't reach this point; we rely on the fact that `fn store` does not allow
628				// empty transactions. Without this check, it would fail anyway below with
629				// `InvalidProof`.
630				ensure!(!tx_info.block_chunks.is_zero(), Error::<T>::BadDataSize);
631
632				// Convert a global chunk index into a transaction-local one.
633				let tx_chunks = num_chunks(tx_info.size);
634				let prev_chunks = tx_info.block_chunks - tx_chunks;
635				let tx_chunk_index = selected_block_chunk_index - prev_chunks;
636
637				(tx_info, tx_chunk_index)
638			};
639
640			// Verify the tx chunk proof.
641			ensure!(
642				sp_io::trie::blake2_256_verify_proof(
643					tx_info.chunk_root,
644					&proof.proof,
645					&encode_index(tx_chunk_index),
646					&proof.chunk,
647					sp_runtime::StateVersion::V1,
648				),
649				Error::<T>::InvalidProof
650			);
651
652			Ok(())
653		}
654	}
655}
pallet_transaction_storage/lib.rs

pallet_transaction_storage/
lib.rs
