Proof of Nonmembership

Using a sorted Merkle tree, it becomes possible to verify non-membership in logarithmic time and space. This is, we can prove that a particular block is not in the Merkle tree. And the way we do that is simply by showing the path to the item just before where the item in question would be and showing the path to the item just after where it would be. If these two items are consecutive in the tree, then this serves as proof that the item in question is not included - because if it were included, it would need to be between the two items shown, but there is no space between them, as they are consecutive.

Reference:

Narayanan, Arvind, et al. (2017). Bitcoin and Cryptocurrency Technologies. United States: Princeton Press

Leave a Reply

Your email address will not be published. Required fields are marked *