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