Script

與腳本相比,Simplicity 如何更適合靜態分析?

  • April 17, 2020

引自白皮書,Simplicity 的設計目標之一是:

提供形式語義,便於使用現有的現成證明輔助軟體對程序進行簡單推理。

Simplicity 是如何實現比腳本更適合靜態分析的?是位機中的讀寫順序嗎?

對於這個答案,我將主要關注記憶體使用和時間等計算資源的靜態分析。

在 Simplicity 中,我們將 Simplicity 語言和 Bit Machine 語言分開,並將 Simplicity 語言正式翻譯為 Bit Machine 語言(參見白皮書中的圖 2 )。此翻譯已在 Coq 證明助手中正式化。只有 Simplicity 語言在區塊鏈的共識層公開,Bit Machine 在技術上是一個實現細節。這意味著只需要分析 Simplicity 語言。

因為 Simplicity 子表達式只能操作它們的本地數據(即從 Bit Machine 實現的角度來看,Simplicity 子表達式只能操作讀寫堆棧的頂部),我們可以編寫一個簡單的遞歸分析來確定計算成本,例如記憶體使用(參見白皮書中的圖 3 和圖 5 )以及類似的時間資源(尚未實現)。此外,Simplicity 組合子非常簡單,這使得靜態分析變得實用。一種形式的記憶體靜態分析算法已經被 Coq 證明助手驗證正確。

另一方面,Script 帶有一些阻礙靜態分析的缺陷。特別DEPTH是非本地的(即它不是固定數量的堆棧元素的簡單函式),並且IFDUP根據頂部堆棧項的執行時值在堆棧上留下一個或兩個項目。Script 中沒有任何東西可以保證在退出一個IF ENDIF塊時,在任何一種情況下剩餘的堆棧項的數量都是相同的(與 Simplicity 的case組合器相比,它要求兩個分支的結果類型相同)。最後,雖然ROLL、、PICKCHECKMULTISIG通常與常量n(和m)參數一起使用,但沒有任何保證會如此。

所有這些都使得對通用 Script 程序的記憶體使用進行靜態分析變得更加複雜,儘管對於不使用/濫用上述 OP 程式碼的特定普通 Script 程序,分析可能是可行的。

時間分析的故事要好一些,因為 Script 只是遍歷程式碼。雖然ROLL是有問題的,因為它需要 O(n) 的工作。(最近IF修復了 的實現,現在只需要 O(1) 的工作)。簡單組合器每個只需要恆定量的時間,除了iden,它在位機中實現時複製靜態已知數量的位。因為工作量iden是靜態已知的,所以我們可以將其納入我們的分析中。

Simplicity 旨在使計算資源的靜態分析比腳本更容易,同時提高語言的實際表達能力。

作為參考,我知道的SCRIPT Analyzer簡化了關於腳本操作的假設(例如,傳遞給 OP_IF 的值是 0 或 1)。另一方面,SCRIPT Analyzer進行完整的符號分析,而不是時間和空間資源分析。這樣的符號分析對於 Simplicity 程序可能並不實用。相反,人們期望使用 Simplicity 的形式語義來直接推理 Simplicity 表達式(例如,我們在 Simplicity 中證明了 SHA-256 實現的正確性)。

引用自:https://bitcoin.stackexchange.com/questions/95332