最近大熱的Truebit到底解決了什麼問題？

原文標題：《 Truebit: the marketplace for verifiable computation 》 

原文作者： Sina Habibian 

翻譯來源：以太坊愛好者

翻譯作者： 安仔 Clint & 閔敏

去中心化應用程序向我們描繪了美好的未來圖景。它們透明度高且具有防篡改性，永不停歇地運行著，在全球範圍內釋放激勵並解決協調性問題。

但發展的道路上也有阻礙。

去中心化的計算十分昂貴，受區塊 Gas 上限的限制，致使許多去中心化應用變得十分昂貴和不切實際。

難題：去中心化的計算

使用 Solidity 編寫的代碼會在 EVM（以太坊虛擬機）中編譯為位元組碼，然後打包到區塊鏈中。自此之後，每一筆向存儲著位元組碼的合約地址發送的交易都會觸發代碼的運行。由此可以看出，區塊鏈共識機制在設計上存在冗餘：所有的礦工進行一樣的計算，然後對結果達成共識。

計算被量化，相應地費用也是視代碼執行的複雜程度決定的。區塊鏈虛擬機指令集中的每個操作都被標好價格（稱之為「Gas」），交易的發送者每執行一個指令，都會根據計算量來支付費用。

但凡複雜的業務邏輯，總會帶來高昂的成本。

不止如此，在網路上進行的計算總量會受 Gas 上限的影響。Gas 上限是指在一個區塊中所有交易能消耗的 Gas 總量。不幸的是，由於存在驗證者困境的問題，我們不能單純地增加 Gas 上限；礦工一旦接收到一個剛剛形成的區塊，就需要先驗證這個區塊是否有效，才能開始尋找下一個區塊，但是這樣的驗證是免費的勞動。受利益驅動的礦工處在了一個兩難的境地：驗證這個區塊還是直接跳過它。而當區塊的 Gas 上限增加時，這種困境的影響也隨之變大了。

所以說計算是昂貴且受限制的。

Turebit 旨在解決這一問題。

它通過將計算移到鏈下來解決這一問題，並通過一種互動式的加密經濟協議來驗證計算的正確性。

解決方案：鏈下的可驗證計算

當一個 dApp（去中心化應用程序）想要運行昂貴或是超過 Gas 上限的計算時，與其直接在以太坊上運行計算，不如交給 Truebit 協議。

Truebit 合約

和 Truebit 協議進行交互的 API 十分簡單：它僅僅是 Truebit 智能合約上的一個叫做 createTask 的函數。

dApp 調用 createTask 函數的過程需發送以下內容：

· 程序：程序代碼。Turebit 使用的是 WebAssembly 虛擬機技術，所以 dApp 能直接將程序代碼的位元組碼發送給 WebAssembly 虛擬機，或者發送該程序代碼在 IPFS 或其他基於內容定址的系統上的哈希值。

· 輸入值：針對程序的輸入值。dApp 能直接發送這些輸入值，或是發送這些輸入值在基於內容定址的系統上的哈希值。

· 獎勵：獎勵金額，提供給任何運行這個程序的人

一個 dApp 創建了一個 Truebit 任務

為了進一步說明這個流程，下面我們來看兩個例子。

Livepeer 是一個去中心化計算平台，它需要檢查轉碼器是否正常工作。於是它調用了 createTask 函數，將 FFmpeg 作為程序、一段視頻作為輸入值發送給了該函數。

Aragon 是一個匿名組織的平台，它想進行計票的工作。在鏈上循環進行大批量的投票工作是十分昂貴的，而且如果計票的數量太多，Gas 上限就會阻礙這項工作的進行。於是 Aragon 調用了 Truebit 的 createTask 函數，將計票函數作為程序、票數數組作為輸入值發送給了該函數。

這個函數會在 Truebit 合約中生成一個新的任務。

Truebit 網路

Truebit 是一個計算任務市場。

任何人都能安裝 Truebit 客戶端，加入無門檻的網路中，然後通過運行計算任務來獲取報酬。

Truebit 礦工所安裝的客戶端會監聽 Truebit 合約所發出的事件。

Truebit 礦工監聽計算任務

一旦生成新的任務，Truebit 礦工能下載其代碼，然後使用任務發布者提供的輸入在本地 Truebit WebAssembly 虛擬機中運行程序，接著將自己的結果發送給智能合約。

承接計算任務的同樣要交納押金，用於保證任務處理人對自己的計算結果負責。

 任務處理人提交結果  

計時器啟動。在挑戰限時之內，任何 Truebit 驗證者都能在交納押金的前提下挑戰已提交的計算結果。

第一種情況：沒有挑戰者

這是符合預期的情況。任務處理人正確地運行了程序。如果在整個挑戰時限內，沒人對已有計算結果提出異議的話，即認定為正確結果。Truebit 合約會使用該計算結果去回調發起任務的 dApp。

 任務發起人收到問題的答案  

第二種情況：有挑戰者

一個驗證者交納了押金，對當前的計算結果發起了挑戰。現在對計算結果產生了分歧。對合約而言，它不但保管著任務發起人所提供的原始任務獎勵，還保管著任務處理人的押金，以及挑戰者的押金。

 一個驗證者發起了挑戰

由此在任務處理人和挑戰者之間展開了一場互動式驗證遊戲。

驗證遊戲

要注意的是 Truebit 任務是一個 WebAssembly 程序，會按順序執行一系列指令。

一個簡單的 C 程序（圖左）及其編譯後的 WebAssembly 文本形式（圖右）

挑戰者發起了驗證遊戲。

任務處理人和挑戰者的初始狀態都是 0，他們各自啟動了一個空的虛擬機，用同樣的程序運行同樣的輸入（如區塊鏈上的任務描述中所規定的那樣）。在狀態為 0 的時候，他們是一致的。

在程序運行的終點，我們假設是在運行了 14 個指令之後，他們計算出了不同的結果。也就是說，在狀態為 14 時，任務處理人和挑戰者出現了分歧。

任務處理人和挑戰者在狀態為 0 時計算結果一致並在狀態為 14 時發生了分歧

挑戰者根據這一信息來查詢任務處理人在程序運行到一半，即運行完第 7 個指令之時的狀態。

挑戰者查詢任務處理人的狀態

任務處理人可以利用 Truebit 的 WebAssembly 虛擬機來計算己方狀態的哈希值。它是由任務處理人的 WebAssembly 虛擬機的堆棧、內存和完整狀態導出一個默克爾樹根。任務處理人會通過一個 Respond（答覆）消息將這個根提交至智能合約。

 任務處理人和挑戰者進行驗證遊戲

現在輪到挑戰者在本地計算己方狀態的默克爾樹根，並且將結果和任務處理人的結果進行比較。

如果兩根相等，就能判斷他們出現分歧的位置是在計算指令集合的後半部分。如果兩根不等，那麼他們的分歧在集合的前半部分就發生了。

為了便於說明，我們現在假設狀態為 7 時這兩個根是相等的。  

挑戰者和任務處理人在狀態為 7 時狀態根相等

 挑戰者於是發送一個 Query（查詢）消息，詢問任務處理人在計算指令集合後半部分的中點，即運行完第 10 個指令後，的狀態根。  

 挑戰者詢問集合內第二個中點的狀態根

任務處理人據此做出相同的回應。

挑戰者發現在狀態為 10 之時兩方的狀態根相同，於是接著查詢下一個中點，即狀態為 12 之時，的狀態根。

挑戰者查詢第三個中點的狀態根

互動式驗證遊戲繼續進行。

挑戰者使用二叉搜索的方法迫使任務處理人找到出現分歧的狀態的位置。整個遊戲的時間複雜度為 O(log(n))，其中 n 是程序中指令的總數。根據任務處理人提交的指令發生前後的狀態根，最終將分歧發生的位置鎖定在某一個指令處。

爭論：從 狀態 12 轉變為 狀態 13 時的那個指令

 現在的計算量已經小到足以讓 Trubit 智能合約根據指令執行前的狀態來初始化一個虛擬機，然後在區塊鏈上運行那個產生爭議的指令。  

 鏈上 WebAssembly 解釋器運行有爭議的指令

如果該狀態的默克爾根計算出來和任務處理人提供的狀態根不同，後者的押金就會被沒收。

整個過程就是這樣！

我們把所有的計算都移到鏈下進行，僅使用以太坊來計算那個單步指令，以防出現爭議。

通過上述方式，我們對最終結果達成了共識，不過這種共識比中本聰的要求大多數人要誠實，BFT 的要求三分之二的人誠實更強。我們得到了一種「沒有爭議的共識：只要有一個誠實的驗證人，就能保證系統的安全。

 加密經濟學

Truebit 的激勵包括任務獎勵、押金、任務處理人和挑戰者之間的挑戰機制以及計算市場的經濟設計。

最近我們公布了 Truebit 代幣的升級計劃，以下是目前考慮使用的兩種解決方案：

 激勵層一：強制出錯 & 累積獎池  

  仔細地研究這個協議，一些敏銳的讀者可能會發現一個問題。

任務處理人明白自己的計算結果會受到檢查，而且如果出錯，會被沒收押金，因此不會作弊。長此以往，驗證者極難發現錯誤，無法獲得收入，最終在計算市場中消失。在驗證者消失之後，任務處理人就會開始作弊了。然後，驗證者會再度出現，把錯誤揪出來。

這個系統並不處在一種穩定的平衡之中，而是經常上下翻轉的。

為了解決這個問題，Truebit 在白皮書中提出了一種強制出錯（forced error）和累積獎池（jackpot）的概念。Truebit 協議會在一定概率下強制任務處理人提供錯誤的計算結果。凡是發現這類錯誤並挑戰成功的驗證者都將自動收到一份累積獎金。這筆意外之財的獎額是從所有任務的獎勵中抽取的，因此十分巨大，為驗證者提供了可觀的預期收益。即使任務處理人總是提供正確的計算結果，驗證任務也是有利可圖的。

 激勵層二：多個任務處理人和結對驗證挑戰  

 另一個替代方案來源於具體實施過程。任務處理人和驗證者總是做著一樣的工作：他們下載相同的程序，在本地運行，然後得到計算結果。那麼與其按照時序規則來規定一個任務處理人和多個挑戰者，為什麼不改變協議，允許每個人在同一時刻提交自己的計算結果呢？

智能合約會檢查所有的計算結果是否一致。如果一致，就認為結果是正確的。如果不一致，且產生了幾類計算結果的話，智能合約會組織不同類的任務處理人進行結對驗證。

這種改進的協議能更好地保證時效性，因為驗證挑戰是並行的。這種改進也能替代強制出錯和累積獎池。但不足之處在於增加了任務發起人應支付多少獎勵以及多個任務處理人之間如何分配獎勵等問題的複雜度。

我們正在努力研究如何改進協議（歡迎向 Zack Lawrence 和 Ali Yahya 的推特提出一些有建設性的建議！）

 模塊化架構  

 Truebit 是一個模塊化系統，可分為以下三個層次：

 Trubit 的模塊化架構

計算層：即 WebAssembly 虛擬機（或者說是一個有限狀態機，就像我們在使用互動式 scrypt 設計 Doge-Ethereum 轉換橋中所用到的那樣）它需要鏈上和鏈下雙重的建設。

Truebit 的 WebAssembly 解釋器具有確定性和可計量性，能夠生成內部狀態的默克爾樹。

爭議解決層： 這是一個兩方間的互動式驗證遊戲，包括任務處理人和驗證者之間多次的互動式問答。

激勵層：這一層包括獎勵、押金、任務處理人和挑戰者之間的挑戰機制，以及代幣機制。各層之間會通過定義好的介面進行交流。

 結語

我們的工程方向目前聚焦於計算和爭議解決層。我們的調研主要針對激勵層和代幣機制。

最近我們公布了針對 Scrypt 驗證的 Truebit 解決方案，它在 Doge-Ethereum 轉換橋中得到了應用。

可以點擊這裡觀看我們的 demo 視頻，或者在 Github 上查閱我們的代碼。

我們的下一版視線中就會支持 WebAssembly VM。

敬請期待！