您的位置:首頁 > 區(qū)塊鏈 >

Zk-stark算法具有可擴展性 其證明耗時可增加倍數(shù)的時間

2019-11-15 17:49:46 來源: 區(qū)塊網(wǎng)

Concept:zk-stark vs zk-snark談到ZKP算法,大伙可能聽過一些,比如zk-snark,zk-stark, bulletproof, aztec, plonk等等。今天,咱就給

Concept:zk-stark vs zk-snark

談到ZKP算法,大伙可能聽過一些,比如zk-snark,zk-stark, bulletproof, aztec, plonk等等。今天,咱就給大伙聊聊這一對“表面兄弟”,zk-stark和zk-snark算法的異同之處。

不如,先讓我們從名稱說起?畢竟,兩個看起來都很厲害的亞子^_^ !

如下圖所示,我們將名稱zk-stark 和 zk-snark根據(jù)功能特點分別分成四個部分,然后逐個比較分析。

Zk-stark => zk - s t ark

· zk:零知識,表明隱私的輸入將會被隱藏,除了證明者,其他任何人不會看見;

· s:可擴展的,和Replay Computation的驗證耗時相比,zk-stark的證明和驗證耗時分別與之呈擬線性關系和對數(shù)關系;

· t:透明的,zk-stark算法沒有CRS setup by Trusted party;

· arg:知識論證,只有知道private input的prover,才能生成有效的proof;

Zk-snark => zk - s n ark

· zk:零知識,表明隱私的輸入將會被隱藏,除了證明者,其他任何人不會看見;

· s:簡潔的,指的是生成的proof足夠小和驗證時間足夠短;

· n:非交互式的,Prover生成證明的過程中和verifier沒有交互;

· arg:知識論證,只有知道private input的prover,才能生成有效的proof;

Compare

· 相同點

1. 都實現(xiàn)了將隱私的輸入可靠隱藏;

2. 都是基于知識論證,不知道private input的prover生成不了有效的proof;

3. 都可以實現(xiàn)交互式與非交互式式的算法,只是取決于randomness是由誰來生成的;

· 不同點

1. zk-stark具有可擴展性,即證明和驗證的耗時與原始計算的耗時分別呈擬線性關系(且線性因子為常量)和對數(shù)關系,這意味著,如果原始輸入的數(shù)據(jù)集增大1000000倍,zk-stark的證明耗時增加線性倍數(shù)的時間,但驗證時間僅僅增加21*log1000000 =~ 420倍。證明耗時呈線性關系基本滿足所有的ZKP算法,但是驗證時間呈對數(shù)關系,僅此一家,因此在擴展性上,zk-stark要勝一籌。

2. zk-stark同樣具有簡潔性,但是是驗證簡潔性。所謂簡潔性,通常是指即使驗證程序很大,生成的proof size也不會很大,同時又能很快的完成驗證(比native computation快很多)。相比對zk-snark,zk-stark的proof size要大的多,因此在簡潔性上,zk-snark要勝一籌。

ALG compare

前面從概念上對zk-stark 和 zk-snark算法做了比較,其異同點可以籠統(tǒng)的概括為:

· 都是基于知識論證的ZKP算法;

· zk-stark不需要zk-snark的Trusted party 設置CRS,因此是Transparent;

· zk-stark的驗證耗時與native computation 耗時呈對數(shù)關系,因此是Scalable;

下面,我們將從算法層面,去做相對更深入一些的比較分析:

· zk-snark ALG 【4】

1. 算法思想:將證明CI statement成立問題轉換成證明多項式等式成立問題,轉換過程用到了算術環(huán)路和QAP方法;

2. 多項式等式成立意味著什么?(圖中黃色部分)

a. 等式兩邊可以看作兩個度相等的多項式,假設為n,其交點最多有n個,假如在一個很大的域范圍內(nèi)隨機選一個點,如果的兩個多項式在此點的值相等,則證明兩個多項式是相等的。

b. 我們可以看到,等式右邊的多項式因子Z是目標多項式,它的零點就是右邊整體多項式的零點,也就是等式左邊整體多項式的零點,而等式左邊的多項式在這些零點的取值,就轉換成了一個個的算術電路里每個乘法門對應的一階線性約束等式(R1CS)成立,即原始計算等式成立(注:R1CS由原始計算等式分解得到);

3. 算法分為三個步驟,CRS生成;證明者證明;驗證者驗證;

4. 可以看到prover生成證明過程中,沒有與驗證者交互,因此是non-interative;

5.如何保證prover用于生成證明的A/B/C/H是多項式且是小于某個度數(shù)呢?

a.通過trusted party 來保證,因為它是可信任的,因此它生成pk,vk用到的A/B/C等肯定是多項式并且是小于某個度的;

b. 如果證明者作惡,那么驗證者將會很大概率驗證失敗;

c. 主要用到了同態(tài)加密HH和系數(shù)知識假設KCA和橢圓曲線雙線性配對等數(shù)學知識;

· zk-stark ALG 【1】【2】【3】

1. 算法思想:將證明CI statement成立問題轉化成證明多項式小于某個度的問題,轉換過程用到了多項式插值方法;

2. 多項式等式成立意味著什么?(圖中黃色部分)

思想與zk-snark一樣,T同樣為目標多項式,其零點已知且公開,也是等式左側多項式Q的零點,多項式Q在每一個零點的取值都對應了一個execute trace的成立(沒錯,在zk-stark中,原始計算語句轉化成了多個execute trace,這類似與zk-snark中的R1CS)。因此多項式相等,意味著execute trace 正確,說明原始CI成立。

3. 多項式小于某個度意味著什么?

和zk-snark類似的是,兩者都把CI statement轉換成了證明多項式等式成立的問題(?可以這么抽象的認為,zk-stark不僅要證明多項式相等,還要證明相應多項式是小于某個度的,這是zk-stark算法的核心,所以才有了第一點的描述)。

為了防止驗證者作惡,必須要保證多項式是低于某個度的(?存在這樣一種可能,攻擊者可以特意生成滿足驗證等式的一些點,這些點并不是真正的多項式上的點,但是根據(jù)這些點生成的證據(jù)也能通過驗證者驗證)。不同的是,zk-snark使用了trusted party機制 和 同態(tài)加密等數(shù)學方法,而zk-stark使用了低度測試等數(shù)學方法。當且僅當多項式真正的小于某個度時,多項式的相等才是真實意義上的相等,說明生成軌跡多項式的execute trace 是正確的,即原始CI成立。

4. 算法分為兩大步驟,算術化和低度測試;

a.算術化:是把問題轉化為多項式形式

b. 低度測試:是證明組合多項式(圖中黃色)和軌跡多項式(圖中綠色)小于某個固定的度-->FRI算法

5. 在生成證明的過程中,有交互(圖中紅線所示),所以圖中描述的是交互式的零知識證明算法;

Summary

以上分別從概念和算法上介紹了zk-snark和zk-stark算法的異同之處,作為引文,后續(xù)發(fā)文將深入詳細介紹zk-stark算法的原理。如有錯誤,麻煩批評指正,謝謝。(江小白)

關鍵詞: Zk-stark算法 證明耗時 時間

精選 導讀

募資55億港元萬物云啟動招股 預計9月29日登陸港交所主板

萬科9月19日早間公告,萬物云當日啟動招股,預計發(fā)行價介乎每股47 1港元至52 7港元,預計9月29日登陸港交所主板。按發(fā)行1 167億股計算,萬

發(fā)布時間: 2022-09-20 10:39
管理   2022-09-20

公募基金二季度持股情況曝光 隱形重倉股多為高端制造業(yè)

隨著半年報披露收官,公募基金二季度持股情況曝光。截至今年二季度末,公募基金全市場基金總數(shù)為9794只,資產(chǎn)凈值為269454 75億元,同比上

發(fā)布時間: 2022-09-02 10:45
資訊   2022-09-02

又有上市公司宣布變賣房產(chǎn) 上市公司粉飾財報動作不斷

再有上市公司宣布變賣房產(chǎn)。四川長虹25日稱,擬以1 66億元的轉讓底價掛牌出售31套房產(chǎn)。今年以來,A股公司出售房產(chǎn)不斷。根據(jù)記者不完全統(tǒng)

發(fā)布時間: 2022-08-26 09:44
資訊   2022-08-26

16天12連板大港股份回復深交所關注函 股份繼續(xù)沖高

回復交易所關注函后,大港股份繼續(xù)沖高。8月11日大港股份高開,隨后震蕩走高,接近收盤時觸及漲停,報20 2元 股。值得一提的是,在7月21日

發(fā)布時間: 2022-08-12 09:56
資訊   2022-08-12

萬家基金再添第二大股東 中泰證券擬受讓11%基金股權

7月13日,中泰證券發(fā)布公告,擬受讓齊河眾鑫投資有限公司(以下簡稱齊河眾鑫)所持有的萬家基金11%的股權,交易雙方共同確定本次交易的標的資

發(fā)布時間: 2022-07-14 09:39
管理   2022-07-14

央行連續(xù)7日每天30億元逆回購 對債市影響如何?

央行12日再次開展了30億元逆回購操作,中標利率2 10%。這已是央行連續(xù)7日每天僅進行30億元的逆回購縮量投放,創(chuàng)下去年1月以來的最低操作規(guī)

發(fā)布時間: 2022-07-13 09:38
資訊   2022-07-13

美元指數(shù)創(chuàng)近20年新高 黃金期貨創(chuàng)出逾9個月新低

由于對美聯(lián)儲激進加息的擔憂,美元指數(shù)11日大漲近1%創(chuàng)出近20年新高。受此影響,歐美股市、大宗商品均走弱,而黃金期貨創(chuàng)出逾9個月新低。美

發(fā)布時間: 2022-07-13 09:36
資訊   2022-07-13

美股三大股指全線下跌 納斯達克跌幅創(chuàng)下記錄以來最大跌幅

今年上半年,美股持續(xù)回落。數(shù)據(jù)顯示,道瓊斯指數(shù)上半年下跌15 3%,納斯達克綜合指數(shù)下跌29 5%,標普500指數(shù)下跌20 6%。其中,納斯達克連續(xù)

發(fā)布時間: 2022-07-04 09:51
推薦   2022-07-04

融資客熱情回升 兩市融資余額月內(nèi)增加超344億元

近期A股走強,滬指6月以來上漲4%,融資客熱情明顯回升。數(shù)據(jù)顯示,截至6月16日,兩市融資余額1 479萬億元,月內(nèi)增加344 67億元,最近一個半

發(fā)布時間: 2022-06-20 09:41
資訊   2022-06-20

4個交易日凈買入超百億元 北向資金持續(xù)流入A股市場

北向資金凈流入態(tài)勢延續(xù)。繼6月15日凈買入133 59億元后,北向資金6月16日凈買入44 52億元。自5月27日至今,除6月13日以外,北向資金累計凈

發(fā)布時間: 2022-06-17 09:37
推薦   2022-06-17