零知识证明
2022年11月14日 in 中国科学院大学
数独解的例子解释零知识证明
如何证明数独有解?不能直接给出解(数据保护问题:数独题目存在价值)。
一、零知识证明方法:
- 承诺
将谜底卡片扣在桌子上,谜面卡片放在桌子上。(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)
铸币过程中只公布序列号的承诺(序列号与身份绑定),使得承诺与拥有者割裂开,没有指定币值。文章来源:https://www.toymoban.com/news/detail-783968.html
1、做法
a. 生成一个序列号S和随机密钥r
b. 生成序列号s的承诺Commit(S,r),可以充当该币地址
c. 在区块链`bitcoin的链`上公布承诺(烧币)
2、如何花小零币
a. 将铸好的小零币注入零币池中,构建承诺对象中r的集合
b. 交易时,交易包涵序列号S和自己能打开承诺的声明
c. 矿工验证零知识证明,认为你可以打开区块链中一个零币
d. 矿工查询序列号S确认没被花费过
e. 花费交易的输出形成一个新的零币,用自己比特币拥有地址来作为输出地址
二、大零币(ZeroCash)
引入了zk-SNARKs提升效率,可以隐藏交易数额。文章来源地址https://www.toymoban.com/news/detail-783968.html
承诺过程
- 公钥地址和序列号与随机数r进行承诺生成commit(k)
- commit(k)和币值v与随机数s进行承诺生成commit(coin)
- 将commit(coin)上链
到了这里,关于【零知识证明】数独解的例子解释零知识证明的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!