發(fā)布時間：所屬分類：計算機職稱論文瀏覽：1次
摘 要： 摘 要: 區(qū)塊鏈是比特幣的底層技術(shù), 用于分布式地存儲比特幣的歷史交易信息. 區(qū)塊鏈中的每個區(qū)塊包含若干交易信息, 礦工一旦挖到新的區(qū)塊, 就將其加入?yún)^(qū)塊鏈, 并以密碼學(xué)方式保證區(qū)塊信息不可篡改和不可偽造. 為了保證系統(tǒng)正常運行, 區(qū)塊鏈將經(jīng)濟因素集成到激
摘 要: 區(qū)塊鏈是比特幣的底層技術(shù), 用于分布式地存儲比特幣的歷史交易信息. 區(qū)塊鏈中的每個區(qū)塊包含若干交易信息, 礦工一旦挖到新的區(qū)塊, 就將其加入?yún)^(qū)塊鏈, 并以密碼學(xué)方式保證區(qū)塊信息不可篡改和不可偽造. 為了保證系統(tǒng)正常運行, 區(qū)塊鏈將經(jīng)濟因素集成到激勵層, 為礦工提供充足的動機去尋找新的區(qū)塊, 激勵層主要包括經(jīng)濟激勵的發(fā)行機制和分配機制等. 因此, 如何設(shè)計高效實用的激勵層成為區(qū)塊鏈中的關(guān)鍵問題. 博弈論作為現(xiàn)代數(shù)學(xué)的一個重要分支, 已經(jīng)成為分析經(jīng)濟學(xué)理論的標準工具之一, 可以用來研究激勵層的機制設(shè)計, 提高區(qū)塊鏈的效率和實用性. 本文首先分析了博弈論、安全多方計算和比特幣 (區(qū)塊鏈 1.0) 三者之間交叉的研究領(lǐng)域, 其中包括理性安全多方計算, 基于比特幣的安全多方計算以及基于博弈論的比特幣協(xié)議. 然后將智能合約 (區(qū)塊鏈 2.0) 應(yīng)用在可驗證云計算中, 使用博弈論為云計算中的委托人設(shè)計智能合約, 該智能合約可以有效地防止云服務(wù)器合謀. 最后在犯罪智能合約中引入隨機參數(shù), 構(gòu)造了 Random-PublicLeaks, 通過驗證智能合約有效性, 發(fā)現(xiàn)隨機性的引入降低了犯罪智能合約的成功概率.
關(guān)鍵詞: 區(qū)塊鏈; 博弈論; 比特幣; 智能合約
1 引言
博弈論 (game theory) 主要研究整個博弈中激勵結(jié)構(gòu)件的相互作用, 根據(jù)是否可以達成具有約束力的協(xié)議, 博弈可以分為合作博弈 (cooperate game) 和非合作博弈 (non-cooperate game) [1] . 合作博弈指的是博弈環(huán)境中的某些 (或者全部) 參與者以同盟、合作的方式進行博弈, 研究的是參與者的收益分配問題. 非合作博弈則把所有參與者的行為都看作是單獨的行為, 與環(huán)境中的其他參與者無關(guān), 研究的是參與者在利益相互影響的局勢中如何選擇決策使自己的收益最大, 即策略選擇問題. 現(xiàn)實中的絕大多數(shù)博弈會包含參與者之間的合作和沖突行為, 因此通�？醋魇呛献鞑┺呐c非合作博弈的混合物. 博弈論廣泛應(yīng)用于經(jīng)濟學(xué)、管理學(xué)、社會學(xué)、政治學(xué)、軍事科學(xué)等領(lǐng)域. 近年來, 博弈論在密碼學(xué)領(lǐng)域引起了研究學(xué)者的重視, 催生了博弈密碼學(xué)的新興交叉學(xué)科: 理性密碼學(xué) [2–5] . 例如, 傳統(tǒng)密碼協(xié)議中的參與者被分為誠實參與者, 半誠實參與者和惡意參與者, 而理性密碼協(xié)議中參與者被認為是理性的. 博弈論在密碼學(xué)領(lǐng)域的研究主要集中在理性多方安全計算領(lǐng)域, 利用理性參與者最大化其收益的特性, 約束他們的行為, 促使他們選擇合適的策略保證協(xié)議的安全性, 多數(shù)情況下用來解決公平性 [6–8] . 然而, 理性多方安全計算中最大的一個瓶頸就是理性參與者的動機, 即收益函數(shù)的定義. 目前大多數(shù)理性協(xié)議中理性收益函數(shù)都來源于某個已知博弈 (例如囚徒困境博弈、連鎖店博弈), 然后再根據(jù)具體協(xié)議定義每個參與者的收益函數(shù). 這些收益函數(shù)的定義詬病在于, 缺乏足夠的經(jīng)濟動機作為理性參與者收益函數(shù)的支撐.
安全多方計算中公平性指的是敵手和誠實參與者同時獲得輸出, 然而 Cleve 指出, 當敵手控制的參與者超過半數(shù)以上時, 公平性是不可能實現(xiàn)的 [9] . 因此, 針對公平性實現(xiàn)的研究一直被忽視. 博弈論的引入解決這個問題, 收益函數(shù)為理性參與者提供了誠實參與安全多方計算的動機, 納什均衡將理性參與者的策略約束在協(xié)議允許范圍內(nèi), 使得誠實參與者都可以獲得輸出, 實現(xiàn)公平性. 然而, 理性安全多方計算中的收益函數(shù), 貌似專門為實現(xiàn)公平性精心設(shè)計的, 缺乏真實的背景環(huán)境支撐. 為了解決這個問題, 學(xué)者們從經(jīng)濟學(xué)角度出發(fā), 將比特幣 (Bitcoin) [10,11] 中的經(jīng)濟激勵引入安全多方計算中, 為參與者參與安全多方計算協(xié)議提供了充分而又真實的動機, 基于比特幣的安全多方計算也可以實現(xiàn)公平性 [12] . 另外, 比特幣本身就是一種貨幣, 用博弈論來分析其中的激勵機制是一種必然的方式. 博弈論中的合作博弈和非合作博弈可以用來分析礦池策略的設(shè)計. 總之, 博弈論、比特幣和安全多方計算之間聯(lián)系緊密、互相滲透, 其連接紐帶就是參與者的動機, 他們之間的關(guān)系如圖1所示.
2 博弈論、比特幣和安全多方計算之間的關(guān)系
2.1 理性安全多方計算
理性安全多方計算 (rational secure multi-party computation, RSMPC) 是博弈論和安全多方計算的一個綜合, 利用博弈論中的一些概念和方法解決安全多方計算中的某些問題 [13–15] . 在 RSMPC 中, 參與者被看作是理性的或自私的, 稱為理性參與者 (rational parties), 以追求利益最大化為行為的動機. 按照博弈論的方法, 參與者的 “利益” 用所謂 “效用函數(shù)” 描述, 理性安全多方計算協(xié)議的執(zhí)行, 就是理性參與者根據(jù)其效用函數(shù)的定義, 以最大化效用為目的, 使用各自的策略進行多輪交互的過程. 傳統(tǒng)的 “誠實參與者” 和 “敵手” 均可看作是特殊的理性參與者. 換句話說, 協(xié)議的執(zhí)行就是理性參與者采取一系列策略的過程, 理性參與者可以遵循協(xié)議, 也可以偏離協(xié)議. 遵循協(xié)議或偏離協(xié)議都取決于他們能否最大化其效用. 協(xié)議設(shè)計的最終目標是: 每個參與者都遵循協(xié)議, 都沒有偏離協(xié)議的動機. 從博弈論的角度解釋這一目標就是: 每個參與者都遵循協(xié)議可以達到納什均衡 (Nash equilibrium), 沒有一個參與者可以通過偏離它而獲得更高的效用.
2.2 基于比特幣的安全多方計算的研究進展
比特幣作為一種電子貨幣可以解決參與者的動機問題 [16,17] , 其中理性參與者參與多方計算的動機可以理解為要么獲得計算結(jié)果, 要么獲得一些經(jīng)濟補償 (例如比特幣). Bentov 和 Kumaresan [18] 定義了幾個理想元語 (ideal primitive): 認領(lǐng)或退款函數(shù)性 F ∗ CR (claim-or-refund functionality) [19] , 帶懲罰的安全計算 F ∗ f (secure computation with penalties) 和帶懲罰的安全彩票 F ∗ lot (secure lottery with penalties). 他們構(gòu)造的多方計算協(xié)議只需要調(diào)用常數(shù)次 F ∗ CR 即可. Kumaresan 和 Bentov 研究了如何使用比特幣激勵參與者實現(xiàn)正確計算 [20] , 他們的工作包括四個方面:
(1) 可驗證云計算 (verifiable computation): 委托人把一個計算外包給云服務(wù)器, 如果云返回了正確的計算結(jié)果, 委托人就支付給云服務(wù)器一定的酬勞. 他們設(shè)計了一個協(xié)議可以實現(xiàn)公開和私有驗證機制.
(2) 帶有限制泄露的安全計算 (secure computation with restricted leakage): 基于 Huang et al [21] 的工作他們提供了一個高效的安全計算協(xié)議, 一旦惡意敵手被發(fā)現(xiàn)試圖獲得 1 比特的信息, 都會受到懲罰 (例如扣除比特幣).
(3) 公平安全計算 (fair secure computation): 當參與者提前中斷協(xié)議時, 會受到金錢方面的懲罰. 他們在比特幣網(wǎng)上構(gòu)造了一個常數(shù)輪的理想交易函數(shù)性 F ∗ ML (ideal transaction functionality), 并且基于該函數(shù)性設(shè)計了一個混合世界下的常數(shù)輪安全計算協(xié)議.
(4) 非交互式懸賞 (non-interactive bounty): 他們提供了一個基于比特幣網(wǎng)絡(luò)的非交互式捐款機制, 使得領(lǐng)賞人只要完成既定任務(wù)就可以領(lǐng)到賞金.
Kumaresan 等還討論了如何利用 Bitcoin 實現(xiàn)去中心化撲克 [22]. 2017 年 Kumaresan 等又分別對 CRYPTO 2014 [18] 和 CCS 2015 [22] 中的方案進行了改進 [23] , 提出如何利用懲罰機制優(yōu)化安全計算模型. Kiayias 等提出了使用區(qū)塊鏈來實現(xiàn)公平且具有健壯性的多方計算協(xié)議 [24] . 他們的工作包括以下三個方面: (1) 提出了一個帶有補償?shù)陌踩喾接嬎愕男问交Ｐ? (2) 該模型是 UC 安全的 [25]; (3) 首次提出了一個常數(shù)輪健壯性多方計算協(xié)議.
2.3 基于博弈論的比特幣協(xié)議
從經(jīng)濟學(xué)角度上看, 比特幣中的激勵機制解決了挖礦者的動機問題, 而博弈論在經(jīng)濟學(xué)領(lǐng)域的應(yīng)用已經(jīng)非常成熟, 因此從博弈論的角度分析比特幣和區(qū)塊鏈中的一些問題水到渠成, 更加方便. 眾所周知, 比特幣中最重要的一個機制就是挖礦 (mining). Tschorsch 和 Scheuermann 給出了比特幣的基本概念和工作流程 [26] . 礦工想要獲得比特幣就需要解決特定的數(shù)學(xué)難題, 即, 找到一個比特幣區(qū)塊, 礦工就可以獲得 12.5 個比特幣. 截止到 2018 年 12 月 23 日, 一個比特幣的價值為 27 706.77 元人民幣. 因此, 挖礦的收益還是很可觀的, 這為礦工提供了最足夠的挖礦動機. 然而解決這些難題需要具備一定的計算能力, 通常單個礦工需要花費幾個月甚至幾年才能挖到一個比特幣區(qū)塊. 然而比特幣網(wǎng)絡(luò)大概 10 分鐘就會出現(xiàn)一個新的區(qū)塊, 所以大部分的礦工徒勞無獲. 為此, 部分礦工組成礦池 (mining pool), 將他們的計算能力作為一個整體, 如果在合適時間內(nèi)挖到一個有效區(qū)塊, 他們就按照每個人的計算能力分享挖礦所得的獎勵. 然而, 從博弈論的角度出發(fā), 如果激勵機制設(shè)計有漏洞, 導(dǎo)致偏離礦池策略能夠帶來更大的收益, 理性的礦工都有偏離礦池策略的動機, 這與博弈論中合作博弈與非合作博弈相似.
相關(guān)論文推薦閱讀：基于區(qū)塊鏈的網(wǎng)絡(luò)安全技術(shù)綜述
摘 要：隨著移動互聯(lián)網(wǎng)與物聯(lián)網(wǎng)技術(shù)的發(fā)展，網(wǎng)絡(luò)空間承載了海量數(shù)據(jù)，必須保證其安全性和隱私性�；趨^(qū)塊鏈的網(wǎng)絡(luò)安全機制具有去中心化、不可篡改、可追溯、高可信和高可用的特性，有利于提升網(wǎng)絡(luò)安全性。探討了區(qū)塊鏈在網(wǎng)絡(luò)安全方面的應(yīng)用方案，分析了基于區(qū)塊鏈的網(wǎng)絡(luò)安全機制的主要技術(shù)特點和方法以及未來研究方向。首先探討了數(shù)據(jù)管理體系應(yīng)用區(qū)塊鏈進行數(shù)據(jù)管理的方法，利用區(qū)塊鏈不可篡改的特性提高數(shù)據(jù)的真實性和可靠性。其次分析了物聯(lián)網(wǎng)應(yīng)用區(qū)塊鏈進行設(shè)備管理的方案，通過區(qū)塊鏈記錄和執(zhí)行設(shè)備控制指令，強化物聯(lián)網(wǎng)設(shè)備權(quán)限和通信管理。最后研究了域名系統(tǒng)應(yīng)用區(qū)塊鏈的部署方案，利用區(qū)塊鏈的去中心化結(jié)構(gòu)抵抗針對中心節(jié)點的分布式拒絕服務(wù)攻擊。
Schrijvers 等從博弈論角度出發(fā), 在單個礦池中定義了一個礦池支付函數(shù) [27] . 礦池中的礦工一旦挖到一個區(qū)塊, 可以選擇何時向礦池管理員報告. 他們定義了支付函數(shù)的三個特性: 激勵相容 (incentive compatibility), 按比例支付 (proportional payments) 和預(yù)算平衡 (budget balanced). Schrijvers 等分析了目前幾種礦池分配策略的支付函數(shù)是否滿足這幾個特性. 按算力比例分配的支付函數(shù) (proportional reward function, 記為 R prop) 指的是按照每個礦工的計算能力來分配收益, 這是一種較早的礦池分配策略. 然而 R prop 滿足按比例支付和預(yù)算平衡的特性, 但它不是激勵相容的. 按份額比例分配的支付函數(shù) (per-per-share reward function, 記為 R pps) 滿足激勵相容的特性, 但不滿足預(yù)算平衡的特性. 因此 Schrijvers 等提出了一個新的激勵相容支付函數(shù) (incentive compatible reward function, 記為 R IC), 該支付函數(shù)不僅考慮到每個礦工的份額還考慮到發(fā)現(xiàn)區(qū)塊者的身份, 使得收益分配更加合理. 他們證明 R IC 滿足激勵相容, 按比例支付和預(yù)算平衡這三個特性. 但是礦工不允許加入到其他礦池或者獨立挖礦, 他只能在礦池中貢獻自己的份額, 也沒有考慮礦工的合謀問題. Eyal 和 Sirer 研究了比特幣協(xié)議的激勵相容問題 [28] , 在允許礦工合謀的情況下, 理性礦工 (rational miner) 最終會變成自私礦工 (selfish miner), 這些自私礦工合謀組成一個自私礦池 (selfish pool), 能夠吸引越來越多的自私礦工加入, 最后礦池會變成控制超過多數(shù)礦工的一個礦池, 比特幣又變成了一種中心化貨幣, 這違背了比特幣的初衷. 也就是說任何一個自私礦池都可以發(fā)展為一個控制絕大多數(shù)礦工的自私礦池, 從而破壞比特幣的去中心化. 這種攻擊稱為自私挖礦攻擊 (selfish mining attack). 為了抵御這種攻擊, 他們提出了一個比特幣協(xié)議的改進版本, 這個新版本是逆向兼容的 (backwards-compatible). 當?shù)V工發(fā)現(xiàn)區(qū)塊有兩個相同長度的分叉 (fork) 時, 同時在全網(wǎng)廣播他們并且隨機均勻地在這兩個分支上繼續(xù)挖礦. 改進版本的比特幣協(xié)議可以阻止那些控制少于 1/4 資源的自私礦池成為一個控制絕大多數(shù)資源的礦池, 優(yōu)于改進之前的門限值 0. Nayak 等擴展了挖礦策略的空間 [29] , 其中包括了 “頑固” 策略 (“stubborn” strategies), 他們證明了對于較大規(guī)模的策略空間來說自私挖礦并不是一個好的策略. Nayak 等主要研究了兩類挖礦攻擊: 類自私挖礦攻擊 (“selfish-mining”-style) 和網(wǎng)絡(luò)層次的攻擊, 又稱之為日食攻擊 (eclipse attack). 一個礦工可以將挖礦供給和網(wǎng)絡(luò)層次的日食攻擊結(jié)合起來增大他的收益. 也就是說, 當給定最優(yōu)策略時, 某些日食攻擊的受害者可以在攻擊過程中受益.
Heilman 引入了首選重置 (freshness preferred, FP) 機制 [30] , 該機制通過使用不可偽造時間戳來懲罰那些不及時釋放區(qū)塊的自私礦工. 他們將 Eyal 和 Sirer [28] 中的門限由 0.25 提升至 0.32. 然而該機制不是激勵相容的, 而且對于可偽造的時間戳不具備健壯性. 也就是說 FP 機制的實現(xiàn)依賴于不可偽造的時間戳, 但是不可偽造的時間戳又很難實現(xiàn) [31,32] , 因此該機制的實現(xiàn)具有一定的局限性. Solat 和 PotopButucaru 針對自私挖礦攻擊和截留攻擊 (withholding attack) 提出了一個解決方案: ZeroBlock [33] , 該方案不需要使用時間戳 (timestamp) 技術(shù), 因為時間戳可以被偽造. 在 ZeroBlock 方案中, 如果一個自私礦工持有區(qū)塊的時間超過幅度間隔 (mat interval), 例如, 最大的可接受一個新區(qū)塊的等待時間, 那么誠實礦工就會拒絕接受這個新區(qū)塊.
Sapirshtein 等擴展了文獻 [28] 的工作, 提出了一個高效算法 [34] , 該算法可以計算 ε-optimal 的自私挖礦策略, 其中 ε > 0. 他們證明了算法的正確性, 并分析了其誤差范圍. 使用這種高效算法, 礦工可以計算自私挖礦策略獲得更大的收益, 而且自私礦工需要控制的資源也少于 1/4, 也就是說攻擊者及時控制的資源少于 1/4 也有利可圖, 這樣就增加了攻擊者的能力, 使他們有機可乘. 他們還證明如果考慮區(qū)塊在網(wǎng)絡(luò)傳播中的延遲, 門限值又變?yōu)?0, 即, 攻擊者不論控制多少資源, 總存在一個自私挖礦策略, 其帶來的收益高于誠實挖礦的收益. 最后他們總結(jié)了自私挖坑和雙花 (double spending) 之間的相互作用. 文獻 [27,28,34] 討論的都是一個礦池對誠實礦工的攻擊. Eyal 討論了兩個礦池之間的攻擊 [35] , 兩個礦池之間存在個人理性與集體理性的矛盾, 這類似于公共地悲劇博弈. Eyal 提出了兩個礦池之間的截留攻擊, 一個攻擊礦池 (attacking pool) 的管理者首先在另一個受害礦池 (victim pool) 注冊為正常礦工, 他從受害礦池接受若干任務(wù)并把這些任務(wù)指派給攻擊礦池中的滲透礦工 (稱之為 infiltrating miners), 滲透礦工在攻擊礦池中的比例稱之為滲透率 (infiltration rate). 攻擊礦池會把滲透礦工的部分工作能力提交給受害礦池, 讓受害礦池評估滲透礦工的能力, 當滲透礦工提交完全的工作證明時, 攻擊礦池忽略這些工作. 截留攻擊的缺陷在于受害礦池的總體計算能力沒有增加 (滲透礦工不工作), 但是它的平均預(yù)算卻降低了. 一方面攻擊礦池分出一部分計算能力給受害礦池, 其自身的計算能力也受到了損害. 因此, 總體來說截留攻擊降低了整個網(wǎng)絡(luò)的計算能力. 對于兩個礦池來說, 采取截留攻擊是唯一的納什均衡, 然而如果雙方都不采取截留攻擊, 他們的收益會更大. 從博弈論角度分析, 是否采取截留攻擊對礦池來說是一個礦工的困境 (miner’s dilemma), 礦工不斷的挖礦過程就類似與一個重復(fù)囚徒困境博弈. Rosenfeld 建議修改區(qū)塊結(jié)構(gòu)來解決這一問題 [36]
