零点课堂 | 加密区块链数据库详解（第一部分）

taotao 深度 2021年6月25日
8.81K 0

区块链数据库是将区块链和数据库的属性结合起来的存储系统，如去中心化、抗篡改、低查询延迟和支持复杂查询。随着它们得到更广泛的采用，人们对它们管理的数据的保密性的担忧也会增加。已经有多个项目使用区块链来存储敏感数据，例如电子医疗保健和财务记录，法律文件和客户数据。

在本文中，我们讨论了我们的新论文《加密的区块链数据库》，其中我们设计了端到端加密的区块链数据库，以支持需要存储和查询敏感数据的去中心化应用程序。特别是我们专注于我们所称的区块链加密多映射（EMM），它可用于实例化各种NoSQL区块链数据库，如键值存储或文档数据库。

密码学领域的重点是端到端加密数据库的设计，更广泛地说，是对加密数据的搜索问题，这一领域被称为加密搜索。关于这个领域的介绍，请参阅布朗大学加密系统实验室的这一系列博客文章。特别是第五篇文章，描述了一个标准的/集中的EMM的构造（在这篇文章中称为加密数据库（EDB））。

加密多重映射

NoSQL数据库由于其简单性、可扩展性和高性能保证，近年来在数据库行业中越来越突出。各种NoSQL数据库，如键值存储（例如DynamoDB）和文档数据库（例如MongoDB），可以用多映射数据结构实例化。多重映射是将标签映射到值元组的字典的泛化。它们支持get和put操作，在给定标签的情况下，可以存储或检索与标签相关联的值的元组。加密多映射（EMM）是一种端到端的加密多映射，它支持get和put操作，但对加密数据进行过度加密。由于多个映射可以用来表示NoSQL数据库，因此设计区块链加密的NoSQL数据库本质上与设计区块链EMM相同。

旧版友好

设计区块链EMM有两种主要方法。首先是设计一个专门支持EMM的新区块链。这种方法的优势在于可以共同设计EMM和区块链以优化性能。第二种方法是设计一种对传统友好的解决方案，因为它可以在已有的区块链之上使用。这种方法的优势在于，区块链EMM可以建立在多个平台之上，无需建立新的区块链。然而，第二种方法存在一些挑战：

  1. 我们如何在区块链上存储数据结构？特别是，如何存储加密的多映射数据结构？大多数现有区块链旨在存储金融交易或智能合约的状态，但不是任意的数据结构。
    2. 由于区块链在设计上是防篡改的，我们如何更新EMM，尤其是如何从中添加/删除数据？

另外一个简单的解决方案如下：每次更新时，我们都可以从区块链读取整个EMM，进行必要的更改，然后将其写回一个全新的EMM。这是查询正确性的理想解决方案，因为每个查询总是从最新的EMM中读取。然而，这种解决方案对于更新操作效率极低，因为每次更新操作都必须读取和写回整个结构。因此，我们还需要考虑以下第三个挑战：

如何针对查询和更新复杂性设计高效的区块链EMM？

在描述我们的区块链EMM构建之前，让我们先讨论一下第一个挑战——第二个和第三个挑战更为棘手，因此我们将在详细描述构建本身时解决它们。

区块链上存储任意数据结构

大多数区块链（例如比特币，以太坊，Algorand）都允许用户在交易中存储任意数据。由于在单个事务中只能存储有限数量的数据，因此必须在多个事务中拆分大型数据结构。然后问题变成：

我们如何将这些事务链接在一起以构建任意数据结构？

要回答这个问题，请首先注意，可以通过将以前事务的“地址”存储在较新的事务中来链接事务。利用这一特性，我们将在区块链顶部叠加一个数据结构，这样我们就可以更新和查询数据结构，而不必对后端（区块链）进行任何修改。在下面，我们提供了一个简单的示例，演示如何叠加一个链接列表。为了在区块链上存储一个值为V=（v1，…，vn）的列表，我们执行以下操作（请参阅图1了解此过程的说明）：

  1. 将每个值vi与存储vi-1的先前事务的地址ri-1连接起来。
    2. 使用vi || ri-1创建一个新交易，并将其发送到区块链。这将生成ri，即新交易的地址。
    3. 对所有值重复此操作。
    4. 最后，存储与客户的最后一笔交易的地址rn。

要读取值，请执行以下操作：

  1. 将rn发送到区块链以恢复值vn和地址rn-1。
    2. 然后使用rn-1恢复vn-1和rn-2。
  2. 继续此过程，直到已读取所有值。

类似地，我们可以在区块链上叠加更复杂的数据结构，例如二叉树。这可以通过将两个地址连接到每个值来完成：一个用于其左子项，一个用于其右子项。如图2所示。

智能合约的局限性

对于支持智能合约的区块链，另一种方法可能是将整个数据结构存储为智能合约的状态，并将查询和更新操作作为智能合约来实现。不幸的是，这种方法有两个主要的局限性。首先它不是通用的，因为（1）许多区块链不支持智能合约（例如比特币），以及（2）许多智能合约平台不维护跨交易的状态（例如Algorand）。第二个限制与使用此类平台的成本有关。事实上，智能合约平台不仅需要支付存储数据和代码的费用，还需要支付执行代码的费用；代码越复杂，成本就越高。请注意，我们将数据结构叠加在区块链之上的第一种方法不仅通用，而且成本更低，因为我们可以将数据存储在交易中而不是智能合约，并且不需要在区块链上执行任何代码 。

在本系列的下一部分中，我们将描述三种在区块链上存储动态emm的方案，每种方案在查询、添加和删除效率之间实现了不同的权衡。

本文由 零点财经 作者：tao 发表，其版权均为 零点财经 所有，文章内容系作者个人观点，不代表 零点财经 对观点赞同或支持。如需转载，请注明文章来源。
分享生成图片
♥赞42

相关文章

发表回复

零点课堂 | 加密区块链数据库详解（第一部分）

2021-06-25 10:22:44

区块链数据库是将区块链和数据库的属性结合起来的存储系统，如去中心化、抗篡改、低查询延迟和支持复杂查询。随着它们得到更广泛的采用，人们对它们管理的数据的保密性的担忧也会增加。已经有多个项目使用区块链来存储敏感数据，例如电子医疗保健和财务记录，法律文件和客户数据。

在本文中，我们讨论了我们的新论文《加密的区块链数据库》，其中我们设计了端到端加密的区块链数据库，以支持需要存储和查询敏感数据的去中心化应用程序。特别是我们专注于我们所称的区块链加密多映射（EMM），它可用于实例化各种NoSQL区块链数据库，如键值存储或文档数据库。

密码学领域的重点是端到端加密数据库的设计，更广泛地说，是对加密数据的搜索问题，这一领域被称为加密搜索。关于这个领域的介绍，请参阅布朗大学加密系统实验室的这一系列博客文章。特别是第五篇文章，描述了一个标准的/集中的EMM的构造（在这篇文章中称为加密数据库（EDB））。

加密多重映射

NoSQL数据库由于其简单性、可扩展性和高性能保证，近年来在数据库行业中越来越突出。各种NoSQL数据库，如键值存储（例如DynamoDB）和文档数据库（例如MongoDB），可以用多映射数据结构实例化。多重映射是将标签映射到值元组的字典的泛化。它们支持get和put操作，在给定标签的情况下，可以存储或检索与标签相关联的值的元组。加密多映射（EMM）是一种端到端的加密多映射，它支持get和put操作，但对加密数据进行过度加密。由于多个映射可以用来表示NoSQL数据库，因此设计区块链加密的NoSQL数据库本质上与设计区块链EMM相同。

旧版友好

设计区块链EMM有两种主要方法。首先是设计一个专门支持EMM的新区块链。这种方法的优势在于可以共同设计EMM和区块链以优化性能。第二种方法是设计一种对传统友好的解决方案，因为它可以在已有的区块链之上使用。这种方法的优势在于，区块链EMM可以建立在多个平台之上，无需建立新的区块链。然而，第二种方法存在一些挑战：

  1. 我们如何在区块链上存储数据结构？特别是，如何存储加密的多映射数据结构？大多数现有区块链旨在存储金融交易或智能合约的状态，但不是任意的数据结构。
    2. 由于区块链在设计上是防篡改的，我们如何更新EMM，尤其是如何从中添加/删除数据？

另外一个简单的解决方案如下：每次更新时，我们都可以从区块链读取整个EMM，进行必要的更改，然后将其写回一个全新的EMM。这是查询正确性的理想解决方案，因为每个查询总是从最新的EMM中读取。然而，这种解决方案对于更新操作效率极低，因为每次更新操作都必须读取和写回整个结构。因此，我们还需要考虑以下第三个挑战：

如何针对查询和更新复杂性设计高效的区块链EMM？

在描述我们的区块链EMM构建之前，让我们先讨论一下第一个挑战——第二个和第三个挑战更为棘手，因此我们将在详细描述构建本身时解决它们。

区块链上存储任意数据结构

大多数区块链（例如比特币，以太坊，Algorand）都允许用户在交易中存储任意数据。由于在单个事务中只能存储有限数量的数据，因此必须在多个事务中拆分大型数据结构。然后问题变成：

我们如何将这些事务链接在一起以构建任意数据结构？

要回答这个问题，请首先注意，可以通过将以前事务的“地址”存储在较新的事务中来链接事务。利用这一特性，我们将在区块链顶部叠加一个数据结构，这样我们就可以更新和查询数据结构，而不必对后端（区块链）进行任何修改。在下面，我们提供了一个简单的示例，演示如何叠加一个链接列表。为了在区块链上存储一个值为V=（v1，…，vn）的列表，我们执行以下操作（请参阅图1了解此过程的说明）：

  1. 将每个值vi与存储vi-1的先前事务的地址ri-1连接起来。
    2. 使用vi || ri-1创建一个新交易，并将其发送到区块链。这将生成ri，即新交易的地址。
    3. 对所有值重复此操作。
    4. 最后，存储与客户的最后一笔交易的地址rn。

要读取值，请执行以下操作：

  1. 将rn发送到区块链以恢复值vn和地址rn-1。
    2. 然后使用rn-1恢复vn-1和rn-2。
  2. 继续此过程，直到已读取所有值。

类似地，我们可以在区块链上叠加更复杂的数据结构，例如二叉树。这可以通过将两个地址连接到每个值来完成：一个用于其左子项，一个用于其右子项。如图2所示。

智能合约的局限性

对于支持智能合约的区块链，另一种方法可能是将整个数据结构存储为智能合约的状态，并将查询和更新操作作为智能合约来实现。不幸的是，这种方法有两个主要的局限性。首先它不是通用的，因为（1）许多区块链不支持智能合约（例如比特币），以及（2）许多智能合约平台不维护跨交易的状态（例如Algorand）。第二个限制与使用此类平台的成本有关。事实上，智能合约平台不仅需要支付存储数据和代码的费用，还需要支付执行代码的费用；代码越复杂，成本就越高。请注意，我们将数据结构叠加在区块链之上的第一种方法不仅通用，而且成本更低，因为我们可以将数据存储在交易中而不是智能合约，并且不需要在区块链上执行任何代码 。

在本系列的下一部分中，我们将描述三种在区块链上存储动态emm的方案，每种方案在查询、添加和删除效率之间实现了不同的权衡。