金华北京网站建设,百度知道在线,wordpress 表单验证码,建湖专业做网站简单的Hash函数介绍
在进入Merkle树之前#xff0c;先简单地介绍一下哈希函数。假设有下面的哈希函数#xff1a; valueHash(value1,value2) v a l u e H a s h ( v a l u e 1 , v a l u e 2 ) 其中#xff0c; value v a l u e 是一个定长的数值#xff0c;作为输入 v…简单的Hash函数介绍
在进入Merkle树之前先简单地介绍一下哈希函数。假设有下面的哈希函数 valueHash(value1,value2) v a l u e H a s h ( v a l u e 1 , v a l u e 2 )
value=Hash(value_1,value_2) 其中 value v a l u e value是一个定长的数值作为输入 value1 v a l u e 1 value_1和 value2 v a l u e 2 value_2的哈希值。 value v a l u e value的特点是如果 value1 v a l u e 1 value_1或者 value2 v a l u e 2 value_2中有一个值发生了变化那么它的数值将会与原来完全不一致而且这种不一致的变化是没有任何规律可言的。同时我们也不可能根据 value v a l u e value的值反推出 value1 v a l u e 1 value_1和 value2 v a l u e 2 value_2的数值。哈希函数的特点保证了对于任意的两个输入组合都有唯一的输出数值与之对应这个特性可以用于校验输入函数参数的性质。 Merkle树的基本架构
Merkle树一般是一个满二叉树当然某些情况下也可以是 k k k叉的。一棵Merkle树的结构如下： 红色的是根结点，灰色的是非叶子结点，黄色的是叶子结点。叶子结点的数值是直接根据数据块的值与0作为参数，经过Hash运算得来的，而灰色结点的值是以两个孩子结点的hash值作为输入，经过Hash运算得来的。下面给出一棵简单的教程： 不过，这里的Hash函数与我们介绍的有一些差异。图片中使用了孩子结点哈希值之和作为输入，而我们不进行求和，直而是直接输入两个孩子结点的参数。把图中叶子结点的哈希函数改成：
Mi=H(0,mi)" role="presentation">Mi=H(0,mi)Mi=H(0,mi)M_i=H(0,m_i) 非叶子结点哈希函数改成 Mi,jH(Mi,Mj) M i , j H ( M i , M j )
M_{i,j}=H(M_i,M_j) 其中 i,j i , j i,j是该结点的两个孩子 Mi,Mj M i , M j M_i,M_j是两个孩子的哈希值。 如果出现需要处理的数据块是奇数个只需要把这些数据块中的任意一个复制一份凑成偶数个就行一般选择复制最后一个块。 综上可知一棵Merkle树有如下特点
叶子结点的值是实际数据块的Hash值。每个非叶子结点的值都是孩子结点的Hash值。根结点称为Merkle根如果树是二叉树的话称为二叉Merkle树且二叉Merkle树一定是满二叉树奇数叶子凑成偶数个
给出复杂度的一些性质
Merkle树的优势
很自然的我们会想到一个问题为什么使用Merkle树而不是直接把所有叶子结点经过一次Hash计算之后直接给出结论比如像上面的介绍图中共有16个叶子结点那么总共需要进行16次Hash运算即可 M0H(0,m0)M1H(M0,m1)M2H(M1,m2)⋮H15H(M14,m15) M 0 H ( 0 , m 0 ) M 1 H ( M 0 , m 1 ) M 2 H ( M 1 , m 2 ) ⋮ H 15 H ( M 14 , m 15 ) M_0=H(0,m_0) \\ M_1=H(M_0,m_1)\\ M_2=H(M1,m_2) \\ \vdots \\ H_{15}=H(M_{14},m_{15})用图表示为 而如果使用Merkle树的话会经过32次的哈希运算这似乎与我们的常识不符合。 设想下面的一个场景 A以上面的图片的形式给B发送了一个处理完的Hash数据就是上面的那个红色Root数据。现在A同学要向B同学证明 M6 M 6 M_6的数据没有被更改过那么A需要向B发送 M6 M 6 M_6到 M15 M 15 M_{15}的所有数据B需要把这些数据重新进行Hash运算才可以验证数据的正确性。显然上面操作的复杂度是 O(n) O ( n ) O(n)。虽然在第一次加密的时候运算简单了但是给后期验证带来计算的麻烦。而在实际的区块链中系统进行验证的次数要远远多于加密运算因此这不是一个好的方式。
然后我们再来看使用Merkle树的优势 同样是进行 M6 M 6 M_6的数据验证A仅需要给B发送图中蓝色的结点即可。在二叉树的情况下它的计算复杂度仅仅是 O(log2m) O ( log 2 m ) O(\log_2{m}) m m script typemath/tex idMathJax-Element-3682m/script是数据块的个数因此把验证数据的复杂度从线性时间降低到了对数时间。同时由于验证数据集的简化我们还可以节约出大量的内存空间。综上所述我们使用Merkle树这种结构来组织区块链的有关数据。
