PLONK 約束系統完整數學推導與安全性證明：從電路錶達到零知識電路的工程實踐

概述

PLONK（Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge）是由 Ariel Gabizon、Zachary J. Williamson 和 Oana Ciobotaru 於 2019 年提出的通用零知識證明系統。本文提供 PLONK 約束系統的完整數學推導，從電路錶達、多項式構造、置換約束、到安全性證明的每一步驟進行詳細分析。截至 2026 年第一季度，PLONK 及其變體已成為以太坊 L2 生態系統的核心技術基礎——Aztec 的 Noir 語言、Polygon zkEVM、Zcash Sapling 等主流項目皆基於 PLONK 家族構建。

第一章：電路錶達與約束系統基礎

1.1 算術電路的表示方法

PLONK 將算術電路轉換為一組多項式約束。設電路包含 $n$ 個乘法門，我們首先定義電線（wire）的概念。

定義 1.1（電線）：電路中的每條連接線稱為電線，用變數 $ai, bi, c_i$ 表示第 $i$ 個門的左輸入、右輸入和輸出。

定義 1.2（複製約束）：若兩條電線實際連接相同值，則存在複製約束。例如，若門 1 的輸出是門 2 的左輸入，則 $c1 = a2$。

定義 1.3（PLONK 門約束）：每個乘法門需滿足以下約束：

$$qM \cdot ai \cdot bi + qL \cdot ai + qR \cdot bi + qO \cdot ci + qC = 0$$

其中 $q_*$ 為選擇器多項式（selector polynomial）的取值，決定該位置執行的約束類型：

1.2 從電路到約束矩陣

令電路包含 $n$ 個門，定義以下矩陣：

┌─────────────────────────────────────────────────────────────┐
│                  PLONK 約束矩陣結構                          │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│   ┌       ┬       ┬       ┬────────┬────────┬────────┐     │
│   │   a   │   b   │   c   │  q_L   │  q_R   │  q_M  │     │
│   ├───────┼───────┼───────┼────────┼────────┼────────┤     │
│   │  a_1  │  b_1  │  c_1  │ q_{L,1}│ q_{R,1}│ q_{M,1}│   │
│   │  a_2  │  b_2  │  c_2  │ q_{L,2}│ q_{R,2}│ q_{M,2}│   │
│   │  ...  │  ...  │  ...  │  ...   │  ...   │  ...  │     │
│   │  a_n  │  b_n  │  c_n  │ q_{L,n}│ q_{R,n}│ q_{M,n}│   │
│   └───────┴───────┴───────┴────────┴────────┴────────┘     │
│                                                             │
│   約束方程：q_M·a·b + q_L·a + q_R·b + q_O·c + q_C = 0      │
│                                                             │
└─────────────────────────────────────────────────────────────┘

示例電路：計算 $y = (x1 \cdot x2) + (x3 \cdot x4)$

門 1：$a1 = x1, b1 = x2, c1 = t1$（乘法門）

門 2：$a2 = x3, b2 = x4, c2 = t2$（乘法門）

門 3：$a3 = t1, b3 = 1, c3 = y$（加法門，等價於 $t_1 + 0 \cdot 1 = y$）

選擇器配置：

• 門 1：$qM = 1, qL = qR = qO = q_C = 0$
• 門 2：$qM = 1, qL = qR = qO = q_C = 0$
• 門 3：$qM = 0, qL = 1, qO = 1, qR = q_C = 0$

第二章：拉格朗日基底多項式

2.1 有限域上的 $n$ 個單位根

PLONK 需要 $n$ 個 $n$ 次單位根。設 $\mathbb{F}_p$ 為質數 $p$ 的有限域，選擇 $n$ 使得 $n | (p-1)$。

定義 2.1（生成元）：令 $\omega$ 為 $\mathbb{F}_p^*$ 的生成元，則 $n$ 個單位根為：

$$\omega^i = \omega^i, \quad i = 0, 1, \ldots, n-1$$

滿足 $\omega^n = 1$ 且 $\omega^i \neq 1$ 當 $i < n$。

定理 2.1（正交性）：拉格朗日基底多項式滿足：

$$Li(\omega^j) = \delta{ij} = \begin{cases} 1 & \text{若 } i = j \\ 0 & \text{若 } i \neq j \end{cases}$$

推導：定義拉格朗日基底：

$$Li(X) = \prod{j \neq i} \frac{X - \omega^j}{\omega^i - \omega^j} = \frac{1}{n} \sum_{k=0}^{n-1} \omega^{(i-j)k}$$

代入 $X = \omega^l$：

$$Li(\omega^l) = \frac{1}{n} \sum{k=0}^{n-1} \omega^{(i-l)k} = \begin{cases} 1 & \text{若 } i = l \\ \frac{1 - \omega^{(i-l)n}}{1 - \omega^{i-l}} = 0 & \text{若 } i \neq l \end{cases}$$

$\square$

2.2 插值多項式

任意定義在 $\{\omega^i\}$ 上的函數 $f$ 可唯一表示為：

$$f(X) = \sum{i=0}^{n-1} fi \cdot L_i(X)$$

其中 $f_i = f(\omega^i)$。

電線多項式的構造：

$$A(X) = \sum{i=0}^{n-1} ai \cdot Li(X), \quad B(X) = \sum{i=0}^{n-1} bi \cdot Li(X), \quad C(X) = \sum{i=0}^{n-1} ci \cdot L_i(X)$$

選擇器多項式：

$$QL(X) = \sum{i=0}^{n-1} q{L,i} \cdot Li(X)$$

類似的定義 $QR(X), QM(X), QO(X), QC(X)$。

第三章：PLONK 約束方程的完整推導

3.1 基本約束方程

將電路約束寫成點值形式：對於每個 $i = 0, \ldots, n-1$：

$$qM(i) \cdot ai \cdot bi + qL(i) \cdot ai + qR(i) \cdot bi + qO(i) \cdot ci + qC(i) = 0$$

將其轉換為多項式形式：

$$P(X) = QM(X) \cdot A(X) \cdot B(X) + QL(X) \cdot A(X) + QR(X) \cdot B(X) + QO(X) \cdot C(X) + Q_C(X)$$

定理 3.1（約束滿足性）：電路約束被滿足當且僅當：

$$P(\omega^i) = 0, \quad \forall i = 0, \ldots, n-1$$

即 $P(X)$ 在所有單位根處為零。

證明：$\Rightarrow$ 方向。若電路約束被滿足，則對每個 $i$，上述點值方程成立。$P(X)$ 是連續函數，且在 $n$ 個點處為零。由於 $P$ 的次數最多為 $3n - 1$（見下節），但有 $n$ 個根，當 $n \geq 3n - 1$ 的條件下不一定成立。我們需要引入消失多項式。

$\Leftarrow$ 方向。若 $P(\omega^i) = 0$ 對所有 $i$，則每個點值約束成立，即電路約束被滿足。$\square$

3.2 消失多項式

定義 3.1（消失多項式）：

$$Z(X) = \prod_{i=0}^{n-1} (X - \omega^i) = X^n - 1$$

定理 3.2（消失性質）：$Z(\omega^i) = 0$ 對所有 $i$，且若 $Z(X) | Q(X)$，則 $Q(\omega^i) = 0$ 對所有 $i$。

引理 3.1（Z 是 $n$ 階消失多項式）：$Z(X)$ 在所有 $n$ 個單位根處為零，且是滿足此性質的首一多項式。

證明：$Z(X) = X^n - 1$ 的根正是所有 $n$ 次單位根。設 $Q(X)$ 是另一個在這些點處消失的多項式，則 $Q(X) = Z(X) \cdot H(X)$。若 $Q$ 次數小於 $n$，則 $H(X) = 0$。$\square$

3.3 商多項式與完整約束方程

定義 3.2（商多項式）：

$$H(X) = \frac{P(X)}{Z(X)}$$

為使 $H(X)$ 為多項式，$Z(X)$ 必須整除 $P(X)$。

約束條件的完整表述：

$$P(X) = Z(X) \cdot H(X)$$

或寫成：

$$QM(X) \cdot A(X) \cdot B(X) + QL(X) \cdot A(X) + QR(X) \cdot B(X) + QO(X) \cdot C(X) + Q_C(X) = H(X) \cdot (X^n - 1)$$

定理 3.3（完整性）：若存在多項式 $A, B, C, H, Q_*$ 滿足上述方程，則相應的電路實例是有效的。

推導步驟總結：

┌─────────────────────────────────────────────────────────────┐
│                  PLONK 約束推導流程                          │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  Step 1: 電路實例                                            │
│          (a_i, b_i, c_i) for i = 0...n-1                   │
│                    │                                         │
│                    ▼                                         │
│  Step 2: 拉格朗日插值                                        │
│          A(X) = Σ a_i · L_i(X)                              │
│          B(X) = Σ b_i · L_i(X)                              │
│          C(X) = Σ c_i · L_i(X)                              │
│                    │                                         │
│                    ▼                                         │
│  Step 3: 選擇器多項式                                        │
│          Q_L(X) = Σ q_{L,i} · L_i(X)                       │
│          ...                                                 │
│                    │                                         │
│                    ▼                                         │
│  Step 4: 約束多項式                                          │
│          P(X) = Q_M·A·B + Q_L·A + Q_R·B + Q_O·C + Q_C     │
│                    │                                         │
│                    ▼                                         │
│  Step 5: 商多項式                                            │
│          H(X) = P(X) / (X^n - 1)                            │
│                    │                                         │
│                    ▼                                         │
│  Step 6: 最終約束                                            │
│          P(X) - H(X)·(X^n - 1) = 0                          │
│                                                             │
└─────────────────────────────────────────────────────────────┘

第四章：置換約束的數學處理

4.1 複製約束的問題陳述

電路中的複製約束要求某些電線具有相同值。例如，若門 1 的輸出連接到門 3 的左輸入，則 $c1 = a3$。

定義 4.1（複製約束集合）：設 $\sigma$ 為將電線索引映射到其「拷貝目標」的置換。我們需要證明：對於所有電線 $i$，$wi = w{\sigma(i)}$。

4.2 Grand Product 論證

PLONK 使用 Grand Product（累積乘積）來處理置換約束。

定義 4.2（Grand Product 論證）：令 $S\alpha$ 和 $S\beta$ 為兩個多重集合。定義：

$$Z(X) = \prod{i=0}^{n-1} \frac{\alpha - S{\alpha,i}}{\beta - S_{\beta,i}}$$

其中 $\alpha, \beta$ 為驗證者選擇的隨機挑戰。

構造過程：

令 $S_\alpha$ 為「左輸入、右輸入、輸出」的索引集合：

$$S\alpha = \{a0, b0, c0, a1, b1, c1, \ldots, a{n-1}, b{n-1}, c{n-1}\}$$

令 $S\beta = \sigma(S\alpha)$ 為應用置換 $\sigma$ 後的集合。

定義 4.3（累積器多項式）：

$$Z{i+1} = Zi \cdot \frac{\alpha - S{\alpha,i}}{\beta - S{\beta,i}}$$

其中 $Z0 = 1$，$Zn$ 應為 1 若兩個集合相同（經適當排序）。

定理 4.1（置換檢查正確性）：$Zn = 1$ 當且僅當 $S\alpha$ 和 $S_\beta$ 包含相同元素（考慮重數）。

證明：

$$Zn = \prod{i=0}^{n-1} \frac{\alpha - S{\alpha,i}}{\beta - S{\beta,i}} = \frac{\prodi (\alpha - S{\alpha,i})}{\prodi (\beta - S{\beta,i})}$$

若 $S\beta = \sigma(S\alpha)$ 是 $S\alpha$ 的排列，則分子和分母相同，故 $Zn = 1$。

反之，若 $Z_n = 1$，則：

$$\prodi (\alpha - S{\alpha,i}) = \prodi (\beta - S{\beta,i})$$

對隨機 $\alpha, \beta$，這只有在 $S\alpha$ 和 $S\beta$ 包含相同元素時才可能。$\square$

4.3 置換約束的完整多項式處理

將 Grand Product 論證寫成多項式形式：

定義 $Z(X)$ 滿足：

$$Z(\omega^i) = Zi = \prod{j=0}^{i-1} \frac{\alpha - S{\alpha,j}}{\beta - S{\beta,j}}$$

約束方程：

$$Z(\omega \cdot X) - Z(X) = \frac{1}{\alpha - \beta} \cdot \left( \frac{\alpha - S\alpha(X)}{\beta - S\beta(X)} - 1 \right) \cdot Z(X)$$

其中 $\omega$ 為 $n$ 次單位根的生成元。

化簡：令 $S\alpha(X)$ 和 $S\beta(X)$ 為對應的拉格朗日插值多項式。

第五章：KZG 承諾與驗證協議

5.1 可信設置的數學結構

PLONK 需要結構化參考字串（SRS），由秘密值 $\tau \in \mathbb{F}_p$ 生成：

$$[1]1 = G1, \quad [\tau]1 = \tau G1, \quad \ldots, \quad [\tau^d]1 = \tau^d G1$$

$$[1]2 = G2, \quad [\tau]2 = \tau G2$$

其中 $G1, G2$ 為配對友好的橢圓曲線群，$[a]1 = a G1$。

定義 5.1（KZG 承諾）：對多項式 $f(X) = \sum f_i X^i$，承諾為：

$$\text{Commit}(f) = \sum fi \cdot [\tau^i]1 = [f(\tau)]_1$$

5.2 承諾階段

證明者對以下多項式計算承諾：

1. $A = [A(\tau)]_1$
2. $B = [B(\tau)]_1$
3. $C = [C(\tau)]_1$
4. $QL = [QL(\tau)]1$，類似的 $QR, QM, QO, Q_C$
5. $Z = [Z(\tau)]_1$（置換累積器）
6. $ZH = [H(\tau)]1$（商多項式承諾）

5.3 Fiat-Shamir 挑戰

為實現非互動式證明，使用 Fiat-Shamir 啟發式：

$$\alpha = H(\text{commitments}), \quad \beta = H(\alpha), \quad \gamma = H(\alpha, \beta), \quad \zeta = H(\alpha, \beta, \gamma)$$

其中 $H$ 為密碼學雜湊函數，輸入為承諾的位元組表示。

5.4 開放大學與驗證

證明者計算並發送：

• $A\zeta = A(\zeta), B\zeta = B(\zeta), C_\zeta = C(\zeta)$
• $S{\sigma1,\zeta} = S{\sigma1}(\zeta), S{\sigma2,\zeta} = S{\sigma2}(\zeta)$
• $Z_\zeta = Z(\zeta)$
• 線性組合多項式在 $\zeta$ 的開放大學

驗證者檢查：

1. 門約束：

$$e(QL + A\zeta \cdot QM + B\zeta \cdot QM \cdot A\zeta + A\zeta \cdot QL + B\zeta \cdot QR + C\zeta \cdot QO + QC - H\zeta \cdot Z(\zeta), [1]_2) = ?$$

1. 置換約束：

$$e(Z\zeta, [\tau - \zeta]2) = e(Z{H,\zeta}, [\tau]2 - [\zeta]_2)$$

其中 $Z_H$ 為置換 Grand Product 的商多項式。

第六章：安全性證明框架

6.1 代數攻擊模型

假設 6.1（$k$-多項式假設）：給定 $[1]1, [\tau]1, \ldots, [\tau^k]1$，沒有多項式時間算法可以計算 $[f(\tau)]1$ 對任意次數超過 $k$ 的多項式 $f$。

定義 6.1（知識 Soundness）：若存在一個 PPT（概率多項式時間）證明者 $P^*$ 能夠產生有效證明，則存在一個 PPT 提取器 $E$ 能夠恢復相應的 witness。

6.2 約束系統的安全性定理

定理 6.1（完美零知識）：PLONK 協議具有完美零知識性——驗證者無法從證明中學習任何關於 witness 的資訊（除了電路被滿足）。

證明構想：

1. 模擬器可以生成與真實證明不可區分的模擬證明
2. 模擬器知道 trapdoor $\tau$，可以「後門」生成任何所需的承諾
3. Fiat-Shamir 轉換保持零知識性

引理 6.1：對於任意非超多項式時間驗證者 $V^$，$V^$ 區分真實證明和模擬證明的優勢是可忽略的。

6.3 知識 Soundness 證明

定義 6.2（Extractability）：$(P, V)$ 系統具有知識 Soundness，若存在提取器 $E$ 使得：

$$\Pr[E^{\text{simulator}}(x, \text{trapdoor}) \text{ outputs } w : (P, V) \text{ accepts}\}] \approx \Pr[V \text{ accepts after interaction with } P]$$

定理 6.2（知識 Soundness）：在 $k$-多項式假設和隨機預言模型下，PLONK 具有知識 Soundness。

證明概要：

1. 反事實知識：假設 $P^*$ 能夠產生有效證明
2. 重繞技術：使用相同的隨機挑戰多次運行 $P^*$，變動部分承諾
3. 約束重構：從多次執行中重構多項式的知識
4. 提取：使用重構的多項式提取 witness

6.4 複雜度分析

定理 6.3（效率界）：

比較：相較於 STARKs（無需可信設置但證明較大，約 100KB+），PLONK 提供更小的證明大小，但需要可信設置。

第七章：實際電路設計範例

7.1 範例：電路約束實現

以下是一個簡單電路的 PLONK 約束系統實現（使用 Python 和惆號庫）：

# 電路：驗證 z = (x * y) + w
# 乘法門：x * y = t1
# 加法門：t1 + w = z

def build_circuit():
    """
    建立 PLONK 約束系統
    """
    n_gates = 3
    
    # 門配置
    # gate 0: 乘法 x * y = t1
    # gate 1: 乘法 w * 1 = t2 (等價於拷貝 w)
    # gate 2: 加法 t1 + t2 = z
    
    # 電線值 (a, b, c)
    a = [x, y, t1]       # 左輸入
    b = [y_var, 1, t1]   # 右輸入  
    c = [t1, t2, z]      # 輸出
    
    # 選擇器
    q_l = [0, 0, t1]      # 左輸入選擇
    q_r = [0, 0, t2]      # 右輸入選擇
    q_m = [1, 1, 0]       # 乘法選擇
    q_o = [0, 0, 1]       # 輸出選擇
    q_c = [0, 0, -z]      # 常數偏移
    
    return a, b, c, q_l, q_r, q_m, q_o, q_c

7.2 電路模擬驗證

def verify_plonk_circuit(a, b, c, q_l, q_r, q_m, q_o, q_c):
    """
    驗證 PLONK 約束被滿足
    """
    n = len(a)
    for i in range(n):
        constraint = q_m[i] * a[i] * b[i] + \
                     q_l[i] * a[i] + \
                     q_r[i] * b[i] + \
                     q_o[i] * c[i] + \
                     q_c[i]
        assert constraint == 0, f"Constraint violated at gate {i}: {constraint}"
    return True

7.3 實例化參數

電路深度選擇：

# 選擇電路大小為 2 的冪次
def select_circuit_size(constraints_count):
    """
    選擇最小的 2^k >= constraints_count
    """
    n = 1
    while n < constraints_count:
        n *= 2
    return n

# 示例：1000 個約束
n = select_circuit_size(1000)  # n = 1024

安全參數：

# BLS12-381 曲線參數
CURVE_ORDER = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
FIELD_MODULUS = 0x1a0111ea397fe69a4b1ba7b6434bacd76468b98f5e95cae12174b00000000001

# 群生成元
G1_GENERATOR = (0x17f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14ef3a33f17d, 
                0x8b3a5a5ba47e0835a9c96b0e0f1543e0a2e1f3f8f9e8d7c6b5a493827160f)

第八章：PLONK 變體與效能優化

8.1 PLONK 變體比較

8.2 性能瓶頸分析

定理 8.1（約束數量界）：對於 $n$ 個門的電路，PLONK 約束數量為：

$$|\text{constraints}| = 5n + 2n + 3n + n = 11n$$

其中：

• 5n：基本門約束
• 2n：置換約束（左右輸入）
• 3n：置換約束（輸出 + 2 個額外複製）
• n：商多項式約束

8.3 實務優化策略

class PlonkOptimizer:
    """
    PLONK 約束系統優化器
    """
    
    def optimize_circuit(self, constraints):
        """
        優化策略：
        1. 合併等價約束
        2. 消除恆等約束
        3. 優化選擇器佈局
        """
        # 步驟 1：識別恆等約束
        # 例如：q_L = 1, q_R = 0, q_M = 0, q_O = 1
        # 表示 a_i = c_i，這類約束可以直接傳遞
        
        # 步驟 2：合併相鄰約束
        # 將連續的同類約束合併為範圍約束
        
        # 步驟 3：選擇器優化
        # 使用更少的非零選擇器值
        
        pass

結論

本文提供了 PLONK 約束系統的完整數學推導，從電路表示、多項式構造、置換約束處理、到安全性證明的每一步驟。核心要點如下：

1. 約束表示：PLONK 使用統一的 $(qL, qR, qM, qO, q_C)$ 選擇器框架表達各類約束
2. 多項式承諾：透過 KZG 承諾實現對電線值的可驗證隱藏
3. 置換約束：Grand Product 論證提供對複製約束的有效驗證
4. 安全性：在 $k$-多項式假設下，PLONK 具有知識 Soundness 和完美零知識
5. 效率：固定大小的承諾和證明，適合作為 L2 批量驗證

PLONK 及其變體已成為構建高效零知識電路的行業標準，其數學優雅性和工程實用性的結合使其在以太坊擴容和隱私保護領域持續發揮核心作用。

參考文獻

1. Gabizon, A., Williamson, Z. J., & Ciobotaru, O. (2019). PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. IACR Cryptol. ePrint Arch.
2. Kate, A., Zaverucha, G. M., & Goldberg, I. (2010). Constant-size commitments to polynomials and their applications. ASIACRYPT 2010.
3. Boneh, D., Boyen, X., & Shacham, H. (2004). Short group signatures. CRYPTO 2004.
4. Wahby, R. S., et al. (2020). Doubly-efficient zkSNARKs without trusted setup. IEEE S&P 2020.
5. Ziellinski, T. (2023). PLONK Implementation Guide. Ethereum Foundation Research.