ZK-SNARK 電路設計數學推導進階教程：從理論到 Circom/Noir 實作

前言

本文深入探討 ZK-SNARK 電路設計的數學推導與實作細節，是對現有 ZK-SNARK 數學推導文章的進階補充。我們將從電路複雜度理論出發，詳細推導約束系統的數學原理，並提供完整的 Circom 與 Noir 實作範例。

第一章：電路複雜度理論基礎

1.1 電路複雜度的數學定義

1.1.1 約束數量複雜度

約束系統的大小直接影響 SNARK 的效率。讓我們從數學上嚴謹分析約束數量的計算。

約束複雜度函數：

對於電路 $C$，定義約束複雜度 $\kappa(C)$ 為：

$$\kappa(C) = \sum_{g \in \text{gates}(C)} w(g) \cdot c(g)$$

其中：

• $g$ 為電路中的門
• $w(g)$ 為門的權重（乘法門權重高於加法門）
• $c(g)$ 為門的約束複雜度

加法約束：

加法 $a + b = c$ 可表示為 R1CS：

$$(a + b - c) \cdot 1 = 0$$

矩陣形式：

$$A = \begin{pmatrix} 1 & 1 & -1 \end{pmatrix}, \quad B = \begin{pmatrix} 0 \end{pmatrix}, \quad C = \begin{pmatrix} 0 \end{pmatrix}$$

乘法約束：

乘法 $a \times b = c$ 可表示為 R1CS：

$$a \cdot b - c = 0$$

矩陣形式：

$$A = \begin{pmatrix} 1 & 0 & 0 \end{pmatrix}, \quad B = \begin{pmatrix} 0 & 1 & 0 \end{pmatrix}, \quad C = \begin{pmatrix} 0 & 0 & 1 \end{pmatrix}$$

1.1.2 電路深度複雜度

乘法深度定義：

對於電路 $C$，定義乘法深度 $\delta(C)$ 為從輸入到輸出最長的乘法路徑上的乘法門數量。

電路示例：

輸入 a, b, c
     │
     ├──► [MUL] ──► x = a × b
     │               │
     │               ├──► [MUL] ──► y = x × c
     │               │               │
     │               │               └──► 輸出 y
     │               │
     │               └──► 乘法深度 = 2
     │
     └──► [ADD] ──► z = a + b  (乘法深度 = 0)

深度與證明時間關係：

def calculate_proof_time(depth: int, constraints: int) -> float:
    """
    估算證明時間
    
    數學模型：
    T_proof ≈ T_pairing × N_constraints + T_fft × δ(C) × log(N)
    
    其中：
    - T_pairing ≈ 10ms (配對運算時間)
    - T_fft ≈ 1ms (FFT 運算時間)
    - N_constraints 為約束數
    - δ(C) 為乘法深度
    """
    T_pairing = 0.01  # 秒
    T_fft = 0.001    # 秒
    
    T_proof = T_pairing * constraints + T_fft * depth * math.log2(constraints)
    
    return T_proof

# 示例
for depth in [1, 5, 10, 20]:
    time = calculate_proof_time(depth, 10000)
    print(f"深度 {depth}: 預計證明時間 {time:.2f} 秒")

1.2 電路複雜度邊界

1.2.1 基礎運算的約束複雜度

1.2.2 約束優化理論

約束合併定理：

若電路中存在 $k$ 個可合併的約束：

$$\bigwedge{i=1}^{k} (Ai \cdot Bi - Ci = 0)$$

可合併為：

$$\prod{i=1}^{k} (Ai \cdot Bi - Ci) = 0$$

但這會增加約束的度數。最佳化需要在約束數和約束度之間取得平衡。

信號複製 vs 約束複製：

信號複製：
signal b <-- a;  // 無約束拷貝
信號數量 +1，約束數量不變

約束複製：
signal b <== a;  // 等價於 b = a
信號數量 +1，約束數量 +1

第二章：橢圓曲線密碼學數學推導

2.1 橢圓曲線群運算

2.1.1 曲線方程式推導

設橢圓曲線 $E$ 定義於質數域 $\mathbb{F}_p$ 上：

$$E: y^2 = x^3 + ax + b \mod p$$

其中 $a, b \in \mathbb{F}_p$，判別式 $\Delta = 4a^3 + 27b^2 \neq 0 \mod p$。

群公理驗證：

1. 單位元：無窮遠點 $\mathcal{O}$
2. 逆元：$(x, y)$ 的逆元為 $(x, -y)$
3. 結合律：需要代數幾何證明（超出本文範圍）

2.1.2 點加法公式推導

設 $P = (x1, y1)$、$Q = (x2, y2)$，求 $R = P + Q = (x3, y3)$。

情形 1：$P \neq Q$

連接 $P$ 和 $Q$ 的直線，與曲線交於第三點 $R'$，反射得到 $R$。

直線方程式：

$$y - y1 = \lambda(x - x1)$$

$$\lambda = \frac{y2 - y1}{x2 - x1} = \frac{y2 - y1}{x2 - x1} \mod p$$

代入曲線方程式：

$$(\lambda(x - x1) + y1)^2 = x^3 + ax + b$$

整理後得到 $x_3$：

$$x3 = \lambda^2 - x1 - x_2 \mod p$$

由韋達定理：

$$x1 + x2 + x_3 = \lambda^2$$

驗證 $x_3$ 的正確性。

情形 2：$P = Q$（倍點運算）

切線的斜率：

$$\lambda = \frac{dy}{dx} = \frac{3x1^2 + a}{2y1} \mod p$$

由隱函數微分：

$$2y \frac{dy}{dx} = 3x^2 + a$$

代入得：

$$\lambda = \frac{3x1^2 + a}{2y1} \mod p$$

倍點公式：

$$x3 = \lambda^2 - 2x1 \mod p$$

$$y3 = \lambda(x1 - x3) - y1 \mod p$$

2.1.3 配對函數數學推導

Tate 配對定義：

設 $E$ 為橢圓曲線，$n$ 為曲線上點的階，$k$ 為嵌入度。Tate 配對定義為：

$$en: E[n] \times E[k] \to \mathbb{F}{p^k}^ / (\mathbb{F}_{p^k}^)^n$$

Miller 算法推導：

Miller 算法計算 $f_{P, Q}(Q)$：

def miller_loop(P: Point, Q: Point, n: int) -> FieldElement:
    """
    Miller 算法實現
    
    數學原理：
    f_{P,Q}(Q) = Π_{i=0}^{log_2(n)} f_i(Q)^{e_i}
    
    其中：
    - f_i 是與第 i 步相關的多項式
    - e_i 是 n 的二進制展開的第 i 位
    """
    m = P
    f = FieldElement(1)
    
    for i in range(log2(n), -1, -1):
        # 倍點步驟
        f = f * f * line_func(m, m, Q)
        m = m.double()  # m = 2m
        
        if (n >> i) & 1:
            # 加法步驟
            f = f * line_func(m, P, Q)
            m = m + P  # m = m + P
    
    return f

def line_func(R: Point, P: Point, Q: Point) -> FieldElement:
    """
    計算線性函數
    
    對於不同點相加：
    λ = (y_2 - y_1) / (x_2 - x_1)
    line = y - y_1 - λ(x - x_1)
    
    對於倍點：
    λ = (3x_1^2 + a) / (2y_1)
    line = y - y_1 - λ(x - x_1)
    """
    if R == P:
        # 倍點
        numerator = 3 * R.x ** 2 + CURVE_A
        denominator = 2 * R.y
    else:
        # 加法
        numerator = Q.y - P.y
        denominator = Q.x - P.x
    
    lambda_ = numerator / denominator  # 有限域除法
    
    # 線性函數值
    return R.y - lambda_ * R.x + lambda_ * P.y - P.y

最終化簡：

$$en(P, Q) = f{P,Q}(Q)^{\frac{p^k - 1}{n}}$$

第三章：約束系統進階推導

3.1 R1CS 到 QAP 的轉換

3.1.1 拉格朗日插值定理

定理敘述：

给定 $n$ 個互不相同的點 $(xi, yi)$，存在唯一的多項式 $P(x)$ 使得 $\deg(P) < n$ 且 $P(xi) = yi$。

構造公式：

$$P(x) = \sum{i=1}^{n} yi \cdot \prod{j \neq i} \frac{x - xj}{xi - xj}$$

證明：

對於每個基多項式：

$$Li(xj) = \begin{cases} 1 & \text{若 } i = j \\ 0 & \text{若 } i \neq j \end{cases}$$

這由分子的結構保證：當 $x = xj$ 且 $j \neq i$ 時，分子包含 $(xj - x_j)$ 因子。

數值穩定性：

插值過程中可能出現病態條件。引入條件數：

$$\kappa = \max{i} \sum{j} |L_{ij}|$$

當插值點靠近時，$\kappa$ 可能急劇增大。

3.1.2 R1CS 到 QAP 轉換詳細步驟

步驟 1：約束編號

設 R1CS 包含 $m$ 個約束，編號為 $1, 2, \ldots, m$。

選擇插值點：$1, 2, \ldots, m+1$（多一個點用於驗證）

步驟 2：矩陣元素插值

對於 $A$ 矩陣的第 $k$ 行：

$$Ak(x) = \text{interpolate}\left(\{(i, A{k,i})\}_{i=1}^{m+1}\right)$$

步驟 3：約束多項式構造

$$A(x) = \sum{k} ak \cdot A_k(x)$$

$$B(x) = \sum{k} bk \cdot B_k(x)$$

$$C(x) = \sum{k} ck \cdot C_k(x)$$

步驟 4：驗證多項式

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

其中 $Z(x) = \prod_{i=1}^{m}(x - i)$。

數值示例：

假設約束數 $m = 3$，選擇點 $1, 2, 3, 4$：

約束：

1. $a1 \cdot b1 = c_1$
2. $a2 \cdot b2 = c_2$
3. $a3 \cdot b3 = c_3$

插值點：

• $A1(x)$：穿過 $(1, A{1,1}), (2, A{1,2}), (3, A{1,3}), (4, A_{1,4})$
• $B1(x)$：穿過 $(1, B{1,1}), (2, B{1,2}), (3, B{1,3}), (4, B_{1,4})$
• $C1(x)$：穿過 $(1, C{1,1}), (2, C{1,2}), (3, C{1,3}), (4, C_{1,4})$

3.2 約束系統效率優化

3.2.1 約束重寫定理

定理：

設約束 $C1$ 和 $C2$ 可合併為 $C_{merged}$，則：

$$\text{constraints}(C{merged}) < \text{constraints}(C1) + \text{constraints}(C_2)$$

合併策略：

1. 代數合併：

$$a \cdot b = c$$

$$d \cdot e = f$$

可合併為：

$$(a \cdot b) \cdot (d \cdot e) = c \cdot f$$

約束數：2 → 1

約束度：2 → 4

1. 線性合併：

$$a + b = c$$

$$d + e = f$$

可合併為：

$$(a + b - c) + (d + e - f) = 0$$

約束數：2 → 1

約束度：1 → 1

3.2.2 查找表約束

查找表理論：

對於離散函數 $f: \mathbb{F}p \to \mathbb{F}p$，若 $f$ 的真值表已給定，則：

$$f(x) = \sum{i=0}^{p-1} f(i) \cdot \prod{j \neq i} \frac{x - j}{i - j}$$

但這需要 $O(p)$ 個約束，對於大域不實際。

離散查找表：

對於小域（如 $\mathbb{F}2$ 或 $\mathbb{F}8$），可以使用查找表：

template Xor8() {
    signal input a;
    signal input b;
    signal output out;
    
    // 8-bit XOR 查找表
    // 256 個條目，每條 1 bit
    // 總共 32 個 8-bit 條目
    
    var table[32] = [
        0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
        0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
        0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
        0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f
    ];
    
    // 使用信號作為索引
    out <== table[a];
}

第四章：Circom 電路設計實作

4.1 Circom 語法與約束生成

4.1.1 信號與約束

// Circom 基本語法
pragma circom 2.0.0;

// 信號宣告
signal input x;           // 輸入信號
signal output y;          // 輸出信號
signal intermediate;      // 中間信號
signal array[5];          // 信號數組

// 約束生成
// === 運算符：生成約束
y <== x * x;  // y === x * x，生成約束 y = x²

// <-- 運算符：不生成約束（拷貝值）
intermediate <-- x * 2;  // 只拷貝，不生成約束

// ==> 運算符：右側約束
x ==> y;  // 生成約束 x = y

// 組合：
// a === b 等價於 a <== b; b <== a;

4.1.2 約束等價性證明

定理：

對於任意算術表達式 $E$，以下三種寫法生成相同的約束：

// 方法 1：直接賦值
out <== a * b + c;

// 方法 2：分步賦值
signal temp;
temp <== a * b;
out <== temp + c;

// 方法 3：使用臨時變量
signal t1;
signal t2;
t1 <== a;
t2 <== b;
out <== t1 * t2 + c;

證明：

方法 1 生成的約束：

$$(out) \cdot 1 - (a \cdot b + c) = 0$$

方法 2 生成的約束：

$$(temp) \cdot 1 - (a \cdot b) = 0$$

$$(out) \cdot 1 - (temp + c) = 0$$

將第二個約束中的 $temp$ 替換為 $a \cdot b$：

$$out = temp + c = a \cdot b + c$$

得證。

4.2 完整電路範例：範圍證明

4.2.1 電路設計

// 範圍證明電路
// 證明 input ∈ [0, 2^n)

pragma circom 2.0.0;

template RangeProof(n) {
    signal input in;
    signal output out;
    
    // 輸出為 1 當且僅當 in ∈ [0, 2^n)
    // 否則輸出為 0
    
    // 方法：分解為二進制位，檢查每一位
    
    // 檢查 in < 2^n
    // 即 in 的範圍是 [0, 2^n)
    
    // 二進制分解
    var bits = n;
    var limbs = (n + 3) \ 4;  // 每個 limb 4 bits
    
    signal bits[bits];
    var lc = 0;
    
    for (var i = 0; i < bits; i++) {
        // 提取第 i 位
        bits[i] <-- (in \ 2**i) % 2;
        
        // 約束：位只能是 0 或 1
        bits[i] * (bits[i] - 1) === 0;
        
        // 重構
        lc += bits[i] * 2**i;
    }
    
    // 約束：重構值等於輸入
    lc === in;
    
    // 輸出
    out <== 1;
}

template Main() {
    signal input in;
    signal output out;
    
    component rangeProof = RangeProof(8);
    rangeProof.in <== in;
    out <== rangeProof.out;
}

4.2.2 約束數量分析

"""
RangeProof 電路約束數量分析
"""

def analyze_range_proof_constraints(n_bits):
    """
    分析 n-bit 範圍證明的約束數量
    
    數學模型：
    
    約束類型：
    1. 位約束：bits[i] * (bits[i] - 1) = 0
       每位 1 個約束 → n 個約束
    
    2. 重構約束：Σ(bits[i] * 2^i) - in = 0
       1 個約束（線性）→ 1 個約束
    
    總約束數 = n + 1
    """
    bit_constraints = n_bits  # 位約束
    reconstruction_constraint = 1  # 重構約束
    
    total = bit_constraints + reconstruction_constraint
    
    return {
        'bit_constraints': bit_constraints,
        'reconstruction_constraint': reconstruction_constraint,
        'total': total,
        'signal_count': n_bits + 3  # input, output, temp signals
    }

# 測試
for n in [8, 16, 32, 64, 128, 256]:
    analysis = analyze_range_proof_constraints(n)
    print(f"n={n}: {analysis['total']} 約束")

4.3 完整電路範例：Merkle 樹驗證

4.3.1 電路設計

// Merkle 樹驗證電路
// 證明 leaf 是 Merkle 樹 root 的子葉

pragma circom 2.0.0;

include "circomlib/poseidon.circom";
include "circomlib/bitify.circom";
include "circomlib/switcher.circom";

template MerkleProofChecker(levels) {
    signal input leaf;
    signal input root;
    signal input path[levels];
    signal input pathDirection[levels];  // 0 = 左, 1 = 右
    
    signal output valid;
    
    // 初始化：葉節點
    signal computed[levels + 1];
    computed[0] <== leaf;
    
    // 沿路徑計算
    for (var i = 0; i < levels; i++) {
        // 選擇左節點
        // 若 direction[i] = 0，左 = computed[i]，右 = path[i]
        // 若 direction[i] = 1，左 = path[i]，右 = computed[i]
        
        // Switcher 實現這個邏輯
        component switcher = Switcher();
        switcher.sel <== pathDirection[i];
        switcher.L <== computed[i];
        switcher.R <== path[i];
        
        // 計算父節點
        component hasher = Poseidon(2);
        hasher.inputs[0] <== switcher.outL;
        hasher.inputs[1] <== switcher.outR;
        
        computed[i + 1] <== hasher.out;
    }
    
    // 驗證根
    computed[levels] === root;
    
    // 輸出有效標誌
    valid <== 1;
}

template Main() {
    signal input leaf;
    signal input root;
    signal input path[20];  // 假設深度 20
    signal input pathDirection[20];
    
    component proofChecker = MerkleProofChecker(20);
    proofChecker.leaf <== leaf;
    proofChecker.root <== root;
    for (var i = 0; i < 20; i++) {
        proofChecker.path[i] <== path[i];
        proofChecker.pathDirection[i] <== pathDirection[i];
    }
    
    signal output valid <== proofChecker.valid;
}

4.3.2 約束數量推導

Poseidon 約束數量：

"""
Poseidon 哈希約束數量分析

Poseidon 使用ark (addition-round-keys) 和 MDS (Maximum Distance Separable) 矩陣。

數學模型：
round_i = MDS × (state + ark_i)

其中：
- state 是 3 元素向量（對於 width=3）
- ark_i 是第 i 輪的 round key
- MDS 是最大距離可分矩陣
"""

def poseidon_constraints(width, full_rounds, partial_rounds):
    """
    計算 Poseidon 約束數量
    
    每個算術約束格式：(a + b) * c = d
    
    - 完整輪：所有狀態元素都參與
      constraints_per_full_round = width × 2  # 每個元素一個約束
    
    - 部分輪：只有一個元素參與（非線性）
      constraints_per_partial_round = 2  # 一個約束
    
    總約束數：
    C = (full_rounds_before + full_rounds_after) × width × 2 
        + partial_rounds × 2
    """
    FR = full_rounds // 2  # 前後各一半
    
    full_constraints = FR * width * 2
    partial_constraints = partial_rounds * 2
    
    return full_constraints + partial_constraints

# 對於 Poseidon-3（width=3）
poseidon_3_constraints = poseidon_constraints(3, 8, 57)
print(f"Poseidon-3 約束數: {poseidon_3_constraints}")

# 對於 Merkle 驗證（depth=20）
merkle_constraints = 20 * poseidon_3_constraints + 1  # +1 為根驗證
print(f"Merkle-20 約束數: {merkle_constraints}")

第五章：Noir 電路設計實作

5.1 Noir 語法基礎

5.1.1 基本類型與約束

// Noir 基本語法

// 導入標準庫
use dep::std;

// 函數定義
fn add(a: Field, b: Field) -> Field {
    a + b  // 自動生成約束
}

// 條件約束
fn conditional_select(cond: Field, a: Field, b: Field) -> Field {
    // 約束：cond * (cond - 1) = 0
    // 輸出：cond * a + (1 - cond) * b
    cond * a + (1 - cond) * b
}

// 數組操作
fn sum_array(arr: [Field; 10]) -> Field {
    let mut sum = 0;
    for i in 0..10 {
        sum = sum + arr[i];
    }
    sum
}

5.1.2 約束生成機制

// Noir 約束語法

fn multiply_constraint() {
    let a = 5;
    let b = 3;
    let c = a * b;  // 自動生成約束 c = a × b
    
    // 顯式約束
    constrain c == 15;
    
    // 使用 Field 類型
    let x: Field = 10;
    let y: Field = 20;
    let z = x * y;
    
    constrain z == 200;
}

// 布爾約束
fn bool_constraint(flag: Field) {
    // 約束：flag × (flag - 1) = 0
    constrain flag * (flag - 1) == 0;
}

5.2 Noir 電路範例：範圍證明

5.2.1 電路實現

// Noir 範圍證明
// 證明值在 [0, 2^n) 範圍內

use dep::std;

struct RangeProof {
    value: Field,
    n_bits: Field,
}

impl RangeProof {
    // 創建新的範圍證明
    fn new(value: Field, n_bits: Field) -> Self {
        RangeProof { value, n_bits }
    }
    
    // 驗證範圍
    fn verify(self) -> bool {
        // 計算 2^n
        let max = 1;
        let mut power = 1;
        
        for i in 0..32 {  // 假設最多 32 位
            if i as Field < self.n_bits {
                power = power * 2;
            }
        }
        
        // 約束：value < 2^n
        // 這生成範圍約束
        let condition = self.value * (max - self.value / power);
        
        // 若 value < 2^n，則 value / power = 0，condition > 0
        // 否則，condition 可能為負（但在 Field 中，這表示很大正值）
        
        // 更嚴格的實現應該檢查位
        let mut valid = true;
        
        for i in 0..32 {
            if i as Field < self.n_bits {
                let bit = (self.value >> i) & 1;
                // 約束：bit ∈ {0, 1}
                constrain (bit * (bit - 1)) == 0;
                
                // 若某位超過 1（不可能，但確保安全）
                // valid = valid & (bit <= 1);
            }
        }
        
        valid
    }
}

// 主函數
fn main(value: Field, n_bits: Field) -> pub Field {
    let proof = RangeProof::new(value, n_bits);
    
    // 驗證
    let is_valid = proof.verify();
    
    // 返回值（若無效，約束失敗）
    if is_valid {
        value
    } else {
        0
    }
}

5.2.2 約束分析

/**
 * Noir RangeProof 約束分析
 *
 * 約束數量：
 * 1. 位約束：n × 1 = n 個
 *    constrain (bit * (bit - 1)) == 0
 *
 * 2. 移位運算：依賴編譯器實現
 *    - 若實現為循環：n × O(1)
 *    - 若實現為直接移位：O(log n)
 *
 * 總約束數：O(n)
 */

// 測試輸出
#[test]
fn test_range_proof_constraints() {
    // 8-bit 範圍證明
    let constraints_8 = 8;
    
    // 16-bit 範圍證明
    let constraints_16 = 16;
    
    // 32-bit 範圍證明
    let constraints_32 = 32;
    
    assert_eq(constraints_8, 8);
    assert_eq(constraints_16, 16);
    assert_eq(constraints_32, 32);
}

5.3 Noir 電路範例：zkID 身份驗證

5.3.1 電路設計

// zkID 身份驗證電路
// 證明用戶持有特定私鑰，而不透露私鑰本身

use dep::std;

struct ZkIdentity {
    private_key: Field,
    public_key_hash: Field,
}

impl ZkIdentity {
    // 創建身份
    fn new(private_key: Field, public_key_hash: Field) -> Self {
        ZkIdentity { private_key, public_key_hash }
    }
    
    // 驗證身份
    fn verify(self) -> bool {
        // 計算公鑰哈希
        // 使用 Poseidon 或其他哈希函數
        let computed_hash = std::hash::poseidon::hash([self.private_key]);
        
        // 約束：計算的哈希等於存儲的哈希
        constrain computed_hash == self.public_key_hash;
        
        true
    }
}

// 簽名驗證電路
struct SignatureVerify {
    message: Field,
    signature: Field,
    public_key_hash: Field,
}

impl SignatureVerify {
    fn new(message: Field, signature: Field, public_key_hash: Field) -> Self {
        SignatureVerify { message, signature, public_key_hash }
    }
    
    fn verify(self) -> bool {
        // 驗證簽名
        // 簽名 = Hash(private_key, message)
        let expected_signature = std::hash::poseidon::hash([
            self.public_key_hash,
            self.message
        ]);
        
        // 這裡需要零知識地驗證 private_key
        // 實際實現會更複雜
        
        constrain self.signature == expected_signature;
        
        true
    }
}

// 主函數
fn main(
    private_key: Field,      // 私有輸入
    message: Field,           // 私有輸入
    public_key_hash: Field,   // 公開輸入
    signature: Field          // 公開輸入
) -> pub Field {
    // 驗證身份
    let identity = ZkIdentity::new(private_key, public_key_hash);
    constrain identity.verify();
    
    // 驗證簽名
    let sig_verify = SignatureVerify::new(message, signature, public_key_hash);
    constrain sig_verify.verify();
    
    // 返回驗證結果
    1
}

第六章：電路設計最佳實踐

6.1 約束優化策略

6.1.1 乘法深度優化

策略 1：並行化約束

// 原始：順序乘法，深度 = 3
signal x1 <== a * b;
signal x2 <== x1 * c;
signal x3 <== x2 * d;
// 乘法深度 = 3

// 優化：並行乘法，深度 = 1
signal t1 <== a * b;
signal t2 <== c * d;
signal x3 <== t1 * t2;
// 乘法深度 = 1

策略 2：約束合併

// 原始：多個約束
signal a <== x * y;
signal b <== x * z;
signal c <== a + b;

// 約束數 = 3

// 優化：使用選擇器
signal sel <== (x != 0) * 1;  // 選擇器
signal c <== sel * (y + z) + (1 - sel) * 0;

// 約束數 = 2

6.1.2 信號複製策略

// 策略 1：使用 <-- 避免約束
signal temp1 <-- x * y;  // 無約束拷貝
signal temp2 <-- temp1 * z;  // 無約束拷貝

// 策略 2：減少信號複製次數
// 共享計算結果
component hasher = Poseidon(2);
hasher.inputs[0] <== data1;
hasher.inputs[1] <== data2;

signal hash1 <== hasher.out;
signal hash2 <== hasher.out;  // 共享，避免重複計算

6.2 安全性考量

6.2.1 輸入驗證

// 確保輸入在有效範圍內
template SecureInput(n) {
    signal input value;
    
    // 範圍檢查
    component rangeCheck = RangeProof(n);
    rangeCheck.in <== value;
    
    // 非零檢查（若需要）
    signal isZero <== 1 - value * (1 / value);  // 這裡需要安全實現
}

template NonZero() {
    signal input in;
    signal output out;
    
    // in * inv = 1 當且僅當 in ≠ 0
    // 否則約束失敗
    
    // 安全實現：
    // 使用條件選擇，若 in = 0，則 inv = 0
    signal inv <-- in != 0 ? 1 / in : 0;
    
    // 約束：in * inv = out
    // 當 in = 0, out = 0 → 約束成立，但 circuit 失敗
    // 當 in ≠ 0, out = 1 → 約束成立
    constrain in * inv == out;
    constrain out == 1;  // 強 制非零
}

6.2.2 側信道攻擊防護

// 防護定時攻擊：使用恆定時間操作
template ConstantTimeSelect() {
    signal input selector;  // 0 或 1
    signal input a;
    signal input b;
    signal output out;
    
    // 恆定時間選擇
    // 不依賴 selector 的值來選擇分支
    
    // 實現：out = selector * a + (1 - selector) * b
    out <== selector * a + (1 - selector) * b;
    
    // 約束：selector 為布爾值
    selector * (selector - 1) === 0;
}

// 防護暴力破解：增加約束複雜度
template AntiBruteForce() {
    signal input secret;
    signal input attempt;
    
    // 比較操作
    signal diff <== attempt - secret;
    signal is_equal <== diff * diff;  // 差值平方
    
    // 約束：相等時 is_equal = 0
    // 不相等時，is_equal > 0
    // 添加額外約束使其更難枚舉
    
    // 防護：添加隨機種子（這裡使用公開值，實際需要私有）
    signal random;
    signal protected <== is_equal * random;
}

結論

本文從數學推導出發，深入分析了 ZK-SNARK 電路設計的核心原理與實作技術。重點包括：

1. 電路複雜度理論：約束數量與乘法深度的數學界限
2. 橢圓曲線密碼學：點運算與配對函數的完整推導
3. 約束系統進階理論：R1CS 到 QAP 的轉換過程
4. Circom 實作：完整的約束生成與優化範例
5. Noir 實作：現代 ZK 電路語言的實作技術
6. 最佳實踐：約束優化與安全性考量

這些技術是構建高效、安全 ZK 應用的基礎。隨著 ZK 技術的持續發展，電路設計將在隱私保護、可擴展性和安全性方面發揮越來越重要的作用。

參考文獻：

1. Groth, J. (2016). On the Size of Pairing-based Non-interactive Arguments.
2. Gabizon, A., Williamson, Z. J., & Ciobotaru, O. (2019). PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge.
3. Ben-Sasson, E., et al. (2018). STARKs: Variants, Practice, and Theory.
4. Buterin, V. (2017). On Slow and Fast Block Times.
5. Circom Documentation. https://docs.circom.io
6. Noir Documentation. https://noir-lang.org