本文翻譯自zcash官方博客葛峻，講解zcash中所使用的zk-SNARKs的原理第四部分两波，此處是原文鏈接。友情提示：本文偏技術(shù)化击儡，適合對(duì)技術(shù)和數(shù)學(xué)非常感興趣的同學(xué)閱讀塔沃。
zkSNARK是zero-knowledge succint non-interactive arguments of knowledge的簡(jiǎn)稱(chēng)，意思是：簡(jiǎn)潔的非交互的零知識(shí)證明阳谍。
(本文授權(quán)BH好文好報(bào)群摘編蛀柴、轉(zhuǎn)載以及相關(guān)轉(zhuǎn)授權(quán)推文行為)
這一章建立在第二章和第三章基礎(chǔ)之上，我們將研究出一套可驗(yàn)證的多項(xiàng)式盲式計(jì)算協(xié)議矫夯。第五章鸽疾，我們將看到這套協(xié)議在構(gòu)造SNARKs中的作用，所以大家先忍忍训貌，很快就到SNARKs了制肮。
和第二章一樣，我們假設(shè)递沪，Alice有一個(gè)d次多項(xiàng)式P豺鼻，Bob選擇了一個(gè)隨機(jī)的s \in \mathbb{F}_p。我們想構(gòu)造這樣一個(gè)協(xié)議款慨，它允許Bob知道E(P(s))儒飒，并具有如下特點(diǎn)：
- 雙盲：Alice不能知道
s，同時(shí)Bob不能知道P - 可驗(yàn)證性：Alice在不知道
P的情況下蒙對(duì)E(P(s))的概率檩奠，必須很小桩了，小到可以忽略
這就是所謂的可驗(yàn)證的多項(xiàng)式盲式計(jì)算附帽。在第二章的協(xié)議中，我們實(shí)現(xiàn)了第一個(gè)特性井誉，但沒(méi)有實(shí)現(xiàn)第二個(gè)蕉扮。為了實(shí)現(xiàn)可驗(yàn)證性，我們需要一個(gè)KCA的擴(kuò)展版本颗圣。關(guān)于KCA慢显，第三章有講解。
可驗(yàn)證性和雙盲特性是非常有用的欠啤，因?yàn)檫@兩個(gè)特性荚藻，Alice可以決定在不知道s的情況下使用哪個(gè)多項(xiàng)式P。同時(shí)洁段，可以保證应狱，讓Alice在不知道s的情況，會(huì)給出一個(gè)正確的多項(xiàng)式祠丝。這個(gè)初心在后面的章節(jié)會(huì)越發(fā)清晰疾呻。
一個(gè)擴(kuò)展的KCA
我們?cè)诘谌轮v的KCA主要是說(shuō)：如果Bob給了Alice一個(gè)\alpha二元組(a, b = \alpha * a)，那么Alice可以生成一個(gè)新的\alpha二元組(a', b')写半，因此她就能知道一個(gè)c岸蜗，使得a' = c * a。換句話說(shuō)叠蝇，Alice知道a'和a之間的關(guān)系璃岳。
現(xiàn)在，假設(shè)Bob不是發(fā)送了一個(gè)二元組悔捶，而是發(fā)送了多個(gè)\alpha二元組(a_1, b_1, ..., (a_d, b_d))(都是同樣的\alpha)铃慷，那么，在Alice收到這些二元組之后蜕该，Alice需要生成另外的二元組(a', b')來(lái)完成這個(gè)挑戰(zhàn)犁柜。請(qǐng)記住，Alice必須要能在不知道\alpha的情況下完成這個(gè)挑戰(zhàn)堂淡。
就像我們?cè)诘谌驴吹降囊粯硬雒澹茏匀坏兀珹lice可以從這多個(gè)二元組中選擇一個(gè)(a_i, b_i)出來(lái)绢淀，然后乘以某個(gè)c萤悴， c \in \mathbb{F}_p^*; 如果(a_i, b_i)是\alpha二元組，那么(c* a_i, c*b_i)也一定是一個(gè)二元組更啄。不過(guò)稚疹，Alice有沒(méi)有別的方法生成\alpha二元組呢居灯？是否可以同時(shí)利用幾個(gè)收到的二元組生成一個(gè)新的祭务？
答案是肯定的内狗。例如，Alice可以選擇兩個(gè)值c_1, c_2 \in \mathbb{F}_p义锥，然后計(jì)算出一個(gè)二元組(a', b') = (c_1*a_1 + c_2*a_2, c_1*b_1 + c_2*b_2)柳沙。這個(gè)可以進(jìn)行簡(jiǎn)單的證明，只要a'不是0拌倍，那么這個(gè)二元組就是\alpha二元組：
b' = c_1*b_1+c_2 * b_2 = c_1\alpha*a_1 + c_2\alpha*a_2 = \alpha * (c_1*a_1+c_2*a_2) = \alpha * a'
更一般地赂鲤，Alice可以使用給定的d個(gè)二元組的任意線性組合，也就是：對(duì)于任意的c_1, ..., c_d \in \mathbb{F}_p柱恤，可以定義：
(a', b') = (\sum_{i=1}^d c_ia_i, \sum_{i=1}^dc_ib_i)数初。
注意，如果Alice用這個(gè)方法生成了她的\alpha二元組梗顺，她就會(huì)知道a'和a_1, ..., a_d之間的線性關(guān)系泡孩。也就是說(shuō)，她知道c_1, ..., c_d使得a'=\sum_{i=1}^d c_i*a_i
這個(gè)擴(kuò)展的KCA是指寺谤，Alice用這種方法生成二元組時(shí)仑鸥，只要她成功了，她就知道a'和a_1, ..., a_d之間的線性關(guān)系变屁。
更正式的表達(dá)是眼俊，假設(shè)G是一個(gè)大小為p的循環(huán)群，并且它的生成元是g粟关，那么G的d次系數(shù)知識(shí)假設(shè)(d-KCA)可以表述為：
d-KCA： 設(shè)Bob隨機(jī)選擇\alpha \in \mathbb{F}_p^*和s \in \mathbb{F}_{p'}疮胖，并把如下的\alpha二元組發(fā)送給Alice(g, \alpha*g), (s*g, \alpha s*g), ..., (s^d*g, \alpha s^d*g).如果Alice輸出了另一組\alpha二元組(a', b')，那么Alice就會(huì)得知c_0, ..., c_d \in \mathbb{F}_p使得\sum_{i=0}^d c_is^i*g = a'闷板。
請(qǐng)注意获列，在d-KCA中，Bob并沒(méi)有發(fā)送任意的\alpha二元組蛔垢，而是發(fā)送了有特定“多項(xiàng)式結(jié)構(gòu)” 的多項(xiàng)式击孩，這對(duì)于下面內(nèi)容有用。
可驗(yàn)證的盲式計(jì)算協(xié)議
假設(shè)我們的HH(同態(tài)隱藏函數(shù))是：E(x) = x * g鹏漆，g是上面循環(huán)群G的生成元巩梢。
由此，我們拿出我們的協(xié)議如下：
- Bob選擇了一個(gè)隨機(jī)的\alpha \in \mathbb{F}_{p'}^*艺玲，并把(1, s, ..., s^d)的隱藏?cái)?shù)(g, s*g, ..., s^d*g)括蝠，以及(\alpha, \alpha s, ..., \alpha s^d)的隱藏?cái)?shù)(\alpha*g, \alpha s*g, ..., \alpha s^d *g)發(fā)送給Alice
- Alice通過(guò)接收到的元素計(jì)算出a = P(s)*g以及b = \alpha P(s)*g，然后把結(jié)果發(fā)給Bob
- Bob驗(yàn)證一下b = \alpha * a饭聚，如果滿足這個(gè)等式忌警，則接受Alice
首先，提醒一下秒梳，在給定了P的系數(shù)之后法绵，P(s)*g是g, s*g, ..., s^d*g的線性組合箕速，\alpha P(s)*g是\alpha * g, \alpha s*g, ..., \alpha s^d *g的線性組合，那么朋譬，根據(jù)第二章的內(nèi)容盐茎，Alice的確是可以從Bob發(fā)送的信息中計(jì)算出這些值的。
其次徙赢，通過(guò)d-KCA我們知道字柠，在這整個(gè)過(guò)程中，Alice知道c_0, ..., c_d \in \mathbb{F}_p,使得a=\sum_{i=0}^d c_i s^i *g狡赐，因?yàn)?span id="8eekdq7" class="math-inline">a = P(s) *g窑业，所以Alice知道這么一個(gè)多項(xiàng)式P(X) = \sum_{i=0}^d c_i*X^i。也就是說(shuō)枕屉，假如Alice不知道這么個(gè)多項(xiàng)式数冬，她瞎蒙一個(gè)結(jié)果能通過(guò)Bob的驗(yàn)證的可能性極小。
總結(jié)一下搀庶，我們通過(guò)d-KCA得了一個(gè)可驗(yàn)證的多項(xiàng)式盲式計(jì)算協(xié)議拐纱，后面的章節(jié)中，我們將看看如何使用這些知識(shí)點(diǎn)構(gòu)建SNARK哥倔。
早贊聲明：為方便早贊秸架、避免亂贊，“BH好文好報(bào)群”為點(diǎn)贊者咆蒿、寫(xiě)作者牽線搭橋东抹，實(shí)行“先審后贊、定時(shí)發(fā)表”的規(guī)則沃测，也讓作品脫穎而出缭黔、速登熱門(mén)！加群微信：we01230123（天平）蒂破。
