Overview
MerkleTree is widely used in Bitcoin technology. This article aims to implement a simple MerkleTree through code and calculate the TreeRoot of Merkle tree.
Merkle Tree is a data structure that verifies any type of data stored, processed and transmitted between computers.
Currently, the main purpose of the Merkle tree is to ensure that the data blocks received from the peer network are not damaged and unchanged, and to check that other peer networks do not lie to send fake data blocks.
Merkle Tree Application Example
Bitcoin
GitA
mazon's Dynamo
Gassandra
Applications in Bitcoin
Each block in Bitcoin contains a collection signature of all transactions. This signature is implemented using Merkle tree. The Merkle tree is used for Bitcoin to summarize all transactions in the block, generate an overall digital fingerprint of the entire set of transactions, and provide a very effective process to verify whether the transaction is included in the block.
A very important use of Merkle trees is to check whether the block contains a specified transaction. Merkle trees are constructed by recursively hashing pairs of nodes until there is only one hash.
Merkle tree code implementation
The hash tree's node is called the Merkle root. The Merkle tree can check whether any data element is included in the tree using the time complexity of log2(N):
package test;import java.security.MessageDigest;import java.util.ArrayList;import java.util.List;public class MerkleTrees { // transaction List List<String> txList; // Merkle Root String root; /** * constructor * @param txList transaction List Transaction List */ public MerkleTrees(List<String> txList) { this.txList = txList; root = ""; } /** * execute merkle_tree and set root. */ public void merkle_tree() { List<String> tempTxList = new ArrayList<String>(); for (int i = 0; i < this.txList.size(); i++) { tempTxList.add(this.txList.get(i)); } List<String> newTxList = getNewTxList(tempTxList); while (newTxList.size() != 1) { newTxList = getNewTxList(newTxList); } this.root = newTxList.get(0); } /** * return Node Hash List. * @param tempTxList * @return */ private List<String> getNewTxList(List<String> tempTxList) { List<String> newTxList = new ArrayList<String>(); int index = 0; while (index < tempTxList.size()) { // left String left = tempTxList.get(index); index++; // right String right = ""; if (index != tempTxList.size()) { right = tempTxList.get(index); } // sha2 hex value String sha2HexValue = getSHA2HexValue(left + right); newTxList.add(sha2HexValue); index++; } return newTxList; } /** * Return hex string * @param str * @return */ public String getSHA2HexValue(String str) { byte[] cipher_byte; try{ MessageDigest md = MessageDigest.getInstance("SHA-256"); md.update(str.getBytes()); cipher_byte = md.digest(); StringBuilder sb = new StringBuilder(2 * cipher_byte.length); for(byte b: cipher_byte) { sb.append(String.format("%02x", b&0xff) ); } return sb.toString(); } catch (Exception e) { e.printStackTrace(); } return ""; } /** * Get Root * @return */ public String getRoot() { return this.root; } }Data preparation
We put the transaction data into the List:
List<String> tempTxList = new ArrayList<String>();tempTxList.add("a");tempTxList.add("b");tempTxList.add("c");tempTxList.add("d");tempTxList.add("e");Implementation process
Prepare transaction data to calculate the hash value of each data, and gradually form the left and right nodes of the tree to execute the loop to know that only one data is left in the end
private List<String> getNewTxList(List<String> tempTxList) { List<String> newTxList = new ArrayList<String>(); int index = 0; while (index < tempTxList.size()) { // left String left = tempTxList.get(index); index++; // right String right = ""; if (index != tempTxList.size()) { right = tempTxList.get(index); } // sha2 hex value String sha2HexValue = getSHA2HexValue(left + right); newTxList.add(sha2HexValue); index++; }test
package test;import java.util.ArrayList;import java.util.List;public class App { public static void main(String [] args) { List<String> tempTxList = new ArrayList<String>(); tempTxList.add("a"); tempTxList.add("b"); tempTxList.add("c"); tempTxList.add("d"); tempTxList.add("e"); MerkleTrees merkleTrees = new MerkleTrees(tempTxList); merkleTrees.merkle_tree(); System.out.println("root : " + merkleTrees.getRoot()); } }Execution results
This article implements a simple MerkleTree from the form of a simple binary tree and calculates TreeRoot, but in fact, MerkleTree is not conservative and binary tree may also be multi-fork trees.
90% of this article is based on translation, original address
The above is all the content of this article. I hope it will be helpful to everyone's learning and I hope everyone will support Wulin.com more.