区块链学习三——比特币的数据结构

文章内容来源于北京大学肖臻老师《区块链技术与应用》公开课

一、哈希指针（hash pointers）

普通的指针存储的是结构体在内存中的起始地址
哈希指针除了存储起始地址还存储该结构体的哈希值
根据哈希值可以检测出该结构体是否被篡改。

二、区块链

由一个一个区块组成的链表
Q：区块链使用的链表与普通链表的区别
A：区块链使用的链表使用哈希指针代替了普通的指针

系统中产生的第一个区块：创世纪区块 genesis block
系统中最近产生的区块：most recent
每个区块都有一个哈希指针
取哈希值是将整个区块的内容合在一起取得哈希（包括哈希指针）
只需记住最后一个哈希值即可检测前面得区块是否被篡改（多米诺骨牌、牵一发而动全身）
因此节点只需保存最近的节点，需要前面得区块可以问别人要，通过计算哈希值即可检测前面的区块是否是正确的。

三、Merkle tree

根节点也可取哈希值叫做根哈希
知道根哈希可以检测出整棵树节点是否被篡改（效率更高）每个节点的改变会导致根节点发生改变
最下面的子节点相当于是交易

这个数跟二叉树很像
最上面深颜色的方块代表区块，tx即最下面的一行代表交易，H()哈希值
每个区块都包含块头block header （有根哈希值、块头没有具体的交易数据的）和块身block body（块身含有交易数据）
区块包含的所有交易组成的merkle tree的根哈希值存在区块的块头

1.Merkle tree的作用：Merkle Proof

全节点：保存整个区块链的内容，有块头block header 和块身block body（块身含有交易数据）
轻节点：只保存块头block header
Q（Merkle Proof）：如何向轻节点证明交易已经写入区块链中 （轻节点没有保存交易列表，只有根哈希值block header）上图黄色的方块包含在Merkle tree。
A：轻节点向全节点发出请求。全节点把图中红色的H() 哈希值发给轻节点。轻节点在本地计算标绿的哈希值 H()，由绿色的哈希值和红色的哈希值可以计算出上一层节点的绿色的哈希值；再由刚才计算出绿色的哈希值与该层红色的哈希值；计算出再上一层的绿色哈希值，再由绿色的哈希值与红色的哈希值即可计算出根节点的哈希值，与轻节点的哈希值比较即可得到是否包含交易信息。
只验证交易数据所在的到根节点的一条分支即可，根哈希值不变，即交易都不会被篡改。人为制造哈希碰撞可以篡改 难度太大了collision resistence

Merkle Proof（Proof of membership、Proof of inclusion）:向轻节点证明交易已经写入区块链中。有n条交易的话时间复杂度为log(n)

2.Proof of non-membership

Q：如何证明Proof of non-membership
A：直接将一棵树发给轻节点，把整个交易都发给轻节点。时间复杂度为O(n)
优化：把交易的哈希值按照顺序进行排序，其他步骤跟merkle proof 过程类似。时间复杂度为log(n)。代价是要先排序。sorted merkle tree。
比特币中不要求排序 不要求Proof of non-membership

四、总结

区块链与Merkle tree都需要使用哈希指针来构造。没有环的链表可以使用哈希指针，有环的不可使用哈希指针。