zk-SNARK：簡潔的證明與可信設定

上一篇把我們留在的那道牆前

上一篇我們把一段運算攤平成一個算術電路，再化為一個 R1CS：一串扁平的乘法約束，由一個祕密的見證（witness）去滿足。我們一路用的小例子是「在不洩漏的前提下，證明你知道 15 的兩個因數」——只有一條約束 `p * q = 15`，而見證就是那一對 `(p, q)`。

那個誠實但天真的證明，其實就是一句「這是我的見證，你自己驗」。它一次踩中兩個地雷：它洩漏了祕密，零知識蕩然無存；而且驗證者必須把每一條約束重跑一遍，毫無節省可言——電路若有十億個閘，驗證者就得做十億次乘法。zk-SNARK 正是這個極端的完全相反面。

逐字拆解這個縮寫

Succinct（簡潔）——證明極小、驗證極快，其大小與時間相對於運算規模是次線性的（通常根本與規模無關）。一個 Groth16 證明永遠是三個群元素，不管電路有一千條還是十億條約束。
Non-interactive（非互動式）——證明者只送出「一則」訊息，沒有來回挑戰的回合。任何人、任何時候都能驗證同一個證明——這正是把它貼上區塊鏈所必需的特性。
ARgument（論證）——它是「計算上」健全，而非無條件健全。一個「證明（proof）」能擋住連算力無限的作弊者；一個「論證（argument）」只擋得住受真實算力限制的作弊者，因為它的健全性是建立在像離散對數這種困難假設之上。
of Knowledge（知識）——證明者不只是顯示某命題為真，更證明它確實「持有」一份見證。這由一個萃取器（extractor）在數學上定義：一台假想的機器，能從任何說服了驗證者的證明者身上，把那份見證反推出來。

其中兩項我們已經有工具。我們用第 1 篇的 Fiat–Shamir 啟發法把證明變成非互動式：把驗證者擲硬幣的挑戰，換成「到目前為止的對話內容」的雜湊，讓證明者自己產生挑戰，卻又無法藉此作弊。真正全新的機械——簡潔性——則來自一段繞經多項式的優美路徑。

把一堆約束化成一條多項式

讓 SNARK 變簡潔的關鍵一躍是：別再一條一條檢查約束，而是把它們全部一次性化成一條多項式恆等式來檢查。 能做到這件事的 R1CS 重新編碼，就叫做二次算術程式（QAP）。

其構造如下：挑 `m` 個相異的點 `r_1 … r_m`，每條約束對應一個，並對每個變數內插出一組多項式，使得在 `r_i` 求值就重現第 `i` 條約束。把它們與見證綑成 `A(x)`、`B(x)`、`C(x)`。於是整句「我的見證滿足全部 m 條約束」就濃縮成一句話：`A(x)·B(x) − C(x)` 在每個 `r_i` 都為零，因此能被消失多項式 `Z(x) = Π(x − r_i)` 整除。也就是說，存在一個商式 `H(x)`，使得 `A·B − C = H·Z`。

# R1CS: for each constraint i,   (A_i . z) * (B_i . z) = (C_i . z)
#   z is the witness vector (the secret inputs plus the constant 1).
#
# Step 1: pick m distinct points r_1 .. r_m, one per constraint.
# Step 2: for each variable j, interpolate column polynomials
#         A_j, B_j, C_j  so that  A_j(r_i) = A[i][j],  etc.

A(x) = sum_j  z_j * A_j(x)
B(x) = sum_j  z_j * B_j(x)
C(x) = sum_j  z_j * C_j(x)
Z(x) = (x - r_1)(x - r_2) ... (x - r_m)        # the "vanishing" polynomial

# z is a valid witness  <=>  A(x)*B(x) - C(x) vanishes at every r_i
#                       <=>  it is divisible by Z(x):
#
#         A(x) * B(x) - C(x)  =  H(x) * Z(x)
#
# The prover commits to A, B, C, H. The verifier picks ONE random s and checks
#
#         A(s) * B(s) - C(s)  ==  H(s) * Z(s)
#
# Schwartz-Zippel: if the identity is false, this passes with prob <= deg/|F|.

R1CS 化為 QAP：「見證是否滿足」的檢驗，變成一條多項式可整除性的檢查。

為什麼只在「一個」隨機點檢查就夠了？這要靠 Schwartz–Zippel 引理：兩個相異的 `d` 次多項式，最多在 `d` 個點上取值相同。所以當驗證者隨機挑一個 `s`，並發現 `A(s)B(s) − C(s) = H(s)Z(s)` 成立時，一個作弊的證明者——它的多項式其實並不滿足恆等式——能矇混過關的機率最多只有 `d/|F|`。在一個約有 `2^254` 個元素的體上，這小到天文等級。數百萬條約束，就此塌縮成「在單一隨機點求幾個多項式的值」。

多項式承諾：KZG 這套魔術

這個抽點檢查有個陷阱。驗證者不能就這麼看見證明者的多項式：它們編碼了祕密見證，而且龐大無比。所以證明者得做兩件事。第一，在得知 `s` 之前就把多項式鎖死，事後無法偷偷更動。第二，只揭露它們在 `s` 的值，並附上一份證明這個值誠實無欺。同時辦到這兩件事的原語，就是多項式承諾——一種專為多項式打造的承諾方案。

主力是 KZG（Kate–Zaverucha–Goldberg，2010）。它用一條結構化參考字串 `{[τ⁰], [τ¹], …, [τ^d]}`——一串對應某祕密純量 `τ` 的橢圓曲線點——把一個多項式 `p` 的承諾濃縮成單一個點 `C = [p(τ)]`。而「`p(a) = v`」的開啟證明，同樣只是單一個點：`π = [q(τ)]`，其中 `q(x) = (p(x) − v)/(x − a)`——這是一次整除，因為 `a` 是 `p(x) − v` 的根。驗證者接著只需檢查一條雙線性配對方程式。

# --- Trusted setup: run ONCE, then the secret tau MUST be destroyed ---
SRS_G1 = [ G1 * tau^i  for i in 0 .. d ]   # d+1 elliptic-curve points
SRS_G2 = [ G2, G2 * tau ]                  # two points for the pairing check

# --- Commit to p(x) = p_0 + p_1 x + ... + p_d x^d ---
def commit(p):
    # = G1 * p(tau), but computable WITHOUT knowing tau, straight from the SRS
    return sum(p[i] * SRS_G1[i] for i in range(len(p)))   # one G1 point

# --- Prove that p(a) = v ---
def open(p, a):
    v = eval(p, a)
    q = poly_div(p - v, x - a)     # exact division: a is a root of p(x) - v
    return v, commit(q)            # the value plus ONE G1 proof point pi

# --- Verify the opening with a single bilinear pairing equation ---
def verify(C, a, v, pi):
    #  e( C - v*G1 , G2 )  ==  e( pi , SRS_G2[1] - a*G2 )
    #  holds because   p(tau) - v  ==  q(tau) * (tau - a)
    return pairing(C - v*G1, G2) == pairing(pi, SRS_G2[1] - a*G2)

KZG 四個動作：承諾、開啟、驗證——每一個都只是單一個群元素，與多項式的次數無關。

好好體會這有多驚人：一個任意次數的多項式，被一個約 48 位元組的點釘死；它的任意一個求值，再用一個點就證明完畢。「綁定性」——也就是你無法把同一個承諾開成兩種不同結果——靠的是一個離散對數型的困難假設。正是這個常數大小的承諾—開啟，才讓整個證明維持常數大小，無論它背後的運算有多浩瀚。

可信設定，與那桶有毒廢料

再死盯著那條參考字串看一次：那些點是某祕密純量 `τ` 的各次冪。一定有人選定了 `τ` 才能造出它們。危險就在這——只要還有誰知道 `τ`，就能偽造。知道 `τ`，他就能為一個根本錯誤的值 `v` 兜出一個看起來合法的開啟 `π`，因為這個祕密給了他一條繞過代數的捷徑。他能證明一個假命題。這桶殘留的祕密，就是可信設定裡的有毒廢料，字串一造好就必須立刻銷毀。

這種偽造破壞的是健全性——它讓你鑄造偽造的證明，例如憑空變出屏蔽幣——但值得注意的是，它不會破壞零知識。然而依舊是災難性的。解法是：絕不讓任何單一個人握有 `τ`。一場冪次儀式（powers of tau）就是一個多方計算：每位參與者摻入自己全新的祕密隨機值，把字串傳下去，再刪掉自己的那一份。最終的 `τ` 是所有人貢獻的乘積，而只要至少有一位參與者誠實地丟掉了自己那份，這個設定就是安全的。這就是著名的 N 取 1（1-of-N） 信任假設。

Zcash 為它的屏蔽 SNARK 參數舉辦過多方儀式——2016 年初版啟動有 6 位參與者，2018 年 Sapling 升級時則跑了規模大得多的冪次儀式。每一場都在防範任何單一方私藏有毒廢料。
以太坊的 KZG 召喚儀式，為 EIP-4844（proto-danksharding）升級而辦，吸引了超過 14 萬筆貢獻——史上規模最大的可信設定。在 14 萬人之中，「至少有一人誠實刪除了自己那份」這個賭注，安全到壓倒性的程度。
逐電路 vs 通用 是關鍵分野。有些系統每一個電路都得跑一場全新的儀式；有些則只跑一場，就能服務所有在某個規模上限以內的電路。光是這個抉擇，就決定了下一節的比較。

Groth16、PLONK，與誠實的取捨

你會不斷遇到兩套系統。Groth16（Jens Groth，2016）是大小冠軍：證明只有三個群元素——區區幾百位元組——用幾次配對就能驗證，便宜到能透過 `alt_bn128` 預編譯合約在以太坊合約內部跑。它的代價是：一份全新、逐電路專屬的可信設定。電路裡改動一個閘，你就得重跑一整場儀式。

PLONK（2019）拿一點點證明大小，換來一個通用、可更新的設定：一條冪次儀式字串就能服務每一個在規模上限以內的電路，而且它直接建立在 KZG 之上。PLONK 式的算術化還解鎖了自訂閘與查表論證（lookup arguments），這也是為什麼大多數現代 zkEVM 與通用證明堆疊，血脈承自 PLONK 而非 Groth16。

// A Groth16 verifier on Ethereum (shape generated by snarkjs), trimmed.
// The whole proof is THREE group elements: a (G1), b (G2), c (G1).
function verifyProof(
    uint[2]    calldata a,        // proof element A  in G1
    uint[2][2] calldata b,        // proof element B  in G2
    uint[2]    calldata c,        // proof element C  in G1
    uint[]     calldata input     // the public inputs
) public view returns (bool) {
    // Rebuild vk_x from the public inputs and the embedded verification key:
    //     vk_x = IC[0] + sum_i input[i] * IC[i+1]
    // Then ONE pairing-product check (4 pairings via the alt_bn128 precompile):
    //     e(-A, B) * e(alpha, beta) * e(vk_x, gamma) * e(C, delta) == 1
    // Constant gas, whether the circuit had 1e3 or 1e9 constraints.
    return pairingCheck(a, b, c, vk_x);
}

一個活在鏈上的 Groth16 驗證器：三個小輸入、一次常數 gas 的配對檢查——把「簡潔」具體化成程式碼。

現在來談誠實的極限。(1) 不抗量子： KZG 與 Groth16 建立在橢圓曲線與配對假設之上，一台夠大的量子電腦能將其攻破——對照下一篇的 zk-STARK，後者只仰賴雜湊函數。(2) 可信設定是真實存在的： 儀式只能削弱，無法消除。(3) 產生證明很沉重： 證明者要跑龐大的 FFT 與多純量乘法，成本常是「單純把運算跑一遍」的數百到數千倍。簡潔性的代價，完全由證明者這一側承擔——而正是這份不對稱，讓 SNARK 完美契合區塊鏈：在鏈下昂貴地證明一次；在鏈上廉價地、永遠地驗證。