风险提示:理性看待区块链,提高风险意识!
Grin币PoW共识算法之Cuckoo Cycle算法
首页 > 币界资讯 > 区块链知识 2019-06-26 15:35:03
币界网报道:

PoW共识最早由比特币采用,也是区块链最早使用的一种共识方法。目前为止PoW是容错能力最好的公有链共识机制。公有链的安全基石是共识机制,PoW以物理算力为基础,当链的算力达到一定规模后,像比特币,由于必须拥有全网一半以上的算力(51%攻击),这使得攻击非常昂贵,在算力比较去中心化的时候,很难发生算力攻击。

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

常见的POW算法类型:

纯hash类型的算法:随机碰撞、计算困难

Equihash类算法:广义生日悖论问题、memory-hard

ethhash:基于DAG解决约束、memory-hard

Cuckoo Cycle:图论式工作模式证明、memory-hard

而在此之上延伸出PoW的Cuckoo Cycle算法,该算法是一种更平等的共识方式,可以最大限度地降低硬件架构中的性能差异,并使硬件的开采具有成本效益。

Cuckoo Cycle是一种新颖的图论理论算法设计,它结合了可扩展的内存需求和即时可验证性。此外,它也是第一个设计运行时内存延迟主导。除非出现任何无法预料的内存时间权衡,否则它会产生近乎理想的内存限制工作证明,其商品硬件的成本效益可以极大地有利于矿业的分散化。

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

Grin的PoW算法:Cuckoo Cycle

Grin的基本Proof-of-Work算法称为Cuckoo Cycle,2014年由John Tromp 发明。它主要是一种内存约束算法,意味着解决方案时间受内存带宽而非原始处理器或GPU速度的约束。 因此,Cuckoo Cycle的解决方案应该在大多数商品硬件上都是可行的。 Grin 引入了两种POW算法。主要算法是被设计为 ASIC 友好的,而次要算法是抗 ASIC 的。在最初发布时,Grin 挖矿从最初抗ASIC 逐渐过渡到对ASIC友好。

网络启动时90% 的区块将会被次要算法挖出,而主要算法只会挖出大约 10% 的区块。主要算法称为Cuckatoo31+,次要算法Cuckaroo29 ,Cuckaroo29抗ASIC是通过每6个月改变一次算法来实现的。

Cuckoo Cycle问题

Cuckoo Cycle问题是指从Cuckoo图中找到一个L长度的环。Cuckoo图是一个二分图, 其中边(即连接节点的线)仅在2个单独的节点组之间连接的图。由N个节点和M个边组成, 节点采用Cuckoo散列表表示。

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

Cuckoo Cycle的存在概率

要保证POW的工作量证明的安全性和公平性,意味着需要所有参与方无法通过某种方法来提高解决问题的概率。Cuckoo Cycle存在的概率,和图的节点多少,边的多少有关,随着M、N的增加,图中寻找到L大小的环路概率 会趋于稳定。

下图是L=42时,随着M/N的比例变化,所能找到的环的概率。可以看到M=29 、31, N=2M,M/N = 50%,此时寻找到L=42的环的概率在1/42。

Cuckoo 图的Edge修剪和环路检测

通过计算节点的自由度,反复修剪小于2的边(永远不会成为循环的一部分),可以大幅度减少环路寻找算法所需的边数 。比如下图,先是可以把(2,15) (11,12) 的边剪掉,此时(10,11) (4,15) 又出现可以剪掉的条件,最后剩下右边的修剪完成对图,实现其边数减少了40%。

环路的检测是从第一条边开始,依次加入其他边,在没有环的时候会形成树结构;对新加入的边,根据深度选择一颗树,通过回溯根节点判断是否形成环路。对所有点边执行一次可以找到所有边相关的环路,并和目标参数比较,如果有相等长度的环路,即解决问题成功。

Grin的PoW运行流程

当处理完一个块后,可以得到其区块头,对区块头的哈希结合Cuckoo算法,寻找图中的环,并对找到的结果进行哈希和目标难度比较,当小于目标时,PoW工作量完成。其流程如下:

对新块头进行哈希处理以创建哈希值K。

哈希值K将用作SIPHASH函数的KEY,该函数将为图中的每个元素生成位置对。

通过剪边,执行Cuckoo循环检测算法试图在生成的图中找到解(即长度为42的循环)。

对找到的环进行Blake2b哈希并将其与当前目标难度进行比较。

如果哈希难度大于或等于目标难度,则将块广播到网络,并在下一个块开始工作。

如果没有找到解决方案,则将区块头中的Nounce增加1,并更新时间戳,以便下一次哈希值迭代。

 文章转载自QTUM官方:https://qtum.org/ru/post/qtum-cuckoo%20cycle 


上一篇: 什么是区块链虚拟机?为什么智能合约需要区块链虚拟机?
下一篇: 使用树莓派手机进行QTUM量子链POS挖矿的教程
推荐专栏
Boss Wallet Web3 Econom Pass
专注币圈最新资讯
通俗浅显地聊透Web3大事小情
读懂区块链生态与未来,尽在币界网!
热门币种
更多
币种
美元价格
24H涨跌幅
BTC比特币
60,963.61 USDT
¥435,103.38
-2.72%
ETH以太坊
3,368.69 USDT
¥24,042.67
-0.3%
BNB币安币
570.68 USDT
¥4,073.00
-0.28%
USDT泰达币
1.02 USDT
¥7.25
-0.19%
SOL
135.96 USDT
¥970.36
+7.66%
USDC
1.00 USDT
¥7.15
-0.01%
TON
7.59 USDT
¥54.14
+4.55%
XRP瑞波币
0.47720 USDT
¥3.41
+0.48%
DOGE狗狗币
0.12210 USDT
¥0.87140
+2.43%
ADA艾达币
0.39050 USDT
¥2.79
+3.88%
热搜币种
更多
币种
美元价格
24H涨跌幅
比特币
61034.17 USDT
¥443,407.14
-1.54%
Solana
137.36 USDT
¥997.91
-0.91%
Filecoin
4.3477 USDT
¥31.59
-2.19%
Curve
0.296 USDT
¥2.15
-6.71%
柚子
0.5733 USDT
¥4.16
-0.28%
Terra Classic
8.173E-5 USDT
¥0.00
-1.28%
Shiba Inu
1.72E-5 USDT
¥0.00
-3.75%
Conflux
0.1558 USDT
¥1.13
-1.64%
狗狗币
0.1223 USDT
¥0.89
-3.78%
dYdX
1.3774 USDT
¥10.01
-1.18%
Arweave
25.8768 USDT
¥187.99
-10.03%
Uniswap
9.2944 USDT
¥67.52
-2.17%
最新快讯
更多
新SwellrswETH池已上线Penpie
2024-06-27 11:34:46
Custodia要求上诉法院指示地区法院撤销对Custodia主账户的拒绝
2024-06-27 11:26:52
Custodia寻求法官撤回授权美联储拒绝其主账户申请的决定
2024-06-27 11:26:52
XT即将上线新一期鲨鱼鳍理财
2024-06-27 11:26:33
WEEX唯客将于7月1日开启第二期Launchpool,投入WXT瓜分37,000ZK
2024-06-27 11:25:57
币界网实时价格午报:PEPE站上0.000012722美元/枚,涨幅达3.03%
2024-06-27 11:23:47
数字资产银行Custodia寻求法官撤回授权美联储拒绝其主账户申请的决定
2024-06-27 11:22:40
下载币界网APP