拜占庭將軍比特幣

A. 如何理解拜占庭將軍問題

-----------------[簡單理解]-----------------
因為Lamport是分布式系統祖師爺級的人物，所以我就從分布式系統的角度來說。如果要保證分布式系統一致性和可用性，就必須處理錯誤節點，防止系統出現用戶可以觀察到的錯誤。拜占庭將軍問題在我看來是提出了一個錯誤模型。即錯誤節點可以做任意事情（不受protocol限制），比如不響應、發送錯誤信息、對不同節點發送不同決定、不同錯誤節點聯合起來干壞事等等。總之就是說，沒有節點會出現比這更嚴重的錯誤。很顯然，拜占庭錯誤是overly pessimistic的模型，因為這種錯誤實際環境中比較少見。那麼為什麼要研究這個模型呢？其中最簡單的一個原因是，如果某個一致性演算法能夠保證在系統出現f個拜占庭錯誤時保持系統一致，那麼這個演算法也就能夠保證在出現f個任意其他錯誤的時候也保持系統一致。錯誤模型有上限，肯定也就有一個下限（overly optimistic，沒有比它還要弱的模型）。這個下限就是『fail-stop』模型。這個模型的假設是：當一個節點出錯，這個節點會停止運行，並且其他所有節點都知道這個節點發生了錯誤。用同樣的邏輯，如果某個一致性演算法不能保證在系統出現f個錯誤的時候保持一致，那麼這個演算法也就沒法處理其他f個任意其他問題。應用這些錯誤模型，可以對不同演算法進行比較，也可以對具體演算法的cost進行討論。

-----------------[關於演算法]-----------------
第一個提出解決拜占庭將軍問題演算法的，是Lamport於1980年發表的 Reaching agreement in the presence of faults [http://research.microsoft.com/en-us/um/people/lamport/pubs/reaching.pdf]。這篇文章描述了當出現拜占庭錯誤的節點數（f）為1時的演算法。上面匿名用戶貼的鏈接是Lamport與1982年發表的文章，其中描述了第一個能夠處理f≥1的演算法。對這個問題的下一個進展是在1999年，是由Barbara Liskov（三位女性圖靈獎獲得者之一）提出。但是，具體列出這個進展之前，需要提一下拜占庭將軍問題和FLP定理之間的關系。除了錯誤模型，系統一致性的另一個重要方面是討論在不同系統假設（通信非同步/同步，任務完成時間有沒有規定上限）下達成一致性的可能性和相應演算法/協議。由於FLP（Impossibility of Distributed Consensus with One Faulty Process）決定了在非同步+無響應上限的情況下不存在能夠mask一個節點崩潰（強於fail-stop，節點崩潰，其他節點不知情）的有效演算法。所以解決拜占庭問題的演算法都會有同步假設（或者同步保證safety，或者同步保證liveness）。

B. Byzantinefailures——拜占庭將軍是什麼

拜占庭將軍問題是由萊斯利·蘭伯特提出的點對點通信中的基本問題。含義是在存在消息丟失的不可靠信道上試圖通過消息傳遞的方式達到一致性是不可能的。因此對一致性的研究一般假設信道是可靠的，或不存在本問題。

C. 比特幣如何防止篡改

比特幣網路主要會通過以下兩種技術保證用戶簽發的交易和歷史上發生的交易不會被攻擊者篡改：

• 非對稱加密可以保證攻擊者無法偽造賬戶所有者的簽名；

• 共識演算法可以保證網路中的歷史交易不會被攻擊者替換；

非對稱加密



• 非對稱加密演算法3是目前廣泛應用的加密技術，TLS 證書和電子簽名等場景都使用了非對稱的加密演算法保證安全。非對稱加密演算法同時包含一個公鑰（Public Key）和一個私鑰（Secret Key），使用私鑰加密的數據只能用公鑰解密，而使用公鑰解密的數據也只能用私鑰解密。





圖 4 - 51% 攻擊



• 1使用如下所示的代碼可以計算在無限長的時間中，攻擊者持有 51% 算力時，改寫歷史 0 ~ 9 個區塊的概率9：


• #include


• #include



• double attackerSuccessProbability(double q, int z) {


• double p = 1.0 - q;


• double lambda = z * (q / p);


• double sum = 1.0;


• int i, k;


• for (k = 0; k <= z; k++) {


• double poisson = exp(-lambda);


• for (i = 1; i <= k; i++)


• poisson *= lambda / i;


• sum -= poisson * (1 - pow(q / p, z - k));


• }


• return sum;


• }



• int main() {


• for (int i = 0; i < 10; i++) {


• printf("z=%d, p=%f\n", i, attackerSuccessProbability(0.51, i));


• }


• return 0;


• }



• 通過上述的計算我們會發現，在無限長的時間中，佔有全網算力的節點能夠發起 51% 攻擊修改歷史的概率是 100%；但是在有限長的時間中，因為比特幣中的算力是相對動態的，比特幣網路的節點也在避免出現單節點佔有 51% 以上算力的情況，所以想要篡改比特幣的歷史還是比較困難的，不過在一些小眾的、算力沒有保證的一些區塊鏈網路中，51% 攻擊還是極其常見的10。



• 防範 51% 攻擊方法也很簡單，在多數的區塊鏈網路中，剛剛加入區塊鏈網路中的交易都是未確認的，只要這些區塊後面追加了數量足夠的區塊，區塊中的交易才會被確認。比特幣中的交易確認數就是 6 個，而比特幣平均 10 分鍾生成一個塊，所以一次交易的確認時間大概為 60 分鍾，這也是為了保證安全性不得不做出的犧牲。不過，這種增加確認數的做法也不能保證 100% 的安全，我們也只能在不影響用戶體驗的情況下，盡可能增加攻擊者的成本。



總結



• 研究比特幣這樣的區塊鏈技術還是非常有趣的，作為一個分布式的資料庫，它也會遇到分布式系統經常會遇到的問題，例如節點不可靠等問題；同時作為一個金融系統和賬本，它也會面對更加復雜的交易確認和驗證場景。比特幣網路的設計非常有趣，它是技術和金融兩個交叉領域結合後的產物，非常值得我們花時間研究背後的原理。



• 比特幣並不能 100% 防止交易和數據的篡改，文中提到的兩種技術都只能從一定概率上保證安全，而降低攻擊者成功的可能性也是安全領域需要面對的永恆問題。我們可以換一個更嚴謹的方式闡述今天的問題 — 比特幣使用了哪些技術來增加攻擊者的成本、降低交易被篡改的概率：



• 比特幣使用了非對稱加密演算法，保證攻擊者在有限時間內無法偽造賬戶所有者的簽名；

• 比特幣使用了工作量證明的共識演算法並引入了記賬的激勵，保證網路中的歷史交易不會被攻擊者快速替換；



• 通過上述的兩種方式，比特幣才能保證歷史的交易不會被篡改和所有賬戶中資金的安全。

D. 如何理解拜占庭將軍問題

拜占庭將軍問題（以下簡稱「共識問題」）的正式表述是：如何在一個不基於信任的分布式網路中就信息達成共識？這個表述聽起來有些晦澀，但其本質並不復雜，下面的例子與共識問題雖然並不完全一致，但卻有助於我們的理解[9]。 想像一下在遙遠的拜占庭時代，有一個富饒的城邦，金銀珠寶綾羅綢緞應有盡有，它的領主哆啦A夢獨享著這一切奢華與榮耀。而在城邦的外圍，四位拜占庭將軍大雄、胖虎、小夫和靜香都覬覦著哆啦A夢的財富，於是他們決定聯手攻佔哆啦A夢的城邦。根據雙方的實力對比，必須有超過半數的將軍同時發起進攻方能克敵制勝，因此獲勝條件就是四人中至少三個人可以就進攻時間達成一致。那麼四位將軍的勝算有多少呢？ 這個問題的答案就要取決於四個人的合作方式了，如果是集中式系統，有一個盟主，比如胖虎（相當於中央伺服器），那麼他們的勝利是毫無懸念的，因為就進攻時間達成一致非常簡單，只要胖虎召集大雄、小夫和靜香開個會討論一下就可以了，即使大家意見有分歧胖虎也可以在最後予以定奪。下面讓我們回到拜占庭將軍問題的假設里，在不基於信任的分布式網路中，四位將軍的勝算又如何呢？ ? 首先由於四位將軍之間缺乏信任，因此聚到小黑屋裡開個密謀會的可能性被排除了（一旦在小黑屋裡被胖虎綁架了怎麼辦？）；其次由於沒有盟主，四個人的意見都會被同等的看重。在這種情況下，四位將軍只能通過信使在各自營地之間傳遞消息，來商定進攻時間了。比如大雄覺得早上6點是發動進攻的好時機，他就會派信使將自己的意見告訴胖虎、小夫和靜香，與此同時，胖虎可能認為晚上9點發動突襲更好，小夫更喜歡下午3點出擊，而靜香希望是上午10點，他們三人也會在同一時間派出自己的信使。這樣一來，在第一輪通信結束後，四位將軍每個人都有了四個可供選擇的進攻時間，他們各自要在下一輪通信中把自己選定的時間告知另外三人。由於四個人的決策都是獨立做出的，因此最終的選擇結果就有256種可能，而只有當三人以上都恰好選擇了同一時間的時候，共識才被達成，而這樣的結果才64種，也就是說達成共識的概率僅為1/4。這還只是四位將軍的情況，如果將軍的人數是10人，100人，1000人呢？我們稍加計算就可以發現隨著人數的增加，達成共識的希望會變得越來越渺茫。 把上面例子中的將軍換成計算機網路中的節點，把信使換成節點之間的通信，把進攻時間換成需要達成共識的信息，你就可以理解共識問題所描述的困境了。達成共識的能力對於一個支付系統來說重要性不言而喻，如果你給家裡匯了一筆錢買車，第二天去銀行核實的時候櫃台告訴你「關於你匯了多少錢的問題，我們的系統里有三個版本的記錄」，這樣的銀行你顯然是不敢把錢存進去的。在比特幣出現之前共識問題是很難被完美解決的，要保證達成共識就需要採用集中式系統（除非節點滿足特定條件），要想去中心化共識就無法保證。那麼區塊鏈技術又是如何解決這一難題的呢？

E. 拜占庭將軍問題 口頭協議演算法是怎麼推導出來的

我也是額，老是卡，而且不止第一集，後面兩集也是，放一會時間就會卡一下，就像定格了一樣

F. 數字貨幣雙花 拜占庭將軍是什麼意思

拜占庭將軍問題在我看來是提出了一個錯誤模型。即錯誤節點可以做任意事情（不受protocol限制），比如不響應、發送錯誤信息、對不同節點發送不同決定、不同錯誤節點聯合起來干壞事等等。總之就是說，沒有節點會出現比這更嚴重的錯誤。
很顯然，拜占庭錯誤是overly
pessimistic的模型，因為這種錯誤實際環境中比較少見。那麼為什麼要研究這個模型呢看其中最簡單的一個原因是，如果某個一致性演算法能夠保證在系統出現f個拜占庭錯誤時保持系統一致，那麼這個演算法也就能夠保證在出現f個任意其他錯誤的時候也保持系統一致。
錯誤模型有上限，肯定也就有一個下限（overly
optimistic，沒有比它還要弱的模型）。這個下限就是『fail-stop』模型。這個模型的假設是：當一個節點出錯，這個節點會停止運行，並且其他所有節點都知道這個節點發生了錯誤。用同樣的邏輯，如果某個一致性演算法不能保證在系統出現f個錯誤的時候保持一致，那麼這個演算法也就沒法處理其他f個任意其他問題。
應用這些錯誤模型，可以對不同演算法進行比較，也可以對具體演算法的cost進行討論。

G. 什麼協議是加密加拜占庭將軍

是由萊斯利·蘭伯特提出的點對點通信中的基本問題。含義是在存在消息丟失的不可靠信道上試圖通過消息傳遞的方式達到一致性是不可能的。因此對一致性的研究一般假設信道是可靠的，或不存在本問題。
拜占庭位於如今的土耳其的伊斯坦布爾，是東羅馬帝國的首都。由於當時拜占庭羅馬帝國國土遼闊，為了防禦目的，因此每個軍隊都分隔很遠，將軍與將軍之間只能靠信差傳消息。 在戰爭的時候，拜占庭軍隊內所有將軍和副官必需達成一致的共識，決定是否有贏的機會才去攻打敵人的陣營。

H. 什麼是比特幣加密技術

比特幣和區塊鏈的誕生需要依賴於很多核心技術的突破：一是拜占庭容錯技術；二是非對稱加密技術；三是點對點支付技術。下面會依次介紹。
拜占庭容錯技術
比特幣和區塊鏈誕生的首要難點在於如何創建分布式共識機制，也就是菜斯利·蘭伯特等人1982年提出的拜占庭將軍問題。所謂拜占庭將軍問題是指，把戰爭中互不信任的各城邦軍隊如何達成共識並決定是否出兵的決策過程。延伸至計算機領域，試圖創建具有容錯性的分布式系統，即使部分節點失效仍可確保系統正常運行，也可讓多個基於零信任基礎的節點達成共識，並確保信息傳遞的一致性。
中本聰所提到的「拜占庭將軍問題」解決方法起始於亞當﹒拜克在1997年發明的哈希現金演算法機制，起初該設計是用於限制垃圾郵件發送與拒絕服務攻擊。2004年，密碼朋克運動早期和重要成員哈爾·芬尼將亞當﹒拜克的哈希現金演算法改進為可復用的工作量證明機制。他們的研究又是基於達利亞·馬凱與邁克爾·瑞特的學術成果：拜占庭容錯機制。正是哈爾·芬尼的可復用的工作量證明機制後來成為比特幣的核心要素之一。哈爾·芬尼是中本聰的最早支持者，同時也是第一筆比特幣轉賬的接受者，在比特幣發展的早期與中本聰有大量互動與交流。
非對稱加密技術
比特幣的非對稱加密技術來源於以下幾項密碼學的技術創新：1976年，Sun公司前首席安全官Whitfield Diffie與斯坦福大學教授Martin Hell，在開創性論文《密碼學的新方向》首次提出公開鑰匙密碼學的概念，發明了非對稱加密演算法。1978年省理工學院的倫納德·阿德曼、羅納德·李維斯特、阿迪·薩莫爾三名研究人員，共同發明了公開鑰匙系統「RSA」可用於數據加密和簽名，率先開發第一個具備商業實用性的非對稱RSA加密演算法。1985年，Neal Koblitz和Victor Miller倆人，首次提出將橢圓曲線演算法（ECC），應用於密碼學，並建立公鑰加密的演算法，公鑰密碼演算法的原理是利用信息的不對稱性，公鑰對應的是私鑰，私鑰是解開所有信息的鑰匙，公鑰可以由私鑰反推算出。ECC能夠提供比RSA更高級別的安全。比特幣使用的就是橢圓曲線演算法公鑰用於接收比特幣，而私鑰則是比特幣支付時的交易簽名。這些加密演算法奠定了當前非對稱加密理論的基礎，被廣泛應用於網路通信領域。但是，當時這些加密技術發明均在NSA嚴密監視的視野之內。NSA最初認為它們對國家安全構成威脅，並將其視為軍用技術。直到20世紀90年代末，NSA才放棄對這些非對稱加密技術的控制，RSA演算法、ECC演算法等非對稱加密技術最終得以走進公眾領域。
不過，中本聰並不信任NSA公布的加密技術，在比特幣系統中沒有使用RSA公鑰系統，原因除了ECC能夠提供比RSA更高級別的安全性能外，還擔心美國安全部門在RSA留有技術後門。2013年9月，斯諾登就曾爆料NSA採用秘密方法控制加密國際標准，比特幣採用的RSA可能留有後門，NSA能以不為人知的方法弱化這條曲線。所幸的是，中本聰神一般走位避開了RSA的陷阱,使用的加密技術不是NSA的標准，而是另一條鮮為人知的橢圓曲線，這條曲線並不在美國RSA的掌握之下。全世界只有極少數程序躲過了這一漏洞，比特幣便是其中之一。