结合区块链技术的改进K-匿名激励机制方案

徐 健，温 蜜，张 凯

上海电力大学 计算机科学与技术学院，上海200090

1 引言

随着移动互联网的迅猛发展，基于位置的服务大量出现在日常生活服务中，如美团、百度地图和饿了么等。基于位置服务（Location Based Service，LBS）[1]是服务提供商基于用户地理位置信息向其提供相应服务的一种网络服务。然而，移动用户的位置隐私所面临的诸多威胁并没有得到充分关注，因为用户只有将自己的地理位置信息提交给服务商后，才可以享受服务商提供的服务。Beresford 和Stajano[2]首先将位置隐私定义为阻止其他各方了解自己当前或过去的位置的能力。为了保护位置隐私，Chow 等人[3]提出了多种保护移动用户位置隐私的方法，目前最广泛的方法是Gruteser和Grunwald[4]从数据隐私保护中[5]引入的K-匿名技术。K-匿名[6]技术的基本思想是在移动用户和LBS 提供商之间设置一个安全可信第三方代理进行中继通信。当移动用户使用LBS，代理通过返回一个至少包含K-1其他移动用户的隐匿区域来调整实际用户位置信息的分辨率并将其发送给LBS 服务器，然后将LBS 服务器返回的数据转发给请求用户，从而使攻击者无法准确区分出同一隐匿区域中的真正的请求服务用户和其他用户[7]。K-匿名技术简便易于实现，无需占用大量计算资源，并能取得较好的隐私保护效果，因此被大量应用于位置隐私保护方案中[8]。然而，K-匿名技术要求必须至少有K 个处于匿名集合之中的移动用户生成一个隐匿区域。在实际的LBS 应用场景中，各用户节点间互不信任，并且不是所有用户都关注他们的隐私泄漏问题[9]。而且，在实际应用中，即使某一个节点愿意向其他节点提供帮助生成K-匿名隐匿区域，它也无法从中获得任何利益。因此，一般节点通常会拒绝向他人提供帮助，导致LBS请求者无法构造K-匿名集合，无法获得匿名服务。

因此，Yang等人[10]将P2P网络中被大量研究的激励机制引入到了生成K 匿名集合中，它的基本思想是用拍卖游戏来实施激励机制通过向其他节点提供服务，使网络中的节点直接受益。该方案是基于文献[11]中的拍卖模式提出的。

然而，文献[10]所提出的方案有以下不足：（1）文中所提拍卖师是一个可信的第三方，这在现实中是不存在的，并且一旦该第三方受到DOS 攻击，激励机制就无法正常运作；（2）由于交易信息过度集中化，当用户出现大量访问请求，会导致运行激励机制的第三方服务器瞬间瘫痪；（3）同时该方案缺乏有效的惩罚机制，无法限制恶意用户的参与。从而限制了激励机制在K-匿名隐私保护场景中的应用。

针对以上问题，本文提出了一种新的K-匿名隐私保护激励机制设计方案。首先改进现有的激励机制方案并与区块链[12]智能合约[13]结合，具备以下创新点：（1）激励机制运行于区块链各参与节点中可以做到去中心化交易有效抵御DOS攻击；（2）区块链采用P2P交易形式，可避免交易信息过度集中出现算力瓶颈；（3）智能合约中加入保证金准入机制，可有效限制恶意用户加入，且由于运行于公链上可激励更多用户加入该激励机制。

2 区块链与智能合约

区块链是一种由所有用户同时存储和维护的点对点去中心化交易账本[14]。该账本是按照时间顺序将交易数据由矿工打包处理生成区块，并以顺序相连的方式组合成的一种链式数据结构，利用密码学数字签名方式保证数据不可篡改和不可伪造。矿工可以通过计算随机哈希散列的数值解争夺处理交易和维护区块链账本的权力并收取费用，并且能够自由加入和退出以达到去中心化的作用[15]。

智能合约[16]是一套以数字形式定义的承诺，该承诺控制着数字资产流转，并包含了合约参与者约定的权利和义务，合约是由计算机系统自动执行。智能合约以数字化的形式写入区块链中，由区块链技术的特性保障存储、读取、执行[17]。同时，由区块链自带的共识算法构建出一套状态机系统，使智能合约能够高效地运行[18]。

智能合约允许交易实体根据其他事务、事件或时间存储和转移资金的条件编写规范，提供了实施和执行金融交易规则的机会，并且不依赖于可信的第三方（如银行、公用事业）。如图1 所示：在区块链2.0 中，可以将各种合约提前用代码逻辑编写好，由矿工记录发布于区块链上，每个节点都可以访问它，通过向其发送指定的交易和事件触发写好的代码逻辑然后进一步生成新的交易和事件，同时可以包含公链上通用货币的代管，然后根据合约中规定的条件支付给各种其他合约。

图1 区块链2.0

智能合约与区块链相结合迎来了区块链2.0 时代，以期实现更为复杂的功能。目前，比特币[12]和以太坊[16]是最被广泛使用的两大公共区块链。尽管比特币交易可以包括基本的脚本能力但其主要还是作为密码货币。而以太坊除了对以太坊密码货币的支持外还可以执行智能合约。

3 系统结构

本文基于区块链智能合约，提出了一种去中心化K-匿名激励机制。智能合约开发时写入合约自动达成时的条件，以激励用户加入一个K 匿名群体。服务请求者和K-匿名服务提供者按照智能合约中的规则合作以实现K-匿名的目标。生成K-匿名隐匿区域并通过合智能合约验证后，这些K-匿名服务提供者会得到相应的奖励。为了安全以及更好地确定参与用户人选，该方案采取保证金准入机制并使用与文献[10]中所不同的单向拍卖机制来完成K-匿名的需求，拍卖过程被整合到智能合同中[19]。拍卖记录由矿工保存在区块链系统中，而不是在一个中心服务器中，实现去中心化的目的。

本文方案系统架构如图2 所示，由卖家(K-匿名请求人）和买家（投标人）组成，并假设每个卖家和投标人都可通过智能设备访问，确定是否完成LBS 信息查询。此外，假定卖方和投标人及其智能设备可以向区块链智能合约发送和接收消息，并且每个投标人都有一份自己的公私密钥对，能够对自己发送的内容进行签名，确保交易内容的唯一性和不可抵赖性。该体系结构实现了四个关键部分，包括（1）投标人、（2）卖方、（3）智能设备和（4）智能合约。各部分的功能如下：

申请人代理：申请人代理将在需要服务时发起新的拍卖，并向智能合约发送要求数量K 以及保证金。

投标人代理：每个投标人代理可以随时监控公链上的智能合约状态，如果有人发起拍卖申请，可申请加入，向智能合约发送一定数量保证金。

智能设备：可以向LBS 服务器发送LBS 请求，也可以向区块链智能合约发送和接收消息。

智能合约：智能合同将接收并存储来自申请人、投标人和智能设备发送的数据，并执行拍卖和支付功能。

图2 系统架构

该激励机制主要执行过程如下：

（1）在公有区块链上部署智能合约。

（2）申请人公布所需要的K 匿名数量及保证金额度。

（3）潜在的竞买人监视区块链以进行新的拍卖并提交出价。

（4）智能合约执行拍卖活动以确定中标者。

（5）前K+1名支付保证金最高者获得任务完成机会，与买家形成一个K 匿名群组。

（6）位置隐私保护任务开始，中标的买家和卖家组成了一个匿名组。组中的所有成员都将其位置和请求发送给服务提供商。攻击者只能找到K 个用户一起请求服务，无法确定哪一组位置和请求是真的。

（7）任务完成，进行款项交割，奖励金加上保证金一并退回中标账号。

4 激励机制设计

本章中所使用的符号意义如表1所示。

表1 各符号对应意义

4.1 保证金准入机制

该激励机制以拍卖活动的形式进行，Us是卖家，Ub是买家，智能合约则作为拍卖人，为了便于说明，当不具体区分买卖双方时，统称这二者为代理人。为保证参与用户权益，需要卖家和买家先向拍卖人支付一定数额的保证金才能发起拍卖活动，以防止任一用户出现违约情况时，由拍卖人进行赔偿。卖家为想要实现的K-匿名隐私保护提供价格，向智能合约发送一笔保证佣金V,并提供Ki件货物名额（即所需要参加K-匿名用户数量）。若卖家违约，则该保证金均等赔偿给中标用户。则每位Ub赔偿金额为：

而买家则需要向拍卖人支付参与一定数额的保证金Bi才能参加该拍卖活动，若部分买家中途退出或出现违约行为，则保证金全部没收赔偿给卖家。

4.2 单项拍卖算法

（1）本文将K 匿名拍卖建模为单轮密封出价拍卖。拍卖过程如图3所示。

（2）由于该拍卖活动是密封的出价，每个代理人提供的价格是代理人根据自身要求提出的，没有代理人有兴趣知道由其他人提供的价格。Bj(Bj＞0)既作为保证金同时也作为Ubj的出价（注意Bj不一定等于Cj）。拍卖开始时，卖方首先向拍卖人提出自身要求发起拍卖活动，买方相应提交出价获得参加资格。以所给出买方的出价和卖方的要求作为输入，拍卖人确定中标买方组WG，且满足：

图3 拍卖游戏

（3）拍卖开始后，委托人账户向拍卖人账户发送标的数额以及相应的保证金V，竞买人若要参加拍卖，则可以向拍卖人账户发送愿意支付的保证金Bj，拍卖人对竞买人发送的Bj进行排序，且满足：

拍卖人首先要检查委托人和竞买人的总数是否至少为Ki+2。这里需要比K 匿名要求数量更多的两个代理人，为了保证真实，需要去掉排名最高和最低的两个竞买人。拍卖人选择满足以下要求的Ki+1个竞买人作为中标人：

若该情况成立，则缴纳保证金额度最多的前K+1个竞买人成为中标赢家，每个竞买人都得到参与完成该次位置隐私保护任务并可获取委托人佣金的机会。未中标的买家则返还他们的保证金。

单向拍卖算法流程如图4所示。

图4 单项拍卖流程图

4.3 智能合约设计

本节详细介绍智能合约以及用于启用单向拍卖的相关功能。智能合约假定密码货币（例如：以太币）可以在卖方和买方之间进行货币交换且具有现实意义，该智能合约主要包括以下函数：初始化函数、投标函数、拍卖函数、退款函数、奖惩函数。各主要函数功能详述如下：（1）初始化函数：此函数定义与该拍卖游戏相关的所有值。每一项合同必须保持一组变量，代表拍卖的数量(K)、投标清单（出价）、投标时间（bTime）、交易时间（tTime）、揭晓期时间（rTime）以及拍卖中是否有任何当前的中标者(W)。

委托人必须调用初始化函数来初始化新的拍卖，然而，在进行新的拍卖之前，委托人代理必须向合同支付保证金，以防止恶意拍卖。在委托人所提交的K 匿名位置隐私保护任务完成之后，该保证金将被平均支付给参与任务的中标人。在初始化函数执行之后，该智能合约准备接受各竞买人投标。

（2）投标函数：通过监测区块链网络上的智能合约，不同的竞买人可以查看何时有人寻求匿名帮助可供拍卖以及提交他们的出价。这个步骤都必须在预定义的时间bTime 内执行。投标函数向智能合约提交了一个投标，但没有透露他们的出价。投标函数接受数据为＜b,Hbid,deposit,nonce ＞ 的 元 组 ，Hbid=H(bid,nonce),H 是一个陷门函数（例如密码散列函数），Nonce是为该交易选择的随机值，hbid 将被存储在区块链上，直到投标周期结束。投标函数还要求各竞买人将保证金从竞买人的代理账户转移到智能合约账户中，以防止竞标人提交欺诈性投标。

（3）拍卖函数：在每个出价被披露之后，合同将执行拍卖函数来执行单项拍卖算法来确定拍卖买受人和结算价格。拍卖函数将每个显示的出价与当前规定范围内的最低出价进行比较。如果发现新的高出价，规定范围内的最低和次最低出价将增加，并记录当前规定范围内的最低出价投标者。

（4）退款函数：在bTime时间后，拍卖买受人将被选中，开始执行K-匿名任务。此时调用退款函数将未中标竞买人的保证金退还，而买受人将继续留在智能合约中。

（5）奖惩函数：在隐私保护交易完成(t ＞tTime)后执行，以完成最终K 匿名任务和金融结算的结果核算。最后确定功能从中标者发送的LBS服务信息中获得输入，以验证他们分别完成了LBS 查询任务。奖惩函数将被调用，用以奖励或处罚相关用户。

5 实验部分

5.1 拍卖算法用时比较

实验所使用1台计算机配置为Inter i7-8550U 1.99GHz处理器和8 GB 内存，Windows10 64 位操作系统。实验使用Python 3.6 语言分别模拟不同数量的用户使用单向拍卖机制算法竞拍并与文献[10]进行相关实验对比。生成K-匿名群组所需要的时间与买家数量变化关系的结果如图所示，其中方块表示文献[10]中算法，圆点表示单向拍卖算法。

如图5 所示，当K=20时，文献[10]中由于假定具有相同隐私保护请求的用户已超过20 且自行组成K-匿名群体，从而不需要请求其他用户帮助，因此在该匿名要求下，文献[10]中所需要的时间与参与游戏的买家数量并没有关系。而单向拍卖算法依旧需要对参与游戏的买家进行排序选择生成群组，因而生成K 匿名组合时间相对于文献[10]较长。

图5 K=20时匿名区域生成时间

如图6 所示，当K=120 时，文献[10]中算法需对卖家和买家分别进行排序，随着参与人数增加所花费时间越来越多。而本文中算法仅是针对参与游戏的买家用户进行排序，当参与人数少于120 时生成K 匿名区域失败，当参与人数大于或等于120 时，采用快速排序算法并生成K-匿名区域。从图中可以看出单项拍卖算法生成K 匿名组合时间相对于文献[10]中较短。

图6 K=120时匿名区域生成时间

5.2 智能合约实验

以太坊是一个可实现智能合约的开源区块链平台，智能合约相当于存储在该平台区块链中的程序，以太坊虚拟机支持运行已编写好的智能合约，可允许用户使用测试区块链进行智能合约的测试。以太坊平台有其专属通用代币，在测试时可以自动为指定账户充值一定量代币做实验。

本文智能合约采用类似于JavaScript 的高级语言Solidity 语言编写，并在以太坊环境下使用其官方推荐的IDE—Remix 上对智能合约进行实验测试，内核版本为0.4.24，同时Remix 提供了相应的程序接口。合约调试编译结果及部分代码如图7所示。

图7 智能合约

Remix 为智能合约提供了一个区块链环境，图7 页面为测试智能合约时的部分页面，该页面顶部提供了测试合约时可使用的功能。智能合约代码在调试后在图中底部出现蓝色框则表示合约代码编译成功，ABI则表示该智能合约的接口地址。接着可对智能合约中各主要函数进行测试，测试界面如图8 所示：该测试环境会默认提供多个账户，且账户中有少量以太币用于调用函数测试交易，图8 下方则显示该智能合约中设计的各函数，可依次点击各函数进行交易测试。

图8 智能合约函数测试

目前以太坊的平均出块时间为15 s，上述智能合约的实验测试结果可以看出，该智能合约很好地实现了激励机制所设计的功能，并且实验验证了智能合约的有效性与可行性。以区块链网络为载体，使本文所提激励机制可面向更多用户。

6 安全性能分析

（1）无需第三方机构：与传统的激励机制设计不同，本文所提激励机制采用基于区块链的去中心化架构来保证其安全性，智能合约充当第三方机构被同步运行在公有区块链所有节点中，不依赖于全局可信的第三方实体机构，各节点间采用端到端的通信方式，分布式存储交易数据，可以有效解决中心化模式下的计算资源不足等问题；而当部分公有区块链节点遭遇分布式拒绝服务攻击时，其他的公有区块链节点中依旧可以正常工作并保存着所有的交易记录，不至于使整个激励机制系统崩溃。

（2）节点身份隐私保护：由于本文所提激励机制是基于区块链系统实现，参与该激励机制的用户为区块链中各代理节点，且都采用假名保护的方式来进行通信，切断了用户名与其真实身份之间的联系，通信双方或第三方无法获知通信节点的真实身份；同时，结算过程中使用不同用户的非对称密钥对发送的数据进行加密，攻击者很难破解所有节点的加密密钥，最大可能保证相关交易信息安全。

（3）位置隐私保护：保护用户的位置隐私是保护用户身份信息与位置信息的关联。本文采取K 匿名技术通过对使用K 名用户同时向LBS服务器发送服务申请，混淆身份信息与位置信息的一一对应关系。该公有区块链上每个用户只是用一串数字账户作为代理，初始便以假名机制构造K-匿名群组，极大提高了安全性。该基于区块链的K 匿名激励模型只是隐藏了身份信息与位置信息的对应关系；但保留了精确的位置数据，并且在选择K 匿名组成员时比之前方案更充分地考虑了用户的忠诚度，也采取收取保证金的方式在一定程度上限制了部分恶意节点的参与，提高了形成K 匿名组的成功率。因此，本方案既保护了用户的位置隐私也提供了较高的服务质量。

7 结束语

本文提出了一种基于区块链智能合约的K-匿名激励机制。通过引入保证金制度可以有效限制恶意玩家节点的加入，从而有效提高生成K-匿名区域的成功率。本文基于区块链的去中心化架构可使智能合约运行于所有区块链节点中，凭借众多的公有区块链用户节点，可以吸引更多用户参与K-匿名。并提出一种单向拍卖算法，实验仿真结果显示相较于相关工作在算法执行速度上有一定的优势。本文对该方案进行分析，相关结果证明该方案安全可靠且该激励机制是具有实用性的。后续工作可以对该激励机制算法进一步优化以及采用盲签名技术等密码学方法加强智能合约中节点间发送交易数据的安全性。