證明你知道祕密，卻不把它說出來

一座山洞、一扇魔法門，與一位多疑的朋友

想像一座環形的山洞。從入口進去，先是一條通道，接著分岔成兩條走廊——就叫它們 A 路與 B 路吧——兩條走廊各自彎繞，在最深處又重新會合。會合之處立著一扇沉重的石門，而這扇門只會為唸出某個祕密咒語的人敞開。佩吉（Peggy）知道咒語，她的朋友維克多（Victor）不知道，而且他生性多疑——他想要被說服佩吉確實知道咒語，但佩吉拒絕把咒語唸出來，甚至連她用什麼把戲都不肯透露。她有沒有辦法證明自己握有一個祕密，卻不洩漏這個祕密的任何一絲一毫？答案令人驚訝：可以。

這個思想實驗出自密碼學家 Jean-Jacques Quisquater 與 Louis Guillou 之手，是通往零知識證明的大門：一套協定，讓證明者說服驗證者某個陳述為真，卻不洩漏除了「它為真」以外的任何資訊。聽起來自相矛盾，但化解之道是一個優美而簡單的遊戲。

維克多在洞外等候。佩吉走進去，在他看不見的地方隨機挑一條走廊——A 或 B——走到石門前。
接著維克多走到岔路口，喊出他要佩吉從哪一側走出來——A 或 B——這是他當場擲硬幣隨機決定的。
如果佩吉知道咒語，她就能打開石門，每一次都從維克多指定的那一側走出來。如果她不知道，她只能原路折返——除非她事先恰好猜中維克多會喊哪一邊，否則就會卡住。
他們一輪又一輪地玩下去。誠實的佩吉每一輪都會成功；虛張聲勢的人只能靠運氣過關，每輪的機率是二分之一。

這就是整個構想的縮影。請留意它的三件事，因為它們正是每一個零知識證明都必須遵守的三個承諾。

三個承諾：完備性、健全性與零知識

密碼學家用三個性質把這個山洞遊戲釘死。其中完備性與健全性合起來，才讓它成為一個證明；而第三個性質，才讓它成為零知識的。

健全性不是免費的——它是用重複換來的。單獨一輪，虛張聲勢者矇混過關的機率是 1/2。各輪彼此獨立，所以經過 n 輪後，她每一輪都騙過維克多的機率塌縮為 (1/2)^n。10 輪後大約是千分之一；20 輪後，不到百萬分之一；40 輪後，低於兆分之一。維克多想多疑，只要把 n 調高即可：健全性誤差呈指數縮小，而誠實證明者的成本只呈線性成長。

一個能證明、卻不必交出背後祕密的事實

山洞證明的是「我知道一個祕密」。第二個經典範例出自 Oded Goldreich 與 Avi Wigderson，它展示了更微妙的威力：證明一個有意義的事實，同時把使它成立的見證藏起來。假設你的朋友有紅綠色盲，而你手上有兩顆球，大小形狀完全相同，一紅一綠。在他眼中兩顆球一模一樣，他根本不信兩者有任何差別。你想說服他這兩顆球顏色不同——卻不告訴他哪顆是哪顆。

你把兩顆球交給他，一手一顆。他把雙手都藏到背後。
在背後，他依一次祕密擲硬幣的結果，決定要不要把兩手的球對調，然後把雙手伸回你看得見的地方，問：『我有沒有對調？』
因為你看得見顏色，你每次都答得出來——『有，你調了』或『沒有，你沒調』。
如果兩顆球其實同色，你根本無從分辨，只能用猜的，平均半數正確。連續許多輪都誠實答對，就會說服他這兩顆球確實不同色。

看看你的朋友最後得到了什麼。他變得確信兩顆球顏色不同——這是一個貨真價實、有用的事實——然而他對「哪顆是紅的」卻一無所知。讓這個陳述為真的東西（你能看見顏色的能力，也就是見證）從未傳遞給他。這道鴻溝——信念被轉移，見證被保留——正是零知識的全部重點。它也正是日後能讓人證明「我已滿 18 歲」或「我擁有足夠資金」，卻不必交出生日或餘額的關鍵。

模擬器：「什麼都沒洩漏」的驚人定義

你要怎麼證明一套協定什麼都沒洩漏？光靠嘴上說說可不行。密碼學家找到了一把極其巧妙的尺，叫做模擬器（simulator）。「維克多什麼都學不到」這句話被精確化成這樣：維克多在協定過程中看到的一切，他都能完全靠自己造出來，不需要佩吉，也不需要那個祕密。如果一段對話的紀錄能被一個一無所知的人偽造出來，那麼一段真實的紀錄裡就不可能含有任何知識——裡頭沒有任何東西是非得靠那個祕密才能產生的。

把它套到山洞上。想像你把佩吉連過二十輪的過程錄成影片，拿給一個陌生人看。看起來很厲害——直到你發現，就算你根本不知道咒語，也能偽造出一模一樣的影片。只要：拍佩吉走進隨機一條走廊，在維克多喊出之前偷偷告訴她他會喊哪一邊，然後只留下她選中那側恰好吻合的鏡頭，其餘剪掉就行。這捲偽造的帶子，在統計上與真實的帶子毫無二致。所以就算是真實的帶子，對第三方也什麼都證明不了：它承載的可轉移知識為零。（這也是為什麼零知識證明只能說服那位現場提供不可預測挑戰的驗證者——絕不能說服一個事後看重播的旁觀者。）

承諾、挑戰、回應：從山洞走進真實密碼學

目前為止的每個範例都遵循同一支三步舞：證明者先承諾某樣東西，驗證者拋出一個隨機挑戰，證明者再給出一個驗證者能檢查的回應。具有這種形狀的協定叫做 Sigma 協定，它們正是真實互動式證明系統的核心。想看一個用真正數學、而非山洞打造的例子，就來認識 Schnorr 協定——一種證明「你知道某把公鑰背後祕密指數」的證明，正是真實簽章機制內部的引擎。

在一個大質數階 q、生成元為 g 的循環群中運作（可以想成一條固定的橢圓曲線）。祕密是一個數 x；公開的陳述是 y = g^x。所有人都看得到 y；只有證明者知道 x，而從 y 算回 x（即離散對數）被認為是難解的，所以 y 不會把祕密洩漏給任何人。佩吉想證明她知道 x，卻不把它說出來。

# Schnorr's proof of knowledge of a discrete log
# Public:  cyclic group G of prime order q, generator g
#          statement  y = g^x   (everyone knows y; only the prover knows x)

# 1. COMMIT   -- prover picks a FRESH random r in [0, q), sends:
t = g^r

# 2. CHALLENGE -- verifier replies with a random c in [0, q):
c = random()

# 3. RESPONSE -- prover computes and sends:
s = (r + c * x) mod q

# VERIFY -- verifier accepts if and only if:
g^s  ==  t * (y^c)
#   because  g^(r + c*x) = g^r * (g^x)^c = t * y^c

Schnorr 的 Sigma 協定：一輪「承諾—挑戰—回應」即可證明知道 x，而 x 始終不被傳送。

驗證靠簡單的代數成立：g^s = g^(r + c·x) = g^r · (g^x)^c = t · y^c。完備性成立，因為誠實證明者的數字總會滿足它。這裡的健全性比山洞還要銳利：如果一個證明者能對同一個承諾 t 回答出兩個不同的挑戰 c 與 c′，那麼從兩個回應，任何人都能解出 x = (s − s′)/(c − c′)——所以任何能可靠通過的人，必定真的知道 x。這個更強的保證叫做知識證明（proof of knowledge），而把祕密拽出來的演算法就是萃取器（extractor）。它同時仍是零知識的：一個對 x 一無所知的模擬器，可以隨機挑 s 與 c，令 t = g^s · y^(−c)，輸出一段完美通過的紀錄 (t, c, s)——和山洞影片那套偽造論證如出一轍。

Fiat-Shamir：把驗證者開除

互動很麻煩。區塊鏈上沒有一位活生生的維克多隨時待命擲硬幣；一個張貼在鏈上的證明，必須在事後、不經來回問答地說服每一個人。1986 年，Amos Fiat 與 Adi Shamir 找到了徹底拿掉驗證者的招數。回想模擬器那一節的樞紐：驗證者唯一的貢獻，是一個證明者事先無法得知的不可預測挑戰。那就用一個密碼學雜湊函數取代真人——讓證明者把陳述與自己的承諾一起雜湊，算出她自己的挑戰。

# Fiat-Shamir: replace the verifier's coin flip with a hash.
# H is a cryptographic hash, modeled as a RANDOM ORACLE.

# Prover, ALONE, produces the whole proof:
r = random()
t = g^r
c = H(g, y, t)            # the 'challenge' nobody chose interactively
s = (r + c * x) mod q
proof = (t, s)            # non-interactive: publish once, verify offline

# Anyone verifies later, with no further interaction:
c = H(g, y, t)
accept  iff  g^s == t * (y^c)

# Hash a message m in too -- c = H(g, y, t, m) --
# and (t, s) is EXACTLY a Schnorr SIGNATURE on m.

Fiat-Shamir 變換：證明者把陳述與承諾一起雜湊，為自己製造出一個無法操弄的挑戰。

因為一個好的雜湊實質上不可預測，證明者無法刻意磨出一個能產生有利挑戰的承諾 t——在雜湊把一個她無法操控的 c 交給她之前，她就已經被綁定在 t 上了，這在沒有現場驗證者的情況下重現了「現場挑戰」的條件。這就是 Fiat-Shamir 啟發法，它能把任何 Sigma 協定轉換成非互動式證明。把一則訊息也餵進雜湊裡，Schnorr 協定就變成了 Schnorr 簽章——一個數位簽章，字面意義上就是一個「你知道某把私鑰」的非互動式零知識證明。Fiat-Shamir 也是讓 zk-SNARK 與 zk-STARK 變成非互動、能張貼到區塊鏈上的最後一步。

從客廳把戲到一台證明機器

Schnorr 證明的是你知道一個數。零知識在區塊鏈上的夢想遠比這宏大：證明你正確地跑完了一整段程式——「我執行了這 10,000 筆交易，而新的狀態根恰好是這個」——而且要用一個小到、快到能讓整個 zk-Rollup 只花幾分錢就張貼到以太坊的證明來辦到。這個性質就是簡潔性（succinctness）：無論背後的運算多麼龐大，證明本身與它的驗證都維持微小。

要走到那一步，還需要再兩次飛躍，而它們正是本階接下來的指南。首先你得把一段運算變成可被證明的東西——將程式攤平成一個算術電路與一套約束系統（電路那篇）。接著你需要一套能簡潔地證明「那些約束存在一組有效解」的機制：多項式承諾加上可信設定，給你 zk-SNARK（SNARK 那篇）；而雜湊加上低次測試，則給你透明、抗量子的 zk-STARK（STARK 那篇）。本階的一切——以及階末的 zkEVM 與隱私身分系統——都是同一個山洞遊戲，被放大、並被做成簡潔的版本。