圖的一側是用奇數索引編號的陣列(最大為圖的大小),另一側用偶數索引編號。下面的簡單圖表就是這樣一個圖形,偶數側(頂部)有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,並更新時間戳,以便下一次雜湊值迭代