nil Foundation的in-EVM Full Mina State Verification

1. 引言

nil Foundation系列博客有：

• nil Foundation的基于Solana light client实现的zk-bridge方案
• nil Foundation的Solana-Ethereum Bridge Based on Light-Client State Proof Verification

2021年2月，Mina Foundation和Ethereum Foundation发表联合request for proposals (RFP)，以在以太坊上支持recursive SNARK application。

该RFP会开放6周，欢迎在以太坊虚拟机上实现Pickles SNARK verification的设计和实现机制 proposals。以太坊基金会希望在以太坊上构建a verifier for Pickles SNARK，从而使得mina可be verified on Ethereum，从而可实现以太坊与mina之间的bridge。

经过严格筛选，nil Foundation赢得了120万美金的项目资金。

由于整个Mina Protocol state（archive nodes除外）都packed with the single Pickles SNARK proof （仅约22KB），因此，可将整个Mina Protocol state放入以太坊，从而可 以合理的gas cost在EVM中验证整个Mina Protocol state。 A full Mina Protocol state in-EVM verification意味着，可将所有发生在Mina链上的信息 带入到 以太坊链上，包括financial应用、provable computations等等。

2. 核心问题

核心问题在于：在EVM中直接验证Pickles SNARK非常昂贵。但是，可设计一种系统来对Pickles SNARK做某些预计算（如，计算a STARK that verifies the Pickles SNARK which itself may be efficiently verified on the EVM）。

Mina中的Pickles SNARK verifier的verification算法由以下元素组成：

• 1）根据the data of the proof，计算多个hash值。这包括了使用Poseidon hash函数 with 63 full rounds both over F p \mathbb{F}_p Fp​ and F q \mathbb{F}_q Fq​ with round constants，以及 基于 F p \mathbb{F}_p Fp​的MDS matrix 和 基于 F q \mathbb{F}_q Fq​的MDS Matrix。这一步非常便宜，可在EVM中以合理的gas实现。
• 2）检查多个arithmetic equations。这一步也很便宜，可在EVM中直接实现。
• 3）运行一个size 为 2 n 2 + 4 + ( 2 + 25 ) = 63 2n_2+4+(2+25)=63 2n2​+4+(2+25)=63的multi-scalar multiplication(MSM)运算，某些bases为fixed，某些bases为variable。这一步似乎可在EVM上以合理的效率实现，尽管要比第一步和第二步要贵。
• 4）对于每个 i i i，运行a multi-scalar multiplication over G i G_i Gi​ of size 2 n i 2^{n_i} 2ni​ with a fixed array of bases, and with scalars that can be very efficiently computed from the proof。

第4）步貌似无法直接在EVM中高效实现，除非可将计算切分为多块。

3. 引入Auxiliary STARK-based proof

Mina state verification的threshold cost为500万gas。因此，直接进行Pickles proof verification的gas不会超过500万。在Full verification of the Mina blockchain on EVM 中提出可向EVM额外提交一个STARK proof来证明a successful Pickles SNARK proof part verification，从而实现a valid in-EVM confirmation of everything what happened inside Mina。这种提交proof of successful proof verification的方法，似乎可控制在500万gas以内。

基于STARK的auxiliary proof的基本circuit中，包含的basic constraints（对应以上verification算法的第4）步）有： 令：

• 1） P 1 , P 2 P_1,P_2 P1​,P2​为MSM results。
• 2） n 1 , n 2 n_1,n_2 n1​,n2​为MSM sizes。
• 3） G 1 = [ G 1 , 0 , ⋯   , G 1 , n 1 − 1 ] , G 2 = [ G 2 , 0 , ⋯   , G 2 , n 2 − 1 ] G_1=[G_{1,0},\cdots,G_{1,n_1-1}], G_2=[G_{2,0}, \cdots, G_{2,n_2-1}] G1​=[G1,0​,⋯,G1,n1​−1​],G2​=[G2,0​,⋯,G2,n2​−1​]为the sets of fixed points。

则对于 k = 1 , 2 k=1,2 k=1,2 有：

• 1） R 0 = ( 0 : 1 : 0 ) R_0=(0:1:0) R0​=(0:1:0)
• 2） ∀ 0 ≤ i < n k : R i + 1 = R i + f ( s i , G k , i + 1 ) \forall 0\leq i < n_k: R_{i+1}=R_i+f(s_i, G_{k,i+1}) ∀0≤i