trie_db/proof/
mod.rs

1// Copyright 2019, 2020 Parity Technologies
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Generation and verification of compact proofs for Merkle-Patricia tries.
16//!
17//! Using this module, it is possible to generate a logarithmic-space proof of inclusion or
18//! non-inclusion of certain key-value pairs in a trie with a known root. The proof contains
19//! information so that the verifier can reconstruct the subset of nodes in the trie required to
20//! lookup the keys. The trie nodes are not included in their entirety as data which the verifier
21//! can compute for themself is omitted. In particular, the values of included keys and and hashes
22//! of other trie nodes in the proof are omitted.
23//!
24//! The proof is a sequence of the subset of nodes in the trie traversed while performing lookups
25//! on all keys. The trie nodes are listed in pre-order traversal order with some values and
26//! internal hashes omitted. In particular, values on leaf nodes, child references on extension
27//! nodes, values on branch nodes corresponding to a key in the statement, and child references on
28//! branch nodes corresponding to another node in the proof are all omitted. The proof is verified
29//! by iteratively reconstructing the trie nodes using the values proving as part of the statement
30//! and the hashes of other reconstructed nodes. Since the nodes in the proof are arranged in
31//! pre-order traversal order, the construction can be done efficiently using a stack.
32
33pub use self::{
34	generate::generate_proof,
35	verify::{verify_proof, Error as VerifyError},
36};
37
38mod generate;
39mod verify;
trie_db/proof/mod.rs

trie_db/proof/
mod.rs
