【技術貼】從拜占庭問題，談區塊鍊技術實作及政務應用

本文，作者首先介紹了拜占庭問題和口頭消息算法；其次，詳細讨論以HyperLedger1.0為基礎的系統架構和資料庫事務處理流程，并分析該架構與傳統中心化資料庫的主要差別；最後，以南京政務網建設為例子闡述區塊鍊技術的具體應用。

作者 | 丁藝明

拜占庭問題

探究區塊鍊其源頭，我們不得不追溯到“拜占庭将軍問題”。它是整個區塊鍊技術核心思想的真正根源，也直接決定了區塊鍊技術的種種與衆不同的颠覆性特質。

在2013年獲得計算機科學領域最高獎項圖靈獎的31年前，萊斯利·蘭伯特（Leslie Lamport）加入斯坦福國際研究院（SRI）。在SRI那段歲月裡， 有一個項目，要在美國航空航天局建立容錯型航電計算機系統。考慮到系統的工作性質，故障是不允許發生的。這段經曆孕育了兩篇旨在解決一種特殊故障的論文，由蘭伯特和SRI同僚馬歇爾·皮斯（Marshall Pies）及羅伯特·肖斯塔克（Robert Shostak）合作完成。使用計算機術語，普通故障可能會導緻資訊丢失或程序停止，但系統不會遭到破壞，因為這種普通故障屬于一出錯就會停下來的故障類型，剩下的備份的、正常的部分照樣可以運轉，發揮作用。就像戰場上的士兵，他們一旦受傷或陣亡就停止戰鬥，但并不妨礙他人繼續作戰。然而一旦發生“拜占庭故障”，就會非常麻煩，因為它們不會停下來，還會繼續運轉，并且給出錯誤訊息。就像戰争中有人成了叛徒，會繼續假傳軍情，惑亂人心。使用三台計算機進行萬一其中一台出錯的備份工作，并不能完全解決這個問題。三台獨立的計算機按照少數服從多數的原則“投票”。要求其中一台機器提供了錯誤結果的情況下，其他兩台仍然會提供正确答案。但是為了證明這種解決“拜占庭故障”方法的有效性，必須拿出證據。而在編寫證據的過程中，研究人員遇到了一個問題：“錯誤”的計算機可能給其他兩台計算機發送互不相同的資訊，而後者卻無法差別正确性。這就需要使用第四台計算機來應對這類“拜占庭故障”。

蘭伯特認為把問題以講故事的形式表達出來更能引起人們的關注。蘭伯特還聽吉姆·格雷談論過另一個性質大體相同的問題，這引起了蘭伯特有關司令将軍和叛徒将軍的聯想，于是他将這個問題及其解決方案命名為“拜占庭将軍問題”。

拜占庭帝國想要進攻一個強大的敵人，為此派出了10支軍隊去包圍這個敵人。這個敵人雖不比拜占庭帝國，但也足以抵禦5支正常拜占庭軍隊的同時襲擊。基于一些原因，這10支軍隊不能集合在一起單點突破，必須在分開的包圍狀态下同時攻擊。他們任一支軍隊單獨進攻都毫無勝算，除非有至少6支軍隊同時襲擊才能攻下敵國。他們分散在敵國的四周，依靠通信兵互相通信來協商進攻意向及進攻時間。困擾這些将軍的問題是，他們不确定其中是否有叛徒，叛徒可能擅自變更進攻意向或者進攻時間。在這種狀态下，拜占庭将軍們能否找到一種分布式的協定來讓他們能夠遠端協商，進而赢取戰鬥？這就是著名的拜占庭将軍問題。

應該明确的是，拜占庭将軍問題中并不去考慮通信兵是否會被截獲或無法傳達資訊等問題，即消息傳遞的信道絕無問題。蘭伯特已經證明了在消息可能丢失的不可靠信道上試圖通過消息傳遞的方式達到一緻性是不可能的。是以，在研究拜占庭将軍問題的時候，我們已經假定了信道是沒有問題的，并在這個前提下，去做一緻性和容錯性相關研究。

口頭消息算法，簡稱OM（m）

在原始的戰争年代，将軍與将軍、将軍與下屬間隻能采用原始的方式——“出行靠走，通訊靠吼”的口頭傳輸。這對應蘭伯特論文提出算法中的第一部分的口頭消息算法，簡稱OM（m）算法。這種情形，真僞很難辨識，隻有當叛徒的總數不超過将軍總數的1/3，成為一個特殊的“拜占庭容錯系統”時，才能在很大的消息驗證代價後，實作最終的一緻行動。這個結果非常令人驚訝，如果将軍們隻能發送口頭消息，除非超過2/3的将軍是忠誠的，否則該問題無解。尤其是，如果隻有三個将軍，其中一個是叛變者，那麼此時無解。但這樣的錯誤，這樣的有意、無意的“叛徒”卻可能經常出現。

首先，我們明确什麼是口頭協定。我們将滿足以下三個條件的方式稱為口頭協定：

A1：每個被發送的消息都能夠被正确的投遞

A2：資訊接收者知道是誰發送的消息

A3：能夠知道缺少的消息

簡而言之，信道絕對可信，且消息來源可知。

定義一個變量vi（為不失一般性，并不要求vi是布爾值），作為其他将軍收到的第i個将軍的指令值；i将軍會将把自己的判斷作為vi。可以想象，由于叛徒的存在，各個将軍收到的vi值不一定是相同的。之後，定義一個函數來處理向量(v1,v2,…,vn)，代表了多數人的意見，各将軍用這個函數的結果作為自己最終采用的指令。至此，我們可以利用這些定義來形式化這個問題，用以比對一緻性和正确性。

一緻性

條件1：每一個忠誠的将軍必須得到相同的(v1,v2,…,vn)指令向量或者指令集合。

這意味着，忠誠的将軍并不一定使用i将軍送來的資訊作為vi，i将軍也可能是叛徒。但是僅靠這個條件，忠誠的将軍的資訊送來的資訊也可能被修改，這将影響到正确性。

正确性

條件2：若i将軍是忠誠的，其他忠誠的将軍必須以他送出的值作為vi。

OM(0)算法

1. 司令将他的指令發送給每個副官。

2. 每個副官采用從司令發來的指令；如果沒有收到指令，則預設為撤退指令。

OM(m)算法

2. 對于每個i，vi是每個副官i從司令收到的指令，如果沒有收到指令，則預設為撤退指令。副官i在OM(m-1) 中作為發令者将之發送給另外n-2 個副官。

3. 對于每個i，和每個j ≠ i，vj 是副官i 從第2步中的副官j （使用OM(m-1)算法）發送過來的指令，如果沒有收到第2步中副官j 的指令，則預設為撤退指令。最後副官i 使用majority(v1,…,vn-1)得到指令。

其中，majority(v1,…,vn-1)代表了大多數人的指令，若不存在則預設為撤退指令。

口頭消息算法執行個體推演

考慮m=1，n=4的情形：

n=4，意味着一個司令發送指令給三個副官，m=1意味着他們中有一個叛徒。首先考慮司令忠誠而副官3是叛徒的情況。



圖1   m=1，n=4中司令忠誠而副官3是叛徒的情形

參考圖1，

L1收到：（A，A，R）=》輸出共識 majority(A，A，R) = A

L2收到：（A，A，R）=》輸出共識 majority(A，A，R) = A

L3收到：（A，A，A）=》輸出共識 majority(A，A，R) = A

那麼對于副官1（或副官2）來說将會采用A。

倘若司令是叛徒，為友善，我們假設叛徒司令在OM(1)會給三個副官發送的資訊是(x,y,z)，其中x，y，z都可以是A或R的任意一種。之後，三位忠誠的副官将會按照OM(0)要求的那樣，交換他們收到的資訊。

圖2  m=1，n=4中司令是叛徒的情形

L1收到：（x，y，z）=》輸出共識 majority（x，y，z） ；

L2收到：（x，y，z）=》輸出共識 majority（x，y，z）；

L3收到：（x，y，z）=》輸出共識 majority（x，y，z）。

對于副官1，他綜合司令、副官2和副官3後得到的消息向量将會是(x,y,z)，可以發現對于其他兩個忠實的副官，他們得到的消息向量也将是(x,y,z)。不管x，y，z如何變化，majority(x,y,z)對于三人來說都是一樣的，是以三個副官将會采用一緻的行動。

口頭消息算法證明

算法的證明思路其實并不複雜，簡單的來說，對于一個遞歸算法，基于一個叛徒情景下的執行個體推演，可使用數學歸納法來證明。考慮篇幅，這裡未提供完整的證明，可參考相關資料。

HyperLedger1.0系統架構

Hyperledger是被業界非常看到的聯盟鍊的實作，包括IBM、Intel、R3、各個大型商業銀行等都參與其中，帶給我們關于區塊鍊技術與軟體工業、金融、保險、物流等領域碰撞結合的想象空間；在這個聯盟中，有超過1/4的成員都來自中國，這更是我們對于它的一舉一動都非常關注。很大程度上，Hyperledger和它背後的聯盟體系就代表着區塊鍊在産業環境中的未來。

主要子產品：

• 用戶端SDK（Client SDK）: 協助應用安全管理、和協助處理區塊鍊上交易事務。
• 節點是網絡中的組成部分，負責維護節點的賬本和職能合約。
• 任意多個節點可參與到網絡中。
• 節點類型可以是背書節點（endorser）、或傳遞節點（committer ）。背書節點必然是傳遞節點。
• 背書節點執行并對交易事務進行背書。
• 傳遞節點驗證背書結果并對交易事務進行驗證。
• 節點管理事件集線器（event hub）并發送事件給訂閱者。
• 節點組建成一P2P網絡。
• 節點是無運作狀态的，事務與事務間是獨立的。
• 排序服務（Ordering Service）：是處于一個非中心化的網絡中的一個中心化的節點。其排序服務是一可插拔的元件，例如Kafka、或BFT等。
• 成員權限管理：通過基于 PKI 的成員權限管理，平台可以對接入的節點和用戶端的能力進行限制。

圖3  HyperLedger1.0系統結構圖

事務交易流程

HyperLedger1.0的共識機制（Consensus）是通過事務背書政策（Transaction Endorsement Policy）、排序服務、和各送出節點Committer的校驗這三個措施保證的。

背書（Endorsement）: 每個背書節點（stakeholder ）決定是否接受或拒絕一事務。

排序服務（Ordering）: 對執行後的事務進行排序形成一即将送出的區塊。

校驗（Validation）: 所有送出節點（Committer ）都需校驗事務的背書是否滿足背書政策（Endorsement Policy），同時根據資料庫多版本并發控制MVCC，校驗事務轉換是否有效。

以背書節點n=4、送出節點數p=5為例子。背書政策設定為：4個背書節點中，允許1個拜占庭故障節點情況下，要求有3個以上的有效簽名。

圖4  事務交易流程

也就是，如果允許m個無效簽名的情況下，要求背書節點總數n>=3*m + 1，即需要有效簽名數n-m>=2*m+1。如圖4所示事務處理流程為：

步驟1：送出事務

用戶端SDK送出一封包為Propose的消息的交易事務Transaction到用戶端選擇的背書節點E0，要求執行一智能合約A。

圖5   步驟1送出事務

步驟2：第一個背書節點執行事務

被用戶端選中的背書節點E0模拟交易的執行。

圖6   步驟2第一個背書節點執行事務

步驟3：其他背書節點執行事務

用戶端根據背書政策，要求其他節點E1E2和E3進一步背書。

圖7   步驟3其他背書節點執行事務

步驟4：背書簽名

背書節點對智能合約的執行結果進行簽名，并發送背書簽名給用戶端。

圖8  步驟5送出排序服務

步驟5：送出排序請求

最後，用戶端根據背書政策（Endorsement Policy）檢查是否滿足條件，若滿足條件則發送給排序服務。

圖9  步驟6傳遞

步驟6：傳遞

排序服務叢集傳遞事務執行結果的下個版本的賬本資料塊給各節點。

圖10  步驟7校驗并更新

區塊鍊應用于政務網

傳統中心化的電子證照技術自2008年發展至今，解決了傳統模式下的資料歸集和中心化的資料标準與安全問題。但經過近十年的“網際網路+政務服務”的應用發展，該技術也凸顯它的局限性。

• 跨部門的政務資料是否可信
• 資訊難以全面歸集
• 資訊難以快速檢索
• 資訊洩露安全隐患
• 系統穩定性難度大
• 金字塔模式效率低下

雖然已有的人口資訊、法人資訊實作了部分集中管理，但中心化系統存在資訊洩露，存儲丢失等風險，而且中心化系統的建設、維護成本非常高，無法互動驗證，無法實作各個部門真正意義上的資訊共享、共建。是以，如何在現有的電子政務基礎上，打破部門的資料壁壘，實作各部門之間的高效協作，實作真正意義的“一張網”，為群衆提供便利的服務，是政務工作迫切需要解決的問題。

另外，區塊鍊技術具有資訊共享、資訊透明、難以篡改的優勢。利用該優勢可打破原有資訊傳遞的壁壘，實作電子證照服務模式的創新，提升使用者體驗。

目前證照辦理過程中，大部分步驟需線上下處理，并且受到地域、時間的限制，需消耗較多的時間；同時紙質證明存在易僞造風險，相關證明接收機構還需核驗證明的真僞性。

通過區塊鍊技術打造各類證明的線上認證服務模式，可以提供證明從申請、開立、查詢、銷毀的全流程服務，打造電子證明生态圈。該創新将帶來巨大的社會效益：

對于證明所有者，無須在證明開立方和證明使用方來回傳遞紙質證明，省卻了實體地點（如異地）對證明開立及使用的限制；

對于證明提供方的權威機構，可通過自動化審批替代目前的人工審批，大大提高了工作效率和服務水準；

對于證明需求方，基于區塊鍊的電子證明難以僞造及篡改，大大降低了虛假證明的風險。

圖11  “我的南京”App政務辦理

在南京政府多部門的支援下，率先上線全國第一批基于區塊連結技術的電子證照共享平台。參見圖11，市民可通過“我的南京”App進行政務的辦理，“我的南京”App是該電子證照共享平台的資料通路終端。電子證照共享平台由政府職能部門共同組成的電子證照區塊鍊網絡，建立起政府部門之間點對點的可信網絡。采用區塊鍊的去中心化同步記帳、交易身份認證、資料不可篡改、以及資料加密等多種技術手段。參見圖12電子證照政務網結構圖，網絡由資訊中心、公安、民政、社保、稅務、衛生等多個節點組成。共享賬本中存儲公民資訊和資料歸集記錄。在智能合約中實作了資料目錄規則、和資料隐私管理規則。現有電子證照網絡隻支援南京市的資料，考慮到擴充性支援，通過全國索引節點，不同城市不同省份的資料索引到不同的電子證照區塊鍊子網。

圖12  電子證照政務網結構圖

基于區塊鍊技術的電子證照共享平台與傳統的電子證照庫相比，具有更好的真實作、安全性、穩定性及可行性，解決了傳統中心化架構的電子證照庫采集和應用過程中權責不分的問題，徹底解決了資料被篡改的可能性，并通過激勵機制提升資料相關方共享資料的積極性，且具備資料不被篡改、去中心化、資料加密及信任傳遞的特征，創新實作電子證照在全省、全市範圍内跨區域的資訊歸集、快速檢索和結果應用。透過任意職能部門提供照證證明服務，提高政務工作效率，提高市民、企業的辦事效率。對進一步推進南京“網際網路＋政務服務”，深化簡政放權、放管結合，實作各部門、各層級間政務服務資料共享，促進政府高效施政，提供了強有力的支援。

區塊鍊弱并發問題

在應用區塊鍊解決方案于政務網工程建設過程中，發現不少差別于傳統關系型資料庫的區塊鍊特點。

HyperLedger其設計目标主要包括一緻性（共識）、保密性、可擴充性和安全性，但是對高并發寫事務的支援并不其主要目标。HyperLedger采用樂觀鎖（多版本并發控制）機制來支援并發，當傳遞節點（Submitter Peers）送出事務之前，如果發現ReadSet和WriteSet已經不一緻了，将復原事務。用戶端需要盡可能避免同一關鍵字的寫沖突，如果寫沖突，需要多次送出事務。

假設在同一時刻有10個事務同時送出，當時這10個事務讀取到的賬本的資料一緻。第一階段，各背書節點執行事務，計算每個事務的讀集合ReadSet0~9（K,V）和寫集合WriteSet0~9（K,V），并送出到排序服務；第二階段，排序服務對10個事務進行排序，并依次送出到所有的傳遞節點（Submitter Peers），傳遞節點會根據目前賬本中的值檢查對應于某一事務的讀集合和寫集合。如果對于同一個鍵Key，被前一個事務修改了，則該事務的讀集合與目前賬本的讀集合不一緻，則該事務不得不復原。

為了避免并行執行的事務讀寫沖突，提升事務的并發執行效率。對于出現讀寫沖突的事務，采用拆分事務成為兩個階段的方法，在背書階段記錄事務的明細賬，在送出階段才進行彙總。例如對于會員積分變更的應用場景，在背書階段，記錄會員積分的變化明細，+ x1 + ... + xi 和 - y1 - ... - yi，在送出階段才進行彙總積分的變更 D += + x1 + ... + xi - y1 - ... - yi 。

關系型資料模組化的支援

區塊鍊的底層資料模型為比較簡單的鍵值對Key/Value模型，對于現實中的結構化資料的模組化一般采用關系資料模型，如果采用Key/Value模型，開發人員需要耗費很多精力用于各種應用場景下資料模型的建設，和資料的索引、查詢、統計等正常處理；同時存儲在區塊鍊中的資料需要進行進一步的大資料分析和資料挖掘工作，需要支撐區塊鍊中的資料的導入導出到關系型資料庫。另外現有區塊鍊還沒有支援資料的隐私保護、資料的送出維護和通路的權限管理。需要一完善的區塊鍊資料模組化基礎架構來解決這些基于區塊鍊的應用開發問題。

基于鍵值資料模型為基礎進行關系型資料模組化，其支援的特征包括：

基于鍵值資料模型，選擇一取值唯一的字段作為鍵，包括多個屬性字段的記錄作為值，記錄用獨立于語言的輕量級資料交換格式JSON進行編碼。

支援表結構、索引結構資料字典的維護；屬性字段支援數值類型、字元串類型、日期類型。這些類型的字段是有序的、可建索引的；支援屬性索引，索引類型包括唯一索引、非唯一索引。索引的維護與記錄的增删改同步，同時索引資料結構的維護對模型的使用者透明。對于複雜結構的字段例如結構數組，可用JSON編碼，隻是該JSON類型字段不支援索引。另外利用索引支援資料限制，例如屬性字段取值的唯一性限制。

支援豐富的資料查詢方式，例如根據鍵的某一取值查詢記錄；根據鍵的取值範圍查詢多條記錄；根據已建立唯一索引的屬性字段的某一取值查詢記錄；根據已建立非唯一索引的屬性的某一取值，或屬性字段的取值範圍查詢多條記錄；支援分組統計，例如基于屬性字段的非唯一索引進行分組統計，統計函數包括個數統計、取分組的最大值、最小值、平均值；支援分頁查詢和分頁統計；支援區塊鍊資料的導入導出到關系型資料庫，用于支撐資料分析。

後續豐富的政務網應用

本電子證照共享平台還将實作更多政務事項線上辦理功能，如：“購車資格證明線上辦理”、“戶口線上遷入”、“社保線上轉移”、“公積金線上提取”、“護照線上辦理”、“出入境自助簽注”等。

原文釋出時間為：2018年02月23日

本文作者：區塊鍊大學營

本文來源：

CSDN區塊鍊大學營

，如需轉載請聯系原作者。