快捷搜索:  创业 手机 疯狂 生态 坏人 华人 发明

Nano PoW —详细信息

Nano PoW是一种免认证的速率限制算法,通常称为工作量证明。交易对手经过身份验证后的速率限制是微不足道的-在尝试登录的限制器和带宽,存储或时间的用户配额中很常见。但是,在尚未认证或无法执行认证的情况下,很难对速率进行限制。

工作量证明自动限速器的最初使用是电子邮件垃圾邮件预防工具。使用电子邮件,可以以非常低的成本发送大量不请自来的电子邮件,并且很容易用不想要的通讯方式淹没个人的电子邮件箱。一个明显的选择是使用电子邮件发件人地址白名单,尽管这对于用户而言很麻烦,而且用户倾向于要求较低的自发消息率。代替此白名单,建议发件人附加一小段称为证明的数据。该证明将在数学上证明发件人专用于进行此传输的资源不只是微不足道的。

遵循与早期电子邮件建议类似的模式,Nano网络要求使用基于blake2b的算法来证明迄今为止的每笔交易。尽管要求证明的原始设计仍然有用,但是现有算法被证明太容易并行化,需要一种新方法来实现其预期功能。下面将详细概述这种新的Nano PoW算法的设计,尽管它在更广泛的应用中很有用,但第一种实现将在Nano网络上完成。


设计目标

  • 免认证:必须在没有认证的情况下构造证明。
  • 最小化证明大小:证明应尽可能小:8–16字节,以便在提供证明时最大程度地减少空间开销。
  • 最小化证明验证资源:验证应花费最少的计算时间和资源。
  • 规范简单:更简单的解决方案更易于分析和实施。
  • 最大化产生时间的面积乘积:该算法应需要一定的时间和硬件资源才能有效解决。
  • 降低功耗:验证方法应使用尽可能少的功率。

算法细节

工作量证明是2个数的解(x,y),每个N位,是方程H0x+ H1y= 0 mod 2 equation的解,其中D是经过调谐的难度参数和H0H1是由问题随机数P键控的耐原像散列函数。


有效证明必须满足的Nano PoW方程

例如,如果H0H1产生8位输出,并且我们选择难度D = 4,则有:


散列函数H0H1:选择了两个不同的散列函数,以消除解决方案查找优化,我们将在后面详细说明。这些哈希函数可以使用单个算法家族来构造,只需通过使用不同的密钥初始化哈希函数即可。例如,可以通过始终在P中设置固定位来锁定H0,并且可以通过清除同一位来锁定H1

加号运算符:一种可逆运算符,它的选择还在于消除求解方法的优化。

0 mod2ᴰ:较高的 D表示较高的难度,并将其调整为用户所需的难度阈值。

解决方案查找方法

寻找解决方案的简单方法就是尝试尝试xy的随机值处理器为x选择一个值,然后迭代y直到找到解决方案。可以将其视为存储1个候选x值,并且每次我们尝试y值时,我们都会针对单个候选对象检查此尝试。

通过存储多个x个候选对象并将y个尝试与所有存储的x个候选对象进行比较,可以对此进行改进该优化的关键在于能够在恒定时间内将一次y次尝试与所有存储的x个候选者进行比较我们可以通过根据H0x)的最低有效位将x个候选数进行基数排序来实现此目的当我们尝试y时,可以通过将解方程重写为H0x)= 0- H1ymod 2ᴰ,我们知道候选解决方案只能在存储区LSB(0- H1y))中。


如果表中填充了M个值,则我们可以通过一个恒定的时间计算和一个内存查找,将一个y次尝试与M个x个候选值进行比较这是查询表的M因子。

在最佳时间内找到解决方案涉及在用候选者填充表格和进行尝试之间找到平衡。

填写查询表

由于要求H0,H1必须具有防原像功能,因此无法选择和填充特定的存储桶条目-我们必须随机填充表格并以统计上的最佳数量停止。随着工作台负载系数的增加,碰撞机会也随之增加,并且额外的填充会迅速减少回报。

搜索查询表

解决方案查找算法必须以一种处理未初始化数据的方式进行设计,因为从性能的角度来看,填写整个表不是必需的,也不是期望的。我们将继续针对存储的候选者检查新尝试,直到找到解决方案。


最佳解决方案查找方法包括两个步骤:随机填充查找表,以及有效地搜索潜在的解决方案

调整查询表的大小

查找表的最佳大小是问题难度的函数,这是由较高的表加载因子导致的收益递减的因素。每次填充都需要进行H0计算和存储器写操作。每次尝试都需要一个H1哈希,一个内存读取和另一个H0哈希,以便重新构造所获取值的完整哈希。我们发现,大约2 ^(D / 2)项的查找表可提供最佳的解决方案查找时间。


给定表格大小的M因子和填充计数比率

设计注意事项

  • 简单哈希算法:与计算时间开销相比,我们希望最大化内存访问开销。因此,我们正在寻找最简单的哈希函数,该函数既可以产生均匀的随机输出,又可以防止原像。Siphash非常易于实现,并提供了我们需要的两个保证。
  • 查找与哈希表:由于存储的密钥已经是统一随机的,因此无需为密钥计算额外的哈希码,因此我们可以使用值本身。由于我们可以从特定存储桶中的值重构完整键,因此我们根本不需要存储完整键值。
  • 高负载因子:为了充分利用分配的内存,我们希望最大化表的负载因子,同时考虑到随着冲突增加,填充的收益递减。
  • 垃圾和数据争用免疫:由于无法保证任何特定存储桶都包含初始化值,因此该算法旨在即使面对垃圾数据,数据争用或数据故障也可以继续进行。这意味着整个算法在任何阶段都无需线程同步或原子内存操作即可继续进行。

并行Rho搜索

Nano PoW算法与查找哈希冲突之间存在相似之处。使用Rho搜索¹,使用非常有限的内存可以找到长度小于加密安全长度的哈希冲突。我们在解方程中添加了两个部分,这两个部分独立地使Rho搜索无法找到解。

使用Rho进行冲突查找的方法如下:将散列函数的输出反馈到其输入中,以形成一条路径,在该路径上,随着连续的输出作为输入被反馈,特定值将遵循该路径。当来自两个不同输入的输出恰好相同时,Rho搜索依赖于这两个路径最终合并为一条路径。一旦两条路径合并,它们将永远不会分开。最终,路径到达一个可分辨点,在该点处算法发现了当前和先前可分辨点之间的哈希冲突。

我们添加的第一件事是在运算符的任一侧使用两个不同的哈希函数。当我们使用两个不同的哈希函数时,即使在两个值之间发现了冲突,它们也不会继续遵循相同的路径,因此,区别点无法检测到冲突。

我们添加的第二件事是使用加法运算符而不是相等比较。Rho搜索使用路径合并作为找到解决方案的信号,并且路径合并仅在寻找值相等时有效。如果我们使用加法而不是等式比较,则合并路径并不表示解决方案,因此无法应用Rho。

通过尾随零对操作数计数进行缩放

我们选择的增加问题难度的方法是,要求解决方案具有更多的尾随零。尾随更多的零将需要更多的尝试,因此需要更长的解决方案位字符串。我们确实考虑了通过要求将其他操作数加在一起来扩大问题难度的另一种方法。要比较的相关数量是给定解决方案大小的附加位需要多少附加内存。

对于大约每两个尾随零位,我们的内存需求量增加了一倍。这意味着,如果我们将所需的尾随零的数量加倍,则会对所需的内存量进行平方。相反,如果我们将所需的操作数加倍,则仅将所需的内存量加倍。

通过要求附加的尾随零来增加问题难度,以解决方案长度为单位对存储要求进行二次方缩放,但是,通过要求附加操作数仅线性缩放,来提高问题难度。

内存与逻辑元素

内存和计算元素都代表与发现解决方案相关的物理量。但是,存储元素比计算元素更节能。当逻辑元件在高态和低态之间转换时,数字逻辑所消耗的大部分功率来自开关损耗。内存门保持其值稳定,并且不会消耗每个元素那么多的功率。内存是高度商品化的,甚至在竞争的处理器实现之间也是如此,并且是市场上价格最低的晶体管。²

查找表中项目之间没有数据关系

查找表中的所有项目都是伪随机函数的输出,并且彼此之间没有可确定的数据关系。此属性消除了类似于scrypt³的时间存储器折衷的可能性,在scrypt³中,可以根据表中的数据关系来折衷数据存储以进行计算。此外,由于查找表中的候选解决方案与尝试之间没有空间或时间上的关系,因此数据缓存的命中率较低。

观察性能

下表列出了所选CPU和GPU在生成和验证证明的平均性能。设备使用最佳线程数(T)和2MB页面(如果可能)。所有数字都是针对难度60得出的。所使用的内存是指查询表的大小-4GB对应于查询30,8GB对应于查询31。结果为空白,其中所需的内存超出了可用内存。验证仅由CPU执行。


纳米网络实施

Nano PoW算法的第一个实现已在以下GitHub存储库中公开以供审查和反馈:

正在计划将此实现添加到带有V20 Lydia的Nano节点的计划。如果您有兴趣帮助测试性能并提供有关Nano PoW的反馈,请在#nano-pow频道的https://chat.nano.org中加入我们

您可以还会对下面的文章感兴趣:

  • Nano PoW —详细信息
  • 每周更新19/9/27-庆祝Nano网络的继续分散化
  • Nano PoW —基本要素
  • V20 —看看莉迪亚(Lydia)
  • 每周更新9/20/19-V20 Lydia即将推出
  • 最新评论

    留言与评论(共有 0 条评论)
       
    验证码: