STARK算法解析

• STARK算法解析

• 第4部分：STARK Polynomial IOP

• 第2部分：有用的“工具”

• 第3部分：FRI

• 第4部分：STARK Polynomial IOP

• 第5部分：A Rescue-Prime STARK

• 第5部分：A Rescue-Prime STARK

第6部分：加速整個流程

1.什麼是STARKs？

最近，密碼學證明系統領域最令人興奮的進展之一是STARKs 的發展。它是在區塊鏈行業蓬勃發展之後出現。整體上來看，證明系統似乎是為其量身定做的：區塊鍊網絡通常由相互不信任的各方組成，他們希望使用秘密信息進行交易，或根據狀態演變規則更新集體狀態。由於參與者是相互不信任的，因此他們需要驗證其同伴提出的交易（或狀態更新）的有效性的方法。

• 由於zk-SNARKs 的以下特點，它們自然具備在這種環境中提供計算完整性保證的能力：

• zk-SNARKs 一般是通用的，意味著它們能夠證明任意計算的完整性；

• zk-SNARKs 是非交互式的，這意味著整個完整性證明由單個消息組成；

• zk-SNARKs 的驗證是高效的，也就是說，與簡單地重新運行計算相比，驗證者的工作量會降低一個數量級（譯者註：幾個數量級也是有可能的）；

"zk-SNARKs 是零知識的，這意味著它們不會洩露關於計算秘密輸入的任何信息。"我期待zk-SNARKs 在未來10-20年內滲透到主流世界，並引領一場重大的革命。

—— “ V神” 2021.9.2

• zk-SNARKs 已經存在了一段時間，但STARK 證明系統是一個相對較新的東西。它的脫穎而出有幾個原因：

• 傳統的zk-SNARKs 依賴於尖端的密碼學難題和假設，而STARK 證明系統中唯一的密碼學成分是一個抗碰撞的哈希函數。因此，在理想化的哈希函數模型下，該證明系統的抗量子安全性是可以被證明的（在文獻中，這種理想化被稱為“量子隨機預言機模型” quantum random oracle model ）。這與第一代SNARKs 形成鮮明對比，後者使用雙線性映射，且只在不可證偽的（Unfalsifiable）假設下具有可證明的安全性。

• 傳統的zk-SNARKs 依靠一個可信的設置儀式來產生公共參數。儀式結束後，使用的隨機參數必須被安全地遺忘。儀式本身並非去信任的，因為如果參與者拒絕或忘記刪除這種密碼學上的“有害垃圾”，他們就會保留偽造證明的能力。相比之下，STARKs 沒有可信的設置，因此沒有密碼學上的"有害垃圾“。



有害垃圾“。

“我基本同意，但在兩點上持有保留意見:

1) 是STARKs 將占主導地位，而不是SNARKs

2) 3-5年就會滲透到主流世界

在我的日曆上寫上提醒，以便4年後來檢驗這些話。 ” —— Eli Ben-Sasson 2021.9.2

在本教程中，我將解釋其中許多部分是如何一起工作的。這個文字解釋由一個證明和驗證基於Rescue-Prime 哈希函數的簡單計算的Python 實現來支持。在閱讀或學習了本教程之後，你應該能夠為你選擇的計算編寫你自己的零知識STARK 證明者和驗證者

2.為什麼寫作本文？

• Vitalik Buterin 的多部分教程（第一/二/三部分）。

• Vitalik Buterin 的多部分教程（第一/二/三部分）。

• StarkWare 的一系列博文（第1、2、3、4、5部分）。

• StarkWare 的一系列博文（第1、2、3、4、5部分）。

• StarkWare 的STARK @ Home 網絡廣播

• StarkWare 的STARK 101 在線課程

• StarkWare 的EthStark文檔

一般來說， StarkWare 推出的任何東西

有了這麼多學習資源，我為什麼還要再寫一個教程呢？

已有的教程比較淺顯。在從高層次上解釋了這些技術是如何工作的方面，這些教程做得不錯，並傳達了一種直覺——為什麼STARKs 可以起作用。然而，它們沒有描述一個完整的、可供部署的系統。例如，沒有一個教程描述如何實現零知識，如何批處理各種低度證明，或如何確定由此產生的安全級別。 EthSTARK 文檔確實提供了一個完整的參考資料來回答這些問題中的大部分，但它是針對一個特定計算的，沒有涵蓋零知識，也沒有給出一個易懂直觀的解釋。

這些論文是難懂的。令人難過的是，科學出版業的激勵機制被設定為：使科學論文對非專業讀者來說難以閱讀。因此，需要像本文這樣的教程，以使這些論文能被更多的人理解。

資料已經過時了。各種教程中描述的許多技術後來都得到了改進。例如，EthSTARK 文檔（上面引用的最新的文檔）描述了一種DEEP 插入技術，以便將正確求值的要求降低到有界度的多項式。這些資料中沒有提到這種技術，因為這些資料比該技術出現得更早。

我更喜歡我自己的風格。我不同意很多符號和名稱，我希望人們能使用正確的符號和名稱。特別是，我喜歡把重點放在多項式上，作為證明系統的最基本對象。與此相反，所有其他資料都是以對里德-所羅門碼字的操作來描述證明系統的機制。

這個教程有助於我更好地理解STARK 。寫這篇教程有助於我將自己的知識系統化，並找出其淺薄或完全缺乏的地方。

3.所需要的背景知識

• 本教程在需要的時候會溫習一些背景知識。但建議所有讀者還是了解和學習一下以下主題，因為如果不熟悉這些主題，這裡的介紹可能會過於密集。

• 哈希函數

• 哈希函數

• 哈希函數

哈希函數

• 4.系列嚮導

• Part 1: 縱觀STARK 從高層次描繪了概念和工作流程

• Part 2: 有用的“工具” 介紹基本的數學和密碼學工具，證明系統將由此建立

• Part 4: STARK Polynomial IOP（IOP,Part 3: FRI 涵蓋了低度測試，這是證明系統的密碼學核心

• interactive oracle proof）解釋了從任意的計算性要求中生成抽象證明系統的信息理論

• Part 5: A Rescue-Prime STARK 把這些工具放在一起，為一個簡單的計算建立一個透明的零知識證明系統"S "Part 6: 加速整個流程引入算法和技術，使整個流程變得更快，有效地將

  (簡潔性，succinct) 放入STARK

5.致謝

作者希望感謝Bobbin Threadbare、Thorkil Værge 和Eli Ben-Sasson 的有用反饋和意見，以及Nervos 基金會的資金支持。請給他發郵件：alan@nervos.org，或在twitter 或Github 上關注aszepieniec。

About zCloak Network

譯者註：原文中有大量文獻鏈接，由於公眾號限制無法附上，請讀者自行參考原文中的文獻鏈接。