[發(fā)明專利]一種拜占庭容錯方法及其實現(xiàn)系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201810356617.5
• 申請日: 2018-04-19
• 公開（公告）號: CN108667614B
• 公開（公告）日: 2021-02-02
• 發(fā)明（設(shè)計）人: 叢宏雷;胡凝
• 申請（專利權(quán)）人: 上海分布信息科技有限公司
• 主分類號: H04L9/32
• 分類號: H04L9/32;H04L12/801;H04L29/06;H04L29/08
• 代理公司: 上海恒銳佳知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 31286
• 代理人: 黃海霞

本發(fā)明公開了一種拜占庭容錯方法，包括：節(jié)點選擇步驟：從區(qū)塊鏈網(wǎng)絡(luò)中選擇至少提案節(jié)點、背書節(jié)點、確認節(jié)點。提案步驟：提案節(jié)點構(gòu)建新的備選區(qū)塊。背書步驟：背書節(jié)點對收到的備選區(qū)塊進行驗證，然后將備選區(qū)塊進行優(yōu)先級排序，并對具有最高優(yōu)先級的備選區(qū)塊進行背書。確認步驟：如有備選區(qū)塊在預(yù)定時間內(nèi)得到預(yù)定數(shù)量的背書節(jié)點的背書，則由所述確認節(jié)點對其進行確認。區(qū)塊保存步驟：如有備選區(qū)塊在預(yù)定時間內(nèi)的到預(yù)定數(shù)量的所述確認節(jié)點的確認，則所述備選區(qū)塊完成共識；區(qū)塊鏈網(wǎng)絡(luò)中的所有節(jié)點保存所述完成共識的區(qū)塊。本發(fā)明還公開了所述拜占庭容錯方法的實現(xiàn)系統(tǒng)。本發(fā)明可確保在極端情況下持續(xù)運行，并有利于區(qū)塊鏈網(wǎng)絡(luò)擴大規(guī)模。

技術(shù)領(lǐng)域

本發(fā)明涉及一種區(qū)塊鏈(Blockchain)網(wǎng)絡(luò)的共識算法(consensus mechanism)，尤其涉及一種拜占庭容錯(Byzantine FaultTolerance，BFT)方法。

背景技術(shù)

2016年10月18日工業(yè)和信息化部發(fā)布的《中國區(qū)塊鏈技術(shù)和應(yīng)用發(fā)展白皮書》中，將區(qū)塊鏈定義為一種無須中介參與、亦能在互不信任或弱信任的參與者之間維系一套不可篡改的賬本記錄的技術(shù)。首先，區(qū)塊鏈是一種以區(qū)塊(block)為單位的鏈(chain)狀數(shù)據(jù)結(jié)構(gòu)，每一個區(qū)塊都與前續(xù)區(qū)塊通過密碼學(xué)證明的方式鏈接在一起。其次，區(qū)塊鏈是一種全網(wǎng)共享的分布式賬本(distributed ledger)。許多場景中，區(qū)塊鏈與分布式賬本這兩個技術(shù)術(shù)語具有相同含義。

典型地，區(qū)塊鏈技術(shù)被P2P網(wǎng)絡(luò)(peer-to-peer network)的全部或部分節(jié)點用來根據(jù)某種共識算法驗證新的區(qū)塊，通過驗證的新區(qū)塊被新增到區(qū)塊鏈數(shù)據(jù)結(jié)構(gòu)的末尾。采用區(qū)塊鏈技術(shù)的P2P網(wǎng)絡(luò)就被稱為區(qū)塊鏈網(wǎng)絡(luò)。共識是指多方參與的節(jié)點在預(yù)設(shè)規(guī)則下，通過多個節(jié)點交互對某些數(shù)據(jù)、行為或流程達成一致的過程。共識機制是定義共識過程的算法、協(xié)議和規(guī)則。

共識算法，作為分布式算法的一種，其復(fù)雜度主要通過消息復(fù)雜度(MessageComplexity)表示。所謂消息復(fù)雜度就是共識算法完成共識的過程中需要在區(qū)塊鏈網(wǎng)絡(luò)中傳播的消息的數(shù)量。

常見的共識算法包括實用拜占庭容錯(Practical Byzantine Fault Tolerance，PBFT)算法、授權(quán)拜占庭容錯(Delegated Byzantine Fault Tolerance)算法等。這些傳統(tǒng)的拜占庭容錯算法完成一輪共識的消息復(fù)雜度為N²，其中N為網(wǎng)絡(luò)規(guī)模，即區(qū)塊鏈網(wǎng)絡(luò)中全部節(jié)點的數(shù)量。因此，傳統(tǒng)的拜占庭容錯算法在區(qū)塊鏈網(wǎng)絡(luò)中使用時，隨著網(wǎng)絡(luò)規(guī)模擴大所要傳播的消息數(shù)量成平方級增長，這容易發(fā)生消息堵塞網(wǎng)絡(luò)的情況。

因此，有必要開發(fā)一種新型拜占庭容錯方法以解決上述技術(shù)問題。

發(fā)明內(nèi)容

本發(fā)明所要解決的技術(shù)問題是：提供一種拜占庭容錯方法，用作區(qū)塊鏈網(wǎng)絡(luò)的共識算法時，隨著網(wǎng)絡(luò)規(guī)模擴大消息數(shù)量緩慢增長，因而不容易堵塞網(wǎng)絡(luò)，有利于擴展網(wǎng)絡(luò)規(guī)模。相應(yīng)地，本發(fā)明還要提供一種拜占庭容錯方法的實現(xiàn)系統(tǒng)。

為解決上述技術(shù)問題，本發(fā)明提供了一種拜占庭容錯方法，包括如下步驟。

節(jié)點選擇步驟：從區(qū)塊鏈網(wǎng)絡(luò)的全部節(jié)點中選擇至少三種節(jié)點，分別作為提案節(jié)點、背書節(jié)點和確認節(jié)點。

提案步驟：所述提案節(jié)點構(gòu)建新的備選區(qū)塊，簽名后在所述區(qū)塊鏈網(wǎng)絡(luò)中廣播；所述提案節(jié)點分為至少兩個不同的優(yōu)先級，優(yōu)先級高的提案節(jié)點構(gòu)建的備選區(qū)塊具有較高的優(yōu)先級。

背書步驟：所述背書節(jié)點對收到的備選區(qū)塊進行驗證，然后將備選區(qū)塊進行優(yōu)先級排序，并對具有最高優(yōu)先級的備選區(qū)塊進行背書，簽名后在區(qū)塊鏈網(wǎng)絡(luò)中廣播。

確認步驟：如有備選區(qū)塊在預(yù)定時間內(nèi)得到預(yù)定數(shù)量的背書節(jié)點的背書，則由所述確認節(jié)點對預(yù)定時間內(nèi)得到預(yù)定數(shù)量的背書節(jié)點的背書的備選區(qū)塊進行確認，簽名后在區(qū)塊鏈網(wǎng)絡(luò)中廣播。