# 定义「知识可靠性」

## 引言

「知识证明」关心的不只是「这个陈述是不是正确的」，而是「你是否知道为什么这个陈述是正确的」。「陈述是正确的」并不意味这「你知道为什么这个陈述是正确的」，完全存在如下可能：你在不知道该陈述为什么是正确的「证据」的同时可以生成「该陈述是正确的」零知识证明。反过来如果「陈述是错误」的，那么你是不可能「知道」相应的「并不存在」的证据的。

比如说有一个公钥$h=g^{x}$ ，你想要证明你拥有私钥$x$从而证明你的身份。如果你只是调用对任意$\mathcal{NP}$语言的零知识证明系统去证明$h \in L$，其中$L=\left\{h \mid \exists x: g^{x}=h\right\}$。（回想教科书里的零知识证明都是在证明某个陈述$x\in L$，该系统满足完备性，可靠性和零知识性。），你只需要永远发送信息“Yes"即可。这是一个合法的零知识证明系统，但这当然是远远不够的，因为对于任意一个群元素$h$，其对应的私钥$x$一定「存在」。你要去证明的是「我知道相对应的私钥」，而不仅仅是「对应的私钥存在」。

在定义「知识证明」之前先来回顾一下一个哲学家们争论了几千年也没有结果的问题：「什么是知识？」[维基百科](https://en.wikipedia.org/wiki/Knowledge)中对「知识」定义如下：Knowledge is a familiarity or awareness, of someone or something。这个定义因为无法量化，涉及主观和内隐的东西，并不能令人满意。（关于「知识」和「信息」关系的更多讨论，请参考我[之前的文章](https://hackmd.io/@Kurt-Pan/S1YokJnc5)）于是秉持「实用主义」的计算机科学家开始尝试用「输出」来定义「知识」，使得「知识」变为具体的可以进行检验和处理的东西。这种思想迁移到计算机世界中就是「图灵机」的输出，这也和图灵本人定义「人工智能」的「[行为主义](https://zh.wikipedia.org/zh-hans/%E8%A1%8C%E4%B8%BA%E4%B8%BB%E4%B9%89)」观点是一致的。

> 如果机器「知道」一个东西，它可以将其「输出」出来。

具体一点，如果一个机器知道陈述$x$的证据，那么它就可以把该证据$w$(满足$(x,w)\in R$)输出出来。

但是这又引出了另一个困难，机器「可以」输出出来，到底是什么意思？一台机器如果把这个「知识」输出了出来，那么它当然「知道」这个知识。但是它可能从来不输出这个知识（零知识证明系统的证明者永远不会明文传输证据本身），一天到晚吹水闲聊，但是它依然可能「知道」这个知识，因为它「可以」输出这个知识。

## 知识可靠性定义

### 第1个尝试

> 机器$M$知道一个陈述$x$的证据，如果存在某个$M^\prime$输出$w$，使得$(x, w) \in R$。

这个定义有个明显的问题：人家$M^\prime$输出了$w$和你$M$有什么关系？如果二者没有关联，那并不能说明$M$也知道$w$。定义必须要和机器产生证明的行为过程有关。

### 第2个尝试
定义多项式时间预言机$K$，称为知识抽取器（knowledge extractor），可以预言访问$M$，即可以与$M$任意交互。

> 机器$M$知道一个陈述$x$的证据，如果$K^{M(\cdot)}(x)$ 输出$w$ ，使得 $(x, w) \in R$。

因为$K$是一个通用算法，所以它能输出$w$的事实就意味着$M$知道$w$。
但是这个定义依然存在问题：依然没有和机器产生证明的行为过程关联起来，$K$可能本来就知道$w$，和于$M$的交互完全无关。

### 第3个尝试

> 证明者$P^{*}$ 知道一个陈述$x$的证据，如果每当$P^{*}$使$V$相信$x$时，$K^{P^*(\cdot)}(x)$ 输出$w$ ，使得 $(x, w) \in R$。

输出证据的概率和证明者使得验证者相信的概率几乎相同。$K$是通用算法对任意$x$任意$P^*$都成立（于是不可能存储特定证据然后输出，于是可以输出$w$一定是因为$P^*$的性质），如果$P^*$可以使得$V$相信且$K$可以输出$w$，那么$M$就知道$w$。

这个定义依然存在问题，$K$输出$w$的概率和$P^{*}$使$V$相信$x$的概率相同，这会使得$K$运行时间为期望多项式时间，而且没有考虑恶意证明者通过成功调用零知识模拟器生成正确协议脚本的固有概率。

### 最终形式化定义
引入「知识错误（knowledge error ）$\kappa$」，表征恶意证明者幸运的猜对所有挑战从而调用零知识模拟器生成正确协议脚本的概率。最终的输出概率是排除掉知识错误之后的概率。

> 定义（**知识可靠性**）：一个证明系统具有带错误$\kappa$的知识可靠性，如果存在概率多项式时间$K$使得对于任意证明者$P^{*}$，如果$P^{*}$ 以概率$\epsilon>\kappa$使得$V$相信$x$，那么$K^{P^*(\cdot)}(x)$ 以至少$\epsilon(|x|)-\kappa(|x|)$的概率输出$w$ ，使得 $(x, w) \in R$。

### 等价定义
算法以$\epsilon$的概率输出意味着期望运行时间为$1/\epsilon$。

> 定义（**知识可靠性**）：一个证明系统具有带错误$\kappa$的知识可靠性，如果存在概率多项式时间$K$使得对于任意证明者$P^{*}$，如果$P^{*}$ 以概率$\epsilon>\kappa$使得$V$相信$x$，那么$K^{P^*(\cdot)}(x)$ 以期望运行时间$\frac{p o l y(|x|)}{\epsilon(|x|)-\kappa(\mid x)}$输出$w$ ，使得 $(x, w) \in R$。

## 总结
知识证明系统满足「知识可靠性（Knowledge Soundness）」，是一般证明系统里的「可靠性（Soundness)」的增强。「知识可靠性」蕴含「可靠性」，但是更强，不光证明了「陈述是正确的」，而且证明了你「知道为什么陈述是正确的」，即你知道相应的「证据」。