基於近似共識的分散式隨機性：非同步拜占庭容錯協定

1 緒論

隨機化是設計分散式系統的關鍵工具。共同幣原語能讓系統成員就不可預測的隨機數達成共識，已被證實對拜占庭共識、分散式金鑰生成與領導者選舉等協定特別有用。然而，由於FLP不可能性結果，在易出錯的非同步系統中實現完美的共同幣協定是不可能的。

本文介紹了完美共同幣的兩種鬆弛形式：(1) 近似共同幣，生成彼此接近的隨機數；(2) 蒙地卡羅共同幣，以任意小但非零的失敗機率生成共同隨機數。我們的協定建構於近似共識原語之上，無需可信設置或公開金鑰基礎建設，即可容忍最多三分之一的拜占庭程序。

2 背景與相關工作

2.1 共同幣原語

完美的共同幣協定必須滿足三個屬性：

終止性：每個正確程序最終都會輸出某個值
一致性：任意兩個正確程序不會輸出不同值
隨機性：輸出值在定義域D上必須均勻分佈，且|D| ≥ 2

先前的實作要么假設同步或部分同步系統並需要可信設置。我們的工作專注於無此假設的非同步系統。

2.2 近似共識

近似共識允許程序在預定義容錯ε內決定彼此接近的值。其收斂函數可表示為：

$v_i^{r+1} = \frac{\sum_{j \in S} v_j^r}{|S|}$，其中$S$是可接受範圍內接收值的集合

此原語構成了我們近似共同幣實作的基礎。

3 協定設計

3.1 近似共同幣

我們的近似共同幣協定確保所有正確程序在k輪後輸出的值彼此距離在ε內。該協定隨輪數呈指數級快速收斂：

$\epsilon_k \leq \epsilon_0 \cdot \alpha^k$，其中$\alpha < 1$為收斂速率

該演算法以非同步輪次進行，每個程序廣播其當前估計值，並對接收值應用近似共識函數。

3.2 蒙地卡羅共同幣

蒙地卡羅共同幣保證對於任意小的δ > 0，達成一致的機率為1-δ。失敗機率隨輪數呈指數級下降：

$P[\text{失敗}] \leq e^{-\beta k}$，其中$\beta > 0$為常數

此協定結合近似共識與密碼學技術，無需可信設置即可達成所需屬性。

4 技術分析

4.1 數學基礎

我們協定的安全性依賴於存在拜占庭錯誤時近似共識的收斂特性。對於具有n個程序且f < n/3個拜占庭故障的系統，我們證明：

$\lim_{k \to \infty} \max_{i,j \in \text{正確}} |v_i^k - v_j^k| = 0$

收斂速率取決於網路拓撲與所使用的特定共識函數。

4.2 安全性分析

我們的協定能抵抗控制最多f < n/3個程序的適應性拜占庭敵手。安全性證明遵循模擬典範，顯示任何環境都無法區分真實協定與理想功能。

5 實驗結果

我們在模擬的非同步網路中評估了我們的協定，涵蓋不同程序數量（n = 10至100）與拜占庭故障率（f < n/3）。結果顯示：

對於典型參數，在5-10輪內呈指數級收斂至共識
二元拜占庭共識的通訊複雜度為O(n³log n)
相較於先前O(n⁴)解決方案有顯著改善

以下虛擬碼說明了核心近似共識輪次：

function ApproximateAgreementRound(value, round):
    broadcast("PROPOSE", value, round)
    received = wait_for_messages(n - f, round)
    valid_values = filter_within_range(received, value - ε, value + ε)
    new_value = median(valid_values)  // 或對連續定義域取平均
    return new_value

6 實作細節

我們的實作使用標準密碼學原語，包括雜湊函數與數位簽章。核心演算法結構：

class MonteCarloCommonCoin:
    def __init__(self, n, f, delta):
        self.n = n  # 總程序數
        self.f = f  # 最大拜占庭故障數
        self.delta = delta  # 失敗機率
        self.round = 0
        
    def generate_coin(self):
        while True:
            self.round += 1
            estimate = self.approximate_agreement_round()
            if self.consensus_achieved(estimate):
                return self.finalize_output(estimate)
            if self.round > self.required_rounds():
                return self.fallback_output()

7 應用與未來方向

當前應用：

通訊複雜度為O(n³log n)的拜占庭共識
使用近似共同幣與格雷碼解決隨機子集交集問題
無許可區塊鏈系統中的領導者選舉

未來研究方向：

調整協定以適用於抗量子密碼學
擴展至動態成員設定
針對具部分同步性的真實網路條件進行最佳化
與分片區塊鏈架構整合

8 參考文獻

Fischer, M. J., Lynch, N. A., & Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM.
Rabin, M. O. (1983). Randomized Byzantine generals. Symposium on Foundations of Computer Science.
Cachin, C., Kursawe, K., & Shoup, V. (2000). Random oracles in Constantinople: Practical asynchronous Byzantine agreement using cryptography. PODC.
Miller, A., Xia, Y., Croman, K., Shi, E., & Song, D. (2016). The honey badger of BFT protocols. CCS.
Abraham, I., Malkhi, D., & Spiegelman, A. (2019). Asymptotically optimal validated asynchronous Byzantine agreement. PODC.

原創分析

本研究透過解決非同步系統的基本限制，對分散式隨機性生成領域做出了重要貢獻。近似與蒙地卡羅共同幣的引入代表了一種繞過FLP不可能性的務實方法，類似於像比特幣這樣的實用區塊鏈系統如何將理論共識概念演進為可運作的實作。

作者在二元拜占庭共識上達成O(n³log n)通訊複雜度，相較於先前O(n⁴)解決方案有顯著改善。此進展與可擴展分散式系統研究的趨勢一致，其中降低通訊開銷對實際部署至關重要。類似的效率考量也推動了其他領域的發展，例如機器學習中生成對抗網路（GANs）的最佳化，其中CycleGAN展示了如何透過精心的演算法設計使理論概念變得實用。

結合近似共識與格雷碼解決隨機子集交集問題的方法尤其創新。此方法展示了古典電腦科學概念如何被重新應用於現代分散式系統挑戰。該技術與分散式儲存系統中的編碼理論應用有相似之處，其中高效的資料分佈與檢索依賴於具有特定交集屬性的數學結構。

從安全性角度來看，無需可信設置或PKI即能抵抗適應性拜占庭敵手的能力值得注意。這與當前去中心化系統優先考慮信任最小化的趨勢一致。該方法與零知識證明系統在哲學上有相似之處，其中密碼學技術能在不揭露底層資料或依賴可信權威的情況下實現驗證。

協定中展示的指數級收斂速率暗示了超出討論立即使用案例的潛在應用。類似的收斂特性在最佳化演算法與機器學習中已被證明具有價值，其中快速收斂至共識能實現高效的分散式計算。正如麻省理工學院電腦科學與人工智慧實驗室等機構的研究所指出的，此類特性在資源受限的邊緣運算環境中特別有價值。

未來工作可探索與同態加密和安全多方計算的關聯，其中分散式隨機性生成扮演關鍵角色。本文開發的技術也可能在聯邦學習系統中找到應用，其中在無中央權威的情況下協調分散節點間的隨機性，呈現出與本研究解決的挑戰相似的問題。