構建通用零知識證明之旅。
1. 隱藏秘密：單向功能
在《星際迷航》的宇宙中，P = NP，這對於計算界也許是件好事，它意味著所有可以在多項式時間內驗證的問題，也可以在多項式時間內求解。但對於密碼學界而言，這可能是一場災難。
密碼學需要存在一種「單向功能」，也就是說能夠從 A 計算出 B，但從 B 計算出 A 存在著計算上的不可行性——計算從 A 到 B 是單向的，我們才有可能把 A 藏起來。而如果 P = NP，在多項式時間內可驗證的問題同時也是可求解的，那麼透過 B 就能計算出 A，秘密也就無法隱藏。
這就是密碼學背後的簡單邏輯：單向功能。而單向功能背後的支撐是 P! = NP。
這與零知識證明的關係是什麼呢？我們可以把零知識證明分解為兩個功能，第一個功能是隱藏秘密，第二個功能是證明自己有秘密。而隱藏秘密，如上文所述，就是找到一個具有單向功能的計算式。
零知識證明：
零知識證明是指讓驗證者相信某個斷言為真，且整個過程不洩露「斷言為真」之外的任何知識。為了更容易理解，本文把它簡化為隱藏秘密和證明擁有秘密。
橢圓曲線演算法（ECC）是密碼學中被普遍應用的一個具有單向功能的函式，它看起來是這樣的：k × P = Q，在已知 P 的情況下，我們可以透過 k 計算出 Q，但難以透過 Q 反向計算出 k。需要注意的是，密碼學中加法或乘法運算的含義不侷限於我們熟悉的實數域上加法或乘法運算的含義。
讓我們看看它是如何做到單向性的。在該函式中，P 是橢圓曲線上的一個點，我們把一個小球放在該點並沿切線方向擊打出去，小球在橢圓曲線中撞來撞去撞了 k 次（大致可以這麼理解），最後會落在一個點 Q 上。如果我們知道初始位置 P 和撞擊次數 k，是能算出小球的落點 Q 的；但如果我們只看見小球落在 Q 上，是無法算出從 P 點到 Q 點撞了多少次，也就是 k 的。
下圖是 k = 2 的一個示例，小球從 P 點出發，撞擊了兩次落在 Q 點上，因此 Q 等於2 × P。橢圓曲線演算法常被用於生成公鑰和私鑰，公鑰就是小球最後的落點 Q，私鑰就是撞擊次數 k。k × P = Q 的單向功能使得它可以隱藏私鑰這個秘密。
2. 證明秘密：同態
對於零知識證明來說，隱藏秘密只是第一步，我們還需要證明自己確實掌握了秘密。就像在第一段旅程中只需要理解單向功能，在這第二段旅程中，我們只需要理解「同態」，有了同態我們就有了證明秘密的能力。那麼什麼是同態？
我們可以把單向功能看成一種對映關係，比如 k × P = Q 就是 k 到 Q 的對映：在一個空間中，我們有無數個 k 點，它們被對映到另一個空間，變成無數個 Q 點。這就像現實世界和影子世界，透過光線的對映，現實空間的物體變成了影子空間的影子。
這時候假設有一塊機械手錶，機芯就是那個隱藏起來的秘密。我們把含機芯的手錶拆成 8 個零部件並對映到影子空間中，這時影子空間就會有 8 個影子；但注意在現實空間我們展示給大家看的是一塊完整的手錶，機芯是未暴露的，這塊手錶在影子空間也會有個影子，我們叫它第 9 號影子。
現在我們把 8 個零部件的影子組合起來，如果它們能夠組成一塊完整的手錶影子，就可以用該影子與第 9 號影子做對比，如果兩者是相同的，就能證明現實空間的這塊手錶中是有機芯的，因為它的影子與含機芯的零部件組成的影子相同。這其實就完成了一個簡單的零知識證明過程。
完整零部件的影子組合成的手錶影子與完整手錶的影子相同，我們稱這種對映為同態。用數學公式來表達就是 f(手錶) = f(零件1 + …… + 零件8) = f(零件1) + …… + f(零件8)。其中，f(手錶)是手錶的影子，f(零件1) + …… + f(零件8) 是零部件的影子組合成的手錶影子。
簡化一下這種關係就是：f(a+b) = f(a) + f(b)，即「先計算後加密的結果」f(a+b) 與「先加密後計算的結果」f(a) + f(b) 是相同的。同態使得我們可以直接對密文進行計算，然後對隱藏了秘密的明文先計算後加密，再透過比較兩者是否相同驗證明文中是否真的藏有秘密。
同態定義：
抽象代數中，同態是兩個代數結構（例如群、環、或者向量空間）之間的保持結構不變的對映。
如果你只想瞭解零知識證明的基本邏輯，旅程到這裡就可以結束了，知識點只有兩個：1. 用單向功能隱藏秘密；2. 用同態對映證明秘密。是不是還算輕鬆？
接下來讓我們看看這個過程在真實的密碼學中是怎樣的，以橢圓曲線數字簽名演算法（ECDSA）為例，它是一個具有「零知屬性」的演算法。你可以選擇不看，它不會影響你對同態的理解。
橢圓曲線數字簽名演算法對簽名的驗證：
在該演算法中，關鍵的過程是驗證 f(Z + dA × R) = f(Z) + f(dA × R) = f(Z) + Qa × R，其中，Z 是需要用私鑰簽名的訊息，dA 是私鑰，R 與隨機數相關，Qa 是公鑰。因為同態屬性，這個等式是成立的，我們就可以用等式右邊的 Qa(公鑰)來驗證 Z 是否是用等式左邊的 dA(私鑰) 簽名的。
在這裡，dA 是機芯，Z+dA×R 是藏有機芯的手錶，f(Z + dA × R) 是這塊手錶的影子，而 f(Z) + f(dA × R) 是手錶零部件的影子組合成的手錶影子。
橢圓曲線演算法的同態屬性使得其他演算法，比如橢圓曲線數字簽名演算法，可以利用它來隱藏並證明秘密，但該演算法的能力有限，因為它只具備加法同態，也就是 f(a+b) = f(a) + f(b)，但不具備乘法同態，即 f(a×b) = f(a) × f(b)。
這相當於把現實空間的物體投射到影子空間後，影子空間可以用加法來組合影子，但對於一些需要用乘法才能組合的影子，它就無能為力了。
怎麼辦？可以引入「配對函式」。比如橢圓曲線配對函式就是對橢圓曲線演算法做一系列的調整，生成一個新的對映空間，這個新空間既滿足加法同態，也滿足類乘法同態（注意，只是類乘法同態），這樣一來，除了用加法，我們還可以用類乘法去證明秘密。
現在，第二段旅程抵達了終點。我們需要了解的是，同態是證明秘密的關鍵所在，但並不是所有的對映關係都有「良好」的同態，而不同的應用場景對同態的要求也不一樣，在實際的設計中，需要根據具體需求實現不同的同態。
如果原空間與對映空間既滿足加法同態，也滿足乘法同態，我們稱其為全同態。全同態意味著可以對密文進行任意的運算（可以對影子進行任意方式的組合），這對實現資料隱私有著重要的意義，但實現全同態是一件非常困難的事情。
3. 通用零知識證明：NPC 問題
你一定注意到了，我們說橢圓曲線數字簽名演算法具有「零知屬性」，卻並沒有說它是零知識證明協議，因為它的主業是做數字簽名，隱藏私鑰只不過是它必須要實現的一個功能。而且它也只能隱藏私鑰，如果想讓它幫你隱藏一個你自己的秘密，它是做不到的。
而零知識證明協議，比如我們熟悉的 zk-SNARKs，它的主業就是隱藏並能證明需要它隱藏的各類秘密。這是如何做到的？
讓我們回到本文最開始的那個單向函式 k × P = Q，它能隱藏一個秘密 k，如果我們把它變複雜一些，比如變成 t × h = (v0 + a1 × v1 + …… + am × vm)(w0 + b1 × w1 + …… + bm × wm)這樣一個多項式，是不是就有了很多可以隱藏秘密的「空間」，比如把秘密放在 a1，a2，……，am 中。
事實上，上文中這個複雜的多項式就是 zk-SNARKs 中用於實現零知識證明的多項式，該多項式能夠證明各類秘密，因為它能證明布林電路。
為什麼能證明布林電路，就能證明各類秘密？因為布林電路可滿足性是一個 NPC（NP-Complete）問題，而 NPC 問題有一個「特性」，即所有的 NP 問題（包含NPC）都可以在多項式時間內歸約（轉換）成某一個具體的 NPC 問題。
比如布林電路、圖論三染色、甚至我們熟悉的掃雷遊戲，都是 NPC 問題。我們可以把掃雷遊戲規約成布林電路的可滿足性，也就是能夠用證明布林電路的多項式實現對掃雷遊戲的零知識證明；可以把圖論三染色規約成布林電路的可滿足性，也就是能夠用證明布林電路的多項式實現對三染色的零知識證明……
因此理論上，我們能夠以任何一個 NPC 問題為基礎構建一個通用的零知識證明協議。但這僅僅是理論上的，因為使用它們做證明的難易度是截然不同的。目前主流的方法是選擇布林電路或算術電路，因為它們實現起來相對容易、電路規模小，zk-SNARKs 和 Bulletproofs 都是選擇的這種方法。
4. 零知識證明協議
在三段旅程之後，零知識證明對我們而言也許不再是神秘莫測的事物，它背後有著簡單邏輯：1. 單向功能是隱藏秘密的方法；2. 同態對映是證明秘密的基礎；3. 證明 NPC 問題的多項式（但這並非唯一的方法）可以實現通用零知識證明。
不同的零知識證明協議在這三點上的具體實現是不一樣的，最主要的不同可能體現在第 3 點中，哪怕證明的是同一個 NPC 問題，也可以有截然不同的方法。因為不同的設計，零知識證明協議最常被提及的差異主要包括：
1. 不同的計算空間和計算時間。更小的空間和更短的時間是我們不斷改進零知識證明協議的主要動力，也是比較不同零知識證明協議的主要指標。
比如下圖是 ZCash 執行長 Zooko Wilcox 在談到零知識證明協議時用到的表格，主要比較的就是不同協議的證明時間、驗證時間和證明大小。
2. 是否需要初始化可信設定。不需要可信設定當然更好，會減少信任問題和安全問題，不過新的證明方法就可能帶來新的計算問題，比如 Bulletproofs 不需要可信設定，但它在高複雜度情況下的驗證成本會很高。
3. 所依賴的安全假設。安全假設與安全密切相關，比如 Bulletproofs 依賴的是一個標準安全假設：離散對數問題，加上一個隨機預言模型；而 zk-SNARKs 依賴的是一個不可否證的安全假設問題：指數知識假設。
上述的這些指標和屬性很難被同時滿足，因此在設計零知識證明協議，或者選擇零知識證明協議/方法作為某個協議的功能元件的時候，需要考慮特定場景的需求問題。比如對證明時間有較高要求，就可能需要選擇佔用更多空間、或者具有較小通用性的方法；對可信設定有要求，就可能需要選擇有更高證明成本的方法。
因此，一方面，零知識證明是不斷髮展的，各種不同的協議正在被設計出來，某些新協議在某些方面會更具優勢；另一方面，不同的協議有不同的適用場景，要根據需求來做設計或選擇，並沒有一個適用於所有場景的更好的協議。
如果你願意，旅程到此就可以結束了；如果你想繼續，接下來的這一段有點「野」。
5. 另闢蹊徑
這是關於 zk-STARKs 的。它也是零知識證明協議，但它是基於資訊編碼的零知識證明，這是完全不同的一條道路，並且有可能打亂你已經清晰的思路。
zk-STARKs 並沒有使用密碼學中的單向函式，簡單理解的話，它是這樣做的：假設 P 有 9 個要證明的數，a1，a2，……，a9，那麼把它們編碼成 b1，b2，……，b9，每個bi中都含有a1，a2，……，a9 的部分資訊。在做驗證的時候，驗證者 V 對 b1，b2，……，b9 做抽樣檢查，從少量 bi 中就能分析出編碼有沒有錯誤，這樣就可以大概率探測到 a1，a2，……，a9 是否屬實。
當 V 對 P 作隨機抽樣時，P 能夠主動用隨機數混淆抽樣的 bi，同時又能使 V 完成驗證，從而實現零知識性。
所以 zk-STARKs 的「單向」並不是基於計算不可行的單向，它是因為沒有暴露 b1，b2，……，b9 全部，導致無法透過 b1，b2，……，b9 反向計算出 a1，a2，……，a9。在「同態」部分，它也不是抽象代數（或密碼學）中的同態概念，而是基於線性編碼糾錯理論進行抽樣驗證。
zk-STARKs 也不是基於上文介紹的 NPC 難題做驗證，它是基於概率檢查做驗證的。關於這類驗證方法，可以從一種古老的驗證系統 PCP（Probabilistically Checkable Proofs）中找到線索，不過在 zk-STARKs 中使用的方法叫 IOP（Interactive Oracle Proofs），與 PCP 的不同之處在於它用的是 Oracle。
之所以介紹 zk-STARKs，一方面是因為它也頗為流行，另一方面是想說明零知識證明可能是一個難以探索到邊界的事物，比如 zk-STARKs 就是迥異的，因此本文只是理解零知識證明的一個角度，且因為自身認知有限，這種角度也許並不適用於所有的零知識證明方法。
希望這篇文章能讓你更瞭解零知識證明一些，也希望能讓你覺得密碼學、數學是有趣的，因為它的複雜，也因為複雜背後的簡單邏輯。
