从并发视角来看智能合约（上）【渡鸦论文系列】
論文作者：
Ilya Sergey1and Aquinas Hobor2
1 University College London, United Kingdomi.sergey@ucl.ac.uk
2 Yale-NUS College and School of Computing, National University of Singaporehobor@comp.nus.edu.sg
翻譯：渡鴉
「讓國內外的區塊鏈技術沒有時差」。
寫在【新欄目】前面：
翻譯論文無比痛苦。
但是我們的目標是「讓國內外的區塊鏈技術沒有時差」。
帶給大家更多區塊鏈技術干貨。
能力有限，還請各路大神多多監督、指教。
歡迎投稿、中英文均可。
摘要：
在本文中，我們探討了諸如Ethereum等智能合約的多事務行為與共享內存并發的經典問題之間的顯著相似之處。我們從Ethereum區塊鏈中檢查兩個真實世界的例子，并分析它們是如何容易受到與傳統并發程序中經常出現的錯誤的影響。然后，我們詳細闡述可觀察的合約行為與已深入研究的并發主題之間的關系，如原子性，干擾，同步和資源所有權。描述的并發對象類似的類比可以更深入地了解智能合約的潛在威脅，指導實踐，并使用現有的最先進的形式驗證技術。
1、介紹：
智能合約是存儲在區塊鏈上，拜占庭容錯數據庫的程序。智能合約可以通過區塊鏈交易觸發，并在其塊上讀取和寫入數據[38] 。雖然智能合約以分布式方式運行和驗證，但是盡管存在許多復雜的交互模式，包括例如重入和遞歸調用，但它們的語義表明可以將它們視為順序程序。這種心理模型簡化了關于合約的正式和非正式推理，使得可以立即重用現有的通用框架來進行程序驗證[5，16，31，32] ，可用于驗證例如寫入的智能合約。固化[15] 只有微小的調整。
雖然區塊上的所有計算都是確定的[1]，但由于交易本身之間的競爭（如為某個給定的區塊選擇了哪些交易），所以仍然會發生一些非確定性的計算。我們將展示，非決定論可以被敵對方利用，并對合約行為進行推理，特別微妙，讓人想起傳統并行編程中涉及的已知挑戰。
在本文中，我們概述了智能合約的并發執行屬性。這種執行可以跨越多個區塊鏈交易（在同一個塊內或多個塊中），從而違反了僅使用合約的實施和本地狀態而不能指定的所需安全屬性，正是現有驗證方法所關注的[5, 32] 。為了便于共同編程的重用，我們提出以下類比：
在區塊鏈中使用智能合約的帳戶就像在共享內存中使用并發對象的線程。
在共享內存中使用并發對象的線程。通過并發對象，我們意味著用于在同時運行的多個線程（進程）之間交換數據和管理交互的大量數據結構[20] 。并發對象的典型示例是區塊，隊列和原子計數器 - 通常通過諸如java，util，concurrent的數據庫使用。同時，在運行時，這些并發對象被分配到正在運行的線程可訪問的共享內存塊中。由線程同時訪問對象而產生的行為 - 即干擾是難以預測的，因此極難理解。
其不利用適當同步的并發對象（例如，具有鎖定或障礙物）可以在干擾下會出現數據競爭[2]行為，導致內存完整性的喪失。即使對于無競爭對象，在一個或多個客戶端的觀點下，觀察到的干擾行為可能是錯誤的。例如，特定的線程可能不會“預見”具有共享對象的其他線程采取的動作，因此可能不會期望該對象以干擾方式改變。
帳戶使用智能合約塊。智能合約類似于并發對象。他們儲存在塊狀物中而不是一個共享的記憶中; 不是由線程使用，而是由帳戶（用戶或其他合約）調用。像并發對象一樣，它們具有內部可變狀態，管理資源（例如資金），并且可以在塊內和多個塊中的多方訪問。與傳統并發對象不同，由于計算的事務模型，智能合約的方法而是原子的。也就是說，合約的單一調用（或一系列調用一系列相互調用的合約）是有序執行 - 沒有中斷 - 并且在成功更新區塊鏈之后終止或者中止并且回到之前的配置。
然而，“原子性自由”的概念是欺騙性的，因為在區塊鏈的水平上仍然可以觀察到并發行為：
- 在交易執行時，包含在交易中的交易的順序并不確定，因此，結果可以在很大程度上取決于其他交易的排序[27].
- 幾個編程任務需要將合約邏輯分散在幾個區塊鏈交易中（例如，當合約與塊之外的世界進行“通信”時），從而實現真正的并發行為。
- 調用其他合約可以被認為是一種多任務合作。通過協同多任務，多個線程可以運行，但不要中斷，除非它們明確地“產生”。也就是說，從合約A到合約B的呼叫可以被認為是從合約A的角度來看的收益，合約B在返回時收益。智能合約的關鍵在于，合約B可以運行合約A的設計者無意識到的代碼，這使得情況比典型的順序設備更接近并發設置。[3]特別地，合約B可以在調用期間修改合約A可能承擔的狀態。這是DAO錯誤[9]，的精髓，合約B在返回[27]之前調用合約A來修改A的本地狀態。然而，重入并不是表現出來的唯一錯誤，因為：
- 不難想象某種合約被用作其他區塊（用戶和合約），管理對共享資源的訪問以及在某種意義上作為并發庫的場景。隨著多重交易變得越來越普遍，各種觀察到的干涉模式，也應該考慮在內。
我們的目標和動機。幸運的是，在過去三十年中進行的并行和分布式編程的研究為大量的理論和應用框架提供了代碼，指定，理由和正式驗證并發對象及其實現的框架。因此，本文的目標是雙重的。首先，我們將簡要概述在智能合約中可能發生的一些已知的并發問題，在更傳統的并發抽象方面表征問題。第二，我們的目標是建立一個直觀的“良好”和“不良”的合約行為，可以相應地識別和驗證/檢測，使用現有的正式方法推理并發。
2.并發行為示例
在這里，我們討論了已經部署在Ethereum塊上的兩個合約，每個合并都說明了并發類型行為的不同方面。BlockKing的合約，像今天的Ethereum集團許多其他人一樣，實現了一個簡單的賭博游戲[2]。雖然BlockKing使用不廣泛，但我們研究它是因為它展示了Oraclize服務的潛在用途[4]，這是一種允許合約與塊之外的世界進行通信的服務，從而了解真正的并發性。由于Oraclize服務的早期采用者將其作為該服務的演示，并將其源代碼免費提供，希望使用Oraclize的許多其他合約可能會在其實現中反映出來。
我們討論的第二個例子是DAO中廣泛研究的錯誤[1]。 DAO與18,000多名投資者建立了一個業主管理的風險投資基金;它吸引了當時存在的14%的以太幣。隨后的攻擊使投資者花費了大約360萬Ether，當時價值約5000萬美元。 DAO采用了我們所說的“不協調的多任務”，因為當DAO向收件人發送錢時，那個接收者能夠運行代碼，通過DAO的合約狀態來干擾DAO的合約狀態，假設DAO在調用期間不會改變。
2.1BlockKing合約
BlockKing的賭博如下。在任何時候，都有一個指定的“塊王”（最初是合約的編者）。當發送方將貨幣發送到合約時，在1到9之間生成隨機數j。如果當前塊號10等于j，則s成為新的塊王。之后，BlockKing在合約中收到了一定比例的資金（根據不同的參數，從50％到90％），合約的編者將收到余額。
在確定性系統中，生成優質隨機數是很困難，特別是在所有數據被公開存儲的情況下，而且對于攻擊者來說，都有經濟激勵。因此，BlockKing利用信任方WolframAlpha的服務，使用Oraclize服務生成其隨機數。假設Oraclize是很好的行為，這個隨機數選擇的策略應該是攻擊者的預測。
BlockKing的代碼有365行，但是在圖1中給出的代碼十分有趣; 這里的行號是由Etherscan[2]給出的合約的實際源代碼。當貨幣發送到合約時，輸入函數被調用。它設置一些合約變量（行 299-301)），然后發送查詢到Oraclize服務(行 303)。
圖1.BlockKing代碼片段[2]
oraclize_query函數引發一個事件在“真實世界”中可見，然后返回到其調用者，然后退出(行 304)。在現實世界中，Oraclize服務器監視事件日志，服務請求（在這種情況下通過聯系WolframAlpha Web服務），然后在指定的回調點（BlockKing中的行 306 ）對原始合約進行新的調用。在事件和其回調之間，可能會發生許多事情，在這種意義上，塊調用可以在調用oraclize_query之前推出幾個塊，并在回調時恢復控制。在此期間，塊狀態，甚至BlockKing合約本身的狀態可能會發生巨大變化。換句話說，這是塊上的真正并發行為。
什么可以出錯？假設多個賭徒希望在短時間內嘗試運氣（甚至在同一個區塊內）。合約沒有嘗試追蹤這種行為。因此，每個新的參賽者都將覆蓋第s 299-301行中的上一個數據（關鍵warrior塊和warrior變量）。當回調最終發生時，批次中的最后一名參賽者將享有多次機會，以贏得該批次中參加其他回調的參賽者的寶座。罪魁禍首是來自process_payment函數的第 339-347 行，稱為行309中的回調函數的最后一行。
每次process_支付函數被稱為warrior區塊的最低有效數字被計算并存儲到變量singleDigitBlock中.[4]。每次調用process_支付函數時，他都有一個新機會匹配第339 行中的隨機數。如果數字匹配，則最后的參賽者在第345行加冠。
2.2DAO合約
DAO的源代碼有1,239行，比BlockKing更復雜[[23]由于這個bug已經寫得很多了（例如[9，27])），所以我們僅在圖2中給出了關鍵行。問題是第1012行的順序，（通過一系列進一步的函數調用）將Ether發送到msg.sender，在1014 行，將零余數的msg.sender的帳戶為零。
圖.2.?DAO代買片段[23]
在順序程序中，重新排序兩個獨立的操作對程序的最終行為沒有影響。然而，在并發程序中，順序無害的重新排序的效果可以具有顯著的效果，因為操作發生的順序可以影響線程如何干擾。在DAO中，在第1012 行中發送Ether，在某些多任務的意義上，產生“位于msg.sender的任意（潛在的惡意）合約的控制。
不幸的是，DAO內部狀態仍然表明該賬戶由于其賬戶余額在第1014 行尚未清零而得到資助。因此，惡意msg.sender可以通過回調DAO合約來啟動第二次撤回，該協議將在當控制再次到達1012行時，轉一次付款。事實上，惡意的msg.sender可以啟動第三，第四等撤回，所有這些將導致付款。只有在支付原始余額的許多倍數之后，最終他的賬戶被清除。
以前對此bug的分析表明，問題是在于遞歸或意外的重入。在狹義上，這是真的，但在更廣泛的意義上，正在發生的是順序代碼在并發環境中運行的意義。
3干預和同步
3.1共享內存并發中的原子更新
圖3描述了錯誤使用的并發對象的示例（以類似Java8的偽代碼呈現），該實例應該使用get和set方法實現“原子”計數器。由于使用了同步原語，左邊的并發計數器的實現顯然是線程安全的（即無數據競爭）[17] 。然而，有問題的是，在右側的多線程客戶端代碼中如何使用Counter類的實例。
圖. 3. 并發計數器（左）及其雙線程客戶端應用程序（右）
具體來說，有兩個線程并行運行并且它們的操作分離，對線程2的body內的incr（）的調用可能會發生在例如在a中的賦值與a之間的調用c.set（a + 1））調用thread1。這將使以下assert語句中的條件無效，使得整個程序對于某個執行失敗！
出現這個問題是因為在計數器之上的incr（）的實現沒有提供客戶端代碼預期的原子性保證。具體來說，右邊的代碼是假設incr（）的語句之間不會有任何干擾的，因此計數器c將被增加1，a和b將在也是一樣的。實際上，并發的運行線程2并不總是這樣，不僅a和b將不同，所以后來的c.set（）調用也將“覆蓋”早期的結果。
與提供incr（）的原子實現相比，更好的Counter的設計實現可以提供通過顯式鎖定或通過Java的同步關鍵字，fetch-and-increment操作[20，§5.6]來實施。然而，給定唯一的兩種方法是獲取和設置，Counter的實現具有一個原子寄存器的同步屬性，該原子寄存器的共識號[20，§5.1]（即可以明確地同意get和 set）正好是1.因此，而不依賴于一些額外的同步，不給予某些預先設定的線程的優先級，通過僅使用get和set來實現c的原子增量是根本不可能的。
也許有點令人驚訝的是，盡管圖3的Counter的實現本身并沒有缺陷，但是它的弱原子性質使得它在無限數量的線程的存在下變得無用，使得實際上不可能做出任何穩定的（即，有彈性的關于并發變化）關于其內部狀態的假設。
3.2并發區塊鏈交易中的原子更新
圖4的左邊部分顯示了一個在Solidity[15]中實現的智能合約，其功能和方法讓人聯想到原子并發計數器的功能和方法。函數get允許一個查詢與當前余額相關聯的合約，與一些固定的地址id相關聯，而集合函數可以通過msg.value從消息中獲取新的余額來更新余額，發回舊的數量和因此返回。
圖.4.計數器合約（左）和同步testAndSet方法（右）
既然獲取和設置的兩個實體將在一些事務的過程中按順序執行，那么既不需要同步它們，在Solidity也沒有任何明確的方法。然而，不難看出，作為最簡單的可能存儲（例如，對于某些id相關資金）的實現，由多個不同方使用以更新其平衡，計數器合約與其對應的圖中的Java對應，看圖3。
例如，假設雙方不知道彼此試圖增加一個數量的計數器存儲的某個值。由于合約不能為他們在一個操作中提供一種方法，所以他們必須首先通過獲取查詢數量，然后嘗試通過設置函數來改變它，遵循與圖中實施incr相同的模式。實際上，這兩個調用都可以在單個事務中實現。但是由于天然氣需求有限，在執行過程中不宜調用多個外部合約。此外，獲取的調用可以由塊的外部的客戶端執行，這意味著獲取和設置的連續調用將最終在兩個不同的事務中。如果是這種情況，這些調用可能會干擾多方嘗試同時修改Counter的其他事務。我們將面對一個常見的問題：不能從本地觀察中預測調用函數集的結果。
在共享存儲器和塊狀情況下，問題的原因是缺乏強大的同步原語，允許在同時執行的情況下同時觀察和操縱計數器。該問題的一個解決方案是增加計數器的原子可能性，使用testAndSet函數增強計數器（圖4的右側部分）。該功能實現了類似于比較和交換原語[20，第5.8節]（在Intelx86和Itanium架構上稱為CMPXCHG）的檢查/更新邏輯，作為實現多線程之間同步的一種方式。已知testAndSet（和其他一些類似的Read-Modify-Write原語）的一致數量為∞，因此它足夠強大，允許任意數量的并發方與操作的結果一致。
關于正式推理和驗證的注意事項。運行時并發驗證的方法基于探索動態執行跟蹤和總結其屬性，為檢測違反原子性假設和缺乏同步提供了有效的工具[26]。例如，通過將我們的合約轉換為相應的共享內存并發對象，可以使用現有工具來總結其跟蹤[13]，從而可以觀察到不需要的交互模式。
原文：?https://zhuanlan.zhihu.com/p/29291411
總結
以上是生活随笔為你收集整理的从并发视角来看智能合约（上）【渡鸦论文系列】的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 如何让区块链连接外面的世界
- 下一篇： 从并发视角来看智能合约（下）【渡鸦论文系