摘 要: 区块链是比特币的底层技术, 用于分布式地存储比特币的历史交易信息. 区块链中的每个区块包含若干交易信息, 矿工一旦挖到新的区块, 就将其加入区块链, 并以密码学方式保证区块信息不可篡改和不可伪造. 为了保证系统正常运行, 区块链将经济因素集成到激励层, 为矿工提供充足的动机去寻找新的区块, 激励层主要包括经济激励的发行机制和分配机制等. 因此, 如何设计高效实用的激励层成为区块链中的关键问题. 博弈论作为现代数学的一个重要分支, 已经成为分析经济学理论的标准工具之一, 可以用来研究激励层的机制设计, 提高区块链的效率和实用性. 本文首先分析了博弈论、安全多方计算和比特币 (区块链 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]
