Stores Actors Data Tree Downloads
AnalysisObject trees

Object trees mature

Through the hash list, objects span a tree:

3a229f... ba6eb4... 6f0146... a83e31... 409688... 3a229f... ba6eb4... 6f0146... a83e31... 2 2 0 1 0 82b79d... ...

Each node in that tree is an object, spanning its own subtree. The hash of a tree is simply the hash of its root object. Two trees with the same hash are most likely equal.

An object can obviously be referenced from more than one object. This is particularly useful for versioned data, as common subtrees can be shared:

Current version Previous version

The data tree implementation takes advantage of this.

Graph properties

Objects can only form acyclic graphs. Constructing a loop (cycle) would require constructing a hash collision.

To understand that, assume an object A that references an object B. Hence, A contains the SHA-256 sum of B. To create a back-reference from B to A, we would need to construct a new object B' containing the hash of A, and yielding the same hash as B, which is computationally infeasible.

For the same reason, an object cannot reference itself.

Objects can be referenced by more than one other object, however. In that case, the resulting structure is still a directed acyclic graph, but not a tree:

a5195c... a5195c... a5195c... Directed acyclic graph Corresponding tree

Since objects are immutable, we can (conceptually) duplicate such objects, and draw a corresponding tree. Every use of the object is then regarded as a separate instance, that just happens to have the same content.