# 区块链技术与应用03-BTC数据结构

By [kanikig.eth](https://paragraph.com/@kanikig-2) · 2022-10-28

---

[![]({{DOMAIN}}/editor/youtube/play.png)](https://www.youtube.com/watch?v=W9YMtTWHAdk)

哈希指针
----

哈希指针，相比于普通指针，除了保存结构体的地址，还有结构体的哈希值，可以检测结构体内容是否被篡改

每一个区块都包含前一个区块的哈希指针

tamper-evident log

区块中任何一处改动，指向最后一个区块的哈希指针的值就会改变。因此大部分节点可以不用储存整条链的数据，只要保存最近的一些区块即可。

![image-20221023170454933](https://storage.googleapis.com/papyrus_images/14f646a88063cb8772396a96de71178adbb057c55149f88215ed9fc6aa68ea89.png)

image-20221023170454933

默克尔树
----

merkle tree

binary tree

也是用哈希指针代替了普通指针

只要根节点哈希值，就能检测整个树任何部位修改

block header 内有根哈希值

block blody 包含区块内容

![image-20221023171918529](https://storage.googleapis.com/papyrus_images/b40b0e39d69291cd7389f3dece6cf84376e0a4ffbcdadd334bde0ea4917375b7.png)

image-20221023171918529

默克尔树的作用：merkle proof

全节点保存整个区块内容，轻节点只保存header

![image-20221023172131510](https://storage.googleapis.com/papyrus_images/57fde5f8a243055b547b1ffbc7f57c704fc669cd1257e7908fd4afe13173c185.png)

image-20221023172131510

需要证明的交易到根节点的路径，轻节点只需要向全节点请求红色的哈希，就可以往上算出根哈希。轻节点只需要把算出来的哈希和自己本身blockheader存储的根哈希对比，相等即证明该交易存在

这种证明也叫proof of membership/inclusion

merkle proof 证明存在的复杂度是logN

证明不存在：如果叶节点不排序的话，除了全节点把整颗树发给轻节点遍历tx外（复杂度N），没有更高效的方法

将叶节点按tx的哈希值排序 sorted merkle tree，可以解决这个问题。

比特币没有用排序，因为他不需要作不存在证明。

将带证明的tx哈希值算出来，找到他相邻两个tx，（按假设他不存在？）都作merkle proof，如果两个算出来根节点数值都正确，则说明这两个tx是相邻的，中间没有存在交易，即交易不存在（logN）

哈希指针不能用于有环结构

---

*Originally published on [kanikig.eth](https://paragraph.com/@kanikig-2/03-btc)*