Qtum研究院:Cuckoo Cycle算法简介

2019-04-01 21:33 栏目:经验之谈 来源: 查看()
MimbleWimble是一种区块链协议,它依赖强大的加密原语来提供出色的可扩展性,隐私性和可替代性。 MimbleWimble项目的主要目标和特征是——隐私,这使得无法从交易的公共信息中跟踪交易金额,发送方和接收方; Utxo削减并最小化事务数量(< 100字节内核),而其他区域Blockchain节省了大量空间; MimbleWimble功能强大且经过验证,仅依赖椭圆曲线加密技术,经过数十年的尝试和测试。最近社区驱动的项目Grin使用新的PoW的Cuckoo Cycle算法来鼓励采矿。

Qtum研究院:Cuckoo Cycle算法简介

PoW共识首先被比特币采用,并且是区块链使用的第一种共识方法。到目前为止,PoW是容错的最佳公共链共识机制。公共链的安全基石是共识机制。 PoW基于物理计算能力。当链的计算能力达到一定规模时,比如比特币,因为它必须拥有整个网络一半以上的计算能力(51%的攻击力),这使得攻击非常昂贵,很难发挥作用权力分散时的攻击。

因此,算法选择倾向于分散计算能力(反并行挖掘算法)。这是通过使主存储器延迟成为瓶颈来实现的,因为DRAM延迟保持相对恒定,而CPU速度和存储器带宽在硬件架构和处理技术之间变化很大。

常见的POW算法类型

·纯哈希类型算法:随机碰撞,计算难度
·Equihash类算法:广义生日悖论问题,记忆难熬
·ethhash:基于DAG来解决约束,记忆力很强
·杜鹃循环:图形工作模式的证明,记忆力很强

除此之外,还扩展了PoW的Cuckoo Cycle算法,这是一种更加平等的共识方法,可最大限度地减少硬件架构中的性能差异,并使硬件挖掘具有成本效益。
Cuckoo Cycle是一种新颖的图论理论算法设计,它结合了可扩展的内存需求和即时可验证性。此外,它也是第一个主导内存延迟的设计运行时。除非存在任何不可预测的记忆时间权衡,否则它将产生近乎完美的内存限制证据,证明其商品硬件的成本效益可以极大地促进采矿业的分散化。

Cuckoo Cycle的一个有趣特性是制造ASIC不具有成本效益。尽管如此,ASIC几乎是不可避免的,因此在某些时候,Cuckoo环路的ASIC将变得可用。但是,即使发生这种情况,硬件制造商也无法在普通用户上创建ASIC。

本文重点介绍Grin使用的PoW一致性算法—— Cuckoo Cycle。
 
Grin的PoW算法:Cuckoo Cycle

Grin的基本Proof-of-Work算法称为Cuckoo Cycle,由John Tromp于2014年发明。它主要是一种内存约束算法,这意味着解决方案时间受内存带宽的限制,而不是原始处理器或GPU速度。因此,Cuckoo Cycle的解决方案应该适用于大多数商品硬件。 Grin介绍了两种POW算法。主要算法设计为ASIC友好,而辅助算法是ASIC抗性。在最初发布时,Grin Mining逐渐从反ASIC变为ASIC友好型。

当网络启动时,90%的块将通过辅助算法挖出,并且主算法将仅挖掘大约10%的块。主要算法称为Cuckatoo31 +,通过每6个月更改一次算法实现二级算法Cuckaroo29,Cuckaroo29 anti-ASIC。
 
 杜鹃循环问题

Cuckoo Cycle问题是从Cuckoo图中找到一个L长度的环。 Cuckoo图是一个二分图,其中边(即连接节点的线)仅在两个独立的节点组之间连接。它由N个节点和M个边组成,节点由Cuckoo哈希表表示。

图的一侧是用奇数索引编号的数组(图的最大大小),另一侧用偶数索引编号。下面的简单图表是这样一个图表,偶数侧(顶部)有4个节点,奇数侧(底部)有4个节点和4个边。

Qtum研究院:Cuckoo Cycle算法简介

杜鹃循环存在的概率

为了确保POW工作负载证明的安全性和公平性,这意味着所有参与者都无法以某种方式提高解决问题的可能性。布谷鸟循环存在的概率与图中的节点数和边数有关。随着M和N的增加,在图中找到L的循环的概率将趋于稳定。

下图显示了当L=42时,可以找到环的概率作为M/N变化的比率。可以看出M=29,31,  N=2M,M/N=50%,并且找到L=42的环的概率是1/42。

Qtum研究院:Cuckoo Cycle算法简介

布谷鸟图的边缘修剪和环路检测

通过计算节点的自由度并重复修整小于2的边缘(其永远不会是环路的一部分),可以大大减少环路寻找算法所需的边缘数量。例如,下图中,您可以先切断(2,15) (11,12)的边缘。此时(10,11) (4,15),出现可以切断的状态,最后留下右边的修剪。完成地图并使边数减少40%。

Qtum研究院:Cuckoo Cycle算法简介

循环检测从第一条边开始,依次添加其他边。当没有环时,形成树形结构。对于新添加的边缘,根据深度选择树,并且回溯根节点以确定是否形成环。对所有点执行一次,找到与边相关的所有循环,并将它们与目标参数进行比较。如果存在等长的循环,则问题成功解决。

格林的PoW跑步过程

处理完块后,您可以获取其块头,将块头的哈希值与Cuckoo算法相结合,在图中找到环,并将找到的结果的哈希与目标难度进行比较。当它小于目标时,PoW工作负载执行。过程如下:

1.散列新的块头以创建一个哈希值K
2.哈希值K将用作SIPHASH函数的KEY,它将为图中的每个元素生成一个位置对
3.通过修剪,执行Cuckoo循环检测算法以尝试在生成的图形中找到解(即,长度为42的循环)
4.在找到的环上执行Blake2b哈希并将其与当前目标难度进行比较
5.如果哈希难度大于或等于目标难度,则将块广播到网络并开始在下一个块中工作
6.如果未找到解决方案,请将块头中的Nounce增加1并更新下一个哈希迭代的时间戳

微信二维码
售前客服二维码

文章均源于网络收集编辑侵删

提示:仅接受技术开发咨询!

郑重申明:资讯文章为网络收集整理,官方公告以外的资讯内容与本站无关!
NFT开发,NFT交易所开发,DAPP开发 Keywords: NFT开发 NFT交易所开发 DAPP开发