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

文：李畫

來源：BixinInstitute

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

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

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

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

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

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

隱藏秘密之旅；

證明秘密之旅；

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

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

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

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

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

以太坊客戶端Prysm發布含多項重要修復的v4.0.3版本:4月21日消息，據官方推特，以太坊客戶端Prysm已發布v4.0.3版本，此版本包含多項重要修復，建議所有用戶升級。值得注意的是，此版本包含對外部塊生成器代碼路徑和密鑰管理器中漏洞的修復。[2023/4/21 14:18:18]

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

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

零知識證明：

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

橢圓曲線算法是密碼學中被普遍應用的一個具有單向功能的函數，它看起來是這樣的：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?的單向功能使得它可以隱藏私鑰這個秘密。

委內瑞拉已在與加密貨幣相關的石油腐敗案件中逮捕21人:金色財經報道，委內瑞拉檢察官已經逮捕了21位與該國加密貨幣相關的石油腐敗案件人士，他們涉嫌參與國有石油公司委內瑞拉石油公司 (PDVSA) 的一項廣泛的加密貨幣計劃，據悉被捕者中有11人是商人，其余10人是政府官員，此外委內瑞拉政府還對另外11名涉嫌參與同一加密貨幣計劃的人發出了逮捕令，不過委內瑞拉總檢察長Tarek Saab暫時沒有透露相關公司名稱和人員姓名。（路透社）[2023/3/26 13:27:37]

橢圓曲線

◆2.證明秘密：同態◆

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

我們可以把單向功能看成一種映射關系，比如?k?×?P=Q?就是?k?到?Q?的映射：在一個空間中，我們有無數個?k?點，它們被映射到另一個空間，變成無數個?Q?點。這就像現實世界和影子世界，通過光線的映射，現實空間的物體變成了影子空間的影子。

這時候假設有一塊機械手表，機芯就是那個隱藏起來的秘密。我們把含機芯的手表拆成?8?個零部件并映射到影子空間中，這時影子空間就會有?8?個影子；但注意在現實空間我們展示給大家看的是一塊完整的手表，機芯是未暴露的，這塊手表在影子空間也會有個影子，我們叫它第?9?號影子。

現在我們把?8?個零部件的影子組合起來，如果它們能夠組成一塊完整的手表影子，就可以用該影子與第?9?號影子做對比，如果兩者是相同的，就能證明現實空間的這塊手表中是有機芯的，因為它的影子與含機芯的零部件組成的影子相同。這其實就完成了一個簡單的零知識證明過程。

Chipper Cash澄清：在硅谷銀行資金僅約100萬美元，從未尋求被收購:3月15日消息，針對市場出現支付公司Chipper Cash將考慮出售的傳言，該公司首席執行官Ham Serunjogi在其官方網站發布澄清聲明，其中指出雖然硅谷銀行和Silvergate Bank倒閉引發了混亂，但對Chipper Cash的影響“微不足道”，雖然硅谷銀行是該公司的投資方，但他們在硅谷銀行賬戶中持有的資金非常有限，僅約100萬美元，而且Chipper Cash沒有接觸過Silvergate Bank，也“從未尋求被收購”。[2023/3/15 13:05:09]

完整零部件的影子組合成的手表影子與完整手表的影子相同，我們稱這種映射為同態。用數學公式來表達就是?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.?用同態映射證明秘密。是不是還算輕松？

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

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

北京：推動落地國家區塊鏈技術創新中心、加快區塊鏈先進算力平臺建設:金色財經報道，北京市人民政府印發《2023年市政府工作報告重點任務清單》，《任務清單》指出，加快區塊鏈先進算力平臺、人工智能公共算力平臺建設，推動國家區塊鏈技術創新中心在京落地，力爭在區塊鏈等領域取得更多創新應用成果。加大元宇宙等技術應用，建設元宇宙應用創新中心等科技創新標志性場景，加快金融業數字化轉型，推動數字人民幣全域全場景應用。[2023/2/4 11:47:15]

在該算法中，關鍵的過程是驗證?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)。

這相當于把現實空間的物體投射到影子空間后，影子空間可以用加法來組合影子，但對于一些需要用乘法才能組合的影子，它就無能為力了。

怎么辦？可以引入「配對函數」。比如橢圓曲線配對函數就是對橢圓曲線算法做一系列的調整，生成一個新的映射空間，這個新空間既滿足加法同態，也滿足類乘法同態，這樣一來，除了用加法，我們還可以用類乘法去證明秘密。

現在，第二段旅程抵達了終點。我們需要了解的是，同態是證明秘密的關鍵所在，但并不是所有的映射關系都有「良好」的同態，而不同的應用場景對同態的要求也不一樣，在實際的設計中，需要根據具體需求實現不同的同態。

Nervos宣布推出改進后的新版Godwoken:7月3日消息，Nervos在推特上宣布推出改進后的新版Nervos Layer 2網絡Godwoken，它是一個100%兼容EVM的Optimistic Rollup，繼承了L1的安全性，以低Gas費用提供即時交易。[2022/7/3 1:47:38]

如果原空間與映射空間既滿足加法同態，也滿足乘法同態，我們稱其為全同態。全同態意味著可以對密文進行任意的運算，這對實現數據隱私有著重要的意義，但實現全同態是一件非常困難的事情。

◆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：ARKARKSNPCSTARKark幣是騙局嗎MARKS價格MNPCoinSTARK幣

狗狗幣