ZK-SNARKs 數學推導完整指南：從零知識證明基礎到 Groth16 協議工程實踐

概述

零知識證明（Zero-Knowledge Proof，ZK）是密碼學領域最革命性的概念之一，其允許證明者說服驗證者某個陳述為真，同時不透漏任何除陳述真實性以外的資訊。自 1985 年 Goldwasser、Micali 和 Rackoff 首次提出這一概念以來，零知識證明經歷了從理論到實際應用的漫長道路。特別是近年來，隨著 zk-SNARKs（Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge）和 zk-STARKs 技術的成熟，零知識證明已成為區塊鏈隱私保護和擴容的核心支柱。

本文從工程師的視角出發，提供零知識證明數學基礎的完整推導。我們將從密碼學安全假設出發，逐步建立零知識證明的理論框架，深入分析 zk-SNARKs 的核心協議——包括 Groth16、PLONK 與 Halo2 的設計原理與數學推導，並提供完整的程式碼範例說明如何在以太坊上實際部署零知識證明系統。讀者將能理解為何零知識證明是安全的、它如何實現簡潔性和非互動性、以及如何在實際應用中使用這項技術。

一、零知識證明基礎理論

1.1 形式化定義

零知識證明系統由三個機率多項式時間（PPT）演算法組成：鑰匙生成器（Key Generator）、證明者（Prover）和驗證者（Verifier）。設 $R$ 為一個關係，$L(R) = \{x | \exists w, (x, w) \in R\}$ 為對應的語言，$x$ 為陳述（Statement），$w$ 為見證（Witness）。

定義（一個零知識證明系統）：

一個證明系統 $(P, V)$ 對於關係 $R$ 是零知識的，如果滿足以下三個性質：

1. 完整性（Completeness）：如果 $(x, w) \in R$，則誠實證明者總是能說服誠實驗證者：

$$\Pr[V(x, P(x, w)) = \text{accept}] = 1$$

1. 可靠性（Soundness）：如果 $x \notin L(R)$，則任何欺騙證明者成功欺騙驗證者的機率是可忽略的：

$$\Pr[V(x, P^*(x)) = \text{accept}] \leq \text{negl}(n)$$

1. 零知識性（Zero-Knowledge）：對於任意驗證者 $V^*$，存在一個模擬器 $S$ 使得以下兩個分佈是不可區分的：

$$\{P(x, w) : (x, w) \in R\} \approx \{S(x) : x \in L(R)\}$$

第三個性質是零知識性的核心：驗證者在證明過程中獲得的資訊（稱為「視角」，View）等价於由模擬器產生的「模擬視角」，而模擬器僅使用陳述 $x$ 而無需見證 $w$。這意味著驗證者從證明過程中無法推斷出任何關於 $w$ 的資訊。

1.2 交互式與非互動式證明

最初的零知識證明是交互式的，需要證明者和驗證者進行多輪通信。這種設計的問題在於：

1. 同步性要求：雙方必須同時在線
2. 可擴展性問題：多個驗證者需要重複與證明者交互
3. 存檔困難：無法向第三方驗證

菲亞特-沙米爾啟發式（Fiat-Shamir Heuristic） 提供了一種將交互式證明轉換為非互動式證明的標準方法。其核心思想是使用密碼學雜湊函數模擬驗證者的隨機硬幣：

$$challenge = H(x || \text{prover\_commitment})$$

這種轉換的安全性基於隨機預言機模型（Random Oracle Model）：如果原始交互式協議是安全的，且雜湊函數可以建模為隨機預言機，則非互動式協議同樣安全。

在區塊鏈應用中，非互動式特性至關重要，因為區塊鏈本身就是一個非同步的、公共可驗證的媒介。SNARKs 中的「N」正是代表非互動式（Non-interactive）。

1.3 簡潔性與扎實性

SNARKs 的兩個關鍵屬性是簡潔性（Succinctness） 和扎實性（Soundness）：

簡潔性要求驗證時間是次線性的，通常為 $O(\log n)$ 或 $O(\sqrt{n})$，其中 $n$ 是計算規模。這使得驗證極大計算變得實際可行。例如，驗證一個包含 $10^9$ 次運算的計算，只需要幾毫秒而非數年。

扎實性錯誤（Soundness Error） $\epsilon$ 定義為欺騙者成功的機率上限。在密碼學中，我們通常要求 $\epsilon \leq 2^{-80}$ 或更低。Groth16 等 SNARKs 協議提供精確扎實性（Perfect Soundness），即 $\epsilon = 0$。

二、密碼學安全假設

2.1 離散對數假設

零知識證明的安全性通常基於幾個經典的密碼學假設。

離散對數假設（DLP）：給定一個循環群 $\mathbb{G}$，其階為大質數 $q$，以及生成元 $g$，計算 $h = g^x$ 中的指數 $x$ 在計算上是不可行的：

$$\Pr[\mathcal{A}(g, g^x) = x] \leq \text{negl}(n)$$

在密碼學中，我們通常使用以下群：

1. 橢圓曲線群：基於橢圓曲線上的點加法運算
2. 有限域乘法群：$\mathbb{Z}_p^*$，其中 $p$ 為大質數

2.2 雙線性配對

雙線性配對（Bilinear Pairing） 是現代 zk-SNARKs 的核心工具。設 $\mathbb{G}1, \mathbb{G}2, \mathbb{G}_T$ 為三個階為素數 $r$ 的循環群。一個雙線性配對是一個有效可計算的映射：

$$e: \mathbb{G}1 \times \mathbb{G}2 \rightarrow \mathbb{G}_T$$

滿足以下性質：

1. 雙線性：對於任意 $a, b \in \mathbb{Z}r$，$g \in \mathbb{G}1$，$h \in \mathbb{G}_2$：

$$e(g^a, h^b) = e(g, h)^{ab}$$

1. 非退化性：如果 $g$ 是 $\mathbb{G}1$ 的生成元，$h$ 是 $\mathbb{G}2$ 的生成元，則 $e(g, h)$ 是 $\mathbb{G}_T$ 的生成元。

1. 可計算性：配對映射 $e$ 可以有效計算。

常用的配對友好曲線包括：

• BN128：$E: y^2 = x^3 + 3$，用於以太坊早期版本
• BLS12-381：$E: y^2 = x^3 + 4$，現為業界標準
• BLS12-377：類似 BLS12-381，用於特定應用

2.3 q-假設與指數知識假設

Groth16 協議的安全性基於 q-假設 家族：

q-Strong Diffie-Hellman 假設（q-SDH）：給定 $(g, g^x, g^{x^2}, ..., g^{x^q})$，計算 $g^{1/(x+c)}$ 對任意非零 $c \in \mathbb{Z}_r$ 是不可行的。

q-假設描述：給定 $(g, g^a, g^{a^2}, ..., g^{a^q})$，計算 $c$ 使得 $g^{a^{q+1}} = (g^{a^q})^c$ 在計算上是不可行的。

這些假設比標準 DLP 更強，因為攻擊者獲得更多信息（多項式值），但這使得構建更高效的協議成為可能。

三、算術化電路與約束系統

3.1 從計算到代數

將任意計算轉換為零知識證明系統可驗證的形式，需要經過以下步驟：

原始計算 → 電路描述 → 約束系統 → 多項式約束 → QAP

步驟 1：電路表示

任意計算都可以表示為由加法和乘法門組成的算術電路。例如，計算 $z = (x + y) \times (x - y)$ 的電路如下：

Input x ──┬──→ Add gate → x+y ──┐
          │                     ├──→ Mul gate → z
Input y ──┴──→ Sub gate → x-y ──┘

步驟 2：約束系統

電路中的每個門可以表示為一個約束。最常見的是 R1CS（Rank-1 Constraint System）：

$$(Ai \cdot s) \cdot (Bi \cdot s) - (C_i \cdot s) = 0$$

其中 $s$ 是所有線（wires）的向量，$Ai, Bi, C_i$ 是將約束選擇性地應用於 $s$ 的矩陣。

步驟 3：QAP 轉換

R1CS 可以轉換為二次算術程式（Quadratic Arithmetic Programs） 形式：

$$A(x) \cdot B(x) - C(x) = H(x) \cdot Z(x)$$

其中 $Z(x) = \prod_{i=0}^{n-1} (x - \omega^i)$，$\omega$ 是 $n$ 個單位根。

3.2 R1CS 實作

以下是一個將簡單計算轉換為 R1CS 的 Python 實作：

from dataclasses import dataclass
from typing import List, Tuple
import numpy as np

@dataclass
class Wire:
    """電路線"""
    name: str
    value: int = None
    constraints_as: List[int] = None  # A矩陣中的係數
    constraints_bs: List[int] = None  # B矩陣中的係數
    constraints_cs: List[int] = None  # C矩陣中的係數

@dataclass
class Gate:
    """算術門"""
    gate_type: str  # 'add' or 'mul'
    inputs: List[str]
    output: str

class R1CSBuilder:
    """R1CS 約束生成器"""
    
    def __init__(self):
        self.wires: Dict[str, Wire] = {}
        self.constraints: List[Tuple] = []
        self.next_wire_id = 0
        
    def add_input(self, name: str) -> str:
        """添加公開輸入"""
        wire_id = f"pub_{name}"
        self.wires[wire_id] = Wire(name=name, value=None)
        return wire_id
        
    def add_private_input(self, name: str) -> str:
        """添加私有輸入（見證）"""
        wire_id = f"priv_{name}"
        self.wires[wire_id] = Wire(name=name, value=None)
        return wire_id
        
    def add_constraint(self, A: List[int], B: List[int], C: List[int]):
        """添加 R1CS 約束
        
        約束形式：(A · s) × (B · s) = (C · s)
        
        這對應於：(Σ a_i × s_i) × (Σ b_i × s_i) = (Σ c_i × s_i)
        """
        # 驗證向量長度一致
        n = len(A)
        assert len(B) == n and len(C) == n, "維度不匹配"
        
        # 確保所有線都已經註冊
        for i in A + B + C:
            if i > len(self.wires):
                # 添加一個輔助線（值為 0）
                self._add_aux_wire()
                
        self.constraints.append((A, B, C))
        
    def mul_gate(self, left: str, right: str, out: str):
        """添加乘法門
        
        約束：left × right = out
        
        轉換為 R1CS：
        A = [0, ..., 1_at_left, ..., 0]
        B = [0, ..., 1_at_right, ..., 0]
        C = [0, ..., 1_at_out, ..., 0]
        """
        # 獲取線的索引
        left_idx = self._get_wire_idx(left)
        right_idx = self._get_wire_idx(right)
        out_idx = self._get_wire_idx(out)
        
        # 構建約束向量（長度為當前總線數）
        n = len(self.wires)
        
        A = [0] * n
        A[left_idx] = 1
        
        B = [0] * n
        B[right_idx] = 1
        
        C = [0] * n
        C[out_idx] = 1
        
        self.add_constraint(A, B, C)
        
    def add_gate(self, left: str, right: str, out: str):
        """添加加法門
        
        約束：left + right = out
        
        轉換為 R1CS：
        (left × 1) + (right × 1) - (out × 1) = 0
        即：(left + right - out) × 1 = 0
        
        A = [1_at_left]
        B = [1]
        C = [1_at_out]
        """
        left_idx = self._get_wire_idx(left)
        right_idx = self._get_wire_idx(right)
        out_idx = self._get_wire_idx(out)
        
        n = len(self.wires)
        
        # 合併 A 向量
        A = [0] * n
        A[left_idx] = 1
        A[right_idx] = 1
        
        # B 向量只有一個 1（常量 1）
        B = [1]
        
        # C 向量
        C = [0] * n
        C[out_idx] = 1
        
        self.add_constraint(A, B, C)
        
    def _get_wire_idx(self, name: str) -> int:
        """獲取線的索引"""
        wires = list(self.wires.keys())
        if name not in wires:
            self.wires[name] = Wire(name=name)
            wires = list(self.wires.keys())
        return wires.index(name)
        
    def _add_aux_wire(self):
        """添加輔助線（值為 0）"""
        idx = self.next_wire_id
        self.next_wire_id += 1
        self.wires[f"aux_{idx}"] = Wire(name=f"aux_{idx}", value=0)
        
    def verify(self, assignment: Dict[str, int]) -> bool:
        """驗證賦值是否滿足所有約束"""
        s = self._build_assignment_vector(assignment)
        
        for i, (A, B, C) in enumerate(self.constraints):
            # 將稀疏向量擴展為完整向量
            A_full = self._expand_vector(A, len(s))
            B_full = self._expand_vector(B, len(s))
            C_full = self._expand_vector(C, len(s))
            
            left = sum(a * b for a, b in zip(A_full, s))
            right = sum(b * b for b in B_full)  # B 可能更短
            if len(B_full) < len(s):
                # 如果 B 是短向量，補 0
                right = sum(b * b for b in B_full) + sum(s[len(B_full):]) * 0
            else:
                right = sum(b * b for b, s_val in zip(B_full, s))
                
            out = sum(c * s_val for c, s_val in zip(C_full, s))
            
            if (left * right - out) % self.field_order != 0:
                return False
                
        return True
        
    def _build_assignment_vector(self, assignment: Dict[str, int]) -> List[int]:
        """根據賦值構建完整向量"""
        wires = list(self.wires.keys())
        s = []
        for w in wires:
            if w in assignment:
                s.append(assignment[w])
            elif w.startswith("aux_"):
                s.append(0)
            else:
                raise ValueError(f"Missing assignment for wire: {w}")
        return s

3.3 將電路轉換為 QAP

二次算術程式（QAP） 是將 R1CS 約束轉換為多項式約束的關鍵步驟：

class QAPBuilder:
    """QAP（Quadratic Arithmetic Program）生成器"""
    
    def __init__(self, r1cs: R1CSBuilder, field_order: int):
        self.r1cs = r1cs
        self.field_order = field_order
        self.root_of_unity = self._get_primitive_root(field_order)
        
    def build_qap(self) -> Tuple:
        """
        將 R1CS 約束轉換為 QAP
        
        對於每個約束 i，選擇一個點 x_i
        然後插值得到多項式 A(x), B(x), C(x)
        
        使得在每個點 x_i：
        A(x_i) · B(x_i) - C(x_i) = 0
        
        最終約束：A(x) · B(x) - C(x) = H(x) · Z(x)
        其中 Z(x) = ∏(x - x_i)
        """
        n_constraints = len(self.r1cs.constraints)
        n_wires = len(self.r1cs.wires)
        
        # 選擇插值點（使用域的根）
        x_points = [pow(self.root_of_unity, i, self.field_order) 
                    for i in range(n_constraints)]
        
        # 為每個線構建多項式
        # A_poly[i][wire] = 多項式 A_i 在點 x_i 處對於線 wire 的值
        A_matrix = []
        B_matrix = []
        C_matrix = []
        
        for constraint_idx, (A_sparse, B_sparse, C_sparse) in enumerate(self.r1cs.constraints):
            # 擴展稀疏向量
            A_full = self._expand_sparse_vector(A_sparse, n_wires)
            B_full = self._expand_sparse_vector(B_sparse, n_wires)
            C_full = self._expand_sparse_vector(C_sparse, n_wires)
            
            A_matrix.append(A_full)
            B_matrix.append(B_full)
            C_matrix.append(C_full)
            
        # 插值：對每個線索引，構建其多項式
        A_polys = []
        B_polys = []
        C_polys = []
        
        for wire_idx in range(n_wires):
            # 提取該線在所有約束點的值
            A_values = [A_matrix[i][wire_idx] for i in range(n_constraints)]
            B_values = [B_matrix[i][wire_idx] for i in range(n_constraints)]
            C_values = [C_matrix[i][wire_idx] for i in range(n_constraints)]
            
            # 拉格朗日插值
            A_poly = self._lagrange_interpolate(x_points, A_values)
            B_poly = self._lagrange_interpolate(x_points, B_values)
            C_poly = self._lagrange_interpolate(x_points, C_values)
            
            A_polys.append(A_poly)
            B_polys.append(B_poly)
            C_polys.append(C_poly)
            
        # 構建 Z(x) = ∏(x - x_i)
        Z = self._build_zero_poly(x_points)
        
        return (A_polys, B_polys, C_polys, Z)
        
    def _lagrange_interpolate(
        self, 
        x_points: List[int], 
        y_values: List[int]
    ) -> List[int]:
        """
        拉格朗日插值
        
        給定 n 個點 (x_i, y_i)，構建穿過所有點的多項式：
        P(x) = Σ y_i · L_i(x)
        
        其中 L_i(x) = ∏_{j≠i} (x - x_j) / (x_i - x_j)
        """
        n = len(x_points)
        coeffs = [0] * n
        
        for i in range(n):
            # 計算拉格朗日基多項式 L_i(x)
            num = [1]  # 分子：∏(x - x_j)
            den = 1    # 分母：∏(x_i - x_j)
            
            for j in range(n):
                if i != j:
                    # (x - x_j)
                    num = self._poly_mul(num, [-x_points[j], 1])
                    den = den * (x_points[i] - x_points[j]) % self.field_order
                    
            # 逆元計算
            den_inv = pow(den, -1, self.field_order)
            
            # 合併到係數
            for k, c in enumerate(num):
                coeffs[k] = (coeffs[k] + y_values[i] * c * den_inv) % self.field_order
                
        return coeffs
        
    def _build_zero_poly(self, x_points: List[int]) -> List[int]:
        """
        構建零多項式 Z(x) = ∏(x - x_i)
        """
        Z = [1]
        
        for x in x_points:
            # 乘以 (x - x)
            Z = self._poly_mul(Z, [-x, 1])
            
        return Z
        
    def _poly_mul(self, a: List[int], b: List[int]) -> List[int]:
        """多項式乘法（係數在 field_order 下）"""
        result = [0] * (len(a) + len(b) - 1)
        
        for i, ai in enumerate(a):
            for j, bj in enumerate(b):
                result[i + j] = (result[i + j] + ai * bj) % self.field_order
                
        return result

四、Groth16 協議

4.1 協議描述

Groth16 是目前最高效的 zk-SNARK 協議之一，由 Jens Groth 在 2016 年提出。其證明大小僅為三個群元素（約 288 位元組），驗證時間為三個配對運算。

設定階段（Setup）：

Groth16 使用通用可信賴設定（Universal Trusted Setup） 或 一次性設定（One-Time Setup）：

1. 選擇雙線性配對群 $\mathbb{G}1, \mathbb{G}2, \mathbb{G}_T$
2. 生成結構化參考字串（SRS，Structured Reference String）：

$$\text{SRS} = (g^{\alpha}, g^{\beta}, g^{\delta}, \{g^{\beta \cdot \tau^i}\}{i=0}^{n-1}, \{g^{\alpha \cdot \tau^i}\}{i=0}^{n-1})$$

證明者計算：

給定 QAP $(A\tau, B\tau, C_\tau)$ 和見證 $w$：

1. 計算 $A = A_\tau(\tau) + \alpha + \beta$
2. 計算 $B = B_\tau(\tau) + \beta$
3. 計算 $C = C_\tau(\tau) + \delta \cdot H(\tau)$
4. 輸出證明 $\pi = (A, B, C)$

驗證者計算：

給定公鑰 $vk$、公開輸入 $x$ 和證明 $\pi$：

$$e(A, B) = e(g, g)^{\alpha \cdot \beta} \cdot e(g^{\delta}, g^{\beta}) \cdot e(C, g)$$

4.2 Groth16 實作

以下是一個簡化的 Groth16 協議實作：

from dataclasses import dataclass
from typing import List, Tuple, Dict
import hashlib

@dataclass
class G1Point:
    """橢圓曲線群 G1 中的點"""
    x: int
    y: int
    
    def __mul__(self, scalar: int) -> 'G1Point':
        """標量乘法"""
        return point_mul(self, scalar)
        
    def __add__(self, other: 'G1Point') -> 'G1Point':
        """點加法"""
        return point_add(self, other)
        
@dataclass
class G2Point:
    """橢圓曲線群 G2 中的點"""
    x0: int  # G2 中的點以擴展座標表示
    x1: int
    y0: int
    y1: int

@dataclass
class Proof:
    """Groth16 證明"""
    A: G1Point
    B: G2Point
    C: G1Point

@dataclass
class VerifyingKey:
    """驗證金鑰"""
    alpha: G1Point       # g^α
    beta: G1Point        # g^β
    gamma: G2Point       # g^γ
    delta: G2Point       # g^δ
    IC: List[G1Point]    # 公開輸入映射
    
@dataclass
class ProvingKey:
    """證明金鑰"""
    A: List[G1Point]     # A 多項式在 τ 處的估值
    B: List[G2Point]     # B 多項式在 τ 處的估值
    C: List[G1Point]     # C 多項式（延遲打開）
    gamma: G2Point       # g^γ
    delta: G2Point       # g^δ
    
class Groth16:
    """Groth16 協議實現"""
    
    def __init__(self, curve_params: Dict):
        self.g1_gen = G1Point(curve_params['g1_x'], curve_params['g1_y'])
        self.g2_gen = G2Point(curve_params['g2_x'], curve_params['g2_y'])
        self.field_order = curve_params['field_order']
        
    def setup(self, qap: Tuple) -> Tuple[ProvingKey, VerifyingKey]:
        """
        可信賴設定
        
        在實際應用中，這應該使用 MPC（多方計算）儀式來生成
        這裡我們使用模擬設定說明原理
        """
        A_polys, B_polys, C_polys, Z = qap
        n = len(A_polys)
        
        # 抽樣隨機標量
        tau = self._sample_random()
        alpha = self._sample_random()
        beta = self._sample_random()
        gamma = self._sample_random()
        delta = self._sample_random()
        
        # 預計算 τ 的冪
        tau_powers = [pow(tau, i, self.field_order) for i in range(n)]
        
        # 生成證明金鑰
        proving_key = ProvingKey(
            A=[self.g1_gen * (A_polys[i].evaluate(tau_powers)) for i in range(n)],
            B=[self.g2_gen * (B_polys[i].evaluate(tau_powers)) for i in range(n)],
            C=[self.g1_gen * (C_polys[i].evaluate(tau_powers)) for i in range(n)],
            gamma=self.g2_gen * gamma,
            delta=self.g2_gen * delta,
        )
        
        # 生成驗證金鑰
        verifying_key = VerifyingKey(
            alpha=self.g1_gen * alpha,
            beta=self.g1_gen * beta,
            gamma=self.g2_gen * gamma,
            delta=self.g2_gen * delta,
            IC=[self.g1_gen * beta * A_polys[0].evaluate(tau_powers)],  # 公開輸入映射
        )
        
        return proving_key, verifying_key
        
    def prove(
        self, 
        pk: ProvingKey, 
        public_inputs: List[int],
        private_inputs: List[int],
    ) -> Proof:
        """
        證明生成
        
        輸入：
        - pk: 證明金鑰
        - public_inputs: 公開輸入
        - private_inputs: 私有見證
        """
        # 合併所有輸入
        all_inputs = public_inputs + private_inputs
        
        # 計算 A
        A = self.g1_gen * pk.A[0]  # 基點
        for i, val in enumerate(all_inputs):
            A = A + pk.A[i + 1] * val
            
        # 計算 B
        B = self.g2_gen * pk.B[0]  # 基點
        for i, val in enumerate(all_inputs):
            B = B + pk.B[i + 1] * val
            
        # 計算 C
        C = pk.C[0]
        for i, val in enumerate(all_inputs):
            C = C + pk.C[i + 1] * val
            
        # 這裡應該計算 H(τ)·δ，但在實際實現中需要更複雜的計算
        # 省略細節...
        
        return Proof(A=A, B=B, C=C)
        
    def verify(
        self, 
        vk: VerifyingKey, 
        public_inputs: List[int], 
        proof: Proof
    ) -> bool:
        """
        驗證證明
        
        驗證方程：
        e(A, B) = e(α, β) · e(Σ IC_i·input_i, γ) · e(C, δ)
        """
        # 計算 IC · inputs
        IC_times_inputs = vk.IC[0] * 0
        for i, val in enumerate(public_inputs):
            IC_times_inputs = IC_times_inputs + vk.IC[i] * val
            
        # 配對計算
        # 左邊：e(A, B)
        left = pairing(proof.A, proof.B)
        
        # 右邊：e(α, β) · e(IC, γ) · e(C, δ)
        right = (
            pairing(vk.alpha, vk.beta) *
            pairing(IC_times_inputs, vk.gamma) *
            pairing(proof.C, vk.delta)
        )
        
        return left == right
        
    def _sample_random(self) -> int:
        """採樣隨機標量"""
        import secrets
        return secrets.randbelow(self.field_order)

4.3 安全性證明概述

Groth16 的安全性可以從兩個方面理解：

零知識性：證明者可以透過在 A 和 B 中添加隨機遮罩來隱藏見證。具體來說：

$$A' = A + \rho \cdot \delta_G$$

$$B' = B + \sigma \cdot \delta_G$$

$$C' = C + A' \cdot B' - A \cdot B - \rho \cdot \sigma \cdot \delta_G^2$$

其中 $\rho, \sigma$ 是證明者選擇的隨機數。這些遮罩確保驗證方程仍然成立，因為：

$$A' \cdot B' - C' = (A + \rho \delta)(B + \sigma \delta) - (C + A \cdot B - A \cdot B) = A \cdot B - C = \alpha \cdot \beta$$

扎實性：欺騙者成功的關鍵在於他們需要生成 $(A, B, C)$ 使得驗證方程成立。這等价於解決 $q$-SDH 假設等密碼學難題。

五、在以太坊上部署 zk-SNARKs

5.1 Solidity 驗證合約

以下是一個使用 Groth16 驗證的 Solidity 合約示例：

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.19;

/**
 * @title Groth16Verifier
 * @notice 使用 Groth16 驗證 zk-SNARK 證明的合約
 * @dev 驗證方程：e(A, B) = e(α, β) · e(γ, δ)⁻¹ · e(C, δ)
 */
contract Groth16Verifier {
    // G1 點結構：覆蓋 3 個標量（一個 x 座標 + 兩個 y 座標以處理壓縮）
    struct G1Point {
        uint256 X;
        uint256 Y;
    }
    
    // G2 點結構
    struct G2Point {
        uint256[2] X;
        uint256[2] Y;
    }
    
    // 驗證金鑰
    G1Point public vk_alpha;
    G2Point public vk_beta;
    G2Point public vk_gamma;
    G2Point public vk_delta;
    G1Point[] public vk_gamma_abc;
    
    // 配對合約地址（預先部署的 BN128 配對檢查合約）
    address public constant PAIRING_CHECK = address(0x8b);
    
    /**
     * @notice 建構子，初始化驗證金鑰
     */
    constructor(
        uint256[2] memory _vk_alpha,
        uint256[2][2] memory _vk_beta,
        uint256[2][2] memory _vk_gamma,
        uint256[2][2] memory _vk_delta,
        uint256[2][] memory _vk_gamma_abc
    ) {
        vk_alpha = G1Point(_vk_alpha[0], _vk_alpha[1]);
        vk_beta = G2Point(_vk_beta[0], _vk_beta[1]);
        vk_gamma = G2Point(_vk_gamma[0], _vk_gamma[1]);
        vk_delta = G2Point(_vk_delta[0], _vk_delta[1]);
        
        // 初始化公共輸入映射
        for (uint i = 0; i < _vk_gamma_abc.length; i++) {
            vk_gamma_abc.push(G1Point(
                _vk_gamma_abc[i][0],
                _vk_gamma_abc[i][1]
            ));
        }
    }
    
    /**
     * @notice 驗證 zk-SNARK 證明
     * @param a 證明 A 元素
     * @param b 證明 B 元素
     * @param c 證明 C 元素
     * @param input 公共輸入
     * @return bool 驗證是否成功
     */
    function verifyProof(
        uint256[2] memory a,
        uint256[2][2] memory b,
        uint256[2] memory c,
        uint256[] memory input
    ) public view returns (bool) {
        // 驗證輸入長度
        require(input.length + 1 == vk_gamma_abc.length, "Input length mismatch");
        
        // 計算 Σ IC_i · input_i
        uint256[2] memory input_lincomb = pairingLinearCombination(input);
        
        // 驗證配對方程
        uint256[24] memory inputParams = [
            // e(A, B)
            a[0], a[1], b[0][0], b[0][1], b[1][0], b[1][1],
            // e(α, β)
            vk_alpha.X, vk_alpha.Y, vk_beta.X[0], vk_beta.X[1], vk_beta.Y[0], vk_beta.Y[1],
            // e(Σ IC_i·input_i, γ)
            input_lincomb[0], input_lincomb[1], vk_gamma.X[0], vk_gamma.X[1], 
            vk_gamma.Y[0], vk_gamma.Y[1],
            // e(C, δ)
            c[0], c[1], vk_delta.X[0], vk_delta.X[1], vk_delta.Y[0], vk_delta.Y[1]
        ];
        
        uint256 gas_start = gasleft();
        
        // 調用預編譯合約執行配對檢查
        uint256 success;
        assembly {
            success := staticcall(sub(gas_start, 2000), PAIRING_CHECK, add(inputParams, 0x20), 0x300, inputParams, 0x20)
        }
        
        return success == 1 && inputParams[0] == 1;
    }
    
    /**
     * @notice 計算線性組合 Σ IC_i · input_i
     */
    function pairingLinearCombination(
        uint256[] memory input
    ) internal view returns (uint256[2] memory result) {
        result = [uint256(0), uint256(0)];
        
        for (uint i = 0; i < input.length; i++) {
            // 結果 += IC_i * input[i]
            // 使用座標加法和標量乘法
            (uint256 x, uint256 y) = (
                vk_gamma_abc[i + 1].X,
                vk_gamma_abc[i + 1].Y
            );
            
            // 標量乘法
            uint256 lambda = input[i];
            uint256 rx = x * lambda;
            uint256 ry = y * lambda;
            
            // 座標加法
            result[0] = addmod(result[0], rx, 0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47);
            result[1] = addmod(result[1], ry, 0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47);
        }
        
        // 加上 IC_0（通常為零）
        result[0] = addmod(result[0], vk_gamma_abc[0].X, 0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47);
        result[1] = addmod(result[1], vk_gamma_abc[0].Y, 0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47);
    }
}

5.2 Gas 成本分析

在以太坊上驗證 zk-SNARKs 的主要成本來自配對運算。讓我們分析典型 Groth16 驗證的 Gas 消耗：

對於複雜電路（大量公開輸入），Gas 成本可能達到數百萬。這是為何 zkEVM 和 zkRollup 項目需要大量優化，以及為何 PLONK 和 Halo2 等具有通用可更新設定的協議越來越受歡迎。

六、結論與展望

本文提供了零知識證明數學基礎的完整推導，從形式化定義到 Groth16 協議的工程實作。讀者應該能夠理解：

1. 零知識性的理論基礎：如何透過模擬器論證零知識性
2. 電路到約束系統的轉換：R1CS 和 QAP 的原理
3. Groth16 的核心思想：如何透過雙線性配對實現簡潔驗證
4. 以太坊部署考量：Solidity 驗證合約的設計與 Gas 優化

展望未來，零知識證明技術將繼續演進：

• 通用 zkEVM：zkSync、Polygon zkEVM、Scroll 等項目正在實現完全 EVM 相容的 ZK 證明系統
• 遞歸證明：Halo2 和 Nova 等技術允許證明證明，進一步提升效率
• 硬體加速：GPU 和 ASIC 加速器將大幅降低證明生成時間
• 跨鏈隱私：Dark Forest 等應用展示了無許可隱私的可能性

零知識證明代表了密碼學與區塊鏈交叉領域最前沿的技術創新。對於希望在這個領域深耕的開發者和研究者而言，扎實的數學基礎是理解未來發展的必備條件。

參考資料

ZK-SNARKs 論文

Gro16 論文

PLONK 論文

Halo2 論文

Solidity 官方文檔