BCH升级提案：使用一种新的DAA算法——ASERT

2 264

Written by

No bio yet...

4 years ago

摘要

BCH的难度调整算法（DAA）允许“摇摆”矿工从忠诚矿工中谋取大量利润。矿工来回切算力导致挖矿难度和算力振荡。在我的测试模拟中，DAA会导致忠诚矿工损失约6％的收入，而EMA系列的DAA却能将损失控制在0.35％至0.65％之间。我为BCH 2020年11月的协议升级提出了一种称为ASERT的特定类型的EMA，并提供了关于该算法的广泛模拟结果以及示例C ++部署（未测试）。

DAA存在的问题

当前的BCH难度调整算法“cw-144”得名于链工作量(chainwork)的。它存在这样一个问题：易于振荡。该振荡是当前BCH DAA使用简单移动平均线（simple moving average）的结果。此前的文章对这一问题进行了详细描述。早在2017年10月份，cw-144就被曝出了这一问题。那时cw-144尚未在主网上被激活。

（如果你很熟悉这一问题，或者观看了我在2020年2月27日的视频，可跳过此部分，转到“稳定DAA”部分。）

该问题及其引发的激励问题存在以下bug：

1，如果90％的算力行为都是理智的，它将使平均交易确认时间增加约2倍。

2，如果100％的算力行为理智，它将导致链完全停止；

3，它允许自私挖矿攻击。自私挖矿会导致区块重组，降低公众对该区块链的信心，并使双花攻击更加可行；

4，对BCH的忠诚矿工是一种惩罚；

5，小型个体矿工无法掌握相关技术以自动执行算力切换；

6，它允许矿工作恶，有意放大振荡，激励算力切换。方法是自己来回猛烈地切换算力，或者操纵他们所挖区块的时间戳。

简而言之，振荡是由于cw-144使用最新144个区块的简单移动平均线（SMA）来估计哈希。例如在一个高哈希的块离开SMA窗口后，挖矿难度降低的幅度与新区块进入该窗口增加的幅度相同。因此，离开窗口的区块会剧烈地改变挖矿难度，激励矿工重复这一离开区块的哈希。我称这种效果为“哈希回声”。值得注意的是，这些回声并不是恶意的矿工行为，而仅仅是矿工在遵循DAA给他们的直接短期激励。

这些算力振荡的周期约为1.05天，在大多数难度或算力图表（使用1天的采样间隔）中不可见，但在此交互式图表中清晰可见。

这些哈希回声在cw-144 DAA于2017年11月被激活不久后首次出现在BCH中。当时，振荡幅度约为1 EH / s，每日峰值通常为每日最小值的2倍：

由于一些大型BCH矿池的挖矿行为发生了变化，这些回声在2019年10月1日左右变得极为严重。BitMEX Research甚至发表了一篇文章。振荡幅度达到11 EH / s，日峰值为日最小值的4倍至8倍。2020年1月20日左右和2020年4月的大部分时间都观察到了类似的极端情况。

算力振荡是由挖矿难度的变化引起的。这些难度振荡幅度通常超过10％，导致忠诚矿工在大多数时间都处于亏损状态（与挖矿BTC相比），而摇摆矿工每天切入约2-6个小时来获得所有有利可图的区块。

振荡严重影响了用户体验。高算力迸发很短，两者之间的算力低谷很长。大多数交易是在算力低谷期间发布的。因此对于正常的泊松分布（Poisson distribution），平均交易需要等待的时间远比理想的600秒长得多。在此交互式确认时间图表中可以看到这种效果。确认时间最近也变得更糟，自2019年9月以来平均大约15分钟，并在2020年1月达到峰值28分钟。

在2017年9、10月份，kyuupichan和其他一些开发人员编写了“ 难度软件套件”，模拟这些难度波动以及使用不同DAA进行的算力切换。 2020年2月，我用基于浏览器的图形用户界面（代码；慢在线版本）扩展了此套件。这些仿真证实了使用cw-144算法哪怕没有任何恶意矿工行为就能产生了这些振荡。对矿工来说，用cw-144生成它们所需的一切，在任何给定时刻挖最赚钱的币（BCH或BTC）即可。

模拟证明了振荡是特定于cw- *的故障。只要矿工是逐利的，cw的所有变体中都会出现这种振荡，对于灵敏度更高的变体w（例如，cw-144比cw-576更糟），其摆幅更大且更频繁，但是所有的摆幅都不存在其他好的DAA种类中。

摇摆矿工的收入可能比忠诚矿工高5-20%。通过切换到不同的DAA（例如EMA系列算法），我们可以将切换挖矿的动机降低大约90％-95％。

基于简单移动平均线（SMA）的cw-144算法的不稳定性是由区块离开144块窗口时突然结束的难度造成的。这种不稳定性可以随着时间的流逝来降低块的影响而逐渐消失。例如，如果影响在144个块上线性减小，则不稳定性消失。这就是lwma（线性权重移动平均值）算法以及Tom Harding的相关wt（权重时间）算法的作用。另一种选择是使影响随着时间呈指数衰减，例如144个块的时间常量。这就是EMA（指数移动平均线）算法系列的功能。该系列包括许多变体，例如Jacob Eliosoff的ema-1d和simpexp-1d，Tom Harding的wtema和Mark Lundeberg的asert算法。

在这些稳定的DAA中，我们确定了四种主要的候选算法：asert，wtema，lwma和wt。在我的模拟和zawy12的模拟中，所有这四种算法均表现良好。下表是针对所有四种候选算法进行一次这样的模拟运行的数据表，另加cw作为参考，对应于1天（如当前的DAA，cw-144），2天或4天的三种不同的响应设置。表中第三列中包含交易的平均确认时间。理想情况下，该数字应尽可能低。在“贪婪”到“稳定”列中，该表显示了各种挖矿策略（与挖BTC相比）的相对获利能力。在最后一列中，该表显示了从最差的挖矿策略切换到最佳挖矿策略所获得的优势。理想情况下，该数字应尽可能接近0％。

算法 — 区块平均间隔(秒) — 平均确认时间(秒) — 贪婪 — 可变 — 稳定 — 优势

当前的DAA算法cw-144是所有算法中算力稳定性最差的算法。与cw-144相比，该测试中最好的DAA asert-576仅花费了51％的时间来确认平均交易，并且将切换算力的动机降低了94.4％。在给定的响应度设置下，除cw以外的所有算法在性能上都紧密地聚集在一起。与中等设置相比，最长的响应时间（576块，4天）的性能优势是中等的。

模拟中这四个选项之间的算力调节性能差异很小。基于EMA的算法（wtema和asert）常常有一个很小的优势，但是优势很小，我们相信应该选择其他方面的考虑，例如部署复杂性。 lwma和wt都需要抽样其窗口中的每个块标投（如288个块）才能计算下一个块的难度，而EMA系列通常只需要采样两个区块头，因此我们应把注意力集中在EMA系列上。基于EMA的算法（wtema和asert）似乎常常有一个很小的优势，但是优势很小，我们相信应该选择其他方面的考虑，例如部署复杂性。 lwma和wt都需要抽样其窗口中的每个块标投（如288个块）才能计算下一个块的难度，而EMA系列通常只需要采样两个区块头，因此我们应把注意力集中在EMA系列上。

我们要考虑使用哪种EMA。最有趣的似乎是wtema 和 asert。

WTEMA和ASERT

看起来最好的两个EMA算法是wtema和asert。 wtema算法是由dgenr8（Tom Harding）在2018年1月1日或之前创建的。这是一种基于以下伪代码的非常简单的纯整数EMA：

next_target = prior_target / (IDEAL_BLOCK_TIME * alpha_recip)

next_target *= block_time + IDEAL_BLOCK_TIME * (alpha_recip - 1)

用抽象的术语来说，如果最新的块间隔完全代表算力，则wtema首先估计要改变多少区块“目标”（难度的倒数）才能实现600秒的块。然后，它使用1 / alpha_recip作为加权系数，在该值和最后一个块的目标之间执行加权平均。这使得wtema成为递归定义的函数，并且是典型的简单一阶IIR过滤程序，等效于电子RC过滤程序。它的性能与复杂的PID控制器系统一样好，但是复杂度却很小。

asert算法主要是由Mark Lundeberg在2020年2月或之前开发的。（其等效公式在2018由Jacob Eliosoff独立发现，但没有Mark Lundeberg的详细分析。） asert由以下公式定义：

target_timestamp = (height + 1 - activation_height)*IDEAL_BLOCK_TIME next_target = target_at_activation * 2^((last_timestamp − target_timestamp)/tau)

注意：^表示浮点指数，而不是整数XOR。

asert代表绝对时间计划的指数上升目标。用抽象的术语来说，Asert的工作原理是设定一个理想的出块时间计划，并根据其父块在该计划之前或之后的差距以指数方式设置每个块的难度。每个区块提前该时间计划tau秒，下一个区块的难度将增加两倍。tau的合理值可以从几小时到几周不等。像wtema一样，asert的代码和数学都很简单，并且仅取决于两个区块。与wtema不同的是，asert仅依赖于最新的块，创世区块或激活了asert的分叉区块。这避免了wtema的递归定义。有关asert的更多信息，我强烈推荐Mark Lundeberg的简要介绍性论文。

只要出块间隔时间正常，这两种算法在功能上几乎相同，仅在极端情况下有所不同。

wtema和asert在求解时间短时大约相等，但是当求解时间更长时就显出不同。无论哪种情况，asert都具有更出色的性能。使用wtema时，较大的负求解时间会导致×轴交叉问题。而使用 asert，大的正求解时间能响应更快地降低难度。图片来源：dgenr8

两种算法之间的争论围绕以下四个问题：

1，整数近似：由于wtert使用显式指数函数，因此wtema比asert更容易，但二者都可以实现。

2，奇点和消极的解决时间：如上图所示（来源：dgenr8），wtema会引起问题，但asert不会。可能需要规则来将求解时间限制为大于某个值（例如wtema-144> -0.5 * 144 * 600秒）

3，数学和理论上的优雅-两者兼而有之，但asert更好

4，四舍五入/近似误差的累积：wtema适中，asert由于其绝对性质而不存在。

＃1和＃2是主要问题。对2 ^ x的整数近似的需要使asert更复杂。而防止大量负面解决时间的需求使wtema更加复杂。为解决这一问题，我们最终决定对难度计算函数本身添加几行代码，而非添加或更改其他共识规则。因此，我们选择了asert。

在讨论了不同的整数近似方法后，我最终选择对0 <= x <1使用Mark Lundeberg的2 ^ x三次近似，并使用2 ^ x = 2 * 2 ^（x-1）恒等式将域扩展到所有实数。此近似值可将误差容限保持在0.013％以下。这里有一个aserti3算法的尚未测试的示例C ++部署，还有一个经过良好测试的aserti3的python3部署。性能与真正的asert非常相似。我们接下来会进行C ++部署的测试。

另一种选择是Jacob Eliosoff的exp_int_approx（）实现，该实现使用从Stack Overflow抓取的算法来实现随机精度，但要使用for指令和更晦涩的数学和代码。

我选择了2天的半衰期（tau = 2 * 24 * 60 * 60，等效于2 * 144 / ln（2）或aserti3-415.5的响应设置），这在模拟中性能几乎达到最佳的值范围，同时也易于理解和讨论。区块的时间戳每提前两天，难度就会加倍。我认为1天的半衰期（aserti3-207.75）也可以接受，但建议不要低于207.75或高于576。

激活

因为asert计算取决于分叉块的高度和难度，所以如果激活是在预定的区块高度而不是在经过的预定的中间时间（MTP）上进行的，则实现起来将更加简单。如果使用后一种方法，则需要分叉新的asert代码，以便在区块链中搜索MTP超过分叉时间的第一个区块，并从该区块的区块头中提取高度和难度。相反，如果使用分叉高度，则asert算法仅需要在区块链中搜索已知高度上的难度-该操作非常简单。虽然可以基于MTP激活asert，但我认为基于块高度进行激活会更简单。

Bitcoin ABC习惯在其代码中预先添加自戕式防御，以在预先确定的MTP分叉掉过时的软件版本。如果使用分叉高度激活asert，那么自戕式防御和asert激活将不会完全重合。这可能会导致接连出现两个技术性硬分叉，而不是单个三向分叉。这是使用分叉高度激活的一个小缺点。但是即使自戕式防御不能重合，它仍然可以达到其目的：阻止个人继续运行过时的软件。

我相信基于高度激活的asert更简单的代码要比无法重合的问题更重要，因此我在示例C ++部署中使用了基于高度的激活。如果大多数BCH开发社区不同意这一点，我也可以接受。

测试网

标准的20分钟测试网规则适用如下：如果某个块的时间戳比上个块的时间戳至少早20分钟，则该区块的挖矿难度可能是1。因为在asert机制下，挖矿难度调整是基于时间而非区块高度，所以“时间翘曲（timewarp）”技术在测试网上重置难度（通过反复向前移动时间戳以降低最后一个难度调整间隔内的平均链工作）。因此，在进行此更改后，测试网的难度调整将比以前慢，并且ASIC矿工离开测试网后，测试网用户可能会在几天中都遇到20分钟才出一个块的情况。这一问题可通过降低测试网上的tau值来解决，但是这样会降低测试网与主网的相似度。经常使用测试网的开发人员应该讨论他们更喜欢哪种方法。

攻击

我们研究了针对aserti3的多种不同类型的攻击。目前为止，使用现有的共识规则和非ABC / BCHN的节点策略在几乎所有情况下aserti3的性能均优于cw-144。只有少数一些情况存在问题。目前已发现的攻击影响都很小（小于其他已知和现有的攻击类型），并且只需要稍微更改节点策略即可改善。

第一种攻击是在没有振荡的情况下进行自私挖矿。在这种情况下，自私的矿工A可以人为地创造时间更早的时间戳为A1的区块（例如，求解时间为1秒），这会使下一个区块A2的难度增加0.24％。这可能导致链A2的工作量比B2多，导致节点更喜欢A2而不是B2，即哪怕节点先看到B2。Bitcoin ABC和BCHN已经具有阻止此攻击的节点策略规则，但BU和大多数其他节点并没有。为解决此问题，我们建议所有其他节点在块的先见规则（ first-seen rule）中增加滞后：只有当新链的工作量超过第一个链的某一数值，如10％或50％时，节点才应切换链。

第二种攻击是FTL（未来时间限制）攻击。在此攻击中，矿工创建了一个时间戳设置为FTL的区块（目前为7200秒），以降低在秘密链上进行挖矿的难度，尽可能挖出多的区块直到难度恢复正常。在某些（但不是全部）情况下，asert上更容易进行这种攻击。这是因为，asert的难度是在单个区块后做出相应，而非连续两个块。通过使用较慢的响应度设置（aserti3-2d大约是cw-144的响应度的1/4）可以大大减轻这种影响，但是可以通过简单地降低FTL更好的解决。

降低FTL看起来是一种直接的改进。许多竞争币都降低了FTL，且没有发现负面影响。在NTP和GPS的现代世界中，将系统时钟同步到0.1秒以内很容易，因此没有理由允许高达7200秒的错误而不受惩罚。即使在跨星际的未来中，600秒的FTL也不会对比特币协议造成问题，因为区块的时间戳反映的是发布时间，将导致其他行星使用旧时间戳（而不是未来时间戳）接收区块。在遥远的未来，一旦使用以相对论速度的工具来挖比特币，我们可能不得不重新考虑FTL。但在此之前，我建议将其降低到600秒。

以上没有对潜在的攻击进行详尽讨论。 zawy12的BCH EMA（第2部分）和哈希攻击示例Github发行线程中可以找到对其他攻击场景的讨论。