Proof Of Membership

Another nice feature of Merkle trees is that, unlike the block chain that we built before, they allow a concise proof of membership. To prove that a data block is included in the tree only requires showing the blocks in the path from that data block to the root.

Suppose that someone wants to prove that a certain data block is a member of the merkle tree. As usual we remember just he root. Then they need to show us this data block, and the blocks on the path from the data block to the root. We can ignore the rest of the tree, as the blocks on the path are enough to allow us to verify the hashes all the way up to the root of the tree.

If there are n nodes in the tree, only about log(n) items need to be shown. And since each step just requires computing the hash of the child block, it takes log(n) time for us to verify it. And so if the Merkle tree contains a large number of blocks, we can still prove membership in a relatively short time. Verification thus runs in time and space that's logarithmic in the number of nodes in the tree.

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 *