sonobe：针对IVC的fold arithmetic电路实例

1. 引言

近日，arnaucube发推宣称 在EVM链（Optimistic）上验证了首个Nova+CycleFold proof，对应开源代码实现见：

• https://github.com/privacy-scaling-explorations/sonobe（Rust + Solidity）

sonobe为：

• 0xPARC和PSE团队联合开发的folding schemes库
• 采用模块化结构
• 用于Incremental Verifiable computation (IVC) 场景
• 支持多个folding schemes和decider setups，支持用户按需选择
• 致力于将folding schemes推向实用化，并促进其proof在EVM链上的验证。

所谓folding scheme，是指高效证明：
$z_n=F(\cdots F(F(F(F(z_0,w_0),w_1),w_2),\cdots ),w_{n-1})$
其中：

• $w_i$为每个递归步骤中额外的witness。

Sonobe基本流程为：

• 1）定义要折叠的电路，即前端，支持arkworks、Circom、Noir等。

• 2）设置所使用的folding scheme方案，如Nova+CycleFold。CycleFold改进了Nova中的cycle of curves使用：
  
  其中，Nova电路与CycleFold电路之间的组合方式为：
  

• 3）设置生成final proof的final decider，如基于Pasta curves的Spartan、基于BN254的Groth16等。分链上链下两大类：

  • 3.1）On-chain decider
    
  • 3.2）Off-chain decider

• 4）生成decider verifier。

当前已实现的Folding schemes有：

• Abhiram Kothapalli、Srinath Setty 和 Ioanna Tzialla 2021年论文 Nova: Recursive Zero-Knowledge Arguments from Folding Schemes
• Abhiram Kothapalli 和 Srinath Setty 2023年论文 CycleFold: Folding-scheme-based recursive arguments over a cycle of elliptic curves

正在实现中的Folding schemes有：

• Abhiram Kothapalli 和 Srinath Setty 2023年论文 HyperNova: Recursive arguments for customizable constraint systems
• Liam Eagen 和 Ariel Gabizon 2023年论文 ProtoGalaxy: Efficient ProtoStar-style folding of multiple instances

2. Sonobe用例

2.1 sonobe-btc：链上Bitcoin light client

sonobe-btc 为利用Sonobe实现的链上Bitcoin light client：

• 使用Nova来验证比特币上前10万个区块的proof of work
• 在Optimistic L2链上以Groth16来做该zkSNARK IVC proof验证

开源代码见：

• https://github.com/dmpierre/sonobe-btc（Solidity+Rust）

运行该light client的开销有：

• 33h of compute on an aws ec2 c6i.4xlarge instance (16 cores, 32gb RAM) = 26.64 USD
• Contract deployment + verification on Optimism = 0.91 USD，交易详情见：https://optimistic.etherscan.io/address/0x83c2acbbcc5e223be030288b5e5afb0b80e96f3f

参考资料

[1] 2024年4月19日arnaucube twitter 在EVM链上验证了首个Nova+CycleFold proof
[2] sonobe docs