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

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

Concept：zk-stark vs zk-snark談到ZKP算法，大伙可能聽(tīng)過(guò)一些，比如zk-snark，zk-stark, bulletproof， aztec， plonk等等。今天，咱就給

Concept：zk-stark vs zk-snark

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

不如，先讓我們從名稱說(shuō)起?畢竟，兩個(gè)看起來(lái)都很厲害的亞子^_^ !

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

Zk-stark => zk - s t ark

· zk：零知識(shí)，表明隱私的輸入將會(huì)被隱藏，除了證明者，其他任何人不會(huì)看見(jiàn);

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

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

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

Zk-snark => zk - s n ark

· zk：零知識(shí)，表明隱私的輸入將會(huì)被隱藏，除了證明者，其他任何人不會(huì)看見(jiàn);

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

· n：非交互式的，Prover生成證明的過(guò)程中和verifier沒(méi)有交互;

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

Compare

· 相同點(diǎn)

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

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

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

· 不同點(diǎn)

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

2. zk-stark同樣具有簡(jiǎn)潔性，但是是驗(yàn)證簡(jiǎn)潔性。所謂簡(jiǎn)潔性，通常是指即使驗(yàn)證程序很大，生成的proof size也不會(huì)很大，同時(shí)又能很快的完成驗(yàn)證(比native computation快很多)。相比對(duì)zk-snark，zk-stark的proof size要大的多，因此在簡(jiǎn)潔性上，zk-snark要?jiǎng)僖换I。

ALG compare

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

· 都是基于知識(shí)論證的ZKP算法;

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

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

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

· zk-snark ALG 【4】

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

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

a. 等式兩邊可以看作兩個(gè)度相等的多項(xiàng)式，假設(shè)為n，其交點(diǎn)最多有n個(gè)，假如在一個(gè)很大的域范圍內(nèi)隨機(jī)選一個(gè)點(diǎn)，如果的兩個(gè)多項(xiàng)式在此點(diǎn)的值相等，則證明兩個(gè)多項(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)換成了一個(gè)個(gè)的算術(shù)電路里每個(gè)乘法門對(duì)應(yīng)的一階線性約束等式(R1CS)成立，即原始計(jì)算等式成立(注：R1CS由原始計(jì)算等式分解得到);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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