ARK:一文讀懂零知識證明背后的簡單邏輯_NPC

文：李畫

來源：BixinInstitute

作者感謝郭宇、吳為龍和ElderRyan的寶貴意見，當然，文責自負。

本文約5000字，閱讀全文需約15分鐘。

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

為什么需要去了解它？隱私問題自不用提，另一個重要原因則在于，隨著對區塊鏈探索的深入，我們發現通過密碼學的方法來實現信任是對共識算法信任的有效補充，這兩種信任可以更低摩擦地結合在一起，因此也更易被實現和應用。這個趨勢也可以從近期區塊鏈技術的發展方向中察覺到。

而只有當我們知道這些密碼學方法背后的邏輯，才不會迷失其中，才能理解它為何要這樣去設計，它適用于什么樣的應用場景。

那么現在，就讓我們開始零知識證明之旅吧。它包含三段旅程：

隱藏秘密之旅；

證明秘密之旅；

構建通用零知識證明之旅。

在《星際迷航》的宇宙，P=NP。

◆1.隱藏秘密：單向功能?◆

在《星際迷航》的宇宙中，P=NP，這對于計算界也許是件好事，它意味著所有可以在多項式時間內驗證的問題，也可以在多項式時間內求解。但對于密碼學界而言，這可能是一場災難。

密碼學需要存在一種「單向功能」，也就是說能夠從?A?計算出?B，但從?B?計算出?A?存在著計算上的不可行性——計算從?A?到?B?是單向的，我們才有可能把?A?藏起來。而如果?P=NP，在多項式時間內可驗證的問題同時也是可求解的，那么通過?B?就能計算出?A，秘密也就無法隱藏。

PROOF聯創：已向70多位藝術家支付超過160萬美元版稅:金色財經報道，PROOF 創始人Kevin Rose在社交媒體上分享了“Moonbirds的項目狀態”，講述了該項目在今年上半年取得的進步，從Moonbirds的藝術愿景到即將推出的獎勵系統。Kevin Rose表示，Moonbirds一直在深化對藝術家的承諾，截至目前已通過Grails III、Evolving Pixels、Diamond Exhibition、Outliers Program和Archive of Feelings by Mika Tajima等NFT項目向70多位藝術家支付超過160萬美元的版稅，他還透露位于洛杉磯的一個實驗性實體空間“The Foundry ”即將開業以更好地支持藝術家合作。此外，Kevin Rose表示PROOF正在開發一個激勵系統，并希望將其打造成PROOF生態系統的基礎，利用代幣作為藝術、數字和現實生活獎勵之間的工具。[2023/7/6 22:20:06]

這就是密碼學背后的簡單邏輯：單向功能。而單向功能背后的支撐是?P!?=NP。

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

零知識證明：

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

橢圓曲線算法是密碼學中被普遍應用的一個具有單向功能的函數，它看起來是這樣的：k?×?P=Q，在已知?P?的情況下，我們可以通過?k?計算出?Q，但難以通過?Q?反向計算出?k。需要注意的是，密碼學中加法或乘法運算的含義不局限于我們熟悉的實數域上加法或乘法運算的含義。

上海：探索區塊鏈在稅務服務、市場監管等場景中應用:金色財經報道，上海市人民政府辦公廳近日印發《2023年上海市全面深化“一網通辦”改革工作要點》。根據《工作要點》，上海市將運用區塊鏈技術賦能政務服務，推動上海市政務區塊鏈與國家行業部門區塊鏈跨鏈共享，逐步建立安全、可信、高效的“一網通辦”平臺服務體系。探索區塊鏈在稅務服務、市場監管、民生服務、財政專項資金支持等場景中應用。(金十)[2023/3/17 13:11:13]

讓我們看看它是如何做到單向性的。在該函數中，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?點。這就像現實世界和影子世界，通過光線的映射，現實空間的物體變成了影子空間的影子。

數據：2月份加密市場共計披露120筆融資，總額達9.5億美元:3月1日消息，據數據網站統計，2023年2月加密市場共計披露120次投融資事件，涉及總金額約9.51億美元，均較1月大幅上漲。其中，基礎設施、游戲、DeFi是融資金額排名前三的賽道，分別為3.6億、1.1億、0.98億美元。另外，融資規模最大的三個項目分別是專注于顛覆性區塊鏈和隱私硬件的半導體公司ChainReaction（7000萬美元）、數字資產基礎設施提供商Taurus（6500萬美元）和數字資產基礎設施提供商Salt Lending（6440萬美元）。[2023/3/1 12:36:15]

這時候假設有一塊機械手表，機芯就是那個隱藏起來的秘密。我們把含機芯的手表拆成?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)?是相同的。同態使得我們可以直接對密文進行計算，然后對隱藏了秘密的明文先計算后加密，再通過比較兩者是否相同驗證明文中是否真的藏有秘密。

一家不良資產投資公司對FTX債權索賠的收購報價僅為每美元8至12美分:11月16日消息，不良資產投資公司Cherokee Acquisition在周二發布的最新價格表中，對于存款索賠超過10萬美元FTX用戶，其收購指導價為每美元8至12美分。當一家公司申請破產保護或宣布破產時，那些不愿等到漫長的破產程序結束后才收回部分或全部資產的債權人，可能會將其信用債權出售給不良資產投資公司。

FTX索賠相對較低的價格表明，FTX用戶收回資金的可能性降低了。507 Capital管理合伙人Thomas Braziel表示，即使是這樣低的價格，對潛在買家來說可能也太高了，沒有人會以這樣的價格購買。他認為更現實的FTX存款債權市場價格應該接近3至5美分。（CoinDesk）[2022/11/16 13:10:29]

同態定義：

抽象代數中，同態是兩個代數結構之間的保持結構不變的映射。

如果你只想了解零知識證明的基本邏輯，旅程到這里就可以結束了，知識點只有兩個：1.?用單向功能隱藏秘密；2.?用同態映射證明秘密。是不是還算輕松？

接下來讓我們看看這個過程在真實的密碼學中是怎樣的，以橢圓曲線數字簽名算法為例，它是一個具有「零知屬性」的算法。你可以選擇不看，它不會影響你對同態的理解。

橢圓曲線數字簽名算法對簽名的驗證：

在該算法中，關鍵的過程是驗證?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)?是手表零部件的影子組合成的手表影子。

Quidd 推出了將數字收藏品鑄造和取消鑄造成 NFT 的功能:6月22日消息，Animoca Brands 及其數字收藏品交易平臺子公司 Quidd 已在名為 Mintables 的以太坊區塊鏈上推出了一項用于鑄造和取消鑄造數字收藏品的功能。根據 Animoca 的一份聲明，Mintables 將使初學者更容易、更便宜地鑄造他們的第一個 NFT，并消除對加密貨幣的需求，同時這些資產與 OpenSea 等流行的以太坊 NFT 市場的互操作性。Animoca Brands 于 2019 年收購了 Quidd 。該應用程序專注于虛擬收集和交易流行品牌的收藏品，從包括曼聯在內的足球隊，以及 Ricky and Morty 等節目。其平臺的數字藏品資產以法定貨幣支付。[2022/6/22 4:44:04]

橢圓曲線算法的同態屬性使得其他算法，比如橢圓曲線數字簽名算法，可以利用它來隱藏并證明秘密，但該算法的能力有限，因為它只具備加法同態，也就是?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問題，而?NPC?問題有一個「特性」，即所有的?NP?問題都可以在多項式時間內歸約成某一個具體的?NPC?問題。

比如布爾電路、圖論三染色、甚至我們熟悉的掃雷游戲，都是?NPC?問題。我們可以把掃雷游戲規約成布爾電路的可滿足性，也就是能夠用證明布爾電路的多項式實現對掃雷游戲的零知識證明；可以把圖論三染色規約成布爾電路的可滿足性，也就是能夠用證明布爾電路的多項式實現對三染色的零知識證明……

因此理論上，我們能夠以任何一個?NPC?問題為基礎構建一個通用的零知識證明協議。但這僅僅是理論上的，因為使用它們做證明的難易度是截然不同的。目前主流的方法是選擇布爾電路或算術電路，因為它們實現起來相對容易、電路規模小，zk-SNARKs?和?Bulletproofs?都是選擇的這種方法。

掃雷游戲

◆

4.零知識證明協議◆

在三段旅程之后，零知識證明對我們而言也許不再是神秘莫測的事物，它背后有著簡單邏輯：1.?單向功能是隱藏秘密的方法；2.?同態映射是證明秘密的基礎；3.?證明?NPC?問題的多項式可以實現通用零知識證明。

不同的零知識證明協議在這三點上的具體實現是不一樣的，最主要的不同可能體現在第?3?點中，哪怕證明的是同一個?NPC?問題，也可以有截然不同的方法。因為不同的設計，零知識證明協議最常被提及的差異主要包括：

1.?不同的計算空間和計算時間。更小的空間和更短的時間是我們不斷改進零知識證明協議的主要動力，也是比較不同零知識證明協議的主要指標。

比如下圖是?ZCash?首席執行官?ZookoWilcox?在談到零知識證明協議時用到的表格，主要比較的就是不同協議的證明時間、驗證時間和證明大小。

來源：https://slideslive.com/38911617/privacy-for-everyone

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中找到線索，不過在?zk-STARKs?中使用的方法叫?IOP，與?PCP?的不同之處在于它用的是?Oracle。

之所以介紹?zk-STARKs，一方面是因為它也頗為流行，另一方面是想說明零知識證明可能是一個難以探索到邊界的事物，比如?zk-STARKs?就是迥異的，因此本文只是理解零知識證明的一個角度，且因為自身認知有限，這種角度也許并不適用于所有的零知識證明方法。

希望這篇文章能讓你更了解零知識證明一些，也希望能讓你覺得密碼學、數學是有趣的，因為它的復雜，也因為復雜背后的簡單邏輯。

Tags：ARKARKS區塊鏈NPCPark StarARKS幣區塊鏈技術通俗講解pptnpc幣官網

火幣交易所