hash pointer
A Hash Pointer consists of two essential components:
- Pointer to the location where the information is stored
- 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
Python Tutorial ——Python新手入门指南 PDF版，内容包括： Whetting Your Appetite 开胃菜 Using the Python Interpreter使用Python解释器 More Control Flow Tools 流程控制 Data Structures数据结构 Errors and Exceptions错误和异常 标准库概览……&hell
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.
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
