转载请注明出处~
我们说BTC是一个分布式的账本，
这个账本本身就是BTC中一个最基本的数据结构，
也就是我们常说的区块链，
区块链就是一个一个区块串联起来的链表，
每个区块里边记录着不同的交易记录，
那这里的区块链和普通的链表有什么独到之处呢？
指针、哈希指针
精髓就在哈希指针！
在计算机的世界里所有的数据都是存放在存储器中的，内存是以字节为单位的连续编址空间，每一个字节都有一个唯一的内存单元地址。
有过编程经验的同学都知道，不同类型的变量占用字节数不同，比如java里的 int类型占 4 个字节，char 类型占 2 个字节：
系统在内存中为变量分配存储空间的首个字节单元的地址，就是该变量的地址。
指针也是一个变量，只不过存储的是某个变量在内容中的地址，有了指针用户就能正确访问存储单元中的数据，我们形象的表示为指针P指向内存中的某个结构体：
那什么是哈希指针呢？
不同于一般指针，哈希指针不但要指向该结构体，还要存储该结构体的哈希值：
哈希指针有啥特殊之处呢？
我们在《BTC 学习笔记连载(3)——Hash》已经介绍过哈希函数，哈希指针的独到之处就是不但可以指向一个结构体，还能验证该结构体的内容是否被修改过，这是比特币数据结构的核心基础：
全网每个节点在内存中都存储了这样一个链表，基于哈希指针该链表才能在全网达成共识。
除了创世区块，每个区块都存储了前一个区块的哈希，任何试图篡改某个区块交易的行为都无法被其它诚实节点接受，如上图：
-
某个作恶者想篡改Block#2 的一笔Transaction
-
由于Block#3中存储了Block#2的哈希，所以作恶者必须连带修改H(2)
-
一直到当前正在出块的Block#5中存储的H(4)
-
这必将和全网其它诚实节点存储的H(4)对不上
-
最终单一节点的作恶行为不会被全网大多数其它诚实节点所接受，自然就保障了Transaction无法被篡改
这显然和普通链表是有本质区别的，基于哈希指针构造的链表是牵一发而动全身的，对任何区块的任何地方的修改都会最终影响到当前Mining区块的Pre哈希值，而全网任意节点只要存储该最新区块的哈希值即可验证整条链表有没有被修改过。
基于这个特性，比特币网络中的部分节点就没有必要保存全部区块的数据：
-
非全节点可以只保存最近的几千个区块
如图，Block# n-m 到Block#n -
当需要更早的区块时再问相邻的全节点请求数据
比特币是一个开放式的去中心化系统，你怎么知道你请求的不是一个恶意节点呢？如果一个恶意节点欺骗你返回篡改过的区块怎么办呢？
显然这是不可能的！
为什么？
3秒钟思考一下
……
……
……
跟上面讲的道理一样，只要自己的区块数据包含正确的Pre哈希值，基于哈希指针就可以验证请求的区块数据是否被篡改过。
这就是区块链，这就是比特币，由哈希指针构造的链式账本。
Block chain is a linked list using hash pointer！
Binary Tree、Merkle Tree
实际上我们熟悉的BTC的链表结构比上面讲的要复杂一点，每一个Block其实是由2部分构成的，即Block header 和 Block body：
-
前面讲的哈希指针，其实是只针对Block header的
每个Block header里存放这Pre Block header的哈希值 -
Block body里包含完整的Transaction数据
-
整个Block Body的所有Transaction会计算出一个根哈希存放在Block header里
我们把任意一个Block展开，具体看一下整个区块的构成：
Block header包含了该区块的一些关键信息：
-
版本、时间戳
-
难度值、Nonce
Mining过程就是不停地尝试Nonce计算满足难度要求的哈希 -
Pre Block header Hash
每个Block存储上一个Block header的哈希，即我们签名讲的哈希指针 -
Root Hash
本Block内所有交易形成的根哈希
Block body里包含的就是：
- Transaction 以及由这些Tx计算出来的跟哈希
在Block body里有一个长得很像二叉树的结构。
什么是二叉树？
做过机器学习的同学应该就很熟悉了，XGBoost、逻辑回归等模型算法一般都是基于二叉树来构造的。二叉树即我们熟知的binary tree，是指树的节点不大于2的有序树，是一棵由一个根节点和两棵互不相交的左子树和右子树构成，左子树和右子树又同样都是二叉树。
但BTC用到的事Merkle Binary Tree，简称Merkle Tree。
什么是Merkle Tree？
简单理解就是基于哈希指针构造的二叉树：
-
最下面黄色底的即为Block包含的Transaction
-
Transaction之上的部分就是Hash Pointers
先计算每一笔Transaction的哈希值
然后每2笔Transaction的哈希再合一起取哈希，直到形成区块的根哈希（Root Hash） -
Root Hash存放到Block header里
有了这个Root Hash即可保障Block body的Transaction不被篡改
《BTC 学习笔记连载(4)——公钥密码学：D-H & RSA》这篇文章介绍过Merkle，公钥密码学的始祖，再次向他致敬！
为什么要将Block分成2部分？
为什么要用Merkle Tree？
这个肯定是有考究的，
为什么？
思考一下
……
……
……
Block header里没有具体的Transaction，所有的Transaction列表都存放在Block body里，Block body里Tx列表构成Merkle Tree，其根哈希存放在Block header里。
简单来讲我们可以将BTC的全网所有节点分为全节点和轻节点：
-
全节点需要存放区块的完整数据
-
全节点又可以划分为归档节点和剪枝节点
归档节点也叫 “监听节点”，是保存了全部历史区块数据的全节点
当其它节点Ask时，将对应区块数据分享出去
减枝节点就是前面提到过的只存放最近几千个区块数据的这类节点，需要的时候再问归档节点要 -
轻节点只保存Block header数据
比如手机上的Token poket、metamask等钱包应用
因为它不可能去存放Block body的巨量Transaction数据
轻节点也不需要Mining，所以只需要验证跟自己相关的Transaction就足够了
BTC将Block分成Block header、Block body2部分，从而巧妙地解决了轻节点的存储及带宽问题，不得不为中本聪的一些细节设计能力点赞！
但是问题又来了，钱包应用没有Transaction的数据，要怎么验证一笔交易呢？
我们举个例子把这个问题展开：
-
张三将爷爷祖传的4星龙珠卖给李四
-
李四通过手机钱包支付给张三1个BTC
-
张三的钱包要怎么确定该笔转账交易已经Confirm了，或者说已经上链了
-
如果钱包错误的确认交易，龙珠就白送了
可能你觉得这不是一个问题，看看你手机钱包是否到账就好了呀，咱们不是常说的经过6个区块确认基本就Confirm了吗？
是的，如果这是一个全节点很容易就能验证这笔交易，但是手机端的钱包app怎么验证这个事情呢？
向其它全节点请求该区块的完整交易数据，然后构造一颗完整的Merkle Tree验证。
可以吗？
可以，但这是笨办法。
这样验证的复杂度是线性的O(n)，当这个区块只有几笔交易时没什么问题，但当有4000笔的时候这个开销就比较大了。
有没有更好的办法呢？
这个就是Merkle Tree的独到之处了，交易方只需要给接收方（轻节点）提供一个Merkle Proof即可：
-
黄底Tx 003：待验证的交易
-
绿色：Merkle proof提供的哈希值
-
蓝色：SPV本地计算的哈希值
-
紫色：该区块的根哈希
SPV是什么？
就是简易支付验证，在比特币白皮书中有介绍，绝大部分的轻钱包都通过SPV验证交易。
从图中我们可以看出，通过Merkle proof提供的几个绿色底的哈希值，就可以计算出跟Tx 003这笔交易整条路径相关的哈希，最后将计算出来的根哈希和手机钱包应用中存储的根哈希比对，即可验证Tx 003是否已经成功写入该区块。
很明显这个计算复杂度是O(log(n))，相比复杂度是线性的O(n)要高效得多。
这里留个作业，读者有兴趣可以一起交流：
由于轻节点没有Tx 004、Tx 002、C Tx等交易数据，所以自然无法验证Merkel proof提供的的几个哈希，一个作恶节点是否可以伪造Tx 003，并通过篡改H(004) 等几个绿色底的哈希值达到最终计算出来的Root hash值跟链上的Root hash值一致？
为什么？
可以结合之前的文章《BTC 学习笔记连载(3)——Hash》思考一下，如果还整不明白欢迎Twitter交流。
另外，如果提供这个验证过程的钱包应用本身就有问题，用户怎么规避？
规避不了！
如果想在币圈活得久一点，还是不要去用那些奇奇怪怪的钱包。
Mining、nonce、Proof fo non-menbership
上面的Merkle proof实际是 Proof of membership，可不可以 Proof of non-membership？也就是证明某笔Transaction不在该区块内。
当然也可以，请求整棵树一一比对就可以证明，但前面也讲过了这个负责度是O(n)，显得太笨。能不能复制 Proof of membership 的方式证明 non-membership？
思考一下
……
……
……
如果不对叶节点Transaction 按哈希进行排序，是没有办法证明的！
但恰恰BTC的共识机制并不要求对区块的Tx进行排序。
为什么？
这里涉及到一些Mining的内容（挖矿后面会单独一篇详细讲），比特币的共识协议里nonce只占4个字节，也就是说只有2^32的取值空间。
我们知道挖矿的过程就是通过不停地尝试nonce值，使得H(Block header) <= target，但是如果我们打包好一个区块，然后遍历完所有的nonce取值都没有找到这个符合难度要求的哈希值怎么办？
再思考一下？ ^^
……
……
……
遇到这种情况有矿工一般有3种办法：
-
调整Coinbase Tx的域值
还记得中本聪在创世区块里记录的那句话吗？
Chancellor on brink of second bailout for banks
就是记录在Coinbase Tx的域值里的 -
微调 timeStamp
-
调整Transaction
包括增加/删除Transaction、调整Transaction打包顺序
对这些内容的任意微调都将导致Root Hash值变化，每变化一次就又有2^32的nonce取值空间。不过第2种方式一般不建议，而在不改变Coinbase Tx的域值和Transaction的情况下，调整打包交易顺序就是最简单成本最低的方式了。
所以当然是不排序更有利，当然这个理由也并不是那么绝对，但BTC的设计之简洁巧妙真的是让我非常佩服，伟大的中本聪！
BTC的数据结构就介绍到这里。
其实还有一个非常重要的数据结构：UTXO
这是BTC的精髓，我会单独开一遍详细推敲。