原標題：干貨 | 零知識證明引論（一）
作者：Cyte
繼上一次 Shor 發出了對支付網路中路由問題的全面研究之后，又有一位熱愛研究的 Nervos 小伙伴 Cyte 對零知識證明做了詳細的研究，
在這篇文章中，Cyte 會和大家介紹零知識證明 (ZKP) 的定義，并將零知識證明與 SNARK 和 STARK 這兩個概念進行辨析。
ZKP、SNARK 和 STARK 等這些密碼學概念隨著最近區塊鏈的興起變得熱⻔起來，但是，它們經常會被誤解和混用，其實，所有這些概念都屬于一個更廣義的范疇，叫做證明系統 (Proof System)，或者叫做密碼學證明（Cryptographic Proof）。零知識證明和 SNARK、STARK 之間都有交叉的部分，但并不相互包含。它們之間的關系可以用一張圖來表示，
本文將首先介紹證明系統的定義，并討論證明系統的各類性質，重點討論「零知識性」、「知識證明」、「簡潔性」和「非互動性」，特別的，如果一個證明系統具有「零知識性」，那么它就被稱為一個「零知識證明」。最后，文章會討論 SNARK 和 STARK 的定義并將其進行比較，
證明系統
一個證明系統 (Proof System) 是一個互動式協議，包含兩個參與方 Prover 和 Verifier，以及一個演算法 Setup，證明系統的作用是讓 Prover 說服 Verifier 相信一件事，我們把這件事叫做一個陳述 (Statement)，
協議開始前，需要由某人呼叫 Setup 演算法。Setup 演算法接受一些公共引數作為輸入，并輸出 Prover 和 Verifier 所需的 Setup 資訊，其中 Verifier 獲知的資訊記為 ，Prover 獲知的資訊記為 。 和 的公共部分稱為公共參考字串 (Common Reference String, CRS)，具體由誰、在什么時候呼叫 Setup 演算法，取決于證明系統的設計。協議一開始，Prover 和 Verifier 同時得到輸入陳述 。Prover 相對于 Verifier 必然要有一些額外的優勢，例如更強大的計算能力，或者得到了一些額外的輸入 ，除此之外，Prover 和 Verifier 還分別獲知了 和 ，Setup 資訊獲取的時間取決于證明系統的設計，例如，有可能是 Prover 和 Verifier 早就下載好存在各自硬碟里可以反復使用的，也可能是協議開始前當場輸入的。然后 Prover 和 Verifier 開始執行證明系統規定的協議，如果 Prover 和 Verifier 都是誠實的，那么它們都嚴格遵守協議執行。不過，也有可能某一方是惡意的，沒有按照協議規定來執行，此時會發生什么事情，取決于證明系統的安全性，如果兩方都是惡意的，它們都不遵守協議，那就和這個證明系統沒關系了。最后，Verifier 輸出 accept 或 reject，表示是否相信陳述 ，一個證明系統需要滿足兩個性質：
- 完整性 (Completeness)：如果陳述 是正確的，而 Prover 和 Verifier 都遵守這個協議，那么 Verifier 以至少 的概率輸出 accept，這里 被稱為證明系統的完整性誤差 (Completeness error)
- 可靠性 (Soundness)：如果陳述 是不正確的，此時 Prover 必然是不誠實的，而 Verifier 遵守協議，那么任何 Prover 都不能讓 Verifier 輸出 accept 的概率超過 ，這個 被稱為證明系統的可靠性誤差 (Soundness error)
這兩個要求是使得一個證明系統成立的最基本的要求。少了哪個要求，我們都可以得到符合條件但完全沒用的證明系統，例如，如果我們只要求完整性，那就無論 Prover 做什么，Verifier 永遠只輸出 accept 就好了；如果只要求可靠性，那就讓 Verifier 永遠只輸出 reject。此外，一般希望 和 都不超過 ，并且加起來小于 ，否則這個證明系統誤差太大，也近乎無用，如果將一個證明系統的可靠性只對任何計算能力受限的 Prover 成立，也就是說，計算能力無限的敵手是有可能欺騙 Verifier 的，此時這個證明系統只有計算可靠性 (Computational Soundness)，這樣的系統又稱為 論證系統 (Argument System)，相比之下，對任何 Prover 都安全的可靠性被稱為統計可靠性 (Statistical Soundness)。
證明系統的其他性質
一個證明系統還可以滿足一些其他(并非必需的)性質
- CRS 模型 (CRS model)：如果 Setup 資訊是對所有人公開可見的，即 Setup=Setup=Setup，稱這個證明系統是在 CRS 模型下的
- 互動 (Interactive) / 非互動 (Non-interactive)：如果整個互動過程只有 Prover 向 Verifier 發送一條資訊，就稱這個系統是非互動證明系統；否則這個系統就是互動式證明系統
- 可遷移 (Transferable) / 可抵賴 (Deniable)：如果陳述 是正確的，并且把互動過程發送給其他 Verifier，也能夠讓其他 Verifier 相信陳述 的正確性，這個證明系統就是可遷移的；否則這個證明系統就是可抵賴的
- 公開可驗證 (Public Verifiable) / 特定驗證者 (Designated Verifier)：如果 Setup 是對所有人公開可見的，即任何人都可以成為 Verifier，這個零知識證明系統就是公開可驗證的。否則這個系統就是針對特定驗證者的
- 公開隨機 (Public coin)：如果 Verifier 的所有訊息的選取都均勻隨機且獨立于 Prover 的訊息，就稱這個系統是公開隨機的
- 零知識 (Zero-Knowledge)：在陳述 是正確的情況下，如果除了 的正確性，Verifier 無法從互動中獲取任何其他“知識”，就稱這個系統是零知識的
- 簡潔性 (Succinctness)：如果這個證明系統是用來證明 NP 語言的，并且證明系統的通信量比證據 還要小，那么這個證明系統就具有簡潔性
例：證明兩個球的顏色不同
Setup 資訊：有兩個球
陳述 ：這兩個球顏色不同Verifier 計算能力受限 (蒙上雙眼)，Prover 具有正常的視力
- Verifier 左右手各持一個球，展示給 Prover 看。
- Verifier 把雙手放到背后，接著 (在心里) 隨機拋硬幣，如果是正面朝上，就交換左右手里的球，否則不交換。
- Verifier 把球拿出來給 Prover 看，
- Prover 告訴 Verifier 兩個球有沒有交換。
結果：如果 Prover 猜對了，Verifier 輸出 accept，否則 Verifier 輸出 reject。性質討論完整性如果兩球顏色不同，顯然 Prover 一定能以百分之百的概率猜中 Verifier 有沒有交換球可靠性如果兩球顏色相同，那么 Prover 只能盲目猜測，只有 1/2 的概率猜中。這個系統的可靠性誤差為 1/2CRS這個證明系統是在 CRS 模型下的，因為 Setup 資訊是公開的互動性這是個互動系統，因為 Prover 和 Verifier 互相發送的資訊超過一條可遷移性這個系統是不可遷移的，即可抵賴的。即使 Verifier 把互動過程記錄下來展示給其他蒙住眼的人，他們也不能確信兩個球顏色不同公開可驗證性這個系統是公開可驗證的，任何 Verifier 都可以和 Prover 進行這個協議公開隨機性這個系統不是公開隨機的，因為 Verifier 發送給 Prover 的資訊不是均勻隨機的零知識性這個系統是零知識的，因為在兩個球顏色確實不同的情況下，Prover 的猜測是 Verifier 意料之中的，除了表示陳述 x 的正確性外，沒有任何額外知識
重要性
上文中我們給出了證明系統的定義，樣例和性質，接下來我們討論證明系統的幾個重要的性質，
零知識性
零知識性用來保護誠實的 Prover 不被惡意的 Verifier 欺騙而泄露證明所需的秘密證據，
上文中已經提到了證明系統的零知識性，將其簡單描述為 Verifier 無法從互動中獲取任何“知識”，這個描述是不確切的，因為它并沒有給出一個嚴格的判斷標準。零知識性的定義本身是違直覺的：Prover 明明發送了一些位元資料給 Verifier，為什么這個系統會是“零知識”的呢？實際上，“資訊”并不等同于“知識”。如果 Verifier 獲取了資訊，但獲得這些資訊并不能讓 Verifier 計算出更多結果，或者說這些資訊是 Verifier 自己就能夠計算出來的，那么 Verifier 就沒有獲取任何“知識”，在一個證明系統的執行過程中，Verifier 獲得的所有資訊包括：；Verifier 自己的亂數；Prover 發送給 Verifier 的所有資訊 (記為 )。我們把這些資訊稱為 Verifier 的“視野”，記為 。這些資訊是 Verifier 計算過程中的所有不確定性的來源。確定了這些資訊后，其他的一切都可以確定性地計算出來，注意到， 是一個隨機變數，當 Verifier 與 Prover 執行了證明系統之后，Verifier 會獲得這個隨機變數的一個樣本，如果 Verifier 能在沒有 Prover 參與的情況下獨自采樣 ，那么這個系統就是零知識的，我們把采樣 這個隨機變數的演算法叫做模擬器 (Simulator)，根據模擬器工作方式的不同，有如下不同的定義方式：
- 非黑盒模擬器，相對應的零知識性叫做非黑盒零知識，這個零知識的定義允許每個 Verifier 都存在一個“獨家定制”的模擬器，這種定義允許模擬器針對不同的 Verifier 的實現細節來定制不同的采樣過程。
- 黑盒模擬器，對應的就是黑盒零知識，這個零知識的定義要求存在唯一的模擬器，使得對所有的 Verifier，它都能夠采樣出 ，這個唯一的模擬器不可能知道所有 Verifier 的具體實現細節，所以它只能通過黑盒呼叫的方式來訪問 Verifier，不過，模擬器對 Verifier 具有完全的控制權。模擬器可以決定 Verifier 的亂數 ，并給 Verifier 輸入任何的 Prover 訊息或 ，所以，在模擬器的眼里，Verifier 是一個黑盒的確定性演算法，
- 如果模擬器只針對誠實 Verifier，對應的是誠實 Verifier 零知識 (Honest Verifier ZK)，因為誠實 Verifier 的行為是完全在預期中的，模擬器自然可以利用這些資訊，因此這個模擬器對 Verifier 的訪問是非黑盒的。
非黑盒模擬器訪問到的資訊更多，所以非黑盒零知識性比黑盒零知識性更容易成立。而誠實 Verifier 零知識是最容易實現的。關于誠實 Verifier 零知識，這里的誠實 Verifier 更準確地說是半誠實 (Semi-Honest) 的，或者說“誠實但好奇的”。這樣的 Verifier 表面上會遵守協議，但有可能私下里試圖從訊息中提取知識。相比之下，惡意 Verifier 的行為是完全不受限制的，Verifier 可能宕機、發送不符合格式的訊息、不按協議規定的分布采樣，等等。要證明一個系統對惡意的 Verifier 滿足零知識性，就要把所有這些情況都覆寫到。模擬器是一個隨機演算法，它的輸出值也是一個隨機變數，記為 ，零知識性要求 和 這兩個隨機變數難以區分。不過，“難以區分”這個詞也有很多種版本，由此可以推出零知識證明的多種定義：
- 如果兩個隨機變數的分布是統計不可區分的，也就是它們的統計距離 (Statistical Distance) 可忽略，就稱這個證明系統是統計零知識 (Statistically Zero-Knowledge) 的；如果統計距離就是 0，又叫做完美零知識 (Perfect Zero-Knowledge) 的；
- 如果兩個隨機變數的分布是計算不可區分的，也就是任何多項式時間的隨機敵手都無法區分這兩個分布，就稱這個證明系統是計算零知識 (Computationally Zero-Knowledge)的，
注意到，零知識的定義中，只要求對于正確的陳述 ， 和 的分布難以區分，對于錯誤的陳述，我們并不關心 Verifier 能夠獲取什么知識，因為這種情況下 Prover 本身就是不誠實的，沒有必要去保護它，或者說，Prover 既然不遵守協議，那我們的協議設計得再好也保護不到它，不過，雖然 是錯誤的情況下，零知識性對 的分布不做任何假定，但如果輸入錯誤的 采樣得到的 被 Verifier 驗證通過的概率和 正確的情況下有顯著差別的話，我們就可以借此判斷 的正確性。這就意味著 只能來自一個平凡的 NP 語言，所以，對于困難的 NP 問題，把錯誤的 輸入給模擬器，得到的 也能夠以一樣的概率被驗證通過。這么一來，零知識性和可靠性豈不是矛盾的？換句話說，對于錯誤的 ，Prover 為什么不能呼叫模擬器來欺騙 Verifier？實際上，Prover 不能控制 Verifier，它也就不能為模擬器提供采樣 所需要的資源。的確，一個惡意的 Prover 可以去呼叫模擬器，但是這對它來說沒用，因為模擬器輸出的 中的 并不是正在與 Prover 互動的 Verifier 的亂數。此外，模擬器輸出的 也可能和 Verifier 收到的 不同而導致驗證不通過，不過，Prover 調起的模擬器無法獲取 Verifier 的亂數，這已經足夠保證安全性了，所以互動式證明中 即使是固定常量也沒問題，
知識證明
如果要求 Prover 必須“知道”一些資訊才能讓 Verifier 驗證通過，這個系統就被稱為知識證明 (Proof of Knowledge)，知識證明可以看做可靠性的加強版，知識證明也有計算意義下的版本，叫做知識論證 (Argument of Knowledge)，
知識證明系統通常是用來證明 NP 語言的，一個 NP 語言是指一個集合 ，使得元素 屬于 可以由一個證據 來證明，即存在一個多項式時間的演算法能夠判定 是否是 屬于 的合法證據。普通的證明系統使得 Prover 可以向 Verifier 證明 ，而知識證明系統使得 Prover 可以向 Verifier 證明的不僅是 ，還可以證明 Prover “知道” ，也就是說，即使 ，如果 Prover 不知道對應的 ，也難以驗證通過，和上一節討論的零知識性類似，“知識性”也需要嚴格的定義，一個程式 P “知道”資料 ，到底該怎樣定義呢？想象一下把這個程式運行在一個虛擬機里，它的亂數是可以由我們隨意指定的。它的整個運行過程中，CPU 狀態的完整歷史記錄，以及所有的記憶體讀寫操作，都可以由虛擬機記錄下來。如果這個程式“知道” ，我們總該從這些記錄中提取出 的資訊吧。實際上，這就是提取器 (Extractor) 的一種直觀的理解方式。提取器就是一個演算法，它能夠和被提取的程式同時運行，并能夠訪問到被提取的程式的內部狀態，最后，它可以輸出提取的結果。上面描述的提取器是非黑盒提取器，因為它可以訪問被提取程式的內部狀態，非黑盒提取器的演算法必然要隨著被提取程式的不同而變化，所以，一個證明系統是一個知識證明，是這樣定義的：“對于任意 Prover ，存在一個提取器 ，它和 同時執行，并能夠訪問到 的內部狀態，如果 和 互動后 輸出 accept，那么 就會輸出滿足條件的 。”類似于零知識定義中的模擬器，提取器也可以用黑盒的方式定義，提取器無法訪問程式的內部狀態，但可以呼叫這個程式，控制這個程式的亂數，并讀取這個程式的輸出。我們引入這樣一個記號 ，表示提取器通過黑盒的方式訪問一對 Prover 和 Verifier 的互動過程，黑盒提取器對所有的 Prover 只需要有一個就夠了，所以知識性證明就可以如下定義：“存在一個提取器 ，對于任意 Prover ，如果 和 互動后 輸出 accept，那么 就會輸出滿足條件的 。”
簡潔性
用 表示一個 NP 語言的實體， 表示 存在語言中的證據，簡潔性 (Succinctness) 是指一個證明系統所需的通信量低于 的線性函式，換句話說，Prover 和 Verifier 執行這個證明系統，比 Prover 直接把 發送給 Verifier，還要節省通信帶寬，有時候，簡潔性還可能要求 Verifier 在證明系統中的計算量要低于驗證 。總之，簡潔性要求證明系統在效率方面有優勢，
我們可能會希望一個簡潔證明系統的通信量達到對數級別或更低，即 。然而這樣的簡潔性要求會帶來安全性的損失，因為如果通信量低達對數級別，那么 Prover 的訊息組合 所在的整個空間是可以在 時間內窮舉的，然而，系統的可靠性要求，對于錯誤的陳述 ， Prover 不能找到讓 Verifier 驗證通過的 。假如能夠驗證通過的 壓根不存在，這樣確實能夠保證可靠性，但這樣就可以通過窮舉 來判斷 的合法性，那么 就不是一個困難問題，這就排除了一般的 NP 語言。如果我們想要一般的 NP 語言的證明系統，我們必須允許即使對于錯誤的 ，也存在少量的能夠驗證通過的 ，這種情況下，我們只能額外引入一個安全引數 ，將通信量的大小放寬為 ，使得窮舉 的復雜度達到 ，這樣至少實現了計算意義下的可靠性，同時，通信量相對于 仍然是對數級別的，所以滿足了簡潔性。綜上，對于一般的 NP 語言，(對數級別的) 簡潔證明系統只能是論證系統，
非互動性
非互動性 (Non-Interactivity) 是指證明系統的全部互動只有 Prover 向 Verifier 發送的一條訊息，這個訊息叫做一個證明，記為 。非互動性可以帶來許多的便利，為證明系統帶來更多的應用場景。例如，在區塊鏈系統中，非互動性的零知識證明可以附在交易中，供任何人隨時查驗，而不需要交易的作者隨時在線與驗證者互動。
任何 NP 語言都天然具有一個非互動證明協議，也就是 Prover 直接將證據發送給 Verifier，而且這個證明是知識證明。所以，構造一個單純具有非互動性的證明系統意義不大，非互動性只有和前面討論的兩個性質，即零知識性或簡潔性組合起來才有意思。非互動性 + 零知識將零知識性和非互動性結合起來，就有了非互動零知識 (Non-Interactive Zero-Knowledge, NIZK)。我們之前在討論零知識性時講到，零知識性之所以和可靠性不矛盾，是因為呼叫模擬器采樣的 中的 大概率和與 Prover 互動的 Verifier 的亂數不同，但是，對于非互動零知識，我們要重新審視一下這個推理過程。在互動證明中，一個亂數為 的 Verifier 能夠驗證通過的 Prover 訊息 ，直接搬到亂數為 的 Verifier 那里就很可能驗證不通過了，所以，在互動式證明中， 的正確性不是全域的，而是依賴 的，而在非互動證明中，Prover 沒有收到 Verifier 的任何訊息，所以 Prover 的計算過程沒有用到 Verifier 的亂數 。所以，為了達到證明系統的完整性，誠實的 Prover 輸出的 ，對于大部分 Verifier 亂數 都是能驗證通過的。所以，非互動證明中的 的正確性是全域的，不依賴任何，零知識性要求，Verifier 的視野 和模擬器的輸出 不可區分，這意味著，如果單獨觀察這它們部分分量，它們也是不可區分的，即 和 中的 也是不可區分的，所以，一個惡意的 Prover 可以呼叫模擬器來輸出 ，這在互動式證明中不成問題，惡意的 Prover 僅僅是得到了關于某個 正確的 罷了，但在非互動證明中， 的正確性是不依賴 的，就會帶來安全問題，這時候，就要輪到 發揮作用了，雖然 的正確性不再依賴于 ，但還是依賴于 的，為了可靠性，我們希望，給定 和陳述 難以計算出能夠通過驗證的 ，雖然模擬器在給定 時可以同時輸出一對 ，但是難以先計算前者再計算后者，具體是怎樣做到這一點的，后續文章中介紹具體方案時會詳細講解，非互動性 + 簡潔性上文提到，簡潔性的證明系統必然是論證系統，結合非互動性，就有了簡潔非互動式論證 (Succinct Non-interactive ARGument, SNARG)。實際上，滿足 SNARG 定義的系統早在 2000 年就由 Micali 構造出來了，而這個名字是后來才出現的，如果一個 SNARG 同時是一個知識論證，它就被稱為簡潔非互動式知識性論證 (Succinct Non-interactive ARgument of Knowledge, SNARK)。SNARK 這個名稱由論文 BCCT12 首創，現在已經成為零知識證明領域最熱門的概念之一。其實 SNARK 只具有簡潔性和非互動性，并不一定具有零知識性，如果有零知識性，應該叫 zkSNARK。STARK 和 SNARK 辨析另一個經常和 SNARK 一起提到的概念是 STARK。它和 SNARK 只有一字之差，但有很多不同。下面我們比較一下這兩個概念，共同點：
- 都是知識論證 (ARK)，即只有計算意義下的可靠性，且證明是知識性的
區別：
- SNARK 的 “S” 是簡潔性 (Succintness)，而 STARK 的 “S” 是可擴展性 (Scalability)，它在簡潔性的基礎上還要求 Prover 復雜度至多是擬線性 (Quasi-linear) 的，即 ，而 Setup 的計算復雜度最多是對數的
- 透明性 (Transparent)：STARK 不需要可信第三方 Setup；而 SNARK 沒有這個限制
- 非互動性 (Non-Interactivity)：SNARK 一定是非互動的，而 STARK 沒有這個限制
可以看出，SNARK 比 STARK 唯一多出的限制就是非互動性，盡管如此，通過后續文章將要介紹的 Fiat-Shamir 變換，STARK 一般都可以轉化為非互動證明，轉化的結果必然是一個 SNARK。在這種意義上，可以把 STARK 看做 SNARK 的子集，上述 SNARK 和 STARK 的定義是這兩個名詞的廣義涵義，狹義上，它們分別指代兩個具體的構造方案，其中 SNARK 指的是以 Groth16 方案為代表的一系列基于 QAP 和雙線性對的 zkSNARK 構造方案，而 STARK 在狹義上就專門指代 Ben-Sasson 等人在 2018 年提出的基于 AIR 和 FRI 的那一個方案。
小結
本文介紹了證明系統的定義，并討論了證明系統的各類性質，重點討論了“零知識性”、“知識證明”、“簡潔性”和“非互動性”，解釋了如何用模擬器來定義零知識性，以及用提取器來定義知識性證明。最后，文章討論并比較了 SNARK 和 STARK。
參考資
- Goldreich. Foundations of Cryptography, Volume 1. Basic Tools. 2001.
- ZKProof Community. ZKProof Community Reference. 2019. https://docs.zkproof.org/reference.pdf
- Yehuda Lindell. How To Simulate It – A Tutorial on the Simulation Proof Technique. 2018.
- Eli Ben-Sasson. A Cambrian Explosion of Crypto Proofs. https://nakamoto.com/cambrian-explosion-of-crypto-proofs/
