比特币区块头存放的数据包括 Big Talk Neo 系列：默克尔树

本系列主要结合neo的源码，给大家分享区块链的那些事。

这篇文章和大家聊聊Merkle树。

1. Merkle树是区块中所有交易记录的数据指纹

Merkle 树是一种二叉树，因为它可以快速检查和汇总大量数据，它被用来记录区块中交易记录的完整性。 下面是neo中block的属性，也就是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;// 用于验证该区块的脚本

可以看出，区块由区块版本、上一个哈希值、默克​​尔树的根节点、时间戳、区块高度、下一个区块的记账合约哈希、验证脚本组成。 今天我们主要讲Merkle Tree Root。

区块头明白了比特币区块头存放的数据包括，那么区块的数据区包含什么，来了：public Transaction[] Transactions，这是neo中区块的数据区，一个Transactions的数组。 众所周知：区块链中流通的信息就是交易数据比特币区块头存放的数据包括，也就是neo中的Transaction。

这样做的原因是让大家意识到：Merkle树存在于neo中区块头的根节点，数据区是交易的数组，而不是交易数据的Merkle树。 neo 中的 Merkle 树的价值体现在根节点上。

2. Neo在区块头中生成Merkle根

在neo区块中，所有交易的哈希值构成Merkle树的叶子节点，叶子节点两两组合进行双重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
        }

上面的递归可以通过下图加深

新马克尔树构建

两个相邻的子节点组合起来生成一个父节点。 如果右子节点缺失，则用左子节点填充。 不存储中间变量，只保存最后计算的根节点。

通过Merkle树，在256bits的数据指纹中减少了大量的交易记录。

如果你是一个节点，那么要检查数据是否被修改，只需要计算交易记录的默克尔树的根节点，然后与区块头的默克尔根进行比较就可以得到结果。 3、默克尔树用于SPV的交易验证

这是一个扩展章节，我想在这里和你谈谈Merkle路径认证。 原因是neo中没有spv的应用。

3.1 spvs介绍

SPV 是比特币的轻量级客户端。 它的中文名称是简单支付验证。 主要解决的痛点是比特币共识链过大，非矿工节点需要拉取过多的数据。

SPV只会下载共识链的未阻塞链，可以节省大约1000倍的存储空间。 由于没有得到完整的数据，spv客户端不能作为矿工节点。

3.2 SPV通过Merkle路径进行交易验证

SPV没有交易数据，所以如果需要交易验证，SPV会发送广播让其他非SPV节点向它发送验证数据。 在比特币中，这种类型的数据就是 MerkleBlock。

class CMerkleBlock
{
    public:
        /** Public only for unit testing */
        CBlockHeader header;
        CPartialMerkleTree txn;
        .......
}

这是一段比特币区块的源代码，我们暂且称之为默克尔区块。

一个 Merkle 区块包含两个重要的数据，一个是区块头，另一个是 Merkle 树。 这里的区块头就是比特币区块的区块头。 Merkle树根据其名字可以看做是一系列的交易，实际上是一条Merkle认证路径。

class CPartialMerkleTree
{
protected:
    /** the total number of transactions in the block */
    unsigned int nTransactions;
    /** node-is-parent-of-matched-txid bits */
    std::vector vBits;
    /** txids and internal hashes */
    std::vector vHash;
    /** flag set when encountering invalid data */
    bool fBad;
    ......

接收到 spv 节点请求的完整节点将发送目标区块的区块头和验证路径的交易字符串（交易号和哈希）。 这样就可以通过下图所示的方法对节点进行验证了。 （黑色块是发送的交易）

默克尔路径证明

spv在验证交易e时，只需要通过与交易f计算得到ROOT的值，H(gg), H(H(ab)+H(cd))，然后与区块中的Merkle根进行比较header 可以进行简单的验证。 这里的整个过程就是Merkle交易验证，黑色路径就是Merkle认证路径。

3.3 总结

SPV可以有效减少非矿工节点在公链上的数据存储，目前neo不支持。 同时，比特币区块数据区存储交易Merkle树，而neo存储交易数组。

Merkle树就这些了，后面还有很多关于区块链的分享，期待与大家分享共赢~

csdn地址：