在区块链里，每个区块都使用Merkel树来代表交易的摘要。
Merkel树就是散列树（Hash Tree），由一个根节点、一组中间节点和一组叶节点组成。顾名思义，就是存储hash值的一棵树。Merkle树的叶子是数据块(例如，文件或者文件的集合)的hash值。非叶节点是其对应子节点串联字符串的hash。
Merkel树把相邻的两个哈希合并成一个字符串，然后运算这个字符串的哈希，这样每两个哈希就得到了一个子哈希。如果最底层的哈希总数是单数，那到最后必然出现一个单身哈希，这种情况就直接对它进行哈希运算，所以也能得到它的子哈希。最下面的叶节点包含存储数据或其哈希值，每个中间节点是由它的两个子节点内容的哈希值，根节点由它的两个子节点内容的哈希值组成。
在比特币网络中，用的哈希树（Hash Tree）算法是SHA256。不管多少个交易，都会汇集为32字节。
Merkel树在SPV节点上得到了广泛的应用。
散列树
我们选择质数分辨算法来建立一棵散列树。
选择从2开始的连续质数来建立一个十层的哈希树。第一层结点为根结点，根结点下有2个结点;第二层的每个结点下有3个结点;依此类推，即每层结点的子节点数目为连续的质数。到第十层，每个结点下有29个结点。
同一结点中的子结点，从左到右代表不同的余数结果。
例如:第二层结点下有三个子节点。那么从左到右分别代表:除3余0，除3余1，除3余2。
对质数进行取余操作得到的余数决定了处理的路径。
结点:结点的关键字(在整个树中是唯一的)，结点的数据对象，结点是否被占据的标志位(标志位为真时，关键字才被认为是有效的)，和结点的子结点数组。
依此类推，即每层结点的子节点数目为连续的质数。
哈希树特点
哈希树的结构是动态的，也不像某些哈希算法那样需要长时间的初始化过程，只需要初始化根结点就可以开始工作。哈希树也没有必要为不存在的关键字提前分配空间。
查找迅速，最多只需要10次取余和比较操作，就可知道这个对象是否存在。哈希树的查找次数和元素个数没有关系。
结构不变，哈希树在删除的时候并不做任何结构调整。这也是它的一个非常好的优点。常规树结构在增加元素和删除元素的时候都要做一定的结构调整。
非排序性，哈希树不支持排序，没有顺序特性。需要注意的是:哈希树是一个单向增加的结构，即随着所需要存储的数据量增加而增大。即使数据量减少到原来的数量，但是哈希树的总结点树不会减少。这样做的目的是为了避免结构的调整带来的额外消耗。
哈希树(HashTree)算法就是要提供一种在理论上和实际应用中均能有效地处理冲突的方法。
哈希树的理论基础
质数分辨定理
这个定理可以简单的表述为：n个不同的质数可以“分辨”的连续整数的个数和他们的乘积相等。“分辨”就是指这些连续的整数不可能有完全相同的余数序列。这个为哈希树的分辨方式奠定了理论基础。
显然，这个定理的一个特殊情况就是从2起的连续质数。我们可以记M(n)为前n个连续质数的乘积。连续10个质数就可以分辨大约M(10) = 6464693230 个数，已经超过计算机中常用整数（32bit）的表达范围。连续100个质数就可以分辨大约M(100) = 4.711930 乘以10的219次方。
而按照目前的CPU水平，100次取余的整数除法操作几乎不算什么难事。在实际应用中，整体的操作速度往往取决于节点将关键字装载内存的次数和时间。一般来说，装载的时间是由关键字的大小和硬件来决定的；在相同类型关键字和相同硬件条件下，实际的整体操作时间就主要取决于装载的次数。他们之间是一个成正比的关系。
余数分辨定理
余数分辨定理可以简单的表述为：n个不同的数可以“分辨”的连续整数的个数不超过他们的最小公倍数。超过这个范围就意味着冲突的概率会增加。
线性分辨算法
线性分辨算法是利用线性函数f(x)=ax+b作为分辨算法的分辨算法，或者称为余数分辨算法。这种算法简单易行。上面所有的讨论都是基于线性分辨算法的。
非线性分辨算法
非线性分辨算法是指在特征数的获取过程中采用非线性函数的方法。这也就是说，可以完全使用非线性函数，或者非线性函数和线性函数混合使用。但是只要是使用了非线性函数，那么就被称作非线性分辨。
Hash
Hash是一个把任意长度的数据映射成固定长度数据的函数。
例如，对于数据完整性校验，最简单的方法是对整个数据做Hash运算得到固定长度的Hash值，然后把得到的Hash值公布在网上，这样用户下载到数据之后，对数据再次进行Hash运算，比较运算结果和网上公布的Hash值进行比较，如果两个Hash值相等，说明下载的数据没有损坏。可以这样做是因为输入数据的稍微改变就会引起Hash运算结果的差异，而且根据Hash值反推原始输入数据是困难的。
网友评论