如何證明錯誤的陳述（二）
原文：https://blog.cryptographyengineering.com/2025/02/06/how-to-prove-false-statements-part-2/
作者：Matthew Green
譯者：Kurt Pan
在上一篇文章中，我們介紹了幾個概念，包括：“可驗證運算”證明系統（有時被以太坊社群不準確地稱為零知識）、雜湊函數、我們用於安全性證明的一些理想模型，以及這些“理想模型”實則虛假——有時它們甚至會讓我們對在現實世界中完全不安全的方案產生信心。
今天，我想繼續前進，進一步探討標題中提到的近期成果：Khovratovich、Rothblum 與 Soukhanov 發表的論文《如何證明錯誤的陳述：針對 Fiat-Shamir 的實際攻擊》（以下簡稱 KRS）。這篇論文展示了一個在某個設定下看似安全的證明方案，可能實際上並不安全。
https://eprint.iacr.org/2025/118
討論這篇論文的一種方法是從頭開始逐步講解到結尾，但我們不會那樣做。相反，我打算採取一種跳躍式的論述方式。我的瘋狂中自有其方法。
在進入正題之前，我們需要先介紹一些基本背景。
背景部分第一：互動式證明系統
我在這系列文章開頭曾重申對所謂隨機預言模型範式的批評，即我們假設雜湊函數實際上是隨機函數。深思熟慮的密碼學家們無疑會因此感到不悅，因為事實上 KRS 論文並不是關於隨機預言！相反，它展示了另一種密碼學家們普遍使用的“啟發式方法”存在的問題：這就是所謂的 Fiat-Shamir 啟發式。
儘管 Fiat-Shamir 與隨機預言模型並不相同，但兩者卻存在於相似的領域，甚至共享著某些相同的基礎。我的意思是：在某些極為有限的理論情況下，Fiat-Shamir 可以不依賴隨機預言模型，但在實際應用中，兩者通常是相互依賴的。
因此，要解釋這個新結果，我需要先說明 Fiat-Shamir 的運作原理。而在此之前，我必須介紹什麼是互動式證明。（如果你已經了解這部分內容，可以自行略過。）
我們今天使用的許多可驗證運算“證明系統”，都屬於一類稱為互動式證明的協議。這些協議中，兩個參與方——證明者與驗證者——通過訊息交換，使得證明者能夠向驗證者證明某一陳述的真實性（例如「我知道一個使特定程式正常運作的輸入 x」，並可能提供輔助證明的見證w）。在許多情況下，這些協議遵循如下形式的互動模式：
證明者發送一個訊息，對輸入與見證（也可能包含其他相關資訊）進行「承諾」，並將這個承諾訊息法送給驗證者。 接著，驗證者產生一個或多個挑戰，證明者必須對此作出回應；這裡具體的處理方式會依證明方案而有所不同。 然後，證明者依據每個挑戰計算出相應的回應，驗證者則檢查每項回應的有效性（檢查方法同樣因證明方案而異）；若有任何回應不符要求，驗證者便會拒絕該證明。 這對參與者可以將上述步驟重複多次——無論是連續進行或平行處理。
我知道對於這些挑戰與回應的具體運作，我的描述可能顯得非常籠統，但事實上，目前我們並不需要過於關注細節。你只需知道，若證明者誠實（也就是說，見證確實能使程式滿足要求），那麼面對挑戰時應能輕易作出正確回應；相反，若證明者在作弊、即沒有提供正確見證，那麼成功應對隨機挑戰的機率就應當非常低。
（注意，我們並不要求挑戰必須讓作弊的證明者完全無法應對！這也是為什麼證明系統通常會多次重複挑戰與回應階段：即使作弊者有一絲機會能夠通過某次挑戰，但連續多次作弊的成功機率將大幅降低。）
從整個設置中，你可能會注意到兩個重點：第一，互動式證明需要大量（嗯）互動；第二，它們假設驗證者是誠實的，且能提出「良好」的挑戰。
這種對互動的需求在許多應用中相當令人困擾，尤其是對於像區塊鏈這樣的系統來說，可能有數以千計甚至數百萬台電腦需要驗證某個陳述（例如，一筆交易）的正確性。如果證明者僅與單一驗證者進行一次證明，然後將他們的互動記錄公開，情況將會容易得多，任何人都可以檢查該記錄以確認證明者是否正確回答了所有挑戰！
然而，這個想法存在一個關鍵問題！ 這些協議的安全性依賴於驗證者所提出的挑戰是隨機的，或至少對證明者而言極難預測。如果證明者能夠在第一步承諾其輸入之前就預知將面臨的挑戰值，那麼它往往可以通過在第一條訊息中調整策略來進行作弊。更具體地說，一個不誠實的驗證者甚至可以與證明者「串通」，暗中提前告知挑戰內容，以幫助證明一個錯誤的陳述。因此，驗證者必須保持誠實，且絕不能與證明者串通，這一點至關重要。
但這些系統的全部意義在於我們根本不需要信任任何單獨的參與者！如果我們只是單純相信大家都會誠實行事，那這一切又有何意義呢？
更多背景：Fiat-Shamir
現在，我想帶你回到很久以前，回到1980年代中期。
1986年，兩位密碼學家 Amos Fiat 與 Adi Shamir 遇到了一個與此相似的問題。他們當時擁有一個互動式證明系統——當時的系統相對簡單，畢竟那是1980年代——而他們希望將這種互動式證明轉變為任何人都能驗證的非互動式證明。他們曾考慮過上述提及的證明記錄（transcript）的概念，但很快意識到那行不通，因為驗證者可以輕易與證明者串通來幫助其作弊。為了解決這一問題，他們提出了一個既巧妙又簡單的解決方案，同時也開啟了一條至今仍在探索的龐大理論領域。
https://link.springer.com/content/pdf/10.1007/3-540-47721-7_12.pdf
Fiat轉向Shamir（我想象中）並闡述了整個問題。Fiat（或Shamir）說：「也許我們能找到一種方式，讓驗證者能以隨機但可重現的方式選擇挑戰，這樣任何人都能確認這些挑戰確實是隨機且不可預測的。」隨後其中一人說道：聽起來很像一個雜湊函數。
於是，Fiat-Shamir啟發式便誕生了。
Fiat與Shamir提議，不再隨機挑選挑戰值，而是讓「驗證者」通過對證明者所發送的「承諾」訊息進行雜湊（或許還包括其他附加資訊，如正在證明的「程式」或電路）來決定挑戰值。接著，證明者對這些挑戰訊息作出回應，並輸出整個證明的記錄。
就是這樣。這便是整個妙招。
儘管方法簡單，但這種Fiat-Shamir方法具有一些顯而易見的吸引之處：
優秀的雜湊函數通常能產生看似非常「隨機」的結果，這正是我們在挑戰中所需要的。 任何第三方只需檢查證明記錄，確認挑戰值是否與證明者「承諾」訊息的雜湊值相符，即可輕鬆驗證證明。（換句話說，既然一切皆已確定，就再無驗證者與證明者串通或作弊的餘地。）
更關鍵的是，這裡存在一個有趣的「循環」悖論。 作弊的證明者可能會試圖利用以下技巧來預測它將面臨的挑戰值：具體而言，它可能先（1）選定一個承諾訊息，然後（2）對該訊息進行雜湊以得到挑戰值。一旦它得知了這些挑戰，就可能試圖改變第一步中的輸入，以便更容易地在那些特定的挑戰點上作弊。但關鍵在於，這種方法會產生悖論……！ 若證明者更改了第一步的輸入，就會產生一個全新的「承諾」訊息；當這新的承諾訊息被雜湊後，便會產生一組截然不同的挑戰值，而作弊者則陷入了一個永無止境的時間循環，無法自拔！
Fiat-Shamir的精妙之處在於，一旦挑戰生成的驗證者完全確定，便不再需要由另一個獨立方來運行這段程式碼。證明者可以獨自運行這段確定性的挑戰生成程式碼，也就是說，執行所有必要的雜湊運算以生成挑戰，然後輸出最終的證明記錄。這樣一來，原本分別屬於證明者和驗證者的程式碼便合而為一（我們從此只稱之為證明者），而新的驗證者則變成了一個用於檢查證明記錄的演算法——執行所有必要的雜湊運算以及挑戰與回應的檢查，以確保一切正確無誤。
最終生成的證明（即證明記錄）在驗證時不再需要任何互動，因此我們甚至可以將它們發布到區塊鏈上。數以千計甚至數以百萬計的人皆可進行驗證，而我們也因此能夠在此基礎上懸掛大量資金。
Starknet 只是眾多以 Fiat-Shamir 式證明系統懸掛真金白銀的密碼貨幣系統之一，還有其他不少！
我敢打賭你現在就會不停地喋喋不休地談論 Fiat-Shamir 的可證安全性，對吧？
等等，你怎麼知道我正要談這個？ 哦，原來如此：其實「你」就是我，所以我只是在回答自己的問題。（這不正生動地展示了 Fiat-Shamir 所幫助解決的那個悖論嗎！）
我將盡量簡明扼要地說明，但情況是這樣的：Fiat-Shamir 看似一個瘋狂的招數。我們甚至稱它為一種啟發式方法，這恰恰承認了它的不完美。然而，實際上已經有數以百計的論文探討了 Fiat-Shamir 及其相關方案的可證安全性。
總結起來就是：只要我們做出一個有利的假設，Fiat-Shamir 常常能被證明是安全的（當然這裡的「安全」有各種不同的定義）。具體而言，我們假設所使用的雜湊函數實際上是一個隨機預言。我不打算深入探討這個論點，但只想讓你記住隨機預言的運作方式：
在隨機預言模型中，雜湊函數被視為一個隨機函數。通俗來說，這意味著當它被查詢一個全新的值時，會輸出與該輸入完全不相關的隨機位元。 雜湊函數「存在於」一個完全獨立的單位中，稱為預言。你把需要雜湊的資料送過去，若該輸入從未被處理過，你就會獲得一個不可預測的隨機值。
這顯然與互動式證明的環境十分相似！簡而言之（絕無雙關之意）：如果一個合適的方案能在互動環境中證明其安全性——也就是證明者與一位誠實、會選取隨機挑戰的驗證者互動——那麼看來，該協議的 Fiat-Shamir 版本在隨機預言下也應能正常運作。隨機預言基本上扮演了原始互動方案中驗證者的角色：它產生出大家都能「信任」為真正隨機的挑戰，而且任何第三方在檢查證明記錄時，都能要求它重現同樣的挑戰！
而在很多情況下，這種隨機預言的方法通常運作良好。當然，也有人提出一些瘋狂的理論反例（也就是構造出在隨機預言模型中安全，但在實際使用真實雜湊函數時便會崩潰的互動式協議），但大多數從業者都會忽略這些，因為它們顯然充斥著種種離奇的荒謬。
https://eprint.iacr.org/2003/034.pdf
在現實世界中，應用密碼學家每天都在設計新的證明系統，我們已經採用了一個相當標準的模式：首先，新證明系統會以互動式協議的形式被描述出來。最終，每個人都清楚該證明系統並不會以互動方式實際運用，而是會經由 Fiat-Shamir 壓平後，應用於區塊鏈上。然而，論文作者通常不會花費大量篇幅去討論 Fiat-Shamir 部分，他們只會描述出具有正確結構的互動式協議，然後說類似「當然，只要我們假設存在一個隨機預言之類的，這個協議就可以利用 Fiat-Shamir 壓平」的話，隨後大家便會點頭認可，並投入數十億資金。
但這其中總有問題，不是嗎？
確實，這整個策略中存在一個重要的附帶條件，我必須提出來。
儘管我們有時能證明 Fiat-Shamir 協議是安全的（通常是在隨機預言模型中），但這些證明的一個關鍵特性是：我們——也就是協議的參與者——並不知道雜湊函數的精簡描述。這是不可避免的，因為隨機預言模型中所使用的雜湊函數是一個龐大且隨機的函數，無法以精簡的形式表達。
在現實世界中，我們自然會用 SHA-3 或甚至更令人興奮的雜湊函數如 Poseidon 來取代隨機預言。這樣一來，協議中的每個人都會知道該雜湊函數的精簡描述。如前所述，這可能會引發理論上的問題。早在 2004 年，Goldwasser 與 Tauman（以及後來的 Kalai）就設計出一個特定的互動式協議，但當該協議中的雜湊函數被實例化為任何具體的雜湊函數時，它就會徹底崩潰。
https://eprint.iacr.org/2003/034.pdf
然而，Goldwasser/Tauman 的協議極為人為，其協議描述中明顯包含了一些荒謬的設計。顯然，只要我們不採用那些做法，情況也許就沒問題，吧。
但現在的問題在於，我們正在部署的證明系統可以證明幾乎任何合理程式（或“NP-關係”）的正確性，而這些程式可能會包含 Fiat-Shamir 雜湊函數的實現。在隨機預言模型中，這在字面上是不可能的——因此我們僅僅假設這種情況不會發生；但在現實世界中，這種情況非常有可能發生，我們必須假定它確實會且能發生。
事實上，某些電路中確實極有可能包含 Fiat-Shamir 雜湊函數的實現！原因正是因為我在上一篇文章中提到的那些遞迴證明。
假設我們想建立一個遞迴證明系統，用以驗證我們其中一個經過壓平的 Fiat-Shamir 證明。回想一下，為了達到這個目的，我們必須將用來檢查 Fiat-Shamir 證明記錄的 驗證者演算法實作於一個程式（或電路）中。接著，我們需要執行該程式，並生成一個證明，證明我們已成功運行了它！而為了讓這一切順利進行，我們確實必須在程式中嵌入一份 Fiat-Shamir 雜湊函數的實現——這絕非可有可無。
令人匪夷所思的是，我們甚至無法在隨機預言模型中證明這些基於 Fiat-Shamir 的遞迴證明是安全的！在隨機預言模型中，由於雜湊函數沒有精簡描述，因此我們也無法撰寫出一個精簡的遞迴型驗證者程式或電路。這種遞迴根本是不可能的。事實上，遞迴型 Fiat-Shamir 證明只能存在於隨機預言模型之外，那時我們會用類似 SHA-3 的東西來實作雜湊函數；但當然，在隨機預言模型之外，我們就無法對其安全性做出任何證明。結果就是：每當你看到一個遞迴型 Fiat-Shamir 證明時，我們基本上就是把可證安全性徹底拋諸腦後，孤注一擲地使用它。
這種情況極為糟糕，許多理論學家都因此而大傷腦筋。
我現在已經寫完了整整一篇第二篇文章，但還沒談到我此行原本要談的 KRS 結果！還有人在閱讀嗎？這東西還在進行嗎？我真心希望如此。
現在，我們準備好談論 KRS，而我將在下一篇文章中馬上開始。在結束這篇文章並準備撰寫下一篇重磅文章之前，讓我來回顧一下我們目前的位置：
我們知道 Fiat-Shamir 可以被證明是安全的，但通常（對於完整的 SNARKs 而言）僅能在隨機預言模型中證明。 一旦我們真正用真實的雜湊函數來實例化 Fiat-Shamir，任何奇怪的事情都有可能發生——尤其是當我們要證明的程式或電路中也實作了相同的雜湊函數時。 遞迴型（Fiat-Shamir）證明實際上要求我們在要證明的程式中嵌入雜湊函數的實現，這真是令人極為擔憂。
接下來，我們需要證明 Fiat-Shamir 在實際應用中確實可能是不安全的。或者更具體地說：存在某些「惡意」程式或電路，能夠破壞一個原本運作良好的使用 Fiat-Shamir 的證明系統。
在下一篇文章中，我終於要談談這個問題了。
註記：
當然，Fiat-Shamir 技巧並非對所有顯然的攻擊免疫。例如，一個作弊的證明者（通常也同時扮演驗證者）可以對證明進行「窮舉攻擊」——也就是嘗試許多不同的第一步訊息輸入，然後針對每一種情況檢驗所產生的挑戰是否有利於其作弊。如果存在微小的作弊成功機率，這種「多次嘗試」的方法便能顯著提高作弊者在挑戰／回應過程中偶然成功的概率，因為他們可以利用數百萬（甚至數十億！）次的機會來尋找一個有利的挑戰。不過，現實中我們合理假設，真正作弊的證明者僅擁有有限的計算能力。即使一個證明者能進行大量的雜湊嘗試（例如 次），你仍可以輕易設計方案，使其成功作弊的機率保持在任意小的水平。當然，並非所有人都能完美做到這點：我的博士生 Pratyush 最近就合著了一篇關於一些實際區塊鏈證明系統中參數選擇的優秀論文。 https://eprint.iacr.org/2023/1071 當我說 Fiat-Shamir 的可證安全性依賴於隨機預言模型時，我的說法或許略嫌不精確。通常，隨機預言模型足以證明 Fiat-Shamir 的安全性主張。然而，事實上有一些（相對較新的）研究成果展示了如何利用非隨機預言的雜湊函數來構造針對特定互動式協議的 Fiat-Shamir 方法——這類雜湊函數稱為關聯不可求解函數。據我所知，利用這些函數來證明基於 Fiat-Shamir 的 SNARK 能夠處理任意（可自適應選擇的）程式或電路的安全性似乎是不可能的，但對此細節我也樂於接受可能有誤的可能。