原文来自：Hu et al. - - Searching an Encrypted Cloud Meets Blockchain A Decentralized , Reliable and Fair Realization
【翻译】
可搜索加密结合区块链：去中心化、可信且公平的实现
摘要：直接在加密数据上进行搜索是一项有前景的技术，它使用户能够更有效地利用数据(这些数据一般加密后外包给云服务提供商等远程服务器)。到目前为止，大多数现有的解决方案都是针对诚实但好奇(honest-but-curious)的服务器，而针对恶意(malicious)服务器的安全设计还没有引起足够的重视。
直到最近，才有一些研究解决了可验证设计(verifiable designs)的问题，即数据所有者可以验证搜索结果的完整性。不过，这些验证机制高度依赖于特定的加密搜索索引结构，并且不支持复杂的查询。因此我们缺乏一个通用的验证机制，使它可以适用于所有的搜索方案。此外，当检测到一个不诚实(unfaithful)的服务器时，没有有效的对策(如，惩罚欺骗者)可用。
在本文中，我们探索了以太坊中的智能合约的潜力，以太坊是一种新兴的基于区块链的去中心化技术，为可信和透明的计算提供了一个新的范例(paradigm)。
通过用一个精心设计的智能合约替换中央服务器，我们构建了一个去中心化的(decentralized)隐私保护搜索方案，数据所有者可以放心地接收正确的搜索结果，而不必担心恶意服务器的潜在错误。为了更好地支持实际应用，我们还设计了一个新的智能合约来实现搜索结构的公平性，在这个合约中，每个参与者(特别是在多用户环境中)都得到了平等的对待，并受到激励来遵守正确的计算。这样，一个诚实的人总能得到他应得的，而一个恶意的人什么也得不到。最后，我们实现了构建的原型，并将其部署到一个局部模拟网络和一个官方的以太坊测试网络中。大量的实验和评估证明了我们的去中心化隐私保护搜索方案在加密数据上的实用性。
【补充】诚实但好奇：服务器试图从存储的加密数据和/或元数据中学习尽可能多的信息，但同时正确地执行可搜索加密协议。
一、引言
由于存储和计算资源需求的增长，如今的企业组织往往会把数据外包给云服务提供商等远程服务器。不过由于外包数据可能包含敏感信息，数据拥有者在外包给服务器前往往都会选择加密他们的数据(例如金融交易信息、医疗病历等数据)。但这反过来又会妨碍数据的使用，比如会妨碍经常用到的搜索操作。
自从在可搜索加密方面的开创性工作[1]以来，许多研究都致力于设计有效和高效的机制，使搜索能够在加密数据上进行。在大多数现有的工作中，远程服务器被建模为一个诚实但好奇(honest-but-curious)的实体[2][3]，它从不试图偏离规定的协议。然而，在现实中，恶意(malicious)服务器可能只返回部分搜索文件，甚至返回压根与搜索结果不匹配的文件(例如，由于随机故障)。更严重的是，任何安全漏洞和内部攻击者都可能非法获得修改数据计算的权限。当主机被恶意(malware)软件感染(例如，电子邮件附件、受感染的P2P媒体)，进而给了攻击者一个高访问权限时，就会发生这种情况。为了解决这些问题，迫切需要针对恶意服务器的安全设计来促进加密数据搜索的广泛应用。
最近，一些研究已经在设计可验证的隐私保护搜索方案，其中数据所有者可以验证搜索结果的完整性。尽管如此，它们的验证技术(例如使用MAC[4]或散列表[5])高度依赖于特定的搜索方案，并且目前只支持简单的查询方式，如单个关键字搜索。如何对现有的支持语义和复杂数据结构的查询(如相似度搜索[6]或图结构的数据[3][7])等多种搜索方案增加可验证性，目前尚未研究清楚。更重要的是，现有的可验证搜索方案都是针对作弊行为(cheating)的检测，却没有跟进有效的应对措施(如惩罚作弊者punishing the cheater)，这极大地阻碍了该方案的推广应用。以通用的pay-peruse模型为例，在最坏的情况下，数据所有者可能会在损失金钱的同时得到一个错误的结果，而恶意服务器则通过欺骗赚钱。这显然需要在加密数据上实现更可靠的搜索方案，不仅需要可验证性来检测恶意服务器的错误行为，还需要内置的公平机制来保护数据所有者的利益。
为了解决上述问题，我们首先注意到可能出现欺骗的主要原因是中心服务器太强大却没有受到监视。因此，我们建议采用智能合约(smart contract)，这是一种新兴的基于区块链的去中心化计算范式，在以太坊(Ethereum)[8]中，所有操作都是透明可靠的。不需要中央服务器，而是将搜索查询外包给智能合约，我们不仅能借助它得到正确的、不可篡改的结果，而且不需要数据所有者的进一步验证。只要以太坊的安全得到保证，它就能彻底消除我们对恶意敌手的疑虑(misgivings)。
为了实现这一目标，我们首次提出了去中心化的隐私保护搜索方案Π，并且使用了目前广泛使用的分布式平台：以太坊中的智能合约。为了给一个典型的实例，我们基于经典的反向索引搜索对称加密方案[5][9],在以太坊中设计出了相应的智能合约来克服原方案存在的各种问题(例如，燃料限制gas limitation )。此外我们还强调，我们的结构(framework)是一个通用的结构，许多支持复杂的表达性(例如，相似度搜索)和结构化数据(例如，图)的搜索方案也适合我们的方案，它们也可以被修改为去中心化方案。
为了进一步缩小理论可行性和实际的隐私保护搜索方案之间的差距，我们注意到，在现实世界中这种应用程序背后的关键激励机制是，数据拥有者希望将计算代价巨大的工作外包给工人(即，处于云环境下的远程服务器)，作为回报，工人将获得一定数额的货币作为报酬。因此，我们创造性地使用智能合约来创建了一个公平的互惠机制，在这个机制中，数据拥有者只要诚实地支付货币，就可以收到正确的搜索结果，而工人只要忠实地遵守合约，就可以得到报酬。
此外，我们还考虑了一个更复杂的场景，即多用户环境[2][10]，数据拥有者可能倾向于通过与合法用户共享数据库来获利。因此，我们提出了一个公平的隐私保护搜索方案，并设计了一个新的智能合约，它能够在多用户环境中追踪各方的货币报酬情况，包括交易费用。因此该机制可以确保只要数据拥有者展示了脚本(transcipt)从而允许其他用户搜索数据库的文字记录，那么他就能获利；只要用户支付了报酬，那么他就可以得到正确的搜索结果。
综上所述，我们的主要贡献如下：
•利用以太坊(Ethereum)的智能合约(smart contract)，我们首次提出了一种去中心化的隐私保护搜索方案Π，保证数据所有者收到正确的搜索结果，并且在面对恶意敌手时无需进行验证。
•在此基础上，我们还创造性地引入了公平(fairness)的概念，并提出了一个公平的隐私保护搜索方案Π-fair，这样每个参与者，特别是在多用户环境下，都能得到公平的对待和激励，以遵守正确的计算。
•我们实现了设计的原型，分别把方案部署到一个本地模拟网络和一个官方的以太坊测试网络上。通过大量的实验和评估，验证了针对加密数据的去中心化搜索方案的可行性。
二、背景知识
A. 以太坊的智能合约
①Ethereum
以太坊是一个很有前景的基于区块链的去中心化计算平台[8][11]。它的安全性由一组谜题(或块)的密码链来维护。以太坊网络中的矿工在挖掘新块时验证并认同交易。他们通过成功地解决一个指定的密码难题来打包(挖掘)一个新的块，并且获得新生成的加密货币作为报酬，从而激励他们去挖掘更多的块。这种激励机制保证了网络的正确性。总的来说，以太坊为我们提供了两个优秀的特性：
•共识。整个网络都认可该网络中的规则，从而去验证每个交易和块。在以太坊上存储的数据和执行的计算必须在不同的矿工之间达成一致共识，并且不能篡改或否认。
•透明。以太坊是一个公共网络。所有存储的数据和执行的计算对任何用户都是公开透明的。
因此，以太坊作为一个可信的基础，它的正确性和可用性受到信任，而隐私不受信任。
② Smart Contract
以太坊中的智能合约是在区块链中存储状态的应用程序。这些程序可以简化、验证和强制合同的执行过程。每个由特殊地址(a special address)标识的智能合约由脚本代码(script coded)、货币余额(currency balance)和形式为键(key)/值(value)的存储空间(storage space)组成。一旦创建并部署到以太坊，智能合约的代码就永远不能被修改，甚至创建者也不能。
③Gas System
燃料系统是智能合约中一个非常有用的功能。它能够降低对以太坊网络的拒绝服务(DoS)攻击。具体来说，智能合约的脚本被编译成以太坊操作码(op codes)并存储在区块链中。每个操作码将花费一定数量的预先定义的燃料gas[8]。当通过发送交易来启动智能合约时，交易发起人必须指定支持执行的可用的燃料上限(gas Limit)，以及发起人愿意为每单位燃料支付的相应的燃料报酬(gas Price)。只有当发起人的余额大于gas Limit×gas Price时，交易才会被成功包含在区块链中。
加密工具
在我们的结构中，我们使用了可变输入长度伪随机函数(PRFs)，它是多项式时间的可计算函数，不能在任何多项式时间的概率内被敌手手从一些随机函数中区分出来。在[12]中可以找到PRFs的正式定义。
三、准备工作
系统概述
在图1中，我们概述了我们的设计架构(architecture)。我们的方案由以下三种算法组成：
•Setup(DB): 数据拥有者输入数据库DB，得到输出三元组(EDB、K、δ)，其中EDB是加密数据库，K是密钥，δ是数据拥有者的状态(state)。
•Search(K,δ,w;EDB): 数据拥有者输入密钥K，自身的状态δ，以及一个搜索关键词w∈{0,1}∗，然后向智能合约输入加密过的数据库EDB。接着智能合约输出一组标识符(identifiers)，而数据拥有者没有输出。
•Update(K,δ,op, id, Wid;EDB): 数据拥有者输入密钥K，状态δ，操作op∈{添加add、删除del}，文件标识符id，和一组不同的关键字集合Wid，，并向智能合约输入EDB。这些输入的操作表示通过标识符id，对文件执行添加或删除操作。
为了便于理解，我们没有在后面的结构(framework)中展示对数据文件的具体加密操作，因为数据拥有者可以很容易地通过传统的对称加密方案来加密数据，然后将加密数据外包给任何去中心化的文件存储网络(例如星际文件系统IPFS)。
符号
一个数据库DB =(idi,Wi) di = 1就是一组标识符-关键词对(identifier-keyword pairs)，其中idi∈{0,1}l，Wi⊆{0,1}∗。数据库DB的关键字集合为W =∪di=1Wi。给定关键字w∈W的文档集合为DB(w) = {idi|w∈Wi}。我们总是将m = |W|和N =∑w∈W |DB(w)|分别设为不同关键词的数目和数据库中所有关键字-文档对(keyword-document pairs)的数目。
设计目标
Fairness公平。隐私保护搜索的公平性是本文研究的重点。我们的核心结论是基于现实世界中此类应用背后的激励机制的经济性质。宽泛地说，我们的公平理念将保证：
• 只要数据所有者为矿工的搜索工作付费，那么他就能得到正确的搜索结果；只要矿工诚实地遵守协议，那么他就能获得报酬。
• 在多用户环境中，除上述要求外，其他用户只要为矿工的搜索工作以及对数据所有者的数据访问行为付费，那么用户就可以得到正确的搜索结果。数据所有者只要展示脚本(如，搜索令牌ST)就可以赚钱。
总之，公平保证了每一方都有动力去做正确的计算。如果一方违反(deviates)协议，那么他什么也得不到。
Soundness稳健性。这个属性表示如果服务器试图违反协议，它将被捕获。以前的研究通常是让数据所有者进行一系列的验证来达到稳健性。但是在本文中，我们扩展了这一概念：我们默认接收到的搜索结果是可信(reliable)且绝对正确的(correct definitely)，因此数据所有者不需要对搜索结果进行验证。
Confidentiality保密性。我们应该确保数据文件(file)以及查询关键字(keyword)是保密的，使它们不被敌手所知。此外，我们的目标是提供另一个强大的安全概念：更进一步的隐私(forward privacy).
四、设计挑战与对策
直观地说，任何现有的隐私保护搜索方案都可以用智能合约替换中央服务器，从而直接建立去中心化的环境。但是，一些保证智能合约的健壮性和安全性的创新特点反而成为现有方案与智能合约融合过程中的阻碍。在这一部分中，我们提出了一些主要的设计挑战，并在较高的层次上总结了对策。
燃料系统Gas System
Gas Limitation燃料限制。在以太坊中，在调用智能合约中函数时所进行的每一笔交易都有一个消耗燃料的上限，称为gas Limit，如第II-A节所述。每个操作，包括发送/存储数据和执行计算，都有固定的燃料成本。这就限制了所设计函数的计算步骤和存储空间。因此，为了使在大型数据库上进行隐私保护搜索变得可行，我们倾向于将数据库划分为更小的数据库并单独管理它们。大体思想如下：在构建大型加密索引( EDB)的Setup 指令中，我们将加密索引划分为几个块(blocks)，并将它们上传到具有足够多交易的智能合约中，这样每笔交易花费的gas就比gas Limit少。为了确保正确性，合约需要将数据排列(align)在一起，以返回所有匹配的结果。
Gas Availability燃料的可用性。在智能合约中，每笔交易还与一个gasPrice有关，该价格指名了发送方愿意花费多少钱(以太币ether)来购买一单位gas。以太坊中需要启动交易的用户的帐户余额大于执行交易的燃料成本(cost)，否则交易将中途中止，并且已消费的燃料无法退还。因此，考虑到燃料成本，我们应该非常仔细地设计智能合约。一方面，我们要确保智能合约中的每项功能函数(如搜索Search、更新Update)的燃料成本不超过发送方的账户余额；另一方面，我们应该及时跟进每次指令(phase)执行所消费的燃料量(gas consumption)，这样才能最终保证公平。更多关于燃料可用性的要求，我们在第七节中的协议中进行了说明。
验证者困境
在以太坊中，矿工被要求验证交易的有效性(validity)。然而，当智能合约中有大量复杂的表达式时，验证交易可能需要花费很大的计算代价。因此对于理性(?)的矿工来说，他们会倾向于跳过那些代价巨大的交易验证步骤，以便在挖掘下一个区块的竞赛中保持领先。这种现象称为验证者困境[13]。
为了减少这种攻击，我们希望尽可能地减少智能合约的计算负担(burden)。
我们的第一个想法是，智能合约支持字典(dictionary)数据类型，而主要的计算代价在于Search指令。因此，我们使用字典数据类型来存储加密索引(即， EDB)，从而使搜索的时间复杂度为O(dw)，其中dw是关键字w曾经(historically)被添加到数据库的次数。——w所包含的文件数目？|DB(w)|
我们的第二个优化是利用打包方式(packing method)，这个灵感来自[9]。具体来说，我们可以打包多个明文，然后对打包结果进行加密，从而获得一个大小相同的密文。因此，最终的搜索结果是打包块而不是单个(individuals)。此外，打包也利于我们规避之前提到的燃料限制，因为它大大降低了存储成本。不过我们注意到，尽管[9]声称也使用了打包方法，但没有明确描述该如何实现它，而我们在第五节给出了详细结构(construction)。
五、去中心化结构
在本节中，我们建立了一个去中心化隐私保护搜索方案Π，并且这个方案具有稳健性(soundness)和保密性(confidentiality)。Π是建立在现有的开创性的反向索引结构(如[5][9])之上的。我们将在第八节中说明，我们的设计原理也可以应用于其他具有表达性查询或复杂数据类型的加密搜索方案。
基本结构
图2给出了Π的正式描述。
为了简单起见，我们令F:{0,1}λ×{0,1}∗→{0,1}λ,G:{0,1}λ×{0,1}λ→{0,1}∗是两个伪随机函数(注：对于不同的输入密钥，应该有不同的伪随机函数）。使用||来表示连接(concatenation)操作。“[·]”是一个向下取整函数(floor function)，“|·|”表示列表中元素的数目。对于字典数据类型，它包括：添加(Add)和删除(Delete)两种算法。我们使用术语Get来获取字典中指定的数据项。例如，给定一个字典数据类型γ和一个输入标签l，Get(γ,l)将输出相应的项目d ||r，并解析成d和r。——基本元素label-data 对，r是相应的伪随机密钥
在Setup指令中，数据所有者把数据库DB (w)分为α+ 1个块，每个块有p个项目。这里p是由数据所有者所设置的系统参数。我们使用串连接(concatenation)把多个文件标识符(id)打包成一个。为了保密性，打包结果id~ 的比特长度应该小于安全参数λ的长度。因此，我们有p≤λ/l，其中l是文件标识符的比特长度。另外还注意到，在上传数据库之前，列表L应该按字母顺序排列。否则，它将泄漏有关输入的处理顺序的信息。为了避免超出gasLimit，我们将加密的数据库划分为n个块，并使用n个不同的交易把它们逐个发送到合约。在智能合约端，它们迭代地(iterative)接收这n个交易并使用字典数据类型将它们放在一起。类似地，搜索过程也将通过R次交易完成，每个交易最多返回step个项。其中n、R、step为公共系统参数，并由实验确定最佳值。
在Search指令中，每次查询时，数据所有者把包含搜索令牌(search token)的交易发送到指定的智能合约。注意，每个合约在以太坊中都有一个惟一的地址。智能合约利用令牌和预先储存的加密索引(EDB)，执行Search算法并把搜索结果(即，文件标识符id)存储到智能合约的状态(state)，该状态是公共的(包括数据所有者在内)。
支持动态更新(Dynamic Updates)
Π支持动态更新。在Add指令中，我们不再使用打包方式去加密文件标识符(id)。因为把多个id明文加密成一个密文会使智能合约难以识别哪个文件-关键字对(file-keyword pair)已被先前删除，即，它是否存在于集合IDdel中。此外，在实际情况中，一般只需要对一个或几个文档进行增删操作，所以Update算法的gas cost比gas Limit低得多。因此单独地处理文件id有利于进行Update操作。对于智能合约的协议，里面的交易触发函数(triggering function)不返回任何结果，任何函数的执行只会改变它的状态，当然这个状态会永久存储在以太坊上。我们的方案就是通过将搜索结果保存到状态，然后数据所有者去读取状态，从而得到搜索结果。
前向隐私(Forward Privacy)
更进一步的隐私是本文一个重要的安全设计目标。它意味着对手不知道新添加的文件是否包含以前搜索过的关键字。这个灵感是收到了文献[5]的启发，我们的方案Π可以很容易地扩展去实现更进一步的隐私。关键思想就是通过陷门加密(trapdoor permutation)，使得搜索令牌(search token)与更新令牌(update token)无法联系起来。具体来说，当DB(w)中的第c个文件生成伪随机标签(label)时，我们不再使用一个计数器c来表示增加，而是通过一个陷门加密 π，βc =π-1sk(βc-1)并且标签设置为l = F (K,βc)，——原本是直接用计数c其中β0是一个随机选择的整数。然后在于智能合约端，它只能在多项式时间内用公钥计算βc-1 =πpk(βc)，而不能计算βc + 1，因为它没有私钥。鉴于新加入到DB(w)的第(c + 1)个文件没有被搜索过，所以就不能从以前泄露的搜索令牌βc推导出它是否包含以前搜索过的关键字。——敌手用βc无法去搜索第c+1个文件
这个改进的方案和Π有相同的通信复杂性度(communication complexity），并且数据所有者和智能合约只增加一点由排列(permutation)所造成的计算代价(overheads)。
六、安全证明
Soundness稳健性：直观地看，只要以太坊的安全性得到保证，那么我们的方案Π就具有稳健性。这是因为如果智能合约在以太坊上正确执行，那么搜索结果将通过合约的状态而得到永久、公开的存储。以太坊中的每个矿工都可以对数据进行验证，并且它的共识(consensus)属性确保每个搜索操作都能正确执行。
Confidentiality保密性：为了证明保密性，我们遵循了真实理想的模拟范例[9]，并在我们的结构中首次给出了三中状态泄漏函数L = (L1, L2, L3)的正式定义。
定理1.如果G和F是伪随机，那么我们的方案Π在非适应性攻击模型中是L-secure的。
L是泄露函数。
七、公平性
在本节中，我们将展示如何使用智能合约来构建一个基于Π的公平的隐私保护搜索方案。我们对公平的定义是对安全多方计算[14]的一个变体，其灵感来自于最近关于金融公平[15]的著作。我们建希望达到这样一个目标：在经济上激励每一方去进行正确的计算，如果不诚实的一方作弊，那么他最终将一无所获。
单用户环境
我们对隐私保护搜索方案中公平性的主要结论是，在现实中，此类应用程序背后关键的激励机制是让工人(即在云环境下的服务器)在完成委托的搜索任务后，能够获得金钱报酬。鉴于此，所有现有的方案都可能遇到这样的情况：如果数据所有者先付钱，那么恶意的(malicious)工人可能会违反协议，同时还赚到了钱。另一方面，贪婪的(greedy)数据所有者也可能会让工人进行搜索任务而不预先付费。结果，工人完成任务后可能得不到任何报酬。
而我们的方案Π，在保证之前提过的稳健性和保密性以外，也天然能够保证公平性。这是因为无论数据所有者想要执行什么操作(例如，Search、Update)，他都必须先向工人(以太坊中的矿工)支付一种名为Ether的加密货币，这个货币能够购买gas。智能合约在每个矿机上自动执行，然后把正确的操作结果设置为状态，数据所有者去读取状态。
我们要注意到，现有的可验证搜索方案[4][5][16]不支持公平性。它们通常让数据所有者在工人进行查询操作前就付款，然后再验证查询结果是否正确。然而，在这种情况下，工人最终可能会在不遵守协议的情况下赚钱。这在涉及到金融问题的环境中显得尤为不适合。
多用户环境
在多用户环境中，数据所有者允许第三方(即其他通过认证的合法用户)能够在数据库中进行搜索[2][10]，但这样事情就复杂多了。因为用户之间是互不信任的，而我们需要确保每一方都得到公平对待。具体来说，我们需要确保：
数据所有者在用户搜索数据库时能够得到报酬；用户付费后，能够得到正确的搜索结果。
为此，我们修改了方案Π，构建了一个公平的隐私保护搜索方案Π-fair。
Overview概述.图3给出了Π-fair的概述。鉴于智能合约上的每项任务都是公开的，利用现有的技术(如广播加密[10])来添加或移除用户，使他们具有搜索权限是不可行的, 因为这需要把私钥告诉矿工。因此，我们使用了文献[2]中方案的扩展版本：数据所有者接收用户的查询请求，并生成相应的搜索令牌，这样就和他自己在搜索数据库一样了。
Notation符号.这里给出来Π-fair主要用到符号表示。我们使用$来表示加密货币(即，以太币)。$Bowner和$Buser分别是数据所有者和用户的惟一以太坊帐户余额。数据所有者为每次搜索设置价格$offer，用户为每次搜索支付$deposit。执行搜索操作Gsrch的gas cost是一个系统常数，查找操作GLsrch的gas limit和每单位气体价格$gasPrice则由数据所有者指定。
Contract Design合约设计.图4展示了Π-fair的合约设计。Π-fair中的Search()部分与方案Π是完全相同的。为了简单起见，这里我们只将它用作一个子例程(subroutine)，并使用ST表示接收到的搜索令牌，其他细节则省略。
为了保证公平性，我们增加了时间限制T1，这个参数是由用户指定。在T1时间内，数据所有者把搜索令牌发送到合约中并赚钱。超过了T1，则用户的搜索请求过期，用户的押金将被退还。注意，允许搜索的一个重要条件是，押金(deposit)应该大于数据所有者的报价$offer与执行Search()函数的gas cost之和。这是因为查询事务是由数据所有者发起的，并且gas cost也会从数据所有者的账户余额$Bowner中扣除。这是不公平的，因为数据所有者只是触发了代替用户的查询事务。因此，用户必须支付那些额外查询的费用，即gas cost。当搜索工作结束时，数据所有者所花费的cost会被智能合约发送到账户$Bowner。另外还注意到，剩余的押金则应该立即退还到用户帐户$Buser，以防止数据所有者带着退款跑路，方法是使用相同的搜索令牌重复发送查询事务。
在我们的结构中，数据所有者可以通过线下(off-line)向用户发送搜索令牌，并让用户自行发起搜索交易。在这种情况下，合同需要稍作修改：$deposit只需大于$offer，并且令$cost只等于$offer。但是，我们建议通过智能合约来传输和记录搜索令牌，因为它会使任何欺骗行为暴露在公众中，而且如果数据所有者不披露令牌，那么合约可以在经济上惩罚他。
八、结构的广义化(generalization)
近期关于隐私保护搜索的研究都集中在提高其表达力(expressiveness)上，例如支持相似性搜索[6]或开发结构化加密(例如图形加密)[3][7]。但所有这些研究都面临严重的安全挑战：恶意的中央服务器在一些时候可能只输出部分结果，甚至输出不正确的结果。针对这个问题，只要解决了我们第四节提出的设计挑战，那些方案就都可以适应到我们提出的去中心化环境中去。
对于这种广义化的最直观的观察是，智能合约实际上为我们提供了一个可靠且透明的“服务器”，不过它的主要障碍在于如何处理智能合约中gas system的各种限制。而我们提出的几种对策(如，把加密索引分块并单独解决它们、打包多个标识符并加密为一个)为如何解决该问题提供了便利。使用了智能合约的方案，它就天然能够保证健壮性，并且不再需要与恶意服务器打交道。另外，我们在图4中设计的智能合约也为那些多用户环境提供了一个模板，以实现该环境下的公平性。基于此，我们还能够根据特定的实际情况完善合约中的各种复杂多变的条件。例如，在数据所有者希望与朋友共享他的照片的情况下[10]，价格$ offer可以设置为0，从而让其他人免费地搜索数据库。
九、实验和评价
我们用5000多行代码去实现了方案Π的原型(prototype)，包括它的测试程序。我们在一台16GB内存，4个Intel核心i7-3770，运行Ubuntu 16.04.2的计算机上实例化了数据所有者。智能合约被部署到一个本地模拟网络TestRPC和一个官方的以太坊测试网络Rinkeby上。数据所有者端和智能合约分别使用Python语言编写，并使用Javascript和Solidity作为中间交互语言。我们并没有特别展示出方案Π-fair的结果，因为对于各种评价指标(例如,时间成本)，该方案的性能和Π类似，并且Π-fair可以通过对Π施加一系列的控制条件从而很容易地实现，而不需要其他显著的成本。
实现细节
我们用 HMAC-SHA256实现伪随机函数(PRF)和随机预言机(random oracles)。鉴于以太坊目前不支持HMAC实例化，我们遵循了[12]中的HMAC标准结构，并分别使用Python和Solidity来实现HMAC-SHA256。
为了避免超出gasLimit，在Setup指令中，我们把加密的数据库EDB分成了n个子集合，并分别发送到最终包含n个交易的智能合约中。由于gasLimit随时间波动，对于每笔交易，我们令列表L包含70个文件，每次打包的数目设置为p = 8。此外，每次搜索查询最多完成了R个事务，每个事务最多返回step=47个文件。在我们的实验中，R = 4可满足要求。
我们使用了来自Enron电子邮件的数据集，它是一个纯文本文件的集合。我们提取了电子邮件的一个子集，并从原始子集中选择不断增加的子集作为文档集合，这些文档集合具有不同的编号(w, id)(即关键字/标识符)对，表二总结了这些数据集的关键属性。
模拟网络实验
为了展示我们方案的的可扩展性和独特的性能特点，我们首先使用TestRPC在本地构建了一个模拟的以太坊网络。TestRPC是用默认配置初始化的，它很像真实的以太坊环境，只不过它的挖掘块的时间设置为0。这使得我们可以专注于智能合约上关于搜索的性能，而不考虑以太坊中那些耗时的挖掘过程和复杂的网络环境(如广播延迟、交易挖掘延迟)。
表三概述了不同数据集上每个指令的时间成本和交易数量。这里D.O.和S.C.分别代表“数据所有者”和“智能合约”的时间成本。#Tx表示完成相应指令所需的交易数目。通过返回100个匹配的文件来评估搜索时间。通过添加和删除文件来展示Update指令的代价，选择该文件只会产生一笔交易。在Setup指令中，与现有的数据所有者方主导效率的集中式搜索方案不同，智能合约的时间成本远远高于数据所有者。这是因为存储EDB需要完成数千笔交易，每笔交易平均花费4秒来操作。
为了展示核心算法，图5(a)给出了每次找到文件的搜索时间随匹配记录数量的变化图。我们统计了30多个试验的平均运行时间。得到的第一个结论是，较大的结果集的搜索代价较小(在每个匹配文档的基础上)。这归因于在每次搜索运行之前，将以前挖掘的块从磁盘加载到内存中的固定成本。这也解释了我们的第二个结论：数据集越大，搜索算法越慢。因为挖掘出的块越多，加载时间越长。
官方测试网络上的实验
展示我们的方案的可行性，我们把方案Π部署到以太坊的官方测试网络Rinkeby上，该网络可以模仿真正的生产网络。由于余额有限，我们只在最小的数据库DB1上进行实验。我们在Rinkeby上的账户和合同地址如下
•0 x7aef688b95a1bee573d464766b3a6c0470b9b57b。
•0 xece97a98da7f5dbeccb81e772dd04710e676aa96。
为了说明挖掘过程对效率的影响，我们记录了Setup指令中每笔交易产生的块数和相应的gas使用量，如图5(b)所示。总之，它包含350个交易，每笔交易都被挖掘到一个块中，块号从176 837到177 187不等。挖矿的平均时间是15秒，完成整个Setup指令需要88分钟。这再次解释了为什么设置的时间成本由智能合约控制，而不是像现有的中心化搜索方案那样由数据所有者控制。此外，一笔交易消耗的平均gas量为4,201,232。目前，1gas的成本约为1.8*10-8以太币，1以太币约合89美元。因此，每笔交易的成本约为0.076以太(或6.7美元)。乍一看，对于只有查询需要的一般用户来说，这些成本似乎有点昂贵。不过Π仍然适用于许多真实世界的场景。例如，个人的医疗档案对每个人来说都很重要。正确完整的病史可以帮助医生做出准确的疾病诊断和健康评估。在这些高要求的情况下，为了获取高度可靠的数据而花费更多的钱还是值得的。
图6(a)展示了给定搜索令牌后，执行搜索所需的总时间(我们忽略了生成搜索令牌的成本，因为它是一个微秒级的小常数)。图中每个点都是10次执行的平均值。它也清楚地表明了Π的性能缺陷：我们可以看到搜索时间随着匹配文件数目的增加而增加。但造成急剧增长主要原因是完成搜索任务所需要的交易数量的增加。这表明挖掘每个交易的时间成本占了每个搜索的开销。相反，搜索算法本身对效率的影响是微弱的。一般情况下，挖矿过程的时间成本是动态可调的。当区块链环境扩展到允许更高的gas Limitation或更快的挖矿过程时，我们的搜索效率也会提高。
类似的情况出现在图6(b)中，它展示了随着添加/删除文件所需的交易数目的变化而变化的时间成本。通过选择不同大小的文件，我们可以通过不同数量的交易来完成Update。这再次表明，每笔交易的挖掘过程是影响效率的主要因素。
十、结论
传统的隐私保护搜索方案依赖于一个中央服务器来执行搜索任务。而在本文中，我们借助区块链技术，构造了一个针对恶意敌手的去中心化方案。与现有的可验证方案不同，我们的搜索结果天然是是正确的、不可篡改的，并且不需要数据所有者进行验证。此外，我们利用智能合约构造了一个公平的隐私保护搜索方案，其中每一个参与方，特别是在多用户环境下，都能够受到公平对待，并且受到激励去做正确的计算。在模拟网络上的实验结果证实了该方案的可行性。
