基于零知識證明的匿名投票方案

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

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

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

以太坊(Ethereum)[7]和零知識證明(zero knowledge proof)[8]技術(shù)的出現(xiàn)為這些缺陷提供了解決辦法。以太坊是去中心化系統(tǒng)的代表，它的數(shù)據(jù)分布于全球礦工節(jié)點，智能合約在以太坊上基于共識機制運行，具有透明性和可信性。所有礦工節(jié)點保存著一份公認的合約執(zhí)行結(jié)果，因此在區(qū)塊鏈上運行的智能合約結(jié)果具有不可篡改性。現(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ū)塊鏈的一個典型應用是當前實現(xiàn)在鏈上的各種不具備匿名性的去中心化自治組織(decentralized autonomous organization，DAO)，其通過智能合約運轉(zhuǎn)，具有較高的透明度和投票參與率，是未來區(qū)塊鏈發(fā)展的重要方向。零知識證明由Goldwasser等[8]在1985年提出，旨在讓證明者可以在不為驗證者提供任何有用信息的情況下，使驗證者相信某個論斷正確。將零知識證明應用于鏈上的投票系統(tǒng)，可使投票者在不透露任何身份信息的前提下完成投票。

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

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

1.1 橢圓曲線密碼

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

1.2 單向散列函數(shù)

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

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

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

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

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

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

(1)

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

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

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

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

(10)對皮特森哈希基點進行哈希抽取，抽取其x值作為最終皮特森哈希值。

1.3 非交互式零知識證明

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

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

在眾多zk-SNARK算法中，Ronald Mannak對比了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ù)量大小和驗證速度方面，Groth16遠好于其余算法[20]。因此使用Groth16算法作為系統(tǒng)核心算法，以達到減少投票成本、提升投票速度的目的。

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

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

實線箭頭代表函數(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ù)通過訪問者地址對訪問者身份進行認證。

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

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

3 基于零知識證明的匿名投票方案

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

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

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

圖2 匿名投票方案運行流程Fig.2 Anonymous voting scheme operation process

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

3.1 準備階段

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

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

算法1：零知識證明算術(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ù)電路生成用于進行零知識證明的兩組隨機數(shù)：Pk和Vk。隨后方案用得到的Pk和Vk生成驗證合約，驗證合約用于在驗證階段對智能合約的訪問者進行身份驗證。

3.2 投票發(fā)布階段

在投票發(fā)布階段，投票發(fā)布者會發(fā)布投票問題和相應選項至投票合約，并設(shè)置每個投票者最大投票次數(shù)。投票發(fā)布階段算法如算法2所示，對應圖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 投票階段

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

算法3：投票算法。

輸入：Vq,Vo;

輸出：R;

VrequireQifromSt;

returnQitoV;

VrequireOifromSt;

returnOitoV;

R=[Qi,Oi];

3.4 驗證階段

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

算法4：驗證算法。

輸入：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ù)到驗證合約*/

VsendπtoSv;

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

if Verify(π，Pi):

(8)SvsendR′ toSt;

(9) else

(10) visitor is not a voter;

(11)end if

3.5 計票階段

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

算法5：計票算法。

(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)應具有的7種基本安全性質(zhì)：合格性、匿名性、不可重復性、完整性、正確性、公平性和可驗證性，還滿足穩(wěn)定性和通用性。

4.1 安全性分析

4.1.1 合格性

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

4.1.2 匿名性

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

4.1.3 唯一性

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

4.1.4 完整性

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

4.1.5 正確性

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

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

4.1.6 公平性

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

4.1.7 可驗證性

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

4.1.8 穩(wěn)定性

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

4.1.9 通用性

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

4.2 方案對比分析

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

表2 方案對比Table 2 Comparison of schemes

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

5 結(jié)論

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