【BTC】数据结构

那比特币区块链的组织形式到底是以链表的形式，还是树的形式呢？

区块头和区块体与默克尔树的关系

默克尔证明详解

区块链和链表最大的区别就是区块链用哈希指针代替了普通指针。

链表的指针就是指向一个结构体在内存中的地址，而哈希指针除了记录这一个区块的地址外，还会记录这个区块的哈希值（这个哈希值是整个区块所有数据进行哈希得到的），这样就能更方便的验证这个区块是否被篡改过（如果被篡改过，那么哈希值肯定就和以前的不一样了）。

第一个区块就是创世纪块，新创建出来的区块会被追加在最后，每一个区块有一个指向前序节点哈希指针。

基于区块链的这种结果，实现了通过其中一个区块的哈希值，就能推算出任何区块的哈希值是否被篡改（防止数据篡改），每一个区块的哈希值是根据自己以及前面的区块计算得来的。因为只要有一个恶意节点篡改了其中一个节点的数据，这个结点哈希值变了，那么连带着后面的所有结点哈希值都要跟这变，牵一发而动全身，这也就给了我们验证的条件。

比特币中的另外一个数据结构就是Merkle tree，他和binary tree（二叉树）的一个区别就是用哈希指针代替了普通指针。

每个区块之间是通过链表组织起来的，而每个区块内部会存储很多交易数据块（tx）。这些区块内部的交易数据块是通过Merkle tree组织起来的。Merkle tree的叶子节点就是交易数据块，上面的都是哈希指针节点，存储的是哈希指针。同样的道理，我们只要是有了根哈希指针（root hash index），我们就能判断出链上的数据区块的数据是否被篡改（因为只要是有一个区块发生了变化，那么根哈希指针肯定也会变化），并且通过Merkle tree的结构，使得查询速度有了很大提高。

只要记住根哈希值，就能检测树中任何部位的修改，如某个交易数据块修改会传导至根节点使根哈希值变化。

那比特币区块链的组织形式到底是以链表的形式，还是树的形式呢？

在比特币中，区块链的组织形式本质上是链表结构，但同时结合了默克尔树（Merkle Tree）这一树状结构来处理交易数据，二者相互配合，共同为区块链的运行提供支持。

链表形式：区块链由一个个区块组成，这些区块之间通过哈希指针依次连接，形成了类似链表的结构。其中，最前面的是创世纪块，最后面的是最新产生的区块。每个区块的哈希指针是根据前面整个区块的内容计算得出的。这种链表结构使得区块链具有抗时间篡改的特性，任何对前面区块内容的修改，都会导致后续所有区块的哈希指针发生变化，从而被轻易检测到。例如，若有人修改了中间某个区块的内容，那么该区块的哈希值会改变，这会使得下一个区块中指向它的哈希指针不再匹配，并且这种影响会像多米诺骨牌一样传递到后续所有区块，最终导致系统中保存的最后一个区块的哈希值也发生变化。
树的形式（默克尔树）：在每个区块内部，交易数据是通过默克尔树来组织的。默克尔树底层的叶节点是一个个交易数据块，上层的内部节点都是哈希指针。这些哈希指针是由下层相邻数据块的哈希值拼接后再取哈希得到的，层层向上直至根节点，根节点的哈希值保存在区块头（block header）中。默克尔树的主要作用是提供默克尔证明（Merkle Proof），用于验证交易是否存在于区块中。比特币节点分为全节点和轻节点，全节点保存整个区块的内容，包括交易的具体信息；轻节点只保存区块头（比如我们本地下载的钱包，就只保存轻节点数据，用于验证交易数据），当轻节点需要验证某个交易时，全节点会提供从交易所在叶节点到根节点路径上的哈希值，轻节点通过计算这些哈希值来验证交易是否存在。

区块链的整体数据结构如下：各个区块用哈希指针连接，默克尔树的根哈希值存于区块头（block header），区块头无交易具体内容，交易列表存于区块体（block body），区块体就存储了默克尔树的结构。

我们本地下载的钱包只会存储轻节点，轻节点只存储了区块头（block header），区块头中存储了交易所在的默克尔树的根哈希值，但并没有存储区块链上的交易数据本身。

假设存在一个轻节点，该轻节点仅保存了 Merkle 树的根哈希值（存于区块的 block header 中），没有保存交易列表及 Merkle 树的具体内容。此时，轻节点想要验证某一特定交易（PPT 中标为黄色的交易）是否存在于区块中。

轻节点会向某个全节点发出请求（某一台矿工机器），全节点收到请求后，将图中标为红色的三个哈希值发送给轻节点。轻节点在接收到这些哈希值后，在本地进行计算。首先计算黄色交易自身的哈希值（图中标为绿色），然后将该绿色哈希值与全节点提供的相邻红色哈希值进行拼接，通过计算得出上一层节点中的绿色哈希值。按照这样的方式，继续将新得到的绿色哈希值与相邻红色哈希值拼接计算，进而算出再上一层的绿色哈希值，直至计算出整棵 Merkle 树的根哈希值。

最后，轻节点将计算得到的根哈希值与自身保存的 block header 里的根哈希值进行比较，以此来判断黄色交易是否存在于该 Merkle 树中，即是否存在于对应的区块里。如果两者一致，则表明该交易在对应的区块中。

区块头和区块体与默克尔树的关系

结构组成：在比特币的每个区块中，分为区块头（block header）和区块体（block body）两部分。
默克尔树根哈希值存储位置：默克尔树的根哈希值存放在区块头中。这一设计至关重要，因为区块头包含的是与整个区块相关的关键元数据，根哈希值作为默克尔树的关键标识，放在此处可用于快速验证整个区块内交易数据的完整性。而区块头并不包含交易的具体内容，这使得其数据量相对较小，便于节点存储和传输。
区块体的交易列表：区块体则存放着该区块内的交易列表。这些交易作为默克尔树的叶节点数据，通过层层计算哈希值构建出完整的默克尔树结构。每个交易在区块体中都有其对应的记录，是区块链交易信息的具体承载部分。

默克尔证明详解

证明的作用：默克尔证明（Merkle Proof）主要用于在比特币网络中，让轻节点能够高效验证某个交易是否存在于特定区块中。由于轻节点只保存区块头，缺乏完整的交易列表信息，默克尔证明提供了一种可靠的验证方式。
证明过程
- 请求与响应：当轻节点想要验证某个交易时，会向全节点发出请求。全节点收到请求后，会将从该交易所在叶节点到根节点路径上的哈希值发送给轻节点。
- 本地计算验证：轻节点收到这些哈希值后，在本地进行计算。首先计算该交易本身的哈希值，然后将其与全节点提供的相邻哈希值依次拼接并计算新的哈希值，按照默克尔树的构建规则层层向上计算，直至得到根哈希值。最后，将计算出的根哈希值与自己保存的区块头中的根哈希值进行比较。
- 验证原理：如果两个根哈希值一致，根据默克尔树的特性，即树中任何一个部位的修改都会导致根哈希值变化，就可以证明该交易确实存在于这个区块中。因为如果交易不存在或被篡改，计算出的根哈希值必然会与区块头中的根哈希值不同。
安全性讨论：在验证过程中，虽然轻节点只能验证交易所在分支的哈希值，但篡改交易数据并使验证通过的难度极大。因为即使修改了交易内容，想要通过调整旁边不用验证的哈希值来保持整个节点的哈希值不变，这在实际中是不可行的，属于人为制造哈希碰撞，而哈希函数的抗碰撞性保证了这种操作几乎无法实现。
复杂度分析：从复杂度角度来看，若底层有 n 个交易，默克尔证明的时间和空间复杂度都是对数级别的。这意味着随着交易数量的增加，验证所需的时间和空间增长速度较慢，是一种高效的验证方式。对于证明交易不存在，如果不对叶节点排序，需要验证整个树，复杂度为线性；若对叶节点按交易哈希值排序，可通过提供相邻交易到根节点的路径证明，复杂度为对数级，但比特币中由于没有证明交易不存在的硬性需求，默克尔树不要求排序。

比特币中的两种基本结构 —— 区块链和默克尔树，都是用哈希指针构造。比特币并不要求默克尔树的叶子节点是有序的，因为比特币中没有证明交易不存在的需求。同时指出，只要数据结构无环，都可用哈希指针代替普通指针，有环结构会出现循环依赖问题。