最近以太坊啟動(dòng)了“大都會(huì)”硬分叉扛伍，很重要的一個(gè)功能就是整合了ZCash的零知識證明技術(shù)zkSNARK圃阳。我們一起來看一下zkSNARK這個(gè)拗口的技術(shù)到底是什么鬼谦趣。

零知識證明

要了解zkSNARK慰照，必須先理解什么是零知識證明富腊。

關(guān)于零知識證明蛆挫，概念并不難理解赃承，我們以一個(gè)老掉牙的故事作為例子。

阿里巴巴被強(qiáng)盜抓住悴侵，為了保命瞧剖，他需要向強(qiáng)盜證明自己擁有打開石門的密碼，同時(shí)又不能把密碼告訴強(qiáng)盜可免。他想出一個(gè)解決辦法抓于，先讓強(qiáng)盜離開自己一箭之地，距離足夠遠(yuǎn)讓強(qiáng)盜無法聽到口令浇借，足夠近讓阿里巴巴無法在強(qiáng)盜的弓箭下逃生捉撮。阿里巴巴就在這個(gè)距離下向強(qiáng)盜展示了石門的打開和關(guān)閉。

這個(gè)整個(gè)過程就是零知識證明妇垢，證明者能夠在不向驗(yàn)證者提供任何有用信息（石門的口令）的情況下巾遭，使驗(yàn)證者相信某個(gè)論斷（阿里巴巴知道打開石門的方法）是正確的。

當(dāng)然闯估，現(xiàn)實(shí)生活中類似的應(yīng)用有很多灼舍，大家可以參考阿里巴巴的零知識證明或者零知識證明。

在計(jì)算機(jī)世界里面涨薪，零知識的應(yīng)用場景就更多了骑素，例如我們常用非對稱加密來做身份認(rèn)證，驗(yàn)證方只要使用公鑰解出自己提供的隨機(jī)數(shù)刚夺，即可證明被認(rèn)證方的身份献丑，不需要其提供自己的私鑰末捣。

以上例子都是針對特定場景的特定方法，比如說石門不是通過口令控制而是通過實(shí)物鑰匙控制创橄，這個(gè)方法就不可用了塔粒，是否有一個(gè)通用方法去認(rèn)證任何事件呢？

zkSNARK

zkSNARK是zero-knowledge succint non-interactive arguments of knowledge的簡稱筐摘，全稱里面每個(gè)單詞都有特定的含義：

Zero knowledge：零知識證明卒茬，見前文。

Succinctness：證據(jù)信息較短咖熟，方便驗(yàn)證

Non-interactivity：幾乎沒有交互圃酵，證明者基本上只要提供一個(gè)字符串義工驗(yàn)證。對于區(qū)塊鏈來說馍管，這一點(diǎn)至關(guān)重要郭赐，意味著可以把該消息放在鏈上公開驗(yàn)證。

Arguments：證明過程是計(jì)算完好（computationally soundness）的确沸，證明者無法在合理的時(shí)間內(nèi)造出偽證（破解）捌锭。跟計(jì)算完好對應(yīng)的是理論完好（perfect soundness)，密碼學(xué)里面一般都是要求計(jì)算完好罗捎。

of knowledge：對于一個(gè)證明者來說观谦，在不知曉特定證明 (witness) 的前提下，構(gòu)建一個(gè)有效的零知識證據(jù)是不可能的桨菜。

接下來豁状，我們一步一步解釋這個(gè)zkSNARK到底是怎么實(shí)現(xiàn)的。

同態(tài)隱藏

說到zkSNARK倒得，不能不提的一個(gè)概念就是同態(tài)隱藏泻红，說它是zkSNARK的核心技術(shù)一點(diǎn)都不為過。

滿足下面三個(gè)條件的函數(shù)E(x）霞掺，我們稱之為加法同態(tài)谊路。

1.對于大部分的x，在給定的E(x)通常很難求解出x.

2.不同輸入將會(huì)得到不同輸出 - 因此如果x≠y,菩彬，則E(x)≠E(y).

3.如果某人知道了E(x)和E(y),缠劝，則他可以生成在算數(shù)運(yùn)算式中的x和y.。比如挤巡，他們可以使用E(x)和E(y).來計(jì)算E(x+y)剩彬。

同理我們可以定義乘法同態(tài)甚至是全同態(tài)酷麦。

我們常用的的非對稱加密方式RSA和ECC都支持加法同態(tài)矿卑，計(jì)算和證明證明需要比較多的公式運(yùn)算，有時(shí)間另外開一篇文章講解沃饶。

跟RSA和ECC一樣母廷，注意這里的E(x)計(jì)算是在有限域里面進(jìn)行轻黑，這個(gè)域下文稱為Fp。

有了同態(tài)隱藏這個(gè)利器以后琴昆，我們就可以實(shí)現(xiàn)一定程度的零知識證明了氓鄙。

A擁有x和y兩個(gè)秘密的數(shù)字，需要向B證明這兩個(gè)數(shù)字的和是7业舍，只需要執(zhí)行下面三個(gè)步驟：

1.A計(jì)算E(x)抖拦，E(y)，并發(fā)送給B

2.因?yàn)楹瘮?shù)E(x)滿足加法同態(tài)舷暮，B可以通過E(x)态罪，E(y)計(jì)算E(x+y)

3.B獨(dú)立計(jì)算E(7)，并驗(yàn)證E(x+y)=E(7)

多項(xiàng)式盲驗(yàn)證

利用加法同態(tài)的特性下面，我們可以簡單的把零知識證明推廣到多項(xiàng)式中复颈。

假定A知道一個(gè)最高d次的多項(xiàng)式P，而B想要知道對應(yīng)某個(gè)s的E(P(s))

我們希望在驗(yàn)證的過程中沥割，A只知道P耗啦，不知道s，B只知道s机杜，不知道P帜讲，可以通過下面方式實(shí)現(xiàn)：

1.對s的每個(gè)指數(shù)，B計(jì)算E(1)椒拗，E(s)舒帮，...，E(sd)陡叠，并發(fā)送給A

2.A知道多項(xiàng)式的所有系數(shù)玩郊，可以利用同態(tài)特性計(jì)算P(s)，并回送給B

KCA以及完整的多項(xiàng)式盲驗(yàn)證

上一章提供的多項(xiàng)式盲驗(yàn)證方式有一個(gè)致命的問題枉阵，就是B根本沒法驗(yàn)證A是真正利用多項(xiàng)式P(s)去計(jì)算結(jié)果译红，也就是說無法證明A真正知道這個(gè)多項(xiàng)式P(X)。我們繼續(xù)完善一下上面的驗(yàn)證兴溜。

我們先定義一個(gè)概念：α對是指滿足b=α*a的一對值（a侦厚，b）。注意這里的乘法其實(shí)是橢圓曲線（ECC）上的乘法拙徽，橢圓曲線上的運(yùn)算符合兩個(gè)特性：一是當(dāng)α值很大的情況下刨沦，很難通過a和b倒推出α，二是加法和乘法滿足可交換群的特性膘怕，也就是說加法和乘法交換律在橢圓曲線上也是成立的想诅。橢圓曲線的運(yùn)算很復(fù)雜，本文暫不詳述，大家只要記住橢圓函數(shù)的乘法滿足同態(tài)隱藏的特性来破，即可完成下面的證明篮灼。

我們利用α對的特性，構(gòu)建一個(gè)稱為KCA（Knowledge of Coefficient Test and Assumption）的過程

1.B隨機(jī)選擇一個(gè)α生成α對（a徘禁，b）侧到，α自己保存黔宛，（a踩娘，b）發(fā)送給A

2.A選擇γ搔谴，生成(a′,b′)=(γ?a,γ?b)，把(a′,b′)回傳給B驶沼。利用交換律它改，可以證明(a′,b′)也是一個(gè)α對，b′=γ?b=γα?a=α(γ?a)=α?a′

3.B校驗(yàn)(a′,b′)商乎，證實(shí)是α對央拖，就可以斷言A知道γ

這個(gè)證明可以推廣到多個(gè)α對的場景，稱為d-KCA

1.B發(fā)送一系列的α對給A

2.A使用(a′,b′)=(c1?a1+c2?a2,c1?b1+c2?b2)生成新的α對

3.B驗(yàn)證通過鹉戚，可以斷言A知道c數(shù)組

這個(gè)KCA咋看似乎沒有什么用鲜戒，但正好可以補(bǔ)足了之前多項(xiàng)式盲驗(yàn)證 的缺陷，一個(gè)完整的多項(xiàng)式盲驗(yàn)證過程如下

0.因?yàn)闄E圓曲線的乘法符合同態(tài)隱藏的特性抹凳，A和B可以共同選擇x?g作為E(x)

1.B計(jì)算g,s?g,…,sd?g和α?g,αs?g,…,αsd?g并發(fā)送給A遏餐，實(shí)際上過程同上一章的第一步，只是把E(x)替代成乘法赢底，增加了αs相應(yīng)的多項(xiàng)式結(jié)果

2.A計(jì)算a=P(s)?g失都，b=αP(s)?g并回傳

3.a值即為B所需校驗(yàn)的E(P(s))結(jié)果，同時(shí)KCA保證了a值必然是通過多項(xiàng)式生成

好了幸冻，到這里喘口氣粹庞，回顧一下我們現(xiàn)在到底做到了些什么。

通過加法同態(tài)洽损，我們可以實(shí)現(xiàn)加法隱藏庞溜，讓B在不知道x和y的情況下，校驗(yàn)x+y的值碑定。進(jìn)一步流码，通過多項(xiàng)式盲驗(yàn)證，我們可以在不暴露多項(xiàng)式P(X)的情況下延刘，讓B校驗(yàn)任意給定s對應(yīng)的P(s)漫试。

接下來坐好扶穩(wěn)，我們要從多項(xiàng)式推廣到任意計(jì)算的盲驗(yàn)證了碘赖。

任意計(jì)算轉(zhuǎn)換到多項(xiàng)式證明

直接上例子驾荣，假定A需要向B證明他知道c1外构，c2，c3秘车，使(c1?c2)?(c1+c3)=7典勇，按照慣例劫哼，c1叮趴，c2，c3需要對B保密权烧。

我們要做的第一步就是把計(jì)算“拍平”眯亦，通過基本的運(yùn)算符把原計(jì)算畫成這樣的“計(jì)算門電路”。

當(dāng)然我們也可以用程序員比較熟悉的方式來表達(dá)

S1=C1*C2

S2=C1+C3

S3=S1*S2

通過增加中間變量般码，我們把復(fù)雜的計(jì)算拍平妻率，使用最簡單的門電路表達(dá)。新的門電路跟原計(jì)算是等價(jià)的板祝。

我們要做的第二步就是把每一個(gè)門電路表示為等價(jià)的向量點(diǎn)積形式宫静，這個(gè)過程成為R1CS（rank-1 constraint system）。

對每個(gè)門電路券时，我們定義一組向量（a,b,c）孤里，使得s . a * s . b - s . c = 0。其中s代表全部輸入的向量橘洞，也就是[C1,C2,C3,S1,S2,S3]捌袜，為了讓加法門也能用同樣的方式表達(dá)，我們增加一個(gè)虛擬的變量成為one炸枣，s向量變成[one,C1,C2,C3,S1,S2,S3]虏等。

對應(yīng)到第一個(gè)門

a=[0,1,0,0,0,0,0]

b=[0,0,1,0,0,0,0]

c=[0,0,0,0,1,0,0]

把s，a适肠，b和c代入s . a * s . b - s . c = 0霍衫，得到C1*C2-S1=0，即這個(gè)向量表達(dá)跟第一個(gè)門是完全等價(jià)的侯养。

同理我們可以計(jì)算第二個(gè)門

a=[1,0,0,0,0,0,0]

b=[0,1,0,1,0,0,0]

c=[0,0,0,0,0,1,0]

第三個(gè)門

a=[0,0,0,0,1,0,0]

b=[0,0,0,0,0,1,0]

c=[0,0,0,0,0,0,1]

好了慕淡，到這里，我們把一個(gè)計(jì)算式拍平成為門電路沸毁，接著又通過R1CS把門電路“編碼”成向量的表達(dá)方式峰髓。

接下來是最重要的一步，把向量表達(dá)式表示為多項(xiàng)式息尺，從而把向量的驗(yàn)證轉(zhuǎn)化為多項(xiàng)式的驗(yàn)證携兵，這個(gè)過程稱為QAP（Quadratic Arithmetic Programs）。

具體辦法是搂誉，在Fp上面選定任意三個(gè)不同的值徐紧，例如我們選定1，2，3并级，尋找一組多項(xiàng)式

使得多項(xiàng)式在x取值1拂檩，2，3的時(shí)候a嘲碧，b稻励，c數(shù)組的取值分別對應(yīng)到前述三個(gè)門電路的向量。

問題轉(zhuǎn)化為通過已知解倒推多項(xiàng)式定義愈涩，這部分可以使用拉格朗日插值完成望抽，本文不再詳述。這個(gè)過程中需要對向量的每個(gè)取值做拉格朗日插值履婉，對于復(fù)雜問題煤篙，這個(gè)向量會(huì)非常龐大，計(jì)算過程會(huì)很復(fù)雜毁腿，這里可以利用快速傅里葉變換進(jìn)行優(yōu)化辑奈。

到這里，我們把原來的三個(gè)向量組表示成為一個(gè)用x表示的數(shù)組a(x),b(x),c(x)已烤。

取多項(xiàng)式P(x)=s . a(x) * s . b(x) - s . c(x)鸠窗，根據(jù)我們原來的定義，在x取值為1草戈，2或3的時(shí)候塌鸯，P(x)=0。根據(jù)多項(xiàng)式特性唐片，P(a)=0等價(jià)于P可以被（x-a）整除丙猬，P(x)一定能被(x-1)(x-2)(x-3)整除，也就是說存在H（X）费韭，使P(x)=T(x)*H(x)茧球，其中T(x)=(x-1)(x-2)(x-3)。

注意QAP這個(gè)過程把原來三個(gè)點(diǎn)的取值轉(zhuǎn)化成為一個(gè)多項(xiàng)式星持，相當(dāng)于中間插入了很多沒有意義的值抢埋，這些值的取值與原公式是無關(guān)的。也就是說多項(xiàng)式的驗(yàn)證與原計(jì)算的驗(yàn)證本質(zhì)并不等價(jià)督暂，但驗(yàn)證了多項(xiàng)式也就驗(yàn)證了元計(jì)算揪垄。

好了，最終我們把原算式的證明轉(zhuǎn)化成為多項(xiàng)式的證明逻翁，只要證明P(x)=T(x)*H(x)饥努，即可驗(yàn)證原算式。

匹諾曹協(xié)議

通過QAP八回，我們已經(jīng)把計(jì)算式的證明轉(zhuǎn)化為多項(xiàng)式的證明酷愧，現(xiàn)在萬事具備驾诈，只欠東風(fēng)，就差一個(gè)完整的驗(yàn)證流程了溶浴。

為了簡化下文描述乍迄，我們定義s . a(x)為L(x)，s . b(x)為R(x)士败，s . c(x)為O(x)闯两，那么我們需要證明的等式就改寫成L(x)*R(x)-O(x)=T(x)*H(x)。L拱烁，R和O的最高階數(shù)是d生蚁，所以這個(gè)等式的最高階數(shù)是2d噩翠，我們知道戏自，兩個(gè)不等價(jià)的多項(xiàng)式交點(diǎn)數(shù)量最多只有2d個(gè)，2d相較于有限域的元素個(gè)數(shù)p來說很小的情況下伤锚，我們可以采用采樣的方式驗(yàn)證多項(xiàng)式相等擅笔，A隨意選擇多項(xiàng)式P(x)被校驗(yàn)通過的概率只有2d/p。隨機(jī)采樣校驗(yàn)的過程如下：

1.A按照上一章方法選擇多項(xiàng)式L,R,O,H

2.B選擇隨機(jī)點(diǎn)s屯援，計(jì)算E(T(s))

3.A計(jì)算E(L(s)),E(R(s)),E(O(s)),E(H(s))? （根據(jù)B發(fā)過來的E(s)猛们，E(s2),...)

4.B檢驗(yàn)E(L(s)*R(s)-O(s))=E(H(s)*T(s))

這個(gè)證明過程還有四個(gè)問題需要解決：

1.保證L,R,O從同一組參數(shù)s生成

這個(gè)證明過程存在一個(gè)缺陷，正如按照我們的定義L(x)=s . a(x)狞洋，R(x)=s . b(x)弯淘，O(x)=s . c(x)，這里隱含了一個(gè)限定條件是L吉懊，R和O必須是由同一個(gè)向量s生成庐橙，證明中忽略了這一點(diǎn)，也就是說A可以通過選擇不符合這個(gè)限定條件的多項(xiàng)式來作弊借嗽。解決辦法仍然是KCA态鳖，只不過這次的KCA要復(fù)雜一些。

先定義兩個(gè)公式：

這個(gè)公式的含義是要把L恶导，R浆竭，O的指數(shù)錯(cuò)開，如果L惨寿，R邦泄，O真是從同一組s=[s1,....sm]生成的話，必然有

換句話說裂垦，只要A能給出F和Fi的線性組合顺囊，即可證明L，R缸废，O符合限定條件包蓝。這個(gè)限定條件的問題就轉(zhuǎn)化為一個(gè)d-KCA的問題了驶社。

1.B選擇隱秘的α，計(jì)算E(α*Fi）并發(fā)送給A

2.A計(jì)算E(αF)回傳給B

3.B根據(jù)本文公式自行計(jì)算E(F)并校驗(yàn)α對

2.防止暴力破解

在現(xiàn)在的流程里面测萎，A需要把E(L(s)),E(R(s)),E(O(s))亡电，根據(jù)同態(tài)隱藏的特性，根據(jù)這些值無法倒推原多項(xiàng)式硅瞧。但是如果需要驗(yàn)證的問題份乒，解不多的情況下，B還是可以通過窮舉的方式暴力破解原問題腕唧，得到A的原始數(shù)據(jù)或辖。例如我們已知A有兩個(gè)正整數(shù)，要求盲驗(yàn)證這兩個(gè)正整數(shù)的乘積是12枣接，那么B完全可以窮舉乘積是12的所有正整數(shù)組合颂暇，正向執(zhí)行驗(yàn)證過程，與E(L(s))但惶，E(R(s))和E(O(s))比對即可知道正確的答案是什么耳鸯。

當(dāng)然，我們也有解決辦法膀曾。解決思路就是在生成L县爬，R，O的時(shí)候引入隨機(jī)偏置

因?yàn)?/p>

令

新的組合

任然可以通過多項(xiàng)式的校驗(yàn)添谊，而因?yàn)锽不知道隨機(jī)數(shù)财喳，也無法通過暴力破解的方式知曉原始參數(shù)。

3.乘法同態(tài)

匹諾曹協(xié)議的最后一步斩狱，B需要檢驗(yàn)E(L(s)*R(s)-O(s))=E(H(s)*T(s))耳高，而事實(shí)上，我們之前只提到E(x)滿足加法同態(tài)喊废，B是無法通過E(H(s))計(jì)算出E(H(s)*T(s))的祝高。

解決辦法需要回歸到我們的數(shù)學(xué)工具上，我們需要用到橢圓曲線配對的特性污筷，這里說來話長工闺，本文只給出結(jié)論。通過橢圓曲線配對瓣蛀，我們可以得到一個(gè)弱化版的乘法同態(tài)陆蟆。

定義E1(x):=x?g,E2(x):=x?h,E(x):=x?g，因?yàn)槿齻€(gè)函數(shù)都是橢圓曲線惋增，自然分別都符合加法同態(tài)叠殷，同時(shí)橢圓曲線配對特性可以保證我們能通過E1(x)，E2(y)計(jì)算E(xy)诈皿。

4.減少交互

最后一個(gè)問題也是最關(guān)鍵的一個(gè)問題是林束，匹諾曹協(xié)議中需要A和B之間做很多的消息交互像棘，而在區(qū)塊鏈中，我們想要做到的是“公開認(rèn)證”壶冒。最理想的情況就是只要A把證據(jù)作為一個(gè)字符串放置到鏈上缕题，任何人都能驗(yàn)證結(jié)論。

可惜的是胖腾，實(shí)際上這種嚴(yán)格意義上的零交互證明已經(jīng)被證明不能滿足所有的證明場景烟零。我們退而求其次，采用了一種稱為CRS（COMMON REFERENCE STRING）的方式咸作。原理很簡單锨阿，實(shí)際上就是把隨機(jī)數(shù)α和s內(nèi)置于“系統(tǒng)”中。

所以終極版的zkSNARK過程就是：

0.配置α和s记罚，以之計(jì)算 (E1(1),E1(s),…,E1(sd),E2(α),E2(αs),…,E2(αsd))E2(α),并公示

1.A使用公示參數(shù)計(jì)算驗(yàn)證多項(xiàng)式

2.B校驗(yàn)多項(xiàng)式墅诡，乘法同態(tài)部分利用橢圓曲線配對的特性完成，形如E(αx)=Tate(E1(x),E2(α))

當(dāng)然CRS有一個(gè)極其嚴(yán)重的問題就是毫胜，“系統(tǒng)”內(nèi)建的隨機(jī)參數(shù)非常重要书斜，知道這個(gè)秘密參數(shù)的人就擁有超級管理員的權(quán)限诬辈，可以任意制造偽幣酵使，這在一個(gè)去中心化的系統(tǒng)中幾乎是不可接受的。

事實(shí)上焙糟，ZCash的系統(tǒng)參數(shù)采用了一種影視劇中經(jīng)常出現(xiàn)的橋段去“保護(hù)”這個(gè)不應(yīng)該也不需要由任何人掌握的配置數(shù)據(jù)口渔。選擇世界各地六個(gè)可信任的人，每人生成密鑰一部分穿撮，六個(gè)人的密碼拼接在一起生成公示的數(shù)據(jù)后缺脉，再分別銷毀掉各自手上的密鑰。除非六人合謀作弊悦穿，否則沒有人擁有超級管理員的權(quán)限攻礼。

參考文獻(xiàn)

ZCash7篇，有社區(qū)翻譯版栗柒，但還是推薦看原汁原味的? ? ?https://z.cash/blog/snark-explain.html

Vitalik3篇礁扮，小天才作者我就不介紹了，這三篇介紹得也是很透徹

https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627

https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6

一篇不錯(cuò)的中文介紹材料?http://news.btc123.com/news/detail?id=8125

libsnark開源庫地址?https://github.com/scipr-lab/libsnark