零知識(shí)證明的邏輯概念詳細(xì)解析

零知識(shí)證明的工程實(shí)現(xiàn)是一件極具挑戰(zhàn)性的工作，但這并不意味著理解零知識(shí)證明這件事也同樣困難，它背后的邏輯是簡(jiǎn)單的。

為什么需要去了解它？隱私問(wèn)題自不用提，另一個(gè)重要原因則在于，隨著對(duì)區(qū)塊鏈探索的深入，我們發(fā)現(xiàn)通過(guò)密碼學(xué)的方法來(lái)實(shí)現(xiàn)信任是對(duì)共識(shí)算法信任的有效補(bǔ)充，這兩種信任可以更低摩擦地結(jié)合在一起，因此也更易被實(shí)現(xiàn)和應(yīng)用。這個(gè)趨勢(shì)也可以從近期區(qū)塊鏈技術(shù)的發(fā)展方向中察覺(jué)到。

而只有當(dāng)我們知道這些密碼學(xué)方法背后的邏輯，才不會(huì)迷失其中，才能理解它為何要這樣去設(shè)計(jì)，它適用于什么樣的應(yīng)用場(chǎng)景。

那么現(xiàn)在，就讓我們開(kāi)始零知識(shí)證明之旅吧。它包含三段旅程：

隱藏秘密之旅；

證明秘密之旅；

構(gòu)建通用零知識(shí)證明之旅。

1. 隱藏秘密：?jiǎn)蜗蚬δ?/p>

在《星際迷航》的宇宙中，P = NP，這對(duì)于計(jì)算界也許是件好事，它意味著所有可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證的問(wèn)題，也可以在多項(xiàng)式時(shí)間內(nèi)求解。但對(duì)于密碼學(xué)界而言，這可能是一場(chǎng)災(zāi)難。

密碼學(xué)需要存在一種「單向功能」，也就是說(shuō)能夠從 A 計(jì)算出 B，但從 B 計(jì)算出 A 存在著計(jì)算上的不可行性——計(jì)算從 A 到 B 是單向的，我們才有可能把 A 藏起來(lái)。而如果 P = NP，在多項(xiàng)式時(shí)間內(nèi)可驗(yàn)證的問(wèn)題同時(shí)也是可求解的，那么通過(guò) B 就能計(jì)算出 A，秘密也就無(wú)法隱藏。

這就是密碼學(xué)背后的簡(jiǎn)單邏輯：?jiǎn)蜗蚬δ?。而單向功能背后的支撐?P！ = NP。

這與零知識(shí)證明的關(guān)系是什么呢？我們可以把零知識(shí)證明分解為兩個(gè)功能，第一個(gè)功能是隱藏秘密，第二個(gè)功能是證明自己有秘密。而隱藏秘密，如上文所述，就是找到一個(gè)具有單向功能的計(jì)算式。

零知識(shí)證明：

零知識(shí)證明是指讓驗(yàn)證者相信某個(gè)斷言為真，且整個(gè)過(guò)程不泄露「斷言為真」之外的任何知識(shí)。為了更容易理解，本文把它簡(jiǎn)化為隱藏秘密和證明擁有秘密。

橢圓曲線算法（ECC）是密碼學(xué)中被普遍應(yīng)用的一個(gè)具有單向功能的函數(shù)，它看起來(lái)是這樣的：k × P = Q，在已知 P 的情況下，我們可以通過(guò) k 計(jì)算出 Q，但難以通過(guò) Q 反向計(jì)算出 k。需要注意的是，密碼學(xué)中加法或乘法運(yùn)算的含義不局限于我們熟悉的實(shí)數(shù)域上加法或乘法運(yùn)算的含義。

讓我們看看它是如何做到單向性的。在該函數(shù)中，P 是橢圓曲線上的一個(gè)點(diǎn)，我們把一個(gè)小球放在該點(diǎn)并沿切線方向擊打出去，小球在橢圓曲線中撞來(lái)撞去撞了 k 次（大致可以這么理解），最后會(huì)落在一個(gè)點(diǎn) Q 上。如果我們知道初始位置 P 和撞擊次數(shù) k，是能算出小球的落點(diǎn) Q 的；但如果我們只看見(jiàn)小球落在 Q 上，是無(wú)法算出從 P 點(diǎn)到 Q 點(diǎn)撞了多少次，也就是 k 的。

下圖是 k = 2 的一個(gè)示例，小球從 P 點(diǎn)出發(fā)，撞擊了兩次落在 Q 點(diǎn)上，因此 Q 等于2 × P。橢圓曲線算法常被用于生成公鑰和私鑰，公鑰就是小球最后的落點(diǎn) Q，私鑰就是撞擊次數(shù) k。k × P = Q 的單向功能使得它可以隱藏私鑰這個(gè)秘密。

2. 證明秘密：同態(tài)

對(duì)于零知識(shí)證明來(lái)說(shuō)，隱藏秘密只是第一步，我們還需要證明自己確實(shí)掌握了秘密。就像在第一段旅程中只需要理解單向功能，在這第二段旅程中，我們只需要理解「同態(tài)」，有了同態(tài)我們就有了證明秘密的能力。那么什么是同態(tài)？

我們可以把單向功能看成一種映射關(guān)系，比如 k × P = Q 就是 k 到 Q 的映射：在一個(gè)空間中，我們有無(wú)數(shù)個(gè) k 點(diǎn)，它們被映射到另一個(gè)空間，變成無(wú)數(shù)個(gè) Q 點(diǎn)。這就像現(xiàn)實(shí)世界和影子世界，通過(guò)光線的映射，現(xiàn)實(shí)空間的物體變成了影子空間的影子。

這時(shí)候假設(shè)有一塊機(jī)械手表，機(jī)芯就是那個(gè)隱藏起來(lái)的秘密。我們把含機(jī)芯的手表拆成 8 個(gè)零部件并映射到影子空間中，這時(shí)影子空間就會(huì)有 8 個(gè)影子；但注意在現(xiàn)實(shí)空間我們展示給大家看的是一塊完整的手表，機(jī)芯是未暴露的，這塊手表在影子空間也會(huì)有個(gè)影子，我們叫它第 9 號(hào)影子。

現(xiàn)在我們把 8 個(gè)零部件的影子組合起來(lái)，如果它們能夠組成一塊完整的手表影子，就可以用該影子與第 9 號(hào)影子做對(duì)比，如果兩者是相同的，就能證明現(xiàn)實(shí)空間的這塊手表中是有機(jī)芯的，因?yàn)樗挠白优c含機(jī)芯的零部件組成的影子相同。這其實(shí)就完成了一個(gè)簡(jiǎn)單的零知識(shí)證明過(guò)程。

完整零部件的影子組合成的手表影子與完整手表的影子相同，我們稱這種映射為同態(tài)。用數(shù)學(xué)公式來(lái)表達(dá)就是 f（手表） = f（零件1 + …… + 零件8） = f（零件1） + …… + f（零件8）。其中，f（手表）是手表的影子，f（零件1） + …… + f（零件8） 是零部件的影子組合成的手表影子。

簡(jiǎn)化一下這種關(guān)系就是：f（a+b） = f（a） + f（b），即「先計(jì)算后加密的結(jié)果」f（a+b） 與「先加密后計(jì)算的結(jié)果」f（a） + f（b） 是相同的。同態(tài)使得我們可以直接對(duì)密文進(jìn)行計(jì)算，然后對(duì)隱藏了秘密的明文先計(jì)算后加密，再通過(guò)比較兩者是否相同驗(yàn)證明文中是否真的藏有秘密。

同態(tài)定義：

抽象代數(shù)中，同態(tài)是兩個(gè)代數(shù)結(jié)構(gòu)（例如群、環(huán)、或者向量空間）之間的保持結(jié)構(gòu)不變的映射。

如果你只想了解零知識(shí)證明的基本邏輯，旅程到這里就可以結(jié)束了，知識(shí)點(diǎn)只有兩個(gè)：1. 用單向功能隱藏秘密；2. 用同態(tài)映射證明秘密。是不是還算輕松？

接下來(lái)讓我們看看這個(gè)過(guò)程在真實(shí)的密碼學(xué)中是怎樣的，以橢圓曲線數(shù)字簽名算法（ECDSA）為例，它是一個(gè)具有「零知屬性」的算法。你可以選擇不看，它不會(huì)影響你對(duì)同態(tài)的理解。

橢圓曲線數(shù)字簽名算法對(duì)簽名的驗(yàn)證：

在該算法中，關(guān)鍵的過(guò)程是驗(yàn)證 f（Z + dA × R） = f（Z） + f（dA × R） = f（Z） + Qa × R，其中，Z 是需要用私鑰簽名的消息，dA 是私鑰，R 與隨機(jī)數(shù)相關(guān)，Qa 是公鑰。因?yàn)橥瑧B(tài)屬性，這個(gè)等式是成立的，我們就可以用等式右邊的 Qa（公鑰）來(lái)驗(yàn)證 Z 是否是用等式左邊的 dA（私鑰） 簽名的。

在這里，dA 是機(jī)芯，Z+dA×R 是藏有機(jī)芯的手表，f（Z + dA × R） 是這塊手表的影子，而 f（Z） + f（dA × R） 是手表零部件的影子組合成的手表影子。

橢圓曲線算法的同態(tài)屬性使得其他算法，比如橢圓曲線數(shù)字簽名算法，可以利用它來(lái)隱藏并證明秘密，但該算法的能力有限，因?yàn)樗痪邆浼臃ㄍ瑧B(tài)，也就是 f（a+b） = f（a） + f（b），但不具備乘法同態(tài)，即 f（a×b） = f（a） × f（b）。

這相當(dāng)于把現(xiàn)實(shí)空間的物體投射到影子空間后，影子空間可以用加法來(lái)組合影子，但對(duì)于一些需要用乘法才能組合的影子，它就無(wú)能為力了。

怎么辦？可以引入「配對(duì)函數(shù)」。比如橢圓曲線配對(duì)函數(shù)就是對(duì)橢圓曲線算法做一系列的調(diào)整，生成一個(gè)新的映射空間，這個(gè)新空間既滿足加法同態(tài)，也滿足類乘法同態(tài)（注意，只是類乘法同態(tài)），這樣一來(lái)，除了用加法，我們還可以用類乘法去證明秘密。

現(xiàn)在，第二段旅程抵達(dá)了終點(diǎn)。我們需要了解的是，同態(tài)是證明秘密的關(guān)鍵所在，但并不是所有的映射關(guān)系都有「良好」的同態(tài)，而不同的應(yīng)用場(chǎng)景對(duì)同態(tài)的要求也不一樣，在實(shí)際的設(shè)計(jì)中，需要根據(jù)具體需求實(shí)現(xiàn)不同的同態(tài)。

如果原空間與映射空間既滿足加法同態(tài)，也滿足乘法同態(tài)，我們稱其為全同態(tài)。全同態(tài)意味著可以對(duì)密文進(jìn)行任意的運(yùn)算（可以對(duì)影子進(jìn)行任意方式的組合），這對(duì)實(shí)現(xiàn)數(shù)據(jù)隱私有著重要的意義，但實(shí)現(xiàn)全同態(tài)是一件非常困難的事情。

3. 通用零知識(shí)證明：NPC 問(wèn)題

你一定注意到了，我們說(shuō)橢圓曲線數(shù)字簽名算法具有「零知屬性」，卻并沒(méi)有說(shuō)它是零知識(shí)證明協(xié)議，因?yàn)樗闹鳂I(yè)是做數(shù)字簽名，隱藏私鑰只不過(guò)是它必須要實(shí)現(xiàn)的一個(gè)功能。而且它也只能隱藏私鑰，如果想讓它幫你隱藏一個(gè)你自己的秘密，它是做不到的。

而零知識(shí)證明協(xié)議，比如我們熟悉的 zk-SNARKs，它的主業(yè)就是隱藏并能證明需要它隱藏的各類秘密。這是如何做到的？

讓我們回到本文最開(kāi)始的那個(gè)單向函數(shù) k × P = Q，它能隱藏一個(gè)秘密 k，如果我們把它變復(fù)雜一些，比如變成 t × h = （v0 + a1 × v1 + …… + am × vm）（w0 + b1 × w1 + …… + bm × wm）這樣一個(gè)多項(xiàng)式，是不是就有了很多可以隱藏秘密的「空間」，比如把秘密放在 a1，a2，……，am 中。

事實(shí)上，上文中這個(gè)復(fù)雜的多項(xiàng)式就是 zk-SNARKs 中用于實(shí)現(xiàn)零知識(shí)證明的多項(xiàng)式，該多項(xiàng)式能夠證明各類秘密，因?yàn)樗茏C明布爾電路。

為什么能證明布爾電路，就能證明各類秘密？因?yàn)椴紶栯娐房蓾M足性是一個(gè) NPC（NP-Complete）問(wèn)題，而 NPC 問(wèn)題有一個(gè)「特性」，即所有的 NP 問(wèn)題（包含NPC）都可以在多項(xiàng)式時(shí)間內(nèi)歸約（轉(zhuǎn)換）成某一個(gè)具體的 NPC 問(wèn)題。

比如布爾電路、圖論三染色、甚至我們熟悉的掃雷游戲，都是 NPC 問(wèn)題。我們可以把掃雷游戲規(guī)約成布爾電路的可滿足性，也就是能夠用證明布爾電路的多項(xiàng)式實(shí)現(xiàn)對(duì)掃雷游戲的零知識(shí)證明；可以把圖論三染色規(guī)約成布爾電路的可滿足性，也就是能夠用證明布爾電路的多項(xiàng)式實(shí)現(xiàn)對(duì)三染色的零知識(shí)證明……

因此理論上，我們能夠以任何一個(gè) NPC 問(wèn)題為基礎(chǔ)構(gòu)建一個(gè)通用的零知識(shí)證明協(xié)議。但這僅僅是理論上的，因?yàn)槭褂盟鼈冏鲎C明的難易度是截然不同的。目前主流的方法是選擇布爾電路或算術(shù)電路，因?yàn)樗鼈儗?shí)現(xiàn)起來(lái)相對(duì)容易、電路規(guī)模小，zk-SNARKs 和 Bulletproofs 都是選擇的這種方法。

4. 零知識(shí)證明協(xié)議

在三段旅程之后，零知識(shí)證明對(duì)我們而言也許不再是神秘莫測(cè)的事物，它背后有著簡(jiǎn)單邏輯：1. 單向功能是隱藏秘密的方法；2. 同態(tài)映射是證明秘密的基礎(chǔ)；3. 證明 NPC 問(wèn)題的多項(xiàng)式（但這并非唯一的方法）可以實(shí)現(xiàn)通用零知識(shí)證明。

不同的零知識(shí)證明協(xié)議在這三點(diǎn)上的具體實(shí)現(xiàn)是不一樣的，最主要的不同可能體現(xiàn)在第 3 點(diǎn)中，哪怕證明的是同一個(gè) NPC 問(wèn)題，也可以有截然不同的方法。因?yàn)椴煌脑O(shè)計(jì)，零知識(shí)證明協(xié)議最常被提及的差異主要包括：

1. 不同的計(jì)算空間和計(jì)算時(shí)間。更小的空間和更短的時(shí)間是我們不斷改進(jìn)零知識(shí)證明協(xié)議的主要?jiǎng)恿?，也是比較不同零知識(shí)證明協(xié)議的主要指標(biāo)。

比如下圖是 ZCash 首席執(zhí)行官 Zooko Wilcox 在談到零知識(shí)證明協(xié)議時(shí)用到的表格，主要比較的就是不同協(xié)議的證明時(shí)間、驗(yàn)證時(shí)間和證明大小。

2. 是否需要初始化可信設(shè)置。不需要可信設(shè)置當(dāng)然更好，會(huì)減少信任問(wèn)題和安全問(wèn)題，不過(guò)新的證明方法就可能帶來(lái)新的計(jì)算問(wèn)題，比如 Bulletproofs 不需要可信設(shè)置，但它在高復(fù)雜度情況下的驗(yàn)證成本會(huì)很高。

3. 所依賴的安全假設(shè)。安全假設(shè)與安全密切相關(guān)，比如 Bulletproofs 依賴的是一個(gè)標(biāo)準(zhǔn)安全假設(shè)：離散對(duì)數(shù)問(wèn)題，加上一個(gè)隨機(jī)預(yù)言模型；而 zk-SNARKs 依賴的是一個(gè)不可否證的安全假設(shè)問(wèn)題：指數(shù)知識(shí)假設(shè)。

上述的這些指標(biāo)和屬性很難被同時(shí)滿足，因此在設(shè)計(jì)零知識(shí)證明協(xié)議，或者選擇零知識(shí)證明協(xié)議/方法作為某個(gè)協(xié)議的功能組件的時(shí)候，需要考慮特定場(chǎng)景的需求問(wèn)題。比如對(duì)證明時(shí)間有較高要求，就可能需要選擇占用更多空間、或者具有較小通用性的方法；對(duì)可信設(shè)置有要求，就可能需要選擇有更高證明成本的方法。

因此，一方面，零知識(shí)證明是不斷發(fā)展的，各種不同的協(xié)議正在被設(shè)計(jì)出來(lái)，某些新協(xié)議在某些方面會(huì)更具優(yōu)勢(shì)；另一方面，不同的協(xié)議有不同的適用場(chǎng)景，要根據(jù)需求來(lái)做設(shè)計(jì)或選擇，并沒(méi)有一個(gè)適用于所有場(chǎng)景的更好的協(xié)議。

如果你愿意，旅程到此就可以結(jié)束了；如果你想繼續(xù)，接下來(lái)的這一段有點(diǎn)「野」。

5. 另辟蹊徑

這是關(guān)于 zk-STARKs 的。它也是零知識(shí)證明協(xié)議，但它是基于信息編碼的零知識(shí)證明，這是完全不同的一條道路，并且有可能打亂你已經(jīng)清晰的思路。

zk-STARKs 并沒(méi)有使用密碼學(xué)中的單向函數(shù)，簡(jiǎn)單理解的話，它是這樣做的：假設(shè) P 有 9 個(gè)要證明的數(shù)，a1，a2，……，a9，那么把它們編碼成 b1，b2，……，b9，每個(gè)bi中都含有a1，a2，……，a9 的部分信息。在做驗(yàn)證的時(shí)候，驗(yàn)證者 V 對(duì) b1，b2，……，b9 做抽樣檢查，從少量 bi 中就能分析出編碼有沒(méi)有錯(cuò)誤，這樣就可以大概率探測(cè)到 a1，a2，……，a9 是否屬實(shí)。

當(dāng) V 對(duì) P 作隨機(jī)抽樣時(shí)，P 能夠主動(dòng)用隨機(jī)數(shù)混淆抽樣的 bi，同時(shí)又能使 V 完成驗(yàn)證，從而實(shí)現(xiàn)零知識(shí)性。

所以 zk-STARKs 的「單向」并不是基于計(jì)算不可行的單向，它是因?yàn)闆](méi)有暴露 b1，b2，……，b9 全部，導(dǎo)致無(wú)法通過(guò) b1，b2，……，b9 反向計(jì)算出 a1，a2，……，a9。在「同態(tài)」部分，它也不是抽象代數(shù)（或密碼學(xué)）中的同態(tài)概念，而是基于線性編碼糾錯(cuò)理論進(jìn)行抽樣驗(yàn)證。

zk-STARKs 也不是基于上文介紹的 NPC 難題做驗(yàn)證，它是基于概率檢查做驗(yàn)證的。關(guān)于這類驗(yàn)證方法，可以從一種古老的驗(yàn)證系統(tǒng) PCP（Probabilistically Checkable Proofs）中找到線索，不過(guò)在 zk-STARKs 中使用的方法叫 IOP（InteracTIve Oracle Proofs），與 PCP 的不同之處在于它用的是 Oracle。

之所以介紹 zk-STARKs，一方面是因?yàn)樗差H為流行，另一方面是想說(shuō)明零知識(shí)證明可能是一個(gè)難以探索到邊界的事物，比如 zk-STARKs 就是迥異的，因此本文只是理解零知識(shí)證明的一個(gè)角度，且因?yàn)樽陨碚J(rèn)知有限，這種角度也許并不適用于所有的零知識(shí)證明方法。