Skip to content

Latest commit

 

History

History
181 lines (121 loc) · 17.1 KB

7_2.md

File metadata and controls

181 lines (121 loc) · 17.1 KB
Raw

以太坊共识

区块链鼻祖比特币采用Pow共识，到目前为止已经稳定运行了十余年。但在2011年开始，因为比特币有利可图，在市场的驱动下出现了专业矿机（ASIC）专门针对哈希算法、散热、耗能进行优化以此来提高挖矿的投入产出比，这脱离了比特币one cpu on vote的原则。将造成比特币节点中心化和增加面临51%攻击的风险，因此当以太坊也采用Pow共识算法的时候就需要针对这些问题改进Pow算法本身。

在以太坊早期起草的共识算法是 Dagger-Hashimoto2， 但被证明 Dagger很容易受到 Sergio Lerner 共享内存硬件加速的影响。 所以最终抛弃了 Dagger-Hashimoto。 在对 Dagger-Hashimoto 进行大量修改后，终于形成了新算法：Ethash。

Dagger

Dagger算法由Vitalik Buterin发明，旨在通过DAG（有向无环图）来同时获得“memory-hard计算”和“memory-easy验证”这两个特性，其主要原理是每个Nonce的生成需要大量数据的一小部分，而每次为生成Nonce重新计算大量数据的代价又十分高昂，因此不得不将其存储避免重复生成。但是对于验证Nonce的有效性却不用生成大量的数据。但是，Sergio Lerner证明Dagger容易受到共享内存硬件加速的影响，因此Dagger并不是一个可靠的算法。

Hashimoto

Hashimoto算法由Thaddeus Dryja发明，通过增加对内存读取瓶颈来抵制ASIC矿机。从理论上讲，内存本质上比计算本质上具有更多的通用性，并且数十亿美元的研究已经针对不同的用例进行了优化，这些用例通常涉及近乎随机的访问模式（因此称为“随机访问存储器”）。因此，现有RAM可能会适度接近最佳值，如果要对内存读取进行专门优化来获得挖矿时更高的性价比是一件极为困难的事。

Dagger-Hashimoto

在以太坊早期起草的共识算法是Dagger-Hashimoto，Dagger-Hashimoto算法由Dagger和Hashimoto融合而成，后来对其又进行了大量修改，最后形成了明显不同于 Dagger-Hashimoto的新算法Ethash。采用Ethash算法是想要达到如下目标；

  • 对抗ASIC专业矿机，避免算力集中化；
  • 支持轻客户端，对硬件性能比较差的轻节点也能进行SPV验证；
  • 全链存储数据；

Ethash

Ethash算法的总体思路是这样的，轻节点因为硬件设备和节点特性，存在计算能力不足，内存小的特点，而矿工因为挖矿需要计算大量哈希，甚至是专业设计的ASIC矿机，具有计算能力强，内存大的特点，为了对抗ASIC矿机就需要在挖矿时增加内存消耗，而验证时只需要很小的内存，避免了挖矿只需要算力的问题，使挖矿更贴近普通计算机，实践one cpu one vote。

这里可能会有疑问，既然是专业设计的矿机，为什么不可以针对Ethash算法设计计算能力强内存大的专业矿机？相较于提升计算能力，提升内存容量需要更高的成本和门槛，提升完内存之后，内存与cpu的带宽又会极大的限制内存的读取速度，而内存带宽又是很难提升的，这些限制导致设计针对Ethash算法的矿机困难重重。

Ethash算法流程；

  • 根据区块信息生成一个种子（seed）;
  • 根据seed计算出一个16M的伪随机缓存（cache），由轻客户端存储；
  • 根据缓存计算出一个1G的数据集（dataset），其中的每一个数据都是通过cache中的一小部分数据计算出来，该数据集由全节点存储，大小随时间线性增长；
  • 矿工会从dataset中随机取出数据计算哈希（hash），来判断是否满足挖矿难度；
  • 轻节点验证者会根据缓存重新生成数据集中所需要的那部分数据，因此只需要存储缓存即可；

数据集（dataset）又被称为DAG

这里cache选择16MB缓存是因为较小的缓存过于容易生成数据集，容易用于 ASIC。而较大的缓存会增加轻客户端的存储要求，同时验证算法难度的增加也会使得轻客户端无法进行区块校验。

选择初始大小为 1GB 的 DAG 数据集是为了要求内存级别超过大多数专用内存和缓存的大小，但普通计算机能够也还能使用它。 数据集选择 30000 个块更新一次，是因为间隔太大使得更容易创建被设计为非常不频繁地更新并且仅经常读取的内存。 而间隔太短，会增加进入壁垒，因为弱机器需要花费大量时间在更新数据集的固定成本上。

同时，缓存和数据集大小随时间线性增长，且为了降低循环行为时的偶然规律性风险，数据大小是一个不超过上限的素数。 每年约以 0.73 倍的速度增长，这个增长速率大致同摩尔定律持平。这仍有越过摩尔定律的风险，将导致挖矿需要非常大量的内存，使得普通的 GPU 不再能用于挖矿。因为可通过使用缓存重新生成所需数据集的特定部分，少量内存进行 PoW 验证，因此你只需要存储缓存，而不需要存储数据集。

算法具体的流程如下：

缓存和数据集

  • 在以太坊中，每30000个区块称作一个纪元（epoch），每产生一个纪元就更新一次dataset和cache。

  • 前2048个纪元的生成的dataset和cache的大小是硬编码在代码里的，如果超过这个数量就需要自己计算了。

    1. dataset的计算方式(2^24 + 2^17 * epoch - 128)，用这个值除以128看结果是否是一个质数，如果不是，减去128再重新计算，直到找到最大的质数为止。

    2. cache的计算方式(2^24 + 2^17 * epoch - 64)，用这个值除以64看结果是否是一个质数，如果不是，减去64再重新计算，直到找到最大的质数为止。

dataset从1GB 开始，以每年约520MB的速度增大，cache从16MB 开始，以每年约 12MB 的速度增大。

生成种子（Seed）

种子Seed实际是一个哈希值，每个窗口周期（30000 个区块）更新一次。它是经过多次叠加Keccak256计算得到的。第一个窗口周期内的种子哈希值 s 是一个空的32字节数组，而后续每个周期中的种子哈希值，则对上一个周期的种子哈希值再次进行 Keccak256 哈希得到。

生成缓存

根据区块高度，可计算验证区块所需要的缓存大小，为了加速计算速度，已经根据增长算法，内置了最早 1024 个时期的缓存大小。相当于在 30720000 区块前是可以直接使用缓存的。否则根据区块所在时期，进行缓存大小计算。

缓存 cache 生成过程中，是将 cache 切割成 64 字节长的若干行数组操作的。

先将种子哈希值的 Keccak512 结果作为初始化值写入第一行中；随后，每行的数据用上行数据的Keccak512哈希值填充；最后，执行了3次 RandMemoHash 算法（在严格内存硬哈希函数 Strict Memory Hard Hashing Functions (2014)中定义的内存难题算法）。该生成算法的目的是为了证明这一刻确实使用了指定量的内存进行计算。

RandMemoHash 算法可以理解为将若干行进行首尾连接的环链，其 n为行数。

每次 RandMemoHash 计算是依次对每行进行重新填充。先求第 i 行的前后两行值得或运算结果，再对结果进行 Keccak512 哈希后填充到第 i 行中。

最后，如果操作系统是 Big-Endian(非 little-endian)的字节序，那么意味着低位字节排放在内存的高端，高位字节排放在内存的低端。此时，将缓存内容进行倒排，以便调整内存存放顺序。最终使得缓存数据在内存中排序顺序和机器字节顺序一致。

生成数据集

利用缓存 cache 来生成数据集，首先将缓存切割成n个16bytes大小的单元。在生成过程中时将数据集切割为若干个 64bytes 大小的数据项，可对每项数据 mix 并发生成。最终将所有数据项拼接成数据集。

  • 在生成 index 行的数据时，先从缓存中获取第 index % n 个单元的值 u;
  • 数据项 mix 长度 64bytes，分割为 4bytes 的 16 个 uint32。第一个 uint32 等于 u^index，其他第 i 个 uint32 等于 u+i;
  • 用数据项 mix 的 Keccak512 哈希值覆盖 mix；
  • 对 mix 进行 FNV 哈希。在 FNV 哈希时，是要从缓存中获取 256 个父项进行运算。
    • 确定第 p 个父项位置： FNV(index^p ， mix[p%16]) % n；
    • 再将 FNV( mix[p%16], cache[p] )的值填充到 mix[p%16]中；其中，FNV(x,y)= x*0x01000193 ^ y ；这里的 256 次计算，相当于 mix 的 16 个 uint32 循环执行了 16 次。
  • 再一次用数据项 mix 的 Keccak512 哈希值覆盖 mix；
  • 如果机器字节序是 Big-Endian 的，则还需要交换高低位；
  • 后将 mix 填充到数据集中，即 dataset[index]=mix;

1GB的数据集，则需要填充 16777216 次，每次都是根据索引 index 从缓存中获取 64 字节数据作为初始值，并进行依次哈希计算。随后，哈希后的 64 字节数据还需要执行 256 次 fnvHash 计算。 最终对计算结果进行哈希，得到最终需要的 64 位字节。 并填充到数据集中。

这样1GB数据需要进行16777216 * 256次计算。整个过程非常耗时，因此在 geth中会利用多核进行并行计算。即使如此，1GB数据集生成也是缓慢的。

这也就是为什么在搭建私有链时，刚开始时会看到一段“Generating DAG in progress” 的日志，直到生成数据集完成后，才可以开始挖矿。可以执行geth 的子命令dgeth makedag 10000 /tmp/ethdag来直接生成数据集。

FNV哈希算法

FNV哈希算法全名为Fowler-Noll-Vo，是以三位发明人Glenn Fowler，Landon Curt Noll，Phong Vo的名字来命名的，最早在1991年提出。FNV能快速hash大量数据并保持较小的冲突率，它的高度分散使它适用于hash一些非常相近的字符串，比如URL，hostname，文件名，text，IP地址等

FNV算法有三个版本：FNV-0（已废弃）、FNV-1和FNV-1a，两个算法需要用到的变量如下；

hash值：一个n位的unsigned int型hash值
offset_basis：初始的哈希值
FNV_prime：FNV用于散列的质数
octet_of_data：8位数据（即一个字节）

FNV-1和FNV-1a的算法都很简单，FNV-1算法如下

hash = offset_basis
for each octet_of_data to be hashed
    hash = hash * FNV_prime
    hash = hash xor octet_of_data
return hash

FNV-1a算法如下；

hash = offset_basis 
for each octet_of_data to be hashed
    hash = hash xor octet_of_data
    hash = hash * FNV_prime
return hash

FNV_prime的取值: 32 bit FNV_prime = 2^24 + 2^8 + 0x93 = 16777619 64 bit FNV_prime = 2^40 + 2^8 + 0xb3 = 1099511628211

以太坊采用的是FNV-1

算法原理

挖矿所需具备的数据集准备好后，则在每次需要挖出新块时，需要结合新区块链信息、数据集、随机数来进行数据聚合计算， 如果此算法的输出结果（result） 低于目标 （target），则随机数（nonce）有效。

上图是 Ethash 的计算流程图。说明如下：

  • 首先将传入的新区块头哈希值和随机数 nonce 拼接后进行 KEC512 哈希，得到 64 字节的种子 seed；
  • 然后初始化一个 128 字节长的 mix，初始化时分割成 32 个 4 字节的单元；使用 128 字节的顺序访问，以便每次 Ethash 计算都始终从 RAM 提取整页，从而最小化页表缓存未命中情况。理论上，ASIC 是可以避免的；
  • mix 数组的每个元素值来自于 seed; mix[i]= s[i%16*4];是 seed 的第 0、4、8...60 位的值；
  • 紧接着完成 64 次循环内存随机读写。 每次循环需要从 dataset 中取指定位置 p（fnv(i^s[:32]，i%32) % rows）和 p+1 上的两个 16 字节拼接成 32 字节的 m；然后，使用 fnv(mix[i],m[i])去覆盖 mix[i]; 其中，i 是循环索引、s[:32]是种子 seed 的前 32 字节、rows 是表示数据集 dataset 可分成 rows 个 128 字节。
  • 然后压缩 mix。压缩是将 mix 以每 16 字节分别压缩得到 8 个压缩项。每 16 字节又是 4 小份的 fnv 叠加哈希值 fnv(fnv(fnv(m[0],m[1]),m[2]),m[3]);
  • 拼接这 8 个压缩项就得到 mix 的哈希值 mixHash;
  • 最后将 seed 和 mixHash 进行 KEC256 哈希得到伪随机数 N；
  • 最终，返回这两个参数：mixHash 和 N；

其中的数据流如下图所示；

难度炸弹

尽管以太坊对比特币的工作量证明算法进行了大量的改进，但是有一些算法根本性的缺点还是无法克服，比如挖矿时会浪费大量的资源、整个网络处理效率较低等等。为了解决这些问题，有人就在2011年提出：“可不可以在PoW的基础上，重新设计一个机制？既能保留PoW的优势，又能解决它的问题”。于是权益证明（Proof of Stake）共识机制就应运而生，简称Pos。

权益证明机制主要是通过权益记账的方式，来解决网络的效率低下、资源浪费和各节点的一致性问题，简单来说，就是谁拥有的权益多谁说了算。以太坊从2013年底诞生到目前也有近十年的发展时间，其中掺杂了太多的利益方，从工作量证明到权益证明就不仅仅是一个技术上的难题，还涉及附着在以太坊社区之上的利益团体能否达成一致支持共识算法的变更，而矿工的利益就是其中很重要的一部分，取得矿工们的支持无疑对以太坊共识算法的变更有着极为重要的作用。

以太坊“难度炸弹”是以太坊在2015年加入的一段代码，通过逐步增加挖矿难度，从而人为减慢以太坊挖矿速度。这一机制是为了使以太坊的共识算法从工作量证明向权益证明机制（Pos）算法的巨大转变而设计的。

难度炸弹指的是计算难度时除了根据出块时间和上一个区块难度进行调整外，加上了一个每十万个区块呈指数型增长的难度因子。

这有点像一个温水煮青蛙的过程，一开始附加的难度并不引人注意，但是随着区块高度的增加，呈指数增长的难度因子比重将会显著提高，使得出块难度大大增加，矿工将难以挖出新的区块。在2017年9月的时候以太坊的区块高度超过420万，难度炸弹已经开始发挥威力，出块时间从之前很长一段时间维持的平均15秒左右渐渐增加到了25秒，每天新产生的ETH降到了19000以下（2017年9月2日数据）。由于出块越来越艰难，到最后区块将被完全冻结，这个过程又被称作“冰川时代”（Ice Age）。有了这个预期，那么转PoS引起的硬分叉就不会是一个困难的选择，毕竟没有人会继续待在那条将要走向凛冬的区块链。

可以通过下图看到难度炸弹的威力:

然而权益证明的机制设计中有很多问题需要解决，开发时间比原本计划的要长。根据最近的以太坊改进建议EIP-649（2017年8月26日被接受 ），转换到权益证明的时间节点将被延迟约一年半，工作量证明（PoW）将会继续担当大任。为了不堵塞交易，维持系统稳定运行，难度炸弹也需要被相应地延迟，实现方式是将挖矿难度按照回退300万个区块的高度去计算，因此出块时间又将回到15秒左右，如果不采取任何行动，则ETH的供应量会明显超出按原本难度炸弹时间表规划的供应量，这会导致通货膨胀，降低ETH的价值，为了使ETH的供应量与原本计划的数量相当，于是需要减少每个区块的奖励，从原本的5个ETH减少为3个ETH，叔块的奖励也将相应减少。

在目前的工作量证明共识机制的条件下，矿工每次创建新区块并将其添加到区块链中时都会赢得奖励。但当以太坊难度炸弹设置为“引爆”时，矿工通过挖矿获得奖励的难度将成倍增加。

以太坊挖矿难度调整

与比特币每2016个区块调整挖矿难度不同，在以太坊中每个区块都有可能调整挖矿难度，调整的公式如下；

本区块难度 = 父区块难度 + 难度调整 + 难度炸弹

难度调整 = 父区块难度 / 2048 * MAX(1 - (block_timestamp - parent_timestamp) / 10, -99)

难度炸弹 = INT(2**((block_number / 100000) - 2))