这个系列主要结合neo的源码,和大家分享一下区块链的那些事.
这篇文章和大家家聊聊梅克尔树.
1. 梅克尔树是区块中所有交易记录的数据指纹
梅克尔树是一种二叉树,由于它能快速检查和归纳大量数据,被用在区块中记录交易记录的完整性.下面是neo中Block的属性,是区块的头信息组成:
public uint Version; //区块版本
public UInt256 PrevHash; //前一个区块的散列值
public UInt256 MerkleRoot;// 该区块中所有交易的Merkle树的根
public uint Timestamp; // 时间戳
public uint Index; // 区块高度
public ulong ConsensusData; //一致性数据 不知道是什么,这个字段以后再说
public UInt160 NextConsensus; // 下一个区块的记账合约的散列值
public Witness Script;// 用于验证该区块的脚本
可见区块由区块版本、前一个哈希值、梅克尔树根节点、时间戳、区块高度、下一个区块的记账合约散列、验证脚本组成,今天主要聊一下Block中的Merkle Tree Root.
区块头了解了,那么区块的数据区包含什么了,来了:public Transaction[] Transactions,这就是neo中区块的数据区,一个Transaction的数组.正如大家所知道的:区块链中流通的信息就是交易数据了,在neo中就是Transaction.
将这个的原因是想让大家意识到:梅克尔树在neo中存在于区块头部的根节点,数据区是交易的数组,并不是交易数据的梅克尔树.neo中梅克尔树的价值通过根节点体现.
2. neo生成区块头中的梅克尔根
neo区块中,所有的交易的哈希值构成梅克尔树的叶子节点,叶子节点两两组合做双SHA-256运算得到父节点,以此类推等到最后的根节点,同时根节点被记入区块头部.
//双SHA-256运算
public byte[] Hash256(byte[] message)
{
return message.Sha256().Sha256();
}
//左右孩子组合求父节点的哈希值
//concat:组合 a.concat(b) = ab
parents[i].Hash = new UInt256(Crypto.Default.Hash256(parents[i].LeftChild.Hash.ToArray()
.Concat(parents[i].RightChild.Hash.ToArray()).ToArray()));
代码毕竟是一个程序员友好型的东西,那么下面来一波图解,相信聪明的你就get了.
叶子节点是一个交易的哈希值,父节点的哈希值是左右孩子的哈希值联合进行双哈希运算的来的.大家会看到最后面那个叶子节点和倒数第二个相同.这是因为当缺少一个叶子节点时,梅克尔树会将最后的那个节点复制,然后两两组成他们的父节点,形成了一个完整的树形结构.
neo建树的过程就是通过两两子节点计算父节点的过程.话不多说,源码贴上先
//梅克尔树节点
internal class MerkleTreeNode
{
public UInt256 Hash; //节点哈希值
public MerkleTreeNode Parent; //父节点
public MerkleTreeNode LeftChild; //左孩子节点
public MerkleTreeNode RightChild;//右孩子节点
public bool IsLeaf => LeftChild == null && RightChild == null;
public bool IsRoot => Parent == null;
}
//通过建立梅克尔树获取梅克尔树根节点
private static MerkleTreeNode Build(MerkleTreeNode[] leaves)
{
//没有数据,无法建树
if (leaves.Length == 0) throw new ArgumentException();
//只有一个数据,那么根节点就是它了
if (leaves.Length == 1) return leaves[0];
//父节点数组,new出来的不会保存前面的值
MerkleTreeNode[] parents = new MerkleTreeNode[(leaves.Length + 1) / 2];
for (int i = 0; i < parents.Length; i++)
{
parents[i] = new MerkleTreeNode();
//父节点有左右孩子节点
parents[i].LeftChild = leaves[i * 2];
leaves[i * 2].Parent = parents[i];
if (i * 2 + 1 == leaves.Length)
{
//如果叶子节点是奇数,那么最后的叶子节点做复制,两两组成父节点
parents[i].RightChild = parents[i].LeftChild;
}
else
{
parents[i].RightChild = leaves[i * 2 + 1];
leaves[i * 2 + 1].Parent = parents[i];
}
//父节点的哈希值为孩子节点哈希值的联合求双SHA256.
parents[i].Hash = new UInt256(Crypto.Default.Hash256(parents[i].LeftChild.Hash.ToArray().Concat(parents[i].RightChild.Hash.ToArray()).ToArray()));
}
//递归计算
return Build(parents); //TailCall
}
上面的递归可以通过下面的图示来加深理解
相邻两个子节点组合,生成父节点.缺失右孩子节点的,用左孩子节点补齐.不存储中间变量,只保存最后计算出来的根节点.
通过梅克尔树,大量交易记录就缩小在256bits的数据指纹里面啦.
如果你是一个节点,那么检查数据是否被修改就只需要计算一下交易记录的梅克尔树的根节点,然后和区块头的梅克尔跟比较就可以得出结果了。
3. 梅克尔树又用于SPV的交易验证
这里属于拓展篇了,小编想在这里和大家聊聊梅克尔路径认证.归为拓展的原因是neo中没有应用spv.
3.1 spv简介
spv是比特币的轻量级客户端，它的中文为简单支付验证，主要解决的痛点是比特币共识链太大，使非矿工节点需要拉取过多数据。
spv只会下载共识链的去块头的链条，能节省大约1000倍的存储空间。由于没有获取完整的数据，所以spv客户端不能作为矿工节点。
3.2 spv通过梅克尔路径进行交易验证
spv没有交易数据，所以如果需要进行交易验证的时候，spv就会发送一条广播，让其他非spv节点给它发送验证数据，bitcoin中，这类数据类型为MerkleBlock。
class CMerkleBlock
{
public:
/** Public only for unit testing */
CBlockHeader header;
CPartialMerkleTree txn;
.......
}
这是比特币区块的一段源码,我们暂且称呼它为梅克尔块.
梅克尔块中包含两个重要的数据，一个是区块头，另外一个是梅克尔树。这里的区块头就是比特币区块的区块头，梅克尔树可以根据它的命名看出是一串交易，它实际上是一条梅克尔认证路径。
class CPartialMerkleTree
{
protected:
/** the total number of transactions in the block */
unsigned int nTransactions;
/** node-is-parent-of-matched-txid bits */
std::vector<bool> vBits;
/** txids and internal hashes */
std::vector<uint256> vHash;
/** flag set when encountering invalid data */
bool fBad;
......
收到spv节点请求的完整节点会把目标区块的区块头和一条验证路径的交易串(交易编号和哈希)发送过来。这样节点就可以通过下图所示的方法进行验证了。（黑色区块就是发送过来的交易）
spv验证交易e时，只需要通过和交易f、H(gg)、H(H(ab)+H(cd))的计算来计算ROOT的值，然后和区块头中的梅克尔根进行比对就可以进行简单的验证了。这里的整个过程就是梅克尔交易验证，黑色路径为梅克尔认证路径。
3.3 总结
spv可以有效减少非矿工节点对共有链的数据存储，目前neo中并不支持。同时比特币区块数据区存储的是交易的梅克尔树，而neo中则是存放的交易数组。
梅克尔树就讲到这里来，后面还会有很多关于区块链的分享,期待与您共享共赢~
csdn地址:http://blog.csdn.net/little_prog/article/details/79263342
