UDN-企业互联网技术人气社区

板块导航

浏览  : 2262
回复  : 0

[讨论交流] 区块链中的梅克尔树的Java实现。

[复制链接]
开花包的头像 楼主
发表于 2016-12-29 22:20:40 | 显示全部楼层 |阅读模式
  引言

  这篇文章介绍了MerkleTree,MerkleTree被广泛的应用在比特币技术中,本文旨在通过代码实现一个简单的MerkleTree,并计算出了Merkle树的TreeRoot

6.png


  梅克尔树简介

  梅克尔树是一种数据结构,用于验证在计算机之间和之间存储,处理和传输的任何类型的数据。

  目前,梅克尔树的主要用途是确保从对等网络中接收的数据块未受损和未改变,和检查其他对等网络没有撒谎发送假数据块。

  梅克尔树应用例子

  比特币

  混帐

  亚马逊的迪纳摩

  Gassandra

  环境

  Windows 7的

  甲骨文的JDK 1.8.2

  Eclipse的Java EE的IDE,用于Web开发。

  版本:Neon.1a版本(4.6.1)

  比特币中的应用

  比特币中每个块中都包含了所有交易的集合签名,这个签名就是用了Merkle树实现的

5.png


  梅克尔树用于比特币以汇总块中的所有事务,产生整个事务集合的整体数字指纹,提供非常有效的过程来验证事务是否包括在块中。

  梅克尔树一个很重要的用处是检查块中是否包含指定的交易,梅克尔树是通过递归哈希节点对来构造的,直到只有一个哈希

4.png


  梅克尔树算法和实现

  这个哈希树的跟节点称为梅克尔根,梅克尔树可以仅用LOG2(N)的时间复杂度检查任何一个数据元素是否包含在树中,

  1. 封装测试;
  2. 进口java.security.MessageDigest中;
  3. 进口的java.util.ArrayList;
  4. 进口的java.util.List;
  5. 公共类MerkleTrees {
  6.           //交易名单
  7.           名单<String>的txList;
  8.           //梅克尔根
  9.           串根;
  10.           
  11.           / **
  12.            *构造
  13.            * @参数txList交易列表交易列表
  14.            * /
  15.           公共MerkleTrees(名单<String>的txList){
  16.             this.txList = txList;
  17.             根=“”;
  18.           }
  19.           
  20.           / **
  21.            *执行merkle_tree并设置根。
  22.            * /
  23.           公共无效merkle_tree(){
  24.             
  25.             名单<String>的tempTxList =新的ArrayList <String>的();
  26.             
  27.             的for(int i = 0; I <this.txList.size();我++){
  28.               tempTxList.add(this.txList.get(I));
  29.             }
  30.           
  31.             名单<String>的newTxList = getNewTxList(tempTxList);
  32.           
  33.             而(newTxList.size()!= 1){
  34.               newTxList = getNewTxList(newTxList);
  35.             }
  36.             
  37.             this.root = newTxList.get(0);
  38.           }
  39.           
  40.           / **
  41.            *返回节点列表哈希。
  42.            * @参数tempTxList
  43.            * @返回
  44.            * /
  45.           私人名单<String>的getNewTxList(名单<String>的tempTxList){
  46.             
  47.             名单<String>的newTxList =新的ArrayList <String>的();
  48.             INT索引= 0;
  49.             而(指数<tempTxList.size()){
  50.               // 剩下
  51.               字符串左= tempTxList.get(指数);
  52.               指数++;
  53.               // 对
  54.               字符串右=“”;
  55.               如果(索引!= tempTxList.size()){
  56.                 右= tempTxList.get(指数);
  57.               }
  58.               // SHA2十六进制值
  59.               字符串sha2HexValue = getSHA2HexValue(左+右);
  60.               newTxList.add(sha2HexValue);
  61.               指数++;
  62.              
  63.             }
  64.             
  65.             返回newTxList;
  66.           }
  67.           
  68.           / **
  69.            *返回十六进制字符串
  70.            * @参数海峡
  71.            * @返回
  72.            * /
  73.           公共字符串getSHA2HexValue(字符串str){
  74.                 字节[] cipher_byte;
  75.                 尝试{
  76.                     消息摘要MD = MessageDigest.getInstance(“SHA-256”);
  77.                     md.update(str.getBytes());
  78.                     cipher_byte = md.digest();
  79.                     StringBuilder的SB =新的StringBuilder(2 * cipher_byte.length);
  80.                     对于(BYTE B:cipher_byte){
  81.                       sb.append(的String.format(“%02X”,B&0xFF的));
  82.                     }
  83.                     返回sb.toString();
  84.                 }赶上(例外五){
  85.                         e.printStackTrace();
  86.                 }
  87.                 
  88.                 返回“”;
  89.           }
  90.           
  91.           / **
  92.            *获得root
  93.            * @返回
  94.            * /
  95.           公共字符串getRoot(){
  96.             返回this.root;
  97.           }
  98.             
  99.         }
复制代码


  数据准备

  我们将交易的数据,放入到名单中

  1. 名单<String>的tempTxList =新的ArrayList <String>的();
  2. tempTxList.add(“一”);
  3. tempTxList.add(“B”);
  4. tempTxList.add(“C”);
  5. tempTxList.add(“D”);
  6. tempTxList.add(“E”);
复制代码


3.png


  实现过程

  准备交易数据

  计算出每个数据的哈希值,从左到右逐步组成树的左右节点

  执行循环知道最后只剩下一个数据

2.png


  核心代码

  1.  私人名单<String>的getNewTxList(名单<String>的tempTxList){
  2.   名单<String>的newTxList =新的ArrayList <String>的();
  3.   INT索引= 0;
  4.   而(指数<tempTxList.size()){
  5.     // 剩下
  6.     字符串左= tempTxList.get(指数);
  7.     指数++;
  8.     // 对
  9.     字符串右=“”;
  10.     如果(索引!= tempTxList.size()){
  11.       右= tempTxList.get(指数);
  12.     }
  13.     // SHA2十六进制值
  14.     字符串sha2HexValue = getSHA2HexValue(左+右);
  15.     newTxList.add(sha2HexValue);
  16.     指数++;
  17.   }
复制代码


  测试代码

  1. 封装测试;
  2. 进口的java.util.ArrayList;
  3. 进口的java.util.List;
  4. 公共类应用{
  5.           公共静态无效的主要(字串[] args){
  6.             名单<String>的tempTxList =新的ArrayList <String>的();
  7.             tempTxList.add(“一”);
  8.             tempTxList.add(“B”);
  9.             tempTxList.add(“C”);
  10.             tempTxList.add(“D”);
  11.             tempTxList.add(“E”);
  12.             
  13.             MerkleTrees merkleTrees =新MerkleTrees(tempTxList);
  14.             merkleTrees.merkle_tree();
  15.             的System.out.println(“根”+ merkleTrees.getRoot());
  16.           }
  17.         }
复制代码

  执行结果

1.png


  总结

  本文从简单二叉树的形式实现了简单的MerkleTree,并且计算出了TreeRoot,但是实际上的的MerkleTree不拘谨与二叉树还可能是多叉树.MerkleTree应用广泛,尤其在各类校验中,下一部分我们将着重探讨MerkleTree和传统的HashList校验的差别。

  声明

  本文90%为翻译组合,10%为原创

  引用

  http://java-lang-programming.com/en/articles/29

原文作者:佚名  来源:开发者头条

相关帖子

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部