本文是零知識證明系列的第二篇，上一篇《零知識證明系列（0）：從數獨遊戲說起》透過數獨遊戲和三染色問題兩個簡單的例子引出了零知識證明的相關概念。本文主要介紹兩部分的內容：

簡單回顧前文中的例子，透過實際例子引出零知識證明技術方案具備的若干性質。

介紹互動式證明與非互動式證明的區別，以及互動式證明轉變到非互動式證明的前提假設和轉變方法。

前文中我們透過數獨遊戲和三染色問題介紹了零知識證明的核心過程，由證明者 P 向驗證者 V 證明“自己知道特定數獨遊戲的答案”或者“自己知道特定三染色問題的答案”的正確性，並且不洩漏除了正確性以外的任何資訊。

圖一 互動式零知識證明過程

如圖一所示，這一證明過程中，證明者 P 需要提前提供承諾等待驗證者 V發起挑戰，然後根據挑戰中的隨機值迴應挑戰。如果證明者 P 確實能證明命題的正確性，那麼他能順利透過每輪挑戰，否則只能以一定機率透過每輪挑戰。驗證者 V 透過進行多輪挑戰，直到認為證明者 P 證明正確的機率達到足夠大的時候認可該證明，但驗證者 V 無法透過承諾和每輪挑戰的迴應得到任何關於答案的資訊。

從上述過程我們可以看出，零知識證明技術滿足以下三個性質：

完備性（Completeness）：如果證明者 P 知道證據（Witness）能證明命題的正確性，則能以極大機率讓驗證者 V 信任。

正確性（Soundness）：一個惡意的證明者 P‘ 難以用一個錯誤的命題欺騙驗證者 V。這裡的正確性區分為計算正確性和完美正確性。滿足計算正確性的零知識證明方案能防止只能做多項式時間計算的惡意證明者（可以簡單理解為惡意證明者只有有限計算資源），這樣的方案也稱為“論據”（Arguments），之後將會介紹的zk-SNARK和zk-STARK方案都屬於 Arguments，而滿足完美正確性的方案可以防止擁有任意計算資源的惡意證明者。

零知識性（Zero-knowledge）：一個惡意的驗證者 V’ 不能獲取除了命題是否正確以外的資訊。同樣，我們區分計算零知識性和完美零知識性。

我們如何證明一個零知識證明方案具備這些性質呢？

對於完備性和正確性，我們在前文透過機率計算的方式進行了一定的證明，對於其他的方案也可以用同樣的計算結果得到證明。問題的難點在於，如何證明零知識性，也就是驗證者無法透過某些特殊的挑戰得到證明答案（數獨問題中的數字解和三染色問題中的染色方案）的任何資訊。

直接證明較為困難，這裡我們提出一個有趣的“時光機假設”來說明這一特性，假設三染色問題的證明者並不知道正確的染色方案，但他擁有一臺時光機，可以回到過去。那麼當驗證者提出挑戰（特定的兩個相鄰頂點）後，證明者透過時光機回到承諾階段修改承諾的地圖，使得這一挑戰能透過測試，這一切對於驗證者來說是不知情的，所有過程和正常的一樣。那麼當驗證完成時，由於證明者本身不知道正確的染色方案的任何資訊，而驗證者獲取的資訊不可能多於證明者擁有的資訊，所以可以推論出“驗證者獲取的資訊 <= 證明者擁有的資訊 = 零知識”。

當然，這一說明還存在兩個問題，一點在於時光機並不存在，也許造出時光機需要的資訊包含了染色方案的答案資訊，因此證明者擁有的資訊並不能說是零知識。另一點在於如果驗證者提出的挑戰與承諾息息相關，那麼證明者及時返回過去修改了承諾，驗證者也會相應地修改挑戰。對於這一點我們只能認為，證明者給出的承諾對於驗證者來說是近乎隨機的，因而驗證者無法從中獲取任何資訊。但請大家記住這一有趣的性質，後續介紹的非互動式零知識證明就會用到這一特性，使得即使擁有時光機的證明者，也無法偽造證明！

目前為止，我們介紹的例子包括數獨遊戲和三染色問題，都需要驗證者和證明者同時線上，並且透過若干輪驗證者的挑戰和證明者的迴應來完成證明。這樣一來零知識證明方案存在很多限制：首先參與方必須同時線上，並且只有驗證者才會相信證明的正確性，因為只有驗證者才知道提出的挑戰是隨機的，還是和證明者串通作弊的。

這一限制在傳統的中心化節點的架構中並不嚴重，我們可以相信中心化節點的驗證以及頒發的證書（比如在DNS，HTTPS等協議中）。但是在區塊鏈領域，使用者信奉著“Don‘t trust， verify it”（別相信，驗證它）的理念。所有參與的節點都需要獨立驗證區塊鏈上的資料是否正確，如果我們要求證明者時刻線上等待著所有參與節點發起的挑戰，那麼只有極少伺服器可以作為證明者參與這一過程，普通人將難以使用該系統。

因此，如果我們希望其他人也信任該證明的正確性，要麼其他人都信任該驗證者，要麼存在一個公開可信的隨機數列作為“驗證者”的身份發起挑戰。但這也存在一個問題，如果隨機數列是公開的，那麼證明者也可以訪問到，進而根據這一數列提前偽造承諾。如果大家對前文的時光機部分還有印象，那麼就知道我們需要的是與承諾資料相關的挑戰，這樣可以避免證明者事先偽造好承諾。換句話說，我們需要透過承諾計算得到公開可信的隨機數列。實際上，利用hash函式結果的隨機性，我們可以將承諾資料的hash計算結果作為隨機數列用於生成挑戰，這也就是 Fiat–Shamir 變換

［1］

，具體過程如圖二所示。

圖二 非互動式零知識證明過程

可以看到，圖二與圖一相比減少了重複的挑戰和迴應過程，證明者只需要傳送一次資料供驗證者驗證。對照這一過程，讓我們再來回顧剛才討論的幾個難題。

如何保證一次證明被多個驗證者驗證？

去掉互動過程，證明者直接公開驗證所需的資料。

所有驗證者如何相信挑戰包含隨機數的隨機性？

該隨機性由hash函式的隨機性保證。

證明者能否先知道挑戰再更改承諾？

計算上不可行，hash函式是單向的，也就是說使用者需要透過承諾計算挑戰，知道挑戰後更改承諾會導致hash結果改變，挑戰需要重新生成，足夠多次計算才能得到使用者希望的hash結果，這普遍認為是計算不可行的。

可以看到，這一方案解決了非互動式零知識證明面臨的困境，使得零知識證明在區塊鏈領域可以大展身手了。後續我們將看到非互動式零知識證明在區塊鏈領域的應用，使得使用者可以發起一筆交易，證明自己擁有足夠的餘額支付這筆交易，並且不洩漏和自己賬號、密碼以及餘額相關的任何資訊。重點會介紹兩個經典方案，zk-SNARK和zk-STARK。也許還有需要數學和密碼學的知識需要準備，但我們會在介紹的過程中，不斷進行補充。

參考

^

What is the Fiat-Shamir transform？ 這是Bristol大學密碼組的一篇部落格，這一系列列舉了密碼學博士需要知道的52個知識點

http：//bristolcrypto。blogspot。com/2015/08/52-things-number-47-what-is-fiat-shamir。html