丁香五月天婷婷久久婷婷色综合91|国产传媒自偷自拍|久久影院亚洲精品|国产欧美VA天堂国产美女自慰视屏|免费黄色av网站|婷婷丁香五月激情四射|日韩AV一区二区中文字幕在线观看|亚洲欧美日本性爱|日日噜噜噜夜夜噜噜噜|中文Av日韩一区二区

您正在使用IE低版瀏覽器,為了您的雷峰網(wǎng)賬號安全和更好的產(chǎn)品體驗,強烈建議使用更快更安全的瀏覽器
此為臨時鏈接,僅用于文章預(yù)覽,將在時失效
金融科技 正文
發(fā)私信給AI金融評論
發(fā)送

0

區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

本文作者: AI金融評論 2017-12-29 11:03
導(dǎo)語:大多數(shù)關(guān)于 zkSNARKs 的解釋都浮于表面,并暗示只有最聰明的人才能懂得它的工作原理。實際上,zkSNARKs 可以總結(jié)為 4 個簡單技術(shù)。

雷鋒網(wǎng)按:原文標題為《zkSNARKs in a nutshell》,作者是以太坊智能合約語言Solidity的發(fā)明人Christian Reitwiessner。譯者楊文濤,授權(quán)轉(zhuǎn)載自作者知乎專欄。

摘要:

zkSNARKs(zero-knowledge succint non-interactive arguments of knowledge)的成功實現(xiàn)讓我們印象深刻,因為你可以在不執(zhí)行,甚至在不知道執(zhí)行具體內(nèi)容的情況下確定某個計算的結(jié)果是否正確——而你唯一知道的信息就是它正確地完成了。但是不幸的是,大多數(shù)關(guān)于 zkSNARKs 的解釋都浮于表面,并暗示只有最聰明的人才能懂得它的工作原理。實際上,zkSNARKs 可以總結(jié)為 4 個簡單的技術(shù),本篇博客將會逐一解釋這些技術(shù)。任何懂得 RSA 加密系統(tǒng)工作原理的人都會對當前使用的 zkSNARKs 有一個更好的理解和認識。

我們當前使用的 zkSNARKs 包含 4 個主要部分:

A) 編碼成一個多項式問題(Polynomial problem)

把需要驗證的程序編寫成一個二次的多項式方程:t(x) h(x) = w(x) v(x),當且僅當程序的計算結(jié)果正確時這個等式才成立。證明者需要說服驗證者這個等式成立。

B) 簡單隨機抽樣

驗證者會選擇一個私密評估點 s 來將多項式乘法和驗證多項式函數(shù)相等的問題簡化成簡單乘法和驗證等式 t(s)h(s) = w(s)v(s) 的問題。這樣做不但可以減小證明的大小,還可以大量地減少驗證所需的時間。

C) 同態(tài)編碼 / 加密(Homomorphic encoding / encryption)

譯者注:在1978年,Ron Rivest,Leonard Adleman,以及 Michael L. Dertouzos 就以銀行為應(yīng)用背景提出了同態(tài)加密的概念,當時使用的單詞是 homomorphism,也就是和抽象代數(shù)的同態(tài)是一個單詞?,F(xiàn)在一般都使用 homomorphic encryption,國內(nèi)密碼學(xué)圈子基本也都稱作同態(tài)加密。Ron Rivest 和 Leonard Adleman 分別就是著名的RSA算法中的 R 和 A(還有一位是 Adi Shamir)。

補充(來自白老師):同胚和同態(tài)在數(shù)學(xué)上不是一個意思。同胚指連續(xù)變形下的不變性,同態(tài)指映射下代數(shù)運算關(guān)系的保持性。

我們使用一個擁有一些同態(tài)屬性的(并不是完全同態(tài)的,至少在實際使用中有一些不是同態(tài)的)編碼 / 加密函數(shù) E。這個函數(shù)允許證明者在不知道 s 的情況下計算 E(t(s)), E(h(s)), E(w(s)), E(v(s)),她只知道 E(s) 和一些其他有用的加密信息。

D) 零知識(Zero Knowledge)

證明者通過乘以一個數(shù)來替換 E(t(s)), E(h(s)), E(w(s)), E(v(s)) 的值,這樣驗證者就可以在不知道真實的編碼值的情況下驗證他們正確的結(jié)構(gòu)了。

困難的問題在于對一個隨機的私密數(shù) k(k 不等于 0)來說,校驗 t(s)h(s) = w(s)v(s) 和校驗 t(s)h(s) k = w(s)v(s) 幾乎是完全一樣的,而不同點則是如果你只接收到了 (t(s)h(s) k) 和 w(s)v(s) 那么從中獲取到 t(s)h(s) 或者 w(s)v(s) 的值就幾乎不可能了。

當然,這些都只是基礎(chǔ)的部分,是為了讓讀者更地的理解 zkSNARKs 的本質(zhì),接下來將開始詳細講解這些知識點。

RSA 和 零知識證明

現(xiàn)在讓我們快速回想一下 RSA 是如何工作的,先不管那些瑣碎的細節(jié)。想想看,我們經(jīng)常用一個數(shù)字對一些數(shù)字取模,而并不是所有的整數(shù)。這里的等式 “a + b ≡ c (mod n)” 等價于 “(a + b) % n = c % n”。注意,“(mod n)” 這個部分并不是應(yīng)用在 “c” 上面的,而是應(yīng)用在 “≡” 以及相同等式所以其他的 “≡” 上面。雖然這樣非常難以閱讀,但是我保證盡量少用他們。接著讓我們回到 RSA:

證明者提供了下面的數(shù)字:

p,q:兩個隨機的私密素數(shù)

n := p q

d:1 < d < n – 1 的隨機數(shù)

e:d e ≡ 1 (mod (p-1)(q-1))

公鑰是 (e, n),私鑰是 d。素數(shù) p 和 q 可以丟棄,但是不能暴露。

消息 m 通過下面的公式加密:

 區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

c = E(m) 通過下面的公式解密:

 區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

因為  區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng),并且 m 的指數(shù)就是對 (p-1)(q-1) 這一組數(shù)取模,這樣我們就得到了區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng) (譯者注:可以由費馬小定理和中國剩余定理推出)。而且 RSA 的安全性是基于假設(shè):n 不能被輕易有效的因式分解,d 不能通過 e 計算得到(如果我們知道 p 和 q 的話,就可以輕易得到我們想要的值)。

RSA 的一個牛逼的特性是同態(tài)乘法。通常來講,如果你可以交換兩個操作的順序而不影響計算結(jié)果,那么我們就說這兩個操作是同態(tài)的。在同態(tài)加密中,這就是你可以對加密數(shù)據(jù)進行計算的一個屬性。完全同態(tài)加密是存在的,但是現(xiàn)在還沒有應(yīng)用到實際中,它能夠?qū)θ魏位诩用軘?shù)據(jù)的程序完成計算。在這里對于 RSA 來說,我們只談?wù)?group multiplication。更準確的說就是:區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)  ,用文字描述就是:兩個加密信息的乘積等于兩個信息乘積的加密。

這個同態(tài)的特性已經(jīng)有一些乘法的零知識證明了:證明者知道一些私密的數(shù)字 x 和 y,并計算出了它們的乘積,但是只給驗證者發(fā)送加密的版本:a = E(x), b = E(y) 以及 c = E(x y)。驗證者檢驗等式 (a b) % n ≡ c % n 是否成立,此時驗證者只知道加密版的乘積以及乘積是否被正確的計算,但是她不知道兩個乘數(shù)和真正的乘積。如果你用加法來替代乘法,那就是一個主要操作為添加余額的區(qū)塊鏈方向了。

交互式驗證

我們已經(jīng)對零知識這個概念有了一定的了解了,現(xiàn)在讓我們著重看一下 zkSNARKs 的另一個主要的特性:簡明性(succinctness)。之后你會看到這個簡明性是 zkSNARKs 更牛逼的部分,因為零知識部分的實現(xiàn)就是因為這一特定編碼,而這個特定的編碼是一個有限形式的同態(tài)編碼。

SNARKs 是 succinct non-interactive arguments of knowledge 的縮寫。一般都通用設(shè)置之所以叫做交互式協(xié)議,是因為這里有一個證明者和一個驗證者,證明者想要通過交換信息的方式讓驗證者相信一個表達式(比如 f(x) = y)。一般來說,沒有證明者可以讓驗證者相信一個錯誤的表達式(可靠性),而且對于證明者來說一定存在一個確定的策略讓驗證者相信任何真實的表達式(完整性)。SNARKs 各個部分的的意義如下:

  • Succinct:比起真正需要計算的長度來說,我們發(fā)送的信息大小是很小的。

  • Non-interactive:沒有或者只有很少很少的交互。對于 zkSNARKs 來說就是在證明者向驗證者發(fā)送一條信息之后的過程。此外,SNARKs 還常常擁有叫做『公共驗證者』的屬性,它的意思是在沒有再次交互的情況下任何人都可以驗證,這對于區(qū)塊鏈來說是至關(guān)重要的。

  • Arguments:驗證者只對計算能力有限的證明者有效。擁有足夠計算能力的證明者可以創(chuàng)造出關(guān)于錯誤表達式的(注意,只要擁有足夠的計算能力,任何公鑰加密系統(tǒng)都可以被破解)證明和參數(shù)。這也叫做『計算可靠性』,相對的還有『完美可靠性』。

  • of Knowledge:對于證明者來說在不知道一個叫做證據(jù)(witness)(比如一個哈希函數(shù)的原象或者一個確定 Merkle-tree 節(jié)點的路徑)的情況下,構(gòu)造出一組參數(shù)和證明是不可能的。

如果你添加了零知識的前綴,那么在交互中你就需要一個性質(zhì),即驗證者除了知道表達式的正確與否之外其他一無所知。尤其是驗證者不能知道 witness string ——稍后我們會詳細解釋這是什么。

區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

關(guān)于零知識的部分相對正式的定義(仍然缺乏一些細節(jié))就是:存在一個模擬器,它可以生成一些設(shè)置字段,但是卻不知道私密的 witness,它還可以和驗證者交互 -- 但是外部的觀察者卻不能分辨出哪個與驗證者進行的交互,哪個是與證明者進行的交互。

NP 和 簡化的復(fù)雜性理論

為了了解 zkSNARKs 能用于哪些問題和計算,我們不得不基于復(fù)雜的理論定義一些說法。如果你不知道什么是 “witness” 的話,那么即使『讀』完零知識證明你也不會知道它是什么,并且你也不會了解到為什么 zkSNARKs 只適用于特定的多項式問題,如果真是這樣的話,那么你就可以跳過本節(jié)了。

P 和 NP

首先,我們限制函數(shù)只能輸出 0 和 1,并稱這樣的函數(shù)為問題(problems)。因為你可以單獨的查詢一個長長的結(jié)果的每一位(bit),所以這不是一個真正的限制,但是這樣可以讓定理變的簡單一點。現(xiàn)在我們想衡量解決一個給定的問題(計算函數(shù))到底有多『難』。對于一個數(shù)學(xué)函數(shù) f 的特定機器的實現(xiàn) M,給定一個輸入 x,我們可以計算出這個函數(shù) f 需要的步數(shù) -- 這就叫做 x 在 M 上的執(zhí)行時間,這里的『步數(shù)』其實不太重要。因為程序?qū)τ诟蟮妮斎胪鶗枰嗟牟綌?shù),而這個執(zhí)行時間則是用輸入值的大小或者說長度(bit 的數(shù)量)來衡量。這就是例如『 區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng) 算法』的來源 -- 這就是一個當輸入值大小為 n 時,至多需要 區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng) 個步數(shù)的算法。這里的『程序』和『算法』廣義上是相同的。

執(zhí)行時間至多為 區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng) 的程序也叫做 “polynomial-time programs”(多項式時間問題)。

在復(fù)雜性理論中有兩個主要的類別,他們就是 P 問題和 NP 問題:

P 問題是具有多項式時間的一類問題

雖然 k 的指數(shù)對于一些問題來說確實非常大,但是實際上對于那些非人造的,k 不大于 4 的 P 問題仍然被認為是可以『解決的』的問題。要確認一筆比特幣的交易就是一個 P 問題,因為經(jīng)過評估它需要一個多項式時間(并且只能輸出 0 和 1)。簡單的說就是,如果你只是計算一些值而不去『搜索』,那么這個問題就是 P 問題。但是如果你不得不搜索一些東西,那么你就會進入到另一個叫做 NP 問題的類別中。

NP 類問題

幾乎所有的 NP 類問題都是 zkSNARKs,今天在實際中使用的 zkSNARKs 在通常意義上講都屬于 NP 問題。而我們目前還不知道的是,有沒有不屬于 NP 問題的 zkSNARKs 存在。

所有的 NP 問題都有一個特定的結(jié)構(gòu),這個特定的結(jié)構(gòu)來自于 NP 問題的定義:

  • NP 問題是 L(含有多項式時間的程序 V)的一類問題, 這個程序 V 可以在給定一個多項式尺度的叫做因子的 witness 的情況下驗證這個因子。更正式的說就是:
    當且僅當一些多項式尺度的字符串 w(被稱作 witness)滿足 V(x, w) = 1 時,L(x) = 1 成立。

區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

P = NP ?

如果你將 NP 問題定義為長度為 0 的 witness strings,那么你會發(fā)現(xiàn)這就是 P 問題。因此 每個 P 問題其實都是 NP 問題。在復(fù)雜性理論研究中有一個主要的任務(wù)就是發(fā)掘出這兩類問題的不同 -- 即一個不屬于 P 的 NP 問題。在這里似乎是很顯然的,但是如果你可以再一般情況下證明它,那么你可以獲得 1 百萬美元。額外說一句,如果你可以反向證明,即 P 和 NP 是等價的,也可以獲得那筆獎金。而數(shù)字貨幣領(lǐng)域有朝一日能夠證明的概率很大。我這么說的原因是,比起一個哈希函數(shù)的碰撞或者根據(jù)地址找到私鑰來說,找到一個工作難題解決辦法的證明顯然更容易一點。這些都是 NP 問題,因為你剛已經(jīng)證明了 P = NP,那么對于這些 NP 問題來說就一定存在一個多項式時間的程序。但是本文就不討論了,雖然大部分研究者都認為 P 問題和 NP 問題并不是等價的。

NP 完全問題

讓我們再回到 SAT。這個看起來簡單的問題有個有趣的特性就是它并不僅是 NP 問題,還是 NP 完全問題?!和耆贿@個詞在這里和『圖靈完備』是一個意思。這意味著它是 NP 中最難的問題,但是更重要的是 NP 完全的定義——任何 NP 問題的輸入都可以用下面的方法轉(zhuǎn)換成一個同樣的 SAT 的輸入:

所有 NP 問題 L 都有一個在多項式時間可計算的『還原函數(shù)(reduction function)』f:

  • L(x) = SAT(f(x))

這樣的一個還原函數(shù)不能被看成一個編譯器:編譯器是可以將一些編程語言寫的源代碼等價的轉(zhuǎn)換成另一種編程語言的機器,也就是擁有語義行為的機器語言。因為 SAT 是 NP 完全的,所以這樣一個還原對于任何可能的 NP 問題都是存在的,比如給定一個合適的 block hash,驗證一筆比特幣交易是否合法。這里還可以將一筆交易轉(zhuǎn)換成一個布爾函數(shù)的還原函數(shù),因此當且僅當這個交易是合法的時候這個布爾函數(shù)就是可滿足的。

還原示例

為了弄明白這樣一個還原的方法,讓我們先考慮評估多項式的問題。首先,讓我們定義一個由整數(shù)常量,變量,加法,減法,乘法和(正確匹配的)括號構(gòu)成的多項式(類似于布爾函數(shù))?,F(xiàn)在讓我們考慮下面的問題:

  • 如果 f 是一個變量都來自于集合 {0, 1} 的多項式,并且其中包含一個零項,那么 PolyZero(f) := 1

現(xiàn)在我們就可以構(gòu)建出一個從 SAT 到 PolyZero 的還原方法了,同時這也說明了 PolyZero 也是一個 NP 完全問題(驗證它是否屬于 NP 就當是留給你們的小練習(xí)啦)。

區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

有些人可能會假設(shè)將 r((f ∧ g)) 定義為 r(f) + r(g),但是那樣的話多項式的結(jié)果就會超出集合 {0, 1} 了。

使用函數(shù) r,((x ∧ y) ∨?x) 被轉(zhuǎn)換成了 (1 – (1 – (1 – x))(1 – (1 – y))(1 – (1 – x))。

注意,對于 r 來說,每一個替換規(guī)則都滿足了之前聲明的目的,因此 r 也正確的實現(xiàn)了還原:

  • 當且僅當 r(f) 含有集合 {0, 1} 中的一個 0 時,SAT(f) = PolyZero(r(f)) 或者說 f 是可滿足的

Witness preserving

從這個例子中你可以看出還原函數(shù)只定義了如何轉(zhuǎn)換輸入,但是當你仔細看的時候(或者閱讀完如何完成一個可用的還原證據(jù)之后)你就會知道如何將一個可用 witness 和 輸入一起轉(zhuǎn)換。在我們的例子中,我們只定義了如何將函數(shù)轉(zhuǎn)換為多項式,但是不知道如何將我們解釋的證據(jù)轉(zhuǎn)換成滿足賦值的 witness。這個 witness 在同一時間轉(zhuǎn)換對于交易來說不是必要的,但是通常都會包含。而這對于 zkSNARKs 來說是至關(guān)重要的,因為對于證明者來說他唯一的任務(wù)就是讓驗證者相信有這樣一個 witness 存在,并且還不會暴露任何有關(guān) witness 的信息。

Quadratic Span Programs

在上一部分中,我們看到了 NP 問題的計算是如何被相互化簡的,尤其是那些 NP 完全問題,那些 NP 完全問題基本上又都再次形成了其他的 NP 問題——包括交易驗證問題。那么對我們來說找到一個對所有 NP 問題都通用的 zkSNARKs 就變的很容易了:我們只需要選擇適合的 NP 完全問題。所以如果我們想展示如何使用 zkSNARKs 來驗證交易的話,那么展示如何處理這個確定的 NP 完全問題就是一個有效的方法,并且比從理論上解釋更容易讓人接受。

接下來就是基于論文GGPR12(這里面鏈接的技術(shù)報告比原文的干貨更多)來談了,這篇論文的作者發(fā)現(xiàn)了一個叫做 Quadratic Span Programs(QSP)的問題,這個問題完全就是為 zkSNARKs 準備的。一個 Quadratic Span Program 是由一組多項式和尋找給定多項式倍數(shù)的線性組合任務(wù)構(gòu)成。此外,輸入字符串的每個單獨的 bit 都限制了你能夠使用的多項式。詳細來說(通常來講 GSPs 限制不是那么嚴格,但是我們就是需要這種強限制的版本,因為后面我們會用到)就是:

對于輸入長度為 n 的在域 F 上的 QSP 問題由下面這些部分構(gòu)成:

區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

這里的任務(wù)很粗糙,就是給多項式乘以一個因子并把它們加起來(也叫做『線性組合』)使得它們的總和是 t 的倍數(shù)。對于每一個二進制輸入字符串 u 來說,函數(shù) f 限制了可以被使用的多項式,或者更嚴格的講就是它們必須是線性組合的因子。正式的表示就是:

區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

注意,在這里當 2n 小于 m 時,選擇元組 a 和 b 仍然是有很大的自由度的。這就意味著 QSP 只對特定大小的輸入是有價值的——這個問題可以通過使用非均勻復(fù)雜度來解決,非均勻復(fù)雜度這個話題今天我們不會深入的講解,我們只需要知道當輸入值很小時,我們的密碼學(xué)也能良好運轉(zhuǎn)。

區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

這里我們不會討論如何將通用計算和線路問題簡化成 QSP 問題,因為這對于我們了解基本概念沒有任何幫助,我們只需要知道 QSP 是 NP 完全(或者說比一些非均勻分布的像 NP/poly 問題更完全)的就好了。實際上,這個簡化是一個『工程』部分——必須要使用一種很聰明的方法才能讓 QSP 問題盡可能的小并且有一些其他的優(yōu)良特性。

區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

zkSNARK 詳解

現(xiàn)在讓我們來詳細的描述一下 QSP 上的 zkSNARK。它在開始設(shè)置階段會執(zhí)行每一個單獨的 QSP。在 zCash 中,交易驗證者的線路是固定的,因此 QSP 的多項式也是固定的,這個 QSP 在設(shè)置階段只允許被執(zhí)行一次,然后在所有的只有輸入 u 不同的交易上復(fù)用。這個開始的設(shè)置會生成一個公共參考串(common reference string,CRS),驗證者選擇一個隨機且私密的域元素,并在這個點加密多項式的值。驗證者使用一些特定的加密方法 E 并在 CRS 中

區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

如何使用零知識來簡單估計一個多項式

首先讓我們先來看一種簡單的情況,即一個多項式在私密點上的加密估值,而不是完整的 QSP 問題。

區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

這里的這個示例告訴我們驗證者并不需要求出完整的多項式來證明這一點,僅僅使用配對函數(shù)就可以了。下一步我們就要添加零知識的部分了,這樣驗證者就不能構(gòu)建任何關(guān)于 f(s) 值了,甚至連 E(f(s)) 這種加密信息也不行。

區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

好的,現(xiàn)在我們總算知道了一點關(guān)于在驗證者不知道那個值的情況下,證明者是如何在一個加密的私密點上面計算出多項式加密值的。接下來讓我們把這些應(yīng)用到 QSP 問題中吧。

QSP 問題的 SNARK

區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng) 區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng) 區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

最后一個等式用來檢驗是否使用了正確的多項式(這一部分還沒有講到,不過其他的例子會說到它)。要注意的是,我們所有的加密值,證明者只需要知道 CRS 就可以全部推算出來。

而驗證者現(xiàn)在要做的還有這些:

區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

假設(shè)證明者提供了一個正確的證明,讓我們檢驗一下等式是否滿足。左邊和右邊的部分分別是:

區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

添加零知識

區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

在輸入和 Witness 大小之間取一個折中的值

就像你在上面這些小節(jié)中看到的一樣,我們的證明由一個群(就是一個橢圓曲線)的 7 個元素組成。而且驗證者的工作就是檢驗一些配對函數(shù)的等式是否成立以及計算 區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng) 這樣一個跟隨輸入大小的線性任務(wù)。最主要的是,在這個驗證過程中,既不需要 witness 字符串的大小,又不需要計算工作量來驗證 QSP(沒有 SNARKs)。這就意味著 SNARKs 的校驗是個很復(fù)雜的問題,而簡單的問題往往都是一樣的。造成這個結(jié)果的主要原因則是,因為我們只在一個單獨的點上面檢驗了多項式的一致性,而不是全部的點。多項式可以變的非常非常復(fù)雜,但是一個點始終是一個點。而唯一能影響到驗證結(jié)果的參數(shù)就是安全性的等級(比如群的大?。┖洼斎胫档淖畲蟪叽?。

減小第二個參數(shù)是可行的,將輸入值的一部分移動到 witness 中:我們不驗證函數(shù) f(u, w),u 是輸入,w 是 witness,而是做一次 hash,然后驗證:

 區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

這樣就意味著我們可以用一個 hash 來代表輸入 h(u) 了(這樣就會變的更短),除了驗證 f(x, w),我們還需要驗證某個值 x 的 hash 等于 H(u)(這樣的話,那 x 極有可能就等于 u 了)。這樣就將原始輸入 u 移動到 witness 字符串中了,這樣雖然會增大 witness 的大小,但是輸入值的大小就減小為一個常數(shù)了。

這簡直太厲害了,因為這意味著我們可以在常數(shù)時間內(nèi)完成對任何復(fù)雜表達式的檢驗。

zkSNARKs 和 Ethereum 關(guān)系緊密

因為驗證計算是 Ethereum 區(qū)塊鏈的核心,所以 zkSNARKs 和 Ethereum 關(guān)系緊密相連。有了 zkSNARKs,我們不但可以完成任何人都可證實的私密的計算,而且還可以高效的完成。

雖然 Ethereum 使用了一個圖靈完備的虛擬機,但是當前在 Ethereum 上實現(xiàn)一個 zkSNARK 還是不可能的。從概念上講,驗證者的任務(wù)似乎很簡單,但是配對函數(shù)是真的很難計算,而且在單個區(qū)塊中還會消耗更多的 gas。橢圓曲線的乘法相對來講已經(jīng)非常復(fù)雜了,而配對函數(shù)將這個復(fù)雜度又增加了一個級別。

像 zCash 這種現(xiàn)存的 zkSNARK 系統(tǒng)對每一個任務(wù)都使用的是同樣的問題,circuit 計算。在 zCash 中,就是交易驗證。在 Ethereum 上,zkSNARKs 將不會只單單做一個計算問題,而是讓所有的人都能夠在不發(fā)布一個新的區(qū)塊鏈的情況下構(gòu)建他們自己的 zkSNARK 系統(tǒng)。每一個添加到 Ethereum 上的 zkSNARK 系統(tǒng)都需要進行一個新的私密的可信任的準備階段(一些可以復(fù)用,一些不能),比如生成一個新的 CRS。像為一個『通用虛擬機』添加 zkSNARK 系統(tǒng)將會變的可能。這樣的話當你使用一個新的實例時,你就不需要重新設(shè)置了,因為你將不再需要為 Ethereum 上新的智能合約發(fā)布一個新的區(qū)塊鏈。

如何在Ethereum 上啟用 zkSNARKs 

在 Ethereum 上啟用 zkSNARKs 有很多種方式。所有的方式都可以為配對函數(shù)和橢圓曲線操作(其他必要的操作都很簡單)減小真實的損耗,因此我們也要減小這些操作消耗的 gas。

  • 提升(確保)EVM 的性能

  • 只在確定的配對函數(shù)和橢圓曲線乘法上提升 EVM 的性能

第一項在長期顯然會得到很好的回報,但是實現(xiàn)起來難度比較大。我們現(xiàn)在已經(jīng)在對 EVM 添加一些新的功能和限制了,例如更好的支持及時編譯以及在現(xiàn)存實現(xiàn)下最小改動的解釋器的實現(xiàn)。當然也不排除直接用 eWASM 來替換 EVM。

第二項則可以通過強制所有的 Ethereum 客戶端執(zhí)行一個確定的配對函數(shù)和確定的橢圓曲線乘法的叫做預(yù)編譯合約的東西來實現(xiàn)。這樣做的好處就是實現(xiàn)起來既簡單又快速。而缺點呢則是這樣做我們就會固定在一個確定的的配對函數(shù)和一個確定的橢圓曲線上。所有 Ethereum 上新的客戶端都不得不再實現(xiàn)一遍這個預(yù)編譯合約。所有,如果有什么新的進展,或者有人可以找到更好的 zkSNARKs 的方法,更好的配對函數(shù),更好的橢圓曲線,又或者發(fā)現(xiàn)了橢圓曲線,配對函數(shù)和 zkSNARK 的一些缺點,那么我們就會添加到新的預(yù)編譯合約中。

區(qū)塊鏈研習(xí) | 詳解零知識證明的四大基礎(chǔ)技術(shù),如何與以太坊發(fā)生反應(yīng)

雷峰網(wǎng)版權(quán)文章,未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。

分享:
相關(guān)文章

編輯

關(guān)注金融科技前沿!在這里,讀懂智能金融與未來!
當月熱門文章
最新文章
請?zhí)顚懮暾埲速Y料
姓名
電話
郵箱
微信號
作品鏈接
個人簡介
為了您的賬戶安全,請驗證郵箱
您的郵箱還未驗證,完成可獲20積分喲!
請驗證您的郵箱
立即驗證
完善賬號信息
您的賬號已經(jīng)綁定,現(xiàn)在您可以設(shè)置密碼以方便用郵箱登錄
立即設(shè)置 以后再說