楊坤橋，王煜翔，郭 兵，李 強(qiáng)

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

自2008年中本聰[1]發(fā)布比特幣白皮書以來，區(qū)塊鏈技術(shù)的發(fā)展就受到了公眾廣泛的關(guān)注。因區(qū)塊鏈具備去中心化、不可篡改、數(shù)據(jù)透明、集體維護(hù)等特性，使得區(qū)塊鏈在許多領(lǐng)域具有廣泛的實(shí)用價(jià)值。區(qū)塊鏈已經(jīng)從最初單一的數(shù)字貨幣，逐漸應(yīng)用到了物流、版權(quán)保護(hù)、鑒證證明、金融[2]等多個(gè)領(lǐng)域。共識算法是構(gòu)建區(qū)塊鏈應(yīng)用的信任基礎(chǔ)[3]，它是為了解決獨(dú)立節(jié)點(diǎn)如何達(dá)成一致性的方案。當(dāng)下存在多種共識算法，例如，比特幣依賴于工作量證明（Proof of Work，PoW）算法，該算法主要思想是讓系統(tǒng)中的所有節(jié)點(diǎn)共同計(jì)算一道復(fù)雜的Hash難題[4]，其中最先計(jì)算出答案的節(jié)點(diǎn)會獲得系統(tǒng)的記賬權(quán)。PoW算法的主要缺點(diǎn)在于爭奪記賬權(quán)的過程中，大量節(jié)點(diǎn)參與而最終只有一個(gè)節(jié)點(diǎn)勝出，這就會造成大量能源的浪費(fèi)[5]。為了解決Pow算法存在的問題，King等人提出了一種權(quán)益證明（Proof of Stake，PoS）[6]的共識機(jī)制，該算法無需消耗大量算力就能保障系統(tǒng)的正常運(yùn)行。PoS算法首先提出了幣齡的概念，幣齡是指幣的數(shù)量與持有幣的時(shí)間的乘積。在PoS中各節(jié)點(diǎn)再也無需像PoW那些消耗大量算力來爭奪記賬權(quán)，而是由系統(tǒng)選擇擁有幣齡最高的節(jié)點(diǎn)獲得系統(tǒng)的記賬權(quán)。某種程度上這大大提高了系統(tǒng)的共識效率和系統(tǒng)吞吐量，但存在著大節(jié)點(diǎn)獲得記賬權(quán)的概率遠(yuǎn)遠(yuǎn)大于其他節(jié)點(diǎn)的概率，這就加劇系統(tǒng)的中心化趨勢[7]。為了解決PoS與Pow算法存在的缺點(diǎn)，委托股權(quán)證明算法（Delegated Proof of Stake，DPoS）[8]隨后被提出。在DPoS算法中不再需要統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的幣齡做排序操作，而是每個(gè)節(jié)點(diǎn)將它擁有的幣齡作為選票投給它自己信任的受托節(jié)點(diǎn)，由系統(tǒng)從這些受托節(jié)點(diǎn)中選擇排名靠前的節(jié)點(diǎn)輪流完成記賬，比特股（BitSHares）是第一個(gè)采用這種算法的區(qū)塊鏈。DPoS算法通過每輪投票選擇多個(gè)節(jié)點(diǎn)輪流記賬，大幅提高了系統(tǒng)的共識效率。但它也存在著一些問題：系統(tǒng)節(jié)點(diǎn)參與度不高，因?yàn)閰⑴c投票共識需要一些資源的消耗。其次由于依據(jù)幣齡作為選票，當(dāng)發(fā)現(xiàn)錯(cuò)誤節(jié)點(diǎn)時(shí)，不能快速地將它們剔除。還有DPoS算法在完成記賬發(fā)放激勵(lì)時(shí)只對那些受托節(jié)點(diǎn)發(fā)放，而不對那些投票節(jié)點(diǎn)激勵(lì)，長期來看會加劇系統(tǒng)的中心化趨勢。

本文針對DPoS算法存在節(jié)點(diǎn)投票積極性不高、錯(cuò)誤節(jié)點(diǎn)剔除不及時(shí)、節(jié)點(diǎn)收益分配不合理等問題做出了改進(jìn)，提出了一種改進(jìn)算法模型。首先對計(jì)票方式做出了改進(jìn)，提出了一種綜合計(jì)票的選舉方式，將幣齡、節(jié)點(diǎn)繳納的保證金、節(jié)點(diǎn)參與的歷史共識信息等多個(gè)維度的信息納入計(jì)票范圍，能夠更綜合性地評價(jià)選舉節(jié)點(diǎn)的情況。此外本文投票激勵(lì)機(jī)制和記賬激勵(lì)機(jī)制對算法激勵(lì)機(jī)制進(jìn)行改進(jìn)。因此本文貢獻(xiàn)如下：

（1）改進(jìn)原始算法的計(jì)票機(jī)制，將節(jié)點(diǎn)更多信息納入計(jì)票范疇，使得選票更全面地反映節(jié)點(diǎn)的信譽(yù)度，此外根據(jù)節(jié)點(diǎn)的投票記錄，動(dòng)態(tài)調(diào)整節(jié)點(diǎn)的權(quán)重，加快了錯(cuò)誤節(jié)點(diǎn)的剔除。

（2）改進(jìn)了算法的激勵(lì)機(jī)制，通過投票激勵(lì)和記賬激勵(lì)，對節(jié)點(diǎn)的收益進(jìn)行合理分配，有助于減小節(jié)點(diǎn)的中心化趨勢。

（3）通過實(shí)驗(yàn)驗(yàn)證了改進(jìn)方案的可行性。

1 相關(guān)研究

共識算法是保障區(qū)塊鏈系統(tǒng)穩(wěn)定運(yùn)行的核心技術(shù)，主要為了解決區(qū)塊鏈系統(tǒng)中各節(jié)點(diǎn)的一致性問題。近年隨著對區(qū)塊鏈技術(shù)的不斷深入，共識算法研究成為了區(qū)塊鏈研究的熱點(diǎn)問題。針對共識算法的改進(jìn)大致分為四個(gè)方面：（1）提高算法的共識效率。（2）加快錯(cuò)誤節(jié)點(diǎn)的剔除。（3）優(yōu)化節(jié)點(diǎn)激勵(lì)機(jī)制和收益分配方案。（4）提高共識算法安全性。

例如：在EOS項(xiàng)目中為了提高DPoS的共識效率，它將DPoS算法與拜占庭容錯(cuò)算法（Byzantine Fault Tolerance，BFT）進(jìn)行了結(jié)合[9]。在原始的DPoS算法中，區(qū)塊的確認(rèn)需輪到自己生成區(qū)塊時(shí)進(jìn)行集中確認(rèn)，而BFT算法的特點(diǎn)是生成區(qū)塊向全網(wǎng)廣播，各節(jié)點(diǎn)接收新區(qū)塊立即對區(qū)塊進(jìn)行驗(yàn)證。因此引入BFT算法加快了原始算法的確認(rèn)速度，提升了算法的效率。Eischer等人[10]首先將協(xié)議并行化為多個(gè)組，然后由各組按確定的順序處理相應(yīng)的請求。其次通過動(dòng)態(tài)調(diào)整需要在組之間排序的請求數(shù)量，能夠最大化地利用節(jié)點(diǎn)的服務(wù)資源，提高了算法的伸縮性和共識效率。

對于共識機(jī)制加快錯(cuò)誤節(jié)點(diǎn)的剔除，黃嘉成等人[11]提出了一種由選民節(jié)點(diǎn)投反對票來加快剔除速度的方案。該方案當(dāng)節(jié)點(diǎn)的反對票達(dá)到一定閾值后觸發(fā)系統(tǒng)熔斷，系統(tǒng)會將這些節(jié)點(diǎn)的信用降級。此外高迎等人[12]提出了在系統(tǒng)中設(shè)立審查節(jié)點(diǎn)與信用機(jī)制來解決這一問題，該方案下若在規(guī)定時(shí)間沒有產(chǎn)生有效區(qū)塊，則降低其信用系數(shù)。

針對優(yōu)化收益分配的研究，Eyal[13]提出可以將PoW共識機(jī)制中的挖礦行為看做一種博弈過程，并用博弈論的相關(guān)知識進(jìn)行了定性分析，但并未給出相應(yīng)的策略。隨后唐長兵等人[14]在這基礎(chǔ)之上對其進(jìn)行了拓展和進(jìn)一步分析。對于PoS算法的研究劉怡然等人[15]提出了計(jì)算參與共識節(jié)點(diǎn)的夏普利值來實(shí)現(xiàn)收益的二次分配，這一改進(jìn)能夠提高小節(jié)點(diǎn)獲得收益的概率。由于Banzhaf值更適合于衡量聯(lián)盟中的各成員權(quán)利大小[16]。為此本文的記賬激勵(lì)部分在這些前人研究的基礎(chǔ)之上利用Banzhaf值進(jìn)行了改進(jìn)。

針對安全性問題，Pungila等人[17]提出了一種利用異構(gòu)計(jì)算增強(qiáng)區(qū)塊鏈的事務(wù)處理和安全驗(yàn)證的模型，該模型減小了系統(tǒng)的復(fù)雜度并提高了系統(tǒng)的安全性。在文獻(xiàn)中為了提升系統(tǒng)的安全性，提出了一種安全協(xié)議，該協(xié)議在完成共識后，通過快速確認(rèn)來保障系統(tǒng)的安全運(yùn)行。Berrang等人[18]提出了一種基于事務(wù)強(qiáng)確認(rèn)的改進(jìn)模型，該模型在共識完成后通過及時(shí)確認(rèn)來保障系統(tǒng)的安全性和可靠性。

2 DPoS機(jī)制的改進(jìn)

本文主要改進(jìn)了原始共識算法的計(jì)票機(jī)制和激勵(lì)機(jī)制。原始的計(jì)票制度單一地統(tǒng)計(jì)受托人節(jié)點(diǎn)的幣齡作為選票依據(jù)，不能夠準(zhǔn)確地反應(yīng)節(jié)點(diǎn)的真實(shí)情況，而改進(jìn)的計(jì)票制度將更多的因素納入了計(jì)票范圍，能反映節(jié)點(diǎn)的更多信息。同時(shí)為了預(yù)防系統(tǒng)節(jié)點(diǎn)共謀破壞系統(tǒng)共識，可通過動(dòng)態(tài)調(diào)整這些參數(shù)來剔除錯(cuò)誤節(jié)點(diǎn)。此外針對當(dāng)前激勵(lì)機(jī)制只對受托節(jié)點(diǎn)進(jìn)行激勵(lì)對投票節(jié)點(diǎn)不激勵(lì)，在系統(tǒng)長時(shí)間運(yùn)行后易加劇系統(tǒng)中的“貧富差距”的問題，本文提出了兩種激勵(lì)方式來抑制這種情況的發(fā)生。具體方案如下。

2.1 綜合計(jì)票

計(jì)票機(jī)制的改進(jìn)是為了讓選票更具有公信力，同時(shí)加快對系統(tǒng)作惡節(jié)點(diǎn)的剔除。原始的DPoS算法將系統(tǒng)中的節(jié)點(diǎn)分為見證人節(jié)點(diǎn)和受托人節(jié)點(diǎn)，見證人節(jié)點(diǎn)負(fù)責(zé)投票給受托人，見證人節(jié)點(diǎn)的選票是其持有的幣齡。當(dāng)受托人節(jié)點(diǎn)的選票達(dá)到一定標(biāo)準(zhǔn)，這些受托人會被選為“董事會成員”負(fù)責(zé)生成區(qū)塊。因此受托人節(jié)點(diǎn)的選票數(shù)為投票給它的所有節(jié)點(diǎn)的見證人節(jié)點(diǎn)的幣齡之和，計(jì)算公式如下：

這種計(jì)票方式只對節(jié)點(diǎn)的幣齡進(jìn)行統(tǒng)計(jì)，意味著節(jié)點(diǎn)擁有的幣齡越多，那么就擁有更高的投票權(quán)。即使檢測到作惡節(jié)點(diǎn)的存在，由于節(jié)點(diǎn)的幣齡較高，它也擁有較高的投票權(quán)，因此無法對作惡節(jié)點(diǎn)快速地剔除。為此本文提出了一種改進(jìn)的方案，改進(jìn)方案不光對節(jié)點(diǎn)的幣齡進(jìn)行統(tǒng)計(jì)，在投票前還需繳納一定的保證金作為選票的背書，增加選票的可信度同時(shí)也增加了節(jié)點(diǎn)的作惡成本。此外還將記錄節(jié)點(diǎn)投票的共識信息納入統(tǒng)計(jì)，歷史共識信息包括節(jié)點(diǎn)參與成功的共識次數(shù)和失敗的次數(shù)，節(jié)點(diǎn)參與的正確共識越多說明節(jié)點(diǎn)本次的投票越可信。因此將投票節(jié)點(diǎn)的這些信息納入到綜合計(jì)票的統(tǒng)計(jì)范疇中，有利于提高節(jié)點(diǎn)選票的可信度。為此綜合投票的計(jì)算公式如下：

Ticket*為最后統(tǒng)計(jì)的得票數(shù)。其中ωi為需要統(tǒng)計(jì)各因素的權(quán)重，φi為各節(jié)點(diǎn)幣齡、保證金、共識記錄的值。將多種因素納入計(jì)票范疇，并分配不同的權(quán)重是為了降低選票對幣齡的單一因素依賴。權(quán)重系數(shù)的和等于1。在設(shè)置各權(quán)重大小時(shí)，首先為了避免文獻(xiàn)[19]所指出的部分節(jié)點(diǎn)通過共謀串票的方式來破壞選舉，因此在設(shè)置參數(shù)時(shí)不能過度依賴于單一權(quán)重，各個(gè)權(quán)重應(yīng)盡量保持均衡。其次通常系統(tǒng)中的大節(jié)點(diǎn)擁有更多的保證金，若保證金的權(quán)重設(shè)置過大不利于小節(jié)點(diǎn)成為受托節(jié)點(diǎn)。此外在DPoS機(jī)制中系統(tǒng)節(jié)點(diǎn)存在不積極參加共識的問題，因此將投票記錄的權(quán)重設(shè)置相對大有利于激勵(lì)節(jié)點(diǎn)積極參與共識。最后綜合考慮設(shè)置各權(quán)重為ωi=[0.4,0.2,0.4]。在參與共識的過程中，為了加快作惡節(jié)點(diǎn)的剔除，就需要能及時(shí)地降低這些節(jié)點(diǎn)的權(quán)重，但又要防止節(jié)點(diǎn)受這些失敗記錄的影響造成長期的投票權(quán)重過低。因此本文在統(tǒng)計(jì)歷史共識信息時(shí)設(shè)置為2次成功的共識記錄可以抵消一次失敗的共識記錄。當(dāng)正確共識次數(shù)小于錯(cuò)誤次數(shù)兩倍時(shí)，統(tǒng)計(jì)結(jié)果為負(fù)值且呈指數(shù)減小，大于兩倍時(shí)線性增長。通過動(dòng)態(tài)調(diào)整節(jié)點(diǎn)的權(quán)重，能夠快速降低作惡節(jié)點(diǎn)選票對整體投票結(jié)果的影響，也能鼓勵(lì)節(jié)點(diǎn)參加正確的共識來提高它的選票投票權(quán)重。為此公式如下：

其中能夠看出隨著節(jié)點(diǎn)參與的正確共識增加，其投票的權(quán)重也會相應(yīng)的增加。當(dāng)節(jié)點(diǎn)參與的錯(cuò)誤共識越多時(shí)，其投票權(quán)重呈指數(shù)級下降，這樣能快速地降低錯(cuò)誤節(jié)點(diǎn)的投票權(quán)重，從而將它們快速地剔除掉。為此投票算法的偽代碼如下所示：

原始的DPoS算法將系統(tǒng)中的節(jié)點(diǎn)分為受托節(jié)點(diǎn)和見證人節(jié)點(diǎn)，受托節(jié)點(diǎn)代表見證人節(jié)點(diǎn)參與共識。當(dāng)前存在部分節(jié)點(diǎn)不及時(shí)投票，以及惡意串聯(lián)投票等方式來破壞選舉。針對這些問題，文獻(xiàn)[11]提出一種信用機(jī)制來加快惡意節(jié)點(diǎn)的剔除，該方案為每個(gè)節(jié)點(diǎn)設(shè)置信用分?jǐn)?shù)和信用等級，信用總分為100分，每25分劃分為一個(gè)等級共4個(gè)等級。在一個(gè)投票周期內(nèi)根據(jù)各節(jié)點(diǎn)的投票情況調(diào)整節(jié)點(diǎn)的信用分?jǐn)?shù)，分?jǐn)?shù)下降至25分以下的節(jié)點(diǎn)不會參與后續(xù)的共識。文獻(xiàn)[12]對于上述問題提出了一種基于信任機(jī)制的投票模型，一個(gè)節(jié)點(diǎn)的信用值分為直接信任和間接信任。直接信任值是指與該能夠直接建立聯(lián)系的節(jié)點(diǎn)，該方案認(rèn)為這些節(jié)點(diǎn)的信譽(yù)值較高賦予了較高的信譽(yù)權(quán)重。間接信任值是指當(dāng)前節(jié)點(diǎn)通過直接節(jié)點(diǎn)作為中間人，能夠間接建立聯(lián)系的節(jié)點(diǎn)的信譽(yù)值。該方案認(rèn)為間接信任節(jié)點(diǎn)具有一定的信譽(yù)度，但存在著一定的風(fēng)險(xiǎn)，賦予這類節(jié)點(diǎn)相對較低的信譽(yù)權(quán)重。投票節(jié)點(diǎn)根據(jù)節(jié)點(diǎn)的直接信任值和間接信任值，加權(quán)得到節(jié)點(diǎn)的綜合信任值，投票節(jié)點(diǎn)根據(jù)節(jié)點(diǎn)的信用等級進(jìn)行投票。本文的改進(jìn)方案為了防止節(jié)點(diǎn)共謀串票的發(fā)生，增加節(jié)點(diǎn)的作惡成本，讓節(jié)點(diǎn)在投票時(shí)繳納一定的保證金作為擔(dān)保，越高的保證金增加了節(jié)點(diǎn)的作惡成本，因此節(jié)點(diǎn)的信譽(yù)度應(yīng)該越高。此外節(jié)點(diǎn)的共識記錄作為節(jié)點(diǎn)過去履約的記錄，可以看做節(jié)點(diǎn)信用的背書，將節(jié)點(diǎn)的共識記錄作為節(jié)點(diǎn)的信用評級也是合理的。

2.2 激勵(lì)機(jī)制改進(jìn)

針對原有算法投票節(jié)點(diǎn)積極性不高的問題，本文設(shè)計(jì)了兩種激勵(lì)機(jī)制：（1）投票激勵(lì)機(jī)制，用來激勵(lì)那些積極參與投票的節(jié)點(diǎn)。（2）記賬激勵(lì)機(jī)制，當(dāng)見證人節(jié)點(diǎn)完成記賬獲得激勵(lì)時(shí)，通過對記賬激勵(lì)再分配來減小系統(tǒng)中各節(jié)點(diǎn)的“貧富”差距。具體方案如下所示。

（1）投票激勵(lì)機(jī)制

為了激勵(lì)系統(tǒng)節(jié)點(diǎn)積極參與投票，因?qū)τ趨⑴c投票的所有節(jié)點(diǎn)都進(jìn)行激勵(lì)。節(jié)點(diǎn)的激勵(lì)收益由節(jié)點(diǎn)繳納的保證金，以及節(jié)點(diǎn)的歷史共識情況決定。投票激勵(lì)的計(jì)算如式（4）所示：表示所有節(jié)點(diǎn)繳納的

其中，ρ表示保證金的多少數(shù)目，Cs表示參與正確共識的次數(shù)，Ce表示錯(cuò)誤次數(shù)。從公式能夠看出節(jié)點(diǎn)繳納的保證金占比越多，節(jié)點(diǎn)的投票收益越高。這樣有利于鼓勵(lì)節(jié)點(diǎn)多繳納保證金，增加節(jié)點(diǎn)的作惡成本。其次也能看出，節(jié)點(diǎn)參與正常共識的次數(shù)越多也能夠增加其投票收益。針對投票激勵(lì)算法如下：

（2）記賬激勵(lì)機(jī)制

投票激勵(lì)一定程度上能夠解決系統(tǒng)節(jié)點(diǎn)積極性不高的問題，但在原始算法中還存在著分配機(jī)制不合理的問題。在原始算法中節(jié)點(diǎn)投票后選出受托節(jié)點(diǎn)代為完成記賬，系統(tǒng)會給予相應(yīng)激勵(lì)，這些激勵(lì)由受托節(jié)點(diǎn)獨(dú)享，由于這些受托節(jié)點(diǎn)的投票權(quán)通常較大，而這些激勵(lì)長期只分給這些節(jié)點(diǎn)就會拉大系統(tǒng)節(jié)點(diǎn)的“貧富差距”，加大系統(tǒng)的中心化。為了解決這一問題本文引入博弈論相關(guān)知識進(jìn)行解決。

博弈論是指研究多個(gè)決策主體之間行為具有相互作用時(shí)，各主體根據(jù)所掌握的信息作出有利于自己決策的理論。博弈的基本要素有行動(dòng)順序、局中人、效用、均衡。在DPoS共識算法中，每個(gè)投票節(jié)點(diǎn)視作局中人，投票獲得的收益可以看做為效用，每個(gè)節(jié)點(diǎn)采取的不同投票策略做為行動(dòng)順序，以上能夠看出整個(gè)共識過程符合博弈論的特征。此外投票節(jié)點(diǎn)將自己選票投給受托節(jié)點(diǎn)與其他節(jié)點(diǎn)競爭記賬權(quán)的行為可以看做是一種合作博弈[15]。為此本文根據(jù)合作博弈中的Banzhaf權(quán)利指數(shù)對記賬激勵(lì)進(jìn)行了再次分配。

Banzhaf權(quán)利指數(shù)是用來定量分析投票者在一次投票中的重要程度的指數(shù)，投票者在聯(lián)盟中越重要，其權(quán)利指數(shù)越大。在聯(lián)盟博弈中，若某個(gè)投票者在加入一個(gè)聯(lián)盟后能使原本沒有獲勝機(jī)率的聯(lián)盟獲勝，或它在退出聯(lián)盟后能使原本獲勝的聯(lián)盟無法取勝，那么這些聯(lián)盟可以看做這個(gè)投票者的有效聯(lián)盟[16]。對于每個(gè)投票者而言，其有效聯(lián)盟越多，它擁有的投票權(quán)也就越大。對于一個(gè)聯(lián)盟博弈(N,V)來說，若局中人投票權(quán)重可用向量β={β1,β2,…,βn}表示，權(quán)利指數(shù)計(jì)算公式[16]如下：

其中N={1,2,…,n}表示投票節(jié)點(diǎn)集合，V:2N→R為效用函數(shù)，并且K∈N，v(K)表示聯(lián)盟收益。其范圍為0到1，βi越接近1權(quán)利越大。每個(gè)投票節(jié)點(diǎn)的記賬激勵(lì)由各節(jié)點(diǎn)的權(quán)利指數(shù)確定。偽代碼如下所示：

在激勵(lì)方案中，節(jié)點(diǎn)的收益分為投票收益和記賬收益。對于投票激勵(lì)而言，節(jié)點(diǎn)取得的收益由節(jié)點(diǎn)的保證金占比和節(jié)點(diǎn)的共識記錄共同決定的。若假設(shè)系統(tǒng)中有a、b兩個(gè)節(jié)點(diǎn)，若二者的保證金占比都相同的情況下。節(jié)點(diǎn)若想取得更多的收益，就必須積極參與共識，積累更多次數(shù)的正確共識。對于記賬激勵(lì)而言，運(yùn)用博弈論知識來解決這類問題已經(jīng)成為一種必然方式[20]。如文獻(xiàn)[21]在對算法進(jìn)行改進(jìn)時(shí)建立了獎(jiǎng)勵(lì)機(jī)制，其機(jī)制應(yīng)用了沙普利值對節(jié)點(diǎn)取得的收益進(jìn)行二次分配。由于DPoS的選舉方式更接近于議會選舉，Banzhaf值更能體現(xiàn)個(gè)體理性的特征[16]。本文為此在改進(jìn)時(shí)采用了Banzhaf權(quán)利指數(shù)對節(jié)點(diǎn)的收益進(jìn)行二次分配，為了證明方案的有效性在第4章實(shí)驗(yàn)部分與文獻(xiàn)[21]進(jìn)行了比較實(shí)驗(yàn)，證明方案的有效性。

3 改進(jìn)后的共識流程

改進(jìn)后的DPoS算法大致流程如圖1所示，流程主要包含兩個(gè)階段：選舉階段、記賬同步階段。

圖1 共識算法流程圖Fig.1 Flow chart of consensus algorithm

3.1 選舉階段

在選舉階段中，系統(tǒng)中節(jié)點(diǎn)主要分為投票節(jié)點(diǎn)、候選節(jié)點(diǎn)和受托節(jié)點(diǎn)。投票節(jié)點(diǎn)將自己的選票投給候選節(jié)點(diǎn)，系統(tǒng)按得票數(shù)對其進(jìn)行排序，最后選出受托節(jié)點(diǎn)負(fù)責(zé)一輪記賬。大致過程如下：

（1）首先各節(jié)點(diǎn)向系統(tǒng)中廣播＜Init_Msg:msgid,clock,ticket,nodetype,secretkey＞初始化消息，消息內(nèi)容包含節(jié)點(diǎn)的id編號、時(shí)鐘信息、選票信息、節(jié)點(diǎn)的公鑰信息等，各節(jié)點(diǎn)將接收到的初始化消息緩存至本地，用于后續(xù)校驗(yàn)數(shù)據(jù)。

（2）在各節(jié)點(diǎn)的元數(shù)據(jù)完成同步后，投票節(jié)點(diǎn)開始發(fā)出投票消息＜Vote_Msg:msgid,voteid,receiverid,signature,ticket＞內(nèi)容包括消息編號、投票人id、受票節(jié)點(diǎn)id、消息簽名，以及節(jié)點(diǎn)的選票數(shù)。其中消息編號每次遞增，用于區(qū)分選票的輪次。為了加快共識速度，節(jié)點(diǎn)需在規(guī)定的時(shí)間內(nèi)完成投票，否則產(chǎn)生超時(shí)異常，認(rèn)定投票無效將罰沒節(jié)點(diǎn)的保證金。

（3）在節(jié)點(diǎn)在投票之后，還要對選票進(jìn)行校驗(yàn)。主要校驗(yàn)選票的簽名是否正確，以及選票的id是否大于等于本地緩存的id號。若選票無效也將罰沒節(jié)點(diǎn)的保證金，同時(shí)記錄節(jié)點(diǎn)的投票的失敗信息。有效則選出受托節(jié)點(diǎn)，將這些節(jié)點(diǎn)添加到一個(gè)隊(duì)列里面，這些節(jié)點(diǎn)將輪流完成下一輪區(qū)塊的生成。在成功選出受托節(jié)點(diǎn)后，對那些受托節(jié)點(diǎn)的投票節(jié)點(diǎn)發(fā)放投票激勵(lì)。

3.2 記賬同步階段

在這個(gè)階段，為了將受托節(jié)點(diǎn)的選舉次數(shù)控制在合理范圍，在受托列表的每個(gè)節(jié)點(diǎn)，都要生成五個(gè)區(qū)塊，才進(jìn)行新的一輪選舉。在節(jié)點(diǎn)生成區(qū)塊后，廣播區(qū)塊信息。其他節(jié)點(diǎn)接收到廣播消息，對區(qū)塊的簽名、區(qū)塊的高度等信息進(jìn)行校驗(yàn)。在數(shù)據(jù)同步過程中主要分有兩個(gè)過程，push階段和pull階段。push階段是當(dāng)前生成區(qū)塊的受托節(jié)點(diǎn)，在生成區(qū)塊后主動(dòng)地向其他節(jié)點(diǎn)發(fā)出同步信息的過程。pull階段是其他節(jié)點(diǎn)存放的數(shù)據(jù)可能滯后于最新數(shù)據(jù)時(shí)，主動(dòng)向其他節(jié)點(diǎn)拉取最新數(shù)據(jù)的過程。

（1）push階段：當(dāng)前的受托節(jié)點(diǎn)在生成區(qū)塊后，主動(dòng)廣播相應(yīng)信息，其中頭部包含這些信息＜Block_Msg:nodeid,previoushash,blockheight,blocktime,signature＞。各 個(gè)節(jié)點(diǎn)在接收到消息之后，驗(yàn)證生成區(qū)塊的節(jié)點(diǎn)id是否在受托節(jié)點(diǎn)列表中，區(qū)塊的時(shí)間戳是否小于當(dāng)前節(jié)點(diǎn)的本地時(shí)間，區(qū)塊頭中的blockheight必須大于當(dāng)前節(jié)點(diǎn)緩存的高度，此外還要對父節(jié)點(diǎn)的Hash值等信息進(jìn)行校驗(yàn)。若區(qū)塊校驗(yàn)正確則將區(qū)塊存放到本地，并廣播成功信息，發(fā)放記賬激勵(lì)。若校驗(yàn)失敗則廣播失敗消息，記錄到失敗日志，更新節(jié)點(diǎn)信息。

（2）pull階段：這個(gè)過程是節(jié)點(diǎn)才啟動(dòng)，或一些節(jié)點(diǎn)可能因某些原因在規(guī)定時(shí)間內(nèi)沒有收到來自受托節(jié)點(diǎn)push的區(qū)塊數(shù)據(jù)時(shí)，主動(dòng)向其他節(jié)點(diǎn)請求同步的過程。節(jié)點(diǎn)首先會發(fā)出請求同步消息＜Syn_Msg:synid,nodeid,blockheight,timestamp＞請求同步。其他節(jié)點(diǎn)在收到同步請求后，檢查自己本地緩存最大的blockheight是否大于請求的blockheight當(dāng)如果大于當(dāng)前節(jié)點(diǎn)的區(qū)塊鏈長度大于請求節(jié)點(diǎn)的長度，被請求節(jié)點(diǎn)則會把最新數(shù)據(jù)同步給請求節(jié)點(diǎn)，從而完成區(qū)塊數(shù)據(jù)的同步。

4 實(shí)驗(yàn)

為了驗(yàn)證改進(jìn)算法的有效性，本文共模擬了150個(gè)共識節(jié)點(diǎn)，通過實(shí)驗(yàn)從多個(gè)維度對原始算法和改進(jìn)算法進(jìn)行了比較。實(shí)驗(yàn)環(huán)境如表1所示。

表1 實(shí)驗(yàn)環(huán)境Table 1 Experimental environment

4.1 綜合計(jì)票驗(yàn)證

綜合計(jì)票機(jī)制主要是增加了節(jié)點(diǎn)選票的可信度，有利于降低錯(cuò)誤節(jié)點(diǎn)選票權(quán)重，進(jìn)而影響其成為見證人節(jié)點(diǎn)的概率。因此實(shí)驗(yàn)?zāi)康氖菫榱藱z驗(yàn)綜合計(jì)票機(jī)制在系統(tǒng)中存在30%的錯(cuò)誤節(jié)點(diǎn)時(shí)，經(jīng)過多輪共識能否將這些節(jié)點(diǎn)的權(quán)重盡量降低。實(shí)驗(yàn)條件如下：開始時(shí)各節(jié)點(diǎn)擁有相同的幣齡，在實(shí)驗(yàn)開始后逐漸使一部分節(jié)點(diǎn)參與無效投票或產(chǎn)生錯(cuò)誤區(qū)塊，通過這種方式來模擬系統(tǒng)中的作惡節(jié)點(diǎn)。在經(jīng)過多輪共識后，系統(tǒng)中的各節(jié)點(diǎn)的狀態(tài)會不盡相同，從而各投票節(jié)點(diǎn)的選票權(quán)重產(chǎn)生差異。如圖2所示為經(jīng)過50輪投票的結(jié)果。

圖2 正常節(jié)點(diǎn)的選票權(quán)重Fig.2 Vote weights for normal nodes

從圖2中能夠看出在實(shí)驗(yàn)輪數(shù)較少時(shí)，改進(jìn)算法和原始算法錯(cuò)誤節(jié)點(diǎn)的比例相差不大。當(dāng)實(shí)驗(yàn)進(jìn)行到20輪時(shí)改進(jìn)算法中的選票權(quán)重比例已經(jīng)保持較為穩(wěn)定，并與原始算法產(chǎn)生了較大差距。分析原因可知當(dāng)一些節(jié)點(diǎn)參與了錯(cuò)誤共識后，系統(tǒng)會記錄下它的共識記錄，改進(jìn)算法在計(jì)票時(shí)會根據(jù)這些記錄對這些節(jié)點(diǎn)的投票權(quán)重進(jìn)行調(diào)整，錯(cuò)誤節(jié)點(diǎn)的選票權(quán)重就被降低了。而原始算法由于只對節(jié)點(diǎn)的幣齡信息進(jìn)行統(tǒng)計(jì)，并不能很好地減小錯(cuò)誤節(jié)點(diǎn)的投票權(quán)重。因此能夠得出結(jié)論改進(jìn)的算法能夠加快系統(tǒng)對異常節(jié)點(diǎn)的篩選，降低異常節(jié)點(diǎn)成為受托節(jié)點(diǎn)的概率。

4.2 時(shí)延比較

共識算法的時(shí)延是指從開始投票到生成區(qū)塊的時(shí)間消耗。因此算法的時(shí)延能夠直接反應(yīng)出算法的真實(shí)性能，時(shí)間消耗越少，算法性能越高。本文在相同條件下進(jìn)行了50輪實(shí)驗(yàn)，得到了兩種算法的時(shí)延對比圖，如圖3所示。

圖3 兩種算法共識時(shí)間消耗對比Fig.3 Comparison time consumption of two algorithms

從圖3中能夠看出，隨著實(shí)驗(yàn)次數(shù)的增加，兩種算法的時(shí)間消耗都呈增長趨勢，但總體而言原始算法時(shí)間消耗的增長率高于改進(jìn)算法。因此隨著共識次數(shù)的增多，改進(jìn)算法的時(shí)間消耗的優(yōu)勢體現(xiàn)得越明顯。

4.3 節(jié)點(diǎn)參與度比較

原始算法存在投票節(jié)點(diǎn)積極性不高的問題，為了驗(yàn)證激勵(lì)機(jī)制能否增加系統(tǒng)節(jié)點(diǎn)的活躍度。本實(shí)驗(yàn)在各投票節(jié)點(diǎn)初始幣齡一致的情況下進(jìn)行了50輪共識，并統(tǒng)計(jì)了各輪次參與投票的節(jié)點(diǎn)的比例，實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 參與共識投票的節(jié)點(diǎn)比例Fig.4 Proportion diagram of number of voting nodes

從圖4中能夠看出，改進(jìn)算法相較于原始算法具有明顯的優(yōu)勢，原始算法在多輪共識后，節(jié)點(diǎn)的參與度接近于70%，改進(jìn)算法的節(jié)點(diǎn)活躍度接近于80%左右。分析原因可知改進(jìn)算法對參與投票的節(jié)點(diǎn)有相應(yīng)的投票激勵(lì)，在投票后它的委托節(jié)點(diǎn)成功完成共識后，會有相應(yīng)的記賬激勵(lì)。在兩種激勵(lì)機(jī)制的作用下改進(jìn)算法的節(jié)點(diǎn)參與度要顯著高于原始算法，說明兩種激勵(lì)機(jī)制能夠提高系統(tǒng)節(jié)點(diǎn)的參與度。

5 本文方案與其他方案的比較

對于DPoS共識算法的改進(jìn)研究，已經(jīng)有了很多相關(guān)研究。如文獻(xiàn)[12]針對節(jié)點(diǎn)的投票積極性不高和系統(tǒng)沒有快速對錯(cuò)誤節(jié)點(diǎn)進(jìn)行剔除等問題，提出通過建立節(jié)點(diǎn)的信任等級來加快錯(cuò)誤節(jié)點(diǎn)的剔除。文獻(xiàn)[20]提出了通過激勵(lì)機(jī)制來解決原始算法存在的問題，在投票時(shí)根據(jù)投票的次數(shù)以及耗時(shí)發(fā)放相應(yīng)激勵(lì)，其次利用舉報(bào)激勵(lì)來減小系統(tǒng)的串票發(fā)生。文獻(xiàn)[21]在改進(jìn)算法時(shí)，利用夏普利值對節(jié)點(diǎn)的收益進(jìn)行了二次分配。為了證明本文方案的有效性，進(jìn)行了如下的比較。

5.1 時(shí)間消耗比較

共識算法共識的時(shí)間耗時(shí)越少，共識的效率越高。本實(shí)驗(yàn)旨在對比本方案與文獻(xiàn)[12]提出的算法在完成50輪共識后的時(shí)間消耗情況。對比實(shí)驗(yàn)的數(shù)據(jù)來自于文獻(xiàn)[12]中所給出的實(shí)驗(yàn)數(shù)據(jù)。對比結(jié)果如圖5所示。

圖5 本文方案與文獻(xiàn)方案耗時(shí)比較Fig.5 Time consumption between two schemes

從圖中可以看出文獻(xiàn)[12]的時(shí)間消耗呈線性增長，每輪時(shí)間消耗相對穩(wěn)定。但本文的方案時(shí)間消耗雖略有波動(dòng)，穩(wěn)定性不及文獻(xiàn)[12]的方案，但進(jìn)行50輪實(shí)驗(yàn)的總體耗時(shí)要好于文獻(xiàn)[12]所提出的方法。

5.2 參與投票節(jié)點(diǎn)的比較

為了比較本方案與文獻(xiàn)[20]所提方案在投票節(jié)點(diǎn)參與度方面的表現(xiàn)。本實(shí)驗(yàn)環(huán)境設(shè)置了和文獻(xiàn)[20]相同的實(shí)驗(yàn)條件，即仿真100個(gè)節(jié)點(diǎn)參與投票共識，并進(jìn)行了20組實(shí)驗(yàn)。本實(shí)驗(yàn)的對比數(shù)據(jù)來自于文獻(xiàn)[20]中所提供的在其投票激勵(lì)生效時(shí)的數(shù)據(jù)，對比結(jié)果如圖6所示。

圖6 兩種方案參與共識投票的節(jié)點(diǎn)比例Fig.6 Node ratio of consensus voting in two schemes

從圖中能夠看出文獻(xiàn)[20]提出的投票激勵(lì)改進(jìn)方案的投票節(jié)點(diǎn)數(shù)維持在65%～70%。而本文提出的方案參與投票的節(jié)點(diǎn)總體上要高0.1左右。因此本文所提的方案在節(jié)點(diǎn)投票比例方面優(yōu)于文獻(xiàn)[20]所給方案。

5.3 節(jié)點(diǎn)的收益分配方式比較

為了驗(yàn)證本文改進(jìn)方案在收益分配方面的有效性，本實(shí)驗(yàn)與文獻(xiàn)[21]進(jìn)行了對比。當(dāng)系統(tǒng)中節(jié)點(diǎn)情況和文獻(xiàn)[21]保持一致的情況下，增加系統(tǒng)中的節(jié)點(diǎn)數(shù)目，進(jìn)行多輪共識，觀察節(jié)點(diǎn)的收益變化。隨著節(jié)點(diǎn)數(shù)目的增多，最后收益的分布占比如圖7所示。

圖7 兩種方案收益對比Fig.7 Comparison of benefits between two schemes

從圖7中可以看出，在條件相同的情況下。雖然本文方案收益分配方式的最終效果比文獻(xiàn)[21]略差，但隨著節(jié)點(diǎn)數(shù)目的增多，二者的收益都呈現(xiàn)下降的趨勢，總體上與文獻(xiàn)[21]呈現(xiàn)趨勢大致相同，能夠說明本文的激勵(lì)方案具有有效性。

6 結(jié)束語

本文針對現(xiàn)有的DPoS算法存在著錯(cuò)誤節(jié)點(diǎn)剔除不及時(shí)和收益分配不合理等問題進(jìn)行了研究，并對算法的計(jì)票機(jī)制和激勵(lì)機(jī)制進(jìn)行了改進(jìn)。改進(jìn)后的計(jì)票機(jī)制將節(jié)點(diǎn)的更多維信息納入了計(jì)票范疇，使得選票能更準(zhǔn)確地反映出節(jié)點(diǎn)的真實(shí)信譽(yù)度，這有助于加快錯(cuò)誤節(jié)點(diǎn)的剔除。激勵(lì)機(jī)制的改進(jìn)分為投票激勵(lì)和記賬激勵(lì)兩個(gè)部分。投票激勵(lì)會對參與投票的所有節(jié)點(diǎn)進(jìn)行激勵(lì)，記賬激勵(lì)對完成記賬的聯(lián)盟，根據(jù)博弈論中的權(quán)利指數(shù)對記賬收益進(jìn)行二次分配，讓節(jié)點(diǎn)之間的收益更為均衡。未來的工作會對算法的吞吐量、安全性等方面進(jìn)行研究，進(jìn)一步提升算法的性能，為區(qū)塊鏈技術(shù)的發(fā)展做出自己的貢獻(xiàn)。