t square. We use a python style notationmat[:,i] to select the i-th column of a matrix mat。 function PC. Commit(ϕ): Parse w as 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 receives a random vector Y0∈Fk from the verifier Proximity Consistency Prover sends C1,y1,C0,y0 to the verifier. Verifier randomly samples t[n] as an array Î and send it to prover 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∈Î,CY0[idx]==and EC(Yy0)==CY0 Consistency:∀idx∈Î,C1[idx]==and EC(Y1)==C1 y== ∀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. 结语:多项式承诺是一类非常重要的密码学协议,被广泛的应用在许多密码学系统当中,尤其是零知识证明系统。本文详细介绍了多项式承诺 Brakedown 协议以及和其相关的数学知识,作为 FOAKS 很重要的底层组件,Brakedown 对 FOAKS 的实例化性能的提升起到了重要作用。 参考文献 [GLS+]:Alexander Golovnev, Jonathan Lee, Srinath Setty, Justin Thaler, and Riad S. Wahby. Brakedown: Linear-time and post-quantum snarks for r1cs. Cryptology ePrint Archive. https://ia.cr/2021/1043. [XZS22]:Xie T, Zhang Y, Song D. Orion: Zero knowledge proof with linear prover time[C]//Advances in Cryptology–CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part IV. Cham: Springer Nature Switzerland, 2022: 299-328.https://eprint.iacr.org/2022/1010 [BCG20]:Bootle, Jonathan, Alessandro Chiesa, and Jens Groth. "Linear-time arguments with sublinear verification from tensor codes." Theory of Cryptography: 18th International Conference, TCC 2020, Durham, NC, USA, November 16–19, 2020, Proceedings, Part II 18. Springer International Publishing, 2020. Justin Thaler from A16zcrypto, Measuring SNARK performance: Frontends, backends, and the future https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/ 张量积的介绍:https://blog.csdn.net/chenxy_bwave/article/details/127288938 来源:金色财经lg...