Hash Pointers and Data Structures

hash pointer

A hash pointer consists of two essential components:

1. Pointer to the location where the information is stored
2. Cryptographic hash of the information

The pointer facilitates access to the information, while the hash enables verification of the information's integrity.

Data Structures Utilizing hash pointers

Blockchain

Hash pointers can be employed to construct a linked list, commonly known as a blockchain.

It's important to note that the hash contained in the hash pointer encompasses the entire data of the previous block, including the hash pointer to the preceding block. This feature renders it impossible to alter a block within the blockchain without detection.

Tamper Evident Nature of Blockchain

We only need to retain the hash pointer to the final block of the blockchain. When someone presents the entire blockchain and asserts that the data remains unmodified, we can verify this by traversing the blocks in reverse and checking the hashes sequentially.

Insou AI

Insou AI 是一款强大的人工智能助手，旨在帮助你轻松创建引人入胜的内容和令人印象深刻的演示。

下载

Explanation

If an attacker wishes to tamper with a block, say block 1:

• The attacker modifies the content of block 1. Due to the "collision-free" nature of the hash function, finding another piece of data with the same hash as the original is infeasible. Consequently, the hash of the altered block changes.
• To maintain consistency and avoid detection, the attacker must also update the hash pointer in the subsequent block, block 2.
• With block 2's content modified, the hash pointer in block 3 must also be altered to maintain the chain's integrity.
• The attacker faces a significant challenge at the hash pointer to the last block of the blockchain, as we retain and remember this hash pointer.

Merkle Tree

A Merkle tree is a binary tree constructed using hash pointers. The leaves represent data blocks, while higher-level nodes contain hashes of their child nodes.

Features

• Tamper Evident: Similar to a blockchain, only the hash pointer at the root (top-level node) needs to be remembered. From there, we can traverse down to any leaf data block to verify if a node is part of the tree or has been tampered with.
• Traversal Efficiency: To verify a data block, we only need to traverse the path from the root to the leaf containing the data. This results in a complexity of O(log n), which is significantly more efficient than the O(n) complexity of a linked list blockchain.
• Non-membership Proof: If the Merkle tree is sorted, we can prove that a given data item is not in the tree. If the data items before and after the given data are both in the tree and consecutive, leaving no space between them, it proves that the given data is not present in the tree.

Example Codes on GitHub

• Blockchain Implementation in Java
• Merkle Tree Implementation in Java