一.写在前面

　　本篇文章主要是分析了比特币中使用到的数据结构，分为hash指针和merkle tree两个部分来讲解。

二.hash指针

　　　传统的指针中存放的内容为所指向结构体的地址，而hash指针中存放的不仅仅是结构体的地址还包括整个结构的hash值。为什么额外保存了所指向结构体的hash值，主要是为了防止结构体中的内容被篡改。看个例子，常说的区块链其实就是一个个区块通过hash指针连接在一起的,具体的如图2-1

　　　　　　　　　　　　　　　　　　　　　　　　　　图 2-1hash 指针链表

图2-1中每个长方形代表一个区块，H()就表示hash指针,图中共画出了6个区块，从左往右进行编号分别为1，2，3，4，5，6。编号1的区块被称为创世纪块genesis block。以编号3的区块为例，区块3中的hash指针中存放的hash值是整个区块2的值，这点需要注意，不仅仅包括区块2中存放的数据信息还包括区块2中hash指针。通过这样的数据结构可以实现tamper-evident log即防篡改日志。具体如何实现的还是以图2-1的为例，可以看到6个区块通过hash指针相连后，在链的末尾可以得到一个hash指针，假设区块3中的内容被篡改，则可以通过检测区块4中的hash值判断出篡改的发生，为此必须继续篡改区块4中内容才可以保证篡改不被发现，此时又可以通过区块5中内容发现篡改发生，依此类推只要保证链末尾的指针不被篡改，一般是将链末的hash指针保存在本地，就可以检测是否发生了篡改。

三.merkle tree

　　merkle tree中文译为梅克尔树。merkle tree是区块链中区块中交易的组织方式，和传统的二叉树比起来主要的区别点在于merkle tree中的指针均为hash指针。图3-1就是一颗merkle tree。

　　

　　　　　　　　　　　　　　　　　　　　　　图3-1 merkle tree

　　如图3-1，在这个merkle tree 中最底层的叶子节点表示的是数据块data block，在区块链中代表的就是交易信息tx，图中总共由8个tx块，对其从左往右编号为1-8。在tx块这一层的上面三层均为hash指针，在最顶层为包含两个hash指针的节点，对这个节点取hash值便可以得到这颗merkle tree的根hash值merkle root。这个根hash值是存储在区块中的，对应的就是图中的蓝色长方形。区块分为block header和block body 两部分，根hash值存储在block header中，但在bloker header 并不存储具体的交易内容，而在blocker body里存有交易列表。比特币中的节点由两种，一种为全节点，包括blocker header 和blocker body,另一种为轻节点仅有blocker header。

　　观察merkle tree这种数据结构，所有的节点相连均使用了hash指针，显然是使用这种数据结构可以确保数据是无法被篡改的，一旦想要修改某个交易信息tx，就必须往上修改hash指针中的hash值，而修改了hash指针中的hash值就必须再修改上一层hash指针中的hash值，如此以往直到根hash指针，你只需要保存根hash的值不被篡改就可以保证所有交易不被篡改。通过使用这种数据结构可以实现merkle proof,它的应用场景主要是在节点为轻节点的情形下，轻节点种仅有根hash的值，如果交易发生，要如何向轻节点证明已经将交易写入区块中，也就是merkle proof的过程，具体过程如图3-1。图3-1描述的是向轻节点证明黄色的交易块tx,也就是编号3已经写入区块链中merkle proof的过程。首先轻节点要向全节点发出请求，请求能证明黄色方块在这颗merkle tree中的mekle proof。之后全节点将返回给轻节点图中标注红色的hash值，在有了红色的hash值之后，轻节点能在本地计算出所有绿色的hash值，进而计算出根hash的值，再和blocker header中原先保存的根hash值进行对比即可知道交易是否已经写入区块中。这个过程其实就是在二叉树从叶子节点出发找到一条到达节点的路径，所以merkle proof 的时间复杂度是log(n)级别的。

四.写在最后

　　几个疑问，第一个就是一直都在说使用hash这种机制可以确保无法篡改，可这都是在校验的时候才发现的，那到底什么时候进行校验?保存修改的时候？到底是能做到无法修改还是能做到修改被发现？第二疑问是在视频中的同学提出的，在使用merkle proof的时候，以图3-1为例，如果得到的结果是有误的，可这并不一定能说明问题是出现在黄色的tx数据块上，也有可能是因为在它右边的编号4的方块被篡改了而导致最终得到的根hash的值不同。