上次文章中提到Bitcoin網(wǎng)絡中各個節(jié)點是“黑暗森林”中的“獵人”猫缭，它們除了要“隱藏”自己耘分，更重要的是要保證自己存的交易記錄和其他節(jié)點的是一致的举塔，要不然就有可能出現(xiàn)雙重支付或者偽造支付的情況，如上海地區(qū)的節(jié)點中有交易記錄A求泰，但北京地區(qū)的節(jié)點中沒有交易記錄A央渣，如果匯款方在上海，他說我已經(jīng)支付過了渴频，但收款方在北京芽丹，他說我沒有收到過你的轉賬記錄，你沒有支付卜朗，得繼續(xù)支付拔第。這就是網(wǎng)絡中節(jié)點狀態(tài)不一致導致交易無法完成的情況。所以說场钉，Bitcoin網(wǎng)絡中最關鍵的問題是如何保證各節(jié)點在有限時間內(nèi)達到狀態(tài)一致蚊俺。
這個問題先放一放，我先講幾個小故事逛万。
《囚徒》
南緯15°56'泳猬， 西經(jīng)5°42'，圣赫勒拿島宇植，發(fā)生一起搶劫案暂殖，警察迅速找到并逮捕了兩名嫌疑人A和I。
警察將A和I關在兩個封閉的審訊室里分開審訊当纱，并對他們承諾：如果告發(fā)另一個人呛每，可以無罪釋放，另一個人構成搶劫罪會判10年坡氯；同時也明白告知他們：如果兩人都招供晨横，可以按自首處理，他們會一起判5年箫柳。A和I聽到后手形，不以為然，因為他們知道悯恍，他們還有一個選擇：只要兩人都死扛库糠，誰都不招供，只要警方找不到有力證據(jù)，他們最多被拘48小時瞬欧。在行動之前贷屎，A和I就商量好了，一旦事發(fā)艘虎，兩人必須咬死不招唉侄，這樣對大家都有好處。
A和I在審訊室里沉默了幾個小時野建，警察著急了属划，開始對他們攻心: 如果你們中一方選擇告發(fā)另一個人，那么被告發(fā)的那個人要么被判5年候生，要么被判10年同眯，而告發(fā)的那個人要么被釋放，要么被判5年唯鸭，其中利害你們自己想一想须蜗。然后故意向A和I分別透露已經(jīng)掌握的一些證據(jù)，讓他們以為是對方向警方提供的肿孵。A和I一開始都咬定準備死杠了唠粥，因為很顯然疏魏，這對雙方都有好處停做。但時間一分一分地煎熬，加上警方的分化大莫，他們內(nèi)心都出現(xiàn)了動搖蛉腌。他們知道他們的關系并非是牢不可破，從對自己有利的角度來想只厘，選擇告發(fā)對方可以肯定地減少自己的刑期烙丛，最差也是5年，肯定不會是10年羔味；但如果自己死杠河咽，一旦對方選擇告發(fā)，那自己就是10年赋元，而對方在外逍遙了忘蟹。思來想去，A和I都覺得不能犧牲自己的利益來換取可能的最大化的共同利益搁凸，所以不約而同地選擇了告發(fā)對方媚值。。护糖。
《議員》
北緯37°58'褥芒，東經(jīng)23°43'，古希臘雅典城嫡良，男人們在大聲討論著锰扶。令人討厭的波斯不停地侵擾著半島献酗，為了加強防御、一致對外少辣，各城邦需要強化聯(lián)系凌摄，就一些事務共同決策。于是在雅典城和斯巴達城的共同提議下漓帅，各城邦派出代表齊集雅典市集锨亏，商討各城邦如何有效地共同商討決策問題。為了方便敘述忙干，我們暫且稱這些代表為議員器予，雖然直到羅馬才有。
斯巴達方的議員們比較冷靜和強勢捐迫，他們直接指出：各城邦之間只能通過送信的方式聯(lián)絡乾翔，但城邦之間有的有山脈和海灣阻隔，送信可能有很長時間的延遲施戴，或者送信人在中途出意外導致信根本就送不到對方反浓；而且，城邦收到議事的信后赞哗，還要就所議事情在內(nèi)部召集人們討論雷则，可能需要較長時間回復，或者有些東部城邦由于在和波斯交戰(zhàn)肪笋，暫時根本沒有精力來參與議事月劈，要等戰(zhàn)爭結束后才能參與進來。此言一出藤乙，各大小城邦議員紛紛點頭稱是猜揪。在長期的民主政體熏陶下，雅典議員們較為平和與沉著坛梁，其中有一長者而姐，略一沉吟說到：大家的初衷都是一致的，就是要在通信不暢或者議事不及時的情況下划咐，就共同的提案商議以達成一致決議拴念，所以我們各城邦要真實表達自己的投票意見，不能故意擾亂協(xié)商過程尖殃，大家的目標都是盡快地達到一致決議丈莺。眾議員紛紛點頭稱是。隨后送丰，大家便開始商討各種達成決議的辦法缔俄。
其中，米利都城的議員提議到：讓有提案的城邦派信使將其提案送給其余各城邦，等各城邦投票后再由信使送還俐载，收集各城邦投票結果后再根據(jù)多數(shù)城邦的意見形成決議蟹略，再由提案城邦派信使將決議通告各城邦即可。小亞細亞沿岸各城邦紛紛點贊遏佣，認為此舉應該能讓大家達成決議挖炬。
但哈爾基斯城的議員立即反問到：如果信使沒能送到，或者城邦當時無法回復状婶，導致收集到的投票始終無法過半數(shù)意敛，怎么辦？或者膛虫，在一個提案投票未完成時草姻，又有一個相同問題的不同提案被另一個城邦提出來，如果兩個提案都收集到了過半的投票稍刀，那到底應該執(zhí)行哪一個決議呢撩独？
話音一落，眾議員紛紛竊竊私語账月，有的點頭表示贊同综膀，有的搖頭表示問題好難，有的一言不發(fā)局齿，似乎在思索答案剧劝。。项炼。
當日担平，眾議員沒有商議出一個好辦法示绊，于是各回旅店休息锭部。
是日，又議面褐，未果拌禾；如此數(shù)日，未果展哭。
眼看此次集會預定的時間將截止湃窍，還沒有商量出好辦法，大家都比較著急匪傍。這時您市，雅典議員代表中一個年輕人猶豫著舉起了手，然后站起來說道：如果各城邦能保證一定投票役衡，真實投票茵休，而且大家目標是為了盡快達成一致決議，而不是為了實現(xiàn)自己的提案而抬杠的話，我有一個辦法榕莺。之前那個雅典長者對他投來了贊許和信任的目光俐芯，并說：帕克索斯，請講钉鸯。
帕克索斯得到了支持吧史，自信地說到：我們可以把投票過程分為兩個階段。第一個階段唠雕，由有提案的城邦 A 寫好提案編號和要提案的內(nèi)容贸营，由信使發(fā)送出去，然后等待其他城邦的回復岩睁。第一階段其他城邦不需要投票莽使，所以他們的回復不是支持或者贊成，而是告訴城邦 A 能不能正式向其他城邦發(fā)起投票請求笙僚，或者現(xiàn)在是不是有針對相同問題的其他提案正在協(xié)商芳肌。等到城邦 A 收到了過半數(shù)城邦的回復，該城邦就可以發(fā)起第二階段的投票了肋层。在第二階段中亿笤，城邦 A 根據(jù)收到的回復，如果過半數(shù)的其他城邦的回復中都表示可以繼續(xù)發(fā)起投票栋猖，而且回復中沒有說明有正在協(xié)商的其他提案净薛，那城邦 A 就可以向其余城邦寫信發(fā)送提案投票的請求，如果有半數(shù)人支持就可以達成決議蒲拉，由城邦 A 將決議告知其他城邦執(zhí)行肃拜；或者第一階段中有城邦回復說要停止提案，因為有其他城邦更緊急地提出了提案雌团，那城邦 A 就不再發(fā)起投票請求燃领，以免造成投票混亂，而是等待給那個更緊急的提案投票锦援；又或者第一階段中有城邦回復表示可以繼續(xù)發(fā)起投票但是他們有的已經(jīng)同意了另外一個相同問題的其他提案猛蔽，那么城邦 A 就要放棄自己的提案，將其改成回復中表明的已經(jīng)被同意了的另一個提案灵寺，然后向其余城邦發(fā)起投票請求曼库，由于這個時候各城邦收到的投票提案是一樣的，所以能很快得到多數(shù)同意并形成一致決議略板。
帕克索斯說完后毁枯，整個集市沉默了下來。有的人微蹙眉頭叮称，似乎在默默推理和反詰他的方法种玛；有的人則是一臉茫然胀糜，表示完全沒有聽懂。這時底比斯城的一個中年議員問了一個問題： 你的方法中第一階段是不是為了保證第二階段只有一個提案值蒂誉？ 帕克索斯說是的教藻。底比斯城的另一個年輕議員又問道：第一階段中，如果有城邦回復說他已經(jīng)接受了另一個提案右锨，那城邦 A 就把自己的提案改成那個提案了括堤，是不是因為那個提案肯定已經(jīng)有多數(shù)城邦不反對或者說同意了。帕克索斯說非常正確绍移。這時悄窃，底比斯城的議員們一致表示他們贊成帕克索斯的方法，認為他的辦法可以保證各城邦較快達成一致蹂窖。
隨后轧抗，由雅典、斯巴達和底比斯等城的議員給其他城邦的議員反復解釋后瞬测，大家明白了這個方法家卖，并一致決定采用這個方法來協(xié)商事務仿滔。后來今豆，根據(jù)這套協(xié)商機制撇簿，希臘各城邦共進共退，終于取得了波希戰(zhàn)爭的最后勝利孝宗。雖然后來雅典獨自做大穷躁，引起斯巴達不滿，進而演化成各城邦相互廝殺的局面因妇，但帕克索斯的提案若干年后還是被各城邦的有識之士津津樂道问潭。
《將軍》
北緯41°01'，東經(jīng)28°58'婚被，君士坦丁堡狡忙。城外一片蕭殺，奧斯曼海軍已經(jīng)兵臨金角灣摔寨，隨時有可能突入帝國首都后方去枷。
君士坦丁十一世焦急地召集部署在金角灣和首都東面臨海的將軍們怖辆，心急地要求他們：務必協(xié)同作戰(zhàn)是复，保證防線萬無一失。因為帝國戰(zhàn)力已經(jīng)告急竖螃，各將軍必須組織共同進攻或者共同撤退淑廊，單方面的冒進或者后退都會導致防線失守，徹底戰(zhàn)敗特咆。然而季惩，將軍們卻各懷心思: 誰能保證步調(diào)一致呢录粱，誰知道其中有沒有叛徒，萬一準備進攻的時候画拾，叛徒將軍故意傳達撤退命令怎么辦啥繁？年輕的皇帝看出了大家的心思，心里滿是悲愴青抛，盡管帝國僅存孤城旗闽，他還是想最后一博，無論如何不能投降蜜另。于是他開誠布公地說道: 我知道諸位的顧慮适室，戰(zhàn)事至此，只希望諸公與我奮力保衛(wèi)新羅馬举瑰，戰(zhàn)場態(tài)勢變化不定捣辆，無法由我來協(xié)調(diào)，所以需要諸將軍即時協(xié)調(diào)攻守此迅，如果大家擔心其中有叛徒或者傳令兵被調(diào)包汽畴，也請大家想出辦法來，在可能有叛徒的情況下仍然保證共進共退耸序，只有共進共退整袁，我們才有死守成功的可能。諸將軍聽完后佑吝，頭皮發(fā)麻坐昙，覺得此問題無解，應該先找出叛徒正法為妥芋忿。
皇宮內(nèi)安靜得可怕炸客，將軍們粗重的呼吸清晰可辨。然而只有皇帝心急如焚戈钢，將軍們卻是平靜而放松痹仙。時間一點一點流失，皇帝反復追討辦法無果殉了。這時开仰，旁邊的主教蘭波特說：陛下，我有辦法可以讓將軍們保證進退一致薪铜。將軍們詫異地將目光集中到蘭波特身上：這個長袍禿頭的家伙這回居然和皇帝站在了一邊众弓。皇帝欣喜地說道：主教大人隔箍，請講谓娃。
蘭波特清了清嗓子，說道：我們這里有10位將軍蜒滩，雖然我們現(xiàn)在無法弄清誰是叛徒滨达，但我們有辦法知道將軍中的叛徒個數(shù)奶稠，而且我有信心，即使有叛徒捡遍，也不會超過3位锌订。假如你們在戰(zhàn)場上的聯(lián)絡是沒有問題的，就是說画株，傳令兵會把命令傳到另一位將軍那里瀑志，無論傳令兵有沒有被調(diào)包。那么當你們收到將軍A的傳令兵的消息后污秆，先不要相信他傳達的命令劈猪，而是派出自己的親兵去問一下其他將軍：將軍A給他們傳的命令是什么？ 如果叛徒不止一個的話良拼，收到其他將軍回復后也不要選擇相信战得，因為他們中間可能還有叛徒。假如回復的8個將軍分別是將軍 1 - 8庸推，為了確認他們回復的是否可相常侦，應該再分別問除了回復的將軍外其他將軍。比如贬媒，如果要確認將軍 1 回復的是否可信聋亡，要問一下將軍 2 - 8，將軍 1 給他們傳達的是什么命令际乘。確認將軍 2 - 8 的回復也采用類似的方法坡倔，直到根據(jù)叛徒數(shù)量確定剩下的將軍中可能沒有叛徒為止。最后脖含，收集各將軍的回復罪塔，選擇多數(shù)的結果作為對應將軍的命令，分別確定將軍 2 - 8的命令养葵，然后與自己收到的命令一起選一個多數(shù)意見執(zhí)行進攻或者撤退征堪。每個將軍都用相同的方法決定最后的執(zhí)行結果，可以保證大家共進共退关拒。
聽完后佃蚜，各將軍一臉茫然，直觀感覺要傳好多道令着绊。而且他們都知道主教作了一個假設谐算，說最多只有3個叛徒，所以有將軍提出來說：萬一咱們中的叛徒不止3個畔柔，有5個甚至7個怎么辦氯夷？
蘭波特微微一笑，說這個也好辦：如果叛徒超過3個人靶擦，你們就要對傳令的文書簽名了腮考，而且除非是兩個叛徒共謀篡改簽名，正常的簽名是很容易被識別的玄捕。如果將軍A傳令踩蔚，那他簽好名后由傳令兵向其他 9 個將軍傳達命令。這9個將軍收到 A 的命令后枚粘，也不會立即選擇相信并執(zhí)行馅闽，而是先把他的傳令記下來，并在傳令文書上加上自己的簽名后馍迄，再由傳令兵傳遞給其他 8 位將軍福也；剩下的將軍收到傳令文書后，檢查一下簽名攀圈，看還沒有誰的簽名暴凑，如果還有人沒有簽名，就把自己的簽名加上去赘来，給他發(fā)一份现喳。這樣一段時間后，各將軍手上都有收到不止一份簽過名的傳令文書犬辰。每個將軍把他收到的所有傳令文書上的命令都記下來嗦篱。如果一段時間內(nèi)沒有收到某個將軍簽名的文書的話，就默認這個將軍對應的命令是撤退幌缝。這個方法可以保證灸促，一段時間當將軍們不再收到新的傳令后，所有將軍記下來的命令集合是一致的涵卵，將軍們最后都通過選擇命令集合中最多數(shù)的命令執(zhí)行就可以實現(xiàn)共進共退了腿宰。
將軍們已經(jīng)昏昏欲睡，皇帝則滿臉狐疑地問道：主教大人缘厢，你確定在我們知道叛徒人數(shù)的情況下吃度，這兩種方法都能讓將軍們行動一致？
蘭波特用力地點了點頭贴硫，給皇帝信心椿每。皇帝將信將疑：你的辦法要求反復傳令英遭，我擔心戰(zhàn)場上不好實施啊间护。蘭波特默然，但建議皇帝事情緊急挖诸，沒有更好的辦法了汁尺。皇帝于是要求將軍們按主教大人的辦法執(zhí)行多律，等叛徒人數(shù)確定后痴突，再選擇執(zhí)行方案一或者方案二搂蜓。
不久，奧斯曼海陸軍并進辽装。主教確認帮碰，有3個將軍是叛徒，拜占庭的將軍們選擇方案一進行協(xié)商拾积，但蘭波特的方法實在太過繁復殉挽，傳令兵還沒有跑完，奧斯曼海軍已經(jīng)突入金角灣拓巧，切斷了西邊的補給和救援通道斯碌。沒過多久，君士坦丁堡被攻陷肛度。
好了傻唾，故事已經(jīng)講完了。有同學可能會問：這些故事與Bitcoin網(wǎng)絡的共識有什么關系贤斜？關系蠻大的策吠。相信不少同學對上面的故事已經(jīng)會心一笑了，我只不過把幾個有名的故事重新講了一遍瘩绒。第一個故事便是博弈中的囚徒困境問題猴抹，它是說在單次或者有限次博弈中，理性個人總是選擇對自己有利的方案锁荔，而不顧全局最優(yōu)選擇蟀给。第二個故事是Lamport提出的Paxos算法，討論的是無欺騙的故障容錯算法阳堕。第三個故事講的是拜占庭將軍問題跋理，講的是分布式系統(tǒng)中有惡意節(jié)點存在時如何達到一致的問題，解決的理論辦法是Lamport提出的口頭協(xié)議和書面協(xié)議算法恬总。Bitcoin網(wǎng)絡是一個分布式系統(tǒng)前普，也需要解決有惡意節(jié)點和有故障節(jié)點時如何讓各節(jié)點達成一致的問題。
從上面的故事中可以看到壹堰，Lamport提出的理論算法復雜度比較高拭卿，雖然已經(jīng)有算法提出來，實現(xiàn)了多項式級別復雜度贱纠，但針對大規(guī)模網(wǎng)絡峻厚，節(jié)點數(shù)量很多，從達成一致的時間要求和成本要求來看谆焊，無法高效實用惠桃。上述算法要達到的是確定共識狀態(tài)，即最后能確定達到一致狀態(tài)。大家已經(jīng)知道辜王，Bitcoin網(wǎng)絡采用的是PoW共識算法劈狐，它是一種概率共識算法，即最后全網(wǎng)是以一定概率逐步達成共識的誓禁。
PoW算法不再贅述懈息，這里只以筆者有限的理解肾档，來簡要說明一下Bitcoin網(wǎng)絡中的共識機制與上述三個故事的關系摹恰。PoW算法中，要求節(jié)點必須完成工作量證明后怒见，才能向其他節(jié)點廣播被“挖”出來的區(qū)塊俗慈，這實際上是變相完成了議員故事中講的第一階段，即提高了提案的成本遣耍，讓一段時間內(nèi)只有一個提案供網(wǎng)絡投票闺阱。另一方面，為了防止區(qū)塊或其中的交易被篡改舵变，區(qū)塊中的交易會通過Hash形成Markle樹酣溃，區(qū)塊頭中包含了上一區(qū)塊的Hash然后再計算自己的Hash，會使得中間節(jié)點篡改會很快被發(fā)現(xiàn)纪隙，從而無法在網(wǎng)絡中傳播被修改的提案赊豌。然而，如何防止“礦工”自己篡改區(qū)塊呢绵咱，“礦工”可以有意排除一些交易或者虛構工作量證明碘饼？這個問題就是通過其他節(jié)點收到該區(qū)塊后的決策來解決的。具體來說悲伶，其他節(jié)點收到這個被篡改的區(qū)塊后艾恼，會驗證工作量證明是否正確，一方面是區(qū)塊目標難度是不是預定的值麸锉，另一方面就是給出的隨機值能不能滿足區(qū)塊頭Hash小于目標難度钠绍。對于有意排除一些交易或者虛構工作量證明的礦工，其他節(jié)點無法在驗證工作量證明環(huán)節(jié)識別花沉，因而將這一“假區(qū)塊”根據(jù)區(qū)塊高度暫時添加到自己的區(qū)塊鏈上柳爽，但他們會通過類似將軍故事中第二個方案中的其他將軍那樣，等其他節(jié)點或者礦工發(fā)過來的區(qū)塊主穗。一段時間后泻拦，相同高度的正確的區(qū)塊會被其他礦工“挖”出來并傳播出來，節(jié)點于是有了相同高度的真假區(qū)塊在自己的區(qū)塊鏈上忽媒，也就是發(fā)生了分叉争拐，這時節(jié)點會選擇工作量最大或者最長的區(qū)塊為正確的區(qū)塊，對應的分叉為主鏈，另一個分叉和其上的區(qū)塊被丟棄架曹。如果要偽造工作量證明隘冲，只可能往工作難度小的方向篡改，因為能更快地“挖”出區(qū)塊绑雄，所以工作量最大的肯定是正常的區(qū)塊展辞。
那么，這里還有一個可能性: 如果其他節(jié)點不是選擇工作量最大或者最長鏈為主鏈万牺，而是與惡意“礦工”合作罗珍，選擇虛假區(qū)塊，那不就可以了么脚粟。這里節(jié)點就面臨囚徒困境了覆旱，因為被系統(tǒng)承認的區(qū)塊會給相應的礦工獎勵若干比特幣，而沒被系統(tǒng)接受的“礦工”所付出的算力及背后對應的電力核无、設備折舊帶來的經(jīng)濟成本就成為了沉沒成本扣唱，由“礦工”自己承擔。那么团南，就會有不少“礦工”開始琢磨噪沙，要不要和惡意“礦工”合伙作假了，因為作假的成本確實有點高吐根，除非拉攏了超過全網(wǎng)1/3甚于1/2的節(jié)點正歼，才有可能得成。想一想佑惠，還是老老實實“挖”吧朋腋。。膜楷。
