用零知识证明解决投票安全
原创
用零知识证明解决投票安全
背景
我们经常会遇到需要给别人投票的情况，比如有些公司会组织员工给领导做反向打分，但是往往员工都不敢“真心实意”的打分，为什么呢？归根结底是害怕所谓的匿名不是真匿名，万一领导拿到了投票数据给你穿个小鞋你就别混了。
为什么害怕投票系统不是真匿名呢？稍微懂点技术的可能就知道一般的投票系统的做法是投票者需要登录进系统，首先证明自己的身份，然后投票，这样后台是可以看到身份和投票的一一对应关系的，且不谈后台可以悄悄的记录下来这个对应关系，即使“良心”的后台不记录这种关系，但是数据在传输到后台之前可以被网络上黑客给劫持，然后黑客可以还原这种关系。
再退一步假如他们真的不记录这种一一的对应关系，那么系统对被投票者来说也是不安全的，因为既然没有身份和投票结果的一一对应关系，就没有办法复盘投票过程，那么票数后台是可以伪造的。
零知识证明技术的引入可以解决这个问题，既可以隐藏投票者的身份信息保证真匿名，也可以让后台可以放心大胆的记录投票结果，如果有人质疑投票结果，也可以复盘投票过程，让投票无论对投票者来说还是被投票来说都是安全的。
怎么做呢？
简单来讲就是提供一段“混淆加密过的数据”，这段数据可以证明制造这段数据的人是在“投票者”这个集合中的，但是大家却不知道他具体是哪一个投票者。
零知识证明基础
什么是零知识证明？
零知识证明是能够在不向验证者任何有用的信息的情况下，使验证者相信某个论断是正确的。对应到我们要解决的场景就是，不提供投票者信息的情况下证明我是一个投票者。
零知识证明的技术实现的基础单元
假设我们有一个函数C，这个函数有两个输入x和w，输出是布尔值，表示成r=C(x,w)其中x表示公共的输入，w表示一个私密的输入，而r表示w和x是否满足C这个函数的约束。零知识证明就是解决这样的问题：
给定一个输入x，证明者对外证明他知道私密的输入w可以使得C(x,w)=true
举一个例子
假如小花有一个hash值H，希望找到这个hash值的原值，小明有一个数据D，H正好是D的hash值，也就是满足H=hash（D）。小明希望向小花证明他知道H的原值，正常情况下小明需要把D给小花，小花通过计算hash（D），对比hash（D）是否等于H，才能知道小明确实有H的原值。
但是，假如小明不想把D提供给小花，他仅仅想证明他知道D而已，他可以用零知识证明的体系解决他的问题。
我们用简单的js函数可以描述小明的问题
function C(x, w) {
? return ( sha256(w) == x );
}这个函数功能就是输入一个hash值x和一个普通数据w，然后假如满足sha256（w）等于x就返回true。现在小明的问题可以转换为小明创建一个证明proof，可以证明C（H，D）=true，但是并不把D公开。这个就是普通的零知识证明问题。
零知识证明通用解决方案中有一个分支叫做zk-SNARK（Zero-Knowledge Succinct Non-Interactive Argument ofKnowledge）它的定义如下（盗用大牛的公式）：
Generator (C circuit):
(pk, vk) = G(C)
Prover (x pub inp, w sec inp):
π = P(pk, x, w)
Verifier:
V(vk, x, π) == (? w s.t. C(x,w))
Generator（G）接受一个代表“电路”的C也就是我们上文中提到的函数C，生成一个验证密钥vk和一个公钥pk，同一个“电路”C只能生成一对唯一的vk和pk。其中C和G证明者（小明）和验证者（小花）都知道，也就是vk和pk证明者（小明）和验证者（小花）都知道。
Prover（P）用于生成证明数据π，而他的参数是pk（小明和小花都知道）、公共的输入x（小明和小花都知道的H）和私密的输入w（只有小明知道的D）。这个是证明者（小明）一方运行的函数。
Verifier（V）用于验证数据π是否符合预期，输入的参数是vk（小明和小花都知道）、公共的输入x（小明和小花都知道的H）和证明数据π（小明生成提供给小花的）如果V的结果为true等价于C（x，w）=C（H，D）=true。
使用zk-SNARK复盘上文中提到的小明和小花的例子
小明和小花怎么通过zk-SNARK的方法解决他们的难题呢?
第一步，小明和小花需要先定义一个“电路”，也就是函数C如下：
function C(x, w) {
? return ( sha256(w) == x );
}第二步，小明和小花同时使用“电路”改造生成器G，作用于函数C，生成对应的vk和pk：
(pk, vk) = G(C)
这时小明和小花同时拥有相同的vk和pk
第三步，小明使用P函数生成π，P函数的参数是pk、H和只有他自己知道的D
π = P(pk,H,D)
第四步，小明将π发送给小花
第五步，小花使用V函数对π进行验证，V函数的参数是π、H和vk
V(vk, H, π)
假如V函数返回true那么表明小明真的知道H的原值D，如果为false表明小明其实并不知道H的原值D。
回过头来再看整个过程，小明告诉小花的只有一个π，而不是D，就证明了自己是确实知道D的。而且zk-SNARK可以保证小花是没有办法通过π反推出D的。
构建匿名投票约束
投票系统需要解决的核心问题如下：
1、 投票者需要证明自己是合法的投票者
2、 投票者不想暴漏自己具体是哪一个投票者
那我们将问题转换成如下问题：
验证者提供一个投票者ID集合K，证明者提供一个证明π，证明自己是这个集合中的一员，但是并不给出任何ID信息
由于zk-SNARK只支持固定的“电路”，也就是R1CS(rank-1 constraint system，一阶约束系统)所以我们必须把问题转换成它可以读懂的方式。（具体什么是R1CS限于本篇幅有限暂时不做介绍，读者可以自行google或者等读者后续文章讲解）。比如上文中的H=hash（D）就可以通过R1CS构造出来，算是一条约束。
首先，我们为n个投票者生成n个私钥sk，然后用私钥sk生成用户ID：
ID=hash（sk）
由于hash的不可逆性，所以知道用户ID并不能反推出私钥sk，那么第一条约束就建立了，表示如下：
C1:ID=hash（sk）
然后，我们构造一棵二叉树T，这个二叉树有一个专业点的名字叫merkle-tree。他的构造方式是：
1、 所有的节点（包含叶子节点）的值都是hash值
2、 所有的父节点P是两个子节点L，R的hash值也就是P=hash（L，F）
3、 如果子节点只有L没有R那么P=hash（L，L）
4、 所有的叶子节点都是用户ID
5、这棵树的根我们用R（root）表示
也就是这棵树的叶子节点是用户ID的集合K，由于hash的不可逆性，所以如果我们知道一个用户ID和他对应走到R的路径P（path）上的所有hash值就可以算出来R，但是知道R并不能反推出路径P和叶子节点用户ID，为了方便理解，可以参考下图：
如图，这棵树中有ID1-ID8 共8个用户，I1-I6 6个中间节点，R表示树的根。如果用户3想证明自己是在K中，可以提供ID3和路径P3（ID4，I3，I2）就可以算出来R。
约束2是提供ID和一个路径P必须可以构造出树根R，表示为
C2:R=Gen_Tree_Root（ID,P）
由于证明数据π可以被劫持和重复发送，所以一定要把投票结果放到约束中去，这样即使π被劫持了他也不能修改我们的投票结果。假如投票结果用VR（vote result）表示，用私钥sk对VR做约束：
C3：VRH（vote result hash）= hash（sk， VR）
这样如果有人想投票就必须知道sk，否则不能构造出合法的VRH
那么梳理一下我们的“电路”（函数）是
function C(x, w) {return? (ID==hash（sk）&& R==Gen_Tree_Root（ID,P）&& VRH== hash（sk,VR）)}其中x是（R,VRH, VR），w是（sk,P）
由sk可以推导出ID，由ID和P可以推导出R，由sk和VR可以推导出VRH，进而满足所有三个约束。
接下来我们演练下整个投票过程，所有投票者生成一个自己的私钥sk，然后hash（sk）生成了代表自己的ID，投票公正官小花收集所有的投票者提供的ID，构造出来一棵二叉树T，这棵树的树根是R，然后小花把这棵树公布出来，让所有的投票者都能看到，同时公布的还有“电路”C，和用电路C生成的pk，假如小明是一个投票者，小明决定了投票结果为VR，然后使用函数P生成π如下：
VRH=hash(sk,VR)
π=P(pk, (R,VRH,VR), (sk,P))
其中由于R和T都是公开的，小明又是知道自己的ID，所以P小明可以自己推算出来。
小明算好π以后把π，VRH和VR一同打包提交到后台（注意这里是不需要登录的，小明可以随便找一台机器提交，后台只能拿到一个ip但是拿不到用户ID）。
小花从后台取出来数据（π，VRH，VR）用函数V进行验证如下
V（vk,(R,VRH,VR）, π)
如果V返回为true就把VR当作正确的投票结果记录，如果为false，说明投票不合法不记录。
再看整个过程小明只给了投票结果和投票结果的hash VRH以及证明π，并没有提供自己的私钥sk或者自己的用户ID，就可以让小花知道他这个投票是合法的。
思考题：如果读者读懂了这篇文章可能会看到这个投票系统还有一个漏洞，就是投票者可以重复投票，或者修改投票结果。其实这个可以通过再加一个约束杜绝，这个留给读者思考，如果有兴趣可以和笔者交流。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。