序言

密码算法之中的零知识证明技术的应用 web3 全球拥有广泛应用，包含开展隐私计算、zkRollup 等。在其中 Layer2 新项目 FOX 所使用的 FOAKS 就是一个零知识证明优化算法。在相关的一系列运用之中，针对零知识证明优化算法来讲，只有两个层面特性极其重要，那便是算法的效率及其互动性。

算法效率起着至关重要的作用，高效率的算法能明显的下降系统软件使用时间，从而减少手机客户端延迟时间，明显的提升用户体验和效率，那也是 FOAKS 专注于完成线形证明时长的一个重要原因。

另一方面，从密码算法的角度来说，零知识证明系统设计通常依靠证明者与验证者多次互动。比如在很多详细介绍零知识证明的科普读物之中都会采用的“零知识洞窟”故事之中，证明的完成就取决于阿里（证明者）和新闻记者（验证者）多次的信息的传递互动才能达到。但是实际上，在很多应用领域之中，依靠互动会使系统软件不会再可以用，或是非常高的提升延迟时间。就像是在 zkRollup 系统软件之中，大家期待证明者（其实就是 FOX 之中的 folder）可以在本地，不依赖和验证者互动的情况下算出正确证明值。

从这点说，如何把交互式的零知识证明协议更新改造属于非交互式，便是一个很有意义的问题。在这篇文章之中，我们将要详细介绍 FOX 应用经典 Fiat-Shamir 启发性（heuristic）来形成 Brakedown 里的考验以此来实现非交互式协议的一个过程。

零知识证明里的 Challenge

零知识证明优化算法伴随着运用的铺平逐渐变得异常火爆，近几年来也出现了包含 FOAKS、Orion、zk-stark 在内的各种各样优化算法。这种优化算法，及其登陆密码学术界早期 sigma 协议等关键证明逻辑性全是证明者（Prover）先把某一值发给验证者（Verifier），验证者根据当地随机数字产生一个考验（Challenge），把这个任意造成的考验值发送给证明者，证明者必须确实有文化才可以以很有可能作出根据验证者回应。比如在零知识洞窟之中，新闻记者抛一个硬币，告知阿里从左边出去还是对于右边出去，这儿的“左和右”便是对阿里巴巴集团考验，他如果真了解符咒，就一定能从标准的方向走出去，不然就会有一半的几率不成功。

这儿我们注意到，Challenge 的形成是一个很重要的流程，生活中有2个规定，任意且不可被证明者预测分析。第一点，偶然性确保了它几率特性。第二点，假如证明者可以预测考验值也就意味着协议安全性被破坏，证明者并没有专业知识还可以通过验证，还可以继续对比，阿里如果可以预测分析记者要求我从哪儿出去，他即便没有符咒还可以提前进入那一边，结论表达出来一样能通过协议。

所以我们要一种方法，可以让证明者自身当地形成这样一个难以预测的随机数字，同时也可以被验证者验证，那样就能实现非交互式的协议。

哈希函数（Hash Function）

哈希函数的名称对于我们来说也许应该十分熟悉，不论是在比特币的共识协议 POW 之中出任挖矿的世界数学难题，或是缩小信息量，结构信息验证码等，都是有哈希函数身影。但在以上不同类型的协议之中，其实就是应用了哈希函数的多种不同特性。

具体而言，安全哈希函数的特性包含以下几个方面：

膨胀性：确立的哈希函数能将随意长度消息压缩变成固定不动长短。

实效性：给出键入 x，测算导出 h（x）是很容易的。

抗撞击性：已知一个键入 x1，期待寻找另一个键入 x2，x1x2，h（x1）= h（x2），是艰难的。

留意，假如哈希函数达到抗撞击性，那样必定达到不可逆性，换句话说给出一个导出 y，要找到 x 达到 h（x）= y 是艰难的。在密码算法之中，没法结构出本质上肯定达到不可逆性的函数公式，可是哈希函数在实际应用之中能够基本上看作单边函数公式。

这样一来，不难发现以上这几种运用分别代表于哈希函数的几点不一样的特性，与此同时大家说，哈希函数还有一个很重要的的作用是给予偶然性，尽管密码算法基础理论之中标准的完美随机数生成器现阶段也难以结构，可是哈希函数在具体之中同样也可以当做角色，这就给大家下文推荐的 Fiat-Shamir 启发性（Heuristic）技巧带来了基本。

Fiat-Shamir 启发性（Heuristic）

实际上，Fiat-Shamir 启发性（Heuristic）就是通过哈希函数来对前边产生的脚本制作开展哈希运算，从而获得一个值，用这种值来当做考验值。

由于将哈希函数 H 看作一个随机函数，挑战是匀称随机事件被挑选，不同于证明者公开数据和约定的。安全分析觉得 Alice 不可以预测分析 H 输出，只有把它当作一个 oracle。在这样的情况下，Alice 在没有遵照协议的情形下作出合理回应的几率 ( 尤其是当他不知道必需的真相时 ) 与 H 的函数值域大小反比。

图 1: 运用 Fiat-Shamir Heuristic 完成非交互式证明

非交互式 FOAKS

在这节，大家详细展现 Fiat-Shamir 启发性在 FOAKS 协议之中的运用，主要是用于造成 Brakedown 一部分的考验，以此来实现非交互式的 FOAKS。

首先我们要见到，在 Brakedown 形成证明的流程之中，必须考验的流程是“类似性检测”及其 Merkle Tree 的证明一部分（阅读者可以参考一下其他回答《一文掌握 FOAKS 之中的代数式服务承诺协议 Brakedown》）。针对第一点本来的过程是证明者在这儿必须验证者所产生的一个随机向量，计算步骤如图所示：

图 2: 非互动证明 FOAKS 里的 Brakedown Checks

如今我们应用哈希函数，让证明者自身造成这一随机向量。

令γ0=H(C1,R, r0,r1)，相对应的，在验证者验证测算之中，也要增加这一算出γ0的流程。依据那样的结构，不难发现，在形成服务承诺以前，证明者根本无法提早预测分析考验值，因此不可以提早依据考验值来相对应的“舞弊”，其实就是相对应的形成假服务承诺值，与此同时，依据哈希函数输出偶然性，这一考验值也达到偶然性。

针对第二点，令 Î =H(C1,R, r0,r1,c1,y1,cγ0,yγ0)。

使用伪代码得出改造设计非交互式的 Brakedown 代数式服务承诺之中的证明和验证函数公式，那也是 FOAKS 系统软件之中所使用的函数公式。

1. function PC. Commit(ϕ)：
2. Parse was a k × k matrix. The prover locally computes the tensor code encoding C1，C2 ，C1 is a k × n matrix，C2 is a n × n matrix.
3. for i ∈ [n] do
4. Compute the Merkle tree root Roott=Merkle.Commit(C2[:,i])
5. Compute a Merkle tree root R=Merkle.Commit([Root0,......Rootn-1]),and output R as the commitment.
6. function PC. Prover(ϕ, X, R)
7. The prover generates a random vector γ0 ∈ Fk by computing: γ0 =H(C1,R, r0,r1)
8. Proximity:

1. Consistency:

1. Prover sends c1,y1,cγ0,yγ0 to the verifier.
2. Prover computes a vector Î as challenge, in which Î = H(C1,R, r0,r1,c1,y1,cγ0,yγ0)
3. for idx ∈ Î do
4. Prover sends C1 [:,idx] and the Merkle tree proof of Rootidx for C2 [:,idx] under R to verifier
5. function PC. VERIFY_EVAL(ΠX,X,y= ϕ (X),R)
6. Proximity: ∀idx ∈ Î, Cγ0 [idx] == <γ0, C1[:,idx]> and Ec(yγ0) == Cγ0
7. Consistency: ∀idx ∈ Î, C1 [idx] == <γ0, C1[:,idx]> and Ec(y1) == C1
8. y==1, y1>
9. ∀idx ∈ Î, Ec ( C1[:,idx])is consistent with ROOTidx, and ROOTidx’s Merkle tree proof is valid.
10. Output accept if all conditions above holds. Otherwise output reject.

结束语

很多的零知识证明优化算法在规划之时都依靠证明者与验证者彼此之间的互动，但这种交互式证明协议不应该用在追求高效，网络通信开销大的使用场景下，例如链上数据隐私保护和 zkRollup 等。根据 Fiat-Shamir 启发性（Heuristic），能够在没有毁坏协议安全系数的条件下让证明者当地生成随机数“考验”，并可以被证明者验证。依据此方法，FOAKS 一样完成了非交互式的证明，并运用在设备之中。

论文参考文献

1.Fiat, Amos; Shamir, Adi (1987). "How To Prove Yourself: Practical Solutions to Identification and Signature Problems". Advances in Cryptology — CRYPTO' 86. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 263: 186–194. doi:10.1007/3-540-47721-7_12. ISBN 978-3-540-18047-0.

2.https://www.cnblogs.com/zhuowangy2k/p/12246575.html

来源：liurui