Dagger算法

发表于 2019-05-28 更新于 2021-11-17 分类于翻译本文字数： 3k 阅读时长 ≈ 3 分钟

原文地址

从过去五年比特币以及其他加密货币的经验来看，工作证明的一个重要属性是内存困难，计算有效的工作证明不仅需要大量的计算，而且需要大量的内存。目前存在两大类内存困难型函数:scrypt和Primecoin，但都不完善;这两种方法都不像理想的内存困难型函数那样需要那么多内存，而且都面临着时间-内存权衡攻击，在这种情况下，函数的计算内存都比预期的少很多，代价是牺牲了一些计算效率。本文介绍了Dagger，一种基于适度连接的有向无环图（DAG，因此得名）的内存困难型的工作证明，虽然远非最优，但具有比当今使用的任何其他东西更强的内存困难特性

为什么要内存困难？

内存困难之所以重要的主要原因是使工作证明不受专用硬件的影响。比特币的挖矿算法仅仅需要简单的sha256计算，创建特殊的“专用集成电路(ASICs)”公司已经出现了一年多，这种通过特殊设计和配置芯片的机器，目的是仅仅为了数十亿次的哈希运行，从而找到有效的比特币区块。这种芯片除了比特币挖矿和密码破解外没有任何应用，这些芯片的存在，使得在计算哈希值时每美元和千瓦时的效率是普通cpu的数千倍，这使得使用通用CPU和GPU硬件的普通用户无法与之竞争。

专业硬件的这种优势有几个不利的影响：

它否定了加密货币挖掘的去中心化方面。在通用硬件主导的生态系统中，每个人都拥有计算机的这个事实保证至少每个人都有平等的机会获得一些初始货币供应。对于专用硬件，这种情况不再存在;每个经济主体的矿业潜力与其现有资本数量上之比是线性的(事实上，略微超线性)，这可能加剧现有的财富不平等。
它增加了资源浪费。在有效的市场中，边际收入接近边际成本。由于采矿收入与采矿的硬件成本及电费支出是呈线性的，这也意味着总收入接近总成本。因此，在专用硬件主导的生态系统中，资源浪费量接近网络安全级别的100%。在CPU和gpu主导的生态系统中，因为每个人都已经有了一台计算机，所以人们不需要购买专门的硬件来获得每秒几哈希值的挖掘能力。因此，收入在成本上是次线性的——每个人都“免费”获得一点收入。这意味着网络所浪费的资源数量可能大大低于其安全参数。
它将采矿集中在几个参与者手中，这使得51%的攻击更有可能发生，并有可能使网络面临监管压力。

专门的硬件是如此强大，因为它包含了成千上万个专门为计算工作证明函数而设计的电路，允许硬件并行地计算函数的成千上万次。内存困难通过使主要限制因素不是CPU功率而是内存来缓解这个问题。人们也可以通过以CPU时钟速度为目标进行适度的改进，但是由于技术考虑，这种优化的程度上限非常低。因此，通过改进是得并行化遇到这样一个障碍:并行运行10个内存困难型计算需要10倍的内存。专业的硬件制造商当然可以将数TB的内存打包到他们的设备中，但这可以通过两个因素来减轻这种影响。首先，业余爱好者可以通过购买许多现成的存储卡来达到同样的效果。其次，与SHA256散列芯片相比，存储器的生产成本要高得多（如果用笔记本电脑等价物测量）;普通计算机中使用的RAM已基本上是最佳的。

算法详述

本质上，Dagger算法的工作原理是创建一个有向无环图（树的技术术语，其中每个节点允许有多个父节点），其中包含根节点总共有10层，2^25 -1个值。在级别1到8中，每个节点的值取决于它上一级的三个节点，并且每一级的节点数是前一级别的8倍。在第9层中，每个节点的值取决于其父节点中的16个，并且该级别仅是前一级的两倍;这样做的目的是使自然时间-内存权衡攻击在第一级实现高的人工成本，因此根本不可能实现任何时间-内存权衡优化。最后，该算法使用这些数据与nonce一起伪随机地选择图中的八个底层节点，并放在一起计算所有的这些节点的散列。如果矿工发现一个随机数，使得此结果散列低于2^256除以难度参数，则结果是有效的工作证明。

设D是基础数据（例如，在比特币的情况下是块头），N是nonce，||是字符串连接运算符(‘foo’ || ‘bar’ == ‘foobar’)。算法的整个代码如下：

spread(L) = 16 if L == 9 else 3

node(D,xn,0,0) = D
node(D,xn,L,i) = 
    with m = spread(L)
        p[k] = sha256(D || xn || L || i || k) mod 8^(L-1) for k in [0 ...m-1]

eval(D,N) = 
    with xn = floor(n/2^26)
        p[k] = sha256(D || xn || i || k) mod 8^8*2 for k in [0...m-1]
    sha256(node(D,xn,9,p[0]) || node(D,xn,9,p[1]) ...||node(D,xn,9,p[3])

目标：发现一个k使得eval(D,k) < 2^256/diff

性能

使用2^ 25内存（即512MB，因为每个内存单元是32字节哈希），最佳算法是预先计算2^ 24个叶子节点,运行eval时有2^ 25种可能性。主要的计算困难是计算SHA256哈希,1到8层的的每个节点需要两次哈希，所以需要2^ 25-4次哈希(因为根节点不需要散列，所以不是-2)。在第9层每个节点需要16个哈希，增加2^ 28次哈希，之外每个nonce占用8次哈希，在增加2^28次哈希。因此运行2^ 26个nonce需要2^ 29+2^ 25-4次哈希。
一个潜在的问题是延迟评估：为了减少所需的哈希数，树的一部分可以被估计。然而，由于2^ 25个节点中有一个(伪)随机节点被取了2^ 28次，我们可以统计估计每个节点剩余未使用的变化量为1/e^ 8—只有0.03%左右。因此，延迟评估的好处是微不足道的。
可以用很少的内存运行算法，但是必须重新计算工作证明每个nonce上依赖的8个底部叶子节点。这是一个指数计算，计算一个nonce需要3^ 8*16(104976)步。实际上，很多值都是重用的，所以平均只需要6000个哈希值，但是这仍然是一个非常大的量——基于内存的算法每nonce只管理8个计算，这使得低内存硬件的代价是750倍
验证需要在没有预先计算的情况下计算一个nonce，因此它还需要6000个哈希值和大约160 KB的内存。
由于最后一层中的每个节点都有16个父节点，而不是3个，因此时间-内存权衡攻击被严重削弱，试图存储8层而不是9层会减少2倍的内存使用量，但会降低16倍的计算速度。因此，不存在实际的时间权衡攻击;任何合理的效率水平都需要接近完整的512 MB。

结论

该算法提供了一个工作证明挖矿函数，其内存困难特性并不理想，但与以前的任何方法相比，这是一个巨大的改进。计算需要512MB，验证需要112KB内存和4078哈希，而且由于底层的分支调整，即使是最小的时间-内存折衷也不值得实现。这些参数允许Dagger在内存需求方面比Primecoin或scrypt大胆得多，后者要求为单个线程提供512MB的RAM。决定难度的主要因素是内存，而不是计算，专有硬件只有很少的优势。即使在这样的均衡状态下，使用普通cpu进行开采也很依然是可行的。

题图来自unsplash：https://unsplash.com/photos/ttw2EsTM8VI