初识Merkle Tree
前段时间在一篇微信公众号上看到一段用java代码实现区块链Merkle Tree的文章，感觉很有意思。
那么什么是Merkle Tree呢？
最近区块链那么火，可能会有一些小伙伴知道Merkle Tree是区块链里面用于保证从对等网络中接收的数据块未受损和未改变。而实际上我们知道区块链一个最大的特征就是去中心化，那么p2p网络就是体现这种去中心化的特征的一个典型。下面我就举一个p2p网络的例子来尝试解释一下Merkle Tree。
北邮的小伙伴应该都很熟悉北邮人BT，这简直是一个获取各种电影各种剧、球赛还有各种软件的神器。这个平台能实现下载速度如此之快的原因，就是它是一个p2p的下载平台，你正在下载的资源实际上是由其他正在挂载此项资源的同学提供的。A提供一点，B提供一点，C提供一点，它就具有很明显的“去中心化”的特征。
但我们要如何验证我们正在下载的资源是不是我们的资源呢？有没有被篡改呢？有没有受到攻击呢？
当然北邮人BT用的是北邮的内网，那如果不考虑这个因素，我们是如何保证在p2p网站上下载的东西是正确的且完好无损的呢？这可跟从固定数据源下载资源不同，如果从固定数据源下载，那么只要把数据进行hash运算得到固定长度的hash值，再与可信的来源公布的该段数据的hash值进行比较，就可以校验其正确性了。
在这里插播一段关于hash(散列)的特征：
1、hash运算实际上是把任意长度的明文加密成固定长度的秘闻的一种加密方式，据我的理解，就是说，假设密文长度用n来表示，那么不管明文长度有多长，加密后的密文长度一定是n；
2、两条随机抽取的消息，它们不可能含有相同的hash码。
3、两则不同的消息不可能有相同的消息摘要（Message Dingest），即明文信息通过hash加密得到的消息。严格来说应该是可能性极小，在网上看到过一个比较，说是这个概率就跟在有10个太阳大小的球体中随机选取一点就找到一个特定的原子的概率差不多；
刚才说到从固定资源下载，只需要把数据进行hash运算并与标准进行匹配就行了。而p2p网络上的下载，数据来自于不同的源。再加上如果数据量比较大，又怎么校验每一段数据的完整性呢？
假如我们要从BT上下载电视剧《欢乐颂》，大概有40多G。
某用户A要下载《欢乐颂》，假设此时正好有B、C、D、E、F五个用户正在挂着《欢乐颂》，那自然A要下载的资源就从这五个用户得来。
但是假如我们无法保证B、C、D、E、F这五台机器的稳定性和可信度，这部剧这么大，又从这么多台机器上下载，这台机器一点，那台机器一点，我怎么校验这部剧下载得是否完好了呢？
基本思想就是把大的文件分割成小的数据块，并对数据块进行逐个校验。如果发现某块数据块校验未通过，那么只需要再下载这一小块数据块即可。
可是怎么校验呢？
有一种方法是对每一个小的数据块进行hash运算，分别得到各自的hash值，如下图：
假设我们把这部剧的数据文件分成了n个小的数据块，每块分别作其散列值hash1，hash2……hash n。这就有一个散列表（hash list）。将散列表中的每一个元素串在一起，做一次散列运算，得到散列表的根hash。
我们在下载数据之前，会从可信的数据源得到这整份文件的正确的根hash（一般来说，正确的根hash会封装在事先下好的种子文件里面），在后续计算出散列表的根hash之后，我们用计算出来的根hash来与正确的根hash比较，来校验hash list的正确性，进而校验每一个hash值，每个数据块的正确性。
但这种方式有一个很明显的短板，就是我们在获得根hash之后，必须对这个文件所有的数据块hash值进行逐一检查，才能够找到其中可能出错的数据块。
而Merkle Tree就解决了这个问题。
关于Merkle Tree的原理，先上图。
如图，假设我们把一份大文件分成7个小数据块，如图中的data1-data7，然后分别对其进行散列加密，如图中的hash1-hash7，这是第一层（level1）；而后，hash1和hash2合并，并计算合并后的hash值hash2-1，hash3和hash4，hash5和hash6同理合并，分别得到hash2-2和hash2-3，最后hash7落单，便独自hash加密成hash2-4，这是第二层（level2）；再往上，同理归并，最后得到整个Merkle Tree的根Tree Root，其实也就相当于hash list里面的根hash。
即：每一层的hash数据块与相邻的hash数据块两两配对并加密成新的hash块。如果落单，则自身hash加密即可。
我的理解，它相对于hash list的好处，就是在发现根hash出错以后，不必要对每一个数据块的hash值进行逐一检查，而是可以根据树的原理，逐层分析其左右子树的正确性，最终找到那个出错的数据块。
在这里把文章开头说过的看到的那篇代码贴上，先声明这段代码不是我的成果，原文链接：https://mp.weixin.qq.com/s/DrsloxXGXV_F9imWiRdIaw
package merkleTree;
import java.security.MessageDigest;
import java.util.ArrayList;
import java.util.List;
public class MerkleTrees {
//transaction ListListtxList;
//Merkle RootString root;
/** * constructor * @param txList transaction List */
public MerkleTrees(Listtx) {
txList = tx;
root = "";
}
/** * execute merkle_tree and set root */
public void merkle_tree() {
List<String> tempTxList = new ArrayList<String>();
for(int i=0;i<txList.size();i++){
tempTxList.add(this.txList.get(i));
}
List<String> newTxList = getNewTxList(tempTxList);
while(newTxList.size()!=1) {
newTxList = getNewTxList(newTxList);
}
root = newTxList.get(0);
}
/** * return node hash list * @param tempTxList * @return */
private List<String> getNewTxList(List tempTxList) {
List<String> newTxList = new ArrayList<String>();
int index = 0;
while(index<tempTxList.size()){
String left = tempTxList.get(index).toString();
index++;
String right = " ";
if(index!=tempTxList.size()){
right = tempTxList.get(index).toString();
}
String sha2HexValue = getSHA2HexValue(left+right);
newTxList.add(sha2HexValue);
index++;
}
return newTxList;
}
public String getSHA2HexValue(String str){
byte[] ciper_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){
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;
}
代码中的加粗体是我感觉最能体现Merkle Tree特性的片段，其核心就是在特定的一层中，对于每单数个hash过后的数据块，如果它不是该层最后一个数据块，则和它下一个数据块组成一个新的字符串，并再次进行hash运算。
至于这个hash运算的过程具体是怎样的，从代码中只能看出它似乎使用SHA-256的加密算法进行运算。本科的时候学过SHA-1算法，具体的算法步骤一直都很难看懂，后续还需要再学习一下。
