超硬核文章說透「時鐘問題」,拜占庭環境中分佈式計算系統的基本問題。構建最有效時鐘的區塊鏈,將可以成功地分離時間和狀態,並能夠進行擴展,以安全和去中心化的方式支持數百萬用戶的吞吐量。

撰文:Ryan Gentry,Multicoin Capital 技術分析師
編譯:June Chan

未來一兩年間將推出許多智能合約平臺,如以太坊 2.0、Polkadot、Dfinity、Near Protocol、Algorand、Kadena、Spacemesh 和 Solana。每個團隊都在追求獨特的擴展策略。

然而,大多數這些方法都沒有解決拜占庭環境中分佈式計算系統的一個基本問題:時鐘問題。爲了達成共識,網絡中至少 51% 的機器必須在同一時間以相同的順序執行相同的事務。想要實現這一點,這些機器需要就一個全局時鐘達成一致。

「時鐘問題」,指的是讓許多不信任的機器在拜占庭式的設置下,就全局時鐘達成一致所面臨的挑戰。一旦每個人都同意一個全局時鐘,事務排序就會變得簡單得多,因爲每個事務都使用相同的全局時鐘分配時間戳。

在現代加密時代之前,時鐘問題已經在其他大規模網絡中彰顯了出來,尤其是在無線通信領域。手機信號發射塔必須同時支持成千上萬的手機。由於沒有足夠的帶寬讓每部手機都按自己的無線頻率來傳輸,因此電信行業需要使用「多重接入技術」,好在同一頻率上塞進多個電話呼叫。

碼分多址 (CDMA) 是在二戰期間發明的。爲了解決時鐘問題,CDMA 要求每臺手機用一個唯一的密鑰加密數據,並像其他手機一樣同時傳輸多個頻率的數據,依靠發射塔將組合的信號劃分爲各自單獨的通話。此模式的效率只會隨着加密模式複雜性的提高而同步改進。對於必須支持廉價終端設備的廣泛可用網絡,這類改進的速度歷來緩慢而穩定。

自 2G 蜂窩網絡出現以來,時分多址 (TDMA) 已成爲解決時鐘問題的標準解決方案,電信公司藉此獲得了更快的效率收益。

TDMA 指定發射塔,將每個無線電頻率劃分爲時間段,並將這些時間段分配給每個電話呼叫。通過這種方式,蜂窩塔爲網絡提供了一個全局可用的時鐘。這極大地提高了有限帶寬的可擴展性,使得每個頻率可支持多個同步數據通道,並減少來自多個電話在同一頻率上同時廣播的干擾。

在本文中,我將探討不同的區塊鏈如何在拜占庭式的設置下處理時間問題。

我的結論是,構建最有效時鐘的區塊鏈將成功地分離時間和狀態,並能夠進行擴展,以安全和去中心化的方式支持數百萬用戶的吞吐量。

去中心化共識與時鐘

谷歌的 Spanner 數據庫是全局性能最好的分佈式數據庫之一,擁有 18 個實例,所有的事務處理都是同步的。它支持每秒 50,000+個事務 (TPS),最終性時間 (TTF) 控制在 1 秒內。Spanner 利用了於 1989 年首次發佈的 Paxos 共識算法。Spanner 是一個許可式的可信數據庫。而 Paxos 算法使得 Spanner 在面對斷電、服務器故障、惡意 bug 等許多其他錯誤時仍能取得進展。

在當今吞吐量最高的區塊鏈僅用 21 個實例就難以實現 5,000+ TPS 時,Paxos 是如何實現這種性能的?谷歌會聘請全職工程師來到現場,定期以極高的精度同步每個數據中心的原子鐘。提供一個全局可用的可信時鐘,可以對事務分配時間戳,以便每個實例接收到無序的事務,但同時又能以正確的順序處理它們。這就是時間和狀態分離,因爲每個實例都會更新其狀態,而無需與其他實例進行檢查,以確保它們以相同的順序執行相同的操作。

我們能從 Spanner 中學到什麼?如果在非拜占庭式的環境中有一個全局可用的時鐘,那麼達成共識是小菜一碟。遺憾的是,如今的智能合約平臺有兩個 Spanner 沒有的額外限制:
1. 成爲一個驗證器必須是無需許可的,以保持平臺的抗審查性
1. 區塊鏈必須保護用戶的資金安全,哪怕高達⅓的驗證器是有惡意的。

如果任何人都可以在全世界任何地方啓動驗證器實例,則必須設計共識算法來適應不同的硬件和網絡配置,並必須管理惡意驗證器。此外,爲了真正抵抗審查,不可信任各種帶外信息(即預言機問題)。

Paxos 共識算法發明 20 年後,有人想出了一個辦法,讓一個無需許可的計算機網絡就交易的規範順序達成共識。這個人就是中本聰 (Satoshi Nakamoto),解決方案是工作證明 (PoW) 共識。

工作證明+時間鏈 = 時鐘

有意思的是,中本聰提前發佈的比特幣源代碼實際上將人們熟悉的區塊鏈數據結構稱爲「時間鏈 (Timechain)」。這個時間鏈的設計是平均每 10 分鐘滴答 (tick) 一次(通過巧妙地將工作證明、難度調整和最長鏈規則整合在一起,這超出了本文的範圍),其中,每次滴答都以更新全局狀態的事務塊的形式出現。在節點執行一個事務塊之後,它會被鎖定,不能進行任何狀態更新,直到它自己生成一個有效的新塊,或者從網絡接收到一個有效的新塊。

在 PoW 中,時間和狀態是耦合在一起的,總是步調一致地前進。時間無法通過更新到狀態進行處理。

什麼能令區塊「有效」,這個話題一直會引起非常激烈的爭論。事務格式和區塊大小隻是需要考慮的衆多特性當中的兩個。不過,有效區塊的其中一個方面不存在爭議,那就是它必須包含前一個塊的哈希,好讓網絡知道將它放在時間鏈中的前一個塊之後。

Multicoin:從中本聰共識和 Tendermint 談起,讀懂時間與狀態分離的意義圖說:區塊鏈中的每個塊都包含前一個塊的哈希,以證明它在後面。

時間鏈的目的是解決上面的需求#2:成爲一個驗證器必須是無需許可的。驗證比特幣網絡當前狀態是否有效的唯一方法是從創世區塊中的狀態開始,執行從創世區塊到當前狀態的每一筆交易。通過證明區塊高度爲 12 的事務已經發生,並且必須在區塊高度爲 11 的事務之後執行,時間鏈爲一個新的驗證器提供了審計軌跡。因爲第 12 區塊必須包含第 11 區塊的哈希,第 12 區塊只能在第 11 區塊之後創建。

哈希的這個時間鏈產生一個合邏輯的、單調一致的(儘管不規則而且細粒度不夠)時鐘,網絡中的任何驗證器都可以在沒有任何帶外信息的情況下獨立地驗證這個時鐘。

在一個開放的、無許可的環境中生產這種全局可用且可信的時鐘,這是中本聰最大的創新。由於在出新塊前,全局狀態被鎖定,因此可伸縮性的計算很簡單:
吞吐量 [TPS] = 區塊大小 [每區塊 txs] / 區塊時間 [每塊秒]

爲了增加吞吐量,協議必須要麼增加區塊大小,要麼減少區塊時間。增加區塊大小不利於區塊生產者的去中心化,而減少區塊時間又增加了鏈分叉的概率。

因爲時間和狀態是耦合的,沒有辦法繞過它。

回到無線通信的例子,讓我們將這個問題與 CDMA 進行比較。在 CDMA 中,無線電發射塔有一個固定的頻率帶寬可以被聽到,這類似於區塊生產者有一個固定的區塊大小可供其處理。提高 CDMA 的可伸縮性意味着要創建更復雜的編碼方案,以便在有限的帶寬內適應更多的電話呼叫。這類似於 Segwit、閃電通道和 Schnorr 簽名,作爲更復雜的編碼方案,它們均可以提高性能。

比特幣有 1 MB 的區塊,區塊時間爲 600 秒,最小交易大小爲 250 B,理論上最大吞吐量爲 7 TPS。這比 Spanner 的吞吐量低了約 7000 倍,比它的 TTF 慢了 3600 倍(因爲它需要 6 個區塊時間來實現概率不可逆的最終性)。

顯然,比特幣還有改進的空間。

權益證明+時間鏈 = 更快的時鐘

比特幣的發展引發了共識算法研究的復興。CAP 定理告訴我們,在網絡分區的情況下,分佈式數據庫系統必須在一致性(網絡中斷)和可用性(網絡分叉)之間做出選擇。中本聰共識算法這個大家族體系中有許多共識算法,所有都選擇可用性而不是一致性。中本聰本人的算法是這個共識算法家族中的第一個無許可的拜占庭容錯共識算法。

相較中本聰家族,經典共識算法家族則更喜歡一致性而非可用性,其中之首是 Leslie Lamport 的 Paxos 算法。

在 Paxos 和許多其他經典共識家族的算法中,每個參與共識的節點必須與網絡中的其他所有驗證器同步通信,以進行每個狀態更新。這使得通信複雜度爲 O(n2) (其中 n 是驗證器計數),這意味着隨着驗證器計數的增加,每個狀態更新之間所需的時間呈指數級增長。

Jae Kwon 和 Ethan Buchman 率先從事經典共識研究,爲之傾注了 20 年的時間,他們將一種名爲「綁定權益證明」(BPoS) 的加密經濟激勵結構注入其中,以安全地限制驗證器的數量。他們所取得的工作成果,便是經典共識家族中的第一個高性能、無許可的 BFT 共識算法:Tendermint。

與中本聰共識一樣,Tendermint 捆綁了時間和狀態更新,因此只有當區塊大小增加或區塊時間減少時,它的吞吐量纔會增加。2009 年比特幣問世時,10 分鐘的區塊時間是合理的。然而,自那以後,帶寬呈指數級增長,使得 Tendermint 鏈的區塊時間縮短到了幾秒鐘。

因爲 Tendermint 更喜歡一致性,不可能分叉,所以可以減少區塊時間,直到某個給定驗證器計數的網絡吞吐量瓶頸系統性能達到極限爲止。現在,Tendermint 允許網絡安全地將驗證器數量限制在 100 個以內,這樣做的好處是過濾掉帶寬差的節點,並允許使用更大的區塊。

Tendermint 正在生產中。Cosmos Hub (第一個實時 Tendermint 實例)以 6 秒的區塊時間運行,區塊大小爲 150 kB,最大吞吐量爲 100 TPS (假設事務爲 250 字節)。它還只有幾個月的歷史,不過很快就會成熟。從理論上講,擁有 5 秒出塊時間和 5 MB 區塊大小的 Tendermint 網絡可以達到 4000 TPS 吞吐量,而與比特幣相比,它在抗審查性和無許可性方面所做出的犧牲最小——這意味着吞吐量增加了 570 倍,TTF 減少了 720 倍!

遺憾的是,由於經典共識算法的同步特性,匹配 Spanner 會對系統的抗審查性和無許可性產生不利影響。更大的區塊將不可避免地需要更長的時間來在網絡中傳播,驗證器也需要更長的時間進行驗證,這就爲出塊時間設定了一個下限。爲了提高時鐘的速度,驗證器的數量需要顯著減少,而且它們都需要直接連接到同一個光纖網絡。這將增加驗證器串通合謀的可能性和新驗證器進入的障礙,並使光纖網絡的操作員成爲一箇中心點。

區塊鏈共識的下一個演進將採取一個重要步驟來分離時間和狀態,以相當高的成本獲得巨大的吞吐量提升。

分片+時間鏈 = 獨立時鐘

使用 BPoS, Tendermint 解除了驗證器數量帶來的抗審查性,這使得網絡時鐘從每 600 秒滴答一次加速到每 5 秒一次,從而大大提高了性能。然而,在時鐘的每一次滴答之間,整個全局狀態仍然被鎖定,以保持全局一致的狀態。

緩解這一問題的一種方法是將全局狀態分割成一串更小的碎片,每個碎片都有自己獨立的時鐘,可以彼此獨立前進。只要這些分片不需要相互交互,每個分片的性能就能保持不變,並且所有分片的總吞吐量隨切分的數量線性增加。

Cosmos 設想許多獨立的區塊鏈網絡並行存在,能夠在彼此之間傳遞價值,但主要是在各自的系統內進行交易。如果每個網絡可以處理 4000TPS,並且有 13 個不同的網絡,那麼整個系統可以達到 52000 TPS,超過 Spanner 的吞吐量!

不過,這種方法存在兩個問題:

1) 權益證明區塊鏈的安全性是通過獲得 33% 的抵押代幣和批准無效交易的成本來衡量的。如果不是單一的代幣供應,而是有 13 個單獨的網絡,那麼獲得給定網絡 33% 的份額的成本將大大降低。這遠談不上安全,而且嚴重損害了區塊鏈的價值主張,其中安全是網絡價值的一個功能。
2) 與網絡內傳輸相比,網絡間傳輸的 TTF 至少增加 4 倍。網絡必須來回通信以同步它們的時 鍾,並確保如果 Alice 向 Bob 發送代幣,需要在網絡上燒掉 Alice 的代幣之前,令 Bob 成功在他的網絡上接收到價值。
3)
儘管 Cosmos 設想了一個由許多自主網絡管理自身安全的世界,但以太坊 2.0、Polkadot、Algorand、Dfinity 和 Near Protocol 正在構建至少能夠解決共享安全問題的系統(上述需求#1)。每個團隊的方法都有細微的差別,但是基本的體系結構包括一個信標鏈,它既爲網絡的其餘部分提供時鐘,又安全地將驗證器跨分片打亂,以便它們都共享一個公共的安全池。與 Cosmos 一樣,增加吞吐量很容易:只需添加更多的分片!

Multicoin:從中本聰共識和 Tendermint 談起,讀懂時間與狀態分離的意義圖說:以太坊 2.0 的單鏈和分片狀態。

遺憾的是,網絡間傳輸的高 TTF 問題(上述需求#2)仍然存在。即使信標鏈提供了一個全局時鐘,每個分片也只是週期性地將其本地時鐘與信標鏈的時鐘同步。爲了讓 Alice 從分片 A 向分片 B 中的 Bob 發送代幣,分片 A 中的驗證器必須證明它們燒掉了 Alice 的代幣,然後分片 B 中的驗證器才能爲 Bob 生成等量的代幣。按照以太坊 2.0 目前的設計來計,這個過程將花費 6 分鐘,是跨分片區塊時間的 60 倍。

雖然分片有用,但是基本的擴展限制仍然基於每個分片中的時間和狀態更新是耦合的這一事實。面對 Tendermint 有關區塊大小和區塊時間的問題,每個分片仍然受到同樣的限制。

分片類似於 TDMA 的某些元素;狀態被劃分成獨立的分片,使用它們自己的時鐘,就像手機信號塔把它們的帶寬劃分成獨立的無線電頻率和時間段一樣。這樣做的好處很明顯,但並沒有得到充分利用,這一點可以從跨分片延遲得到證明。

但是,如果可以在無許可設置中完全解耦時間和狀態更新,情況會怎樣呢?

分離時間和狀態

到目前爲止,我們已經討論了中本聰如何創建時間鏈數據結構,來爲比特幣網絡提供一個免信任的時鐘;Kwon 和 Buchman 如何將 BPoS 應用於 PBFT 中,從而安全地減少驗證器數量並加快 Tendermint 網絡時鐘;以及使用獨立時鐘將網絡分片成許多小塊將如何極大地提高吞吐量(只要將跨分片事務最小化)。然而,通過這些進展,我們已經注意到狀態和時間的更新仍然是耦合的,狀態更新只與時鐘滴答同時發生,這爲抗審查和無許可的計算網絡的吞吐量和實現最終性的時間造成了根本上的限制。

分離時間和狀態需要一個全局可用的時鐘,它是快速、精確和信任最小化的。使用這樣的時鐘,狀態更新可以像在 Spanner 中一樣連續和異步地發生。只要每個人都同意使用一個全局時鐘,並且事務具有時間戳,事務就可以在網絡中持續流動。

通過將基於哈希的時間鏈與對狀態更新的共識中分離,Solana 已經爲他們的智能合約平臺構建了一個信任最小化的時鐘。Solana 網絡中的驗證器不是將哈希鏈接到每個塊上,而是在塊內連續地散列哈希本身。這種機制稱爲歷史證明 (Proof of History, PoH),它爲網絡中要同步的所有節點生成一個全局可用、信任最小化的細粒度時間鏈。

深入研究 PoH 的機制超出了本文的範圍。有關 PoH 如何運作的更多細節,請參閱 Solana 的 PoH 文檔(https://solana-labs.github.io/book/synchronization.html)。

Multicoin:從中本聰共識和 Tendermint 談起,讀懂時間與狀態分離的意義圖說:歷史證明將標準化的時間戳編織到區塊鏈中的方式。

這種獨立的時間鏈的存在使得領導者在收到分配有時間戳的交易後,會盡快向委員會傳播。時間戳提供規範的順序,而不是由區塊生成者確定的任意順序。由於整個網絡都能夠就哪個事務先發生達成一致,所以現在解決雙花的嘗試是很容易的。

它改變了一切。

Solana 中的驗證器可以不斷地向其對等方實時發送狀態更新,而不是強制驗證器每隔 6-600 秒達成共識,以驗證時間的推移。

Solana 不需要像其他所有區塊鏈一樣等待每個驗證器的確認,而是可以使用一種名爲 Turbine 的新型扇出機制(靈感來自 BitTorrent)來保持通信複雜度,即複雜度爲 O(log(n)),而不是 O(n2)。這使得 Solana 可以在單個全局狀態下處理超過 50,000 TPS,且能實現快速最終性,而且還不需要分片。

這意味着驗證器池的大小與 Tendermint 相當,大約 100-1,000 個,但是允許進行鏈分叉。需要一個積極的分叉管理策略,以確保無論何時出現一個鏈分叉,系統都能快速地收斂到單個鏈上,這是異步進程和恆定可用性的必要折衷。

將無線通信比喻成一個完整的輪迴,PoH 對於區塊鏈的意義就像 TDMA 對於蜂窩網絡的意義一樣。把 Solana 的 1,000 個驗證器想象成無線電發射塔,利用它們的同步時鐘將它們的帶寬細分爲各個時間段。它們不斷地接收新的事務,每個事務都有發送者附加的簽名 PoH 哈希,並將它們轉發給鄰居,鄰居可以立即使用這些 PoH 哈希進行排序。當領導者根據全局時鐘進行輪換時,每個領導者都會選擇一組有序的事務來執行,然後將「條目」傳播到網絡。驗證器對每個「條目」投票,在他們看到⅔的驗證器與自己一起投票後,確認事務終結。

這個網絡作爲一個整體,不斷地以難以置信的高容量,按照相同的順序處理事務,但是每個驗證器都在獨立地進行。相對於其他鏈條,這是一個微妙而深刻的變化。在 Solana 中,驗證器永遠不會停止前進。而且不管網絡條件和共識如何,他們總是獨立前進。

還有其他一些相關但不太重要的問題(例如快速的鏈增長、新的編程模型、時間鏈的不偏性、並行性),這些新設計超出了本文的討論範圍,不過在 Solana 的文檔中已經討論過了。如今,Solana 的測試網在 5 大洲 200 個驗證器的網絡上處理超過 50,000 個 TPS,平均 TTF 爲 1.5 秒。這些參數與 Spanner 旗鼓相當,只不過 Solana 是在有目的地去中心化。

在一個信任最小化、無許可的計算機領域中,這種級別的性能只有在 Solana 將時間和狀態分離的情況下才可能實現。Solana 網絡的全局可用時鐘允許每個節點更新其狀態,而不需要像 Spanner 那樣與任何其他節點通信。

重構可伸縮性

儘管加密社區已經就可伸縮性和一致性模型撰寫了連篇累牘的文章,但是沒有人專門研究分佈式時鐘的問題。幾年來對權益證明的研究,帶來的最佳成果是 Tendermint + BpoS,無數分片方案基本上都圍繞着「信標鏈+狀態分片」架構展開,而允許異步狀態進展的細粒度時間鏈將爲喜歡可用性、而不是一致性的非分片系統提供最佳性能。

提供一個全局可用的時鐘,這使得 Solana 團隊能善加利用 40 多年來的分佈式系統研究。樂觀併發控制(又名「樂觀鎖」,Optimistic Concurrency Control,簡稱「OCC」)等概念是 1981 年發明的,多年來一直應用於大型計算項目中,但在時間和狀態必須同時進行時則無法應用。與 GPU 的並行處理從 1995 年開始就已經存在,不過在 2007 年英偉達 (Nvidia) 發佈 CUDA 開發環境之前主要侷限於圖形卡,無法被基於區塊鏈的系統充分利用,這類系統悲觀地鎖定除當前正在處理事務的賬戶以外的一切狀態。

理解時間的推移對於分佈式系統在許可和無許可設置下的性能都是至關重要的。時間就是一切,使用一種以歷史證明的形式編碼時間推移的新方法,無許可系統可以與經過驗證的中心化雲計算供應商的性能相匹配。

感謝 Anatoly Yakovenko 和 Zaki Manian 對本文的反饋。

來源鏈接:multicoin.capital