文章閱讀頁通欄

零知識證明 - DIZK介紹

來源: 星想法 作者:Star Li
經常有人在提及超大電路證明的時候,談到DIZK。最近有空,我就看了看DIZK的論文以及源代碼。總的來說,從技術人的角度來說,還是有點驚喜,DIZK利用分......
經常有人在提及超大電路證明的時候,談到DIZK。最近有空,我就看了看DIZK的論文以及源代碼。總的來說,從技術人的角度來說,還是有點驚喜,DIZK利用分布式數據處理Apache Spark平臺,實現了zk-SNARK證明系統。

DIZK論文是Howard Wu等在2018年發表。論文的下載地址如下:

https://eprint.iacr.org/2018/691.pdf

DIZK,Distributed Zero Knowledge,分布式的零知識證明系統。在分布式環境下,DIZK能支持超大規模電路(10億門級別)的計算。而且,論文給出的測試數據表明,DIZK的計算性能隨著分布式實例的增長,線性增長。

1. DIZK邏輯框架

雖然DIZK是分布式零知識證明系統,零知識證明的協議和計算和傳統的證明系統非常像。論文通過兩張圖給出了兩者的區別和聯系:

左邊代表的是傳統的零知識證明(zk-SNARK)系統,主要由三部分計算組成:Setup/Prover/Verifier。右邊代表是DIZK的邏輯框架。DIZK將Setup/Prover的計算用分布式實現,計算之間的依賴也用分布式數據表示。Verifier相對來說簡單(毫秒級的計算),不需要分布式實現。

2. R1CS/QAP和Groth16

Prover生成證明,計算公式如下:

Verifer驗證某個證明是否成立,計算公式如下:

3. Apache Spark

Apache Spark是大數據分布式處理框架。可以查看Spark官方介紹理解Spark的一些邏輯:

http://spark.apache.org/docs/latest/cluster-overview.html

物理上,Spark框架包括三個角色:Driver Program就是Spark框架上編寫的程序,Cluster Manager就是集群管理節點,Worker Node就是集群節點。從軟件角度看,SparkContext維護了整個程序的執行環境。所有的計算會分解成一個個的Task,所有的Task都由Executor執行。

RDD(Resilient Distributed Datasets)是Spark框架下大數據的表示。你可以理解,RDD是分布式的數據表示。

DIZK設計中,R1CS的電路采用RDD數據表示,因為R1CS電路隨著電路門的個數變大而變大。Pk(pubilc key)頁是隨著門和R1CS的contraint的個數變大而變大,也采用RDD表示。輸入信息包括兩部分:公開的輸入信息和隱私的輸入信息。一般來說,公開的輸入信息比較小,DIZK直接采用一般向量表示。隱私信息采用RDD數據表示。

4. DIZK計算框架

在Spark的框架上,DIZK設計了Setup和Prover的計算框架:

Setup包括兩步:1)Lag(拉格朗日插值),R1CS到QAP的轉化過程 2)fixMSM - 定點的多倍點加法。Prover也包括兩步:1)FFT(計算H多項式)2)varMSM - 不定點的多倍點加法。

DIZK在第4章詳細描述了FFT/Lag/fixMSM/varMSM四個計算都能采用分布式算法。簡單的說,FFT的分布式算法相對復雜一些,其他三個計算天生可以分布式計算。

分布式計算的核心,是讓多個executor執行的計算量盡量均勻。在Lag的計算步驟中,因為R1CS的(1+N)xM的矩陣是稀疏矩陣,DIZK提出了讓多個executor均勻計算的方法。

Lag的計算的公式如下:

如果a矩陣是個密集型矩陣的話,只要均勻的切分計算量即可。但是,在現實應用中,a矩陣是個稀疏矩陣。DIZK提出的方法也比較簡單明了:預先處理矩陣,統計每列的非零個數。非零個數,代表了計算量。然后再根據這些非零個數,確定計算量的劃分。

5. DIZK計算性能

DIZK論文給出了分布式計算的測試結果:

簡單的說,DIZK的Setup和Prover計算性能隨著計算節點的個數增長成線性增長。

總結:

DIZK,是在Spark大數據計算框架下的分布式零知識證明系統。DIZK詳細分析了Groth16的計算,并針對幾個計算模塊提出了分布式計算算法。從DIZK的測試數據看,DIZK的Setup和Prover計算性能隨著計算節點的個數增長成線性增長。

關鍵詞: 零知識證明  DIZK  
0/300
? 波克城市捕鱼游戏 下载真人麻将 精选三肖三码中特期期准 陕西丫丫麻将怎样带挂 新浪福建22选5走势图 街机金蟾捕鱼2赢话费 申城棋牌下载? 20选5开奖查询最新 现在上证指数是多少 在家上班赚钱 丫丫陕西麻将下载 秒速赛车人工计划在线 大圣闹海捕鱼游戏中心 极速飙车破解版 龙江福彩p62开奖 海螺水泥股票分析 如何通过网络赚钱