IT虾米网

区块链的java实现详解

lxf 2018年09月16日 编程语言 189 0

概述
MerkleTree被广泛的应用在比特币技术中,本文旨在通过代码实现一个简单的MerkleTree,并计算出Merkle tree的 TreeRoot。
Merkle Tree 是一种数据结构,用于验证在计算机之间和之间存储,处理和传输的任何类型的数据。
目前,Merkle树的主要用途是确保从对等网络中接收的数据块未受损和未改变,和检查其他对等网络没有撒谎发送假数据块。
这里写图片描述
Merkle Tree应用举例

    比特币
    Git
    Amazon’s Dynamo
    Gassandra

比特币中的应用
比特币中每个块中都包含了所有交易的集合签名,这个签名就是用Merkle tree实现的,Merkle树用于比特币以汇总块中的所有事务,产生整个事务集合的整体数字指纹,提供非常有效的过程来验证事务是否包括在块中。
这里写图片描述
Merkle树一个很重要的用处是检查块中是否包含指定的交易,Merkle树是通过递归哈希节点对来构造的,直到只有一个哈希。
这里写图片描述
Merkle tree 代码实现
哈希树的跟节点称为Merkle根,Merkle树可以仅用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; 
      } 
 
    }

数据准备
我们将交易的数据,放入到List中:

List<String> tempTxList = new ArrayList<String>(); 
tempTxList.add("a"); 
tempTxList.add("b"); 
tempTxList.add("c"); 
tempTxList.add("d"); 
tempTxList.add("e");

实现过程
    准备交易数据
    计算出每个数据的hash值,从左到右逐步组成树的左右节点
    执行循环知道最后只剩下一个数据

 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++; 
  }

测试

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()); 
      } 
    }

本文从简单二叉树的形式实现了简单的MerkleTree,计算出TreeRoot,但是实际上的的MerkleTree不拘谨与二叉树还可能是多叉树。

发布评论

分享到:

IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

只用120行Java代码写一个自己的区块链详解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。