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

第41卷 第4期2023年7月应用科学学报JOURNAL OF APPLIED SCIENCESElectronics and Information EngineeringVol.41 No.4Jul.2023DOI:10.3969/j.issn.0255-8297.2023.04.001基于区块链的公平和可验证电子投票智能合约刘红，张靖宇，雷梦婷，肖云鹏重庆邮电大学 软件工程学院，重庆 400060摘摘摘要要要：针对等权投票机制中存在的公平性缺陷和重放攻击问题，提出一种基于区块链的加密证明方案。首先，将投票流程和规则写入智能合约，包括时间戳和财务激励，以保证投票按时进行。规定每个投票者负责自己的地址密钥生成，构建基于地址公钥的 Merkle 树来证明投票者身份的合法性且保证交易数据不被篡改。同时利用哈希函数生成随机序列预防重复投票。其次，考虑到最终目的是得到求和结果，利用区块链公告板和 Paillier 算法加密存储选票，在克服公平性缺陷的同时提升加解密效率。最后，考虑到交易合法性和计算结果准确性问题，利用区块链的不可篡改特性，构造基于 zk-SNARK 的零知识证明。将需要证明的现实问题转化为特定输出的计算问题，将加密算法从零知识证明电路中抽离，不会泄露验证数据的信息。理论分析和实验结果表明，所提出的方案与已有方案相比显著提高了投票的安全和隐私，且具有更低的时间开销和成本消耗。关键词：区块链；智能合约；零知识证明；Paillier 算法；投票协议中图分类号：TP309文章编号：0255-8297(2023)04-0541-22Fair and Verifiable Voting Smart ContractBased on BlockchainLIU Hong,ZHANG Jingyu,LEI Mengting,XIAO YunpengCollege of Software Engineering,Chongqing University of Posts and Telecommunication,Chongqing 400060,ChinaAbstract:This paper proposes a blockchain-based encryption-proof scheme to address thefairness flaws and replay attacks in the equal voting mechanism.First,the voting processand rules are written into smart contracts,including time stamps and financial incentives,to ensure that voting takes place on time.It is stipulated that each voter is responsible forhis address key generation.A Merkle tree based on the address public key is constructedto prove the legitimacy of the voters identity.Meanwhile,a random sequence is gener-ated by hash to prevent repeat voting.Second,the blockchain bulletin board and Paillieralgorithm encrypt and store votes to improve the encryption and decryption rate whileovercoming the fairness defect.Finally,to ensure transaction legality and calculation accu-racy,a zero-knowledge proof based on zk-SNARK is constructed based on the immutable收稿日期：2022-10-25基金项目：国家重点研发计划（No.2021YFF0704102）资助通信作者：刘红，副教授，研究方向为区块链和多媒体安全。E-mail:542应用科学学报第41卷characteristics of the blockchain.In this way,the real problem to be proved is transformedinto a calculation problem with specific output,and the encryption algorithm is separatedfrom the zero-knowledge proof circuit,so that the information of the verification data willnot be disclosed.Theoretical analysis and experimental results show that the proposedscheme significantly improves the security and privacy of voting and has lower time andcost consumption.Keywords:blockchain,smart contract,zero-knowledge proof,Paillier algorithm,votingprotocol电子投票面临的主要挑战是同时实现两个对立的目标：投票的隐私性和可验证性。以往的研究大多数使用简单加密技术实现电子投票。然而，文献 1 证明使用加密技术的投票机器在 90 min 内被攻破，导致用户隐私泄露。这一现象引起了人们对电子投票安全性的关注，因此，如何设计安全公平的电子投票协议是一个具有挑战性的问题。各国学者对区块链技术的研究使电子投票协议得到了广泛的应用，尤其是在信息安全领域2-3。智能合约4-5是在区块链上运行的程序，由相互不信任的节点正确执行，无需外部可信机构。因此，基于区块链的电子投票是解决目前存在问题的一种选择。文献 6 设计了比特币投票问题的协议，通过对投票者的投票行为实施激励机制来保证公平。虽然该方案有一定的局限性，但这是将电子投票和区块链联系起来的首次尝试。文献 7 将比特币区块链作为匿名公告板，与盲签名协议相辅相成来实现安全和匿名的电子投票。区块链上也有很多电子投票应用，这些应用程序使用区块链作为投票箱，依靠可信的机构来保护投票者的隐私。基于区块链的自计票协议在隐私性和安全性方面得到了改善，但目前仍存在一些挑战。在自计票方案中，最后的用户计算选票数早于其他参加投票的用户，这会引发公平性问题，从而进一步引起适应性问题和中止性问题。适应性问题指对计票结果的了解可能会影响最后一位投票者的投票方式。文献 8 提出由投票管理机构进行最终的投票，但其投票结果不计入最终的计票结果中。他们引入不可信赖的合作机构，可能存在该机构和最后一个投票者合谋的情况。中止性问题意味着当他们对已知的总票数不满意时可以弃权，这种行为使得投票被迫暂停，无法计算最终的票数。自计票方案存在重放攻击威胁。在选票交易广播的过程中，攻击者截取交易信息，篡改信息，形成重放攻击。投票者可能尝试复制和修改自己的选票或者注册相同的投票密钥，通过重放密钥和零知识证明，实现复制目标投票者的选票。恶意的管理者可能和候选人勾结篡改选票或最终的计票和。恶意的攻击者试图拦截他人选票形成重放攻击。自计票方案存在验证问题。在计票的过程中，投票管理员可能对结果进行修改，比如抛弃部分选票或者添加虚拟的选票等，从而无法保证计票结果的唯一性。本文的主要目的是解决自计票协议存在的公平性缺陷和重放攻击问题，同时实现个人可验证、资格可验证和普遍可验证。个人可验证保证选票不被篡改且包含在最终的计票结果中。资格可验证指的是对投票者的资格进行检查，保证选票只能由合格的用户生成。普遍可验证确保计票结果是唯一的，任何人都可对结果验证。本文的主要研究工作和贡献如下：1）设计无需可信第三方的电子投票方案。区块链作为公告板存储交易信息，同时设计部署智能合约到区块链，代替投票规则，其中包括时间戳和财政激励。电子投票最终的目的是计算选票和，采用 Paillier 算法加密数据，在克服公平性缺陷的同时提升加解密效率。2）设计基于 Merkle 树结构且隐藏身份信息的验证方案。规定每个投票者负责自己的密钥生成，构建基于地址公钥的 Merkle 树来证明投票者身份的合法性且保证交易数据不被篡改。同时利用哈希函数生成随机序列防止重复投票。对单个用户验证时无需下载所有节点数第4期刘红，等：基于区块链的公平和可验证电子投票智能合约543据，减少了计算量。3）设计基于 zk-SNARK 的选票数据有效零知识证明。将需要证明的选票合法问题转化为在多项式时间内验证特定解是否正确的问题。在保证加密和证明数据的一致性的前提下，实现基于算数电路的验证。通过连接性将加密算法从零知识证明电路中抽离进行，减少电路的大小，从而提升性能，并且证明者不会泄露验证数据的信息。目前已有的电子投票方案大多存在公平性缺陷且无法同时满足个人可验证、资格可验证和普遍可验证性。本文提出的无可信机构的可验证的自计票方案（without trusted-authorityself-tallying verifiable scheme,WTSV），与具有最大选民隐私的董事会投票智能合约 VOTE9、分散式博尔达计票智能合约系统 BC10和无可信计票机构的在线投票系统 PV11方案安全性对比分析情况如表 1 所示。表 1 现有方案安全性对比Table 1 Security comparison of existing solutions安全属性VOTEBCPVWTSV资格可验证信任机构yesyesyes个人可验证yesyesyesyes普遍可验证yesnoyesyes自计票yesyesyesyes重放攻击noyesnoyes公平缺陷nonoyesyes无收据noyesyesyes注：yes 表示满足安全属性，no 表示不满足安全属性。1相关工作电子投票的目的不仅是决定结果，也是为了保证投票者和候选人之间的信任。这就强调投票的自由、公平和秘密选举的必要性，并且保证在没有可信第三方的参与下选举是公开和可信的。通常，保护选民隐私的投票协议依赖可信第三方，以验证的方式对选票进行加密和解密。当前，很多使用区块链进行电子投票的协议已经被提出，但是大多数方案都是将区块链作为公告板，仍然使用可信的权威机构来保护选民和选票的隐私。比如 Blockchain VotingMachine12、Follow My Vote13和 TIVI14等公司提出了使用区块链作为投票箱来存储选票的解决方案11。文献 12 提出一种结合 Zerocoin 和比特币平台的电子投票方案。由于比特币系统不具有匿名性的特点，通过 Zerocoin 来实现电子投票系统的匿名性。文献 13 提出了一个独立于区块链平台的电子投票系统，利用环签名技术设计了基于智能合约的可验证电子投票系统。文献 14 提出了一个分布式的匿名电子投票系统，将选票信息存储在区块链公告板上。这些解决方案仅是将区块链作为不可篡改的全局数据库来存储投票结果，都是在可信机构的参与下保证选民隐私。自计票协议将计票转化为一个开放的过程，在投票结束后，任何用户都可以计算投票结果，这就取消了计票机构在投票中的作用。公平性意味着没有人有优先权提前计算中间结果，544应用科学学报第41卷但是自计票协议存在公平性缺陷，因为最后一个投票者可以先于其他人计算结果。这样就会导致适应性问题和中止性问题。文献 8 首次提出了一种用于董事会的自计票协议，该方案的提出使得小规模的电子投票无需任何可信第三方的介入。在投票过程中，投票者的行为普遍可验证，使得投票的私密性得到一定的保障。但是该方案需要很大的计算量和通信量。随后文献 15 在文献 8 所提方案的基础上进行了改进，提高了效率，降低了计算量。上述两方案都仅适用于小规模的双候选人电子投票，这样一来投票的效率就受到很大的制约。2017 年，文献 9 首次提出了使用区块链实现最大隐私保护的去中心化和自计票电子投票协议。该方案实现了隐私保护和安全可验证，适用于董事会选举，但是计算开销很大。此外，自计票协议自身存在公平性缺陷。对于公平缺陷中的自适应问题，该方案在投票过程中增加了一个可选阶段来解决自适应问题，但这使得协议变得更加复杂。对于中止性问题，该方案在注册阶段设置了保证金，但这就增加了额外的系统预算。文献 10 提出一种分散式的博尔达计票智能合约系统，该方案的提出保证了选民的隐私，但该方法在安全性方面还存在一些问题，其无法做到普遍可验证。文献 11 提出了一种无可信计票机构的普遍可验证在线投票方法，但该方案可验证加密和解密时间花费较高，且无法抵御重放攻击，安全性方面有一定缺陷。文献 16 提出了一种基于区块链的去中心化物联网自计票 TALLY 协议，并使用一系列零知识证明解决了中止性问题，但该协议仅支持 2个投票选项，因此适合于小规模投票应用，且未考虑选民的隐私。文献 17 提出一种基于区块链的可追踪自计票电子投票系统，该协议利用同态时间锁谜题实现了自动计票，同时保证了选票的保密性。该方案还构建了一个面向事件的可链接组签名，以保护选民的隐私并防止重复投票。2方案概述2.1系统模型系统框架是基于区块链的电子投票，投票者和发起者通过区块链进行交互。图 1 为本方案的系统框架，主要包含以下三个部分：1）选民。作为该方案的投票者，负责构建选票信息块，将其加密文件和证明一起发送到区块链。首先投票者注册地址密钥对，将地址公钥作为投票资格发送到公告板。然后，投票者加密选票并生成身份合法和选票有效零知识证明，将得到的结果集广播到区块链。2）投票发起者。本次投票的发起者，不是所谓的权威机构。首先初始化投票信息，部署智能合约。其次，收集区块链上的地址公钥得到投票者白名单，构造白名单集合对应的 Merkle树。将选票有效问题转化为算数电路可处理的数学模型，将得到的公共信息广播至区块链公告板。3）区块链。存储选票信息，使用智能合约进行验证和结果计算。首先作为公告板存储公开可用的信息，如地址公钥、白名单、选票。其次对提交至区块链的选票信息进行验证，调用智能合约对交易密文进行解密计算并将得到的结果返回给客户端。图 1 为本方案的系统框架图，主要包含注册阶段、初始化阶段、投票阶段和计票阶段。定义本方案 WTSV 主要有以下几个算法组成（Register,Setup,Vote,Tally）：1）注册阶段。参与投票的选民登录自己的以太坊账户，并注册获得地址密钥对，将得到的公钥广播到区块链公告板。2）初始化阶段。投票发起者初始化选举信息，通知选举开始。首先收集选民 pkID构造白名单 pklist。其次，初始化选票验证信息。3）投票阶段。合格选民依据初始化信息加密选票和生成证明，主要包括身份和选票合法第4期刘红，等：基于区块链的公平和可验证电子投票智能合约545?QAPOutputvic1+vic2+.+vicj=0sabc=s1,0,.,0,0,0,.,00,1,1,.,0,0,.,00,0,.,0,0,1,.,0gae(g,g)abEenc(vic1)Eenc(vic2)Msum,vpkIDcopathpkIDpkIDpkIDskIDskIDskIDskIDBlock1Block2BlocknEenc(vicj)Eenc(vicj)voten:vicjvote2:vic2vote1:vic1Eenc(vic2)Eenc(vic1).gbrtH(h0+h1)H(pkID0)H(pkID1)H(pkIDn)H(pk.)H(h.+hn)pkID0pkID1pk.pkIDnMerkle?图 1 系统框架图Figure 1 System framework diagram性证明。最后将选票信息发送到区块链公告板。4）计票阶段。首先对提交的选票信息进行验证，包括资格可验证和选票验证两部分。其次，进行计票并将结果公布。任何人都可以对计票结果进行验证。2.2威胁模型假设存在恶意攻击者可以通过加密消息学习敏感信息。现有攻击可能发生在身份核查和提交选民阶段。图 2 为选票交易信息泄露造成的威胁模型。加密信息是由确定性算法生成的，并且所有的信息是公开发送到公告板上的，因此敌手可以监听窃取交易信息。重放攻击包括三种情况：选民复制并重复发送选票、恶意敌手拦截并篡改选票、恶意管理员修改计票结果。详细攻击描述如下：选民在不改变传输路径的情况下，向区块链多次发送交易，形成重复投票。在选民将交易信息发送到区块链的过程中，恶意敌手截获交易块，重新加密获得新的交易信息，将其重新发送到区块链上形成重放攻击。在计票阶段，恶意管理员利用解密密钥修改计票结果或者添加额外选票。2.3系统目标研究发现可验证性的无法满足将导致隐私泄露18。本文的目标是隐藏交易信息，克服公546应用科学学报第41卷?图 2 重放攻击模型Figure 2 Replay attack model平缺陷，抵御重放攻击和构造基于零知识的非交互验证。非交互验证主要包括个人可验证、资格可验证和普遍可验证。个人可验证是投票者可以核实自己的选票是否包含在内。资格可验证是选票只能由具有投票权的合格投票者产生。普遍可验证意味着计票的唯一性。为了实现整体目标，本文在等权投票机制下，提出了一种基于区块链的 Paillier 加密证明电子投票方案。对于交易数据加密，本方案采用 Paillier 算法加解密选票数据Dec(Enc(m1)Enc(m2)=m1+m2(1)式中：Enc 为加密运算；Dec 为解密运算。对两个密文的乘积解密得到对应的明文之和。基于 zk-SNARK 算法实现投票者身份隐藏证明和选票合法性验证。通过在 zk-SNARK中构造 Merkle 树，将投票者身份信息隐藏在零知识证明中。参考 Zerocash19的例子，使用隶属度证明来量化投票者资格验证pkID=H(skID)rt=MerkleTree(pkID,copath)sn=H2(skID)(2)式中：(skID,pkID)为地址密钥对；rt 为 Merkle 树根；H(skID)表示利用哈希函数生成地址公钥；copath 为构建 Merkle 树的路径向量；sn 作为随机数用来预防重复投票。本文通过最小化数据下载量和验证计算量来实现目标。因此，当证明一个选民存在白名单时，只需要得到从该叶子节点到根的路径 copath，不需要所有叶子节点参加，减少了计算量。zk-SNARK 技术可以将隐私保护信息压缩成简洁证明，提升验证的效率。由于zk-SNARK无法直接应用于实际问题，必须有量化的输入，需要将实际待验证问题转化为特定输出的数学模型。本方案要求所有的投票者只可以选择一名候选人进行投票，将此需求转化为以一个可计算的问题，即存在一个程序，其输入为选票数据 vicj。如果选民没有选择候选人，则输出结果为 0，否则为 1。在初始化条件下，用户没有选择任何候选人。针对选民 vi的投票情况，定义初始化表达式值为 0，即vic1+vic2+vicj=0,i (1,2,n),j (1,2,m)(3)式中：vicj表示第 i 个选民选择第 j 个候选人；n 表示选民数量；m 表示候选人数量。本方案要求每个用户仅可选择 1 名候选人进行投票，因此式(3)的最终结果只有在 1 的情况下才符合选票合法要求。在证明阶段，可以通过式(3)的成立实现选票合法验证。第4期刘红，等：基于区块链的公平和可验证电子投票智能合约5473WTSV 方案详细描述本文通过隐藏选票信息和保证身份数据的安全可验证来实现自计票。图 3 为本方案具体投票场景。为了消除可信第三方的介入，本文利用区块链作为公告板存储交易信息，同时在区块链上设计部署智能合约保证选举按预期规则进行。利用 Paillier 算法加密选票，在加密选票的同时生成身份和选票数据证明，将密文和证明作为交易信息块广播到区块链。?zk-SNARKstatementcircuit?图 3 投票框架图Figure 3 Voting framework diagram接下来，将进行本文所提出方案的具体细节描述，主要包含注册阶段、初始化阶段、投票阶段和计票阶段。表 2 为本方案涉及的变量参数解释。表 2 参数解释Table 2 Parameter explanation变量释义vi第 i 个选民，其中 i (1,2,n)cj第 j 个候选人，其中 j (1,2,m)CTi选民 vi的加密密文Msum所有密文解密的明文和copath叶子节点到树根的路径rt选民地址公钥构造的 Merkle 树根sn利用哈希函数生成的随机数(skID,pkID)注册的地址公钥对，用于验证身份(skdec,pkenc)加密密钥对pklist合格的选民名单CRS公共参考字符串548应用科学学报第41卷3.1注册阶段在调查研究中发现，现有的投票协议需要权威机构负责密钥颁发，这将导致授权机构从投票交易中发现投票者身份。基于隐私保护，本文规定投票者对自己的密钥负责。为了更好地保护用户隐私，用户使用以太坊账户地址 ID 来标识每个投票者的身份。每个地址 ID 只可以完成一次注册，并且每个注册账户仅可以进行一次投票。选择常数 1，将 1作为安全参数，生成随机私钥 sk，利用 ID 和私钥组合得到地址私钥 skID。利用抗碰撞哈希函数生成地址公钥 pkID=H(skID)。确保每个参与投票的选民账户都有一定数量的以太币，可以通过购买和挖矿获得。在注册阶段，所有用户存储一定数量的以太币到智能合约作为财务激励。在投票结束后智能合约会自动退款到账户，任何在投票截止前中止投票的选民都将失去押金。3.2初始化阶段为了更好地实现可验证和隐私保护，使用 Merkle 树结构来隐藏选民身份和基于zk-SNARK 算法的选票有效零知识证明。主要包含两部分：初始化 Merkle 树和数学模型构建。3.2.1Merkle 树初始化首先，投票发起者初始化选举信息，利用选民公钥集合 PK=pk1,pk2,pki,i n，构造参加选举的选民名单 pklist。然后进行 Merkle 树的构造，对于叶子节点 pkID，使用哈希对其进行编码得到真实数据的哈希值。非叶子节点存储 2 个子节点组合的哈希值，重复向上散列，直到得到根节点 rt=GetMerkleRoot(pklist)。3.2.2数学模型构建由于 zk-SNARK 不能直接用于任意问题，必须有量化的输入。因此将选票有效问题转化为 zk-SNARK 可以处理的数学模型。具体描述如下。首先将算数逻辑方程转化为算数电路验证。选民需要在不暴露选票 vicj的情况下证明选票有效，则算数逻辑表达式为vic1+vic2+vicj=1,i (1,2,n),j (1,2,m)(4)为了将方程式转化为算数电路，将其分解为加法组成的最小操作，通过增加中间变量将其转化为门电路表示，式(4)对应的门电路表示为svc1=vic1+vic2svc2=svc1+vic3out=svcj2+vicj(5)式中：svci表示中间门电路的输出；vicj表示第 i 个选民选择第 j 个候选人；out 是最后的输出结果。当输出的结果为 1 表明选票合法，输出为 0，则不合法。对应的电路如图 4 所示。从图 4 中可以看出，证明者和验证者作为 2 个角色分开执行。算术电路的输出是特定投票者的输入通过证明电路计算得到的。上述算术电路转化为 QAP20(quadratic assignmentproblems)，QAP 定义如下。第4期刘红，等：基于区块链的公平和可验证电子投票智能合约549?vic1svc1svc2svc1+vic3vic1+vic2+.+vicjoutvic2vic3vicj图 4 选票合法性电路Figure 4 Vote legitimacy circuit给定一系列多项式 li(x),ki(x),di(x)，其中 i (0,1,n)，是否可以根据这一系列多项式，求得它们的一个线性组合 ai,(i (0,1,n)，刚好可以整除目标多项式 t(x)nXi=0(aili(x)(aiki(x)(aidi(x)=t(x)h(x)(6)将图 4 中的变量定义为一组集合向量 ss=one,vic1,vicj,svc1,svcj2,out(7)式中：one 表示一个常量 1；vicj为算数电路的输入，即选票；svcj为中间门电路的输出；out为整个电路的输出。以门电路 vic1+vic2=svc1为例进行转换，存在一组向量(y,z,k)满足sy sz sk=0(8)y=1,0,0,0,0,0z=0,1,1,0,0,0k=0,0,0,0,1,0(9)根据式(8)和(9)，可以得到如下多项式组：sy=onesz=vic1+vic2sk=svc1(10)将向量(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)为V(x)=sy(x)sz(x)sk(x),x (1,2,n)(11)550应用科学学报第41卷为了满足 QAP 定义，假设存在目标多项式 H(x)=0，T(x)=(x 1)(x v)，可以整除 V(x)。从而得到验证的 QAP 方程式为sy(x)sz(x)sk(x)=T(x)H(x)(12)通过验证满足式(12)来证明提交的选票信息是合法的。此外，利用公共参考字符串模型21（common reference strings,CRS）实现非交互式证明。利用 zk-SNARK 中的 CRS 结合预先定义的资格可验证和选票有效关系，生成 CRSzk-SNARKSetup(relation)。智能合约调用加密算法，生成加密所需的投票密钥对(pkenc,skdec)，其中加密公钥为 pkenc=(g,n)，解密私钥为 skdec=(,)。3.2.3智能合约模型构建根据投票方案的功能，本方案设计智能合约包括投票合约和密码合约。1）投票合约。投票协议逻辑，主要包括初始化选举时间戳、获取候选人列表、收集选票等。具体设计如表 3 所示。表 3 投票合约设计表Table 3 Voting contract design合约函数功能说明State(Register,Setup,Vote,Tall)选举的阶段getCandidayes()获取候选人列表setEligible(assress)设置注册beginSignUp(finishRegister)开始选举Vote(enc(m),proof)收集选票，输入选票信息2）加密合约。包含创建和验证协议的零知识证明。投票所需的证明在本地生成，目的是确保所有选民都能使用相同的加密算法。具体设计如表 4 所示。表 4 密码合约设计表Table 4 Cryptographic contract design合约函数功能说明Secp256k1_noconflict()椭圆曲线配对LocalCrypto()本地加密合约createZKP(CT)创造零知识证明verifyZKP()验证零知识证明3.3投票阶段投票过程主要包括对选票加密和证明构造两部分。为了更好地隐藏选票，采用 Paillier 算法加密，同时构造基于 zk-SNARK 的零知识证明。图 5 为加密证明构建过程。第4期刘红，等：基于区块链的公平和可验证电子投票智能合约551rtHash12Hash1pkID1pkID2pkIDiDataBlocksHash2Hashi-1iMiE(Mi)EncHashi?图 5 加密证明构建过程Figure 5 Cryptographic proof construction process3.3.1基于 zk-SNARK 的零知识证明选民需要在加密选票的同时构造零知识证明，主要包含两部分：身份证明和选票有效证明。下面详细介绍证明构造过程。首先构造身份证明。选民登录以太坊账户，利用 copath GetMerklePath(pkID,pklist)得到从地址公钥 pkID到根节点的认证路径 copath，利用 rt MerkleTree(pkID,copath)获得树根 rt。其次，构造选票有效证明。利用抗碰撞哈希函数生成随机数 sn=Hsn(skID)来保证选票的唯一性，抵御中间人攻击。采用椭圆曲线配对，实现式(12)的乘法同态。对于明文 m1和m2来说，加密后的密文存在如下等式：e(gE(m1),gE(m2)=e(g,g)E(m1)E(m2)(13)为了实现非交互式零知识，采用 CRS 模型。生成器随机选取随机数(,)形成CRS，并将其公开。选民读取 CRS，利用椭圆曲线的同态性质计算生成选票有效证明，其中(,)来自随机参数 CRS。选票有效性证明转化为待验证的多项式，即证明多项式sy(x)sz(x)sk(x)=T(x)H(x)的成立。选民可以得到各多项式数组对应的 对，假设选民待证明的信息为 m，通过 对计算得到如下证明：E(m)=E(m)(14)因此，选民生成待验证多项式中每个多项式对应的证明，选民将生成的 对作为整体的证明 发送到区块链，具体为E(sy(x),E(sy(x)E(sz(x),E(sz(x)E(sk(x),E(sk(x)E(H(x),E(H(x)E(sy(x)+sz(x)+sk(x)(15)552应用科学学报第41卷3.3.2选票加密选民利用 Paillier 加密体制的选票加密算法，使用加密公钥 pkenc加密选票获得密文CT=Enc(vicj)。候选人可以收集加密的选票，候选人 cj的选票加密为Enc(Cj)=Enc(v1cj+v2cj+vicj)=gv1cj+v2cj+vicj rnn0mod n02(16)式中：v1cj+v2cj+vicj表示候选人 j 的所有选票和；n0表示两个大小相近的大素数的乘积；r 是在条件 0 r n 中随机选择的，使用加密公钥 pkenc=(n,g)加密选票。选民将获得的选票信息块 Ballot=(sn,rt,CT,)提交到区块链公告板。3.3.3区块链节点验证选票在计票之前，区块链节点验证每张选票，主要包含两部分：验证选票是否由合格的选民生成、选票是否有效。首先进行身份验证。区块链节点获取选民提交的 Merkle 根 rt 进行验证。当验证值和初始化树根的哈希值一样，即选民是在选民名单中的。(rt MerkleTree(pkID,copath)sn/Blockchain(17)利用 sn 检测重复投票，如果 sn 满足 sn Blockchain，则表明该身份对应的选票已经存在，直接中止该交易数据块。利用椭圆曲线的 对特性进行多项式盲验证，验证选民提交的证明 是由初始化定义的多项式计算生成。已知配对函数定义为e(gm1,gm2)=e(g,g)m1m2(18)基于多项式特性，在进行投票合法验证的过程中，仅需要随机选择作用域内的任意一点进行验证。以 sy(x)为例，通过验证式(17)和(18)，可以验证 E(sy(x)和 E(sy(x)满足 对的特性，从而在不暴露隐私的情况下证明选票有效性：e(E(sy(x),g)=e(gsy(x),g)=e(g,g)sy(x)(19)e(E(sy(x),g)=e(gsy(x),g)=e(g,g)sy(x)(20)此外还需要证明多项式(21)是成立的。e(E(sy(x),E(sz(x)=e(gsy(x),gsz(x)=e(g,g)sy(x)sz(x)(21)e(E(P(x),E(Q(x)e(E(sk(x),g)=e(gP(x),gQ(x)e(gsk(x),g)=e(g,g)P(x)Q(x)e(gsk(x),g)=e(g,g)P(x)Q(x)+sk(x)(22)式中：P(x)、Q(x)为 QAP定义中的目标多项式。3.4计票阶段当参与投票的所有选民都将交易消息发送到区块链后，通知智能合约开始计票。由于Paillier 加密算法满足加同态，对密文的乘法运算可以直接得到明文和。以候选人 cj为例，通过私钥解密计算可以得到最终的明文计票和 Msum,cjMsum,cj=Dec(Enc(CT)ni=1)=Dec(CT1,CT2,CTi)=v1cj+v2cj+vicj(23)第4期刘红，等：基于区块链的公平和可验证电子投票智能合约553式中：(v1cj,v2cj,vicj),i (1,2,n),j (1,2,m)表示选择候选人 j 的所有选票。在解密计算的过程中，生成解密证明 v。在计票结束后，将解密证明和计算结果(Msum,v)发布到区块链，任何人都可以通过解密证明对计票结果进行验证。v=rskdec(r Z)(24)式中：r 为随机整数；skdec为私有的解密密钥；生成解密证明为 v。投票者 vi对计票结果(M,CT,v)进行验证，其中 M=(m1,m2,mn)，CT=(c1,c2,cn)。因为解密证明是可验证的，因此不存在任何解密证明满足错误的密文，即e(cj,VK)e(r,VK)skdec=e(G,VK)mj(25)(sn=H(skID,Vi)Dec(CTi)=M(26)投票者利用地址私钥生成的随机序列 sn 是唯一的，当提交的密文被篡改时，则存在重复且不唯一的随机序列 sn。如果密文解密后仍为原始消息，表明选票没有被篡改。为了确保最终的解密结果是正确的，基于符合剩余类问题可以对计票结果进行验证，根据 Cmrmichaels22定理可得c=(gmrn)=gm(27)通过关系(1+n)x=1+nx mod n2将公式转化为gm=(1+mn)mod n2(28)最后，利用 L(X)函数可以得出解密结果是正确的m=L(cmod n2)mod n=L(cmod n2)L(gmod n2)mod n(29)4安全和性能分析4.1安全性分析在文献 23 提出的选票隐私定义的基础上，对本方案的安全性进行评估。在整个投票过程中，如果存在恶意的节点进行联合来截取选票信息，进一步伪造选民的身份进行投票。本方案在满足公平性的基础上，实现身份可验证、个人可验证和普遍可验证。所有的选票在进行计票前都需要进行身份和个人可验证，如果恶意的节点形成重放攻击，则形成的选票信息中验证身份的随机数可能发生改变，并且新构建的 Merkle 树根也无法对应原始数据。因此，本方案可以有效地避免恶意节点形成的重放攻击。4.1.1投票隐私定理 1恶意的敌手无法篡改选票信息。为了证明投票隐私，定义攻击者 A 和投票发起者 D 之间的隐私保护游戏 GameBP。主要目的是让敌手 A 在完全控制选民的前提下构造 2 个不同的投票集合。投票隐私满足敌手无法区分加密选票。对于任意的概率多项式时间(PPT)敌手 A，如果存在一个可忽略函数 negl()，使得flflflAdvGameBPWTSV,A()1/2flflfl negl()成立，则表明本方案满足投票隐私。其中 GameBP表示协议满足投票隐私，AdvGameBPWTSV,A()表示敌手A 赢得游戏的概率。554应用科学学报第41卷证明以下构造 AdvGameBPWTSV,A()表示敌手赢得游戏。使用 Ga