引用本文

唐长兵, 杨珍, 郑忠龙, 陈中育, 李翔. PoW共识算法中的博弈困境分析与优化. 自动化学报, 2017, 43(9): 1520-1531. doi: 10.16383/j.aas.2017.c160672

TANG Chang-Bing, YANG Zhen, ZHENG Zhong-Long, CHEN Zhong-Yu, LI Xiang. Game Dilemma Analysis and Optimization of PoW Consensus Algorithm. ACTA AUTOMATICA SINICA, 2017, 43(9): 1520-1531. doi: 10.16383/j.aas.2017.c160672

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2017.c160672

关键词

区块链，工作量证明，共识算法，区块截留攻击，纳什均衡，零行列式策略 

摘要

区块链是随着比特币等数字加密货币逐渐兴起而盛行的一种新型去中心化分布式系统，具有去中心化、时序数据、集体维护、可编程和安全可信等特点.目前，区块链已引起政府部门、金融机构、科技企业和资本市场的高度重视与广泛关注.如何在一个去中心化的分布式系统中高效地达成共识是区块链技术研究的重要问题.本文从工作量证明（Proof of work，PoW）共识算法的挖矿困境入手，分析PoW共识过程中矿工策略选择的纳什均衡存在条件.利用零行列式（Zero determinant，ZD）策略对矿工策略选择进行优化，并通过数值仿真来验证优化算法的有效性.概括来说，本文从博弈论角度来理解和剖析PoW共识算法，为进一步设计基于博弈论的共识算法提供新的思路和方法.

文章导读

区块链技术最初是为比特币设计的一种特殊数据库技术, 它基于密码学中的椭圆曲线数字签名算法来实现去中心化的P2P系统设计[1-3].但区块链的作用不仅仅局限于比特币.现在人们在使用区块链这个词时, 有时是指数据结构, 有时是指数据库, 有时则是指数据库技术.从数据的角度来看, 区块链是一种分布式数据库(或称为分布式共享总账[4], Distributed shared ledger), 这里的“分布式”不仅体现为数据的分布式存储, 也体现为数据的分布式记录(即由系统参与者集体维护); 从记录效果的角度来看, 区块链可以生成一套记录时间先后、不可篡改、可信任的数据库, 这套数据库是去中心化存储且数据安全能够得到有效保证.具体地说, 区块链技术就是一种大家共同参与记录信息和存储信息的技术.过去, 人们将数据记录和存储的工作交给中心化的机构来完成, 而区块链技术则让系统中的每一个人都可以参与数据的记录和存储.区块链技术在没有中央控制点的分布式对等网络下, 使用分布式集体运作的方法, 构建了一个P2P的自组织网络[3].通过复杂的校验机制, 区块链数据库能够保持完整性、连续性和一致性, 即使部分参与人作假也无法改变区块链的完整性, 更无法篡改区块链中的数据.区块链技术涉及的关键点包括:去中心化(Decentralized)、去信任(Trustless)、集体维护(Collectively maintain)、可靠数据库(Reliable data base)、时间戳(Time stamp)、非对称加密(Asymmetric cryptography)等[1].

区块链技术原理的来源可归纳为数学上的拜占庭将军问题[5-6].将拜占庭将军问题延伸到互联网生活中来, 其内涵可概括为:在互联网大背景下, 当需要与不熟悉的对手进行价值交换活动时, 人们如何才能防止不会被其中的恶意破坏者欺骗和迷惑, 从而做出错误的决策.而如果进一步将拜占庭将军问题延伸到技术领域中来, 其内涵可概括为:在缺少可信任的中央节点和可信任通道的情况下, 分布在网络中的各个节点应如何达成共识.从这些角度来看, 区块链技术解决了闻名已久的拜占庭将军问题, 它提供了一种无需信任单个节点, 还能创建共识网络的方法.

作为区块链技术最成功的应用, 比特币系统应用工作量证明(Proof of work, PoW)[7]的共识机制实现交易的不可篡改性和不可伪造性[8]. PoW共识机制的核心思想是通过引入分布式节点的算力竞争来保证数据的一致性和共识的安全性.比特币系统中, 各节点基于各自的算力相互竞争, 共同解决一个求解复杂但验证容易的SHA256数学难题, 最快解决该难题的节点将获得区块记账权和系统自动生成的比特币奖励.具体过程如下:如果想产生一个区块并写入到区块链中, 需要找到一个小于系统规定难度值的随机数, 这样才可能被其他节点认可, 并写入到区块链中.而找到随机数需要输出密码散列函数家族SHA256的哈希算法.其中, 一个符合要求的输出值由N个前导零构成.零的个数取决于网络的难度值, 挖矿难度越高, 零的个数会越多.当输出值不满足要求时, 这个随机数就会增加一个单位, 直到找到为止.找到合适随机数后, 节点获得记账权和相应比特币奖励, 并将该过程中产生的所有交易记录在区块上, 所有区块按时间顺序连接则构成区块链.一般地, 比特币系统通过灵活调整随机数搜索的难度值来控制区块的平均生成时间.

在比特币系统中, 产生区块的过程称为挖矿, 进行挖矿的参与者称为矿工[9].由于比特币系统大约每10分钟产生一个区块, 这意味着大部分矿工在一定时间内很难产生区块.为了增加获得稳定收益的可能性, 矿工会选择加入开放矿池进行合作挖矿.具体地, 矿池中的矿工需要耗费资源尝试产生区块, 即发送完整工作量证明给管理者.但完整工作量很难产生, 矿工也可以选择发送部分工作量证明获得相应收益.无论哪个矿工产生区块, 获得的收益将按贡献比例分配给每个矿工.参与者注册为矿工很简单, 只需要提供一个公共的网络接口就可以加入开放矿池, 因此开放矿池很容易受到攻击.有些注册矿工只发送部分工作量证明, 当产生完整工作量证明时就会将其抛弃, 这种攻击方式被称为区块截留攻击[10-11].在这种情形下, 攻击者发送部分工作量证明, 但不会对矿池产生有效收益, 这也导致攻击者与其他矿工共同分享矿池收益, 从而减少其矿池的收益[12-13].

研究表明, 在一个开放的矿池中, 矿工可以通过攻击其他矿工增加自己的收益.如果所有矿工都选择攻击对方, 那么他们获得的收益将少于他们互不攻击时获得的收益.这就是PoW共识算法中的挖矿困境, 而这种困境也对应到博弈论中经典的囚徒困境(Prisoner′′s dilemma)[14-16], 即攻击对个体而言是最优策略, 但却不是系统最优的.如何理解和分析挖矿过程中的博弈困境无疑给比特币的发展和技术开发乃至投入使用提供了理论基础.例如Eyal基于博弈理论, 定性地分析了挖矿过程中的困境[17], 但并没有给出纯策略存在条件以及相应证明.本文在文献[17]的基础上进一步分析矿工博弈困境的纯策略和混合策略均衡, 并给出两种均衡存在的条件.

更为重要的是, PoW共识机制存在着显著的缺陷, 其强大算力造成的资源浪费(例如算力)历来为研究者所诟病, 而且长达10分钟的交易确认时间使其相对不适合小额交易的商业应用.与此同时, 随着区块链技术的发展和各种数字币的相继涌现, 研究者提出多种不依赖算力而能够达成共识的机制, 例如权益证明(Proof of stake, PoS)共识[18], 授权股份证明机制(Delegated proof of stake, DPoS)共识[19], 缠结(Tangle)[20]以及Tendermint[21]机制等.而最理想的共识算法是系统中的节点达成的共识是一个纳什均衡[21], 即单方面改变自己的策略都不会提高自身的收益.这为基于博弈论构建共识机制提供了新的思路.另一方面, PoW共识过程中的挖矿困境对应经典的囚徒困境模型, 其纳什均衡为互相攻击, 此时的系统收益并不能达到最优.为提高系统的整体效益, 有必要建立相关机制, 使矿工趋向于合作, 以获得较高的系统收益, 从而为实现高效的共识算法提供依据.

零行列式(Zero determinant, ZD)策略是近几年在博弈论中兴起的一种新方法, 它能够打破传统的纳什均衡理论.如Press和Dyson[22]用ZD策略优化囚徒困境模型, 一方面可以解决系统收益低问题, 另一方面, 无论对手采取何种策略, 都可以强迫对手与自己收益之间满足线性关系[23-24].此外, ZD策略被应用到无线网络中的资源管理[25]和频谱共享[26]等问题.这些都为本文运用ZD策略对矿工的策略选择进行优化提供了参考和借鉴.

本文组织结构为:第1节介绍区块截留攻击和博弈理论中的纳什均衡及囚徒困境模型; 第2节利用博弈均衡理论对矿工算力相同和不相同两种情形的挖矿困境进行分析, 给出纯策略均衡以及混合策略均衡存在条件; 第3节运用ZD策略对区块截留攻击博弈进行优化, 得到获得较高系统收益时矿工策略选择的优化条件; 第4节给出数值仿真; 第5节总结本文内容, 并对今后工作进行展望.

图 1  矿工纯策略纳什均衡分布图

图 2  算力不同时矿工的收益分布情况

图 3  当矿工算力相同时, LM采用不同策略, SM始终采用WSFS策略后, 系统收益分布情况

一方面, 均衡分析是博弈论中的一块重要内容.本文对共识算法挖矿困境的分析, 对理解和剖析PoW共识算法本身具有一定的理论参考价值.具体地, 当矿工算力相同时, 3种情况的纯策略纳什均衡分为(A, A), (C, C)和(A, A), (C, C).对于混合策略均衡, 给出均衡存在条件, 并得到两个重要结论: 1) 当收益扩大倍数r不变时, 资源耗费c与合作概率成正比; 2) 当c不变时, 收益扩大倍数r与合作概率成反比.当矿工算力不相同时, 根据参数满足不同的条件, 可以将此时的困境分为4种, 纯策略纳什均衡分别为(A, A), (C, C), (A, A)和(C, C), (A, C).通过分析得到混合策略均衡存在条件, 以及一个重要结论:当收益扩大倍数r和费用支出c保持不变时, 矿工的算力与合作的概率成反比.这些性质, 对矿工挖矿的均衡选择起到理论指导意义.

另一方面, 有效共识机制的设计一直是区块链技术的核心问题.在PoW共识算法中正常挖矿的纳什均衡是相互攻击, 给系统本身造成资源浪费.本文应用ZD策略对PoW共识算法中矿工的策略选择进行优化, 使得系统收益达到最大化, 为进一步设计基于博弈论的高效共识算法提供了新的研究思路和方法.具体地, 对PoW共识过程中矿工的策略选择进行优化, 发现LM采取ZD策略, 可以使系统收益达到较高值, 甚至控制系统收益, 使之达到最优, 也可以使SM的收益与自己的收益保持线性关系, 并给出数值仿真, 进一步说明结论的正确性.

此外, 以太坊中的PoS共识算法中也存在类似的策略选择困境:权益较大者忠实于矿池是否能获得高收益, 权益较小者忠实于矿池是否一定能维护自己的权益并获得相应收益.后续工作将对这种情况及区块链中类似模型进行分析, 通过对系统均衡的分析, 设计更合理更有效的共识机制.

作者简介

唐长兵 

博士, 浙江师范大学数理与信息工程学院讲师. 2015年获得复旦大学博士学位.主要研究方向为复杂网络, 博弈理论及其应用, 网络安全与优化控制.E-mail: tangcb@zjnu.cn

杨珍

浙江师范大学数理与信息工程学院硕士研究生.2015年获得河北科技师范学院学士学位.主要研究方向为区块链技术, 博弈理论及其应用.E-mail: y_zh_en@163.com

郑忠龙

浙江师范大学数理与信息工程学院教授.2005年获得上海交通大学博士学位.主要研究方向为数据科学, 机器学习, 图像处理.E-mail: zhonglong@zjnu.edu.cn

李翔

复旦大学信息科学与工程学院教授. 2002年获得南开大学博士学位.主要研究方向为复杂网络与系统控制.E-mail: lix@fudan.edu.cn

陈中育

浙江师范大学数理与信息工程学院教授.2011年获得上海大学博士学位.主要研究方向为软件形式化方法, 需求建模技术, 区块链应用技术.本文通信作者. E-mail: czy@zjnu.cn