ZKSwap团队解读:ZKSync中better_better_cs如何实现聚合证明

ZKSwap团队解读:ZKSync中better_better_cs如何实现聚合证明

我们研读了 ZKSync 中 better_cs 如何?成 single proof、aggregation proof 的电路逻辑等实现。在这篇?章中,我们继续研读 ZKSync 的聚合证明,我们重点关注better_better_cs 如何?成聚合证明。

还是?上?篇的这张代码调?图,我们这篇着重讲 create_proof。

/>

我们分析的 bellman_ce 代码版本是 beta 分?,commit id 为 48441155ec7006bf7bfac553b5fb7d466d7fcd00 。Aggregation_proof 的?成

create_proof 这个函数在 bellman_ce/src/plonk/better_better_cs/proof/mod.rs 中,将近 2000 ?代码。

?体上,分为以下?个步骤:

1.基本的?些检查和预计算

2.?成 state 多项式状态和 witness 多项式状态,且为lookup table 参数?成排序好的多项式

3.构造 lookupdataholder,?于后续计算

4.对置换多项式进?乘积(grand product)计算

5.对商多项式进?计算

6.根据 lookup table 进?线性化

7.对多项式的 selectors 进? open 取值

8.增加拷?置换多项式、lookup置换的优化结果

9.使? lookup 进? query

10.对多项式的 selectors 在 z 进? open 取值

11.将最终的 lookup 值放?proof中

12.计算 z、z_omega 处的 open 值,最后组装 proof

在这个函数中,我们看到了熟悉的 MainGate 函数,从上?版如何实现聚合中,我们知道这个?于?的设计,可以实现 custom gate,达到优化电路的?的。?除开 custom gate,ZKSync 中还使?了plonkup(即 plonk + lookup table) 来提升效率。

我们在之前的?章中,已经讲解过plonkup的原理了,简单来说,就是预计算有效的input/output组成 lookup table,prover需要证明witness在这个table?,详细内容请参?ZKSwap团队解读Plookup原理。ZKSync 对 plonkup 的实现,并不是将 custom gate 和 plonkup 分开的,?是结合在?起来优化电路设计的。 我们下?看看,MainGate trait 中的接?,是如何和 plonkup 结合的。

Lookup 的使?

在上?节的 create_proof 函数中,线性化?到了 gate 的 contribute_into_linearization_for_public_inputs 函数,我们以它为例,来看看 lookup 的使?。这个代码在 bellman_ce/src/plonk/better_better_cs/cs.rs 中。

?到的传?参数有 hashmap 格式的 queried_values、单项式缓存值、随机数数组 queried_values 这个参数是在 create_proof 时,根据排序的query 列表?成的,key 是多项式,value是 Fr 值。query 列表的排序规则是先 witness、gate 的 selector 次之、gate 的setup 再次之,这个 SortedGateQueries 的结构是:

代码中,调? sort_queries_for_linearization 函数来?成 SortedGateQueries ,这个函数也在当前 mod.rs ?件中。这个函数输?参数是 gate 数组,输出即为 SortedGateQueries 。

函数会对传?的 gate 数组遍历,根据 gate 返回的多项式数组,将其按照 VariablesPolynomial,WitnessPolynomial, GateSetupPolynomial 的不同类型,将多项式存? SortedGateQueries 中。

回到 contribute_into_linearization_for_public_inputs 函数,可以看到,它会从queried_values 中,获取 a/b/c/d 的值。? Q_a/Q_b/Q_c/Q_d/Q_m的值,都是从 create_proof 刚开始?成的单项式缓存数据中取到的,也是?个lookup table 的概念。

这个单项式缓存的值是从电路的setup 获得的,即电路确定了,那么电路的?就确定了,则在?成proof时,这些数据都已经有了,可以直接将setup 预计算的结果,放? lookup table 中,查询使?数据。

最后,结合a/b/c/d和Q_a/Q_b/Q_c/Q_d,可以?常?便的构造出多项式。

另外?个 MainGate ?的接?函数,都是?样的,结合lookup table,?常容易的计算出多项式。

综上,ZKSync 将witness、gate 的 selector、setup 放?lookup table 中,在?成 proof 时,使?lookuptable,直接查询?不是再次计算,加快?成速度,提升 prover 效率。

引?

https://github.com/matter-labs/zksync

https://github.com/matter-labs/bellman

https://eprint.iacr.org/2020/315.pdf