Proof of non membership in a Verkle Tree?

Question

According to the author of the original paper[1],

Verkle Trees basically let you save space (typically bandwidth, which can be expensive) by replacing a secure hash with a vector commitment scheme, making the tree shorter and fatter with some branching factor $k > 2$. This saved bandwidth comes at the cost of some extra computation required to generate the Verkle tree and verify proofs of leaf nodes. [2]

So, if in Verkle Trees we can prove that a child node is at a given position of its parent node, then does it mean we can easily have a proof of non membership for an element?

Answer 1

Quoting a recent research article

Non-membership proofs are constructed in the exact same way as membership proofs. The only difference is that, at the point where the path to a key terminates, the prover must prove the presence of a null hash. This is possible because, when interpolating the polynomial to calculate the commitment to a node as discussed above, the prover uses the null hash to represent empty indices. Therefore, when proving non-membership for multiple keys, the prover provides a KZG proof that convinces the verifier that the values of the keys in question inside the tree are equal to the null hash.

The above is not too difficult to do IF "at the point where the path to a key terminates" there is an inner node - i.e. you can simply prove that the next sub-index has a hash that computes to the field scalar zero. It's like pretending there's a leaf in the tree with the key you are looking for, with a zero hash.

However, it is different (and I haven't found a really satisfying solution for that yet) if it happens that the last node in the tree along the path is actually a leaf node. In that case you can only prove that at a certain prefix of a missing key there's actually a terminal node (i.e. a leaf) - and you'll have to reveal data that you are probably not supposed to (that might not be an issue in some cases, though). In principle that could be enough to convince a verifier because the proof contains the depth of the node - so they can extrapolate at which prefix the leaf node was encountered, and infer that no other leaves can exist below it. The implementation needs however to be careful to not allow a cheating prover to prove inner nodes - only key-values in leaves - otherwise a malicious prover could build non-membership proofs for just about any entry in the tree.