能预测 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 系统当中使用的函数。 function PC. Commit(ϕ): 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. for i ∈ [n] do Compute the Merkle tree root Roott=Merkle.Commit(C2[:,i]) Compute a Merkle tree root R=Merkle.Commit([Root0,......Rootn-1]),and output R as the commitment. function PC. Prover(ϕ, X, R) The prover generates a random vector γ0 ∈ Fk by computing: γ0 =H(C1,R, r0,r1) Proximity: Consistency: Prover sends c1,y1,cγ0,yγ0 to the verifier. Prover computes a vector Î as challenge, in which Î = H(C1,R, r0,r1,c1,y1,cγ0,yγ0) for idx ∈ Î do Prover sends C1 [:,idx] and the Merkle tree proof of Rootidx for C2 [:,idx] under R to verifier function PC. VERIFY_EVAL(ΠX,X,y= ϕ (X),R) Proximity: ∀idx ∈ Î, Cγ0 [idx] == <γ0, c1[:,idx]=""> and Ec(yγ0) == Cγ0 Consistency: ∀idx ∈ Î, C1 [idx] == <γ0, c1[:,idx]=""> and Ec(y1) == C1 y==1, y1> ∀idx ∈ Î, Ec ( C1[:,idx]) is consistent with ROOTidx, and ROOTidx’s Merkle tree proof is valid. 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之道 来源:金色财经lg...