比特幣交易所 比特幣交易所
Ctrl+D 比特幣交易所
ads

萬字雄文講透中本聰共識的經典魅力_BFT

Author:

Time:1900/1/1 0:00:00

原文標題:《為何說比特幣是重大創新?談傳統分布式共識VS中本聰共識》作者:PreethiKasireddy,區塊鏈真偽驗證平臺TruStory創始人兼首席執行官,曾任職于高盛、A16z、Coinbase翻譯:灑脫喜

譯者前言:我們知道,比特幣等區塊鏈是分布式系統的一個子集,但它和傳統分布式賬本是有差異的,那這些差異在于哪里呢?為什么我們說比特幣是一項重大創新?來自前Coinbase、a16z、高盛的區塊鏈工程師PreethiKasireddy將在這篇文章中給出她的答案。

以下為譯文:

你知道分布式系統是如何工作的嗎?

這可能是一個很難學習的話題,主要是因為圍繞它的知識是很分散的.....

在自我學習分布式計算這個課題之前,我多次趴到了桌上,但經過多次考驗和磨難,我終于準備好向您解釋分布式系統的基礎知識。

我還想討論區塊鏈技術對該領域的深遠影響。區塊鏈迫使工程師和科學家們重新審視并質疑分布式計算中根深蒂固的范式。也許沒有其它技術能夠比區塊鏈更快地促進這一研究領域的進展。

區塊鏈是一種新型的分布式系統。它的出現始于比特幣,并從此在分布式計算領域產生了持久的影響。因此,如果你想真正了解區塊鏈的工作原理,那么掌握分布式系統的原理是至關重要的。

不幸的是,很多關于分布式計算的文獻,要么是難以理解的,要么分散在太多的學術論文當中。而讓問題變得更復雜的是,當前存在著數百種架構,而所有架構都滿足不同的需求。因此,將其歸結為一篇可理解的文章,足以稱得上是一件壯舉。

因為這個領域很廣,我不得不仔細選擇要覆蓋的內容。我還必須進行概括,以掩蓋一些復雜性。請注意,我的目標不是讓你成為該領域的專家。相反,我只是想讓你了解一些知識,開啟分布式系統和共識基礎知識的旅程。

閱讀完這篇文章之后,您將更深入地了解到以下這些內容:

分布式系統是什么?

分布式系統的屬性;

在分布式系統達成共識是什么意思?

理解基礎共識算法;

為什么中本聰共識是一項重大創新?

我希望你準備好了這次學習!

什么是分布式系統?

分布式系統涉及了一組不同的進程,將消息在彼此之間進行傳遞,并協調以實現共同的目標。

簡而言之,分布式系統是一組共同實現統一目標的計算機。雖然這些進程是分開的,但系統對終端用戶而言只是一臺計算機。

正如我所提到的,分布式系統存在著數百種架構。例如,單個計算機也可以被視為分布式系統;中央控制單元、存儲器單元和輸入-輸出通道,是協作完成一個目標的單獨進程。

舉飛機的例子,它們的共同努力是讓你從A點到B點:

來源:https://www.weetech.de/en/news-info/tester-abc/distributed-system-1/

在這篇文章中,我們將關注分布式系統,其中進程是指空間分離的計算機。

注意:我可能會把「節點」、「對等節點」、「計算機」或「組件」這些術語與「進程」互換使用。對于本文而言,它們都意味著相同的事情。同樣地,我可能會使用「網絡」和「系統」這兩個可互換的術語。

分布式系統的屬性

每個分布式系統都有一組特定的特征,這些包括:

A)并發

系統中的進程同時運行,這意味著同時會發生多個事件。換句話說,網絡中的每臺計算機與網絡中的其它計算機,會同時獨立地執行事件。

而這就需要協調。

Lamport,L(1978):分布式系統中的時間、時鐘和事件排序

B)缺乏全局時鐘

對于同時運行的計算機集合系統,我們需要某種方法來確定事件的順序。但是,在分布式計算機系統中,有時不可能明確兩起事件中的哪起事件是先發生的,因為計算機在空間上是分開的。換句話說,沒有一個全局時鐘來確定網絡中所有計算機發生的事件序列。

在《分布式系統中事件的時間、時鐘和順序》這篇論文當中,LeslieLamport展示了如何通過記住以下因素來推斷出一個事件是否發生在另一個事件之前:

某巨鯨拋售16,751枚ETH,售出均價1840美元:7月25日消息,據Lookonchain數據,某巨鯨地址于約12小時前拋售16,751枚ETH(約合3,080萬美元)。該地址將16,751枚ETH存入Binance后,提出3080萬枚USDT,售出均價約為1840美元。然后通過2個地址將3080萬枚USDT存入Aave和Compound。[2023/7/25 15:57:07]

1)消息是在它們被收到之前發送的;2)每臺計算機都有事件的序列;

通過確定哪個事件是發生在另一個事件之前的,我們可以獲得系統中事件的部分排序。

Lamport的論文描述了一種算法,該算法要求每臺計算機都能夠「聽到」其它每臺計算機。

通過這種方式,事件就可以基于這種偏序進行完全排序。

但是,如果我們完全根據每臺計算機正在聽到的事件進行排序,則可能導致此順序與外部用戶所感知的順序會不同。因此,該論文提到的算法仍然可允許異常行為。

最后,Lamport討論了如何通過使用正確同步的物理時鐘來防止這種異常情況。

但是,等等,這里有一個巨大的警告:協調獨立的時鐘,是一個非常復雜的計算機科學問題。即使你最初準確地設置了一堆時鐘,時鐘也會在一段時間后開始出現差異。這是由「時鐘漂移」問題造成的,這是一種時鐘以稍不同速率計算時間的現象。

本質上,這篇論文證明了,事件的時間和順序,是在空間上分離的分布式計算機系統的基本障礙。

C)組件的獨立故障

理解分布式系統的一個關鍵部分,在于承認分布式系統中的組件會存在故障。這就是它被稱為「容錯分布式計算」的原因。

擁有一個沒有故障的系統是不可能的。真實的系統會存在很多可能的缺陷或弱點,無論這是一個進程崩潰,消息丟失、扭曲或重復,還是網絡分區延遲或出現丟棄消息的情況,甚至會出現進程完全失控,并根據一些惡意計劃發送消息的情況。

這些失敗大致可分為三類:

1.崩潰失敗:組件在沒有警告的情況下停止工作;2.遺漏:組件發送了消息,但其它節點并沒有收到消息;3.拜占庭:組件的表現是任意的。在受控環境下出現這類故障是無關緊要的,其中可能沒有什么惡意行為。相反,這類錯誤會發生在所謂的「對抗性環境」下。基本上,當一組分散的獨立行動者充當網絡中的節點時,這些行動者可能選擇以「拜占庭」的方式行事。這意味著他們會惡意選擇更改,阻止或不發送消息。

考慮到這些問題,我們的目標是設計一種協議,它可允許具有故障組件的系統,仍可實現共同目標,并提供有用的服務。

鑒于每個系統都會有故障,我們在構建分布式系統時必須做出的核心假設是,即使其部件偏離了正常行為,它也能繼續存活,無論是否由于非惡意行為還是因為惡意行為。

從廣義上講,制作分布式系統時,需考慮兩種類型的模型:

1)簡單的容錯

在一個簡單的容錯系統中,我們假設系統的所有部分都執行以下兩種操作之一:它們要么完全遵循協議,要么失敗。這種類型的系統,應能夠處理脫機或失敗的節點。但它不必擔心節點表現出隨意或惡意行為。

2)拜占庭容錯

簡單的容錯系統在不受控制的環境當中,并不是很有用。在一個去中心化的系統當中,節點是由獨立的參與者控制的,它們之間在開放的、無需許可的互聯網上進行通信,我們還需要為那些選擇惡意或「拜占庭」行為的節點進行設計。因此,在拜占庭容錯系統當中,我們假設節點是可以失敗或惡意的。

2b)BAR容錯

盡管大多數真實系統都被設計為能夠承受拜占庭式的故障,但一些專家認為它過于籠統,并沒有考慮到「理性」故障。換句話說,根據激勵的情況,節點是可以誠實的,也可以是不誠實的。如果激勵措施足夠高,那么即使是大多數節點也可能會做不誠實的事。

更正式地講,這被定義為BAR模型,它同時考慮了拜占庭和理性故障問題。BAR模型假設有三種類型的成員:

1.拜占庭:拜占庭節點是惡意的,它們試圖搞砸你;2.利他主義者:誠實的節點總是遵循協議。3.理性節點:理性節點只有在他們認為合適時才會遵循協議。

經濟學家:預計歐洲央行將在5月會議上加息25個基點:5月4日消息,大華銀行經濟學家Lee SueAnn:預計歐洲央行將在5月的會議上加息25個基點,因為該行愿意撲滅銀行業的困境之火,而且最新預測證實,歐洲央行可能并不認為抗通脹斗爭已經結束。從長遠來看,歐洲央行25個基點的加息幅度將是謹慎的。(金十)[2023/5/4 14:42:12]

D)消息傳遞

如上面所述,分布式系統中的計算機,通過一臺或多臺其他計算機之間的「消息傳遞」進行通信和協調。消息可使用任何消息傳遞協議進行傳遞,無論是HTTP,RPC還是為特定實現構建的自定義協議。

有兩種類型的消息傳遞環境:

1)同步

在同步系統中,假設消息將在某個固定的已知時間內進行傳遞。

同步消息傳遞在概念上并沒有那么復雜,因為用戶擁有一個保證:當他們發送消息時,接收組件將在特定時間范圍內獲得它。這允許用戶使用固定的時間上限來建模他們的協議,該上限是消息到達那里所需的時間。

但是,在真實的分布式系統中,這種類型的環境并不是那么實用,因為計算機可能會崩潰或脫機,并且可能會丟失、復制、延遲或無序接收消息。

2)異步

在異步消息傳遞系統中,假設網絡可能無限延遲消息,復制消息或無序傳遞消息。換句話說,消息接收的時間長度,沒有設置固定的上限。

在分布式系統達成共識是什么意思?

到目前為止,我們已經了解了分布式系統的以下屬性:

進程的并發性;

缺乏全局時鐘;

存在故障進程;

消息傳遞

接下來,我們將專注理解在分布式系統中實現「共識」意味著什么。但首先,重申我們之前提到的內容會是非常重要的:目前有數百種不同的用于分布式計算的硬件和軟件架構。

其中最為常見的形式被稱為復制狀態機。

復制狀態機

復制狀態機是一種確定性狀態機,很多計算機會對其進行復制,但它是作為單個狀態機運行的。這些計算機中的任何一臺都可能出現故障,但狀態機仍是可運行的。

在復制狀態機中,如果交易有效,則一組輸入將導致系統狀態轉換到下一個狀態。一筆交易是在一個數據庫中進行的原子操作。這意味著操作要么完全完成,要么根本不發生。在復制狀態機中維護的交易集被稱為「交易日志」。

從一個有效狀態轉換到下一個有效狀態的邏輯,被稱為「狀態轉換邏輯」。

復制狀態機是一組分布式計算機,它們都以相同的初始值開始。對于每個狀態轉換,每個進程決定下一個值。而達到「共識」,意味著所有計算機必須共同商定該值的輸出。

反過來,這在系統中的每臺計算機上都保持一致的交易日志。

復制狀態機必須不斷地將新交易接收到該日志當中。它必須這樣做,盡管存在以下這些因素:

有些計算機會出現故障;

網絡不可靠,消息可能會出現無法傳遞、延遲或出現故障的現象;

沒有全局時鐘來幫助確定事件的順序;

而這些,就是任何共識算法要去實現的基本目標。

確定了共識問題

如果算法滿足以下條件,則我們說該算法達成了共識:

協議:所有非故障節點決定相同的輸出值;

終止:所有非故障節點最終決定某些輸出值;

從廣義上講,共識算法通常假設系統中有三種類型的參與者:

提議者;

接受者;

學習者;

提議者通常也被稱為領導者或協調者。接受者是監聽來自提議者的請求,并用值進行響應的進程。學習者是系統中的其它進程,它們學習決定的最終值。

通常,我們可以通過三個步驟定義共識算法:

第1步:選舉

進程選擇單個領導者來做出決策。

領導者提出下一個有效的輸出值。

第2步:投票

無故障進程會監聽領導者提出的值,對其進行驗證,并將其作為下一個有效值。

OpenSea實施對NFT稀有度進行排名的新協議:金色財經報道,NFT市場OpenSea宣布在其平臺內實施Open Rarity,這是一種為NFT提供可驗證稀有度計算的協議。該協議使用透明的數學方法來計算稀有度。OpenSea表示,稀有的NFT的數字會比較小,而具有與許多其他NFT相似屬性的NFT的數字會比較大。因此,市場強調買家在考慮購買NFT時可以看到可靠的“稀有度排名”。(thebharatexpressnews)[2022/9/23 7:15:39]

第3步:決定

無故障進程必須就單個正確的輸出值達成共識。如果它收到滿足某些標準閾值數量的相同投票,則進程將決定該值。

否則,步驟重新開始。

重要的是,每個共識算法都會有不同:

術語

如何處理投票的進程;

如何確定最終值的標準;

盡管如此,如果我們可使用這個通用進程來構建一個算法,它可保證上面定義的一般條件,那我們就有了一個能夠達成共識的分布式系統。

聽起來,很簡單,對嗎?

FLP不可能

…并不是的。但是你很快就會了解到了!

回想一下,我們如何描述同步系統和異步系統之間的區別:

同步環境是在固定時間范圍內傳遞消息的地方;

異步環境是消息的傳遞無保證的地方;

這種區別很重要。

在同步環境中達成共識是可能的,因為我們可假設消息傳遞所需的最長時間。因此,在這種類型的系統中,我們可允許系統中的不同節點輪流提出新的交易,輪詢多數投票,如果在最長時限內未提供提議,則跳過任何節點。

但如前所述,假設我們在同步環境中操作,在受控環境之外進行是不實際的,例如具有同步原子鐘的數據中心。

實際上,大多數環境不允許我們進行同步假設,所以我們必須為異步環境而進行設計。

如果我們不能在異步環境中假設最大的消息傳遞時間,那么實現終止會困難得多。請記住,達成共識必須滿足的條件之一是「終止」,這意味著每個非故障節點必須決定某些輸出值。

這被稱為「FLP不可能結果」。它是如何得到這個名字的呢?好吧,很高興你能問這個問題!

研究人員Fischer,Lynch和Paterson在1985年撰寫的《在一個錯誤進程中不可能達成分布式共識》這一論文中提到,即使只是一個錯誤的進程,也無法在確定性異步進程中達成共識。

基本上,由于進程可能在不可預測的時間點失敗,因此它們也可能在阻止達成共識的恰當時機失敗。

這個結果對分布式計算領域而言是一個巨大的頭疼點。盡管如此,科學家們還是在繼續努力尋找繞過FLP不可能的方法。

在較高的層面上,有兩種方法可以避免FLP不可能:

使用同步假設;

使用非確定論;

現在,讓我們深入了解這兩種方法。

方法1:使用同步假設

好吧,我知道你在想什么:這到底意味著什么?

讓我們重新審視我們的不可能結果。這里有考慮它的另一種方式:FLP不可能結果基本上表明,如果我們不能在系統中取得進展,那么我們就無法達成共識。換句話說,如果異步傳遞消息,則無法保證終止。回想一下,終止是一個必需條件,這意味著每個非故障節點最終必須決定一些輸出值。

但是,如果我們不知道異步網絡何時會傳遞消息,我們如何才能保證每個非故障進程都能決定一個值?

要明確的是,這一發現并未表明共識無法實現,相反,由于不同步,在固定的時間內無法達成共識。說共識是「不可能的」,只是意味著共識「并非總是可行的」,這是一個微妙但至關重要的細節。

避免這種情況的一種方法是使用超時設定。如果在確定下一個值沒有進展,我們會等待一個時間段,然后再重新開始步驟。

正如我們即將看到的那樣,像Paxos和Raft這些共識算法就是這樣的。

Paxos算法

Paxos算法的提出是在20世紀90年代,這也是第一個真實可用的容錯共識算法。它是首個被廣泛采用的共識算法,并曾被谷歌和亞馬遜等全球互聯網公司用于構建分布式服務。

BTC最近活躍5年以上的供應百分比達到歷史新高:金色財經報道,Glassnode數據顯示,BTC最近活躍5年以上的供應百分比剛剛達到23.675%的歷史新高,之前的數值為23.674%。[2022/7/18 2:20:25]

Paxos的工作方式如下:

階段1:準備請求

提議者選擇新的提案版本號(n),并向接受者發送「準備請求」。

如果接受者收到準備請求,其n大于他們已經回復的任何準備請求,接受者發出(“ack,”n,n’,v’)或(“ack,”n,^,^)。

接受者以承諾回應,表示不再接受編號小于n的任何提案。

接受者建議他們已接受的最高數提案的值(v),否則,他們會以^回應;

階段2:接受請求

如果提議者收到來自大多數接受者的響應,那么它可以發出一個接受請求,其數量為n,值為v。

n是準備請求中出現的數字。

v是響應中編號最高的提議值。

如果接受者收到一個接受請求(“accept,”n,v),它會接受該提議,除非它經響應了一個數字大于n的準備請求。

階段3:學習階段

每當接受者接受提議時,它會響應所有學習者(“accept,”n,v)

學習者從大多數接受者那里接收(“accept,”n,v),決定v,并向所有其他學習者發送(“decide,”v);

學習者接受(“decide,”v)并決定v;

來源:https://www.myassignmenthelp.net/paxos-algorithm-assignment-help

嗯!困惑了嗎?我知道這里有很多信息需要去消化。但是,等等……還有更多的信息!

我們現在知道,每個分布式系統都是有故障的。在Paxos算法中,如果提議者失敗,則可延遲決策。Paxos通過從第1階段的新版本號開始處理此問題,即使之前的嘗試從未結束。

我不會詳細介紹,但在這種情況下,恢復正常運行的進程是非常復雜的。

Paxos難以理解的主要原因,是它的很多實現細節都留給了讀者:例如我們如何知道提議者什么時候失敗?我們是否使用同步時鐘來設置超時時間,來決定提議者何時失敗?等等。

Paxos在領導者選舉,故障檢測和日志管理等內容是模糊或完全不明確的。

這種設計選擇最終成為Paxos最大的缺點之一,它不僅難以理解,而且也很難實現。反過來,這使得分布式系統領域也難以駕馭。

到目前為止,你可能想知道同步假設的來源。

在Paxos中,雖然算法中沒有明確的超時,但在實際實現時,在一些超時時間之后選擇一個新的提議者是實現終止所必須的。否則,我們就無法保證接收者會輸出下一個值,系統可能會因此停止運行。

Raft算法

2013年,Ongaro和Ousterhout發布了一種名為Raft的復制狀態機共識算法,其核心目標是可理解性

我們從Raft算法學到的一個重要新事物,是使用共享超時的概念來處理終止問題。在Raft中,如果你崩潰了并重新啟動,你需要等待至少一個超時時間,才能讓自己被宣布為領導者,并保證你取得進步。

但等等...拜占庭環境呢?

雖然傳統的共識算法能夠使用某種程度的同步假設在異步環境中發展,但它們不是拜占庭容錯的。它們只是崩潰容錯的。

崩潰故障是較容易處理的,因為我們可以將進程建模為工作或崩潰,進程不能惡意行事或撒謊。因此,在崩潰容錯系統中,分布式系統是可構建的,其中簡單的多數參與者就足以達成共識。

而在開放和去中心化的系統中,用戶無法控制網絡中的節點。相反,每個節點都會針對其各自的目標做出決策,這可能與其他節點的目標沖突。

在拜占庭系統中,節點具有不同的激勵,它們可以撒謊、協調或任意行動,你不能假設簡單的多數節點就能夠達成共識。一半或更多的誠實節點是可相互協調和欺騙的。

Polygon 部署自定義區塊鏈擴展解決方案“Avail”:6月29日消息,Polygon 已經部署了自定義區塊鏈擴展解決方案“Avail” ,供開發人員在 Polygon 主鏈和其他區塊鏈上啟動獨特的區塊鏈應用程序。新產品將允許開發人員“脫鏈”訪問區塊鏈數據,這意味著他們不需要不斷檢查來自網絡的數據以查找部署在 Polygon 上的應用程序。Avail可以部署在任何與以太坊虛擬機 (EVM) 兼容的區塊鏈上,基于 Avail 構建的應用程序將使開發人員能夠更新、分叉和更改其區塊鏈處理執行的方式,這對于可能需要修補錯誤、試驗執行或只是減少對外部鏈依賴的 DeFi 和游戲開發人員來說至關重要。

此前4月份,Polygon曾宣布將于第二季度推出可拓展性區塊鏈網絡Avail測試網。[2022/6/29 1:40:05]

然而,Raft并不是為了容忍這種行為而設計的。例如,如果當選的領導者是拜占庭,并且與其他節點保持強大的網絡連接,則可能會危及系統。Raft和Paxos是簡單的容錯,但不是拜占庭容錯。

拜占庭將軍問題

試圖建立一個可處理沖突信息進程的可靠計算機系統,被稱為「拜占庭將軍問題」。拜占庭容錯協議應該能夠實現其共同目標,即使是遭受來自節點的惡意行為。

LeslieLamport,RobertShostak和MarshallPease撰寫的《拜占庭將軍問題》論文,提供了解決拜占庭將軍問題的第一個證明:它表明具有x個拜占庭節點的系統,必須至少有個總節點,才能達到共識。

原因如下:

如果x節點出現故障,則系統需要與節點協調后才能正常運行并且沒有響應)。但是,我們必須為不響應的可能沒有錯誤的X節點做準備,它也可能是做出回應的X節點。如果我們希望非故障節點的數量超過故障節點的數量,我們至少需要>x,因此,n>3x1是最佳的。

但是,該論文中演示的算法僅適用于同步環境。這不是一個好消息!看起來,我們只能得到一個或另一個,對嗎?

但為什么不包括兩個呢?

簡而言之,建立一個能夠承受異步環境和拜占庭環境的共識算法......好吧,這就像創造奇跡一樣。

像Paxos和Raft這樣的算法,是眾所周知且被廣泛使用的。但也有很多學術工作正在嘗試研究拜占庭異步的共識算法。

所以系上你的安全帶......

我們將要實地考察理論學術論文的領域。

你應該感到興奮!還記得我們之前討論過的「創造奇跡」嗎?

我們將查看兩種算法,這些算法要比以往任何時候都更接近于打破拜占庭異步的障礙。

DLS算法

由Dwork,Lynch和Stockmeyer共同撰寫的論文《部分同步存在下的共識》引入了拜占庭容錯共識的一項重大進步:它定義了如何在一個「部分同步系統」中達成共識,該算法也因三位作者的名字而被稱為「DLS」算法。

你可能還記得,在同步系統中,消息從一個處理者發送到另一個處理者所需的時間有一個已知的固定上限。在異步系統中,則不存在固定的上限。

而部分同步,則位于同步系統和異步系統之間。

該論文解釋了部分同步假設的兩個版本:

假設消息傳遞的長短存在固定邊界。但它們不是先驗已知的。無論實際的界限如何,目標都是達成共識。

假設消息傳遞的上限是已知的,但它們只能保證在某個未知時間開始。目標是設計一個能夠達成共識的系統,無論何時發生。

以下是DLS算法的工作原理:

一系列round分為「嘗試」和「鎖定釋放」階段。

每一輪都有一個提議者,并從每個進程開始,傳達他們認為正確的值。

如果至少有個進程傳達了一個值,則提議者「提出」該值。

當進程從提議者處接收建議值時,它必須鎖定該值,然后廣播該信息。

如果提議者從x1進程接收到他們鎖定某個值的消息,則將其作為最終值提交。

DLS是一項重大技術突破,因為它創造了一種新的網絡假設類型,即部分同步,其還證明了這種假設的共識是可能的。DLS論文中另一個必要的內容,是將拜占庭和異步設置達成共識的問題分為兩個方面:安全性和活躍性。

安全性

這是我們前面討論過的「協議」屬性的另一個術語,其中所有非故障進程都對同一輸出達成一致。如果我們能夠保證安全性,則我們能夠保證整個系統保持同步。我們希望所有節點同意交易日志的總順序,盡管會存在失敗和惡意行為者的干擾。而違反安全性,意味著我們最終會得到兩個或更多有效的交易日志。

活躍性

這是我們早期討論的「終止」屬性的另一個術語,其中每個非故障節點最終決定某些輸出值。在區塊鏈設置當中,活躍性意味著區塊鏈通過添加有效新區塊而不斷增長。活躍性是很重要的,因為它是網絡繼續有用的唯一方式,否則,網絡就會停滯不前。

正如「FLP不可能」告訴我們的,在完全異步的系統中是無法達成共識的。而DLS論文認為,為實現活躍條件而做出部分同步假設,足以克服FLP不可能性。

因此,這篇論文證明了算法不需要使用任何同步假設來實現安全條件。

很明確,對吧?如果不是,不要擔心。讓我們深入探討這個概念:

請記住,如果節點沒有決定某個輸出值,系統就會暫停。因此,如果我們做出一些同步假設,以保證終止,并且其中一個會失敗,那么這也會使系統停止。

但是,如果我們設計一個算法,其中我們假設了超時,而如果同步假設失敗,則會帶來導致兩個有效交易日志的風險。

這比前一種選擇會危險得多。如果服務損壞,則沒有必要提供有用的服務。

基本上,擁有兩個不同的區塊鏈,會比整個區塊鏈停止會更糟。

分布式系統總是需要權衡利弊的,如果你想克服限制,你必須在其它地方做出犧牲。在這種情況下,將關注點分解為安全性和活躍性是非常好的。它允許我們構建一個在異步設置中安全,但仍需要某種形式超時來保持生成新值的系統。

盡管DLS論文提供了所有內容,但DLS算法從未真正被廣泛實施,或用于真實世界的拜占庭式設置。這可能是由于DLS算法的核心假設之一,是使用同步處理器時鐘。實際上,同步時鐘容易受到大量攻擊,并且它在拜占庭容錯設置中并不是很好。

PBFT算法

另一種由MiguelCastro和BarbaraLiskov于1999年發表的拜占庭容錯算法,被稱為「實用拜占庭容錯」。對于展示拜占庭行為的系統而言,它被認為是一種更為「實用」的算法。

從這個意義上來說,「實用」意味著它可以在互聯網等異步環境中運行,此外它也進行了一些優化,使其較以前的共識算法要更快。該論文中提到,以前的算法雖然被證明是「理論上可行的」,但它們要么太慢,無法被使用,要么是為了安全性而做了假定同步。

正如我們已經解釋的那樣,在異步設置中,這可能是非常危險的。

簡而言之,PBFT算法表明,假設/3個節點出現了故障,它可以提供安全性和活躍性。正如我們之前討論的那樣,這是我們需要容忍拜占庭故障的最小節點數。因此,該算法的抵抗性是最理想的。

無論有多少節點出現故障,該算法都能夠提供安全性。換句話說,它沒有為安全性而假設同步。然而,該算法確實依賴于同步性來實現活躍:

最多的情況下,/3個節點可出現故障,并且消息延遲的增長速度不會超出某個時間限制。

因此,PBFT通過使用同步假設來保證活躍性,從而規避了FLP不可能性。

該算法通過一系列「view」,其中每個view都有一個「主要」節點,其余view都是「備份」節點。以下是有關PBFT工作方式的逐個步驟:

在客戶端上發生了一筆新的交易,并向主要節點廣播;

主要節點將它復制到所有的備份節點;

備份節點執行交易,并向客戶端發送回復;

客戶端希望從備份節點處獲得x1個與結果相同的回復。這是最終結果,且狀態轉變發生了。

如果領導者沒有發生錯誤,協議會工作得很好,然而,檢測不良主要節點和重新選擇新主要節點的過程是非常低效的。例如,為了達成共識,PBFT需二次數量的消息交換,這意味著每臺計算機都必須與網絡中的每臺其他計算機進行通信。

雖然PBFT是對以前算法的改進,但對于存在大量參與者的真實世界應用而言,它的擴展性是不夠的。但是,嘿,至少在涉及故障檢測和領導者選舉方面,該算法會顯得更明確一些。

承認PBFT算法的貢獻是重要的,它結合了重要的革命思想,而新的共識協議可從中學習和進行改進。

例如,Tendermint是一種受PBFT影響很大的新共識算法。在Tendermint的「驗證」階段,其使用了兩個投票步驟來決定最終值。與PBFT算法的主要區別在于,Tendermint的設計,會更加實用。

例如,Tendermint每輪都會輪換新的領導者。如果當前輪次的領導者在一段時間內沒有響應,其會跳過領導者,并且算法會簡單地移動到帶有新領導者的下一輪。這實際上比每次需要進行view更改和選擇新領導者時使用點對點連接更有意義。

方法2:非確定論

正如你從上面了解到的,大多數拜占庭容錯共識協議,最終使用某種形式的同步假設來克服FLP不可能性。然而,還有另一種方法可以克服FLP不可能性,即:非確定論。

進入中本聰共識

正如我們剛剛了解到的那樣,在傳統的共識中,f被定義為提議者和一群接受者必須全部協調和通信,以決定下一個值。

這太復雜了,因為它需要知道網絡中的每個節點,以及每個節點與其它節點的通信。簡而言之,它不能很好地擴展,并且不能在開放、無需許可的系統中工作。

而中本聰共識的聰明之處,在于概率性地完成了上述的過程。相比每個節點都同意一個值,f(x)是使所有節點都同意值是正確的可能性。

等等,這意味著什么?

拜占庭容錯

相比選舉一個領導者,然后與所有節點協調,而是根據哪個節點能夠最快解決計算難題來解決共識。比特幣區塊鏈中的每個區塊,都由解決這個難題的節點添加。擁有最多累積工作量的鏈即是標準鏈。最長的鏈,不僅可作為區塊序列的證明,而且可以證明它來自最大的CPU功率池。因此,只要大部分CPU功率由誠實節點控制,它們將繼續產生最長鏈,并超過攻擊者。

區塊獎勵

中本聰共識,通過假設節點為爭奪下一個區塊,會擴展計算投入的方式而工作。該算法的聰明之處,在于經濟上激勵節點重復執行這種計算,以獲取隨機獲得區塊獎勵的機會。

抵抗女巫攻擊

解決這個難題所需的工作量證明,使得協議本身具有抵抗女巫攻擊的特性。它不需要PKI或任何其他花哨的身份驗證方案。

對等gossip

中本聰共識的主要貢獻,是使用了gossip協議,它更適合于無法假設非故障節點間通信的對等設置。相反,我們假設節點僅連接到其它節點的子集。然后,我們使用對等協議,其中消息在節點之間互相傳播。

在異步環境中,并不是「技術」安全的

在中本聰共識中,安全保障是概率性的,我們會不斷增長最長鏈,而每個新區塊都會降低惡意節點嘗試構建另一個有效鏈的可能性。

因此,中本聰共識在技術上并不保證異步設置的安全性。讓我們花點時間了解下原因。

對于在異步設置中實現安全性條件的系統,我們應該能夠在異步網絡條件下維護一致的交易日志。考慮它的另一種方式,是節點可隨時脫機然后再返回在線狀態,并使用區塊鏈的初始狀態來確定最新的正確狀態。任何誠實節點都可以查詢過去的任意狀態,并且惡意節點不能提供誠實節點認為是真實的欺詐性信息。

在本文討論的前幾種算法中,這是可能的,因為我們確定性地在每一步完成一個值。只要我們終止每個值,我們就可以知道過去的狀態。然而,比特幣在「技術上」不是異步安全的,其原因是有可能存在一個網絡分區,其中攻擊者具有足夠強大的算力來創建一條比誠實鏈更快的替代鏈。在這個替代鏈上,攻擊者可嘗試改變他自己的一筆交易來收回他所花的錢。

不可否認的是,這就要求攻擊者獲得大量的算力,而這需要大量的資金。

從本質上講,比特幣區塊鏈的不可更改性來源于這樣一個事實:即大多數礦工實際上并不想采用替代鏈。這是因為,要掌握足夠的算力以使其余礦工采用替代鏈是很困難的。換句話說,成功創建替代鏈的可能性是非常低的,它幾乎可以忽略不計。

中本聰共識vs傳統共識算法

出于實際目的,中本聰共識是拜占庭容錯的。但它顯然沒有達成共識研究人員傳統上所假設的共識。因此,它最初被視為完全脫離拜占庭容錯世界。

感謝你,中本聰!

根據設計,中本聰共識可以讓任意數量的節點以開放式的方式參與系統,而且沒有人必須要知道完整的參與者集。這一突破的重要性不容小覷!

它比以往的共識算法要更簡單,它消除了以前共識算法在點對點連接、領導者選舉、二次通信開銷等方面的復雜性。你只需在任何計算機上啟動比特幣協議軟件,并開始挖礦任務。

這使其可在真實環境中輕松部署,它確實是比PBFT更「實用」的共識算法。

結論

現在你應該對分布式系統共識算法的簡要基礎知識有所了解了。對于分布式計算而言,這是一個漫長而曲折的研究和獨創性之旅。我希望這篇文章能夠有助于你對這個領域有更多的了解。

中本聰共識是一項真正的創新,它讓研究人員、科學家、開發者和工程師在共識協議研究中不斷開天辟地。

還有一個全新的協議系列正在不斷開發中,嗯,它就是權益證明,作者在接下來的文章中會談到,敬請關注!

注:為了簡單目的,作者跳過了很多重要的論文和算法。例如BenOrr的CommonCoin也使用了概率方法,但它沒有最佳的抵抗性。其它算法如哈希現金也使用PoW,但其是用于限制電子郵件垃圾郵件和拒絕服務攻擊目的的。這篇文章遺漏了很多傳統的共識協議!但作者認為,上述內容足以幫助你了解傳統共識算法和中本聰共識算法的不同。

特別感謝ZakiManian提出的有關分布式共識的所有問題。

Tags:區塊鏈AXOFLPBFT魔獸幣是有使用區塊鏈技術嗎axo幣的最新價格FLP價格bft幣最高價

火必交易所
BTC下降三角區間內震蕩整理 等待變盤_SDT

技術圖形4小時走勢,BTC從前期9700美元短時快速拉升至12000美元,并重新站上前期從7500美元至19年最高位14000美元中期上行趨勢線.

1900/1/1 0:00:00
CFTC 報告:機構投資比特幣興趣并未上升 但名義價值集中度提高_比特幣

原文標題:《2Q19CMEBitcoinFuturesAnalysis:Growinginstitutionalinterest?Notquite》作者:RyanTodd編譯:區塊律動Block.

1900/1/1 0:00:00
德勤報告:中國希望利用區塊鏈作為“戰略武器”_IDEO

摘要:根據四大會計師行之一德勤會計師事務所報告,多達73%的中國企業將區塊鏈看作戰略重點。在題為“德勤2019年全球區塊鏈調查”的報告中,該公司對11個國家的1,386名企業代表進行了調查,其中.

1900/1/1 0:00:00
IMF總裁被提名為歐洲央行行長候選人 曾多次發表支持區塊鏈、加密貨幣相關言論_INE

據CNBC今日消息,國際貨幣基金組織總裁ChristineLagarde被提名為歐洲歐央行行長候選人,或取代MarioDraghi擔任歐洲央行行長.

1900/1/1 0:00:00
Facebook面臨全球監管合規挑戰,正申請紐約州BitLicense_FACE

摘要:據路透社報道稱,社交媒體巨頭Facebook想要創建一個全球加密貨幣和支付網絡的計劃正面臨著前所未有的監管障礙。雖然其正在采取措施來滿足世界各地的監管機構的要求,但許多專家擔心這仍還不夠.

1900/1/1 0:00:00
世界貨幣體系需要新的價值錨定物,但不會是Facebook的Libra_LIB

“Libra本質上有利于推動數字文明的進展,但對中小國家的主權貨幣會帶來一定的沖擊,甚至在美國監管機構介入后有可能淪為美元意志在不發達國家的延伸.

1900/1/1 0:00:00
ads