最最最簡化的SCP,希望大家能看得懂。
協議系統允許一組參與者就某事達成相同的決定——例如,午餐吃什麼。在區塊鏈中,則決定了那些交易可以寫入到新的區塊上。
在了解共識協議前,先提一下拜占庭將軍問題(Byzantine Generals Problem),它是由Leslie Lamport、Robert Shostak和Marshall Pease在其論文中提出的分散式對等網路通信容錯問題。
論文描述了一組拜占庭將軍分別各率領一支軍隊共同圍困一座城市。條件在於所有的軍隊必須一起進攻或一起撤離,否則會導致災難性結果。因為各位將軍分處城市不同方向,他們只能通過信使互相聯絡,通知其他將軍自己投票給進攻還是撤退,這樣一來每位將軍根據自己的投票和其他所有將軍送來的資訊就可以知道共同的投票結果而決定行動策略。
系統的問題在於,將軍中可能出現叛徒,傳給其他將軍假的訊息。也不能排除信使被敵人截殺,甚至被敵人間諜替換等情況。
拜占庭容錯,又或稱拜占庭容錯協議(Byzantine Fault Tolerance, BFT)正是解決這個情境題的經典解答,所以,我們常聽見的「拜占庭容錯協議」其實是答案,背後要解決的,是上述的「拜占庭將軍問題」。
拜占庭容錯協議的做法,就是基於團隊會忠誠執行指令的前題下,所有人只需要執行最大多數的共同指示即可。說穿了,就是少數服從多數,將錯誤的信息預計在內,再加以排除。
Leslie Lamport等人在論文中證明,當叛變者不超過1/3時,保證一定能達到一致結果。假如節點總數為 N,故障節點數為 F,則當 N >= 3F + 1 時,問題才能有解。
(大家有興趣也可以看看李永樂老師的影片,講得很淺顯易懂: https://youtu.be/e9KVmyI1eCg )
但傳統的拜占庭協議解決的是「封閉系統」中的共識問題。既然要少數服從多數,就要先知道「多數」是什麼,也就是節點成員資格要經過審查,不是想加入就能隨時加入,是中心化的系統。
聯邦拜占庭協議(Federated Byzantine Agreement, FBA)是對拜占庭協議的一種改編,應用在具有「開放」成員資格的系統,不必提前知道和驗證每個節點。成員資格是開放的,節點能隨時加入,也能隨時退出。節點間無須(也無法)知道所有的節點成員。
Stellar.org的首席科学家David Mazières教授的論文介绍了恒星共識協議(Stellar Consensus Protocol, SCP),同時它也是聯邦拜占庭協議第一個安全可證的實作成果,所以說恒星共識協議是基於聯邦拜占庭協議算法的。
簡單的講,
BFT:中心化、少數服從多數。
FBA:改進為去中心化。
SCP:真正實作FBA的結果(前面兩個只是理論)。
投票是SCP的核心,過程涉及多輪聯邦投票(Federated Voting)(本文略過聯邦投票的細節)。但在具有動態成員資格的去中心化網路中,不可能提前知道有多少節點,以及有多少節點才叫做多數,要怎麼決定投票結果呢?
聯邦投票採用仲裁切片(quorum slice)來解決這個問題。仲裁切片就是節點所信任的一群節點集合(Pi安全圈指的就是這個嗎?),會互相傳達投票的信息。每個節點都定義了自己的仲裁切片,本身也是仲裁切片中的一員。
從某一個節點開始,添加它的仲裁切片的成員,然後再添加這些成員的仲裁切片的成員,依此類推。直到最後沒有新的節點可以添加,就形成了一個仲裁(quorum)。仲裁內的節點都接受相同的投票結果。
沒有剩餘的節點要添加。這就是一個仲裁。
事實上,每個節點可能有多個仲裁切片。要形成仲裁,只需選擇其中一個切片並添加成員;然後為每個成員選擇任何一個切片並添加這些成員,依此類推。這意味著每個節點都是許多可能的仲裁的成員。
產生不同的仲裁。
SCP要求網路必須具備仲裁交集(quorum intersection)的特性,任何兩個仲裁總是至少有一個節點重疊。這表示如果任何仲裁同意X,則沒有其他仲裁可以同意"非X",因為它一定包含第一個仲裁中已經投票給X的某個節點。
總是會重疊的。
一個節點可以從他們的廣播消息中看到其他節點是如何投票的,進而可能改變自己的投票,最後達到一個仲裁的節點全都接受相同結果(本文略過聯邦投票的細節)。
如果上面這些專有名詞看得一頭霧水,我再試著舉例說明。
人際關係是一個很複雜的網路(據說世界上互不相識的兩個人,只需要6個中間人,就能夠相互建立起聯結),假設小安從他信任的朋友中任意挑選幾位,他挑了小浪跟小黑(小安+小浪+小黑就是小安的仲裁切片),小浪也從自己信任的朋友中挑選了阿佑和小程,阿佑又選了小逸。一直這樣持續下去,到沒有新朋友可以加入,就形成了一個小群體(組成一個仲裁)。
當然,小安也可以一開始是選大衛跟艾瑪(不同的仲裁切片),這樣組成新群體的成員可能就跟上一個群體不一樣。
而遠在地球另一端有位阿正,他可能透過朋友的朋友的朋友跟小逸牽上關係,所以這兩個群體就有了仲裁交集。
小安這群人可能決定了中午要吃排骨飯,阿正這群人還沒做出決定,但因為有小逸這位中間人,所以最後阿正這群人也決定要吃排骨飯。
再次強調!本文略過了聯邦投票的細節,因為太複雜了,另開篇幅在 https://yuanrui919.github.io/FederatedVoting/ 說明,所以這個例子是在解釋仲裁、仲裁切片,並非解釋投票的過程,不要誤解了。
最後,我猜測Pi的安全圈跟仲裁切片有關,我的節點的仲裁切片可能是由我的安全圈的人組成(前提是這些人也有架節點),除此之外,應該還會包含官方的節點。不過還是要等到開放主網才能確定。