基于零知識(shí)證明的匿名投票方案

于筌，劉曉彤，刁恩虎，劉秀磊*

(1.北京信息科技大學(xué)北京材料基因工程高精尖創(chuàng)新中心，北京 100101； 2.北京信息科技大學(xué)數(shù)據(jù)與科學(xué)情報(bào)分析研究所，北京 100101)

電子投票是互聯(lián)網(wǎng)時(shí)代常用的決策手段，第一個(gè)電子投票協(xié)議由Chaum[1]在1981年提出，該協(xié)議使用公鑰密碼學(xué)技術(shù)，解決了不可信通信環(huán)境下的投票安全問題?，F(xiàn)有的大多數(shù)電子投票方案均依托于中心化節(jié)點(diǎn)，使用諸如盲簽名[2]等密碼學(xué)技術(shù)對(duì)投票過程進(jìn)行加密。中心化架構(gòu)具有系統(tǒng)結(jié)構(gòu)簡潔、響應(yīng)速度快等特點(diǎn)，但同時(shí)也存在諸多不足。從系統(tǒng)需求的角度，中心化系統(tǒng)易被單點(diǎn)攻擊，公信力不強(qiáng)；從加密算法的角度，中心化系統(tǒng)所基于的各種密碼學(xué)算法限制了系統(tǒng)的構(gòu)建：基于盲簽名的電子投票系統(tǒng)[3]無法完全隱藏投票者身份信息；基于秘密共享的電子投票系統(tǒng)[4]通信復(fù)雜度較高[5]；基于混合網(wǎng)絡(luò)的電子投票系統(tǒng)[6]雖然可以完成匿名投票，但需要多個(gè)混合服務(wù)器，系統(tǒng)成本較高。

以太坊(Ethereum)[7]和零知識(shí)證明(zero knowledge proof)[8]技術(shù)的出現(xiàn)為這些缺陷提供了解決辦法。以太坊是去中心化系統(tǒng)的代表，它的數(shù)據(jù)分布于全球礦工節(jié)點(diǎn)，智能合約在以太坊上基于共識(shí)機(jī)制運(yùn)行，具有透明性和可信性。所有礦工節(jié)點(diǎn)保存著一份公認(rèn)的合約執(zhí)行結(jié)果，因此在區(qū)塊鏈上運(yùn)行的智能合約結(jié)果具有不可篡改性?，F(xiàn)有很多系統(tǒng)選擇使用區(qū)塊鏈作為其底層結(jié)構(gòu)來提升安全性，如基于區(qū)塊鏈技術(shù)的數(shù)據(jù)共享系統(tǒng)[9]、基于聯(lián)盟區(qū)塊鏈的水產(chǎn)養(yǎng)殖品質(zhì)量追溯系統(tǒng)等[10]。在電子投票領(lǐng)域，基于區(qū)塊鏈的一個(gè)典型應(yīng)用是當(dāng)前實(shí)現(xiàn)在鏈上的各種不具備匿名性的去中心化自治組織(decentralized autonomous organization，DAO)，其通過智能合約運(yùn)轉(zhuǎn)，具有較高的透明度和投票參與率，是未來區(qū)塊鏈發(fā)展的重要方向。零知識(shí)證明由Goldwasser等[8]在1985年提出，旨在讓證明者可以在不為驗(yàn)證者提供任何有用信息的情況下，使驗(yàn)證者相信某個(gè)論斷正確。將零知識(shí)證明應(yīng)用于鏈上的投票系統(tǒng)，可使投票者在不透露任何身份信息的前提下完成投票。

現(xiàn)從基本的非匿名智能合約鏈上投票系統(tǒng)出發(fā)，使用零知識(shí)證明技術(shù)對(duì)智能合約進(jìn)行改進(jìn)，以滿足可重復(fù)匿名投票與不可重復(fù)匿名投票的應(yīng)用場景，彌補(bǔ)原始鏈上投票系統(tǒng)的缺陷，使最終投票系統(tǒng)同時(shí)具備匿名性與不可偽造性。上述系統(tǒng)除滿足常見投票場景外，亦可滿足涉及隱私的問卷調(diào)查場景，進(jìn)一步彰顯本系統(tǒng)的價(jià)值。所有智能合約、合約部署步驟及相關(guān)交互代碼均已開源，期望能為相關(guān)系統(tǒng)開發(fā)人員提供有益的參考。

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

1.1 橢圓曲線密碼

橢圓曲線密碼 (elliptic curve cryptography)[11]是指利用橢圓曲線的特性來實(shí)現(xiàn)如公鑰加密、共享密鑰等技術(shù)的統(tǒng)稱。與其他密碼算法相比，其優(yōu)勢(shì)在于相同長度下密碼強(qiáng)度高。由美國國家標(biāo)準(zhǔn)與技術(shù)研究院(National Institute of Standards and Technology，NIST) SP800-57文件[12]可知，長度250 bit左右的橢圓曲線密碼與長度為2 048 bit的RSA(Rivest-Shamir-Adleman)密碼具有近似的強(qiáng)度。使用對(duì)零知識(shí)證明電路設(shè)計(jì)友好的橢圓曲線Baby Jubjub[13]加密投票者身份信息，以保證投票方案的匿名性。

1.2 單向散列函數(shù)

單向散列函數(shù)是指可以將消息映射到散列值的函數(shù)，常見散列函數(shù)有SHA-256[14]、RIPEMD-160[15]、皮特森哈希(Pedersen Hash)[16]等。它需滿足以下3種性質(zhì)：抗碰撞性、隱秘性和謎題友好性。抗碰撞性是指函數(shù)難以人為產(chǎn)生哈希碰撞；隱秘性是指函數(shù)只能單向計(jì)算；謎題友好性是指函數(shù)輸出值不可預(yù)測。為滿足投票的實(shí)時(shí)性，選擇使用電路精簡、運(yùn)行速度快的皮特森哈希。皮特森哈希的生成過程如下。

(1)對(duì)域名分隔符、數(shù)組[0,1,…,63]使用blake2s-256散列函數(shù)[17]生成散列值，再將散列值使用映射函數(shù)在Baby Jubjub曲線上映射生成64個(gè)點(diǎn)[G0,G1,…,G63]。

(2)將輸入的位數(shù)用0填充至3的倍數(shù)。

(3)按照每塊189 bit分塊。

(4)再將每塊按照每片3 bit分片，共63片。

(5)每片使用式(1)進(jìn)行計(jì)算，其中mj代表此塊中的第j片，s0、s1、s2分別為第j片的第1、2、3位。

(1)

(6)將每片結(jié)果再乘以24j。

(7)所有結(jié)果相加得到H。

(8)計(jì)算[HG0,HG1,…,HG63]，得到[P0,P1,…,P63]。

(9)計(jì)算P0+P1+…+P63，得到皮特森哈希基點(diǎn)。

(10)對(duì)皮特森哈?；c(diǎn)進(jìn)行哈希抽取，抽取其x值作為最終皮特森哈希值。

1.3 非交互式零知識(shí)證明

非交互式零知識(shí)證明(non-interactive zero knowledge proof)[18]是一種特殊的零知識(shí)證明，證明者可以在不與驗(yàn)證者交互的情況下生成證明，以此排除證明者與驗(yàn)證者串通的情況。由于非交互式零知識(shí)證明協(xié)議允許智能合約充當(dāng)驗(yàn)證者，因此非常適用于以太坊應(yīng)用程序。在這種情況下，任何人都可以生成證據(jù)并將證據(jù)作為交易的一部分發(fā)送給智能合約，智能合約對(duì)證據(jù)進(jìn)行驗(yàn)證后，根據(jù)結(jié)果執(zhí)行后續(xù)操作。

最常用的非交互式零知識(shí)證明協(xié)議是簡潔的非交互式零知識(shí)證明(zero-knowledge succinct non-interactive argument of knowledge，zk-SNARK)[19]。它是具有簡潔證明和次線性驗(yàn)證時(shí)間的非交互式零知識(shí)協(xié)議，因其較高的可編程性而被大多數(shù)以太坊開發(fā)人員所接受。

在眾多zk-SNARK算法中，Ronald Mannak對(duì)比了8種主流的zk-SNARK算法的性能參數(shù)[20]，F(xiàn)ractal[21]、Halo[22]、SuperSonic[23]、Plonk[24]、Marlin[25]、Sonic[26]、Groth16[27]、zk-STARK[28]。研究表明，在證明數(shù)據(jù)量大小和驗(yàn)證速度方面，Groth16遠(yuǎn)好于其余算法[20]。因此使用Groth16算法作為系統(tǒng)核心算法，以達(dá)到減少投票成本、提升投票速度的目的。

2 基于智能合約的投票系統(tǒng)

基于智能合約的投票系統(tǒng)結(jié)構(gòu)如圖1所示，系統(tǒng)由鏈上智能合約與前端用戶交互界面組成。智能合約負(fù)責(zé)提供基本投票功能、存儲(chǔ)投票結(jié)果，并將投票過程標(biāo)識(shí)為相應(yīng)事件，以便用戶從以太坊區(qū)塊中查看。前端交互界面部分通過MetaMask瀏覽器錢包插件與鏈上智能合約進(jìn)行交互。系統(tǒng)具體投票步驟如下。

實(shí)線箭頭代表函數(shù)調(diào)用；虛線箭頭代表數(shù)據(jù)傳輸圖1 基于智能合約的投票系統(tǒng)結(jié)構(gòu)Fig.1 The architecture of the voting system based on smart contracts

(1)用戶連接MetaMask錢包，通過前端頁面訪問智能合約。

(2)智能合約使用權(quán)限函數(shù)通過訪問者地址對(duì)訪問者身份進(jìn)行認(rèn)證。

(3)認(rèn)證通過后，用戶調(diào)用功能函數(shù)進(jìn)行投票。

(4)待投票結(jié)束后，合約返回投票結(jié)果至前端，以供用戶查看。

3 基于零知識(shí)證明的匿名投票方案

上述實(shí)現(xiàn)的投票系統(tǒng)雖然通過地址對(duì)訪問者身份進(jìn)行了判斷，在一定程度上保證了投票過程的安全性，但這種驗(yàn)證方式并不具備匿名性。在這種地址與投票權(quán)一一綁定的驗(yàn)證方式中，攻擊者可以對(duì)地址的交易信息進(jìn)行分析，構(gòu)建用戶畫像，進(jìn)而獲取投票者部分身份信息。為了避免投票者身份信息泄露，系統(tǒng)需選擇一種可以完全隱藏身份信息的方法。首先，采用數(shù)字簽名技術(shù)標(biāo)識(shí)投票者，將用于數(shù)字簽名的公私鑰稱為投票私鑰Pr和投票公鑰Pb，以鏈下形式分發(fā)；其次，使用零知識(shí)證明技術(shù)隱藏Pr與Pb之間的關(guān)系，從而達(dá)到匿名投票的目的。

由于零知識(shí)證明方法會(huì)完全隱藏投票者特有信息，因此該方案無法滿足不可重復(fù)投票的應(yīng)用場景。為提高其通用性，在方案中加入皮特森哈希作為投票者的特征信息。智能合約可通過投票者發(fā)送的Pr的皮特森哈希來記錄每個(gè)投票者的投票次數(shù)，以消除惡意投票者對(duì)投票過程的影響。引入的皮特森哈希既與Pb無直接關(guān)系，又可以保護(hù)Pr，使該方案滿足匿名性的同時(shí)提高了通用性。

圖2所示的匿名投票方案的具體運(yùn)行流程分為5個(gè)階段，分別為準(zhǔn)備階段、發(fā)布投票階段、投票階段、驗(yàn)證階段和計(jì)票階段。下面將對(duì)每個(gè)階段的算法進(jìn)行介紹，其中表1記錄了算法中用到的主要參數(shù)及其代表符號(hào)。

圖2 匿名投票方案運(yùn)行流程Fig.2 Anonymous voting scheme operation process

表1 主要參數(shù)Table 1 Primary parameters

3.1 準(zhǔn)備階段

系統(tǒng)準(zhǔn)備階段共分為兩個(gè)部分，編寫零知識(shí)證明算術(shù)電路和構(gòu)造可信設(shè)置，對(duì)應(yīng)圖2中的步驟1、步驟2。

方案創(chuàng)建者首先需編寫零知識(shí)證明算術(shù)電路。電路描述構(gòu)造和驗(yàn)證零知識(shí)證明證據(jù)時(shí)需遵循的約束規(guī)則，其輸入分為私有輸入與公有輸入。 私有輸入包括所有證明者想要證明的秘密，對(duì)驗(yàn)證合約不可見；公有輸入包含私鑰哈希、投票者投票選擇等投票信息，對(duì)驗(yàn)證合約可見。

算法1：零知識(shí)證明算術(shù)電路。

私有輸入：Pr,R;

公共輸入：PbG,H′,R′;

Pb= GenPublicKey(Pr);

(2)fori= 1,2,3,…,len(PbG) do:

(3)/*約束投票公鑰必須在投票公鑰組中*/

PbG[i]=Pb;

(4)end for

H= GenHash(Pr) ;

(6)/*約束投票私鑰的哈希與合約接收的投票私鑰哈希一致*/

(7)/*約束投票選擇與合約接收的投票選擇一致*/

構(gòu)造可信設(shè)置即使用算術(shù)電路生成用于進(jìn)行零知識(shí)證明的兩組隨機(jī)數(shù)：Pk和Vk。隨后方案用得到的Pk和Vk生成驗(yàn)證合約，驗(yàn)證合約用于在驗(yàn)證階段對(duì)智能合約的訪問者進(jìn)行身份驗(yàn)證。

3.2 投票發(fā)布階段

在投票發(fā)布階段，投票發(fā)布者會(huì)發(fā)布投票問題和相應(yīng)選項(xiàng)至投票合約，并設(shè)置每個(gè)投票者最大投票次數(shù)。投票發(fā)布階段算法如算法2所示，對(duì)應(yīng)圖2的步驟(3)～步驟(7)。

算法2：投票發(fā)布算法。

輸入：Vq,Vo,Vmax;

輸出：Qi,Oi;

(1)PsendVqtoSt;

(2)StassignQitoVq;

(3)returnQitoP;

(4)fori= 1,2,3,…,do:

(5)Psend (Vo,Qi) toSt;

(6)end for

(7)StassignOitoVo;

(8)returnOitoP;

(9)PsendVmaxtoSt;

(10)StsaveVmax;

3.3 投票階段

在投票階段，投票者將其選擇輸入前端，前端與合約交互得到相應(yīng)問題與選項(xiàng)的id，以便在驗(yàn)證階段完成電路約束，生成證據(jù)。投票算法如算法3所示，對(duì)應(yīng)圖2的步驟(8)～步驟(13)。

算法3：投票算法。

輸入：Vq,Vo;

輸出：R;

VrequireQifromSt;

returnQitoV;

VrequireOifromSt;

returnOitoV;

R=[Qi,Oi];

3.4 驗(yàn)證階段

在驗(yàn)證階段，驗(yàn)證合約驗(yàn)證訪問者是否擁有投票權(quán)限。投票者需要對(duì)投票選擇進(jìn)行簽名，前端根據(jù)其投票私鑰生成證據(jù)，并將證據(jù)、投票私鑰哈希和在投票階段獲得的相應(yīng)id發(fā)送給驗(yàn)證合約。驗(yàn)證合約根據(jù)證據(jù)檢查投票者身份和投票選擇的正確性。驗(yàn)證階段算法如算法4所示，對(duì)應(yīng)圖2的步驟(14)～步驟(18)。

算法4：驗(yàn)證算法。

輸入：Pr,PbG,R;

(1)H= GenHash(Pr);

(2)Ci=[Pr,PbG,H,R];

(3)W= Calculate Witness(Ci);

(4)Pi= Slice(W);

(5)/*使用見證和證明密鑰生成證據(jù)*/

π= Prove(W，Pk);

(6)/*投票者發(fā)送證據(jù)到驗(yàn)證合約*/

VsendπtoSv;

(7)/*驗(yàn)證合約驗(yàn)證訪問者身份*/

if Verify(π，Pi):

(8)SvsendR′ toSt;

(9) else

(10) visitor is not a voter;

(11)end if

3.5 計(jì)票階段

當(dāng)訪問用戶被確定是投票者后，驗(yàn)證合約將信息發(fā)送給投票合約，方案進(jìn)入計(jì)票階段。在計(jì)票階段，投票合約需先驗(yàn)證投票者的投票次數(shù)是否符合規(guī)范。如果符合，則將投票計(jì)入；否則，將投票作廢。投票結(jié)束后，投票合約根據(jù)投票選擇將得票最多的選項(xiàng)設(shè)置為最終投票結(jié)果。計(jì)票階段算法如算法5所示，對(duì)應(yīng)圖2的步驟(19)～步驟(21)。

算法5：計(jì)票算法。

(1) ifH′ not in HL:

(2) PutH′ in HL；

(3) else:

(4) ifVc

(5) vaild vote;

(6) else:

(7) invaild vote;

(8) end if

(9) end if

(10) after voting:

(11)Stcalculate final results;

(12) return final results;

4 方案分析

提出的匿名投票方案不僅滿足Fujioka等[29]在1992年提出的電子投票系統(tǒng)應(yīng)具有的7種基本安全性質(zhì)：合格性、匿名性、不可重復(fù)性、完整性、正確性、公平性和可驗(yàn)證性，還滿足穩(wěn)定性和通用性。

4.1 安全性分析

4.1.1 合格性

合格性指沒有投票權(quán)的用戶無法進(jìn)行投票。在本文方案中，驗(yàn)證合約需要根據(jù)訪問者提交的證據(jù)驗(yàn)證訪問者的身份，給予其相應(yīng)的投票權(quán)限。只有擁有投票私鑰的投票者能生成正確的證據(jù)，執(zhí)行投票操作，因此方案滿足合格性。

4.1.2 匿名性

匿名性指所有投票者信息應(yīng)被保密。本文方案分兩步完成投票匿名性。第一步，方案使用數(shù)字簽名和零知識(shí)證明技術(shù)解除了投票權(quán)對(duì)地址的依賴，使投票者可以通過任意以太坊地址進(jìn)行投票，消除了投票者真實(shí)以太坊地址暴露的隱患。第二步，方案用于與鏈上合約交互的數(shù)據(jù)和合約中保存的數(shù)據(jù)均不包含任何投票者身份信息，防止攻擊者通過合約竊取投票者相關(guān)信息。至此方案滿足匿名性。

4.1.3 唯一性

唯一性指投票者在某些場景下不可重復(fù)投票。本文方案采用投票私鑰哈希作為特有信息標(biāo)識(shí)投票者。在不可重復(fù)的投票場景中，投票合約可以通過此標(biāo)識(shí)判斷投票者投票情況。因此方案滿足唯一性。

4.1.4 完整性

完整性指所有有效選票都被正確計(jì)算。對(duì)方案驗(yàn)證階段和計(jì)票階段的投票完整性進(jìn)行分析。在驗(yàn)證階段，方案使用零知識(shí)證明技術(shù)約束投票者的投票選擇無法被篡改。在計(jì)票階段，因智能合約具有原子性，投票合約接收的正確的投票選擇一定會(huì)按照規(guī)定好的投票規(guī)則計(jì)入結(jié)果。因此方案滿足完整性。

4.1.5 正確性

正確性指所有無效選票都不被計(jì)算。本文方案共有兩種出現(xiàn)無效選票的場景，一種是投票者投票次數(shù)超出投票發(fā)布者規(guī)定的最大投票次數(shù)，另一種是攻擊者篡改投票者正確的投票選擇后生成偽造選票。

針對(duì)第一種場景，方案在驗(yàn)證階段通過檢查投票者的投票次數(shù)對(duì)其進(jìn)行甄別。針對(duì)第二種場景，由于偽造選票不滿足零知識(shí)證明算術(shù)電路的約束，因此其無法通過驗(yàn)證合約的檢測。至此兩種無效選票均無法計(jì)入投票結(jié)果，方案滿足正確性。

4.1.6 公平性

公平性指投票中間結(jié)果不可被獲取。本文方案雖然在投票結(jié)束前不會(huì)公布投票結(jié)果，但每個(gè)投票者的投票選擇會(huì)伴隨交易記錄保存在以太坊中。由于投票選擇采用明文傳輸，攻擊者可以通過交易記錄中的數(shù)據(jù)計(jì)算出中間投票結(jié)果。針對(duì)上述場景，方案可通過合理設(shè)置投票時(shí)間來避免中間投票結(jié)果泄露，滿足公平性。

4.1.7 可驗(yàn)證性

可驗(yàn)證性指投票結(jié)果不會(huì)被偽造。本文方案在以太坊上運(yùn)行，投票過程的每一步和投票結(jié)果都通過交易記錄和事件日志被記錄在以太坊分布全球的節(jié)點(diǎn)中，具有不可篡改性。因此投票結(jié)果與投票過程均不可篡改，方案滿足可驗(yàn)證性。

4.1.8 穩(wěn)定性

穩(wěn)定性指系統(tǒng)抗干擾的能力。本文方案是去中心化的投票方案。方案不會(huì)因節(jié)點(diǎn)故障等中心化系統(tǒng)常出現(xiàn)的問題，造成投票數(shù)據(jù)丟失、投票系統(tǒng)崩潰等嚴(yán)重后果，因此方案穩(wěn)定性較強(qiáng)。

4.1.9 通用性

通用性指系統(tǒng)適用于不同應(yīng)用場景的能力。本文方案可同時(shí)滿足可重復(fù)匿名投票和不可重復(fù)匿名投票兩種投票場景，且支持投票發(fā)布者根據(jù)自身需求設(shè)置每個(gè)投票者的最大投票次數(shù)，具有良好的通用性。

4.2 方案對(duì)比分析

通過將本文方案與已提出的電子投票方案進(jìn)行對(duì)比分析(表2)，表明本文方案基本解決了電子投票系統(tǒng)常見的安全問題。

表2 方案對(duì)比Table 2 Comparison of schemes

文獻(xiàn)[30]提出的投票方案雖然在文獻(xiàn)[29]提出的方案上進(jìn)行改進(jìn)，解決了選票碰撞問題，增強(qiáng)了方案的安全性。但其仍然是中心化投票方案，嚴(yán)重依賴可信第三方，因此不滿足投票匿名性、可驗(yàn)證性和穩(wěn)定性。文獻(xiàn)[31]和文獻(xiàn)[32]提出的電子投票方案將保存的以太坊地址作為投票者特有信息來驗(yàn)證投票唯一性。與第3節(jié)描述的方案相同，這種方式限制投票者只能使用特定的以太坊地址進(jìn)行投票，雖然沒有直接暴露投票者身份信息，但攻擊者可以由此得到投票者真實(shí)以太坊地址，進(jìn)而獲取投票者真實(shí)身份信息，方案不滿足匿名性。文獻(xiàn)[30-32]提出的電子投票方案雖然分別使用可信第三方分配的身份標(biāo)識(shí)和以太坊地址作為投票者特有信息對(duì)投票唯一性進(jìn)行判定，但3種方案均未考慮可重復(fù)投票場景，不滿足通用性。文獻(xiàn)[33]中提出的方案使用一次性環(huán)簽名算法，滿足電子投票系統(tǒng)的基本安全要求。但方案無法同時(shí)滿足可重復(fù)投票和不可重復(fù)投票場景，通用性差于本文提出方案。和上述3種方案相比，本文方案滿足電子投票方案應(yīng)具有的安全特性，且具備更好的通用性，可以滿足各種不同的應(yīng)用場景。

5 結(jié)論

提出一種結(jié)合零知識(shí)證明與數(shù)字簽名技術(shù)的鏈上匿名投票方案。該方案可以使投票者在不暴露任何身份信息的前提下完成投票，并通過算術(shù)電路來約束投票過程的完整性和正確性。借助以太坊去中心化、透明、不可篡改等特點(diǎn)，實(shí)現(xiàn)了投票可驗(yàn)證性和系統(tǒng)穩(wěn)定性。經(jīng)過對(duì)比分析，方案在滿足電子投票系統(tǒng)基本安全特性的同時(shí)，還具備比已提出的電子投票系統(tǒng)更好的通用性，適用于不同的應(yīng)用場景。