导入

以太坊和比特币具有诸多方面的不同,例如以太坊的出块时间相对较短,只有十几秒。除此之外,以太坊没有和比特币一样采用简单的SHA256算法进行工作量证明,而是提出了一种具有Memory Hard特性的ETHash算法,这种算法主要的意义在于能在一定程度上阻碍ASIC矿机的研发。

当然最为重要的是,比特币是一种加密货币系统,而以太坊是一种加密合约系统。合约的有效性同样通过区块链上的共识机制实现。

ETH的账户系统

账户系统基础

比特币是一个基于交易的记账系统,不会维护每个账户的余额信息。当A给B转账10个BTC时,需要说明BTC的交易来源,即交易的输入。当输入的交易的BTC金额大于本次转账的金额时,需要将剩下的比特币重新转回给自己,否则就会被当作矿工费处置。

而在以太坊中,每个账户都会维护余额信息,即一个基于账户的记账系统。以太坊的账户模式本身就可以防御”双花“攻击,因为两次扣减余额不会成功。但可能会遭到”重放攻击“,即收款人将转账交易重放。为解决该问题,每个以太坊交易中会记录Nonce,即该交易是对应账户发布的第几次交易。如果该值不符,交易会被拒绝。

以太坊中的账户分为两类,即外部账户和合约账户。合约账户包含合约代码、代码对应的存储(即变量取值),合约账户无法主动发起交易,只能由外部账户调用合约。

之所以以太坊要采用合约为基础的账户体系,是因为在合约中,参与用户的身份要保持相对稳定。

状态树

在设计以太坊账户的数据结构时,必须要考虑到以太坊中的使用需求。首先,以太坊账户在每个交易中会变化状态的账户只占极小一部分,因此要求不能有一点变动就要重构整个数据结构。除此之外,由于查询余额和修改余额等操作都非常常见,因此必须要方便对账户的索引。

综合考虑上述特性,以太坊中的账户树采用了类似于Trie的数据结构,Trie的索引就是账户地址,但进行了路径压缩,例子如下:

image-20210407201907028

image-20210407202341886

之所以进行路径压缩,是因为以太坊的账户地址是极为稀疏的,压缩可以有效提升查找和存储效率。

和比特币类似,以太坊中的MPT也会计算其根哈希值放在区块头中。从下图中可以看到,两次交易间,账户树的绝大部分节点都指向同样的位置,只有极少部分发生交易的节点才会变化,非常好的节约了资源。

image-20210407202707794

以太坊的账户系统会维护账户信息的历史状态,便于交易的回滚。

每个区块都必须维护一个完整的状态树,否则不便于账户状态的查找。特别是当有新账户插入时,将会是灾难性的。

交易树和收据树

交易树和收据树和状态树一样,都是以MPT为基础的数据结构,且三棵树的根哈希值都记录在了以太坊的区块头中。交易树主要记录了区块中的交易信息,收据树则主要记录了区块中各个交易的执行结果,便于对于合约类的交易,快速获取结果。

交易树主要是便于对交易进行查找,证明某个交易在某个区块中。为了便于对于交易的查找,以太坊中引入了Bloom Fliter数据结构。

Bloom Filter是一种对集合做摘要的算法。例如一个集合中有a、b、c三个元素,则我们可以将这三个元素进行哈希后存入一个128位的定长向量中的对应位置(将对应位置记为1)。当有第4个元素d需要被确认是否在该集合中,我们就可以通过先对d进行对应的哈希运算,查找向量中对应位置是否为1来实现快速查找。

image-20210407203756783

但Bloom Filter数据结构存在明显的局限性,即不支持删除操作。

以太坊中,每个交易的收据都有一个Bloom Filter,记录了交易的类型等信息。发布的区块中也会有一个总的Bloom Filter,是区块中所有Bloom Filter的并集。因此在查找交易类型时,可以通过Bloom Filter进行快速查找,先查找区块头,再依次寻找交易,提高查找效率。

因而以太坊的实质就是一个交易驱动的状态机。

ETH共识机制——GHOST协议

以太坊的出块时间非常短,仅有十几秒。由于P2P协议的不确定性,新的区块很可能不能及时被其他矿工收到。导致其他矿工收到这个区块的广播时,已经挖出了自己的区块。也就是产生了分叉。在比特币中,出块时间大约为10分钟,因而发生分叉的概率相对比较低。但在以太坊中,分叉就成为了常态。

在比特币中,只有最长合法链上的矿工可以获得出块奖励,其他链上的出块奖励其实作废。但对于以太坊来讲,由于分叉的概率很高,对于矿工其实并不公平。尤其是对于个体矿工,如果矿池挖出一个区块,矿池为了保障自己的利益,一定会沿着自己产生的区块往下挖,使得个体矿工的区块作废,实现自己的利益最大化。

为了解决上述问题,以太坊中引入了改进的GHOST协议。一个分支上的区块可以被认为是一个叔父区块(Uncle Block),且最近一个叔父区块的奖励为八分之七的正常出块奖励,而包含这个叔父区块的区块则可以得到出块奖励三十二分之一的额外奖励。一个区块最多可以包括2个叔父区块,如果包含2个,则三十二分之一可以乘以2,图示如下:

image-20210407210131858

在这个协议的背景下,就算是挖出叔父区块的矿工也能获得绝大多数出块奖励,有利于合并系统中的分叉。

当然,上述协议没有限制叔父区块的代数,存在恶意矿工持续挖掘很早以前的区块的叔父区块的问题。如果只算最近的一个区块是叔父区块,则可能存在矿池间恶意商业攻击,且如果多于2个叔父区块也能被后面的区块包含进来。因而在以太坊中,对叔父区块的代数做了限制,要求在7代以内有共同祖先,并将代数和对应奖励的比例挂钩,但对于包含叔父的区块,奖励同样为三十二分之一不变。如下图所示:

image-20210407210643243

在以太坊中,出块奖励由静态奖励(目前为3个ETH)和交易费组成。上述叔父的出块奖励只包括静态奖励。

需要注意的是,在包含叔父区块时,当前区块的矿工并不会执行叔父区块中的交易。防止系统出现混乱。收到叔父区块后,当前区块的矿工只会检查该区块的工作量证明是否有效。

如果叔父区块后还存在其他的区块,后续的区块都不会获得出块奖励,以提高分叉攻击的代价。

ETH挖矿算法——ETHash

为避免ASIC矿机带来的算力集中问题,ETH中设计的挖矿算法是Memory Hard,即对内存操作有极高要求的。

在设计挖矿算法时,基本要求是验证答案容易,但求解难。

ETHash算法中,将数据集分为16M的Cache和1G的DAG,之所以要分为两种大小的数据集,是为了照顾进行区块验证的轻节点。验证的轻节点只需要保存16M的Cache,而只有需要挖矿的矿工才需要维护1G的DAG。Cache和DAG的大小会定期增长,因为计算机的内存大小也是定期增长的。

和莱特币类似,ETHash中也是维护了一个由种子元素依次哈希运算生成的数组,这也就是16M的Cache的来源。紧接着,我们会按照伪随机的顺序依次读取Cache中的元素(例如先读取A,根据A的哈希值得到下一个要读取的位置,读取出元素B,以此类推),生成一个远远更大的数据集,即DAG。

当进行挖矿时,矿工会按照根据区块头算出一个初始的哈希值,然后依据这个哈希映射到DAG中的位置,再读取其旁边的数,再根据读取的数寻找下一个要读取的位置,循环64次,共读取128个数,得到一个哈希值,和挖矿难度进行比较,得到挖矿结果。伪代码如下:

  1. 生成Cache

    image-20210407213914033

  2. 生成DAG

    image-20210407213938418

  3. 挖矿和验证算法

    image-20210407214020105

由上图可知,轻节点在验证时,只需要维护16M的Cache,在验证时和挖矿一致,进行64轮循环,只不过在验证时临时生成大数据集中的对应元素,虽然比较麻烦,但以时间换空间,也是可以接受的。但矿工需要重复这个流程若干次,如果不保存DAG的话就是在是太慢了。

ETH的难度调整算法

以太坊中每个区块都可能会调整挖矿难度。以太坊中的难度由基础难度和难度炸弹组成,难度炸弹是为了由工作量证明转向权益证明准备的。

调整公式如下:

image-20210407214729519

以太坊中的出块难度以上一个区块难度的2048分之一为单位进行调整,即自适应调整部分:

image-20210407215003047

难度炸弹部分:

image-20210407215439095

以太坊的权益证明

从本质上讲,算力的投票也就是钱的投票。而算力资源是从区块链外得到的,反而是一种不安全的因素。

权益证明类似于在股份制公司中,每个人按自己所占的股份进行投票的机制。如果某人想发动对加密货币系统的攻击,则需要大量购买对应的代币,反而造成代币价格的大幅上涨,这使得维护区块链系统安全的资源形成了闭环。

和工作量证明不同,权益证明允许矿工使用自己的代币质押,并获得挖矿难度的降低。但这也带来了在分叉链上的”两边下注“问题(下注在一个分叉的代币在另一个分叉中仍可正常使用)

以太坊中的Casper协议:

为了解决分叉问题,在该协议中,用户可以以一定量的代币质押成为Validator,Validator会投票某个区块是否能成为一个有效的区块,投票的权重由Validator质押的代币数目决定。区块必须获得三分之二以上的Validator投票同意才能生效。

但并不是每一个区块都需要单独投票,以太坊将连续一段时间的区块分为一个Epoch,这个Epoch中的区块都被挖出后进行投票,必须要连续两轮Epoch的投票都生效,区块才有效。

image-20210407220844046

参与过程的验证者会获得对应的代币奖励,如果有不良行为(不投票、给两个分叉均投票等),会扣去一部分的保证金,扣去的保证金会被销毁,减少了以太币的总供应量。每个验证者任期过后有一定等待期,等待期其他用户可以检举揭发验证者的不良行为,若无不良行为,等待期过后可以取回质押的代币。

随着时间的推移,以太坊中挖矿获取的奖励会越来越少,权益证明获取的奖励会越来越多,促使工作量证明逐步转为权益证明。