基于区块链的公平和可验证电子投票智能合约

刘 红，张靖宇，雷梦婷，肖云鹏

重庆邮电大学软件工程学院，重庆400060

电子投票面临的主要挑战是同时实现两个对立的目标：投票的隐私性和可验证性。以往的研究大多数使用简单加密技术实现电子投票。然而，文献[1] 证明使用加密技术的投票机器在90 min 内被攻破，导致用户隐私泄露。这一现象引起了人们对电子投票安全性的关注，因此，如何设计安全公平的电子投票协议是一个具有挑战性的问题。

各国学者对区块链技术的研究使电子投票协议得到了广泛的应用，尤其是在信息安全领域[2-3]。智能合约[4-5]是在区块链上运行的程序，由相互不信任的节点正确执行，无需外部可信机构。因此，基于区块链的电子投票是解决目前存在问题的一种选择。文献[6] 设计了比特币投票问题的协议，通过对投票者的投票行为实施激励机制来保证公平。虽然该方案有一定的局限性，但这是将电子投票和区块链联系起来的首次尝试。文献[7] 将比特币区块链作为匿名公告板，与盲签名协议相辅相成来实现安全和匿名的电子投票。区块链上也有很多电子投票应用，这些应用程序使用区块链作为投票箱，依靠可信的机构来保护投票者的隐私。基于区块链的自计票协议在隐私性和安全性方面得到了改善，但目前仍存在一些挑战。

在自计票方案中，最后的用户计算选票数早于其他参加投票的用户，这会引发公平性问题，从而进一步引起适应性问题和中止性问题。适应性问题指对计票结果的了解可能会影响最后一位投票者的投票方式。文献[8] 提出由投票管理机构进行最终的投票，但其投票结果不计入最终的计票结果中。他们引入不可信赖的合作机构，可能存在该机构和最后一个投票者合谋的情况。中止性问题意味着当他们对已知的总票数不满意时可以弃权，这种行为使得投票被迫暂停，无法计算最终的票数。

自计票方案存在重放攻击威胁。在选票交易广播的过程中，攻击者截取交易信息，篡改信息，形成重放攻击。投票者可能尝试复制和修改自己的选票或者注册相同的投票密钥，通过重放密钥和零知识证明，实现复制目标投票者的选票。恶意的管理者可能和候选人勾结篡改选票或最终的计票和。恶意的攻击者试图拦截他人选票形成重放攻击。

自计票方案存在验证问题。在计票的过程中，投票管理员可能对结果进行修改，比如抛弃部分选票或者添加虚拟的选票等，从而无法保证计票结果的唯一性。

本文的主要目的是解决自计票协议存在的公平性缺陷和重放攻击问题，同时实现个人可验证、资格可验证和普遍可验证。个人可验证保证选票不被篡改且包含在最终的计票结果中。资格可验证指的是对投票者的资格进行检查，保证选票只能由合格的用户生成。普遍可验证确保计票结果是唯一的，任何人都可对结果验证。本文的主要研究工作和贡献如下：

1）设计无需可信第三方的电子投票方案。区块链作为公告板存储交易信息，同时设计部署智能合约到区块链，代替投票规则，其中包括时间戳和财政激励。电子投票最终的目的是计算选票和，采用Paillier 算法加密数据，在克服公平性缺陷的同时提升加解密效率。

2）设计基于Merkle 树结构且隐藏身份信息的验证方案。规定每个投票者负责自己的密钥生成，构建基于地址公钥的Merkle 树来证明投票者身份的合法性且保证交易数据不被篡改。同时利用哈希函数生成随机序列防止重复投票。对单个用户验证时无需下载所有节点数据，减少了计算量。

3）设计基于zk-SNARK 的选票数据有效零知识证明。将需要证明的选票合法问题转化为在多项式时间内验证特定解是否正确的问题。在保证加密和证明数据的一致性的前提下，实现基于算数电路的验证。通过连接性将加密算法从零知识证明电路中抽离进行，减少电路的大小，从而提升性能，并且证明者不会泄露验证数据的信息。

目前已有的电子投票方案大多存在公平性缺陷且无法同时满足个人可验证、资格可验证和普遍可验证性。本文提出的无可信机构的可验证的自计票方案（without trusted-authority self-tallying verifiable scheme,WTSV），与具有最大选民隐私的董事会投票智能合约VOTE[9]、分散式博尔达计票智能合约系统BC[10]和无可信计票机构的在线投票系统PV[11]方案安全性对比分析情况如表1 所示。

表1 现有方案安全性对比Table 1 Security comparison of existing solutions

1 相关工作

电子投票的目的不仅是决定结果，也是为了保证投票者和候选人之间的信任。这就强调投票的自由、公平和秘密选举的必要性，并且保证在没有可信第三方的参与下选举是公开和可信的。

通常，保护选民隐私的投票协议依赖可信第三方，以验证的方式对选票进行加密和解密。当前，很多使用区块链进行电子投票的协议已经被提出，但是大多数方案都是将区块链作为公告板，仍然使用可信的权威机构来保护选民和选票的隐私。比如Blockchain Voting Machine[12]、Follow My Vote[13]和TIVI[14]等公司提出了使用区块链作为投票箱来存储选票的解决方案[11]。文献[12] 提出一种结合Zerocoin 和比特币平台的电子投票方案。由于比特币系统不具有匿名性的特点，通过Zerocoin 来实现电子投票系统的匿名性。文献[13] 提出了一个独立于区块链平台的电子投票系统，利用环签名技术设计了基于智能合约的可验证电子投票系统。文献[14] 提出了一个分布式的匿名电子投票系统，将选票信息存储在区块链公告板上。这些解决方案仅是将区块链作为不可篡改的全局数据库来存储投票结果，都是在可信机构的参与下保证选民隐私。

自计票协议将计票转化为一个开放的过程，在投票结束后，任何用户都可以计算投票结果，这就取消了计票机构在投票中的作用。公平性意味着没有人有优先权提前计算中间结果，但是自计票协议存在公平性缺陷，因为最后一个投票者可以先于其他人计算结果。这样就会导致适应性问题和中止性问题。

文献[8] 首次提出了一种用于董事会的自计票协议，该方案的提出使得小规模的电子投票无需任何可信第三方的介入。在投票过程中，投票者的行为普遍可验证，使得投票的私密性得到一定的保障。但是该方案需要很大的计算量和通信量。随后文献[15] 在文献[8] 所提方案的基础上进行了改进，提高了效率，降低了计算量。上述两方案都仅适用于小规模的双候选人电子投票，这样一来投票的效率就受到很大的制约。2017 年，文献[9] 首次提出了使用区块链实现最大隐私保护的去中心化和自计票电子投票协议。该方案实现了隐私保护和安全可验证，适用于董事会选举，但是计算开销很大。此外，自计票协议自身存在公平性缺陷。对于公平缺陷中的自适应问题，该方案在投票过程中增加了一个可选阶段来解决自适应问题，但这使得协议变得更加复杂。对于中止性问题，该方案在注册阶段设置了保证金，但这就增加了额外的系统预算。文献[10] 提出一种分散式的博尔达计票智能合约系统，该方案的提出保证了选民的隐私，但该方法在安全性方面还存在一些问题，其无法做到普遍可验证。文献[11] 提出了一种无可信计票机构的普遍可验证在线投票方法，但该方案可验证加密和解密时间花费较高，且无法抵御重放攻击，安全性方面有一定缺陷。文献[16] 提出了一种基于区块链的去中心化物联网自计票TALLY 协议，并使用一系列零知识证明解决了中止性问题，但该协议仅支持2个投票选项，因此适合于小规模投票应用，且未考虑选民的隐私。文献[17] 提出一种基于区块链的可追踪自计票电子投票系统，该协议利用同态时间锁谜题实现了自动计票，同时保证了选票的保密性。该方案还构建了一个面向事件的可链接组签名，以保护选民的隐私并防止重复投票。

2 方案概述

2.1 系统模型

系统框架是基于区块链的电子投票，投票者和发起者通过区块链进行交互。图1 为本方案的系统框架，主要包含以下三个部分：

图1 系统框架图Figure 1 System framework diagram

1）选民。作为该方案的投票者，负责构建选票信息块，将其加密文件和证明一起发送到区块链。首先投票者注册地址密钥对，将地址公钥作为投票资格发送到公告板。然后，投票者加密选票并生成身份合法和选票有效零知识证明，将得到的结果集广播到区块链。

2）投票发起者。本次投票的发起者，不是所谓的权威机构。首先初始化投票信息，部署智能合约。其次，收集区块链上的地址公钥得到投票者白名单，构造白名单集合对应的Merkle树。将选票有效问题转化为算数电路可处理的数学模型，将得到的公共信息广播至区块链公告板。

3）区块链。存储选票信息，使用智能合约进行验证和结果计算。首先作为公告板存储公开可用的信息，如地址公钥、白名单、选票。其次对提交至区块链的选票信息进行验证，调用智能合约对交易密文进行解密计算并将得到的结果返回给客户端。

图1 为本方案的系统框架图，主要包含注册阶段、初始化阶段、投票阶段和计票阶段。定义本方案WTSV 主要有以下几个算法组成（Register,Setup,Vote,Tally）：

1）注册阶段。参与投票的选民登录自己的以太坊账户，并注册获得地址密钥对，将得到的公钥广播到区块链公告板。

2）初始化阶段。投票发起者初始化选举信息，通知选举开始。首先收集选民pkID构造白名单pklist。其次，初始化选票验证信息。

3）投票阶段。合格选民依据初始化信息加密选票和生成证明，主要包括身份和选票合法性证明。最后将选票信息发送到区块链公告板。

4）计票阶段。首先对提交的选票信息进行验证，包括资格可验证和选票验证两部分。其次，进行计票并将结果公布。任何人都可以对计票结果进行验证。

2.2 威胁模型

假设存在恶意攻击者可以通过加密消息学习敏感信息。现有攻击可能发生在身份核查和提交选民阶段。图2 为选票交易信息泄露造成的威胁模型。

图2 重放攻击模型Figure 2 Replay attack model

加密信息是由确定性算法生成的，并且所有的信息是公开发送到公告板上的，因此敌手可以监听窃取交易信息。重放攻击包括三种情况：选民复制并重复发送选票、恶意敌手拦截并篡改选票、恶意管理员修改计票结果。详细攻击描述如下：选民在不改变传输路径的情况下，向区块链多次发送交易，形成重复投票。在选民将交易信息发送到区块链的过程中，恶意敌手截获交易块，重新加密获得新的交易信息，将其重新发送到区块链上形成重放攻击。在计票阶段，恶意管理员利用解密密钥修改计票结果或者添加额外选票。

2.3 系统目标

研究发现可验证性的无法满足将导致隐私泄露[18]。本文的目标是隐藏交易信息，克服公平缺陷，抵御重放攻击和构造基于零知识的非交互验证。非交互验证主要包括个人可验证、资格可验证和普遍可验证。个人可验证是投票者可以核实自己的选票是否包含在内。资格可验证是选票只能由具有投票权的合格投票者产生。普遍可验证意味着计票的唯一性。为了实现整体目标，本文在等权投票机制下，提出了一种基于区块链的Paillier 加密证明电子投票方案。对于交易数据加密，本方案采用Paillier 算法加解密选票数据

式中：Enc 为加密运算；Dec 为解密运算。对两个密文的乘积解密得到对应的明文之和。

基于zk-SNARK 算法实现投票者身份隐藏证明和选票合法性验证。通过在zk-SNARK中构造Merkle 树，将投票者身份信息隐藏在零知识证明中。参考Zerocash[19]的例子，使用隶属度证明来量化投票者资格验证

式中：(skID,pkID) 为地址密钥对；rt 为Merkle 树根；H(skID) 表示利用哈希函数生成地址公钥；copath 为构建Merkle 树的路径向量；sn 作为随机数用来预防重复投票。本文通过最小化数据下载量和验证计算量来实现目标。因此，当证明一个选民存在白名单时，只需要得到从该叶子节点到根的路径copath，不需要所有叶子节点参加，减少了计算量。

zk-SNARK 技术可以将隐私保护信息压缩成简洁证明，提升验证的效率。由于zk-SNARK无法直接应用于实际问题，必须有量化的输入，需要将实际待验证问题转化为特定输出的数学模型。本方案要求所有的投票者只可以选择一名候选人进行投票，将此需求转化为以一个可计算的问题，即存在一个程序，其输入为选票数据vicj。如果选民没有选择候选人，则输出结果为0，否则为1。在初始化条件下，用户没有选择任何候选人。针对选民vi的投票情况，定义初始化表达式值为0，即

式中：vicj表示第i个选民选择第j个候选人；n表示选民数量；m表示候选人数量。本方案要求每个用户仅可选择1 名候选人进行投票，因此式(3) 的最终结果只有在1 的情况下才符合选票合法要求。在证明阶段，可以通过式(3) 的成立实现选票合法验证。

3 WTSV 方案详细描述

本文通过隐藏选票信息和保证身份数据的安全可验证来实现自计票。图3 为本方案具体投票场景。为了消除可信第三方的介入，本文利用区块链作为公告板存储交易信息，同时在区块链上设计部署智能合约保证选举按预期规则进行。利用Paillier 算法加密选票，在加密选票的同时生成身份和选票数据证明，将密文和证明作为交易信息块广播到区块链。

图3 投票框架图Figure 3 Voting framework diagram

接下来，将进行本文所提出方案的具体细节描述，主要包含注册阶段、初始化阶段、投票阶段和计票阶段。表2 为本方案涉及的变量参数解释。

表2 参数解释Table 2 Parameter explanation

3.1 注册阶段

在调查研究中发现，现有的投票协议需要权威机构负责密钥颁发，这将导致授权机构从投票交易中发现投票者身份。基于隐私保护，本文规定投票者对自己的密钥负责。

为了更好地保护用户隐私，用户使用以太坊账户地址ID 来标识每个投票者的身份。每个地址ID 只可以完成一次注册，并且每个注册账户仅可以进行一次投票。选择常数1，将1λ作为安全参数，生成随机私钥sk，利用ID 和私钥组合得到地址私钥skID。利用抗碰撞哈希函数生成地址公钥pkID=H(skID)。确保每个参与投票的选民账户都有一定数量的以太币，可以通过购买和挖矿获得。在注册阶段，所有用户存储一定数量的以太币到智能合约作为财务激励。在投票结束后智能合约会自动退款到账户，任何在投票截止前中止投票的选民都将失去押金。

3.2 初始化阶段

为了更好地实现可验证和隐私保护，使用Merkle 树结构来隐藏选民身份和基于zk-SNARK 算法的选票有效零知识证明。主要包含两部分：初始化Merkle 树和数学模型构建。

3.2.1 Merkle 树初始化

首先，投票发起者初始化选举信息，利用选民公钥集合PK={pk1,pk2,···,pki},i ∈n，构造参加选举的选民名单pklist。然后进行Merkle 树的构造，对于叶子节点pkID，使用哈希对其进行编码得到真实数据的哈希值。非叶子节点存储2 个子节点组合的哈希值，重复向上散列，直到得到根节点rt=GetMerkleRoot(pklist)。

3.2.2 数学模型构建

由于zk-SNARK 不能直接用于任意问题，必须有量化的输入。因此将选票有效问题转化为zk-SNARK 可以处理的数学模型。具体描述如下。

首先将算数逻辑方程转化为算数电路验证。选民需要在不暴露选票vicj的情况下证明选票有效，则算数逻辑表达式为

为了将方程式转化为算数电路，将其分解为加法组成的最小操作，通过增加中间变量将其转化为门电路表示，式(4) 对应的门电路表示为

式中：svci表示中间门电路的输出；vicj表示第i个选民选择第j个候选人；out 是最后的输出结果。当输出的结果为1 表明选票合法，输出为0，则不合法。对应的电路如图4 所示。

图4 选票合法性电路Figure 4 Vote legitimacy circuit

从图4 中可以看出，证明者和验证者作为2 个角色分开执行。算术电路的输出是特定投票者的输入通过证明电路计算得到的。上述算术电路转化为QAP[20](quadratic assignment problems)，QAP 定义如下。

给定一系列多项式{li(x),ki(x),di(x)}，其中i ∈(0,1,···,n)，是否可以根据这一系列多项式，求得它们的一个线性组合{ai},(i ∈(0,1,···,n))，刚好可以整除目标多项式t(x)

将图4 中的变量定义为一组集合向量s

式中：one 表示一个常量1；vicj为算数电路的输入，即选票；svcj为中间门电路的输出；out为整个电路的输出。以门电路vic1+vic2=svc1为例进行转换，存在一组向量(y,z,k) 满足

根据式(8) 和(9)，可以得到如下多项式组：

将向量(y,z,k) 代入sy×sz-sk=0 中计算可以得到one×(vic1+vic2)-svc1=0，转换后的表达式和原始门电路vic1+vic2=svc1相等。对于电路中存在的其他门电路，通过上述方法都可以得到对应的向量组，并将其转化为相应的向量表达式。

上述描述是针对特定门电路vic1+vic2=svc1说明。从图4 中可以观察到存在多个门电路，即存在多组向量。利用拉格朗日插值公式将向量表达式转化为多项式，将所有向量看作是一个多项式的解。以门电路vic1+vic2=svc1为例，基本多项式y(x) 的某一个解是向量y的系数，可以通过多项式数组y(x)、z(x)、k(x) 来确定门电路对应的向量组。为了方便计算，定义多项式V(x) 为

为了满足QAP 定义，假设存在目标多项式H(x)=0，T(x)=(x-1)···(x-v)，可以整除V(x)。从而得到验证的QAP 方程式为

通过验证满足式(12) 来证明提交的选票信息是合法的。此外，利用公共参考字符串模型[21]（common reference strings,CRS）实现非交互式证明。利用zk-SNARK 中的CRS 结合预先定义的资格可验证和选票有效关系，生成CRS¬Πzk-SNARK·Setup(relation)。智能合约调用加密算法，生成加密所需的投票密钥对(pkenc,skdec)，其中加密公钥为pkenc=(g,n)，解密私钥为skdec=(λ,µ)。

3.2.3 智能合约模型构建

根据投票方案的功能，本方案设计智能合约包括投票合约和密码合约。

1）投票合约。投票协议逻辑，主要包括初始化选举时间戳、获取候选人列表、收集选票等。具体设计如表3 所示。

表3 投票合约设计表Table 3 Voting contract design

2）加密合约。包含创建和验证协议的零知识证明。投票所需的证明在本地生成，目的是确保所有选民都能使用相同的加密算法。具体设计如表4 所示。

表4 密码合约设计表Table 4 Cryptographic contract design

3.3 投票阶段

投票过程主要包括对选票加密和证明构造两部分。为了更好地隐藏选票，采用Paillier 算法加密，同时构造基于zk-SNARK 的零知识证明。图5 为加密证明构建过程。

图5 加密证明构建过程Figure 5 Cryptographic proof construction process

3.3.1 基于zk-SNARK 的零知识证明

选民需要在加密选票的同时构造零知识证明，主要包含两部分：身份证明和选票有效证明。下面详细介绍证明构造过程。

首先构造身份证明。选民登录以太坊账户，利用copath←GetMerklePath(pkID,pklist)得到从地址公钥pkID到根节点的认证路径copath，利用rt←MerkleTree(pkID,copath) 获得树根rt。

其次，构造选票有效证明。利用抗碰撞哈希函数生成随机数sn=Hsn(skID) 来保证选票的唯一性，抵御中间人攻击。采用椭圆曲线配对，实现式(12) 的乘法同态。对于明文m1和m2来说，加密后的密文存在如下等式：

为了实现非交互式零知识，采用CRS 模型。生成器随机选取随机数(α,β,γ,δ) 形成CRS，并将其公开。选民读取CRS，利用椭圆曲线的同态性质计算生成选票有效证明π，其中(α,β,γ,δ) 来自随机参数CRS。

选票有效性证明转化为待验证的多项式，即证明多项式sy(x)×sz(x)-sk(x)=T(x)H(x)的成立。选民可以得到各多项式数组对应的α对，假设选民待证明的信息为m，通过α对计算得到如下证明：

因此，选民生成待验证多项式中每个多项式对应的证明，选民将生成的α对作为整体的证明π发送到区块链，具体为

3.3.2 选票加密

选民利用Paillier 加密体制的选票加密算法，使用加密公钥pkenc加密选票获得密文CT=Enc(vicj)。候选人可以收集加密的选票，候选人cj的选票加密为

式中：v1cj+v2cj+···+vicj表示候选人j的所有选票和；n′表示两个大小相近的大素数的乘积；r是在条件0

3.3.3 区块链节点验证选票

在计票之前，区块链节点验证每张选票，主要包含两部分：验证选票是否由合格的选民生成、选票是否有效。

首先进行身份验证。区块链节点获取选民提交的Merkle 根rt 进行验证。当验证值和初始化树根的哈希值一样，即选民是在选民名单中的。

利用sn 检测重复投票，如果sn 满足sn∈Blockchain，则表明该身份对应的选票已经存在，直接中止该交易数据块。利用椭圆曲线的α对特性进行多项式盲验证，验证选民提交的证明π是由初始化定义的多项式计算生成。已知配对函数定义为

基于多项式特性，在进行投票合法验证的过程中，仅需要随机选择作用域内的任意一点进行验证。以sy(x) 为例，通过验证式(17) 和(18)，可以验证E(sy(x)) 和E(αsy(x)) 满足α对的特性，从而在不暴露隐私的情况下证明选票有效性：

此外还需要证明多项式(21) 是成立的。

式中：P(x)、Q(x) 为QAP定义中的目标多项式。

3.4 计票阶段

当参与投票的所有选民都将交易消息发送到区块链后，通知智能合约开始计票。由于Paillier 加密算法满足加同态，对密文的乘法运算可以直接得到明文和。以候选人cj为例，通过私钥解密计算可以得到最终的明文计票和Msum,cj

式中：(v1cj,v2cj,···,vicj),i ∈(1,2,···,n),j ∈(1,2,···,m) 表示选择候选人j的所有选票。在解密计算的过程中，生成解密证明v。在计票结束后，将解密证明和计算结果(Msum,v) 发布到区块链，任何人都可以通过解密证明对计票结果进行验证。

式中：r为随机整数；skdec为私有的解密密钥；生成解密证明为v。投票者vi对计票结果(M,CT,v) 进行验证，其中M=(m1,m2,···,mn)，CT=(c1,c2,···,cn)。因为解密证明是可验证的，因此不存在任何解密证明满足错误的密文，即

投票者利用地址私钥生成的随机序列sn 是唯一的，当提交的密文被篡改时，则存在重复且不唯一的随机序列sn。如果密文解密后仍为原始消息，表明选票没有被篡改。

为了确保最终的解密结果是正确的，基于符合剩余类问题可以对计票结果进行验证，根据Cmrmichael’s[22]定理可得

通过关系(1+n)x=1+nxmodn2将公式转化为

最后，利用L(X) 函数可以得出解密结果是正确的

4 安全和性能分析

4.1 安全性分析

在文献[23] 提出的选票隐私定义的基础上，对本方案的安全性进行评估。在整个投票过程中，如果存在恶意的节点进行联合来截取选票信息，进一步伪造选民的身份进行投票。本方案在满足公平性的基础上，实现身份可验证、个人可验证和普遍可验证。所有的选票在进行计票前都需要进行身份和个人可验证，如果恶意的节点形成重放攻击，则形成的选票信息中验证身份的随机数可能发生改变，并且新构建的Merkle 树根也无法对应原始数据。因此，本方案可以有效地避免恶意节点形成的重放攻击。

4.1.1 投票隐私

定理1 恶意的敌手无法篡改选票信息。为了证明投票隐私，定义攻击者A和投票发起者D之间的隐私保护游戏GameBP。主要目的是让敌手A在完全控制选民的前提下构造2 个不同的投票集合。投票隐私满足敌手无法区分加密选票。对于任意的概率多项式时间(PPT)敌手A，如果存在一个可忽略函数negl(λ)，使得

证明以下构造表示敌手赢得游戏。使用用来假设投票发起者D模仿敌手A的行为。具体细节如下：

初始化投票发起者D开始游戏GameBP，并通过向敌手A输出CRS 初始化选举，敌手A构造所有投票者地址密钥对集合给投票发起者D。

开始投票基于地址公钥集合构造选民白名单pklist 和Merkle 树根rt，通知选举开始。

计票在挑战结束后，投票发起者D返回计票结果Msum和解密证明v。

4.1.2 资格可验证

定理2资格可验证是区块链节点检验选民身份和投票的有效性，保证选票只能由合格的选民产生。假设敌手加密后将选票交易{CT,sn,rt,π}并发送到区块链，区块链节点对选票进行验证。在snBlockchain 前提下，如果敌手提交通过资格验证的投票的概率可以忽略不计，则表明协议满足资格验证。

证明假设敌手构造的选票通过资格可验证，则验证信息满足

本方案规定选民对自己的密钥对负责，因此敌手的公钥不可能存在于pklist。在H(skID)=pkID的前提下，敌手提交的选票经过验证无法得到rt′=rt。表明敌手不在合格的选民列表中，从而无法满足资格可验证的条件。

4.1.3 个人可验证

定理3个人可验证性指的是选民确保发布的选票是自己的原始信息。假设H表示长度为ℓ的哈希函数，为敌手私钥，并且敌手提交的选票{CT,sn,rt,π}解密后无法得到原始的明文Dec(CT)M。如果对于任意的多项式时间敌手A，存在一个可忽略的函数，使得则表示本方案满足个人可验证，其中表示敌手A破坏哈希函数抗碰撞或加密的健壮性的概率。

第2 种情况，如果选民的原始选票被修改，即Dec(CT)M，则表明敌手破坏了加密的健壮性。

4.1.4 普遍可验证

定理4 普遍可验证意味着计票的唯一性，任何人都可以对计票结果进行验证。在输入密文不为原始选票的情况下，通过可验证解密的概率是可以忽略的，表明该方案满足普遍可验证

式中：Verify_Dec(VK,CT,M,v)=1 表示有效的解密。

证明假设敌手在计票阶段篡改选票，即对于密文CT=(c1,c2,···,cn) 和明文M=(m1,m2,···,mn)，存在一个密文块ci无法解密为明文mi。计票结束后公布解密结果和解密证明{Msum,v}，因为解密证明是有效的Verify_Dec(Msum,CTsum,VK,PK,V)=true。如果密文块被修改，解密无法得到原始明文信息Verify_Dec(Msum,CTsum,VK,PK,V)=false，与敌手提供的解密结果相矛盾。无法在选票信息篡改的情况下表明计票结果正确，从而保证本方案WTSV 满足普遍可验证。

4.2 性能分析

本节对基于Paillier 同态加密和基于配对非交互式零知识证明的以太坊区块链投票进行性能分析。

4.2.1 通信和存储开销

每个选民发布公钥pkID和选票交易|V|=ck+pk。假设公钥长度为常数c，选民人数为n，因此所占空间大小为nc+n|V|。假设密钥对大小为常数p，投票发起者公布加密和验证密钥对2kp，所有人使用相同的密钥对，参与选举的候选人人数即为生成次数。假设密钥对大小为常数p，部署一次智能合约到以太坊，合约大小为tbit，所占空间大小为2tbit。每个选民存储私钥和验证选票信息skID+|V|，以太坊客户端存储交易n|V| 和得到的解密信息k(ncd+1)。

4.2.2 计算开销

假设参与选举的候选人数为m，选民人数为n。初始化阶段投票发起者需要进行m次运算来生成加密密钥对，另外还有m个对应的验证密钥对，生成密钥对时间复杂度为O(klb2(p))，其中p为大素数。投票阶段，每个选民需要1 次幂运算加密、Hash 运算和Merkle树的构造，n个选民需要操作nEncv+nHash(skID)，时间复杂度为O(n)。区块链节点对提交的每笔交易信息进行验证。计票阶段仅需投票发起者对所有选票的密文和进行解密，即进行m次，时间复杂度为O(m)，总的时间开销为knDec+nProve。

如表5 所示，本方案与实验对比方案在存储开销、通信开销以及计算开销的分析比较。VOTE 协议分两轮执行，在第一轮中选民需要计算一次指数运算和NICK 的零知识证明。在第二轮中，进行一次加密的幂运算和1/m的零知识证明。BC 协议也是分两轮进行，第一轮选民需要进行m次幂运算和k次证明，第二轮采用和VOTE 相同的方法进行。

表5 性能分析Table 5 Performance analysis

5 实验评估

5.1 实验设置

本文采用以太坊测试链作为区块链框架，Remix 编辑器编译部署智能合约。Web 端通过Web3.js 提供的API 接口和链上智能合约进行交互。采用Metamask 钱包和Ganache cli测试网络创建，管理账户，并且模拟客户端交易行为，实现完整的投票交互过程。实验条件为：64 位操作系统Windows 10，Inter Core i5-10210U 3.7 GHz 的CPU。在进行非交互式零知识证明的实验中，参考了Groth16[24-25]，使用了Jsnark 和Libsnark[26]开源系统库提供的第三方代码。选举过程涉及的Hash 函数参考了Ajtai 函数[27]，每张选票的加密采用加同态加密算法。

5.2 实验结果评估

在实验中，对提出方案的时间和成本消耗进行评估，并与现有方案进行比较。通过调试不同数量的投票者，对时间和成本消耗进行统计分析，对所得的结果进行matplotlib 仿真。本文主要从选举各阶段进行分析比较。

5.2.1 投票时间

每个选民构造加密选票和零知识证明，其中证明包括身份验证和选票有效性证明。首先评估加密和证明生成时间，图6 为选票加密时间和选民人数的变化关系图，图7 为证明生成时间和选民人数的关系图。

图6 加密时间和选民人数Figure 6 Encryption time and the voters count

图7 证明生成时间和选民人数Figure 7 Proof generation time and voters count

从图6 和7 中可以得知，选民人数为8 时，本文方案WTSV 加密选票仅需要3.8 ms，证明生成需要5.2 ms。方案TALLY 加密需要9.4 ms，证明需要3.8 ms。方案PV 加密需要10.4 ms，证明需要17.8 ms。方案BC 加密需要28.0 ms，证明生成为26.9 ms。方案VOTE需要的时间最多，加密需要20.4 ms，证明需要35.9 ms。在选民人数为20 的情况下，本方案WTSV 的加密和证明时间分别为8.9 ms 和9.7 ms。方案TALLY 加密需要14.3 ms，证明需要10.8 ms。方案PV 加密需要18.7 ms，生成证明需要40.1 ms。方案BC 加密花费时间为51.9 ms，证明生成时间为59.8 ms。方案VOTE 需要的时间最多，加密需要41.4 ms，证明需要70.3 ms。

本方案通过构造Merkle 树的路径、树根以及生成随机数，来证明身份的合法性和选票的有效性，使用加同态加密算法加密选票，对比方案采用Elgmal 加密算法。PV 方案投票阶段包含三部分：预计算、投票和证明生成。将Elgmal 加密和基于组的加密结合使用，实现对选民隐私的保护。在提交前生成部分知识证明(PKP) 和零知识证明(ZKP) 两种证明，PKP 用于证明选票在合理的范围，ZKP 用于证明选票正确加密，相比于本方案操作复杂，花费的时间较多。BC 方案是在VOTE[9]的基础上完成的，分两轮进行，进行两次NIZK 零知识证明的生成。除此之外，在投票前需要将选票的哈希值作为承诺发送到区块链，从而增加了投票时间。从图6 和7 可以发现，本方案WTSV 比对比方案在加密和证明生成上花费的时间都少，甚至在加密部分比BC 方案快5 倍。

5.2.2 可验证加密

区块链节点验证提交的选票是否合法且未被篡改，选民对提交至区块链的选票进行个人可验证。由于BC 不包含可验证加密，因此不进行此部分比较。图8 为本方案WTSV 和对比方案可验证加密花费时间和选民数量的关系。

图8 可验证加密时间和选民人数Figure 8 Verifiable encryption time and voters count

从图8 中可以看出，选民人数为12，本方案WTSV 可验证加密时间消耗为25.6 ms，TALLY 方案为32.5 ms，PV 方案为36.3 ms，VOTE 方案为43.7 ms。在选民人数为20时，本方案WTSV 的验证时间为39.2 ms，TALLY 方案为48.9 ms，PV 方案的时间为58.9 ms，VOTE 方案为48.7 ms。本方案WTSV 可验证加密包含区块链节点验证和个人可验证两部分，区块链节点通过检验Merkle 树根发生修改检查选民资格，通过检查序列号sn 的唯一性保证选票的唯一性从而防止篡改和重复投票。PV 方案不论是个人可验证还是区块链节点验证都需要进行PKP 和ZKP 两部分验证，花费的时间较高。在同等选民数量的情况下，本方案WTSV 的验证时间总是少于对比方案TALLY。

5.2.3 计票

在所有的选票提交后，投票发起者通知以太坊开始计票。图9 为计票花费时间和选票数量的关系图。

图9 计票时间和选票数量Figure 9 Counting time and voters count

当选票数量为8，本方案WTSV 的计票时间为4.2 ms，VOTE 方案的时间消耗为6.2 ms，BC 方案的时间消耗为2.1 ms，TALLY 方案的时间消耗为0.27 ms。在选票数量为20的情况下，本方案WTSV 时间消耗为14.3 ms，VOTE 方案的时间消耗为15.8 ms，BC 方案的时间花费为4.1 ms，TALLY 方案的时间消耗为3.6 ms。在PV 中计票时间随着候选人数的变化而变化，与投票者的数量无关，时间消耗固定为0.25 ms。计票时间取决于选票数量以及解密算法。本方案WTSV 使用Paillier 加同态加密，解密时仅需要进行一次幂运算，对所有的密文和进行解密即可得到最终的计数。对比方案TALLY、PV 和BC 都使用Elgamal 加密算法。BC 在计票阶段对每个候选人的每一张选票采用暴力搜索的方式进行计算，在选民数量较少的情况下可行，一旦选民数量超过一定范围，时间将无法估计。本方案计票时间花费比对比方案消耗大，主要是因为本方案在计票的同时会生成相应的解密证明在普遍可验证阶段使用，计票阶段花费的时间较长。

5.2.4 可验证解密

在计票结束后，任何感兴趣的第三方都可对解密结果进行验证。图10 为普遍可验证时间和候选人数量的关系图。

图10 可验证解密时间和候选人数量Figure 10 Verifiable decryption and candidates count

从图10 中可以得知，当候选者人数为8，本方案WTSV 的验证时间为2.4 ms，方案TALLY 的验证时间为2.6 ms，方案PV 的验证时间为3.7 ms，方案VOTE 的验证时间为6.8 ms。在人数为20 的情况下，本方案WTSV 的验证时间为3.6 ms，方案TALLY 的验证时间为5.1 ms，方案PV 的验证时间为10.1 ms，方案VOTE 的验证时间为14.9 ms。本文使用加同态加密算法，在解密时对密文和进行解密，同时生成解密证明。在验证阶段只需要通过解密证明对每位候选者的密文和进行验证，时间相比于对比方案较少。PV 方案验证时需要从区块链下载所有的选票以及相应的证明进行验证，最终和进行验证花费的时间较多。从图中可以看出，随着候选人数的越来越多，本方案WTSV 和方案TALLY 的时间差距逐渐增大，在人数为20 时快1/3 倍。

5.2.5 参数大小设置

在方案中消息块的大小决定着参数大小，其中选票作为消息块。图11 为参数和消息块大小的关系图。从图中可以看出，PK、VK 和CT 的大小随着消息块大小的增大而增大。在初始化阶段，固定关系R为选票和身份的有效性，所以在电路设计中使用到的参数CRS 的大小和交易信息块的大小无关，始终保持稳定值16 MB。

图11 参数大小设置Figure 11 Parameter size setting

5.2.6 成本消耗

图12 为选民和投票发起者平均费用和参与选举选民数量的关系图。选举过程中产生的费用由消耗量和价格两个因素决定，计算公式为：Cost=GasUsed∗GasPrice。将区块的gas 限制设置为670 万，以减少网络影响，并以当前的市场价值为基准1 eth=2 490 $，1 gas=0.000 000 02 eth。从图中可以看出，投票发起者的成本随选民人数的增加呈线性增加。由于选民每次投票只需要发送一笔交易，因此选民的成本保持不变。

图12 参与投票的用户平均费用和选民数量Figure 12 Average cost of voters and voters count

图12 为完整的投票过程中投票发起者和选民所需要花费的gas，由于智能合约包含的协议逻辑较多，在部署的过程中消耗较多的gas。图13 所示为投票发起者在选举过程中的gas消耗量。图14 所示为选民在选举过程中的gas 消耗量。

图13 管理员gas 消耗Figure 13 Admin gas consumption

图14 选民gas 消耗Figure 14 Voter gas consumption

通过在线编译器部署智能合约。投票合约包含投票协议的逻辑，加密合约包含创建和验证协议的零知识证明的代码。选民在本地计算机上进行零知识证明代码的运行。密码合约的目的是确保所有选民都能使用相同的协议和算法。表6 所示为选举过程中每项操作的gas 消耗量和消耗总量，其中gas 消耗量由交易的计算量来决定。通过发送交易模拟8 个选民参与协议来和对比方案BC 进行比较，其中选举管理员每个事务仅发送一次，每个选民也广播一次。由于智能合约包含的协议逻辑较多，在部署的过程中消耗较多的gas。表6 中可以看出，本方案在各阶段的gas 消耗量远小于对比方案。

表6 投票过程中的gas 消耗分析Table 6 Comparison of gas consumption during voting

6 结语

本文设计了基于区块链的电子投票智能合约方案，主要目的是克服公平缺陷、抵御重复攻击和实现3 种可验证。本文设计的Paillier 算法实现选票信息的隐藏，zk-SNARK 算法实现选民身份的隐藏，智能合约实现自计票。利用zk-SNARK 构造Merkle 树保证选民身份的合法性，同时生成随机序列sn 来监听选票是否重复或发生篡改。本方案WTSV 将加密的密文混入zk-SNARK 验证中，将加密算法从zk-SNARK 中抽离出来，减少电路尺寸和证明时间，提高选举效率。本方案满足选举的个人可验证、资格可验证、普遍可验证，解决自计票协议存在的公平缺陷和重放攻击问题。实验结果表明，加密单张选票的时间为0.4 ms，生成证明的时间为0.6 ms，远低于对比方案，并且初始化参数CRS 的大小固定不变，与电路中包含加密方法相比更加实用。本方案同样适用于一人多票的形式。进行一人多票的选举时，只需要将初始化阶段的算数逻辑表达式修改为待验证的即可。在后续的工作中，将进一步研究大规模选举，减少因条件约束和选民数量增加给选举系统带来的压力，增强可扩展性。