Module trie_db::proof

Generation and verification of compact proofs for Merkle-Patricia tries.

Using this module, it is possible to generate a logarithmic-space proof of inclusion or non-inclusion of certain key-value pairs in a trie with a known root. The proof contains information so that the verifier can reconstruct the subset of nodes in the trie required to lookup the keys. The trie nodes are not included in their entirety as data which the verifier can compute for themself is omitted. In particular, the values of included keys and and hashes of other trie nodes in the proof are omitted.

The proof is a sequence of the subset of nodes in the trie traversed while performing lookups on all keys. The trie nodes are listed in pre-order traversal order with some values and internal hashes omitted. In particular, values on leaf nodes, child references on extension nodes, values on branch nodes corresponding to a key in the statement, and child references on branch nodes corresponding to another node in the proof are all omitted. The proof is verified by iteratively reconstructing the trie nodes using the values proving as part of the statement and the hashes of other reconstructed nodes. Since the nodes in the proof are arranged in pre-order traversal order, the construction can be done efficiently using a stack.

Enums

• VerifyError
  Errors that may occur during proof verification. Most of the errors types simply indicate that the proof is invalid with respect to the statement being verified, and the exact error type can be used for debugging.

Functions

• generate_proof
  Generate a compact proof for key-value pairs in a trie given a set of keys.
• verify_proof
  Verify a compact proof for key-value pairs in a trie given a root hash.