zk-STARK

zk-STARK（可擴展透明知識論證）是一套幾乎完全由雜湊函數搭建而成的證明系統。SNARK 仰賴橢圓曲線配對與可信設置，STARK 卻只用抗碰撞雜湊與默克爾樹，這換來兩項珍貴的性質：它是透明的（沒有處理有毒廢料的儀式——公開隨機性就夠了），而且很可能是抗量子的（量子電腦能攻破橢圓曲線假設，卻攻不破一個強健的雜湊）。所謂「可擴展」是指：證明時間隨計算規模呈準線性增長，而驗證仍維持在多對數等級。

在機制上，STARK 把計算算術化成一個 AIR（代數中間表示）：把執行軌跡排成一張表，每一列是一個機器狀態，其有效性由必須在整條軌跡上「消失（取值為零）」的多項式約束來刻畫。證明者把這些軌跡欄位做低次延伸，鋪展到一個大得多的求值域上，用一個默克爾根對它們做承諾，再用 FRI（快速 Reed-Solomon 互動式預言機鄰近性證明）證明這些約束多項式確實是低次的。FRI 是整套系統的核心：透過一連串對半折疊的隨機操作與少數幾次默克爾開封，它使驗證者相信被承諾的函數很接近一個低次多項式——而這正是一條誠實軌跡所蘊含的。

其代價是大小與成本。STARK 證明（數十到數百 KB）比只有幾百位元組的 SNARK 大，在以太坊上驗證一個 STARK 要花更多 gas，不過仍遠比重跑該計算便宜。透明、抗量子，以及沒有可信設置風險，正是 StarkWare 的 StarkEx 與 Starknet、以及 Polygon zkEVM 的部分元件，都建立在 STARK 之上的原因——而它們往往會把一個 STARK 包進最後一個小型 SNARK 裡，好把鏈上佔用縮到區區數百位元組。