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