一個使用更少 Gas 的非重複亂數的生成算法

為何我們需要一個非重複亂數生成的算法？

NFT 在開盲盒的時候，我們需要一個公平的方法。而所謂的 “公平” 意指：假定目前整個專案還有 100 個盲盒尚未被人購買，則公平的方法應該要使得每一個盲盒被選中的機率應該要是一樣的。

當持續抽下去時，那些出現過被抽走的盲盒號碼不應該給予之後開箱的使用者，並且依然要保持公平的機率。一個解決這個問題的作法，是將所有的盲盒做編號，比方說從 1 到 200。此時若是存在一個非重複的亂數公平生成器則可以輕易解決。

基本思路

在區塊鏈中，隨機亂數的生成不是一個簡單的問題。目前業界可以選擇的解法通常有以下三種：

• 使用 Verifiable delay function 去構造亂數生成器。
• 使用 ChainLink 提供的服務，當作隨機亂數的 oracle 使用。
• 使用最新 block 的 data，當作隨機種子，再透過 keccak256 做 Hash 後的產物轉型成 uint256，當成使用的隨機數。

（註：這三種方法的優劣比較，將會再開專文做仔細的討論。）

以上三種方法，所提供的亂數是可能產生相同隨機數。因此我們需要透過一些算法將重複的數字給移除並且確保機率的一致性。接下來為了問題簡單化，假定：存在一個可重複的公平隨機亂數生成器 G(N) 範圍從 {1, …,N}。每一個在 1 到 N 的數字出現的機率皆為 1/N。

從這個假設為前提，產生不重複數字的公平亂數生成器有算法：Fisher–Yates shuffle。

Fisher–Yates shuffle

此方法是業界都採用的方法。它的優點是實作邏輯簡單。我們使用一個例子為此算法做講解。一開始假設有 5 個數字：

1. 此時使用亂數生成器 G(5)，假設生成的數字是 3，則我們就當這次選取的數字為位置為 3 的數字，也剛好也就是 3。接下來，我們將抽取後的狀態更新為（將 3 和 5 的位置交換。利用 3 已經被抽取過，將其跟 5 做交換後，透過將下次亂數的範圍縮減 1，可以自動把 3 給排除）。
2. 使用亂數生成器 G(4)，假設生成的數字是 4，則產生的亂數便是 4。則狀態可更新（因為現在剩下 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。

以上的演算法，可以透過利用 map 去紀錄每一個格子目前的數字狀態。在每一次的抽取後更新狀態。參考程式碼如下：

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 有一個優雅的解法：透過將相鄰的 bit 兩兩相加，再不斷依序對半組合相加。整個運算可以透過 binary operation 完成，所以是一個有效率的算法。

透過這個演算法再加上 binary search 的概念，便可以給出所考慮問題的一個解法。我們用一個例子闡釋其概念。假設現在有 256 個物品， 要找第 150 個位置；目前紀錄的 uint256 的數字為 5（換句話說，編號 1 和編號 3 的盲盒已經被抽走）。

1. 首先將 5 與 2¹²⁸ - 1 做 AND 會得到結果 5，這時候透過上面的演算法會得到在前 128 位置中只有 2 個 1，換句話說可用的空間只有 126 個位置。
2. 因為 150 > 126，此時再將 5 與 2¹²⁸+...+2¹⁹¹ 做 AND 會得到 0，透過演算法得知 129 到 192 位置中有 64 個 0。
3. 因為 126+64 > 150，接下來考慮 5 跟數字 2¹²⁸+...+2¹⁵⁹ 做 AND 會得到 0，得知 129 到 160 位置中有 32 個 0。
4. 以此類推，利用對半切的方式（Binary Search），最終可以精準且低消耗地定位出第 150 個可用的位置是在 152。

最後，每 256 個數量我們都可以用一個 uint256 去紀錄抽取的狀況。因此當盲盒的數量大於 256 個，則只要用多個數字去紀錄即可。

結論

在 Solidity 裡最貴的動作是存取到 storage slot。第一次寫入 storage slot 會是最貴的（20000 Gas），之後重複讀取或寫入所消耗的 Gas 雖然會少很多，但是相比於其他運算仍然是比較昂貴的動作。

在 Fisher–Yates shuffle 裡，因為每一個亂數生成基本上就是要一個新的 storage slot。而我們的方法每 256 個才用一個 storage slot，因此產生減少 Gas 消耗的可能性。雖然我們的算法運算量較大，但是我們採用大量的 binary operation 並且盡量的避免使用迴圈，所以使得總消耗比較少。此外，可觀察當我們的作法如果隨機到的值是在同一個 storage slot 時便可以省 Gas，所以在 mint 多個時會更顯優勢。

在智能合約實作中，如何減少 Gas 的消耗，不但是考驗團隊的功力和其研究精神。在開發的過程中，test case 的撰寫和一些合約上 Gas 消耗的眉眉角角都是需要經驗的。在這邊我們拋磚引玉的提出一個目前沒看到其他團隊使用的非重複亂數的生成算法，除了希冀有人更精進這個算法之外，更讓大家知道 AMIS 團隊開發合約除了正確性，也會仔細的斤斤計較的研究如何讓 Gas 消耗成本達到最低。

Thanks to Ian Liu, Cara Shen, Alan Chen, and Yu-Te Lin.

ChihYun Chuang

Cryptography Researcher @ AMIS

ChihYun is a cryptography researcher specializing in Multi-Party Computation (MPC) and Threshold Signature Schemes (TSS). He is dedicated to building robust and secure infrastructure for decentralized finance.