1. 引言

• non-interactive STARKs，起源于Interactive Oracle Proofs (IOPs)，然后通過random oracle模式轉(zhuǎn)換為非交互式。
• StarkWare團(tuán)隊(duì) ethSTARK Documentation – Version 1.2（2023年7月）論文做了更新，給出了完整具體的random oracle模式下的ethSTARK安全性分析。本文對(duì)該論文的更新做了解釋。

2. STARK安全性解釋

STARK proof system (Scalable Transparent Argument of Knowledge)是用于證明計(jì)算完整性（CI，computational integrity）的強(qiáng)大工具：

• 支持以trustless方式，來驗(yàn)證基于某公開數(shù)據(jù)的計(jì)算的正確性。

本文深入探索由STARK proofs所提供的安全性，對(duì)該安全性進(jìn)行定義，并探索證明方案安全性的技術(shù)。
詳情見：

• StarkWare團(tuán)隊(duì) ethSTARK Documentation – Version 1.2（2023年7月）論文第6章。
• Justin Thaler等人2023年論文Fiat-Shamir Security of FRI and Related SNARKs。

我們?cè)噲D通過安全分析實(shí)現(xiàn)什么？：

• 試圖找到一種對(duì)STARK系統(tǒng)的“成功攻擊”方式，使得對(duì)于某false statement，可生成讓STARK Verifier 接受的 STARK proof。

由于false statement是危險(xiǎn)的，可能具有任意大小和形狀，而所構(gòu)建的STARK系統(tǒng)是希望能抵御 所有 false statement的。

任何false statement，哪怕是1+1=3，若可基于該false statement生成讓STARK Verifier信服的STARK proof，則可認(rèn)為是對(duì)該STARK系統(tǒng)的成功攻擊。（有密碼學(xué)背景的人可能會(huì)對(duì)，STARK所滿足的更強(qiáng)安全概念——“knowledge soundness”，感興趣。為簡(jiǎn)化表述，本文關(guān)注更簡(jiǎn)單的soundness?！発nowledge soundness”知識(shí)具體可參見Eli Ben-Sasson等人2016年論文 Interactive Oracle Proofs。）

如何來正式定義某STARK系統(tǒng)的安全性呢？：

• 通過粗略計(jì)算，攻擊者構(gòu)建成功攻擊所需的“cost（開銷）”，來分析“soundness error”。即，找到某能讓STARK Verifier接受的 false statement的 STARK proof。
• 從數(shù)學(xué)上說，“soundness error”對(duì)應(yīng)為某函數(shù)$(t)$：
  • 其輸入為時(shí)間參數(shù)“$t$”，代表攻擊者發(fā)起攻擊所需的計(jì)算時(shí)長(zhǎng)。
  • 其輸出為攻擊者攻擊成功的概率。所謂攻擊成功，是指找到了某false statement讓人信服的proof。
  • 若攻擊者愿意花費(fèi)的“cost（開銷）” $t$越大，則其攻擊成功的概率將增加。

為此，可將STARK安全性定義為函數(shù)$(t)$：

• 其不同于在crypto Twitter上討論安全性的自然方式。

如，對(duì)于“本方案具有96位安全性”這樣的陳述，如何將其轉(zhuǎn)換為安全性定義？
答案是不唯一的，因?yàn)槿藗儗?duì)“$x$-位安全性”的理解有細(xì)微差異：

• 1）版本1：嚴(yán)格意義上來說：是指，對(duì)于任意的$t\in [1,2^{96}]$，該soundness error為$(t)2^{96}$。即，對(duì)于任意運(yùn)行時(shí)長(zhǎng)最多為$2^{96}$的攻擊者，其成功的概率很小，小于$2^{96}$——即小于 “10億??10億??10億”。
• 2）版本2：寬松意義上來說（或是更通用版本）：$96$-位安全性，是指對(duì)于任意的$t$，對(duì)$t/(t)2^{96}$其成立。即意味著，成功概率與運(yùn)行時(shí)長(zhǎng)呈（inverse）線性關(guān)系。如，某攻擊者的運(yùn)行時(shí)長(zhǎng)為$2^{86}$，則其成功的概率最多為$2^{10}$。

本文基于上面的版本2來分析。

3. 由IOPs 到 具有96-位安全性的STARKs

如何來證明某方案具有96位安全性呢？
需先理解如何構(gòu)建STARKs的高層結(jié)構(gòu)。

STARK主要有3大要素：

• 1）an IOP（interactive oracle proof）
• 2）a Merkle tree
• 3）a Fiat-Shamir hash

一旦定義了這3大要素，就可將其編譯生成某STARK

本文主要關(guān)注IOP。同時(shí)將詳細(xì)說明這3大要素，以及如何將它們組合在一起。

3.1 IOP

IOP類似于表中的interactive proof，其中某Prover和Verifier多輪交互。（本文限定為public-coin協(xié)議，即Verifier僅需給Prover發(fā)送random challenges）。

在IOP中，Verifier不讀取完整的Prover消息，而是僅從每個(gè)Prover消息中采樣少量bits。從而可實(shí)現(xiàn)后續(xù)編譯出的STARK的簡(jiǎn)潔性。

3.2 由IOP到STARK

有IOP之后，如何基于該IOP構(gòu)建某STARK呢？

• Prover消息可能很長(zhǎng)（事實(shí)上，其要長(zhǎng)于計(jì)算本身）。
• 為壓縮消息，會(huì)使用Merkle tree。
  • Merkle tree是二進(jìn)制哈希tree，每個(gè)葉子節(jié)點(diǎn)代表IOP的某query或某answer。
  • Merkle tree root為對(duì)整個(gè)消息的承諾值。
  • 當(dāng)Verifier想要讀取該消息的某特定位置時(shí)，Prover會(huì)提供該位置的值以及相應(yīng)的認(rèn)證路徑。Verifier可使用該路徑來驗(yàn)證該值的正確性。
  • IOP Verifier僅需讀取Prover消息的少量位置。從而使用Merkle tree構(gòu)建了succinct且具有少量通訊的協(xié)議。

4. Compressing Rounds

對(duì)于交互式STARK，為簡(jiǎn)化流程，通常會(huì)將其轉(zhuǎn)換為非交互式的，這樣在構(gòu)建時(shí)Prover就無需再等待外部消息。事實(shí)上，當(dāng)前所部署的所有STARK系統(tǒng)，包括ethSTARK協(xié)議，都是非交互式STARK。

非交互式STARK也是transparent SNARKs的一個(gè)特例（所謂transparent，是指在實(shí)例化時(shí)無需trusted setup，又名“Arthur Merlin protocol”或“public coin IOP”）。最終，最后一步是應(yīng)用Fiat-Shamir來將rounds壓縮為單個(gè)消息，稱其為STARK proof。

Fiat-Shamir轉(zhuǎn)換會(huì)將交互式協(xié)議轉(zhuǎn)換為非交互式協(xié)議：

• Prover 通過“talking to a hash function”來模擬交互協(xié)議。為派生第$i$輪的隨機(jī)挑戰(zhàn)值，Prover需對(duì)直到第$i$輪的所有transcripts都進(jìn)行哈希，將相應(yīng)的哈希輸出結(jié)果作為下一挑戰(zhàn)值。
  這樣可確保Prover在生成挑戰(zhàn)值之后無法改變其responses。

然而cheating Prover有一些新的（交互式IOP所沒有的）策略手段。cheating Prover可通過修改最后一條Prover消息（這將給出新的transcript，從而給出新的挑戰(zhàn)值），來重新生成Verifier挑戰(zhàn)值。由此可知，IOP的標(biāo)準(zhǔn)可靠性概念不足以證明Fiat-Shamir轉(zhuǎn)換的安全性。

如，考慮一個(gè)有96輪的IOP，對(duì)Verifier進(jìn)行如下“hack”：

• 若96輪中，Verifier的每個(gè)隨機(jī)值的第一位是0，在該Verifier接受（而根本不看proof）。

一旦對(duì)Verifier添加了該hack，其僅給IOP的soundness error加了一項(xiàng)$2^{96}$。但是，經(jīng)Fiat-Shamir轉(zhuǎn)換之后，攻擊者很容易通過修改Prover消息，來確保每個(gè)哈希結(jié)果以0開頭，從而在很短時(shí)間內(nèi)破解該系統(tǒng)。

不過請(qǐng)放心，這僅僅是個(gè)理論示例，而不適用于已部署的STARK。

為何StarkWare的STARK是安全的呢？
簡(jiǎn)而言之，將展示最多允許$n$步的攻擊者，其攻擊成功的概率最多為$(t)t{2}^{96}$。

4.1 IOPs and Round-by-Round Soundness

STARK僅可與其底層的IOP一樣安全。但是，某IOP具有96位安全性，意味著什么？
標(biāo)準(zhǔn)定義應(yīng)是：該IOP的soundness error為$2^{96}$，即意味著，任何攻擊者（不考慮運(yùn)行時(shí)長(zhǎng)）愚弄Verifier的概率最多為$2^{?96}$。

但是，正如之前所討論，STARK由3大要素組成，IOP soundness只是三者之一，其并不足以讓由三大要素所編譯的STARK也具有96位安全性。

事實(shí)上，所編譯的STARK的安全性證明，是假定該STARK具有96位 round-by-round soundness error（有時(shí)，也稱為state-restoration soundness）。

直觀來說，round-by-round soundness error是指：

• 每輪的安全性為96位，而不僅是整體協(xié)議的安全性是96位。

更具體來說，round-by-round是指：

• 存在某predicate，已知該協(xié)議的某partial transcript，可告知該transcript是否是“fooling”的。
  • empty transcript不是“fooling的”。
  • 當(dāng)且僅當(dāng)Verifier接受，某full transcript是“fooling”的。
  • 對(duì)于任何不愚弄Verifier的partial transcript，在下一輪中該transcript是“fooling”的概率最多為$2^{96}$。
• 若存在滿足以上屬性的predicate，則稱該協(xié)議具有96位round-by-round soundness（不要求該predicate可高效計(jì)算）。

很多情況下，僅分析了某IOP的soundness，而未分析其round-by-round soundness。
需承認(rèn)的是，很難想到一個(gè)例子——某IOP具有標(biāo)準(zhǔn)可靠性，但不是round-by-round soundness（人為例子除外）。

但是IOP soundness與round-by-round soundness 是有差別的：

• 當(dāng)派生具體的安全上限時(shí)，每個(gè)bit都是有關(guān)系的。
• 為此，為派生嚴(yán)謹(jǐn)具體的上限時(shí)，必須對(duì)IOP的round-by-round soundness 進(jìn)行嚴(yán)謹(jǐn)分析。StarkWare團(tuán)隊(duì)對(duì)FRI協(xié)議以及ethSTARK IOP均做了相應(yīng)的嚴(yán)謹(jǐn)分析。該分析自身不在本文詳述。
  • 具體見2023年2月視頻StarkWare Sessions 23 | The Soundness of FRI | Dan Carmon
• 借助新的分析，可為StarkWare的STARK proof設(shè)置精確的參數(shù)。

round-by-round soundness 可給出所需的保證：

• Prover可多次重新生成挑戰(zhàn)值，但是對(duì)于任意round，其生成“fooling” transcript的概率為$2^{96}$。
  因此，若該P(yáng)rover具有time $t$——用于衡量哈希調(diào)用次數(shù)，則其最多可嘗試$t$次來試圖獲得某“fooling” transcript，從而限制其成功概率為$(t)t{2}^{96}$。

5. Adding All the Error Terms

最后，需確保Prover無法對(duì)Merkle tree進(jìn)行攻擊。只需要構(gòu)建Merkle tree所使用的哈希函數(shù)不存在碰撞即可。

攻擊者對(duì)某隨機(jī)函數(shù)調(diào)用$t$次，嘗試找到某碰撞的概率，最多為$t2/2$。其中$t2$為該哈希函數(shù)的輸出長(zhǎng)度（基于“生日悖論”）。這也是為何需設(shè)置哈希函數(shù)的輸出長(zhǎng)度，應(yīng)為所需安全性的2倍。

若有某哈希函數(shù)的輸出長(zhǎng)度為192，且某IOP的round-by-round soundness為96位，則所編譯的STARK的soundness error為$(t)=t{2}^{96}+t2?2^{196}$。最終該STARK方案的安全性為95位，因$t/(t)=t/(t{2}^{96}+t2?2^{196})=1/2^{96}+1/2^{96}=2^{?95}$。

6. 總結(jié)

STARK proof system (Scalable Transparent Argument of Knowledge)是用于證明計(jì)算完整性（CI，computational integrity）的強(qiáng)大工具：

• 支持以trustless方式，來驗(yàn)證基于某公開數(shù)據(jù)的計(jì)算的正確性。

STARKs的安全性通常以“soundness error”來衡量，其代表了攻擊者成功為某false statement提供讓Verifier信服的proof 的概率。

為實(shí)現(xiàn)所需的安全性，如96位，底層的IOP必須滿足round-by-round soundness，以確保每輪都維護(hù)高級(jí)別安全性。

StarkWare團(tuán)隊(duì)分析了ethSTARK底層的round-by-round soundness，從而可派生出具體的安全上限。

參考資料

[1] StarkWare團(tuán)隊(duì)2023年10月博客 Safe and Sound — A Deep Dive into STARK Security文章來源地址http://www.zghlxwxcb.cn/news/detail-767920.html

到了這里，關(guān)于深入探索STARK的安全性和可靠性——STARKs全面安全分析的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！