Zk-stark算法具有可擴(kuò)展性其證明耗時可增加倍數(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ù)功能特點(diǎn)分別分成四個部分，然后逐個比較分析。

Zk-stark => zk - s t ark

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

· s：可擴(kuò)展的，和Replay Computation的驗(yàn)證耗時相比，zk-stark的證明和驗(yàn)證耗時分別與之呈擬線性關(guān)系和對數(shù)關(guān)系;

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

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

Zk-snark => zk - s n ark

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

· s：簡潔的，指的是生成的proof足夠小和驗(yàn)證時間足夠短;

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

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

Compare

· 相同點(diǎn)

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

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

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

· 不同點(diǎn)

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

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

ALG compare

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

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

· zk-stark不需要zk-snark的Trusted party 設(shè)置CRS，因此是Transparent;

· zk-stark的驗(yàn)證耗時與native computation 耗時呈對數(shù)關(guān)系，因此是Scalable;

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

· zk-snark ALG 【4】

1. 算法思想：將證明CI statement成立問題轉(zhuǎn)換成證明多項(xiàng)式等式成立問題，轉(zhuǎn)換過程用到了算術(shù)環(huán)路和QAP方法;

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

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

b. 我們可以看到，等式右邊的多項(xiàng)式因子Z是目標(biāo)多項(xiàng)式，它的零點(diǎn)就是右邊整體多項(xiàng)式的零點(diǎn)，也就是等式左邊整體多項(xiàng)式的零點(diǎn)，而等式左邊的多項(xiàng)式在這些零點(diǎn)的取值，就轉(zhuǎn)換成了一個個的算術(shù)電路里每個乘法門對應(yīng)的一階線性約束等式(R1CS)成立，即原始計(jì)算等式成立(注：R1CS由原始計(jì)算等式分解得到);

3. 算法分為三個步驟，CRS生成;證明者證明;驗(yàn)證者驗(yàn)證;

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

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

a.通過trusted party 來保證，因?yàn)樗强尚湃蔚?，因此它生成pk,vk用到的A/B/C等肯定是多項(xiàng)式并且是小于某個度的;

b. 如果證明者作惡，那么驗(yàn)證者將會很大概率驗(yàn)證失敗;

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

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

1. 算法思想：將證明CI statement成立問題轉(zhuǎn)化成證明多項(xiàng)式小于某個度的問題，轉(zhuǎn)換過程用到了多項(xiàng)式插值方法;

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

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

3. 多項(xiàng)式小于某個度意味著什么?

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

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

4. 算法分為兩大步驟，算術(shù)化和低度測試;

a.算術(shù)化：是把問題轉(zhuǎn)化為多項(xiàng)式形式

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

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