从数据结构的角度上看区块链到底是什么
关于我
一个有思想的程序猿，终身学习实践者，目前在一个创业团队任team lead，技术栈涉及Android、Python、Java和Go，这个也是我们团队的主要技术栈。
Github：https://github.com/hylinux1024
微信公众号：终身开发者(angrycode)
自从最近央视提出要发展自主区块链技术的号召以来，区块链领域又骚动了起来。程序猿是学习能力很强的群体，了解新技术是日常工作生活的一部分。作为一个从事区块链相关产品创业的从业者，今天就以数据结构的角度来看看区块链(Blockchain)技术。个人水平有限，如有错误的地方，欢迎留言拍砖。
区块链Blockchain
首先看看百度百科给的定义
区块链是分布式数据存储、点对点传输、共识机制、加密算法等计算机技术的新型应用模式。区块链（Blockchain），是比特币的一个重要概念，它本质上是一个去中心化的数据库，同时作为比特币的底层技术，是一串使用密码学方法相关联产生的数据块，每一个数据块中包含了一批次比特币网络交易的信息，用于验证其信息的有效性（防伪）和生成下一个区块。
乍一看这个定义还是比较学术性的，对于刚接触区块链的人来说，依然很难理解区块链到底是什么样子的。不过我们可以从中看出几个关键词分布式、点对点、加密、共识等等。
它有以下几个特点：
- 区块链中的数据是分布式的存储于各个节点
- 不需要中心服务器，而通过点对点的进行数据传输
- 通过加密、共识算法保证数据的完整性和安全性
这么说区块链是一个分布式、点对点传输的数据存储技术，那么这个数据库到底长什么样子呢？
我觉得从区块链(Blockchain)字面上看可以从两个词区块(block)和链(chain)来理解：
逻辑上它是一个链式(chain)结构，每个结点上就是一个区块信息(block)，区块里面则存储了交易的信息。
上图所示为区块高度为4的区块链
可以看出，这个结构跟链表很相似，只不过最新的一个区块是通过包含了前一个区块的哈希值来体现这种链的关系的。
接下来我们看看这些区块的具体结构，以及如何保证区块数据的安全性的。
区块结构Block
区块数据结构主要包括为区块头和区块体两部分。其中区块头包含父区块哈希值、merkle根、难度目标和nonce值等信息；而区块体则包含了交易哈希列表。
区块头
区块的哈希值是通过区块头中的信息进行计算的。这个哈希值是区块的标识符，可以通过这个哈希值找到对应的区块（当然也可以通过区块高度来查询，但区块分叉时，区块高度有可能会对应多个区块）。
我们知道当前区块中包含来前一个区块的哈希值，但自己本区块的哈希值是不存储当前区块结构中的，而是由节点接收到区块信息后计算出来，然后存储在一个独立的索引数据库中的，这样可以方便检索。
Merkle根
要理解Merkle根，就要先了解Merkle树。Merkle树是一种哈希二叉树。
由于在一个区块里面包含很多交易信息（以哈希值来表示），这些交易信息就是通过Merkle树进行表示的。
那么要怎么得到这颗树的呢？Merkle树是自底向上构建的。假设区块中有A、B、C、D 4个交易信息，那么将这个4个交易信息分别哈希之后，构成Merkle树的叶子节点。
# TxA 表示A交易信息（其它类似）
# 计算出A交易的哈希值HA后
# 把其当作Merkle树的叶子节点
HA = hash(TxA)
HB = hash(TxB)
HC = hash(TxC)
HD = hash(TxD)A节点的哈希与B结点的哈希又组成了它们父节点的哈希值HAB
# A节点与B节点又组成了它们父节点的哈希`HAB`
HAB = hash(HA+HB)
HCD = hash(HC+HB)最后HAB节点与HCD节点又组成了根结点的哈希HABCD
HABCD=hash(HAB+HCD)而HABCD就是Merkle根，它归纳总结了所有的交易信息。
通过上面计算就可以得到一颗Merkle树了。
有人可能要问了，这是二叉树，如果区块中的交易个数为奇数，那么如何计算呢？那就将最后一个交易复制一份然后就可以组成满二叉树了。
这个Merkle树有什么用呢？
首先要知道在一个区块里面是包含了成百上千个交易的，而通过Merkle树就可以将这些交易信息归纳成一个哈希值（即Merkle根），而且在区块头中存储这个Merkle根需要的空间非常小，只需要32个字节。
另外节点可以利用这个Merkle树快速的验证一笔交易是否在这个区块中。
这个过程是这样的：
只要能在这颗树上找到一个叶子节点到Merkle根的路径，就能证明这笔交易存在这个区块中。
结合下图来理解
如果一个节点要验证HK是否在包含在该区块中，只需要生成一个HL-HIJ-HMNOP-HABCDEFGH的路径（图中蓝色节点），这样HK可以跟HL可以生成HKL，类似得，HIJKL、HIJKLMNOP、HABCDEFGHIJKLMNOP（图中虚线节点）也可以通过验证路径进行计算，最后得到Merkle根，这样就可以对交易进行验证了。
假设一个区块里面有n笔交易，那么这颗树的高度就是log(n)+1。对于有成百上千个交易来说这个验证路径是非常高效的。
由于区块链的数据是点对点传输的，这个验证可以使节点在传输区块头以及一条验证路径信息后，就可以对区块中的交易进行验证，而不用下载整个区块数据，达到快速验证的效果。
最后由于一个区块是包含了上一个区块的哈希值，那么如果有节点对区块中的交易信息进行了篡改，这个区块若要得到其它节点的认可（即共识），就要维持这个链式结构，即该区块的后续区块信息也需要篡改（因为区块内容变动了，导致区块的哈希值也变化了）。
篡改后的区块要被大多数节点接受，理论上就需要控制51%的节点。对于存在大多数诚实节点网络来说，这几乎是很难做到的。而且一个区块有越多的后续区块，它被篡改的可能性就越小。因为需要篡改的区块越多，需要控制的节点算力就越大。
总结一下Merkle树的作用
- 归纳交易信息，节省空间
- 快速验证交易
- 保证数据安全
nonce
一个交易被发送到区块链网络中，需要被打包成一个区块，然后把区块发送到网络中，被共识后，存储于链上，这个交易就算完成了。
怎么打包区块信息呢？
这就需要寻找nonce值了。nonce是一个随机数，但这个随机数不是随便给的，节点需要不停地寻找一个合适的随机数，使得这个区块的哈希值少于难度目标值。只要有节点寻找到了一个合适的nonce，就完成了一次挖矿，它就构建一个完整合法的区块，然后广播到点对点的网络中。只要其它节点认可（即共识）了这个区块，那么完成挖矿的节点就能得到挖矿奖励。这个也是鼓励节点参与到挖矿中，维护区块链的安全。
参与挖矿的节点就是矿工。
寻找nonce比拼的就是节点计算机的算力。谁的算力高找到nonce的速度就快。
难度目标值是区块链网络中为了调节挖矿难度而设置的，保证挖矿的速度在10分钟左右。每生成2016个区块后就重新计算一次难度目标。
新的目标难度值=旧目标难度值*(前2016个区块生成的实际耗时分钟/20160分钟)这个挖矿算法就是PoW(Proof of Work)，即工作量证明。这个过程非常消耗CPU（GPU），也非常耗电。所以目前也出现了很多其它的共识算法。
总结
区块链是一个分布式的、点对点传输的数据存储技术，它的数据结构可以简单的分为区块头和区块体。
区块头中有使用前一个区块的哈希来维持链式结构，使用merkle根来归纳区块中的交易信息，同时节点可以使用merkle树进行快速验证交易。nonce和难度目标值是在打包区块时矿工进行挖矿的。矿工一旦找到一个合适的nonce，就能得到挖矿奖励。
区块体则主要是包含了成百上千的交易信息。一个交易被发送到区块链网络中后，就会被打包到区块中。