zk-STARK 是什麼？
zk-STARK 是一個零知識證明系統，與 zk-SNARK 相比，它不再依賴於初始化“有毒廢物”參數的可信設置。
通俗地說，zk-STARK 的基本建構塊是什麼，它們是如何工作的？
STARK 是一個透明的零知識證明系統。換句話說，證明者和驗證者不需要分別使用第三個生成參數來生成證明和檢查聲明的有效性。相反，zk-SNARK 系統會缺乏安全性（這些方案基於通用參考字元串（CRS））。
讓有一個數據中心來回答使用者的查詢。例如，在 STARK 白皮書中提到的 CODIS 系統中，驗證者想知道 FBI 數據中心中是否存在特定的 DNA 配置文件（通過快速辨識累犯來防止進一步的犯罪）。在這個術語中，這個數據中心不僅要降低執行每個查詢的協議的複雜性，而且還要在第三方受信任方的攻擊下保持安全（通過使用主密鑰洩露資訊和損害隱私），這一點非常重要）。
假設有 100 萬個 DNA 配置文件，並且作為證明者的數據中心只想為所有配置文件生成一個證明來說服驗證者。一個瘋狂的解決方案似乎是數據中心為每個配置文件生成一個證明，但它效率不高（即雙重效率）。對於 Reed-Solomon (RS) 糾錯碼，證明者能夠獲得對應於所有 DNA 譜的編碼函式。對於每個 RS 程式碼， $ RS[F, S, \rho] $ 是函式族 $ f: S\to F $ 這些函式是對次數小於的多項式的求值 $ \rho|S| $ . 準確地說，編碼的輸出是一個多項式，證明者聲稱如果驗證者將每個 DNA 輪廓放入該多項式中作為輸入，則輸出等於零（即是低次多項式的根）。重要的一點是驗證者永遠不知道關於其餘配置文件的任何資訊。
但如你所知，這不足以讓驗證者檢查聲稱的功能是好是壞！我的意思是關於 Schwartz-Zipple 引理兩個不同的多項式 $ d $ 最多有 d 個交叉點，所以函式 $ f $ 對於 999.999 DNA 配置文件來說並不是唯一的。此外，驗證者需要檢查所有配置文件以確定函式的有效性（即是一個低次多項式）。STARK 白皮書的作者解決的方法是 FRI（快速傅里葉變換 Reed Solomon 互動式鄰近測試）方案。它是解決低度接近測試問題的解決方案。該方案試圖通過檢查低次多項式而不是原始結構來逐步減少S集合中的元素數量以說服驗證者。（多項式的次數選擇小於配置文件的數量以提供更好的可靠性，例如，10.000 次的多項式用於 100 萬個 DNA 配置文件）
FRI 方案基於互動式預言機證明（IOP）系統，驗證者選擇一些隨機數，證明者為他/她提供相應的預言機訪問權限。最後，經過幾輪，驗證者可以決定證明者聲明的正確性。也可以提供非互動式 IOP。
關鍵點是關於證明者想要產生對應於電路可滿足性問題的接近度測試問題的算術化。換句話說，證明者和驗證者同意電路分別證明和檢查其執行的有效性。該術語基於一些技術來解決對數複雜度而不是 NP 完全問題（3SAT 是一個 NP 問題）。我只是在這裡提到這些技術，如果您需要了解更多資訊，請發表評論。
電路可滿足性 $ \to $ 代數約束滿足問題（CSP） $ \to $ 3SAT $ \to $ 3-著色問題 $ \to $ de-Bruijn Graphs解決 3 種著色問題等等。
zkSTARK 在一個NP 完全計算完整性關係的知識系統論證中，它滿足以下屬性：
- 零知識
- 非互動性
- 漸近最優效率（多對數證明大小和驗證者時間，以及準線性證明者時間）
- 透明度（設置中的所有隨機性都是公開的）
雖然確切構造的細節很複雜，但總體構想是建構一個互動式論證系統，在該系統中，驗證者可以自由地以機率方式查詢證明者的消息，而不是完整地閱讀它們。這種類型的協議稱為互動式預言機證明 (IOP)。如果所有驗證者的查詢都是從均勻分佈中生成的，那麼可以使用 Fiat-Shamir 啟發式使 IOP 成為非互動式的。zkSTARK 的主要創新是（1）降低了關於 Reed-Solomon 碼的某些語句的計算完整性，以及（2）為前面提到的語句建構了一個非常有效的 IOP。