暸解 Plonk
在撰寫 SNARKs 的應用程式時，最令人頭痛的就是可信任設置，每個應用都需要建立自己的可信任設置。在 Plonk 出現後，一切就不一樣了，Plonk 的可信任設置是通用的且可以更新的，因此在未來 SNARKs 應用的開發上，就更加友善了。
以下提的 Plonk，都是指 Plonk + Kate Commitment Scheme，也因為 Kate commitment 需要可信任設置，Plonk 才會需要。若把 Kate commitment 換成 FRI 則不需要可信任設置（但是證明大小會增加 1 - 2 個數量級），Polygon 新推出的 Plonky2 就是 Plonk + FRI 的證明系統。
在閱讀前，建議對 SNARKs 有基本了解，本文比較著重於跟以往的 Groth16 不同作比較。建議具備以下知識
- Lagrange Polynomials，知道這是的作用，不需要知道背後數學原理
- 基本的 ECC 運算。例如：橢圓曲線上 G 代表的意思。假如 P = p * G，知道 P 並不能回推 p（離散數對問題）
- Merkle tree 及 Merkle root 計算
- 對於基於 Groth16 的 SNARKs 有基本概念，重複或類似的部分會快速帶過，可以參考深入瞭解 zk-SNARKs。
這篇文章的思路及計算沿用 PLONK by Hand 這系列文章，以畢氏定理產生零知識證明，畢氏定理就是直角三角形邊長的公式，其方程式為 a² + b² = c²。以下我們用邊長（3, 4, 5）作為例子。
單位根（Roots of Unity）
在實務上使用單位根作為 x 值（以 ω 的次方 1, ω, ω², ω³… 來表示），因單位根的數學特性，可降低運算的複雜度，所以實際計算上不會用整數（1, 2, 3…）當作多項式的 x 值。此外單位根也可簡化後續的複雜驗證。如果是想深入瞭解 Plonk 論文中的公式，這是需要具備的知識，但若只是想理解 Plonk 的概念，可以把後面的 1, ω, ω² … 想像成整數 1, 2, 3… 即可。
借用 PLONK by Hand 系列文章 中的範例，使用質數 17 的域（𝔽₁₇）來產生證明，根據下圖計算，可得四次單位根為 H:{1, 4, 16, 13}。
多項式承諾（Polynomial Commitments）
在開始之前，先了解一下多項式承諾。多項式承諾在近兩年以太坊的研究中越來越常出現，了解何為多項式承諾，對於了解以太坊近期的研究也有所幫助。但在介紹多項式承諾前，先認識什麼是承諾。通常的應用場景是將一個承諾跟一組資料做綁定，且因密碼學特性，若將資料修改則無法得到同樣的承諾。舉例來說，在線上參加猜謎遊戲，不想先把自己的答案公開，但同時又需要讓其他人知道你已經作答，這個時候就可以先送出一個承諾（例如，把答案做雜湊）。等答案公布之後，再公開你的答案，並證明先前送出的承諾（雜湊值）是由你的答案所產生的。一個日常的例子，就是在網站上下載檔案，下載後會驗證雜湊值，來確認是否和原本要下載的檔案相同，以防檔案在傳輸中途有被篡改過。
區塊鏈常用的 Merkle tree 也是一種承諾，屬於向量承諾（vector commitment），產生承諾的證明為一串固定數量的數值。舉例來說，有個數列從 a₀, a₁, …, a₁₀₂₃，共1024個， 使用 Merkle tree 來產生承諾，則證明的數量為 log₂ⁿ = 10（一個陣列長度為 10，每個值為 32 bytes）。若我們把數列變成多項式的係數，如 p(x) = a₀ + a₁x + a₂x² + … + a₁₀₂₃x¹⁰²³，那我們的證明數量就只剩 1（x 在某個隨機點 z 的值）。所以藉由多項式承諾，能大幅減少證明的數量。
接下來快速解釋如何驗證多項式承諾（以下皆有在 深入瞭解 zk-SNARKs 一文解釋過，這邊快速帶過）。想證明 p(z) = a，可以藉由證明
(p(x) - a) / (x - z) 是否能整除得到多項式 Q(x)
若成立，則代表 (x - z) 為 p(x) - a 的因數。接著就是 z 點怎麼選擇，在非互動的前提下，藉由可信任設置得到 G, s*G, s²G… sⁿG，這串值是由點 s（所謂的有毒廢棄物（toxic waste））經過橢圓曲線做同態隱藏（HH）所得到的。因此可算出 p(s) = a₀ + a₁(G) + a₂(s²G) + … + a₁₀₂₃(s¹⁰²³G)。回到 Q(x) ，移項後可得
因為橢圓曲線上兩個點只能相加無法相乘，因此這裡需要用到橢圓曲線配對（pairing）才能做到 Q(s) * (s - z)。配對的計算這邊也不贅述，最終的式子如下
多項式承諾在近期最常使用的是 Kate commitment，除了在本文的 Plonk，在 Vitalik 提出的 Verkle Tree 也是，是以太坊近期研究中，最常使用的是多項式承諾。不過 Kate commitment 也不是萬靈丹，如上述 Kate commitment 需要可信任設置，但是 Kate commitment 厲害的地方就是只需要一個可信任設置就可以執行任意程式＊，跟以往一個可信任設置對應一個程式邏輯是很不一樣的。有興趣可以去看 Dankrad 所寫的 KZG polynomial commitments。
＊任意程式必須是其多項式的次方須小於可信任設置的次方。舉上述例子來說，以 p(x) 作可信任設置，但欲執行程式的多項式有 1024 次方，則無法執行。
Plonk 限制式方程式（Constraint Equation）
接著切入正題。回到畢氏定理（ a² + b² = c²）的例子，將方程式一步步拆解，可以拆為四個單一運算的方程式，這又稱為限制式（constraint）。Plonk 算術電路的方程式為
Q 的下標符號，L 代表左，R 代表右，O 代表輸出，M 代表相乘，C 代表常數
接著，就是用上述 Plonk 算數電路方程式來表達上面四個限制式。前三個都是乘法，所以就只有 Q_M 跟輸出 Q_O 不為零。而最後一個是加法運算，因此 Q_L 及 Q_R 跟輸出 Q_O 不為零。計算如下：
以邊長（3, 4, 5）為例，則
接著，使用 Lagrange 插值法來算出多項式 fa(x), fb(x) 跟 fc(x)， 如”單位根”小節所說，可以使用整數（1, 2, 3, 4）來做計算。但這裡我們跟隨 PLONK by Hand 的例子使用單位根 H{1, 4, 16, 13} 當作 x 來推算多項式
最終可得 fa(x), fb(x) 及 fc(x)
最終證明也會需要 Q_L 到 Q_C 等多項式，不過本文不會用到，故不寫出。
與 R1CS 比較
在 Plonk 中，每個電路限制式只能有一個加法或是乘法，而 R1CS 系統裡，每個電路一樣只能有一個乘法運算，但是可以有無限個加法運算。這個特性使得 Plonk 的電路會比以往的 Groth16 的電路還要更大。不過 Plonk 可以開外掛使用自訂邏輯閘（custom gate）跟查表，使得電路的彈性更大，克服先天的劣勢，文章最後會簡單提一下。
Groth16 是藉由 R1CS 的方式做電路轉換，R1CS 不是 Groth16 專屬的一個方式，只是在 Plonk 之前，Groth16 是最被廣用的 SNARKs ，所以通常提 R1CS 都是以 Groth16 為代表，下面可以把 Groth16 跟 R1CS 當作同義字做理解。
為什麼 R1CS 可以有無限的加法？這邊以 Vitalik 文章 QAP: from Zero to Hero 中的例子做解釋。 首先，Groth16 算數電路的方程式如下
文章中要產生證明的多項式為 x³ + 3x + 5 = 35，將電路拍平（flattern）後，可以得到這些變數 (x, ~out, sym_1, y, sym_2)，接著決定向量 s = [~one, x, ~out, sym_1, y, sym_2]。以 sym_2 = y + x 這個運算為例，可以得到 A, B, C 三個向量
A = [0, 1, 0, 0, 1, 0]
B = [1, 0, 0, 0, 0, 0]
C = [0, 0, 0, 0, 0, 1]
看圖比較好理解。陣列 A 所代表的是把 x 加上 y，若把 A 的第一個值改成 1（ A = [1, 1, 0, 0, 1, 0]）， 那得到的就是 (x + y + 1)，而這樣的改變並不會使算數電路變多一筆。由此可以看到，在 R1CS 系統裡，加法是被包含在 R1CS 這個大矩陣裡，因而不需要額外的限制式。因為 Plonk 跟 R1CS 電路的形式不同，所以有如此不一樣特性。
相等限制式（Copy Constraints）
相等限制式限制了不同邏輯閘之間變數的必須相等。
我們可以把上述的限制式畫成下圖的邏輯閘。到目前為止，每個限制式都還是獨立沒有相互關聯的。接下來，需要把每個限制式之間的關聯銜接起來，定義某個邏輯閘的某一變數（有可能是輸入或輸出）必須等於另一個邏輯閘的某一變數（如圖中橘色虛線部分），而這就叫做相等限制式。而一樣會藉由多項式來定義相等限制式。
跨邏輯閘間的變數需相等，基本上就是在證明存在兩個多項式 f, g ，滿足 f(x) = g(y)。以上圖橘線來說，就是 fa(4) = fc(1), fb(4) = fc(2), fc(3) = fc(4)。在 Plonk 中，定義了下列多項式 f(i), g(i) 跟 Z(i)，並且要滿足 Z(i) = Z(i-1) * f(i) / g(i)。
在此 f(i) 代表多項式，fᵢ 代表數列，g, Z 同理
稍後再來解釋上述方程式。我們先從另一個角度切入，假設有兩個長度相同的數列 fᵢ , gᵢ，想要證明且所包含的數相同（但順序不同）。例如，fᵢ = (0, 1, 3, 5, 7), gᵢ = (0, 5, 3, 1, 7)，那最直覺的方式就是把所有的數相乘。但若像範例的 fᵢ , gᵢ 有 0 或是證明者讓所有數都為 1，這樣的檢查就無效了。因此，我們可以藉由引進亂數（如上述 f(i) 中的 β 跟 γ），來解決 0 值或是都為 1 的問題，使得我們依然可以用相乘的方式來檢查兩數列。
瞭解 f(i) 之後，再來就是解釋 g(i) 中的 σ(i)。σ(i) 又稱為置換函數（在這節，不會計算方程式 σ(i)，為了方便說明，都以數列 σᵢ 做代表），置換函數提供了兩個數列之間索引值互換的資訊。以上述例子來說，f2 = g4, f4 = g2，我們可以得到 σᵢ =(1, 4, 3, 2, 5)，σᵢ 所代表的就是 “現在第 i 個位置的數值跟原本數列的第 σᵢ 個位置取得”。以 σ₁來說，就是現在第一個位置的數值（g2）等於原本數列的第三個位置（f4）。
回到上述的 Z(i)，Z(i) 是證明者所需提供的。要證明存在多項式 g(i)，使得 Z(i) = Z(i-1) * f(i) / g(i) 成立。然後我們來試著拆解 Z(i)，當 i = n
再把上述的數列 fᵢ , gᵢ 跟 σᵢ 帶入，
上下 (…) 是一樣的，可以消掉，所以偷懶沒寫出來。紅色的匡跟綠色的匡就是我們互換的兩個值（f2 = g4, f4 = g2）。式子列出來後可以發現，兩個值也是可以互相消掉的。因此最終可以得到 Z(5) = Z(0) = 1。
驗證者若只確認 Z(n) ?= 1，很容易被證明者呼嚨，所以驗證者除了確認 Z(n) = 1 之外，還是需要確認中間值 Z(i) = Z(i-1) * f(i) / g(i), i = n - 1, n - 2, …, 1。
這裡為了方便理解，i 都為整數，但在實際的應用上，會使用單位根 ω 作為索引值。1, 2, 3, …n 則改為 1, ω, ω², ω³ …ωⁿ。
跨多項式
為了方便解釋，上面使用了單一多項式作解釋。回到畢氏定理的例子，以上圖來說，我們需要定義 a4 = c1, b4 = c2 等跨數列的數值交換。為了避免索引值有重複，而這邊 i 值用了一些技巧，把每個數列串起來，aᵢ 的 i = 1 ~ n，bᵢ 的 i = n + 1 ~ 2n，cᵢ 的 i = 2n + 1 ~ 3n。若以單位根來表示，就是 1 ~ ωⁿ⁻¹, g * (ωⁿ ~ ω²ⁿ⁻¹), g² * (ω²ⁿ ~ * ω³ⁿ⁻¹)（g 是為了避免索引值重複而存在，實際上不是任意數。不過為了理解方便，可以將 g 視為域裡面的任意數）。
置換函數的計算
接著試著來計算看看置換函數。在利用 Lagrange 插值法產生置換函數之前，還需要幾個數字當作 x 的值（也就是上一節的 i 值）。可以簡單把單位根 H 乘上常數來做使用，分別為 2H:{2, 8, 15, 9} 跟 3H:{3,12, 14, 5}。
接著，定義三個多項式 σ₁(x), σ₂(x) 跟 σ₃(x)，分別用 H, 2H 跟 3H 來作為 x 座標值。而這三個多項式代表 fa(x), fb(x) 跟 fc(x) 的置換多項式。
根據畢氏定理（a² + b² = c²），可以得到
a1 = b1 (a²)
a2 = b2 (b²)
a3 = b3 (c²)
a4 = c1
下圖是每個邏輯閘變數之間的關係，再透過 Lagrange 插值法可以得出下圖右邊的 σ₁(x), σ₂(x) 跟 σ₃(x) 三個多項式。
與 Groth16 比較
為什麼 Groth16 不需要 copy constraint equation??
我們一樣用 QAP: from Zero to Hero 作為例子，回到 R1CS 那小節，s = [~one, x, ~out, sym_1, y, sym_2]，s 除了定義了輸出（~out），也定義了計算的中間值（sym_1, sym_2），所以在運算過程中就已經把前後關係在矩陣裡定義好了。以本文用的畢氏定理來說，下圖可以看到使用 Groth16 跟 Plonk 之間算數電路的不同
小結
本文是以畢氏定理作為例子，利用 Plonk 的限制式多項式，將畢氏定理轉成四個限制式。接著藉由相等限制式的公式來定義每個限制式之間的關係（須滿足 Z(i) = Z(i-1) * f(i) / g(i)），過程中得到置換函數σ₁(x), σ₂(x) 跟 σ₃(x)。為了要產生證明，需要把 aᵢ, bᵢ, cᵢ（witness）轉成多項式 a(x), b(x) 跟 c(x)。
而上述多個多項式的驗證，則透過多項式承諾來驗證（透過 s 來產生承諾，從 驗證 Q(s) = (p(x) - a) / (x - z)）是否成立），而最終的證明只會有數個承諾而已。
補充：自訂邏輯閘（custom gate）
最後補充一下自訂邏輯閘，本身還沒有很深入的了解，這邊只是簡單介紹一下我所知道的。舉例來說，若在算數電路有這樣的運算 c(i) = a(i) * b(i) * c(i-1)，則可將限制式方程式改為如下，一樣藉由控制 Q_L, Q_R, … Q_P 的值來符合我們要的算數電路。
