What is a Merkle Tree?
A Merkle Tree, also known as a Hash Tree, is a binary tree structure typical in cryptography and computer science. A Merkle tree consists of a root node, a set of intermediate nodes, and a set of child nodes. A Merkle tree allows any node to verify that all data in a database is correct by means of zero-knowledge proofs, while at the same time safeguarding the privacy of the data to a certain extent.
The concept of Merkle tree was first proposed by Merkle Ralf in 1979, and has been used in distributed file systems and P2P systems to verify the integrity and correctness of data.
Principle of Merkle Tree
1. Hash Algorithm
Hash algorithm is an algorithm that allows data of arbitrary length to be output as a fixed length. Its advantage is one-way encryption, i.e. there is no way to reverse the calculated value to the original data. For example, through the hash algorithm for data A encrypted output as B, can not be reversed from B out of the value of data A, played a protective role. A classic application of the hash algorithm is in the Bitcoin, through the private key can generate the address of the Bitcoin, but can not be reversed from the address of the Bitcoin out of the private key. When the data to be encrypted changes, the data generated by the encrypted output will also change naturally.
2. Constructing a Merkle Tree
The construction of a Merkle tree starts from the bottom.
First of all, the unique ID and asset data of a user at a certain point in time to create a “leaf”, and then the data in this leaf, through the hash algorithm to calculate a hash value, and so on... Each user has a unique hash value (such as Hash1, Hash2, Hash3...), and there is the first layer of the tree branches.
Combine the branches of the first level, the hash value of user 1 and user 2 is calculated as a new hash value Hash12, the hash value of user 3 and user 4 is calculated as a new hash value Hash34, and so on. This generates the second level of branches.
This process is repeated until all the hashes are combined into a single top-level hash, the root hash, at which point a complete Merkle tree from leaf to root has been constructed. In the tree data structure of root nodes and sub-nodes, all data processing processes are hierarchical and all nodes are divided into levels. In the process of bottom-up transmission of data results, the need for continuous verification of the front and back nodes, verification failure can not continue the next step, to ensure that the data calculation process will not occur in the error or error.
Merkle Tree in Proof of Reserves
Merkle trees are beginning to be used in proof of reserves in cryptocurrency exchanges due to their properties such as integrity and uniformity of data. The user generates a hash value for the moment by using his UID and balance information, and the system matches whether there is consistent data in the Merkle Tree, and if so, it proves that the accounts of the current platform are accurate and reliable.