文章閱讀頁通欄

比特幣與拜占庭將軍問題

來源: 區塊鏈鉛筆 作者:
拜占庭將軍問題(Byzantine failures)是由萊斯利·蘭伯特提出的點對點通信中的基本問題。含義是在存在消息丟失的不可靠信道上試圖通過消息傳遞的方式達......
拜占庭將軍問題(Byzantine failures)是由萊斯利·蘭伯特提出的點對點通信中的基本問題。含義是在存在消息丟失的不可靠信道上試圖通過消息傳遞的方式達到一致性是不可能的。因此對一致性的研究一般假設信道是可靠的,或不存在本問題。這個難題也被稱為“拜占庭容錯”、“拜占庭將軍問題”、或者“兩軍問題”。
拜占庭將軍問題是一個協議問題,拜占庭帝國軍隊的將軍們必須全體一致的決定是否攻擊某一支敵軍。問題是這些將軍在地理上是分隔開來的,并且將軍中存在叛徒。叛徒可以任意行動以達到以下目標:欺騙某些將軍采取進攻行動;促成一個不是所有將軍都同意的決定,如當將軍們不希望進攻時促成進攻行動;或者迷惑某些將軍,使他們無法做出決定。如果叛徒達到了這些目的之一,則任何攻擊行動的結果都是注定要失敗的,只有完全達成一致的努力才能獲得勝利。

拜占庭假設是對現實世界的模型化,由于硬件錯誤、網絡擁塞或斷開以及遭到惡意攻擊,計算機和網絡可能出現不可預料的行為。拜占庭容錯協議必須處理這些失效,并且這些協議還要滿足所要解決的問題要求的規范。

首先,不要把比特幣當成一種貨幣,而是一個總賬。它是個電子賬本,網絡上的每一個參與者的電腦都會有一份賬本的備份,并且所有的備份都是在實時的持續的更新、對賬、以及同步著。每一個參與者都能在這本賬本里記上一筆,這一筆記錄著一定數量的幣從一個參與者那里被發送到另一個參與者那里,并且每一條這樣的記錄都接著就實時的廣播到網絡了,所以在每一臺電腦上的每一分份拷貝都是幾乎同時更新的,并且所有的賬本拷貝都保持著同步。這本公開的分布式的賬本就可以稱為“區塊鏈(blockchain)”,并且它使用了BT技術以保證所有的拷貝都是同步的。

可以把比特幣當作一個對于在分布式系統領域的一個復雜的算法難題的通用解決方法。

這一問題的趣味非正式表述如下:想象一下,在拜占庭時代有一個墻高壁厚的城邦,拜占庭,高墻之內是它的鄰居想象不到之多的財富。它被其他10個城邦所環繞,這10個城邦也很富饒,但和拜占庭相比就微不足道了。它的十個鄰居都覬覦拜占庭的財富,并希望侵略并占領它。

但是,拜占庭的防御是如此的強大,沒有一個相鄰的城邦能夠成功入侵。任何單個城邦的入侵行動都會失敗,而入侵者的軍隊也會被殲滅,使得其自身容易遭到其他九個城邦的入侵和劫掠。這十個城邦之間也互相覬覦對方的財富并持續互相對抗著。而且,拜占庭的防御如此之強,十個鄰居的一半以上同時進攻才能攻破它。

也就是說,如果六個或者更多的相鄰敵軍一起進攻,他們就會成功并獲得拜占庭的財富。然而,如果其中有一個或者更多背叛了其他人,答應一起入侵但在其他人進攻的時候又不干了,也就導致只有五支或者更少的軍隊在同時進攻,那么所有的進攻軍隊都會被殲滅,并隨后被其他的(包括背叛他們的那(幾)個)鄰居所劫掠。這是一個由不互相信任的各方構成的網絡,但他們又必須一起努力以完成共同的使命。

而且,是個鄰居之間通訊和協調統計時間的唯一途徑是通過騎馬在他們之間傳遞信息。他們不能聚在一個地方開個會(所有的王都不互相信任他們的安全在自己的城堡或者軍隊范圍之外能夠得到保障)。然而,他們可以在任意時間以任意頻率派出任意數量的信使到任意的對方。每條信息都包含類似如下的內容:“我將在第四天的6點鐘進攻,你愿意加入嗎?”。

如果收信人同意了,他們就會在原信上附上一份簽名了的/認證了的/蓋了圖章的/驗證了的回應,然后把新合并了的信息的拷貝再次發送給九個鄰居,要求他們也如此這樣做。最后的目標是,通過在原始信息鏈上蓋上他們所有十個人的圖章,讓他們在時間上達成共識。最后的結果是,會有一個蓋有十個同意同一時間的圖章信息鏈,可能還會有一些被拋棄了的包含部分但不是全部圖章的信息鏈。

但是,問題在于如果每個城邦向其他九個城邦派出一名信使,那么就是十個城邦每個派出了九名信使,也就是在任何一個時間又總計90次的傳輸,并且每個城市分別收到九個信息,可能每一封都寫著不同的進攻時間。除此以外,部分城邦會答應超過一個的攻擊時間,故意背叛發起人,所以他們將重新廣播超過一條的信息鏈。這個系統迅速變質成不可信的信息和攻擊時間相互矛盾的糾結體。

比特幣通過對這個系統做出一個簡單的(事后看是簡單的)修改解決了這個問題,它為發送信息加入了成本,這降低了信息傳遞的速率,并加入了一個隨機元素以保證在一個時間只有一個城邦可以進行廣播。它加入的成本是“工作量證明”,并且它是基于計算一個隨機哈希算法的。哈希是一種算法,它唯一做的事情就是獲得一些輸入然后進行計算,并得到遺傳64位的隨機數字和字母的字符串,就像這個:

d70298566aa2f1a66d892dc31fedce6147b5bf509e28d29627078d9a01a8f86b

在比特幣的世界中,輸入數據包括了到當前時間點的整個總賬(區塊鏈)。并且盡管單個哈希值用現在的計算機可以幾乎即時的計算出來,但只有一個前13個字符是0的哈希值結果可以被比特幣系統接受成為“工作量證明”。這樣一個13個0的哈希值是極其不可能與罕見的,并且在當前需要花費整個比特幣網絡大約10分鐘的時間來找到一個。在一臺網絡中的機器隨機的找到一個有效哈希值之前,上十億個的無效值會被計算出來,這就是減慢信息傳遞速率并使得整個系統可用的“工作量證明”。下面是一個例子:

f51d0199c4a6d9f6da230b579d850698dff6f695b47d868cc1165c0ce74df5e1
d70298566aa2f1a66d892dc31fedce6147b5bf509e28d29627078d9a01a8f86b
119c506ceaa18a973a5dbcfbf23253bc970114edd1063bd1288fbba468dcb7f8

在找到一個有效值之前,成百萬上億個更多的類似上面這樣的字符串被計算出來。。。

000000000000084b6550604bf21ad8a955b945a0f78c3408c5002af3cdcc14f5

那臺發現下一個有效哈希值的機器(或者說在我們類比中的城邦),把所有的之前的信息放到一起,附上它自己的,以及它的簽名/印章/諸如此類,并向網絡中的其他機器廣播出去。只要其他網絡中的機器接收到并驗證通過了這個13個0的哈希值和附著在上面的信息,他們就會停止他們當下的計算,使用新的信息更新他們的總賬拷貝,然后把新更新的總賬/區塊鏈作為哈希算法的輸入,再次開始計算哈希值。哈希計算競賽從一個新的開始點重新開始。如此這般,網絡持續同步著,所有網絡上的電腦都使用著同一版本的總賬。

與此同時,每一次成功找到有效哈希值以及區塊鏈更新的間隔大概是10分鐘(這是故意的,算法難度每兩周調整一次以保證網絡一直需要花費10分鐘來找到一個有效的哈希值)。在那10分鐘以內,網絡上的參與者發送信息并完成交易,并且因為網絡上的每一條機器都是使用同一個總賬,所有的這些交易和信息都會進入遍布全網的每一份總賬拷貝。當區塊鏈更新并在全網同步之后,所有的在之前的10分鐘內進入區塊鏈的交易也被更新并同步了。因此分散的交易記錄是在所有的參與者之間進行對賬和同步的。

最后,在個人向網絡輸入一筆交易的時候,他們使用內嵌在比特幣客戶端的標準公鑰加密工具來同時他們的私鑰以及接收者的公鑰來為這筆交易簽名。這對應于拜占庭將軍問題中他們用來簽名和驗證消息時使用的“印章”。因此,哈希計算速率的限制,加上公鑰加密,使得一個不可信網絡變成了一個可信的網絡,使得所有參與者可以在某些事情上達成一致(比如說攻擊時間、或者一系列的交易、域名記錄、政治投票系統、或者任何其他的需要分布式協議的地方)。

這里是比特幣為何如此特別的關鍵:它代表了一個對于一個困難的算法上的難題的解決方案,這一解決方案在一系列的歷史事件發生之前是不可能的,這些事件有:

· 互聯網的創造
· 公鑰加密算法的發明
· 點對點Bitorrent(BT)協議的發明。BT協議最開始是開發來用于在網絡上的相對小的用戶子集之間共享許多文件的,但比特幣用它來在所有用戶之間共享單個文件。
· 人們意識到,在系統中添加一個簡單的時間延遲,同時使用公鑰加密算法以驗證每筆交易,可以解決這個問題。

如果說一些最棒的想法在事后看來是很簡單的,那么上述的第四點就完全符合條件,盡管整個項目是站在了巨人的肩膀上的。

最后,這一對于拜占庭將軍問題的解決方案,可以推廣到任何核心問題是在分布式網絡上缺乏信任的領域。如我們已經提到樂的,人們正在為互聯網建設一個分布式的域名系統,以及為政治選舉建設分布式的投票系統(還沒有網站)。如果人們認為單純的文件分享攪亂了這個世界,那么比特幣解決方案和協議才剛剛打開洪水的閘門。

更多數字貨幣信息:www.guwutu.icu/news
關鍵詞: 比特幣  拜占庭將軍問題  
0/300
? 时时彩龙虎和计划app