拜占庭將軍問題的前世與區塊鏈今生

文/國立中央大學資工系蔡宗翰教授 蔡宗翰

拜占庭將軍問題(The Byzantine Generals Problem)是一個分散式對等網路通信容錯問題,如今被廣泛應用於區塊鏈等領域。然而,為何取名叫拜占庭將軍?為什麼不是英國將軍或中國將軍?讓深入研究拜占庭歷史的資工學者蔡宗翰教授為您分析。

拜占庭史上第一將軍貝利撒留 (500–565)

拜占庭帝國指的是395年分家以後的東羅馬帝國,首都位於新羅馬,又稱為君士坦丁堡。它的國祚長達1061年,一直到1453年才被奧斯曼帝國(Ottoman Empire)滅亡。為何現在多數人不以東羅馬稱呼這個帝國呢?因為西羅馬在476年就滅亡,其疆域由蠻族王國繼承發展。800年時,一統中西歐的查理大帝(或譯查理曼)由教皇加冕為皇帝,雖然帝國一百年後就分裂,實際被許多大大小小的封建領主分治,但以中歐德奧為主的這個鬆散的政治聯盟就被稱為神聖羅馬帝國。1557年,神聖羅馬歷史學家赫羅尼姆斯·沃爾夫為了區分神聖羅馬與東羅馬,就取東羅馬首都的古稱拜占庭,來代替東羅馬。

395年狄奧多西大帝去世時,將羅馬帝國分給兩子。東帝國分長子阿卡狄奧斯,首都新羅馬(又稱君士坦丁堡、拜占庭);西帝國分次子霍諾留,首都羅馬。[圖片來源:Ancient History Encyclopedia]
拜占庭帝國這個名稱則到18世紀開始普及,西方是英、法、普、奧、西等基督教民族國家,東方則是由異教徒奧斯曼帝國所佔據。當時西方學者以孟德斯鳩為首正熱衷於啟蒙運動,認為東方保守落後,西方才是羅馬帝國的傳人。於是形成一種打壓東方的意識,並附和沃爾夫的主張,將東羅馬改稱拜占庭,以便將東羅馬與原本的羅馬帝國切割。

1700年時的歐洲,紅線為神聖羅馬帝國範圍。由圖可見異教徒Ottoman與東羅馬的疆域幾乎重合,可能因此引來西方的貶意。[圖片來源:維基百科]
拜占庭帝國從四世紀末以來,由於富庶地理位置重要,不斷面臨各種新興勢力入侵,大體上還能維持羅馬帝國半壁江山的規模。不過636年被新興的阿拉伯人在敘利亞擊敗以後,陸續丟失了中東、埃及、以及整個北非。因應防禦上的壓力,從641年的大鬍子君士坦斯二世皇帝開始,逐漸在領土上建立一個個塞馬州(Theme)。每個州就是一個軍區,每個軍區的軍政、行政、司法都由將軍管理。兵士平時耕種,自給自足,有點類似屯田制。若有需要,中央就會徵召部分塞馬州的軍隊與君士坦丁堡的禁衛軍組成聯軍,與敵人戰鬥。這個制度有效地讓拜占庭的局勢穩定下來,一次次擊退南方的阿拉伯人與北方的保加利亞人等入侵。

750年時的拜占庭帝國軍區圖 [圖片來源:維基百科]
然而,這個制度也留下了隱患。由於羅馬 — 拜占庭並沒有明確的繼承制度,皇帝的任何一個兒子或軍頭都有機會,因此塞馬州的將軍經常獨立叛變或是在作戰時叛變。例如741年皇子君士坦丁五世繼位。在742年新皇帝穿越小亞細亞迎戰阿拉伯人時,身兼亞美尼亞(Armeniacs)與奧普西金軍區(Opsikion)將軍的國舅阿爾塔瓦茲德叛變,襲擊新皇帝。君士坦丁五世被迫逃到阿摩利阿姆。可以說,拜占庭帝國史幾乎就是一本叛變史,據蔡老師推測,這應是Leslie Lamport在其1982年的論文將這個問題取名為拜占庭將軍的原因。(相對拜占庭來說,西歐的封建層層相屬較為穩定)

接下來蔡老師來說明拜占庭將軍問題本身。假設有一次敵人來犯,帝國徵召了 10支駐扎在不同地點的塞馬州軍隊去迎擊敵人,至少要有 6 支軍隊同時襲擊才能戰勝。每位將軍要如何保證至少有 6 支軍隊同時發起進攻?在古代,將軍們必須透過信使來互通訊息。論文中,Lamport 用數學證明,叛徒數必須少於總數的1/3,才能達成共識。

那為何今世的區塊鏈也會扯到古代的拜占庭將軍問題呢?因為區塊鏈想解決的也是一樣概念的問題:

各節點(將軍)送訊給所有節點(將軍),各節點(將軍)根據收到的所有消息決策,如何避免惡意節點(叛徒)影響共識的達成?

在過程中,若節點故意拒絕合作(惡意節點)或根本沒有說任何事情(錯誤節點),就是叛徒。因此,在比特幣的區塊鏈網路設計中 , 中本聰藉由密碼學與工作量證明機制 (Proof of Work,PoW)等方法來制約這些叛徒。透過PoW,節點必須付出大量的工作量(算力)去證明自己的忠誠,之後才能打包交易,送訊給其他節點。最長鏈機制則是各節點都沿著已知的最長鏈進行。所以即使惡意節點試圖破壞,也會付出很大的代價(付出超過整體系統一半的算力)。 在各節點都想最大化自己利益的情況下,PoW的確有效抑制了叛徒作惡的動機,進而解決了拜占庭將軍問題。

 

※本文轉載<拜占庭將軍問題的前世與區塊鏈今生>,感謝蔡老師提供。

人瀏覽過