為什么關注ZK-ConSNARKSuterusu項目關注的是無需trusted setup，且證明空間復雜度為常數的，計算高效的零知識證明方案，簡稱ZK-ConSNARK。

為什么關注ZK-ConSNARK

Suterusu項目關注的是無需trusted setup，且證明空間復雜度為常數的，計算高效的零知識證明方案，簡稱ZK-ConSNARK。我們知道，一般情況下區塊鏈系統需要將交易通過p2p網絡傳輸給系統中每個驗證節點進行驗證。

因此，網絡單位時間能處理的交易數目，俗稱出塊率，很大程度上取決于區塊大小，以及單位交易所占空間大小【CDEGJKMSSSS16】。交易越小，則出塊率越高。在隱私保護區塊鏈方案中，交易大小又很大程度上取決于其所包含的零知識證明大小。

事實上，需要trusted setup的ZK-ConSANRK文獻里已有不少，Zcash所使用的方案就屬于這個類別。但無需trusted setup的ZK-ConSNARK卻是稀有品種，目前本人所能找到這方面的結果只有兩篇：Crypto 2019年新鮮出爐的結果【LM19, BBF19】。這篇文章將簡單介紹這兩個方案的基本思路以及Suterusu項目在ZK-ConSANRK上的關注點。

上述兩篇論文【LM19, BBF19】都結合了概率性可驗證證明(Probabilistically Checkable Proof，PCP)和子向量承諾(Subvector Commitment)方案。PCP是復雜性理論和密碼學里一個非常經典的結果，相關定理的提出者因此獲獎無數。

PCP作為一個基礎方案可用于構造零知識證明。上述兩篇論文主要貢獻不在于PCP，而在于這個子向量承諾方案。其原因在于PCP方案如果想在非交互式零知識證明這個領域施展身手離不開高效的子向量承諾方案這個助手。

什么是概率性可驗證證明

首先，我們簡單介紹下什么是概率性可驗證證明。我們在前文【林19-1】中介紹過零知識證明的概念。零知識證明中有這么個驗證者的概念，在PCP中也有個驗證者。但PCP的驗證者特別懶，所以我們需要考慮驗證者如何能在做非常少工作的情況下，還能準確判斷PCP證明者針對一個定理提供的證明是否正確。

盡管PCP本身的證明是非常長，但PCP有個神奇的性質就是在證明者生成證明后，驗證者只需隨機在證明上查詢若干點(實際中大概是安全系數×3bits即可，所以如果是256-bit security，查詢長度只需256*3 bits)，然后做一些極為高效的運算就可以驗證證明的正確性。

我們在前文【林19-1】中提過，區塊鏈中使用的零知識證明需要是極為簡短的且最好計算也是高效的，盡管PCP的驗證計算頗為高效，但證明過長仍是個弊病。我們注意到在驗證時驗證者真正需要訪問的只是整個證明中極小一部分內容。

那么問題來了，有沒有可能讓證明者在生成PCP證明后自己在證明上隨機選取驗證者需要的查詢點，然后只傳輸這些信息給驗證者，從而大大減少通信量呢?

這個思路是對的，但一個惡意的證明者，或者一個不掌握證明秘密的人可以針對這個簡單思路發起如下幾個攻擊：比如可能這個用于隨機選取查詢點的隨機數本身不隨機，或者攻擊者先生成隨機數，然后再針對這些隨機位置生成對應證明，換句話說他可能沒有能力生成全部正確PCP證明，但他卻有辦法針對提前生成的隨機位置生成合法的部分證明，進而相應地替換篡改他所生成的非法證明的對應位置內容，從而通過驗證。

什么是子向量承諾

如何防止這類攻擊呢?這就需要引入我們的子向量承諾方案了。首先，我們先說下2019年前的工作中如何解決這個問題。承諾這個概念我在前面介紹Mimblewimble的文章【林19-3】中曾提到，事實不僅僅有Pedersen承諾方案，我前面關于Zcash的文章【林19-2】中提到的Merkle tree也可以被看作是一種承諾方案。

那么具體Merkle tree可以怎么和PCP結合呢?

證明者首先生成PCP證明，這些證明每個bit將作為Merkle tree的一個葉節點來計算哈希樹根節點數值，這個數值就是一個對上述PCP證明的承諾了。

我們之前提過承諾方案有個soundness性質可以保證一旦承諾公開，用戶是沒法在打開承諾時改變承諾的內容的，在Merkle tree中這個性質主要是由所使用哈希函數的抗碰撞性來保證的。

那么好，證明內容一旦生成無法篡改了，接下來的問題就是隨機性如何解決的問題了?如果Merkle tree現在的根節點值是r的話，那么用于決定證明查詢位置的隨機數將被定義成H(r)，這里H是個安全哈希函數，比如SHA256。

為什么這能保證H(r)是隨機的呢?

這個是和哈希函數的理論建模有關的。密碼學理論里一般把H(.)建模成隨機預言機，這意味著即使哈希函數的輸入是公開的，其輸出也是完全隨機的。

哈希函數的這個隨機預言機模型和承諾方案的soundness性質合力保證驗證者可以相信這個隨機數是在證明者把PCP證明關進承諾這個箱子之后才生成的，且這個用于定義證明查詢位置的隨機數確實是隨機的。因此如果他確定后面承諾打開過程中顯示的消息確實是這些隨機數對應的位點信息后，那么上述攻擊就可以被認為是無效的。

好，那么現在問題就規約到如何保證證明者在承諾打開階段輸出的信息確實是對應由這些隨機數定義的位置的。在Merkle tree這種承諾中，每個打開的消息同時還會有一些附屬的證明信息來證明這個打開的消息確實是某個葉節點位置的信息。但注意這個承諾方案的附屬證明空間復雜度不是常數，而是PCP空間復雜度的對數。

另外，由于Merkle tree每次只能打開一個證明位點，上述證明過程需要重復和安全參數相關的次數(比如256*3次)，這就導致證明所占空間無法避免地膨脹。【LM19】文章提到如果一個PCP所占空間為1GB，使用Merkle tree這種承諾方案，對應的最終零知識證明所占空間為88KB，且絕大部分都是由Merkle tree的這種附屬證明導致的額外開銷。

現在，我們終于可以介紹什么是子向量承諾了，事實上，Merkle tree可以看作一種非常簡陋的子向量承諾方案。和Merkle tree一樣，Crypto 19提出的子承諾方案可以一次性把整個向量裝進承諾這個黑箱里，但和Merkle tree不同的是，在打開承諾階段，用戶可以同時打開和向量若干個位置綁定的內容，而且對應的證明空間復雜性為常數。這個方案的構造需要用到一個特殊的代數結構，叫group of unknown order。

事實上，這個概念可以看作RSA group的一種抽象。但RSA group對應方案需要trusted setup，所以不太適用于隱私保護區塊鏈系統。目前也存在無需trusted setup的RSA group方案，但效率極低。所以上述兩文都提到了另外一種基于class groups of quadratic imaginary order的代數結構來保證無需trusted setup的高效子向量承諾方案。

Suterusu的關注點

盡管上述兩文的方案已能實現可高效驗證的ZK-ConSNARK，但底層基于的PCP方案由于生成證明的開銷太大無法實際應用，但他們起碼從理論上證明了無需trusted setup的ZK-ConSNARK的可行性。Suterusu將針對去中心化隱私支付這種特殊的應用場景優化實現一些特殊的ZK-ConSNARK，來推進隱私保護區塊鏈的效率和去中心化程度。（林煌）

關鍵詞： ZK-ConSNARK trusted setup 隱私