一文了解ZCash背後的零知識證明

　　在複雜的密碼學領域，零知識證明為一項看似矛盾的任務提供了獨特的解決方案：在不透露資訊本身的情況下證明知道某一資訊。這種加密方法涉及兩方：證明者及驗證者。證明者的目的是證明他們擁有某一資訊（我們稱之為 x），而不透露任何關於 x 本身的資料。驗證者則從交流中了解到的只是證明者擁有這種知識的簡單事實。最重要的是，驗證者並沒有獲得關於 x 的額外資訊。

　　比如當小零與小十在玩密室逃脫，此時小零告訴小十他已經破解了某“寶箱”的密碼。但是小零不願意直接分享現成的“答案”，也不願當著小十的面將寶箱打開。那麼怎樣證明給小十，他真的破解了迷題並且知道寶箱密碼呢？

　　於是他讓小十在一張紙上寫一段只有自己知道的字串，同時簽上自己名字，將紙張從寶箱的縫隙中塞了進去。

　　隨後小零打開寶箱取出了小十放進去的紙張，並展示給了小十看，小十核對字串和簽名無誤。這證明了小零確實知道寶箱密碼，而且這張紙確實是寶箱裡拿出來的。

　　該解密過程既沒有被小十知曉，同時小零又證明了他已破解了寶箱密碼。

零知識證明

　　密碼學中，零知識證明（Zero Knowledge Proof，也稱 ZKP）或零知識協議是一種方法，該方法可令證明者在不透露資訊本身或其他任何資訊的情況下，讓驗證者相信或證明給驗證者某個陳述或論斷的真實性。

　　零知識證明最初是于由麻省理工教授 Shafi Goldwasser、Silvio Micali 以及密碼學大師 Charles Rockoff 三位作者在《The Knowledge Complexity of Interactive Proof Systems》論文中提出的。該一演算法概念為現代密碼學奠定了一定基礎。

　　零知識證明有兩個額外的屬性：簡明性和零知識。簡明性允許驗證者接受一個大型計算的正確性，而無需自己計算該語句或陳述。而零知識保證了沒有任何關於輸入的資料被洩露。

　　零知識證明對於確保許多加密協議的隱私和安全至關重要。它們是防止潛在資訊洩露的保障，是 Crypto 世界的隱形防彈衣。該知識的應用可延伸至不同領域，包括區塊鏈技術和安全認證系統，其中敏感性資料的保護是最重要的。

應用領域廣泛

　　區塊鏈及加密技術：像 Zcash 這樣的區塊鏈技術使用了零知識證明來保護交易隱私。一個人可以證明他們有足夠的 Cypto 貨幣來進行交易但又不透露其資金的確切數額。這保證了隱私的同時確保了交易的完整性。

　　身份驗證及認證：零知識證明還可以在不透露不必要的資訊同時，用於確認身份。例如，一個人可以在不提供確切的出生日期的情況下證明他們已經超過 18 歲，或者在不分享密碼等敏感性資料的情況下證明他們的身份。這最大限度地減少了盜取身份或未經授權訪問的風險。

　　安全多方計算（SMPC）：零知識證明可以促進多方之間的複雜互動，其中每一方都可以證明他們遵循商定的協議，而不透露其輸入的具體內容。這在如保護隱私的資料採擷、安全投票系統等諸多方面都十分有效。

　　網路安全：零知識證明可以提供改進的安全協定，如安全密碼政策。其可以驗證使用者提出的密碼是否符合某些安全標準，而不讓伺服器知曉或記錄實際密碼。因為密碼不會被儲存在任何地方，因此可以防止潛在的違規行為。

　　保護隱私的同時共用資料：零知識證明可以用來證明某些資料符合特定的要求，而不透露資料本身，這在醫療或金融等領域尤其重要。這些領域對資料隱私的規定很嚴格，但以安全、保護隱私的方式分享資訊或許會帶來巨大收益，比如促進醫療事業的發展等等。

　　零知識證明已經在區塊鏈中釋放了新的技術可能性。這可以從 ZKSync 和 Polygon 的 zkEVM 等各種 Layer 2 中看到。然而，這僅僅是零知識證明創建的區塊鏈的一個子集。

如何表示一個證明

　　在這一節以及文章的其餘部分，我們將重點討論為基於 PLONK 證明系統構建的證明。

　　PLONK是一種零知識證明系統，其全稱是

　　“Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge”，即“基於拉格朗日基數的全域非互動式知識證明排列”。

　　從本質上講，PLONK 是一個通用的、可更新的加密證明系統，這一創新允許在區塊鏈系統和其他分散式網路中進行有效的驗證和擴展。

　　PLONK 背後的想法是構建一個通用的且可更新的證明系統。在零知識證明系統的背景下，“通用”意味著它可以被用於任何類型的計算；“可更新”則意味著加密參考字串（用於生成和驗證證明的一段資料）可以隨著時間的推移安全地更新。

　　PLONK 因其高效和簡單性而引人注目，也因此成為了對安全、私密交易系統有需求的專案及公司的熱門選擇。與其他系統相比，它每個 gate（計算的基本單位，我們下文統稱“門”）使用的約束條件更少，這使得計算速度更快且可擴展性更高。

　　Vitalik Buterin 已經發表了關於 PLONK 的更全面的描述。【複製下連結至流覽器即可查看原文 https://vitalik.ca/general/2019/09/22/plonk.html】

證明

　　在證明某個陳述前，我們先將該陳述用電路表示。一個電路將計算中的值與另外兩種類型的資料一起編碼：

　　1. 操作：比如對輸入資料進行的乘法和加法計算

　　2. 操作執行的順序

　　為了編碼這些資料，PLONKish 電路會被表示為一組向量和約束條件。約束條件是向量中單元必須遵守的關係，其中約束類型有：門約束和複製約束，他們分別表示電路中的操作和操作的順序。

　　採用不同的門和電路架構，有多種方法來表達電路。

　　???? 將陳述表示為一個電路

　　假設我們有兩個門：一個乘法門和一個加法門。乘法門被表示為一個長度為 3 的向量|a|b|c|。

　　如果這個門被選中，那麼它將約束 c 等於 a*b。同樣，加法門表示為一個長度為 3 的向量，如果選擇加法門，則 c 等於 a+b。使用這些門，讓我們表示兩個向量（a, b）和（c, d）之間的點積。要做到這一點，我們需要完成以下計算：

　　1. 使用乘法門計算 a*b

　　2. 用乘法門計算 c*d

　　3. 用加法門計算 ab+cd

　　這可以用向量來表示。

　　注意，第一個和第二個乘法門的輸出是加法門的輸入值。這個資料在我們的電路中是和門的約束條件分開編碼的。這被稱為複製約束。

　　那麼，為什麼電路約束很重要呢？如果沒有約束，那麼惡意驗證者就可以在電路中輸入他們喜歡的任何數值。例如，驗證者可以用 aba*b 替換 ab+cd。與智慧合約類似，約束條件在使用前必須通過證明系統得到驗證。

　　???? 證明陳述

　　現在我們可以用電路來表示陳述，那麼證明者如何說服驗證者證明是有效的呢？對於 PLONK 系統來說，證明者必須讓驗證者相信門的約束和複製約束得到了實現。對於複製約束來說，這是通過進行排列組合檢查來實現的。

　　替換檢查是由 Bayer-Groth 首先提出的，然後由 Gabizon、Williamson 和 Ciobotaru 在 PLONK 論文中得到了進一步發展。為了證明門的約束，需要計算某個 quotient polynomial（商的多項式）。

　　直觀地說，置換檢查表明，如果複製約束的條目被置換，電路仍然是相同的。???? 置換檢查

　　如果對於 b 的所有第 i 個位置，存在與 a 相等的σ(i)位置，我們就說一個向量 a 與向量 b 之間是通過置換σ來關聯的。我們將其表示為σ(a)=b。給定兩個向量 a=(a, b,..., c), b=(a', b',..., c')$, 和置換σ，我們想確定σ(a)=b。這可以按以下方法進行：

　　將向量表示為 a'=((a, 1),(b, 2),...,(c, n))和 b'=((a',σ( 1),(b',σ( 2)),...,(c',σ(n)) )。這是對關於置換σ的向量進行編碼。

　　將向量重寫為多項式向量：a''=((a+ 1 X),(b+ 2 X),...,(c+nX))和 b''=((a'+σ( 1)X), (b'+σ( 2)X),..., (c'+σ(n)X))

　　檢查 a''和 b''作為多集是否等價，可以通過隨機選擇 gamma 來完成，從而顯示$(a+ 1 X+γ)(b+ 2 X+γ)....(c+nX+γ) = (a'+σ( 1)X)+γ)(b'+σ( 2)X+γ)....(c'+σ(n)X+γ)$ 。

　　通過隨機選擇一個β，我們可以通過 Schwartz-Zippel lemma 檢查這些多項式是否等價。如果它們作為多項式是等價的，那麼集合 a''和 b''作為多集則是等價的。如果它們不是等價多項式，那麼 a''和 b''就不是等價的多集。

最後

　　雖然零知識證明是一個複雜的主題，但其應用率卻在不斷攀升。本文我們已經對零知識證明的工作原理進行了直觀的解釋。日後，CertiK 團隊將與大家 j 一起深入探討零知識證明的應用以及團隊如何為新的用例優化其電路。