BTC数据结构

简介

​ 区块链是由包含交易信息的区块从后向前有序链接起来的数据结构。它可以被存储为flat file（⼀种包含没有相对关系记录的⽂件），或是存储在⼀个简单数据库中。⽐特币核⼼客⼾端使⽤Google的LevelDB数据库存储区块链元数据。区块被从后向前有序地链接在这个链条⾥，每个区块都指向前⼀个区块。区块链经常被视为⼀个垂直的栈，第⼀个区块作为栈底的⾸区块，随后每个区块都被放置在其他区块之上。⽤栈来形象化表⽰区块依次堆叠这⼀概念后，我们便可以使⽤⼀些术语，例如：“⾼度”来表⽰区块与⾸区块之间的距离；以及“顶部”或“顶端”来表⽰最新添加的区块。

​ 对每个区块头进⾏SHA256加密哈希，可⽣成⼀个哈希值。通过这个哈希值，可以识别出区块链中的对应区块。同时，每⼀个区块都可以通过其区块头的“⽗区块哈希值”字段引⽤前⼀区块（⽗区块）。也就是说，每个区块头都包含它的⽗区块哈希值。这样把每个区块链接到各⾃⽗区块的哈希值序列就创建了⼀条⼀直可以追溯到第⼀个区块（创世区块）的链条。

​ 虽然每个区块只有⼀个⽗区块，但可以暂时拥有多个⼦区块。每个⼦区块都将同⼀区块作为其⽗区块，并且在“⽗区块哈希值”字段中具有相同的（⽗区块）哈希值。⼀个区块出现多个⼦区块的情况被称为“区块链分叉”。区块链分叉只是暂时状态，只有当多个不同区块⼏乎同时被不同的矿⼯发现时才会发⽣。最终，只有⼀个⼦区块会成为区块链的⼀部分，同时解决了“区块链分叉”的问题。尽管⼀个区块可能会有不⽌⼀个⼦区块，但每⼀区块只有⼀个⽗区块，这是因为⼀个区块只有⼀个“⽗区块哈希值”字段可以指向它的唯⼀⽗区块。

​ 由于区块头⾥⾯包含“⽗区块哈希值”字段，所以当前区块的哈希值因此也受到该字段的影响。如果⽗区块的⾝份标识发⽣变化，⼦区块的⾝份标识也会跟着变化。当⽗区块有任何改动时，⽗区块的哈希值也发⽣变化。⽗区块的哈希值发⽣改变将迫使⼦区块的“⽗区块哈希值”字段发⽣改变，从⽽⼜将导致⼦区块的哈希值发⽣改变。⽽⼦区块的哈希值发⽣改变⼜将迫使孙区块的“⽗区块哈希值”字段发⽣改变，⼜因此改变了孙区块哈希值，等等以此类推。⼀旦⼀个区块有很多代以后，这种瀑布效应将保证该区块不会被改变，除⾮强制重新计算该区块所有后续的区块。正是因为这样的重新计算需要耗费巨⼤的计算量，所以⼀个⻓区块链的存在可以让区块链的历史不可改变，这也是⽐特币安全性的⼀个关键特征。

​ 你可以把区块链想象成地质构造中的地质层或者是冰川岩芯样品。表层可能会随着季节⽽变化，甚⾄在沉积之前就被⻛吹⾛了。但是越往深处，地质层就变得越稳定。到了⼏百英尺深的地⽅，你看到的将是保存了数百万年但依然保持历史原状的岩层。在区块链⾥，最近的⼏个区块可能会由于区块链分叉所引发的重新计算⽽被修改。最新的六个区块就像⼏英⼨深的表⼟层。但是，超过这六块后，区块在区块链中的位置越深，被改变的可能性就越⼩。在100个区块以后，区块链已经⾜够稳定，这时Coinbase交易（包含新挖出的⽐特币的交易）可以被⽀付。⼏千个区块（⼀个⽉）后的区块链将变成确定的历史，永远不会改。

区块结构

​ 区块是⼀种被包含在公开账簿（区块链）⾥的聚合了交易信息的容器数据结构。它由⼀个包含元数据的区块头和紧跟其后的构成区块主体的⼀⻓串交易组成。区块头是80字节，⽽平均每个交易⾄少是250字节，⽽且平均每个区块⾄少包含超过500个交易。因此，⼀个包含所有交易的完整区块⽐区块头的1000倍还要⼤。 区块结构：

大小	字段	描述
4字节	区块大小	⽤字节表⽰的该字段之后的区块⼤⼩
80字节	区块头	组成区块头的⼏个字段
1-9 （可变整数）	交易计数器	交易的数量
可变的	交易	记录在区块⾥的交易信息

区块头

​ 区块头由三组区块元数据组成。⾸先是⼀组引⽤⽗区块哈希值的数据，这组元数据⽤于将该区块与区块链中前⼀区块相连接。第⼆组元数据，即难度、时间戳和nonce，与挖矿竞争相关，详⻅第8章。第三组元数据是merkle树根（⼀种⽤来有效地总结区块中所有交易的数据结构）。

区块头结构如下： 大小| 字段| 描述 | —- | —- |—- | 4字节| 版本 | 版本号，⽤于跟踪软件/协议的更新| 32字节 | ⽗区块哈希值 | 引⽤区块链中⽗区块的哈希值| 32字节 | Merkle根 | 该区块中交易的merkle树根的哈希值| 4字节 | 时间戳 | 该区块产⽣的近似时间（精确到秒的Unix时间戳）| 4字节| 难度⽬标 | 该区块⼯作量证明算法的难度⽬标| 4字节| Nonce | ⽤于⼯作量证明算法的计数器|

Nonce、难度⽬标和时间戳会⽤于挖矿过程

区块标识符：区块头哈希值和区块⾼度

​ 区块主标识符是它的加密哈希值，⼀个通过SHA256算法对区块头进⾏⼆次哈希计算⽽得到的数字指纹。产⽣的32字节哈希值被称为区块哈希值，但是更准确的名称是：区块头哈希值，因为只有区块头被⽤于计算。例如:000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f是第⼀个⽐特币区块的区块哈希值。区块哈希值可以唯⼀、明确地标识⼀个区块，并且任何节点通过简单地对区块头进⾏哈希计算都可以独⽴地获取该区块哈希值。

​ 请注意，区块哈希值实际上并不包含在区块的数据结构⾥，不管是该区块在⽹络上传输时，抑或是它作为区块链的⼀部分被存储在某节点的永久性存储设备上时。相反，区块哈希值是当该区块从⽹络被接收时由每个节点计算出来的。区块的哈希值可能会作为区块元数据的⼀部分被存储在⼀个独⽴的数据库表中，以便于索引和更快地从磁盘检索区块.

​ 第⼆种识别区块的⽅式是通过该区块在区块链中的位置，即“区块⾼度（block height）”。第⼀个区块，其区块⾼度为0，和之前哈希值000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f所引⽤的区块为同⼀个区块。因此，区块可以通过两种⽅式被识别：区块哈希值或者区块⾼度。每⼀个随后被存储在第⼀个区块之上的区块在区块链中都⽐前⼀区块“⾼”出⼀个位置，就像箱⼦⼀个接⼀个堆叠在其他箱⼦之上。2014年1⽉1⽇的区块⾼度⼤约是278,000，说明已经有278,000个区块被堆叠在2009年1⽉创建的第⼀个区块之上。

​ 和区块哈希值不同的是，区块⾼度并不是唯⼀的标识符。虽然⼀个单⼀的区块总是会有⼀个明确的、固定的区块⾼度，但反过来却并不成⽴，⼀个区块⾼度并不总是识别⼀个单⼀的区块。两个或两个以上的区块可能有相同的区块⾼度，在区块链⾥争夺同⼀位置。这种情况在“8.10.1 区块链分叉”⼀节中有详细讨论。区块⾼度也不是区块数据结构的⼀部分，它并不被存储在区块⾥。当节点接收来⾃⽐特币⽹络的区块时，会动态地识别该区块在区块链⾥的位置（区块⾼度）。区块⾼度也可作为元数据存储在⼀个索引数据库表中以便快速检索。

创世区块

​ 区块链⾥的第⼀个区块创建于2009年，被称为创世区块。它是区块链⾥⾯所有区块的共同祖先，这意味着你从任⼀区块，循链向后回溯，最终都将到达创世区块。

因为创世区块被编⼊到⽐特币客⼾端软件⾥，所以每⼀个节点都始于⾄少包含⼀个区块的区块链，这能确保创世区块不会被改变。每⼀个节点都“知道”创世区块的哈希值、结构、被创建的时间和⾥⾯的⼀个交易。因此，每个节点都把该区块作为区块链的⾸区块，从⽽构建了⼀个安全的、可信的区块链的根。

在chainparams.cpp⾥可以看到创世区块被编⼊到⽐特币核⼼客⼾端⾥。 创世区块的哈希值为：

000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f

​ 你可以在任何区块浏览⽹站搜索这个区块哈希值，如blockchain.info，你会发现⼀个⽤包含这个哈希值的链接来描述这⼀区块内容的⻚⾯： https://www.blockchain.com/btc/block/000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f ​ 在命令⾏使⽤⽐特币核⼼客⼾端：

$ bitcoind getblock 000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f

{
"hash":"000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f",
"confirmations":308321,
"size":285,
"height":0,
"version":1,
"merkleroot":"4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33b",
"tx":["4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33b"],
"time":1231006505,
"nonce":2083236893,
"bits":"1d00ffff",
"difficulty":1.00000000,
"nextblockhash":"00000000839a8e6886ab5951d76f411475428afc90947ee320161bbf18eb6048"
}

​ 创世区块包含⼀个隐藏的信息。在其Coinbase交易的输⼊中包含这样⼀句话The Times 03/Jan/2009 Chancellor on brinkof second bailout forbanks.这句话是泰晤⼠报当天的头版⽂章标题，引⽤这句话，既是对该区块产⽣时间的说明，也可视为半开玩笑地提醒⼈们⼀个独⽴的货币制度的重要性，同时告诉⼈们随着⽐特币的发展，⼀场前所未有的世界性货币⾰命将要发⽣。该消息是由⽐特币的创⽴者中本聪嵌⼊创世区块中。

区块的连接

​ ⽐特币的完整节点保存了区块链从创世区块起的⼀个本地副本。随着新的区块的产⽣，该区块链的本地副本会不断地更新⽤于扩展这个链条。当⼀个节点从⽹络接收传⼊的区块时，它会验证这些区块，然后链接到现有的区块链上。为建⽴⼀个连接，⼀个节点将检查传⼊的区块头并寻找该区块的“⽗区块哈希值”。 ​ 让我们假设，例如，⼀个节点在区块链的本地副本中有277,314个区块。该节点知道最后⼀个区块为第277,314个区块，这个区块的区块头哈希值为： 00000000000000027e7ba6fe7bad39faf3b5a83daed765f05f7d1b71a1632249。 然后该⽐特币节点从⽹络上接收到⼀个新的区块，该区块描述如下：

{
"size":43560,
"version":2,
"previousblockhash":"00000000000000027e7ba6fe7bad39faf3b5a83daed765f05f7d1b71a1632249",
"merkleroot":"5e049f4030e0ab2debb92378f53c0a6e09548aea083f3ab25e1d94ea1155e29d",
"time":1388185038,
"difficulty":1180923195.25802612,
"nonce":4215469401,
"tx":["257e7497fb8bc68421eb2c7b699dbab234831600e7352f0d9e6522c7cf3f6c77",
//#[...many more transactions omitted...]
"05cfd38f6ae6aa83674cc99e4d75a1458c165b7ab84725eda41d018a09176634"
]
}

​ 对于这⼀新的区块，节点会在“⽗区块哈希值”字段⾥找出包含它的⽗区块的哈希值。这是节点已知的哈希值，也就是第277314块区块的哈希值。故这个区块是这个链条⾥的最后⼀个区块的⼦区块，因此现有的区块链得以扩展。节点将新的区块添加⾄链条的尾端，使区块链变⻓到⼀个新的⾼度277,315。 显⽰了通过“⽗区块哈希值”字段进⾏连接三个区块的链。

​ 区块通过引⽤⽗区块的区块头哈希值的⽅式，以链条的形式进⾏相连:

Merkle树

​ 区块链中的每个区块都包含了产⽣于该区块的所有交易，且以Merkle树表⽰。

​ Merkle树是⼀种哈希⼆叉树，它是⼀种⽤作快速归纳和校验⼤规模数据完整性的数据结构。这种⼆叉树包含加密哈希值。术 语“树”在计算机学科中常被⽤来描述⼀种具有分⽀的数据结构，但是树常常被倒置显⽰，“根”在图的上部同时“叶⼦”在图的下 部，

​ 在⽐特币⽹络中，Merkle树被⽤来归纳⼀个区块中的所有交易，同时⽣成整个交易集合的数字指纹，且提供了⼀种校验区块 是否存在某交易的⾼效途径。⽣成⼀棵完整的Merkle树需要递归地对哈希节点对进⾏哈希，并将新⽣成的哈希节点插⼊到 Merkle树中，直到只剩⼀个哈希节点，该节点就是Merkle树的根。在⽐特币的Merkle树中两次使⽤到了SHA256算法，因此 其加密哈希算法也被称为double-SHA256。

​ 当N个数据元素经过加密后插⼊Merkle树时，你⾄多计算2*log2(N)次就能检查出任意某数据元素是否在该树中，这使得该数 据结构⾮常⾼效。

​ Merkle树是⾃底向上构建的。在如下的例⼦中，我们从A、B、C、D四个构成Merkle树树叶的交易开始，如图。起始时所 有的交易都还未存储在Merkle树中，⽽是先将数据哈希化，然后将哈希值存储⾄相应的叶⼦节点。这些叶⼦节点分别是 HA、HB、HC和HD：

H~A~ = SHA256(SHA256(交易A))

​ 通过串联相邻叶⼦节点的哈希值然后哈希之，这对叶⼦节点随后被归纳为⽗节点。 例如，为了创建⽗节点HAB，⼦节点A和 ⼦节点B的两个32字节的哈希值将被串联成64字节的字符串。随后将字符串进⾏两次哈希来产⽣⽗节点的哈希值:

H~AB~=SHA256(SHA256(H~A~ + H~B~))

​ 继续类似的操作直到只剩下顶部的⼀个节点，即Merkle根。产⽣的32字节哈希值存储在区块头，同时归纳了四个交易的所有 数据。

​ 因为Merkle树是⼆叉树，所以它需要偶数个叶⼦节点。如果仅有奇数个交易需要归纳，那最后的交易就会被复制⼀份以构成 偶数个叶⼦节点，这种偶数个叶⼦节点的树也被称为平衡树。如图所⽰，C节点被复制了⼀份。

​ 由四个交易构造Merkle树的⽅法同样适⽤于从任意交易数量构造Merkle树。在⽐特币中，在单个区块中有成百上千的交易是 ⾮常普遍的，这些交易都会采⽤同样的⽅法归纳起来，产⽣⼀个仅仅32字节的数据作为Merkle根。下图，你会看⻅⼀ 个从16个交易形成的树。需要注意的是，尽管图中的根看起来⽐所有叶⼦节点都⼤，但实际上它们都是32字节的相同⼤⼩。 ⽆论区块中有⼀个交易或者有⼗万个交易，Merkle根总会把所有交易归纳为32字节。

​ 为了证明区块中存在某个特定的交易，⼀个节点只需要计算log2(N)个32字节的哈希值，形成⼀条从特定交易到树根的认证路径或者Merkle路径即可。随着交易数量的急剧增加，这样的计算量就显得异常重要，因为相对于交易数量的增⻓，以基底为 2的交易数量的对数的增⻓会缓慢许多。这使得⽐特币节点能够⾼效地产⽣⼀条10或者12个哈希值（320-384字节）的路 径，来证明了在⼀个巨量字节⼤⼩的区块中上千交易中的某笔交易的存在。

​ 下图中，⼀个节点能够通过⽣成⼀条仅有4个32字节哈希值⻓度（总128字节）的Merkle路径，来证明区块中存在⼀笔交 易K。该路径有4个哈希值（在图7-5中由蓝⾊标注）HL、HIJ、HMNOP和HABCDEFGH。由这4个哈希值产⽣的认证路径， 再通过计算另外四对哈希值HKL、HIJKL、HIJKLMNOP和Merkle树根（在图中由虚线标注），任何节点都能证明HK（在图 中由绿⾊标注）包含在Merkle根中。

​ 构建merkle树：

#include <bitcoin/bitcoin.hpp>
bc::hash_digest create_merkle(bc::hash_digest_list& merkle)
{
// Stop if hash list is empty.
if (merkle.empty())
return bc::null_hash;
else if (merkle.size() == 1)
return merkle[0];
// While there is more than 1 hash in the list, keep looping…
while (merkle.size() > 1)
{
// If number of hashes is odd, duplicate last hash in the list.
if (merkle.size() % 2 != 0)
merkle.push_back(merkle.back());
// List size is now even.
assert(merkle.size() % 2 == 0);
// New hash list.
bc::hash_digest_list new_merkle;
// Loop through hashes 2 at a time.
for (auto it = merkle.begin(); it != merkle.end(); it += 2)
{
// Join both current hashes together (concatenate).
bc::data_chunk concat_data(bc::hash_size * 2);
auto concat = bc::make_serializer(concat_data.begin());
concat.write_hash(*it);
concat.write_hash(*(it + 1));
assert(concat.iterator() == concat_data.end());
// Hash both of the hashes.
bc::hash_digest new_root = bc::bitcoin_hash(concat_data);
// Add this to the new list.
new_merkle.push_back(new_root);
}
// This is the new list.
merkle = new_merkle;
// DEBUG output -------------------------------------
std::cout << "Current merkle hash list:" << std::endl;
for (const auto& hash: merkle)
std::cout << " " << bc::encode_hex(hash) << std::endl;
std::cout << std::endl;
// --------------------------------------------------
}
// Finally we end up with a single item.
return merkle[0];
}
int main()
{
// Replace these hashes with ones from a block to reproduce the same merkle root.
bc::hash_digest_list tx_hashes{
{
bc::decode_hash("0000000000000000000000000000000000000000000000000000000000000000"),
bc::decode_hash("0000000000000000000000000000000000000000000000000000000000000011"),
bc::decode_hash("0000000000000000000000000000000000000000000000000000000000000022"),
}
};
const bc::hash_digest merkle_root = create_merkle(tx_hashes);
std::cout << "Result: " << bc::encode_hex(merkle_root) << std::endl;
return 0;
}

​ 编译以及运⾏构造Merkle树代码:

$ # Compile the merkle.cpp code
$ g++ -o merkle merkle.cpp $(pkg-config --cflags --libs libbitcoin)
$ # Run the merkle executable
$ ./merkle
Current merkle hash list:
32650049a0418e4380db0af81788635d8b65424d397170b8499cdc28c4d27006
30861db96905c8dc8b99398ca1cd5bd5b84ac3264a4e1b3e65afa1bcee7540c4
Current merkle hash list:
d47780c084bad3830bcdaf6eace035e4c6cbf646d103795d22104fb105014ba3
Result: d47780c084bad3830bcdaf6eace035e4c6cbf646d103795d22104fb105014ba3

Merkle树的效率

交易数量	区块的近似⼤⼩	路径⼤⼩（哈希数量）	路径⼤⼩（字节）
16笔交易	4KB	4个哈希	128字节
512笔交易	128KB	9个哈希	288字节
2048笔交易	512KB	11个哈希	352字节
65535	16MB	16个哈希	512字节

​ 依表可得，当区块⼤⼩由16笔交易（4KB）急剧增加⾄65,535笔交易（16MB）时，为证明交易存在的Merkle路径⻓度增⻓极其缓慢，仅仅从128字节到512字节。有了Merkle树，⼀个节点能够仅下载区块头（80字节/区块），然后通过从⼀个满节 点回溯⼀条⼩的Merkle路径就能认证⼀笔交易的存在，⽽不需要存储或者传输⼤量区块链中⼤多数内容，这些内容可能有⼏ 个G的⼤⼩。这种不需要维护⼀条完整的区块链的节点，⼜被称作简单⽀付验证（SPV）节点，它不需要下载整个区块⽽通 过Merkle路径去验证交易的存在。

Merkle树和简单⽀付验证

​ Merkle树被SPV节点⼴泛使⽤。SPV节点不保存所有交易也不会下载整个区块，仅仅保存区块头。它们使⽤认证路径或者 Merkle路径来验证交易存在于区块中，⽽不必下载区块中所有交易。

​ 例如，⼀个SPV节点欲知它钱包中某个⽐特币地址即将到达的⽀付，该节点会在节点间的通信链接上建⽴起bloom过滤器， 限制只接受含有⽬标⽐特币地址的交易。当节点探测到某交易符合bloom过滤器，它将以Merkleblock消息的形式发送该区 块。Merkleblock消息包含区块头和⼀条连接⽬标交易与Merkle根的Merkle路径。SPV节点能够使⽤该路径找到与该交易相 关的区块，进⽽验证对应区块中该交易的有⽆。SPV节点同时也使⽤区块头去关联区块和区块链中的区域区块。这两种关联，交易与区块、区块和区块链，证明交易存在于区块链。简⽽⾔之，SPV节点会收到少于1KB的有关区块头和Merkle路径 的数据，其数据量⽐⼀个完整的区块（⽬前⼤约有1MB）少了⼀千倍有余。

• 区块链
• blockchain
• btc