zkSNARK的可能性令人印象深刻，您可以驗(yàn)證計(jì)算的正確性，而無需執(zhí)行它們，您甚至不會知道執(zhí)行了什么 - 只是它正確地完成了。 不幸的是，大多數(shù)zkSNARKs的解釋都是在某種程度上揮手致意，因此他們?nèi)匀皇恰吧衿娴摹?#xff0c;這表明只有最開明的人才能真正理解他們是如何以及為什么（以及如果？）他們的工作。 現(xiàn)實(shí)情況是，zkSNARK可以簡化為四種簡單的技術(shù)，本博文旨在解釋它們。 任何懂得RSA密碼系統(tǒng)工作原理的人，都應(yīng)該對目前使用的zkSNARK有很好的理解。 讓我們看看它是否會實(shí)現(xiàn)其目標(biāo)！

pdf版本

作為一個非常簡短的總結(jié)，zkSNARKs目前已經(jīng)實(shí)現(xiàn)，有4個主要成分（不用擔(dān)心，我們將在后面的章節(jié)中解釋所有術(shù)語）：

A）編碼為多項(xiàng)式問題

要檢查的程序被編譯成多項(xiàng)式的二次方程：t（x）h（x）= w（x）v（x），其中當(dāng)且僅當(dāng)程序正確計(jì)算時等式成立。 證明者想說服驗(yàn)證者這種平等。

B）通過隨機(jī)抽樣的簡潔性

驗(yàn)證者選擇一個秘密評估點(diǎn)s來減少乘以多項(xiàng)式和驗(yàn)證多項(xiàng)式函數(shù)等式的問題到簡單的乘法和等式檢查數(shù)字：t（s）h（s）= w（s）v（s）

這極大地減少了驗(yàn)證尺寸和驗(yàn)證時間。

C）同態(tài)編碼/加密

使用編碼/加密函數(shù)E，它具有一些同態(tài)特性（但不完全同態(tài)，但還不實(shí)際）。 這允許證明者在不知道s的情況下計(jì)算E（t（s）），E（h（s）），E（w（s）），E（v（s）），她只知道E其他有用的加密值。

D）零知識

證明者通過與數(shù)值相乘來置換值E（t（s）），E（h（s）），E（w（s）），E（v（s）），以便驗(yàn)證者仍然可以檢查他們的正確結(jié)構(gòu)而不知道實(shí)際的編碼值。

非常粗略的想法是檢查t（s）h（s）= w（s）v（s）與檢查t（s）h（s）k = w（s）v秘密數(shù)k（不為零），區(qū)別在于如果僅發(fā)送數(shù)字（t（s）h（s）k）和（w（s）v（s）k），則不可能推導(dǎo)出t（s）h（s）或w（s）v（s）。

這是揮手致意的部分，以便您可以了解zkSNARK的本質(zhì)，現(xiàn)在我們將詳細(xì)介紹。

RSA和零知識證明

讓我們先快速提醒一下RSA的工作方式，留下一些挑剔的細(xì)節(jié)。 請記住，我們經(jīng)常使用模數(shù)來代替其他數(shù)字，而不是完整整數(shù)。 這里的符號是“a +b≡c（mod n）”，意思是“（a + b）％n = c％n”。 請注意，“（mod n）”部分不適用于右側(cè)的“c”，但實(shí)際上適用于“≡”和所有其他的“≡”。 這使得它很難閱讀，但我保證謹(jǐn)慎使用它。 現(xiàn)在回到RSA：

證明者提出以下數(shù)字：

• p，q：兩個隨機(jī)秘密素?cái)?shù)
• n：= pq
• d：1 <d <n - 1的隨機(jī)數(shù)
• e：一個數(shù)，使得de≡≡（mod（p-1）（q-1））。

公鑰是（e，n），私鑰是d。 素?cái)?shù)p和q可以丟棄，但不應(yīng)該顯示。

消息m通過加密

• E（m）：= m ^e ％n

和c = E（m）通過解密

• D（c）：= c ^d ％n。

由于c d≡（m ^e ％n）d≡m ^ed （mod n）和m的指數(shù)中的乘法表現(xiàn)如同模（p-1）（q-1）中的乘法一樣，我們得到m ed≡m（mod n）。 此外，RSA的安全性依賴于n不能有效地進(jìn)行因式分解，因此d不能從e計(jì)算（如果我們知道p和q，這很容易）。

RSA的一個顯著特點(diǎn)是它是乘法同態(tài)的 。 一般而言，如果可以交換順序而不影響結(jié)果，則兩個操作是同態(tài)的。 在同態(tài)加密的情況下，這是您可以對加密數(shù)據(jù)執(zhí)行計(jì)算的屬性。 完全同態(tài)加密 ，存在但是不實(shí)用的東西，將允許評估加密數(shù)據(jù)上的任意程序。 在這里，對于RSA，我們只是在談?wù)摻M乘法。 更正式地說：E（x）E（y）≡x ^e y e≡（xy）e≡E（xy）（mod n）或者用文字表示：兩條消息的加密乘積等于消息的產(chǎn)品。

這種同態(tài)性已經(jīng)允許某種乘法的零知識證明：證明者知道一些秘密數(shù)字x和y并計(jì)算它們的乘積，但只發(fā)送加密版本a = E（x），b = E（y）和c = E（xy）給驗(yàn)證者。 驗(yàn)證者現(xiàn)在檢查（ab）％n≡c％n并且驗(yàn)證者學(xué)習(xí)的唯一東西是產(chǎn)品的加密版本以及產(chǎn)品是否正確計(jì)算，但她既不知道這兩個因素，也不知道實(shí)際產(chǎn)品。 如果您通過添加替換產(chǎn)品，這已經(jīng)進(jìn)入?yún)^(qū)塊鏈的方向，主要操作是添加余額。

交互式驗(yàn)證

關(guān)于零知識方面，讓我們現(xiàn)在關(guān)注zkSNARK的另一個主要特點(diǎn)，即簡潔性。 正如你將會看到的那樣，簡潔性是zkSNARKs中非常重要的部分，因?yàn)榱阒R部分將由于允許有限形式的同態(tài)編碼的某種編碼而被“免費(fèi)”給出。

SNARKs是簡潔的非交互式知識論的簡稱。 在這種所謂的交互協(xié)議的一般設(shè)置中，存在證明者和驗(yàn)證者 ，證明者想通過交換消息來說服驗(yàn)證者說明一個陳述（例如f（x）= y）。 通常所需的屬性是沒有證明者可以說服驗(yàn)證者說明一個錯誤的語句（ 健全性 ），并且證明者有一定的策略來說服驗(yàn)證者說明任何真實(shí)的陳述（ 完整性 ）。 首字母縮略詞的各個部分具有以下含義：

• 簡潔：與實(shí)際計(jì)算的長度相比，消息的大小很小
• 非互動性：沒有或只有很少的互動。 對于zkSNARK，通常會有一個設(shè)置階段，然后從證明者到驗(yàn)證者發(fā)送一條消息。 此外，SNARKs通常具有所謂的“公開驗(yàn)證者”屬性，意味著任何人都可以驗(yàn)證而無需重新進(jìn)行交互，這對區(qū)塊鏈很重要。
• 參數(shù)：驗(yàn)證者僅受計(jì)算限制的證明者的保護(hù)。 具有足夠計(jì)算能力的證明者可以創(chuàng)建關(guān)于錯誤陳述的證明/論據(jù)（請注意，具有足夠的計(jì)算能力，任何公鑰加密都可以被破壞）。 這也被稱為“計(jì)算健全性”，而不是“完美健全性”。
• 知識：證明者不可能在不知道某個所謂的證人的情況下構(gòu)造一個證明/論證（例如，她想從中度過的地址，哈希函數(shù)的原像或者某個默克爾樹的路徑節(jié)點(diǎn)）。

如果添加零知識前綴，則還需要該屬性（粗略地說）在交互期間，驗(yàn)證者除了語句的有效性之外什么都不學(xué)習(xí)。 驗(yàn)證者尤其不了解證人字符串 - 我們稍后會看到那是什么。

作為一個例子，讓我們考慮下面的事務(wù)驗(yàn)證計(jì)算：當(dāng)且僅當(dāng)σ1和σ2是根哈希值時，f（σ1，σ2，s，r，v，p _s ，p _r ，v）= 1 Merkle-trees（前置狀態(tài)和后置狀態(tài)），s和r是發(fā)送者和接收者賬戶，p是Merkle樹證明，證明s的平衡在σ1中至少為v，如果v從s的平衡移動到r的平衡，他們就散列到σ2而不是σ1。

如果所有輸入已知，驗(yàn)證f的計(jì)算相對容易。 因此，我們可以把f變成zkSNARK，其中只有σ1和σ2是公知的，（s，r，v，p _s ，p _r ，v）是證人字符串。 零知識屬性現(xiàn)在導(dǎo)致驗(yàn)證者能夠檢查證明者是否知道某個證人將根哈希從σ1變?yōu)棣?，這樣做并不違反任何正確事務(wù)的要求，但她不知道誰發(fā)給誰多少錢。

零知識的正式定義（仍然省略一些細(xì)節(jié)）是有一個模擬器 ，它也生成了安裝字符串，但不知道秘密證人，可以與驗(yàn)證器交互 - 但外部觀察者不能將這種互動與真正的證明者的互動區(qū)分開來。

NP和復(fù)雜性 - 理論上的減少

為了看到zkSNARKs可以用于哪些問題和計(jì)算，我們必須從復(fù)雜性理論中定義一些概念。 如果你不關(guān)心什么是“證人”，在“閱讀”零知識證明之后你不會知道什么，或者為什么只有針對關(guān)于多項(xiàng)式的特定問題才有zkSNARK，那么你可以跳過本節(jié)。

P和NP

首先，讓我們限制只輸出0或1的函數(shù)，并調(diào)用這些函數(shù)問題 。 因?yàn)槟憧梢詥为?dú)查詢每一個較長結(jié)果的位，所以這不是一個真正的限制，但它使理論變得更容易。 現(xiàn)在我們要測量解決給定問題的“復(fù)雜”（計(jì)算函數(shù)）。 對于數(shù)學(xué)函數(shù)f的特定機(jī)器實(shí)現(xiàn)M，我們總是可以計(jì)算在特定輸入x上計(jì)算f所需的步驟數(shù) - 這稱為M on x的運(yùn)行時間 。 到底什么是“步驟”，在這方面并不太重要。 由于程序?qū)τ谳^大的輸入通常需要更長的時間，因此此運(yùn)行時間總是以輸入的大小或長度（以位數(shù)為單位）進(jìn)行度量。 這就是例如“n ²算法”的概念來自哪里 - 它是一個算法，在大小為n的輸入上最多需要n ^2個步驟。 “算法”和“程序”的概念在這里大致相同。

對于某些k，運(yùn)行時最多為n ^k的程序也稱為“多項(xiàng)式時間程序”。

復(fù)雜性理論中的兩類主要問題是P和NP：

• P是具有多項(xiàng)式時間程序的問題類別L.

盡管指數(shù)k對于某些問題可能相當(dāng)大，但P被認(rèn)為是“可行”問題的類別，事實(shí)上，對于非人為問題，k通常不大于4.驗(yàn)證比特幣交易在P中是個問題，正如評估一個多項(xiàng)式（并將該值限制為0或1）。 粗略地說，如果你只需要計(jì)算一些值而不是“搜索”某些東西，那么問題幾乎總是在P中。如果你必須搜索某些東西，那么你最終會在一個名為NP的類中結(jié)束。

NP類

對于NP中的所有問題，有zkSNARKs，實(shí)際上，今天存在的實(shí)用的zkSNARKs可以以通用的方式應(yīng)用于NP中的所有問題。 目前尚不清楚在NP之外是否有任何問題存在zkSNARK。

NP中的所有問題總是具有一定的結(jié)構(gòu)，源于NP的定義：

• NP是具有多項(xiàng)式時間程序V的問題類別L，其可以用于驗(yàn)證事實(shí)上給定多項(xiàng)式大小的所謂證人的事實(shí)。 更正式地說：
  L（x）= 1當(dāng)且僅當(dāng)存在某個多項(xiàng)式大小的字符串w（稱為見證）時 ，V（x，w）= 1

作為NP中問題的一個例子，讓我們考慮布爾公式可滿足性（SAT）的問題。 為此，我們使用歸納定義來定義一個布爾公式：

• 任何變量x ₁ ，x ₂ ，x ₃ ，...都是一個布爾公式（我們也使用任何其他字符來表示變量
• 如果f是布爾公式，則?f是布爾公式（否定）
• 如果f和g是布爾公式，則（f ^ g）和（f∨g）是布爾公式（連接/和，或/或）。

字符串“（（x 1∧x ₂ ）∧?x2）”將是一個布爾公式。

如果有一種方法可以將真值分配給變量，以便公式計(jì)算為真（其中，真假，真假真，真假假等等，常規(guī)規(guī)則），則布爾公式是可滿足的 。 可滿足性問題SAT是所有可滿足的布爾公式的集合。

• 如果f是一個可滿足的布爾公式，則SAT（f）：= 1，否則為0

上面的例子“（（x 1∧x ₂ ）∧?x ₂ ）”是不可滿足的，因此不在SAT中。 給定公式的見證是它令人滿意的分配，并驗(yàn)證變量賦值是令人滿意的是一個可以在多項(xiàng)式時間內(nèi)求解的任務(wù)。

P = NP？

如果將NP的定義限制為見證長度為零的字符串，則可以捕獲與P中相同的問題。因此，P中的每個問題也都在NP中。 復(fù)雜性理論研究的主要任務(wù)之一是顯示這兩類實(shí)際上是不同的 - NP中存在一個問題，它不在P中。看起來很明顯，情況就是這樣，但如果你能正式證明它，你可以贏得100萬美元 。 哦，只是作為一個便箋，如果你可以證明相反的話，那么P和NP是平等的，除了贏得這個數(shù)額之外，加密貨幣很有可能從一天到下一天不復(fù)存在。 原因在于，找到工作難題證明的解決方案，散列函數(shù)中的沖突或?qū)?yīng)于地址的私鑰會更容易。 這些都是NP中的問題，既然你證明了P = NP，那么他們必須有一個多項(xiàng)式時間程序。 但是這篇文章并不是為了嚇倒你，大多數(shù)研究人員都認(rèn)為P和NP是不相等的。

NP完全性

讓我們回到SAT。 這個看似簡單的問題的有趣屬性是它不僅存在于NP中，而且也是NP完全的。 這里的“complete”一詞與“Turing-complete”完全相同。 這意味著它是NP中最難的問題之一，但更重要的是 - NP-complete的定義 - 對NP中任何問題的輸入都可以轉(zhuǎn)化為SAT的等價輸入，其意義如下：

對于任何NP問題L，都有一個所謂的約化函數(shù) f，它可以在多項(xiàng)式時間內(nèi)計(jì)算，這樣：

• L（x）= SAT（f（x））

這種簡化函數(shù)可以看作是一種編譯器：它將源代碼編寫成某種編程語言，然后轉(zhuǎn)換成另一種編程語言的等價程序，這種編程語言通常是一種具有某種語義行為的機(jī)器語言。 由于SAT是NP完全的，所以NP的任何可能的問題都存在這種減少，包括檢查例如比特幣交易在給定適當(dāng)?shù)膲K散列情況下是否有效的問題。 有一個將事務(wù)轉(zhuǎn)換為布爾公式的歸約函數(shù)，當(dāng)且僅當(dāng)事務(wù)有效時，公式才可滿足。

縮小例子

為了看到這樣的減少，讓我們考慮評估多項(xiàng)式的??問題。 首先，讓我們定義一個多項(xiàng)式（類似于布爾公式）作為由整型常量，變量，加法，減法，乘法和（正確平衡）括號組成的表達(dá)式。 現(xiàn)在我們要考慮的問題是

• PolyZero（f）：= 1如果f是一個多項(xiàng)式，其中的變量取自集合{0,1}

我們現(xiàn)在將構(gòu)建從SAT到PolyZero的縮減，從而表明PolyZero也是NP完全的（檢查它是否在NP中作為練習(xí)）。

在布爾公式的結(jié)構(gòu)元素上定義簡化函數(shù)r就足夠了。 這個想法是，對于任何布爾公式f，值r（f）是具有相同數(shù)量變量的多項(xiàng)式，當(dāng)且僅當(dāng)r（f）（a ₁ ，...，a _k ）為零，其中true對應(yīng)于1，false對應(yīng)于0，并且r（f）僅對來自{0,1}的變量采用值0或1：

• r（x _i ）：=（1-x _i ）
• r（?f）：=（1-r（f））
• r（（f ^ g））：=（1-（1-r（f））（1-r（g）））
• r（（f∨g））：= r（f）r（g）

人們可能假設(shè)r（（f ^ g））將被定義為r（f）+ r（g），但是這將取多元式的值超出{0,1}集合。

使用r，公式（（x∧y）∨?x）被轉(zhuǎn)化為（1-（1-（1-x））（1-（1-y））（1-（1-x）），

請注意，r的每個替換規(guī)則都滿足上述目標(biāo)，因此r正確地執(zhí)行了減少操作：

• SAT（f）= PolyZero（r（f））或f滿足當(dāng)且僅當(dāng)r（f）在{0,1}

見證保存

從這個例子中，你可以看到，約簡函數(shù)只定義了如何翻譯輸入，但當(dāng)你仔細(xì)觀察它時（或者讀取它證明它有效的減少），你也會看到一種方法來轉(zhuǎn)換有效的證人與輸入一起。 在我們的例子中，我們只定義了如何將公式轉(zhuǎn)換為多項(xiàng)式，但是通過證明我們解釋了如何轉(zhuǎn)換證人和令人滿意的分配。 交易不需要證人的同時轉(zhuǎn)換，但通常也是這樣做的。 這對于zkSNARK來說非常重要，因?yàn)樽C明者的唯一任務(wù)是說服驗(yàn)證者證明這樣的證人存在，而不透露關(guān)于證人的信息。

二次跨度程序

在前一節(jié)中，我們看到了NP內(nèi)部的計(jì)算問題如何相互減少，特別是存在NP完全問題，這些問題基本上只是NP中所有其他問題的重新解釋 - 包括交易驗(yàn)證問題。 這使得我們可以很容易地找到NP中所有問題的通用zkSNARK：我們只是選擇一個合適的NP完全問題。 因此，如果我們想要展示如何使用zkSNARK來驗(yàn)證事務(wù)，那么足以展示如何針對某個NP完全的問題進(jìn)行處理，并且可能在理論上更容易處理。

本文和下一節(jié)基于GGPR12文件（鏈接的技術(shù)報(bào)告比期刊論文更多），作者發(fā)現(xiàn)稱為二次跨度程序（QSP）的問題特別適合于zkSNARK。 二次跨度程序由一組多項(xiàng)式組成，其任務(wù)是找出那些是另一個給定多項(xiàng)式的倍數(shù)的線性組合。 此外，輸入字符串的各個位限制您允許使用的多項(xiàng)式。 詳細(xì)地說（一般的QSP比較寬松一些，但我們已經(jīng)定義了強(qiáng)壯的版本，因?yàn)樗院髸皇褂?#xff09;：

長度為n的輸入的字段F上的QSP由下式組成

• 在該域F上的一組多項(xiàng)式v ₀ ，...，v _m ，w ₀ ，...，w _m ，
• F上的多項(xiàng)式t（目標(biāo)多項(xiàng)式），
• 一個內(nèi)射函數(shù)f：{（i，j）| 1≤i≤n，j∈{0,1}}→{1，...，m}

這里的任務(wù)大致是將多項(xiàng)式乘以因子并將它們相加，使得總和（稱為線性組合 ）是t的倍數(shù)。 對于每個二進(jìn)制輸入字符串u，函數(shù)f限制可以使用的多項(xiàng)式，或更具體地說，它們在線性組合中的因子。 對于正式的：

當(dāng)且僅當(dāng)存在來自字段F的元組a =（a ₁ ，...，a _m ），b =（b ₁ ，...，b _m ）時，輸入u被QSP 接受 （驗(yàn)證）

• （如果k = f（i，u [i]），對于某個i，（u [i]是u的第i個比特）
• 一個_k ，b _k = 0，如果k = f（i，1 - u [i]）
• 目標(biāo)多項(xiàng)式t除以v _a w _b其中v _a = v ₀ + a ₁ v ₀ + ... + a _m v _m ，w _b = w ₀ + b ₁ w ₀ + ... + b _m w _m 。

請注意，如果2n小于m，則在選擇元組a和b時仍有一些自由。 這意味著QSP僅適用于輸入達(dá)到一定大小的情況 - 這個問題通過使用非均勻復(fù)雜性來解決，這是我們現(xiàn)在不會涉及的一個主題，讓我們注意到，對于輸入通常很小的密碼學(xué)來說，它非常適用。

作為布爾公式的可滿足性的類比，可以將因子a ₁ ，...，a _m ，b ₁ ，...，b _m看作變量的分配，或者一般情況下可以看到NP證人。 為了看到QSP在NP中，注意所有驗(yàn)證者必須做的事情（一旦她知道了因素）就是檢查多項(xiàng)式t除以v _a w _b ，這是一個多項(xiàng)式時間問題。

我們不會在此討論從泛型計(jì)算或電路到QSP的減少，因?yàn)樗鼰o助于理解一般概念，所以您必須相信我QSP是NP-complete（或者對于一些非統(tǒng)一的類似NP /聚）。 在實(shí)踐中，這種減少是實(shí)際的“工程”部分 - 它必須以一種聰明的方式完成，使得產(chǎn)生的QSP將盡可能小，并且還具有一些其他好的特征。

我們已經(jīng)可以看到的關(guān)于QSP的一件事是如何更有效地驗(yàn)證它們：驗(yàn)證任務(wù)包括檢查一個多項(xiàng)式是否劃分另一個多項(xiàng)式。 這可以通過證明者提供另一個多項(xiàng)式h來促成，使得將任務(wù)轉(zhuǎn)變?yōu)闄z查多項(xiàng)式身份或?qū)⑵洳煌刂脫Q為檢查th-v _a w _b = 0，即檢查確定多項(xiàng)式是零多項(xiàng)式。 這看起來相當(dāng)容易，但我們稍后將使用的多項(xiàng)式相當(dāng)大（程度大約是原始電路中柵極數(shù)的100倍），因此乘以兩個多項(xiàng)式不是一件容易的事。

因此，驗(yàn)證者不是實(shí)際計(jì)算v _a ，w _b及其乘積，而是選擇一個秘密隨機(jī)點(diǎn)s（這個點(diǎn)是zCash的“有毒廢物”的一部分），計(jì)算數(shù)字t（s），v _k （s）和w _k （s）對于所有的k和它們，v _a （s）和w _b （s）并且僅檢查t（s）h（s）= v _a （s）w _b （s）。 因此，一堆多項(xiàng)式加法，與標(biāo)量和多項(xiàng)式乘積的乘法被簡化為場乘法和加法。

只在一個點(diǎn)上檢查一個多項(xiàng)式身份，而不是在所有的點(diǎn)上當(dāng)然會降低安全性，但是證明者可以作弊的唯一方法就是如果她不是零多項(xiàng)式，那就是如果她設(shè)法達(dá)到零的該多項(xiàng)式，但是因?yàn)樗恢纒和0的個數(shù)（多項(xiàng)式的階數(shù)）與s（場元素的個數(shù)）的可能性相比是微小的，所以這在實(shí)踐中是非常安全的。

詳細(xì)zkSNARK

我們現(xiàn)在詳細(xì)描述用于QSP的zkSNARK。 它始于每個QSP必須執(zhí)行的設(shè)置階段。 在zCash中，電路（交易驗(yàn)證器）是固定的，因此QSP的多項(xiàng)式是固定的，它允許設(shè)置只執(zhí)行一次，并重新用于所有交易，這只會改變輸入u。 對于生成公共參考字符串 （CRS）的設(shè)置，驗(yàn)證者選擇一個隨機(jī)和秘密字段元素s并在該點(diǎn)加密多項(xiàng)式的值。 驗(yàn)證者使用一些特定的加密E并在CRS中發(fā)布E（v _k （s））和E（w _k （s））。 CRS還包含其他幾個值，這使得驗(yàn)證更有效，并且還增加了零知識屬性。 在那里使用的加密E具有一定的同態(tài)特性，這允許證明者在沒有實(shí)際知道v _k （s）的情況下計(jì)算E（v（s））。

如何簡潔地和零知識地評估多項(xiàng)式

讓我們先看一個更簡單的情況，即只是在秘密點(diǎn)對多項(xiàng)式進(jìn)行加密評估，而不是完整的QSP問題。

為此，我們修復(fù)一個組（這里通常選擇一個橢圓曲線）和一個生成器g。 請記住，如果有一個數(shù)字n（組順序），使得列表g ⁰ ，g ¹ ，g ² ，...，g ^n-1包含組中的所有元素，則稱該組為元素。 加密僅僅是E（x）：= g ^x 。 現(xiàn)在驗(yàn)證者選擇一個秘密字段元素并發(fā)布（作為CRS的一部分）

• E（s ⁰ ），E（s ¹ ），...，E（s ^d ） - d是所有多項(xiàng)式的最大度數(shù)

之后，s可以（并且必須）被遺忘。 這正是zCash所說的有毒廢物，因?yàn)槿绻腥四軌蚧謴?fù)這個以及稍后選擇的其他秘密值，他們可以通過在多項(xiàng)式中找到零來任意欺騙證據(jù)。

使用這些值，證明者可以在不知道s的情況下計(jì)算任意多項(xiàng)式f的E（f（s））：假設(shè)我們的多項(xiàng)式是f（x）= 4x2 + 2x + 4，并且我們想要計(jì)算E（f（s））那么我們得到E（f（s））= E（4s ² + 2s + 4）= g ^{4s ^ 2 + 2s + 4} = E（s ² ）4E（s ¹ ）2E（s ⁰ ）可以在不知道s的情況下從已發(fā)布的CRS中計(jì)算出來。

這里唯一的問題是，由于s被破壞，驗(yàn)證者無法檢查證明者是否正確評估了多項(xiàng)式。 為此，我們還選擇另一個秘密字段元素α，并發(fā)布以下“移位”值：

• E（αs0），E（αs1），...，E（αsd）

與s一樣，在設(shè)置階段之后，值α也被破壞，并且證明者和驗(yàn)證者都不知道。 使用這些加密值，證明者可以類似地計(jì)算E（αf（s）），在我們的例子中，這是E（4s ² +2αs+4α）= E（αs2） ⁴ E（αs1）2E（αs0 ） ⁴ 。 因此，證明者發(fā)布A：= E（f（s））和B：= E（αf（s）），并且驗(yàn)證者必須檢查這些值是否匹配。 她通過使用另一種主要成分來做到這一點(diǎn)：所謂的配對功能 e。 橢圓曲線和配對函數(shù)必須一起選擇，以便以下屬性適用于所有x，y：

• e（g ^x ，g ^y ）= e（g，g） ^xy

使用這個配對函數(shù)，驗(yàn)證者檢查e（A， ^gα ）= e（B，g） - 注意^gα是驗(yàn)證者已知的，因?yàn)樗荂RS的一部分，為E（αs0）。 為了證明如果證明者沒有作弊，這個檢查是有效的，讓我們看看以下的等式：

e（g，g）= e（g ^f（s） ， ^gα ）= e（g，g） ^αf（s）

e（B，g）= e（ ^gαf（s） ，g）= e（g，g） ^αf（s）

然而，更重要的部分是證明者是否能夠以某種方式提出滿足檢查e（A， ^gα ）= e（B，g）但不是E（f（s））的值A(chǔ)，B和E（αf（s）））。 這個問題的答案是“我們不希望”。 嚴(yán)重的是，這被稱為“指數(shù)假設(shè)的d-power知識”，并且作弊證明人是否可以做這樣的事情是未知的。 這個假設(shè)是為證明其他公鑰加密方案的安全性而做出的類似假設(shè)的延伸，并且這些假設(shè)同樣未知為真或假。

實(shí)際上，上述協(xié)議實(shí)際上并不允許驗(yàn)證者檢查證明者是否評估了多項(xiàng)式f（x）= 4x2 + 2x + 4，驗(yàn)證者只能檢查證明者是否在點(diǎn)s處評估了一些多項(xiàng)式。 QSP的zkSNARK將包含另一個值，允許驗(yàn)證者檢查證明者的確評估了正確的多項(xiàng)式。

這個例子表明驗(yàn)證者不需要評估完整的多項(xiàng)式來證實(shí)這一點(diǎn)，只需要評估配對函數(shù)即可。 在下一步中，我們將添加零知識部分，以便驗(yàn)證者不能重構(gòu)關(guān)于f（s）的任何內(nèi)容，甚至不能重建加密值（E（f（s）））。

為此，證明者選擇一個隨機(jī)δ而不是A：= E（f（s））和B：= E（αf（s））），她通過A'：= E（δ+ f（s） ））和B：= E（α（δ+ f（s））））。 如果我們假設(shè)加密不能被破壞，那么零知識屬性就非常明顯。 我們現(xiàn)在必須檢查兩件事情：1.證明者實(shí)際上可以計(jì)算這些值，并且2.驗(yàn)證者的檢查仍然是真實(shí)的。

對于1.，請注意，A'= E（δ+ f（s））= ^{gδ+ f（s）} = ^gδgf（s） = E（δ）E（f（s））= E ）A和類似地，B'= E（α（δ+ f（s））））= E（αδ+αf（s）））= ^{gαδ+αf（s）} = ^{gαδgα F（S）}

= E（α） ^δE （αf（s））= E（α） ^δB 。

對于2.，注意驗(yàn)證者檢查的唯一事情是她接收到的值A(chǔ)和B對于某個值a滿足等式A = E（a）和B = E（αa），這對于a來說顯然是這種情況=δ+ f（s），這是a = f（s）的情況。

好的，所以我們現(xiàn)在知道一些關(guān)于證明者如何在加密的秘密點(diǎn)上計(jì)算多項(xiàng)式的加密值而沒有驗(yàn)證者知道關(guān)于該值的任何事情的信息。 現(xiàn)在讓我們將其應(yīng)用于QSP問題。

針對QSP問題的SNARK

請記住，在QSP中，給定多項(xiàng)式v ₀ ，...，v _m ，w ₀ ，...，w _m，目標(biāo)多項(xiàng)式t（度至多為d）和二進(jìn)制輸入串u。 證明者找到一個₁ ，...，a _m， b ₁ ，...，b _m （根據(jù)u有些限制）和一個多項(xiàng)式h

• th =（v ₀ + a ₁ v ₁ + ... + a _m v _m ）（w ₀ + b ₁ w ₁ + ... + b _m w _m ）。

在上一節(jié)中，我們已經(jīng)解釋了如何設(shè)置公共參考字符串（CRS）。 我們選擇秘密數(shù)字s和α并發(fā)布

• E（s ⁰ ），E（s ¹ ），...，E（s ^d ）和E（αs0），E（αs1），...，E（αsd）

由于我們沒有單一的多項(xiàng)式，而是針對問題固定的多項(xiàng)式集合，所以我們也立即發(fā)布評估的多項(xiàng)式：

• E（t（s）），E（αt（s）），
• E（v ₀ （s）），...，E（v _m （s）），E（αv ₀ （s）），...，E（αv _m （s）），
• E（w ₀ （s）），...，E（w _m （s）），E（αw ₀ （s）），...，E（αw _m （s）），

我們需要更多的秘密數(shù)βv，βw，γ（它們將用于驗(yàn)證那些多項(xiàng)式是否被評估過，而不是某些任意多項(xiàng)式）并發(fā)布

• E（γ），E（βvγ），E（βwγ），
• E（βv _v1 （s）），...，E（βv v _m （s））
• E（βw _w1 （s）），...，E（βw w _m （s））
• E（βv t（s）），E（βw t（s））

這是完整的公共參考字符串。 在實(shí)際的實(shí)現(xiàn)中，CRS的某些元素是不需要的，但這會使表示變得復(fù)雜。

現(xiàn)在證明者做什么？ 她使用上面解釋的減少來找出多項(xiàng)式h和值a ₁ ，...，a _m， b ₁ ，...，b _m 。 在這里，使用證人保留約簡是很重要的（見上文），因?yàn)橹挥羞@樣，值a ₁ ，...，a _m， b ₁ ，...，b _m才能與約簡一起計(jì)算，并且很難找到除此以外。 為了描述證明者向驗(yàn)證者發(fā)送的證明作為證明，我們必須回到QSP的定義。

有一個內(nèi)射函數(shù)f：{（i，j）| 1≤i≤n，j∈{0,1}}→{1，...，m}，這限制了a ₁ ，...，a _m， b ₁ ，...，b _m的值 。 由于m相對較大，因此對于任何輸入都有不會出現(xiàn)在f的輸出中的數(shù)字。 這些指數(shù)不受限制，所以讓我們稱他們?yōu)?sub>自由并且定義v _free （x）=Σk a _k v _k （x）其中k在所有指數(shù)中都是_{免費(fèi)的} 。 對于w（x）= b ₁ w ₁ （x）+ ... + b _m w _m （x），證明現(xiàn)在由

• V _free ：= E（v _free （s）），W：= E（w（s）），H：= E（h（s）），
• V'free：= E（αv _free （s）），W'：= E（αw（s）），H'：= E（αh（s）），
• Y：= E（βv _vfree （s）+βw w（s）））

最后一部分用于檢查是否使用了正確的多項(xiàng)式（這是我們在另一個例子中未覆蓋的部分）。 請注意，所有這些加密值都可以由證明者只知道CRS而生成。

驗(yàn)證者的任務(wù)如下：

由于_k的值（其中k不是“自由”的指數(shù)）可以直接從輸入u計(jì)算出來（這也是驗(yàn)證者已知的，這是要驗(yàn)證的），驗(yàn)證者可以計(jì)算缺失部分v的全部金額：

• è（V _中（S））= E（Σ _?一個_? v _?（S）），其中k的范圍在所有索引不是在我_釋放。

由此，驗(yàn)證者現(xiàn)在使用配對函數(shù)e確認(rèn)以下等式（不要害怕）：

E（V ' _免費(fèi)，G）= E（V _免費(fèi)，克^α）中，e（W'，E（1））= E（W，E（α））中，e（H”，E（1））= e（H，E（α））

E（E（γ）中，Y）= E（E（β _v γ），V _免費(fèi)）E（E（β _瓦特 γ），W）

è（E（V ₀（S））電子（V _中（S））V _免費(fèi)，E（W ₀（S））W）= E（H，E（T（S）））

要掌握這里的一般概念，您必須明白，配對函數(shù)允許我們對加密值進(jìn)行一些有限的計(jì)算：我們可以進(jìn)行任意的加法，但只是一次乘法。 此加法來自加密本身已經(jīng)加性同態(tài)的事實(shí)，并且單一乘法是由配對函數(shù)具有的兩個參數(shù)實(shí)現(xiàn)的。 因此，e（W'，E（1））= e（W，E（α））在加密空間中基本上將W'乘以1，并將其與加密空間中乘以α的W進(jìn)行比較。 如果您查看W和W'的值應(yīng)該是 - E（w（s））和E（αw（s）），則檢查證明者是否提供了正確的證據(jù)。

如果您還記得關(guān)于在秘密點(diǎn)評估多項(xiàng)式的??部分，這三個首先檢查基本上驗(yàn)證了證明者確實(shí)評估了由CRS中的部分構(gòu)建的多項(xiàng)式。 第二項(xiàng)用于驗(yàn)證證明者使用正確的多項(xiàng)式v和w，而不僅僅是一些任意的。 其背后的思想是證明者無法通過某種其他方式計(jì)算加密組合E（βv _vfree （s）+βw w（s））），而不是從E（v _free （s） ）和E（w（s））。 原因是值βv不是孤立的CRS的一部分，而是僅與數(shù)值v _k （s）結(jié)合，并且βw僅與多項(xiàng)式w _k （s）結(jié)合而已知。 “混合”他們的唯一方法是通過同樣加密的γ。

假設(shè)證明者提供了正確的證據(jù)，讓我們檢查平等是否成立。 左側(cè)和右側(cè)分別是

• e（E（γ），Y）= e（E（γ），E（βv _vfree （s）+βw w（s）））= e（g，g） ^{γ（βv v _free ）+βw _w （s））}
• e（E（βvγ），V _free ）e（E（βwγ），W）= e（E（βvγ），E（v _free （s）））e （g，g） ^（ e，w（s）））= e（g，g） ^{（βvγ）v _free （s）} e ^{βv _vfree （s）+βw w（s））}

（s）+ a ₁ v ₁ （s）+ ... + a _m v _m （s））（w ₀ （s）+ b ₁ w ₁ （s）+ ... + b _m w（s））= h（s）t（s），這是QSP問題的主要條件。 注意，對加密值的乘法轉(zhuǎn)換為對未加密值的加法，因?yàn)镋（x）E（y）= g ^x g ^y = g ^{x + y} = E（x + y）。

增加零知識

正如我在開始時所說的，關(guān)于zkSNARKS的顯著特征比零知識部分更簡潔。 我們現(xiàn)在將看到如何增加零知識，下一部分將更加簡單地介紹簡潔性。

這個想法是，證明者將一些數(shù)值“轉(zhuǎn)移”一個隨機(jī)秘密數(shù)量，并平衡等式另一端的偏移。 證明者選擇隨機(jī)δ自由度δw并在證明中執(zhí)行以下替換

• v _自由 （s）被v _自由 （s）+δ _自由 t（s）取代
• w（s）由w（s）+δw t（s）代替。

通過這些替換，含有證人因素編碼的V _free和W值基本上變得不可區(qū)分形式的隨機(jī)性，因此不可能提取證人。 大多數(shù)平等檢查對修改是“免疫的”，我們?nèi)匀槐仨毤m正的唯一值是H或h（s）。 我們必須確保

• （s）+ ... b _m w（s））（w ₀ （s）+ a ₁ v ₁ （s）+ ... + a _m v _m = h（s）t（s），換句話說
• （s）+ v _free （s））（w ₀ （s）+ w（s））= h（s）t（s）

仍然成立。 隨著修改，我們得到了

• （s）+ v _free （s）+δfree t（s））（w ₀ （s）+ w（s）+δw t（s））

并通過擴(kuò)大產(chǎn)品，我們看到用h取代h（s）

• （s）+ v _自由 （s））+（δ _自由 δw）t（（s）+δ _自由 （w ₀ （s）+ w（s））+δw S）

會做的伎倆。

投入與證人規(guī)模之間的權(quán)衡

正如您在前面的章節(jié)中看到的，證明只包含一個組的7個元素（通常是橢圓曲線）。 此外，驗(yàn)證者所要做的工作是檢查涉及配對函數(shù)和計(jì)算E（v _in （s））的一些等式，這是一個輸入大小為線性的任務(wù)。 值得注意的是，驗(yàn)證字符串的大小和驗(yàn)證QSP（沒有SNARKs）所需的計(jì)算量都不起任何作用。 這意味著SNARK-驗(yàn)證極其復(fù)雜的問題和非常簡單的問題都需要付出相同的努力。 主要原因是因?yàn)槲覀冎粰z查單點(diǎn)的多項(xiàng)式標(biāo)識，而不檢查完整的多項(xiàng)式。 多項(xiàng)式可以變得越來越復(fù)雜，但一個點(diǎn)總是一個點(diǎn)。 影響驗(yàn)證工作的唯一參數(shù)是安全級別（即組的大小）和輸入的最大大小。

通過將其中的一些參數(shù)轉(zhuǎn)換為證人，可以減少第二個參數(shù)，輸入大小：

而不是驗(yàn)證函數(shù)f（u，w），其中u是輸入，w是證人，我們?nèi)∫粋€散列函數(shù)h并驗(yàn)證

• f'（H，（u，w））：= f（u，w）∧h（u）= H。

這意味著我們用輸入h（u）的散列（它應(yīng)該更短）替換輸入u，并驗(yàn)證存在H（u）的一些值x（因此很可能等于u ）除了檢查f（x，w）。 這基本上將原始輸入u移動到見證字符串中，從而增加見證大小，但將輸入大小減小到常量。

這是顯著的，因?yàn)樗刮覀兡軌蛟诓粩嗟臅r間內(nèi)任意地檢驗(yàn)復(fù)雜的語句。

這如何與以太坊相關(guān)？

由于驗(yàn)證任意計(jì)算是以太坊區(qū)塊鏈的核心，zkSNARK當(dāng)然與以太坊非常相關(guān)。 使用zkSNARK，不僅可以執(zhí)行任何人都可以驗(yàn)證的秘密任意計(jì)算，而且可以高效地執(zhí)行此操作。

雖然以太坊使用圖靈完整虛擬機(jī)，但目前還不可能在以太坊實(shí)施zkSNARK驗(yàn)證程序。 驗(yàn)證者任務(wù)在概念上可能看起來很簡單，但配對函數(shù)實(shí)際上很難計(jì)算，因此它將使用比單個塊中當(dāng)前可用的更多的氣體。 橢圓曲線乘法已經(jīng)相當(dāng)復(fù)雜，并且配對將其轉(zhuǎn)換到另一個級別。

現(xiàn)有的zkSNARK系統(tǒng)（如zCash）為每項(xiàng)任務(wù)使用相同的問題/電路/計(jì)算。 在zCash的情況下，它是交易驗(yàn)證者。 在Ethereum上，zkSNARK不會局限于單個計(jì)算問題，相反，每個人都可以為其專門的計(jì)算問題建立一個zkSNARK系統(tǒng)，而無需啟動新的區(qū)塊鏈。 添加到以太坊的每個新zkSNARK系統(tǒng)都需要一個新的秘密可信設(shè)置階段（某些部分可以重復(fù)使用，但不是全部），即必須生成新的CRS。 也可以為“通用虛擬機(jī)”添加zkSNARK系統(tǒng)。 這不需要為新用例創(chuàng)建新設(shè)置，就像您不需要為以太坊新智能合約引導(dǎo)新區(qū)塊鏈一樣。

讓zkSNARKs進(jìn)入以太坊

有多種方法可以為Ethereum啟用zkSNARK。 所有這些都降低了配對功能和橢圓曲線操作的實(shí)際成本（其他所需操作已經(jīng)足夠便宜），因此也可以降低這些操作的氣體成本。

提高EVM的（保證）性能

僅對某些配對函數(shù)和橢圓曲線乘法改進(jìn)EVM的性能

第一種選擇當(dāng)然是從長遠(yuǎn)看更好的方案，但難以實(shí)現(xiàn)。 目前，我們正在努力為EVM添加功能和限制，這將允許更好的實(shí)時編譯和解釋，而無需對現(xiàn)有實(shí)施進(jìn)行太多必要的更改。 另一種可能是完全更換EVM并使用諸如eWASM之類的東西。

第二種選擇可以通過迫使所有以太坊客戶端實(shí)現(xiàn)一定的配對函數(shù)并在某個橢圓曲線上乘以所謂的預(yù)編譯合約來實(shí)現(xiàn)。 好處是這可能更容易和更快實(shí)現(xiàn)。 另一方面，缺點(diǎn)是我們固定在一定的配對函數(shù)和一定的橢圓曲線上。 以太坊的任何新客戶都必須重新實(shí)施這些預(yù)編譯的合同。 此外，如果有進(jìn)步，有人發(fā)現(xiàn)更好的zkSNARK，更好的配對函數(shù)或更好的橢圓曲線，或者如果在橢圓曲線，配對函數(shù)或zkSNARK中找到缺陷，我們將不得不添加新的預(yù)編譯合約。

https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/

總結(jié)

以上是生活随笔為你收集整理的【译】zkSNARKs in a nutshell的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。