互動式證明系統

互動式證明系統是一場對話。一方稱為證明者，試圖說服另一方驗證者相信某個陳述為真——例如「我知道這道謎題的解」或「這項計算確實正確完成」。兩者不是交出一份靜態文件，而是來回交換訊息：驗證者拋出隨機挑戰，證明者作答，幾輪之後驗證者決定接受或拒絕。互動的關鍵在於：一個作弊的證明者——其陳述為假者——無論回答得多巧妙，都會以壓倒性的機率被抓出來。

形式上，這類系統必須同時滿足完備性（誠實的證明者、為真的陳述，永遠能說服誠實的驗證者）與可靠性（說謊的證明者只能以可忽略的機率騙過驗證者）。驗證者的隨機性是關鍵成分：因為證明者無法預測下一個挑戰，就無法事先準備好一套謊言劇本。經典的例子是「阿里巴巴山洞」故事，其中反覆的隨機擲幣會把作弊者的成功機率，在 k 輪獨立挑戰後壓低到 (1/2)^k。當協議還額外地不洩漏「為何陳述為真」的任何資訊時，它就同時是零知識的。

互動式證明是深刻的計算複雜度理論，而不只是密碼學：擁有高效互動式證明的問題類別 IP 等於 PSPACE，這個令人震驚的結果顯示，互動加上隨機性能換來巨大的驗證能力。對區塊鏈而言，其實務後代最為重要——sigma 協議、sumcheck 協議，以及 STARK 內部的互動式論證——因為幾乎每一個現代的簡潔證明，最初都是一個互動式協議，再被編譯成單一訊息的非互動式版本（通常透過 Fiat-Shamir 啟發法），才能張貼到鏈上。