A hash tree (Merkle tree) is a complete binary tree, the leaf vertices of which contain hashes from data blocks, and the internal vertices contain hashes from the addition of values in child vertices. The root node of the tree contains a hash of the entire data set, that is, a hash tree is a one-way hash function. Merkle trees transform data into a hash, so they only work in one direction: It is easy to construct a tree from raw data, but it is impossible to reconstruct data from it. The merkle root can be published publicly without fear of data disclosure - it is a hash of all transaction hashes in the merkle tree. When transactions are successfully paired and hashed, the result is a Merkle root. A change in any data will change the Merkle root. This way, merkle root ensures that no data on the network is changed.
Used for efficient storage of transactions in the cryptocurrency blockchain (for example, Bitcoin, Ethereum). It allows you to obtain a “fingerprint” of all transactions in a block, as well as effectively verify transactions. Named after Ralph Merkle, who proposed the corresponding hashing technique for cryptographic functions in 1979, Merkle called his idea “Tree Signatures” or “Tree Authentication.” Today this idea is better known as a Merkle Tree, named after the inventor. Given a Merkle root, as well as a few other pieces of data, any computer can efficiently check all the other entries in the Merkle tree. In blockchain technology, these records represent transaction identification numbers. The “leaves” on the Merkle Tree are hashes of transactions, followed by internal vertices - hashes that include the results of adding the “leaves”. And so on to the very root, that is, a hash that includes information from the entire tree. The essence of the Merkle Tree check is to “audit” the state of the blockchain without the need to download it completely, since the algorithm allows you to obtain one hash for many blocks of the blockchain.
All transactions in a Bitcoin block are strings in hexadecimal format, they are hashed and represented as transaction identifiers (txid). All txids in a block are hashed until a single hash value for the block is obtained. In the process, a Merkle tree is built: first, the txid (Transaction ID) itself is calculated, that is, transaction hashes;
then hashes are calculated from the sum of transaction hashes. The Merkle tree is binary, that is, at each new hashing stage, the number of tree elements must be even. If there is an odd number of transactions in a block, the hash of the last one is duplicated and added to itself; new hashes are calculated from the hashes of the sum of transaction hashes. And so on until a single hash (merkle root) is obtained. It is indicated in the block header.
The process of constructing a Merkle tree is similar to data folding. Thanks to it, a huge list of transactions or any other array of information can be represented in just one line. The beauty is that if somewhere in the list of these same transactions we change just one symbol, the next “level” of the tree will be completely different and the final hash - that is, the “top” of the tree - will also change.
In other words, you cannot insert another transaction into the block or change the data of existing ones. This is why a Merkle tree is considered an efficient way to record transactions on a blockchain.
