非交互式零知識證明

本節(jié)主要介紹一種新的零知識證明-$zkSNARK$，$zkSNARK：zero?knowledgeSuccinctNon?InteractiveArgumentsofKnowledge$。

背景

$zkSNARK$是零知識證明中最經(jīng)典的加密算法體系。目前已經(jīng)被應(yīng)用在很多地方，特別是在區(qū)塊鏈領(lǐng)域，包括實際生活中隱私保護相關(guān)的應(yīng)用。

$Zero?Knowledge$: 零知識證明體系里有兩個角色，一個是證明者(Prover)， 一個是驗證者(Verifier)。舉個例子，比特幣創(chuàng)始人中本聰身份不明，之前傳出過很多人聲稱自己是中本聰最后都不了了之。那么一個人如何證明自己是中本聰呢？因為大家知道中本聰錢包的地址。因此他只需要用這個錢包的私鑰對這句話簽名 “我是XXX，我其實就是中本聰"。然后其他人(Verifier) 都可以用中本聰錢包的公鑰對這個簽名進行驗證。這個就是一個零知識證明。首先只有私鑰持有方的簽名才能通過驗證，其次這個簽名沒有泄漏私鑰的任何信息，錢包不會被其他人盜用。因此零知識證明解決了兩個問題，一個是信任問題，一個是隱私問題。

$Succinct$：是指對于一個很復(fù)雜的問題，驗證者可能需要進行很長時間的計算才能提供出相應(yīng)的證明，但是我們希望證明的大小不要太大 (比如實際應(yīng)用中只有幾十$kb$)，同時驗證者只需要很少的時間(比如微秒級別的時間) 就能夠驗證計算是否正確。

$Non?Interactive$：是指在證明的過程中雙方不需要互相交換信息。有一些算法體系需要證明者和驗證者之間互相對話幾次，交換信息。這對于實際應(yīng)用就很不方便，增加了系統(tǒng)特別是網(wǎng)絡(luò)通訊的復(fù)雜度。因此最好的情況是證明者一次性地把證明發(fā)送給驗證者，驗證者直接驗證即可。

$ArgumentofKnowledge$：指的是證明者只有知道問題的答案才可能提供證明。這個比較繞口，另一個解釋就是證明者造假成功的概率可以忽略不計。這里還有一個類似的概念 Proof of Knowledge。它們之間是有區(qū)別的。對于Argument來說，證明者的計算能力有限，也就是多項式的算力，而Proof of Knowledge則對證明者計算能力沒有要求。比如一個驗證者是從未來穿越回來，帶著最先進的量子計算機，那么對于Proof of Knolwege的系統(tǒng)，他仍然沒法造假。但是對于Argument of Knowledge的系統(tǒng)則有可能。簡單的說就是：proof（證明）和argument（論證）在零知識證明里，是有區(qū)別的，在proof system中，即便是計算能力無限的prover也沒法欺騙verifier去相信一個錯誤的陳述為真（統(tǒng)計可靠性），而在argument system中，只有多項式時間計算能力的沒法欺騙（計算可靠性），假設(shè)能破解橢圓曲線離散對數(shù)問題，那么可能就不再安全。

多項式知識的證明（Proving Knowledge of a Polynomial）

我們從一個證明多項式知識的問題開始，然后使用一般方法。我們還會發(fā)現(xiàn)多項式的其他性質(zhì)。

到目前為止，問題集中在一個薄弱的證明概念上，各方必須相互信任。例如，證明者不需要知道多項式，他可以使用任何其他可用的方法來得出正確的結(jié)果。而且，如果驗證者多項式求值的范圍并不大，她可能有概率會猜到一個數(shù)，這個概率是無法忽視的。接下來我們來處理這個缺陷，但首先要清楚的分析多項式的性質(zhì)。一個多項式表達形式如下（n階多項式）：
$$c_n{x}^n+...+c_1{x}^1+c_0{x}^0$$
如果證明者或者驗證者知道是1階多項式（$c_1{x}^1+c_0$），那意味著他們知道該多項式系統(tǒng)為$c_1,c_0$，而且系數(shù)可能為任意值。代數(shù)基本定理指出，任何多項式都可以分解成線性多項式(即，1階多項式代表一條直線)，只要它是可解的。因此，我們可以將任何有效多項式表示為線性多項式的乘積：
$$(x?a_0)(x?a_1)...(x?a_n)=0$$
從上式看出一個多項式可以由多個1階多項式組成。例如多項式$x^3?3x^2+2x$分解為$(x?0)(x?1)(x?2)$。從分解的多項式可以明顯的看出解為$0,1,2$，你可以很容易地在多項式的任意一種形式上檢查這個解，但是分解形式在表面上有所有以上的解(也稱為根)。

假設(shè)證明者聲明，他知道一個3次多項式的根是1和2，這意味著他的多項式具有這種形式：$(x?1)(x?2)...$，換句話說，$(x?1)$和$(x?2)$可以看作多項式$x^3?3x^2+2x$的余子式。因此，如果證明者想要證明他聲明的多項式有這些根，但又不想揭露多項式本身，他需要證明他的多項式$p(x)$是這些余子式$t(x)=(x?1)(x?2)$的乘積，所以存在任意多項式$h(x)$有以下形式：
$$p(x)=t(x)h(x)$$
因此，多項式多項式$p(x)$是由多項式$t(x)$和多項式$h(x)$乘積等到，多項式$p(x)$包含多項式$t(x)$。

如何得到多項式$h(x)$，這里我們很自然想到$h(x)=\frac{p(x)}{t(x)}$，如果證明者不能找到多項式$h(x)$，這意味著多項式$p(x)$并沒有多項式$t(x)$余子式，這也以為多項式除法有余數(shù)。這里舉個小例子：$p(x)=x^3?3x^2+2x$，$t(x)=(x?1)(x?2)=x^2?3x+2$，這里很容易得到$h(x)=x$。

證明者和驗證者具體驗證協(xié)議如下：

• 驗證者隨機選取一個值$r$，計算$t=t(r)$，并把$r$發(fā)送給證明者
• 證明者計算$h(x)=\frac{p(x)}{t(x)}$，將$p(r)$和$h(r)$值發(fā)送給驗證者
• 驗證者檢查$p=t\times h$，如果多項式相等，意味著多項式$p(x)$有$t(x)$余子式

這里還需要介紹一種情況，如果證明者使用不同的$p\prime (x)$，它沒有必要的代數(shù)余子式,，例如：$p\prime (x)=2x^3?3x^2+2x$，這里我們可以得到$p\prime (x)=t(x)\times (2x+3)+7x?6$。因此證明者整除將會有余數(shù)，所以我們將式子$p\prime (x)=t(x)\times (2x+3)+7x?6$整除$t(x)$得到$h(x)=2x+3+\frac{7x?6}{t(x)}$。因為x是由驗證者隨機選擇的,有一個低概率概率余數(shù)$7x?6$被$t(x)$整除,如果驗證者檢查$p(x),h(x)$必須是整數(shù),這樣的證明將被拒絕。但是，該檢查要求多項式系數(shù)也是整數(shù)，這對協(xié)議造成了很大的限制。因此，這就是引入密碼原語的原因，這使得這種除法不可能實現(xiàn)，即使原始的計算結(jié)果碰巧是可除的。

問題（issues）

• 證明者可能不知道聲明的多項式$p(x)$，他可以計算$t=t(r)$，并選擇一個隨機數(shù)$h$，計算$p=t\times h$，驗證者接收到值是正確的。
• 證明者知道隨機點$x=r$，他能構(gòu)造任意多項式在$r$處有一個共享點與$t(r)\times h(r)$。
• 在初始情況下，證明者聲稱知道一個特定次數(shù)的多項式，在當前的協(xié)議中沒有階數(shù)的強調(diào)。因此，證明者可以利用一個滿足余子式檢查的高次多項式進行欺騙。

這里說明一下，零知識證明的研究方向，本文主要一環(huán)扣一環(huán)的講解，希望有興趣的朋友能耐心讀下去。文章來源地址http://www.zghlxwxcb.cn/news/detail-806665.html

到了這里，關(guān)于零知識證明學習（三）—— 非交互式零知識證明(zkSNARKs)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！