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

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

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

常見(jiàn)的POW算法類型

· 純hash類型的算法：隨機(jī)碰撞、計(jì)算困難

· Equihash類算法：廣義生日悖論問(wèn)題、memory-hard

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

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

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

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

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

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

Grin的PoW算法：Cuckoo Cycle

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

網(wǎng)絡(luò)啟動(dòng)時(shí)90% 的區(qū)塊將會(huì)被次要算法挖出，而主要算法只會(huì)挖出大約 10% 的區(qū)塊。主要算法稱為Cuckatoo31+，次要算法Cuckaroo29 ，Cuckaroo29抗ASIC是通過(guò)每6個(gè)月改變一次算法來(lái)實(shí)現(xiàn)的。

Cuckoo Cycle問(wèn)題

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

圖的一側(cè)是用奇數(shù)索引編號(hào)的數(shù)組（最大為圖的大?。硪粋?cè)用偶數(shù)索引編號(hào)。下面的簡(jiǎn)單圖表就是這樣一個(gè)圖形，偶數(shù)側(cè)（頂部）有4個(gè)節(jié)點(diǎn)，奇數(shù)側(cè)（底部）有4個(gè)節(jié)點(diǎn)，4條邊。

Cuckoo Cycle的存在概率

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

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

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

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

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

Grin的PoW運(yùn)行流程

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

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

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

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

4. 對(duì)找到的環(huán)進(jìn)行Blake2b哈希并將其與當(dāng)前目標(biāo)難度進(jìn)行比較

5. 如果哈希難度大于或等于目標(biāo)難度，則將塊廣播到網(wǎng)絡(luò)，并在下一個(gè)塊開(kāi)始工作

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