# The unordered set collection in the Holochain DHT

The unordered set is one of the fundamental data structures provided by most modern languages. It is characterised by the following operations

- `insert(item)` Inserts a new item into the set. Will de-dup if required.
- `remove(item)` Remove an item from the set
- `contains(item)` Returns a boolean if the given item is contained in the set
- `items()` Return all items in the set. This of course has no ordering requirements and will contain no duplicates.

Other set operations such as unions etc will not be considered at this time.

## First approach

Sets are commonly implemented using search trees or hash tables and a similar approach is proposed for storing in the Holochain DHT. The hash space should be partitioned into smaller buckets which are not expected to contain more entries than can be processed by a single agent. This is similar to how entries in the DHT are distributed to different agents but with no redundancy factor.

This introduces a trade-off between having many buckets with few entries and few buckets with many entries. Both have drawbacks depending on the usage requirements. Let $B$ be the number of bits in the prefix of the hash allocated to the bucket identifier. There will be $N_{buckets} = 2^B$ buckets. For the 256 bit Hashes used by Holochain the maximum number of entries per bucket is therefore $E_{max} = 2^{(256 - B)}$. This upper bound is still extremely large for any reasonable number of buckets (in the order of $10^{70}$). What should actually be taken into consideration is the expected number of items per bucket which is, thanks to the uniform distribution, the expected number of items divided by the number of buckets.

Let us take the example of Twitter's $260 * 10^6$ registered users. These users could be kept track of using a Set. By varying the prefix size you can see the expected number of users linked per bucket.

$B$ | $N_{buckets}$ | $E_{avg}$
----- | ----- | -----
0 | 1 | 260000000
4 | 16 | 65000000
8 | 256 | 1015625
10 | 1024 | 253906
12 | 4096 | 63477

With a reasonable number of buckets it is foreseeable how a twitter scale application could exist on Holochain. 4k buckets is not an unreasonable number to scan (and this would be an unusual operation. How often do you retrieve all twitter users?) and 63k entries is likely small enough to fit in WASM memory. Furthermore very few applications are at the scale of twitter so these numbers should be vastly smaller in most cases.

### Operations

- `insert`
- Hash the entry
- calculate the correct bucket based on the prefix
- link the entry to the bucket

- `remove`
- hash the entry
- calculate the correct bucket
- mark the link between bucket and entry as deleted

- `contains`
- hash the entry
- calculate the correct bucket
- retrieve all links
- scan links for existence of hash

(Note this can be performed in O(1) if it is known the entry does not exist unless it is in the set. Then )

- `items`
- Iterate over buckets
- retrieve links from each bucket

## Adaptive Approach

The success and longeivity of bitcoin can be in part attributed to its dynamic difficulty adjustment. One could argue that truly scaleable distributed applications required some degree of dynamism in order to successfully bootstrap and then scale.

The approach suggested above required some estimation on the part of the DNA developer of the number of users such that a sensible trade-off bucket size could be selected. This will likely be too many buckets at the start of the hApps life and perhaps not enough if there is strong adoption. An ideal set would increase the number of buckets only when it is required to do so to keep link numbers below some threshold to prevent DHT hotspots and retrieval issues.

The dynamic set should start with $B=0$ and when an agents detects there is more than some threshold number of links when trying to insert, they instead create the next layer bucket and insert there. Of course this is susceptible to the classic partition attacks so something needs to be figured out there.

The resulting data structure is a binary tree of buckets that span the hash space with increasing granularity. Early entries will be added further up the tree and later ones further down. As a result the `insert`, `delete` and `contains` operations become $O(log(n))$ as they require traversal down a single path in the tree. The `items` opertaions also becomes more expensive as it has to scan the links from all nodes in the tree.

### Operations

- `insert`
- Hash the entry
- go to the first bucket
- check the bucket, if non-full insert there
- else figure out the next bucket based on the hash
- repeat above 3 steps until non-full bucket found

- `remove`
- Hash the entry
- go to the first bucket
- check the bucket to see if entry is there. If so remove it
- else figure out the next bucket based on the hash
- If end of tree reached then abort

- `contains`
- Hash the entry
- go to the first bucket
- check the bucket to see if entry is there
- else figure out the next bucket based on the hash
- If end of tree reached then return false

- `items`
- traverse tree
- retrieve links from each bucket and collect

### Summary

It is important that such a set collection dynamically scales with the number of items added. This presents a possible approach however it suffers from the classic attack where a partitioned node is out of sync with the data structure, can add entries to the root, and upon rejoining will effectively flood it with entries. By repeating this it is possible to add an infinite number of entries to the root, thus making the data structure useless.

The solution to this problem requires some type of consensus which is beyond the scope of this document.