重要概念：哈希指针 hash pointers
普通的指针是存结构体的地址，哈希指针除了保存地址之外，还要保存这个结构体的哈希值。
比特币中的两个数据结构：区块链、Merkle tree都用到了hash pointers
区块链
区块链和普通的链表的区别：用哈希指针代替了普通指针
Block chain is a linked list using hash pointers.
普通链表你可以改变链中的其中一个元素，对链的其他元素是没有影响的。
假设上图比特币区块链的最左边的为创世区块Genesis block，最右边的为最新区块Most recentBlcok，可以看到每个区块的块头都有一个指向前一个区块的hash指针（key,value）。
区块链中，每一个区块（元素）都包含着前一个区块X（X本身的数据+X上保存的X-1整个区块的哈希值）的哈希指针，本地中保存着最后一个区块整块的哈希指针，取Hash时候是把整个区块包括前面区块的Hash Point在内的前部内容一起取Hash（HashPreBLock），因此，区块链是有记忆的。每修改一个区块的数据，就会导致后面所有的区块的哈希指针都对不上。牵一发而动全身！--->只要保存最后一个区块的哈希指针就能知道有没有人改过区块链中任何一个区块了，--->tamper-evident log 防篡改日志
（如果节点试图修改区块使得交易合法，那么他需要修改后面的全部区块的块头。而修改一个区块的块头由于Hash算法的特性，和挖矿获得记账权的难度是一样的。除非该恶意节点拥有全网51%以上的算力，否则修改的速度是赶不上合法矿工的挖矿速度，这些篡改的区块是不会被其他矿工接受的。）
通过这一特性使得比特币的部分节点可以不必保留全部的区块信息，而只需要保存最近的几个节点的信息，当需要用到以前的节点时候可以再向其他区块请求。而如果网络中存在某些恶意节点试图修改信息，试图提供的前节点信息是错误的，那么只要对该提供的信息进行一次Hash运算，判断Hash值与原有的Hash值相等就可以进行验证。
Merkle tree
对比binary tree: 1.哈希指针代替了普通指针 ，叶子节点是数据块，data blocks，叶子结点上面的都是哈希指针 hash pointers,每个节点再根据下面两个节点的hash值计算出hash值保存在父节点上，根结点也计算出一个 root hash 。
Merkle tree的结构与普通二叉树Binary tree接近，最下面的均为数据块Data Blocks，上面的均为Hash指针。这些节点的Hash值再取Hash后形成新的Hash指针，最上方的指针为根Hash指针Root Hash。这个结构的好处是，只要记住根节点的Hash指针，就可以保护整棵树，对该树种任何节点的篡改都被记录。任意一个区块的修改（如黄色的tx），就会随着其Hash指针的变动一直传导到Root Hash。
只要记住root hash，整颗树哪个地方进行了修改，都能检测到。
比特币当中，各个区块是用哈希指针连接在一起的，每个区块所包含的交易，是组织称一个Merkle tree的形式。也就是说，Merkle tree底下的每一个叶子节点数据块实际上是一个交易。
每个区块分为两部分，分为块头（block header）和块身(block body),block header保存着root hash，block header没有交易的具体内容，block body里有交易的列表。
Merkle tree的一个用途是提供 Merkle proof
比特币中的结点分为两类，一类是全节点，还有一类是轻节点。全节点是保存整个区块的内容（block header + block body）。轻结点只保存header（例：手机上的比特币钱包）。当轻结点需要证明某个交易(tx)存在时，就需要用到Merkle proof。 Merkle proof可以理解为某个交易（叶子结点）到root hash（根结点）之间的路径。轻节点向某个全节点发出请求，得到路径中所有节点的兄弟节点的Hash，就可以逐层计算出root hash 与自己保存的root hash进行对比，即可知道交易是否被记录。
果此时轻节点需要证明某个交易是被写入到区块链中（比如购买商品时，要证明支付已经完成，而收款方为手机钱包轻节点，需要验证该交易是否被写入到区块中）。即上图需要证明黄色的tx交易是否被记录，此时Merkle Proof的路径为黄色交易向上，直到Root节点。
证明过程为： ①轻节点向全节点请求一个Merkle Proof，全节点只要把上图中标红的三个Hash值发给该轻节点； ②轻节点首先在本地计算(下数第二行)标为绿色的Hash值； ③并与右边红色请求的红色Hash值一起，再在本地计算新的Hash值（下数第三行）； ④再与左边请求的红色Hash值一起进行Hash，又得到新的Hash值（下数第四行）; ④最后与右边请求的红色Hash值一起，计算出根节点的Hash值； ⑤最后把计算得到的Hash值与事先保存的Hash值进行比较，就可以知道该交易是否被包含在交易列表中。
（恶意的交易会影响正常的交易数据的验证，恶意修改交易靠修改其他交易数据是掩饰不了的？？）
这种证明又叫做 proof of membership。proof of inclusion
对于轻结点来说，你发给我这么一个Merkle proof ，时间和空间的复杂度：O(logN)
能不能证明 proof of non-membership:1.遍历所有叶子结点（O(N)），这种方法效率低 2.如果叶结点是按照交易的hash值排序... sorted Merkle tree（比特币中的Merkle tree不要求排序）
哈希指针不能用在有环的数据结构中（会循环依赖！）
这个Merkle Proof只能验证交易所在的分支，却没有验证其他分支，是否会给伪造不在交易分支中的交易提供自由度呢？这个问题就相当于因为其他的Merkle Tree的节点并没有被验证，能否通过修改其他节点来使得Root Hash不变。实际上这样的篡改是不可行的，如果想要通过修改其他交易而Hash值不变，根据Collision resistance的特性，伪造Hash值只能通过花费计算资源暴力求解，而这个暴力求解要比挖矿的难度大得多。因为挖矿只要求Hash结果小于Target，即 퐻푎푠ℎ(푡푥,푛표푛푐푒)<푡푎푟푔푒푡 ，而伪造Merkle Tree需要计算出指定的Hash结果，即要求 퐻푎푠ℎ(푡푥,푛표푛푐푒)==푡푎푟푔푒푡 ，它的难度将远远大于挖矿，约等于挖矿难度的Target倍。
Merkle Proof不需要验证全部的交易即可完成交易验证，即在Merkle Tree中最下方的交易有N个，Merkle Proof算法的时间复杂度是 푂(푙표푔(푛)) ，是一个高效的算法。那么能否通过Merkle Proof来证明不包含某个交易，即Proof of non-membership呢？最简单的证明方式就是把整棵树都传给轻节点，轻节点对树的构造的即每个Hash值进行验证，如果每个交易都被恰当地记录了，而需要找的节点并不包含在内，那么就相当于做了一个Proof of non-membership。但是这个算法的时间复杂度是 푂(푛) ，并不是一个高效的算法。一种更高效的算法是，把所有叶节点做顺序而去验证相邻节点。比如把所有的叶节点order by Hash(tx)即按照Hash值排序，然后再去构造一个排过序的Merkle Root。此时当需要证明一笔交易不存在时，只要根据交易列表找到其相邻的左右两个交易，证明Hash(tx)左右相邻的交易是相邻的，即可证明要找的交易tx不被包含在内，即提供了这样的Merkle Proof证明。这种算法叫做Sorted Merkle tree，它的时间复杂度也是 푂(푙표푔(푛)) ，代价是需要对交易的Hash值排序。在比特币中并没有采用这种算法，因为比特币并不需要这种Proof of non-membership这样的证明。
Merkle tree与Sorted Merkle tree均属于Hash指针应用的数据结构。一般只要是无环的数据结构，均可以使用Hash指针的方式存储，以确保数据未被篡改。而如果数据结构有环，自身的Hash值是自身Hash值的函数，会形成循环引用，这类有环的数据结构不适用Hash指针的方式。
相关文章
发表评论