如下圖所示，我們將名稱zk-stark 和 zk-snark根據功能特點分別分成四個部分，然後逐個比較分析。
Zk-stark => zk - s t ark
· zk：零知識，表明隱私的輸入將會被隱藏，除了證明者，其他任何人不會看見；
· s：可擴充套件的，和Replay Computation的驗證耗時相比，zk-stark的證明和驗證耗時分別與之呈擬線性關係和對數關係；
· 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. 都實現了將隱私的輸入可靠隱藏；
2. 都是基於知識論證，不知道private input的prover生成不了有效的proof；
3. 都可以實現互動式與非互動式式的演算法，只是取決於randomness是由誰來生成的；
· 不同點
1. zk-stark具有可擴充套件性，即證明和驗證的耗時與原始計算的耗時分別呈擬線性關係（且線性因子為常量）和對數關係，這意味著，如果原始輸入的資料集增大1000000倍，zk-stark的證明耗時增加線性倍數的時間，但驗證時間僅僅增加21*log1000000 =~ 420倍。證明耗時呈線性關係基本滿足所有的ZKP演算法，但是驗證時間呈對數關係，僅此一家，因此在擴充套件性上，zk-stark要勝一籌。
2. zk-stark同樣具有簡潔性，但是是驗證簡潔性。所謂簡潔性，通常是指即使驗證程式很大，生成的proof size也不會很大，同時又能很快的完成驗證（比native computation快很多）。相比對zk-snark，zk-stark的proof size要大的多，因此在簡潔性上，zk-snark要勝一籌。
ALG compare
前面從概念上對zk-stark 和 zk-snark演算法做了比較，其異同點可以籠統的概括為：
· 都是基於知識論證的ZKP演算法；
· zk-stark不需要zk-snark的Trusted party 設定CRS，因此是Transparent；
· zk-stark的驗證耗時與native computation 耗時呈對數關係，因此是Scalable；
下面，我們將從演算法層面，去做相對更深入一些的比較分析：
· zk-snark ALG 【4】
1. 演算法思想：將證明CI statement成立問題轉換成證明多項式等式成立問題，轉換過程用到了算術環路和QAP方法；
2. 多項式等式成立意味著什麼？（圖中黃色部分）
a. 等式兩邊可以看作兩個度相等的多項式，假設為n，其交點最多有n個，假如在一個很大的域範圍內隨機選一個點，如果的兩個多項式在此點的值相等，則證明兩個多項式是相等的。
b. 我們可以看到，等式右邊的多項式因子Z是目標多項式，它的零點就是右邊整體多項式的零點，也就是等式左邊整體多項式的零點，而等式左邊的多項式在這些零點的取值，就轉換成了一個個的算術電路里每個乘法門對應的一階線性約束等式（R1CS）成立，即原始計算等式成立（注：R1CS由原始計算等式分解得到）；
3. 演算法分為三個步驟，CRS生成；證明者證明；驗證者驗證；
4. 可以看到prover生成證明過程中，沒有與驗證者互動，因此是non-interative;
5.如何保證prover用於生成證明的A/B/C/H是多項式且是小於某個度數呢？
a.透過trusted party 來保證，因為它是可信任的，因此它生成pk,vk用到的A/B/C等肯定是多項式並且是小於某個度的；
b. 如果證明者作惡，那麼驗證者將會很大概率驗證失敗；
c. 主要用到了同態加密HH和係數知識假設KCA和橢圓曲線雙線性配對等數學知識；
· 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演算法的核心，所以才有了第一點的描述）。為了防止驗證者作惡，必須要保證多項式是低於某個度的（？存在這樣一種可能，攻擊者可以特意生成滿足驗證等式的一些點，這些點並不是真正的多項式上的點，但是根據這些點生成的證據也能透過驗證者驗證）。不同的是，zk-snark使用了trusted party機制 和 同態加密等數學方法，而zk-stark使用了低度測試等數學方法。當且僅當多項式真正的小於某個度時，多項式的相等才是真實意義上的相等，說明生成軌跡多項式的execute trace 是正確的，即原始CI成立。
4. 演算法分為兩大步驟，算術化和低度測試；
a.算術化：是把問題轉化為多項式形式
b. 低度測試：是證明組合多項式(圖中黃色)和軌跡多項式（圖中綠色）小於某個固定的度-->FRI演算法
5. 在生成證明的過程中，有互動（圖中紅線所示），所以圖中描述的是互動式的零知識證明演算法；
Summary
以上分別從概念和演算法上介紹了zk-snark和zk-stark演算法的異同之處，作為引文，後續發文將深入詳細介紹zk-stark演算法的原理。如有錯誤，麻煩批評指正，謝謝。
Appendix
V神三部曲，含淚拜讀 https://vitalik.ca/general/2017/11/09/starks_part_1.html
zk-stark論文 chrome-extension://cdonnmffkdaoajfknoeeecmchibpmkmg/assets/pdf/web/viewer.html?file=https%3A%2F%2Feprint.iacr.org%2F2018%2F046.pdf
starkware官方講解系列 https://medium.com/starkware/stark-math-the-journey-begins-51bd2b063c71
zk-snark論文 chrome-extension://cdonnmffkdaoajfknoeeecmchibpmkmg/assets/pdf/web/viewer.html?file=https%3A%2F%2Feprint.iacr.org%2F2013%2F879.pdf
