基于区块链的零知识位置证明系统设计

基于区块链的零知识位置证明系统设计

吴炜, 刘儿兀, 杨昌鑫, 王睿

同济大学电子与信息工程学院，上海 201804

摘要：智能终端设备及定位技术的发展催生了许多基于位置的服务，如定点打卡服务（访问特定地点获取相应的奖励），这导致非法用户为了获取利益对位置服务器进行位置欺骗。因此，需要对用户提供的位置证书进行验证。但现有的位置证明系统在验证用户位置证书的同时对用户隐私保护并不周全，且用户对位置证书的控制并不灵活。基于区块链技术，提出一种分布式位置证明系统架构；进而在此架构基础上，引入零知识证明，提出一种零知识位置证明协议。架构与协议组成的零知识位置证明系统允许用户根据需求，自由选择披露的证书内容及位置精度，实现分级的位置隐私保护。

关键词: 区块链 ; 零知识证明 ; 隐私保护 ; 位置证明系统

中图分类号：TP393

文献标识码：A

doi:10.11959/j.issn.2096−109x.20200020

1 引言

随着智能终端设备和高精度定位技术的发展，越来越多的位置服务（LBS，location-based service）使人们生活更加便利。例如，基于位置的定点签到服务，用户需到达指定地点签到获取相应的奖励；基于位置的个性推荐服务，用户需向位置服务提供商（LBSP，location-based service provider）提供位置信息，LBSP则根据该信息，为用户提供兴趣点推荐；基于位置的社交网络：用户可通过智能手机、平板、智能穿戴设备等对当前所在的兴趣点签到，并将签到信息和用户体验与好友分享。为了防止恶意用户滥用LBSP维护的服务资源，LBSP要求请求位置服务的用户提供相关的位置证明（PL，proof of location），证明其位置证书（LC，location certificate）的合法性。但是，用户的某些不必要披露的隐私信息会随PL暴露给LBSP，因此，在实现用户LC可验证的同时保护位置隐私是必要的。

国内外有许多学者对位置证明系统进行研究，并取得了丰富的成果。现有位置证明系统大致可分为两种：中心式系统与分布式系统。在中心式位置证明系统中，用户 LC 存储在单一的中央服务器或服务器群上，而在分布式位置证明系统中，用户LC存储在分布式网络上。Tyagi等基于类混合空间模型，结合其他多种方法，提出一种位置证明系统，保护用户隐私。Javali 等基于信道状态信息（CSI，channel state information）以及密码基元fuzzy vault，提出一种包含证书生成与证书签发两部分的位置证明系统，该系统允许用户以高概率证明其LC的有效性。Li等基于Wi-Fi或蜂窝网接入点（AP，access point），提出一种基于基础设施的位置证明系统，该系统允许数据库在不知道用户精确位置的情况下验证LC的有效性。上述位置证明系统均为中心式，存在以下几点缺陷：第一，中心式位置证明系统需要专用的大功率中央服务器用于服务大量用户，造成负载不均衡，一旦中央服务器过载，整个系统就会瘫痪；第二，中央服务器成为安全的焦点，恶意攻击者更容易攻陷系统；第三，用户 LC 完全由中央服务器管理，用户失去对其数据控制权，用户隐私安全建立在中央服务器诚实的基础上。为了解决这些问题，一系列分布式位置证明系统被提出，如Zhu等提出的APPLAUS、Wang等提出的 STAMP 以及 Nosouhi 等 提出的SPARSE。另外，Amoretti等提出了基于区块链的位置证明系统，在这些系统中，用户以短程通信方式请求邻近的证人节点为其签发LC。

尽管这些解决方案克服了中心式系统的弊端且不需要Wi-Fi、AP等基础设施，但它们或存在证人节点作恶不可控造成系统的合谋攻击问题；或存在假名而非匿名造成的用户隐私推导攻击问题。因此，本文结合区块链技术，提出一种分布式的位置证明系统架构，该架构由3种节点组成：用户节点、LBSP节点以及证书签发节点（CIN， certificate issuing node），证书签发节点可以是Wi-Fi、AP、微基站等。特别注意的是，证书签发节点依据地理位置进行二进制编码，其目的是实现不同精度的位置证明。然后，在该系统架构的基础上，提出一种零知识位置证明协议。完整位置证明系统允许用户自主选择披露的LC参数，提供任意精度的位置证明，实现用户可控的分级隐私保护，适应不同的应用场景。此外，本文针对可能的恶意攻击，对系统的安全性进行理论分析，得知系统可抵御这些恶意攻击。最后，对不同位置精度等级的位置证明系统进行实验研究，得出位置精度等级与系统性能关系：位置证明系统执行时延随位置精度等级增加而增大。

2 系统架构

区块链技术是多种技术的融合，包括加密、共识机制、激励机制、分布式存储和智能合约。本质上，区块链是用密码方法保证其不可破坏的、不可篡改的链式数据结构（或公共账本），它由一系列区块组成，后一个区块通过包含前一个区块的加密散列值与前一个区块相连，该区块还包含时间戳、随机数、交易数据等。然后，通过共识算法，如工作量证明（PoW）和权益证明（PoS），网络中的所有对等点对区块数据写入权（公共账本记账权）达成共识。获得记账权的对等节点随后将打包的块添加到链中，链上记录的数据无法修改。这整个过程被称作挖矿，参加记账权竞争的对等节点被称为“矿工”。对公有链来说，最终获得记账权并完成记账的“矿工”将获得代币奖励，这种机制称为激励机制。当前，至少有4种类型的区块链网络：公有链、私有链、联盟链和混合链。本文介绍的区块链网络是混合链，混合链网络中不同的对等节点根据其不同的职能有不同的权限。

用户的位置数据描绘了用户的数字轨迹。除此之外，攻击者可通过数字挖掘，探寻该数字轨迹更深层次的上下文信息，如个人习惯、兴趣爱好、社交活动等。这些敏感信息的暴露使用户成为追踪广告、垃圾邮箱、恶意跟踪等非法活动的受害者，造成用户的精神及财产损失，甚至使用户受到人身伤害。传统位置证明系统架构中，用户的 LC 不由用户控制，或存储在中央服务器上，或存储在分布式数据库上，为了解决这些缺陷，本文提出基于区块链的位置证明系统架构，并结合零知识位置证明（ZK-PL， zero-knowledge proof of location）协议，使用户完全掌握自身的LC。

ZK-PL系统架构由3个组件组成，分别是公共账本、LBSP 以及用户，如图1 所示。公共账本是由CIN组成区块链网络，每个CIN为一个点，两个地理位置相邻的CIN组成一个块，两个地理位置相邻的块组成一个区，两个地理位置相邻的区组成一个域，两个地理位置相邻的域组成一个宏，以此方式，公共账本覆盖的地理范围呈指数级方式增加，满足任何的应用场景。对每个CIN进行二进制编码，图中 CIN 编号范围为0000~1111，其中左上角CIN为0000号，右下角为1111号（按照左0右1、上0下1编码方式）。公共账本的主要职能有：第一，为用户签发LC；第二，记录LC指纹；第三，为用户提供生成PL所需要的公共参数（CRS，common reference string）；第四，保存服务记录。用户主要职能有：第一，以短程通信方式接入区块链网络，向附近CIN请求签发LC；第二，利用LC生成PL，以远程通信方式向LBSP请求相关位置服务。LBSP的主要职能有：第一，验证PL，为用户提供位置服务；第二，以远程通信方式请求CIN保存服务记录。该系统架构实现用户位置数据与位置服务的分离，各组件职能明确，避免了服务器或其他第三方掌握敏感的用户隐私信息。公共账本作为可信之根本，在不暴露用户隐私的情况下杜绝了LC 的伪造、篡改及抵赖。用户则可通过生成零知识位置证明，向 LBSP证明其持有证书的合法性，获取位置服务。相对地，LBSP 只能从ZK-PL中获取必要的用户位置信息，避免了用户隐私泄露。

图1 零知识位置证明系统架构 Figure 1 Zero-knowledge location proof system architecture diagram

明确了系统架构组成及各组件职能之后，需要明确各个组件之间的交互细节。为此，下文提出一种零知识位置证明协议（ZK-PLP， zero-knowledge proof of location protocol）。

3 ZK-PLP

ZK-PLP由两部分组成，分别是LC签发协议和LC验证协议。其中，LC签发协议主要用于规定用户如何与CIN交互，请求签发LC；LC验证协议主要用于规定用户如何产生 ZK-PL 以及LBSP如何验证ZK-PL的合法性。协议流程如图2所示。LC签发阶段，用户首先以短程通信方式接入区块链网络，请求邻近 CIN 签发 LC。CIN在收到请求后，验证请求的有效性，验证通过则返回 LC 参数；同时，CIN 结合用户请求中包含的信息，生成 LC 指纹并将指纹广播至整个区块链网络，等待网络中节点挖矿保存指纹。而用户在收到CIN返回的LC参数后，生成LC保存至本地，留待请求位置服务时使用。LC验证阶段，用户使用本地保存的LC生成ZK-PL。然后，以远程通信方式将ZK-PL发送给LBSP，请求位置服务。LBSP在收到ZK-PL后，验证ZK-PL的有效性，验证通过则返回位置服务；同时，LBSP生成服务记录并请求CIN将服务记录保存至区块链网络。

图2 零知识位置证明协议流程 Figure 2 Zero-knowledge location proof protocol flowchart

3.1 LC签发协议

在阐述LC签发协议细节之前，首先说明LC格式及其各参数的含义，LC格式如下。

各个参数含义如表1所示。需要额外说明的是，每个用户拥有唯一的公私钥对，可由权威中心（政府）统一管理，类似于个人身份证。CIN编号之所以能表征用户出现地点，是因为CIN的地理位置是固定的且用户只有在短程通信范围内才能成功签发LC，通信范围越小，其表征的用户位置越精确。

下面说明 LC 签发流程细节：假设某用户需要签发一张LC，首先，该用户通过短程通信的方式接入区块链网络，向邻近的CIN发起证书签发请求，请求格式如下。

其中，infuser 表示由用户发出的消息，大括号的下标skuser和pkCIN分别表示用户私钥和 CIN 公钥对大括号内消息进行加密。siguser为用户对其发出消息的数字签名，目的是防止恶意中间人对消息进行篡改。CIN公钥加密确保只有CIN才能解密请求，防止恶意中间人窃取请求中的消息。

CIN收到用户请求之后，做如下检测：

1) 请求内容是否被篡改；

2) 用户与其通信方式是否为短程通信。

检测通过后，CIN响应用户，响应格式如下。

其中，证书序列号为CIN生成的随机数，一定程度上，证书序列号代表着证书所有权。CIN以类似方式对响应及响应中的消息分别进行加密和数字签名，确保恶意中间人无法篡改与窃听。

成功接收到响应后用户告知CIN，然后用户利用infuser与infCIN生成 LC 保存至本地。与此同时，CIN 生成位置证书指纹（DLC，digest of location certificate），形式如下。其中，||为连接符。

并将其广播至区块链网络，等待挖矿保存至公共账本中。完成 DLC 广播后，CIN 删除infuser与infCIN。CIN的所有行为都可通过嵌入智能合约的方式使其规范化，防止其作恶。当用户需要LBSP提供位置服务时，可利用保存在本地的LC生成ZK-PL，证明其拥有的证书的合法性，即该用户拥有的证书与链上证书指纹匹配。

3.2 LC验证协议

现有的位置服务种类繁多，不同的位置服务中，LBSP需要查验的用户位置信息也不尽相同。例如，在打卡获取商场优惠券服务中，LBSP 只需验证用户是否去过特定商场，而不需要知道用户身份（即公钥）、去该商场的时间以及去到商场的哪个特定位置（假设商场为一个宏，LBSP 不需知道用户去哪个域、哪个区、哪个块甚至哪个点）。再比如，某用户需要向法院提供不在场证明，则他/她需要提供证明，披露其身份以及在特定时间出现在特定地点。基于ZK-SNARK的LC验证协议允许用户根据位置服务类型，生成不同的ZK-PL，只披露必要的位置信息，更好地保护用户隐私。

依据前面分析，不同位置服务可能要求用户披露不同的 LC 参数，也可能需要不同的位置精度。因此，按披露参数不同，将ZK-PL分为若干类型，如表2所示。

表2 中公共参数与私密参数统称为输入参数，为生成ZK-PL的输入；公共参数直接披露给LBSP。位置精度由 CIN 的短程通信范围决定，通信范围越小精度越高，相同覆盖面积所需要的CIN个数越多，最终导致CIN的编码长度越长。在打卡获取商场优惠券的例子中，商场由8个CIN覆盖，因此编码长度为4位（即精度等级为4）。

下面说明 LC 验证流程细节：假设上述 LC签发流程中用户欲使用签发完成的 LC 生成ZK-PL，向LBSP证明他/她去过0域1区，从而获取相应的奖励。此场景应选择表2中类型1的ZK-PL。用户需要证明以下算式成立。

其中，||为连接符；∧为按位与运算；1100 为位置掩码，用于屏蔽LBSP不必了解的位置信息，精度等级4中的位置掩码如表3所示。

(1) 计算问题到QAP问题的转化

一般计算问题需转化为 QAP 问题才能通过ZK-SNARK协议，以零知识的方式证明其计算的正确性。QAP问题可以简单地描述为：对于一系列多项式以及一个目标多项式，寻找这些多项式的线性组合，使目标多项式能够整除此多项式组合。计算问题(5)可转化为以下QAP问题。

其中，{li(x),ri(x),oi(x)} 为变量多项式，i=0代表伪变量one，其变量赋值固定为1。 代表公共变量（本例中m=0），即表2中公共参数，其赋值是LBSP可见的。 代表私密变量，即表2中私密参数以及一系列私密中间值。t(x)为 d 阶目标多项式。至此，用户提供 LC 参数使之满足式（5）的问题转化为用户提供见证。

使之满足

(2) 计算CRS

计算问题到QAP的转化完成之后，需要选取随机值组{s,g,ρl,ρr,αl,αr,αo,β,γ}。然后，利用随机值组以及上述QAP，计算证明密钥（proving key）以及验证密钥（verification key）。

其中，s,ρl,ρr,αl,αr,αo,β, ，g为椭圆曲线G1的生成元； 。

用户利用证明密钥及本地计算的见证生成ZK-PL并发送给LBSP。然后，LBSP利用验证密钥验证ZK-PL的有效性。一旦CRS计算完毕，随机值组立刻删除。因为任何拥有该随机值组的恶意中间人可在不知道问题正确解的情况下伪造ZK-PL，通过 LBSP 的验证，骗取位置服务。因此，随机值组也被称为“毒废料”。步骤 1)、步骤2)统称为可信初始化（TS，trusted setup），由系统中的CIN完成。正如前文所述，CIN中嵌入的智能合约可规范其行为，保证用户隐私不泄露，保证ZK-PL不可伪造。

(3) 计算见证

初始化完成以后，为了生成ZK-PL，用户需要根据自己的LC证书，本地生成QAP问题的解，类似于式(7)。

此处之所以不需计算 ，是因为 是公共变量多项式的赋值，该赋值（即需要披露的位置信息）可直接披露给 LBSP。需要注意的是，私密变量及中间变量的赋值不可直接披露给LBSP，因为这些赋值包含了LBSP不需要知道的位置信息。

(4) 生成ZK-PL

用户使用变量多项式计算L(x)、R(x)和O(x)。

用户计算

然后用户根据证明密钥计算

其中，k<d。用户根据证明密钥计算证明变量多项式及其α偏移。

然后用户计算变量一致性多项式。

最后，用户将计算的各部分组成ZK-PL。

用户将生成的ZK-PL发送给LBSP，请求位置服务，请求格式如下。

其中，index为服务编号，指明用户所请求的服务类型。需要说明的是，用户向LBSP请求服务时采用远程通信方式，其加密方式与传统位置服务系统一致，本文不作讨论。此外，用户远程通信中使用的ID不再是其唯一公钥。因此，用户真实身份不会暴露。

(5) 验证ZK-PL

LBSP收到用户请求后，首先检测该LC是否失效。LC失效是因为某些位置服务存在响应次数限制。例如，打卡获取商场优惠券服务中，每张LC只能兑换一张或者数张优惠券。LC有效性检测通过查询公共账本服务记录的方式实现，每次LBSP完成一次服务之后，会请求CIN保存服务记录，服务记录具体格式后文说明。

检测LC有效后，LBSP检测ZK-PL是否合法：LBSP使用验证密钥计算验证变量多项式。

然后检测下面式子是否成立。

其中，，称为双线性映射。双线性映射将加密空间G1中的两点x，y映射为另一加密空间G2中的两点的积xy，如图3所示。

图3 双线性映射示意 Figure 3 Bilinear mapping diagram

检测ZK-PL合法后，LBSP返回用户请求的服务并生成服务记录。

其中，pkLBSP为该LBSP的唯一公钥；DLC为本次服务用户所用的 DLC；index 为本次提供的位置服务类型；times为截至当前提供该类型位置服务给该用户的次数。生成服务记录之后，LBSP以远程通信方式请求区块链网络中某个CIN保存服务记录。收到请求的CIN以同样的方式将服务记录广播至区块链网络，等待“挖矿”保存在公共账本中。如上文所述，之后 LBSP 可通过查询账本中服务记录的内容判断用户使用的LC是否有效。

至此，用户完成了证明其在 0 域 1 区并获得了相应的奖励，其他应用场景交互流程类似，由于篇幅限制，本文不再详细讨论。下文将对提出的位置证明系统的安全性进行分析，并进行实验研究位置精度等级对该位置证明系统效率的影响。

4 性能评估

本节讨论提出的位置证明系统面对数种可能攻击的安全性，以及位置精度对系统性能的影响。

4.1 安全性

(1) 身份欺骗

身份欺骗指的是恶意用户向CIN提供与签名私钥不匹配的公钥，顶替其他用户生成LC证书。在 LC 签发协议中，LC 证书参数serialno、time以及number均由CIN产生，而CIN由嵌入的智能合约保证其行为诚实，因此恶意的用户只能对CIN进行身份欺骗，即发送假身份 给CIN。但CIN可通过检测式(24)是否成立来判断用户提供的 是否合法。

其中， 与 分别表示用 解密和用skuser加密。如果用户提供的与用户用于签名的sk user不匹配，则检测不通过。

(2) 服务欺骗

服务欺骗指的是不拥有 LC 的恶意用户生成假证明骗取LBSP的位置服务以及恶意用户重复利用同一 LC 骗取某些特殊的、请求次数有限制的位置服务。可通过检测式(18)~式(20)是否成立来杜绝第一种行为。可通过查询公共账本中的服务记录来杜绝第二种行为，即查询用户使用的LC是否已经超过其使用次数限制。

(3) 隐私推导

隐私推导指的是恶意攻击者利用可见协议漏洞、DLC及ZK-PL推导用户位置隐私及位置隐私包含的其他上下文信息。在LC签发过程中，用户位置信息只有用户自身以及CIN可获得，但是因为CIN由内嵌智能合约限制，不会泄露用户位置隐私。并且，公共账本上只存储了DLC，哈希函数的抗碰撞性以及其逆向不可计算性可保证无法从 DLC 中得到LC，从而不会泄露用户隐私。在LC验证协议中，单项陷门函数可保证恶意用户无法从CRS以及ZK-PL中获取见证。因此，LBSP只能获得其应知晓的信息而不会获得额外的隐私信息。

4.2 系统效率

下面通过实验仿真研究位置精度等级，即CIN编码位数对系统性能的影响。实验环境如下：主机型号MateBook 13、1.8 GHz i7处理器、8 GB RAM。实验基于 Github 开源项目 Circom和Snarkjs进行二次开发，主要开发语言为JavaScript。Circom是将计算问题（程序）转化为算术电路的电路生成器，而 Snarkjs 是可以对Circom 生成的计算电路进行满足性验证的密码学证明系统。由于提出的位置证明系统主要时延来自ZK-PL的产生与验证，因此实验针对位置精度等级4到位置精度等级70的零知识位置证明系统，测试其 LC 验证过程各阶段执行时间，得到如图4所示结果（位置精度等级70对应CIN编码位数为70，可对量级1021的CIN进行编号。假设每个CIN覆盖范围为1 m3，则70位的CIN可覆盖范围为 1×1021m3。而地球体积约为1×1012m3，因此，70位的CIN编码满足实际应用需求）。

从实验结果图可知：计算见证的执行时间基本不随位置精度等级变化，稳定在650 ms左右；同样地，验证ZK-PL的执行时间不随位置精度变化，稳定在3 800 ms左右。可信初始化的执行时间大致随位置精度等级呈线性增长，最小值为1 024 ms，最大值为4 299 ms；生成ZK-PL的执行时间随位置精度等级增加而始化时执行一次，此后每次不同位置服务过程无须再执行，因此提出的位置证明系统的总执行时间可大致估计为其余三者时间总和，约为5 240~6 686 ms。该执行时延满足大部分位置服务，如基于位置的个性推荐服务、基于位置的社交网络、基于位置的定点签到服务等。但对于一些时延十分敏感的服务，如实时定位导航，该系统有所欠缺。因此，此后的工作将围绕如何缩短系统时延展开，将从协议流程、电路生成器、密码学证明系统等方面出发，优化提出的零知识位置证明系统。

图4 系统效率与位置精度等级关系 Figure 4 Diagram of system efficiency and position accuracy

零知识位置证明系统首次将零知识证明引入位置证明系统中。零知识证明协议保证了它的隐私保护性，另外，5~7 s的延迟可满足绝大多数位置服务。因此，零知识位置证明系统有着较好的隐私性和效率。

5 结束语

本文设计了一种新型的位置证明系统架构，并且在此系统架构的基础上，首次引入零知识证明，设计了一种基于 ZK-SNARK 的位置证明协议，由此二者组成零知识位置证明系统。该零知识位置证明系统允许用户自主选择披露的 LC 参数，提供任意精度的位置证明，实现用户可控的分级隐私保护。此外，本文对提出的零知识位置证明系统安全性进行理论分析，分析表明，该系统可应对可能的安全攻击。最后，针对位置精度等级对系统效率的影响，进行实验探究。实验结果表明：位置证明系统执行时延随位置精度等级增加而增大，等级4~70的执行时延为5 240~6 686 ms。70位的编号可对量级为1021的CIN进行编码，该量级的CIN可覆盖足够大的范围，具有较好的实用性。另外，除了少部分时延非常敏感的位置服务外，如实时定位导航，提出的零知识位置证明系统的时延可满足大部分位置服务，如基于位置的个性推荐服务、基于位置的社交网络、基于位置的定点签到服务等。之后，笔者将考虑通过优化协议流程，采用不同的电路生成器以及密码学证明系统等方式优化零知识位置证明系统性能，使之适用于所有的位置服务。

作者简介

吴炜（1995-），男，安徽安庆人，同济大学硕士生，主要研究方向为区块链和隐私保护 。

刘儿兀（1973-），男，福建福安人，同济大学教授、博士生导师，主要研究方向为位置服务、定位导航、人工智能和区块链 E-mail：erwuliu@tongji.edu.cn。

杨昌鑫（1997-），男，河南信阳人，同济大学硕士生，主要研究方向为区块链 。

王睿（1984-），男，安徽宣城人，同济大学副教授、博士生导师，主要研究方向为无线通信和智能信号处理 。

声明：本文来自网络与信息安全学报，版权归作者所有。文章内容仅代表作者独立观点，不代表安全内参立场，转载目的在于传递更多信息。如有侵权，请联系 anquanneican@163.com。