最近以太坊啟動(dòng)了“大都會(huì)”硬分叉宜雀，很重要的一個(gè)功能就是整合了ZCash的零知識(shí)證明技術(shù)zkSNARK辐董。我們一起來(lái)看一下zkSNARK這個(gè)拗口的技術(shù)到底是什么鬼简烘。
零知識(shí)證明
要了解zkSNARK孤澎，必須先理解什么是零知識(shí)證明覆旭。
關(guān)于零知識(shí)證明岖妄，概念并不難理解荐虐，我們以一個(gè)老掉牙的故事作為例子福扬。
阿里巴巴被強(qiáng)盜抓住忧换，為了保命，他需要向強(qiáng)盜證明自己擁有打開(kāi)石門(mén)的密碼酪耳，同時(shí)又不能把密碼告訴強(qiáng)盜碗暗。他想出一個(gè)解決辦法言疗，先讓強(qiáng)盜離開(kāi)自己一箭之地噪奄，距離足夠遠(yuǎn)讓強(qiáng)盜無(wú)法聽(tīng)到口令，足夠近讓阿里巴巴無(wú)法在強(qiáng)盜的弓箭下逃生都毒。阿里巴巴就在這個(gè)距離下向強(qiáng)盜展示了石門(mén)的打開(kāi)和關(guān)閉账劲。
這個(gè)整個(gè)過(guò)程就是零知識(shí)證明瀑焦，證明者能夠在不向驗(yàn)證者提供任何有用信息（石門(mén)的口令）的情況下榛瓮，使驗(yàn)證者相信某個(gè)論斷（阿里巴巴知道打開(kāi)石門(mén)的方法）是正確的榆芦。
當(dāng)然匆绣，現(xiàn)實(shí)生活中類似的應(yīng)用有很多什黑，大家可以參考阿里巴巴的零知識(shí)證明或者零知識(shí)證明愕把。
在計(jì)算機(jī)世界里面恨豁，零知識(shí)的應(yīng)用場(chǎng)景就更多了橘蜜，例如我們常用非對(duì)稱加密來(lái)做身份認(rèn)證，驗(yàn)證方只要使用公鑰解出自己提供的隨機(jī)數(shù)徽职，即可證明被認(rèn)證方的身份佩厚，不需要其提供自己的私鑰抄瓦。
以上例子都是針對(duì)特定場(chǎng)景的特定方法钙姊，比如說(shuō)石門(mén)不是通過(guò)口令控制而是通過(guò)實(shí)物鑰匙控制摸恍，這個(gè)方法就不可用了立镶，是否有一個(gè)通用方法去認(rèn)證任何事件呢媚媒？
zkSNARK
zkSNARK是zero-knowledge succint non-interactive arguments of knowledge的簡(jiǎn)稱缭召，全稱里面每個(gè)單詞都有特定的含義：
Zero knowledge：零知識(shí)證明嵌巷，見(jiàn)前文搪哪。
Succinctness：證據(jù)信息較短坪圾，方便驗(yàn)證
Non-interactivity：幾乎沒(méi)有交互兽泄，證明者基本上只要提供一個(gè)字符串義工驗(yàn)證病梢。對(duì)于區(qū)塊鏈來(lái)說(shuō)，這一點(diǎn)至關(guān)重要栈雳，意味著可以把該消息放在鏈上公開(kāi)驗(yàn)證哥纫。
Arguments：證明過(guò)程是計(jì)算完好（computationally soundness）的蛀骇，證明者無(wú)法在合理的時(shí)間內(nèi)造出偽證（破解）擅憔。跟計(jì)算完好對(duì)應(yīng)的是理論完好（perfect soundness)暑诸，密碼學(xué)里面一般都是要求計(jì)算完好个榕。
of knowledge：對(duì)于一個(gè)證明者來(lái)說(shuō)西采，在不知曉特定證明 (witness) 的前提下械馆，構(gòu)建一個(gè)有效的零知識(shí)證據(jù)是不可能的霹崎。
接下來(lái)冶忱，我們一步一步解釋這個(gè)zkSNARK到底是怎么實(shí)現(xiàn)的。
同態(tài)隱藏
說(shuō)到zkSNARK朗和，不能不提的一個(gè)概念就是同態(tài)隱藏错沽，說(shuō)它是zkSNARK的核心技術(shù)一點(diǎn)都不為過(guò)。
滿足下面三個(gè)條件的函數(shù)E(x）眶拉，我們稱之為加法同態(tài)千埃。
1.對(duì)于大部分的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).來(lái)計(jì)算E(x+y)蜈缤。
同理我們可以定義乘法同態(tài)甚至是全同態(tài)。
我們常用的的非對(duì)稱加密方式RSA和ECC都支持加法同態(tài)冯挎，計(jì)算和證明證明需要比較多的公式運(yùn)算底哥，有時(shí)間另外開(kāi)一篇文章講解。
跟RSA和ECC一樣房官，注意這里的E(x)計(jì)算是在有限域里面進(jìn)行趾徽，這個(gè)域下文稱為Fp。
有了同態(tài)隱藏這個(gè)利器以后翰守，我們就可以實(shí)現(xiàn)一定程度的零知識(shí)證明了孵奶。
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可以通過(guò)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)的特性肖爵，我們可以簡(jiǎn)單的把零知識(shí)證明推廣到多項(xiàng)式中。
假定A知道一個(gè)最高d次的多項(xiàng)式P臀脏，而B(niǎo)想要知道對(duì)應(yīng)某個(gè)s的E(P(s))
我們希望在驗(yàn)證的過(guò)程中劝堪，A只知道P，不知道s揉稚，B只知道s秒啦，不知道P，可以通過(guò)下面方式實(shí)現(xiàn)：
1.對(duì)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è)致命的問(wèn)題即舌，就是B根本沒(méi)法驗(yàn)證A是真正利用多項(xiàng)式P(s)去計(jì)算結(jié)果，也就是說(shuō)無(wú)法證明A真正知道這個(gè)多項(xiàng)式P(X)挎袜。我們繼續(xù)完善一下上面的驗(yàn)證顽聂。
我們先定義一個(gè)概念：α對(duì)是指滿足b=α*a的一對(duì)值（a肥惭，b）。注意這里的乘法其實(shí)是橢圓曲線（ECC）上的乘法紊搪，橢圓曲線上的運(yùn)算符合兩個(gè)特性：一是當(dāng)α值很大的情況下蜜葱，很難通過(guò)a和b倒推出α，二是加法和乘法滿足可交換群的特性耀石，也就是說(shuō)加法和乘法交換律在橢圓曲線上也是成立的牵囤。橢圓曲線的運(yùn)算很復(fù)雜，本文暫不詳述娶牌，大家只要記住橢圓函數(shù)的乘法滿足同態(tài)隱藏的特性奔浅，即可完成下面的證明。
我們利用α對(duì)的特性诗良，構(gòu)建一個(gè)稱為KCA（Knowledge of Coefficient Test and Assumption）的過(guò)程
1.B隨機(jī)選擇一個(gè)α生成α對(duì)（a芙盘，b），α自己保存扔水，（a廷没，b）發(fā)送給A
2.A選擇γ，生成(a′,b′)=(γ?a,γ?b)径荔，把(a′,b′)回傳給B督禽。利用交換律，可以證明(a′,b′)也是一個(gè)α對(duì)总处，b′=γ?b=γα?a=α(γ?a)=α?a′
3.B校驗(yàn)(a′,b′)狈惫，證實(shí)是α對(duì)，就可以斷言A知道γ
這個(gè)證明可以推廣到多個(gè)α對(duì)的場(chǎng)景鹦马，稱為d-KCA
1.B發(fā)送一系列的α對(duì)給A
2.A使用(a′,b′)=(c1?a1+c2?a2,c1?b1+c2?b2)生成新的α對(duì)
3.B驗(yàn)證通過(guò)胧谈，可以斷言A知道c數(shù)組
這個(gè)KCA咋看似乎沒(méi)有什么用，但正好可以補(bǔ)足了之前多項(xiàng)式盲驗(yàn)證 的缺陷荸频，一個(gè)完整的多項(xiàng)式盲驗(yàn)證過(guò)程如下
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í)際上過(guò)程同上一章的第一步旭从，只是把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值必然是通過(guò)多項(xiàng)式生成
好了退疫，到這里喘口氣，回顧一下我們現(xiàn)在到底做到了些什么鸽素。
通過(guò)加法同態(tài)蹄咖，我們可以實(shí)現(xiàn)加法隱藏，讓B在不知道x和y的情況下付鹿，校驗(yàn)x+y的值澜汤。進(jìn)一步蚜迅，通過(guò)多項(xiàng)式盲驗(yàn)證，我們可以在不暴露多項(xiàng)式P(X)的情況下俊抵，讓B校驗(yàn)任意給定s對(duì)應(yīng)的P(s)谁不。
接下來(lái)坐好扶穩(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需要對(duì)B保密秩命。
我們要做的第一步就是把計(jì)算“拍平”尉共，通過(guò)基本的運(yùn)算符把原計(jì)算畫(huà)成這樣的“計(jì)算門(mén)電路”。
當(dāng)然我們也可以用程序員比較熟悉的方式來(lái)表達(dá)
S1=C1*C2
S2=C1+C3
S3=S1*S2
通過(guò)增加中間變量弃锐，我們把復(fù)雜的計(jì)算拍平袄友，使用最簡(jiǎn)單的門(mén)電路表達(dá)。新的門(mén)電路跟原計(jì)算是等價(jià)的霹菊。
我們要做的第二步就是把每一個(gè)門(mén)電路表示為等價(jià)的向量點(diǎn)積形式剧蚣，這個(gè)過(guò)程成為R1CS（rank-1 constraint system）。
對(duì)每個(gè)門(mén)電路旋廷，我們定義一組向量（a,b,c）鸠按，使得s . a * s . b - s . c = 0。其中s代表全部輸入的向量柳洋，也就是[C1,C2,C3,S1,S2,S3]待诅，為了讓加法門(mén)也能用同樣的方式表達(dá)叹坦，我們?cè)黾右粋€(gè)虛擬的變量成為one熊镣，s向量變成[one,C1,C2,C3,S1,S2,S3]。
對(duì)應(yīng)到第一個(gè)門(mén)
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è)門(mén)是完全等價(jià)的鬼吵。
同理我們可以計(jì)算第二個(gè)門(mén)
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è)門(mén)
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ì)算式拍平成為門(mén)電路齿椅，接著又通過(guò)R1CS把門(mén)電路“編碼”成向量的表達(dá)方式琉挖。
接下來(lái)是最重要的一步，把向量表達(dá)式表示為多項(xiàng)式涣脚，從而把向量的驗(yàn)證轉(zhuǎn)化為多項(xiàng)式的驗(yàn)證示辈，這個(gè)過(guò)程稱為QAP（Quadratic Arithmetic Programs）。
具體辦法是遣蚀，在Fp上面選定任意三個(gè)不同的值矾麻，例如我們選定1，2芭梯，3险耀，尋找一組多項(xiàng)式
使得多項(xiàng)式在x取值1，2玖喘，3的時(shí)候a甩牺，b，c數(shù)組的取值分別對(duì)應(yīng)到前述三個(gè)門(mén)電路的向量芒涡。
問(wèn)題轉(zhuǎn)化為通過(guò)已知解倒推多項(xiàng)式定義柴灯，這部分可以使用拉格朗日插值完成，本文不再詳述费尽。這個(gè)過(guò)程中需要對(duì)向量的每個(gè)取值做拉格朗日插值赠群，對(duì)于復(fù)雜問(wèn)題，這個(gè)向量會(huì)非常龐大旱幼，計(jì)算過(guò)程會(huì)很復(fù)雜查描，這里可以利用快速傅里葉變換進(jìn)行優(yōu)化。
到這里柏卤，我們把原來(lái)的三個(gè)向量組表示成為一個(gè)用x表示的數(shù)組a(x),b(x),c(x)冬三。
取多項(xiàng)式P(x)=s . a(x) * s . b(x) - s . c(x)，根據(jù)我們?cè)瓉?lái)的定義缘缚，在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)整除齐媒，也就是說(shuō)存在H（X）蒲每，使P(x)=T(x)*H(x)，其中T(x)=(x-1)(x-2)(x-3)喻括。
注意QAP這個(gè)過(guò)程把原來(lái)三個(gè)點(diǎn)的取值轉(zhuǎn)化成為一個(gè)多項(xiàng)式邀杏，相當(dāng)于中間插入了很多沒(méi)有意義的值，這些值的取值與原公式是無(wú)關(guān)的唬血。也就是說(shuō)多項(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é)議
通過(guò)QAP状您，我們已經(jīng)把計(jì)算式的證明轉(zhuǎn)化為多項(xiàng)式的證明勒叠，現(xiàn)在萬(wàn)事具備，只欠東風(fēng)膏孟，就差一個(gè)完整的驗(yàn)證流程了眯分。
為了簡(jiǎn)化下文描述，我們定義s . a(x)為L(zhǎng)(x)柒桑，s . b(x)為R(x)弊决，s . c(x)為O(x)，那么我們需要證明的等式就改寫(xiě)成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來(lái)說(shuō)很小的情況下息拜，我們可以采用采樣的方式驗(yàn)證多項(xiàng)式相等溉潭，A隨意選擇多項(xiàng)式P(x)被校驗(yàn)通過(guò)的概率只有2d/p。隨機(jī)采樣校驗(yàn)的過(guò)程如下：
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ā)過(guò)來(lái)的E(s)喳瓣，E(s2),...)
4.B檢驗(yàn)E(L(s)*R(s)-O(s))=E(H(s)*T(s))
這個(gè)證明過(guò)程還有四個(gè)問(wèn)題需要解決：
1.保證L,R,O從同一組參數(shù)s生成
這個(gè)證明過(guò)程存在一個(gè)缺陷，正如按照我們的定義L(x)=s . a(x)赞别，R(x)=s . b(x)畏陕，O(x)=s . c(x)，這里隱含了一個(gè)限定條件是L仿滔，R和O必須是由同一個(gè)向量s生成惠毁，證明中忽略了這一點(diǎn)，也就是說(shuō)A可以通過(guò)選擇不符合這個(gè)限定條件的多項(xiàng)式來(lái)作弊堤撵。解決辦法仍然是KCA仁讨，只不過(guò)這次的KCA要復(fù)雜一些羽莺。
先定義兩個(gè)公式：
這個(gè)公式的含義是要把L实昨，R，O的指數(shù)錯(cuò)開(kāi)盐固，如果L荒给，R丈挟，O真是從同一組s=[s1,....sm]生成的話，必然有
換句話說(shuō)志电，只要A能給出F和Fi的線性組合曙咽，即可證明L，R挑辆，O符合限定條件例朱。這個(gè)限定條件的問(wèn)題就轉(zhuǎn)化為一個(gè)d-KCA的問(wèn)題了。
1.B選擇隱秘的α鱼蝉，計(jì)算E(α*Fi）并發(fā)送給A
2.A計(jì)算E(αF)回傳給B
3.B根據(jù)本文公式自行計(jì)算E(F)并校驗(yàn)α對(duì)
2.防止暴力破解
在現(xiàn)在的流程里面洒嗤，A需要把E(L(s)),E(R(s)),E(O(s))，根據(jù)同態(tài)隱藏的特性魁亦，根據(jù)這些值無(wú)法倒推原多項(xiàng)式渔隶。但是如果需要驗(yàn)證的問(wèn)題，解不多的情況下洁奈，B還是可以通過(guò)窮舉的方式暴力破解原問(wèn)題间唉，得到A的原始數(shù)據(jù)。例如我們已知A有兩個(gè)正整數(shù)利术，要求盲驗(yàn)證這兩個(gè)正整數(shù)的乘積是12呈野，那么B完全可以窮舉乘積是12的所有正整數(shù)組合，正向執(zhí)行驗(yàn)證過(guò)程印叁，與E(L(s))际跪，E(R(s))和E(O(s))比對(duì)即可知道正確的答案是什么。
當(dāng)然喉钢，我們也有解決辦法姆打。解決思路就是在生成L，R肠虽，O的時(shí)候引入隨機(jī)偏置
因?yàn)?/p>
令
新的組合
任然可以通過(guò)多項(xiàng)式的校驗(yàn)幔戏，而因?yàn)锽不知道隨機(jī)數(shù)，也無(wú)法通過(guò)暴力破解的方式知曉原始參數(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是無(wú)法通過(guò)E(H(s))計(jì)算出E(H(s)*T(s))的。
解決辦法需要回歸到我們的數(shù)學(xué)工具上找颓，我們需要用到橢圓曲線配對(duì)的特性合愈，這里說(shuō)來(lái)話長(zhǎng)，本文只給出結(jié)論。通過(guò)橢圓曲線配對(duì)佛析，我們可以得到一個(gè)弱化版的乘法同態(tài)益老。
定義E1(x):=x?g,E2(x):=x?h,E(x):=x?g，因?yàn)槿齻€(gè)函數(shù)都是橢圓曲線寸莫，自然分別都符合加法同態(tài)捺萌，同時(shí)橢圓曲線配對(duì)特性可以保證我們能通過(guò)E1(x)，E2(y)計(jì)算E(xy)膘茎。
4.減少交互
最后一個(gè)問(wèn)題也是最關(guān)鍵的一個(gè)問(wèn)題是桃纯，匹諾曹協(xié)議中需要A和B之間做很多的消息交互，而在區(qū)塊鏈中披坏，我們想要做到的是“公開(kāi)認(rèn)證”慈参。最理想的情況就是只要A把證據(jù)作為一個(gè)字符串放置到鏈上，任何人都能驗(yàn)證結(jié)論刮萌。
可惜的是驮配，實(shí)際上這種嚴(yán)格意義上的零交互證明已經(jīng)被證明不能滿足所有的證明場(chǎng)景。我們退而求其次着茸，采用了一種稱為CRS（COMMON REFERENCE STRING）的方式壮锻。原理很簡(jiǎn)單，實(shí)際上就是把隨機(jī)數(shù)α和s內(nèi)置于“系統(tǒng)”中涮阔。
所以終極版的zkSNARK過(guò)程就是：
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)部分利用橢圓曲線配對(duì)的特性完成敬特，形如E(αx)=Tate(E1(x),E2(α))
當(dāng)然CRS有一個(gè)極其嚴(yán)重的問(wèn)題就是掰邢，“系統(tǒng)”內(nèi)建的隨機(jī)參數(shù)非常重要，知道這個(gè)秘密參數(shù)的人就擁有超級(jí)管理員的權(quán)限伟阔，可以任意制造偽幣辣之，這在一個(gè)去中心化的系統(tǒng)中幾乎是不可接受的。
事實(shí)上皱炉，ZCash的系統(tǒng)參數(shù)采用了一種影視劇中經(jīng)常出現(xiàn)的橋段去“保護(hù)”這個(gè)不應(yīng)該也不需要由任何人掌握的配置數(shù)據(jù)怀估。選擇世界各地六個(gè)可信任的人，每人生成密鑰一部分合搅，六個(gè)人的密碼拼接在一起生成公示的數(shù)據(jù)后多搀，再分別銷毀掉各自手上的密鑰。除非六人合謀作弊灾部，否則沒(méi)有人擁有超級(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開(kāi)源庫(kù)地址?https://github.com/scipr-lab/libsnark
