【译】From Smart Contracts to Courts with not so Smart Judges
以太坊通常被描述為自我實(shí)施智能合約的平臺(tái)。 雖然這確實(shí)是正確的，但本文認(rèn)為，特別是當(dāng)涉及更復(fù)雜的系統(tǒng)時(shí)，它更像是一個(gè)擁有聰明的律師的法院和一個(gè)不那么聰明的法官，或者更正式的法官，他是一個(gè)計(jì)算資源有限的法官。 稍后我們將看到如何利用這種視圖來編寫非常有效的智能合約系統(tǒng)，以便能夠以幾乎免費(fèi)的方式實(shí)現(xiàn)交叉鏈代幣轉(zhuǎn)移或計(jì)算工作證明等計(jì)算。
法庭類比
首先，您可能知道以太坊上的智能合約本身無法從外部世界檢索信息。 它只能要求外部參與者代表其提供信息。 即便如此，它要么必須信任外部參與者，要么驗(yàn)證信息本身的完整性。 在法庭上，法官通常會(huì)向?qū)＜以儐査麄兊囊庖?#xff08;他們通常信任的人）或證人的證詞，這些證詞通常經(jīng)過交叉核對(duì)驗(yàn)證。
我猜很明顯，由于氣體限制，以太坊中的判斷者的計(jì)算資源受到限制，與來自外部世界的律師的計(jì)算能力相比，這種限制相當(dāng)?shù)汀?然而，以這種方式受到限制的法官仍然可以決定非常復(fù)雜的法律案件：她的權(quán)力來自于她可以扮演辯護(hù)人對(duì)抗檢察官這一事實(shí)。
復(fù)雜性理論
這個(gè)確切的類比在Feige，Shamir和Tennenholtz， Noisy Oracle Problem的一篇文章中正式化。 他們主要結(jié)果的一個(gè)非常簡(jiǎn)化的版本如下：假設(shè)我們有一個(gè)合同（判斷）誰可以使用N個(gè)步驟來執(zhí)行計(jì)算（可能分布在多個(gè)事務(wù)中）。 有幾個(gè)外部演員（律師）可以幫助法官，其中至少有一個(gè)是誠(chéng)實(shí)的（即至少有一個(gè)演員遵循既定的協(xié)議，其他人可能是惡意的并發(fā)送任意信息），但法官不知道誰誠(chéng)實(shí)的演員是。 這樣的合同可以在沒有外界幫助的情況下執(zhí)行可以使用N個(gè)存儲(chǔ)器單元和任意數(shù)量的步驟執(zhí)行的任何計(jì)算。 （正式版本聲明多項(xiàng)式時(shí)間驗(yàn)證器可以接受此模型中的所有PSPACE）
這可能聽起來有點(diǎn)笨拙，但他們的證明實(shí)際上非常有啟發(fā)性，并且使用PSPACE的類比是可以通過“游戲”解決的一類問題。 舉個(gè)例子，讓我告訴你一個(gè)以太坊合約如何下棋幾乎沒有汽油費(fèi)用（專家可以原諒我使用NEXPTIME完成的國(guó)際象棋，但我們將在這里使用經(jīng)典的8x8變體，所以它實(shí)際上是在PSPACE ... ）：在這種情況下下棋意味著一些外部演員提出國(guó)際象棋位置，合同必須確定該位置是否是白色的獲勝位置，即白色總是獲勝，假設(shè)白色和黑色是無限聰明的。 這假設(shè)誠(chéng)實(shí)的脫鏈演員有足夠的計(jì)算能力來完美地下棋，但是......所以任務(wù)不是與外部演員下棋，而是確定給定位置是否是白棋的獲勝位置并且詢問外部演員（除了其中一個(gè)可能誤導(dǎo)，給出錯(cuò)誤的答案）以尋求幫助。 我希望你同意在沒有外界幫助的情況下這樣做非常復(fù)雜。 為簡(jiǎn)單起見，我們只看一下我們有兩個(gè)外部演員A和B的情況。這是合同的作用：
合同并不需要對(duì)國(guó)際象棋戰(zhàn)略有任何線索。 它只需要能夠驗(yàn)證單個(gè)移動(dòng)是否有效。 因此合同的成本大致為N*(V+U) ，其中N是移動(dòng)的數(shù)量（實(shí)際上是ply），V是驗(yàn)證移動(dòng)的成本，U是更新電路板的成本。
這個(gè)結(jié)果實(shí)際上可以改進(jìn)為N*U + V ，因?yàn)槲覀儾恍枰?yàn)證每一個(gè)動(dòng)作。 我們可以更新電路板（假設(shè)移動(dòng)是通過坐標(biāo)給出的），當(dāng)我們要求下一步時(shí)，我們也會(huì)詢問前一步是否無效。 如果回答為“是”，我們檢查移動(dòng)。 根據(jù)移動(dòng)是否有效，其中一名球員被騙，我們知道誰獲勝。
家庭作業(yè)：改進(jìn)合同，以便我們只需存儲(chǔ)移動(dòng)序列并僅為移動(dòng)的一小部分更新電路板，并僅針對(duì)單個(gè)移動(dòng)執(zhí)行移動(dòng)驗(yàn)證，即將成本帶到N*M + tiny(N)*U + V ，其中M是存儲(chǔ)移動(dòng)的成本，而tiny是一個(gè)適當(dāng)?shù)暮瘮?shù)，它返回N的“微小部分”。
在旁注中， Babai，Fortnow和Lund表明，律師正在合作但不能相互溝通的模型和法官被允許擲骰子（兩個(gè)變化都很重要）捕獲了一個(gè)據(jù)稱更大的類NEXPTIME，非確定性指數(shù)時(shí)間。
將加密經(jīng)濟(jì)學(xué)添加到游戲中
從前一節(jié)要記住的一點(diǎn)是，假設(shè)交易沒有受到審查，合同將始終找出誠(chéng)實(shí)的人和不誠(chéng)實(shí)的演員是誰。 這導(dǎo)致了一個(gè)有趣的觀察，我們現(xiàn)在有一個(gè)相當(dāng)便宜的交互協(xié)議來解決難題，但我們可以添加一個(gè)加密經(jīng)濟(jì)機(jī)制，確保幾乎不必執(zhí)行該協(xié)議：該機(jī)制允許任何人提交結(jié)果與保證金一起計(jì)算。 任何人都可以挑戰(zhàn)結(jié)果，但也必須提供押金。 如果存在至少一個(gè)挑戰(zhàn)者，則執(zhí)行交互協(xié)議（或其多證明者變體）。 假設(shè)在提議者和挑戰(zhàn)者中至少有一個(gè)誠(chéng)實(shí)的行為者，那些不誠(chéng)實(shí)的行為者將被揭露，而誠(chéng)實(shí)的行為者將獲得存款（減去一定百分比，這將阻止一個(gè)不誠(chéng)實(shí)的提議者自我挑戰(zhàn)）作為獎(jiǎng)勵(lì)。 因此，最終的結(jié)果是，只要至少有一個(gè)誠(chéng)實(shí)的人正在觀察誰沒有受到審查，惡意行為者就沒有辦法成功，甚至嘗試對(duì)惡意行為者來說也是代價(jià)高昂的。
想要使用計(jì)算結(jié)果的應(yīng)用程序可以將存款作為計(jì)算可信度的指標(biāo)：如果解決方案提議者存在大量存款而且在一定時(shí)間內(nèi)沒有質(zhì)詢，則結(jié)果可能是正確的。 一旦出現(xiàn)挑戰(zhàn)，應(yīng)用程序應(yīng)該等待協(xié)議得到解決。 我們甚至可以創(chuàng)建計(jì)算結(jié)果保險(xiǎn)，承諾檢查離線計(jì)算并退還用戶，以防無效結(jié)果未及早提出質(zhì)疑。
二元搜索的力量
在接下來的兩節(jié)中，我將給出兩個(gè)具體的例子。 一個(gè)是交互式地驗(yàn)證外部區(qū)塊鏈中數(shù)據(jù)的存在，第二個(gè)是關(guān)于驗(yàn)證一般（確定性）計(jì)算。 在它們兩者中，我們經(jīng)常會(huì)遇到這樣的情況：提議者有一個(gè)很長(zhǎng)的值列表（由于它的長(zhǎng)度而不能直接用于合同），它以正確的值開頭但以不正確的值結(jié)束（因?yàn)樘嶙h者想欺騙）。 合同可以很容易地計(jì)算第i個(gè)（i + 1）st值，但檢查完整列表會(huì)太昂貴。 挑戰(zhàn)者知道正確的列表，并可以要求提議者從該列表中提供多個(gè)值。 由于第一個(gè)值是正確的而且最后一個(gè)是不正確的，所以在這個(gè)列表中必須至少有一個(gè)點(diǎn)i，其中第i個(gè)值是正確的并且（i + 1）st值是不正確的，并且挑戰(zhàn)者的任務(wù)是找到這個(gè)位置（讓我們稱這一點(diǎn)為“轉(zhuǎn)換點(diǎn)”），因?yàn)槟菚r(shí)合同可以檢查它。
讓我們假設(shè)列表的長(zhǎng)度為1.000.000，因此我們的搜索范圍為1到1.000.000。 挑戰(zhàn)者詢問位置500.000的價(jià)值。 如果正確，則至少有一個(gè)轉(zhuǎn)換點(diǎn)在500.000和1.000.000之間。 如果不正確，則存在介于1和500.000之間的轉(zhuǎn)換點(diǎn)。 在這兩種情況下，搜索范圍的長(zhǎng)度減少了一半。 我們現(xiàn)在重復(fù)這個(gè)過程，直到我們達(dá)到大小為2的搜索范圍，這必須是轉(zhuǎn)換點(diǎn)。 基數(shù)2的對(duì)數(shù)可用于計(jì)算“迭代二分”所采用的步數(shù)。 在1.000.000的情況下，這些是log1.000.000≈20步。
廉價(jià)的跨鏈轉(zhuǎn)移
作為第一個(gè)真實(shí)世界的例子，我想展示如何設(shè)計(jì)一個(gè)極其便宜的交叉鏈狀態(tài)或支付驗(yàn)證。 由于區(qū)塊鏈不是確定性的，但可以分叉，這有點(diǎn)復(fù)雜，但總體思路是一樣的。
提議者提交她想要在目標(biāo)合同中可用的數(shù)據(jù)（例如比特幣或狗狗幣交易，另一個(gè)以太坊鏈中的狀態(tài)值，或者M(jìn)erkle-DAG中的任何東西，其根哈希包含在區(qū)塊鏈的塊頭中并且是公知的（這是非常重要的））以及塊號(hào)，該塊頭的散列和存款。
請(qǐng)注意，我們只提交一個(gè)塊號(hào)和哈希值。 在BTCRelay的第一個(gè)版本中，目前需要提交所有比特幣塊頭，并驗(yàn)證所有比特幣的工作證明。 該協(xié)議僅在發(fā)生攻擊時(shí)才需要該信息。
如果一切正常，即外部驗(yàn)證器檢查塊編號(hào)的散列是否與規(guī)范鏈匹配（并且可選地具有一些確認(rèn)）并查看該塊中包含的事務(wù)/數(shù)據(jù)，則提議者可以請(qǐng)求返回存款和交叉 - 鏈轉(zhuǎn)移完成。 這就是非攻擊案件中的全部?jī)?nèi)容。 這應(yīng)該每次轉(zhuǎn)移耗費(fèi)約20萬個(gè)氣體。
如果出現(xiàn)問題，即我們要么有惡意提議者/提交者或惡意挑戰(zhàn)者，那么挑戰(zhàn)者現(xiàn)在有兩種可能：
注意，區(qū)塊鏈?zhǔn)怯蓛蓚€(gè)“臂”組成的Merkle-DAG：一個(gè)形成塊頭鏈，一個(gè)形成狀態(tài)或事務(wù)的Merkle-DAG。 一旦我們接受根（當(dāng)前塊頭哈希）有效，雙臂中的驗(yàn)證就是簡(jiǎn)單的Merkle-DAG證明。
（2）因此，讓我們先考慮第二種情況，因?yàn)樗?jiǎn)單：因?yàn)槲覀兿ＭM可能高效，所以我們不要求提議者提供完整的Merkle-DAG證明。 相反，我們只是請(qǐng)求從根到數(shù)據(jù)的DAG路徑（即一系列子索引）。
如果路徑太長(zhǎng)或索引無效，則挑戰(zhàn)者會(huì)詢問提議者超出范圍的點(diǎn)的父值和子值，并且提議者無法提供散列到父級(jí)的有效數(shù)據(jù)。 否則，我們的情況是根哈希是正確的，但某些點(diǎn)的哈希是不同的。 使用二進(jìn)制搜索，我們?cè)诼窂街姓业揭粋€(gè)點(diǎn)，我們?cè)谝粋€(gè)不正確的哈希上方有一個(gè)正確的哈希值。 提議者將無法提供散列到正確散列的子值，因此合同可以檢測(cè)到欺詐。
（1）現(xiàn)在讓我們考慮提議者使用無效塊或作為廢棄叉子一部分的塊的情況。 讓我們假設(shè)我們有一種機(jī)制將其他區(qū)塊鏈的區(qū)塊編號(hào)與以太坊區(qū)塊鏈上的時(shí)間相關(guān)聯(lián)，因此合同有一種方法可以告訴區(qū)塊編號(hào)無效，因?yàn)樗仨氃趯泶嬖凇?提議者現(xiàn)在必須提供所有塊頭（比特幣只有80個(gè)字節(jié)，如果它們太大，僅從哈希開始）直到合同已經(jīng)知道的某個(gè)檢查點(diǎn)（或者挑戰(zhàn)者以塊的形式請(qǐng)求它們）。 挑戰(zhàn)者必須做同樣的事情，并希望提供一個(gè)具有更高的區(qū)塊數(shù)/總難度的區(qū)塊。 現(xiàn)在兩人都可以交叉檢查他們的積木。 如果有人發(fā)現(xiàn)錯(cuò)誤，他們可以將塊號(hào)提交給合同，該合同可以檢查或讓其由另一個(gè)交互階段驗(yàn)證。
一般計(jì)算的特定交互式證明
假設(shè)我們有一個(gè)尊重局部性的計(jì)算模型，即它只能在一個(gè)步驟中對(duì)內(nèi)存進(jìn)行局部修改。 圖靈機(jī)尊重局部性，但隨機(jī)訪問機(jī)器（通常的計(jì)算機(jī)）如果只在每一步中修改內(nèi)存中的恒定點(diǎn)數(shù)，也可以。 此外，假設(shè)我們有一個(gè)H位輸出的安全散列函數(shù)。 如果在這樣的機(jī)器上進(jìn)行計(jì)算需要t步并且使用最多s個(gè)字節(jié)的內(nèi)存/狀態(tài)，那么我們可以在以太網(wǎng)中執(zhí)行關(guān)于log（t）+ 2 * log的此計(jì)算的交互式驗(yàn)證（在提議器/挑戰(zhàn)者模型中） （log（s））+ 2輪，其中每輪中的消息不長(zhǎng)于max（log（t），H + k + log（s）），其中k是“程序計(jì)數(shù)器”的大小，寄存器，磁頭位置或類似的內(nèi)部狀態(tài)。 除了將消息存儲(chǔ)在存儲(chǔ)器中之外，合同還需要執(zhí)行機(jī)器的最多一步或散列函數(shù)的一次評(píng)估。
證明：
該想法是計(jì)算（至少在請(qǐng)求時(shí)）每個(gè)步驟中計(jì)算所使用的所有存儲(chǔ)器的Merkle樹。 合同很容易驗(yàn)證單步對(duì)存儲(chǔ)器的影響，并且由于只能訪問存儲(chǔ)器中的恒定點(diǎn)數(shù)，因此可以使用Merkle-proofs驗(yàn)證存儲(chǔ)器的一致性。
在不失一般性的情況下，我們假設(shè)每一步都只訪問內(nèi)存中的一個(gè)點(diǎn)。 協(xié)議從提交者提交輸入和輸出開始。 挑戰(zhàn)者現(xiàn)在可以針對(duì)各種時(shí)間步驟i請(qǐng)求存儲(chǔ)器的Merkle樹根，內(nèi)部狀態(tài)/程序計(jì)數(shù)器以及訪問存儲(chǔ)器的位置。 挑戰(zhàn)者使用它來執(zhí)行二進(jìn)制搜索，該步驟導(dǎo)致步驟i，其中返回的信息是正確的但在步驟i + 1中是不正確的。這需要最多l(xiāng)og（t）輪和大小log（t）的消息。 H + k + log（s）。
挑戰(zhàn)者現(xiàn)在請(qǐng)求訪問（在步驟之前和之后）的內(nèi)存中的值以及沿著根路徑的所有兄弟（即Merkle證明）。 請(qǐng)注意，兄弟姐妹在步驟之前和之后是相同的，只有數(shù)據(jù)本身發(fā)生了變化。 使用此信息，合同可以檢查步驟是否正確執(zhí)行并且根哈希是否正確更新。 如果合同驗(yàn)證Merkle證明有效，則輸入內(nèi)存數(shù)據(jù)必須正確（因?yàn)樯⒘泻瘮?shù)是安全的，并且提議者和挑戰(zhàn)者都具有相同的預(yù)根哈希）。 如果步驟執(zhí)行被驗(yàn)證正確，則它們的輸出存儲(chǔ)器數(shù)據(jù)相等。 由于Merkle樹的兄弟姐妹是相同的，找到不同的后根哈希的唯一方法是計(jì)算或Merkle證明有錯(cuò)誤。
注意，前一段中描述的步驟進(jìn)行了一輪并且消息大小為（H + 1）log（s）。 所以我們總共有l(wèi)og（t）+ 1輪和消息大小max（log（t），k +（H + 2）log（s））。 此外，合同需要計(jì)算散列函數(shù)2 * log（s）次。 如果s很大或散列函數(shù)很復(fù)雜，我們可以稍微減小消息的大小，并且只需要以更多交互為代價(jià)來達(dá)到散列函數(shù)的單個(gè)應(yīng)用程序。 我們的想法是在Merkle證明上執(zhí)行二進(jìn)制搜索，如下所示：
我們不要求提議者發(fā)送完整的Merkle證明，而只發(fā)送內(nèi)存中的pre-post值和post值。 合同可以檢查停止的執(zhí)行，所以讓我們假設(shè)轉(zhuǎn)換是正確的（包括步驟i + 1中的內(nèi)部post狀態(tài)和內(nèi)存訪問索引）。 剩下的案例是：
在第一種情況下，挑戰(zhàn)者在從包含存儲(chǔ)器數(shù)據(jù)的Merkle樹葉到根的路徑上執(zhí)行交互式二進(jìn)制搜索，并找到具有正確父但錯(cuò)誤子的位置。 這最多需要log（log（s））輪次和大小log（log（s））的消息。 H位。 最后，由于散列函數(shù)是安全的，因此提議者不能為散列到父節(jié)點(diǎn)的錯(cuò)誤子節(jié)點(diǎn)提供兄弟節(jié)點(diǎn)。 這可以通過合同檢查哈希函數(shù)的單個(gè)評(píng)估。
在第二種情況下，我們處于倒置狀態(tài)：根是錯(cuò)誤的，但葉子是正確的。 挑戰(zhàn)者再次在最多l(xiāng)og（log（s（n））輪中執(zhí)行交互式二進(jìn)制搜索，其中消息大小為log（log（s））resp。 H位并在樹中找到父P錯(cuò)誤但子C正確的位置。 挑戰(zhàn)者向提議者詢問兄弟S，使得（C，S）散列到P，合同可以檢查。 由于我們知道只有存儲(chǔ)器中的給定位置可以隨著步驟的執(zhí)行而改變，所以S也必須出現(xiàn)在步驟之前的存儲(chǔ)器的Merkle樹中的相同位置。 此外，提議者為S提供的值不能正確，因?yàn)槟菚r(shí)，（C，S）不會(huì)哈希到P（我們知道P是錯(cuò)誤的，但C和S是正確的）。 因此，我們將其減少到提議者在pre-Merkle-tree中提供了錯(cuò)誤節(jié)點(diǎn)但是正確的根哈希的情況。 如第一種情況所示，這最多需要log（log（s））輪次和大小log（log（s））的消息。 H位驗(yàn)證。
總的來說，我們最多有l(wèi)og（t）+ 1 + 2 * log（log（s））+ 1輪，消息大小最多為max（log（t），H + k + log（s））。
家庭作業(yè)：將此證明轉(zhuǎn)換為可用于EVM或TinyRAM（以及C）程序的工作合同，并將其集成到Piper Merriam的以太坊計(jì)算市場(chǎng)中 。
感謝Vitalik建議使用Merkle-hash內(nèi)存以允許任意的步進(jìn)內(nèi)存大小！ 順便說一句，這很可能不是一個(gè)新結(jié)果。
在實(shí)踐中
這些對(duì)數(shù)很好，但這在實(shí)踐中意味著什么？ 讓我們假設(shè)我們?cè)谑褂? GB RAM的4 GHz計(jì)算機(jī)上進(jìn)行5秒的計(jì)算。 簡(jiǎn)化實(shí)際時(shí)鐘速率與人工架構(gòu)上的步驟之間的關(guān)系，我們大致有t =20000000000≈243和s =5000000000≈232。 交互式驗(yàn)證這樣的計(jì)算應(yīng)該采用43 + 2 + 2 * 5 = 55輪，即2 * 55 = 110塊并使用大約128字節(jié)的消息（主要取決于k，即架構(gòu)）。 如果我們不以交互方式驗(yàn)證Merkle證明，我們得到44輪（88塊）和大小為1200字節(jié)的消息（只有最后一條消息那么大）。
如果你說110塊（在以太坊上大約30分鐘，3比特幣上的確認(rèn)）聽起來很多，不要忘記我們?cè)谶@里談?wù)摰膬?nèi)容：4 GHz機(jī)器上實(shí)際使用5 GB RAM的5秒鐘。 如果您經(jīng)常運(yùn)行具有如此強(qiáng)大功能的程序，它們會(huì)搜索滿足特定條件的特定輸入值（優(yōu)化例程，密碼破解程序，工作解算器證明......）。 由于我們只想驗(yàn)證計(jì)算，因此不需要以這種方式執(zhí)行搜索，我們可以從頭開始提供解決方案，只檢查條件。
好吧，對(duì)于每個(gè)計(jì)算步驟計(jì)算和更新Merkle樹應(yīng)該是非常昂貴的，但是這個(gè)例子應(yīng)該只顯示這個(gè)協(xié)議在鏈上的擴(kuò)展程度。 此外，大多數(shù)計(jì)算，特別是在函數(shù)式語言中，可以細(xì)分為我們稱之為昂貴函數(shù)的級(jí)別，這些函數(shù)使用大量?jī)?nèi)存但輸出的數(shù)量很少。 我們可以將此功能視為主協(xié)議中的一個(gè)步驟，并在該功能中檢測(cè)到錯(cuò)誤時(shí)啟動(dòng)新的交互協(xié)議。 最后，正如已經(jīng)說過的那樣：在大多數(shù)情況下，我們只是驗(yàn)證輸出并且從不挑戰(zhàn)它（只有那時(shí)我們才需要計(jì)算Merkle樹），因?yàn)樘嶙h者幾乎肯定會(huì)失去他們的存款。
打開問題
在本文的幾個(gè)地方，我們假設(shè)我們只有兩個(gè)外部參與者，其中至少有一個(gè)是誠(chéng)實(shí)的。 我們可以通過要求提議者和挑戰(zhàn)者的存款來接近這個(gè)假設(shè)。 一個(gè)問題是其中一個(gè)可能只是拒絕繼續(xù)協(xié)議，所以我們需要超時(shí)。 另一方面，如果我們?cè)黾映瑫r(shí)，惡意行為者可能會(huì)使區(qū)塊鏈與不相關(guān)的交易飽和，希望答案不會(huì)及時(shí)成為一個(gè)塊。 合同是否有可能檢測(cè)到這種情況并延長(zhǎng)超時(shí)？ 此外，誠(chéng)實(shí)的提議者可能會(huì)被阻止離開網(wǎng)絡(luò)。 正因?yàn)槿绱?#xff08;并且因?yàn)楸葠阂庋輪T更誠(chéng)實(shí)），我們可能允許任何人在存款后進(jìn)入（雙方）。 同樣，如果我們?cè)试S這樣做，惡意行為者可以介入“誠(chéng)實(shí)”的一方，只是假裝誠(chéng)實(shí)。 這聽起來有點(diǎn)復(fù)雜，但我相信它最終會(huì)成功。
https://blog.ethereum.org/2016/02/17/smart-contracts-courts-not-smart-judges/
總結(jié)
以上是生活随笔為你收集整理的【译】From Smart Contracts to Courts with not so Smart Judges的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Ethermint部署及框架解析
- 下一篇： Guide To Using The G