nil Foundation的Placeholder证明系统（2）

前序博客：

• nil Foundation的Placeholder证明系统（1）

=nil; Foundation团队2022年11月论文《Placeholder证明系统》。[2022年11月29日版本]

8. 优化

8.1 Batched FRI

不同于单独检查每个commitment，可对其进行FRI聚合。如对多项式$f_0,\cdots ,f_k$：

• 1）从transcript中获取$\theta$。
• 2）计算$f=f_0\cdot {\theta }^{k-1}+\cdots +f_k$。
• 3）基于$f$运行FRI，using oracles to $f_0,\cdots ,f_k$。

从而可对所有committed polynomials只允许依次FRI实例。详细参看RedShift论文。

8.2 Hash By Column

不同于对每个多项式都进行commit，可对多个多项式采用相同的Merkle tree，这样可降低Prover所需提供的Merkle tree paths数量。
详细参看RedShift论文。

8.3 Hash By Subset

每个$i+1$ FRI round假定Prover发送all elements from a coset $H\in 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参数

令$\mathbf{RS}[\mathbb{F},D,\rho ]$为Reed-Solomon code family。此处有$|D|=n=2^k,\rho =2^{-R}(k,R\mathbb{N})$。这意味着committing polynomials的degree bound为$d=2^{k-R}$。
令$r\in [1,\log d=\hat{n}]$为FRI inner rounds数，$l$为repetition参数。
相应的：

• Prover：$\mathcal{O}(n)$
• Verifier：$\mathcal{O}(\log n)$

对于每个$ϵ\in (0,1]$，令$J_{ϵ}:[0,1]\to [0,1]$函数为：
$J_{ϵ}(X)=1-\sqrt{1-X(1-ϵ)}$

假设$\Delta (f,\mathbf{RS})=\delta >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。
令$d$为the smallest power of two，使得$d\ge N_{rows}$。在Placeholder中，$d$定义为the highest degree of polynomials that can be committed by FRI instance。
令$w$为$d$-th root of unity。有$d=2^{\hat{n}}$，且$\hat{n}\ge N_{rows}$。

用$\mathbf{RS}[\mathbb{F},D,\rho ]$来表示FRI commitments，其中：

• $\mathbb{F}$：与PLONK arithmetization中的field相同。
• $D$：为domain of $n=2^k=2^{\hat{n}+R}$ root of unity。
• $\rho =2^{-R}$：为可调整的参数。

Soundness error定义为：
${ϵ}_{\pi }(\delta )\le \max ({ϵ}_{FRI}(\delta ),{ϵ}_{IOP}^N,\frac{1}{\mathbb{F}})$
其中，${ϵ}_{IOP}^N=(J_{p,\nu }{)}^8\cdot \frac{4n}{\mathbb{F}/D}$

令$\log |\mathbb{F}|=255,\nu =|\mathbb{F}{|}^{-1/20},D=2^{28}$，其对${ϵ}_{IOP}^N$的error contribution量级为$2^{-128}$。
令$\rho =1/16$，根据上面的FRI error公式，为达到80 bits security ，需要40个verifier queries（$\lambda$）。
【注意，以上参数并未考虑借助”grinding“技术，可进一步降低queries数量。】

10. Circuit性能评估

关键标识有：

标识	含义
$n$（对应之前$N_{rows}$）	Rows的数量
$N_{witness}$	Witness Columns（又名”Advice Columns“）的数量
$N_{perm}$	包含在Permutation Argument中的Witness Columns数量
$N_{sel}$	Circuit中所使用的Selectors数量
$N_{lookup}$	Lookup Constraints数量
$N_c$	Constraints Polynomials数量【根据RedShift论文，Constraint Polynomials：由Selector Polynomials ${\mathbf{q}}_{\mathbf{L}},{\mathbf{q}}_{\mathbf{R}},{\mathbf{q}}_{\mathbf{O}},{\mathbf{q}}_{\mathbf{M}},{\mathbf{q}}_{\mathbf{C}}$ 和 Permutation Polynomials {Sidi(X)}i=13,{Sσj(X)}j=13\{S_{id_i}(X)\}_{i=1}^3, \{S_{\sigma_j}(X)\}_{j=1}^3{Sidi​​(X)}i=13​,{Sσj​​(X)}j=13​组成】
$N_{PI}$	Public input Columns数量
$w_i$	Witness Polynomials，其中$0\le i<N_{witness}$
$c_j^{(i)}$	Constraints Polynomials，其中$0\le i<N_{sel}$
${\mathbf{gate}}_i$	Gate Polynomials，$0\le i<N_{sel}$。Gate Polynomials for Selector $q_i(X)$ and Constraints {cj(i)}j=0ni′−1\{c_j^{(i)}\}_{j=0}^{n_i'-1}{cj(i)​}j=0ni′​−1​
$P{I}_i$	Public input Polynomials，其中$0\le i<N_{PI}$
$\sigma (col:i,row:j)=(col:i^{\prime },row:j^{\prime })$	Permutation over the Table
$\mathbf{o}$	Set of all Offsets。
${\mathbf{f}}_i$	Witness polynomials，$0\le i<N_{witness}$
${\mathbf{f}}_{c_i}$	Constant-related polynomials，$0\le i<N_{const}$
$H_c$	Commitment hash
$H_r$	Random Oracle hash
$l_{H_c}$	Number of bits in commitment hash
$l_{H_r}$	Number of bits in random oracle hash

10.1 Proof Size

Proof中包含：

• $f_{0,comm},\cdots ,f_{N_{witness}-1,comm}$：对witness多项式的承诺值。
• $A_{comm}^{\prime },S_{comm}^{\prime }$：为lookup承诺值。
• $P_{comm},Q_{comm}$
• $V_{comm}$：lookup相关
• $T_{0,comm},\cdots ,T_{N_{perm}-1,comm}$
• Values and paths with size $\log n$：
  • $f_i(y)$ for $i\in [0,N_{witness}-1]$
  • $P(y),P(yw),Q(y),Q(yw)$
  • $T_j(y)$ for $j\in [0,N_{perm}-1]$
  • $A^{\prime }(y),S^{\prime }(y),V(y),A^{\prime }(y{w}^{-1}),V(yw)$
  • Gate-depending $f_i(y{w}^{\mu })$
• For circuit polynomials：区分point values
• Evaluation proof for the values above（$l$次）：

附录 nil Foundation系列博客

• nil Foundation的Solana-Ethereum Bridge Based on Light-Client State Proof Verification
• nil Foundation的基于Solana light client实现的zk-bridge方案
• nil Foundation的Mina-＞以太坊 bridge原型已完成
• nil Foundation的Mina-Ethereum State Proof Verification Applications
• nil Foundation的in-EVM Full Mina State Verification
• nil Foundation的Placeholder证明系统（1）
• zkLLVM：nil Foundation开发的电路编译器

参考资料

[1] ZCash Halo2 Lookup argument
[2] ZCash Halo2 Permutation argument