Qtum研究院:Cuckoo Cycle演算法簡介

買賣虛擬貨幣
常見的POW演算法型別Grin的PoW演算法:Cuckoo Cycle Cuckoo Cycle問題

圖的一側是用奇數索引編號的陣列(最大為圖的大小),另一側用偶數索引編號。下面的簡單圖表就是這樣一個圖形,偶數側(頂部)有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工作量完成。其流程如下:

1. 對新塊頭進行雜湊處理以建立雜湊值K
2. 雜湊值K將用作SIPHASH函式的KEY,該函式將為圖中的每個元素生成位置對
3. 透過剪邊,執行Cuckoo迴圈檢測演算法試圖在生成的圖中找到解(即長度為42的迴圈)
4. 對找到的環進行Blake2b雜湊並將其與當前目標難度進行比較
5. 如果雜湊難度大於或等於目標難度,則將塊廣播到網路,並在下一個塊開始工作
6. 如果沒有找到解決方案,則將區塊頭中的Nounce增加1,並更新時間戳,以便下一次雜湊值迭代

免責聲明:

  1. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读

;