前语

暗码学傍边的零常识证明技能在 web3 国际有着广泛的运用，包含进行隐私核算、zkRollup 等等。其间 Layer2 项目 FOX 所运用的 FOAKS 便是一个零常识证明算法。在上述的一系列运用傍边，关于零常识证明算法而言，有两方面属性极为重要，那便是算法的功率以及交互性。

算法功率的重要性不言而喻，高效的算法能够显着的降低体系运转时刻，然后降低客户端推迟，明显的提高用户体会和功率，这也是 FOAKS 致力于完成线性证明时刻的一个重要原因。

另一方面，从暗码学的视点来讲，零常识证明体系的规划往往依靠证明者和验证者的多轮交互。例如在许多介绍零常识证明的科普文章傍边都会运用的“零常识洞穴”的故事傍边，证明的完成就依靠于阿里巴巴（证明者）和记者（验证者）多轮的信息传递交互才能完成。可是事实上，在许多运用场景傍边，依靠交互会使得体系不再可用，或者极高的增加推迟。就像在 zkRollup 体系傍边，咱们期望证明者（也便是 FOX 傍边的 folder）能够在本地，不依靠于和验证者交互的情况下就核算出正确的证明值。

从这个视点说，如何将交互式的零常识证明协议改造为非交互式，便是一个很有意义的问题。在这篇文章傍边，咱们将介绍 FOX 运用经典的 Fiat-Shamir 启发式（heuristic）来生成 Brakedown 中的应战然后完成非交互式协议的进程。

零常识证明中的 Challenge

零常识证明算法随着运用的铺开而变得反常火爆，近些年也诞生了包含 FOAKS、Orion、zk-stark 等在内的各种算法。这些算法，以及暗码学界早期的 sigma 协议等的中心证明逻辑都是证明者（Prover）先将某个值发送给验证者（Verifier），验证者经过本地随机数发生一个应战（Challenge），将这个随机发生的应战值发给证明者，证明者需求真的有常识才能以大概率做出经过验证者的呼应。例如在零常识洞穴傍边，记者抛一个硬币，告知阿里巴巴从左边出来仍是从右侧出来，这儿的“左和右”便是对阿里巴巴的应战，他假如真的知道咒语，就一定能够从要求的方向走出来，否则就有一半的概率失败。

这儿咱们注意到，Challenge 的生成是一个很关键的进程，它有两个要求，随机和不行被证明者猜测。第一点，随机性确保了它的概率属性。第二点，假如证明者能够猜测应战值那就意味着协议的安全性被破坏了，证明者没有常识也能够经过验证，能够继续类比，阿里巴巴假如能猜测记者要求他从哪边出来，他即使没有咒语也能够提前进入那一边，成果表现出来一样能够经过协议。

所以咱们需求一种办法，能够让证明者自己本地生成这样一个不行猜测的随机数，一起还能够被验证者验证，这样就能够完成非交互式的协议。

哈希函数（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,c0,y0)。

咱们运用伪代码给出改造后非交互式的 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,c0,y0 to the verifier.

2. Prover computes a vector as challenge, in which = H(C1,R, r0,r1,c1,y1,c0,y0)

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 ∈ , C0 [idx] == and Ec(y0) == C0

7. Consistency: ∀idx ∈ , 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

撰文：康水跃，Fox Tech CEO；孟铉济，Fox Tech 首席科学家

来源：DeFi之道