Hacker Dōjō 密碼學(xué)專題一：5.1 Groth16證明系統(tǒng)
Hacker??Dōjō?Web3前沿技術(shù) workshop文稿
研究種類：密碼學(xué)-Groth16證明系統(tǒng)
資助金額：100 USDT
Bounty鏈接：https://dorahacks.io/zh/daobounty/146
Workshop回顧：?https://b23.tv/PBcuXYu
內(nèi)容貢獻(xiàn)者：密碼學(xué)專家?Lynndell
本項(xiàng)目由Hacker?Dōjō?資助，文章轉(zhuǎn)載請注明出處。
??學(xué)習(xí)量子計算、密碼學(xué)、Space等Web3前沿技術(shù)
??認(rèn)領(lǐng)Bounty，賺取賞金
??參與Hackathon，獲得資助
更多Web3精彩技術(shù)分享盡在Dōjō??
WeChat: @HackerDojo0
密碼學(xué)專題一課程安排
第一課：對稱加密?（DES、AES、五種加密模式）
第二課：哈希函數(shù)?（SHA2、SHA3、MiMC、Rescue、Poseidon）
第三課：群與公鑰加密?（群，橢圓曲線群，Diffie-Hellman密鑰交換，ElGamal加密）
第四課：數(shù)字簽名?（BLS、Schnorr、EdDSA、ECDSA）
第五課：零知識證明?（Sigma零知識證明、Groth16、PLONK）
第五課：Groth16證明系統(tǒng)
1 零知識證明基礎(chǔ)
?1.1 預(yù)備知識
交互式零知識證明：證明方P發(fā)送數(shù)據(jù)給驗(yàn)證方V，也需要驗(yàn)證方V發(fā)送數(shù)據(jù)給證明方P。與TCP/IP協(xié)議的交互式一樣。
非交互式證明：證明方P生成證明，發(fā)送給驗(yàn)證方V；驗(yàn)證方V驗(yàn)證一致性即可。該過程沒有其他額外的數(shù)據(jù)交互。與用戶將ECDSA簽名發(fā)送出去而共識節(jié)點(diǎn)進(jìn)行一致性驗(yàn)證過程一樣，整個過程只有一次數(shù)據(jù)發(fā)送。
多項(xiàng)式時間算法：能夠快速計算出結(jié)果的算法Polynomial-Time-Algorithms。
倍點(diǎn)算法：已知私鑰sk和橢圓曲線基點(diǎn)G，能夠快速計算出公鑰PK
PK:=sk?G哈希運(yùn)算：已知原象x和哈希函數(shù)SHA256，能夠快速計算出函數(shù)值y
y:=SHA256(x)
非多項(xiàng)式時間算法：包括指數(shù)時間算法、亞指數(shù)時間算法。以下計算需要指數(shù)時間：
離散對數(shù)：已知公鑰PK和橢圓曲線基點(diǎn)G，不能夠在多項(xiàng)式時間內(nèi)計算出私鑰sk，而需要指數(shù)時間才能計算出私鑰sk，使得以下等式成立
PK=sk?G哈希求逆：已知函數(shù)值y和哈希函數(shù)SHA256，不能夠在多項(xiàng)式時間內(nèi)計算出原象x，而需要指數(shù)時間才能計算出原象x，使得以下等式成立
y=SHA256(x)
根據(jù)維基百科，目前，學(xué)術(shù)屆還沒有區(qū)分P問題是否等于NP問題。為方便理解zkSnark，從應(yīng)用角度出發(fā)，我們認(rèn)為P問題不等于NP問題。
P問題：在多項(xiàng)式時間內(nèi)可解的問題P-NP。以下問題多項(xiàng)式時間內(nèi)可求解：
求公鑰？已知私鑰sk和橢圓曲線基點(diǎn)G，求滿足以下離散對數(shù)關(guān)系的公鑰PK
PK=sk?G求哈希值？已知原象x和哈希函數(shù)SHA256，求滿足以下計算關(guān)系的函數(shù)值y
y=SHA256(x)
NP問題：（1）多項(xiàng)式時間內(nèi)不可計算的問題，需要指數(shù)時間或亞指數(shù)時間。（2）但是，一旦已知解，則能夠在多項(xiàng)式時間內(nèi)驗(yàn)證解是否正確P-NP。以下是3個典型的NP問題：
求私鑰？已知公鑰PK和基點(diǎn)G，求私鑰sk。要求私鑰與公鑰滿足以下離散對數(shù)關(guān)系
PK=sk?G
不能在多項(xiàng)式時間內(nèi)求解出私鑰sk，需要指數(shù)時間。但是，一旦給出私鑰sk，則能夠在多項(xiàng)式時間內(nèi)驗(yàn)證該私鑰sk與公鑰PK是否滿足離散對數(shù)關(guān)系。求哈希原象？已知函數(shù)值y和哈希函數(shù)SHA256，求原象x。要求原象x和函數(shù)值y滿足以下SHA256計算關(guān)系
y=SHA256(x)
不能在多項(xiàng)式時間內(nèi)求解出原象x，需要指數(shù)時間。但是，一旦給出原象x，則能夠在多項(xiàng)式時間內(nèi)驗(yàn)證該原象x與函數(shù)值y是否滿足SHA256計算關(guān)系。
因此，NP問題的本質(zhì)是單向性，不可快速逆向求解，但是能夠快速正向驗(yàn)證。
第3個重要的NP問題：多項(xiàng)式整除問題
給定一系列的多項(xiàng)式u0?(x),u1?(x),…,um?(x);v0?(x), v1?(x),…,vm?(x),w0?(x)，w1?(x),…,wm?(x)，且給定一個目標(biāo)多項(xiàng)式z(x)=(x-1)…(x-n)，找出這些多項(xiàng)式的線性組合能整除目標(biāo)多項(xiàng)式。
求向量
滿足以下整除關(guān)系
**原理分析:**向量s分別對三組多項(xiàng)式u0?(x),u1?(x),…,um?(x);v0?(x), v1?(x),…,vm?(x),w0?(x)，w1?(x),…,wm?(x)進(jìn)行線性組合，分別得到三個線性組合多項(xiàng)式
然后，將前兩個線性組合多項(xiàng)式相乘并減去第三個多項(xiàng)式。這兩個過程稱為組合運(yùn)算。
向量s的維度為m。如果每個元素si的取值空間為a，則將
稱為二次算法多項(xiàng)式，簡稱QAP多項(xiàng)式。QAP多項(xiàng)式的構(gòu)造為指數(shù)空間am。如果元素si的取值空間為0或1，則將
稱為二次擴(kuò)張多項(xiàng)式，或二次布爾多項(xiàng)式，簡稱QSP多項(xiàng)式。QSP多項(xiàng)式的構(gòu)造為指數(shù)空間2m。因此，這兩個組合運(yùn)算的計算時間均是指數(shù)時間。
多項(xiàng)式z(x)等于零有n個解，而QAP/QSP多項(xiàng)式等于零的解數(shù)量為2n-2。所以，除z(x)=0的n個解以外，QAP/QSP多項(xiàng)式還有n-2個其他解。因此，可以計算出商多項(xiàng)式，且商多項(xiàng)式本質(zhì)上就是QAP/QSP多項(xiàng)式等于零的n-2個其他解構(gòu)成的多項(xiàng)式。
如果不知道向量，則只能隨機(jī)選擇一個向量，計算QAP/QSP多項(xiàng)式，然后檢測與之是否滿足整除關(guān)系。如果滿足，則接受，否則拒絕。因此，需要指數(shù)時間才能夠暴力搜索出向量。但是，一旦給定向量，則能夠快速基于向量構(gòu)造出QAP/QSP多項(xiàng)式，并快速驗(yàn)證與構(gòu)造出的QAP/QSP多項(xiàng)式是否滿足整除關(guān)系。因此，多項(xiàng)式z(x)與QAP/QSP多項(xiàng)式的整除關(guān)系，滿足單項(xiàng)性，構(gòu)成NP問題。?該構(gòu)造至關(guān)重要，本文后續(xù)的舉例需使用多項(xiàng)式整除關(guān)系構(gòu)造NP問題。
運(yùn)算關(guān)系公開?，則需要提供正確的數(shù)據(jù)s1,…sn，使得數(shù)據(jù)s1,…sn滿足運(yùn)算關(guān)系。
對于第1個NP問題【求私鑰】，可使用經(jīng)典的Σ協(xié)議證明證明方P知道私鑰sk而不泄露私鑰sk。第2個問題【求哈希原象】無法使用Σ協(xié)議進(jìn)行證明，但是可以將第2個NP問題等價轉(zhuǎn)換為第3個NP問題【多項(xiàng)式整除關(guān)系】，然后將多項(xiàng)式系數(shù)放到橢圓曲線離散對數(shù)點(diǎn)上（即多項(xiàng)式承諾），形成離散對數(shù)困難，使得驗(yàn)證方能夠重構(gòu)整除關(guān)系。最后，驗(yàn)證方驗(yàn)證了向量s 正確性，但是證明方?jīng)]泄露向量s 。
注意：如果私鑰sk的位寬、哈希函數(shù)原象x的位寬、向量s 維度比較小，則對應(yīng)的指數(shù)計算復(fù)雜度較低，則容易被暴力破解。如果足夠大，則對應(yīng)的計算復(fù)雜度較高，能夠抵抗暴力破解。為方便展示計算過程，本文在第2.3節(jié)的舉例使用方程對應(yīng)的向量s 維度比較小，容易暴力破解。但是，如果方程的階很高，對應(yīng)的向量s 維度很大，則不會被暴力破解。
1.2 零知識證明
零知識證明引言
對于第1個NP問題：證明方P向驗(yàn)證方V證明其擁有私鑰sk，但不泄露sk。
證明方P用私鑰sk和隨機(jī)數(shù)k，計算ECDSA簽名σ=(r,s)。
驗(yàn)證方V基于(r,s)構(gòu)造橢圓曲線點(diǎn)，結(jié)合公鑰PK重構(gòu)線性關(guān)系，則驗(yàn)證成功。
則驗(yàn)證方V認(rèn)可證明方P有私鑰sk而不知道該私鑰sk。
該舉例使用數(shù)字簽名實(shí)現(xiàn)零知識證明，可見零知識證明由數(shù)字簽名發(fā)展而來。數(shù)字簽名中的私鑰天然滿足對公鑰的離散對數(shù)關(guān)系，但是零知識證明中的秘密ω滿足任意計算規(guī)則y=F(ω)。因此，零知識證明對離散對數(shù)關(guān)系進(jìn)行了巨大的擴(kuò)展，使得零知識證明有了廣泛的應(yīng)用范疇。
定義1：零知識證明：令R為一個高效可計算的二元關(guān)系。對于一對二元組(x,ω)∈R，x為聲明，ω為秘密見證。對于二元運(yùn)算關(guān)系R，證明系統(tǒng)包括系統(tǒng)參數(shù)生成SysGen，證明P和驗(yàn)證V。
一個具體的知識證明協(xié)議ZK{ω|(x,ω)∈R}包括5個多項(xiàng)式時間算法，系統(tǒng)參數(shù)生成SysGen，承諾Commitment，挑戰(zhàn)Challenge，響應(yīng)Response和驗(yàn)證Verify。對于一個固定的安全參數(shù)λ，這5個算法如下運(yùn)行：
系統(tǒng)參數(shù)：安全多方計算生成系數(shù)所需公共參數(shù)CRS
CRS←SysGen(1^λ)
? 承諾：證明方P選擇一個隨機(jī)數(shù)r，計算并發(fā)送承諾
C←Com(x,ω;r)
? 挑戰(zhàn)：驗(yàn)證方V選擇從某個域中一個隨機(jī)數(shù)作為挑戰(zhàn)e并發(fā)送給證明方P。
? 響應(yīng)：證明方P對驗(yàn)證方V輸出響應(yīng)
z←Response(x,ω;e,r)
? 驗(yàn)證：驗(yàn)證方V基于承諾、挑戰(zhàn)和響應(yīng)計算并輸出判斷結(jié)果
Valid/Invalid←Verify(x,C,e,z)
ZK{ω|(x,ω)∈R}協(xié)議具有完備性，如果滿足以下性質(zhì)：
ZK{ω|(x,ω)∈R}協(xié)議具有知識提取魯棒性，如果滿足以下性質(zhì)：
對秘密證明2次，則可以提取秘密，說明秘密確實(shí)使用了。承諾的隨機(jī)數(shù)使用2次，挑戰(zhàn)不同，影響不同，則可以解方程組。
ZK{ω|(x,ω)∈R}協(xié)議具有誠實(shí)驗(yàn)證方零知識，如果滿足以下性質(zhì)：
定義：如果協(xié)議ZK{ω|(x,ω)∈R}具有完成性、知識提取的魯棒性和誠實(shí)驗(yàn)證方零知識，則協(xié)議ZK{ω|(x,ω)∈R}是一個Σ協(xié)議。
1.3 協(xié)議
Σ協(xié)議包括： （1）生成系統(tǒng)參數(shù)CRS，（2）承諾，（3）挑戰(zhàn)，（4）響應(yīng)，（5）驗(yàn)證。其中，系統(tǒng)參數(shù)CRS由多方安全計算生成。
系統(tǒng)參數(shù)CRS： 群G的階為q，生成元為G；公開輸入為Q∈G。在該系統(tǒng)下，證明方P證明：其知道ω滿足離散對數(shù)關(guān)系Q=ω?G。
交互式零知識證明
承諾：證明方P選擇隨機(jī)數(shù)r，計算并發(fā)送：C:=r?G；
挑戰(zhàn)：驗(yàn)證方V選擇隨機(jī)數(shù)e，發(fā)送e；
響應(yīng)：證明方P計算并發(fā)送：z:=r+e?ω；
驗(yàn)證：驗(yàn)證方V驗(yàn)證
z?G=C+e?Q
如果等式成立，則接受，否則拒絕。
協(xié)議思想：
如圖1所示，證明方P將ω與隨機(jī)數(shù)e進(jìn)行線性組合z:=r+e?ω，生成隨機(jī)數(shù)z；
驗(yàn)證方V基于隨機(jī)數(shù)z,e構(gòu)造橢圓曲線離散對數(shù)點(diǎn)z?G,e?Q，并與點(diǎn)C，在橢圓曲線離散對數(shù)上重構(gòu)線性關(guān)系，實(shí)現(xiàn)一致性驗(yàn)證。
非交互式零知識證明
承諾：證明方P選擇隨機(jī)數(shù)r，計算：C:=r?G；
挑戰(zhàn)：證明方P計算隨機(jī)數(shù)：e:=Hash(Q,C)；（此處有變化）
響應(yīng)：證明方P計算z:=r+e?ω，發(fā)送：C,e,z
驗(yàn)證：驗(yàn)證方V計算e:=H(C)，然后驗(yàn)證
z?G=C+e?Q
如果等式成立，則接受，否則拒絕。
數(shù)字簽名定義：
Alice用私鑰sk對消息m簽名，驗(yàn)證方Verifier用Alice的公鑰PK對消息簽名對(m,σ)進(jìn)行一致性驗(yàn)證
非交互式零知識證明擴(kuò)展為數(shù)字簽名
對于離散對數(shù)關(guān)系Q=ω?G，把ω看作私鑰sk，Q看作公鑰PK。
承諾：證明方P選擇隨機(jī)數(shù)r，計算：C:=r?G；
挑戰(zhàn)：證明方P計算隨機(jī)數(shù)：e:=Hash(C,m)；（此處有變化）
響應(yīng)：證明方P計算z:=r+e?ω，發(fā)送：C,e,z,m；
驗(yàn)證：驗(yàn)證方V計算e:=Hash(C,m)，然后驗(yàn)證
z?G=C+e?Q
如果等式成立，則接受，否則拒絕。
保密隨機(jī)數(shù)的作用等價于私鑰。舉例：tornado cash就是zk證明知道承諾的隨機(jī)數(shù)r，就可以提幣。
核心思想：?第3步的數(shù)據(jù)等價于Alice的對消息的簽名，第4步等價于驗(yàn)證方使用Alice的公鑰對消息與簽名的一致性驗(yàn)證。因此，該協(xié)議滿足數(shù)字簽名的定義。
本質(zhì)上該協(xié)議是證明：（1?）Alice?擁有私鑰?，且（2）?ω與消息m具有綁定關(guān)系e=Hash(A,m)。
Σ協(xié)議：證明方P證明其知道ω滿足離散對數(shù)關(guān)系Q=ω?G。由于Q=ω?G即是天然的NP問題，又是天然的離散對數(shù)關(guān)系，所以可以直接基于這個NP問題在橢圓曲線離散對數(shù)點(diǎn)上構(gòu)造線性關(guān)系，形成離散對數(shù)困難問題。最后，驗(yàn)證方V驗(yàn)證了NP問題的解的正確性，但是證明方P沒泄露ω。
zk-SNARK協(xié)議：需要證明ω滿足任意多項(xiàng)式時間計算關(guān)系y=F(ω)。該任意計算包括NP問題和P問題。
NP問題：已知函數(shù)值y和哈希函數(shù)SHA256，求原象x；已知Merkle根，求Merkle樹的葉子和路徑；
P問題：已知兩個布爾值a,c，求布爾值b，使得等式a⊕b=c成立；已知方程x4+x3+x2+x=120，求解x；
這4個算法中，
哈希函數(shù)的原象x、Merkle樹的葉子和路徑、布爾值b、方程解x=3以及計算過程的中間狀態(tài)值就是秘密，記為ω或witness。
哈希函數(shù)值y、Merkle根、布爾運(yùn)算結(jié)果c和方程的值120，記為statement。
為不泄露秘密，需使用R1CS約束（電路約束）等價描述算法的運(yùn)算規(guī)則。公開R1CS約束（電路約束），然后將滿足公開的計算關(guān)系等價轉(zhuǎn)化為滿足R1CS約束并合并R1CS?約束?，再等價轉(zhuǎn)化為向量與多維向量的內(nèi)積，再等價轉(zhuǎn)化為向量與矩陣的內(nèi)積，再等價轉(zhuǎn)化為向量對三組多項(xiàng)式的組合運(yùn)算，再等價轉(zhuǎn)化為目標(biāo)多項(xiàng)式整除QAP多項(xiàng)式（?構(gòu)成NP?問題?），再等價轉(zhuǎn)化為基于這三個多項(xiàng)式的系數(shù)計算橢圓曲線離散對數(shù)點(diǎn)（即多項(xiàng)式承諾），形成離散對數(shù)困難問題；最后，驗(yàn)證方基于橢圓曲線離散對數(shù)點(diǎn)（多項(xiàng)式承諾）重構(gòu)整除關(guān)系，驗(yàn)證了向量的正確性，但是證明方?jīng)]泄露向量。
zk-SNARK協(xié)議的7?個核心等價轉(zhuǎn)化關(guān)系?，如圖2所示
接下來對zk-SNARK協(xié)議中的核心等價轉(zhuǎn)換關(guān)系進(jìn)行詳細(xì)敘述。
2 多項(xiàng)式時間算法等價轉(zhuǎn)換為階為1的等式
2.1 哈希函數(shù)等價于階為1的等式
哈希函數(shù)SHA256輸入512bits的數(shù)據(jù)，通過與、或、非、異或、循環(huán)移位等基礎(chǔ)運(yùn)算的耦合，進(jìn)行線性變換與非線性變換(擴(kuò)張與有損壓縮)，輸出256bits的隨機(jī)數(shù)。以下是SHA256的運(yùn)算原理，循環(huán)64次后輸出函數(shù)值。其中，x,y,z位寬均為32bits，Si循環(huán)右移i bits，Ri循環(huán)右移i bits。
以下對布爾值和異或運(yùn)算進(jìn)行等價轉(zhuǎn)化：
布爾值a和b，如下拆為階為1的等式
位異或運(yùn)算a⊕b=c，如下拆為4個階為1的等式
推論1?：布爾值?和?等價于階為1?的等式2?；
推論2?：位異或運(yùn)算?等價于4?個階為1?的等式3?。
因此，基于推論2.1和2.1，可以得出以下推論：
推論3?：哈希函數(shù)SHA256?或公式1?等價于?某些階為1?的等式?。?a*b=c
推論4?：Merkle?樹等價于某些階為1?的等式。
上述3個階為1的等式就是電路約束。這3個階為1的等式是乘法等式，所以是乘法約束。?公式3的前3個乘法約束限定輸入為布爾值，第4個乘法約束實(shí)現(xiàn)異或運(yùn)算的等價功能。一方面：可以基于這****4?個等式，設(shè)計實(shí)際的硬件電路或FPGA?。另一方面：可以用程序表達(dá)這4?個運(yùn)算規(guī)則，則等價于表達(dá)出電路約束，等價于實(shí)現(xiàn)電路運(yùn)算原理。因此，算法的運(yùn)算規(guī)則等價于電路約束。
a和b是輸入值，c是輸出值。證明方把a(bǔ),b,c發(fā)送給驗(yàn)證方，則驗(yàn)證方根據(jù)a,b,c和上述階為1的等式（電路約束）成功驗(yàn)證，則驗(yàn)證方認(rèn)可證明方是對布爾值a和b誠實(shí)進(jìn)行異或運(yùn)算。類似地，證明方把哈希函數(shù)的原象x和函數(shù)值y發(fā)送給驗(yàn)證方，驗(yàn)證方根據(jù)x,y和階為1的等式成功驗(yàn)證，則能夠確定證明方誠實(shí)計算哈希函數(shù)，且原象x和函數(shù)值y是正確的。
在零知識證明協(xié)議中，witness是布爾值a,b或原象x，statement是c或哈希值y，算法的計算規(guī)則就是電路約束（R1CS約束）。因此，上述證明與驗(yàn)證過程存在2個缺點(diǎn)：
秘密泄露：布爾值a,b或原象x泄露，缺乏零知識，后續(xù)通過離散對數(shù)解決。
驗(yàn)證方的計算復(fù)雜度沒降低：階為1的等式的計算復(fù)雜度等于原算法的計算復(fù)雜度，所以驗(yàn)證方的計算量沒降低。后續(xù)通過多項(xiàng)式放到離散對數(shù)上解決。
計算壓縮：
數(shù)據(jù)壓縮：向量s={0jkdshgfgfshk}
Proof長度是固定的幾個橢圓曲線點(diǎn)。
2.2 數(shù)字簽名等價于階為1的等式
（一）預(yù)備知識
橢圓曲線離散對數(shù)困難問題：已知基點(diǎn)G=(x0,y0)和公鑰Q=(xq,yq)，計算私鑰是困難的
Q=sk?G
因此，密碼學(xué)提供計算安全，是相對安全，而不是絕對安全。已知私鑰sk和基點(diǎn)G=(x0,y0)，可在多項(xiàng)式時間內(nèi)計算公鑰Q=(xq,yq)。
（二）數(shù)字簽名
ECDSA簽名：用戶的私鑰為d，對于消息M，選擇隨機(jī)數(shù)k∈[1,…,n-1]，如下計算：
則簽名為σ=(r,s)。廣播(M,σ,Q)，其中Q是公鑰。
ECDSA簽名原理解析：
選擇一個隨機(jī)數(shù)k，計算橢圓曲線離散對數(shù)k?G。隨機(jī)數(shù)k對私鑰d進(jìn)行隨機(jī)化，防止攻擊者計算出私鑰d。
計算出兩個隨機(jī)數(shù)(r,s)就是簽名。這兩個隨機(jī)數(shù)(r,s)是隨機(jī)數(shù)k-1、私鑰d、消息的摘要值SHA(M)和橫坐標(biāo)r的線性組合
因此，攻擊者無法根據(jù)(r,s)計算出隨機(jī)數(shù)k與私鑰sk。
ECDSA?驗(yàn)證：?驗(yàn)證方基于如下計算：
如果等式r=x1modn成立，則接受，否則拒絕。
ECDSA驗(yàn)證原理解析：
基于兩個隨機(jī)數(shù)(r,s)和消息M計算出u1,u2；
基于u1,u2、基點(diǎn)G和公鑰Q進(jìn)行倍點(diǎn)運(yùn)算，計算出2個橢圓曲線點(diǎn)u1?G,u2?Q；
對這兩個橢圓曲線離散對數(shù)點(diǎn)u1?G,u2?Q進(jìn)行點(diǎn)加運(yùn)算，則結(jié)果為(x1,y1)；
新橢圓曲線點(diǎn)的橫坐標(biāo)x_1與隨機(jī)數(shù)r應(yīng)該相等的，則驗(yàn)證成功。
ECDSA思想精華： 用戶從私鑰角度計算橢圓曲線離散對數(shù)點(diǎn)(x1,y1)，并產(chǎn)生兩個隨機(jī)數(shù)(r,s)，使得驗(yàn)證方能夠從公鑰的角度重新計算出橢圓曲線離散對數(shù)點(diǎn)(x1,y1)。
ECDSA算法包括3個基本的運(yùn)算，分別為橢圓曲線離散對數(shù)點(diǎn)加運(yùn)算u_1?G+u_2?Q、倍點(diǎn)運(yùn)算k?G、域元素相乘的模n運(yùn)算。
為方便后續(xù)分析，將點(diǎn)加運(yùn)算(x1,y1):=u_1?G+u_2?Q進(jìn)行如下修改：
(x3,y3):=(x1,y1)+(x2,y2)
點(diǎn)加運(yùn)算：
已知兩個橢圓曲線離散對數(shù)點(diǎn)(x1,y1),(x2,y2)，求第三個點(diǎn)(x3,y3)， 計算過程如下：
上面是求值：求值電路。
其中，a=-1,d=-168696/168700是兩個常量。
當(dāng)x1=x2,y1=y2，就是倍點(diǎn)運(yùn)算，因此以下僅討論點(diǎn)加運(yùn)算。
將上述點(diǎn)加運(yùn)算公式6拆為7個階為1的等式
驗(yàn)證電路?：把結(jié)果放到電路里面去了。
推論5?：點(diǎn)加運(yùn)算公式6?與等式1.7?等價。
推論6?：ECDSA?能夠等價拆為階為1?的等式。或ECDSA?與某些階為1?的等式等價。
這些階為1?的等式就是電路約束。其中，階為1?的乘法等式就是乘法約束，階為1?的加法等式就是加法約束。這7?個約束實(shí)現(xiàn)點(diǎn)加運(yùn)算的等價功能。一方面：可以基于這7?個階為1?的等式（R1CS?約束），設(shè)計實(shí)際的運(yùn)算電路或FPGA?。另一方面：可以用程序表達(dá)這7?個運(yùn)算規(guī)則，則等價于表達(dá)出電路約束，等價于實(shí)現(xiàn)電路運(yùn)算原理。因此，算法的運(yùn)算規(guī)則就是電路約束。
證明方把(x1,y1),(x2,y2),(x3,y3),A1,A2,A3,A4,A5,A6發(fā)送給驗(yàn)證方，則驗(yàn)證方根據(jù)階為1的等式1.8成功驗(yàn)證，則驗(yàn)證方確定證明方是誠實(shí)進(jìn)行點(diǎn)加運(yùn)算的。
類似地，證明方把消息M、簽名值σ和公鑰Q發(fā)送給驗(yàn)證方，驗(yàn)證方根據(jù)某些階為1的等式進(jìn)行驗(yàn)證，則能夠確定證明方誠實(shí)計算了ECDSSA簽名。
但是，仍存在以下兩個缺點(diǎn)：
1. 消息太多：或秘密泄露。交易消息M、簽名值σ和公鑰Q泄露。解決方案：僅存儲交易消息M中的公開數(shù)據(jù)pubdata和Merkle根，剩余的所有消息隱藏起來，如簽名和公鑰當(dāng)作witness。
2. 驗(yàn)證方的計算復(fù)雜度沒降低：階為1的等式的計算復(fù)雜度等于簽名驗(yàn)證計算復(fù)雜度。后續(xù)通過多項(xiàng)式和離散對數(shù)解決該問題。
推論7：任意多項(xiàng)式時間算法均能夠拆為階為1的等式?；蛉我舛囗?xiàng)式時間算法與某些階為1的等式等價。
2.3 多項(xiàng)式時間算法等價于階為1的等式
任意多項(xiàng)式時間算法（包括上述SHA256和ECDSA）均有一個對應(yīng)的階為1的等式（R1CS約束）。此處，將多項(xiàng)式時間算法限定為一個方程，將方程拆為階為1的等式。該舉例有2個作用：（1）解該方程是P問題，體現(xiàn)了基于P問題構(gòu)造NP問題；（2）能夠較好的展現(xiàn)出對R1CS約束的優(yōu)化。
方程x4+x3+x2+x=120如下拆為階為1的等式
關(guān)鍵結(jié)論：x=3?滿足方程的解，等價于x=3?滿足電路約束。
關(guān)鍵結(jié)論：x?滿足任意多項(xiàng)式時間運(yùn)算y=f(x)?，等價于x?滿足電路約束。
這6?個階為1?的等式限定了方程的運(yùn)算規(guī)則，能夠用電路約束表達(dá)同樣的運(yùn)算規(guī)則。電路約束即能用硬件電路或FPGA?實(shí)現(xiàn)，也可以用軟件實(shí)現(xiàn)等價的功能。階為1?的等式=?電路約束，階為1?的乘法等式=?乘法約束，階為1?的加法等式=?加法約束。
關(guān)鍵術(shù)語：?階為1?的等式（Rank 1 Constraint System, R1CS?）。
以下術(shù)語是等價描述：階為1的等式、R1CS約束、電路約束。
上述6個階為1的等式包含3個乘法等式和3個加法等式，可使用3個乘法約束和3個加法約束實(shí)現(xiàn)運(yùn)算原理，如圖1(a)所示。此外，可以將加法約束優(yōu)化到乘法約束中，則上述6個階為1的等式8化簡為以下3個階為1的乘法等式9。僅使用3個乘法約束即可實(shí)現(xiàn)等價的運(yùn)算規(guī)則，如圖1(b)所示。
推論8?：方程?(多項(xiàng)式時間算法)等價于R1CS約束，形式化表達(dá)如下
因此，可以得出以下推論：
推論9：任意多項(xiàng)式時間算法（哈希函數(shù)SHA256、Merkle樹、ECDSA驗(yàn)證、方程等）均可等價為階為1的等式（也稱為：R1CS約束、電路約束）。
?3 witness滿足R1CS約束的等價轉(zhuǎn)化
3.1 witness等價于向量s
本節(jié)將witness即方程的解x=3（也可以是哈希函數(shù)原象x，Merkle樹的葉子和節(jié)點(diǎn)、ECDSA中的消息M、簽名σ和公鑰Q）等價轉(zhuǎn)化為向量
對約束等式10
的(b)，有以下等價關(guān)系
可見R1CS約束等式(b)中的向量需要包含更多的中間狀態(tài)變量s3,s4,s5。在下一節(jié)，R1CS約束等式(b)對應(yīng)的矩陣維度也更大，進(jìn)而在后續(xù)步驟中會產(chǎn)生階數(shù)更高的多項(xiàng)式和更復(fù)雜的拉格朗日插值多項(xiàng)式（或傅里葉變換）。因此，下一節(jié)的R1CS約束約束等價轉(zhuǎn)化為矩陣時，使用優(yōu)化的R1CS約束等式(c)。
業(yè)務(wù)語言：隱私數(shù)據(jù)（方程的解x=3、哈希函數(shù)原象x，Merkle樹的葉子和節(jié)點(diǎn)、ECDSA數(shù)據(jù)M簽名σ和公鑰Q）就是零知識證明中的witness。
在實(shí)際應(yīng)用時，為防止證明方P欺騙驗(yàn)證方V，不能將所有數(shù)據(jù)隱藏起來，需要公開局部參數(shù)。所以，1,out需要公開， x,s1,s2,s3隱藏。因此，將向量s 為公開數(shù)據(jù)與隱私數(shù)據(jù)。公開數(shù)據(jù)記為statement=(1,out)，隱私數(shù)據(jù)記為witness=(x,s1,s2,s3)。這里的out是方程的計算結(jié)果120。對于Layer2技術(shù)，out則是Merkle根。
3.2 witness滿足R1CS約束等價于向量內(nèi)積
對于第1個階為1的等式（R1CS約束）s1=x*x，如下進(jìn)行向量內(nèi)積等價轉(zhuǎn)化：
3.3 向量內(nèi)積等價轉(zhuǎn)化為向量與矩陣的內(nèi)積
4 向量與矩陣內(nèi)積的等價轉(zhuǎn)化
命題2：多項(xiàng)式值表達(dá)等價于多項(xiàng)式系數(shù)表達(dá)。
證明：?設(shè)階多項(xiàng)式為
已知多項(xiàng)式的值f0,…,fm和橫坐標(biāo)x0,…,xm，可以計算出多項(xiàng)式的系數(shù)a0,…,am；計算方法包括解方程組、拉格朗日插值法、快速傅里葉逆變換等。反之，已知多項(xiàng)式的系數(shù)a0,…,am和橫坐標(biāo)x0,…,xm，可以計算出多項(xiàng)式的值f0,…,fm。因此，多項(xiàng)式值表達(dá)等價于多項(xiàng)式系數(shù)表達(dá)?？焖儆嬎惴椒ǎ嚎焖俑道锶~變換。
4.1 向量對三組多項(xiàng)式的組合運(yùn)算
將方程x4+x3+x2+x=120轉(zhuǎn)換為R1CS約束后，得到以下三個矩陣
將矩陣中的元素當(dāng)作多項(xiàng)式的值，如對矩陣W
對于多項(xiàng)式值表達(dá)等價轉(zhuǎn)化為多項(xiàng)式系數(shù)表達(dá)，以下介紹的拉格朗日插值法不是最優(yōu)算法，但在理解上是最直觀的。最優(yōu)算法是快速傅里葉變換、基4時分的Cooley-Tukey?蝶形變換，運(yùn)算可并行化，并使用GPU/FPGA?等加速。
對于多項(xiàng)式的值，每一列有3個函數(shù)值，所以取任意3個變量，如，作為橫坐標(biāo)。可使用拉格朗日插值多項(xiàng)式，基于多項(xiàng)式的值計算多項(xiàng)式的系數(shù)
如下計算多項(xiàng)式的系數(shù)表達(dá)
則多項(xiàng)式
以此類推，可以計算出多項(xiàng)式
則有以下等價關(guān)系
4.2 目標(biāo)多項(xiàng)式整除QAP多項(xiàng)式構(gòu)造NP問題
上述拉格朗日插值多項(xiàng)式引入橫坐標(biāo)為x=1,2,3，則能夠構(gòu)造多項(xiàng)式
z(x)=(x-1)(x-2)(x-3)
z(x)稱為目標(biāo)多項(xiàng)式。可以取任意橫坐標(biāo)變量，如令x=4,5,6，則重新使用拉格朗日插值定理計算函數(shù)值并令目標(biāo)多項(xiàng)式為z(x)=(x-4)(x-5)(x-6)。
KZG承諾：y=f(z)函數(shù)點(diǎn)運(yùn)算正確
基于現(xiàn)有的運(yùn)算構(gòu)造出多項(xiàng)式，進(jìn)行多項(xiàng)式承諾打開某些點(diǎn)。F(x)
120=f(x=3)，確實(shí)知道秘密x=3，提供了正確數(shù)據(jù)。
z(x)*Q(x)=QAP(X)，基于PK，a，z(a)*G1
z(x)=3x^3+2x^2+x
PK=a^3G1,a^2G1,aG1
a^3G2,a^2G2,aG
e(z(a)*G1,Q(a) *G2)=e(QAP(a) *G1,G2)
z(a)*Q(a)=QAP(a)
反之，如果驗(yàn)證方V能夠基于橢圓曲線離散對數(shù)點(diǎn)（多項(xiàng)式承諾）重構(gòu)整除關(guān)系，則向量s對三組多項(xiàng)式的組合運(yùn)算是正確的，則向量與矩陣的內(nèi)積運(yùn)算正確，則向量與多維向量的內(nèi)積正確，則witness滿足R1CS約束，則x=3是方程的解（或x是哈希函數(shù)的原象，a,b是布爾值，葉子與節(jié)點(diǎn)滿足Merkle樹），則證明方P對數(shù)據(jù)的運(yùn)算是正確，則用戶提交了正確交易數(shù)據(jù)。因此，用戶交易會成功。
5 zk-SNARK協(xié)議框架
分析
將QAP多項(xiàng)式、目標(biāo)多項(xiàng)式和商多項(xiàng)式的系數(shù)放到橢圓曲線的離散對數(shù)上，驗(yàn)證方在橢圓曲線點(diǎn)上重構(gòu)整除關(guān)系，實(shí)現(xiàn)正確性驗(yàn)證，卻不知道多項(xiàng)式的系數(shù)（或不知道解向量s ?），即零知識。
計算復(fù)雜度很高的任意多項(xiàng)式時間算法，等價轉(zhuǎn)化為R1CS約束、矩陣、多項(xiàng)式。最后與向量對三組項(xiàng)式組合運(yùn)算生成QAP多項(xiàng)式，并與目標(biāo)多項(xiàng)式、商多項(xiàng)式的系數(shù)均放到橢圓曲線離散對數(shù)點(diǎn)上（多項(xiàng)式承諾），所以證明方P的計算復(fù)雜度很高；而驗(yàn)證方僅需要使用橢圓曲線點(diǎn)重構(gòu)整除關(guān)系，則實(shí)現(xiàn)向量s 的正確性驗(yàn)證，所以計算復(fù)雜度較低。
算法評價
1：Groth16的CRS包含R1CS約束等價轉(zhuǎn)化來的多項(xiàng)式W(x),U(x),V(x)，非常具體。
優(yōu)點(diǎn)：證明方P直接使用CRS中的多項(xiàng)式W(x),U(x),V(x)生成證明，速度很快。
缺點(diǎn)：這個CRS包含的多項(xiàng)式W(x),U(x),V(x)是由R1CS約束轉(zhuǎn)換而來，已經(jīng)固化，只能表達(dá)唯一電路，不能表達(dá)其他電路，所以表達(dá)能力極差。如果對layer2的電路進(jìn)行修改，則步驟7的初始化b局部CRS也需要修改，則Layer1的合約參數(shù)CRS也需要對應(yīng)修改才能夠進(jìn)行一致性驗(yàn)證。
2：PLONK的CRS不包含R1CS約束多項(xiàng)式，而只包含大量的橢圓曲線離散對數(shù)點(diǎn)。
優(yōu)點(diǎn)：CRS的表達(dá)能力很強(qiáng)，能夠用于任意多項(xiàng)式時間電路生成證明。
缺點(diǎn)：CRS表達(dá)能力太強(qiáng)，R1CS約束力不夠，不足以防止證明方P作弊，所以引入額外的線約束。線約束計算復(fù)雜度很高，導(dǎo)致證明生成緩慢。
6 Groth16協(xié)議詳解
6.1 協(xié)議原理
注意：x是具體值，所以多項(xiàng)式u(x),v(x),w(x)是具體的多項(xiàng)式值；σ_1,σ_2中與多項(xiàng)式u(x),v(x),w(x)無關(guān)的項(xiàng)在步驟0完成，與電路多項(xiàng)式u(x),v(x),w(x)相關(guān)的項(xiàng)在步驟7完成。注意：此處的多項(xiàng)式u(x),v(x),w(x)就是上一節(jié)討論的多項(xiàng)式W(x),U(x),V(x)。
ECDSA的驗(yàn)證算法寫成了電路；則用戶提交正確的交易單就是s
6.2 協(xié)議分析
（一）、一致性
（三）、證明方無法作弊：
原理分析
α和β迫使證明A,B,C必須采用同一套向量statement=a0,…,a0參數(shù)，而不能是其他參數(shù)。反之：如果A采用第1套參數(shù) a0,…,am參數(shù)。B采用第2套參數(shù)a0‘,…,am’，那么C應(yīng)該采用第1套還是第2套參數(shù)呢？答：不管C采用第1套還是第2套參數(shù)，等式都不會成立。如果C采用第1套參數(shù)，計算出來的表達(dá)式與A有對應(yīng)關(guān)系，卻與B沒有對應(yīng)關(guān)系，等式肯定不成立。
對于A,B,C的構(gòu)造，需要證明方選擇隨機(jī)數(shù)r,s。如果不添加隨機(jī)數(shù)r,s，那么證明A,B,C就失去了隨機(jī)性，驗(yàn)證方可以根據(jù)等式求解出witness。因此，算法中添加隨機(jī)數(shù)的算法功能叫作：盲化或隨機(jī)化，讓對方計算不出witness。
關(guān)于Hacker Dōjō?
Hacker Dōjō?是由Hacker共建的加密、Web3前沿技術(shù)開源知識社區(qū)。Dōjō?會以直播/音頻/文字等形式定期組織分享session, 分享主題主要覆蓋L1和L2的共識算法，架構(gòu)，GitHub repo相關(guān)內(nèi)容，包括不限于以下話題：Scroll / Polygon zkEVM、 Eigen的混合證明系統(tǒng)、Starkware、azTec、 Optimism、Zecrey、Aptos、 Move、密碼學(xué)(零知識證明、公鑰加密、哈希函數(shù)、格密碼) 、 分布式系統(tǒng)、 以太坊協(xié)議棧、 量子計算和量子信息、衛(wèi)星通信系統(tǒng)和航天器系統(tǒng)設(shè)計等。
?Bounty詳情及認(rèn)領(lǐng)進(jìn)度詳情：https://innovative-laser af4.notion.site/174922df15884848b6ac8b57cb4f2fae?v=612e13dc6b9d44dd8197f755abb9fe9c
?加入?Dōjō?中文社區(qū)微信聯(lián)系：@HackerDojo0
有關(guān)DoraHacks
DoraHacks 是一個全球范圍內(nèi)的極客運(yùn)動，全球黑客馬拉松組織者，也是全球最活躍的多鏈 Web3 開發(fā)者平臺之一。DoraHacks.io平臺使得世界各地的Hacker和開源開發(fā)者可以參與黑客馬拉松、Bounty、Grant、Grant DAO，以及公共物品質(zhì)押等加密原生協(xié)議和基礎(chǔ)設(shè)施進(jìn)行協(xié)作并獲得資助。到目前為止，DoraHacks 社區(qū)的 4000 多個項(xiàng)目已經(jīng)獲得了來自全球行業(yè)支持者超過 3000 萬美元的資助。大量開源社區(qū)、DAO 和 超過50個主要區(qū)塊鏈生態(tài)系統(tǒng)正在積極使用 Dora 的基礎(chǔ)設(shè)施（DoraHacks.io）進(jìn)行開源融資和社區(qū)治理。
官網(wǎng)：https://dorahacks.io/
