《区块链技术与应用》——数据结构笔记

普通指针存储的是某个结构体在内存中的地址。而哈希指针除了要存地址之外，还要保存该结构体的哈希值H()。

Hash pointer（哈希指针） 解释：

保存了哈希值和地址

作用：

我们不仅可以找到该结构体的位置，同时还能够检测出该结构体的内容有没有被篡改。

---

比特币中常见的数据结构有两种，分别为区块链和Markle Tree（默克尔树）。

区块链 解释：

区块链就是一个一个区块组成的链表。

区块链第一个区块叫作创世纪块（genesis block）最后一个区块是最近产生的区块（most recent block）每一个区块都包含指向前一个区块的哈希指针。

一个区块的哈希指针怎么算（取哈希）：

是把前面整个区块的内容，包括里面的hash pointer ，合在一起取哈希值。

作用：

通过这种结构，可以实现tamper-evident log（篡改证明记录）。如果有人改变了一个区块的内容，后面一个区块的哈希指针就对不上，因为后一个区块哈希指针是根据前一个区块的内容算出来的，所以后一个哈希指针也得改，以此类推，我们保留的是最后一个哈希值也会变化。

区块链和普通的链表相比有什么区别：

①用哈希指针代替了普通指针(Block chain is a linked list using hash pointers)

②普通链表可以改变任意一个元素，对链表中其他元素是没有影响的。而区块链是牵一发而动全身。

Merkle Tree（默克尔树）

类比Binary Tree

最下面一层是data blocks（数据块）

上面三层内部节点都是hash pointers（哈希指针）

第一层是根节点，根节点的区块也可以取个哈希，叫root hash（根哈希值）

作用：

只要记住根哈希值，就能检测出对树中任何部位的修改。

提供merkle proof。

比特币当中各区块之间用哈希指针连接在一起，每个区块所包含的交易组织成一个merkle tree的形式，data blocks一个区块实际上是一个交易，每个区块分为两部分，分别是block header, block body（块头和块身）。block header里面有根哈希值，但是，block header没有交易的具体内容，block body里面是有交易的列表的。

---

比特币中的节点分为两类

全节点：保存整个区块的内容，即block header, block body都有，有交易的具体信息

轻节点：只有block header

如何向一个轻节点证明某个交易是写入区块链的?

利用merkle proof。

找到交易所在的位置(最底行的其中一个区块)，这时该区块一直往上到根节点的路径就叫merkle proof。​

全节点将整个Markle proof发送给轻节点（如上图），轻节点即可根据其算出根哈希值，和自己保存的对比，从而验证该交易是否被写入区块链。只要沿着该路径，所有哈希值都正确，说明内容没有被修改过。

假设某个轻节点想知道图中黄色的交易，是否包含在了merkle tree里面。这时轻节点向一个全节点发出请求，请求证明黄色的交易被包含在merkle tree里面的merkle proof。全节点收到请求后，将图中标为红色的这三个哈希值发给轻节点即可。有了这些哈希值之后，轻节点可以在本地计算出图中标为绿色三个哈希值。首先算出黄色交易的哈希值，即它正上方的那个绿的哈希值，然后跟旁边红色的哈希值拼接起来，可以算出上层节点绿色的哈希值。依次向上拼接，就可以算出整棵树的根哈希值。轻节点将此根哈希值和block header里的根哈希值比较，就能知道黄色的交易是否存在。（验证时只能验证该路径的哈希值，其他路径是验证不了的，即该图中红色的哈希值是验证不了的）

merkle proof可以证明merkle tree里面包含了某个交易，所以这种证明又叫proof of membership或 proof of inclusion。merkle proof 复杂程度是θ(log(n))​如何证明merkle tree里面没有包含某个交易?即proof of non-membership。

方法一：把整棵树传给轻节点，轻节点收到后验证树的构造都是对的，每一层用到的哈希值都是正确的，说明树里只有这些叶节点，要找的交易不在里面，就证明了proof of non-membership。它的复杂度是θ(n)。

方法二：对叶节点排序，按照交易的哈希值从小到大排序。二分查找+反证法

比如，在五六之间，这时提供的proof是第五个第六个叶节点都要往上到根节点。如果其中哈希值都是正确的，最后根节点算出的哈希值也是没有被改过的，说明第五六个节点在原来的merkle tree里面，确实是相邻的点。所以就不存在这个交易。

其复杂度也是log形式，代价是要排序。排好序的叫作sorted merkle tree。比特币中没有用到这种排好序的merkle tree，因为比特币中不需要做不存在证明。​