PoW consensus最早由比特币采用，也是区块链使用的第一种共识方法。迄今为止，PoW是容错性最好的公链共识机制。公链安全的基石是共识机制。功率是基于物理计算能力。当链的计算能力达到一定规模，像比特币一样，因为必须拥有全网一半以上的计算能力(51%攻击)，所以攻击的代价非常大。当计算能力分散时，计算能力攻击很难发生。

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

常见的PoW算法类型：

纯hash算法：随机碰撞，计算困难

Equihash算法：广义生日悖论问题，memory-hard

ethhash:基于DAG的约束求解，Memory-hard

Cu hash Memory-hard

并在此基础上扩展了POW的布谷鸟循环算法。该算法是一种更加平等的一致性方式，可以最小化硬件架构中的性能差异，使得硬件的开发更具成本效益。

Cuckoo Cycle是一种基于图论的新颖算法设计，结合了可扩展的内存需求和即时可验证性。此外，它也是第一个设计运行时内存延迟占主导地位。除非有什么意外的内存时间权衡，否则会产生近蓑衣网小编2022乎理想的内存限制，其商品硬件的性价比可以大大有利于矿业的去中心化。

布谷鸟周期的一个有趣特点是制造ASIC不划算。尽管如此，ASIC几乎是不可避免的，所以在某个时候，用于布谷鸟周期的ASIC将变得可用。但是，即使出现这种情况，硬件厂商也无法在普通用户身上打造ASIC。

格林& # 039；s幂算法：布谷鸟循环

Grin & # 039；的基本工作证明算法被称为布谷鸟循环(Cuckoo Cycle)，由约翰特罗姆普(John Tromp)于2014年发明。它主要是一种内存约束算法，也就是说求解时间受内存带宽的约束，而不是受原处理器或GPU速度的约束。所以布谷鸟周期的解决方案在大多数商品硬件上应该是可行的。Grin引入了两种幂算法。主算法被设计成ASIC友好的，而辅助算法是抗ASIC的。在最初的版本中，Grin mining逐渐从抗ASIC转变为ASIC友好。

网蓑衣网小编2022络启动时，次级算法会挖出90%的块，而主算法只会挖出10%左右的块。主算法叫Cuckatoo31，副算法cuccaroo29，cuccaroo29的反ASIC是每半年换一次算法实现的。

布谷鸟循环问题

布谷鸟循环问题是指从布谷鸟图中找出一个长度为L的回路。布谷鸟图是一个二分图，其中边(即连接节点的线)仅在两个独立的节点组之间连接。它由n个节点和m条边组成，节点用Cuckoo哈希表表示。

图的一边是奇数索引号的数组(最大值是图的大小)，另一边是偶数索引号的数组。下面这个简单的图就是这样一个图。偶数边(顶部)有4个节点，奇数边(底部)有4个节点和4条边。

布谷鸟循环的存在概率

为了保证POW的工作量证明的安全性和公平性，意味着所有参与者不能通过某种方法提高解决问题的概率。布谷鸟圈的存在概率与图的节点数和边数有关。随着m和n的增加，在一个图中找到一个L大小的回路的概率趋于稳定。

下图是当L=42时，随着M/N的比值的变化，能找到环的概率。可以看出，M=29，31，N=2M，M/N=50%。此时找到L=42的环的概率是1/42。布谷鸟图

边修剪和回路检测

通过计算节点的自由度，反复修剪小于2的边(这些边永远不会是回路的一部分)，可以大大减少回路查找算法所需的边数。 比如下图，首先可以把(2，15) (11，12)的边切掉，然后再把(10，11) (4，15)切掉。最后留下右侧的修剪，完成图形的对齐，减少了40%的边数。

循环的检测从第一条边开始，然后依次添加其他边，没有循环时会形成树形结构；对于新增的边，根据深度选择一棵树，通过回溯根节点判断是否形成回路。可以为所有边找到一次所有边相关的环，并与目标参数进行比较。如果有等长的循环，问题就成功解决了。

格林& # 039；s PoW运行进程

当一个块被处理时，可以获得它的块头。将块头的hash与Cuckoo算法相结合，寻找图中的环，并对找到的结果的hash和目标难度进行比较。当它小于目标值时，PoW工作负载完成。过程如下：

Hash新的块头创建一个Hash值K

Hash值K将作为SIPHASH函数的KEY，它将为图中的每个元素生成位置对。

通过修剪边，执行布谷鸟循环检测算法以试图在生成的图中找到解决方案(即，长度为42的循环)。

Blake2b散列找到的环，与当前目标难度进行比较。

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

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

？文章转载自QTUM官方：https://qtum.org/ru/post/qtum-cuckoo循环？