MimbleWimble是一種區(qū)塊鏈協(xié)議，依靠強大的加密原語提供極佳的可擴展性，隱私性和可替代性。MimbleWimble協(xié)議的項目主要目標和特點——隱私，這使得從交易的公開信息無法追蹤交易金額、發(fā)送方和接收方；采用Utxo刪減和最小化交易數(shù)量（《100字節(jié)內核），與其他區(qū)塊鏈相比節(jié)省大量空間；強大且經過驗證的密碼學， MimbleWimble只依賴于橢圓曲線密碼學，它已歷經數(shù)十年的嘗試和測試。近期出現(xiàn)以社區(qū)技術驅動的項目Grin使用新的PoW的Cuckoo Cycle算法鼓勵挖礦。

PoW共識最早由比特幣采用，也是區(qū)塊鏈最早使用的一種共識方法。目前為止PoW是容錯能力最好的公有鏈共識機制。公有鏈的安全基石是共識機制，PoW以物理算力為基礎，當鏈的算力達到一定規(guī)模后，像比特幣，由于必須擁有全網一半以上的算力（51%攻擊），這使得攻擊非常昂貴，在算力比較去中心化的時候，很難發(fā)生算力攻擊。

所以算法選型傾向于算力的分散化（抗并行挖礦算法）。這是通過使主存儲器延遲成為瓶頸來實現(xiàn)的，因為DRAM延遲保持相對穩(wěn)定，而CPU速度和存儲器帶寬在硬件架構和處理技術之間變化很大。

常見的POW算法類型

· 純hash類型的算法：隨機碰撞、計算困難

· Equihash類算法：廣義生日悖論問題、memory-hard

· ethhash：基于DAG解決約束、memory-hard

· Cuckoo Cycle：圖論式工作模式證明、memory-hard

而在此之上延伸出PoW的Cuckoo Cycle算法，該算法是一種更平等的共識方式，可以最大限度地降低硬件架構中的性能差異，并使硬件的開采具有成本效益。

Cuckoo Cycle是一種新穎的圖論理論算法設計，它結合了可擴展的內存需求和即時可驗證性。此外，它也是第一個設計運行時內存延遲主導。除非出現(xiàn)任何無法預料的內存時間權衡，否則它會產生近乎理想的內存限制工作證明，其商品硬件的成本效益可以極大地有利于礦業(yè)的分散化。

Cuckoo Cycle的一個有趣特性是制造ASIC并不符合成本效益。盡管如此，ASIC幾乎無法避免，因此在某些時候，用于Cuckoo循環(huán)的ASIC將變得可用。然而，即使發(fā)生這種情況，硬件制造商也無法在普通用戶上創(chuàng)建ASIC。

本文主要介紹 Grin 采用的 PoW 共識算法 —— Cuckoo Cycle。

Grin的PoW算法：Cuckoo Cycle

Grin的基本Proof-of-Work算法稱為Cuckoo Cycle，2014年由John Tromp 發(fā)明。它主要是一種內存約束算法，意味著解決方案時間受內存帶寬而非原始處理器或GPU速度的約束。 因此，Cuckoo Cycle的解決方案應該在大多數(shù)商品硬件上都是可行的。 Grin 引入了兩種POW算法。主要算法是被設計為 ASIC 友好的，而次要算法是抗 ASIC 的。在最初發(fā)布時，Grin 挖礦從最初抗ASIC 逐漸過渡到對ASIC友好。

網絡啟動時90% 的區(qū)塊將會被次要算法挖出，而主要算法只會挖出大約 10% 的區(qū)塊。主要算法稱為Cuckatoo31+，次要算法Cuckaroo29 ，Cuckaroo29抗ASIC是通過每6個月改變一次算法來實現(xiàn)的。

Cuckoo Cycle問題

Cuckoo Cycle問題是指從Cuckoo圖中找到一個L長度的環(huán)。Cuckoo圖是一個二分圖， 其中邊（即連接節(jié)點的線）僅在2個單獨的節(jié)點組之間連接的圖。由N個節(jié)點和M個邊組成， 節(jié)點采用Cuckoo散列表表示。

圖的一側是用奇數(shù)索引編號的數(shù)組（最大為圖的大小），另一側用偶數(shù)索引編號。下面的簡單圖表就是這樣一個圖形，偶數(shù)側（頂部）有4個節(jié)點，奇數(shù)側（底部）有4個節(jié)點，4條邊。

Cuckoo Cycle的存在概率

要保證POW的工作量證明的安全性和公平性，意味著需要所有參與方無法通過某種方法來提高解決問題的概率。Cuckoo Cycle存在的概率，和圖的節(jié)點多少，邊的多少有關，隨著M、N的增加，圖中尋找到L大小的環(huán)路概率 會趨于穩(wěn)定。

下圖是L=42時，隨著M/N的比例變化，所能找到的環(huán)的概率?？梢钥吹組=29 、31， N=2M，M/N = 50%，此時尋找到L=42的環(huán)的概率在1/42。

Cuckoo 圖的Edge修剪和環(huán)路檢測

通過計算節(jié)點的自由度，反復修剪小于2的邊（永遠不會成為循環(huán)的一部分），可以大幅度減少環(huán)路尋找算法所需的邊數(shù) 。比如下圖，先是可以把（2，15） （11，12） 的邊剪掉，此時（10，11） （4，15） 又出現(xiàn)可以剪掉的條件，最后剩下右邊的修剪完成對圖，實現(xiàn)其邊數(shù)減少了40%。

環(huán)路的檢測是從第一條邊開始，依次加入其他邊，在沒有環(huán)的時候會形成樹結構；對新加入的邊，根據(jù)深度選擇一顆樹，通過回溯根節(jié)點判斷是否形成環(huán)路。對所有點邊執(zhí)行一次可以找到所有邊相關的環(huán)路，并和目標參數(shù)比較，如果有相等長度的環(huán)路，即解決問題成功。

Grin的PoW運行流程

當處理完一個塊后，可以得到其區(qū)塊頭，對區(qū)塊頭的哈希結合Cuckoo算法，尋找圖中的環(huán)，并對找到的結果進行哈希和目標難度比較，當小于目標時，PoW工作量完成。其流程如下：

1. 對新塊頭進行哈希處理以創(chuàng)建哈希值K

2. 哈希值K將用作SIPHASH函數(shù)的KEY，該函數(shù)將為圖中的每個元素生成位置對

3. 通過剪邊，執(zhí)行Cuckoo循環(huán)檢測算法試圖在生成的圖中找到解（即長度為42的循環(huán)）

4. 對找到的環(huán)進行Blake2b哈希并將其與當前目標難度進行比較

5. 如果哈希難度大于或等于目標難度，則將塊廣播到網絡，并在下一個塊開始工作

6. 如果沒有找到解決方案，則將區(qū)塊頭中的Nounce增加1，并更新時間戳，以便下一次哈希值迭代