從黑暗中的儀式，到陽光下的證明
上一份指南裡，你看到了 zk-SNARK 的魔法從何而來：它把一個 約束系統 摺成多項式，再用 KZG 承諾 對它做承諾。但那個承諾是有代價的——它需要一段在 可信設定 中烘焙出來的「結構化參考字串」。回想一下 powers-of-tau 儀式：數十人各自摻入一個祕密，只要其中有一個人誠實地銷毀了自己的碎片，系統就安全。那段殘留的祕密叫做「有毒廢料」，一旦攻擊者把它重建出來，就能偽造出能完美通過驗證的假命題證明。你永遠無法證明廢料被銷毀了——你只能選擇相信。
zk-STARK 正是對一個簡單卻頑固的問題的回答：要是我們根本不需要任何儀式呢？ 這個縮寫代表 Scalable Transparent ARgument of Knowledge（可擴展、透明的知識論證）。透明是重點：沒有祕密設定、沒有有毒廢料，只有任何人都能重新推導的公開隨機性。可擴展意味著證明者以接近線性的時間運行，而驗證者所需的時間僅隨運算規模呈對數多項式增長。這套構造由 Eli Ben-Sasson 等人於 2018 年提出，只仰賴一樣你早已信任的密碼學原料：一個抗碰撞的 雜湊函數。
一段運算就是一張表：執行軌跡與 AIR
SNARK 會把程式攤平成一個 算術電路，再化為 R1CS。STARK 採取的觀點不同，而且很「具體」：把這段運算寫成一張在有限體上的數字表格，其中每一列是機器的一個步驟、每一欄是一個暫存器。這張表格就是執行軌跡（execution trace）。當初構成你 R1CS 見證值 的那些祕密輸入，如今就住在這張軌跡裡。
取代 R1CS 的是 AIR——代數中介表示（Algebraic Intermediate Representation）。它不是每個閘一條方程式，而是給你兩種規則：轉移約束，規定每一對相鄰的列都必須滿足（一步如何由上一步推出）；以及邊界約束，釘死特定的格子（也就是輸入與所宣稱的輸出）。拿一個迷你的費氏數列運算來說，它的軌跡只有一欄，而連結三個連續列的那條規則，就是整支程式：
row | a AIR for Fibonacci over a finite field F_p
----+----- ------------------------------------------
0 | 1 boundary: a[0] = 1 , a[1] = 1
1 | 1 transition: a[i+2] - a[i+1] - a[i] = 0 (for all i)
2 | 2 boundary: a[7] = 21 (the claimed result)
3 | 3
4 | 5 # 1) interpolate the column into a polynomial f(x)
5 | 8 # over a domain D = {g^0, g^1, ..., g^7}, g a root of unity
6 | 13 # 2) the transition rule becomes ONE polynomial identity:
7 | 21 # C(x) = f(g^2 . x) - f(g . x) - f(x)
# C(x) must be ZERO on every trace point => divisible by
# the vanishing polynomial Z(x) = x^8 - 1
# 3) prover computes the quotient q(x) = C(x) / Z(x)
# if q(x) is a genuine low-degree polynomial, the trace was valid這正是接下來整個協定運轉的樞紐。「運算是否正確執行了？」已經變成了「這個商式多項式真的是低次數的嗎？」證明者會把每個軌跡多項式延展到一個遠大於軌跡本身的定義域上——這叫做 Reed–Solomon 低次延展，通常是軌跡長度的 4 到 16 倍（即膨脹因子）。在那個大定義域上，一個真正 `d` 次的多項式與一個偽造的高次冒牌貨幾乎處處不相等，因此只要隨機抽查幾個點，就能把兩者分辨開來。所有 STARK 的健全性，最終都歸結到同一個子問題：證明某個函數很接近一個低次數的多項式。
用雜湊而非配對來承諾
這裡是 STARK 與 SNARK 在最深層分道揚鑣之處。SNARK 用像 KZG 這樣的 多項式承諾 對多項式做承諾——一個橢圓曲線群元素、以常數大小開啟，但它建立在配對代數以及那個有毒廢料設定之上。STARK 全盤拒絕這一切。要對一個多項式做承諾，證明者只是單純地在整個大定義域上對它求值，再把這串求值結果做成一棵 Merkle 樹並雜湊起來。
那個 Merkle 根 本身就是承諾。要在驗證者所選的某個點「開啟」這個多項式，證明者揭露該求值，外加它 Merkle 路徑上的 `log(n)` 個兄弟雜湊；驗證者一路向上重新雜湊到根，確認這個值是事先就被釘死、從未被改動。其綁定性完全來自 抗碰撞性——如果證明者能找到兩串不同的求值表卻雜湊出同一個根，他就能作弊；但找到一個雜湊碰撞，正是我們所相信「辦不到」的事。
FRI：如何證明一個多項式是低次數的
現在一切都繫於一個測試：給定一串已用 Merkle 承諾的求值，要在不送出整個多項式的前提下，說服驗證者它們確實來自一個低次數的多項式。完成這件事的引擎是 FRI：Fast Reed–Solomon Interactive Oracle Proof of Proximity（快速 Reed–Solomon 鄰近性互動式預言機證明）。它的核心是透過折疊來遞迴：把次數對半砍，一輪接著一輪，直到剩下的東西小到證明者可以直接整個送出去。
把任意多項式拆成它的偶次半與奇次半：`f(x) = f_even(x²) + x·f_odd(x²)`。每一半的次數都減半。驗證者送出一個隨機挑戰 `β`，證明者則對折疊後的多項式 `f'(y) = f_even(y) + β·f_odd(y)` 做承諾，它定義在大小減半的定義域上。最美的地方在於：你可以從 `x` 與 `−x` 兩處的求值還原出那兩個半邊，因此驗證者稍後能用很便宜的算術檢查這次折疊有沒有誠實完成。
FRI, in two phases
===================
COMMIT phase (log(d) rounds, halving the degree each time)
layer 0: f0 = the polynomial we want to prove is low-degree
repeat until the polynomial is a constant:
verifier (Fiat-Shamir) sends random beta_k
f_{k+1}(y) = f_even(y) + beta_k * f_odd(y) # degree halved
prover Merkle-commits f_{k+1} over the half-size domain
finally: prover sends the tiny final polynomial in the clear
QUERY phase (repeat ~tens of times for soundness)
verifier picks a random point x in the layer-0 domain
for each layer k, prover opens (Merkle paths) the values at x and -x
verifier checks the FOLDING relation links the two layers:
f_{k+1}(x^2) ?= f_even(x^2) + beta_k * f_odd(x^2)
where f_even = (f_k(x)+f_k(-x))/2 , f_odd = (f_k(x)-f_k(-x))/(2x)
ACCEPT only if every layer is consistent AND the final value matches這為什麼健全？如果證明者一開始用的函數遠離任何低次數多項式，這份「距離」會在折疊中存活下來——折疊後的函數一輪又一輪地依然遠離低次數。於是至少有一層在很大一部分的點上是不一致的，而查詢階段中每一次隨機抽查，都以一個固定的機率逮到這個謊言。跑個大約 30 到 80 次查詢（確切次數會依膨脹因子調校），作弊成功的機率就會掉到 `2⁻¹⁰⁰` 以下。對誠實的證明者而言幾乎不花成本；偽造的證明則以壓倒性的機率被揪出。這就是這筆交易的全部——而且完全用雜湊支付。
非互動，以及為什麼量子電腦幫不上忙
上面描述的 FRI 是互動式的——驗證者不斷送出新鮮的隨機 `β` 與查詢點。要把 STARK 放上區塊鏈，我們需要它是非互動的：一份自給自足的證明，不需要在線上的驗證者。解法就是直覺篇裡那一招——Fiat–Shamir 啟發法。凡是原本驗證者該擲硬幣的地方，改由證明者雜湊目前為止的整段紀錄來推導出那份隨機性。由於這些挑戰被釘死在所有已承諾的內容上，證明者無法為自己的利益反覆嘗試湊數——在隨機預言機模型下，雜湊的行為就像一枚誠實、無法預測的硬幣。
現在來誠實地談那個抗量子的主張。像 Groth16 這樣基於配對的 SNARK，或基於 KZG 的 PLONK，把健全性建立在橢圓曲線群中離散對數的困難性之上。Shor 演算法能在大型量子電腦上以多項式時間求解離散對數與因式分解——因此一台具密碼學意義的量子機器，會直接攻破這些 SNARK 的設定，讓攻擊者得以偽造證明。STARK 則沒有任何離散對數假設可破。它唯一的假設是 雜湊函數 抗碰撞、且行為像一個隨機預言機。
面對雜湊，量子電腦能提供的最佳手段只是 Grover 演算法——一個對無結構搜尋僅僅平方級的加速；它能以約 `2^(n/2)` 的工作量找到一個原像，而非 `2^n`。防禦之道很簡單：把輸出長度加倍。一個 256 位元的雜湊，即便面對 Grover 也保有大約 128 位元的安全性——這正是讓基於雜湊的簽章成為抗量子旗艦原語的同一套邏輯。所以 STARK 是有望抗量子的：不是因為有人證明了量子電腦無能為力，而是因為它建立在那一個量子電腦幾乎撼動不了的假設上。
SNARK 對上 STARK：一張誠實的計分卡
天下沒有白吃的午餐，STARK 為透明性付出的代價是位元組。一份 Groth16 證明約 200 位元組，以三次配對在常數時間內完成驗證——在鏈上無人能敵。一份 STARK 證明則攜帶數千個雜湊開啟：實際上是數十到數百 KB。驗證者的工作量是運算規模的對數多項式，這很出色，但也意味著數萬次雜湊運算——在筆電上很便宜，換算成以太坊的原始 gas 卻很貴。把這筆交易攤開來看：
zk-SNARK (Groth16 / KZG-PLONK) zk-STARK (FRI)
----------------- ------------------------------ --------------------
Trusted setup YES - per-circuit or universal NO - fully transparent
ceremony; toxic waste risk (public randomness)
Proof size ~200 B (Groth16) ~tens-hundreds of KB
~0.5 KB (PLONK)
Verify cost constant, ~3 pairings (cheap polylog, many hashes
on-chain) (heavier on-chain)
Prover speed slower, heavy FFT + MSM faster, hashing-bound,
scales near-linearly
Crypto assumption elliptic-curve / pairing collision-resistant
discrete-log hash + random oracle
Quantum threat BROKEN by Shor (discrete log) only Grover (quadratic)
=> plausibly post-quantum業界最愛的一招直接抹平了這個兩難：用 STARK 來證明，再把 STARK 證明包進一個小小的 SNARK 裡。沉重的運算交給 STARK 那透明、快速、可擴展的證明者，最後一份 Groth16 證明則證實「我正確地驗證了那份 STARK」，把鏈上的足跡縮回約 200 位元組。這就是 證明遞迴 的實際運用，也正是 Polygon zkEVM、RISC Zero 之類系統能把一份微小證明貼上以太坊、同時保有透明骨幹的方法。那層包裝只為最末端那一薄層重新引入了可信設定。
STARK 的實戰，與前方的路
STARK 不是白板上的點子——它今天就在結算真實的價值。StarkWare 的 StarkEx 已為 dYdX、Sorare 與 Immutable 證明了數千億美元的交易；StarkNet 是一條通用型 zk-rollup，其合約以 Cairo 撰寫——一種被設計成「執行軌跡天生就可被 STARK 證明」的語言。Polygon Miden、RISC Zero（證明一支 RISC-V 程式被正確執行），以及 Plonky2/Plonky3（一套以 FRI 為基礎、把 PLONK 式算術化與 STARK 承諾融合在一起的系統），全都建立在這同一個只用雜湊的基礎上。
上述每一個系統都產出一份 有效性證明：相對於樂觀 rollup 假定批次誠實、再等上一週讓人挑戰，STARK rollup 在結算之前就證明了它的批次正確，因此一旦證明通過驗證，資金即可立刻離場。如今的前沿在於把證明者做得愈來愈便宜——在迷你的 Mersenne-31 體上的 Circle STARK、硬體加速，以及深度遞迴——並朝著一個能逐一操作碼證明真實以太坊執行的完整 zkEVM 推進。