BTC-数据结构

约 1674 字大约 6 分钟

2021-08-29

block chain

比特币中一个最基本的数据结构就是区块链，区块链就是一个个区块组成的链表。那么区块链和普通的链表有什么区别呢，一个区别就是用哈希指针代替了普通指针。 Block chain is a linked list using hash pointers。

最前面的区块叫做genesis block 创世纪块。最后的叫 most recent block，最近产生的区块。每个区块都包括指向前一个区块的哈希指针。

这种数据结构的好处是什么？H()是算的整个区块内容的哈希，包括内容包括哈希指针。只要保存最后的哈希指针，试图篡改了任意一个内容，，只要对不上就知道链上内容被篡改。后面所有的都得跟着改。这个特性即tamper-evident log（防篡改日志）

所以比特币中有些节点，就不一定要保存整条区块链的内容，可以只保留最近的几千个区块，以前的就不用存了。如果用到一起的区块怎么办呢？可以向其他节点去要就行了。有些节点可能是恶意的，怎么知道给的是否正确呢？还是用到hash指针这个性质。向别的节点询问历史区块，只需要判断它的hash值根自己保存的是否一致即可。

merkle tree

比特币中另外一种重要的数据结构： merkle tree，可能没听说，但是肯定听说过binary tree。有什么区别呢，其实还是哈希指针代替了普通的指针。

比特币中各个区块用哈希指针联系一起，每个区块所包含的交易是组织成merkle tree组织起来的。其中的data blocks就是tx交易。

每个区块可以分为俩个部分，分为块头、块身。一个区块的所有交易组成的merkle tree的 root根hash是存储在block header的。但是block header没有交易的具体内容。block body是有交易的列表。

merkle tree有什么用途呢？一个用途就是提供merkle proof。比特币中的节点分两类：全节点（包含block header和block body）；轻节点（只有block header）比如手机上比特币钱包的应用（如SPV客户端）。例如果需要向一个轻节点证明某个交易是写入到区块链端，怎么证明呢：

比如说：你想我买一些东西，需要给我转一笔钱，那你告诉我说你转给我钱的交易已经写到区块链里了，这个支付已经完成，我是个轻节点，就只能在手机上查查，我怎么知道这个交易是不是已经写到区块链里。这个就要用到merkle proof，找个这个交易所在的位置，从这个交易往上一直到根节点的路径，就叫做merkle proof。最上面是一个小型的区块链，把其中的一个Merkle Tree展现了出来。最下面一行是包含的交易。假设某个轻节点想要知道某个交易（标注黄色的tx）是不是包含在这棵Merkle Tree里面，这个轻节点没有保存交易列表，没有这棵Merkle Tree的具体内容，只有一个根hash值，因为根hash值是保存在block header里面的。可以这样验证：这个轻节点向某个全节点发出请求，请求一个能够证明黄色tx的交易被包含在这棵Merkle Tree的merkle proof。全节点收到这个请求后，只要把图中标为红色的三个hash值发给轻节点即可。有了这些hash值后，轻节点可以在本地计算出图中标为绿色的三个hash值，就能层层往上算出根hash值，轻节点把计算的根hash值根block header中的根hash值比较一下，就能知道这个黄色的tx是不是在这棵Merkle Tree里面。