零知识证明
11月14日 in 中国科学院大学
零知识证明
零知识证明数独解的例子解释零知识证明一、零知识证明方法:二、如何让Alice以外的人相信?三、数独问题零知识证明中出现的问题零知识证明相关理论一、交互证明系统1、交互证明的性质:2、交互证明系统的定义:3、IP语言类二、零知识证明1、定义2、零知识性的三种形式利用零知识证明的应用一、小零币(Zerocoin)1、做法2、如何花小零币二、大零币(ZeroCash)承诺过程数独解的例子解释零知识证明
如何证明数独有解?不能直接给出解(数据保护问题:数独题目存在价值)。
一、零知识证明方法:
承诺将谜底卡片扣在桌子上,谜面卡片放在桌子上。(Alice不能查看)随机挑战
链下互动:Bob让Alice用任意一种(行、列、宫格)方法检查,Alice严格随机选择一种规则进行检查。响应
将Alice选择验证方式的每一行/列/宫格放入一个麻袋中打乱交由Alice验证。(放入过程Alice监视)
Bob在每一次Alice选择验证方式的随机中无法猜测,重复若干次。验证
在Bob没有解的情况下,欺骗成功的概率是1/3,Alice抓住欺骗的概率是2/3。
二、如何让Alice以外的人相信?
将同样的解做多次备份,放入机器中(机器可以根据指令自动完成按行/列/宫格打包)。指令结合不能由Bob生成,找到可信方法生成随机串为机器提供指令,完成非交互式的证明。由此,随机串必须采用所有人公认方法。至此,零知识证明问题的核心是解决随机串的选取问题。三、数独问题零知识证明中出现的问题
交互式证明无法上链非交互式证明在验证的过程数据量过大,无法在一个交易的扩展部分中进行说明。方法:将过大的数据量进行简洁处理,使用Merkle Tree做多次Hash。零知识证明相关理论
一、交互证明系统
交互证明系统中进行证明者和验证者之间的信息交换。通过信息交换,参与方证明某个声明成立。
1、交互证明的性质:
完备性:正确的声明“验证者”总是接受。可靠性:错误的生命“验证者”总是拒绝。交互式:证明者和验证者之间采用交互形式完成证明过程2、交互证明系统的定义:
一个0,1组成的字符串称为语言L,一对交互图灵机<P,V>,P表示证明者(拥有无限计算能力),V表示验证者(在概率多项式时间内可验证)称<P,V>为语言L的交互证明系统,满足以下条件:a. 完备性:Pr[(P,V)(x) = 1|x属于L] <= 1 - negl(|x|)
b. 可靠性:Pr[(P*,V)(x) = 0|x不属于L] >= 1 - negl(|x|)
3、IP语言类
拥有交互证明系统的语言类称为IP语言类。二、零知识证明
零知识证明是交互证明系统的一个实例,目标是:证明某一个事实且不泄漏知识。
1、定义
在交互证明系统基础上增加零知识性(验证者无法从该证明过程中获得额外的信息)。
零知识:在任意概率多项式时间验证者V*,都存在一个概率多项式时间的模拟器S(代表未参与验证的局外人),使得任意x属于L:<P,V*>(x) ~=c S(x)
2、零知识性的三种形式
计算零知识性:没有有效算法区分两个分部统计零知识性:统计距离可忽略完美零知识性:两个分布同分布利用零知识证明的应用
一、小零币(Zerocoin)
铸币过程中只公布序列号的承诺(序列号与身份绑定),使得承诺与拥有者割裂开,没有指定币值。
1、做法
a. 生成一个序列号S和随机密钥rb. 生成序列号s的承诺Commit(S,r),可以充当该币地址c. 在区块链`bitcoin的链`上公布承诺(烧币)
2、如何花小零币
a. 将铸好的小零币注入零币池中,构建承诺对象中r的集合b. 交易时,交易包涵序列号S和自己能打开承诺的声明c. 矿工验证零知识证明,认为你可以打开区块链中一个零币d. 矿工查询序列号S确认没被花费过e. 花费交易的输出形成一个新的零币,用自己比特币拥有地址来作为输出地址
二、大零币(ZeroCash)
引入了zk-SNARKs提升效率,可以隐藏交易数额。