基于實用拜占庭容錯算法的區(qū)塊鏈電子計票方案

李 靖，景 旭，楊會君

（西北農(nóng)林科技大學(xué)信息工程學(xué)院，陜西楊凌712100）（?通信作者電子郵箱jingxu@nwsuaf.edu.cn）

0 引言

投票與我們?nèi)粘Ｉ钕⑾⑾嚓P(guān)，大到國家選舉、大政方針的制定，小到企業(yè)經(jīng)營、日常社會問題的調(diào)查等，均離不開投票。電子投票是伴隨著通信和網(wǎng)絡(luò)技術(shù)的發(fā)展而誕生的全新投票模式，相較于傳統(tǒng)投票方式，電子投票具有高效率、低成本、易操作等特點，在現(xiàn)代社會中發(fā)揮著越來越重要的作用。

但是，在現(xiàn)有一般網(wǎng)絡(luò)化電子投票中，投票信息通常被網(wǎng)絡(luò)傳送到一個假設(shè)安全的中心機(jī)構(gòu)，由其負(fù)責(zé)收集選票和統(tǒng)計結(jié)果，所以很有可能在計票過程中存在投票信息被惡意更改、填塞或遺漏的情況。區(qū)塊鏈?zhǔn)且环N去中心化、防篡改、可追溯、多方共同維護(hù)的分布式數(shù)據(jù)庫，改變了傳統(tǒng)數(shù)據(jù)庫管理系統(tǒng)的單一維護(hù)模式，解決了分布式環(huán)境中多方參與者對交易和狀態(tài)的信任問題［1］。目前區(qū)塊鏈技術(shù)已經(jīng)逐漸被應(yīng)用到電子投票領(lǐng)域中:Zhao 等［2］是第一個提出將區(qū)塊鏈技術(shù)應(yīng)用到投票領(lǐng)域中并得以實現(xiàn)的研究人員，在其方案中通過引入獎勵/懲罰機(jī)制約束區(qū)塊鏈中的投票者行為；但是該方案僅考慮了一般可行性，忽視了投票應(yīng)用應(yīng)有的安全性和隱私性。Lee 等［3-4］為解決在分布式環(huán)境中準(zhǔn)確計票的問題，提出在區(qū)塊鏈中引入一個可信計票機(jī)構(gòu)保護(hù)投票者的投票權(quán)力并確保選票得以正確統(tǒng)計；但是區(qū)塊鏈作為去中心化、去信任的應(yīng)用，引入可信計票機(jī)構(gòu)會打破其固有特性，而且由于在實際應(yīng)用中并沒有完全可信的第三方，因此基于任何第三方充當(dāng)計票機(jī)構(gòu)均存在一定的安全隱患。Somnath 等［5］提出將區(qū)塊鏈作為公告板公開存儲投票信息，以此滿足DRE（Direct-Recording Electronic）系統(tǒng)能夠在被不安全訪問的情況下實現(xiàn)端到端可驗證的電子投票方案；但是該方案同樣基于公告板的假設(shè)安全性，無法應(yīng)對公告板作弊或失效時對投票結(jié)果的保障。顏春輝［6］利用分布式ELGamal 加密體制和零知識證明協(xié)議提出一種基于全同態(tài)加密且無需第三方計票的多候選人投票方式；但是該方案存在同態(tài)加密算法復(fù)雜不利于合約的編寫以及投票過程中單一選票驗證性不強的問題。由此可見，在目前基于區(qū)塊鏈技術(shù)實現(xiàn)的電子投票方案中，大多依靠假設(shè)存在的第三方可信計票機(jī)構(gòu)或安全的公告板負(fù)責(zé)選票收集和計票。然而在區(qū)塊鏈環(huán)境中，并沒有所有節(jié)點都同時信任的第三方，因此，如何在區(qū)塊鏈中完成選票結(jié)果的可信統(tǒng)計對基于區(qū)塊鏈環(huán)境設(shè)計電子投票方案至關(guān)重要。

區(qū)塊鏈作為對等（Peer-to-Peer，P2P）網(wǎng)絡(luò)應(yīng)用，在其投票過程中可以保證選票信息的真實性、不可篡改性。而在惡意模型中，惡意節(jié)點可能有意給出錯誤的計票結(jié)果。為了保證區(qū)塊鏈中計票的準(zhǔn)確，共識機(jī)制是一個比較好的解決方案。共識機(jī)制是解決分布式環(huán)境中數(shù)據(jù)一致性的算法，也是區(qū)塊鏈中維持賬本一致的重要組成技術(shù)。目前，區(qū)塊鏈中的共識機(jī)制［7］主要分為兩類:1）應(yīng)用在公有鏈中以工作量證明（Proof of Work，PoW）機(jī)制和權(quán)益證明（Proof of Stake，PoS）機(jī)制為代表的最終一致性共識；2）應(yīng)用在聯(lián)盟鏈中以實用拜占庭容錯（Practical Byzantine Fault Tolerance，PBFT）算法為代表的強一致性共識。PoW 和PoS 通過節(jié)點算力或相應(yīng)權(quán)益競爭區(qū)塊的記賬權(quán)，雖然采用激勵政策鼓勵礦工準(zhǔn)確記錄交易，但是會在競爭記賬權(quán)時造成資源的大量浪費，降低共識效率。PBFT則是通過對節(jié)點的劃分綜合考慮拜占庭故障、提高共識達(dá)成效率的共識算法，因此PBFT在面向?qū)嶋H應(yīng)用中更有實效性。

PBFT本質(zhì)上是一種基于狀態(tài)機(jī)副本復(fù)制的算法，通過每個狀態(tài)副本保持相同的服務(wù)狀態(tài)，實現(xiàn)客戶的合法請求。在系統(tǒng)存在不多于(N - 1)/3 數(shù)量的拜占庭故障節(jié)點的情況下（N 是節(jié)點總數(shù)），仍然可以維持系統(tǒng)整體的穩(wěn)定性，正確達(dá)成分布式共識。為了實現(xiàn)區(qū)塊鏈電子投票中節(jié)點對計票結(jié)果的正確響應(yīng)，門限簽名是一個比較有效的技術(shù)。門限簽名是一種特殊的數(shù)字簽名，指合法的簽名必須由系統(tǒng)多個簽名者共同簽署，即只有簽名的參與人員大于或等于規(guī)定的門限值時才可以生成合法簽名，一方面實現(xiàn)對消息的多重保護(hù)，另一方面滿足不同層級或數(shù)量構(gòu)成的集合訪問，提高數(shù)據(jù)的可讀性。

因此，針對現(xiàn)有區(qū)塊鏈電子投票研究中存在的問題，本文主要做了以下工作:

1）提出一種基于實用拜占庭容錯協(xié)議的區(qū)塊鏈電子計票方案，實現(xiàn)無可信計票中心的計票過程，消除計票組織對統(tǒng)計結(jié)果的絕對控制；

2）引入門限簽名保障本文方案計票過程的正確性，綜合考慮分布式因素和確保結(jié)果的高可信度，以PBFT中對誠實節(jié)點的最低要求作為合法門限簽名的閾值；

3）區(qū)別于傳統(tǒng)PBFT 中主、從節(jié)點的確定方式，引入信任度的衡量機(jī)制，規(guī)范計票節(jié)點行為，提高共識效率。

1 相關(guān)技術(shù)

1.1 區(qū)塊鏈電子投票

一個完整的電子投票方案包括制票、投票、驗票、計票等基本過程。制票是對不同投票環(huán)境中選票內(nèi)容及格式的指定，可以根據(jù)不同的要求設(shè)計選票形式。投票是在規(guī)定時間內(nèi)完成選票提交。驗票是對選票合法性的檢驗，主要是驗證投票者身份。在驗票過程為解決可能泄露投票者隱私的問題，可以采用盲簽名［4，8-9］等技術(shù)保護(hù)投票者隱私。計票是對所有選票結(jié)果的統(tǒng)計，多數(shù)投票方案［3-5］均由計票機(jī)構(gòu)負(fù)責(zé)選票統(tǒng)計。由此可見，一個良好的計票方案首先應(yīng)該保證收集到的選票都是可以通過驗證的合法選票，只有確保選票來源，才可能得到正確的計票結(jié)果。在基于盲簽名的電子投票方案中，典型合法選票構(gòu)造過程［10］如下:

1）投票者挑選隨機(jī)數(shù)ki作為比特承諾密鑰，用位承諾方案f 加密選票mi，計算加密信息fmi=f（mi，ki），然后隨機(jī)選擇盲因子ri盲化fmi得到消息Mi，如式（1）所示。其中（e，n）是組織者公鑰信息，之后將該消息連同投票者身份標(biāo)識發(fā)送給投票組織，等待簽名。

2）投票組織驗證簽名確認(rèn)是投票者發(fā)送的消息，并對消息Mi進(jìn)行盲簽名，如式（2）所示，其中d是組織者私鑰信息；然后將Di作為投票授權(quán)證書頒發(fā)給投票者。

3）若簽名有效，投票者對盲簽名脫盲，得到基于消息mi的簽名σi，如式（3）所示；然后將消息/簽名信息發(fā)送給計票機(jī)構(gòu)用于無記名投票。

1.2 實用拜占庭容錯算法

1999 年，Castro 等［11］基于拜占庭容錯（Byzantine Fault Tolerance，BFT）算法［12］提出了PBFT 算法，首次將算法復(fù)雜度從指數(shù)級降為多項式級，使得方案在實際系統(tǒng)中變得可行。在區(qū)塊鏈技術(shù)和比特幣出現(xiàn)后，為解決PoW 等需要消耗巨大算力競爭記賬權(quán)的問題，PBFT開始被應(yīng)用在區(qū)塊鏈中作為新的共識機(jī)制。在基于PBFT算法的區(qū)塊鏈中，為保證數(shù)據(jù)在分布式環(huán)境中快速達(dá)成共識，包含三部分:

1）一致性協(xié)議，是共識算法的基礎(chǔ)協(xié)議。網(wǎng)絡(luò)對參與的節(jié)點進(jìn)行主、從節(jié)點劃分，各節(jié)點按序輪流充當(dāng)主節(jié)點。主節(jié)點負(fù)責(zé)率先對交易請求的響應(yīng)和廣播，從節(jié)點負(fù)責(zé)對主節(jié)點廣播的交易進(jìn)行確認(rèn)和再次廣播。主、從節(jié)點的劃分方式節(jié)省了競爭記賬權(quán)時所浪費的資源，能有效避免分叉的產(chǎn)生，顯著縮短達(dá)成共識的時間。

2）視圖更換協(xié)議，是共識算法處理主節(jié)點故障的協(xié)議。當(dāng)主節(jié)點長時間未響應(yīng)客戶端請求或響應(yīng)結(jié)果出現(xiàn)錯誤，此時需要啟動視圖更換協(xié)議變更主節(jié)點。該協(xié)議可以保障網(wǎng)絡(luò)運行暢通，確保不會因為單一主節(jié)點的故障影響整個網(wǎng)絡(luò)。

3）檢查點協(xié)議，是共識算法中關(guān)于刪除歷史共識日志的協(xié)議，起到清理系統(tǒng)內(nèi)存、降低數(shù)據(jù)冗余的作用。

1.3 門限簽名

本文選擇文獻(xiàn)［13］中設(shè)計的無中心化門限簽名方案作為驗票節(jié)點對結(jié)果的簽名方式，該方案利用聯(lián)合秘密共享技術(shù)改進(jìn)了前人方案，避免了泄露簽名者私鑰，防止惡意簽名者聯(lián)合偽造其他簽名者簽名的問題，提高了每個部分簽名的安全性。其構(gòu)造方法［14］如下:

1）密鑰生成中心（Key Generation Center，KGC）選取兩個安全的大素數(shù)p和q，滿足q|p - 1，同時在GF（q）上選取一個q階生成元素g，公開p、q、g。

2）KGC 從［1，q - 1］選取整數(shù)X，并分為a 個不同的子份額，即X = x1+ x2+ …+ xa，將xi發(fā)給每個簽名者Si，對于每一個支持的不同級別訪問的結(jié)構(gòu)Гi（i=1，2，…，a），KGC 分別計算GΓi，如式（4）所示，同時公開所有的GΓi。

2 本文方案整體思路

針對區(qū)塊鏈電子投票中，基于第三方可信計票機(jī)構(gòu)計票不能滿足區(qū)塊鏈去中心化、去信任特性及無法保障可信計票機(jī)構(gòu)“可信”的問題，本文提出一種基于PBFT的區(qū)塊鏈電子計票方案，實現(xiàn)區(qū)塊鏈中的可信計票。在該方案中，首先需要滿足區(qū)塊鏈去中心化、去信任模式，因此，本文的計票過程不再由可信計票機(jī)構(gòu)負(fù)責(zé)，而是選擇由投票者節(jié)點負(fù)責(zé)。但是如果讓區(qū)塊鏈中所有節(jié)點同時計票，又會增加網(wǎng)絡(luò)的計算開銷，造成資源的浪費并且導(dǎo)致結(jié)果難以統(tǒng)一，因此需要固定節(jié)點負(fù)責(zé)選票收集。PBFT 中將所有節(jié)點劃分為主、從節(jié)點，然而對主節(jié)點的選取方式較為隨意，而且某一節(jié)點在被選作主節(jié)點后沒有對其進(jìn)行真?zhèn)涡则炞C，因此使得可能挑選出來的節(jié)點是拜占庭故障節(jié)點。對此，本文根據(jù)PBFT 的基本流程，結(jié)合區(qū)塊鏈電子計票過程，引入對節(jié)點信任度的衡量。在計票階段中，將投票者節(jié)點分為計票節(jié)點和驗票節(jié)點，規(guī)定由信任值最高的節(jié)點充當(dāng)計票節(jié)點，其他節(jié)點均為驗票節(jié)點:其中，計票節(jié)點負(fù)責(zé)收集所有投票節(jié)點發(fā)送的合法選票，匯總選票信息得到待驗計票結(jié)果，并對所有選票和待驗計票結(jié)果簽名，形成待驗選舉結(jié)果，然后發(fā)布到投票區(qū)塊鏈；驗票節(jié)點在計票節(jié)點公布待驗選票結(jié)果后，驗證統(tǒng)計情況，并根據(jù)驗證結(jié)果對待驗選票結(jié)果進(jìn)行部分簽名或表示拒絕。如此確定計票節(jié)點的選取方式，可以更快、更真實得到正確的待驗選票結(jié)果，有效減少更換視圖協(xié)議產(chǎn)生的次數(shù)。

另一方面，為防止計票節(jié)點成為“偽中心”，本文采用驗票簽名的形式確保待驗選票結(jié)果的正確性，使得選票結(jié)果只有在經(jīng)過多數(shù)節(jié)點認(rèn)可時才可以最終公布，單一計票節(jié)點的信任度并不能代表結(jié)果的可信。理想情況下，投票區(qū)塊鏈中所有參與節(jié)點都可以對待驗選票結(jié)果進(jìn)行驗證簽名，則最終公布的選票結(jié)果可以徹底杜絕選票由計票節(jié)點計票時可能產(chǎn)生的選票填塞或遺漏問題。但是，區(qū)塊鏈作為分布式環(huán)境，且無法要求所有驗票節(jié)點在有效時間內(nèi)參與對待驗選票結(jié)果的驗證，因此，在確定合法部分簽名的量化指標(biāo)中，本文將PBFT中對誠實節(jié)點要求的最少數(shù)量作為門限簽名的閾值基礎(chǔ)，即只有至少得到（2n+1）/3 的部分簽名時，系統(tǒng)才可以生成有效的門限簽名，確保最終選票結(jié)果的可信。這樣不僅可以提升方案的可行性，提高門限簽名生成的概率，而且能夠監(jiān)督計票節(jié)點的統(tǒng)計行為和保證待驗選票結(jié)果可以受到多數(shù)驗票節(jié)點的驗證；同時，方案允許超過門限的驗票簽名，最終選票結(jié)果可以根據(jù)具體的簽名人數(shù)得到最低的可信任度，保障對最終選票結(jié)果的高信任共識。

本文旨在解決投票方案中計票環(huán)節(jié)的可信任處理，因此在計票階段前假定系統(tǒng)收到的選票均是滿足1.1 節(jié)中合法選票的構(gòu)造方案，充分確保選票來源的合法性，即投票者構(gòu)成的集合｛V1，V2，…，Vn｝經(jīng)過投票組織機(jī)構(gòu)（Org）完成對身份合法性的檢查，分別得到基于投票消息｛m1，m2，…，mn｝的盲簽名｛σ1，σ2，…，σn｝，形成可以用于投票的消息/簽名元組（mi，σi）。當(dāng)系統(tǒng)發(fā)布投票階段開始后，各投票節(jié)點開始將各自的元組信息（mi，σi）發(fā)送到投票區(qū)塊鏈中，開始投票。本文方案計票整體流程如圖1所示。

3 本文方案設(shè)計

3.1 計票節(jié)點選取

根據(jù)投票區(qū)塊鏈中節(jié)點的信任度高低確定計票節(jié)點，信任度越高的節(jié)點表明該節(jié)點的歷史行為越誠實，越適合負(fù)責(zé)統(tǒng)計選票任務(wù)。本文對所有參與投票的投票者節(jié)點記為Nodei，并統(tǒng)一賦予相同的初始化信任度T0，此后根據(jù)該節(jié)點在投票以及驗票階段的表現(xiàn)動態(tài)更新其最新信任值。節(jié)點更新信任度方式如式（11）所示:

其中:Tij表示第i個節(jié)點的第j次信任值；Ti(j-1)表示第i個節(jié)點的第j - 1次信任值，即該節(jié)點的前次信任值；ε代表在前次選舉中對于該節(jié)點行為表現(xiàn)的獎勵或懲罰。若節(jié)點行為良好，具體表現(xiàn)為每次參與投票、積極驗證選票并針對待驗選票結(jié)果作出正確的響應(yīng)，此時ε 為正值，不斷提高其基礎(chǔ)信任度；若節(jié)點行為較差，具體表現(xiàn)為缺席投票、不驗證選票或響應(yīng)結(jié)果與真實結(jié)果相悖、存在惡意搗亂，此時ε 為負(fù)值，顯著降低該節(jié)點的信任度。對于改變量ε 可以根據(jù)具體業(yè)務(wù)的需求和選舉本身的要求動態(tài)決定。在投票開始前，根據(jù)投票區(qū)塊鏈中所有節(jié)點的信任度劃分為最可信節(jié)點、普通節(jié)點和不可信節(jié)點，如圖2 所示。其中，最可信節(jié)點即為鏈上信任度最高的節(jié)點，也就是負(fù)責(zé)收集選票、統(tǒng)計結(jié)果的計票節(jié)點，網(wǎng)絡(luò)中只有一個節(jié)點是最可信節(jié)點，在普通節(jié)點中產(chǎn)生；不可信節(jié)點包括信任度低于某個固定限值的節(jié)點和作弊被發(fā)現(xiàn)的計票節(jié)點，投票區(qū)塊鏈中可以有多個不可信節(jié)點；其余節(jié)點則屬于普通節(jié)點，普通節(jié)點和不可信節(jié)點均為驗票節(jié)點。

從節(jié)點的信任值變化不難看出，對于每次投票都能積極作出正確響應(yīng)的節(jié)點會不斷提升該節(jié)點的信任度，也就是說，某一節(jié)點的信任度越高說明該節(jié)點在歷史投票、計票、驗票過程中都能夠誠實地響應(yīng)各階段結(jié)果，偏向于相對可靠的節(jié)點，因此由這樣的節(jié)點負(fù)責(zé)計票會較大程度上更好地完成計票任務(wù)。

圖1 計票方案整體流程Fig.1 Overall flowchart of counting scheme

圖2 各節(jié)點信任值的變化Fig.2 Change of credibility of each node

3.2 計票節(jié)點統(tǒng)計選舉結(jié)果

假定Nodec為當(dāng)前選舉中信任度最高的節(jié)點，于是該節(jié)點即被暫定為此次收集選舉信息、統(tǒng)計選票結(jié)果的計票節(jié)點。當(dāng)投票階段開始后，所有合法投票者節(jié)點Nodei（包括計票節(jié)點Nodec）向投票區(qū)塊鏈中匿名發(fā)送自己的選票信息，即消息/簽名對（mi，σi），并且每張選票中應(yīng)明確此次選舉的主題和節(jié)點發(fā)送選票的時間:其中寫明主題是防止選票信息收集錯誤，保證投票內(nèi)容和主題息息相關(guān)；標(biāo)記節(jié)點發(fā)送時間是為選票提供時間證明，解決選票在規(guī)定時間內(nèi)沒有被統(tǒng)計時引發(fā)的爭議問題。選票具體格式和包含內(nèi)容如圖3所示。

圖3 合法選票結(jié)構(gòu)Fig.3 Legal ballot structure

計票節(jié)點Nodec收集選票信息，形成待驗選票結(jié)果的過程如下:

1）收集發(fā)送到投票區(qū)塊鏈中符合投票主題的選票，在收集過程中也可以繼續(xù)驗證投票者身份是否合法、其盲簽名信息是否正確，再度確保選票來源的合法性。

2）將規(guī)定投票時間T1內(nèi)收集的所有合法選票匯總形成表單Listpre，并且根據(jù)Listpre計算投票結(jié)果，得到待驗計票結(jié)果Voteresult。

3）將Listpre和Voteresult以及其他相關(guān)信息一起加密打包形成待驗選票結(jié)果（WVR），如式（12）所示:

其中:csk 為計票節(jié)點的私鑰；ENC 為加密算法保證消息的隱私。

4）對待驗選票結(jié)果添加時間戳證明TS，防止惡意投票節(jié)點在T1后發(fā)送選票信息不被接納而產(chǎn)生對計票節(jié)點的爭議。并對待驗選票結(jié)果和時間戳證明進(jìn)行哈希運算的結(jié)果簽名，如式（13）所示:

其中:Sig為簽名算法保證消息的完整性，確保各節(jié)點如實、平等獲取計票節(jié)點計算的結(jié)果。

5）Nodec將WVR 和C 發(fā)送到投票區(qū)塊鏈中，等待各驗票節(jié)點對計票節(jié)點統(tǒng)計結(jié)果的驗證。

3.3 驗票節(jié)點檢驗待驗選舉結(jié)果

計票節(jié)點Nodec在投票區(qū)塊鏈公布待驗選票結(jié)果后，各驗票節(jié)點首先用計票節(jié)點的公鑰cpk驗證簽名信息C是否正確，若驗證成功，則表示消息完整，確實由計票節(jié)點發(fā)布并且沒有受到惡意節(jié)點對待驗選票結(jié)果的篡改，然后再解密打開密文消息，獲取相關(guān)信息。解密方式如式（14）所示:

驗票節(jié)點得到計票節(jié)點公布的待驗選票結(jié)果后，開始驗證其統(tǒng)計信息是否正確。具體驗證流程如下:

1）首先檢查表單Listpre中是否包含自己的投票/簽名信息元組（mi，σi），若包含自己的選票則繼續(xù)下一步驗證；否則發(fā)出拒絕信號，請求“re-counting”。

2）由于區(qū)塊鏈屬于分布式環(huán)境，各節(jié)點地位相等，任何節(jié)點可以獲取其他節(jié)點發(fā)送到投票區(qū)塊鏈中的選票，所以驗票節(jié)點在投票階段可以自主獲取其他選票。因此，自主收集選票信息的驗票節(jié)點可以驗證計票節(jié)點選票收集是否完備。若選票收集完備，則繼續(xù)驗證；否則同樣發(fā)出拒絕信號，請求“re-counting”。

3）然后根據(jù)當(dāng)前表單Listpre中包含的所有合法投票信息，獨立計算其待驗計票結(jié)果Voteresult是否正確。若計算有誤，則發(fā)出拒絕信號，請求“re-counting”；反之則說明計票節(jié)點計算待驗選票結(jié)果正確，驗票節(jié)點可以對其進(jìn)行部分簽名。簽名過程如下:

①KGC 選取兩個安全的大素數(shù)p 和q，滿足q|p - 1，在GF(q)上選取一個q 階生成元素g，公開p、q、g；同時確定秘密值X，并分解為X = x1+ x2+ …+ xn，然后將每一個xi發(fā)送給驗票節(jié)點Nodei作為秘密份額。

②驗票節(jié)點挑選隨機(jī)數(shù)bi作為簽名時的私鑰，然后根據(jù)離散對數(shù)難解問題計算簽名用到的公鑰信息，如式（15）所示:

③驗票節(jié)點挑取整數(shù)ui，根據(jù)式（16）～（17）分別計算簽名時用到的參數(shù)Ui和oi，并將其廣播到投票區(qū)塊鏈中，然后在驗證時間T2內(nèi)收集所有其他驗證節(jié)點計算的參數(shù)oi，得到由所有oi連乘的公開參數(shù)O。

④驗證節(jié)點根據(jù)自己的秘密份額xi和各公開參數(shù)，對WVR進(jìn)行簽名，形成有效的部分簽名，如式（18）所示:

此時驗票節(jié)點完成驗票任務(wù)，將自己對待驗選票結(jié)果的反饋情況（簽名或拒絕）發(fā)到投票區(qū)塊鏈中，等待其他節(jié)點的驗證情況。同時驗票節(jié)點本地保存該信息，方便用于驗證最終宣布的結(jié)果信息是否和此信息相同。

3.4 選票結(jié)果的發(fā)布

在系統(tǒng)規(guī)定的驗證時間T2結(jié)束后，計票節(jié)點Nodec收集各驗票節(jié)點對待驗選票結(jié)果的驗證情況，查看是否滿足門限閾值。驗證結(jié)果根據(jù)各驗票節(jié)點對計票節(jié)點公布的信息是否接受分為accept 和reject。其中:accept 代表該節(jié)點認(rèn)可計票節(jié)點統(tǒng)計和計算得到的待驗選票結(jié)果，并給出自己部分簽名；reject代表該節(jié)點不同意計票節(jié)點公布的信息，不論是統(tǒng)計錯誤或是計票錯誤，驗證節(jié)點都發(fā)出“re-counting”請求。此時，計票節(jié)點Nodec將根據(jù)收到的accept 和reject 數(shù)量對待驗選票結(jié)果進(jìn)行如下操作:

1）當(dāng)Nodec收到accept 數(shù)量少于投票節(jié)點總數(shù)的2/3 時，代表驗證選票的驗票節(jié)點數(shù)量沒有達(dá)到方案的最低門限要求，此時由于待驗選票結(jié)果僅由較少的節(jié)點參與驗證，無法保證該結(jié)果的正確性，因此，不能生成基于待驗選票結(jié)果的合法門限簽名。但有部分驗票節(jié)點簽名則表示計票節(jié)點的行為正確，導(dǎo)致無法生成最終選票結(jié)果的原因僅因為驗票簽名不足，因此網(wǎng)絡(luò)陷入等待環(huán)節(jié)，繼續(xù)等候驗票節(jié)點的簽名，直到滿足簽名閾值，才能出示最終選舉結(jié)果。

2）當(dāng)Nodec收到reject數(shù)量大于投票節(jié)點總數(shù)的1/3時，表示計票節(jié)點公布的表單Listpre和選舉結(jié)果Voteresult確實存在作弊風(fēng)險，沒有合理正確的統(tǒng)計選票結(jié)果，此時調(diào)用PBFT 中視圖更換協(xié)議取消Nodec計票節(jié)點身份，并降低其信任度；同時選用信任度次高的節(jié)點擔(dān)任計票節(jié)點，然后重新完成選票統(tǒng)計和計票任務(wù)。

3）當(dāng)Nodec收到accept 數(shù)量大于投票者總數(shù)的2/3 時，表示驗證選票節(jié)點數(shù)達(dá)到門限簽名最低要求，且計票節(jié)點統(tǒng)計的待驗選票結(jié)果得到了大多數(shù)節(jié)點的認(rèn)可，此時可以生成對最終選票結(jié)果提供證明的門限簽名，如式（19）所示:

同時，根據(jù)驗票節(jié)點具體生成的部分簽名數(shù)量，可以得到關(guān)于最終選票結(jié)果的最低可信任度ζ，如式（20）所示。

在上述三種情況中，前兩種驗證情況均代表計票任務(wù)以失敗告終，都不能被視作準(zhǔn)確完成電子計票任務(wù)，只有第3）種情況才代表選舉結(jié)果真實可靠。同時，本文通過對參與驗票簽名人數(shù)（記為sn）的劃分明確了選舉結(jié)果的最低可信任度，并對不同信任度下的結(jié)果進(jìn)行標(biāo)識，具體對應(yīng)情況如表1所示。

當(dāng)計票節(jié)點Nodec成功完成計票任務(wù)，即可以將所有投票內(nèi)容以及相關(guān)簽名信息打包生成區(qū)塊。在生成單體區(qū)塊時，仍然選擇由區(qū)塊頭和區(qū)塊體兩部分組成，選票區(qū)塊結(jié)構(gòu)如圖4所示。

圖4 選票區(qū)塊結(jié)構(gòu)Fig. 4 Ballot block structure diagram

區(qū)塊頭包含當(dāng)前區(qū)塊體內(nèi)所有交易形成的哈希根植、前一區(qū)塊的哈希值、用于驗證結(jié)果真實的門限簽名以及選舉結(jié)果，區(qū)塊體包含所有合法的投票交易，在每條交易信息中包含消息/簽名對（m，σ），最后對區(qū)塊添加時間戳證明，形成不可篡改、可供驗證、結(jié)果真實的投票記錄。

表1 選舉結(jié)果狀態(tài)標(biāo)識Tab. 1 Status identifications of election result

4 本文方案分析

4.1 可行性分析

在電子投票領(lǐng)域中，Cortier 等［15-16］提到在當(dāng)前研究中眾多的選舉方案由于或存在中心機(jī)構(gòu)或選票結(jié)果不被驗證，導(dǎo)致很大程度上最終結(jié)果存在選票填充、遺漏或篡改的問題，從而影響選舉結(jié)果的真實性。本文基于區(qū)塊鏈環(huán)境提出了無需可信第三方計票機(jī)構(gòu)的可信計票方案，整體采用PBFT共識機(jī)制保障計票結(jié)果的正確性，同時區(qū)別于當(dāng)前PBFT 中主、從節(jié)點的劃分機(jī)制，以信任度高低確定計票節(jié)點和驗票節(jié)點。一方面提高分布式環(huán)境中計票效率，降低網(wǎng)絡(luò)開銷；另一方面可以監(jiān)督計票節(jié)點統(tǒng)計選票和計票結(jié)果的行為。當(dāng)網(wǎng)絡(luò)中超過1/3 的驗票節(jié)點在驗證過程中計算的結(jié)果信息與計票節(jié)點公布的待驗選票結(jié)果存在差異時，更換計票節(jié)點，結(jié)果完全根據(jù)共識機(jī)制，杜絕計票節(jié)點對數(shù)據(jù)的絕對控制，并且由于計票節(jié)點在公布待驗選票結(jié)果時并不能確定參與驗票的投票節(jié)點，因此更大程度上可以促進(jìn)計票節(jié)點的誠實行為，防止其惡意遺漏、篡改某些選票。采用門限簽名達(dá)成投票者范圍內(nèi)對待驗選票結(jié)果的驗證，考慮到分布式環(huán)境中無法強制要求所有節(jié)點驗證選票結(jié)果和盡可能較大程度保證選舉結(jié)果的真實性，方案將PBFT在分布式環(huán)境中可信節(jié)點的數(shù)量作為門限簽名的閾值:若達(dá)到簽名數(shù)量則結(jié)果可信，反之結(jié)果視為無效，可有效增加方案的可行性。

4.2 安全性分析

本文重在解決選票在計票過程中存在的安全性問題，在此階段前依賴高效的盲簽名技術(shù)完成驗票等環(huán)節(jié)保障選票的合法性。在收集選票過程中，方案選擇由可信度最高的節(jié)點負(fù)責(zé)統(tǒng)計選票，消除了傳統(tǒng)“可信”計票機(jī)構(gòu)對結(jié)果的作弊風(fēng)險，且計票節(jié)點不同于可信機(jī)構(gòu)，投票區(qū)塊鏈中的任何節(jié)點都可以且必須在最終結(jié)果正式公布前驗證待驗選票結(jié)果的正確性，從而保證計票的穩(wěn)定性。在表示驗證成功時，運用門限簽名的形式達(dá)成對待驗選票結(jié)果的共識，每個驗票節(jié)點的部分簽名只能由其獨立簽名，其他任何節(jié)點均不能偽造該節(jié)點對結(jié)果的簽名，并且只有當(dāng)系統(tǒng)中得到的部分簽名數(shù)超過門限閾值時才可以生成合法門限簽名，證明最終結(jié)果的真實性。區(qū)塊鏈作為去中心化、去信任、防篡改的分布式數(shù)據(jù)庫，任何想要否定存儲在區(qū)塊鏈數(shù)據(jù)的攻擊者都需要打破既定的共識機(jī)制，在PBFT中，只有攻擊者控制1/3以上的節(jié)點才可以對合法數(shù)據(jù)進(jìn)行否定，而在分布式環(huán)境中，控制總體數(shù)量的1/3 幾乎難以實現(xiàn)，且如果確實全網(wǎng)超過1/3的節(jié)點不能對合法數(shù)據(jù)達(dá)成共識，則說明網(wǎng)絡(luò)存在問題，選舉受到操控，因此正常情況下，若選票結(jié)果在統(tǒng)計正確時，至多只有不超過1/3 的惡意節(jié)點或非故障節(jié)點提出異議。在選舉結(jié)果達(dá)成共識后，使用哈希算法對交易打包形成區(qū)塊，任何試圖篡改選票的行為都會改變哈希值進(jìn)而影響區(qū)塊信息而被發(fā)現(xiàn)，因此使用區(qū)塊鏈技術(shù)可以保障選票在區(qū)塊賬本中的安全性。

4.3 方案對比分析

將本文方案和其他方案進(jìn)行了有關(guān)計票結(jié)果正確性的對比分析，具體如表2所示。

表2 不同方案的對比Tab. 2 Comparison of different schemes

在文獻(xiàn)［18］的研究基礎(chǔ)上，文獻(xiàn)［8］方案有效地解決了電子投票方案中容易發(fā)生的選票碰撞問題，但是該方案的實現(xiàn)嚴(yán)重依賴于第三方的絕對可信，忽略了計票機(jī)構(gòu)和中心控制機(jī)構(gòu)的“不可信”行為對結(jié)果的影響。文獻(xiàn)［4］方案在基于區(qū)塊鏈技術(shù)設(shè)計電子投票方案時，雖然保證了結(jié)果存儲時的安全性和抗篡改性，但是同樣需要引入可信第三方負(fù)責(zé)計票，如此不僅破壞了區(qū)塊鏈自身的特性，也會影響計票結(jié)果的真實性。文獻(xiàn)［17］方案考慮到無法保證單一驗票員誠實的問題，提出采用多個驗票員驗證選票并收集信息，從而降低對單一驗票員的絕對可信；但是卻沒有考慮驗票員可以通過聯(lián)合作弊來對計票結(jié)果產(chǎn)生較大的影響。和上述方案相比，本文方案徹底取消了計票時常用的第三方，消除了傳統(tǒng)投票方案過程中對計票機(jī)構(gòu)可信的假設(shè)條件，滿足了區(qū)塊鏈環(huán)境的去中心化、去信任特性，防止了“可信”計票機(jī)構(gòu)的“不可信”行為。本文方案通過計票節(jié)點計票+驗證節(jié)點驗票模式的共識機(jī)制保障了計票過程的完整性；采用區(qū)塊鏈技術(shù)負(fù)責(zé)數(shù)據(jù)的安全性，降低了中心數(shù)據(jù)機(jī)構(gòu)的絕對控制權(quán)；通過提高驗票者的數(shù)量，降低了選票信息被遺漏的風(fēng)險，充分保證計票結(jié)果的穩(wěn)定性。

5 仿真實驗

5.1 測試環(huán)境

本文根據(jù)聯(lián)盟鏈環(huán)境設(shè)計基于實用拜占庭容錯算法的區(qū)塊鏈電子計票方案，在實驗過程中涉及的測試工具和其相應(yīng)的作用如表3所示。

表3 測試工具及其作用Tab. 3 Testing tools and their functions

5.2 測試過程

在測試過程中，通過調(diào)試不同節(jié)點總數(shù)N、不同拜占庭故障節(jié)點數(shù)Nf以及不同誠實節(jié)點簽名數(shù)Nt測試系統(tǒng)能否得到選票結(jié)果以及該公布結(jié)果的正確性。具體包括:PBFT算法主節(jié)點選取和本文基于信任確定計票節(jié)點的效率對比，不同節(jié)點總數(shù)下故障節(jié)點對計票結(jié)果的影響，以及固定節(jié)點總數(shù)下故障節(jié)點對計票結(jié)果的影響。

1）測試PBFT 算法主節(jié)點選取和本文基于信任確定計票節(jié)點的效率對比。

本文方案的計票過程中，計票節(jié)點的確定方式不同于原PBFT算法的主節(jié)點選取方式，在PBFT共識算法中，只要網(wǎng)絡(luò)中總體節(jié)點數(shù)量多于3 倍的故障節(jié)點，使用該算法就可以解決分布式環(huán)境中數(shù)據(jù)的一致性和正確性。換句話說，如果網(wǎng)絡(luò)中每4 個節(jié)點中只存在1 個故障節(jié)點時就不會影響系統(tǒng)的穩(wěn)定性。因此，本文以4 個節(jié)點為例，設(shè)定其中1 個節(jié)點為故障節(jié)點，其余3 個是正常節(jié)點，在不影響系統(tǒng)穩(wěn)定性的情況下模擬20 次的投票結(jié)果共識中，兩種不同計票節(jié)點選取方式中計票節(jié)點發(fā)生更換的次數(shù)對比如圖5所示。

圖5 兩種計票節(jié)點選取隨模擬投票總數(shù)遞增的更換次數(shù)Fig. 5 Number of replacements of two types of counting node selection with increasing simulated ballot number

從圖5 不難看出，在模擬20 次投票過程中，通過PBFT 隨機(jī)選取計票節(jié)點的模式共發(fā)生5 次計票節(jié)點的更換。而采用信任關(guān)系確定計票節(jié)點時，僅發(fā)生過兩次計票節(jié)點更換:第一次是對初始消息共識時選定了故障節(jié)點充當(dāng)計票節(jié)點，由于初始階段4 個節(jié)點信任度相同，所以存在較大概率選擇故障節(jié)點充當(dāng)計票節(jié)點；第二次是人為關(guān)閉該節(jié)點網(wǎng)絡(luò)，阻止其參與共識，此時該節(jié)點發(fā)生故障，導(dǎo)致系統(tǒng)重新挑選計票節(jié)點。

由此可見，無論采用何種模式挑選計票節(jié)點都不影響消息的一致性和正確性確認(rèn)，但是基于信任關(guān)系確定計票節(jié)點的模式可以有效降低故障節(jié)點充當(dāng)計票節(jié)點的次數(shù)或概率，從而減少視圖更換協(xié)議產(chǎn)生次數(shù)，提高共識效率。

2）測試不同節(jié)點總數(shù)下Nf和Nt對計票結(jié)果的影響。

本文以節(jié)點的形式代表合法投票者，不同的節(jié)點總數(shù)模擬不同數(shù)量的投票場景。在測試過程中，分別測試了當(dāng)節(jié)點總數(shù)N = 4，10，30 時，計票結(jié)果受拜占庭故障節(jié)點數(shù)和誠實簽名數(shù)的影響，測試結(jié)果如表4 所示。可以看出，只要網(wǎng)絡(luò)中收到誠實節(jié)點的簽名數(shù)是已知拜占庭故障節(jié)點數(shù)的3 倍及以上，系統(tǒng)就可以公布計票節(jié)點統(tǒng)計的計票結(jié)果，并且該計票結(jié)果完全正確，可以實現(xiàn)基于區(qū)塊鏈環(huán)境的可信電子計票，如圖6 所示；但是如果簽名數(shù)量不滿足最低閾值要求，系統(tǒng)則返回提示消息:“簽名不足，請繼續(xù)等待！”，如圖7 所示，即不被允許公布計票結(jié)果，由此也無需判斷該結(jié)果的正確性。

表4 不同節(jié)點總數(shù)下Nf和Nt對計票結(jié)果的影響Tab. 4 Impact of Nf and Nt on counting results under different number of nodes

圖6 可信計票結(jié)果的公示Fig. 6 Publicity of trusted counting result

圖7 持續(xù)等待簽名結(jié)果的提示Fig. 7 Prompt of continuous waiting for signature result

3）測試固定節(jié)點總數(shù)下Nf和Nt對計票結(jié)果的影響。

假定網(wǎng)絡(luò)中節(jié)點總數(shù)固定不變，測試不同數(shù)量的拜占庭故障節(jié)點和獲得的誠實簽名數(shù)量對計票結(jié)果的影響程度。本文以節(jié)點總數(shù)是10 為例，通過動態(tài)調(diào)試網(wǎng)絡(luò)中的故障節(jié)點數(shù)和誠實簽名數(shù)觀察能否得到計票結(jié)果以及該結(jié)果的正確性，測試結(jié)果如表5所示。

表5 固定節(jié)點總數(shù)10下Nf和Nt對計票結(jié)果的影響Tab. 5 Impact of Nf and Nt on counting results under 10 nodes

從表5 可知，隨著故障節(jié)點的不斷增加，網(wǎng)絡(luò)中能夠獲得的誠實簽名逐漸減少，同時不同數(shù)量的拜占庭節(jié)點對于獲取計票結(jié)果時要求的誠實節(jié)點簽名數(shù)量不同:當(dāng)故障節(jié)點越少時，需要的誠實簽名越少，越容易得到可信計票結(jié)果；故障節(jié)點越多時，需要的誠實簽名越多。當(dāng)網(wǎng)絡(luò)中如果沒有故障節(jié)點，所有節(jié)點均為可信節(jié)點時，任何節(jié)點對計票結(jié)果簽名都可以代表結(jié)果的真實性。當(dāng)網(wǎng)絡(luò)中故障節(jié)點數(shù)量超過4 時，即便剩余節(jié)點（6 個）均對計票結(jié)果作誠實簽名也無法顯示投票結(jié)果。因為此時故障節(jié)點數(shù)量已經(jīng)超過PBFT 共識算法的假設(shè)條件，網(wǎng)絡(luò)本身處于不可信狀態(tài)，計票結(jié)果存在較大概率被惡意節(jié)點操控，因此難以在不可信網(wǎng)絡(luò)中獲得公平可信的投票結(jié)果，所以系統(tǒng)不公布該結(jié)果，保障投票的公平性。

由表4～5 可知，當(dāng)網(wǎng)絡(luò)中拜占庭故障節(jié)點數(shù)低于總數(shù)的1/3 且由誠實節(jié)點對計票結(jié)果的簽名數(shù)超過總數(shù)的2/3 時，系統(tǒng)均能夠顯示最終的選票結(jié)果并且該結(jié)果的正確性均為100%。由此可以說明，本文使用PBFT共識算法+門限簽名的方案可以起到和計票機(jī)構(gòu)相同的可信作用，因此，將本文方案應(yīng)用到實際選舉或投票場景的計票過程中，可以更加客觀地保障選票結(jié)果的真實性和公平性。

6 結(jié)語

針對區(qū)塊鏈電子投票中基于第三方計票機(jī)構(gòu)既不滿足區(qū)塊鏈去中心化、去信任特性，又無法保障其在計票中完全“可信”的行為，本文提出一種基于實用拜占庭容錯算法的區(qū)塊鏈電子計票方案。本文方案首先滿足區(qū)塊鏈環(huán)境特性，通過共識機(jī)制替代可信第三方計票機(jī)構(gòu)；其次，運用門限簽名的方法在結(jié)果被所有節(jié)點共識之前增加投票者自身的驗證，保障計票過程的真實性；同時綜合考慮實際因素和保證結(jié)果高度可信，將PBFT共識機(jī)制對誠實節(jié)點要求的最低數(shù)量作為簽名的門限閾值，不僅能夠解決可能存在的拜占庭故障問題，而且可以起到監(jiān)督計票節(jié)點的作用，進(jìn)一步實現(xiàn)去信任化。最后通過區(qū)塊鏈技術(shù)將選票記錄以及結(jié)果存入?yún)^(qū)塊中，由各節(jié)點共同維護(hù)賬本信息，降低傳統(tǒng)中心機(jī)構(gòu)對數(shù)據(jù)的絕對控制和防止中心機(jī)構(gòu)故障導(dǎo)致數(shù)據(jù)的丟失。未來將進(jìn)一步研究計票結(jié)果根據(jù)驗票人數(shù)的變化趨勢，量化可信任度，準(zhǔn)確衡量結(jié)果的真實性。