基于改進(jìn)Raft 算法的私有鏈模型

朱漢成

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0 引言

隨著以比特幣為代表的虛擬數(shù)字貨幣飛速發(fā)展，區(qū)塊鏈作為這個(gè)應(yīng)用的底層關(guān)鍵技術(shù)受到了國家和科技巨頭們的極大關(guān)注。區(qū)塊鏈天生具有去中心化、不可篡改等特性，使其在對(duì)數(shù)據(jù)信息安全性要求高的行業(yè)應(yīng)用前景極其看好[2]，現(xiàn)如今很多銀行帶頭做起金融區(qū)塊鏈，螞蟻金服也發(fā)布了落地應(yīng)用——善款追蹤和商品溯源。但是現(xiàn)在的以太網(wǎng)為代表的區(qū)塊鏈生態(tài)系統(tǒng)的在交易吞吐量等方面遠(yuǎn)遠(yuǎn)滿足不了當(dāng)今大部分應(yīng)用場(chǎng)景的需求。

共識(shí)算法作為區(qū)塊鏈的核心，往往決定著區(qū)塊鏈的出塊效率，如今共識(shí)算法發(fā)展的十分全面[1]。現(xiàn)如今以PoW、PoS 算法為主流共識(shí)算法的公有鏈，雖然可以很好的保證了安全性，但是效率低下。以Paxos、Raft為代表的傳統(tǒng)一致性算法只能追求在宕機(jī)或者網(wǎng)絡(luò)問題時(shí)仍能保證一致性，但是組織惡意節(jié)點(diǎn)進(jìn)行破壞攻擊；PBFT 拜占庭容錯(cuò)算法）則是一種狀態(tài)機(jī)副本復(fù)制算法，可以防止1/3 以下節(jié)點(diǎn)數(shù)的惡意節(jié)點(diǎn)攻擊，但是卻需要較大的網(wǎng)絡(luò)帶寬來保證副本的復(fù)制。

區(qū)塊鏈作為這兩年風(fēng)頭正熱的新興技術(shù)，難以落地一直困擾眾多看好區(qū)塊鏈的政府與企業(yè)。現(xiàn)實(shí)的企業(yè)應(yīng)用中，假如應(yīng)用不涉及代幣內(nèi)容，那么我們可能要求的區(qū)塊鏈的交易吞吐量達(dá)到一個(gè)較高的量級(jí)，而不是常見公有鏈以分鐘計(jì)來確定一個(gè)區(qū)塊。因?yàn)橹髁鞯墓墟湹膮^(qū)塊鏈應(yīng)用不僅效率堪憂，而且浪費(fèi)大量算力是國家和有責(zé)任的企業(yè)不愿意看見的。隨之而來就是大量對(duì)聯(lián)盟鏈和私有鏈的研究。聯(lián)盟鏈?zhǔn)嵌鄶?shù)機(jī)構(gòu)共同維護(hù)一個(gè)聯(lián)盟鏈，并且大多使用基于PBFT 的算法，TPS 可以過萬，但是還是容易收到PBFT 算法影響，當(dāng)節(jié)點(diǎn)個(gè)數(shù)過多時(shí)，共識(shí)難以達(dá)成，效率大受影響。私有鏈與聯(lián)盟鏈類似，但私有鏈由單個(gè)機(jī)構(gòu)或組織來管理，很多時(shí)候默認(rèn)鏈中節(jié)點(diǎn)是不會(huì)成為惡意節(jié)點(diǎn)進(jìn)行攻擊的。但是私有鏈實(shí)際情況之中還是會(huì)出現(xiàn)惡意節(jié)點(diǎn)，假如惡意節(jié)點(diǎn)成為記賬節(jié)點(diǎn)，那么對(duì)于整個(gè)私有鏈?zhǔn)侵旅?。本文將改進(jìn)Raft 算法并且應(yīng)用到我們的私有鏈之中，既保留了算法中快速找出記賬節(jié)點(diǎn)進(jìn)行記賬，同時(shí)保證出現(xiàn)惡意節(jié)點(diǎn)攻擊也能保證系統(tǒng)穩(wěn)定、其他節(jié)點(diǎn)不受影響。

1 相關(guān)工作

Lamport 首次提出Paxos 算法，用以解決分布式中節(jié)點(diǎn)的一致性問題，雖然后來又在中進(jìn)行簡(jiǎn)化說明，仍然理解起來較為吃力并且難以工程實(shí)現(xiàn)。Diego Ongaro 和John Ousterhout[3]提出了Raft 算法，相比于Paxos而言更加簡(jiǎn)單理解而且更容易工程實(shí)現(xiàn)。一致性是指多個(gè)服務(wù)器節(jié)點(diǎn)狀態(tài)達(dá)成一致，但是在一個(gè)分布式的系統(tǒng)之中仍然會(huì)出現(xiàn)一些節(jié)點(diǎn)出現(xiàn)宕機(jī)等不穩(wěn)定狀況，就難以和其他的服務(wù)器保持一致。這時(shí)候一致性協(xié)議出現(xiàn)可以保證盡管出現(xiàn)節(jié)點(diǎn)異常，仍然可以保證整個(gè)分布式系統(tǒng)正常運(yùn)行。在Raft 算法中，主要有三個(gè)角色：Candidate、Leader、Follower。Candidate 節(jié)點(diǎn)分別向其他的節(jié)點(diǎn)索要選票，如果收到的選票可以達(dá)到節(jié)點(diǎn)數(shù)的半數(shù)以上，Candidate 節(jié)點(diǎn)的身份將會(huì)升級(jí)為Leader，Leader 就可以對(duì)其他Follower 節(jié)點(diǎn)進(jìn)行只會(huì)操作。李升林[4]等人也曾改進(jìn)Raft 算法并且將其用在區(qū)塊鏈中，Raft 算法的簡(jiǎn)單高效有著很高的改進(jìn)余地。本文通過對(duì)Raft 算法進(jìn)行改進(jìn)以防止惡意節(jié)點(diǎn)攻擊。本文將增加一個(gè)Monitor 身份用以接收驗(yàn)證信息并且此時(shí)可以判斷哪些節(jié)點(diǎn)出現(xiàn)問題或者是惡意節(jié)點(diǎn)，達(dá)到一定錯(cuò)誤次數(shù)以后將會(huì)進(jìn)行刪除節(jié)點(diǎn)的操作。Leader 將會(huì)把打包的區(qū)塊信息廣播給其他的Follower 節(jié)點(diǎn)，因?yàn)槊總€(gè)節(jié)點(diǎn)都會(huì)收到所有的交易數(shù)據(jù)，那么每個(gè)節(jié)點(diǎn)都可以對(duì)Leader 打包的區(qū)塊進(jìn)行一個(gè)驗(yàn)證。每個(gè)節(jié)點(diǎn)都會(huì)將自己的計(jì)算結(jié)果廣播給所有的其他節(jié)點(diǎn)，此時(shí)所有節(jié)點(diǎn)的身份都將變成Monitor，Monitor 將會(huì)進(jìn)行統(tǒng)計(jì)票數(shù)，如果收到的計(jì)算結(jié)果正確的個(gè)數(shù)超過半數(shù)，則說明Leader 計(jì)算的結(jié)果正確并且進(jìn)行記賬，同時(shí)各個(gè)節(jié)點(diǎn)將會(huì)記錄問題節(jié)點(diǎn)，記錄達(dá)到一定程度，我們將舍棄此節(jié)點(diǎn)；如果收到計(jì)算結(jié)果正確的個(gè)數(shù)未超過半數(shù)，則說明Leader 計(jì)算結(jié)果出錯(cuò)，節(jié)點(diǎn)身份將會(huì)變成Candidate 再次競(jìng)爭(zhēng)Leader，至于上一輪Leader 計(jì)算結(jié)果出錯(cuò)可能會(huì)出現(xiàn)兩種狀況：一是惡意節(jié)點(diǎn)、二是網(wǎng)絡(luò)問題導(dǎo)師交易信息不全，各節(jié)點(diǎn)也將記錄此次Leader，如果再次連續(xù)出現(xiàn)問題記錄，下次Monitor 會(huì)考慮舍棄此節(jié)點(diǎn)。改進(jìn)后的算法可以作為私有鏈的共識(shí)算法，不僅保留了Raft 本身效率高的特點(diǎn)，而且具有防止惡意節(jié)點(diǎn)攻擊的情況出現(xiàn)。

2 改進(jìn)后算法流程

改進(jìn)算法中節(jié)點(diǎn)的四個(gè)角色：

Candidate：候選人，可以競(jìng)選Leader；

Follower：跟隨者，進(jìn)行Leader 選舉投票，校驗(yàn)Leader 打包區(qū)塊的結(jié)果；

Leader：領(lǐng)導(dǎo)者；

Monitor：監(jiān)視者，收集Leader 和Follow 計(jì)算結(jié)果的反饋，從而判斷問題節(jié)點(diǎn)進(jìn)行下一步操作。

每個(gè)節(jié)點(diǎn)都可以同時(shí)具有所有角色，不同的過程扮演不用角色。

（1）Candidate 節(jié)點(diǎn)將進(jìn)行競(jìng)選Leader，我們可以進(jìn)行一些策略避免所有Candidate 節(jié)點(diǎn)同時(shí)競(jìng)選，例如可以參考PoW 算法，產(chǎn)生一定隨機(jī)性。當(dāng)Candidate 收到其他Follower 的返回結(jié)果時(shí)，統(tǒng)計(jì)結(jié)果，如果票數(shù)過半，則說明選舉成功。此節(jié)點(diǎn)角色將由Candidate 變?yōu)長eader，具有此次的記賬權(quán)。

（2）Leader 節(jié)點(diǎn)將自己節(jié)點(diǎn)收到的交易信息進(jìn)行整理、計(jì)算、打包成一個(gè)區(qū)塊，將計(jì)算后的區(qū)塊信息廣播給其他的Follower 節(jié)點(diǎn)。

（3）所有Follower 收到節(jié)點(diǎn)后的將會(huì)根據(jù)自己節(jié)點(diǎn)收到的所有交易信息進(jìn)行整理、計(jì)算，并且與Leader廣播的結(jié)果進(jìn)行比較，然后將自己的結(jié)果廣播給其他的所有節(jié)點(diǎn)（包括Leader 節(jié)點(diǎn)）。

（4）每個(gè)節(jié)點(diǎn)會(huì)收到其他節(jié)點(diǎn)的所有結(jié)果，這個(gè)時(shí)候節(jié)點(diǎn)的角色將會(huì)兼顧著Monitor 的角色。節(jié)點(diǎn)會(huì)接收到其他所有節(jié)點(diǎn)的驗(yàn)證Leader 結(jié)果的反饋，會(huì)有以下兩種情況：

①如果各個(gè)節(jié)點(diǎn)收到Leader 計(jì)算結(jié)果正確的反饋超過半數(shù)，節(jié)點(diǎn)就可以將Leader 廣播的區(qū)塊進(jìn)行記錄上鏈，并且將記錄所有反饋節(jié)點(diǎn)錯(cuò)誤的節(jié)點(diǎn)，并且進(jìn)行監(jiān)管，如果連續(xù)出現(xiàn)問題，可能是網(wǎng)絡(luò)問題導(dǎo)致所接受的交易信息不夠完整，也有可能節(jié)點(diǎn)攻擊后進(jìn)行惡意操作，此時(shí)各個(gè)正常節(jié)點(diǎn)將行使Monitor 的權(quán)利，將此節(jié)點(diǎn)除名，保證安全性。

②如果各個(gè)節(jié)點(diǎn)收到的Leader 計(jì)算結(jié)果正確的反饋未能超過半數(shù)，各個(gè)節(jié)點(diǎn)就會(huì)重新進(jìn)入到步驟（1）進(jìn)行競(jìng)選Leader，同時(shí)記錄Leader 為待驗(yàn)證問題節(jié)點(diǎn)，而反饋Leader 結(jié)果正確的節(jié)點(diǎn)將會(huì)被各個(gè)節(jié)點(diǎn)直接舍棄，因?yàn)橐欢ㄊ潜还舻降膯栴}節(jié)點(diǎn)。

相比較原算法而言，本文提出的改進(jìn)方案多加了一個(gè)角色信息，與此角色相對(duì)應(yīng)的增加了校驗(yàn)Leader節(jié)點(diǎn)計(jì)算結(jié)果全部節(jié)點(diǎn)校驗(yàn)和出錯(cuò)節(jié)點(diǎn)記錄的過程，使得改進(jìn)后的算法具有的容錯(cuò)的功能。

3 對(duì)比實(shí)驗(yàn)

本文將使用改進(jìn)后Raft 算法作為共識(shí)算法的構(gòu)建私有鏈進(jìn)行攻擊，確認(rèn)改進(jìn)后私有鏈的安全性；并且對(duì)比改進(jìn)算法后構(gòu)建私有連的交易吞吐量狀況和傳統(tǒng)的公有鏈的交易吞吐量進(jìn)行對(duì)比，體現(xiàn)私有鏈的可用性。

（1）實(shí)驗(yàn)?zāi)M私有鏈共有五個(gè)節(jié)點(diǎn)，并且分別攻擊一個(gè)非Leader 節(jié)點(diǎn)、一個(gè)Leader 節(jié)點(diǎn)、攻擊兩個(gè)節(jié)點(diǎn)，查看私有鏈的運(yùn)行狀況：

①攻擊一個(gè)Follower 節(jié)點(diǎn)，其他節(jié)點(diǎn)會(huì)正常進(jìn)行記賬并且記錄此Follower 節(jié)點(diǎn)此次出錯(cuò)。

②攻擊Leader 節(jié)點(diǎn)，Leader 節(jié)點(diǎn)會(huì)發(fā)送錯(cuò)誤信息，其他節(jié)點(diǎn)會(huì)發(fā)現(xiàn)計(jì)算區(qū)塊信息錯(cuò)誤并且重新選舉Leader，并且將Leader 記錄此次出錯(cuò)。

③攻擊半數(shù)以上節(jié)點(diǎn)，如果Leader 節(jié)點(diǎn)發(fā)送錯(cuò)誤信息，其他節(jié)點(diǎn)也會(huì)進(jìn)行記賬加區(qū)塊；如果Leader 節(jié)點(diǎn)計(jì)算的區(qū)塊內(nèi)容是正確的，但是由于作惡節(jié)點(diǎn)占到半數(shù)，那么最后每個(gè)節(jié)點(diǎn)都會(huì)認(rèn)為Leader 計(jì)算結(jié)果出現(xiàn)問題，并且重新選舉節(jié)點(diǎn)，并且造成系統(tǒng)癱瘓。

（2）實(shí)驗(yàn)將計(jì)算區(qū)塊生成效率，然后與公有鏈的算法進(jìn)行比較：

經(jīng)過實(shí)驗(yàn)?zāi)M，本文提出基于改進(jìn)Raft 算法的私有鏈打包區(qū)塊的TPS 可以達(dá)到5000 左右，比起主流的區(qū)塊鏈的打包區(qū)塊速度有了質(zhì)的飛躍，如果進(jìn)行后期的足夠優(yōu)化，本文提出的方案將可以更加廣泛的應(yīng)用在各種領(lǐng)域。

4 結(jié)語

本文對(duì)Raft 進(jìn)行改進(jìn)并且將其應(yīng)用到私有鏈之中，既保留原來強(qiáng)一致性的高效，又可以防止惡意節(jié)點(diǎn)的攻擊，為很多私有鏈應(yīng)用落地提供更多可行性的方案。今后的工作將對(duì)Raft 算法進(jìn)行更多的容錯(cuò)方面的改進(jìn)，使其在復(fù)雜的網(wǎng)絡(luò)環(huán)境保證可用性得到提高，能夠有更強(qiáng)的生命活力；并且能夠改進(jìn)通信和負(fù)載均衡方面的結(jié)構(gòu)，讓私有鏈在通信的時(shí)候盡量減小網(wǎng)絡(luò)開銷，提高系統(tǒng)的穩(wěn)定性。