资料篇:共识与工作量证明

共识是区块链系统的核心灵魂。它决定弱信任环境下大家如何达成信任。

目前,以太坊共识是基于工作量证明的机制(Proof of Work, PoW)。

一个好的共识机制能够鼓励正直的矿工记账出块,防止双花攻击的发生,也能够在分布式节点网络中协调所有的节点在短时间内同步区块,承认区块账本的有效性。

分布式系统的问题就在于如何协调各个节点步调一致、共同进退。这称之为“拜占庭将军问题”。

Note

拜占庭将军问题,即为拜占庭将军率领一支军队围困一个城市, 他们要选择进攻还是撤退。如果不能达成共识,部分将军带军进攻而部分选择按兵不动,则会造成极大损失。 因此各位将军都通过派送信使到达其他将军营地的方式来沟通。每位将军得到信使来信后都会根据自己选择与来信信息判断是否执行进攻/撤退命令。 但某些反叛的将军可能发送欺骗性的投票结果,造成整个大部队的损失。 如何甄别真假消息以及统一将军间的共识,称为拜占庭将军问题。

比特币的PoW机制(简单版)

“拜占庭将军问题”映射到比特币网络中,每台网络计算机都是“将军”,连接计算机的网络即为“信使”。在网络中的每个节点都有可能发出欺骗性的区块(假账本),这些区块能否进入区块链?是否被其他各个节点认同?为了排除错误取得网络共识, 比特币网络规定了如下实用准则:

  1. 单一区块所包含的交易集合在执行哈希后的 256bits (32字节) 的哈希值必须是一个特殊数值,它的开头必须满足一定数量的 0000... 作为起始。
  2. 区块串联形成区块链,每个链条环节(称为高度)有且仅有一个区块。
  3. 一旦找到符合条件的区块,立即广播,该区块进入该高度的候选区。候选区内可以包含多个候选者。
  4. 可以从任一候选者基础上,往后计算新区块。
  5. 最高的链才是最终的区块链账本,其他较短的分支链条都不被承认,优胜劣汰。

这几条规定相辅相成,解决了甄别真假消息和统一共识的难题。它通过牺牲巨大电力和交易速度,保障了共识与安全性。 具体分析如下:

第 1 条规定 即为PoW:矿工需要反复排列组合,选取合适的交易加入区块进行 SHA-256 哈希试算计算哈希值,直到符合开头 0 数量多寡的规定。例如比特币区块链上高度为 #286819 的合法区块的哈希值 (开头有16个 0):

0000000000000000e067a478024addfecdc93628978aa52d91fabd4292982a50

Note

哈希函数的特性是输入任意长的字符串,该函数都能将其映射为固定长度的散列值,例如比特币选取的 SHA3-256 函数即为第三代散列函数,输出定长为 256 位(256bits)。

哈希函数满足以下特性:

  1. 碰撞不易:不同的输入值,产生不同的输出值,微小的输入改动也会引起输出的巨大变化。
  2. 单向性:给定输入值,可快速计算输出值;给出输出值,却无法推断输入值。
  3. 穷举性:若要输出值介于某范围,没有比穷举输入更好的尝试方法。

在区块链的领域中,利用哈希函数对不同的输入产生的输出迥异,且无法通过规律预测的特性,来保障矿工确实花费了大量资源来进行计算。矿工无法投机取巧来猜测,只能通过耗费 CPU 算力与电力的方式反复排列输入参数来尝试。 此称为 工作量证明 (PoW,Proof of Work)。

比特币算力的中心化问题

比特币网络规定每个区块头的哈希值必须符合一定数量的 000...,这就给找到符合条件的区块制造了难度。 但这个难度并非一成不变,输出结果的开头 0 数量的要求会随着全球全网算力而动态调整。 每隔 2016 个块根据全网算力提升或下降自动动态调整难度,调整周期大约为 2周。 动态调整的结果是控制这个计算难度维持在 10 分钟左右出一个块 。

正因为有 PoW 机制的存在,转账是缓慢的,无法和支付宝等互联网支付工具实时性到账相媲美。

两者在中心化模式和分布式模式、在效率与公开透明上是各有取舍的。

中心化的模式 的假设前提是“信任”。需要各个使用者相信中央节点的可靠与权威(例如相信支付宝系统的诚实可靠、权威),换来的优势就是近乎瞬间的转账效率。

分布式系统 的假设前提是“互不信任”。则需要在协调各节点达成共识后才能完成转账,这是需要付出昂贵的时间代价的,换来的优势就是账本的可靠性较高且没有中心化风险。

../_images/Picture22.png

中心化支付系统,与去中心化支付系统的拓扑结构

比特币的共识机制被证明是单纯依赖高性能 CPU 就可提升算力。 各个参与的玩家都在千方百计提升自己在全网算力中所占的比例, 有 n% 的算力占有率就有 n% 的概率挖到合法区块。 为了提升算力来获得更大的概率,市场中有层出不穷的高性能比特币专用 ASIC 芯片矿机, 它们的出现让算力集中于买得起矿机的高端玩家手中,而设备制造也被少数高端矿机生产厂商所垄断, ASIC 矿机的出现让普通的家庭计算机一夜之间被淘汰出局,数十年也挖不到一个比特币。

这违背了中本聪设计网络时的初衷:“人人参与,家庭计算机就可挖矿”。目前还没有很好的解决方案。

以太坊的Pow/Pos机制

以太坊在前三个阶段采用 PoW 的共识机制 ,核心是自以太坊1.0起推出的 Ethash 算法 [1] (代码赏析见 ETHASH 挖矿算法)。

为了克服比特币的算力中心化问题,Ethash算法做了诸多调整。

该算法依赖一个预先生成的大型数据集(1GB),在计算的过程中需要反复、分片地读取该数据集,这部分数据集体积远超过ASIC/GPU/FPGA矿机的内部寄存器体积, 较慢的内存读写 I/O 操作时间抵消了 ASIC 矿机厂商的专用芯片集成化带来的计算时间优势,具体的算法规则如下。

  • 每一个区块通过区块头计算一个种子,该种子仅与本区块有关。
  • 基于种子生成一份16MB 的伪随机缓存
  • 基于缓存生成一份大型数据集,称为DAG(有向无环图),体积 1 GB。DAG的数据可由伪随机缓存快速地推导出来,而且 DAG 的数据分块,每块都和对应的缓存块有关。
  • 矿工挖矿的过程是不断地从 DAG 中取出数据作为输入值,再配合反复更改 nonce 试探,达到满足一定难度的输出值的运算。
  • 校验者仅需在得到输出值后,经由缓存推断出对应的DAG数据,代入计算验证输出值,轻客户端也能快速执行该任务。
  • 和比特币一样,Ethash 是一个”挖矿难,检测易”的算法。

Note

该算法的理想是:虽然普通家庭计算机的 CPU 无法和和专用的 ASIC 矿机媲美,但是专用矿机在 1GB 内存数据的读取上也没有巨大的优势。

Ethash 算法实现了部分普通计算机参与挖矿、算力去中心化的理想。但是近来有通过GPU显卡来进行高内存高算力运算的显卡矿机,也有矿机厂商研制出的 ASIC 矿机在慢慢侵蚀 Ethash算法的屏障作用。所以以太坊的共识算法将在不久将来的第四阶段切换到 PoS 模式。

第四阶段的以太坊经济模型采用PoS机制 ,PoS全称 Proof of Stake,任何持有以太币的参与者都可以发起特殊交易,将自己的币锁定在一个存储中,让自己获得打包交易的资格,然后通过一个当前验证者都能参与的共识算法,完成新区块的打包和广播。PoS 算法的特点如下。

  • 不需要耗费大量电力资源来“挖矿”。理论上发行总量可以被控制。
  • 不需要购买昂贵设备,持有以太币即可参与挖矿。
  • 出块速度更快,不受制于PoW挖矿带来的时间延迟。
  • 减少挖矿工具中心化带来的风险。

预计当第四阶段启动时,众多以太坊爱好者已经进入以太坊世界并持有了以太币,他们可以根据自己持币数量和挖矿规则,竞争上岗,打包区块数据进行挖矿。目前已经有了代号 Casper 的测试网络可以运行、试用该共识机制。Casper 网上的共识算法有惩戒措施,出块人取得资格需要质押一定数量的以太币,大家根据共识对新产出的块进行投票来判定该块是否有效,经过大部分人认可后,该块就能合法有效,但若在该过程中有少数人“作恶”被揪出,这些人就会被罚没所抵押的以太币以示惩戒。

[1]Ethereum Community Authors (2018) ‘Ethash’, The Ethereum Wiki, Available at: https://github.com/ethereum/wiki/wiki/Ethash