為何我們需要一個非重複亂數生成的算法？
NFT 在開盲盒的時候，我們需要一個公平的方法。而所謂的 “公平” 意指：假定目前整個專案還有 100 個盲盒尚未被人購買則公平的方法應該要使得每一個盲盒被選中的機率應該要是一樣的。當持續抽下去時，那些出現過被抽走的盲盒號碼不應該給予之後開箱的使用者，並且依然要保持公平的機率。
一個解決這個問題的作法，是將所有的盲盒做編號，比方說從 1 到 200。此時若是存在一個非重複的亂數公平生成器則可以輕易解決。
基本思路：
在區塊鏈中，隨機亂數的生成不是一個簡單的問題。目前業界可以選擇的解法通常有以下三種：
- 使用 Verifiable delay function 去構造亂數生成器。
- 使用 ChainLink 提供的服務，當作隨機亂數的 oracle 使用。
- 使用最新 block 的 data ，當作隨機種子，再透過 keccak256 做 Hash 後的產物轉型成 uint256，當成使用的隨機數。
PS：這三種方法的優劣比較，將會再開專文做仔細的討論。
以上三種方法，所提供的亂數是可能產生相同隨機數。因此我們需要透過一些算法將重複的數字給移除並且確保機率的一致性。接下來為了問題簡單化，假定
存在一個可重複的公平隨機亂數生成器 G(N) 範圍從 {1, …,N}。每一個在 1 到 N 的數字出現的機率皆為 1/ N。
從這個假設為前提，產生不重複數字的公平亂數生成器有算法：Fisher–Yates shuffle。
Fisher–Yates shuffle：
此方法是業界都採用的方法。它的優點是實作邏輯簡單。我們使用一個例子為此算法做講解：
- 一開始假設有 5 個數字：
此時使用亂數生成器 G(5)，假設生成的數字是 3 ，則我們就當這次選取的數字為位置為 3 的數字，也剛好也就是 3。
接下來，我們將抽取後的狀態更新為(i.e. 將 3 和 5 的位置交換。利用 3 已經被抽取過，將其跟 5 做交換後，透過將下次亂數的範圍縮減 1，可以自動把 3 給排除)：
2. 使用亂數生成器 G(4)，假設生成的數字是 4，則產生的亂數便是 4。則狀態可更新成（i.e. 因為現在剩下 4 個數字，因此 1、2、5、4 抽到的機率應該為 1/4）下圖：
此時尚未被抽走的數字為 1、2、5。
3. 使用亂數生成器 G(3)，假設生成的數字是 1，則產生的亂數便是 1。同樣的將抽過的數字跟最後一個數字做位置交換。
此時狀態更新為：
4. 使用亂數生成器 G(2)，假設生成的數字是 2，則產生的亂數便是 2。
5. 最後 G(1)，生成的數字只能是 1，則產生的亂數是 5。
結論：
- 每次抽取到每個數字的機率都是相同的。
機率從 1/5 -> 1/4 -> 1/3 -> 1/2 -> 1。 - 根據上面的例子，抽取五次的給出的亂數依序為：3，4，1，2，5（i.e. 從圖中陣列由後往前依序讀出）。
以上的演算法，可以透過利用 map 去紀錄每一個格子目前的數字狀態。在每一次的抽取後更新狀態。參考程式碼 (ref. Astro gator 鱷魚)如下：
uint256 public remaining; mapping(uint256 => uint256) public cache; function drawIndex() internal returns (uint256 index) {
//RNG
uint256 i = uint(blockhash(block.number - 1)) % remaining; // if there's a cache at cache[i] then use it
// otherwise use i itself
index = cache[i] == 0 ? i : cache[i]; // grab a number from the tail
cache[i] = cache[remaining - 1] == 0 ? remaining - 1 : cache[remaining - 1];
remaining = remaining - 1;
}
這個方法巧妙又簡單。但是每一次抽取的時候，都有很大機會要一個新的 storage slot 去紀錄抽取的新數字。這個動作所需要的開銷不低，是要 20000 Gas 的消耗。同時還有更新狀態所需要的 Gas 消耗，因此每次 call 這個函數所需要消耗的 Gas 數量是四萬到五萬之間。
因此產生了一個自然的問題，有沒有消耗更少 Gas 的演算法，可以達到相同的目的？在區塊鏈中，越低 Gas 的算法，越有經濟效益，因為這使得所需的手續費更低。因此為了降低客戶使用的成本，AMIS 團隊開始研究這個問題。
AMIS 的 Solution ：
經過團隊不斷地研究，AMIS 發現一個方法可以在更少 Gas 的消耗下，解決以上的問題。AMIS 的方案是整合以下的三個概念：
- 減少儲存消耗。每一個 uint256 的數字，因為有 256 bit 因此可以記錄 256 個物品的狀態。比方說，可以透過第 n 個 bit 的狀態來記錄這個編號的盲盒有沒有被抽過：如果是 1 則代表抽過，反之是 0 則代表還沒抽過。
- 使用 Reject Sampling 去亂數抽取。此方法概念是：假設一開始共有一千個物品。則每個物品被抽到的機率是 1/1000。假設抽到已經抽過的數字，則重新再抽一次直到抽到沒有抽中的數字。顯而易見的是此方法是公平的方法。而此方法最大的缺點是當大多數的數字都被抽取後，便很難抽到沒有抽中的數字。因此需要其他方法去處理剩下的數字。
- 使用 Naive 的方法去抽取亂數。此方法的概念如下：
假設有七個物品，目前已抽取過三次，分別抽出的為編號：2、4、5。剩下還可以抽取的為：1、3、6、7。由於只剩下 4 個盲盒，此時使用亂數生成器 G(4)。如果產生的數字為 2 則輸出數字 3。如果是數字 4 則數字為 7。因此根據綠色的數字標號，給出輸出。顯而易見的是此方法是公平的方法。我們會使用此方法去處理剩下的數字。
實作的難點：
整個問題的實作難點是在於方法 3。我們需要知道每一個 uint256 的數字裡面的狀態，需要有一個能消耗很低 Gas 的方法去搜索到指定的位置。比方說在上述例子，假設亂數產生的數字是 4 ，則我們要知道其實它在真正的位置是 7。若是使用 for 迴圈做一個一個檢查每一個 bit 的狀態，所需要消耗的 Gas 是非常恐怖的。
為了解決此難點，首先，我們考慮以下的問題：
給定一個 uint256 的數字，以二進位的眼光來看，存在多少個 bit 為 1 ？
對於上述粗體字所述，在 1960 年，IBM 有一個優雅的解法：
假設有一個 32 bit 的數字，如圖的第一行。
- 此時每 2 個相鄰相加得到第二行，並且將結果以二進位表示。在例子中10 -> 算出來是 1，因此表為 01。下一個數字是 11 ->算出來是 2，因此標為 10。接下來從左到右依此類推。
- 接著第二行的結果，一樣的兩個兩個一組相加，得到第三行。比方說在最左邊的第一二組，分別是 01 和 10，相加就是 3，以二進位表法是 11。
- 依此類推得到的最後結果是 10111，所代表的數量是：16+4+2+1 = 23 個 1。
整個運算可以透過 binary operation 完成，所以是一個有效率的算法。
透過這個演算法再加上 binary search 的概念，便可以給出所考慮問題的一個解法。我們用一個例子闡釋其概念。
假設
- 現在有 256 個物品， 要找第 150 個位置。
- 目前紀錄的 uint256 的數字為 5。換句話說，編號 1 和編號 3 的盲盒已經被抽走。
首先可以簡單地知道這個問題答案應該是第 152 個 bit。
而我們的算法概念如下：
- 首先將 5 與 2¹²⁸ — 1(i.e. 以二進位來看此數有 128 個 1) 做 AND 會得到結果 5，這時候透過上面的演算法會得到在前 128 位置中只有 2 個 1，換句話說可用的空間只有 126 個位置。
- 因為 150 > 126，此時再將 5 與 2¹²⁸+….+2¹⁹¹ 做 AND 會得到 0，透過上面的演算法會得到在 129 位置到 192 位置中共有 64 個 0。
- 因為 126+64 > 150，因此接下來考慮 5 跟數字 2¹²⁸+….+2¹⁵⁹ 做 AND 會得到 0，透過上面的演算法會得到在 129 位置到 160 位置中共有 32個 0。
- 126+32 > 150，因此接下來考慮 5 跟數字 2¹²⁸+…. +2¹⁴³ 做 AND 會得到 0，透過上面的演算法會得到在129 位置到 144 位置中共有 16個 0。
- 150>126+16=142，因此接下來考慮 5 跟數字 2¹⁴⁴+….+2¹⁵¹ 做 AND 會得到 0，透過上面的演算法會得到在在 145 位置到 152 位置中共有 8 個 0。
- 142+8 = 150，此時便可以知道，位置在 152。
PS：在實作，我們在第六步，如果遇到相等的情況下，會繼續依照相同邏輯做下去，故位置將會累加到 144+4+2 =150 ，直到最後一步如果算出來：142+4+2+1 < 150，則會將其加 2 （i.e. 因此位置為 150+2=152）。
最後，每 256 個數量我們都可以用一個 uint256 去紀錄抽取的狀況。因此當盲盒的數量大於 256 個，則只要用多個數字去紀錄即可。
結果比較 （Joint Work with Ian Liu）：
我們將 AMIS 所整合的方法和 Fisher–Yates shuffle 做比較，可以發現我們大幅地減低 Gas 使用量。不過隨著 Mint 總量的增加，AMIS 所提出的方法，會漸漸的在某些情況失去優勢。這是因為在方法 3，我們會用到多個 uint 256 的數字去記錄物品的狀態，隨著 uint256 使用的數量提高，搜索範圍會提高，因此消耗也會變高。
- cyRamdom 指的是 AMIS 的算法
- random 指的是 Fisher–Yates shuffle
- 後面點綴的數字 Five，One，Three 指的是：一次連續 mint 1、3、5 個。在實務的情況，用戶可能會一次買多個盲盒，因此會需要一次產生多個非重複亂數的情況。
Case 1. 總共 mint 255 個：
在方法 cyRandomOne 和 randomOne中，可以觀察出，每生一個非重複亂數，後者的方法比前者多花接近 10000 的 Gas。並且在最糟的情況， AMIS 的方法是 56691，但是 Fisher–Yates shuffle 所消耗的最差情況是 58677。而在同時 mint 3 個和 5 個，AMIS 的算法有顯著的優勢。
Case 2. 總共 mint 525 個：
在方法 cyRandomOne 和 randomOne中，可以觀察出，每生一個非重複亂數，後者的方法比前者多花接近 8400 多的 Gas。並且在最糟的情況， AMIS 的方法是 56691，但是 Fisher–Yates shuffle 所消耗的最差情況是 58677。而在同時 mint 3 個和 5 個，AMIS 的算法有顯著的優勢。
Case 3. 總共 mint 1000 個：
在方法 cyRandomOne 和 randomOne中，可以觀察出，每生一個非重複亂數，後者的方法比前者多花接近 7600多的 Gas。並且在最糟的情況， AMIS 的方法是 63401，但是 Fisher–Yates shuffle 所消耗的最差情況是 58677 (i.e. 開始略多於 Fisher–Yates shuffle)。而在同時 mint 3 個和 5 個，AMIS 的算法有顯著的優勢。
PS：智能合約的程式碼將會在 audit 以後公開。
結論：
在 solidity 裡最貴的動作是存取到 storage slot。 第一次寫入 storage slot 會是最貴的(i.e. 20000 Gas)，之後重複讀取或寫入所消耗的 Gas 雖然會少很多，但是相比於其他運算仍然是比較昂貴的動作。在 Fisher–Yates shuffle 裡，因為每一個亂數生成基本上就是要一個新的 storage slot。 而我們的方法每 256 個才用一個 storage slot，因此產生減少 Gas 消耗的可能性。雖然我們的算法運算量較大，但是我們採用大量的 binary operation 並且盡量的避免使用迴圈，所以使得總消耗比較少。此外，可觀察當我們的作法如果隨機到的值是在同一個 storage slot 時便可以省 Gas，所以在 mint 多個時會更顯優勢。
最後，當隨著 mint 的總數量大於 3000 個以上，Fisher–Yates shuffle 方法的優勢會顯現出來，它的最差情況還是會在五萬多。但是我們的方法在最差情況會被拔高。但是以平均來說 AMIS 的方法還是比較節省。
在智能合約實作中，如何減少 Gas 的消耗，不但是考驗團隊的功力和其研究精神。在開發的過程中，test case 的撰寫和一些合約上 Gas 消耗的眉眉角角都是需要經驗的。在這邊我們拋磚引玉的提出一個目前沒看到其他團隊使用的非重複亂數的生成算法，除了希冀有人更精進這個算法之外，更讓大家知道 AMIS 團隊開發合約除了正確性，也會仔細的斤斤計較的研究如何讓 Gas 消耗成本達到最低。
Reference:
Thanks to Ian Liu, Cara Shen, Alan Chen, and Yu-Te Lin.
文章作者：ChihYun Chuang
原文連結
