title: "ZK-SNARK 與 STARK 數學推導完整攻略：從橢圓曲線到多項式承諾的互動式實戰"

summary: "本文以互動式範例深度解析 ZK-SNARK 與 STARK 的密碼學原理，包含橢圓曲線密碼學基礎、多項式承諾、R1CS 約束系統、Groth16 與 Plonk 演算法、以及 STARK 的 FRI 協議。提供完整的數學推導與 Python/Solidity 程式碼範例，幫助讀者從直覺到嚴密理解零知識證明的底層機制。"

date: "2026-03-31"

category: "privacy"

tags:

• "privacy"
• "zk-snark"
• "zk-stark"
• "zero-knowledge"
• "cryptography"
• "mathematics"
• "elliptic-curve"
• "polynomial"

difficulty: "advanced"

status: "published"

parent: null

datacutoffdate: "2026-03-31"

references:

• title: "以太坊官方文件 - ZK-SNARKs"

url: "https://ethereum.org/developers/docs/zksnarks"

desc: "ZK-SNARK 官方介紹"

tier: "tier1"

• title: "以太坊官方文件 - ZK-STARKs"

url: "https://ethereum.org/developers/docs/zkstarks"

desc: "ZK-STARK 官方介紹"

tier: "tier1"

• title: "Vitalik - ZK-SNARKs: Into the Weeds"

url: "https://vitalik.eth.limo/general/2021/zksnarks.html"

desc: "ZK-SNARK 深度技術解析"

tier: "tier3"

• title: "Vitalik - An approximate introduction to STARKs"

url: "https://vitalik.eth.limo/general/2018/07/21/understandinganimportant.html"

desc: "STARK 技術解析"

tier: "tier3"

• title: "Plonky3 GitHub"

url: "https://github.com/Plonky3/Plonky3"

desc: "Plonky3 實現"

tier: "tier2"

• title: "zkSNARKs in a Nutshell"

url: "https://github.com/julescat/zkproofs"

desc: "zkSNARK 理論基礎"

tier: "tier2"

disclaimer: "本網站內容僅供教育與資訊目的，不構成任何投資建議或推薦。密碼學技術涉及高度專業知識，建議讀者在實際應用前進行深入研究。"

ZK-SNARK 與 STARK 數學推導完整攻略：從橢圓曲線到多項式承諾的互動式實戰

說真的，每次有人跟我炫耀「我們用了零知識證明」，我都忍不住想問：你用的是 SNARK 還是 STARK？Groth16 還是 Plonk？KZG 承諾還是 IPA？如果你答不上來，那所謂的「零知識證明」對你來說就是個黑盒子。

這篇文章我要把這個黑盒子打開給你看。不是那種「相信我，這很安全」的陳述，而是實打實的數學推導和可運作的程式碼。準備好燒腦了嗎？讓我們開始。

一、為什麼要先懂數學

零知識證明是密碼學皇冠上的寶石，但這顆寶石的底層是冰冷的數學。很多人跳過數學直接去看程式碼，結果就是「會用但不會調」——一旦遇到問題就抓瞎。

舉個例子。2022 年底，有個 DeFi 協議號稱使用了 ZK 證明保護用戶隱私。結果被發現，他們的電路設計有漏洞，攻擊者可以在不提供有效證明的情況下通過驗證。問題出在哪？電路約束條件不夠嚴格——這是需要數學推導才能發現的問題。

所以，別急著寫程式碼。讓我們先搞清楚背後的數學。

二、橢圓曲線密碼學：ZK 證明的地基

2.1 橢圓曲線是什麼

零知識證明在以太坊上幾乎都是基於橢圓曲線密碼學（ECC）。讓我們從最基礎開始。

橢圓曲線是一個滿足以下方程式的點集合：

y² = x³ + ax + b (mod p)

其中 p 是一個大質數，a 和 b 是曲線參數。

以太坊和大多數 ZK 系統使用的曲線叫做 BN128（又稱 ALT_BN128），參數如下：

"""
BN128 曲線參數
"""
import math

# 曲線方程：y² = x³ + ax + b (mod p)
# BN128 使用的是優化的參數

# 質數模數（Fp 的階）
P = 21888242871839275222246405745257275088548364400416034343698204186575808495617

# 曲線係數
A = 0
B = 3

# 基點 G（曲線上的一個生成元）
Gx = 1
Gy = 2

# 羣的階（n * G = O，其中 O 是單位元）
N = 21888242871839275222246405745257275088696311157297823662689037894645226208583

# 餘因子（用於計算實際可用的子羣大小）
H = 1  # BN128 是質數階曲線，H = 1

print(f"BN128 曲線參數：")
print(f"質數模數 P: {P}")
print(f"曲線方程: y² = x³ + {A}x + {B} (mod {P})")
print(f"基點 G: ({Gx}, {Gy})")
print(f"羣階 N: {N}")

2.2 點加法與點乘法

橢圓曲線上的點可以相加，這個運算有個漂亮的几何意義：

"""
橢圓曲線點運算
"""
class EllipticCurve:
    def __init__(self, p, a, b):
        self.p = p  # 質數模數
        self.a = a  # 曲線係數 a
        self.b = b  # 曲線係數 b
    
    def on_curve(self, x, y):
        """檢查點 (x, y) 是否在曲線上"""
        return (y * y - x**3 - self.a * x - self.b) % self.p == 0
    
    def point_add(self, P, Q):
        """
        點加法：P + Q
        
        幾何意義：
        - 如果 P != Q：連線 P 和 Q，與曲線交於第三點 R，取 R 的 x 軸對稱點即為 P + Q
        - 如果 P == Q：過 P 作曲線的切線，同樣操作得到 2P
        """
        if P is None:
            return Q
        if Q is None:
            return P
        
        x1, y1 = P
        x2, y2 = Q
        
        if x1 == x2 and y1 == -y2 % self.p:
            return None  # P + (-P) = O（無窮遠點）
        
        if P == Q:
            # 點加倍公式
            # λ = (3x1² + a) / (2y1) mod p
            lam = (3 * x1 * x1 + self.a) * pow(2 * y1, -1, self.p) % self.p
        else:
            # 普通加法公式
            # λ = (y2 - y1) / (x2 - x1) mod p
            lam = (y2 - y1) * pow(x2 - x1, -1, self.p) % self.p
        
        x3 = (lam * lam - x1 - x2) % self.p
        y3 = (lam * (x1 - x3) - y1) % self.p
        
        return (x3, y3)
    
    def scalar_mult(self, k, P):
        """
        標量乘法：k * P
        
        利用二元展開實現高效計算：
        k * P = (b_n * 2^n + ... + b_1 * 2 + b_0) * P
              = b_n * 2^n * P + ... + b_1 * 2 * P + b_0 * P
        
        每個步驟只需要一次加倍和一次加法
        時間複雜度：O(log k)
        """
        if k % self.p == 0:
            return None
        if k < 0:
            return self.scalar_mult(-k, self.point_neg(P))
        
        result = None
        addend = P
        
        while k:
            if k & 1:
                result = self.point_add(result, addend)
            addend = self.point_add(addend, addend)  # 加倍
            k >>= 1
        
        return result

# 測試
curve = EllipticCurve(P, A, B)
G = (Gx, Gy)

# 驗證 G 在曲線上
print(f"G 在曲線上: {curve.on_curve(Gx, Gy)}")

# 計算 2G
double_G = curve.scalar_mult(2, G)
print(f"2G = {double_G}")

# 計算 2^n * G（常見用於公鑰）
for i in [4, 8, 16, 32]:
    result = curve.scalar_mult(i, G)
    print(f"{i}G = {result}")

2.3 離散對數問題：ECC 安全性的核心

ECC 的安全性基於「離散對數問題」：

給定：
- 曲線上的點 G（基點）
- 另一個點 P = k * G

求：
- 整數 k

難度：
- 目前沒有已知的多項式時間演算法
- 對 256 位安全等級的曲線，需要大約 2^128 次運算才能破解

這個問題的難度就是 ZK 證明可靠性的數學基礎。

三、從計算到電路：NP 問題的電路表示

3.1 什麼是算術電路

零知識證明系統的第一步，是把你想證明的計算轉換成「算術電路」。

算術電路由兩種門組成：

• 加法門：把兩個輸入相加
• 乘法門：把兩個輸入相乘

所有其他的運算（減法、除法、指數）都可以用這兩種門來實現。

"""
把簡單計算轉換成算術電路
"""
from collections import defaultdict

class ArithmeticCircuit:
    """
    算術電路表示
    
    電路由以下元素組成：
    - 输入变量（public 或 private）
    - 常量
    - 加法門和乘法門
    - 输出
    """
    
    def __init__(self):
        self.num_inputs = 0
        self.num_outputs = 0
        self.constraints = []  # R1CS 約束列表
        self.wire_mapping = {}  # 變數名 -> 索引
        
    def new_input(self, name, is_public=False):
        """創建新的輸入變數"""
        idx = self.num_inputs
        self.wire_mapping[name] = idx
        self.num_inputs += 1
        return idx
    
    def add_constraint(self, left_vars, right_vars, out_var):
        """
        添加 R1CS 約束
        
        R1CS (Rank-1 Constraint System) 標準形式：
        (Σ a_i * x_i) * (Σ b_i * x_i) = (Σ c_i * x_i)
        
        其中 x_i 是所有變數的集合
        """
        self.constraints.append({
            'left': left_vars,   # 左側線性組合的係數
            'right': right_vars, # 右側線性組合的係數
            'out': out_var        # 輸出變數
        })

def example_zk_identity():
    """
    例子：證明你知道 x 使得 x^3 + x + 5 = y
    
    這個例子展示如何把一個簡單的多項式計算轉換成電路
    """
    circuit = ArithmeticCircuit()
    
    # 創建輸入和輸出
    x = circuit.new_input('x', is_public=False)  # 私密輸入
    y = circuit.new_input('y', is_public=True)   # 公開輸出
    
    # 我們需要引入中間變數來表示計算過程
    # x^3 = x * x * x
    
    # 約束 1: x² = x * x
    circuit.add_constraint(
        {'x': 1},  # 左側：1 * x
        {'x': 1},  # 右側：1 * x  
        'x2'       # 輸出：x²
    )
    
    # 約束 2: x³ = x² * x
    circuit.add_constraint(
        {'x2': 1},  # 左側：1 * x²
        {'x': 1},   # 右側：1 * x
        'x3'        # 輸出：x³
    )
    
    # 約束 3: x³ + x = t1
    circuit.add_constraint(
        {'x3': 1, 'x': 1},  # 左側：1 * x³ + 1 * x
        {'one': 1},          # 右側：1（常數 1）
        't1'                 # 輸出：x³ + x
    )
    
    # 約束 4: t1 + 5 = y
    circuit.add_constraint(
        {'t1': 1},           # 左側：1 * t1
        {'one': 1},          # 右側：1
        'y'                  # 輸出：x³ + x + 5
    )
    
    print("電路約束數量：", len(circuit.constraints))
    print("輸入變數：", circuit.num_inputs)
    
    return circuit

3.2 R1CS 到 QAP 的轉換

R1CS（Rank-1 Constraint System）約束雖然直觀，但驗證效率很低。QAP（Quadratic Arithmetic Program）把約束合併成一個多項式，使得驗證只需要檢查一個多項式等式。

"""
R1CS 到 QAP 的轉換

給定 R1CS 約束系統：
(Σ a_i * x_i) * (Σ b_i * x_i) = (Σ c_i * x_i)

轉換為：
P(x) = L(x) * R(x) - O(x)

其中 L(x), R(x), O(x) 是多項式，在每個約束對應的點上滿足等式。
"""
import numpy as np
from numpy.polynomial import polynomial as P

def r1cs_to_qap(constraints, num_vars):
    """
    把 R1CS 約束轉換為 QAP 多項式
    
    過程：
    1. 對每個約束，把係數向量擴展到長度 = num_vars + 1
    2. 對每個位置，構造拉格朗日插值多項式
    3. 合併得到 L(x), R(x), O(x)
    """
    
    # 構造拉格朗日基多項式
    def lagrange_basis(points, i):
        """
        構造在 points[i] 處為 1，其他點處為 0 的多項式
        """
        xi = points[i]
        numerator = [1]  # (x - x0)(x - x1)...
        denominator = 1
        
        for j, xj in enumerate(points):
            if j != i:
                numerator = np.convolve(numerator, [1, -xj])
                denominator *= (xi - xj)
        
        return [c / denominator for c in numerator]
    
    points = list(range(len(constraints)))
    
    # 構造 A(x), B(x), C(x) 的係數
    A_coeffs = np.zeros(num_vars + 1)
    B_coeffs = np.zeros(num_vars + 1)
    C_coeffs = np.zeros(num_vars + 1)
    
    for idx, constraint in enumerate(constraints):
        # 對每個約束，構造插值多項式
        basis = lagrange_basis(points, idx)
        
        # 累加貢獻
        for var_idx, coeff in constraint['left'].items():
            A_coeffs[var_idx] += coeff * np.array(basis)
        
        for var_idx, coeff in constraint['right'].items():
            B_coeffs[var_idx] += coeff * np.array(basis)
        
        for var_idx, coeff in constraint['out'].items():
            C_coeffs[var_idx] += coeff * np.array(basis)
    
    return A_coeffs, B_coeffs, C_coeffs

# 驗證：測試簡單例子
print("=== R1CS 到 QAP 轉換測試 ===")
constraints = [
    {
        'left': {0: 1, 1: 1},  # x0 + x1
        'right': {0: 1},        # x0
        'out': {2: 1}           # x2
    }
]
A, B, C = r1cs_to_qap(constraints, 3)
print(f"A(x) 係數: {A}")
print(f"B(x) 係數: {B}")
print(f"C(x) 係數: {C}")

四、多項式承諾：SNARK 的關鍵技術

4.1 為什麼需要多項式承諾

QAP 把驗證從 N 個約束檢查變成了一個多項式等式檢查。但這還不夠——我們需要一種方法，讓證明者可以「承諾」一個多項式，稍後再打開它，同時保證被打開的值確實是原多項式在某點的取值。

這就是多項式承諾的作用。

4.2 KZG 承諾：主流的 SNARK 承諾方案

KZG（Kate-Zaverucha-Goldberg）承諾是目前最流行的多項式承諾方案，廣泛應用於 Plonk、PLONKish 等 ZK 電路系統中。

"""
KZG 多項式承諾 - 簡化版實現

核心思想：
- 承諾：把多項式 f(x) 在一個秘密點 τ 處求值，承諾 f(τ)
- 打開：提供 f(x) 和 f(τ)，驗證者檢查 f(τ) 是否正確
- 零知識：τ 從未被揭露
"""

import hashlib
import random

class KZGCommitment:
    """
    KZG 多項式承諾方案
    
    設置（Trusted Setup）：
    - 選擇秘密值 τ
    - 計算 G, τG, τ²G, ..., τ^n G
    - 生成結構化參考字串 (SRS)
    """
    
    def __init__(self, tau, max_degree):
        """
        初始化 KZG 承諾系統
        
        參數：
        - tau: 秘密評估點
        - max_degree: 支持的最大多項式次數
        """
        self.tau = tau
        self.max_degree = max_degree
        
        # 模擬橢圓曲線點（實際應用中用真實的 G1, G2 點）
        self.G = (1, 2)  # 生成元
        
        # 預計算 SRS = [G, τG, τ²G, ..., τ^n G]
        self.srs = []
        current = self.G
        for i in range(max_degree + 1):
            self.srs.append(current)
            current = self.scalar_mult_tau(current)
    
    def scalar_mult_tau(self, P):
        """計算 τ * P"""
        x, y = P
        # 這裡應該是 ECC 點乘法，簡化為：
        return ((x * self.tau) % P, (y * self.tau) % P)
    
    def commit(self, polynomial):
        """
        對多項式生成承諾
        
        f(x) = Σ a_i * x^i
        
        承諾 C = Σ a_i * (τ^i * G) = f(τ) * G
        
        這隱藏了多項式係數，但綁定了多項式本身
        """
        result = (0, 0)  # 單位元
        
        for i, coeff in enumerate(polynomial.coeffs):
            # C += coeff * SRS[i]
            result = self.point_add(
                result,
                self.scalar_mult_scalar(self.srs[i], coeff)
            )
        
        return result
    
    def scalar_mult_scalar(self, P, k):
        """標量乘法 k * P"""
        x, y = P
        return ((x * k) % P[0], (y * k) % P[0]) if isinstance(P[0], int) else ((x * k), (y * k))
    
    def point_add(self, P, Q):
        """點加法"""
        if P == (0, 0):
            return Q
        if Q == (0, 0):
            return P
        x1, y1 = P
        x2, y2 = Q
        # 簡化版本，實際應該用完整的 ECC 加法
        return ((x1 + x2) % 1000000007, (y1 + y2) % 1000000007)
    
    def create_opening(self, polynomial, x):
        """
        創建 opening proof
        
        目標：證明 f(x) = y
        
        構造：
        - 商多項式 h(x) = (f(x) - f(x₀)) / (x - x₀)
        - 承諾 h(τ)
        """
        y = polynomial.evaluate(x)
        
        # 商多項式
        h = polynomial.divide_by_linear(x, y)
        
        # 承諾 h(τ)
        h_commitment = self.commit(h)
        
        return {
            'evaluation_point': x,
            'claimed_value': y,
            'quotient_commitment': h_commitment
        }
    
    def verify_opening(self, commitment, opening):
        """
        驗證 opening proof
        
        檢查：e(C - y*G, G) = e(h_commitment, τG - x*G)
        
        這確保了 h(τ) = (f(τ) - y) / (τ - x)
        即 f(τ) = y + (τ - x) * h(τ)
        """
        # 這裡應該實現真實的雙線性配對驗證
        # 簡化版本只做概念展示
        x = opening['evaluation_point']
        y = opening['claimed_value']
        h_commit = opening['quotient_commitment']
        
        # 驗證邏輯（雙線性配對）
        # e(C - y*G, G) == e(h_commit, τG - x*G)
        
        return True  # 簡化版本

class Polynomial:
    """多項式表示"""
    
    def __init__(self, coeffs):
        self.coeffs = coeffs  # 從常數項開始 [a0, a1, a2, ...]
    
    def evaluate(self, x):
        """在 x 處求值"""
        result = 0
        x_power = 1
        for coeff in self.coeffs:
            result += coeff * x_power
            x_power *= x
        return result
    
    def divide_by_linear(self, x0, y0):
        """
        (f(x) - f(x₀)) / (x - x₀)
        
        利用多項式除法：如果 f(x₀) = y，則 f(x) - y 可以被 (x - x₀) 整除
        """
        # 構造 f(x) - y 的係數
        diff_coeffs = self.coeffs.copy()
        diff_coeffs[0] -= y0
        
        # 多項式長除法
        # (a_n x^n + ... + a₀) / (x - x₀) = b_{n-1} x^{n-1} + ...
        result = []
        current = 0
        for coeff in diff_coeffs:
            current = current * x0 + coeff
            result.append(current)
        
        # 最後一個是餘數，應該為 0（驗證）
        remainder = result.pop()
        assert remainder == 0, f"除法有餘數：{remainder}"
        
        return Polynomial(result) if result else Polynomial([0])

# 使用範例
print("=== KZG 承諾測試 ===")
kzg = KZGCommitment(tau=123456789, max_degree=10)

# 構造多項式 f(x) = 2 + 3x + x²
f = Polynomial([2, 3, 1])

# 生成承諾
commitment = kzg.commit(f)
print(f"多項式 f(x) = 2 + 3x + x² 的承諾：{commitment}")

# 創建 opening
opening = kzg.create_opening(f, x=5)
print(f"在 x=5 處的值：{opening['claimed_value']}")
print(f"預期值 f(5) = 2 + 15 + 25 = {f.evaluate(5)}")

# 驗證
valid = kzg.verify_opening(commitment, opening)
print(f"Opening 驗證結果：{valid}")

4.3 KZG 的雙線性配對

KZG 承諾的安全性依賴於「雙線性配對」（Bilinear Pairing）。

雙線性配對是兩個橢圓曲線羣之間的一個映射：

e: G1 × G2 → GT

滿足：
1. 雙線性：e(aP, bQ) = e(P, Q)^{ab}
2. 非退化：e(G, G) ≠ 1
3. 可計算：e(P, Q) 可以高效計算

這個性質允許我們驗證「多項式承諾的 opening」而無需知道秘密 τ。

五、Groth16：經典 SNARK 演算法

5.1 Groth16 的三個階段

Groth16 是最早被廣泛採用的 ZK-SNARK 演算法，由 Jens Groth 在 2016 年提出。它由三個階段組成：

階段 1：設置（Setup）

"""
Groth16 設置階段

輸入：
- 電路 C（以 QAP 形式表示）
- 安全參數 λ

輸出：
- 公開參數 (G1, G2, Alpha, Beta, Gamma, Delta, A_i, B_i, C_i)
"""
import secrets

class Groth16Setup:
    """
    Groth16 設置
    """
    
    def __init__(self, num_constraints, num_inputs):
        self.n_constraints = num_constraints
        self.n_inputs = num_inputs
        
        # 選擇隨機值（這些值需要被銷毀，永遠不能暴露！）
        self.alpha = secrets.randbelow(2**256)  # 公開隨機
        self.beta = secrets.randbelow(2**256)   # 公開隨機
        self.gamma = secrets.randbelow(2**256) # 公開隨機
        self.delta = secrets.randbelow(2**256) # 公開隨機
        self.tau = [secrets.randbelow(2**256) for _ in range(num_constraints + 5)]
        
    def generate_srs(self):
        """
        生成結構化參考字串 SRS
        
        SRS 包含：
        - [α]_1, [β]_1, [γ]_1, [δ]_1, [τ^i]_1
        - [β]_2, [γ]_2, [δ]_2, [τ^i]_2
        """
        # 這裡應該使用真實的橢圓曲線點
        # 簡化版本用隨機數表示
        srs_g1 = {
            'alpha': self.alpha * 100,  # 模擬 [α]_1
            'beta': self.beta * 100,
            'gamma': self.gamma * 100,
            'delta': self.delta * 100,
            'tau_powers': [self.tau[i] * 100 for i in range(self.n_constraints + 5)]
        }
        
        srs_g2 = {
            'beta': self.beta * 200,  # 模擬 [β]_2
            'gamma': self.gamma * 200,
            'delta': self.delta * 200,
            'tau_powers': [self.tau[i] * 200 for i in range(self.n_constraints + 5)]
        }
        
        return srs_g1, srs_g2
    
    def generate_verification_key(self, srs_g1, srs_g2):
        """
        生成驗證金鑰
        """
        return {
            'alpha_g1': srs_g1['alpha'],
            'beta_g2': srs_g2['beta'],
            'gamma_g2': srs_g2['gamma'],
            'delta_g2': srs_g2['delta'],
        }
    
    def generate_proving_key(self, srs_g1, srs_g2):
        """
        生成證明金鑰
        """
        return {
            'alpha_g1': srs_g1['alpha'],
            'beta_g1': srs_g1['beta'],
            'delta_g1': srs_g1['delta'],
            'tau_powers_g1': srs_g1['tau_powers'],
            'beta_g2': srs_g2['beta'],
            'delta_g2': srs_g2['delta'],
        }

# 測試
setup = Groth16Setup(num_constraints=100, num_inputs=10)
srs_g1, srs_g2 = setup.generate_srs()
pk = setup.generate_proving_key(srs_g1, srs_g2)
vk = setup.generate_verification_key(srs_g1, srs_g2)

print("Groth16 設置完成")
print(f"驗證金鑰：{vk}")

階段 2：證明（Proof Generation）

"""
Groth16 證明階段

輸入：
- 電路 C
- 公開輸入 x
- 私密見證 w
- 證明金鑰 pk

輸出：
- 證明 π = (A, B, C)
"""

class Groth16Proof:
    """
    Groth16 證明結構
    """
    
    def __init__(self, A, B, C):
        self.A = A  # G1 點
        self.B = B  # G2 點
        self.C = C  # G1 點

def groth16_prove(pk, public_inputs, private_witness, A_coeffs, B_coeffs, C_coeffs):
    """
    生成 Groth16 證明
    
    證明者需要：
    1. 計算 A = α + Σ a_i * A_i(tau) + r * δ
    2. 計算 B = β + Σ b_i * B_i(tau) + s * δ
    3. 計算 C = (Σ c_i * C_i(tau) + A * s + B * r - α*β)/δ + t(tau)/δ
    """
    # 1. 計算 A
    # A = alpha + Σ a_i * A_i(tau) + r * delta
    r = secrets.randbelow(2**256)  # 隨機盲化值
    A = pk['alpha_g1']
    
    for i, val in enumerate(public_inputs + private_witness):
        A += val * pk['tau_powers_g1'][i]  # Σ a_i * A_i
    
    A += r * pk['delta_g1']  # 盲化
    
    # 2. 計算 B（類似的過程）
    s = secrets.randbelow(2**256)
    B = pk['beta_g1']  # 實際應該是 G2 點
    
    for i, val in enumerate(public_inputs + private_witness):
        B += val * pk['tau_powers_g1'][i]
    
    B += s * pk['delta_g1']
    
    # 3. 計算 C
    # 這裡簡化了，實際計算要複雜得多
    C = 0
    for i, val in enumerate(public_inputs + private_witness):
        C += val * pk['tau_powers_g1'][i + len(public_inputs)]
    
    C += A * s + B * r - pk['alpha_g1'] * pk['beta_g1']
    C /= pk['delta_g1']
    
    return Groth16Proof(A, B, C)

print("Groth16 證明生成函數已定義")

階段 3：驗證（Verification）

"""
Groth16 驗證階段

輸入：
- 驗證金鑰 vk
- 公開輸入 x
- 證明 π

輸出：
- Accept / Reject
"""

def groth16_verify(vk, public_inputs, proof):
    """
    驗證 Groth16 證明
    
    驗證等式：
    e(A, B) = e(α, β) * e(Σ x_i * A_i, Σ x_i * B_i) * e(C, δ)
    
    這確保了：
    - 電路約束被滿足
    - 私密見證被正確使用
    - 零知識：隨機盲化值 r, s 隱藏了私密輸入
    """
    # 雙線性配對驗證
    # e(A, B) = e(alpha_g1, beta_g2) * e(gamma_g2, delta_g2)^{-Σ x_i}
    
    # 簡化的驗證邏輯
    # 實際需要四次配對運算
    
    # 計算左側配對：e(A, B)
    left_pairing = proof.A * proof.B  # 模擬
    
    # 計算右側
    # e(alpha, beta) * e(C, delta)
    right_pairing = vk['alpha_g1'] * vk['beta_g2']
    
    # 驗證
    # 實際複雜得多，這裡只是概念展示
    is_valid = abs(left_pairing - right_pairing) < 1e-10
    
    return is_valid

print("Groth16 驗證函數已定義")

5.2 Groth16 的優缺點

優點：

• 證明非常小（只有 3 個群元素）
• 驗證速度快（只需要幾次配對運算）
• 非常成熟，有大量實現

缺點：

• 需要每個電路单独進行 trusted setup
• 設置複雜且不安全（如果 τ 洩露，攻擊者可以偽造任意證明）
• 電路和輸入需要「對齊」，無法通用

六、STARK：無需信任設置的替代方案

6.1 STARK 與 SNARK 的核心區別

6.2 FRI 協議：STARK 的核心

STARK 使用 FRI（Fast Reed-Solomon Interactive Oracle Proof of Proximity）來驗證「多項式的次數確實是 d」。

"""
FRI 協議 - 簡化概念展示

目標：證明 f(x) 是一個次數小於 d 的多項式

方法：
1. 提交者聲稱 f 是低次數多項式
2. 驗證者隨機選擇挑戰值 ρ
3. 提交者構造 f 的「折疊」版本
4. 重複步驟 1-3，直到驗證者確信
"""

import random

class FRIProtocol:
    """
    FRI 協議實現
    """
    
    def __init__(self, domain_size, max_degree):
        self.domain_size = domain_size  # 評估域大小
        self.max_degree = max_degree    # 最大次數
        
    def commit_phase(self, f_coeffs):
        """
        提交階段：提交者公開 f 在整個域上的所有取值
        """
        domain = list(range(self.domain_size))
        evaluations = [
            sum(f_coeffs[i] * (x ** i) for i in range(len(f_coeffs)))
            for x in domain
        ]
        return evaluations
    
    def query_phase(self, evaluations, num_queries=20):
        """
        查詢階段：驗證者隨機抽查幾個點
        """
        domain = list(range(self.domain_size))
        query_indices = random.sample(domain, min(num_queries, len(domain)))
        query_values = [evaluations[i] for i in query_indices]
        
        return query_indices, query_values
    
    def fold(self, evaluations, rho):
        """
        折疊階段：把多項式次數降低一半
        
        f(x) = (1 - rho) * f_even(x²) + rho * x * f_odd(x²)
        
        這裡的 f_even 和 f_odd 是 f 的偶數次和奇數次部分
        """
        n = len(evaluations)
        half_n = n // 2
        
        f_even = [
            (evaluations[2*i] + evaluations[2*i+1]) / 2
            for i in range(half_n)
        ]
        
        f_odd = [
            (evaluations[2*i] - evaluations[2*i+1]) / (2 * rho)
            for i in range(half_n)
        ]
        
        # 合併成新多項式（次數降低一半）
        folded = [
            f_even[i] + rho * f_odd[i]
            for i in range(half_n)
        ]
        
        return folded, f_even, f_odd

def stark_prove(f_coeffs, max_degree, num_queries=30):
    """
    完整的 STARK 證明過程
    
    實際的 STARK 還包括：
    - 低次數測試（FRI）
    - 梅森範圍擴展
    - Merkle 樹承諾
    - 最終性確認
    """
    fri = FRIProtocol(domain_size=1024, max_degree=max_degree)
    
    # 1. 提交初始多項式
    evaluations = fri.commit_phase(f_coeffs)
    
    # 2. FRI 折疊循環
    num_layers = int(math.log2(len(evaluations))) - int(math.log2(max_degree))
    current_eval = evaluations
    rho_values = []
    f_even_values = []
    f_odd_values = []
    
    for layer in range(num_layers):
        rho = random.random()  # 驗證者挑戰
        rho_values.append(rho)
        
        current_eval, f_even, f_odd = fri.fold(current_eval, rho)
        f_even_values.append(f_even)
        f_odd_values.append(f_odd)
    
    # 3. 最終多項式（應該是常數）
    final_value = current_eval[0]
    
    # 4. 查詢和驗證
    query_indices, query_values = fri.query_phase(evaluations, num_queries)
    
    proof = {
        'final_value': final_value,
        'rho_values': rho_values,
        'query_indices': query_indices,
        'query_values': query_values,
        'merkle_proofs': []  # 省略 Merkle 樹
    }
    
    return proof

def stark_verify(proof, max_degree, num_queries=30):
    """
    驗證 STARK 證明
    
    驗證過程：
    1. 檢查最終值是常數
    2. 重新計算查詢點的折疊路徑
    3. 驗證每層的代數關係
    """
    # 1. 最終多項式應該是常數
    if abs(proof['final_value'] - 0) > 1e-6:
        return False  # 最終多項式不是零多項式
    
    # 2. 驗證查詢（簡化版本）
    # 實際需要重建整個 Merkle 證明路徑
    
    return True

print("=== STARK FRI 協議概念展示 ===")
print("FRI 協議是 STARK 的核心，允許驗證者確信多項式次數確實低於 d")
print("關鍵特性：只需 O(log n) 次查詢，無需信任設置")

6.3 STARK 的實際應用

STARK 雖然證明較大，但有兩個顯著優勢：

1. 無需信任設置：不會有「有毒廢料」問題
2. 抗量子：只依賴哈希函數的安全性

StarkWare 用 STARK 建構了 StarkEx，一個用於 Layer 2 擴容的 ZK-Rollup。zkSync 3.0（Boojum）也開始使用 STARK。

七、Plonk：通用 SNARK 的崛起

7.1 Plonk 的優勢

Plonk 是一種「通用」SNARK，解決了 Groth16 的幾個主要問題：

• 通用設置：只需要一個「 универсальный」 trusted setup，所有電路可以共用
• 電路可更新：可以添加新電路而無需重新執行整個設置
• 標準化：ERC-7683 等標準都是基於 Plonkish 電路

7.2 Plonk 的電路結構

Plonk 的電路由三種「約束」組成：

"""
Plonkish 電路約束

Plonk 使用統一的約束系統，包括：
1. 普通約束（Standard Wire Constraints）
2. 複製約束（Copy Constraints）- 連接不同門的同一變數
3. 查找約束（Lookup Constraints）- 支援查表操作
"""

class PlonkConstraint:
    """
    Plonk 約束結構
    """
    
    def __init__(self, q_l, q_r, q_o, q_m, q_c, w_l, w_r, w_o):
        """
        Plonk 門約束：
        q_l * a + q_r * b + q_m * a * b + q_o * c + q_c = 0
        
        其中：
        - q_l, q_r, q_o, q_m, q_c 是選擇係數
        - a, b, c 是三個 wire 的值
        - 這個等式必須對所有門都成立
        """
        self.q_l = q_l  # 左輸入選擇係數
        self.q_r = q_r  # 右輸入選擇係數
        self.q_o = q_o  # 輸出選擇係數
        self.q_m = q_m  # 乘法選擇係數
        self.q_c = q_c  # 常數選擇係數
        
        self.w_l = w_l  # 左 wire 索引
        self.w_r = w_r  # 右 wire 索引
        self.w_o = w_o  # 輸出 wire 索引

class PlonkCircuit:
    """
    Plonk 電路
    
    由以下元素組成：
    - n 個普通門
    - m 個 public input/output
    - 複製約束（連接特定的 wires）
    """
    
    def __init__(self, num_gates, num_public_inputs):
        self.gates = []
        self.num_gates = num_gates
        self.num_public_inputs = num_public_inputs
        self.copy_constraints = []
        
    def add_gate(self, constraint):
        """添加一個 Plonk 門"""
        self.gates.append(constraint)
    
    def add_copy_constraint(self, wire_a, wire_b):
        """添加複製約束：wire_a = wire_b"""
        self.copy_constraints.append((wire_a, wire_b))
    
    def add_public_input(self, wire_idx):
        """將某個 wire 標記為 public input"""
        assert wire_idx < len(self.gates) * 3  # 每個門有 3 個 wire
        # 標記邏輯
    
    def generate_permutation_argument(self):
        """
        生成置換論點（Permutation Argument）
        
        用於證明複製約束被滿足
        核心思想：把所有 wires 看成一個循環排列
        """
        # 這是 Plonk 證明中計算量最大的部分之一
        # 需要為所有 wires 構造完整的循環排列
        pass

def plonk_example():
    """
    Plonk 電路示例：證明知道 a, b 使得 a * b = c
    """
    circuit = PlonkCircuit(num_gates=1, num_public_inputs=1)
    
    # 約束：a * b = c
    # 翻譯成 Plonk 形式：0 * a + 0 * b + 1 * (a * b) + 0 * c + 0 = 0
    # 即：(a * b) - c = 0
    constraint = PlonkConstraint(
        q_l=0,
        q_r=0,
        q_o=-1,  # 減去輸出
        q_m=1,   # 乘法係數
        q_c=0,
        w_l=0,   # a
        w_r=1,   # b
        w_o=2    # c
    )
    
    circuit.add_gate(constraint)
    
    # 標記 public inputs/outputs
    circuit.add_public_input(2)  # c 是 public
    
    print("Plonk 電路示例：a * b = c")
    print(f"門數量：{circuit.num_gates}")
    print(f"Public inputs：{circuit.num_public_inputs}")

plonk_example()

八、實際應用：ZK 證明在以太坊上的部署

8.1 以太坊上的 ZK 證明驗證合約

現在大多數 ZK 系統都支援以太坊上的鏈上驗證。以下是 Groth16 驗證的 Solidity 範例：

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

/**
 * @title Groth16Verifier
 * @notice 簡化版 Groth16 驗證合約
 * @dev 實際部署需要使用 snarkjs 或其他工具生成的驗證合約
 */
contract Groth16Verifier {
    
    // 驗證金鑰
    uint256 public alpha_x;
    uint256 public alpha_y;
    uint256 public beta_x1;
    uint256 public beta_x2;
    uint256 public beta_y2;
    uint256 public gamma_x1;
    uint256 public gamma_x2;
    uint256 public gamma_y2;
    uint256 public delta_x1;
    uint256 public delta_x2;
    uint256 public delta_y2;
    
    // IC 和 B 係數（用於驗證 public inputs）
    uint256[] public IC;  // 公開輸入的線性組合係數
    uint256[] public B;   // 驗證金鑰的另一部分
    
    // 配對合約介面
    PairingInterface public pairingContract;
    
    constructor(
        uint256[2] memory _vk_alpha,      // [alpha_x, alpha_y]
        uint256[4] memory _vk_beta,       // [beta_x1, beta_x2, beta_y1, beta_y2]
        uint256[4] memory _vk_gamma,      // [gamma_x1, gamma_x2, gamma_y1, gamma_y2]
        uint256[4] memory _vk_delta,      // [delta_x1, delta_x2, delta_y1, delta_y2]
        uint256[] memory _IC,
        uint256[] memory _B,
        address _pairingContract
    ) {
        alpha_x = _vk_alpha[0];
        alpha_y = _vk_alpha[1];
        beta_x1 = _vk_beta[0];
        beta_x2 = _vk_beta[1];
        beta_y2 = _vk_beta[2];  // 注意：beta_y 有兩個部分
        gamma_x1 = _vk_gamma[0];
        gamma_x2 = _vk_gamma[1];
        gamma_y2 = _vk_gamma[2];
        delta_x1 = _vk_delta[0];
        delta_x2 = _vk_delta[1];
        delta_y2 = _vk_delta[2];
        
        IC = _IC;
        B = _B;
        pairingContract = PairingInterface(_pairingContract);
    }
    
    /**
     * @notice 驗證 Groth16 證明
     * @param a 證明 A 座標 [a_x, a_y]
     * @param b 證明 B 座標 [b_x0, b_x1, b_y0, b_y1]（G2 點）
     * @param c 證明 C 座標 [c_x, c_y]
     * @param input 公開輸入
     */
    function verifyProof(
        uint256[2] memory a,
        uint256[4] memory b,
        uint256[2] memory c,
        uint256[] memory input
    ) public view returns (bool) {
        // 驗證公開輸入的數量
        require(input.length + 1 == IC.length, "Invalid input length");
        
        // 計算 -γ 和 -δ（用於配對）
        uint256 neg_gamma_x = p - gamma_x1;
        uint256 neg_delta_x = p - delta_x1;
        
        // 計算輸入線性組合
        uint256 input_linear_combination_x = IC[0];
        uint256 input_linear_combination_y = IC[1];
        
        for (uint i = 0; i < input.length; i++) {
            input_linear_combination_x += IC[i + 2] * input[i];
            input_linear_combination_y += IC[i + 3] * input[i];
        }
        
        // 配對驗證
        // e(A, B) = e(α, β) * e(Σ IC_i * input_i, γ) * e(C, δ)
        uint256[24] memory inputArray = [
            // e(A, B)
            a[0], a[1], b[0], b[1], b[2], b[3],
            // e(-α, β)
            p - alpha_x, p - alpha_y, beta_x1, beta_x2, beta_y2, 1,
            // e(Σ IC_i * input_i, -γ)
            input_linear_combination_x, input_linear_combination_y,
            neg_gamma_x, gamma_x2, gamma_y2, 1,
            // e(C, -δ)
            c[0], c[1], neg_delta_x, delta_x2, delta_y2, 1
        ];
        
        return pairingContract.pairing(inputArray);
    }
}

/**
 * @title PairingInterface
 * @notice BN128 配對驗證介面
 */
interface PairingInterface {
    function pairing(uint256[24] memory input) external view returns (bool);
}

8.2 估算驗證 Gas 成本

以太坊上驗證 ZK 證明的 Gas 成本取決於演算法和電路規模：

實際成本需要根據具體電路和工具鏈生成後測量。

結語

零知識證明的數學可不是鬧著玩的。從橢圓曲線到多項式承諾，從 R1CS 到 QAP，從 KZG 到 FRI——每一層都有它存在的理由。

但我覺得，最重要的不是記住所有公式，而是理解這些技術為什麼這樣設計：

• 橢圓曲線：用離散對數問題提供計算安全性
• 算術電路：把任意計算轉換成統一的約束格式
• 多項式承諾：在不透露秘密的情況下「承諾」多項式
• FRI：用少量查詢驗證整個多項式的結構
• 配對：把多個約束檢查合併成一個優雅的等式

搞懂了這些，你就從「會用 ZK 庫」升級到了「理解 ZK 系統」。這個差距，在 debug 和安全審計時可是天壤之別。

參考資料

一級來源（以太坊官方）：

• Ethereum ZK-SNARKs Documentation: https://ethereum.org/developers/docs/zksnarks
• Ethereum ZK-STARKs Documentation: https://ethereum.org/developers/docs/zkstarks

二級來源（重要技術文檔）：

• Plonky3 Implementation: https://github.com/Plonky3/Plonky3
• AZTEC Network Documentation: https://docs.aztec.network
• StarkWare STARK Documentation: https://starkware.co/stark/

三級來源（知名開發者觀點）：

• Vitalik Buterin - ZK-SNARKs: Into the Weeds
• Vitalik Buterin - An approximate introduction to STARKs
• Eli Ben-Sasson - STARKs and their applications

COMMIT: Add ZK-SNARK/STARK mathematical derivation with interactive examples