福州绿光网站建设工作室,人力管理系统,免费创建个人商城网站,网站建设明细价格表前序博客#xff1a;
nil Foundation的Placeholder证明系统#xff08;1#xff09;
nil; Foundation团队2022年11月论文《Placeholder证明系统》。[2022年11月29日版本]
8. 优化
8.1 Batched FRI
不同于单独检查每个commitment#xff0c;可对其进行FRI聚合。如对多项…前序博客
nil Foundation的Placeholder证明系统1
nil; Foundation团队2022年11月论文《Placeholder证明系统》。[2022年11月29日版本]
8. 优化
8.1 Batched FRI
不同于单独检查每个commitment可对其进行FRI聚合。如对多项式f0,⋯,fkf_0,\cdots,f_kf0,⋯,fk
1从transcript中获取θ\thetaθ。2计算ff0⋅θk−1⋯fkff_0\cdot \theta^{k-1}\cdotsf_kff0⋅θk−1⋯fk。3基于fff运行FRIusing oracles to f0,⋯,fkf_0,\cdots,f_kf0,⋯,fk。
从而可对所有committed polynomials只允许依次FRI实例。详细参看RedShift论文。
8.2 Hash By Column
不同于对每个多项式都进行commit可对多个多项式采用相同的Merkle tree这样可降低Prover所需提供的Merkle tree paths数量。 详细参看RedShift论文。
8.3 Hash By Subset
每个i1i1i1 FRI round假定Prover发送all elements from a coset H∈D(i)H\in D^{(i)}H∈D(i)。每个Merkle leaf可包含the whole coset instead of separate values。 详细参看RedShift论文。不过RedShift作者在每个leaf中使用了更多的values从而具有更好的性能。
8.4 FRI PoW
待续。。。。
9. Placeholder参数
本节重点讨论Placeholder参数 及其对协议安全和性能的影响。
9.1 FRI参数
令RS[F,D,ρ]\mathbf{RS}[\mathbb{F},D,\rho]RS[F,D,ρ]为Reed-Solomon code family。此处有∣D∣n2k,ρ2−R(k,RN)|D|n2^k,\rho2^{-R}(k,R\mathbb{N})∣D∣n2k,ρ2−R(k,RN)。这意味着committing polynomials的degree bound为d2k−Rd2^{k-R}d2k−R。 令r∈[1,logdn^]r\in [1,\log d\hat{n}]r∈[1,logdn^]为FRI inner rounds数lll为repetition参数。 相应的
ProverO(n)\mathcal{O}(n)O(n)VerifierO(logn)\mathcal{O}(\log n)O(logn)
对于每个ϵ∈(0,1]\epsilon\in (0,1]ϵ∈(0,1]令Jϵ:[0,1]→[0,1]J_{\epsilon}:[0,1]\rightarrow [0,1]Jϵ:[0,1]→[0,1]函数为 Jϵ(X)1−1−X(1−ϵ)J_{\epsilon}(X)1-\sqrt{1-X(1-\epsilon)}Jϵ(X)1−1−X(1−ϵ)
假设Δ(f,RS)δ0\Delta(f,\mathbf{RS})\delta0Δ(f,RS)δ0则根据Eli Ben-Sasson 2019年论文 DEEP-FRI: Sampling Outside the Box Improves Soundness相应的soundness error上限为 err(δ)2log∣D∣ϵ3∣F∣(1−min{δ0,Jϵ(1−ρ)}ϵlog∣D∣)l\mathbf{err}(\delta)\frac{2\log |D|}{\epsilon^3|\mathbb{F}|}(1-\min\{\delta_0,J_{\epsilon}(1-\rho)\}\epsilon \log |D|)^lerr(δ)ϵ3∣F∣2log∣D∣(1−min{δ0,Jϵ(1−ρ)}ϵlog∣D∣)l
9.2 Placeholder参数
当前可将circuit parameters用于FRI commitments。 令ddd为the smallest power of two使得d≥Nrowsd\geq N_{rows}d≥Nrows。在Placeholder中ddd定义为the highest degree of polynomials that can be committed by FRI instance。 令www为ddd-th root of unity。有d2n^d2^{\hat{n}}d2n^且n^≥Nrows\hat{n}\geq N_{rows}n^≥Nrows。
用RS[F,D,ρ]\mathbf{RS}[\mathbb{F},D,\rho]RS[F,D,ρ]来表示FRI commitments其中
F\mathbb{F}F与PLONK arithmetization中的field相同。DDD为domain of n2k2n^Rn2^k2^{\hat{n}R}n2k2n^R root of unity。ρ2−R\rho2^{-R}ρ2−R为可调整的参数。
Soundness error定义为 ϵπ(δ)≤max(ϵFRI(δ),ϵIOPN,1F)\epsilon_{\pi}(\delta)\leq\max(\epsilon_{FRI}(\delta),\epsilon_{IOP}^N, \frac{1}{\mathbb{F}})ϵπ(δ)≤max(ϵFRI(δ),ϵIOPN,F1) 其中ϵIOPN(Jp,ν)8⋅4nF/D\epsilon_{IOP}^N(J_{p,\nu })^8\cdot \frac{4n}{\mathbb{F}/D}ϵIOPN(Jp,ν)8⋅F/D4n
令log∣F∣255,ν∣F∣−1/20,D228\log |\mathbb{F}|255,\nu|\mathbb{F}|^{-1/20},D2^{28}log∣F∣255,ν∣F∣−1/20,D228其对ϵIOPN\epsilon_{IOP}^NϵIOPN的error contribution量级为2−1282^{-128}2−128。 令ρ1/16\rho1/16ρ1/16根据上面的FRI error公式为达到80 bits security 需要40个verifier queriesλ\lambdaλ。 【注意以上参数并未考虑借助”grinding“技术可进一步降低queries数量。】
10. Circuit性能评估
关键标识有
标识含义nnn对应之前NrowsN_{rows}NrowsRows的数量NwitnessN_{witness}NwitnessWitness Columns又名”Advice Columns“的数量NpermN_{perm}Nperm包含在Permutation Argument中的Witness Columns数量NselN_{sel}NselCircuit中所使用的Selectors数量NlookupN_{lookup}NlookupLookup Constraints数量NcN_cNcConstraints Polynomials数量【根据RedShift论文Constraint Polynomials由Selector Polynomials qL,qR,qO,qM,qC\mathbf{q_L},\mathbf{q_R},\mathbf{q_O},\mathbf{q_M},\mathbf{q_C}qL,qR,qO,qM,qC 和 Permutation Polynomials {Sidi(X)}i13,{Sσj(X)}j13\{S_{id_i}(X)\}_{i1}^3, \{S_{\sigma_j}(X)\}_{j1}^3{Sidi(X)}i13,{Sσj(X)}j13组成】NPIN_{PI}NPIPublic input Columns数量wiw_iwiWitness Polynomials其中0≤iNwitness0\leq i N_{witness}0≤iNwitnesscj(i)c_j^{(i)}cj(i)Constraints Polynomials其中0≤iNsel0\leq i N_{sel}0≤iNselgatei\mathbf{gate}_igateiGate Polynomials0≤iNsel0\leq iN_{sel}0≤iNsel。Gate Polynomials for Selector qi(X)q_i(X)qi(X) and Constraints {cj(i)}j0ni′−1\{c_j^{(i)}\}_{j0}^{n_i-1}{cj(i)}j0ni′−1PIiPI_iPIiPublic input Polynomials其中0≤iNPI0\leq i N_{PI}0≤iNPIσ(col:i,row:j)(col:i′,row:j′)\sigma(col:\ i, row:\ j)(col:\ i, row:\ j)σ(col: i,row: j)(col: i′,row: j′)Permutation over the Tableo\mathbf{o}oSet of all Offsets。fi\mathbf{f}_ifiWitness polynomials0≤iNwitness0\leq i N_{witness}0≤iNwitnessfci\mathbf{f}_{c_i}fciConstant-related polynomials0≤iNconst0\leq i N_{const}0≤iNconstHcH_cHcCommitment hashHrH_rHrRandom Oracle hashlHcl_{H_c}lHcNumber of bits in commitment hashlHrl_{H_r}lHrNumber of bits in random oracle hash
10.1 Proof Size
Proof中包含
f0,comm,⋯,fNwitness−1,commf_{0,comm},\cdots,f_{N_{witness}-1,comm}f0,comm,⋯,fNwitness−1,comm对witness多项式的承诺值。Acomm′,Scomm′A_{comm},S_{comm}Acomm′,Scomm′为lookup承诺值。Pcomm,QcommP_{comm},Q_{comm}Pcomm,QcommVcommV_{comm}Vcommlookup相关T0,comm,⋯,TNperm−1,commT_{0,comm},\cdots,T_{N_{perm}-1,comm}T0,comm,⋯,TNperm−1,commValues and paths with size logn\log nlogn fi(y)f_i(y)fi(y) for i∈[0,Nwitness−1]i\in [0, N_{witness}-1]i∈[0,Nwitness−1]P(y),P(yw),Q(y),Q(yw)P(y), P(yw),Q(y), Q(yw)P(y),P(yw),Q(y),Q(yw)Tj(y)T_j(y)Tj(y) for j∈[0,Nperm−1]j\in [0, N_{perm}-1]j∈[0,Nperm−1]A′(y),S′(y),V(y),A′(yw−1),V(yw)A(y),S(y), V(y), A(yw^{-1}),V(yw)A′(y),S′(y),V(y),A′(yw−1),V(yw)Gate-depending fi(ywμ)f_i(yw^{\mu})fi(ywμ) For circuit polynomials区分point valuesEvaluation proof for the values abovelll次
附录 nil Foundation系列博客
nil Foundation的Solana-Ethereum Bridge Based on Light-Client State Proof Verificationnil Foundation的基于Solana light client实现的zk-bridge方案nil Foundation的Mina-以太坊 bridge原型已完成nil Foundation的Mina-Ethereum State Proof Verification Applicationsnil Foundation的in-EVM Full Mina State Verificationnil Foundation的Placeholder证明系统1zkLLVMnil Foundation开发的电路编译器
参考资料
[1] ZCash Halo2 Lookup argument [2] ZCash Halo2 Permutation argument
