Databases

Converge is designed to be able to support a secure, distributed, eventually consistent database as a library.

Overview

There are a lot of types of databases. Here we are concerned with what you might call indexed value stores. We have a value, and we associate it with keys on one or more indexes. Then we can look up either the key or an area of keys on the index, and return the value or values matching that key or area of keys.

The keys may be derived from the value in some way, but often they are arbitrary. When we're layering a database on converge this distinction matters, because we cannot use braids to reference any part of a value that a key is derived from. If we do, the value could change without notice.

B-tree Indexes

[B-trees] are self-balancing tree structures with a large fan-out. Variants are heavily used in databases and file systems, including copy-on-write file systems, which anything based on converge must be.

Encoding a B-tree in converge is relatively straight-forward. The root node is a [version] and each other node is a [blob]. Each node holds a list of (first key, shared key, reference) or (key, value) tuples, where the value may contain a shared key and reference.

This may be compacted by rewriting the references to the index of the reference list in the object's plaintext. While it may be tempting to sort the object references by the order of entries, this will leak significant information about which values are associated with which keys!

Another potential compaction is, for variable length keys, to include the common prefix of all the keys in a header. This provides some of the benefit of radix trees while preserving the log(n) search time of B-trees and leaking less information. However, it does open some possibility of leaking the rough number of keys with a given prefix if an attacker can insert or remove entries.

Security

Observation

This is the typical case for a backed up database, or a node participating in synchronization. The attacker is assumed to be able to see the entire history of the database, but has no control over its contents.

Given the relatively large and consistent fan-out, the attacker can likely distinguish a B-tree from other types of data. With knowledge of the application, this leaks the approximate number of keys, by the number and size of leaf nodes. The quality of this estimate may be reduced by values that reference blobs that also have similar fan-out.

While this attacker cannot associate a particular node with a set of keys (even relative to other keys), they can watch changes to similar areas over time, especially if there's a commit after every change. Batching changes muddies this leakage, one to one mappings become n to n. If there are no external references, a full rebalance (assuming it changes every node) will break continuity entirely.

Entry Modification

If the attacker can update the non-indexed part of a value and knows the key to that value, or if they can insert a value with a known key, they can locate the area of the key.

The more values an attacker can control this way, the more they insight they can gain into the structure of the data. With arbitrary insertion or modification an attacker can efficiently find the approximate boundaries of each node.

This is likewise mitigated by batching changes, though not eliminated if the attacker knows which changes contained updates to the same key. Rebalancing the tree breaks continuity (module external references).

External Reference Knowledge

If the database values include external references, related values may be determined by having nearby keys. This is especially relevant to file system use cases, as similar files are likely to be stored together, and files are likely to be external values.