ｃｈｎｉｑｕｅ，ｗｉｔｈｏｕｔ　ａｎｙ　ｔｒｕｓｔｅｄ　ｔｈｉｒｄ　ｐａｒｔｙ，ｔｈｅ　ｒｅｑｕｅｓｔ　ｕｓｅｒ　ｃａｎ　ｓｕｂｍｉｔ　ａｎ　ａｎｏｎｙｍｏｕｓ　ｃｌｏａｋｉｎｇｒｅｇｉｏｎ　ｔｈａｔ　ｉｎｃｌｕｄｅｓ　ｔｈｅ　ｌｏｃａｔｉｏｎｓ　ｏｆ　ｏｔｈｅｒ　ｃｏｏｐｅｒａｔｉｖｅ　ｕｓｅｒｓ　ｉｎｓｔｅａｄ　ｏｆ　ｈｉｓ／ｈｅｒ　ｒｅａｌ　ｌｏｃａｔｉｏｎ．Ｉｎｔｈｉｓ　ｗａｙ，ｔｈｅ　ａｄｖｅｒｓａｒｙ　ｃａｎ　ｉｄｅｎｔｉｆｙ　ｔｈｅ　ｒｅｑｕｅｓｔ　ｕｓｅｒ’ｓ　ｒｅａｌ　ｌｏｃａｔｉｏｎ　ｗｉｔｈ　ａ　ｓｕｆｆｉｃｉｅｎｔ　ｎｅｇｌｉｇｉｂｌｅｐｒｏｂａｂｉｌｉｔｙ．Ｆｕｒｔｈｅｒｍｏｒｅ，ｃｏｍｐａｒｅｄ　ｗｉｔｈ　ｏｔｈｅｒ　ｍｅｔｈｏｄｓ，ｔｈｅ　ｄｉｓｔｒｉｂｕｔｅｄ　Ｋ－ａｎｏｎｙｍｉｔｙ　ｍｅｔｈｏｄ　ｉｓａｂｌｅ　ｔｏ　ｐｒｏｖｉｄｅ　ｐｒｅｃｉｓｅ　ｑｕｅｒｙ　ｒｅｓｕｌｔｓ　ｗｉｔｈｏｕｔ　ａｎｙ　ｒｅｑｕｉｒｅｍｅｎｔ　ｆｏｒ　ｃｏｍｐｌｉｃａｔｅｄ　ｃｒｙｐｔｏｇｒａｐｈｉｃｔｅｃｈｎｏｌｏｇｉｅｓ　ｒｅｄｕｃｅ　ｔｈｅ　ｒｅｑｕｅｓｔ　ｕｓｅｒ’ｓ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｂｕｒｄｅｎ．Ｉｎ　ｌｉｇｈｔ　ｏｆ　ｔｈｅｓｅ　ａｄｖａｎｔａｇｅｓ，ｔｈｅｄｉｓｔｒｉｂｕｔｅｄ　Ｋ－ａｎｏｎｙｍｉｔｙ　ｍｅｔｈｏｄ　ｈａｓ　ｂｅｅｎ　ｗｉｄｅｌｙ　ｕｓｅｄ　ｔｏ　ｐｒｏｔｅｃｔ　ｔｈｅ　ｒｅｑｕｅｓｔ　ｕｓｅｒ’ｓ　ｌｏｃａｔｉｏｎｐｒｉｖａｃｙ　ｗｈｅｎ　ｈｅ／ｓｈｅ　ｅｎｊｏｙｓ　ＬＢＳ．Ｈｏｗｅｖｅｒ，ｔｈｅ　ｅｘｉｓｔｉｎｇ　ｄｉｓｔｒｉｂｕｔｅｄ　Ｋ－ａｎｏｎｙｍｉｔｙ　ｌｏｃａｔｉｏｎ　ｐｒｉｖａｃｙｐｒｏｔｅｃｔｉｏｎ　ｓｃｈｅｍｅｓ　ｄｏ　ｎｏｔ　ｃｏｎｓｉｄｅｒ　ｌｏｃａｔｉｏｎ　ｌｅａｋｉｎｇ　ｂｅｈａｖｉｏｒｓ　ａｎｄ　ｌｏｃａｔｉｏｎ　ｃｈｅａｔｉｎｇ　ｂｅｈａｖｉｏｒｓ　ｄｕｒｉｎｇｔｈｅ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ｏｆ　ａｎｏｎｙｍｏｕｓ　ｃｌｏａｋｉｎｇ　ｒｅｇｉｏｎ．Ｗｈｅｎ　ｄｉｒｅｃｔｌｙ　ａｄｏｐｔｉｎｇ　ｔｈｅ　ｅｘｉｓｔｉｎｇ　ｓｃｈｅｍｅｓ，ｏｎｏｎｅ　ｈａｎｄ，ａ　ｓｅｌｆｉｓｈ　ｒｅｑｕｅｓｔ　ｕｓｅｒ　ｃｏｕｌｄ　ｄｉｓｃｌｏｓｅ　ｔｈｅ　ｃｏｏｐｅｒａｔｉｖｅ　ｕｓｅｒｓ’ｌｏｃａｔｉｏｎｓ　ｔｏ　ｇａｉｎ　ｉｌｌｅｇａｌｂｅｎｅｆｉｔｓ．Ｏｎ　ｔｈｅ　ｏｔｈｅｒ　ｈａｎｄ，ａ　ｓｅｌｆｉｓｈ　ｃｏｏｐｅｒａｔｉｖｅ　ｕｓｅｒ　ｃｏｕｌｄ　ｐｒｏｖｉｄｅ　ａ　ｆａｋｅ　ｌｏｃａｔｉｏｎ，ｗｈｉｃｈ　ｌｅａｄｓｔｈａｔ　ｔｈｅ　ｃｏｎｓｔｒｕｃｔｅｄ　ａｎｏｎｙｍｏｕｓ　ｃｌｏａｋｉｎｇ　ｒｅｇｉｏｎ　ｃａｎｎｏｔ　ｓａｔｉｓｆｙ　ｔｈｅ　ｐｒｉｖａｃｙ　ｐｒｏｔｅｃｔｉｏｎ　ｒｅｑｕｉｒｅｍｅｎｔｏｆ　ｔｈｅ　ｒｅｑｕｅｓｔ　ｕｓｅｒ　ａｎｄ　ｍｏｒｅ　ｓｅｒｉｏｕｓｌｙ，ｔｈｅ　ａｄｖｅｒｓａｒｙ　ｃｏｕｌｄ　ｂｅ　ｕｓｅｄ　ｔｏ　ｄｉｒｅｃｔｌｙ　ｉｄｅｎｔｉｆｙ　ｔｈｅ　ｒｅｑｕｅｓｔｕｓｅｒ’ｓ　ｒｅａｌ　ｌｏｃａｔｉｏｎ．Ｔｈｅｒｅｆｏｒｅ，ｔｈｅｓｅ　ｓｃｈｅｍｅｓ　ｃａｎｎｏｔ　ｐｒｏｔｅｃｔ　ｔｈｅ　ｕｓｅｒｓ’ｌｏｃａｔｉｏｎ　ｐｒｉｖａｃｙｃｏｍｐｌｅｔｅｌｙ．Ｆｏｒｔｕｎａｔｅｌｙ，ｂｌｏｃｋｃｈａｉｎ　ｃａｎ　ｐｒｏｖｉｄｅ　ａｎ　ｏｐｅｎ　ａｎｄ　ｄｉｓｔｒｉｂｕｔｅｄ　ｌｅｄｇｅｒ　ｔｈａｔ　ｇｕａｒａｎｔｅｅｓ　ｔｈａｔｔｈｅ　ｒｅｃｏｒｄｅｄ　ｔｒａｎｓａｃｔｉｏｎｓ　ａｒｅ　ｉｎｈｅｒｅｎｔｌｙ　ｒｅｓｉｓｔａｎｔ　ｔｏ　ｍｏｄｉｆｉｃａｔｉｏｎ．Ｔｏ　ａｄｄｒｅｓｓ　ｔｈｅ　ｐｒｏｂｌｅｍｍｅｎｔｉｏｎｅｄ　ａｂｏｖｅ，ｔｈｉｓ　ｐａｐｅｒ　ｉｎｔｒｏｄｕｃｅｓ　ｂｌｏｃｋｃｈａｉｎ　ｉｎｔｏ　ｔｈｅ　ｄｉｓｔｒｉｂｕｔｅｄ　Ｋ－ａｎｏｎｙｍｉｔｙ　ｌｏｃａｔｉｏｎｐｒｉｖａｃｙ　ｐｒｏｔｅｃｔｉｏｎ　ａｎｄ　ｐｒｏｐｏｓｅｓ　ａｎ　ａｄｖａｎｃｅｄ　ｓｃｈｅｍｅ．Ｉｎ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｓｃｈｅｍｅ，ｔｈｅ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ｏｆａｎｏｎｙｍｏｕｓ　ｃｌｏａｋｉｎｇ　ｒｅｇｉｏｎ　ｉｓ　ｆｉｒｓｔｌｙ　ｒｅｇａｒｄｅｄ　ａｓ　ａ　ｔｗｏ－ｐａｒｔｙ　ｃｏｏｐｅｒａｔｉｏｎ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ｇａｍｅｂｅｔｗｅｅｎ　ｔｈｅ　ｒｅｑｕｅｓｔ　ｕｓｅｒ　ａｎｄ　ｃｏｏｐｅｒａｔｉｖｅ　ｕｓｅｒ　ｔｏ　ａｎａｌｙｚｅ　ｔｈｅｉｒ　ｓｔｒａｔｅｇｉｅｓ　ａｎｄ　ｕｔｉｌｉｔｉｅｓ，ａｎｄ　ｔｈｅｎｔｈｅ　ｓｅｃｕｒｉｔｙ　ｏｆ　ｄｉｓｔｒｉｂｕｔｅｄ　Ｋ－ａｎｏｎｙｍｉｔｙ　ｌｏｃａｔｉｏｎ　ｐｒｉｖａｃｙ　ｐｒｏｔｅｃｔｉｏｎ　ｉｓ　ｇｉｖｅｎ．Ａｆｔｅｒｗａｒｄｓ，ｂｙａｄｏｐｔｉｎｇ　ｂｌｏｃｋｃｈａｉｎ　ｔｏ　ｒｅｃｏｒｄ　ｔｈｅ　ｕｓｅｒｓ　ｉｎｖｏｌｖｅｄ　ｉｎ　ｔｈｅ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ｏｆ　ａｎｏｎｙｍｏｕｓ　ｃｌｏａｋｉｎｇ　ｒｅｇｉｏｎａｎｄ　ｔｈｅ　ｐｒｏｖｉｄｅｄ　ｌｏｃａｔｉｏｎｓ　ａｓ　ｅｖｉｄｅｎｃｅｓ，ｔｈｅ　ｃｏｒｒｅｓｐｏｎｄｉｎｇ　ｕｓｅｒｓ　ａｒｅ　ｐｕｎｉｓｈｅｄ　ｗｉｔｈ　ｕｎｓｕｃｃｅｓｓｆｕｌｌｙｃｏｎｓｔｒｕｃｔｉｎｇ　ｔｈｅ　ａｎｏｎｙｍｏｕｓ　ｃｌｏａｋｉｎｇ　ｉｎ　ｔｈｅｉｒ　ｆｕｔｕｒｅ　ＬＢＳ　ｑｕｅｒｉｅｓ　ｗｈｅｎ　ｌｏｃａｔｉｏｎ　ｌｅａｋｉｎｇ　ｏｒ　ｃｈｅａｔｉｎｇｂｅｈａｖｉｏｒｓ　ｏｃｃｕｒ．Ｔｈｅ　ｓｅｃｕｒｉｔｙ　ａｎａｌｙｓｉｓ　ｄｅｍｏｎｓｔｒａｔｅｓ　ｔｈａｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｓｃｈｅｍｅ　ｎｏｔ　ｏｎｌｙ　ｐｒｅｖｅｎｔｓｔｈｅ　ｒｅｑｕｅｓｔ　ｕｓｅｒ　ｆｒｏｍ　ｄｉｓｃｌｏｓｉｎｇ　ｔｈｅ　ｃｏｏｐｅｒａｔｉｖｅ　ｕｓｅｒｓ’ｌｏｃａｔｉｏｎｓ　ｂｕｔ　ａｌｓｏ　ｐｒｏｍｏｔｅｓ　ｔｈｅ　ｃｏｏｐｅｒａｔｉｖｅｕｓｅｒｓ　ｔｏ　ｐｒｏｖｉｄｅ　ｔｈｅ　ｒｅａｌ　ｌｏｃａｔｉｏｎｓ，ｔｈｅｒｅｂｙ　ｅｆｆｅｃｔｉｖｅｌｙ　ｐｒｏｔｅｃｔｉｎｇ　ｌｏｃａｔｉｏｎ　ｐｒｉｖａｃｙ　ｏｆ　ｔｈｅ　ｒｅｑｕｅｓｔ　ｕｓｅｒａｎｄ　ｃｏｏｐｅｒａｔｉｖｅ　ｕｓｅｒｓ．Ｅｘｔｅｎｓｉｖｅ　ｅｘｐｅｒｉｍｅｎｔｓ　ｉｎｄｉｃａｔｅ　ｔｈａｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｓｃｈｅｍｅ　ｄｏｅｓ　ｎｏｔ　ｉｎｃｒｅａｓｅｔｈｅ　ｃｏｍｐｕｔａｔｉｏｎ　ｄｅｌａｙ　ａｎｄ　ｃｏｍｍｕｎｉｃａｔｉｏｎ　ｃｏｓｔ　ｏｎ　ｂｏｔｈ　ｔｈｅ　ｒｅｑｕｅｓｔ　ｕｓｅｒ　ｓｉｄｅ　ａｎｄ　ｔｈｅ　ｃｏｏｐｅｒａｔｉｖｅｕｓｅｒ　ｓｉｄｅ，ｗｈｉｃｈ　ｓｈｏｗｓ　ｔｈａｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｓｃｈｅｍｅ　ｃａｎ　ｃｏｎｓｔｒｕｃｔ　ｔｈｅ　ａｎｏｎｙｍｏｕｓ　ｃｌｏａｋｉｎｇ　ｒｅｇｉｏｎｅｆｆｉｃｉｅｎｔｌｙ．Ｋｅｙｗｏｒｄｓ　 ｌｏｃａｔｉｏｎ－ｂａｓｅｄ　ｓｅｒｖｉｃｅ；ｌｏｃａｔｉｏｎ　ｐｒｉｖａｃｙ　ｐｒｏｔｅｃｔｉｏｎ；ｄｉｓｔｒｉｂｕｔｅｄ　Ｋ－ａｎｏｎｙｍｉｔｙ；ａｎｏｎｙｍｏｕｓｃｌｏａｋｉｎｇ　ｒｅｇｉｏｎ　ｃｏｎｓｔｒｕｃｔｉｏｎ；ｃｏｏｐｅｒａｔｉｏｎ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ｇａｍｅ；ｂｌｏｃｋｃｈａｉｎ１　引　言基 于 位 置 的 服 务 （Ｌｏｃａｔｉｏｎ－Ｂａｓｅｄ　Ｓｅｒｖｉｃｅ，ＬＢＳ）［１－２］是根据用户提供的位置信息，在地理信息系统平台的支持下，为用户提供包括兴趣点查询、广告推送和娱乐游戏在内的增值服务．随着移动通信技术的 不 断 发 展 以 及 智 能 终 端 设 备 的 不 断 普 及，ＬＢＳ已被广泛地应用到电子商务、卫生医疗和移动社交等领域，成为人们日常生活必不可少的重要组成．据一项最新报 告显示①，２０１７ 年美 国 共有 ２．２０亿 ＬＢＳ 用 户，占 其 人 口 总 数 的 ６８．０９％，预 计 到２０１８年 ＬＢＳ用户将增至２．４２亿．然而，随着 ＬＢＳ的广泛应用，ＬＢＳ 中的位置隐私泄露问题受到了用户的广泛关注［３－７］．造成用户位置隐私泄露的主要原因是位置服务提供商（Ｌｏｃａｔｉｏｎ－ｂａｓｅｄ　Ｓｅｒｖｉｃｅ　Ｐｒｏｖｉｄｅｒ，ＬＳＰ）会利用数据挖掘等技５期 刘　海等：基于区块链的分布式 Ｋ 匿名位置隐私保护方案３４９① ｈｔｔｐｓ：／／ｗｗｗ． ｓｔａｔｉｓｔａ． ｃｏｍ／ｓｔａｔｉｓｔｉｃｓ／４３６０７１／ｌｏｃａｔｉｏｎ－ｂａｓｅｄ－ｓｅｒｖｉｃｅ－ｕｓｅｒｓ－ｕｓａ．户提交的位置信息中非法获取用户的个人敏感信息［８－９］，如家庭／工作地址、个人嗜好、生活习惯等．Ｋ 匿名［１０－１１］是 ＬＢＳ位置隐私保护中最常见的一种方法，其基本思想是当发送 ＬＢＳ查询请求时，用户首先至少获取其他 Ｋ－１个协作用户真实位置后构建一个匿名区，然后再将该匿名区替代自己的真实位置提交给 ＬＳＰ，从而有效保护自己的个人位置隐私．与 其 他 位 置 隐 私 保 护 方 法 相 比，如 差 分 隐私［１２－１３］、位置坐标变换［１４－１５］和基于密码学［１６－１７］的方法，Ｋ 匿名方法具有以下优势：（１）不依赖复杂的密码技术；（２）可有效地降低用户的计算开销；（３）可让用户获取准确的查询结果，享受较高的 ＬＢＳ服务质量．但是，在传统的 Ｋ 匿名方法［１８－１９］中，需要一个集中式的节点来当匿名服务器，为请求用户构造匿名区．一旦匿名服务器被攻破，攻击者就能轻而易举地获取请求用户和协作用户的真实位置．并且，集中式匿名服务器的存在，不仅使得用户（包括请求用户和协作用户）与匿名服务器间存在通信瓶颈，而且完全可信的第三方在现实环境中也难以找到．这都导致集中式 Ｋ 匿名方法并不实用．为了解决该问题，学者们又提出无需可信第三方的分布式 Ｋ 匿名位置隐私保护方法［１８－３５］．在该方法中，请求用户可直接与周围协作用户进行协商并获取协作用户的真实位置，自主式地生成匿名区来保护自己的位置隐私．然而，现有的分布式 Ｋ 匿名位置隐私保护方案却存在以下两个问题：（１）收到协作用户提供的真实位置后，自利的请求用户会将这些位置信息泄露给第三方以获取额外收益；或者恶意的攻击者会假扮为请求用户来获取协作用户的真实位置，从而导致协作用户位置隐私的泄露．（２）收到请求用户发送的协作请求后，即使某些协作用户位于敏感区域，但由于自利性，其仍会提供虚假位置给请求用户来提高自己的活跃度（或信誉值），以便自己作为请求者时能高效地构造出匿名区．如果自利的协作用户随机生成一个位于无移动用户区域内的虚假位置给请求用户来构造匿名区，由于 ＬＳＰ可利用背景知识如网络监视技术或区域监视技术识别出无用户区域［３６］，ＬＳＰ就能缩小匿名区．这不仅导致请求用户的位置隐私保护需求难以得到满足，甚至还使得 ＬＳＰ可直接推测出请求用户的隐私信息，如图１所示．假设请求用户 Ａｌｉｃｅ使用分布式 Ｋ 匿 名隐 私 保 护 方 法 保 护 其 位 置 隐 私．当Ａｌｉｃｅ发送匿名区构造协作请求后，协作用户 Ｂｏｂ正在酒吧酗酒．此时，他既不想提供自己的真实位置来泄露自己酗酒的不良嗜好，又想参与匿名区构造以提升自己的活跃度使得自己作为请求者时能获得他人帮助，因此 Ｂｏｂ就随机生成了一个位于河流中心的虚假位置提供给 Ａｌｉｃｅ．Ａｌｉｃｅ在收到协作用户Ｂ提供的位置后，将构造出的匿名区连同自己的查询内容提交给 ＬＳＰ，如图１（ａ）所示．当收到 Ａｌｉｃｅ提交的匿名 区 后，ＬＳＰ 识 别 出 该 匿 名 区 中 的 无 人 区域，发现缩小后的匿名区属于医院区域，如图１（ｂ）所示．此时，ＬＳＰ就能以极大概率推测出 Ａｌｉｃｅ的身体健康状况，从而非法获取请求用户 Ａｌｉｃｅ的个人隐私．图 １　协作用户提供虚假位置给请求用户的示例图综上所述，由于未考虑匿名区构造过程中存在的位置泄露和欺骗行为，现有的分布式 Ｋ 匿名位置隐私保护方案并不能完全保护用户的位置隐私．为了解决上述问题，本文提出了一个基于区块链的分布式 Ｋ 匿名位置隐私保护方案．据作者所知，这是第一个利用区块链来研究 ＬＢＳ位置隐私保护的方案．本文的主要贡献如下：（１）通过记录参与匿名区构造的请求用户、协作用户及其提供的位置信息作为证据，惩罚具有位置泄露和欺骗行为的用户，使其作为请求者时不能构造出匿名区，并设计一个交互记录机制来约束匿名区构造过程中请求用户和协作用户的自利性行为．（２）基于设计的交互记录机制，结合区块链技术，本文提出一个 分 布 式 Ｋ 匿 名 位 置 隐 私 保 护 方案．安全性分析证明该方案在有效防止请求用户泄露协作用户的位置信息的同时，还能激励协作用户提供真实位置来参与匿名区的构造．（３）大量实验表明，当请求用户使用本方案构造匿名区时，其与协作用户所需的计算开销、通信开销和存储开销较少，能高效地构造出匿名区．这说明本方案具有较好的实用性．４４９ 计　　算　　机　　学　　报 ２０１９年关工作２．１　分布式环境下匿名区的构造方法分布式 Ｋ 匿 名 位 置 隐 私 保 护 方 法 最 早 是 由Ｃｈｏｗ 等人［２０］提出的，其基本思想是请求用户利用点对点通信方式获取至少其他 Ｋ－１个协作用户的真实位置构造匿名区，使得 ＬＳＰ仅能以不高于１／Ｋ的概率从匿名区中猜测出请求用户的真实位置．然而，在他们的方案中，请求用户和协作用户需要拥有两个独立的通信网络，分别用于Ｐ２Ｐ通信和 ＬＢＳ查询通信．这极大地降低了该方案的实用性．Ｇｈｉｎｉｔａ等人［２１］利用 Ｈｉｂｅｒｔ曲线将请求用户和协作用户的位置信息从二维空间映射至一维空间，并将每个用户的一维位置信息存储于 Ｂ＋树的数据节点中，使得请求用户可快速获取相邻协作用户的真实位置来构造匿名区．但是，当协作用户较多时，请求用户需从 Ｂ＋树的根节点进行检索，从而增大了请求用户的计算开销．为了解决该问题，文献［２２］又利用环形结构替代 Ｂ＋树结构存储所有用户的一维位置，使得请求用户可快速查找相邻用户构造匿名区．Ｃｈｏｗ等人［２３］指出请求用户在构造匿名区时需结合实际的道路交通网络，否则 ＬＳＰ就可根据道路交通网络从请求用户提交的匿名区中识别出某些协作用户的真实位置，乃至直接识别出请求用户的真实位置．他们为请求用户在每条道路上进行 ＬＢＳ查询设置不同的服务质量，在确保服务质量的前提下，使得生成的匿名区中尽可能多地包含交叉路口，提高请求用户的位置隐私保护等级．Ｓｕｎ等人［２４］将网络中所有用户的真实位置进行分类，提出基于位置标签的分布式 Ｋ 匿名隐私保护方案．在他们的方案中，请求用户构造的匿名区中不仅要至少包括 Ｋ－１个协作用户的真实位置，并且协作用户真实位置的类型也要与请求用户真实位置的类型一致．２．２　分布式环境下协作用户位置的获取方法当请求用户未收到 Ｋ－１个协作用户发送的位置信息时，上述方案均通过提高点对点通信跳数的方法来获取更多协作用户提供的位置信息．这势必增加网络传输延迟，加重网络通信负担．为了解决该问题，Ｃｈｏｗ 等人［２５］提出利用历史协作用户的真实位置为请求用户构造匿名区．在他们的方案中，请求用户在进行每次 ＬＢＳ查询后，均会将采用的协作用户的位置信息进行存储．若下次 ＬＢＳ查询时获得的协作用户数量不满足其位置隐私保护需求，可直接利用历史协作用户提供的位置信 息参与构 造匿名区．为了降低请求用户的存储开销，Ｋｉｍ 等人［２６］采用 Ｈｉｂｅｒｔ曲线对历史协作用户的位置信息进行降维处理，并利用构造出的匿名区的信息熵来度量请求用户的位置隐私保护等级，提出了基于网格的分布式 Ｋ 匿名位置隐私保护方案．Ｐｅｎｇ等人［２７］通过让合法请求用户发送虚假查询的方式混淆自己的真实查询，提出了一个适用于分布式网络的 Ｋ 匿名位置隐私保护方案．在他们的方案中，请求用户通过发送虚假协作请求获取协作用户的真实位置，并将它们存入缓存中．当请求用户需要向 ＬＳＰ发送查询请求时，可利用缓存中存取的位置信息构造匿名区．除采用历史协作用户的位置信息外，Ｚｈｏｎｇ和 Ｈｅｎｇ－ａｒｔｎｅｒ［２８］、Ｔａｋａｂｉ等人［２９］结合现有移动通信基础设施，分别提出了两个基于区域感知的分布式 Ｋ 匿名位置隐私保护方案．他们的基本思想是让请求用户随机构造匿名区，通过向移动通信运营商询问该区域内包含的其他用户数量来确定该匿名区是否满足请求用户的隐私保护需求．然而，这两个方案均不能抵抗来自移动通信运营商和 ＬＳＰ 的合谋攻击．Ｃｈｅ等人［３０］通过让网络中所有用户主动发送自己的真实位置以及自己周围邻居的位置信息表的方法，提出了一个双向主动的分布式 Ｋ 匿名隐私保护方案．Ｈｗａｎｇ和 Ｈｕａｎｇ［３１］、Ｈｗａｎｇ等人［３２］提出请求用户可利用社交网络获取协作用户的真实位置来构造匿名区．２．３　分布式Ｋ匿名中的激励机制Ｙａｎｇ等人［３３］指出原有的 分 布 式 Ｋ 匿 名 隐 私保护方案均假设协作用户是诚实的，他们在收到请求用户发送的匿名区协作构造请求后，会提供自己真实的位置给请求用户．然而，在现实环境中，用户都是自利的．若请求用户直接使用这些方案保护自己 ＬＢＳ查询时的位置隐私，将难以获得满足自己隐私保护需求的协作用户真实位 置数量来构 造匿名区．他们利用单轮密封式双重拍卖机制允许多个请求用户通过拍卖的方式获取协作用户的真实位置，从而激励网络中的所有用户都 参与到匿名 区的构造．Ｚｈａｎｇ等人［３４］指出当请求用户的真实位置过于敏感时，若采用方案［３３］的方法，其将难以拍卖到满足隐私保护需求的协作用户位 置 数量来构造匿名区．为了解决该问题，他们利用贪心算法设计了一个中标判定规则，使得所有请求用户均能获得满足其隐私保护需求的位置数量来构造匿名区．Ｌｉ等人［３５］指出上述两个方案均需要存在可信的拍卖者，否则５期 刘　海等：基于区块链的分布式 Ｋ 匿名位置隐私保护方案５４９稿日期：２０１８－０４－２４；在线出版日期：２０１８－１２－２９．本课题得到国家自然科学基金（Ｕ１７０８２６２，Ｕ１７３６２０３，Ｕ１４０５２５５）、国家“九七三”重点研究发展 计 划 项 目 （２０１７ＹＦＢ０８０１８０５）、贵 州 财 经 大 学 引 进 人 才 科 研 启 动 项 目 （２０１８ＹＪ１６）、贵 州 财 经 大 学 校 级 科 研 基 金 项 目（２０１８ＸＹＢ０１）资助．刘　海，博士，主要研究领域为位置隐私保护和安全协议设计．Ｅ－ｍａｉｌ：ｌｉｕｈａｉ４７５７＠１６３．ｃｏｍ．李兴华（通信作者），博士，教授，主要研究领域为网络与信息安全、隐私保护和密码学．Ｅ－ｍａｉｌ：ｘｈｌｉ１＠ｍａｉｌ．ｘｉｄｉａｎ．ｅｄｕ．ｃｎ．雒　彬，博士研究生，主要研究领域为位置隐私保护和信任评估．王运帷，博士研究生，主要研究领域为区块链和隐私保护．任彦冰，硕士研究生，主要研究方向为区块链和位置隐私保护．马建峰，博士，长江学者特聘教授，主要研究领域为网络与信息安全、编码理论、密码学．丁红发，博士研究生，讲师，主要研究领域为数据隐私保护．基于区块链的分布式Ｋ匿名位置隐私保护方案刘　海１），２），３），４）　李兴华２），３），４）　雒　彬２），３），４）　王运帷２），３），４）任彦冰２），３），４）　马建峰２），３），４）　丁红发１）１）（贵州财经大学信息学院　贵阳　５５００２５）２）（西安电子科技大学网络与信息安全学院　西安　７１００７１）３）（西安电子科技大学综合业务网理论及关键技术国家重点实验室　西安　７１００７１）４）（西安电子科技大学陕西省网络与系统安全重点实验室　西安　７１００７１）摘　要　由于无需可信第三方和复杂的密码技术就可为请求用户提供准确的查询结果，分布式 Ｋ 匿名已被广泛地用于保护基于位置服务中用户的位置隐私．然而，现有分布式 Ｋ 匿名位置隐私保护方案均未考虑匿名区构造过程中存在的位置泄露和位置欺骗行为，这使得自利的请求用户会泄露协作用户的真实位置；而自利的协作用户也会提供虚假的位置导致服务提供商能识别出请求用户的真实位置．因此，现有分布式 Ｋ 匿名方案并不能有效保护用户的位置隐私．为了解决上述问题，本文将匿名区的构造视为请求用户与协作用户间的两方博弈，利用区块链记录博弈双方以及协作用户提供的真实位置作为证据，通过惩罚具有位置泄露和欺骗行为的用户，使其作为请求者时不能成功构造出匿名区来约束他们的自利性．基于上文，本文提出一个基于区块链的分布式 Ｋ 匿名位置隐私保护方案．安全性分析和大量实验表明，本文所提方案不仅能激励协作用户提供真实位置参与匿名区构造，而且能防止请求用户泄露协作用户的真实位置，还可高效地生成匿名区，从而有效保护用户的位置隐私．关键词　基于位置的服务；位置隐私保护；分布式 Ｋ 匿名；匿名区构造；协同构造博弈；区块链中图法分类号ＴＰ３９１　　　ＤＯＩ号１０．１１８９７／ＳＰ．Ｊ．１０１６．２０１９．００９４２Ｄｉｓｔｒｉｂｕｔｅｄ　Ｋ－Ａｎｏｎｙｍｉｔｙ　Ｌｏｃａｔｉｏｎ　Ｐｒｉｖａｃｙ　Ｐｒｏｔｅｃｔｉｏｎ　ＳｃｈｅｍｅＢａｓｅｄ　ｏｎ　ＢｌｏｃｋｃｈａｉｎＬＩＵ　Ｈａｉ　１），２），３），４）　ＬＩ　Ｘｉｎｇ－Ｈｕａ２），３），４）　ＬＵＯ　Ｂｉｎ２），３），４）　ＷＡＮＧ　Ｙｕｎ－Ｗｅｉ　２），３），４）ＲＥＮ　Ｙａｎ－Ｂｉｎｇ２），３），４）　ＭＡ　Ｊｉａｎ－Ｆｅｎｇ２），３），４）　ＤＩＮＧ　Ｈｏｎｇ－Ｆａ１）１）（Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ，Ｇｕｉｚｈｏｕ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｆｉｎａｎｃｅ　ａｎｄ　Ｅｃｏｎｏｍｉｃｓ，Ｇｕｉｙａｎｇ　５５００２５）２）（Ｓｃｈｏｏｌ　ｏｆ　Ｃｙｂｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｘｉｄｉａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉ′ａｎ　７１００７１）３）（Ｓｔａｔｅ　Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ｉｎｔｅｇｒａｔｅｄ　Ｓｅｒｖｉｃｅｓ　Ｎｅｔｗｏｒｋｓ，Ｘｉｄｉａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉ′ａｎ　７１００７１）４）（Ｓｈａａｎｘｉ　Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ｎｅｔｗｏｒｋ　ａｎｄ　Ｓｙｓｔｅｍ　Ｓｅｃｕｒｉｔｙ，Ｘｉｄｉａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉ′ａｎ　７１００７１）Ａｂｓｔｒａｃｔ　 Ｗｉｔｈ　ｔｈｅ　ｄｅｖｅｌｏｐｍｅｎｔ　ｏｆ　ｗｉｒｅｌｅｓｓ　ｃｏｍｍｕｎｉｃａｔｉｏｎ　ａｎｄ　ｐｏｓｉｔｉｏｎｉｎｇ　ｔｅｃｈｎｏｌｏｇｉｅｓ，ｌｏｃａｔｉｏｎ－ｂａｓｅｄ　ｓｅｒｖｉｃｅ（ＬＢＳ）ｈａｓ　ｂｅｃｏｍｅ　ａ　ｐａｒｔ　ｏｆ　ｏｕｒ　ｄａｉｌｙ　ｌｉｆｅ．Ｈｏｗｅｖｅｒ，ｓｉｎｃｅ　ＬＢＳ　ａｌｗａｙｓ　ｒｅｑｕｉｒｅｓ　ｔｈｅｕｓｅｒｓ　ｔｏ　ｓｕｂｍｉｔ　ｔｈｅｉｒ　ｌｏｃａｔｉｏｎｓ，ａｎ　ｕｎｐｒｅｃｅｄｅｎｔｅｄ　ｔｈｒｅａｔ　ａｂｏｕｔ　ｌｏｃａｔｉｏｎ　ｐｒｉｖａｃｙ　ｏｆ　ｍｏｂｉｌｅ　ｕｓｅｒｓｃｏｍｅｓ　ｗｉｔｈ　ｔｈｅ　ｃｏｎｖｅｎｉｅｎｃｅ　ｏｆ　ｗｉｄｅｌｙ　ｕｓｅｄ　ｔｅｃｈｎｉｑｕｅ．Ｔｈｅｒｅｆｏｒｅ，ＬＢＳ　ｌｏｃａｔｉｏｎ　ｐｒｉｖａｃｙ　ｐｒｏｔｅｃｔｉｏｎｈａｓ　ａｔｔｒａｃｔｅｄ　ｓｕｂｓｔａｎｔｉａｌ　ａｔｔｅｎｔｉｏｎ．Ａｍｏｎｇ　ｔｈｅ　ｅｘｉｓｔｉｎｇ　ＬＢＳ　ｌｏｃａｔｉｏｎ　ｐｒｉｖａｃｙ　ｐｒｏｔｅｃｔｉｏｎ　ｍｅｔｈｏｄｓ，ｔｈｅ　ｄｉｓｔｒｉｂｕｔｅｄ　Ｋ－ａｎｏｎｙｍｉｔｙ　ｔｅｃｈｎｉｑｕｅ　ｉｓ　ｏｎｅ　ｏｆ　ｔｈｅ　ｍｏｓｔ　ｃｏｍｍｏｎ　ａｎｄ　ｐｏｐｕｌａｒ　ｍｅｔｈｏｄｓ．Ｉｎ　ｔｈｉｓ 请 求 用 户 与 协 作 用 户 的 位 置 信 息 泄 露 给ＬＳＰ．他们将信誉引入到匿名区构造中，提出了基于信誉激励的分布式 Ｋ 匿名区隐私保护方案．在他们的方案中，协作用户只会帮助信誉值高的请求用户构造匿名区，而每个用户的信誉值则靠帮助其它用户构造匿名区来提升．此外，Ｇｏｎｇ等人［３６－３７］指出为了更好地保护请求用户的位置隐私，请求用户与协作用户在参与匿名区构造时需要更换使用的假名．因此，为了激励协作用户更换假名，他们将参与匿名区构造的请求用户和协作视为一类特殊的社会群体，基于群体用户间的社会关系，通过最大化群体收益，激励协作用户在参与匿名区构造时更换自己的假名．综上所述，现有的分布式 Ｋ 匿名位置隐私保护方案均未考虑匿名区构造过程中存在的隐私泄露和欺骗行为．这不仅使得自利的请求用户在收到协作用户的真实位置后可将这些位置信息泄露给第三方，还会使得自利的协作用户提供虚假位置给请求用户，使得最终生成的匿名区不能满足请求用户的位置隐私保护需求，甚至使得 ＬＳＰ可直接获知请求用户的位置隐私．因此，现有的分布式 Ｋ 匿名位置隐私保护方案不能完全保护用户的位置隐私．３　预备知识３．１　系统结构如图２ 所示，本文采用点对点对等式结构［３７］，由请求用户、协作用户和 ＬＳＰ组成，无需第三方．假设请求用户与协作用户以及请求用户与 ＬＳＰ 间存在安全的通信链路．当请求用户 Ｐ０向 ＬＳＰ 发送查询请求时，他首先向周围用户发送协作请求以获取他们的真实位置．当收到协作用户 Ｐ１，Ｐ２，…，ＰＫ－１提供的位置 Ｌｏｃｒｅａｌ１，Ｌｏｃｒｅａｌ２，…，ＬｏｃｒｅａｌＫ－１后，请求用户Ｐ０构造匿名区 ＡＣＲ，并连同查询内容一同提交给ＬＳＰ．图 ２　系统结构当 ＬＳＰ认证通过请求用 户 Ｐ０的身 份 后，他根据请求用户提交的匿名区和查询内容在数据库中进行检索，将 所 有 结 果 返 回 给 请 求 用 户 Ｐ０．在 收 到ＬＳＰ发送的查询结果后，请求用户Ｐ０根据自己的真实位置Ｌｏｃｒｅａｌ０对它们进行筛选，从而获得准确的查询结果．其中，Ｌｏｃｒｅａｌｉ表示第ｉ（１ｉＫ－１）个协作用户 Ｐｉ的 真 实 位 置；匿 名 区 ＡＣＲ＝Ａｒｅａ（Ｌｏｃｒｅａｌ０，Ｌｏｃｒｅａｌ１，…，ＬｏｃｒｅａｌＫ－１）；Ａｒｅａ（·）是匿名区构造函数；Ｋ表示请求用户Ｐ０的隐私保护需求．此外，本文还假设请求用户与协作用户均是理性的，即在匿名区构造过程中，他们总是根据自身利益最大化进行策略选择．对于理性的请求用户 Ｐ０来说，他首先期望获得协作用户提供的真实位置用于生成匿名区 ＡＣＲ；其次，在成功构造匿名区的同时，他会泄露协作用户的真实位置 以获得更多 额外收益．因此，在匿名区构造过程中，理性请求用户 Ｐ０的偏好满足：珦Ｕ＋＞珦Ｕ＞珦Ｕ－＞珦Ｕ－－．其中：·珦Ｕ＋表示请求用户 Ｐ０成功构造匿名区，且泄露协作用户 Ｐｉ真实位置时的收益；·珦Ｕ 表示请求用户Ｐ０成功构造匿名区，但未泄露协作用户 Ｐｉ真实位置时的收益；·珦Ｕ－表示请求用户 Ｐ０未成功构造匿名区，但泄露协作用户 Ｐｉ真实位置时的收益；·珦Ｕ－－表示请求用户 Ｐ０未成功构造匿名区，且未泄露协作用户 Ｐｉ真实位置时的收益．而对于理性的协作用户 Ｐｉ来说，他首先期望能保护自己的位置隐私；其次，在有效保护自己位置隐私的同时，向请求用户提供协作帮助．因此，在匿名区构造过程中，理性协作用户 Ｐｉ的偏好满足：珮Ｗ＋＞珮Ｗ＞珮Ｗ－＞珮Ｗｆ＞珮Ｗ－－．其中：·珮Ｗ＋表示协作用户 Ｐｉ提供虚假位置Ｌｏｃｆａｋｅｉ给请求用户Ｐ０，且请求用户 Ｐ０采用该虚假位置构造匿名区时的收益；·珮Ｗ 表 示 协 作 用 户 Ｐｉ提 供 自 己 的 真 实 位 置Ｌｏｃｒｅａｌｉ给请求用户Ｐ０，且请求用户 Ｐ０未泄露该位置时的收益；·珮Ｗ－表示协作用户 Ｐｉ未提供位置信息来协作请求用户Ｐ０构造匿名区时的收益；·珮Ｗｆ表示协作用户Ｐｉ提供虚假位置Ｌｏｃｆａｋｅｉ给请求用户Ｐ０，但被请求用户正确识别，未采用该位置构造匿名区时的收益；·珮Ｗ－－表 示 协 作 用 户 Ｐｉ提 供 自 己 真 实 位 置Ｌｏｃｒｅａｌｉ给请求用户Ｐ０，但请求用户Ｐ０泄露自己真实６４９ 计　　算　　机　　学　　报 ２０１９年的收益．３．２　分布式Ｋ匿名位置隐私保护的安全性本文分别将请求用户和周围协作用户视为攻击者．在分布式匿名区的构造过程中，自利的请求用户在收到协作用户提供的位置信息后，会泄露这些信息给第三方以获取额外的收益．而自利的协作用户在收到请求用户发送的匿名区构造协作请求后，其可能会提供虚假的位置信息给请求用户，使得请求用户构造出的匿名区不能满足其隐私保护需求，甚至使得 ＬＳＰ可直接推测出请求用户的个人隐私，如图１所示．为了清晰地给出分布式匿名区构造的安全性定义，本文将匿名区的协同构造视为请求用户 Ｐ０和协作用户 Ｐｉ间的两方博弈，首先形式化描述匿名区协同构造博弈．定义１（匿名区协同构造博弈）．匿名区协同构造博弈是一个五元组ＧＡＣＲ＝｛Ｐ，Ａ，Ｈ，Ｆ，Ｕ｝，其中：·Ｐ＝｛Ｐ０，Ｐｉ｝是理性用户集合；Ｐ０表示请求用户；Ｐｉ表示协作用户．·Ａ＝｛Ａ０，Ａｉ｝是参与者的策略集合．其中，Ａ０＝｛ａ（１）０，ａ（２）０｝是请求用户Ｐ０的策略集合：ａ（１）０表示请求用户 Ｐ０在收到协作用户 Ｐｉ提供的位置Ｌｏｃｉ后不将其泄露给第三方；ａ（２）０表示请求用户 Ｐ０在收到协作用户 Ｐｉ提供的位置Ｌｏｃｉ后将其泄露给第三方．Ａｉ＝｛ａ（１）ｉ，ａ（２）ｉ，ａ（３）ｉ｝表示协作用户 Ｐｉ的策略集合：ａ（１）ｉ表示协作用户Ｐｉ在收到协作请求后，提供自己的真实位置Ｌｏｃｒｅａｌｉ给请求用户Ｐ０；ａ（２）ｉ表示协作用户Ｐｉ在收到协作请求后，不提供位置信息给请求用户 Ｐ０；ａ（３）ｉ表示协作用户Ｐｉ在收到协作请求后，提供虚假的位置 Ｌｏｃｆａｋｅｉ给请求用户Ｐ０．并且，在匿名区协同构造博弈ＧＡＣＲ中，请求用户和协作用户各选一个策略形成的向量ａ＝（ａ０，ａｉ）称为理性用户的策略组合．其中，ａ０∈Ａ０；ａｉ∈Ａｉ．·Ｈ 是历史集合．任意一个历史ｈ∈Ｈ 表示其对应时刻理性用户选择的策略构成的策略组合．显然，空 字 符τ∈Ｈ，其 表 示 匿 名 区 协 同 构 造 博 弈 开始．对于任意的历史ｈ∈Ｈ，在其之后可能出现的所有策略组合记为 Ａ（ｈ）＝｛ａ｜（ｈ，ａ）∈Ｈ｝．如果存在ｈ′∈Ｈ 使得Ａ（ｈ′）＝，则称该历史ｈ′是终止的．集合Ｚ 表示所有终止历史组成的集合．·Ｆ：（Ｈ／Ｚ）→Ｐ 是用户分配函数，它为没有终止的历史ｈ∈Ｈ＼Ｚ 指定下一步进行策略选择的用户．由于在匿名区协同构造博弈中，理性协作用户Ｐｉ率先进行策略选择，故Ｆ（τ）＝Ｐｉ．·Ｕ＝｛ｕ０，ｕｉ｝是理性用户的收益集合．其中，ｕ０∈｛珦Ｕ＋，珦Ｕ，珦Ｕ－，珦Ｕ－－｝是理性请求用户 Ｐ０的收益函数；ｕｉ∈｛珮Ｗ＋，珮Ｗ，珮Ｗ－，珮Ｗｆ，珮Ｗ－－｝是理性协作用户Ｐｉ的收益函数．基于形式化描述的匿名区协同构造博弈模型，下面给出分布式 Ｋ 匿名的安全性定义．定义２（分布式Ｋ 匿名位置隐私保护的安全性）．假设 Ｐ０是理性请求用户，Ｐ１，Ｐ２，…，ＰＫ－１是 Ｋ－１个理性协作用户．当理性请求用户 Ｐ０采用分布式 Ｋ匿名隐私保护方案向Ｐ１，Ｐ２，…，ＰＫ－１发送协作构造匿名区请求，且成功构造出匿名区 ＡＣＲ 时，下述条件成立：ｕ０ ＝珦Ｕ （１）ｕｉ ＝珮Ｗ （２）ＰｒＬＳＰ［Ｌｏｃｒｅａｌ０｜ＡＣＲ］１／Ｋ （３烅烄烆）那么，该分布式 Ｋ 匿名位置隐私保护方案就称为是安全的．其中，Ｋ 表示请求用户Ｐ０在发送当前 ＬＢＳ查询时的 位 置 隐 私 保 护 需 求；１ｉＫ －１；ＰｒＬＳＰ［Ｌｏｃｒｅａｌ０｜ＡＣＲ］表示 ＬＳＰ从请求用户Ｐ０提交的匿名区 ＡＣＲ 中正确识别出其真实位置Ｌｏｃｒｅａｌ０的概率．在上述定义中，式（１）和式（２）是从匿名区构造的角度对分布式 Ｋ 匿名位置隐私保护的安全性进行定义．其中，式（１）表示在匿名区构造过程中请求用户Ｐ０不会泄露协作用户的位置；式（２）表示在匿名区构造 过 程 中 协 作 用 户 Ｐｉ提 供 自 己 的 真 实 位 置Ｌｏｃｒｅａｌｉ给请求用户Ｐ０．而式（３）是从 ＬＢＳ查询的角度对分布式 Ｋ 匿名位置隐私保护的安全性进行定义．３．３　区块链区块链①的基本思想是通过整合密码技术和点对点通信技术，基于数据分布式存储一致性的原理，利用智能合约来自动化执行预设脚本代码，在实现去中心化共享数据的同时，确保共享数据的不可篡改性和不可伪造性．区块链的基础架构［３９］可分为六层，自顶向下分别是：应用层、合约层、激励层、共识层、网络层和数据层，如图３所示．（１）应用层应用层封装了区块链在社会活动中可应用的场景及实例．５期 刘　海等：基于区块链的分布式 Ｋ 匿名位置隐私保护方案７４９① Ｎａｋａｍｏｔｏ　Ｓ． Ｂｉｔｃｏｉｎ： Ａ　ｐｅｅｒ－ｔｏ－ｐｅｅｒ　ｅｌｅｃｔｒｏｎｉｃ　ｃａｓｈｓｙｓｔｅｍ［ＥＢ／ＯＬ］．ｈｔｔｐｓ：／／ｂｉｔｃｏｉｎ．ｏｒｇ／［２０１８－０７－２８］．图 ３　区块链基础架构（２）合约层合约层封装了各类脚本代码以及算法机制等，为用户提供可编程环境，从而实现智能合约．利用智能合约，区块链就可将各自业务规则转化成区块链系统中自动执行的合约，使得该合约的执行不依赖任何第三方．理论上智能合约一旦部署且符合其执行的条件，即可自动执行．（３）激励层在区块链中，数据是由所有节点共同维护的．为了激励节点积极参与到区块链的维护中，激励层封装了激励相容的分配规则和支付规则，在各节点参与维护区块链的同时，使其自身收益最大化．（４）共识层在区块链中，由于需要在无中心节点的情况下保证各个节点记账的一致性，此时需利用共识层中封装的各种共识机制在相互没有信任基础的个体间达成共识．（５）网络层网络层封装了区块链系统的组网规则———对等式组网，以及在该网络中节点间的交易账单和其他数据的传播、验证协议等．（６）数据层数据层利用 Ｈａｓｈ算法、Ｍｅｒｋｌｅ树等密码技术和时间戳技术将数据区块生成时间间隔内形成的所有交易账单以链式结构进行存储，确保区块链中存储的数据具有不可伪造、不可篡改和可追溯性．４　基于区块链的分布式Ｋ匿名位置隐私保护方案　　为了防止在分布式匿名区构造过程中请求用户泄露协作用户的位置以及协作用户提供虚假位置欺骗请求用户等情况的发生，本文首先利用加密和签名技术来防止其余用户非法获取协作用户提供的位置信息以及参与匿名区构造用户具有位置欺骗或泄露行为后的抵赖，并利用区块链分布式存储参与匿名区构造的博弈双方以及提供的 位置信息 作为证据，设计了一个分布式 Ｋ 匿名位置隐私保护方案．４．１　共识机制为了防止在分布式匿名区构造过程中请求用户泄露协作用户的位置以及协作用户提供虚假位置欺骗请求用户，本节首先设计了一个协作请求记录机制约束请求用户和协作用户的自利性行为；并且还提出了一个区块链记账权竞争机制，激励网络中所有用户参与区块链的维护中．假设在任意第ｑ次匿名区协同构造博弈中，策略ａｑ＿（１）０表示请求用户 Ｐ０在收到协作用户 Ｐｉ提供的位置Ｌｏｃｑｉ后并不将其泄露给第三方；策略ａｑ＿（２）０表示请求用户 Ｐ０在收到协作用户 Ｐｉ提供的位置Ｌｏｃｑｉ后将其泄露给第三方．策略ａｑ＿（１）ｉ表示协作用户Ｐｉ在收到协作请求后，提供自己的真实位置 Ｌｏｃｒｅａｌｉ给请求用户Ｐ０；策略ａｑ＿（２）ｉ表示协作用户Ｐｉ在收到协作请求后，不提 供 任 何 位 置 信 息 给 请 求 用 户 Ｐ０；策 略ａｑ＿（３）ｉ表示协作用户Ｐｉ在收到协作请求后，提供虚假的位置Ｌｏｃｆａｋｅｉ给请求用户Ｐ０．令ｕｑ０和ｕｑｉ分别表示第ｑ次匿名区协同构造博弈结束时请求用户 Ｐ０和协作用户 Ｐｉ的收益．并且，令策略ａｑ＋ｊ０→０表示第ｑ次匿名区协同构造博弈的请求用户Ｐ０在之后的第ｊ次博弈中仍作为请求者时选择的策略；策略ａｑ＋ｊｉ→０表示参与第ｑ次匿名区协同构造博弈的协作用户Ｐｉ在第ｊ次博弈中作为请求者时选择的策略．那么，本文提出的协作请求记录机制如下所示．定义３（共识机制Ｉ———交互记录机制）．交互记录机制 ＭＲ＝（ａｑ，ｐ［ｑ～＋ｍ］）是一个二元组．其中，·ａｑ＝（ａｑ０，ａｑｉ）是在第ｑ次匿名区协同构造博弈中，请求用户 Ｐ０和协作用户 Ｐｉ选择的策略ａｑ０和ａｑｉ形成的策略组合．·ｐ［ｑ～＋ｍ］＝｛ｐ［ｑ～＋ｍ］０，ｐ［ｑ～＋ｍ］ｉ｝是交互记录机制 ＭＲ根据请求用户Ｐ０和协作用户 Ｐｉ在第ｑ次匿名区协同构造博弈中选择的策略，给予他们在之后的第ｑ～次匿名区协同构造博弈Ｇｑ～ＡＣＲ至第ｑ～＋ｍ 次匿名区协同构造博弈Ｇｑ～＋ｍＡＣＲ的支付收益．对于任意ｊ∈［ｑ～，ｑ～＋ｍ］，它满足：ｐｊ０＝ｕｊ０（ａｊ０→０，ａｊ＿（１）ｉ′）， ａｑ０＝ａｑ＿（１）０ｕｊ０（ａｊ０→０，ａｊ＿（２）ｉ′）， ａｑ０＝ａｑ＿（烅２）烄烆０（４）８４９ 计　　算　　机　　学　　报 ２０１９年ｐｊｉ＝ｕｊｉ→０（ａｊｉ→０，ａｊ＿（１）ｉ′）， ａｑｉ＝ａｑ＿（１）ｉｕｊｉ→０（ａｊｉ→０，ａｊｉ′（λｉ→０，δｉ′）），ａｑｉ＝ａｑ＿（２）ｉｕｊｉ→０（ａｊｉ→０，ａｊ＿（２）ｉ′）， ａｑｉ＝ａｑ＿（３）烅烄烆 ｉ（５）其中：ｍ 表示惩罚轮数；ａｊｉ′表示在匿名区协同构造博弈ＧｊＡＣＲ中协作用户 Ｐｉ′选择的策略；λｉ→０表示参与匿名区协同构造博弈 ＧｑＡＣＲ的协作用户 Ｐｉ在参与博弈ＧｊＡＣＲ时协助其他用户构造匿名区的次数；δｉ′是匿名区协同构造博弈ＧｊＡＣＲ中协作用户 Ｐｉ′的判断阈值．当λｉ→０＜δｉ′时，ａｊｉ′（λｉ→０，δｉ′）＝ａｊ＿（２）ｉ′；否则，ａｊｉ′（λｉ→０，δｉ′）＝ａｊ＿（１）ｉ′．交互记录机制 ＭＲ就是通过记录参与匿名区构造的请求用户、协作用户及其提供的位置信息来约束他们的自利性行为．也就是说，一旦发现匿名区协同构造博弈ＧｑＡＣＲ中请求用户 Ｐ０泄露了协作用户的位置信息，那么其之后的 ｍ 次服务查询中均不会有用户帮助其构造匿名区；同样地，如果发现匿名区协同构造博弈ＧｑＡＣＲ中的协作用户 Ｐｉ提供虚假位置，那么该协作用户在之后的 ｍ 次服务查询中也不会有其他用户帮助其构造匿名区．在本文提出的方案中，将利用区块链分布式存储参与匿名区构造的博弈双方以及协作用户提供的位置信息作为证据．因此，为了激励网络中所有用户参与到区块链的维护中，本文还提出了一个区块链记账权竞争机制．定义４（共识机制ＩＩ———记账权竞争机制）．　记账权竞争机制 ＭＣ＝（珘λ，ｐ～）是一个二元组．其中：·珘λ＝ （λ１～，λ２～，…，λ珘ｎ）是 在 竞 争 生 成 新 区 块ｂｌｏｃｋＭ时，参与竞争获取记账权的用户 Ｐ１～，Ｐ２～，…，Ｐ珘ｎ历史上帮助其他用户构造匿名区的次数λ１～，λ２～，…，λ珘ｎ所形成的历史协同构造次数集合．λ珓ｉ是参与新区块生成记账权的第珓ｉ 个用户Ｐ珓ｉ历史帮助其他用户构造匿名区的次数．·珟ｐ＝｛珟ｐ１～，珟ｐ２～，…，珟ｐ珘ｎ｝是记账权竞争机制 ＭＣ根据参与新区块生成记账权竞争的用户Ｐ１～，Ｐ２～，…，Ｐ珘ｎ历史上帮助其他用户构造匿名区构造的次数，给予他们在生成新区块时的收益．对于任意珟ｐ珓ｉ∈珟ｐ，其满足：珟ｐ珓ｉ ＝０， 其他λ珓ｉ＋１，λ珓ｉ＝ａｒｇ　ｍａｘ｛λ珓ｉ′ ｍｏｄλＭ－１ｍａｘ烅烄烆｝（６）其中，λＭ －１ｍａｘ表示获得生成区块ｂｌｏｃｋＭ －１记账权的用户在当时曾帮助其他用户构造匿名区的历史次数；珓ｉ′∈［１～，２～，…，珘ｎ］．简单来说，本文提出的生成新区块记账权竞争机制 ＭＣ的基本思想是让参与匿名区构造次数最多的用户获取记账权．但是，为了防止参与匿名区构造次数最多的用户始终获取记账权限，从而有机会伪造分布式匿名区协作构造区块链情况的发生，本文利用λ珓ｉ＝ａｒｇ　ｍａｘ｛λ珓ｉ′ ｍｏｄλＭ －１ｍａｘ｝使得区块链的记账权分散给网络中的各个用户．此外，为了激励网络中所有用户来参与区块链的更新，本文将获得生成新区块的记账权视为参与匿名区构造的一种特殊方式．显然，对于网络中任意用户 Ｐ珓ｉ来说，其帮助其他用户构造匿名区的历史次数λ珓ｉ越大，那么 Ｐ珓ｉ作为请求者发送匿名区协同构造请求时就会有越多的用户提供自己的位置信息给他，使其能成功构造出匿名区的概率就越大．这也能在一定程度上预防用户在区块链系统中频繁地使用新ｃＩＤ．值得注意的是，在本文提出的记账权竞争机制中，网络中的任何用户，即包括发送匿名区协同构造请求的请求用户、提供位置信息的协同用户以及收到匿名区协同构造请求未提供位置信息的其他用户均能参与到生成新区块记账权的竞争中．４．２　本文方案本文将请求用户获取协作用户真实位置的过程视为一类特殊的交易（Ｔｒａｎｓａｃｔｉｏｎ），在交易账单中记录交易双方的ＩＤ 以及协作用户提供的位置信息，并将此账单存储至公有链中．当请求用户指认协作用户提供虚假位置或者协作用户指认请求用户泄露自己位置时，可将该交易账单作为凭证用于仲裁．一旦证实出现位置泄露或欺骗行为，那么具有上述行为的用户在作为请求者时将不会有其他用户给其提供帮助，使其不能成功地构造匿名区．此外，为了激励网络中用户参与到区块链的维护中，每次生成区块的用户均会被视为帮助请求用户构造匿名区．具体方案如下所示．Ｓｔｅｐ１．　请求用户 Ｐ０向协作用户发送匿名区构造协作请求Ｒｅｑ ＝｛Ｔ０－ｉ，ｃＩＤ０，λ０，Ｎ（Ｔｒａｎｌ１），Ｎ（Ｔｒａｎｌ２），…，Ｎ（Ｔｒａｎｌλ０），ｓｉｇｎＳＫ－ｃＩＤ０（λ０‖Ｔ０－ｉ）｝ （７）其中，Ｔ０－ｉ表示请求用户Ｐ０发送匿名区构造协作请求时的时间戳；ｃＩＤ０是请求用户 Ｐ０在区块链系统中使用的假名；λ０表示请求用户作为协作者时曾参与匿名区构造的次数；Ｎ（Ｔｒａｎｌｋ）表示存储请求用户Ｐ０协作其他用户构造匿名区的交易账单Ｔｒａｎｌｋ的交易账单号；１ｋλ０；ＳＫ－ｃＩＤ０是请求用户 Ｐ０在区块链系统中的私钥；ｓｉｇｎＳＫ－ｃＩＤ０（λ０‖Ｔ０－ｉ）表示利用５期 刘　海等：基于区块链的分布式 Ｋ 匿名位置隐私保护方案９４９