吳芷菡，崔 喆*，劉 霆，蒲泓全

（1.中國科學(xué)院成都計算機應(yīng)用研究所，成都 610041；2.中國科學(xué)院大學(xué)，北京 100049）

（*通信作者電子郵箱cuizhe@casit.com.cn）

0 引言

隨著現(xiàn)代信息技術(shù)的發(fā)展，社會對電子選舉技術(shù)以及社會民主進步的關(guān)注日益增加。近年來，電子選舉已經(jīng)成為國際信息技術(shù)界一個特殊重要的領(lǐng)域。如今國際電子選舉系統(tǒng)研究主要分為兩個方向：一是基于遠程網(wǎng)絡(luò)通信的電子選舉（Remote e-Voting），主要是基于數(shù)論的密碼學(xué)工具和應(yīng)用技巧，主要有基于同態(tài)加密的電子選舉方案、基于秘密共享的電子選舉方案、基于盲簽名的電子選舉方案和基于混合網(wǎng)絡(luò)的電子選舉方案；二是基于抵近物理站站點投票的電子選舉（Site-Polling e-Voting），主要憑借物理設(shè)備和先進的信息技術(shù)手段實現(xiàn)高可信、高可靠的選舉系統(tǒng)，例如應(yīng)用于我國人民代表大會的選舉系統(tǒng)。本文的研究方向是基于遠程網(wǎng)絡(luò)通信的電子選舉。

基于同態(tài)加密的方案通過同態(tài)加密算法：ElGamal密碼體制［1］、LWE（Learning With Errors）密碼體制［2］和Paillier［3］密碼體制對選票進行加密，然后由可信第三方計票機構(gòu)接收和計算加密選票，文獻［1-2］采用乘法同態(tài)、全同態(tài)運算，計算效率低，復(fù)雜度高，實用性較低?；诿孛芄蚕恚?-5］的方案通過將拆分后的選票發(fā)送至多個機構(gòu)存儲，由部分或全部機構(gòu)恢復(fù)選票并統(tǒng)計結(jié)果，雖然多個可信任計票機構(gòu)中心降低了單一權(quán)威計票機構(gòu)內(nèi)部欺詐的風(fēng)險，但超過一定門限數(shù)量的機構(gòu)串通仍可進行共謀攻擊，控制選舉?；诿ず灻姆桨赣蠪OO（FUJIOKA-OKAMOTO-OHTA）［6］、基 于ElGamal 簽名體制［7］等協(xié)議，通過盲簽名技術(shù)對選民選票簽名，存在依賴選舉管理機構(gòu)的公正性、選票碰撞、選舉過程操作繁瑣、協(xié)議效率低等問題?；诨旌暇W(wǎng)絡(luò)的方案算法復(fù)雜，實現(xiàn)困難［8］。針對現(xiàn)有方案存在的投票效率低、可能存在內(nèi)部欺詐、依賴可信第三方等問題和電子選舉主要的兩個矛盾點，結(jié)合區(qū)塊鏈公開透明、不可篡改、集體維護等特性，本文提出了基于區(qū)塊鏈的去中心化電子選舉方案。選民身份管理設(shè)計基于非交互式零知識證明算法zk-SNARKs（zero-knowledge Succinct Noninteractive ARgument of Knowledges）［9］和區(qū)塊鏈架構(gòu)，既保證了選舉的匿名性又保證了公開可驗證性；選票隱私保護設(shè)計基于Paillier 公鑰密碼體制；通過以太坊智能合約實現(xiàn)選舉投票和計票流程自動化，去中心化。

1 預(yù)備知識

1.1 以太坊與智能合約

以太坊（Ethereum）是一個基于區(qū)塊鏈技術(shù)的，可創(chuàng)建、使用智能合約（Smart Contract）和去中心化應(yīng)用（Decentralized Application，DApp）的開源平臺［10］。智能合約是以太坊網(wǎng)絡(luò)上運行的程序，是一種由事件驅(qū)動的，具有具體狀態(tài)的代碼合約和算法合約。智能合約的代碼編譯后生成的字節(jié)碼可以在以太坊客戶端和節(jié)點運行。以太坊平臺對底層區(qū)塊鏈技術(shù)進行了封裝，讓區(qū)塊鏈應(yīng)用開發(fā)者可以直接基于以太坊平臺進行開發(fā)，只專注于開發(fā)應(yīng)用本身邏輯的智能合約，這樣可以大幅度降低開發(fā)難度和成本。智能合約適用于對信任、安全和持久性要求較高的應(yīng)用場景，例如數(shù)字貨幣、數(shù)字資產(chǎn)、投票、保險、金融應(yīng)用、預(yù)測市場、產(chǎn)權(quán)所有權(quán)管理、物聯(lián)網(wǎng)、點對點交易等。

1.2 零知識證明

零知識證明（Zero-Knowledge Proof）由Goldwasser 等［11］在20世紀(jì)80年代初提出，證明者能夠在不向驗證者提供任何有用的信息的情況下，使驗證者相信某個論斷是正確的。Goldwasser 等［11］提出的是交互式零知識證明，需要證明者和驗證者進行多輪通信證明，對于復(fù)雜問題證明效率較低。De Santis等［12］首次提出了非交互零知識證明的概念，證明者只需要按照協(xié)議向驗證者發(fā)送一次消息就可以讓驗證者以高概率確信一個論斷是正確的。最初的非交互式零知識證明系統(tǒng)的效率是非常低，難以應(yīng)用于實際問題。后續(xù)研究證明對于所有的NP語言都存在對應(yīng)的非交互式零知識證明［13］，研究者們通常將非交互式零知識問題規(guī)約到NP 問題上。非交互式零知識證明已被廣泛應(yīng)用于當(dāng)今的密碼體制中。

區(qū)塊鏈中每一筆交易的共識驗證過程都涉及區(qū)塊鏈網(wǎng)絡(luò)的每一個節(jié)點，采用交互式零知識證明開銷過大，所以在區(qū)塊鏈系統(tǒng)中更適合采用非交互式零知識證明。zk-SNARKs是典型的非交互式零知識證明協(xié)議，通過同態(tài)隱藏、多項式盲估、匹諾曹協(xié)議、橢圓曲線配對等技術(shù)，實現(xiàn)了證明者只需要提供的短小的零知識證明字符串proof 就可以完成簡潔、高效的證明過程。目前匿名性較好的密碼學(xué)貨幣Zerocash［9］就是利用zk-SNARKs 實現(xiàn)交易信息隱私保護。Zerocash中隱私交易信息可以在區(qū)塊鏈上完全加密，在加密的情況下仍然可以通過zk-SNARKs證明在該交易在共識規(guī)則下的有效性。

1.3 Pailier公鑰密碼體制

Paillier 算法是一種具有語義安全性，是基于復(fù)合剩余類的困難問題的公鑰密碼體制，該加密算法滿足加法同態(tài)性和混合乘法同態(tài)性，其中加法同態(tài)性適用于電子選舉系統(tǒng)的選票加密［14］。加法同態(tài)指的是通過密文E(X)和E(Y)可計算獲得E(X+Y)，解密后可得到X+Y。

Paillier 密鑰生成 隨機且彼此獨立地選擇兩個大質(zhì)數(shù)p和q，且滿足gcd(p×q，(p-1) ×(q-1))=1，gcd 表示最大公約數(shù)，計算n=p×q和λ=lcm(p-1，q-1)，lcm 表示最小公倍數(shù)。選擇隨機整數(shù)g∈G，G為模n2的乘法群，并且滿足μ=(L(gλmodn2))-1modn，其中定義函數(shù)L(x)=(x-1)/n。Paillier算法公鑰為(n，g)，私鑰為(λ，μ)。

Paillier 加密 設(shè)m(0 ≤m＜n)為需要加密的信息，選擇加密隨機數(shù)r，r需滿足0 ＜r＜n和r∈G，確保gcd(r，n)=1。加密算法EP(m)=gm×rnmodn2，分別對明文m1 和m2 進行加 密，得到對應(yīng)密文為c1=gm1×rnmodn2和c2=gm2×rnmodn2。密文性質(zhì)有c1×c2=g(m1+m2)×r2nmodn2=EP(m1+m2)，所以Paillier算法具有加法同態(tài)性［14］。

2 去中心化電子選舉方案

2.1 方案設(shè)計

在本電子選舉方案中，參與者如下：

選舉發(fā)起方 發(fā)起選舉，初始化選舉信息。

線下認證中心（由選舉發(fā)起方指定） 選舉方在注冊階段設(shè)置線下驗證點，對選民的身份進行驗證。

選民 用V1，V2，…，Vn表示。

候選人 一場選舉中有多個候選人，對應(yīng)的候選人用C1，C2，…，Cm表示。

選舉初始化階段，選舉發(fā)起方初始化選舉信息，部署選舉智能合約至區(qū)塊鏈；選舉注冊階段，選民在線下認證中心認證、注冊獲得投票資格；選舉投票階段，選民通過zk-SNARKs零知識證明算法生成身份證明proofV和選票合法性證明proofB，通過Paillier 算法加密選票，將零知識證明和加密選票發(fā)送至區(qū)塊鏈；選舉計票階段，智能合約自動調(diào)用計票算法，獲取區(qū)塊鏈上的加密選票，利用Paillier 算法加法同態(tài)實現(xiàn)加密計票。整個選舉過程數(shù)據(jù)經(jīng)國密算法SM2橢圓曲線公鑰密碼算法［15］、SM3密碼雜湊算法［16］處理后公開寫入?yún)^(qū)塊鏈，任何參與者都可以驗證投票數(shù)據(jù)和選舉結(jié)果。

2.2 基于zk-SNARKs算法選民身份隱藏方案

選民身份管理是電子選舉的一大難題，在選舉過程中為保證選民身份合法性，需要對選民身份進行有效的認證，但在選舉過程中又要需要保證匿名性。針對這個問題，通過區(qū)塊鏈架構(gòu)和zk-SNARKs非交互式零知識證明實現(xiàn)選舉匿名性和選民身份合法性驗證。投票階段，通過zk-SNARKs 生成選民身份證明proofV，將proofV和加密選票一同寫入?yún)^(qū)塊鏈；計票階段，智能合約通過調(diào)用驗證算法驗證proofV間接驗證選民身份的合法性。區(qū)塊鏈的數(shù)據(jù)是公開透明的，任何人都可以對區(qū)塊鏈上的proofV進行驗證；區(qū)塊鏈具有一定的匿名性，在區(qū)塊鏈實現(xiàn)一次身份隱藏的基礎(chǔ)上再通過zk-SNARKs實現(xiàn)二次身份隱藏；基于zk-SNARKs 非交互式特性，一次生成證明proofV，無需多次交互，保證選舉效率。

由于zk-SNARKs 不能直接應(yīng)用于任意問題，必須有可量化的輸入，因此需要將實際問題轉(zhuǎn)換成zk-SNARKs 可處理的數(shù)學(xué)描述模型：首先將需要證明的問題約化為指定的NP 問題，實現(xiàn)基于算術(shù)電路的NP 問題的證明和驗證；然后再通過多項式盲驗證、同態(tài)隱藏、匹諾曹協(xié)議等技術(shù)生成零知識證明字符串proof；最終生成的proof基于多項式等式的抽樣驗證只需要O（1）的驗證代價，驗證更為高效、簡潔。

zk-SNARKs身份證明算法生成proofV過程如下［9，17］：

1）算術(shù)邏輯方程驗證轉(zhuǎn)化為算術(shù)電路驗證。

選民需要在不暴露i的具體數(shù)值情況下證明自己是合法選民V1，V2，…，Vn中的一員Vi，算術(shù)邏輯方程可表示為：

式（1）的門電路可表示為方程組（2）：

將算術(shù)方程轉(zhuǎn)化為算術(shù)電路，首先將方程分解為加法、乘法組成的最小操作，然后增加中間變量，把復(fù)雜的計算方程轉(zhuǎn)化為簡單的門電路表示，最終門電路的輸出結(jié)果與原表達式等價。

其中sys1，sys2，…，sysm是算術(shù)電路設(shè)計新增的中間變量，out是整個電路的輸出，等價于方程的計算結(jié)果。該方程的電路表示如圖1所示。

圖1 選民身份證明算術(shù)電路Fig.1 Arithmetic circuit of voter identification

2）算術(shù)電路驗證轉(zhuǎn)化為向量驗證R1CS（Rank-1 Constraint System）［18］。

將每一個門電路表示為等價的向量點積形式，這個過程稱為R1CS，就是將門電路轉(zhuǎn)化成向量的表達方式。首先用一組向量定義算術(shù)電路中的所有的變量。上述電路可表示為：one代表常量變量1，V1，V2，…，Vn，Vi代表輸入，sys1，sys2，…，sysm代表中間門電路的輸出，out代表整體電路輸出。則定義s如下：

然后對于每個門電路，存在一組向量(a，b，c)，使得s?a*s?b-s?c=0 成 立。例如門電路sys1=(V1-Vi)，存在向量組：

a=[1，0，…，0，0，0，…，0]，s?a結(jié)果為one；

b=[0，1，…，0，-1，0，…，0]，s?b結(jié)果為V1-Vi；

c=[0，0，…，0，0，1，…，0]，s?c結(jié)果為sys1；

代入s?a*s?b-s?c=0，可計算得到：one*(V1-Vi)-sys1=0，等價于sys1=(V1-Vi)。以此類推，可將所有門電路轉(zhuǎn)化成向量表達式s?a*s?b-s?c=0，獲得每個門電路對應(yīng)的向量組(a，b，c)。

3）向量驗證R1CS 轉(zhuǎn)化為QAP（Quadratic Assignment Problems）［19］多項式驗證。

本文方案選擇將選民身份驗證問題歸約的NP 問題為二次算數(shù)問題QAP，證明QAP 多項式成立就是證明選民身份合法性。QAP 指的是有一系列多項式和一個目標(biāo)多項式，存在多項式的組合能整除目標(biāo)多項式。

已知w個門電路都對應(yīng)存在向量組(a，b，c)，將a，b，c中每個系數(shù)看成一個多項式的結(jié)果，例如每個門電路對應(yīng)的向量a的系數(shù)作為一個多項式的解，可以反推出多項式a(x)=[f0(x)，f1(x)，…，fk(x)]：對于門電路1，已知解f0(1)，以此類推f0(2)，f0(3)，…，f0(w)都是已知值，可以通過拉格朗日插值法反推出多項式f0(x)，當(dāng)向量比較大時，可以通過快速傅里葉變化進行優(yōu)化。同理可以算出f1(x)，f2(x)，…，fk(x)。最終，轉(zhuǎn)化完成后可獲得三個多項式數(shù)組a(x)，b(x)，c(x)。

定義多項式P(x)=s?a(x)*s?b(x)-s?c(x)，x∈(1，2，…，w)，w是門的數(shù)量。已知每個門電路對應(yīng)的向量組都滿足s?a*s?b-s?c=0，則當(dāng)x取1 至w任意值，都有P(x)=0。根據(jù)多項式特性，若P(a)=0，則(x-a)可以整除P(x)，以此類推，P(x)可以被(x-1)(x-2)…(x-w)整除，即滿足QAP 定義，存在H(x)=0 使得T(x)=(x-1)(x-2)…(x-w)目標(biāo)多項式可以整除多項式組合P(x)，生成QAP方程：

s?a(x)*s?b(x)-s?c(x)=T(x)*H(x) （3）

將驗證計算方程式（1）轉(zhuǎn)化為驗證QAP 方程式（3）過程中的向量s是證明者獨有，也只有正確的s才能使方程成立，且在轉(zhuǎn)化過程中插入的混淆值與計算方程的邏輯沒有任何關(guān)系，QAP多項式的驗證不等于原方程的驗證，而是原方程的驗證包含在QAP 方程的驗證里，那么驗證QAP 方程等于驗證原方程。zk-SNARKs 算法通過抽樣實現(xiàn)簡潔驗證，并不需要驗證所有的x，x∈(1，2，…，w)，只需要隨機抽查任意一個點驗證即可，所以算法驗證速度快。

4）zk-SNARKs零知識證明。

驗證方程為式（3），為了方便表示，定義A(x)=s?a(x)，B(x)=s?b(x)，C(x)=s?c(x)，則方程表示可為A(x)*B(x)-C(x)=T(x)*H(x)。

橢圓曲線配對［20］證明過程采用橢圓曲線加密算法E(x)=gx，g為生成元。已知橢圓曲線滿足加法同態(tài)，在驗證方程A(x)*B(x)-C(x)=T(x)*H(x)時涉及乘法，可以通過橢圓曲線配對實現(xiàn)計算層面的乘法同態(tài)。已知配對函數(shù)定義如下：e(gx，gy)=e(g，g)xy，對于明文m1 和m2，對應(yīng)密文為E(m1)，(m2)，存在等式：

橢圓曲線α對［20］zk-SNARKs 零知識證明利用了α對的性質(zhì)實現(xiàn)多項式盲驗證。橢圓曲線的α對指的是橢圓曲線上滿足y=α*x的一對值(x，y)，利用α對的性質(zhì)，可設(shè)計如下證明過程以滿足在不暴露隱私信息的情況下讓驗證相信證明者擁有某個信息：

驗證者生成α參數(shù)，根據(jù)參數(shù)生成α對(x，y)，驗證者保存參數(shù)α，將α對(x，y)發(fā)送給證明者。

證明者持有信息β，與驗證生成的α對進行計算可獲得(x'，y')=(β*x，β*y)。已知y=α*x，利用交換律，則y'=β*y=β*α*x=α*(β*x)=α*x'，根據(jù)定義(x'，y')也是一個α對。證明者將(x'，y')發(fā)送給驗證者。

驗證者驗證(x'，y')是否是α對，就可以知道證明者是否持有信息β，且驗證過程不會暴露證明者擁有的信息β。

公共參考串（Common Reference String，CRS）模型［21］zk-SNARKs 為了實現(xiàn)非交互式零知識證明，采用了公共參考串模型CRS，將驗證參數(shù)進行處理后公示。若k，α，βa，βb，βc隨機參數(shù)被泄露，則證明的安全前提將不復(fù)存在，所以ZeroCash選擇了世界各地6個可信任機構(gòu)分別生成密鑰的一部分，6份密鑰拼接在一起生成隨機參數(shù)k，α，βa，βb，βc和隨機參數(shù)的公示數(shù)據(jù)CRS 后便被分別銷毀，隨機參數(shù)k，α，βa，βb，βc也被銷毀，由此來保證CRS的安全性。生成proof階段：

步驟一 驗證者確定生成元為g、階為n的有限群，已知A(x)，B(x)，C(x)多項式的最高階為d，隨機選擇有限群中的元素k，和隨機參數(shù)α，βa，βb，βc計算生成CRS式（5），寫入?yún)^(qū)塊鏈并公布。

步驟二 證明者利用橢圓曲線的同態(tài)性質(zhì)，讀取驗證者公布在區(qū)塊鏈上的參數(shù)CRS可計算生成proofVi如式（6）：

驗證proof階段：

步驟一 驗證者僅根據(jù)E(A(k))，E(B(k))，E(C(k))是無法確認是由多項式A(x)，B(x)，C(x)的計算生成，利用α對的特性，進行多項式盲驗證，驗證選民的proofVi是由多項式計算生成。以A(x)為例，驗證式（7）和式（8）運算結(jié)果相等，則證明E(A(k)) 和E(αA(k)) 是α對，以此類推E(B(k)) 和E(αB(k))，E(C(k))和E(αC(k))，E(H(k))和E(αH(k))是α對，由此證明A(x)，B(x)，C(x)，H(x)都是多項式形式。

步驟二 整個驗證過程中，驗證方只隨機抽查任意一點k，若驗證者無法確認方程（3）是否由s生成，同時證明者知道驗證者選擇的驗證點k，那么證明者就可以任意構(gòu)造滿足驗證點的方程，而這個方程可以不由向量s生成。所以驗證過程還需要驗證A(x)，B(x)，C(x)是由同一個向量s生成，利用多項式特性，只要證明者給出A(x)，B(x)，C(x)的線性組合，則能證明A(x)，B(x)，C(x)從同一組參數(shù)s生成，驗證式（9）和式（10）相等，則證明βa A(k)+βbB(k)+βcC(k)為線性組合。

步驟三 通過步驟一和步驟二保證驗證數(shù)據(jù)的合法性，然后驗證式（11）和式（12）若相等，則證明A(x)*B(x)=T(x)*H(x)+C(x)，即證明方程A(x)*B(x)-C(x)=T(x)*H(x)成立。

2.3 基于Paillier算法的選票加密方案

針對既要保證選票信息的隱私保密要求，又要保證選舉結(jié)果的公眾可驗證性，通過區(qū)塊鏈架構(gòu)、zk-SNARKs 算法、Paillier 密碼體制選票實現(xiàn)選票加密方案。投票階段，將Paillier算法加密的選票和zk-SNARKs算法生成選票合法性證明proofB寫入?yún)^(qū)塊鏈；計票階段，通過以太坊智能合約實現(xiàn)自動計票，利用Paillier 算法加法同態(tài)性質(zhì)計算選舉結(jié)果。算法實行多次加密選票，一次解密選舉結(jié)果，既提高了計票效率又實現(xiàn)選票隱私保密；利用加法同態(tài)比乘法同態(tài)和全同態(tài)計算效率更高；選舉數(shù)據(jù)寫入?yún)^(qū)塊鏈，任何人都進行驗證，滿足公眾可驗證性。

選票表示為(ViC1，ViC2，…，ViCm)，ViCj指的是第i位選民投給第j位候選人的票數(shù)，ViCj∈(0，1)，i∈(1，2，…，n)，j∈(1，2，…，m)。初始化選票階段，數(shù)組每一位為0，投票階段，選擇哪位候選者就將對應(yīng)的那一位置為1。用于選票加密的Paillier算法的公鑰為(g'，n')，私鑰為(λ，μ)。對選票進行加密，加密后公開發(fā)布至區(qū)塊鏈，選民選票加密情況如表1所示。

表1 加密選票Tab.1 Encrypted ballots

則候選人Cj的加密票數(shù)由Paillier 算法加法同態(tài)計算得到：使用私鑰(λ，μ)進行解密即可獲得候選人Cj的總票數(shù)：以此類推可計算出所有候選者的票數(shù)(t1，t2，…，tm)。

由于選票加密后無法驗證選票具體數(shù)值，也就無法直接驗證選票是否合法（最多只能有一位置為1，其余位全為0），將選票合法性驗證問題歸約為zk-SNARKs證明。選民需要在不暴露選票(ViC1，ViC2，…，ViCm)的情況下證明選票合法，則邏輯算術(shù)表達式為ViC1+ViC2+…+ViCm=0 或ViC1+ViC2+…+ViCm=1，轉(zhuǎn)化為算術(shù)電路如圖2。

圖2 選票合法性證明算術(shù)電路Fig.2 Arithmetic circuit of proof of ballot legality

若選民沒有選擇候選人，則電路out=0，否則out=1。兩種不同情況對應(yīng)不同的out，該電路可表示為：one代表常量變量1，(ViC1，ViC2，…，ViCm)代表輸入，sys1，sys2，…，sysv代表中間門電路的輸出，out代表整體電路輸出。則定義s如下：

后續(xù)根據(jù)s計算每個門電路對應(yīng)的向量組(a，b，c)，轉(zhuǎn)化為向量驗證和再轉(zhuǎn)化為QAP 多項驗證與選民身份證明s生成過程相同，最終可生成選票合法性證明。

2.4 去中心化電子選舉方案流程

整體選舉流程如圖3所示。

1）選舉系統(tǒng)初始化階段。

選舉發(fā)起方登錄以太坊賬號：

初始化選舉基礎(chǔ)信息：選舉名稱、選舉起止時間等；

初始化用于選票加密的Paillier公私鑰：公鑰為(g'，n')，私鑰為(λ，μ)；

初始化用于選票序列號加密的SM2 公私鑰：公鑰為P0，私鑰為d0；

初始化投票智能合約：候選人名單，C(C1，C2，…，Cm)部署投票智能合約至區(qū)塊鏈。

圖3 選舉流程Fig.3 Election flow

2）選民注冊階段。

選民需要在線下官方機構(gòu)認證是否是此次選舉的合法選民。認證通過后，利用物理可信通道為選民進行注冊；

生成選民的SM2 公私鑰對(di，Pi)，隨機生成唯一選票序列號Ni；

調(diào)用SM3算法，對選民身份信息進行加鹽哈希處理，生成Esm3(Vi，Salti)，調(diào)用智能合約存儲至區(qū)塊鏈合法選民名單V=(Esm3(V1，Salt1)，Esm3(V2，Salt2)，…，Esm3(Vi，Salti))；

調(diào)用SM3 算法，對選票序列號進行哈希處理Esm3(Ni)，調(diào)用智能合約存儲至區(qū)塊鏈合法選票列表N=(Esm3(N1)，Esm3(N2)，…，Esm3(Ni))；

調(diào)用SM2 加密算法對Salti進行加密處理Esm2(Pi，Salti)，調(diào)用智能合約存儲至區(qū)塊鏈加鹽加密隨機參數(shù)列表S=(Esm2(P1，Salt1)，Esm2(P2，Salt2)，…，Esm2(Pi，Salti))；

選民自行保管身份信息Vi，私鑰di和選票序列號Ni。

注冊完畢后，區(qū)塊鏈上存儲的信息為：

調(diào)用zk-SNARKs算法生成后續(xù)零知識證明需要的公示參數(shù)CRS，寫入?yún)^(qū)塊鏈公示。

3）投票階段。

選民在終端使用以太坊賬號登錄。

選民讀取存儲在區(qū)塊鏈上的S，獲取對應(yīng)的Esm2(Pi，Salti)，通過SM2 解密算法獲得處理身份信息的Salti：Dsm2(di，Esm2(Pi，Salti))。

選民調(diào)用SM3 哈希算法計算得到Esm3(Vi，Salti)，讀取存儲在區(qū)塊鏈上的選民身份信息集合V，調(diào)用基于zk-SNARKs選民身份證明算法生成證明字符串proofVi：證明Esm3(Vi，Salti)屬于選民集合V。

選民選擇對應(yīng)的候選人Cj，然后生成選票Balloti=(ViC1，…，ViCj，…，ViCm)，如：(0，…，1，…，0)；調(diào)用基于zk-SNARKs 選票合法性證明算法生成proofBi，證明選票合法；調(diào)用基于Paillier 加密體制的選票加密算法對選票進行加密獲得EP(g'，n'，Balloti)；調(diào)用SM2 加密算法對選票序列號進行加密獲得Esm2(P0，Ni)。

選民將選票信息塊Mi發(fā)布至區(qū)塊鏈即完成投票環(huán)節(jié)：Mi=(Ep(g'，n'，Balloti)，proofBi，proofVi，Esm2(P0，Ni))。

投票結(jié)束，所有選票信息塊為M=(M1，M2，…，Mn)。

4）計票階段。

整個計票流程寫入智能合約，當(dāng)計票環(huán)節(jié)開始時，自動調(diào)用智能合約進行以下流程：獲取區(qū)塊鏈上所有選票信息塊列表M，通過zk-SNARKs 驗證算法驗證每張選票對應(yīng)證明信息proofBi、proofVi是否合法 ；通 過 SM2 算法解密Dsm2(d0，Esm2(P0，Ni))獲得Ni，驗證Esm3(Ni)是否屬于N；若兩項驗證都通過即證明該張選票合法，Ni只能使用一次，證明該張選票合法后，對應(yīng)的Esm3(Ni)失效。

利用Paillier 算法加法同態(tài)性質(zhì)計算獲得候選人(C1，C2，…，Cm)的票數(shù)(t1，t2，…，tm)，公布選舉結(jié)果。

選舉結(jié)束。

3 實驗與結(jié)果分析

本文采用以太坊Rinkeby 測試鏈作為去中心化數(shù)據(jù)庫，Web 端通過Web3j接口與鏈上智能合約進行交互。實驗條件為：64 位操作系統(tǒng)Windows10，內(nèi)存為16 GB，CPU 為Intel Core i5-7300HQ 2.5 GHz。實驗?zāi)康模?）驗證該去中心化電子選舉方案的可行性；2）測試在不同選舉規(guī)模下選民身份證明算法效率以及計票效率。實驗設(shè)定選舉參數(shù)為5 位候選人，分別測試不同選民數(shù)量零知識證明proofV生成和驗證平均耗時，以及選舉結(jié)果計算耗時（每張選票平均耗時）。實驗過程中，選舉執(zhí)行流程按照智能合約的設(shè)定執(zhí)行，實現(xiàn)無需可信第三方計票機構(gòu)完成計票流程。實驗結(jié)果表明，隨著選舉規(guī)模的擴大，選民身份證明的生成與驗證耗時、選舉結(jié)果計算耗時增加，該方案適用于小規(guī)模選舉應(yīng)用場景。測試結(jié)果如圖4所示。

圖4 不同選民數(shù)量各環(huán)節(jié)耗時比較Fig.4 Time comparison of different stages with differentnumber of voters

匿名性 區(qū)塊鏈具有一定匿名性，所有用戶都通過以太坊賬戶地址進行交易，對選民身份進行了第一次隱藏；基于zk-SNARKs 實現(xiàn)的身份隱藏算法生成proofV對身份信息Vi進行二次隱藏。攻擊者無法通過寫入?yún)^(qū)塊鏈的身份證明proofV追蹤具體的選民。選民在不暴露身份信息的情況下實現(xiàn)合法性證明，實現(xiàn)了選舉的匿名性。

選票的隱私性 該選舉方案中通過Paillier 密碼體制加密選票，通過zk-SNARKs 算法生成選票合法性零知識證明proofB，攻擊者無法通過proofB獲取任何信息。且相較于基于乘法同態(tài)、全同態(tài)選舉方案，Paillier 算法加法同態(tài)計算效率更高。

健壯性 非法選民不能破壞系統(tǒng)的正常運行。測試環(huán)節(jié)中，針對投票、計票階段進行攻擊測試。構(gòu)造非法選民Vh(h?(1，2，…，n))寫入非法投票信息塊Mh，計票環(huán)節(jié)驗證非法身份證明proofVh無法通過，非法選票被丟棄。只有合法有效的投票才能被正確地統(tǒng)計。選舉數(shù)據(jù)存儲在區(qū)塊鏈分布式數(shù)據(jù)庫中，單一節(jié)點損壞不影響系統(tǒng)正常運行。

可驗證性 整個選舉過程的數(shù)據(jù)都公開寫入?yún)^(qū)塊鏈，任何投票者都可以檢驗自己的選票是否已經(jīng)被正確計入，也可以驗證區(qū)塊鏈上任意一張選票的投票信息塊Mi的proofV、proofB的合法性，實現(xiàn)了公開可驗證。

4 結(jié)語

本文針對電子選舉主要的兩個矛盾點，設(shè)計了基于區(qū)塊鏈的去中心化安全電子選舉方案。通過零知識證明算法zk-SNARKs 實現(xiàn)了選民身份隱藏，通過Paillier 算法實現(xiàn)了選票信息隱藏，切斷了公布的選票信息與每張選票具體持有選民這二者之間的直接聯(lián)系；通過智能合約實現(xiàn)自動計票，無需可信第三方計票機構(gòu)。但是實驗表明由于零知識證明算法和同態(tài)加密算法限制，隨著選民規(guī)模的擴大，驗證與計算的速度降低，僅適用于小規(guī)模選舉。如何實現(xiàn)去中心化、高效率的大規(guī)模選舉是今后的研究方向，可以對零知識身份證明算法和同態(tài)計算進行進一步研究。