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

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

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

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

拜占庭帝國這個名稱則到18世紀開始普及，西方是英、法、普、奧、西等基督教民族國家，東方則是由異教徒奧斯曼帝國所佔據。當時西方學者以孟德斯鳩為首正熱衷於啟蒙運動，認為東方保守落後，西方才是羅馬帝國的傳人。於是形成一種打壓東方的意識，並附和沃爾夫的主張，將東羅馬改稱拜占庭，以便將東羅馬與原本的羅馬帝國切割。

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

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

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

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

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

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

 

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