比特币(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。

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

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

  • 发表于:
  • 原文链接:https://kuaibao.qq.com/s/20180611G0YATB00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区