Fiat-Shamir heuristic 阅读资料

Whisker17 commented 3 years ago

Whisker17 commented 3 years ago

Whisker17 commented 3 years ago

Whisker17 commented 3 years ago

Whisker17 commented 3 years ago

关键点就在于引入了一个 random oracle ,一般就用 hash 来代替,这样就可以忽略交互的信息,而使用当前存在的具有权威性的数据作为保障

Whisker17 commented 3 years ago

Fiat-Shamir Heuristic是一个1988年被提出的算法，可以把任何交互式的随机验证协议(Public-coin Protocol)转换为非交互式的协议。

首先，我们需要随便定义一个交互式的随机验证协议：

接下来，我们用Fiat-Shamir Heuristic把转换成非交互协议。

首先，我们需要一个安全的哈希函数（cryptographic hash function）。我们同时也需要假设这一类哈希函数是一个随机预言机，也就是说，无论输入的是什么，输出的值我们都可以看作是一个和输入没有关联的随机数。

当我们有了这个假设之后，我们就可以把交互式协议压缩成非交互式协议了：

当验证方收到证明之后，他只需要根据这几个数字和哈希函数重新生成就可以验证证明是否准确了。

通过巧妙运用哈希函数，我们把整个协议变成了非交互式的：证明方可以一口气生成所有的内容，发给验证方之后就可以走人了。验证方则可以在任何时候打开证明，计算出随机数并且验证证明。这样一来，证明方甚至可以把证明直接发到网上，然后验证方可以定期下载这些证明并且验证它们。

Whisker17 commented 3 years ago

下图是一个交互式的随机验证协议：

然后我们引入 random oracle（此处就是一个 hash 函数）将交互式转化为非交互式：

Whisker17 / zkpThings