比特币（3）：密码技术和 PoW 算法

在这个系列的第三篇博文中，我们科普一下比特币系统使用的密码技术（Cryptography)：

哈希 （Hash)

非对称密钥的签名 （Asymmetric Key Signing)

电子签名，是消息产生方附加到消息上的一段字符串。它的目的是客观地确认消息是由某个产生方产生的。

Message :=

消息中的电子签名 signature 能够用来确认 消息 确实是由 消息中的 senderId 所生成的。（注： payload 包括消息的内容及其它数据）。

(上图来自： https://sachi73blog.wordpress.com/2013/11/21/x509-certificate-asymmetric-encryption-and-digital-signatures/）

比特币交易使用了 非对称密钥的签名 （Asymmetric Key Signing) -- 每个比特币账号都有至少一对 非对称密钥 （public key, private key), 其中公钥是公开的，而私钥由账号所有人秘密保存。 账号（付款方）发出比特币的交易的时候，用私钥对交易签名 sign(transaction, sender.priv_key), 把签名附在交易记录中。提交交易就是把交易记录广播给所有的采矿节点 （nodes）。这些节点使用付款账户的公钥来验签 verify(transaction, sender.pub_key)，从而确定交易确实是由其付款方提交的。Asymmetric Key 算法的核心在于数学上保证了用 对外公布的 公钥 很难（在现有硬件计算能力下无法）推导出 私钥，尽管公钥可以用来验证 用私钥对消息的签名。

Hash 可以简单理解为把 任意长度的二进制序列 映射成为 定长二进制序列的函数。很多 Hash 算法都是基于复杂的二进制操作（比如AND, OR， XOR等）来实现。

下面我们简单介绍一下 比特币的区块链的结构，以及“采矿”过程 -- 交易是怎样加入区块链的。

我们曾经提到的 比特币交易链 （区块链）的实现方式实际是一个交易块（block）的链（chain）。每个交易块包含多个交易记录（组织成一个 Merkle Tree 结构）。Merkle Tree 可以简单理解为把多个交易记录逐层 hash 到根节点。每个 block 包括:

交易记录的 Merkle Tree

Timestamp: 生成 Block 的时间

Nonce：一个整数，它确保整个 block 的 SHA256 hash 满足某个给点的条件（比如 hash 值的前几位是 0）。

Previous Hash: 前一个 block 的 hash 值

block_hash_value = hash(block.prev_hash, block.nounce, block.merkle_root_hash, block.timestamp)。

所谓 ”采矿“ 就是要寻找一个 Nonce , 使得当前 block 的 hash 值满足某个条件，比如前 X 位为零。理论上没有比 逐个尝试不同的32位整数 更快的办法来找到符合条件的 Nonce。所以 “采矿”的 PoW 就是不断计算 Hash，直到找到符合条件的 Nonce 为止。

每个比特币交易都会广播给全部 采矿节点 Node (这里我们只考虑 Full Node -- 节点上保存了完整的 Blockchain，也就是有全部的交易记录）。Node 收集到一定数量的交易记录后，会生成一个 Block，然后把 这个 Block 广播给其它节点。Node 的逻辑简单描述是这样：

收到交易记录后，验证该交易记录：首先验证签名，然后确认付款方确实有足够比特币来支付 (Node 有全部的交易记录，因此可以维护所有账号存量）。

基于当前的区块链的最后一个 block 的 hash，和收集到的一组交易记录来生成下一个 block，然后把它广播给其它节点。

收到其它 Node 发来的 block。首先验证block中的每一个交易记录（如 1）。通过后把它附加到它所对应的上一个 block。在这一步中，Node 可能需要维护多个版本的 Blockchain，因为可能会收到多个不同的 block 来附加到当前的 blockchain。Node 选择其中最长的 Blockchain 来生成下一个 block。

在这个算法中，“采矿” 实际上就是多个 Node 间 hash 计算的竞赛，看谁能最快地找到 Nonce， 从而最快地完成下一个 block，附加入 blockchain，从而得到比特币的奖励。算法保证了各个节点保存的 blockchain 趋于一致。

比特币所用到的产生 blockchain 的算法, 在理论上确保了对 "全部历史交易记录及其顺序 （交易链）“ 的分布式的　PBFT 共识 （Practical Byzantine Fault Tolerant Consensus)。对这一算法的攻击需要超过系统全部 PoW 算力 50% 的资源 （整个系统的 PoW 算力可以用 Hash Rate 描述 -- 单位时间内 SHA256 Hash 计算的完成次数）。

下面是描述如何在 51% 攻击中实现 ”重复支付“：

为描述简单起见，我们假设骇客短时间控制了一台超级计算机，它的 hash rate 超过了现在整个比特币系统的 hash rate。现在这个超级计算机加入 比特币系统成为一个 Node （攻击节点）。攻击节点从其它节点下载现有的区块链。骇客账户只有 1 BTC。他首先提交一个合法的交易 -- 用 1 BTC 换取了 8000 美元。然后提交一个非法交易，比如支付 1BTC 给骇客的其它账户。合法交易被接受进区块链，而非法交易因为账户余额不足被拒绝。合法交易完全确认后 （含该交易记录的 block 已经加入到区块链中，并有两个新的block附加于其后），美元完成交割。攻击节点马上开始找到包含那个交易的 block，把该合法交易替换成那个非法交易，攻击节点需要重新计算该 block，和全部的后续block。并且把这些重新计算的 block 广播给其它节点。由于攻击节点拥有系统超过 50% PoW 算力，攻击节点生成 block 的速度可以超过其它节点总和，于是逐步会生成当前最长的 blockchain。从而其它节点不得不采用这些 block。最后的效果是 该非法交易被加入到 blockchain，而原来确认的合法交易被踢出 blockchain。

实际操作中应该是多个攻击节点来合作，这样描述会复杂一些，但是基本流程不变。

骇客可以从自己的账户重复支付，但是并不能修改或取消来自其它账户的交易记录。为什么呢？当然和前述的 密码技术 有关。就作为一道思考题留给读者吧。