零知识证明
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提升效率，可以隐藏交易数额。
