Optimistic Rollups Fraud Proof 成本估算

作者:扎克-赫斯, Zack Hess https://github.com/zack-bitcoin/amoveo-docs/blob/master/other_blockchains/optimistic_rollups_fraud_proof_cost.md

Optimistic rollups式欺詐證明成本估算 #

Optimistic rollups技術評論

爲什麼沒有分片的可用性不能擴展 #

如果我們增加我們可以存儲在共識空間中的可用數據量,但仍然試圖只維護一個單一的每個人的餘額的默克爾樹,我們會遇到縮放限制。就是不可能把元素插入到一個單一的默克爾樹中,並重新計算默克爾的根,超過一定的速度。這種計算有一些方面是不能並行化的。因此,無論我們在網絡上增加多少臺計算機,我們在任何單一的默克爾樹上更新賬戶餘額的速度仍然會有一個上限。

因此,爲了克服這個限制,我們需要維護多個賬戶餘額的數據庫,稱爲分片。我們需要一些較慢的機制來將價值從一個分片中轉移到另一個分片中。

有多少欺詐證明 #


爲了知道你收到的付款是有效的,你需要確認分片的更新是有效的。一個分片的更新只有在該分片之前沒有矛盾的更新纔是有效的。

我們通過激勵證明者產生欺詐證明來發現矛盾的更新。

因此,讓我們說區塊鏈在一段時間內有T個txs,而且它們分佈在許多分片中。有許多證明者在尋找相互矛盾的分片更新,這樣他們就可以從欺詐證明中獲利。

對於每個tx,都會有一個用戶要求提供欺詐證明。

有多少欺詐證明人 #

爲了實現二次可擴展性,我們需要每個驗證人只能下載sqrt(T)個txs的情況。這意味着他們只能下載sqrt(T)個來自用戶的欺詐證明請求,而且他們只能從可用的歷史記錄中下載sqrt(T)個txs。

如果分片的數量與sqrt(T)成正比,那麼這意味着一個只關注一個分片的驗證器只需要查看O(sqrt(T))的許多txs。

我們將需要O(sqrt(T))個欺詐證明器。

欺詐證明的總成本 #

對於每個側鏈,我們可以讓一段時間內的區塊數量與sqrt(sqrt(T))成正比,所以每個區塊中都有O(sqrt(sqrt(T))的許多txs。

對於每個區塊,欺詐證明者需要做log2(sqrt(sqrt(T)))多次比較,看是否有可能做出欺詐證明。

所以成本是O((#證明人)*(#塊)*(每塊的比較)) = O(sqrt(T)*sqrt(sqrt(T))*log(T)) = O(log(T) * T^(3/4))

O(log(T) * T^(3/4))實際上與O(T)是同一回事。

如果我們將T從1增加到10億,那麼每個Tx的成本將只減少約6倍。

結論 #

每個tx的欺詐證明的檢查成本大約是恆定的。如果txs的總數非常小,那麼檢查欺詐的成本就會小於生成簽名的成本。

所以,支付檢查欺詐證明的成本總是小於生成該TX的簽名的成本。

所以欺詐證明的成本永遠不會成爲瓶頸。