代码编织梦想

链客,专为开发者而生,有问必答!

此文章来自区块链技术社区,未经允许拒绝转载。

在这里插入图片描述

背景
我们经常会遇到需要给别人投票的情况,比如有些公司会组织员工给领导做反向打分,但是往往员工都不敢“真心实意”的打分,为什么呢?归根结底是害怕所谓的匿名不是真匿名,万一领导拿到了投票数据给你穿个小鞋你就别混了。

为什么害怕投票系统不是真匿名呢?稍微懂点技术的可能就知道一般的投票系统的做法是投票者需要登录进系统,首先证明自己的身份,然后投票,这样后台是可以看到身份和投票的一一对应关系的,且不谈后台可以悄悄的记录下来这个对应关系,即使“良心”的后台不记录这种关系,但是数据在传输到后台之前可以被网络上黑客给劫持,然后黑客可以还原这种关系。

再退一步假如他们真的不记录这种一一的对应关系,那么系统对被投票者来说也是不安全的,因为既然没有身份和投票结果的一一对应关系,就没有办法复盘投票过程,那么票数后台是可以伪造的。

零知识证明技术的引入可以解决这个问题,既可以隐藏投票者的身份信息保证真匿名,也可以让后台可以放心大胆的记录投票结果,如果有人质疑投票结果,也可以复盘投票过程,让投票无论对投票者来说还是被投票来说都是安全的。

怎么做呢?

简单来讲就是提供一段“混淆加密过的数据”,这段数据可以证明制造这段数据的人是在“投票者”这个集合中的,但是大家却不知道他具体是哪一个投票者。

零知识证明基础
什么是零知识证明?

零知识证明是能够在不向验证者任何有用的信息的情况下,使验证者相信某个论断是正确的。对应到我们要解决的场景就是,不提供投票者信息的情况下证明我是一个投票者。

零知识证明的技术实现的基础单元

假设我们有一个函数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©

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©

这时小明和小花同时拥有相同的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 (IDhash(sk)&& RGen_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,就可以让小花知道他这个投票是合法的。

思考题:如果读者读懂了这篇文章可能会看到这个投票系统还有一个漏洞,就是投票者可以重复投票,或者修改投票结果。其实这个可以通过再加一个约束杜绝,这个留给读者思考,如果有兴趣可以和笔者交流。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_44172023/article/details/100014222

零知识证明_李柏林的博客-爱代码爱编程

什么是零知识证明 零知识证明(Zero—Knowledge Proof),是由S.Goldwasser、S.Micali及C.Rackoff在20世纪80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况

投票证明:基于投票机制和联盟封锁链的高性能一致性协议_易豆豆的博客-爱代码爱编程

Title:投票证明:基于投票机制和联盟封锁链的高性能一致性协议 Abstract:比特币引入了一种革命性的去中心化共识机制。然而,应用于公共区块链的比特币衍生共识机制不适合新兴联盟区块链的部署场景。我们提出了一种新的共识算

零知识证明三—— 如用zksnarks方式构建一个匿名投票系统_许强#的博客-爱代码爱编程

 这个匿名投票系统的例子还是不完善的,如果你有好的建议和想法可以留言一起学习探讨。  https://github.com/XuHugo/zksnarks-election/tree/master     一、构建一个匿名的投票系统,最核心的部分有两个,          1、投票人的匿名          2、投票人身份合法性确认     如何

零知识证明之范围证明的应用-爱代码爱编程

近几年零知识证明的相关构造落地实现有了非常大的进展,每隔一两个月就会出来各种各样的好消息,目前已经有很多很棒的库可以提供给应用层来使用。 本文主要介绍零知识证明中的一小块领域--范围证明的部分应用,这些材料大部分来源于网络,此文不涉及零知识证明背后棘手的加解密原理,相关原理已经有很多非常专业的文档阐述得很好(主要还是因为我担心讲得不好,怕误人子弟)。

WeDPR多方密文决策:自研零知识证明核心算法的实践-爱代码爱编程

WeDPR是微众银行区块链自研的一系列即时可用、场景式隐私保护解决方案,围绕数据隐私保护核心业务场景而打造,已构建的场景方案矩阵涵括多方大数据隐私计算、选择性认证披露、多方密文排名等细分场景的解决方案。本次,WeDPR融合零知识证明最新研发成果,开放多方密文决策(Anonymous Ciphertext Voting,ACV)场景解决方案及核心算法组

零知识证明系列之二——Schnorr协议-爱代码爱编程

​Schnorr协议简介 Schnorr协议是由德国数学家和密码学家Claus-Peter Schnorr在1991年提出,是一种基于离散对数难题的知识证明机制。Schnorr本质上是一种零知识的技术,即Prover声称知道一个密钥x的值,通过使用Schnorr加密技术,可以在不揭露x的值情况下向Verifier证明对x的知情权,即可用于证明你有一个私钥

2022 年预测:零知识证明(ZKP)成为 Web3 的关键-爱代码爱编程

2022 年预测:零知识证明(ZKP)成为 Web3 的关键 去年,零知识证明(ZKP)在加密领域和Web3中扮演了重要角色,它在可扩展性和用户许可隐私方面都发挥着重要作用。这是令人兴奋的,因为它为ZK应用程序在整个加密生态系统中的推出奠定了基础,并成为Web3的杀手级功能。 Web3 Web3是一个经常出现的术语,但它有点模糊。乐观地说,它的最

生命以负熵为生:浅析零知识证明_先驱君的博客-爱代码爱编程

2020年是时代的一个分水岭,以Web2.0创新的产物推特封杀特朗普帐号为标志,人们又经历了一系列期望和失望之后,现在的人们比以往任何时候都更加注重安全、隐私和数据所有权。而快速发展的Web3.0最大特征之一就是让参与者对其内容、数据和资产拥有完全所有权,切实保证了参与者的隐私安全,激发了人们内心对新一代互联网发展的新信心,那么零知识证明在其中将扮演怎样的

零知识证明:web3世界的护身符_coinvoice的博客-爱代码爱编程

作者:Daniel Li 出品:CoinVoice 在经历了Web2.0创新带来的一系列期望和失望之后,现在的人们比以往任何时候都更加注重安全、隐私和数据所有权。而快速发展的Web3.0最大特征之一就是让参与者对其内容、数据和资产拥有完全所有权,切实保证了参与者的隐私安全,激发了人们内心对互联网发展的新信心,那么零知识证明在其中将扮演怎样的角色,它是否真

最全最细的零知识 (zk) 证明解读_区块链技术研究员的博客-爱代码爱编程

零知识 (ZK) 证明就像三箭资本的 Su Zhu 和 Kyle Davies一样,他们出生于上世纪八十年代,但直到最近才成为热门话题。   你可能听说过很多关于它们的信息,但 ZK 证明到底是什么? 你也许了解了基础知识,但想知道使用 ZK 证明最有前途的项目是什么? 现在就让我们通过ZK证明的概述、应用项目和底层技术来回答这些简单又复杂的问

did:零知识证明的第一个应用试验场_区块链技术研究员的博客-爱代码爱编程

DID和社交网络中的零知识证明 作者:Ishanee,IOSG Ventures 首先解释一下文中会使用到的词语的含义: 去中心化身份 (DID) 或个人主权身份 (SSI) :是一个基于开放标准的框架,它使用个人拥有的、独立的、可验证的凭证,并能实现可信的数据交换。 凭证 Credential / 证明 Attestation / 可验证凭证

区块链交易隐私如何保证?华为零知识证明技术实战解析_passersb的博客-爱代码爱编程

【摘要】 零知识证明技术不管应用于金融还是其他领域,都可以对隐私保护,性能提升,或者安全性等场景带来很多帮助。本文通过介绍华为如何在同态加密及零知识证明框架的集成介绍来介绍了一些对金融领域交易隐私保护的思路,通过代码结和应用场景描述了zksnark如何集成到现有联盟链体系保护交易隐私。以及目前零知识证明领域应用的技术挑战,华为是通过什么样的技术解决当前的挑

privacyin week1课程回顾 | 张宇鹏博导开讲零知识证明密码学基础&研究导论_platon技术团队的博客-爱代码爱编程

转自:PrivacyIN 隐私学院 前言 隐私学院【PrivacyIN】第一期ZK训练营课程精讲内容上线啦,本期课堂邀请到美国德州农工大学(Texas A&M University)计算机科学与工程学院的助理教授

​电子投票系统与区块链-爱代码爱编程

前言 大家对于投票一定都不会陌生,相信大家都经历过学生时期五花八门的选举,而选举的重要环节就是投票,那时候的投票还是纸质投票。这种传统的纸质投票存在其自身的弊端,然后人工点票、唱票,在进行大规模选举的时候,不可避免地会消耗大量的人力和物力去实现,同时其自身也有些不可避免的缺点,如结果容易被篡改、选举过程不透明等。 随着时代的发展和科技的