sp_domains/
proof_provider_and_verifier.rs

1#[cfg(not(feature = "std"))]
2extern crate alloc;
3
4#[cfg(not(feature = "std"))]
5use alloc::collections::BTreeSet;
6#[cfg(not(feature = "std"))]
7use alloc::vec::Vec;
8use core::fmt;
9use frame_support::PalletError;
10use hash_db::Hasher;
11#[cfg(feature = "std")]
12use parity_scale_codec::Codec;
13use parity_scale_codec::{Compact, Decode, Encode};
14use scale_info::TypeInfo;
15use sp_core::storage::StorageKey;
16#[cfg(feature = "std")]
17use sp_state_machine::prove_read;
18#[cfg(feature = "std")]
19use sp_state_machine::TrieBackendBuilder;
20use sp_std::fmt::Debug;
21use sp_std::marker::PhantomData;
22use sp_trie::{read_trie_value, LayoutV1, StorageProof};
23#[cfg(feature = "std")]
24use std::collections::BTreeSet;
25#[cfg(feature = "std")]
26use trie_db::{DBValue, TrieDBMutBuilder, TrieLayout, TrieMut};
27
28/// Verification error.
29#[derive(Debug, PartialEq, Eq, Encode, Decode, PalletError, TypeInfo)]
30pub enum VerificationError {
31    /// Emits when the given storage proof is invalid.
32    InvalidProof,
33    /// Value doesn't exist in the Db for the given key.
34    MissingValue,
35    /// Failed to decode value.
36    FailedToDecode,
37    /// Storage proof contains unused nodes after reading the necessary keys.
38    UnusedNodesInTheProof,
39}
40
41impl fmt::Display for VerificationError {
42    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
43        match *self {
44            VerificationError::InvalidProof => write!(f, "Given storage proof is invalid"),
45            VerificationError::MissingValue => {
46                write!(f, "Value doesn't exist in the Db for this key")
47            }
48            VerificationError::FailedToDecode => write!(f, "Failed to decode value"),
49            VerificationError::UnusedNodesInTheProof => write!(
50                f,
51                "Storage proof contains unused nodes after reading the necessary keys"
52            ),
53        }
54    }
55}
56
57/// Type that provides utilities to verify the storage proof.
58pub struct StorageProofVerifier<H: Hasher>(PhantomData<H>);
59
60impl<H: Hasher> StorageProofVerifier<H> {
61    /// Extracts the value against a given key and returns a decoded value.
62    pub fn get_decoded_value<V: Decode>(
63        state_root: &H::Out,
64        proof: StorageProof,
65        key: StorageKey,
66    ) -> Result<V, VerificationError> {
67        let val = Self::get_bare_value(state_root, proof, key)?;
68        let decoded = V::decode(&mut &val[..]).map_err(|_| VerificationError::FailedToDecode)?;
69
70        Ok(decoded)
71    }
72
73    /// Returns the value against a given key.
74    /// Note: Storage proof should contain nodes that are expected else this function errors out.
75    pub fn get_bare_value(
76        state_root: &H::Out,
77        proof: StorageProof,
78        key: StorageKey,
79    ) -> Result<Vec<u8>, VerificationError> {
80        let expected_nodes_to_be_read = proof.iter_nodes().count();
81        let mut recorder = sp_trie::Recorder::<LayoutV1<H>>::new();
82        let db = proof.into_memory_db::<H>();
83        let val = read_trie_value::<LayoutV1<H>, _>(
84            &db,
85            state_root,
86            key.as_ref(),
87            Some(&mut recorder),
88            None,
89        )
90        .map_err(|_| VerificationError::InvalidProof)?
91        .ok_or(VerificationError::MissingValue)?;
92
93        // check if the storage proof has any extra nodes that are not read.
94        let visited_nodes = recorder
95            .drain()
96            .into_iter()
97            .map(|record| record.data)
98            .collect::<BTreeSet<_>>();
99
100        if expected_nodes_to_be_read != visited_nodes.len() {
101            return Err(VerificationError::UnusedNodesInTheProof);
102        }
103
104        Ok(val)
105    }
106
107    /// Constructs the storage key from a given enumerated index.
108    pub fn enumerated_storage_key(index: u32) -> StorageKey {
109        StorageKey(Compact(index).encode())
110    }
111}
112
113#[cfg(feature = "std")]
114type MemoryDB<T> = memory_db::MemoryDB<
115    <T as TrieLayout>::Hash,
116    memory_db::HashKey<<T as TrieLayout>::Hash>,
117    DBValue,
118>;
119
120/// Type that provides utilities to generate the storage proof.
121#[cfg(feature = "std")]
122pub struct StorageProofProvider<Layout>(PhantomData<Layout>);
123
124#[cfg(feature = "std")]
125impl<Layout> StorageProofProvider<Layout>
126where
127    Layout: TrieLayout,
128    <Layout::Hash as Hasher>::Out: Codec,
129{
130    /// Generate storage proof for given index from the trie constructed from `input`.
131    ///
132    /// Returns `None` if the given `index` out of range or fail to generate the proof.
133    pub fn generate_enumerated_proof_of_inclusion(
134        input: &[Vec<u8>],
135        index: u32,
136    ) -> Option<StorageProof> {
137        if input.len() <= index as usize {
138            return None;
139        }
140
141        let input: Vec<_> = input
142            .iter()
143            .enumerate()
144            .map(|(i, v)| (Compact(i as u32).encode(), v))
145            .collect();
146
147        let (db, root) = {
148            let mut db = <MemoryDB<Layout>>::default();
149            let mut root = Default::default();
150            {
151                let mut trie = <TrieDBMutBuilder<Layout>>::new(&mut db, &mut root).build();
152                for (key, value) in input {
153                    trie.insert(&key, value).ok()?;
154                }
155            }
156            (db, root)
157        };
158
159        let backend = TrieBackendBuilder::new(db, root).build();
160        let key = Compact(index).encode();
161        prove_read(backend, &[key]).ok()
162    }
163}