Polkadot 的區塊最終確定性祖父協議 GRANDPA :簡介(第 1 部分)

祖父協議 (GRANDPA)(基於 GHOST 的遞歸祖先派生前綴協議)在混合共識區塊鏈中提供近乎即時的、異步的,負責任安全的最終確定性。

在良好的網絡條件下,我們幾乎可以立即確定區塊。在網絡分區的情況下,當它們解析時 , 我們可以一次性完成數以百萬計的區塊。一次完成的區塊數與網絡開銷無關。

本文是探討 Polkadot 共識和最終確定性 (finality) 的一系列文章中的第一篇。

任何花費足夠時間研究區塊鏈的人都會遇到 共識最終確定性,甚至還有“安全”的概念。這些概念在理解區塊鏈真正起作用時往往是一個很大的障礙。那麼讓我們從共識的入門開始吧。

關於區塊鏈共識的一個常見誤解是它產生了有效的交易歷史。實際上,任何人都可以在自己的計算機上進行一系列有效的交易。困難的部分是讓每個人都同意使用 哪些 有效的交易歷史。這是需要 達成共識 的地方。

經典的 一致性算法 提供兩個主要屬性:安全性活躍性安全 是確保誠實參與者不同意兩個相互衝突的事物(在這種情況下是塊)的屬性 (PS:保證決議結果是對的,無歧義的,不會出現錯誤情況)。活躍性 是確保誠實參與者最終達成一致意見的屬性 (PS:保證決議過程能在有限時間內完成)。在區塊鏈的背景下,安全與最終確定性是一回事。也就是說,一旦塊完成,規範鏈(canonical chain) 將來總是包含該塊。在區塊鏈中,活躍意味着鏈條不斷增長,而且有效交易最終將被包含並最終確定。

所有共識算法僅在某些假設下提供這些安全性和活躍性。這些假設通常用系統中 參與者的比例 來表示拜占庭 – 有多少比例的參與者離線甚至是惡意行爲。還有網絡設定:傳遞消息需要多長時間,消息是否可以無序接收甚至丟棄。網絡設定通常分爲以下幾類:

  • 同步:消息始終在發送的某個時間 T 內傳送,所有參與者都知道。

  • 部分同步:存在一些已知的全局穩定時間(GST),在此之前消息可以被任意延遲,之後消息在 T 內傳遞。

  • 異步:消息最後傳遞。

重要的是要注意,消息可以以不同的順序傳遞給不同的參與者。這些網絡設定也決定了拜占庭參與者的最大可能比例。當網絡是 部分同步異步 時,它必須 小於⅓。爲了說明這是爲什麼,假設⅓節點是惡意的,並且需要絕對多數(> =⅔)才能達成共識。然後,惡意節點可以將剩餘的 2/3 節點分成兩組:A 和 B。惡意節點然後可以參與兩個不同的絕大多數羣組,包括 A 和 B,導致安全違規。只有當 A 和 B 之間的通信延遲的時間長於達到 一致所需 的時間時,纔有可能實現這種情況,這可能是 部分同步異步 網絡模型中的情況。

Polkadot 的區塊最終確定性祖父協議 GRANDPA :簡介(第 1 部分)

兩組良好節點不能相互通信,但壞節點可以與兩個組進行通信,並且每個組都以不同方式達成共識。如果只需要 2/3 的選票,這可能會導致安全違規。

應用於區塊鏈時,請注意不會立即達到區塊安全性。例如,在工作證明 (POW) 中,安全是技術上永遠不會達到。相反,達到的安全性是概率性的,並且通過“共同前綴”屬性進行競爭,該屬性指出,如果每個誠實的一方忽略了他們鏈中的最後一個_k_塊,那麼他們在他們的鏈上達成一致的概率是壓倒性的(足夠多的選擇_k_)。工作量證明和其他概率安全協議也有一點需要注意,即它們不提供 異步安全性,這意味着足夠大的網絡分叉或攻擊可能導致混亂故障。

Polkadot 的區塊最終確定性祖父協議 GRANDPA :簡介(第 1 部分)

這裏有很多鏈,但它們都有一個共同的前綴。POW 共識確保了這一概率,而 GRANDPA 確保了這一確定性。

公有區塊鏈網絡 中,我們要求參與者不要破壞安全屬性和回撤已經達成一致的區塊。與許多基於簡單的 多數誠實 設定的共識算法相反,我們實際上需要更強大的東西:負責任的安全性(accountable safety)。考慮一個安全的共識協議,除非⅓或更多的參與者行爲不端。只要少於參與者的行爲不端,那麼一切都很好。但如果他們這樣做,我們希望能夠證明他們做到了。這是負責任的安全:如果他們行爲不端,參與者可能會被追究責任(即有一些保證金被燒燬)。在負責任的安全性下,我們對 最終確定性 有了更好的定義:除非系統中至少有 1/3 的股權被銷燬,否則無法恢復區塊。

Polkadot 的區塊最終確定性祖父協議 GRANDPA :簡介(第 1 部分)

負責任的安全:儘管惡意驗證者 (validators) 分叉了網絡,但是可以檢測到他們的不當行爲,並且可以在分叉的兩側削減 (slash) 他們的權益 (stake)。不存在行爲不當的節點僥倖逃脫的有效未來狀態。

通常,提供 絕對(非概率)安全性 的共識協議需要傳遞大量消息,以滿足所有協議的要求。通常,需要在參與者之間發送的消息數量與協商一致協議中的參與者不成比例。這使得在每個塊上執行這種協議的成本很高,正如在即時最終確定性協議類中所做的那樣。因此,將 塊的創建 與它們的 最終確定化 分離通常是有益的。這種方法導致了區塊鏈共識的雙重方法:鏈增長系統 (chain growth system)最終確定性配件 (finality gadget)。讓最終確定性配件一次完成多個塊有利於 提高效率,因爲它減少了必須在網絡上的共識參與者之間傳遞的消息數量。這種混合模型可以使鏈的增長速度與 Ouroboros (Ps: Ada 的共識算法) 或 Aurand (Ps: 允許隨機選擇驗證人出塊,而不需要 2/3 成員的共識) 等概率安全共識一樣快,同時也提供與 即時最終確定性共識 (instant-finality consensus) 相同的安全保證。這就是我們在 Polkadot 中使用這種混合共識系統的原因。

Polkadot 的區塊最終確定性祖父協議 GRANDPA :簡介(第 1 部分)

活躍度 (liveness):我們可以持續擴展最終區塊的那條鏈的屬性

由於 最終確定性配件 (finality gadget) 不會產生區塊,我們需要另一種方式來考慮 活躍度,我們之前將活躍度定義爲共識過程輸出某些內容的屬性。相反,我們將最終確定性配件的活躍度屬性視爲依賴於 區塊生產層 的某些屬性。這意味着,只要向鏈添加區塊的方法以特定方式執行,最終確定性配件將始終具有新的事物去最終確定。這是一個非常強大的屬性,因爲它意味着我們總是能夠向鏈中添加不可逆的事務。

Polkadot 使用基於上述描述的共識模型,這是一種混合模型,將區塊生產與這些區塊的最終確定分離開來。我們的目標是使區塊生產層快速且具有概率安全性(probabilistically safe)。最終確定性配件應該是異步安全的,應該提供負責任的安全性,並且應該能夠一次完成許多區塊。我們發明了 GRANDPA(基於 GHOST 的遞歸祖先派生前綴協議),這是一個提供了這些東西或更多的最終確定性配件

GRANDPA 背後的關鍵想法是將區塊鏈結構整合到共識算法中。一個直覺告訴我們,考慮一個區塊有效意味着考慮該區塊的父塊有效,以此類推。以下是該算法的簡化解釋:我們允許參與者對他們認爲有效的最高區塊進行投票,而不是對單個區塊進行投票,算法將該投票傳遞給該區塊的所有祖先區塊。然後,然後算法確定最佳區塊 >⅔絕對多數的選票,併產生 最終確定性證明 (proof-of-finality)最終確定性證明是通過獲得絕對多數投票,並將他們捆綁在一起形成一個單一的信息來構建的。簽名聚合(Signature aggregation) 可用於使其更小。

Polkadot 的區塊最終確定性祖父協議 GRANDPA :簡介(第 1 部分)

祖父協議 GRANDPA 計算出了鏈中有 2/3 以上的節點是哪些區塊,並最終確定它們。它還可以爲不同的節點不同的權重。這些權重可以由協議中記錄的數量決定。在這個圖中區塊 C、B 和 A 被最終確定。

由於這種尋找絕大多數認爲有效的最高共同祖先的策略,祖父協議 GRANDPA 也具體 自適應性:它可以確定一個新區塊,而不管上次區塊確定之後已經經過了多少區塊。如果網絡延遲很低,GRANDPA 幾乎可以立即完成區塊,並且當從很長網絡分區恢復時,GRANDPA 可以一次完成數百萬個區塊,而不會產生任何消息開銷。找到所有參與者都能同意的區塊鏈的公共前綴的操作被轉換成快速找到公共前綴的投票過程。

祖父協議 GRANDPA 的投票發生在 鏈下,並且最終確定性沒有在鏈上註冊。然而,GRANDPA 參與者被鎖定在鏈上,並且相互矛盾的最終確定性證據將導致“模棱兩可”或雙重投票的參與者被發現和懲罰。發現哪些參與者雙重投票的過程將在未來的文章中描述,並且包括鏈下的挑戰 – 響應方式 (Ps: 是零知識證明的方式),只要最多 2/3 的參與者是惡意的,該過程就成功。GRANDPA 只有在歷史參與者受到懲罰的情況下才是安全的,因此屬於“弱主觀性”安全模式,參與者必須經歷相當長的撤回期(可能是幾個月)才能解鎖他們的股權和獲得回報。

這只是祖父協議 GRANDPA 的預告篇。接下來的文章將深入探討其內部運作,GRANDPA 如何提供負責任的安全性,活躍度,處理動態驗證集,基準性能等等。Rust 的第一個實現正在 https://github.com/paritytech/finality-afg

詳細描述了這個配件的文檔在這裏:

https://github.com/w3f/consensus/blob/master/pdf/grandpa.pdf

敬請期待更多的信息!

瞭解有關 Polkadot 的更多信息:

  • [資源清單]

(https://github.com/w3f/Web3-wiki/wiki/Polkadot)

  • [白皮書]

(https://polkadot.network/PolkaDotPaper.pdf)

  • [Lightpaper]

(https://polkadot.network/Polkadot-lightpaper.pdf)

加入 Polkadot 社區:

  • [Riot]

(https://riot.im/app/)

  • [Twitter]

(https://twitter.com/polkadotnetwork)

  • [Reddit]

(https://www.reddit.com/r/dot/)

原文:Robert Habermeier 翻譯:姜富耀 | 0xThreeBody


Polkadot ∣官方授權

Polkadot 的區塊最終確定性祖父協議 GRANDPA :簡介(第 1 部分)Polkadot 的區塊最終確定性祖父協議 GRANDPA :簡介(第 1 部分)

長按,識別二維碼,加關注