15
$\begingroup$

Assume a user $U$ and a server $S$. $U$ uploads its data and wants later to perform an authenticity check. It also sends a Merkle tree to the server. Let’s say we would like $U$ to ask for a specific element in the tree. $S$ then returns the leaf node and the path to the root that would allow $U$ to verify. This acts as a proof of completeness.

In the case an element is not part of the Merkle tree, how the server can prove the non-membership proof?

Improve this question
$\endgroup$
1
  • $\begingroup$ Naive question: If it is not included in the tree doesn't it automatically prove it doesn't exist. I know I am missing something but I wonder what is it? $\endgroup$
    – user1870400
    Jun 18, 2018 at 11:47

4 Answers 4

Reset to default
9
$\begingroup$

If you are not worried about revealing information, then you can commit to the set of data items in one Merkle tree, and to the frontier of that set in another Merkle tree. A frontier is the set of ancestors to all values that are not in the tree (note that this is about the same size as the size of the set itself). Then, in order to prove that a value is inside the set you work with the first tree, and in order to prove that it is not you work with the second tree.

However, I strongly recommend that you read this paper on Zero-Knowledge Sets by Micali, Rabin and Kilian. First, the notion of a frontier mentioned above is defined. Second, they provide a formal definition and analysis. Third, they achieve something much stronger which is that nothing but the fact that the element is in or is not in the set is revealed (not even the size of the set). There was some follow up work on zero-knowledge sets as well, but you can find them easily by Googling.

Improve this answer
$\endgroup$
5
  • $\begingroup$ It seems a bit not efficient if i have to construct a tree with data not in the first tree. It seems like i have to construct a huge tree for the uninerse-my data $\endgroup$
    – curious
    Jan 14, 2016 at 6:02
  • 1
    $\begingroup$ No, that's not true. Read the paper properly and you'll see. The trees are the size of the data set only. $\endgroup$
    – Yehuda Lindell
    Jan 16, 2016 at 19:19
  • $\begingroup$ How the trees are on the size of the data set? Let's say the universe has size |n| and my dataset is of size |d|. Then the membership tree has 2^|n| leaves. And includes the membership tree and the non-mebership one. This the way it is described i think in the paper with the frontier one. They first construct a complete tree of k levels, where k is the size of the hash digest $\endgroup$
    – curious
    Jan 17, 2016 at 6:26
  • $\begingroup$ You didn't read carefully. They do not construct a complete tree; this would not be efficient. $\endgroup$
    – Yehuda Lindell
    Jan 17, 2016 at 9:45
  • $\begingroup$ Lets take the example in Fig 1. The set comprises of 3 elements. How you prove that 1111 is not there?I do not think that it is supported. So there is a restriction on the type of non-membership queries $\endgroup$
    – curious
    Jan 17, 2016 at 16:36
6
$\begingroup$

If your data is a set $S$ of key-value pairs, such that $S = \{(k,v) \mathrel\vert k \in K, v \in V\}$, you can have non-membership proofs for your data by using a sorted Merkle tree (sorted by the keys in $K$).

This tree can be a binary-search tree, a trie, a sparse Merkle Tree (similar to the one in Micali's Zero Knowledge sets paper, and also reintroduced by Google).

You can learn more about this by reading some of the research literature on authenticated dictionaries. This paper by Scott Crosby could be a good starting point.

Later edit: If you have unkeyed data, you might be able to key it by computing $k = \mathsf{SHA256}(v), \forall v$. Depending on your use case, this could or could not be viable.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Still that assumes you are making a Merkle tree with all the universe in it. All possible ranges. $\endgroup$
    – curious
    Jan 15, 2016 at 20:40
  • 1
    $\begingroup$ I'm not sure I understood, but if your set size is $|S| = n$ then your sorted Merkle tree can have exactly $n$ nodes in it and provide you with (non)membership proofs. $\endgroup$
    – Alin Tomescu
    Jan 16, 2016 at 17:18
  • $\begingroup$ Ok, but i still can't see according to the document how you can prevent an attacker of proving a non-membership for an item that actually exists in the merkle tree. Instead of returning the asking H(x) and the path, it returns H(x') and H(x'') which are the before and after nodes $\endgroup$
    – curious
    Jan 17, 2016 at 5:32
  • $\begingroup$ Looks like I never answered this. I apologize. Let's look at a very simple example. I claim that sparse Merkle trees offer secure non-membership proofs. Note that in a sparse Merkle tree over $n$ key-value pairs you only need $n$ leafs (overall the number of nodes is O(n) with a constant < 256). To prove membership of a key $k$, you show its unique 256-node path in the tree leading to a leaf with $(k,v)$ in it. The path is determined by the binary expansion of $H(k)$. To show non-membership for a key $k'$, you show that its unique path does not lead to any leaf! (i.e., ends abruptly) $\endgroup$
    – Alin Tomescu
    Nov 18, 2017 at 17:34
  • 1
    $\begingroup$ Worth noting that the author of this answer has since written a fantastic blog post on why one should not sort their Merkle Tree leaves: alinush.github.io/2023/02/05/… $\endgroup$
    – Olshansky
    May 9 at 21:46
4
$\begingroup$

This is a less formal answer, but describes the same thing as Alin's answer above.

Standard binary merkle tree:

R / \ N N / \ / \ N N N N / \ / \ / \ / \ 6 3 9 0 8 4 7 2

Verifier knows only R, and for prover to prove membership they have to supply leaves along the path from given member towards R. So far so good.

To prove non-membership, what you can do is to have a sorted merkle tree:

R / \ N N / \ / \ N N N N / \ / \ / \ / \ 0 2 3 4 6 7 8 9 <-- values 0 1 2 3 4 5 6 7 <-- binary index

To prove that 5 is not in the set, you supply proof of membership for 4 and 6, which are in successive binary order (3 and 4 in this case), and the hashed values cover a range the query value falls into. And since we have the assumption of order, 5 can't appear anywhere else.

To be specific, the properties are:

  1. The verifier has to trust R to be result of honestly ordered tree. This can be verified probabilistically (including Fiat-Shamir) by samping with few queries and observing the order is always maintained. This may become quite heavy depending on the nature of data (if keys allow for large gaps or not). Better is to simply assume the R we know is honest.

  2. The worst-case proof size, with completely distinct branches is only 2log2(n) of the set.

  3. Worst of all, you cannot easily update the tree without rebuilding it. To make an update you need to know the whole universe, not just the tip R as is the case for membership. Thus the construct is suitable for static dictionaries which are seldom updated, as well as short round membership protocols like joinmarket below.

  4. The tree must be binary and of known size, if it is truncated (some part of the DAG terminate earlier), use some graph rule, like that truncation may occur along the rightmost branches.

R / \ N N / \ / \ N N N 7 / \ / \ / 0 2 3 4 6

For more long-winded description, see https://gist.github.com/chris-belcher/eb9abe417d74a7b5f20aabe6bff10de0

Improve this answer
$\endgroup$
0
$\begingroup$

Merkle trees do not provide the option for a "non-membership-proof". However, as the user knows the whole tree in your case, the server can just send the hash of the element (or the element itself, depending on how you construct the leafs). The user can verify that the hash is unequal to every leaf of the tree. While this is still not very efficient (linear time in the number of elements), it will be more efficient than building an authentication structure for the inverse of your data set as long as your data set is small compared to the (data-)universe.

Improve this answer
$\endgroup$
4
  • $\begingroup$ That seems to kill the nice property of efficient verification of the dataset, since the user has to keep track of all the leaves $\endgroup$
    – curious
    Jan 14, 2016 at 21:36
  • $\begingroup$ Indeed... The problem is that Merkle tree's are only designed for proofs of membership, not for proofs of non-membership. Perhaps you choose the wrong tool? You might want to have a look at cryptographic accumulators (e.g. eprint.iacr.org/2008/538.pdf). $\endgroup$
    – mephisto
    Jan 15, 2016 at 10:00
  • $\begingroup$ I know about accumulators. My problem is their non-standard q-ary assumptions they are based on. $\endgroup$
    – curious
    Jan 15, 2016 at 15:23
  • $\begingroup$ Agreed, that's not nice. However, I guess you do not get more efficient than the two proposed solutions sticking with Merkle trees. Simply because the trees themselves are not aware of the universe the data set lives in. $\endgroup$
    – mephisto
    Jan 15, 2016 at 15:30

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.