零知識證明 - PLONK電路原理

買賣虛擬貨幣
Groth26演算法確實比較美,優點是證明小,非常適合鏈上驗證的場景。但是,Groth26演算法需要可信的初始設定(Trusted Setup),而且每個電路都需要初始設定。特別在業務電路升級的時候,還需要重新初始設定。PLONK演算法,只需要一次初始設定(Universal Trusted Setup)。初始設定的引數可以升級,而且在電路大小不超過範圍的情況下,不需要重新設定。理解PLONK演算法,可以先從PLONK的電路開始。熟悉Groth26演算法的小夥伴都知道,Groth26演算法基於QAP問題。所有的計算電路可以透過R1CS,轉換成QAP問題。PLONK的電路描述採用不同的方式。Vitalik的這篇Blog對PLONK電路的解釋非常清楚,感興趣的小夥伴可以直接看原文:https://vitalik.ca/general/2019/09/22/plonk.htmlPLONK電路

PLONK的電路由加法門/乘法門以及一些常量組成。以P(x) = x^3 + x + 5 = 35為例:

對電路中的常量以及加法門/乘法門進行編號和標註,乘法門和加法門都由三組連線組成:a/b/c,分別代表一種門的兩個輸入(左右輸入)和一個輸出。

以編號為1的乘法門舉例,這個乘法門約束a1*b1=c1。

門約束

PLONK演算法採用兩種約束關係描述整個電路:1/ 加法門/乘法門約束 2/ Copy約束。因為加法門和乘法門,只描述單個門的依賴關係,所以要加上Copy約束才能描述確定的完整電路。所謂的Copy約束,其實就是門和門之間的“共享”連線。從加法門和乘法門約束說起。

因為“門”的描述需要包括三種情況:1/乘法門 2/加法門 3/常量,PLONK系統定義了通用的表示公式:

其中L代表左輸入,R代表右輸入,O代表輸出,M代表乘法,C代表常量。在這種的透過公式下,乘法門/加法門以及常量採用不同的係數。

加法門,採用如下的係數:

乘法門,採用如下的係數:

常量,採用如下的係數:

簡單的說,在通用公式下,所有電路中的門和變數都可以表達。而這一系列的表示式,可以用多項式進行“壓縮”,表示為:

也就是說,電路中的所有加法門/乘法門以及常量的關係可以透過一個多項式進行表示。

Copy約束

顯然,上述的門和常量的約束,只是約束獨立的,相互不依賴的約束關係。在這些約束關係的基礎上,加上“Copy約束“, 門和門之間的連線關係,整個電路就確定了。在介紹Copy約束之前,先介紹一下“座標點累加” (coordinate pair accumulator)。

假設X(x)和Y(x),定義了一系列的X/Y的座標點。x從0開始。p(x)為從0到x(不包括)的座標點累加,定義如下:

p(0) = 1
p(x+1) = p(x)*(v1+X(x)+v2*Y(x))
以Y(x) = x^3 - 5*x^2 + 7x -2 為例,並且v1=3, v2=2 :

簡單的說,p(x)把一系列的座標點累加。因為乘法的交換律,這種累加演算法,並不區分座標點的順序。如果只改變X(x)的點的順序,在累加結果相同的情況下,可以推匯出Y(x)的關係。舉個例子:

一個累加器計算:(0,a(0)),(1,a(1)),(2,a(2)),(3,a(3)),(4,a(4))

另外一個累加器計算:(0,a(0)),(3,a(1)),(2,a(2)),(1,a(3)),(4,a(4))

這兩個累加器計算結果相同,在v1,v2隨機選擇的情況下,可以推匯出a(1) = a(3)。a(1)=a(3)就是Copy約束,第1個門的左輸入和第3個門的左輸入相同。

電路中總共有三組連線:a/b/c。為了表示,不同連線之間的Copy約束,三組連線採用統一的編號。假設總的門的個數為n,a的連線編號從0~n-1,b的連線編號從n~2n-1,c的連線編號從2n~3n-1。也就是說,Xa(x) = x, Xb(x) = n+x, Xc(x) = 2n+x。在舉個例子,比如n=5,為了證明a(2) = b(4), Xa(x)=01234, X'a(x) =01934, Xb(x)=56789, X'b(x) = 56782。

如果在X(x)交換了順序後,pa(n)*pb(n)*pc(n) = p'a(n)*'pb(n)*p'c(n) ,就可以證明交換了連線編號有“連線”關係,相應的Copy約束成立。

特別注意的是,X'a(x), X'b(x), X'c(x)只改變的是X的編號,並不改變Y的結果。

電路驗證

真實的電路計算在有限域,電路中的門的編號並不是整數,而是omega(omega是有限域中的根)。

在上述的電路描述方法下,整個電路需要驗證如下的關係:

1/ 各個門的關係是否正確

2/ 門和門之間的連線正確

先確定累加的計算在X編號變化前後的計算正確。

再確認累加結果的初始和最後一致。

以上介紹了PLONK電路描述和約束的基本原理,具體的PLONK演算法後面的文章會具體介紹。PLONK演算法為什麼能做到Universal,具體的協議過程和計算如何,敬請期待~

總結:

PLONK演算法的電路採用新的描述模型。整個電路由閘電路約束和Copy約束(連線約束)組成。閘電路約束和Copy約束都轉換為多項式表達。Copy約束透過累加演算法實現。

免責聲明:

  1. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读

;