merkle-proof

Verification of compact and non-compact proofs for Modified Merkle-Patricia tries(Substrate).

Solidity version of compact verification is translated by the Rust Version.
Solidity version of non-compact verification is translated by the Rust Version.

Brief

The compact 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.

The non-compact proof is a set of nodes which is put in a hashmap with key being the encoded node hash.Then to verify the proof we just run the process (can be any runtime call or key value access) to check over a trie that use this hash map as a encoded node backend.

Difference

At trie node level it is the same (compact uses 'empty inline node' which is impossible as a way to add information without changing the encoding).

Then at proof level:
Non compact is a set of nodes.
Compact is an ordered set of nodes.
But in the end they both are represented as a list of encoded nodes (Vec).
Just in the compact case the order of the nodes defines the structure of the trie and 'empty inline node' indicate the child is in the proof and the hash should be calculated from it.

One other tiny difference is that for compact proof you cannot have a single proof with nodes from different tries, so in case of child trie used by the proof, compact will need a different encoded where the proof is split by trie (this was named Full when Flat was a single trie proof).

Trie node encoding specification

Note that for the following definitions, | denotes concatenation.

Branch encoding: NodeHeader | Extra partial key length | Partial Key | Value.
NodeHeader is a byte such that:
most significant two bits of NodeHeader: 10 if branch w/o value, 11 if branch w/ value.
least significant six bits of NodeHeader: if len(key) > 62, 0x3f, otherwise len(key).
Extra partial key length is included if len(key) > 63 and consists of the remaining key length.
Partial Key is the branch's key.
Value is: Children Bitmap | SCALE Branch node Value | Hash(Enc(Child[i_1])) | Hash(Enc(Child[i_2])) | ... | Hash(Enc(Child[i_n])).

Leaf encoding: NodeHeader | Extra partial key length | Partial Key | Value.
NodeHeader is a byte such that:
most significant two bits of NodeHeader: 01.
least significant six bits of NodeHeader: if len(key) > 62, 0x3f, otherwise len(key).
Extra partial key length is included if len(key) > 63 and consists of the remaining key length.
Partial Key is the leaf's key.
Value is the leaf's SCALE encoded value.

Features

1. *MerkleProof.sol: Verication for MMPT(16-radix) generated by Substrate trie lib.
2. Node.sol: Encoding and decoding for trie node.
3. Scale.sol: SCALE codec support, bytes and uint32.
4. Hash.sol: Hash algorithm support, keccake256 and blake2b.