balanced-tree-index

此crate包含与以下基本概念相关的一小部分代码

在“传统”数据结构中，二叉树使用指针创建，并使用例如红黑树自平衡策略等方法保持“近似”平衡。

然而，当二叉树具有固定大小时，并且不会动态添加或重构，则有更简单的方法将节点映射到内存中，这更紧凑且具有更好的局部性。

在此映射中，二叉树的内部节点和叶子节点按高度顺序编号，从1开始，到2^n。

                   1
           2               3
       4       5       6       7
     8   9   10 11   12 13   14 15

然后，将节点数据存储在一个包含2^n个元素的数组中。这意味着您不需要对每个节点使用 malloc，可以直接使用块存储接口访问节点成员。

这对于ORAM非常有用，因为ORAM始终使用完全平衡的二叉树。

在此方案中，使用位操作很容易找到节点的父节点、左子节点或右子节点，位操作既快速又具有常量时间。

    parent(x) := x >> 1
    left(x) := x << 1
    right(x) := (x << 1) + 1

在此方案中，0值未使用，因此可以用作哨兵值。

作为理解此方案的一种替代方法，考虑一个数字的二进制表示。

0 0 0 1 0 1 1 0 1

最高位1的位位置指示节点在树中的高度。由于在此示例中有5位在此之后，因此此节点正好在根节点下方5步。

通过读取剩余的数字，我们可以读取到达此数字的路径：首先向左，然后向右，然后向右，然后向左，然后向右。

附加操作

使用此方案，我们可以轻松地在常量时间内执行一些额外的便捷操作，这些操作在ORAM中需要执行。

• 在树中，可以通过计算节点索引的前导零的数量来计算节点的高度。英特尔为此提供了常数时间操作。
• 对于相同高度的两个节点，我们可以通过找到它们差异的最左侧位位置来计算它们的共同祖先的高度。这正好对应于它们从根节点路径分离的第一次。
• 对于不同高度的节点，我们仍然可以计算它们的共同祖先的高度，但首先需要将较深的节点的父节点取出，直到达到相同的级别，或者，在树中用随机位填充较高的节点，直到它们匹配。从特定高度的节点随机取一个子节点有很多用途。

本软件包的范围是提供特性和这些功能的实现，以及相关的在 u32 和 u64 整数类型上的实现，用于 ORAM 实现中。这是一个独立的软件包，以便代码可以共享，并且也可能在 ORAM 内存引擎中使用。

该方案还有一些其他良好的性质

• 如果向树中添加一个层级，旧索引不会失效，它们只是继续。
• 从 u32 升级到 u64 不会破坏任何东西，位操作基本上仍然按之前的方式工作。

常数时间

此代码旨在用于实现基于树的 ORAM 算法，如 Path ORAM。在某些情况下，其中一个操作是常数时间是很重要的。当代码必须提供此属性时，我们会进行说明。由于 mc-oblivious 的范围是专注于 SGX 容器，所以我们只关心 x86-64 架构。