本書(shū)主要介紹區(qū)塊鏈中超級(jí)重要的概念：共識(shí)在各種應(yīng)用場(chǎng)景中的實(shí)現(xiàn)機(jī)制。本書(shū)是目前已面世書(shū)籍中對(duì)共識(shí)概念解析中至權(quán)威、至全面的一本。目標(biāo)讀者為區(qū)塊鏈學(xué)習(xí)及研究人員，以及實(shí)際開(kāi)發(fā)區(qū)塊鏈系統(tǒng)的工程人員。在原著基礎(chǔ)上，翻譯版將增加解讀及部分代碼實(shí)現(xiàn)。
除原稿翻譯之外，譯者還特別增加了自己的注釋，對(duì)書(shū)中的算法、公式進(jìn)行注解。另外，書(shū)中還單獨(dú)增加了兩章新的內(nèi)容。一章是介紹Paxos算法的發(fā)展史和在工業(yè)界的應(yīng)用情況，另一章是對(duì)比分析當(dāng)前主流的兩個(gè)共識(shí)機(jī)制，比特幣的PoW和私有鏈的PBFT。
推薦序I
毫無(wú)疑問(wèn)，互聯(lián)網(wǎng)是20 世紀(jì)最偉大的發(fā)明之一。隨著信息、通信技術(shù)的蓬勃發(fā)展，互聯(lián)網(wǎng)已滲透到生產(chǎn)、貿(mào)易、通信、學(xué)習(xí)、娛樂(lè)等人們生活的幾乎所有方面，更使很多方面產(chǎn)生了革命性的變化。近十年
來(lái)，在互聯(lián)網(wǎng)的基礎(chǔ)上，移動(dòng)互聯(lián)網(wǎng)、物聯(lián)網(wǎng)，乃至智能互聯(lián)網(wǎng)得到了新的發(fā)展。人工智能、深度學(xué)習(xí)、機(jī)器學(xué)習(xí)等一系列技術(shù)和理論的新發(fā)展，又促使互聯(lián)網(wǎng)應(yīng)用面臨更加蓬勃發(fā)展的新局面。在眾多的互聯(lián)網(wǎng)新應(yīng)用中，不得不提及區(qū)塊鏈。
仿佛一夜之間，互聯(lián)網(wǎng)創(chuàng)業(yè)圈和金融圈都在談?wù)搮^(qū)塊鏈。堅(jiān)信者認(rèn)為，去中心化的、不可篡改的分布式賬本，能夠重構(gòu)金融體系，甚至重塑整個(gè)社會(huì)。不知區(qū)塊鏈之父當(dāng)初是否曾預(yù)見(jiàn)到如今區(qū)塊鏈的熱度？
如今，比特幣及其他虛擬貨幣已廣泛流行，并且引起了監(jiān)管當(dāng)局的關(guān)注；政府、巨頭和創(chuàng)業(yè)公司，也都積極參與到區(qū)塊鏈的各種應(yīng)用的探索中。然而，在互聯(lián)網(wǎng)土壤上生長(zhǎng)出的各種技術(shù)和應(yīng)用中，區(qū)塊鏈及其應(yīng)用還很年輕。自2009 年比特幣誕生至今，也才僅7 年，更不要說(shuō)區(qū)塊鏈在互聯(lián)網(wǎng)金融領(lǐng)域和其他領(lǐng)域的應(yīng)用。
作為一個(gè)一直關(guān)注新技術(shù)發(fā)展的互聯(lián)網(wǎng)老兵，我曾數(shù)次應(yīng)邀參加中關(guān)村區(qū)塊鏈產(chǎn)業(yè)聯(lián)盟的活動(dòng)，和互聯(lián)網(wǎng)領(lǐng)域的年輕創(chuàng)業(yè)者、專家、學(xué)者一起，探討、推動(dòng)區(qū)塊鏈的發(fā)展和應(yīng)用。我們的年輕人，尤其是年
輕的創(chuàng)業(yè)者，他們的大膽探索和勇于創(chuàng)新，令我感到歡欣鼓舞。
目前，介紹區(qū)塊鏈應(yīng)用的書(shū)籍非常多，而從理論、技術(shù)層面介紹區(qū)塊鏈的書(shū)比較少。很高興看到有這樣一本從理論、技術(shù)層面介紹區(qū)塊鏈的書(shū)籍出版。希望大家能耐心讀讀這本書(shū)，更深入地理解區(qū)塊鏈技術(shù)，從而有助于推動(dòng)區(qū)塊鏈技術(shù)的發(fā)展和應(yīng)用。
高盧麟博士
中國(guó)互聯(lián)網(wǎng)協(xié)會(huì)副理事長(zhǎng)
美國(guó)芝加哥馬歇爾法學(xué)院客座教授
推薦序II
區(qū)塊鏈（Block Chain）原本只是比特幣網(wǎng)絡(luò)的一種記賬技術(shù)，近幾年來(lái)卻在金融、知識(shí)產(chǎn)權(quán)、數(shù)據(jù)交易、電子證照、慈善、新能源等領(lǐng)域引起了廣泛的關(guān)注。為什么就突然火起來(lái)了？究其原因，我的理
解是：第一，區(qū)塊鏈具有去中心化的特征，不以參與交易的任何一方為中心。去中心化可以帶來(lái)效率的提升和成本的降低，直接增加了企業(yè)的利潤(rùn)。第二，區(qū)塊鏈具有去信任的特征，也就是假定參與交易的任何一方都不是可信任的。我們通過(guò)記錄交易的信息，而且是不可抵賴的，來(lái)迫使交易各方遵守誠(chéng)信。因此也可以說(shuō)，區(qū)塊鏈技術(shù)很好地回應(yīng)了目前互聯(lián)網(wǎng)的痛點(diǎn)誠(chéng)信問(wèn)題。第三，區(qū)塊鏈作為互聯(lián)網(wǎng)的一種基礎(chǔ)設(shè)施，也可以看作是一種分布式數(shù)據(jù)庫(kù)，其核心就是參與交易的多方如何達(dá)成共識(shí)。在分布式數(shù)據(jù)庫(kù)中，為了處理并發(fā)事務(wù)，需要在不同的節(jié)點(diǎn)上維護(hù)一個(gè)全局一致的狀態(tài)，傳統(tǒng)的做法是通過(guò)兩階段鎖協(xié)議來(lái)實(shí)現(xiàn)。
另一方面，通常大型應(yīng)用會(huì)維護(hù)多個(gè)數(shù)據(jù)庫(kù)副本，以實(shí)現(xiàn)數(shù)據(jù)庫(kù)的恢復(fù)。在多個(gè)數(shù)據(jù)庫(kù)副本之間維護(hù)一致的狀態(tài)也是一個(gè)經(jīng)典的難題，而解決這個(gè)難題的最佳算法實(shí)踐正是本書(shū)中的重點(diǎn)內(nèi)容Paxos 算法。這個(gè)算法在大數(shù)據(jù)管理時(shí)代更是大放異彩，在BigTable，Hadoop 等多個(gè)大數(shù)據(jù)計(jì)算平臺(tái)上得到應(yīng)用。
目前市場(chǎng)上關(guān)于區(qū)塊鏈的書(shū)籍很多，但大多偏于介紹區(qū)塊鏈的基礎(chǔ)知識(shí)及應(yīng)用前景，純技術(shù)的書(shū)籍相對(duì)較少。本書(shū)著眼于區(qū)塊鏈的核心問(wèn)題拜占庭共識(shí)，針對(duì)不同的應(yīng)用場(chǎng)景，介紹了適用的分布式共識(shí)算法。書(shū)中包含了很多算法及證明，深入剖析了共識(shí)算法的核心思想。本書(shū)詳細(xì)介紹了在不同應(yīng)用場(chǎng)景下的分布式共識(shí)算法，包括單純宕機(jī)錯(cuò)誤（節(jié)點(diǎn)只可能發(fā)生宕機(jī)，但不會(huì)惡意犯錯(cuò)），拜占庭式錯(cuò)誤節(jié)點(diǎn)（可以認(rèn)為是惡意的節(jié)點(diǎn)，呈現(xiàn)任何行為），允許消息簽名，仲裁系統(tǒng)，弱一致條件下的共識(shí)等，并介紹了分布式存儲(chǔ)的一些基礎(chǔ)知識(shí)（如一致性哈希）。書(shū)中提到的很多算法，特別是PBFT，目前是區(qū)塊鏈的重要分支聯(lián)盟鏈的核心算法。
對(duì)于從事區(qū)塊鏈的研究者或工程技術(shù)人員來(lái)說(shuō)，共識(shí)算法是需要認(rèn)真弄清楚的內(nèi)容。雖然存在不少開(kāi)源的共識(shí)算法或區(qū)塊鏈框架，但不同的應(yīng)用對(duì)共識(shí)算法的要求是不一樣的，應(yīng)該根據(jù)應(yīng)用的特點(diǎn)選擇合
適的共識(shí)算法，甚至對(duì)已有的共識(shí)算法做必要的剪裁。要做到這一點(diǎn)，就必須理解基礎(chǔ)的分布式共識(shí)算法。而這就是本書(shū)的最大價(jià)值。
本書(shū)譯者之一，陳晉川博士，自2009 年從香港理工大學(xué)畢業(yè)后加入中國(guó)人民大學(xué)，一直在我的研究團(tuán)隊(duì)里工作。在大數(shù)據(jù)、分布式數(shù)據(jù)管理等領(lǐng)域做出了不少優(yōu)秀成果。晉川從去年開(kāi)始關(guān)注區(qū)塊鏈，他在查閱很多文獻(xiàn)之后，發(fā)現(xiàn)關(guān)于區(qū)塊鏈核心技術(shù)部分的資料很少，很難把握其精髓。在看到本書(shū)原著之后，他感覺(jué)這正是目前市場(chǎng)所缺少的干貨，就決定將其翻譯出來(lái)。本書(shū)內(nèi)容艱深，為了準(zhǔn)確、清晰地將內(nèi)容譯為中文，晉川投入了大量心血。作為一線科研工作者，能在背負(fù)巨大科研考核壓力的情況下，投入如此多精力從事翻譯工作，殊為不易。
其實(shí)，這本書(shū)不能算是嚴(yán)格意義上的翻譯，譯者除了原稿翻譯之外，還增加了很多譯者自己的注釋，對(duì)書(shū)中的算法、公式進(jìn)行注解（作者很多地方寫(xiě)得較為簡(jiǎn)略）。另外，書(shū)中還增加了兩章新的內(nèi)容。一章
是介紹Paxos 算法的發(fā)展史和在工業(yè)界的應(yīng)用情況，另一章是對(duì)比分析當(dāng)前主流的兩個(gè)共識(shí)機(jī)制，比特幣的PoW 和私有鏈的PBFT。現(xiàn)在都講究混搭，這本譯著也是一種形式的混搭。
杜小勇
中國(guó)計(jì)算機(jī)學(xué)會(huì)數(shù)據(jù)庫(kù)專委會(huì)主任
教育部數(shù)據(jù)工程與知識(shí)工程重點(diǎn)實(shí)驗(yàn)室主任
推薦序 III
身為一個(gè)智能時(shí)代的潮人，誰(shuí)的口袋里還不裝著幾塊比特幣？
近年來(lái)，比特幣作為第一種數(shù)字加密貨幣，受到了褒貶不一的評(píng)價(jià)；其價(jià)格一路飛漲，但走向主流貨幣之路卻是路漫漫其修遠(yuǎn)兮。但是，作為比特幣的核心底層技術(shù)，區(qū)塊鏈技術(shù)的受關(guān)注程度卻一路飆升。自2014 年以來(lái)，國(guó)內(nèi)外多家著名機(jī)構(gòu)在這一研究方向上已經(jīng)累計(jì)投入了數(shù)百億美元。其研發(fā)范圍已經(jīng)遠(yuǎn)遠(yuǎn)超越單純的數(shù)字加密貨幣，遍及銀行、保險(xiǎn)、物流、物聯(lián)網(wǎng)、資產(chǎn)交易、公證與鑒別、社交通信等領(lǐng)域。甚至有人宣稱，未來(lái)的社會(huì)及政府都可以架構(gòu)于區(qū)塊鏈之上。
區(qū)塊鏈為何會(huì)受到如此廣泛的關(guān)注？究其原因，其核心特征，去中心化、去信任化、智能合約等，正好滿足未來(lái)互聯(lián)網(wǎng)持續(xù)發(fā)展所要求的信息的高度自動(dòng)化和高度程序化的安全流轉(zhuǎn)需求。我們知道，互聯(lián)網(wǎng)作為一個(gè)連接媒介，連接了世界上一部分的信息、數(shù)據(jù)、交互和交易；移動(dòng)互聯(lián)網(wǎng)更是將連接范圍進(jìn)一步擴(kuò)大至幾乎所有人類活動(dòng)的范圍，基本完成了人類活動(dòng)的數(shù)字化。
在技術(shù)驅(qū)動(dòng)下，人類生活方方面面的數(shù)據(jù)量開(kāi)始激增，大規(guī)模計(jì)算出現(xiàn)了分布化和并行化的特點(diǎn)。在此基礎(chǔ)上，人工智能第三次浪潮洶涌而來(lái)，進(jìn)一步衍生了對(duì)高度自動(dòng)化和高度程序化的信息流轉(zhuǎn)的需求：非自動(dòng)化環(huán)節(jié)必然被不斷削減；信息的審核和控制將不再受限于任何一個(gè)權(quán)威性的中心節(jié)點(diǎn)，也不應(yīng)該被任何一個(gè)參與節(jié)點(diǎn)偽造、篡改和否認(rèn)。
對(duì)于上述需求，區(qū)塊鏈技術(shù)可以相對(duì)完美地提供解決方案。因此，可以預(yù)見(jiàn)，區(qū)塊鏈技術(shù)將會(huì)是智能時(shí)代數(shù)據(jù)存儲(chǔ)、傳輸、分發(fā)最有競(jìng)爭(zhēng)力的解決方案之一。
區(qū)塊鏈作為一個(gè)分布式的數(shù)據(jù)存儲(chǔ)、傳輸和分發(fā)解決方案，其核心在于如何在一個(gè)分布式、無(wú)受信節(jié)點(diǎn)的環(huán)境下，自動(dòng)形成共識(shí)（consensus）的機(jī)制。所謂共識(shí)機(jī)制，是指分布式系統(tǒng)中全部節(jié)點(diǎn)（或者大部分節(jié)點(diǎn)）就某條數(shù)據(jù)的真實(shí)性或者某條交易的價(jià)值達(dá)成一致，并據(jù)此更新各節(jié)點(diǎn)記錄的一種機(jī)制。不難看出，面對(duì)不同的場(chǎng)景、不同的應(yīng)用需求，需要設(shè)計(jì)并實(shí)施不同的共識(shí)機(jī)制。這就需要對(duì)共識(shí)機(jī)制在理論層面、技術(shù)層面有深入的理解。在智能時(shí)代，區(qū)塊鏈參與節(jié)點(diǎn)將可能是一個(gè)智能體，區(qū)塊鏈系統(tǒng)也將可能是一個(gè)多智能體系統(tǒng)。系統(tǒng)中節(jié)點(diǎn)的數(shù)量和行為可能是基于人工智能技術(shù)自動(dòng)產(chǎn)生和調(diào)整，而不是基于程序員所編寫(xiě)的固定規(guī)則。這種情況下，要想利用共識(shí)機(jī)制充分保證區(qū)塊鏈的安全運(yùn)行，需要對(duì)共識(shí)機(jī)制更為深刻的理解。
國(guó)內(nèi)關(guān)于區(qū)塊鏈的書(shū)籍已經(jīng)有很多了，但大多都是在談應(yīng)用、談理念或者在談相關(guān)的投融資，真正涉及技術(shù)細(xì)節(jié)的書(shū)籍相對(duì)較少�！秴^(qū)塊鏈核心算法解析》以共識(shí)機(jī)制為主體，系統(tǒng)介紹了區(qū)塊鏈所涉及的各種關(guān)鍵定理和證明，也給出了相應(yīng)算法。難能可貴的是，作者還結(jié)合實(shí)例講述了不同場(chǎng)景下的共識(shí)機(jī)制的設(shè)計(jì)方法。這是一本關(guān)于區(qū)塊鏈核心技術(shù)的系統(tǒng)論著，對(duì)于區(qū)塊鏈科研和應(yīng)用人員都具有很高的參考價(jià)值。
戴斌
國(guó)防科技大學(xué)機(jī)電工程與自動(dòng)化學(xué)院副總工程師
前言
當(dāng)你和從事金融科技（FinTech）的朋友在一起交談時(shí)，不可避免地會(huì)注意到一個(gè)非常流行的詞區(qū)塊鏈。聽(tīng)上去，它就像Internet 那樣重要。某些金融科技領(lǐng)域的朋友認(rèn)為區(qū)塊鏈?zhǔn)且欢紊衿娴拇a，它可以使一個(gè)分布式系統(tǒng)的參與者們就系統(tǒng)的狀態(tài)達(dá)成共識(shí)，從而追蹤系統(tǒng)的變化。區(qū)塊鏈這個(gè)詞語(yǔ)是從比特幣借用的，然而，早在區(qū)塊鏈或者比特幣出現(xiàn)之前，共識(shí)技術(shù)（或協(xié)定技術(shù)）（Agreement Techniques）就已經(jīng)在分布式系統(tǒng)領(lǐng)域中存在了。曾經(jīng)出現(xiàn)過(guò)各種各樣的概念和協(xié)議，各有其優(yōu)點(diǎn)和缺點(diǎn)。
本書(shū)的目的是深入剖析這項(xiàng)當(dāng)前最引人注目的技術(shù)區(qū)塊鏈。如果你是一名開(kāi)發(fā)者（不管是否在金融科技領(lǐng)域），本書(shū)將幫助你更好地理解：在你研發(fā)的分布式系統(tǒng)中，什么是對(duì)的，什么是錯(cuò)的，什么是可能的，而什么是不可能的。
本書(shū)介紹了構(gòu)建容錯(cuò)的分布式系統(tǒng)所需的基礎(chǔ)技術(shù)，以及一系列允許容錯(cuò)的協(xié)議和算法，并且討論一些實(shí)現(xiàn)了這些技術(shù)的實(shí)際系統(tǒng)。本書(shū)中的主要概念將獨(dú)立成章。每一章都以一個(gè)小故事開(kāi)始，從而引出該章節(jié)的內(nèi)容。算法、協(xié)議和定義都將以形式化的方式描述，以便于讀者理解如何實(shí)現(xiàn)。部分結(jié)論會(huì)在定理中予以證明，這樣讀者就可以明白為什么這些概念或算法是正確的，并且理解它們可以確保實(shí)現(xiàn)什
么。其他的大部分內(nèi)容將以評(píng)論的方式出現(xiàn)。這些評(píng)論將討論各種各樣非正式的思考，并且為后續(xù)內(nèi)容做好鋪墊。就算不閱讀這些評(píng)論，讀者們也可以掌握章節(jié)的精髓。此外，為了便于讀者尋根溯源，每一章也會(huì)討論相關(guān)技術(shù)的發(fā)展歷史。
本書(shū)將介紹不同的模型(以及模型的組合)，以適用于不同的場(chǎng)景。本書(shū)關(guān)注的是實(shí)用的協(xié)議和系統(tǒng)。換句話說(shuō)，我們?cè)谶x擇概念時(shí)，不會(huì)根據(jù)這些概念是否看起來(lái)有意思，而是根據(jù)它們是否有實(shí)際的價(jià)值。
不管怎樣，希望你在本書(shū)中找到樂(lè)趣！
Roger Wattenhofer博士是瑞士蘇黎世聯(lián)邦理工學(xué)院（ETH Zurich）的一名教授。在這之前，他曾在美國(guó)布朗大學(xué)（Brown University）及微軟研究院工作。他的研究興趣主要包括容錯(cuò)分布式系統(tǒng)、高效的網(wǎng)絡(luò)算法，以及加密貨幣。截至本書(shū)出版，他已發(fā)表了250多篇學(xué)術(shù)論文。
譯者介紹：
陳晉川，香港理工大學(xué)博士，中國(guó)人民大學(xué)信息學(xué)院副教授，碩士生導(dǎo)師，曾作為訪問(wèn)學(xué)者先后在微軟亞洲研究院和德國(guó)烏爾姆大學(xué)工作。目前研究方向?yàn)榇髷?shù)據(jù)管理、區(qū)塊鏈。
薛云志，中國(guó)科學(xué)院軟件研究所博士，清華大學(xué)MBA，中國(guó)科學(xué)院軟件研究所副研究員，碩士生導(dǎo)師，研究方向?yàn)槿斯ぶ悄堋④浖こ獭?br />
林強(qiáng)，律師、專利代理人，中國(guó)科學(xué)院軟件研究所計(jì)算機(jī)應(yīng)用碩士。執(zhí)業(yè)領(lǐng)域?yàn)橹R(shí)產(chǎn)權(quán)法，尤其是專利咨詢、申請(qǐng)、管理和權(quán)利行使。于2004年加入北京東方億思，一直致力于幫助許多財(cái)富500強(qiáng)跨國(guó)公司管理他們?cè)谥袊?guó)的專利組合。近年來(lái)，還幫助一些互聯(lián)網(wǎng)巨頭和國(guó)內(nèi)初創(chuàng)企業(yè)建立、管理全球?qū)＠M合。
祝慶，計(jì)算機(jī)科學(xué)碩士研究生，畢業(yè)于中國(guó)科學(xué)院研究生院。現(xiàn)任職于中國(guó)工商銀行總行，之前在甲骨文Oracle、IBM、Teradata等公司擔(dān)任首席企業(yè)架構(gòu)師、項(xiàng)目總監(jiān)等職位，在金融電信媒體行業(yè)有多年行業(yè)經(jīng)驗(yàn)。
第1章
1.1 分布式系統(tǒng)是什么. . . . . . . . . . . . . . . . . . . . . 1
1.2 本書(shū)概覽. . . . . . . . . . . . . . . . . . . . . . . . . . 2
第2章 容錯(cuò)問(wèn)題和Paxos 算法
2.1 客戶端/服務(wù)器. . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Paxos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
延伸閱讀：Paxos漫談
第3章 共識(shí)機(jī)制
3.1 兩個(gè)朋友約飯局. . . . . . . . . . . . . . . . . . . . . . . 27
3.2 共識(shí). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3 共識(shí)的不可能性. . . . . . . . . . . . . . . . . . . . . . . 29
3.4 隨機(jī)共識(shí). . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.5 共享硬幣. . . . . . . . . . . . . . . . . . . . . . . . . . 41
第4章 拜占庭協(xié)定
4.1 有效性. . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2 有多少個(gè)拜占庭節(jié)點(diǎn). . . . . . . . . . . . . . . . . . . . 49
4.3 國(guó)王算法. . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.4 輪數(shù)的下界. . . . . . . . . . . . . . . . . . . . . . . 55
4.5 異步模式下的拜占庭協(xié)定算法. . . . . . . . . . . . . . 56
第5章 認(rèn)證的協(xié)定
5.1 利用認(rèn)證的協(xié)定. . . . . . . . . . . . . . . . . . . . . . . 62
5.2 Zyzzyva . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
第6章 仲裁系統(tǒng)
6.1 負(fù)載和工作量. . . . . . . . . . . . . . . . . . . . . . . . 82
6.2 網(wǎng)格仲裁系統(tǒng). . . . . . . . . . . . . . . . . . . . . . . . 85
6.3 容錯(cuò). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.4 拜占庭仲裁系統(tǒng)(Byzantine Quorum Systems) . . . . . . 92
第7章 最終一致性以及比特幣
7.1 一致性、可用性，以及分區(qū). . . . . . . . . . . . . . . . 102
7.2 比特幣. . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.3 智能合約(Smart Contracts) . . . . . . . . . . . . . . . . 113
7.4 弱一致性. . . . . . . . . . . . . . . . . . . . . . . . . . 117
延伸閱讀：PoW vs. BFT
第8章 分布式系統(tǒng)
8.1 一致性哈希(Consistent Hashing) . . . . . . . . . . . . . 128
8.2 超立方體網(wǎng)絡(luò)(Hypercubic Networks) . . . . . . . . . . . 131
8.3 DHT ＆ Churn . . . . . . . . . . . . . . . . . . . . . . . 140
新書(shū)資訊