在加密区块链数据库系列文章的第二部分中，我们将介绍三种在区块链上存储动态加密多映射（EMM）的方案，每种方案在查询、添加和删除效率之间实现了不同的权衡。
基于列表的方案A List-Based Scheme（LSX）
回想一下，多映射是多个标签/值元组的集合。在这种结构中，我们将与每个标签相关联的值存储到区块链上单独的逻辑链表中。但是为了保证机密性，我们在将每个与前一个地址连接的值添加到右链接列表之前对其进行加密。精确地，给定要添加到标签l的元组（v1，…，vn），对于每个i∈[1，n]，我们将EncK（vi || ri-1）添加到区块链。对于第一个值，ri-1是l的链表的当前头的地址。为了实现动态性，我们使用了延迟删除，即所有添加和删除的值都标记为添加（+）或删除（-），并且仅在查询时通过从输出中删除标记为删除的值来执行删除。有关LSX的说明，请参见图1 –为清楚起见，我们省略了图中的值和地址的加密。
效率：很容易看出LSX具有最佳的添加和删除时间复杂度：对于每个操作，我们只写入与元组大小一样多的值。然而，它的查询复杂度在更新次数上是线性的。特别是，在每个查询中，我们读取所有添加或删除的值。如果所有更新操作都是加法操作，则此方案具有最佳的查询复杂性，但是如果大多数更新是删除操作，则该方案将产生不小的查询开销。该方案还有另一个缺点：添加和删除操作都需要在用户和区块链之间进行线性数量的写入轮数（以元组的大小为单位）。这是由于以下事实：在计算出vi-1的地址之前，无法写入值vi，因此必须在单独的写入轮数中写入每个值。
计算写轮数很重要，因为由于挖掘和稳定，区块链的写操作要比区块链的读操作花费更长的时间。因此，尽可能多地并行化写入变得很重要。我们称此指标为稳定的复杂性，因为写入所需的时间取决于交易稳定所需的时间–例如，对于比特币，写入时间最多可为60分钟（一个区块必须在链的最长链至少要达到6个区块才能变得不可变）。
接下来，我们描述一种基于树的方案，该方案将稳定复杂度从线性提高到对数。
基于树的方案A Tree-Based Scheme（TRX）
在此方案中，我们修改了值的组织方式，目的是减少存储值之前所需的地址数量。给定要添加/删除的元组，我们将完整的二叉树叠加，而不是在链上叠加链表。这使我们能够并行化在树的相同深度处的所有值的插入。此外，我们还链接了跨多个添加/删除操作构建的树的根。注意，这种简单的结构更改将稳定复杂度从线性降低到了对数。
由于上述两种方案的查询复杂度与添加/删除值的数量呈线性关系（当大多数更新都是删除操作时，这可能很糟糕），因此我们现在描述一种方案，该方案将查询复杂度提高到最佳，但删除的代价有点昂贵。
基于区块的方案A Patch-Based Scheme（PAX）
注意，LSX的查询复杂度不是最优的，因为我们不知道遍历链接列表1时删除的值，因此我们最终读取所有值，而不管它们是否被删除。为了解决这个问题，我们将额外的数据结构（称为区块）附加到链接列表的顶部。块程序是地址对，它将允许查询算法跳过已删除的值。例如假设我们有以下链接列表：
删除v2时，我们创建一个块（addr（v3）addr（v1）），删除v4时，我们创建另一个块（addr（v5）addr（v3））。目前，我们无需担心块的存储位置和存储方式。但是给定了这些块，查询算法可以轻松跳过已删除的值v2和v4：从v5起，它将使用第二个块跳转到v3，从v3起，它将使用第一个块跳转到v1。
现在假设v3也被删除了。在这种情况下，我们将创建一个新块（addr（v5）addr（v1）），该块可帮助查询算法跳过所有值v2，v3和v4。
这有两个问题：
1. v5中有两个块：一个进入v3，一个进入v1。为了使查询正确跳过已删除的值，应使用（v5v1）而不是（v5v3）。
2. 块的数量等于已删除值的数量，这意味着搜索块的成本与使用延迟删除一样昂贵。
为了解决这个问题，我们需要确保我们清理（或删除）旧块。准确地说，删除v3后，我们应该同时删除（v5v3）和（v3v1）。（v5v3）的删除保证了正确性，而（v3v1）的删除则保证了效率，因为剩下的色块数量最多为未删除值的数量。
块数据结构：由于块的数量可能很大，它们不能存储在本地，也必须存储在区块链上。我们可以在链表或树中组织块。无论我们决定如何，我们都将其称为块结构。请注意，无论我们如何在区块链上组织块结构，从中删除块的要求都会带来鸡与蛋的问题：从链接列表中删除多图值需要从块结构中删除块。那么我们应该修补块结构吗？
我们使用另一种称为“写入即复制”的技术来解决这个难题。在高层次上，该技术复制“节点”，并对副本进行修改，而不是修改原始节点。我们用一个例子来解释。假设我们将块结构表示为链表。此外，假设块结构中有100个块是从P1…P100。
要删除P2，我们需要使P3指向P1。但是由于P3存储在区块链上，因此不能将其更改为指向P1。因此，我们创建了P3的拷贝P′3，这样它存储的块数据与P3相同，指向P1。但是，这要求P4指向副本P′3，由于它也存储在区块链上，因此无法做到这一点。因此，创建了P4的副本P′4。这个过程会传播到链表的头部，从P3到P100的每个节点都会被它的副本所取代。
显然，这是非常昂贵的：删除块结构链接列表中很深的块会触发所有后续块的重写。因此，我们将块结构表示为一个平衡的二叉树，在这种情况下，一个块的删除只会触发与树高度相同数量的块的创建。
效率：令| MM [l] | 是当前与多映射中的标签l相关联的值的数量。换句话说，| MM [l] | 表示l的未删除值的数量。我们不会在这里争论，但是不难发现，块结构中的块数量最多为| MM [l] |。由于查询算法现在可以使用块跳过已删除的值，并且搜索块的成本不高，因此查询的时间复杂度为O（| MM [l] |），这是最佳的。加法运算的复杂度与以前相同，因此也是最佳的。删除复杂度为O（| v | log | MM [l] |），其中| v | 是要删除的值的数量。这是因为对于每个删除的值，新的块会插入到块树中和/或删除旧的块会花费（log | MM [l] |）时间。
稳定的复杂性：由于相加操作将值作为链接列表相加（与LSX中相同），所以相加的稳定复杂度为O（| v |）。但是，删除的稳定复杂度为O（log | MM [l] |），因为可以并行进行在块树的同一级别进行的所有修改。
结论
我们讨论了如何将端到端加密集成到区块链数据库中，更确切地说，讨论了将端到端加密多映射存储在区块链上的方法。由于多映射具有足够的表现力来表示键值存储，因此这提供了一种将键值存储存储在区块链上的方法。我们讨论了三种在查询，添加和删除效率之间实现不同权衡的EMM构造。但是还有一些有趣的开放问题。
我们发现，当TRX具有最佳的添加/删除时间复杂度时，TRX具有较差的查询复杂度。另一方面，PAX实现了良好的查询复杂性，但稳定化添加/删除复杂性较差。这引起了以下自然问题：我们能不能设计一个既能做到两全其美的方案？
我们还在论文中表明LSX和TRX都可以使用打包，这允许将多个元组值存储在单个事务中。对于允许进行大笔交易的区块链，打包可以提高性能。不幸的是，我们的PAX构造不支持包装，因此一个自然的问题是：我们可以在PAX中加入打包吗？
---------------------------------------------------------
原文作者：Daniel Adkins, Archita Agarwal, Seny Kamara, Tarik Moataz
译者：链三丰
译文出处：http://bitoken.world
----------------------------------------------------------------------
