交互式零知識證明簡介

前言

零知識證明（“ZKP”）在區塊鏈領域備受關注。主要重點是使交易能夠以簡潔和/或隱私的方式在鏈上公開提交。通常，這種用例需要任何人在任何時間進行驗證，因此，這種情況下的ZKP 必須是 非互動。

還有另一種類型的零知識證明， 互動證明 (“IR-ZKP”), 它們特別適用於oracle 技術領域。簡而言之，預言機形成了一個去中心化的鏈下網絡，通過共識來協調任務。預言機可以幫助以最小的信任去中心化鏈下證明系統。也就是說，它們可以在沒有單點集中或信任的情況下幫助執行證明任務，將輸出協調為一個組。特別是，預言機可以參與與證明者的交互式ZK 對話，共同證明驗證結論。該博客將發布一系列文章，解釋最先進的IR-ZKP 協議和特定用例。

零知識證明

給定一些公共功能 F 和值y，零知識證明(ZKP) 協議允許一方（又名證明者）向驗證者表明它知道一些x，這樣 F(x; y)=1，不透露x 的值。例如，以下可口可樂或百事可樂ZKP 協議允許證明者證明它知道如何區分可口可樂和百事可樂而無需透露如何區分：

1. 驗證者準備一杯可口可樂和百事可樂並隨機洗牌。
2. 在驗證者移開視線的情況下，證明者觀察/品嚐兩個杯子並決定哪一個是可口可樂。
3. 重複上述過程40 次，驗證者接受證明者確實知道如何區分可口可樂和百事可樂，如果證明者每次都正確的話。

上面的ZKP協議不一定有用，其實任何功能 F 使用多項式空間運行可以在零知識中得到證明。

非交互式與交互式ZK

傳統上，許多ZKP 協議可以成為非交互式的，也就是非交互式零知識(NIZK) 證明。這意味著證明者只需要運行一個程序（F, x, y) 作為輸入並輸出證明pi。任何帶有 (F, y, pi) 可以驗證它並確信證明者確實知道x 而無需看到它。 NIZK 的工作流程類似於數字簽名：簽名者使用其私有簽名密鑰簽署公共文檔並生成簽名； 任何擁有文檔、簽名和驗證密鑰的驗證者都可以檢查簽名的有效性。

NIZKs 由於其可轉移性的吸引人的特點，在區塊鏈領域找到了許多應用：證明者，在不知道驗證者身份的情況下，可以生成一個證明，可以用來說服任何接收它的人。具有非常小證明的NIZK 通常被歸類為zk-SNARK。^1個 它們特別適用於可能有許多驗證者有興趣檢查證明的開放系統。在這種情況下，證明只需要計算一次並由許多驗證者廉價地驗證。然而，簡潔ZK 的這些優點也帶來了一些缺點：簡潔NIZK 在證明方的計算和內存方面通常有很高的開銷。證明一個函數所需的資源比以明文方式評估該函數所需的資源高幾個數量級。

另一種類型的ZKP 協議是交互式ZKP。上面的可口可樂或百事可樂示例是證明者和驗證者之間的交互式ZKP：雙方需要輪流通信，信息在整個協議中雙向流動。在ZK 域之外，交互式協議在實踐中很常用。例如，對於通過密碼進行身份驗證的用戶，他們可以運行交互協議：

1. 服務器向客戶端發送隨機數y
2. 客戶端用H(username || password || nonce) 向服務器回復一些加密哈希函數H。
3. 服務器通過在本地重新計算相同的值來檢查該值是否有效。

交互式協議允許服務器生成隨機數，從而防止重放攻擊（攻擊者捕獲消息並稍後將其重新發送到服務器以進行身份​​驗證）。允許一輪交互是至關重要的，因為如果密碼身份驗證僅包含從客戶端到服務器的一條消息，則防止重放攻擊會困難得多。

^1個_{許多NIZK 有一個固定大小的證明； 而其他人則具有多對數證明大小。我們將它們都視為zk-SNARK。}

即將發布的帖子

交互式ZKP 通常是一組更廣泛的協議，其中包含NIZK 協議（特別是，總是可以向NIZK 添加交互以將其變成交互式ZKP）。然而，交互可以帶來簡潔的NIZK 所不具備的特性，例如，對非常大的語句的高可擴展性、廉價的計算、避免可信設置以及最小的內存使用。當聲明只需要向一小部分已知的各方證明時，這很有用。本博客系列將介紹當前最先進的交互式ZK 協議的基礎。在接下來的帖子中，我們將介紹以下內容：

• 評估電路時的內存複雜性。 在這裡，我們將深入研究電路評估的細節，以了解為什麼許多ZK 協議需要使用大量內存以及如何克服這個問題。
• 內存小的ZK 證明：複雜性和權衡。 作為減少內存消耗的第一步，我們將介紹一些內存複雜度較低的NIZK 協議。儘管內存使用量很小，但這些協議在其他指標上表現不佳。
• 基於交互式承諾的可擴展且負擔得起的交互式ZK。 我們講的是交互式ZK，可以認為是上述協議的交互式變體。這些協議依賴於一種特殊類型的承諾，儘管它們需要線性通信，但具有超級廉價的“計算”功能。
• 互動承諾的最新進展。 我們討論瞭如何根據最近關於函數秘密共享和偽隨機相關生成器的工作來實例化交互式ZK 協議中所需的承諾。這需要一個稱為量子安全的假設 學習與噪音的平等.
• 工程困難和未來發展的概述。 最後，我們將談談讓這些交互式ZK 協議變得高效和前沿的研究方向的難點。