We have come to a discussion of the hash pointer and the application used. The hash pointer is a useful data structure in many systems. A hash pointer works like a pointer in general, indicating where the information is stored, along with its hash information. The hash pointer also shows you how to retrieve that information, and also how to verify that information so that it does not change.
A hash pointer is a pointer that shows where the data is stored together with the hash of the data value at a given time.
We can use hash pointers to build all types of data structures. We can also retrieve data structures that use pointers like list links or binary search trees and then apply them with a hash pointer, unlike commonly used pointers.
The image is a linked list using a hash pointer. Furthermore, this data structure is called Block chain. In general, this link list has a series of blocks. Each block has data and pointers leading to the previous block in the list. In the block chain, the previous block will be replaced with a hash pointer. So on every block, it not only gives us where the previous block value is, but also has a value that allows us to verify that value so it can not change, once it is verified.
The block chain will serve as a tamper-evident log . So that data structure saves so much data. And it is possible to add data at the end of the log. If then there is someone who changed the previous data, it will be detected.
To find out why a block chain can be a tamper-evident log, for example there is a bully who wants to change the data in the middle of the block chain. In particular of course the person already knows that the hash pointer on the head only can not detect the interference. Then the person changes some data in block k . Since the data has changed, the hash in the block becomes k + 1 . While the hash is a hash of the entire block k , so it becomes unsuitable.
Keep in mind is, that the new hash will not match the content that has just been changed since the hash function becomes collision-resistant. The change will be detected between the new data in block k and the hash pointer that is in block k + 1 . To cover this, the rioters must change the next hash of blocks as well, and will continue to do this. The person’s strategy will fail when it reaches the top of the list. Specifically, as long as we store the hash pointer in the list head list, and the person can not change it undetected.
So if someone wants to tamper with data anywhere in the entire data chain, in order for the data to be changed to be consistent, then he should change all the hashes from scratch. In the end, the person will experience many obstacles, because it will not be able to fiddle with the parent list. That is why just by putting this single hash pointer, it will be a completely tamper-evident log . So we can create a block chain that can consist of as many blocks as desired.
Next let’s look back at the beginning of the list of blocks known as the genesis block . We will remember that the construction of this block chain is similar to the previously described Merkle-Damgard construction . Both are quite similar, and have a security argument that applies also in both.
The image, if one changes the data in any block in the chain, will result in the hash pointer hash in the next block. If we keep the hash pointer in the list header, and then someone modifies all the pointers to be consistent with the changed data, then the pointer in the block head list will have an error. So that inconsistent data will be detected.
Another useful data structure that we can create using the hash pointer is the binary tree.The binary tree data structure that has a hash pointer, called the Merkle Tree , is found by Ralph Merkle . Suppose we have a number of blocks that have some data. Then, this block is compiled using merkle tree . Then classify the data blocks into two pairs. Each pair is made up of data structures with hash pointers, one on each block. This data structure creates the next level in the tree structure. Then on each pair, create a new data structure that has hash on each. This is done continuously until it reaches one block, which becomes root ( root ).
In the Merkle Tree, the data blocks are grouped in pairs, the hash of each block is stored on the parent node . Next, the parent nodes will be grouped again in pairs, and the hash will be stored again in the next level. This is done continuously until it reaches the root node.
Previously, we would still remember that only a hash pointer placed in a tree’s head can not be changed instead? So if there are any sections under the tree, it will cause the hash pointer at one point with another point above it to be unsuitable. If this change of data continues to be done, it will eventually reach the top of the tree, where the person will not be able to tamper with it, and will be detected just by tethering the hash pointer at the top.
Proof of Membership (proof of membership)
There is another feature in Merkle that is quite useful. But unlike the block chain we discussed earlier. With this feature it allows to create membership summary. So the data becomes shorter and not too long. For example, let’s say that someone wants to provide evidence that a particular block of data is part of the Merkle Tree. Next thing to remember is root only. Then the ornag is required to show the block data, and the data block will run in accordance with the sequence of data block to go to the root. We can ignore the remaining parts of the tree, because the tree path will allow in verifying the hash to reach the root of the tree.
In the drawing, to be able to prove that the block data belongs to a merkle member, then what is needed is to show only the block on a path that can reach to the root.
Sorted Merkle Tree
Sorted Merkle Tree is a Merkle tree where we take blocks at the bottom, then sort them with some functions. Can be alphabetical, lexicographic, numerical, or other sequences.
Proof of Non-Membership
Merkle Tree that has been sorted earlier, it is possible to perform non-membership verification. That is, it can be proven that there are certain blocks that are not part of the Merkle Tree. The trick, is to show the path on the item just before the item is questioned, and also show the path of the item immediately afterwards. If two items are in succession in the merkle, then they can be proof that the item is not part of the merkle. If both items are included in the merkle section, then the two items should be displayed as well, whereas there is no space as both exist in a row.