深度解析STARK的完整安全性

本文解釋了 ethSTARK 文檔的最新更新，對隨機預言機模型中 ethSTARK 協議的安全性進行了全面而具體的分析。

原文：Safe and Sound — A Deep Dive into STARK Security

翻譯及校對：「Starknet 中文社群」

精選速覽

• 非互動式STARK 源自於互動式預言機證明（IOP），在隨機預言機模型中編譯為非互動式證明。

• 本文解釋了ethSTARK 文件的最新更新，對隨機預言機模型中ethSTARK 協議的安全性進行了全面而具體的分析。

STARK 安全性詳解

STARK 證明係統（即可擴展透明知識論證）是計算完整性的強大工具：它允許以無信任的方式驗證在公共資料上執行的計算的正確性。在本文中，我們將深入探討STARK 證明所提供的安全性，並加以定義，並探討證明方案安全性的技術。

（詳情請閱讀ethSTARK 文件（1.2 版）第6 節，以及布洛克等人就此主題所做的重要而全面的獨立工作）。

我們試圖透過安全分析實現什麼？我們希望防止對STARK 係統的「成功攻擊」，這種攻擊是由虛假陳述以及STARK 驗證器針對該（虛假）陳述而接受的STARK 證明引起的。由於虛假陳述很危險，而且它們可能以各種規模和形式出現，所以我們希望能安全地防範所有的虛假陳述。任何虛假陳述，即使是微不足道的1+1=3，隻要與STARK 驗證器接受的STARK 證明相結合，就會被視為對係統的成功攻擊。 （有密碼學背景的人可能有興趣知道，STARK 還能滿足更強的安全概念，如知識可靠性，但為了簡單起見，本篇文章將重點討論關於可靠性的簡單案例）。

我們如何正式定義STARK 係統的安全性？我們透過分析「可靠性誤差」來確定。 「可靠性誤差」大致衡量了攻擊者為成功發動攻擊所需花費的預期「成本」（即為一個虛假陳述找到一個STARK 證明，但該證明卻被STARK 驗證器接受）。從數學上講，可靠性誤差是一個函數(t)，它的輸入是時間參數t，代表攻擊者為發動攻擊而願意花費的計算時間，輸出則是攻擊者攻擊成功的機率（為虛假陳述找到令人信服的證明）。攻擊者願意花費的「成本」 t 越大，他的成功機率就越高。

到目前為止，我們已經將STARK 的安全性定義為一個函數(t)，這與大家日常在加密推特上討論安全性的方式不同。在推特上，你可能會聽到這樣的說法：「該方案有96 位元的安全性。」這種說法如何轉化為我們對安全性的定義呢？這沒有統一的答案，因為人們對「x 位元安全性」的理解略有不同：

• 嚴格解釋的話，即意味著，對於任何t 在1 和2⁹⁶之間的情況下，可靠性誤差為(t) 2⁹⁶ 。運行時間不超過2⁹⁶ 的攻擊者的成功機率很小，小於2⁹⁶，即小於十億分之一乘以十億分之一。

• 一種更寬鬆、或許也更常見的解釋則是，96 位元的安全性意味著對於任何t，都存在t/(t) 2⁹⁶ 的情況。這意味著成功機率與運行時間成（反）線性關係。如果攻擊者的運行時間為2⁸⁶，那麼其成功機率最多為2¹⁰。

在本文中，我們將討論第二種方案。

從IOP 到具備96 位元安全性的STARK

那麼，我們要如何證明一個方案具備了96 位元的安全性呢？為了回答這個問題，我們需要理解建構STARK 的高層結構。 STARK 由三個主要部分組成：IOP（互動式預言機證明）、梅克爾樹和Fiat-Shamir 哈希；我們主要關注的重點部分是IOP。一旦指定了這些元件部分，我們就可以編譯它們來產生一個STARK。我們將詳細介紹這些組件，包括它們是什麼以及如何將它們組合在一起。

首先我們要審查的組件是IOP：IOP 類似於標準的交互式證明，在其中證明器和驗證器進行多輪交互（我們僅限於公共幣協議，即驗證器隻向證明器發送隨機挑戰）。在IOP 中，驗證器不會完全讀取證明器的訊息，而是從每個證明器資訊中抽樣一小部分位元。這就是後來編譯的STARK 能夠實現簡潔性的原因。

有了IOP，如何從中建構STARK？證明器的資訊可能很長（實際上，它們比計算本身還要長）。為了壓縮這些訊息，我們使用梅克爾樹。梅克爾樹是一棵二元哈希樹，其中每個葉節點代表IOP 中的一個查詢或一個答案。樹根是整個訊息的承諾。當驗證器想要讀取資訊中的特定位置時，證明器會提供該位置的值和驗證路徑。驗證器就可以使用該路徑來驗證該值是否正確。 IOP 驗證器隻從證明器資訊中讀取少量的位置資訊。因此，使用默克爾樹可以實現簡潔的協定（通訊量小的協定）。

壓縮輪次

我們可以選擇互動式STARK，但為了簡化產生STARK 的過程，我們通常會選擇非互動式STARK，這樣驗證器在建置STARK 時就無需等待外部資訊。事實上，這是目前所有STARK 係統的部署方式，也是ethSTARK 協定的建構方式。非互動式STARK 也是透明SNARK 的一種特例（透明意味著無需可信設定來實例化它們；“Arthur Merlin 協議”或“公共硬幣IOP”）。為此，最後一個步驟是應用Fiat-Shamir 演算法將多輪交互壓縮至單一訊息，我們稱之為STARK 證明。 Fiat-Shamir 變換是將一個互動式協定轉換為非互動式協定的方法。證明器在“與雜湊函數對話時”模擬互動協議。為了得出第i 輪的隨機挑戰，證明器哈希至第i 輪的部分記錄，並將輸出解釋為下一個挑戰。

這確保了證明器在挑戰生成後無法更改自己的答案。然而，作弊的證明者擁有一些在互動式IOP 中沒有的新策略途徑。證明器可以透過修改最後一個證明器資訊來重新產生驗證器挑戰，這樣就會得到一個新的記錄，因此也會得到一個新的挑戰。事實證明，IOP 的標準可靠性概念不足以證明Fiat-Shamir 轉換的安全性。

例如具有96 輪的IOP，並向驗證器添加以下hack：如果驗證器的隨機性的第一比特在96 輪中每一輪都是0，那麼驗證器就會接受（無需查看任何證明）。我們可以看到，在驗證器上加入這個hack 隻會在IOP 的可靠性誤差中加入一個2⁹⁶ 的項。然而，經過Fiat-Shamir 變換後，攻擊者可以輕鬆修改證明器訊息，確保每個雜湊值都以0 開頭，從而在很短的時間內攻破係統。請放心，這種可怕的情況隻是一個理論上的例子，並不適用於已部署的STARK。那麼，讓我們來看看為什麼我們的STARK 終究是安全的呢。簡而言之，我們將證明，攻擊者最多運行t 步，攻擊成功的機率最多為(t) t 2⁹⁶。

IOP 和逐輪可靠性

STARK 的安全性取決於其底層IOP。但是，一個IOP 具有96 位元的安全性意味著什麼呢？依照標準定義，IOP 的可靠性誤差為2⁹⁶：這意味著任何攻擊者（無論運行時間長短）欺騙驗證器的機率最多為2-96。然而，正如我們所討論的，IOP 的可靠性隻是三個部分中的一個，這並不足以讓從所有三個步驟編譯出來的STARK 獲得96 位元的安全性。相反，假設STARK 有96 位元逐輪可靠性誤差（有時也使用一個被稱為狀態恢復可靠性的類似定義），則編譯後的STARK 的安全性就得到了證明。

直觀地講，「逐輪可靠性」（round-by-round soundness）表明每一輪都有96 位元的安全性，而不僅僅是整個協議。說得詳細一點，即逐輪可靠性指的是存在一個謂詞，它能獲取協議的部分記錄，並告訴我們這個記錄是否是“欺騙性的”：“空記錄”不是“欺騙性”，而當且僅當驗證器接受時，完整的記錄是「欺騙性」。最後，對於任何不是「欺騙」驗證器的部分記錄，在下一輪中記錄變成「欺騙性」 的機率至多為2⁹⁶。如果存在具有這些屬性的判定，我們會說協定具備96 位元的逐輪可靠性（這個謂詞不要求可以有效計算）。

在許多情況下，人們隻分析IOP 的可靠性，而不會分析其逐輪可靠性。誠然，我們很難想到IOP 具有標準可靠性而不具有逐輪可靠性的例子（人為製造的例子除外）。然而，當推導具體安全界限時，兩者之間的差異可能會出現，每個位元都很重要。因此，要推導出嚴密而具體的界限，就必須對IOP 的逐輪可靠性進行嚴格分析。這正是我們對FRI 協議和作為STARK IOP 基礎的ethSTARK IOP 所做的工作。分析本身遠非小事，並超越了本文討論的範疇。使用新的分析，我們可以為我們的證明設定精確的參數。

逐輪可靠性確實為我們提供了所需的保障。證明器可以多次重新產生挑戰，但我們知道，在任何一輪中，產生「欺騙性的記錄機率都是2⁹⁶。因此，如果證明器有t 次時間（以哈希調用次數來衡量），那麼它最多可以嘗試t 次來獲得欺騙性記錄，這將其成功機率限製在(t) t 2⁹⁶。

新增所有錯誤項

最後，要使這一切成立，我們需要確保證明器無法篡改默克爾樹。我們可以表明，隻要證明器在雜湊函數中沒有發現碰撞，他就無法在默克爾樹中作弊。攻擊者使用t 次呼叫（隨機雜湊函數）找到碰撞的機率最多為t2/2，這就是雜湊函數的輸出長度（由「生日悖論「造成）。這就是為什麼我們需要設定雜湊函數的長度為所需安全性的兩倍。如此一來，如果我們有一個輸出長度為192 的雜湊函數和一個逐輪可靠性為96 位元的IOP，我們就會得到一個編譯後的STARK，其可靠性誤差(t)=t2-⁹⁶ + t2 2¹⁹⁶。由於t/(t) = t/(t 2⁹⁶+t2 2¹⁹⁶) 1/(2⁹⁶+1/2⁹⁶) = 22955) = 295595656)性。

總結

綜上所述，STARK 提供了一種強大的方法，用於以無信任的方式驗證在公共資料上執行的計算的正確性。 STARK 的安全性通常以「可靠性誤差」來衡量，它代表了攻擊者成功提供了一個虛假陳述並用證明說服驗證器的機率。為了達到所需的安全級別，例如96 比特，底層的IOP 必須滿足逐輪可靠性，確保每一輪都能保持高安全級別。我們分析了我們的STARK 所基於的IOP 的逐輪可靠性，從而得出了具體的安全界限。

原文鏈接