博弈論在區塊鏈中的應用研究

發布時間：2020-01-18所屬分類：計算機職稱論文瀏覽：1203次

摘 要： 摘 要: 區塊鏈是比特幣的底層技術, 用于分布式地存儲比特幣的歷史交易信息. 區塊鏈中的每個區塊包含若干交易信息, 礦工一旦挖到新的區塊, 就將其加入區塊鏈, 并以密碼學方式保證區塊信息不可篡改和不可偽造. 為了保證系統正常運行, 區塊鏈將經濟因素集成到激

　　摘 要: 區塊鏈是比特幣的底層技術, 用于分布式地存儲比特幣的歷史交易信息. 區塊鏈中的每個區塊包含若干交易信息, 礦工一旦挖到新的區塊, 就將其加入區塊鏈, 并以密碼學方式保證區塊信息不可篡改和不可偽造. 為了保證系統正常運行, 區塊鏈將經濟因素集成到激勵層, 為礦工提供充足的動機去尋找新的區塊, 激勵層主要包括經濟激勵的發行機制和分配機制等. 因此, 如何設計高效實用的激勵層成為區塊鏈中的關鍵問題. 博弈論作為現代數學的一個重要分支, 已經成為分析經濟學理論的標準工具之一, 可以用來研究激勵層的機制設計, 提高區塊鏈的效率和實用性. 本文首先分析了博弈論、安全多方計算和比特幣 (區塊鏈 1.0) 三者之間交叉的研究領域, 其中包括理性安全多方計算, 基于比特幣的安全多方計算以及基于博弈論的比特幣協議. 然后將智能合約 (區塊鏈 2.0) 應用在可驗證云計算中, 使用博弈論為云計算中的委托人設計智能合約, 該智能合約可以有效地防止云服務器合謀. 最后在犯罪智能合約中引入隨機參數, 構造了 Random-PublicLeaks, 通過驗證智能合約有效性, 發現隨機性的引入降低了犯罪智能合約的成功概率.

　　關鍵詞: 區塊鏈; 博弈論; 比特幣; 智能合約

　　1 引言

　　博弈論 (game theory) 主要研究整個博弈中激勵結構件的相互作用, 根據是否可以達成具有約束力的協議, 博弈可以分為合作博弈 (cooperate game) 和非合作博弈 (non-cooperate game) [1] . 合作博弈指的是博弈環境中的某些 (或者全部) 參與者以同盟、合作的方式進行博弈, 研究的是參與者的收益分配問題. 非合作博弈則把所有參與者的行為都看作是單獨的行為, 與環境中的其他參與者無關, 研究的是參與者在利益相互影響的局勢中如何選擇決策使自己的收益最大, 即策略選擇問題. 現實中的絕大多數博弈會包含參與者之間的合作和沖突行為, 因此通常看作是合作博弈與非合作博弈的混合物. 博弈論廣泛應用于經濟學、管理學、社會學、政治學、軍事科學等領域. 近年來, 博弈論在密碼學領域引起了研究學者的重視, 催生了博弈密碼學的新興交叉學科: 理性密碼學 [2–5] . 例如, 傳統密碼協議中的參與者被分為誠實參與者, 半誠實參與者和惡意參與者, 而理性密碼協議中參與者被認為是理性的. 博弈論在密碼學領域的研究主要集中在理性多方安全計算領域, 利用理性參與者最大化其收益的特性, 約束他們的行為, 促使他們選擇合適的策略保證協議的安全性, 多數情況下用來解決公平性 [6–8] . 然而, 理性多方安全計算中最大的一個瓶頸就是理性參與者的動機, 即收益函數的定義. 目前大多數理性協議中理性收益函數都來源于某個已知博弈 (例如囚徒困境博弈、連鎖店博弈), 然后再根據具體協議定義每個參與者的收益函數. 這些收益函數的定義詬病在于, 缺乏足夠的經濟動機作為理性參與者收益函數的支撐.

　　安全多方計算中公平性指的是敵手和誠實參與者同時獲得輸出, 然而 Cleve 指出, 當敵手控制的參與者超過半數以上時, 公平性是不可能實現的 [9] . 因此, 針對公平性實現的研究一直被忽視. 博弈論的引入解決這個問題, 收益函數為理性參與者提供了誠實參與安全多方計算的動機, 納什均衡將理性參與者的策略約束在協議允許范圍內, 使得誠實參與者都可以獲得輸出, 實現公平性. 然而, 理性安全多方計算中的收益函數, 貌似專門為實現公平性精心設計的, 缺乏真實的背景環境支撐. 為了解決這個問題, 學者們從經濟學角度出發, 將比特幣 (Bitcoin) [10,11] 中的經濟激勵引入安全多方計算中, 為參與者參與安全多方計算協議提供了充分而又真實的動機, 基于比特幣的安全多方計算也可以實現公平性 [12] . 另外, 比特幣本身就是一種貨幣, 用博弈論來分析其中的激勵機制是一種必然的方式. 博弈論中的合作博弈和非合作博弈可以用來分析礦池策略的設計. 總之, 博弈論、比特幣和安全多方計算之間聯系緊密、互相滲透, 其連接紐帶就是參與者的動機, 他們之間的關系如圖1所示.

　　2 博弈論、比特幣和安全多方計算之間的關系

　　2.1 理性安全多方計算

　　理性安全多方計算 (rational secure multi-party computation, RSMPC) 是博弈論和安全多方計算的一個綜合, 利用博弈論中的一些概念和方法解決安全多方計算中的某些問題 [13–15] . 在 RSMPC 中, 參與者被看作是理性的或自私的, 稱為理性參與者 (rational parties), 以追求利益最大化為行為的動機. 按照博弈論的方法, 參與者的 “利益” 用所謂 “效用函數” 描述, 理性安全多方計算協議的執行, 就是理性參與者根據其效用函數的定義, 以最大化效用為目的, 使用各自的策略進行多輪交互的過程. 傳統的 “誠實參與者” 和 “敵手” 均可看作是特殊的理性參與者. 換句話說, 協議的執行就是理性參與者采取一系列策略的過程, 理性參與者可以遵循協議, 也可以偏離協議. 遵循協議或偏離協議都取決于他們能否最大化其效用. 協議設計的最終目標是: 每個參與者都遵循協議, 都沒有偏離協議的動機. 從博弈論的角度解釋這一目標就是: 每個參與者都遵循協議可以達到納什均衡 (Nash equilibrium), 沒有一個參與者可以通過偏離它而獲得更高的效用.

　　2.2 基于比特幣的安全多方計算的研究進展

　　比特幣作為一種電子貨幣可以解決參與者的動機問題 [16,17] , 其中理性參與者參與多方計算的動機可以理解為要么獲得計算結果, 要么獲得一些經濟補償 (例如比特幣). Bentov 和 Kumaresan [18] 定義了幾個理想元語 (ideal primitive): 認領或退款函數性 F ∗ CR (claim-or-refund functionality) [19] , 帶懲罰的安全計算 F ∗ f (secure computation with penalties) 和帶懲罰的安全彩票 F ∗ lot (secure lottery with penalties). 他們構造的多方計算協議只需要調用常數次 F ∗ CR 即可. Kumaresan 和 Bentov 研究了如何使用比特幣激勵參與者實現正確計算 [20] , 他們的工作包括四個方面:

　　(1) 可驗證云計算 (verifiable computation): 委托人把一個計算外包給云服務器, 如果云返回了正確的計算結果, 委托人就支付給云服務器一定的酬勞. 他們設計了一個協議可以實現公開和私有驗證機制.

　　(2) 帶有限制泄露的安全計算 (secure computation with restricted leakage): 基于 Huang et al [21] 的工作他們提供了一個高效的安全計算協議, 一旦惡意敵手被發現試圖獲得 1 比特的信息, 都會受到懲罰 (例如扣除比特幣).

　　(3) 公平安全計算 (fair secure computation): 當參與者提前中斷協議時, 會受到金錢方面的懲罰. 他們在比特幣網上構造了一個常數輪的理想交易函數性 F ∗ ML (ideal transaction functionality), 并且基于該函數性設計了一個混合世界下的常數輪安全計算協議.

　　(4) 非交互式懸賞 (non-interactive bounty): 他們提供了一個基于比特幣網絡的非交互式捐款機制, 使得領賞人只要完成既定任務就可以領到賞金.

　　Kumaresan 等還討論了如何利用 Bitcoin 實現去中心化撲克 [22]. 2017 年 Kumaresan 等又分別對 CRYPTO 2014 [18] 和 CCS 2015 [22] 中的方案進行了改進 [23] , 提出如何利用懲罰機制優化安全計算模型. Kiayias 等提出了使用區塊鏈來實現公平且具有健壯性的多方計算協議 [24] . 他們的工作包括以下三個方面: (1) 提出了一個帶有補償的安全多方計算的形式化模型; (2) 該模型是 UC 安全的 [25]; (3) 首次提出了一個常數輪健壯性多方計算協議.

　　2.3 基于博弈論的比特幣協議

　　從經濟學角度上看, 比特幣中的激勵機制解決了挖礦者的動機問題, 而博弈論在經濟學領域的應用已經非常成熟, 因此從博弈論的角度分析比特幣和區塊鏈中的一些問題水到渠成, 更加方便. 眾所周知, 比特幣中最重要的一個機制就是挖礦 (mining). Tschorsch 和 Scheuermann 給出了比特幣的基本概念和工作流程 [26] . 礦工想要獲得比特幣就需要解決特定的數學難題, 即, 找到一個比特幣區塊, 礦工就可以獲得 12.5 個比特幣. 截止到 2018 年 12 月 23 日, 一個比特幣的價值為 27 706.77 元人民幣. 因此, 挖礦的收益還是很可觀的, 這為礦工提供了最足夠的挖礦動機. 然而解決這些難題需要具備一定的計算能力, 通常單個礦工需要花費幾個月甚至幾年才能挖到一個比特幣區塊. 然而比特幣網絡大概 10 分鐘就會出現一個新的區塊, 所以大部分的礦工徒勞無獲. 為此, 部分礦工組成礦池 (mining pool), 將他們的計算能力作為一個整體, 如果在合適時間內挖到一個有效區塊, 他們就按照每個人的計算能力分享挖礦所得的獎勵. 然而, 從博弈論的角度出發, 如果激勵機制設計有漏洞, 導致偏離礦池策略能夠帶來更大的收益, 理性的礦工都有偏離礦池策略的動機, 這與博弈論中合作博弈與非合作博弈相似.

　　相關論文推薦閱讀：基于區塊鏈的網絡安全技術綜述

　　摘 要：隨著移動互聯網與物聯網技術的發展，網絡空間承載了海量數據，必須保證其安全性和隱私性。基于區塊鏈的網絡安全機制具有去中心化、不可篡改、可追溯、高可信和高可用的特性，有利于提升網絡安全性。探討了區塊鏈在網絡安全方面的應用方案，分析了基于區塊鏈的網絡安全機制的主要技術特點和方法以及未來研究方向。首先探討了數據管理體系應用區塊鏈進行數據管理的方法，利用區塊鏈不可篡改的特性提高數據的真實性和可靠性。其次分析了物聯網應用區塊鏈進行設備管理的方案，通過區塊鏈記錄和執行設備控制指令，強化物聯網設備權限和通信管理。最后研究了域名系統應用區塊鏈的部署方案，利用區塊鏈的去中心化結構抵抗針對中心節點的分布式拒絕服務攻擊。

　　Schrijvers 等從博弈論角度出發, 在單個礦池中定義了一個礦池支付函數 [27] . 礦池中的礦工一旦挖到一個區塊, 可以選擇何時向礦池管理員報告. 他們定義了支付函數的三個特性: 激勵相容 (incentive compatibility), 按比例支付 (proportional payments) 和預算平衡 (budget balanced). Schrijvers 等分析了目前幾種礦池分配策略的支付函數是否滿足這幾個特性. 按算力比例分配的支付函數 (proportional reward function, 記為 R prop) 指的是按照每個礦工的計算能力來分配收益, 這是一種較早的礦池分配策略. 然而 R prop 滿足按比例支付和預算平衡的特性, 但它不是激勵相容的. 按份額比例分配的支付函數 (per-per-share reward function, 記為 R pps) 滿足激勵相容的特性, 但不滿足預算平衡的特性. 因此 Schrijvers 等提出了一個新的激勵相容支付函數 (incentive compatible reward function, 記為 R IC), 該支付函數不僅考慮到每個礦工的份額還考慮到發現區塊者的身份, 使得收益分配更加合理. 他們證明 R IC 滿足激勵相容, 按比例支付和預算平衡這三個特性. 但是礦工不允許加入到其他礦池或者獨立挖礦, 他只能在礦池中貢獻自己的份額, 也沒有考慮礦工的合謀問題. Eyal 和 Sirer 研究了比特幣協議的激勵相容問題 [28] , 在允許礦工合謀的情況下, 理性礦工 (rational miner) 最終會變成自私礦工 (selfish miner), 這些自私礦工合謀組成一個自私礦池 (selfish pool), 能夠吸引越來越多的自私礦工加入, 最后礦池會變成控制超過多數礦工的一個礦池, 比特幣又變成了一種中心化貨幣, 這違背了比特幣的初衷. 也就是說任何一個自私礦池都可以發展為一個控制絕大多數礦工的自私礦池, 從而破壞比特幣的去中心化. 這種攻擊稱為自私挖礦攻擊 (selfish mining attack). 為了抵御這種攻擊, 他們提出了一個比特幣協議的改進版本, 這個新版本是逆向兼容的 (backwards-compatible). 當礦工發現區塊有兩個相同長度的分叉 (fork) 時, 同時在全網廣播他們并且隨機均勻地在這兩個分支上繼續挖礦. 改進版本的比特幣協議可以阻止那些控制少于 1/4 資源的自私礦池成為一個控制絕大多數資源的礦池, 優于改進之前的門限值 0. Nayak 等擴展了挖礦策略的空間 [29] , 其中包括了 “頑固” 策略 (“stubborn” strategies), 他們證明了對于較大規模的策略空間來說自私挖礦并不是一個好的策略. Nayak 等主要研究了兩類挖礦攻擊: 類自私挖礦攻擊 (“selfish-mining”-style) 和網絡層次的攻擊, 又稱之為日食攻擊 (eclipse attack). 一個礦工可以將挖礦供給和網絡層次的日食攻擊結合起來增大他的收益. 也就是說, 當給定最優策略時, 某些日食攻擊的受害者可以在攻擊過程中受益.

　　Heilman 引入了首選重置 (freshness preferred, FP) 機制 [30] , 該機制通過使用不可偽造時間戳來懲罰那些不及時釋放區塊的自私礦工. 他們將 Eyal 和 Sirer [28] 中的門限由 0.25 提升至 0.32. 然而該機制不是激勵相容的, 而且對于可偽造的時間戳不具備健壯性. 也就是說 FP 機制的實現依賴于不可偽造的時間戳, 但是不可偽造的時間戳又很難實現 [31,32] , 因此該機制的實現具有一定的局限性. Solat 和 PotopButucaru 針對自私挖礦攻擊和截留攻擊 (withholding attack) 提出了一個解決方案: ZeroBlock [33] , 該方案不需要使用時間戳 (timestamp) 技術, 因為時間戳可以被偽造. 在 ZeroBlock 方案中, 如果一個自私礦工持有區塊的時間超過幅度間隔 (mat interval), 例如, 最大的可接受一個新區塊的等待時間, 那么誠實礦工就會拒絕接受這個新區塊.

　　Sapirshtein 等擴展了文獻 [28] 的工作, 提出了一個高效算法 [34] , 該算法可以計算 ε-optimal 的自私挖礦策略, 其中 ε > 0. 他們證明了算法的正確性, 并分析了其誤差范圍. 使用這種高效算法, 礦工可以計算自私挖礦策略獲得更大的收益, 而且自私礦工需要控制的資源也少于 1/4, 也就是說攻擊者及時控制的資源少于 1/4 也有利可圖, 這樣就增加了攻擊者的能力, 使他們有機可乘. 他們還證明如果考慮區塊在網絡傳播中的延遲, 門限值又變為 0, 即, 攻擊者不論控制多少資源, 總存在一個自私挖礦策略, 其帶來的收益高于誠實挖礦的收益. 最后他們總結了自私挖坑和雙花 (double spending) 之間的相互作用. 文獻 [27,28,34] 討論的都是一個礦池對誠實礦工的攻擊. Eyal 討論了兩個礦池之間的攻擊 [35] , 兩個礦池之間存在個人理性與集體理性的矛盾, 這類似于公共地悲劇博弈. Eyal 提出了兩個礦池之間的截留攻擊, 一個攻擊礦池 (attacking pool) 的管理者首先在另一個受害礦池 (victim pool) 注冊為正常礦工, 他從受害礦池接受若干任務并把這些任務指派給攻擊礦池中的滲透礦工 (稱之為 infiltrating miners), 滲透礦工在攻擊礦池中的比例稱之為滲透率 (infiltration rate). 攻擊礦池會把滲透礦工的部分工作能力提交給受害礦池, 讓受害礦池評估滲透礦工的能力, 當滲透礦工提交完全的工作證明時, 攻擊礦池忽略這些工作. 截留攻擊的缺陷在于受害礦池的總體計算能力沒有增加 (滲透礦工不工作), 但是它的平均預算卻降低了. 一方面攻擊礦池分出一部分計算能力給受害礦池, 其自身的計算能力也受到了損害. 因此, 總體來說截留攻擊降低了整個網絡的計算能力. 對于兩個礦池來說, 采取截留攻擊是唯一的納什均衡, 然而如果雙方都不采取截留攻擊, 他們的收益會更大. 從博弈論角度分析, 是否采取截留攻擊對礦池來說是一個礦工的困境 (miner’s dilemma), 礦工不斷的挖礦過程就類似與一個重復囚徒困境博弈. Rosenfeld 建議修改區塊結構來解決這一問題 [36]

声明:①文献来自知网、维普、万方等检索数据库，说明本文献已经发表见刊，恭喜作者.②如果您是作者且不想本平台展示文献信息,可联系学术顾问予以删除.