導讀上一篇文章（多項式的性質與證明）中，作者介紹瞭如何利用多項式的性質來證明某個多項式的知識，相信大家已經對構造證明有了一些基本的認識。目前的證明協議仍然存在一些缺陷，本文將會針對這些薄弱項進行改進，進而最終構造出關於多項式的零知識證明協議。本文重點：KEA，互動式零知識證明，非互動式零知識證明和 Setup。—— even@安比實驗室作者：Maksym Petkus翻譯 & 註解：even@安比實驗室（[email protected]）校對：valuka@安比實驗室本系列文章已獲作者中文翻譯授權。
限制多項式上文說到，多項式的知識其實就是它的係數 c0, c1, …, ci 的知識。協議中我們是透過對秘密值 s 的冪的加密值再進行求冪來對係數進行“賦值”。我們已經限制了 prover 對 s 冪的加密值的選擇, 但是這個限制並不是強制的 ，也就是說，prover 可以使用任何可能的方法找到滿足下面等式的值 zp 和 zh
再用這兩個值來代替 gᵖ 和 gʰ 將它交給 verifier。所以 verifier 需要能夠證明 prover 給出的值就是用 s 冪的加密值而不是其它值計算出來的。
我們看一個由一個變數和一個係陣列成的一階多項式的簡單例子，對應的 s 的加密值為 E(s) = gˢ。這裡我們要做的就是確保 prover 是拿 s 的加密值，即 gˢ ，而不是其他值與係數 c 做同態相乘的。所以結果一定是這個形式（c 為任意值）：
解決這個問題的一種方法就是用另一個“變換”的加密值做同樣的操作，充當類似算術中“校驗和”（Checksum） 的作用，以此確保結果是原始值的求冪值。
這個是透過 Knowledge-of-Exponent Assumption (簡稱 KEA) 方法來實現的，在 [Dam91] 中有介紹，更精準一點（注意 a 和 α(alpha)這兩個字元的不同）說：
a）Alice 有一個值 a，她想要 Bob 對其進行任意指數的求冪（這裡 a 是一個有限域群的生成器），唯一的要求是隻能對 a 進行求冪，為了保證這一點，她要：
選擇一個隨機數 α
計算 a' = a α(mod n)
提供一個元組 (a, a') 給 Bob, 然後讓他對這兩個值執行任意的求冪運算，返回結果元組 (b, b')，這裡的指數 “α-變換” 依然保持不變，即 bα = b'(mod n)
b) 因為 Bob 無法從元組 (a, a') 中提取 α 的值，透過暴力破解也難以實現，那就可以推斷 Bob 生成有效元組的唯一方法就是執行下面的步驟：
選擇一個值 c
計算 b=(a)c(mod n) 和 b' = (a')c (mod n)
回覆 (b,b')
c) 有了回覆的元組和 α，Alice 就可以驗證等式：
(b)α = b'
(ac)α = (a')c
ac·α = (aα)c
結論是：
Bob 在元組的兩個值的計算上都用了同一個指數（即 c）
Bob 只能用 Alice 原本的元組來保持 α 關係
Bob 知道指數 c，因為構造驗證值 (b,b′) 的唯一方式是用同一個指數
Alice 並不知道 c，這和 Bob 不知道 α 的原因一樣
雖然 c 是被加密的，但它的可能取值範圍並不足夠大到保持其零知識的性質，這個問題我們將在後面“零知識”那一節解決。
最後這個協議提供了一個證明給 Alice ，Bob 確實是用他知道的某個值對 a 進行求冪的，而且他也不能做別的任何操作，例如：乘法，加法，因為這樣就會破壞 α-變換關係。
在同態加密中，求冪是對被加密值進行乘法運算。我們可以應用這個結構到一個簡單的係數多項式 f(x) = c⋅ x的例子中：verifier 選擇隨機數 s, α，然後提供令 x=s 的一階及其轉換的計算值：αprover 代入係數 c 計算:
verifier 驗證：αα
這個結構“限制” prover 只能用 verifier 提供的加密的 s 進行計算，因而 prover 只能將係數 c 賦給 verifier 提供的多項式。現在我們可以擴充套件這種單項式上的方法到多項式上，因為計算是先將每項的分配分開計算然後再 “同態地” 相加在一起的（這個方法是 Jens Groth 在 [Gro10] 中介紹的）。所以如果給定 prover 一個指數為 s 的冪以及它們的變換的加密值，他就可以計算原始的和變換後的多項式，這裡也必須要滿足同樣的校驗。對於階數為 d 的多項式：verifier 提供加密值,,…,和他們的變換 α,α,…,αprover:計算給定的帶有 s 的冪的加密多項式計算給定的帶有 s 的冪的轉換的加密“轉換”多項式：將計算結果,發給verfierverifier 校驗：α
前面的多項式例子 p(x) = x3 - 3x2 +2x 就變成了：
verifier 提供,,和它們的變換 α,α,α
prover 計算：
verifier 校驗：α
現在我們就可以確保 prover 是用了 verifier 提供的多項式而不是其它值做計算的了，因為別的方法不能夠保持 α-變換。當然如果 verifier 想要確保在 prover 的多項式中排除了 s 的某些次冪，如 j， 他就不提供對應的密文及其變換：，α
與前面的協議相比，我們現在已經有了一個比較健壯的協議。但是儘管已經做了加密，在零知識 性質上也還依然存在一個很明顯的缺陷：即理論上多項式引數 cᵢ 是一個很廣的取值範圍內的值，實際上這個範圍可能很有限（比如前面例子中的 6），這就意味著 verifier 可以在有限範圍的係陣列合中進行暴力破解，最終計算出一個與 prover 的答案相等的結果。比如我們將每個係數的取值範圍定為 100，多項式階數為 2，那麼大概會有 100 萬種不同的組合，這裡可以認為暴力破解只需要少於 100 萬次的迭代。更重要的是，即使在只有一個係數，值為 1 的例子中，安全協議也應該能夠保證其安全。
註解even@安比實驗室:有了 KEA，就可以約束 prover 只能透過用 verifier 提供的加密值去構造證明了。嚴格點講，這裡是用的是 KEA的擴充套件版本，叫做 The q-power Knowledge of Exponent Assumption.
零知識證明因為 verifier 能夠從 prover 傳送的資料中提取未知多項式 p(x) 的知識 ，那麼我們就來看一下這些提供的資料（證明）：，，
它們參與到了下面的驗證： (多項式 p(x) 有根 t(x))α (用了正確形式的多項式)
問題是我們如何選擇證明使得這個校驗依然有效，同時又保證沒有知識能被提取？
前面章節給了我們一個答案：我們可以使用隨機值 δ (delta)來“變換”這些值, 如 (gp )δ。現在，為了提取知識，就必須首先要知道一個不可知的值 δ。並且，這種隨機化在統計學上與隨機值沒有什麼區別。
為了保持這種關係，我們在 verifier 的檢查中驗證一下。等式的每一邊都有一個 prover 提供的值。所以如果我們用同一個δ 來“變換” 每一個值，那麼等式一定保持相等。
具體來講，就是 prover 選擇一個隨機值 δ ，並用它對證明中的值進行求冪δ,δ,αδ
然後提供驗證內容給 verifier：δδδαδ
再合併一下我們就可以看到校驗的等式依然成立：δδδαδ
注意零知識是如何輕而易舉地融入到這個結構中去的，這通常也被稱為"無成本的"零知識。
註解even@安比實驗室:藉助這個”無成本的”技巧，就可以輕鬆實現零知了。但是這裡實現零知識的方法和實際中的Pinocchio協議，還有Groth26 方案略有不同。實際方案中是用乘法乘以δ^(δ·t(s))。
非互動式
到現在為止，我們已經講完了一個互動式的零知識方案。但為什麼我們還需要有非互動式呢？因為互動式證明只對原始的 verifier 有效，其他任何人（其他的 verifier）都不能夠信任這個證明，因為：
verifier 可以和 prover 串通，告訴他密碼引數 s, α，有了這些引數 prover 就可以偽造證明，就像前面 remark 3.1 提到的那樣。
verifier 也可以使用同樣的方法自己偽造證明。
verifier 必須儲存 α and t(s) 直到所有相關證明被驗證完畢，這就帶來了一個可能造成秘密引數洩漏的額外攻擊面。
因而 prover 就需要分別和每個 verifier 做互動來證明一個陳述（就是例子中指的多項式的知識）。
儘管互動式證明也有它的用處，例如一個 prover 只想讓一個特定的 verifier （稱為目標 verifier，更多的資訊參見 [JSI96] ）確信，就不能再重複利用同一個證明去向別人證明這個宣告瞭，但是當一個 prover 想讓眾多的參與者同時或者永久地確信的話，這種方法就很低效了。prover 需要保持一直線上並且對每一個 verifier 執行相同的計算。
因而，我們就需要一個可以被重複使用，公開，可信，又不會被濫用的秘密引數。
我們先來思考一下如何在構造出秘密值 (t(s),α) 構造之後保證它的安全性。我們可以對其進行加密，方式與 verifier 在傳送加密值給 prover 之前對 s 的冪使用的加密方式一致。但是 remark 3.2 中提到，我們使用的同態加密並不支援兩個秘密值相乘，這一點對 t(s) 和 h 的加密值相乘以及 p 和 α 的加密值相乘的驗證都很重要。這個問題適合用Pairing配對操作來解決。
註解even@安比實驗室:這裡非互動的證明協議將對引數加密，但引入了兩個問題：1）同態加密無法對兩個加密值做乘法，那如何驗證加密後的引數呢？2）加密值一旦洩露，協議的信任關係將無法保證，如何確保引數的安全性？
加密值相乘配對操作（雙線性對映）是一個數學結構，表示為函式e(g,g)，它給定一個資料集中的兩個加密的輸入（即ga, gb），可以將他們確定性地對映到另一組不同的輸出資料集上的它們的乘積，即e(ga, gb) = e(g, g)ab：
因為源資料集和輸出資料集（通常被稱為一個 group）是不同的，所以一個配對的結果不能用做其他配對計算的輸入。我們可以將輸出集（也稱為“目標集”）視為“不同的宇宙”。因而我們不能用另一個加密值乘以結果，而且配對這個名稱本身也表明了，我們一次只能將兩個加密值相乘。
註解even@安比實驗室: 換句話說，配對只支援 x * y 這種兩個值的乘法，但不支援三個或以上的值相乘，比如不支援 x * y * z。在某種意義上，這個類似於一個雜湊函式，他將所有可能的輸入值對映到可能的輸出值的集合中的一個元素上，通常情況下這個過程是不可逆的。注意：乍一眼看過去，這個限制可能會阻礙相關功能的實現，但在 zk-SNARK 中這反而是保證安全模式的最重要性質，參見 remark 3.3。配對函式 e(g,g) 可以初步（嚴格來說是不對的）地類比成“交換”每一個輸出的基數和指數的操作，使得基數 g 在交換過程中被修改成了指數的方式，即 ga → ag 。"被轉換"的兩個輸入一起被修改了，這樣原始值 a 和 b 就在同一個指數下相乘了，即：
因而因為基數在“轉換”中被修改了，所以在另一個配對中不能再使用這個結果 (ab)ᵍ （即：e((ab)ᵍ, gᵈ)）構造出想要的加密乘積 abd 了。配對的核心性質可以表示成下面的等式：
嚴格來講一個配對的結果是在目標集的一個不同生成元 g 下對原始值乘積的加密，即 e(gᵃ, gᵇ) = gᵃᵇ。因而它具備同態加密的性質，也就是說我們可以把乘法配對的加密乘積放到一起：注意：配對操作是透過改變橢圓曲線來實現這些性質的，現在我們用的符號 gⁿ 就代表曲線上一個由生成元自相加了 n 次的點，而不是我們前面用到的乘法群生成元。[DBS04] 這個綜述提供了學習配對的出發點。可信任參與方的 Setup有了配對，我們現在就準備去設定安全公開且可複用的引數了。假定一下我們讓一個誠實的參與方來生成秘密值 s 和 α。只有 α 和所有必要的 s 的冪及其對應的 α-變換被加密了，那麼原始資料就必須要被刪除（ i 為 0，1,…,d ）：α，，α
這些引數通常被稱為 common reference string 或者 CRS。CRS 生成後，任何的 prover 和任何的 verifier 都可以使用它來構造非互動式的零知識證明協議。CRS 的最佳化版本將包含目標多項式的加密值 ，儘管這個值並不重要。
把 CRS 分成兩組（ i 為 0，1,…,d ）：proving key（也被稱為 evaluation key）：αverification key：α
只要能夠乘以加密值，verifier 就可以在協議的最後一步驗證多項式了：有了verification key，verifier 就可以處理從 prover 那裡得到的加密多項式的值，，：在加密空間中校驗 p = t·h：校驗多項式的限制：α
信任任意一個參與者
儘管受信任設定很有效率，但眾多 CRS 使用者也必須要相信生成者確實刪除了 α 和 s ，這一點沒有辦法證明（proof of ignorance 是一個正在積極研究的領域 [DK18]），所以這種方法依然是無效的。因而很有必要去最小化或者消除這種信任。否則一個不誠實的參與方就可以構造假證明而不被發現。
一種解決辦法就是由多個參與方使用前面小節中介紹的數學工具來生成一個組合式CRS，這樣這些參與方就都不知道「秘密」了。下面是一個實現方案，我們假設有三個參與者 Alice，Bob 和 Carol ，對應為 A，B 和 C，其中 i為 1, 2, …, d：Alice 選擇隨機數和α，然後公開她的 CRS：，α，αBob 選擇他的隨機數和α，然後透過同態乘法結合 Alice 的 CRS：然後公開兩方 Alice-Bob 的 CRS 結果：Carol 用她的隨機數 和α做同樣的事：然後公開 Alice-Bob-Carol 的 CRS:
這個協議最後我們就獲得了一個混合的 sⁱ 和 α：
除非他們串謀，否則參與者們互相之間並不知道其他人的秘密引數。實際上，一個參與者必須要和其它所有的參與者串謀才能得到 s 和 α，這樣在所有的參與者中只要有一個是誠實的，就沒有辦法偽造證明。
注意：這個過程可以被儘可能多的參與者重複完成。
有一個問題是如何驗證參與者在生成 CRS 時用的隨機數值是一致的，因為攻擊者可以生成多個不同的隨機數 s₁, s₂, …和 α₁, α₂, …，然後代入這些不同的隨機數去執行 s 的不同次冪計算（或提供隨機數作為一個 CRS 的擴充），從而使 CRS 無效或者不可用。
慶幸的是，因為我們可以使用配對來乘以加密值，所以我們就可以從第一個引數開始逐一執行一致性校驗，並且確保了每個引數都源於前一個。我們用 s 的 1 次冪作為標準來校驗每一個其它次冪的值與之是否保持一致例如：
2 次冪：
3 次冪：
，等。我們現在再驗證一下前面步驟中 α-變換後的值是否正確：
例如：
3 次冪：
，等。這裡是“i 值分別為 2，3，…，d” 的縮寫， [d] 是 1, 2, …, d 這個範圍的縮寫形式，在後面的章節這種表示方式更為常見。當我們在驗證每一個參與者秘密引數的一致性時，要注意參與者生成 CRS 的過程並沒有強制後一個參與者（就是我們例子中的 Bob 和 Carol）都要使用前面已經公開的 CRS。因而如果一個攻擊者是鏈上的最後一個參與者，他可以像鏈上的第一個參與者一樣忽略前面的 CRS 隨便構造一個有效的 CRS，這樣他就變成了唯一一個知道秘密 s 和 α 的人。為了解決這個問題，我們可以額外再要求除了第一個以外的每一個參與者去加密然後公開他的引數。例如，Bob 同樣公開了：
這就可以去驗證 Bob 的 CRS 是乘以了 Alice 的引數後正常獲得的，這裡 i 為 1, 2,…, d。
同樣的，Carol 也必須證明她的 CRS 是乘以了 Alice-Bob 的 CRS 後正常獲得的。
這是一個健壯的 CRS 設定模式，它並不完全依賴於單個參與者。事實上，即使其它所有的參與者都串謀了，只要有一個參與者是誠實的，他能夠刪除並且永遠不共享它的秘密引數，這個 CRS 就是有效的。所以在設定 CRS （有時候被稱為儀式 [Wil16]）的時候有越多不相關的參與者參與，偽造證明的可能性就越低。當有相互競爭的參與方參與的時候，就幾乎不可能偽造證明了。這種模式能夠包容其他一些懷疑這種 setup 可識別性的不受信方因為校驗步驟確保了他們不會破壞（這裡也包括很弱的 α 和 s 的使用）最終的 CRS。
註解even@安比實驗室: 現在有一些zkSNARK方案支援可升級的 CRS，任何懷疑CRS的參與方都可以對CRS 進行更新。此外還有一些 zkSNARK方案支援 Universal CRS，用不著對每一個電路進行受信任設定，而是隻需要全域性完成一次即可。除此之外，大量無需 Trusted Setup 的方案正在被充分研究。
多項式的SNARK
我們現在準備來合併這個逐步演化出來的 zk-SNARKOP 協議。為簡潔起見，我們將使用大括號來表示由旁邊的下標填充的一組元素，例如：
表示一組數 s1，s2， …， sd 。我們已經明確目標多項式 t(x) 和 prover 的多項式階數 d：Setup挑選隨機值 s，α計算加密值α和，α生成 proving key：生成 verification key:α，Proving分配係數(即知識)得求多項式代入計算多項式和的值代入α計算變換多項式α的值選擇隨機數 δ構造隨機化的證明verification對映證明 π 為驗證多項式約束：α驗證多項式係數：
Remark 3.3 如果 pairing 的結果有可能在其它類似的乘法協議中被複用，那麼這裡就完全沒有安全性可言了，因為這樣的話 prover 就可以構造α
這樣也可以透過"多項式約束"的檢查：
結論
我們用 zk-SNARK 協議來解決多項式問題的知識，不過這是一個有侷限的例子。因為大家可以說 prover 只要用另外一個有界的多項式去乘以 t(x) 就可以很容易得構造出一個能夠透過測試的多項式 p(x) ，並且這種結構也是有效的。
verifier 知道 prover 有一個有效的多項式，但是並不知道是哪一個。我們可以利用多項式的其他性質新增額外的證明，如:被多個多項式整除，是某個多項式的平方。雖然可能會有一個服務能夠接受，儲存和獎勵所有經過證明的多項式，或者有一個需求，加密計算某種形式的未知多項式。然而若有通用方案就可以支撐無數的應用。
註解even@安比實驗室：總結一下這篇文章中一步一步解決了下面的幾個問題：保證 prover 的證明是按照規則正確構造的 ——> KEA保證知識的零知性 ——> “無成本的”δ 變換可複用證明 ——> 非互動式非互動中如何設定安全公開且可複用的引數 ——> 引數加密，verifier 藉助密碼配對進行驗證保證引數的生成者不洩密 ——> 多方的 Setup至此，一個用來證明多項式知識的完整的 zk-SNARK 協議就構造出來了，不過現在的協議在通用性上依然還有很多限制，後面的文章將繼續介紹如何構造通用的 zk-SNARK。
原文連結https://arxiv.org/pdf/1906.07221.pdfhttps://medium.com/@imolfar/why-and-how-zk-snark-works-2-proving-knowledge-of-a-polynomial-f817760e2805https://medium.com/@imolfar/why-and-how-zk-snark-works-3-non-interactivity-distributed-setup-c0310c0e5d1c參考文獻[Dam91] — Ivan Damgård. “Towards practical public key systems secure against chosen ciphertext attacks”. In:Annual International Cryptology Conference. Springer. 1991, pp. 445–456.[Gro10] — Jens Groth. “Short pairing-based non-interactive zero-knowledge arguments”. In:International Conference on the Theory and Application of Cryptology andInformation Security. Springer. 2010, pp. 321–340.[JSI96] — Markus Jakobsson, Kazue Sako, and Russell Impagliazzo. “Designated verifier proofs and their applications”.In:International Conference on the Theory and Applicationsof Cryptographic Techniques. Springer. 1996, pp. 143–154.[DBS04] — Ratna Dutta, Rana Barua, and Palash Sarkar.Pairing-Based Cryptographic Protocols: A Survey. Cryptology ePrint Archive, Report 2004/064. https://eprint.iacr.org/2004/064. 2004.[DK18] — Apoorvaa Deshpande and Yael Kalai.Proofs of Ignorance and Applicationsto 2-Message Witness Hiding. Cryptology ePrint Archive, Report 2018/896. https://eprint.iacr.org/2018/896. 2018.[Wil16] — Zooko Wilcox.The Design of the Ceremony. 2016. url: https://z.cash/blog/the-design-of-the-ceremony/
