zkSNARK 數學原理完整推導指南：從零知識證明到實際應用

概述

零知識證明（Zero-Knowledge Proof，ZKP）是現代密碼學中最重要的突破之一，而 zkSNARK（Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge）則是這一領域最廣泛應用的技術實現。zkSNARK 允許一方（證明者）向另一方（驗證者）證明某個陳述為真，同時不透露任何除「陳述為真」之外的額外資訊。這種技術在區塊鏈領域具有革命性意義，它使得隱私保護、擴容和互操作性等關鍵問題得以解決。

本文從數學角度深入剖析 zkSNARK 的技術原理，假設讀者具備基本的抽象代數和密碼學知識。我們將從零知識證明的定義出發，逐步推導 zkSNARK 的核心數學構建，包括多項式承諾、橢圓曲線密碼學、QAP 轉換、以及最終的簡潔非互動式證明建構。透過完整的數學推導，讀者將能夠理解為何 zkSNARK 能夠實現「簡潔」和「非互動」這兩個關鍵特性，以及這些特性如何在實際應用中發揮作用。

第一章：零知識證明的數學基礎

1.1 零知識證明的形式化定義

零知識證明的概念最初由 Goldwasser、Micali 和 Rackoff 於 1985 年提出。在形式化定義中，一個零知識證明系統包含三個核心角色：證明者（Prover）、驗證者（Verifier）和抽取器（Extractor）。設 P 為證明者，V 為驗證者，x 為公共輸入，w 為見證人（私密輸入）。若存在一個關係 R，使得 (x, w) ∈ R，則證明者需要向驗證者證明「我知道 w 使得 R(x, w) 為真」。

零知識證明系統必須滿足三個核心屬性：

Completeness（ Completeness）：如果 (x, w) ∈ R，那麼誠實的證明者總是能夠說服誠實的驗證者接受證明。形式化表示為：若 P 知道見證人 w，則 Pr[V(x) accepts] = 1。

Soundness（可靠性）：如果 (x, w) ∉ R，那麼任何作弊的證明者都無法說服驗證者接受假的陳述。形式化表示為：若 P 不知道見證人，則 Pr[V(x) accepts] < ε，其中 ε 稱為 soundness error。

Zero-Knowledge（零知識性）：驗證者在與證明者交互的過程中，無法獲得任何關於見證人 w 的額外資訊。形式化定義需要引入模擬器的概念：存在一個模擬器 S，在不知道 w 的情況下，能夠生成與真實交互不可區分的輸出。

1.2 交互式與非互動式證明

早期的零知識證明都是交互式的，需要證明者和驗證者進行多輪通信。這種模式在許多應用場景中並不實用，特別是在區塊鏈環境中。區塊鏈的本質是無需信任的環境，無法依賴長時間的交互過程。

非互動式零知識證明（Non-Interactive Zero-Knowledge，NIZK）的突破在於：證明者只需要發送一條消息，驗證者就能夠驗證證明的正確性。Fiat-Shamir 啟發式轉換是實現 NIZK 的關鍵技術，它利用哈希函數將交互式協議轉換為非互動式協議。

具體而言，在交互式協議中，驗證者發送隨機挑戰 c。證明者計算回應 r 並發送給驗證者。在 Fiat-Shamir 轉換中，證明者自己計算 c = H(x, commit)，其中 H 是密碼學哈希函數，commit 是證明者的初始承諾。這種轉換的有效性基於隨機 oracle 模型，假設哈希函數的輸出是真正隨機的。

zkSNARK 正是 NIZK 的一種特殊形式，其特點是「Succinct」——證明非常簡短，通常只有幾百到幾千位元組，且驗證速度極快。

1.3 密碼學假設

zkSNARK 的安全性基於幾個關鍵的密碼學假設。這些假設雖然尚未被數學證明，但經過數十年的密碼學研究，被認為在計算上是安全的。

離散對數假設（Discrete Logarithm Assumption, DLA）：給定生成元 g 和值 g^a，計算 a 在計算上是困難的。這是橢圓曲線密碼學的基礎。

Decision Diffie-Hellman 假設（DDH）：給定 (g, g^a, g^b, g^c)，區分 (g, g^a, g^b, g^ab) 和 (g, g^a, g^b, g^c) 是困難的。

q-Strong Diffie-Hellman 假設（q-SDH）：這是 Pinocchio 和 Groth16 zkSNARK 的核心假設。

KZG 多項式承諾假設：這是現代 zkSNARK（如 PLONK、Marlin）採用的多項式承諾方案的安全性基礎。

第二章：代數背景知識

2.1 橢圓曲線密碼學

橢圓曲線密碼學（Elliptic Curve Cryptography，ECC）是 zkSNARK 的核心密碼學基礎。橢圓曲線是滿足特定方程式的點的集合，定義在有限域上。

在 zkSNARK 中，我們通常使用配對友好的橢圓曲線。配對（Pairing）是橢圓曲線上的一種雙線性映射，允許我們在不同的群組之間進行乘法運算。

設 E 為一條橢圓曲線，定義在有限域 Fp 上，其中 p 是大質數。曲線上的點構成一個阿貝爾群，記為 E(Fp)。我們通常使用巴豆豆曲線（Barreto-Naehrig curves），如 BN128，其方程式為：

y^2 = x^3 + 1

在 BN128 上，定義兩個循環群 G1 和 G2，以及一個配對 e: G1 × G2 → G_T。配對的雙線性性質是：

e(a·P, b·Q) = e(P, Q)^(ab) = e(b·P, a·Q)

這個性質對於構建零知識證明至關重要，它允許我們驗證多項式約束而無需透露實際的多項式值。

2.2 雙線性對

配對是 zkSNARK 最關鍵的密碼學工具之一。令 G1、G2 和 GT 為三個相同素數階 p 的循環群。雙線性對 e: G1 × G2 → GT 滿足：

1. 雙線性：對於所有 a, b ∈ Z_p 和 P ∈ G1, Q ∈ G2，有 e(aP, bQ) = e(P, Q)^(ab)
2. 非退化性：如果 P 是 G1 的生成元，Q 是 G2 的生成元，則 e(P, Q) ≠ 1

在 zkSNARK 中，我們通常使用 Ate 配對或最佳配對（Optimal Ate Pairing）。這些配對在某些特定曲線上具有高效的計算複雜度。

配對的主要用途包括：

• 多項式驗證：驗證者可以檢查某個多項式在特定點的評価是否正確，而無需知道整個多項式
• 範圍證明：驗證某個值在特定範圍內
• 聚合簽名：將多個簽名聚合為單一簽名

2.3 多項式與多項式承諾

多項式是 zkSNARK 的核心表達工具。透過將計算問題轉化為多項式約束問題，我們可以利用多項式的代數性質來構建高效的零知識證明。

一個 d 次多項式可以表示為：

f(x) = a_0 + a_1·x + a_2·x² + ... + a_d·x^d

多項式承諾（Polynomial Commitment）允許證明者對一個多項式產生「承諾」，這個承諾就像是一個密封的信封，一旦承諾產生，就無法改變多項式的係數。此後，證明者可以「打開」多項式在特定點的取值，證明 f(s) = y，而不透露其他任何關於多項式的資訊。

KZG（Kate-Zaverucha-Goldberg）承諾是 zkSNARK 中最常用的多項式承諾方案。其核心思想是：

1. 設置階段：選擇一個秘密值 s（稱為「陷阱門」或「toxic waste」），計算並公開 s 的幂的承諾
2. 承諾：對多項式 f(x) = Σ ai x^i，計算 C = Σ ai · gi，其中 gi 是預先計算的群的元素
3. 開啟：證明者計算證明 π，使得驗證者可以驗證 f(s) = y

KZG 承諾的關鍵優勢在於其簡潔性：承諾是一個群元素，證明也是一個群元素，且驗證只需要一次配對運算。

第三章：電路到多項式的轉換

3.1 算術電路的表示

任何計算都可以表示為算術電路。算術電路由加法門和乘法門組成，輸入和輸出都是有限域的元素。這種表示方法使得我們可以將任意計算問題轉化為代數問題。

例如，考慮計算 z = (x + y) × (x - y)。這可以表示為：

a = x + y
b = x - y
z = a × b

這形成了一個簡單的算術電路，包含兩個加法門和一個乘法門。

3.2 R1CS 約束系統

Rank-1 Constraint System（R1CS）是一種標準化的電路表示方法。在 R1CS 中，每個約束是以下形式的三元組：

⟨a, s⟩ · ⟨b, s⟩ = ⟨c, s⟩

其中 a、b、c 是向量，s 是所有電路變數的向量（包括輸入、輸出和中間變數），⟨·, ·⟩ 表示內積。

以簡單的乘法閘為例：假設我們要計算 z = x × y。令 s = [one, x, y, z, ...]，則約束可以寫為：

a = [0, 1, 0, 0, ...]  // 選擇 x
b = [0, 0, 1, 0, ...]  // 選擇 y
c = [0, 0, 0, 1, ...]  // 選擇 z

⟨a, s⟩ = x
⟨b, s⟩ = y
⟨c, s⟩ = z
x · y = z

任何算術電路都可以轉換為 R1CS。這種表示方法的优势在于它是标准化的，便于后续的多項式转换。

3.3 QAP 轉換

Quadratic Arithmetic Program（QAP）是將 R1CS 轉換為多項式形式的關鍵步驟。QAP 的核心思想是：將每個約束視為多項式在特定點的取值，這樣所有約束就可以用多項式相等來表達。

具體而言，設有 m 個變數和 n 個約束。對於每個約束系統中的向量 a、b、c，我們構造多項式 Ai(x)、Bi(x)、C_i(x)，使得：

• Ai(j) = ai 的第 j 個分量
• Bi(j) = bi 的第 j 個分量
• Ci(j) = ci 的第 j 個分量

這樣，整個 R1CS 約束系統就可以用以下多項式方程式表示：

A(x) · B(x) - C(x) = H(x) · Z(x)

其中 Z(x) = (x-1)(x-2)...(x-n) 是根多項式，H(x) 是商多項式。

這個轉換的意義在於：我們將「電路正確執行」的證明，轉化為「多項式在特定點相等」的證明。而多項式相等可以透過配對高效驗證。

第四章：zkSNARK 協議詳解

4.1 Trusted Setup 階段

zkSNARK 需要一個可信設置（Trusted Setup）階段。在這個階段，需要生成一個「有毒廢物」（toxic waste），即隨機數 s 和相關的承諾。這些隨機數必須在設置完成後被「遺忘」，否則攻擊者可以偽造證明。

設置階段通常分為两部分：

準備階段（ powers of tau）：這是與電路無關的階段，生成橢圓曲線點的承諾。這個輸出可以被多個電路共用。

特定電路階段：根據具體電路大小，生成最終的 CRS（Common Reference String）。

Groth16 協議的設置過程如下：

1. 選擇隨機值 α, β, δ, s ∈ F_p
2. 計算 G1 元素：g^α, g^β, g^δ, g^s^i (i = 0, ..., d)
3. 計算 G2 元素：h^β, h^δ, h^s^i (i = 0, ..., d)
4. 發布 CRS = {(g^α, g^β, g^δ), {(g^s^i)}, {(h^β, h^δ, h^s^i)}}

設置的安全性完全依賴於隨機數的銷毀。如果攻擊者知道了 s、α、β，就可以構造任何證明，這稱為「setup trapdoor」。

4.2 證明生成

給定公共輸入 x、私密見證 w 和電路，證明者需要生成一個 zkSNARK 證明。Groth16 的證明生成過程如下：

步驟 1：執行計算，計算所有中間變數的值

步驟 2：將 R1CS 約束轉換為 QAP 多項式

步驟 3：計算多項式 A(s)、B(s)、C(s)、H(s)，其中 s 是設置階段的秘密值

步驟 4：選擇隨機值 r、h，使用拉格朗日插值或其他方法計算 πa、πb、π_c

步驟 5：計算最終證明

完整的 Groth16 證明包含三個群元素：

π = (π_a, π_b, π_c) ∈ G1 × G2 × G1

其中：

• π_a = A(s) + r·α
• π_b = B(s) + h·β
• π_c = C(s) + A(s)·B(s)/δ + r·α·h + r·β·s

4.3 證明驗證

驗證者只需要公共輸入 x 和證明 π，就能夠驗證計算的正確性。驗證過程只需要一次配對運算：

e(π_a, π_b) = e(g^α, h^β) · e(g^cx, h) · e(g^cz, h)

其中 cx 和 cz 是基於公共輸入 x 計算的多項式係數。

配對運算的結果相等意味著：

A(s)·B(s) = C(s) + H(s)·Z(s)

這正是 QAP 約束的驗證。因此，驗證者可以確認證明者確實知道一個滿足電路約束的見證。

4.4 零知識性證明

為什麼 Groth16 是零知識的？關鍵在於隨機值 r 和 h 的引入。這些隨機值「遮蔽」（blind）了實際的多項式評価，使得驗證者無法從證明中恢復見證。

形式化證明需要構造一個模擬器。模擬器的工作流程：

1. 給定公共輸入 x，模擬器不知道見證 w
2. 模擬器選擇隨機值 r、h、a'、b'、c'
3. 模擬器計算證明 π' = (g^a', h^b', g^c')
4. 這個證明與真實證明是不可區分的

這個模擬器的存在正是零知識性的形式化證明。

第五章：主流 zkSNARK 協議比較

5.1 Groth16

Groth16 是最早被廣泛使用的 zkSNARK 協議，由 Jens Groth 於 2016 年提出。其特點是：

• 證明最小：只有 3 個群元素
• 驗證最快：只需要一次配對
• 電路特定：每個電路需要新的 trusted setup
• 設置複雜：需要對每個電路大小進行設置

Groth16 的應用包括 Zcash（Sprout 和 Sapling 版本）、Loopring 交易所等。

5.2 PLONK

PLONK（Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge）是由 Gabizon、Williamson 和 Ciobotaru 於 2019 年提出的。其創新點包括：

• 通用設置：只需要一個 trusted setup，適用於任何大小的電路
• 定制門：支援任意算術門
• 查找表：支援離散值查找

PLONK 的設置稱為「Ursula」，是一個多方計算過程，需要多個參與者。理論上，只要有一個誠實參與者，設置就是安全的。

5.3 STARK

STARK（Scalable Transparent Arguments of Knowledge）與 zkSNARK 有本質不同：

• 透明：不需要 trusted setup
• 後量子安全：基於哈希假設，而非橢圓曲線假設
• 可擴展性：證明大小和驗證時間隨計算複雜度呈對數增長

STARK 的缺點是證明較大（數十到數百KB），驗證時間較長。

第六章：實際應用場景

6.1 以太坊 Layer 2 擴容

zkSNARK 在以太坊 Layer 2 擴容中扮演核心角色。zkRollup 將大量交易打包成一個批次，在鏈下生成證明，然後將簡短的證明提交到以太坊主網。

以 zkSync Era 為例，其工作流程：

1. 用戶在 Layer 2 進行交易
2. 排序器將交易批次化
3. 證明者生成 zkSNARK 證明
4. 證明提交到以太坊主網
5. 合約驗證證明並更新狀態

目前主要的 zkRollup 項目包括 zkSync Era、Starknet、Polygon zkEVM、Scroll 等。

6.2 隱私保護

zkSNARK 實現了區塊鏈的隱私保護。傳統區塊鏈的所有交易都是公開的，但透過 zkSNARK，可以證明交易的合法性而不透露金額、發送方或接收方。

Zcash 是最著名的隱私幣應用。當用戶選擇「Shielded」交易時，交易詳情會被加密，只有持有 view key 的人才能查看。同時，zkSNARK 證明確保發送方確實擁有這些資金，且沒有雙重花費。

6.3 區塊鏈互操作性

zkSNARK 實現了輕客戶端驗證。傳統上，驗證另一條區塊鏈的狀態需要運行完整節點，開銷巨大。透過 zkSNARK，一條區塊鏈可以驗證另一條區塊鏈的狀態變化，而無需同步所有歷史數據。

這是跨鏈橋和區塊鏈互操作性的基礎。例如，Polygon Hermez 的 ETH 橋接就是利用 zkSNARK 實現輕客戶端驗證。

6.4 去中心化身份與認證

傳統的身份認證需要透露大量個人資訊。zkSNARK 實現了選擇性揭露（Selective Disclosure），允許用戶只透露特定屬性，而不暴露其他資訊。

例如，Age Proof 可以證明「用戶年齡大於 18」而不透露實際年齡；Residency Proof 可以證明「用戶居住在某個國家」而不透露具體地址。這種技術是去中心化身份（DID）的核心基礎。

第七章：安全性分析與風險

7.1 密碼學假設的風險

zkSNARK 的安全性完全依賴於底層密碼學假設的穩固性。隨著量子計算的發展，基於橢圓曲線的密碼學將被破解。這是 zkSNARK 面臨的長期風險。

然而，STARK 採用哈希函數作為基礎，具有後量子安全性。從長期來看，區塊鏈系統應該過渡到 STARK 或其他後量子安全的零知識證明方案。

7.2 Trusted Setup 的風險

Groth16 等協議的 trusted setup 是一個中心化風險點。如果設置過程中存在惡意參與者，他們可能竊取或濫用設置參數。

PLONK 的多方設置在一定程度上緩解了這個問題，但仍然無法完全消除風險。STARK 的透明設置（Transparent Setup）從根本上解決了這個問題，但代價是證明大小增加。

7.3 實現漏洞

密碼學協議的實現往往比理論更複雜。實際的 zkSNARK 實現中曾發現多個漏洞：

• 2019 年：Zcash Sprout 的 trusted setup 漏洞
• 2020 年：多個 zkRollup 項目的實現漏洞
• 2022 年：某些項目的隨機數生成器漏洞

嚴格的安全審計、形式化驗證和持續的安全更新是必要的。

結論

zkSNARK 代表了零知識證明技術的重大突破，其「簡潔」和「非互動」的特性使其非常適合區塊鏈應用。從數學原理來看，zkSNARK 巧妙地結合了多項式承諾、配對密碼學和 Fiat-Shamir 轉換，將任意計算問題轉化為可高效驗證的代數問題。

本文詳細推導了 zkSNARK 的核心數學原理：從零知識證明的形式化定義出發，介紹了橢圓曲線和配對的代數基礎，展示了如何將計算問題轉換為多項式約束，並詳細解釋了 Groth16 協議的完整構造。

隨著區塊鏈技術的發展，zkSNARK 和更廣義的零知識證明將在隱私保護、擴容和互操作性等方面發揮越來越重要的作用。對於區塊鏈開發者和研究者而言，深入理解這些技術的數學基礎是至關重要的。

參考文獻

• Groth, J. (2016). "On the Size of Pairing-based Non-interactive Arguments"
• Ben-Sasson, E. et al. (2018). "STARKs: Low-dependency SQL-like SNARKs"
• Gabizon, A. et al. (2019). "PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge"
• Kate, A. et al. (2010). "Constant-Size Public-Key Encryption Schemes with Efficient Encryption and Decryption"
• Goldwasser, S. et al. (1985). "The Knowledge Complexity of Interactive Proof Systems"