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

0 条回复 A文章作者 M管理員
    暫無討論,說說你的看法吧