談到 ZKP 算法，大伙可能聽過一些，比如 zk-snark、zk-stark、bulletproof、aztec、 plonk 等等，今天，ZKSwap 團隊就和大伙聊聊這一對“表面兄弟”，zk-stark 和 zk-snark 算法的異同之處，
首先，先從名字說起，
如下圖所示，我們將名稱 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
- 相同點
- 都實現了將隱私的輸入可靠隱藏；
- 都是基于知識論證，不知道 private input 的 prover 生成不了有效的 proof；
- 都可以實現交互式與非交互式式的算法，只是取決于 randomness 是由誰來生成的；
- 不同點
- zk-stark 具有可擴展性，即證明和驗證的耗時與原始計算的耗時分別呈擬線性關系（且線性因子為常量）和對數關系，這意味這，如果原始輸入的數據集增大 1000000 倍，zk-stark 的證明耗時增加線性倍數的時間，但驗證時間僅僅增加 21 * log1000000 =~ 420 倍。證明耗時呈線性關系基本滿足所有的ZKP算法，但是驗證時間呈對數關系，僅此一家，因此在擴展性上，zk-stark 要勝一籌，
- 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】
- 算法思想：將證明 CI statement 成立問題轉換成證明多項式等式成立問題，轉換過程用到了算術環路和 QAP 方法；
- 多項式等式成立意味著什么？（圖中黃色部分） a. 等式兩邊可以看作兩個度相等的多項式，假設為 n，其交點最多有 n 個，假如在一個很大的域范圍內隨機選一個點，如果的兩個多項式在此點的值相等，則證明兩個多項式是相等的。 b. 我們可以看到，等式右邊的多項式因子 Z 是目標多項式，它的零點就是右邊整體多項式的零點，也就是等式左邊整體多項式的零點，而等式左邊的多項式在這些零點的取值，就轉換成了一個個的算術電路里每個乘法門對應的一階線性約束等式（R1CS）成立，即原始計算等式成立（注：R1CS 由原始計算等式分解得到）；
- 算法分為三個步驟：CRS 生成；證明者證明；驗證者驗證；
- 可以看到 prover 生成證明過程中，沒有與驗證者交互，因此是 non-interative;
- 如何保證 prover 用于生成證明的 A/B/C/H 是多項式且是小于某個度數呢？ a. 通過 trusted party 來保證，因為它是可信任的，因此它生成 pk，vk 用到的 A/B/C 等肯定是多項式并且是小于某個度的； b. 如果證明者作惡，那么驗證者將會很大概率驗證失敗； c. 主要用到了同態加密 HH 和系數知識假設 KCA 和橢圓曲線雙線性配對等數學知識；
- zk-stark ALG 【1】【2】【3】
- 算法思想：將證明 CI statement 成立問題轉化成證明多項式小于某個度的問題，轉換過程用到了多項式插值方法；
- 多項式等式成立意味著什么？（圖中黃色部分）
思想與 zk-snark 一樣，T同樣為目標多項式，其零點已知且公開，也是等式左側多項式 Q 的零點，多項式 Q 在每一個零點的取值都對應了一個 execute trace 的成立（沒錯，在 zk-stark 中，原始計算語句轉化成了多個 execute trace，這類似與 zk-snark 中的R1CS）。因此多項式相等，意味著 execute trace 正確，說明原始 CI 成立。
- 多項式小于某個度意味著什么？
和 zk-snark 類似的是，兩者都把 CI statement 轉換成了證明多項式等式成立的問題（可以這么抽象的認為，zk-stark 不僅要證明多項式相等，還要證明相應多項式是小于某個度的，這是 zk-stark 算法的核心，所以才有了第一點的描述），為了防止驗證者作惡，必須要保證多項式是低于某個度的（存在這樣一種可能，攻擊者可以特意生成滿足證等式的一些點，這些點并不是真正的多項式上的點，但是根據這些點生成的證據也能通過驗證者驗證）。不同的是，zk-snark 使用了 trusted party 機制 和 同態加密等數學方法，而 zk-stark 使用了低度測試等數學方法，當且僅當多項式真正的小于某個度時，多項式的相等才是真實意義上的相等，說明生成軌跡多項式的 execute trace 是正確的，即原始 CI 成立，
- 算法分為兩大步驟，算術化和低度測試； a. 算術化：是把問題轉化為多項式形式 b. 低度測試：是證明組合多項式(圖中黃色)和軌跡多項式（圖中綠色）小于某個固定的度–>FRI算法
- 在生成證明的過程中，有交互（圖中紅線所示），所以圖中描述的是交互式的零知識證明算法；
Summary
以上分別從概念和算法上介紹了 zk-snark 和 zk-stark 算法的異同之處，作為引文，后續發文將深入詳細價紹 zk-stark 算法的原理，如有錯誤，麻煩批評指正，謝謝。
