零知识证明
2022年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表示验证者（在概率多项式时间内可验证）
- 称
为语言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：
(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提升效率，可以隐藏交易数额。
承诺过程
- 公钥地址和序列号与随机数r进行承诺生成commit(k)
- commit(k)和币值v与随机数s进行承诺生成commit(coin)
- 将commit(coin)上链