零知識證明之zk-SNARK（一）多項式的性質與證明_VER

導讀

17 年最早接觸 zk-SNARK 開始，就斷斷續續得學習了一些 zk-SNARK 的知識，但對其原理始終存在諸多困惑，沒有形成一個完整的認識。偶然一次機會，看到了 Maksym Petkus 的這篇文章。文章從最基本的多項式性質講起，從一個簡單易懂的證明協議開始，然后像堆積木一樣在發現問題，修改問題中逐步去完善協議，直到最終構造出完整的 zk-SNARK 協議。另外作者這種從問題出發的講解方式，讓讀者知其然，也知其所以然。作為一枚畢業多年早把數學知識還給老師的程序媛，讀到這篇文章如獲至寶，這篇文章讀下來的感受像找到了一個腳手架，將腦海里碎片化的知識逐漸拼湊完整。于是想把它翻譯出來（已獲得作者授權），一方面加深自己的學習，另一方面也將這份寶藏分享給小伙伴們。文章翻譯存在不足之處，歡迎糾正，補充，指導。

——even@ 安比實驗室

Maksym（作者）：不管是原始的論文 [Bit+11]; [Par+13] 還是原理講解 [Rei16]; [But16]; [But17]; [Gab17]，其實市面上已經有大量關于 zk-SNARK 的學習資源了。zk-SNARK 由大量的可變模塊組成，所以對很多人來說它依然像一個黑盒子一樣很難懂。這些資料對 zk-SNARK 中的一些技術難題部分做出了解釋，但由于缺少了對應的其它環節的解釋，大家還是很難通過這些資料了解到 zk-SNARK 的全貌。當我第一次了解到 zk-SNARK 技術是如何將這些東西完美地融合在一起的時候，就被數學之美震撼到了，并且隨著我發現的維度越多，好奇心就越強烈。在這篇文章中，我主要就基于一些實例簡潔明了地闡明 zk-SNARK，并對這里面的很多問題做出了解釋，并利用這種方式分享了我的經驗，進而讓更多人也能夠欣賞到這項最先進的技術以及它的創新之處，最終欣賞到數學之美。這篇文章的主要貢獻是比較簡潔明了的解釋了其中相當復雜的技術，這些簡單的解釋對于在不具備任何與之相關的先決知識，比如密碼學和高等數學，的前提下理解 zk-SNARK 是很有必要的。文章中并不僅僅只解釋 zk-SNARK 是如何工作的，還解釋了為什么這樣就可以工作，以及它是怎么來的。序言和介紹盡管最初計劃寫短一些，但現在已經寫了幾十頁了，不過這篇文章讀起來幾乎不需要什么預備知識，并且你也可以隨意跳過熟悉的部分。如果你不熟悉文中使用的某些數學符號也不需要擔心，文中將會對這些符號逐個進行介紹。

Zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARK) 確實是一種非常精妙的方法，它可以在不揭示任何信息的前提下證明某個論斷為真。但首要問題是，它為什么有用？

其實零知識證明在無數的應用中都具備優勢，包括：

2）匿名認證：在不揭露身份的情況下（比如登錄密碼），證明請求者 R 有權訪問網站的受限區域證明一個人來自一組被允許的國家/地區列表中的某個國家/地區，但不暴露具體是哪個證明一個人持有地鐵月票，而不透露卡號

3）匿名支付：付款完全脫離任何一種身份納稅而不透露收入

4）外包計算將昂貴的計算外包，并在不重新執行的情況下驗證結果是否正確；它打開了一種零信任計算的類別

改進區塊鏈模型，從所有節點做同樣的計算，到只需一方計算然后其它節點進行驗證

Polygon社區提議將Polygon POS鏈與零知識（ZK）技術兼容:金色財經報道，以太坊擴展解決方案Polygon周二發布了一份提案前（Pre-PIP）討論帖，探討將其Polygon POS鏈與零知識（ZK）技術兼容。升級將使主鏈成為zkEVM validium ，這意味著該鏈仍將與以太坊虛擬機兼容。validium與ZK rollup略有不同，因為它們使用鏈下數據可用性模型，Polygon目前還提供ZK rollup，該rollup于3月上線。

據Polygon聯合創始人Mihailo Bjelic撰寫的博客文章，如果該提案得到Polygon社區的批準，重大升級將帶來更高的安全性，并使區塊鏈的框架更加面向未來。此外，Bjelic認為，這種升級將允許更快的交易確認，并擴展區塊鏈。[2023/6/21 21:50:35]

和「零知識證明」這個偉大的名詞一樣，其背后的方法可以說是數學和密碼學的奇跡。自 1985 年，零知識證明這個概念在「交互式證明系統的知識復雜性」[GMR85] 一文中被引入，還有隨后的非交互式零知識證明 [[BFM88] 以來（在區塊鏈環境中尤其重要），至今已經進入到第四個十年的研究。

在任意的「零知識證明」系統中，都有一個 prover 在不泄漏任何額外信息的前提下要讓 verifier 確信某些陳述（Statement）是正確的。例如 verifier 僅能知道 prover 的銀行賬戶金額超過 X（也就是不披露實際金額）。協議應當滿足下面三個性質：

完整性——只要「陳述」是正確的，prover 就可以讓 verifier 確信可靠性——如果「陳述」是錯誤的，那么作弊的 prover 就沒有辦法讓 verifier 相信零知識——協議的交互僅僅揭露「陳述」是否正確而不泄漏任何其它的信息

zk-SNARK 這個術語本身是在 [Bit+11] 中引入的，它在 [Gro10] 的基礎上，又遵循了匹諾曹協議 [Gen+12; Par+13] 使其能夠適用于通用的計算。證明的媒介這里我們先不要去管零知識，非交互性，其形式和適用性這些概念，就從嘗試證明一些簡單的東西開始。

想象一下我們有一個長度為 10 的位數組，現在要向 verifier（例如，程序）證明這樣一個陳述：所有的位都被設置成了 1。

verifier 一次只能檢查（即，讀）一位。為了驗證這個陳述，我們以某種任意的順序讀取元素并檢查其是否確實等于 1。如果第一次抽樣檢查的結果是 1，就設置「陳述」的可信度為 ?= 10％，否則，如果等于 0，就說明「陳述」是錯誤的。驗證者繼續進行下一輪驗證，直到獲得足夠的可信度為止。假如在一些場景下要信任 prover 需要至少 50% 的可信度，那就意味著必須執行 5 次校驗。但假如在其它一些場景下需要 95% 的可信度，就需要檢查所有的元素。很明顯這個證明協議的缺點是必須要根據元素的數量進行檢查，如果我們處理數百萬個元素的數組，這么做是不現實的。

現在我們來看一下由數學方程式表示的多項式，它可以被畫成坐標系上的一條曲線：

上面的曲線對應多項式: f(x) = x3 – 6x2 +11x– 6。多項式的階數取決于 x 的最大指數，當前多項式的階數是 3。

OKX將升級儲備證明，包括full liability tree披露和用于償付能力驗證的零知識證明:3月2日消息，OKX宣布將在未來幾個月內升級其儲備證明（PoR），包括full liability tree披露和用于PoR償付能力驗證的零知識證明（ZKP）。升級建立在OKX當前的Merkle tree解決方案之上，以確保最大程度的透明度，同時增強客戶隱私，具體安排如下：

- full liability tree：此升級將在即將發布的3月PoR報告中生效，允許任何人下載Full liability Merkle tree，從而提高透明度。同時，它將通過將每個用戶的余額分割和轉移到幾個部分（分割葉節點）來維護帳戶余額的隱私；

- 零知識證明：這一升級將在未來幾個月生效，是一種防篡改的加密方法，允許用戶驗證所有客戶存款都被計入，并通過比較用戶資產凈值與交易所儲備來保證償付能力。[2023/3/2 12:39:00]

多項式有一個非常好的特性，就是如果我們有兩個階為 d 的不相等多項式，他們相交的點數不會超過 d。例如，稍微修改一下原來的多項式為 x3 – 6x2 + 10x– 5（注：請注意這里只修改了多項式的最后一個系數，6 改成了 5）并在圖上用綠色標出：

這一點微小的修改就產生了變化很大的曲線。事實上，我們不可能找到兩條不同的曲線，他們會在某段區域內重合（他們只會相交于一些點）。

這是從找多項式共同點方法中得出的性質。如果要查找兩個多項式的交點，就要先令它們相等。例如，要找到多項式與 x 軸的交點（即 f(x) = 0），我們就要令 x3 – 6x2 + 11x – 6 = 0，等式的解就是共同點：x= 1，x= 2 和 x= 3。在上面圖中也可以很清晰得看出這些解，也就是圖上藍色曲線和 x 軸相交的地方。

同樣，我們也可以令上文中原始的多項式和修改后的多項式相等，找到它們的交點。x3 – 6x2 + 11x – 6 =x3 – 6x2 + 10x – 5x-1=0多項式化簡后的結果階數為 1，它有一個很明顯的解 x = 1。因而這兩個多項式有一個交點。任意一個由階數為 d 的多項式組成的等式，最后都會被化簡為另外一個階數至多為 d 的多項式，這是因為等式中沒有能夠用來構造更高階數的乘法。例如：5x3 + 7x2 – x + 2 = 3x3 – x2 + 2x– 5，簡化為 2x3 + 8x2 – 3x + 7 = 0。另外代數的基本原理也告訴我們，對于一個階數為 d 的多項式至多有 d 個解（以下部分將對此進行詳細介紹），因而也就至多有 d 個共同點。

所以我們可以得出結論，任何多項式在任意點的計算結果（更多關于多項式求值參考：[Pik13]）都可以看做是其唯一身份的表示。我們來計算一下當 x = 10 時，示例多項式的結果。

x3 – 6x2 +11x - 6 = 504x3 – 6x2 +10x - 5 = 495

事實上，在 x 可以選擇的所有值中，至多只有三個值能夠使這些多項式相等，其它的值都是不相等的。

零知識證明技術開發公司StarkWare推出第一個公開版本Cairo 1.0:1月6日消息，零知識證明技術開發公司 StarkWare 宣布推出第一個公開版本的 Cairo 1.0，Cairo 于 2020 年作為圖靈完備的編程語言首次推出，用于高效編寫 STARK 可證明的程序。Cairo 1.0 中最重要的變化之一是語法，新版本的 Cairo 允許編寫更安全的代碼。Cairo 1.0 還引入了 Sierra，這是一種新的中間表示，可確保每次 Cairo 運行都可以得到證明。StarkWare 表示，預計在接下來的幾周內，提供與舊版本相同的 Cairo 1.0 功能，對 StarkNet 合約的支持將在即將到來的 StarkNet Alpha 版本中加入。[2023/1/6 10:24:18]

這也是為什么如果一個 prover 聲稱他知道一些 verifier 也知道的多項式（無論多項式的階數有多大）時，他們就可以按照一個簡單的協議去驗證：

verifier 選擇一個隨機值 x 并在本地計算多項式結果verifier 將 x 值給到 prover，并讓他計算相關的多項式結果prover 代入 x 到多項式計算并將結果給到 verifierverifier 檢查本地的計算結果和 prover 的計算結果是否相等，如果相等那就說明 prover 的陳述具有較高的可信度

例如，我們把 x 的取值范圍定在 1 到 10??, 那么計算結果不同的點的數量，就有 10?? – d 個。因而 x 偶然「撞到」這 d 個結果相同的點中任意一個的概率就等于（可以認為是幾乎不可能）：d/10^77

@Maksym（作者）與低效的位檢查協議相比，新的協議只需要一輪驗證就可以讓陳述具有非常高的可信度（假設 d 遠小于 x 取值范圍的上限，就幾乎是 100% 了）這也是為什么即使可能存在其他的證明媒介，多項式依然是 zk-SNARK 相對核心的部分。

注解even@ 安比實驗室：這一節告訴了我們多項式的一個重要性質：我們不可能找到共享連續段的兩條不相等曲線，也就是任何多項式在任意點的計算結果都可以看做是其唯一身份的表示。也就是說只要能證明多項式上的某個隨機點就可以證明這個多項式（只有在知道了多項式，才能算出這個點對于的值），這個性質是我們下面所有證明的核心。這就是 Schwatz-Zippel 定理，它可以擴展到多變量多項式，即在一個多維空間內形成一個曲面。這個定理會在多個零知識證明方案的證明中反復出現。證明多項式的知識我們的討論從證明多項式的知識開始，再將證明協議逐步轉換成一種通用的方法，在這個過程中我們也將發現多項式的很多其它性質。

但是到目前為止，我們的協議還只是一個很弱的證明，因為協議中并沒有采取任何措施去保證參與方必須按照協議的規則生成證明，所以參與方只能互相信任。例如，prover 并不需要知道多項式，也可能通過其它方式得到正確的答案。而且，如果 verifier 要驗證的多項式的解的取值范圍不夠大，比如我們前文說的 10，那個就可以去猜一個數字，猜對答案的概率是不可忽略不計的。因而我們必須要解決協議中的這個缺陷，在解決問題之前首先來想一下，知道多項式意味著什么呢？

多項式可以用下面的形式來表示（其中 n 指的是多項式的階）：cnxn + …… + c1x1 + c0x0如果一個人說他或她知道一個一階多項式（即：c1x1 + c0=0），那么這就意味著他或她確實知道 系數 c0, c1 的值。這個系數可以是包括 0 在內的任意值。假設證明者聲稱他知道一個包含 x=1 和 x=2 兩個解的三階多項式。滿足此條件的一個有效的多項式就是 x3 – 3x2+ 2x= 0。因為 x= 1: 1 – 3 + 2 = 0，x= 2: 8 – 12 + 4 = 0。我們先來仔細得研究一下這個答案的結構。

聲音 | 數字資產研究院郭宇：區塊鏈的信任需要結合共識算法、零知識證明和形式化驗證:12月22日，數字資產與區塊鏈年會（2019）暨中國投資協會數字資產研究中心成立大會在京舉辦。數字資產研究院學術與技術委員郭宇演講中表示，區塊鏈網絡的吞吐率低下的核心原因是網絡寬帶限制，提高出塊速度是此前比較流行的解決方案，但這種做法會導致區塊鏈分叉，甚至可能威脅區塊鏈系統安全。郭宇認為，要在不降低安全性的前提下，提高區塊鏈吞吐率的解決方案是零知識證明。郭宇指出，區塊鏈系統的可信實際上包括三方面：共識算法提供區塊鏈協議信任，零知識證明提供數據信息和計算完整性，形式化驗證保證計算邏輯可信。區塊鏈的信任需要共識算法、零知識證明和形式化驗證三者的結合。（新浪財經）[2019/12/23]

注解even@ 安比實驗室：這一節告訴了我們多項式的一個本質——多項式的「知識」就是多項式的系數。所謂「知道」多項式就是指「知道」多項式的系數。因式分解代數的基本定理表明了任意的一個多項式只要它有解，就可以將它分解成線性多項式（即，一個階數為 1 的多項式代表一條線），因此，我們可以把任意有效的多項式看成是其因式的乘積：(x-a0)(x-a1)…(x-an) = 0也就是說如果任意一個因式為 0，那么整個等式都為 0，也就是說式子中所有的 as 就是多項式的所有解。x3 - 3x2 + 2x =(x-0)(x-1)(x-2)所以這個多項式的解（x 的值）就是：0，1，2，在任何形式下多項式的解都可以很輕松的被驗證，只不過因式的形式可以讓我們一眼就看出這些解（也稱為根）。我們再回到前面的問題，prover 宣稱他知道一個階數為 3，其中兩個根分別為 1 和 2 的多項式，也就是說這個多項式的形式為：(x-1)(x-2) · …換句話說 (x–1) 和 (x –2) 是問題中多項式的兩個因式。因而如果 prover 想要在不揭示多項式的前提下證明他的多項式確實有這兩個根，那么他就需要去證明他的多項式 p(x) 是 t(x) = (x- 1)(x- 2)（也稱為目標多項式）和一些任意多項式 h(x)（也就是我們的例子里面的 x - 0）的乘積，即：p(x) = t(x) · h(x)換句話說，存在一些多項式 h(x) 能夠使得 t(x) 與之相乘后等于 p(x)，由此得出，p(x) 中包含 t(x)，所以 p(x) 的根中也包含 t(x) 的所有根，這也就是我們要證明的東西。自然算出 h(x) 的方式就是直接相除：如果一個 prover 不能找到這樣一個 h(x) 也就意味著 p(x) 中不包含因式 t(x)，那么多項式相除就會有余數。例如我們用 p(x) = x3 – 3x2 + 2x 除以 t(x) = (x – 1)(x – 2) = x2 – 3x+ 2注意：左邊的式子是分母，右上角的是計算結果。底部是余數（多項式相除的解釋及示例可以看這里 [Pik14]）。我們算出結果 h(x) = x，沒有余數。

注意：為了簡化起見，后面我們會用多項式的字母變量來代替計算結果值，例如：p = p(r)。

注解even@ 安比實驗室：多項式可以被因式分解成它的根的因式的乘積。這個性質就意味著，如果一個多項式有某些解，那么它被因式分解后的式子中一定包含這些解的因式。

聲音 | V神評價MimbleWimble：只有零知識證明 ZK-SNARKs 等全局匿名集，才能真正保證隱私安全:針對 Dragonfly Capital 的分析師 Ivan Bogatyy 發布的關于闡述 MimbleWimble 協議有重大缺陷、Grin 網絡 96% 的交易可被破譯的文章。

以太坊創始人Vitalik在推特回應稱：如果隱私模型設置了一個中等的匿名集，那么它實際上設置了一個小范圍的匿名集。如果隱私模型的匿名集較小，則其匿名集為 1。只有全局匿名集（例如，使用 ZK-SNARKs 技術進行的加密）才真正具有安全性。[2019/11/19]

有了這個性質，我們就可以愉快地去做一些證明啦。

利用多項式一致性檢查協議我們就可以比較多項式 p(x) 和 t(x) ? h(x)：verifier 挑選一個隨機值 r, 計算 t = t(r) (即，求值)，然后將 r 發送給 prover。prover 計算 h(x) =p(x) / t(x)，并對 p(r) 和 h(r) 進行求值，將計算結果 p, h 提供給 verifier。verifier 驗證 p= t?h，如果多項式相等，就意味著 t(x) 是 p(x) 的因式。

實踐一下，用下面的例子來執行這個協議：verifier 選一個隨機數 23，并計算 t = t(23) = (23 – 1)(23 – 2) = 462，然后將 23 發給 proverprover 計算 h(x) =p(x) / t(x) = x, 并對 p(r) 和 h(r) 進行求值，p= p(23) = 10626，h= h(23) = 23，將 p 和 h 提供給 verifierverifier 再驗證 p= t?h：10626 = 462 ? 23 是正確的，這樣陳述就被證明了。

相反，如果 prover 使用一個不同的 p′(x)，它并不包含必要的因式，例如 p′(x) = 2x3 – 3x2 + 2x, 那么：

@Maksym（作者）雖然為了簡化而使用了一組數學符號，但是如果忽視這個無處不在的基本符號：』(上撇) 的話將不利于理解。這個符號本質目的是為了強調一個經過初始變量變換或者推導得到的新變量。即，如果我們想要將 v 乘以 2 并給將它賦值給一個新的變量，我們可以使用：v'= 2 ? v。我們算出結果 2x + 3 和余數 7x – 6，即：p(x) = t(x) × (2x+ 3) + 7x – 6。這就意味著 verifier 為了計算出結果他不得不用 余數除以 t(x)，。

不過由于 x 是 verifier 隨機選擇的，就有極低的概率余數 7x – 6 最終可以被 t(x) 整除。如果后面 verifier 要另外再檢查 p 和 h 必須是整數的話，這個證明才會被拒絕。不過要這么校驗就同時要求多項式系數也是整數，這對協議產生了極大的限制。

這就是為什么接下來我們要介紹能夠使余數不被整除的密碼學原理的原因，盡管這個原始值是有可能被整除的。

Remark 3.1 現在我們就可以在不知道多項式的前提下根據特定的性質來驗證多項式了，這就已經給了我們一些零知識和簡明性的特性。但是，這個結構中還存在好多問題：

prover 可能并不知道他所聲稱的 p(x)，他可以先算一下 t = t(r)，然后選擇一個隨機值 h，由此計算出 p = t?h。因為等式是成立的，所以也能通過 verifier 的校驗。

因為 prover 知道隨機點 x = r，他可以構造出一個任意的多項式，這個任意多項式與 t(r) ? h(r) 在 r 處有共同點。

在前面的「陳述」中，prover 聲稱他知道一個特定階數的多項式，但現在的協議對階數并沒有明確的要求。因而 prover 完全可以拿一個滿足因式校驗的更高階數的多項式來欺騙 verifier。下面我們就要來逐一得解決這些問題。

注解even@ 安比實驗室：利用因式的性質構造出了一個證明協議，但這個協議存在一些缺陷，主要是由于

prover 知道了 t(r)，他就可以反過來任意構造一個可以整除 t(r) 的 p(r)prover 知道了點 (r,t(r) · h(r)) 的值，就可以構造經過這一點的任意多項式，同樣滿足校驗協議并沒有對 prover 的多項式階數進行約束模糊計算Remark 3.1 中的前兩個問題是由于 暴露了原始值 而導致的，也就是 prover 知道了 r 和 t(r)。但如果 verifier 給出的這個值像放在黑盒里一樣不可見的話就完美了，也就是一個人即使不破壞協議，也依然能在這些模糊的值上面完成計算。有點類似哈希函數，從計算結果就很難再回到原始值上。同態加密這也就是要設計同態加密的原因。它允許加密一個值并在密文上進行算術運算。獲取加密的同態性質的方法有多種，我們來介紹一個簡單的方法。總體思路就是我們選擇一個基礎的（基數需要具有某些特定的屬性）的自然數 g（如 5），然后我們以要加密的值為指數對 g 進行求冪。例如，如果我們要對 3 進行加密：53=125這里 125 就是 3 對應的密文。如果我們想要對被加密的值乘 2，我們可以以 2 為指數來對這個密文進行計算。1252 = 15625 = (53)2 = 52×3 = 56我們不僅可以用 2 來乘以一個未知的值并保持密文的有效性，還可以通過密文相乘來使兩個值相加，例如 3+2：53 · 52 = 53+2 = 5 5 =3125同樣的，我們還可以通過相除提取加密的數字，例如：5-355/53 = 55 ·5-3 =5 5-3 = 52 =25不過由于基數 5 是公開的，很容易就可以找到被加密的數字。只要將密文一直除以 5，直到結果為 1，那么做除法的次數也就是被加密值的數。

模運算這里就到了模運算發揮作用的地方了。模運算的思路如下：除了我們所選擇的組成有限集合的前 n 個自然數（即，0，1，…，n-1）以外，任何超出此范圍的給定整數，我們就將它「纏繞」起來。例如，我們選擇前六個數。為了說明這一點，可以把它看做一個有六個單位大小相等刻度的圓；這就是我們所說的范圍（通常指的是有限域）。

現在我們看一下數字八應該在哪里。打個比方，我們可以把它看成一條長度為 8 的繩子。

如果我們將繩子固定在圓圈的開頭

然后用繩子纏繞圓圈，我們在纏完一圈后還剩下一部分的繩子。然后我們繼續纏繞，這根繩子將在刻度 2 的地方終止。

這就是模運算操作的結果。無論這根繩子多長，它最終都會在圓圈一個刻度處終止。因而模運算結果將保持在一定范圍內（例子中是 0 到 5）。長度為 15 的繩子將會在刻度 3 的地方終止，即 6 + 6 + 3（纏 2 個完整的圈并剩下 3 個單位長的部分）。負數運算類似，唯一不同的地方就是它是沿相反方向纏繞的，如 -8 的取模結果是 4。

我們執行算術運算，結果都將落在這 n 的范圍內。現在開始我們將用符號「mod n」來表示這個范圍內的數。

3 × 5 = 3 mod 65 + 2 = 1 mod 6

另外，模運算最重要的性質就是運算順序無所謂。例如，我們可以先做完所有的操作，然后再取模，或者每操作完一步都去取模。例如 (2 × 4 – 1) × 3 = 3 (mod 6) 就等于：

2 × 4 = 1 mod 62 - 1 = 1 mod 61 × 3 = 3 mod 6

那么模運算到底有什么用呢？就是如果我們使用模運算，從運算結果再回到原始值并不容易，因為很多不同的組合會產生一個同樣的運算結果：

5 × 4 = 2 mod 64 × 2 = 2 mod 62 × 1 = 1 mod 6……

沒有模運算的話，計算結果的大小會給找出原始值提供一些線索。除非這里既能把信息隱藏起來，又可以保留常見的算術屬性。

強同態加密我們再回到同態加密上，使用模運算，例如取模 7，我們可以得到：51 = 5(mod 7)52 = 4(mod 7)53 = 6(mod 7)……不同指數下運算得到了同樣的結果：55 = 3(mod 7)511 = 3(mod 7)517 = 3(mod 7)……這樣就很難知道指數是多少了。事實上，如果模取得相當大，從運算結果倒推指數運算就不可行了；現代密碼學很大程度上就是基于這個問題的「困難」。

方案中所有的同態性質都在模運算中保留了下來：

encryption: 53 = 6 (mod 7)multiplication: 62 = (53)2 = 56 = 1 (mod 7)addition: 53 · 52 = 55 = 3(mod 7)

注意：模相除有點難已經超出范圍了。我們來明確地說明一下加密函數：E(v) = gv(mod n)這里 v 就是我們要加密的值。Remark 3.2 這個同態加密模式有一個限制，我們可以把一個加密的值和一個未加密的值相乘，但我們不能將兩個加密的值相乘（或者相除），也就是說我們不能對加密值取冪。雖然這些性質第一感覺看起來很不友好，但是這卻構成了 zk-SNARK 的基礎。這個限制后面將在「加密值乘法」一節中講到。

注解even@ 安比實驗室：通過模運算形成的集合被稱為「有限域」，而通過計算指數再進行模運算形成的集合構成「循環群」。常見的同態加密方式除了整數冪取模之外，還有橢圓曲線上的倍乘。加密多項式配合這些工具，我們現在就可以在加密的隨機數 x 上做運算并相應地修改零知識 協議了。我們來看一下如何計算多項式 p(x) = x3 – 3x2 + 2x。我們前面明確了，知道一個多項式就是知道它的系數，也就是這個例子中知道：1，-3，2。因為同態加密并不允許再對加密值求冪，所以我們必須要給出 x 的 1 到 3 次冪取加密值：E(x)，E(x2)，E(x3)，那么我們要計算的加密多項式就是：E(x3)1 · E(x2)-3 · E(x)2 = (gx3)1 · (gx2)-3 ·(gx)2 = g1x3 · (g-3x2)·(gx)2 = g x3-3x2+2x所以通過這些運算，我們就獲得了多項式在一些未知數 x 處的加密計算結果。這確實是一個很強大的機制，因為同態的性質，同一個多項式的加密運算在加密空間中始終是相同的。

我們現在就可以更新前面版本的協議了，比如對于階數為 d 的多項式：

Verifier取一個隨機數 s，也就是秘密值指數 i 取值為 0，1，…，d 時分別計算出 s 的 i 次冪的加密結果，即：代入 s 計算未加密的目標多項式：t(s)將對 s 的冪的加密值提供給 prover：E(s0)，E(s1)，，E(sd)

Prover計算多項式 h(x) = p(x)/t(x)使用加密值，，…，和系數，，…，計算 g^p(s)然后同樣計算 E(h(s)) =gh(s)將結果 gp 和 gh 提供給 verifier

Verifier最后一步是 verifier 去校驗 p = t(s) ·h: gp = (gh)t(s) => gp = gt(s)·h注意：因為證明者并不知道跟 s 相關的任何信息，這就使得他很難提出不合法但是能夠匹配驗證的計算結果。

盡管這個協議中 prover 的靈活性有限，他依然可以在實際不使用 verifier 所提供的加密值進行計算，而是通過其它的方式來偽造證明。例如，如果 prover 聲稱有一個滿足條件的多項式它只使用了 2 個求冪值 s3 和 s1，這個在當前協議中是不能驗證的。

注解even@ 安比實驗室：利用強同態加密這個工具，構造了一個相對較強的零知識證明協議。但是如上文所述，這里還是存在一些問題——無法驗證 prover 是否是真的使用了 verifier 提供的值來構造證明的。

大家可以思考一下，如何解決這個問題？以及這個協議還存在哪些缺陷呢？

在下一節中，我們將會繼續展開討論，并展示如何構造一個完備的多項式的零知識證明協議。

Tags：VERROVERPRORIFIDogereversedAdroversecoinbasepro下載RIFICO幣

歐易交易所app下載