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