為什么關(guān)注ZK-ConSNARKSuterusu項(xiàng)目關(guān)注的是無需trusted setup，且證明空間復(fù)雜度為常數(shù)的，計(jì)算高效的零知識證明方案，簡稱ZK-ConSNARK。
為什么關(guān)注ZK-ConSNARK
Suterusu項(xiàng)目關(guān)注的是無需trusted setup，且證明空間復(fù)雜度為常數(shù)的，計(jì)算高效的零知識證明方案，簡稱ZK-ConSNARK。我們知道，一般情況下區(qū)塊鏈系統(tǒng)需要將交易通過p2p網(wǎng)絡(luò)傳輸給系統(tǒng)中每個(gè)驗(yàn)證節(jié)點(diǎn)進(jìn)行驗(yàn)證。
因此，網(wǎng)絡(luò)單位時(shí)間能處理的交易數(shù)目，俗稱出塊率，很大程度上取決于區(qū)塊大小，以及單位交易所占空間大小【CDEGJKMSSSS16】。交易越小，則出塊率越高。在隱私保護(hù)區(qū)塊鏈方案中，交易大小又很大程度上取決于其所包含的零知識證明大小。
事實(shí)上，需要trusted setup的ZK-ConSANRK文獻(xiàn)里已有不少，Zcash所使用的方案就屬于這個(gè)類別。但無需trusted setup的ZK-ConSNARK卻是稀有品種，目前本人所能找到這方面的結(jié)果只有兩篇：Crypto 2019年新鮮出爐的結(jié)果【LM19, BBF19】。這篇文章將簡單介紹這兩個(gè)方案的基本思路以及Suterusu項(xiàng)目在ZK-ConSANRK上的關(guān)注點(diǎn)。
上述兩篇論文【LM19, BBF19】都結(jié)合了概率性可驗(yàn)證證明(Probabilistically Checkable Proof，PCP)和子向量承諾(Subvector Commitment)方案。PCP是復(fù)雜性理論和密碼學(xué)里一個(gè)非常經(jīng)典的結(jié)果，相關(guān)定理的提出者因此獲獎(jiǎng)無數(shù)。
PCP作為一個(gè)基礎(chǔ)方案可用于構(gòu)造零知識證明。上述兩篇論文主要貢獻(xiàn)不在于PCP，而在于這個(gè)子向量承諾方案。其原因在于PCP方案如果想在非交互式零知識證明這個(gè)領(lǐng)域施展身手離不開高效的子向量承諾方案這個(gè)助手。
什么是概率性可驗(yàn)證證明
首先，我們簡單介紹下什么是概率性可驗(yàn)證證明。我們在前文【林19-1】中介紹過零知識證明的概念。零知識證明中有這么個(gè)驗(yàn)證者的概念，在PCP中也有個(gè)驗(yàn)證者。但PCP的驗(yàn)證者特別懶，所以我們需要考慮驗(yàn)證者如何能在做非常少工作的情況下，還能準(zhǔn)確判斷PCP證明者針對一個(gè)定理提供的證明是否正確。
盡管PCP本身的證明是非常長，但PCP有個(gè)神奇的性質(zhì)就是在證明者生成證明后，驗(yàn)證者只需隨機(jī)在證明上查詢?nèi)舾牲c(diǎn)(實(shí)際中大概是安全系數(shù)×3bits即可，所以如果是256-bit security，查詢長度只需256*3 bits)，然后做一些極為高效的運(yùn)算就可以驗(yàn)證證明的正確性。
我們在前文【林19-1】中提過，區(qū)塊鏈中使用的零知識證明需要是極為簡短的且最好計(jì)算也是高效的，盡管PCP的驗(yàn)證計(jì)算頗為高效，但證明過長仍是個(gè)弊病。我們注意到在驗(yàn)證時(shí)驗(yàn)證者真正需要訪問的只是整個(gè)證明中極小一部分內(nèi)容。
那么問題來了，有沒有可能讓證明者在生成PCP證明后自己在證明上隨機(jī)選取驗(yàn)證者需要的查詢點(diǎn)，然后只傳輸這些信息給驗(yàn)證者，從而大大減少通信量呢?
這個(gè)思路是對的，但一個(gè)惡意的證明者，或者一個(gè)不掌握證明秘密的人可以針對這個(gè)簡單思路發(fā)起如下幾個(gè)攻擊：比如可能這個(gè)用于隨機(jī)選取查詢點(diǎn)的隨機(jī)數(shù)本身不隨機(jī)，或者攻擊者先生成隨機(jī)數(shù)，然后再針對這些隨機(jī)位置生成對應(yīng)證明，換句話說他可能沒有能力生成全部正確PCP證明，但他卻有辦法針對提前生成的隨機(jī)位置生成合法的部分證明，進(jìn)而相應(yīng)地替換篡改他所生成的非法證明的對應(yīng)位置內(nèi)容，從而通過驗(yàn)證。
什么是子向量承諾
如何防止這類攻擊呢?這就需要引入我們的子向量承諾方案了。首先，我們先說下2019年前的工作中如何解決這個(gè)問題。承諾這個(gè)概念我在前面介紹Mimblewimble的文章【林19-3】中曾提到，事實(shí)不僅僅有Pedersen承諾方案，我前面關(guān)于Zcash的文章【林19-2】中提到的Merkle tree也可以被看作是一種承諾方案。
那么具體Merkle tree可以怎么和PCP結(jié)合呢?
證明者首先生成PCP證明，這些證明每個(gè)bit將作為Merkle tree的一個(gè)葉節(jié)點(diǎn)來計(jì)算哈希樹根節(jié)點(diǎn)數(shù)值，這個(gè)數(shù)值就是一個(gè)對上述PCP證明的承諾了。
我們之前提過承諾方案有個(gè)soundness性質(zhì)可以保證一旦承諾公開，用戶是沒法在打開承諾時(shí)改變承諾的內(nèi)容的，在Merkle tree中這個(gè)性質(zhì)主要是由所使用哈希函數(shù)的抗碰撞性來保證的。
那么好，證明內(nèi)容一旦生成無法篡改了，接下來的問題就是隨機(jī)性如何解決的問題了?如果Merkle tree現(xiàn)在的根節(jié)點(diǎn)值是r的話，那么用于決定證明查詢位置的隨機(jī)數(shù)將被定義成H(r)，這里H是個(gè)安全哈希函數(shù)，比如SHA256。
為什么這能保證H(r)是隨機(jī)的呢?
這個(gè)是和哈希函數(shù)的理論建模有關(guān)的。密碼學(xué)理論里一般把H(.)建模成隨機(jī)預(yù)言機(jī)，這意味著即使哈希函數(shù)的輸入是公開的，其輸出也是完全隨機(jī)的。
哈希函數(shù)的這個(gè)隨機(jī)預(yù)言機(jī)模型和承諾方案的soundness性質(zhì)合力保證驗(yàn)證者可以相信這個(gè)隨機(jī)數(shù)是在證明者把PCP證明關(guān)進(jìn)承諾這個(gè)箱子之后才生成的，且這個(gè)用于定義證明查詢位置的隨機(jī)數(shù)確實(shí)是隨機(jī)的。因此如果他確定后面承諾打開過程中顯示的消息確實(shí)是這些隨機(jī)數(shù)對應(yīng)的位點(diǎn)信息后，那么上述攻擊就可以被認(rèn)為是無效的。
好，那么現(xiàn)在問題就規(guī)約到如何保證證明者在承諾打開階段輸出的信息確實(shí)是對應(yīng)由這些隨機(jī)數(shù)定義的位置的。在Merkle tree這種承諾中，每個(gè)打開的消息同時(shí)還會(huì)有一些附屬的證明信息來證明這個(gè)打開的消息確實(shí)是某個(gè)葉節(jié)點(diǎn)位置的信息。但注意這個(gè)承諾方案的附屬證明空間復(fù)雜度不是常數(shù)，而是PCP空間復(fù)雜度的對數(shù)。
另外，由于Merkle tree每次只能打開一個(gè)證明位點(diǎn)，上述證明過程需要重復(fù)和安全參數(shù)相關(guān)的次數(shù)(比如256*3次)，這就導(dǎo)致證明所占空間無法避免地膨脹?！綥M19】文章提到如果一個(gè)PCP所占空間為1GB，使用Merkle tree這種承諾方案，對應(yīng)的最終零知識證明所占空間為88KB，且絕大部分都是由Merkle tree的這種附屬證明導(dǎo)致的額外開銷。
現(xiàn)在，我們終于可以介紹什么是子向量承諾了，事實(shí)上，Merkle tree可以看作一種非常簡陋的子向量承諾方案。和Merkle tree一樣，Crypto 19提出的子承諾方案可以一次性把整個(gè)向量裝進(jìn)承諾這個(gè)黑箱里，但和Merkle tree不同的是，在打開承諾階段，用戶可以同時(shí)打開和向量若干個(gè)位置綁定的內(nèi)容，而且對應(yīng)的證明空間復(fù)雜性為常數(shù)。這個(gè)方案的構(gòu)造需要用到一個(gè)特殊的代數(shù)結(jié)構(gòu)，叫g(shù)roup of unknown order。
事實(shí)上，這個(gè)概念可以看作RSA group的一種抽象。但RSA group對應(yīng)方案需要trusted setup，所以不太適用于隱私保護(hù)區(qū)塊鏈系統(tǒng)。目前也存在無需trusted setup的RSA group方案，但效率極低。所以上述兩文都提到了另外一種基于class groups of quadratic imaginary order的代數(shù)結(jié)構(gòu)來保證無需trusted setup的高效子向量承諾方案。
Suterusu的關(guān)注點(diǎn)
盡管上述兩文的方案已能實(shí)現(xiàn)可高效驗(yàn)證的ZK-ConSNARK，但底層基于的PCP方案由于生成證明的開銷太大無法實(shí)際應(yīng)用，但他們起碼從理論上證明了無需trusted setup的ZK-ConSNARK的可行性。Suterusu將針對去中心化隱私支付這種特殊的應(yīng)用場景優(yōu)化實(shí)現(xiàn)一些特殊的ZK-ConSNARK，來推進(jìn)隱私保護(hù)區(qū)塊鏈的效率和去中心化程度。（林煌）
關(guān)鍵詞： ZK-ConSNARK trusted setup 隱私
