VER:帶你一文了解零知識證明

原標題：干貨|零知識證明引論

作者：Cyte

繼上一次?Shor發出了對支付網絡中路由問題的全面研究之后，又有一位熱愛研究的Nervos小伙伴Cyte對零知識證明做了詳細的研究。

在這篇文章中，Cyte?會和大家介紹零知識證明(ZKP)?的定義，并將零知識證明與SNARK和STARK這兩個概念進行辨析。

ZKP、SNARK和STARK等這些密碼學概念隨著最近區塊鏈的興起變得熱?起來。但是，它們經常會被誤解和混用。其實，所有這些概念都屬于一個更廣義的范疇，叫做證明系統(ProofSystem)，或者叫做密碼學證明。零知識證明和SNARK、STARK之間都有交叉的部分，但并不相互包含。它們之間的關系可以用一張圖來表示。

本文將首先介紹證明系統的定義，并討論證明系統的各類性質，重點討論「零知識性」、「知識證明」、「簡潔性」和「非交互性」。特別的，如果一個證明系統具有「零知識性」，那么它就被稱為一個「零知識證明」。最后，文章會討論?SNARK?和?STARK的定義并將其進行比較。

證明系統

一個證明系統(ProofSystem)?是一個交互式協議，包含兩個參與方Prover和Verifier，以及一個算法Setup。證明系統的作用是讓Prover說服Verifier相信一件事，我們把這件事叫做一個陳述(Statement)。

協議開始前，需要由某人調用Setup算法。Setup算法接受一些公共參數作為輸入，并輸出Prover和Verifier所需的Setup信息，其中Verifier獲知的信息記為?，Prover獲知的信息記為?。?和??的公共部分稱為公共參考字符串(CommonReferenceString,CRS)。具體由誰、在什么時候調用Setup算法，取決于證明系統的設計。協議一開始，Prover和Verifier同時得到輸入陳述?。Prover相對于Verifier必然要有一些額外的優勢，例如更強大的計算能力，或者得到了一些額外的輸入?。除此之外，Prover和Verifier還分別獲知了??和?。Setup信息獲取的時間取決于證明系統的設計。例如，有可能是Prover和Verifier早就下載好存在各自硬盤里可以反復使用的，也可能是協議開始前當場輸入的。然后Prover和Verifier開始執行證明系統規定的協議。如果Prover和Verifier都是誠實的，那么它們都嚴格遵守協議執行。不過，也有可能某一方是惡意的，沒有按照協議規定來執行，此時會發生什么事情，取決于證明系統的安全性。如果兩方都是惡意的，它們都不遵守協議，那就和這個證明系統沒關系了。最后，Verifier輸出accept或reject，表示是否相信陳述?。一個證明系統需要滿足兩個性質：

David Di Franco項目Discord服務器和推特賬戶遭到攻擊:金色財經報道，據CertiK監測，David Di Franco項目Discord服務器和推特賬戶遭到攻擊。請社區用戶警惕釣魚陷阱，在服務器和賬號修復之前不要點擊任何鏈接。[2022/12/21 21:57:46]

完整性(Completeness)：如果陳述??是正確的，而Prover和Verifier都遵守這個協議，那么Verifier以至少??的概率輸出accept，這里??被稱為證明系統的完整性誤差(Completenesserror)可靠性(Soundness)：如果陳述??是不正確的，此時Prover必然是不誠實的，而Verifier遵守協議，那么任何Prover都不能讓Verifier輸出accept的概率超過?，這個??被稱為證明系統的可靠性誤差(Soundnesserror)這兩個要求是使得一個證明系統成立的最基本的要求。少了哪個要求，我們都可以得到符合條件但完全沒用的證明系統。例如，如果我們只要求完整性，那就無論Prover做什么，Verifier永遠只輸出accept就好了；如果只要求可靠性，那就讓Verifier永遠只輸出reject。此外，一般希望??和??都不超過?，并且加起來小于?，否則這個證明系統誤差太大，也近乎無用。如果將一個證明系統的可靠性只對任何計算能力受限的?Prover成立，也就是說，計算能力無限的敵手是有可能欺騙Verifier的，此時這個證明系統只有計算可靠性(ComputationalSoundness)，這樣的系統又稱為?論證系統(ArgumentSystem)。相比之下，對任何Prover都安全的可靠性被稱為統計可靠性(StatisticalSoundness)。

證明系統的其他性質

一個證明系統還可以滿足一些其他(并非必需的)性質

CRS模型(CRSmodel)：如果Setup信息是對所有人公開可見的，即Setup=Setup=Setup，稱這個證明系統是在CRS模型下的交互(Interactive)/非交互(Non-interactive)：如果整個交互過程只有Prover向Verifier發送一條信息，就稱這個系統是非交互證明系統；否則這個系統就是交互式證明系統可遷移(Transferable)/可抵賴(Deniable)：如果陳述??是正確的，并且把交互過程發送給其他Verifier，也能夠讓其他Verifier相信陳述??的正確性，這個證明系統就是可遷移的；否則這個證明系統就是可抵賴的公開可驗證(PublicVerifiable)/特定驗證者(DesignatedVerifier)：如果Setup?是對所有人公開可見的，即任何人都可以成為Verifier，這個零知識證明系統就是公開可驗證的。否則這個系統就是針對特定驗證者的公開隨機(Publiccoin)：如果Verifier的所有消息的選取都均勻隨機且獨立于Prover的消息，就稱這個系統是公開隨機的零知識(Zero-Knowledge)：在陳述??是正確的情況下，如果除了??的正確性，Verifier無法從交互中獲取任何其他“知識”，就稱這個系統是零知識的簡潔性(Succinctness)：如果這個證明系統是用來證明NP語言的，并且證明系統的通信量比證據??還要小，那么這個證明系統就具有簡潔性

灰度：SEC在其比特幣期貨ETF訴訟中提交法律摘要:金色財經報道，Grayscale Investments表示，美國證券交易委員會已經在該加密貨幣資產管理公司因其現貨比特幣交易所交易基金的申請被拒絕而提起的訴訟中提交了其第一份法律簡報。

在73頁的回應簡報中，美國證券交易委員會認為其拒絕是 \"合理的。期貨和現貨的比特幣基金是 \"根本不同的產品。[2022/12/11 21:37:08]

例：證明兩個球的顏色不同

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)。根據模擬器工作方式的不同，有如下不同的定義方式：

加密貨幣錢包應用Ledger Live已支持Acala生態資產:10月31日消息，加密貨幣錢包應用Ledger Live已支持Acala生態資產，包括aUSD、LDOT和tDOT以及Acala的Kusama平行鏈Karura上資產，用戶還可以使用Ledger Live與Acala生態應用進行交互。[2022/10/31 12:01:42]

非黑盒模擬器，相對應的零知識性叫做非黑盒零知識。這個零知識的定義允許每個Verifier都存在一個“獨家定制”的模擬器，這種定義允許模擬器針對不同的Verifier的實現細節來定制不同的采樣過程。黑盒模擬器，對應的就是黑盒零知識。這個零知識的定義要求存在唯一的模擬器，使得對所有的Verifier，它都能夠采樣出?。這個唯一的模擬器不可能知道所有Verifier的具體實現細節，所以它只能通過黑盒調用的方式來訪問Verifier。不過，模擬器對Verifier具有完全的控制權。模擬器可以決定Verifier的隨機數?，并給Verifier輸入任何的Prover消息或?。所以，在模擬器的眼里，Verifier是一個黑盒的確定性算法。如果模擬器只針對誠實Verifier，對應的是誠實Verifier零知識(HonestVerifierZK)。因為誠實Verifier的行為是完全在預期中的，模擬器自然可以利用這些信息，因此這個模擬器對Verifier的訪問是非黑盒的。非黑盒模擬器訪問到的信息更多，所以非黑盒零知識性比黑盒零知識性更容易成立。而誠實Verifier零知識是最容易實現的。關于誠實Verifier零知識，這里的誠實Verifier更準確地說是半誠實(Semi-Honest)的，或者說“誠實但好奇的”。這樣的Verifier表面上會遵守協議，但有可能私下里試圖從消息中提取知識。相比之下，惡意Verifier的行為是完全不受限制的。Verifier可能宕機、發送不符合格式的消息、不按協議規定的分布采樣，等等。要證明一個系統對惡意的Verifier滿足零知識性，就要把所有這些情況都覆蓋到。模擬器是一個隨機算法，它的輸出值也是一個隨機變量，記為?。零知識性要求??和??這兩個隨機變量難以區分。不過，“難以區分”這個詞也有很多種版本，由此可以推出零知識證明的多種定義：

如果兩個隨機變量的分布是統計不可區分的，也就是它們的統計距離(StatisticalDistance)可忽略，就稱這個證明系統是統計零知識(StatisticallyZero-Knowledge)?的；如果統計距離就是0，又叫做完美零知識(PerfectZero-Knowledge)?的；如果兩個隨機變量的分布是計算不可區分的，也就是任何多項式時間的隨機敵手都無法區分這兩個分布，就稱這個證明系統是計算零知識(ComputationallyZero-Knowledge)的。注意到，零知識的定義中，只要求對于正確的陳述?，?和??的分布難以區分。對于錯誤的陳述，我們并不關心Verifier能夠獲取什么知識，因為這種情況下Prover本身就是不誠實的，沒有必要去保護它，或者說，Prover既然不遵守協議，那我們的協議設計得再好也保護不到它。不過，雖然??是錯誤的情況下，零知識性對??的分布不做任何假定，但如果輸入錯誤的?采樣得到的??被Verifier驗證通過的概率和??正確的情況下有顯著差別的話，我們就可以借此判斷??的正確性。這就意味著??只能來自一個平凡的NP語言。所以，對于困難的NP問題，把錯誤的??輸入給模擬器，得到的??也能夠以一樣的概率被驗證通過。這么一來，零知識性和可靠性豈不是矛盾的？換句話說，對于錯誤的?，Prover為什么不能調用模擬器來欺騙Verifier？實際上，Prover不能控制Verifier，它也就不能為模擬器提供采樣??所需要的資源。的確，一個惡意的Prover可以去調用模擬器，但是這對它來說沒用，因為模擬器輸出的??中的??并不是正在與Prover交互的Verifier的隨機數。此外，模擬器輸出的??也可能和Verifier收到的??不同而導致驗證不通過。不過，Prover調起的模擬器無法獲取Verifier的隨機數，這已經足夠保證安全性了，所以交互式證明中??即使是固定常量也沒問題。

Umami將USDC Vault存款上限提升至350萬美元:8月4日消息，Arbitrum上風險對沖收益協議Umami將Vault存款上限提升至350萬美元。Umami USDC Vault通過將用戶存入的USDC用來為GMX提供流動性來獲取收益，并使用Tracer的無清算對沖衍生品3S-BTC/USD+USDC和3S-ETH/USD+USDC來防止市場波動。該Vault將資產分配為50%的穩定幣、30%的以太坊、20%的比特幣以及1-2%的LINK和UNI，用戶收益來源于交易費用、清算費用以及GMX獎勵等。[2022/8/4 12:01:25]

知識證明

如果要求Prover必須“知道”一些信息才能讓Verifier驗證通過，這個系統就被稱為知識證明(ProofofKnowledge)。知識證明可以看做可靠性的加強版。知識證明也有計算意義下的版本，叫做知識論證(ArgumentofKnowledge)。

知識證明系統通常是用來證明NP語言的。一個NP語言是指一個集合?，使得元素??屬于?可以由一個證據??來證明，即存在一個多項式時間的算法能夠判定??是否是??屬于??的合法證據。普通的證明系統使得Prover可以向Verifier證明?。而知識證明系統使得Prover可以向Verifier證明的不僅是?，還可以證明Prover“知道”?。也就是說，即使?，如果Prover不知道對應的?，也難以驗證通過。和上一節討論的零知識性類似，“知識性”也需要嚴格的定義。一個程序P“知道”數據?，到底該怎樣定義呢？想象一下把這個程序運行在一個虛擬機里，它的隨機數是可以由我們隨意指定的。它的整個運行過程中，CPU狀態的完整歷史記錄，以及所有的內存讀寫操作，都可以由虛擬機記錄下來。如果這個程序“知道”?，我們總該從這些記錄中提取出??的信息吧。實際上，這就是提取器(Extractor)?的一種直觀的理解方式。提取器就是一個算法，它能夠和被提取的程序同時運行，并能夠訪問到被提取的程序的內部狀態。最后，它可以輸出提取的結果。上面描述的提取器是非黑盒提取器，因為它可以訪問被提取程序的內部狀態。非黑盒提取器的算法必然要隨著被提取程序的不同而變化。所以，一個證明系統是一個知識證明，是這樣定義的：“對于任意Prover?，存在一個提取器?，它和??同時執行，并能夠訪問到??的內部狀態。如果??和??交互后??輸出accept，那么??就會輸出滿足條件的?。”類似于零知識定義中的模擬器，提取器也可以用黑盒的方式定義。提取器無法訪問程序的內部狀態，但可以調用這個程序，控制這個程序的隨機數，并讀取這個程序的輸出。我們引入這樣一個記號?，表示提取器通過黑盒的方式訪問一對Prover和Verifier的交互過程。黑盒提取器對所有的Prover只需要有一個就夠了，所以知識性證明就可以如下定義：“存在一個提取器?，對于任意Prover?，如果??和??交互后??輸出accept，那么??就會輸出滿足條件的?。”

Bored Ape Yacht Club地板價升至94.69 ETH:金色財經報道，據NFTGo.io數據顯示， Bored Ape Yacht Club總市值為21.5億美元，過去24小時交易額73.8萬美元。當前地板價為94.69 ETH，24小時漲幅1.07%。持有者人數6,285。[2022/6/6 4:04:12]

簡潔性

用??表示一個NP語言的實例，?表示??存在語言中的證據。簡潔性(Succinctness)?是指一個證明系統所需的通信量低于??的線性函數。換句話說，Prover和Verifier執行這個證明系統，比Prover直接把??發送給Verifier，還要節省通信帶寬。有時候，簡潔性還可能要求Verifier在證明系統中的計算量要低于驗證?。總之，簡潔性要求證明系統在效率方面有優勢。

我們可能會希望一個簡潔證明系統的通信量達到對數級別或更低，即?。然而這樣的簡潔性要求會帶來安全性的損失。因為如果通信量低達對數級別，那么Prover的消息組合??所在的整個空間是可以在??時間內窮舉的。然而，系統的可靠性要求，對于錯誤的陳述?，Prover不能找到讓Verifier驗證通過的?。假如能夠驗證通過的??壓根不存在，這樣確實能夠保證可靠性。但這樣就可以通過窮舉??來判斷?的合法性，那么??就不是一個困難問題，這就排除了一般的NP語言。如果我們想要一般的NP語言的證明系統，我們必須允許即使對于錯誤的?，也存在少量的能夠驗證通過的?。這種情況下，我們只能額外引入一個安全參數?，將通信量的大小放寬為?，使得窮舉??的復雜度達到?，這樣至少實現了計算意義下的可靠性。同時，通信量相對于??仍然是對數級別的，所以滿足了簡潔性。綜上，對于一般的NP語言，(對數級別的)簡潔證明系統只能是論證系統。

非交互性

非交互性(Non-Interactivity)?是指證明系統的全部交互只有Prover向Verifier發送的一條消息，這個消息叫做一個證明，記為?。非交互性可以帶來許多的便利，為證明系統帶來更多的應用場景。例如，在區塊鏈系統中，非交互性的零知識證明可以附在交易中，供任何人隨時查驗，而不需要交易的作者隨時在線與驗證者交互。

任何NP語言都天然具有一個非交互證明協議，也就是Prover直接將證據發送給Verifier，而且這個證明是知識證明。所以，構造一個單純具有非交互性的證明系統意義不大。非交互性只有和前面討論的兩個性質，即零知識性或簡潔性組合起來才有意思。非交互性+零知識將零知識性和非交互性結合起來，就有了非交互零知識(Non-InteractiveZero-Knowledge,NIZK)。我們之前在討論零知識性時講到，零知識性之所以和可靠性不矛盾，是因為調用模擬器采樣的??中的??大概率和與Prover交互的Verifier的隨機數不同。但是，對于非交互零知識，我們要重新審視一下這個推理過程。在交互證明中，一個隨機數為??的Verifier能夠驗證通過的Prover消息?，直接搬到隨機數為??的Verifier那里就很可能驗證不通過了。所以，在交互式證明中，?的正確性不是全局的，而是依賴??的。而在非交互證明中，Prover沒有收到Verifier的任何消息，所以Prover的計算過程沒有用到Verifier的隨機數?。所以，為了達到證明系統的完整性，誠實的Prover輸出的?，對于大部分Verifier隨機數??都是能驗證通過的。所以，非交互證明中的??的正確性是全局的，不依賴任何。零知識性要求，Verifier的視野??和模擬器的輸出??不可區分。這意味著，如果單獨觀察這它們部分分量，它們也是不可區分的。即??和??中的??也是不可區分的。所以，一個惡意的Prover可以調用模擬器來輸出?。這在交互式證明中不成問題，惡意的Prover僅僅是得到了關于某個??正確的??罷了。但在非交互證明中，?的正確性是不依賴??的，就會帶來安全問題。這時候，就要輪到??發揮作用了。雖然??的正確性不再依賴于?，但還是依賴于?的。為了可靠性，我們希望，給定??和陳述??難以計算出能夠通過驗證的?。雖然模擬器在給定??時可以同時輸出一對?，但是難以先計算前者再計算后者。具體是怎樣做到這一點的，后續文章中介紹具體方案時會詳細講解。非交互性+簡潔性上文提到，簡潔性的證明系統必然是論證系統。結合非交互性，就有了簡潔非交互式論證(SuccinctNon-interactiveARGument,SNARG)。實際上，滿足SNARG定義的系統早在2000年就由Micali構造出來了，而這個名字是后來才出現的。如果一個SNARG同時是一個知識論證，它就被稱為簡潔非交互式知識性論證(SuccinctNon-interactiveARgumentofKnowledge,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.?FoundationsofCryptography,Volume1.BasicTools.2001.ZKProofCommunity.?ZKProofCommunityReference.2019.https://docs.zkproof.org/reference.pdfYehudaLindell.?HowToSimulateIt–ATutorialontheSimulationProofTechnique.2018.EliBen-Sasson.?ACambrianExplosionofCryptoProofs.https://nakamoto.com/cambrian-explosion-of-crypto-proofs/

Tags：VERRIFVERIRIFIBovineVerse GameDRIFT幣Maverick ProtocolCryptoVerificationCoin

TUSD