Blockchain java code implementation

summary

Merkletree is widely used in bitcoin technology. This paper aims to implement a simple merkletree through code and calculate the treeroot of Merkle tree. Merkle tree is a data structure used to verify any type of data stored, processed and transmitted between computers and. At present, the main purpose of Merkle tree is to ensure that the data blocks received from peer-to-peer networks are not damaged and changed, and to check that other peer-to-peer networks do not send false data blocks.

Application example of Merkle tree

Bitcoin

GitA

mazon's Dynamo

Gassandra

Applications in bitcoin

Each block in bitcoin contains the set signature of all transactions. This signature is implemented by Merkle tree. Merkle tree is used in bitcoin to summarize all transactions in the block and generate the overall digital fingerprint of the whole transaction set. It provides a very effective process to verify whether events are included in the block.

An important use of Merkle tree is to check whether the block contains the specified transaction. Merkle tree is constructed by recursive hash node pairs until there is only one hash.

Merkle tree code implementation

The following node of the hash tree is called the Merkle root. The Merkle tree can check whether any data element is included in the tree only with 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 交易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;
  }

 }