位元幣原始碼分析--深入理解區塊鏈 3.高安全的亂數生成器

計算機程式中使用亂數是常見的，常用來做資料校驗、密碼或其他安全用途，比如很多短信驗證碼就是6位數的亂數字，之所以一般是6位因為要考慮用戶的記憶和輸入方便，太長了用戶記不住輸入也不方便，它可以結合驗證碼的時效和對應的手機號碼來提高安全性，但在Bitcoin中，這種有限長度的數字作為亂數，在強大的算力面前分分鐘被破解，作為Bitcoin的亂數生成器（RNG）使用了大量高強度的亂數來提高系統安全，亂數的核心的應用就是錢包（wallet）系統的私鑰（有關錢包系統在以后的章節中會介紹），私鑰是一個長度為64的十六進制字串（32個位元組，256位），為了保證安全，系統必須保證亂數不被猜中而且是唯一的，對于Bitcoin這種開放、幾乎人人皆可隨時訪問的區塊鏈資料庫，其中錢包系統的安全等級最高，它要求在現有的運算條件下對私鑰的破解概率降低到幾乎是零，因為一旦私鑰遭破解就可以操控錢包賬戶的一切資金，要做到這樣的高安全就必須保證隨機生成的私鑰有最安全的熵源，

計算機中的常用的亂數我們通常稱之為偽亂數(Pseudo-random)，它不是真正的隨機，而是按照某種統計學演算法生成的，在C++語言中很多生成亂數的函式，比如：srand、rand等，但這些遠不能滿足Bitcoin安全的需求，這些函式幾乎排除在Bitcoin能使用的函式之外，熵作為混亂程度的度量，熵源可以理解為計算亂數的資料來源，必須保證這些資料是高度混亂的、不規律的，以確保攻擊者無法預測和破解，

關于熵

維基百科中關于熵是這樣解釋的：在資訊論中，熵（entropy）是接收的每條訊息中包含的資訊的平均量，又被稱為資訊熵、信源熵、平均自資訊量，這里，“訊息”代表來自分布或資料流中的事件、樣本或特征，（熵最好理解為不確定性的量度而不是確定性的量度，因為越隨機的信源的熵越大，）來自信源的另一個特征是樣本的概率分布，熵的概念最早起源于物理學，用于度量一個熱力學系統的無序程度，在資訊論里面，熵是對不確定性的測量，但是在資訊世界，熵越高，則能傳輸越多的資訊，熵越低，則意味著傳輸的資訊越少，

位元幣亂數生成器和熵源的設計

Bitcoin中隨機資料生成的主要函式代碼（注釋有對應的檔案名）：

// https://github.com/bitcoin/bitcoin/blob/master/src/random.cpp
static void ProcRand(unsigned char* out, int num, RNGLevel level) noexcept
{
    // Make sure the RNG is initialized first (as all Seed* function possibly need hwrand to be available).
    RNGState& rng = GetRNGState();

    assert(num <= 32);

    CSHA512 hasher;
    switch (level) {
    case RNGLevel::FAST:
        SeedFast(hasher);
        break;
    case RNGLevel::SLOW:
        SeedSlow(hasher, rng);
        break;
    case RNGLevel::PERIODIC:
        SeedPeriodic(hasher, rng);
        break;
    }

    // Combine with and update state
    if (!rng.MixExtract(out, num, std::move(hasher), false)) {
        // On the first invocation, also seed with SeedStartup().
        CSHA512 startup_hasher;
        SeedStartup(startup_hasher, rng);
        rng.MixExtract(out, num, std::move(startup_hasher), true);
    }
}

下面分別說明三種級別的亂數以及熵源設計：

1.RNGLevel::FAST

顧名思義就是比較快速生成亂數，計算時間相對短，復雜程度相對低，構造流程如下圖：

1. Stack pointer： 使用了一個32位元組長度的buffer在堆疊中的地址，該地址長度一般為8位元組，注意是buffer的堆疊地址，而不是buffer本身的值，堆疊地址是高度隨機且外部用戶無法獲取的安全地址，
2. SeedHardwareFast：呼叫GetRdRand從芯片上的硬體亂數生成器中獲取亂數，所用到的亂數生成器由芯片上的熵池初始化，在呼叫之前，首先在亂數生成器RNGState的初始化中呼叫InitHardwareRand來判斷CPU處理器是否支持RDRAND和RDSEED指令，RDSEED和RDRAND提供了訪問硬體熵池的高級方法，功能比較類似，它們都是計算機的硬體指令，其中RDSEED指令的熵來自時序線路，并且使用硅片上的熱噪聲來以3GHz的速度輸出隨機位元流，在Linux C++中，使用行內的匯編指令來完成這些指令呼叫，
3. SeedTimestamp：呼叫GetPerformanceCounter來讀取CPU時間計數器，回傳一個無符號的64位整數，該數字同樣具有高度隨機性和不可預測性，
4. MixExtract：混合熵并計算512位的哈希值，首先在熵中混合上一次計算的Hash值，同時混合一個64位的無符號計數器，然后計算Hash-512，并將計算結果保存在m_state中供下一次使用，
5. SeedStartup: 繼續構造亂數的熵源，上面步驟構造的熵源已經在暫存在m_state中，該函式繼續執行SeedHardwareSlow，它與SeedHardwareFast類似，加入了RNDSEED亂數，熵源包括：SeedSlow（在下面介紹）、RandAddDynamicEnv動態的環境變數資料，RandAddStaticEnv靜態的環境變數資料、SeedStrengthen執行10毫秒強度的哈希運算并混合熵源，其中SeedStartup只執行一次，
6. MixExtract：再次混合熵源并計算哈希值，

通過上述復雜和多重混合計算，其目的是為了構造一個高度隨機且無法預測的熵源種子亂數，最后通過計算熵源的512位的哈希值獲得指定長度的隨機值（最長64個位元組），且每一次計算都是根據上一次計算的結果再進行混合并不斷累積，從而使資訊熵越來越高，隨機值也越趨安全，

2. RNGLevel::SLOW

計算時間較長，較復雜，混合的熵源比較多，如下圖：

它在SeedFast的基礎上增加了：

• GetOSRand：用于獲取系統設設備的亂數
• SeedEvents：它是RNGState中根據隨機事件來混合熵源，當系統連接到一個新的節點時，呼叫RandAddEvent函式器混合一個32位無符號的的節點id，其目的是系統在運行程序中動態混合一些新的隨機種子，以提高資訊源的熵強度，從而提高亂數的安全性，

3.RNGLevel::PERIODIC

系統會周期（每隔一分鐘）呼叫RandAddPeriodic，從而不斷進行哈希運算和累積熵，從而提高熵的不確定性和安全性，如下圖(藍色背景部分為代碼)：

它與SLOW和FAST區別是增加了SeedStrengthen，其用意是根據CPU的時鐘來加熵的強度，這三種級別的演算法不是獨立的，而是相互關聯的，?并且不斷累積熵源，?

快速亂數(FastRandomContext)

相對于錢包私鑰使用的亂數需要很高的密碼安全特性，一般的亂數，如使用亂數來命名檔案就不需要經過上述那么復雜的運算，因此Bitcoin中針對這些開發了快速亂數的演算法，如下圖所示：

快速亂數生成器有兩個主要函式rand256和randbytes，rand256獲取256位長度的亂數，randbytes獲取指定位元組長度的亂數（不超過64個位元組數），與上面介紹的通過熵源構造的亂數生成器RNGState不同的是，快速亂數使用了ChaCha20（一種新型的流密碼演算法）偽隨機的密鑰流(keystream)的演算法，通過/src/random.cpp的代碼得知，在FastRandomContext的建構式中，通過對chacha20設定key來計算keystream，默認情況下，必須首先請求RandomSeed來獲取一個key，該key通過RNGState來獲取，如果用戶在構造FastRandomContext時設定了key，則不需要通過定RandomSeed來獲得key，Key值是ChaCha20演算法計算keystream的基礎（關于ChaCha20演算法在后面的章節介紹），

下面的代碼是FastRandomContext的兩個建構式：

FastRandomContext::FastRandomContext(bool fDeterministic) noexcept : 
requires_seed(!fDeterministic), bytebuf_size(0), bitbuf_size(0)
{
    if (!fDeterministic) {
        return;
    }
    uint256 seed;
    rng.SetKey(seed.begin(), 32);
}

FastRandomContext::FastRandomContext(const uint256& seed) noexcept : requires_seed(false), bytebuf_size(0), bitbuf_size(0)
{
    rng.SetKey(seed.begin(), 32);
}

第一個建構式表示需要RandomSeed來設定key，第二個建構式表明用戶指定了key?，這里的uint256是一個256位32位元組長度的uint8_t型別的陣列，

使用SHA-512獲取隨機值

Bitcoin系統中獲取高安全亂數，其中錢包系統的256位私鑰，都是通過復雜的計算和混合不同的隨機資料來獲得高度混亂和不可預測的熵源，并最終計算它的SHA-512來獲得隨機值，該隨機值具有很高的密碼安全性，使黑客攻擊變得幾乎不可能，有關SHA-512的演算法在后面的章節再介紹，需注意的是快速亂數演算法并不需要計算SHA-512，而是通過Chacha20演算法實作的，

代碼位置

關于本章亂數的相關代碼主要在Bitcoin下面的檔案中實作：

https://github.com/bitcoin/bitcoin/blob/master/src/random.cpp