零知識(shí)證明研究綜述

摘要：文章論述了密碼學(xué)的新領(lǐng)域——零知識(shí)證明的概念、方法、算法、應(yīng)用，以及其在區(qū)塊鏈領(lǐng)域的若干應(yīng)用。

關(guān)鍵詞：密碼學(xué)；公鑰密碼學(xué)；隱私計(jì)算；零知識(shí)證明；區(qū)塊鏈應(yīng)用

doi：10.3969/J.ISSN.1672-7274.2023.06.025

中圖分類(lèi)號(hào)：TP 311.13" " " " " "文獻(xiàn)標(biāo)志碼：A" " " " " " "文章編碼：1672-7274（2023）06-00-03

Abstract： This paper discusses the concept， method， algorithm and application of zero-knowledge proof， a new field of cryptography， as well as its applications in the blockchain field.

Key words： cryptography; public key cryptography; privacy computing; zero knowledge proof; blockchain applications

1" 零知識(shí)證明的概念

零知識(shí)證明是某種權(quán)益的擁有者，即知道問(wèn)題的解w的人在不泄露任何有關(guān)問(wèn)題的相關(guān)信息的情況下，能證明其確實(shí)掌握有w。

1.1 注解

我們有兩個(gè)角色方，證明者（簡(jiǎn)稱(chēng)P）和驗(yàn)證者（簡(jiǎn)稱(chēng)V），以及對(duì)兩個(gè)角色方來(lái)說(shuō)不是秘密的NP關(guān)系R、問(wèn)題x及答案w這三個(gè)對(duì)象滿(mǎn)足公式：

R（x，w）=1" " " " " " " " " " " " " " " " " " " " " " "（1）

證明者知道問(wèn)題的答案x，他需要向驗(yàn)證者證明他知道問(wèn)題x以及問(wèn)題的答案w，但不泄露關(guān)于w的任何信息。

以上描述等價(jià)于證明滿(mǎn)足以下三個(gè)屬性：

（1）完備性。此證明完成后能夠讓驗(yàn)證者確信證明者沒(méi)有說(shuō)謊，或者說(shuō)證明者確實(shí)握有問(wèn)題x的某個(gè)解w。

（2）合理性。證明者不擁有x的某個(gè)解w，則不能令驗(yàn)證者相信他擁有問(wèn)題x的某個(gè)解。

（3）零知識(shí)性。證明過(guò)程不能泄露關(guān)于w的任何信息。

下面給出零知識(shí)證明這一概念的較為數(shù)學(xué)化的定義。

1.2 定義

考慮等式R（x，w）=1，這里x是一個(gè)數(shù)學(xué)問(wèn)題，w是該問(wèn)題的未知的解，也即w滿(mǎn)足x所定義的若干關(guān)系，R是判斷w是否滿(mǎn)足這些關(guān)系的判定程序，我們還要求R（x，w）=1是一個(gè)NP問(wèn)題，即求解w很難，但驗(yàn)證w是該問(wèn)題的解是容易的。

1.3 注解

在這里，容易和困難的界定是由算法的時(shí)間復(fù)雜度決定的，即能否能在多項(xiàng)式時(shí)間內(nèi)解決問(wèn)題，即算法的時(shí)間復(fù)雜度是否低于多項(xiàng)式的維度。

對(duì)早期的零知識(shí)證明的協(xié)議來(lái)說(shuō)，很多是必須要求證明是某種交互輸入，例如下節(jié)給出的三色問(wèn)題的一個(gè)零知識(shí)證明方案。這種交互式證明是從概率角度進(jìn)行的，而不是通常的推理式證明，以一方或多方進(jìn)行挑戰(zhàn)的方式進(jìn)行，使得證明者和驗(yàn)證者在完成交互后確信證明者的陳述是真實(shí)的，即證明者確實(shí)握有此想要保密的信息[1]。

2" 交互式證明系統(tǒng)

交互式證明是自然的零知識(shí)證明實(shí)現(xiàn)方式，早期的零知識(shí)證明都采用此種形態(tài)。

2.1 定義

交互式證明系統(tǒng)是采用證明者和驗(yàn)證者之間的互動(dòng)式通信的方式完成證明的系統(tǒng)。直觀(guān)上說(shuō)就是設(shè)計(jì)一個(gè)協(xié)議完成語(yǔ)言L(fǎng)的交互式計(jì)算，使得當(dāng)x∈L時(shí)，證明者可以給出使驗(yàn)證者相信的證明，當(dāng)xL時(shí)，任何證明者都不能使驗(yàn)證者相信，無(wú)論證明者擁有多強(qiáng)的算力。

能被交互式證明系統(tǒng)（Poly Round）解決的問(wèn)題類(lèi)記為IP。

2.2 注解

交互式證明系統(tǒng)的一大弊端是無(wú)法阻止證明者和驗(yàn)證者之間串通從而篡改結(jié)論。在1988年，Goldwasser et al.在IP的基礎(chǔ)上提出了MIP。MIP也是一種交互式證明系統(tǒng)，但它的流程中多了一個(gè)證明者，而兩個(gè)證明者之間不存在任何交流的方式，其作用是讓作弊變得更困難。

隨后，MIP=NEXPTIME被Babai等人證明得出。特別地，在MIP系統(tǒng)范疇下，不需要有任何另外的假設(shè)，任意的NP問(wèn)題均有零知識(shí)證明。

這類(lèi)問(wèn)題的研究，將零知識(shí)證明中的計(jì)算和一般的計(jì)算復(fù)雜性理論相結(jié)合，甚至進(jìn)而影響到簡(jiǎn)潔電路相關(guān)的問(wèn)題。這些成果推動(dòng)了相關(guān)知識(shí)體系的構(gòu)建，成為了零知識(shí)證明理論研究的部分基礎(chǔ)。

3" 圖的三色問(wèn)題的零知識(shí)證明

下來(lái)我們以一個(gè)簡(jiǎn)單的例子說(shuō)明零知識(shí)證明的過(guò)程。

3.1 定義

所謂圖的三染色問(wèn)題，指的是將一張圖上的頂點(diǎn)用三種不同顏色進(jìn)行染色，使得對(duì)于任意一對(duì)具有相鄰關(guān)系的頂點(diǎn)用特定的顏色表示：它們的顏色不同。

我們通過(guò)零知識(shí)證明的方式來(lái)向別人證明我們有一張圖的三染色問(wèn)題的解。在這里，我們需要確定以下兩個(gè)前提。

（1）如果證明方本身無(wú)法知道如何進(jìn)行三染色，那么就會(huì)被驗(yàn)證方知道，從而導(dǎo)致證明失敗。

（2）在全部證明過(guò)程中，驗(yàn)證方始終不知道三染色的具體方案。

我們先考慮一次的試驗(yàn)過(guò)程。驗(yàn)證方會(huì)從圖中任意取一條邊查看染色情況，而作為證明方，在每一次的取邊之后都需要依據(jù)本身自己的染色結(jié)果，告知驗(yàn)證方所取的邊的兩個(gè)頂點(diǎn)的染色情況。根據(jù)程序的反饋，如果出現(xiàn)一次相同的結(jié)果，則說(shuō)明證明方作假[2]。具體的驗(yàn)證過(guò)程表示如下，其過(guò)程需要重復(fù)足夠多的次數(shù)。

①證明方向驗(yàn)證方告知自己擁有染色結(jié)果，讓驗(yàn)證方尋求驗(yàn)證。

②證明方借助承諾方案，將該染色的結(jié)果遞交給驗(yàn)證方。

③驗(yàn)證方隨機(jī)取邊，將邊的要求告知證明方，隨后證明方揭示該邊對(duì)應(yīng)兩點(diǎn)的染色方案。

④假若該點(diǎn)染色方案滿(mǎn)足條件，則驗(yàn)證方重復(fù)上述步驟，直到驗(yàn)證方相信證明方確實(shí)擁有結(jié)果。

這樣的驗(yàn)證次數(shù)需要重復(fù)足夠多次，直到驗(yàn)證方愿意相信證明方擁有染色方案這一命題，此即完成證明。作為驗(yàn)證方而言，其自始至終并沒(méi)有掌握整個(gè)圖的染色方法，但是依然得到了證明方擁有此張圖三染色問(wèn)題解這一信息。

我們考慮這樣做的數(shù)學(xué)依據(jù)，該方法的合理性證明如下。

證明：假設(shè)需要驗(yàn)證的圖上有|E|條邊。如果證明方欺騙驗(yàn)證方，那么因?yàn)榻Y(jié)果方每次試驗(yàn)取邊隨機(jī)，對(duì)每一次的驗(yàn)證，驗(yàn)證者被發(fā)現(xiàn)作弊的概率為，按照重復(fù)獨(dú)立試驗(yàn)問(wèn)題模型，我們得出N次獨(dú)立重復(fù)測(cè)試下，被抓住作弊的概率是：

P（第i次試驗(yàn)被抓包，ilt;N）≤1－

P（N次試驗(yàn)均未被抓包）≤（1－）N" " " " "（2）

因?yàn)閨E|是有限的，而驗(yàn)證次數(shù)在結(jié)果方相信前會(huì)一直進(jìn)行下去，如果有欺詐，最終未被抓包的概率無(wú)限趨向于零，驗(yàn)證方總能夠抓住證明方的欺騙情形。因此，在進(jìn)行足夠多的次數(shù)之后，驗(yàn)證方完全以較大的置信度相信結(jié)果的正確性。

3.2 注解

結(jié)果方似乎可以通過(guò)遍歷選擇圖上的所有點(diǎn)，來(lái)實(shí)現(xiàn)對(duì)整個(gè)圖三染色結(jié)果的認(rèn)知，而實(shí)際上這一點(diǎn)無(wú)法實(shí)現(xiàn)。在每一次的重復(fù)試驗(yàn)過(guò)程中，由于承諾協(xié)議的存在，結(jié)果方無(wú)法確切定位是具體哪一條邊，從而其無(wú)法擁有對(duì)整張圖染色情況的了解。而同樣由于這一點(diǎn)，驗(yàn)證方無(wú)法改變?nèi)旧绞奖旧韽亩斐善墼p。

4nbsp; 承諾協(xié)議

承諾（Commitment）是現(xiàn)代密碼學(xué)中的重要概念，在隱私計(jì)算的各種協(xié)議中都是必要的組成。

密碼學(xué)中的承諾[3]分為兩個(gè)階段。在第一階段中，承諾者需要提供一個(gè)加密后的信息給接收者，以證明自己未對(duì)信息進(jìn)行更改。第二階段中，承諾者將消息與密鑰公開(kāi)，以便接收者驗(yàn)證自己所得到的消息是否與之前一致。

該協(xié)議有兩個(gè)性質(zhì)：binding和hiding，其中binding保證了第一階段中若承諾者有惡意，則第二階段驗(yàn)證中無(wú)法通過(guò)；hiding保證了接收者在承諾方公開(kāi)消息前，無(wú)法將所得消息泄露。

Pederson Commitment滿(mǎn)足如下的數(shù)學(xué)結(jié)構(gòu)：

式中，r為ZP中的數(shù)；p為大素?cái)?shù)。

由于r的選取本身的隨機(jī)性，其具有完美隱藏性特性，以及基于離散對(duì)數(shù)假設(shè)的完美綁定性，在數(shù)值驗(yàn)證和審計(jì)計(jì)算中多為常見(jiàn)。

承諾的實(shí)現(xiàn)過(guò)程表示如下：

（1）選擇階為大素?cái)?shù)p的乘法循環(huán)群ZP、由兩個(gè)生成元分別生成。

G=lt;ggt;=lt;hgt;" " " " " " " " " " " " " " " " " " " " " " " （4）

隨后對(duì)三元組（g，h，p）進(jìn)行公開(kāi)。

（2）承諾者隨機(jī)選擇一個(gè)正整數(shù)r，計(jì)算相應(yīng)的數(shù)乘作為承諾者的承諾值，發(fā)送n給接收者。

（3）承諾者傳遞數(shù)據(jù)（m，r）給接收者，接收者通過(guò)計(jì)算驗(yàn)證n=gmhrmod p的成立性來(lái)決定是否接受承諾。

與前面的方法類(lèi)似，可以將離散對(duì)數(shù)的構(gòu)造平移到橢圓曲線(xiàn)的阿貝爾群上。因?yàn)樗赜蛏隙x的橢圓曲線(xiàn)上點(diǎn)的加法交換群上的離散對(duì)數(shù)問(wèn)題的計(jì)算更為困難，未來(lái)可以期待保密性更好、計(jì)算量更小的橢圓曲線(xiàn)密碼協(xié)議[4]。

5" 多項(xiàng)式承諾

在數(shù)據(jù)傳輸?shù)念I(lǐng)域，多項(xiàng)式是重要的數(shù)據(jù)類(lèi)型之一。多項(xiàng)式承諾是很多零知識(shí)證明協(xié)議的必須概念。多項(xiàng)式承諾旨在滿(mǎn)足接收方在不知道多項(xiàng)式具體每一位的數(shù)值的情況下，實(shí)現(xiàn)多項(xiàng)式本身的接收。其簡(jiǎn)單的構(gòu)造方法如下。

（1） 最簡(jiǎn)單的d階多項(xiàng)式，可以隨機(jī)選擇一個(gè)點(diǎn)x，讓證明者通過(guò)計(jì)算多項(xiàng)式在點(diǎn)x處的取值生成y，驗(yàn)證者在可以查看y是否正確。不同的多項(xiàng)式，最多有d個(gè)相交的點(diǎn)。

（2）如果x/y的取值范圍很大（設(shè)為n），在不知道原始多項(xiàng)式的情況下，能正確給出證明的概率也比較低，為d/n。

（3）對(duì)于正常的多項(xiàng)式，能在一次交互中就能獲取比較好的安全系數(shù)，當(dāng)n遠(yuǎn)大于d的話(huà)，甚至可以將近1。

這種協(xié)議形式簡(jiǎn)單，其證明建立在雙方相互信任的基礎(chǔ)上。一般而言，證明者并不能讓驗(yàn)證者確信自己知道多項(xiàng)式，而證明者也并不能通過(guò)邏輯推理推斷出他知道一個(gè)確定的多項(xiàng)式。類(lèi)似地，僅僅知道多項(xiàng)式在一個(gè)整數(shù)上的取值，并不說(shuō)明知道這個(gè)多項(xiàng)式的所有取值也即知道多項(xiàng)式本身。而且，如果多項(xiàng)式的值域的范圍很小的話(huà)，存在證明者撞概率、胡亂證明卻蒙對(duì)的可能，也即有著作弊的可能性。

因?yàn)槎囗?xiàng)式的結(jié)構(gòu)本身的特殊性，長(zhǎng)時(shí)間以來(lái)，針對(duì)多項(xiàng)式協(xié)議的優(yōu)化和改進(jìn)一直是重要的研究方向。現(xiàn)如今，各種形式的多項(xiàng)式協(xié)議已在不同項(xiàng)目中大放異彩。

參考文獻(xiàn)

[1] 秦波．零知識(shí)證明與數(shù)字簽名理論的研究[D]．西安：西安理工大學(xué)，2003.

[2] 曹天杰，張永平，汪楚嬌．安全協(xié)議[M]．北京：北京郵電大學(xué)出版社，2009.

[3] 熊麗兵，董一凡，周小雪．區(qū)塊鏈應(yīng)用開(kāi)發(fā)指南：業(yè)務(wù)場(chǎng)景剖析與實(shí)戰(zhàn)[M]．北京：清華大學(xué)出版社，2021.

[4] 吳為．區(qū)塊鏈實(shí)戰(zhàn)[M]．北京：電子工業(yè)出版社，2020.