1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ It is not easy, for the non-existent element $x$ (assuming that the elements are stored ordered), you may return the $inf(x)$ and $sup(x)$ and use the definition of Verkle Tree to see that there is no element between $inf(x)$ and $sup(x)$. You need special cases for the first and the last element. $\endgroup$
    – kelalaka
    Oct 30 at 20:37

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.