Proof for non-existence values (0x0)

[simon-jentzsch]

Currently when I get the merkle-proof from parity for a storage-value with 0x0 it will return me a array of nodes which are only branches because there is no leaf-node for the 0x0-value.
When I use the verifyProof it will return with a Error 'Unexpected end of proof', which is actually correct, but it raises the question, how are we able to prove non-existend or 0x0-values?

For now I rewrote the verifyProof-Function with a additional Argument (expectedValue) in our repo.
This checks in case of a branch before throwing this error:

  // if we expected this to be null and there is no further node since wantedHash is empty, than it is ok not to find leafs, because it proofs, that this value does not exist
  if (expectedValue === null && wantHash.length === 0)
    return null

  // we reached the end of the proof, but not of the path
  throw new Error('Unexpected end of proof')

In the case the last node is a leaf pointing to a different node, which can happen, I accept this as a proof that this node does not exist:

        // if the relativeKey in the leaf does not match our rest key, we throw!
        if (matchingNibbleLength(node.key, key) !== node.key.length) {
          // so we have a wrong leaf here, if we actually expected this node to not exist,
          // the last node in this path may be a different leaf or a branch with a empty hash
          if (key.length === node.key.length && i === proof.length - 1 && expectedValue === null)
            return val

          throw new Error(errorPrefix + 'Key does not match with the proof one (extention|leaf)')
        }

[holgerd77]

I still am no merkle tree-super expert and have problems to judge this issue, any further comments on this are appreciated.

[simon-jentzsch]

Yes MerkleProof for non-existent values are tricky, but possible. In the end it comes down to following the path of the nibbles and we can be sure the value does not exist, if:

1. if we find a branch and the slot for the next nibble is empty
2. if we have a extension or leaf and the path does not match the target

Here is an example where I implemented this:

https://github.com/slockit/in3-trie/blob/master/src/proof.ts

[holgerd77]

A bit the same question as on the block library, are you open to do a PR here? Does this conform with the license requirements of slockit code base?

[holgerd77]

Closed by #82