论文分享｜Bringing Decentralized Search to Decentralized Services

本文发表在OSDI ’21上，针对区块链应用场景，实现了一款去中心化的搜索引擎DeSearch。确保了去中心化服务中搜索结果的完整性和隐私性。本文在Steemit (一款去中心化的社交媒体) 和OpenBazaar (一款去中心化的电商平台)上实现了DeSearch，并在1312 个虚拟机上进行了实验。结果显示，DeSearch每天可以处理超过 1.28 亿个搜索请求，而用户可以在 1.2 秒内验证结果。

PROBLEM

区块链的发展催生了大量去中心化的应用程序，去中心化服务的诞生初衷是为了对抗传统中心式服务存在的有关数据隐私和审查的问题。然而现有的去中心化应用无法避免使用中心式的搜索引擎来为用户提供服务，如果没有去中心化搜索，反审查的预期目标就很难实现。

本文提出了设计去中心化搜索引擎的三个目标：完整性、隐私性以及高容量（Scalability）。完整性需要确保搜索过程的执行完整性以及搜索结果不被篡改的结果完整性；隐私性确保用户的查询内容以及查询结果不被搜索引擎直接知晓，用户和搜索引擎交换的消息的数量和大小与搜索结果和提供的关键字无关；最后就是搜索引擎的性能保证。

为了实现DeSearch，本文面临三个方面的挑战，其中一些挑战来自于去中心化的环境，而其他挑战则来自于TEE的限制。首先，去中心化的环境允许执行者自由加入和离开系统，这意味着执行者随时有可能离线。其次，Intel SGX的enclave内存有限（128MB或256MB），超过这个限制的任务会触发分页机制带来的高延迟。最后，搜索服务是动态的，很难跟踪和验证从抓取到查询服务的整个搜索过程。

DESIGN

为了解决上述挑战，DeSearch的关键设计如下：

• 将搜索分解成包含多个子任务的任务流水线，每个执行者一次只负责一个任务，并且只对一小部分数据进行操作。
• 执行者是无状态的，他们从一个名为Kanban的存储服务中获取输入，然后将输出写回。Kanban是一个基于云的键值存储，提供高可用性和数据完整性。
• 通过“证人”来跟踪搜索管道内动态执行的任务的完成情况，这是一种加密的总结，记录了数据在执行者之间的正确传输。证人也是一个执行者行为的证明，这使得用户可以事后验证他们的搜索结果。

在 DESEARCH 中，执行者分为四种角色：crawlers, indexers, queriers, masters。前三个角色组成了一个完整的搜索过程，crawlers从公共来源获取数据；indexers构造倒排索引；queriers处理查询、排名和构建搜索结果。masters则是提供服务的执行者：对想要加入 DESEARCH 的 TEE 节点进行身份验证；协调执行者的任务分配以形成最少重复工作的管道； 密钥管理服务 (KMS)，允许任何人识别执行者是否是合法的 DESEARCH 成员。masters 定期在 Kanban 上发布来自合法执行者的公钥列表，以便用户可以验证他们的签名并与之通信。执行者之间通过kanban进行通信。kanban存储了执行者生成的数据，并定期创建所有当前状态的快照并将快照的摘要提交到区块链。沿着流水线的每一步，每个执行者都会产生一个“证人”，证明该执行者看到了什么，做了什么，以及数据是如何传输的。

DESEARCH 包括公共域和私有域。公共域中的执行者访问公共数据（如公共源数据）并生成共享信息（如索引）。另一方面，用户与 DESEARCH 的交互发生在私有域中，他们的通信（例如，搜索请求和响应）被加密并保密。

工作流

• 用户首先检索一个活跃的queriers列表。这个列表由masters和queriers共同维护：queriers通过签名证明来更新他们在列表中的状态；masters对状态证明的合法性进行验证。
• 用户从列表中随机选择一个querier作为领导者，并向领导者发送加密后的搜索关键词。
• 领导者寻找更多的queriers来共同处理该请求。也就是说，不同的querier拥有不同的索引部分，共同为一个用户的搜索请求服务。
• 领导者最后通过基于相关性的排名汇总结果，并向用户返回K个最相关项目的列表。一个项目包括一个链接（指向原始内容）和一个内容片段，该内容片段概括了该项目，并经常包含搜索的关键词。
• 用户最终收到搜索结果的同时还会收到“证人”。由搜索管道产生的所有证人形成一个证人树，用户可以通过从领导者证人开始，遍历该树，检查搜索过程的完整性。

CONCLUSION

本文设计了为去中心化搜索引擎设计了一个新颖的架构，文章在Related Work这一节提到了很多场景以及技术，并谈到了该设计借鉴的一些场景。也许TEE和区块链结合的故事可以拓展到更多领域。